ジャンケンで決着がつくまでの回数（3）

数学

代数的に期待値を求めよう。
n人でジャンケンして決着がつくまでの回数の期待値をE(n)とする。


2人の場合、
どちらかが勝つ確率が2/3、あいこの確率が1/3だから、
1回で決着がつく確率は2/3、
2回で決着がつく確率は1/3 * 2/3 = 2/9、
3回で決着がつく確率は1/3 * 1/3 * 2/3 = 2/27、
となる。
期待値は、
E(2) = 1 * 2/3 + 2 * 2/9 + 3 * 2/27 + ... = 3/2
となる。


3人の場合、
1人が残る確率は1/3、2人が残る確率は1/3、あいこの確率は1/3。
1回で決着がつく確率は1/3、
2回で決着がつく確率は、
3人→3人→1人と3人→2人→1人のパターンがあるから、
1/3 * 1/3 + 1/3 * 2/3 = 1/3、
これ以降はややこしい。


こういう場合の常套手段で、
最初に3人が残ったら、そのあとに決着がつくまでの回数の期待値はE(3)、
などと考えると、

E(3) = 1/3 + 1/3 * (E(2) + 1) + 1/3 * (E(3) + 1)

となる。
E(1) = 0
と考えて、
n人でジャンケンして、m人残る確率をP(n, m)と表すと、

E(n) = P(n, 1)(E(1) + 1) + ... + P(n, n)(E(n) + 1)

ここで、

P(n, m) = (nCm - 2) / 3n (m < n)
P(n, n) = 1 - P(n, 1) - ... - P(n, n-1)

整理すると、

(P(n, 1) + ... + P(n, n-1))E(n) = 1 + P(n, 1)E(n) + ... + P(n, n-1)E(n-1)

となる。