給食で出されるデザートが余っているとき, 希望者が先生とジャンケンをして最後まで先生に勝ち続けた人がそのデザートをもらうことができる, といったことがよく行われる. 同種のジャンケンでは, 誰もやりたがらない委員が決まらないことに業を煮やした担任が行うジャンケン, 何かのイベントで景品をかけた司会者と参加者とのジャンケン等もある. 似たような問題として, 複数枚のコインを投げ, 表が出たコインだけを残して再度投げるというのを繰り返すゲームを考えることもできる. そこで, このようなゲームにおいて何回試行が続くだろうかという疑問が生じる. 給食ジャンケンの例でいうと, デザートをもらえる人が決まるまで何回くらいジャンケンが行われるだろうかというのを知りたいのである. つまり次のような問題を考えよう:
この問題, 例えば給食ジャンケンでは, 勝った人だけが残り続けるとすると
で定める. ただし,
とおくと,
したがって,
マルコフ性より,
を得る.
(2)において, 測度の単調性を用いてすべての
が得られる.
より
各
(2)とマルコフ性より,
である.
なので, 単調収束定理を用いて
前節までの議論から(3)を
すべての
デザートの余り1個, 希望者10人の給食ジャンケンは, 先生に勝った人のみが残り, 勝ち残り人数が1人以下になったとき終了する. 終了するまでのジャンケン回数の期待値は約2.26回である.
他に委員を務めていない20人の中から委員2人を決めるジャンケンは負けた人が残り, 残り人数が2人以下になったら終了する. 終了するまでのジャンケン回数の期待値は約2.41回である. また, あいこも残るとすると約5.67回である.
コイン100枚を表が出たものを残して投げ続ける. このとき5枚以下になるまでのコイントス回数の期待値は約4.69回である. 1000枚だと約8.01回である.
参考用に簡易計算用クソコードを示しておく.(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)
給食ジャンケンがどれくらいで終わるのだろうと思ったのがこの問題を考えたきっかけである. この種の問題を検索しても目ぼしいものは出てこなかったので, 本記事では勝手に"給食ジャンケン問題"と呼んでいる次第である.