013. クイズの森

[mathjax]

サーバーをお引越ししていろいろ便利になったので、試しにWordpressで数式を表示してみました。

けものフレンズ7話の「クイズの森」についての考察（？）です。

問題設定

ここに、サーバルちゃんとかばんちゃんがいる。二人は以下の仕組みの「クイズの森」に挑戦しようとしている。

・\(0\)番の部屋を最初の部屋とし、\(N\)番目の部屋に到達すれば脱出となる。
・それぞれの部屋には右に進むか左に進むかの選択肢がある。
・右か左のどちらかが正解であり、正しい方を選ぶと次の部屋へ、さもなくば最初の部屋へ進む。

サーバルちゃんは文字が読めないため、どの部屋においても直感で行き先を決めるランダム戦略を取る。

かばんちゃんは文字が読めるもののクイズの答えに関する知識が無いため、その正答率はサーバルちゃんと変わらない。ただし、過去に通った部屋の記憶を活かし、一度でも通過して既に正解の選択肢がわかっている部屋では必ず正しい方向に進むかしこい戦略を取る。

サーバルちゃんとかばんちゃん、それぞれがクイズの森脱出までに要する歩数（部屋移動の回数）の期待値を知りたい。

ランダム戦略

記憶を何も持たず、過去の結果とは無関係にそれぞれの部屋で毎回進む方向を等しい確率でランダムに決めるエージェントを考える。

0番目の部屋に居る時点を起点とし、N番目の部屋に到達して脱出する、あるいは0番目の部屋に戻されるまでを1試行と呼ぶことにする。過去の結果を利用しないエージェントではそれぞれの試行は独立している。

任意の\(n-1\)番目の部屋で試行を終える確率は\(2^{-n}\)と表せる。この時かかった歩数は\(n\)歩になる。

このことから、各試行で追加される歩数の期待値\(\overline{t}\)は$$\overline{t}=\sum_{n=1}^{N} 2^{-n}n$$
となる。

ある試行が成功裏に終わる確率は\(2^{-N}\)なので、この逆数を取れば成功するまでにかかる試行回数の期待値\(2^N\)が得られる。つまりクイズの森脱出までにかかる歩数の期待値\(\overline{t}\)は
$$\overline{T}= 2^N\sum_{n=1}^{N}2^{-n}n$$
Σを外すと
$$\overline{T}= 2^{N+1}-N-2$$

以上の結果より、サーバルちゃんの
最短歩数は\(N\)
平均歩数は\(2^{N+1}-N-2\)
最悪歩数は\(+\infty\)
となる。

かしこい戦略

どの部屋のクイズも、一度目の挑戦では正解する確率は\(1/2\)だが二度目以降は必ず正解する。

任意の部屋について、その部屋のクイズに正解して次の部屋に居る状態と、不正解してからその部屋に戻ってきて、先ほどとは違う方を選んで次の部屋に居る状態を考える。不正解の場合はその部屋に戻ってくるまでの歩数が追加されていることを除けば、両者の間でエージェントの状態に違いはない。

そこで、長さ\(N\)の「一発正解失敗時の追加歩数」ベクトル\(\vec{a}=(1,2,3,…,N)\)と、同じく長さ\(N\)の「不正解」ベクトル\(\vec{b}=(b_0,b_1,…,b_{N-1})\)を考える。不正解ベクトルの各要素\(b_{n}\)は、\(n\)番目の部屋で一発正解できたら0、さもなくば1を取る。

このとき、クイズの森脱出までにかかる歩数\(T\)はこの2つのベクトルの内積を用いることで\(T=N+\vec{a} \cdot \vec{b}\)と表せる。

すべての部屋で一発正解、つまり不正解ベクトルが全てゼロだったとき\(T=N\)となり、これは最短歩数である。

逆にすべての部屋で一発正解に失敗、つまり不正解ベクトルが全て1だったとき\(T=N+|\vec{a}|=N+\frac{N(N+1)}{2}=\frac{N^2+3N}{2}\)となり、これは最悪歩数である。

歩数の期待値を得るには、不正解ベクトルの各要素を一発正解失敗の確率とし、\(\vec{b}=(1/2,1/2,…,1/2)\)を使ってTを求めれば良い。つまり平均歩数は\(T=N+\frac{|\vec{a}|}{2}=N+\frac{N(N+1)}{4}=\frac{N^2+3N}{4}\)となる。

以上の結果より、かばんちゃんの
最短歩数は\(N\)
平均歩数は\(\frac{N^2+3N}{2}\)
最悪歩数は\(\frac{N^2+5N}{4}\)
となる。

…で合ってますかね？

数学に自信がないのでシミュレーションしてみました。

コードが間違ってない限りは合ってそうです。

（数式が綺麗に入れられました！ありがとうMathJax-LaTeX）