2
大学数学基礎解説
文献あり

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

420
0

給食ジャンケン問題

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

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

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

マルコフ連鎖の設定

ij, i,j=0,1,2,に対し, pij=(ij)pj(1p)ij=iCjpj(1p)ijとおく. 可測空間(Ω,F)上の{0,1,2,}-値可測関数の列X0,X1,に対し,
Pi(X0=i0,X1=i1,,Xn=in)=δii0pi0i1pi1i2pin1in,i=0,1,2,
で定める. ただし, δijはクロネッカーのデルタとする. またn=0,1,2,に対し, Fn=σ(X0,X1,,Xn)とおく. このとき, (Xn)n0(Ω,F,(Fn),(Pn))上で定義されたマルコフ連鎖であり, Xnは問題1の時刻nにおける粒子数を表す.

T=min{n0Xna}{0,1,2,}{}
とおくと, T(Fn)-停止時刻である. 以後, 期待値Ei[T]:=TdPiを考える.

停止時刻Tに関する補題

i=0,1,2,に対し, 次が成り立つ:
(1)Pi(T=0)={1,ia,0,i>a,(2)Pi(T=k)=jiPj(T=k1)pij,k1.
したがって, Pi(T<)=1, i>aである.

Tの定め方より(1)は明らか.
マルコフ性より,
Pi(T=k)=jiPi(T=kX1=j)Pi(X1=j)=jiPj(T=k1)pij
を得る.

(2)において, 測度の単調性を用いてすべてのk=1,2,に対する和をとると
Pi(T<)=jiPj(T<)pij
が得られる. iaのときPi(T<)=1なので, i>aとして数学的帰納法を用いると,
Pi(T<)=1pi+Pi(T<)pi
よりPi(T<)=1を得る.

i=0,1,2,に対し, Ei[T]<である.

(2)とマルコフ性より, n=1,2,に対し,
Ei[T;Tn]=k=1nkPi(T=k)=jipijk=1nkPj(T=k1)(3)=jipij{k=1n(k1)Pj(T=k1)+Pj(Tn1)}1+jipijEj[T;Tn]
である. iaのときEi[T]<なので, i>aとして数学的帰納法を用いると,
(1pi)Ei[T;Tn]1+ji1Ej[T]
なので, 単調収束定理を用いてnとするとEi[T]<が分かる.

結論

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

問題の解

すべてのi=0,1,に対し, Ei[T]は存在し次を満たす:
Ei[T]={0,ia,11pi(1+ji1pijEj[T]),i>a.

給食ジャンケン

デザートの余り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)
    

おわりに

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

参考文献

[1]
舟木 直久, 確率論, 講座数学の考え方 (20), 朝倉書店, 2004
投稿日:2022228
OptHub AI Competition

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。
バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

megumin
megumin
6
4393
Interest: Stochastic differential equations, stochastic calculus of variations, mathematical finance, quantum computing.

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中
  1. 給食ジャンケン問題
  2. マルコフ連鎖の設定
  3. 停止時刻Tに関する補題
  4. 結論
  5. 簡易計算pythonコード
  6. おわりに
  7. 参考文献