最後の1人が決まるまでジャンケンするゲーム

給食ジャンケン問題

給食で出されるデザートが余っているとき, 希望者が先生とジャンケンをして最後まで先生に勝ち続けた人がそのデザートをもらうことができる, といったことがよく行われる. 同種のジャンケンでは, 誰もやりたがらない委員が決まらないことに業を煮やした担任が行うジャンケン, 何かのイベントで景品をかけた司会者と参加者とのジャンケン等もある. 似たような問題として, 複数枚のコインを投げ, 表が出たコインだけを残して再度投げるというのを繰り返すゲームを考えることもできる. そこで, このようなゲームにおいて何回試行が続くだろうかという疑問が生じる. 給食ジャンケンの例でいうと, デザートをもらえる人が決まるまで何回くらいジャンケンが行われるだろうかというのを知りたいのである. つまり次のような問題を考えよう:

この問題, 例えば給食ジャンケンでは, 勝った人だけが残り続けるとすると$p=1/3$である. 1回のジャンケンで残る人数の期待値はそれまでの人数の1/3なので, $N(1/3{)}^n\le a$となる最小の$n$が求める期待値に思えるが, そうはならない.

マルコフ連鎖の設定

$i\ge j$, $i,j=0,1,2,\dots$に対し, $p_{ij}=\left(\begin{array}{c}i\\ j\end{array}\right)p^j(1-p{)}^{i-j}={}_i{\text{C}}_j{p}^j(1-p{)}^{i-j}$とおく. 可測空間$(\mathrm{\Omega },\mathcal{F})$上の$\{0,1,2,\dots \}$-値可測関数の列$X_0,X_1,\dots$に対し,
$$\begin{array}{r}{P}_i(X_0=i_0,X_1=i_1,\dots ,X_n=i_n)={\delta }_{i{i}_0}{p}_{i_0{i}_1}{p}_{i_1{i}_2}\dots p_{i_{n-1}{i}_n},i=0,1,2,\dots \end{array}$$
で定める. ただし, ${\delta }_{ij}$はクロネッカーのデルタとする. また$n=0,1,2,\dots$に対し, ${\mathcal{F}}_n=\sigma (X_0,X_1,\dots ,X_n)$とおく. このとき, $(X_n{)}_{n\ge 0}$は$(\mathrm{\Omega },\mathcal{F},({\mathcal{F}}_n),(P_n))$上で定義されたマルコフ連鎖であり, $X_n$は問題1の時刻$n$における粒子数を表す.

$$\begin{array}{r}T=min\{n\ge 0\mid X_n\le a\}\in \{0,1,2,\dots \}\cup \{\mathrm{\infty }\}\end{array}$$
とおくと, $T$は$({\mathcal{F}}_n)$-停止時刻である. 以後, 期待値$E_i[T]:=\int Td{P}_i$を考える.

停止時刻$T$に関する補題

結論

前節までの議論から(3)を$n\to \mathrm{\infty }$することで次を得る:

簡易計算pythonコード

参考用に簡易計算用クソコードを示しておく.
(iが100を超えてくると二項係数計算でオーバーフローします^^;)
(scipyの関数に変えたら計算できるようになりました)

      from scipy.special import comb
import numpy as np

def trans_prob(p, i, j):
    return comb(i, j) * p**j * (1 - p)**(i - j)

def E(i, a, p):
    if i <= a:
        return np.array([0. for _ in range(i + 1)])
    p_ij = np.array([trans_prob(p, i, j) for j in range(i)])
    E_prev = E(i - 1, a, p)
    E_now = (1 + p_ij @ E_prev) / (1 - p**i)
    return np.append(E_prev, E_now)
    

おわりに

給食ジャンケンがどれくらいで終わるのだろうと思ったのがこの問題を考えたきっかけである. この種の問題を検索しても目ぼしいものは出てこなかったので, 本記事では勝手に"給食ジャンケン問題"と呼んでいる次第である.