ネストすごろくの解法について書きます。
下記の問題のネタバレを含みます。
[問] 下記のネストすごろくをクリアできる確率はいくらでしょうか?
— 冬koteitan夏たこみぱん (@koteitan) December 19, 2022
ネストすごろく:ゲームが始まると、下記のように START のマスにいる状態になります。サイコロを振り、出た目の数だけ右に進みます。GOAL に達するとクリアです。(GOAL を超えて進む目が出たとしてもクリアです) (つづく) pic.twitter.com/MRBKwbixNj
解法
ネタバレ注意
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
解の存在について
回目までにゴールする確率の極限が求めるものです。この確率は について単調増加かつ有界 *1 なので収束します。
解の候補について
求める成功確率(クリアできる確率)を とします。
以下、マスを順に 0 ~ 6 で表します(スタートが 0 、ゴールが 6 、途中のネストマスは 1 ~ 5)。
について、マス (ネストマスの場合はネストから出た状態)からスタートした場合の成功確率を とします。遷移を考えることにより、 について が成立することが分かります。 が大きい方から順に計算すると が得られ、これが と一致することから方程式が立てられます。整理すると
となります。 の範囲では 1 および約 0.54768 の 2 つの解があるので、 はこれらのうちどちらかであることが分かります。
確率が1より小さい証明
準備
次の定理を使います。
定理:期待値がマイナスのゲーム *2 がいくつかあり、これらの得点の変動は有界であるとする。このとき、これらから好きなゲームを選んで行うことを繰り返すとき、得点を 1 以上増加させる確率は 1 より真に小さい *3
例えば、「サイコロを振って 1 または 2 が出れば 1 円もらう、3 以上が出れば 1 円払う」というゲームや「コインを投げて表なら 1 円もらう、裏なら 2 円払う」というゲームはいずれも期待値がマイナスです。所持金がマイナスになることも許容します。
初期状態 0 円から始めた場合、これらのゲームをどう組み合わせて行っても(可算無限回行っても)所持金が 1 円に達する確率を 1 にする戦略は存在しません。
期待値がちょうどゼロのゲームがある場合や、得点の変動が有界でない場合は反例があります。後者は、例えば ( )回目に「サイコロを振って 1 が出れば 円もらう、それ以外なら 円払う」というゲームを 1 が出るまで行うと、各回での期待値はマイナスですが、確率 1 で所持金を 1 円増やすことができます。
定理の証明は割愛しますが、大数の(弱)法則と同様、チェビシェフの不等式等で示せます *4 。
ポテンシャル
突然ですが、マス (ネストマスの場合はネストから出た状態)のポテンシャル を次のように定めます:
ネスト状態にある場合は、ミニゲームのゴールが出た場所のポテンシャルに一致するように平行移動します。
たとえばマス 3 におけるミニゲームでは、元のゲームのポテンシャルに比べて全体的に 0.3 ずつ小さいポテンシャルになります。ネストが深い場合も同様に定義します。
このとき、各回におけるポテンシャル変動の期待値はマイナスです *5 *6 。よって上の定理からゴールに到達する確率は 1 より真に小さいことが分かります。
結論
以上から、ネストすごろくの成功確率は約 54.768% *7 であることが分かりました。
*1:確率なので 1 以下ですね
*2:特定の確率分布に従って得点が変動するゲーム
*3:本記事の範囲では、ゲームの種類および各ゲームの変動の種類は有限と仮定しても十分です。実際はゲームは無限にあっても大丈夫ですが、ゲームすべてを通じて変動が有界であることを仮定します(分散が有限ぐらいに緩められると思います)。
*4:ちゃんとやってないけどたぶん
*5:マス 0 から 4 の 5 パターンについて計算すると確かめられます
*6:マス 5 にいるとき(ネストから出た状態)は実質的にゴールしていると考えて無視します
*7:より正確には、 4 次方程式 の正の解で、小数第 1000 位まで表示すると