文献あり

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

386

給食ジャンケン問題

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

$a\leq N$, $a,N\in\mathbb{N}$, $0\leq p<1$, $n=0,1,2,\dots$とする. 時刻$n=0$において, $N$個の粒子がある. 時刻$n>0$において, 時刻$n-1$まで消滅せずに残っている粒子はそれぞれ確率$1-p$で消滅する. 残りの粒子が初めて$a$個以下になる時刻を$T$とするとき, $T$の期待値はいくらか.

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

マルコフ連鎖の設定

$i\geq j$, $i,j=0,1,2,\dots$に対し, $p_{ij}=\begin{pmatrix}i\\j\end{pmatrix}p^j(1-p)^{i-j}={}_i\textrm{C}_j\,p^j(1-p)^{i-j}$とおく. 可測空間$(\Omega,\mathcal{F})$上の$\{0,1,2,\dots\}$-値可測関数の列$X_0,X_1,\dots$に対し,
\begin{align*} P_i(X_0=i_0,X_1=i_1,\dots,X_n=i_n) = \delta_{ii_0}p_{i_0i_1}p_{i_1i_2}\dots p_{i_{n-1}i_n}, \quad i=0,1,2,\dots \end{align*}
で定める. ただし, $\delta_{ij}$はクロネッカーのデルタとする. また$n=0,1,2,\dots$に対し, $\mathcal{F}_n=\sigma(X_0,X_1,\dots,X_n)$とおく. このとき, $(X_n)_{n\geq 0}$は$(\Omega,\mathcal{F},(\mathcal{F}_n),(P_n))$上で定義されたマルコフ連鎖であり, $X_n$は問題1の時刻$n$における粒子数を表す.

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

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

$i=0,1,2,\dots$に対し, 次が成り立つ:
\begin{align} P_i(T=0) &= \begin{cases} 1, \quad i\leq a,\\[.5em] 0, \quad i>a, \end{cases} \tag{1} \\[.5em] P_i(T=k) &= \sum_{j\leq i}P_j(T=k-1)\,p_{ij}, \quad k\geq 1. \tag{2} \end{align}
したがって, $P_i(T<\infty)=1,~\forall i>a$である.

$T$の定め方より(1)は明らか.
マルコフ性より,
\begin{align*} P_i(T=k) &= \sum_{j\leq i}P_i(T=k\mid X_1=j)P_i(X_1=j) \\ &= \sum_{j\leq i}P_j(T=k-1)\,p_{ij} \end{align*}
を得る.

(2)において, 測度の単調性を用いてすべての$k=1,2,\dots$に対する和をとると
\begin{align*} P_i(T<\infty) &= \sum_{j\leq i}P_j(T<\infty)\,p_{ij} \end{align*}
が得られる. $i\leq a$のとき$P_i(T<\infty)=1$なので, $i>a$として数学的帰納法を用いると,
\begin{align*} P_i(T<\infty) &= 1-p^i + P_i(T<\infty)\,p^i \end{align*}
より$P_i(T<\infty)=1$を得る.

各$i=0,1,2,\dots$に対し, $E_i[T]<\infty$である.

(2)とマルコフ性より, $n=1,2,\dots$に対し,
\begin{align*} E_i[T;T\leq n] &= \sum_{k=1}^{n}kP_i(T=k) \\ &= \sum_{j\leq i}p_{ij}\sum_{k=1}^{n}kP_j(T=k-1) \\ &= \sum_{j\leq i}p_{ij} \left\{ \sum_{k=1}^{n}(k-1)P_j(T=k-1) + P_j(T\leq n-1)\right\} \tag{3} \\[.5em] &\leq 1 + \sum_{j\leq i}p_{ij}E_j[T;T\leq n] \end{align*}
である. $i\leq a$のとき$E_i[T]<\infty$なので, $i>a$として数学的帰納法を用いると,
\begin{align*} (1-p^i)E_i[T;T\leq n] \leq 1 + \sum_{j\leq i-1}E_j[T] \end{align*}
なので, 単調収束定理を用いて$n\to\infty$とすると$E_i[T]<\infty$が分かる.

結論

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

問題の解

すべての$i=0,1,\dots$に対し, $E_i[T]$は存在し次を満たす:
\begin{align*} E_i[T] &= \begin{cases} 0, \quad i\leq a,\\[.5em] \displaystyle\frac{1}{1-p^i} \left( 1 + \sum_{j\leq i-1}p_{ij}\,E_j[T] \right), \quad i>a. \end{cases} \end{align*}

給食ジャンケン

デザートの余り1個, 希望者10人の給食ジャンケンは, 先生に勝った人のみが残り, 勝ち残り人数が1人以下になったとき終了する. 終了するまでのジャンケン回数の期待値は約2.26回である.

委員決め

他に委員を務めていない20人の中から委員2人を決めるジャンケンは負けた人が残り, 残り人数が2人以下になったら終了する. 終了するまでのジャンケン回数の期待値は約2.41回である. また, あいこも残るとすると約5.67回である.

コイントス

コイン100枚を表が出たものを残して投げ続ける. このとき5枚以下になるまでのコイントス回数の期待値は約4.69回である. 1000枚だと約8.01回である.

簡易計算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)