じゃんけんが終わるまでの平均回数を求める

じゃんけんをするときに人数が多いとあいこが増えて、なかなか終わらなかった経験があると思います
\(n\)人でじゃんけんした時に、ただ1人の勝者が決まるまでの回数の期待値(平均回数)を計算してみました
また大人数でもすぐに勝負がつくゲーマーじゃんけんも取り上げています

この記事ではある人がグー・チョキ・パーを出す確率はそれぞれ等しいとします

じゃんけん

まず結果が知りたい人のために最初にグラフを載せておきます
横軸が人数、縦軸がただ一人の勝者が決まるまでのじゃんけんの平均回数です
\(10\)人で約\(24\)回、\(15\)人で約\(159\)回と、人数が増えると回数の期待値が急激に増えていくのがわかると思います

人数	回数の期待値
1	0
2	1.5
3	2.25
4	3.21428571429
5	4.48571428571
6	6.2198156682
7	8.64673579109
8	12.1044437994
9	17.0919352918
10	24.3495977585
11	34.9794609867
12	50.6250205168
13	73.7403531089
14	107.993133673
15	158.86844073

求め方

求め方を簡単に説明します
\(E_n\)を残り\(n\)人いるときの残り回数の期待値とします
\(P(n, k)\)を残り\(n\)人いるときに\(k\)人が勝つ確率とします(\(k=n\)のときはあいこ)

期待値を条件付き期待値を使って書き直すと以下の式が成り立ちます
\(E_n = \sum_{k=1}^n P(n, k)(E_k + 1) = 1 + \sum_{k=1}^n P(n, k)E_k\)

\(P(n, k)\)は勝った人の手がグー・チョキ・パーの3通り、それに\(n\)人から\(k\)人の選び方の数をかけて、全体の場合の数で割ると以下のような式になります
$$P(n, k) = \frac{3 \times \binom{n}{k}}{3^n}$$

残り\(1\)人の時もうじゃんけんは終わっているので\(E_1 = 0\)
以上より\(E_n\)を\(n\)が小さい方から順に計算することができます

試しに\(E_2\)を計算してみます
$$E_2 = 1 + \sum_{k=1}^2 P(2, k)E_k = 1 + P(2, 1)E_1 + P(2, 2)E_2$$ \(E_1=0\)を使いつつ式変形すると以下のようになり、\(2\)人でやるじゃんけんは平均\(1.5\)回で終了することがわかります
$$E_2=\frac{1}{1 - P(2, 2)} = \frac{1}{1 - \frac{1}{3}}=\frac{3}{2}$$

ゲーマーじゃんけん

• C: ゲーマーじゃんけん - dwangoプログラミングコンテスト | AtCoder

上で見たように、普通のじゃんけんでは人数が増えるとなかなか終わりません
ゲーマーじゃんけんという人数が多くてもすぐに勝敗が決まるじゃんけんの亜種があります

基本的なルールとしては一番出している人数が少ない手が勝ちます
一番出している人数が少ない手が複数あった場合には、それらの手の間で普通のじゃんけんの手の強弱によって勝敗が決まります

以下のグラフを見るとわかるように、ゲーマーじゃんけんは人数が増えても必要な回数があまり増えず、たとえ\(100\)人でやっても平均約\(3.7\)回で勝者が決まります

人数	回数の期待値
1	0
2	1.5
3	1.5
4	1.38461538462
5	1.3875
6	1.5
7	1.66483516484
8	1.8325357168
9	2.03065384615
10	2.11280299063

求め方

基本的には普通のじゃんけんと同様に以下の式を計算すればよいです
\(E_n = \sum_{k=1}^n P(n, k)(E_k + 1) = 1 + \sum_{k=1}^n P(n, k)E_k\)
ただし\(P(n, k)\)の計算が難しくなります
以下の式はもうちょっと整理できそうな気もしますが気力が尽きたので、もっとよい方法があったら教えていただけると嬉しいです

まず人数が最小の手が\(1\)種類で勝利する場合を考えます
この時残りの手は\(1\)種類と\(2\)種類の\(2\)通りが考えられます
この時の確率をそれぞれ\(P_{a, 1}(n, k), P_{a, 2}(n, k)\)とおきます
\(P_{a, 1}(n, k)\)は勝利する手が\(3\)種類、残りの手が\(2\)種類、人の選び方が\(\binom{n}{k}\)通り考えられるので以下のような式になります
$$P_{a, 1}(n, k) = \frac{3 \times 2 \times \binom{n}{k}}{3^n}$$同様に\(P_{a, 2}(n, k)\)は、\(k\)人の次に多い手の人数を\(m\)としたとき以下のような式になります
$$P_{a, 2}(n, k) = \sum_{m = k + 1}^{n - 2k - 1} \frac{3 \times \binom{n}{k} \times \binom{n - k}{m}}{3^n}$$

次に人数が最小の手が\(2\)種類あった場合を考えます
この時の確率を\(P_{b}(n, k)\)とします
勝利する手が\(3\)種類、人の選び方が\(\binom{n}{k}\)通りかける\(\binom{n - k}{k}\)通り考えられるので、以下のような式になります
$$P_{b}(n, k)=\begin{cases} \Large \frac{3 \times \binom{n}{k} \times \binom{n - k}{k}}{3^n} & \text{($3k < n$ or $n = 2k$)} \\ 0 & \text{(otherwise)}\end{cases}$$

以上より\(P(n, k) = P_{a, 1}(n, k) + P_{a, 2}(n, k) + P_{b}(n, k)\)となるので、\(E_n\)が計算できます

おまけ: グーチョキパーで3グループに分かれるときの、均等に分かれるまでの平均回数

グー・チョキ・パーのどれを出したかで3グループに分かれるのをやったことがあると思いますが、うまく均等に分かれるまでの回数の期待値を求めます
人数が\(3\)で割り切れない時は、たとえば\(5\)人の時は\((1, 2, 2)\)人のように余りができるだけ均等に分かれた時終了とします
均等に分かれて終了するかうまく分かれずに繰り返すかのどちらかなので、\(n\)人の時の期待値を\(E_n\)、終了確率を\(P(n)\)としたとき\(E_n = \frac{1}{P(n)}\)と簡単に計算できます
グラフにすると以下のようになり、\(3\)の倍数の人数の時は均等に分かれづらいことがわかります

人数	回数の期待値
1	0
2	1.5
3	4.5
4	2.25
5	2.7
6	8.1
7	3.47142857143
8	3.90535714286
9	11.7160714286
10	4.68642857143

\(P(n)\)の式は以下のようになっています
$$P(n)= \LARGE\begin{cases}
\frac{\binom{n}{\frac{1}{3}n} \times \binom{n - \frac{1}{3}n}{\frac{1}{3}n}}{3^n} & \text{($n \equiv 0 \pmod 3$)} \\
\frac{3 \times\binom{n}{\left\lfloor\frac{1}{3}n\right\rfloor} \times \binom{n - \left\lfloor\frac{1}{3}n\right\rfloor}{\left\lfloor\frac{1}{2}\left(n - \left\lfloor\frac{1}{3}n\right\rfloor\right)\right\rfloor}}{3^n} & \text{(otherwise)}
\end{cases}$$

参考

• 期待値と条件付確率 - math314のブログ
• １人を選ぶのに何回じゃんけんしたらよいの？

図を書くのに使ったPythonのソースコード

じゃんけん

# -*- coding: utf-8 -*-
import math,string,itertools,fractions,heapq,collections,re,array,bisect
from pylab import *

def make_comb_dp(n):
    dp = [[0] * (n + 1) for i in xrange(n + 1)]
    for i in xrange(n + 1):
        dp[i][0] = 1
        dp[i][i] = 1
    for i in xrange(2, n + 1):
        for j in xrange(1, i):
            dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
    return dp

N = 15
comb = make_comb_dp(N)

dp = [0] * (N + 1)
for i in xrange(2, N + 1):
    Z = 0
    dp[i] += 1
    
    for j in xrange(1, i):
        prob = 3.0 * comb[i][j] / (3 ** i)
        dp[i] += prob * dp[j]
        Z += prob
    
    if Z != 0:
        dp[i] /= Z

for i, e in enumerate(dp[1:], 1):
    print '|{}|{}|'.format(i, e)

plot(dp[1:], lw=4)
xticks(range(15), range(1, 16))
xlabel('$n$')
ylabel('$E_n$')
show()

ゲーマーじゃんけん

# -*- coding: utf-8 -*-
import math,string,itertools,fractions,heapq,collections,re,array,bisect
from pylab import *

def n():
    return int(raw_input())

def make_comb_dp(n):
    dp = [[0] * (n + 1) for i in xrange(n + 1)]
    for i in xrange(n + 1):
        dp[i][0] = 1
        dp[i][i] = 1
    for i in xrange(2, n + 1):
        for j in xrange(1, i):
            dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
    return dp

N = 100
comb = make_comb_dp(N)

dp = [0] * (N + 1)
for i in xrange(2, N + 1):
    D =  1.0  / (3 ** i)
    Z = 0
    dp[i] += 1
    
    for j in xrange(1, (i + 1) / 2):
        prob = 3 * 2 * comb[i][j] * D
        for k in xrange(j + 1, (i - j) / 2 + 1):
            prob += 3 * comb[i][j] * comb[i - j][k] * D * (1 if k == i - j - k else 2)
        dp[i] += prob * dp[j]
        Z += prob
    
    for j in xrange(1, i + 1):
        if j < i - 2 * j or i - 2 * j == 0:
            prob = 3 * comb[i][j] * comb[i - j][j] * D
            dp[i] += prob * dp[j]
            Z += prob
    
    if Z != 0:
        dp[i] /= Z

for i, e in enumerate(dp[1:], 1):
    print '|{}|{}|'.format(i, e)

plot(dp[1:], lw=4)
xticks(range(0, N, 10), range(1, N + 1, 10))
xlabel('$n$')
ylabel('$E_n$')
xlim((0, N - 1))
show()

グーチョキパーで3グループに均等に分かれる

# -*- coding: utf-8 -*-
import math,string,itertools,fractions,heapq,collections,re,array,bisect
from pylab import *

def n():
    return int(raw_input())

def make_comb_dp(n):
    dp = [[0] * (n + 1) for i in xrange(n + 1)]
    for i in xrange(n + 1):
        dp[i][0] = 1
        dp[i][i] = 1
    for i in xrange(2, n + 1):
        for j in xrange(1, i):
            dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
    return dp

N = 15
comb = make_comb_dp(N)

expect = [0] * (N + 1)
for i in xrange(2, N + 1):
    if i % 3 == 0:
        expect[i] = (3.0 ** i) / (comb[i][i / 3] * comb[i - i / 3][i / 3])
    else:
        expect[i] = (3.0 ** i) / (3 * comb[i][i / 3] * comb[i - i / 3][(i - i / 3) / 2])

for i, e in enumerate(expect[1:], 1):
    print '|{}|{}|'.format(i, e)

plot(expect[1:], lw=4)
xticks(range(0, N), range(1, N + 1))
xlabel('$n$')
ylabel('$E_n$')
xlim((0, N - 1))
show()