囚人100人の問題

驚くべきことに、囚人全員が30%以上の確率で生き残れる戦略が存在する。成功の鍵は、囚人がどの引き出しを開けるかを事前に決める必要がないことである。各囚人は、すでに開けた引き出しの中身から得た情報を使って、次に開ける引き出しを決めることができる。もう一つ重要な点は、この方法では、ある囚人の成功は他の囚人の成功とは無関係ではないということである。なぜなら、すべての囚人の成功は数字の分布方法に依存しているからである。^{[ 2 ]}

戦略を説明するために、囚人だけでなく引き出しも 1 から 100 まで番号が付けられます。たとえば、左上の引き出しから始めて行ごとに番号が付けられます。戦略は次のようになります。^{[ 3 ]}

1. 囚人たちはそれぞれ、まず自分の番号が書かれた引き出しを開ける。
2. この引き出しに彼らの番号が入っていれば、彼らは任務を完了し、成功したことになる。
3. そうでなければ、引き出しには別の囚人の番号が入っており、次にその番号が書かれた引き出しを開ける。
4. 囚人は、自分の番号が見つかるまで、または最初に開けた50個の引き出しの中に番号が見つからなければ失敗するまで、手順2と3を繰り返す。

囚人がこの方法で無限に続けることができれば、必ず最初に引いた引き出しに戻り、順列サイクルが形成される（下記参照）。囚人は自分の番号から始めることで、自分の番号を含む特定の引き出しサイクルにいることを保証できる。唯一の問題は、サイクルが50個以上の引き出しより長くなるかどうかである。そして、サイクルが長すぎる可能性があるのは1つだけである。なぜなら、最大でも1つのサイクルが全引き出し数の半分以上を占めることはないからである。

これが有望な戦略である理由は、8人の囚人と引き出しを使った次の例で説明できます。各囚人は4つの引き出しを開けることができます。刑務所長は、囚人の番号を次のように引き出しに割り当てました。

囚人たちは現在、以下のように行動している。

• 囚人1はまず引き出し1を開けて7番を見つける。次に引き出し7を開けて5番を見つける。そして引き出し5を開けると、自分の番号を見つけ、成功する。
• 囚人2は、2番、4番、8番の順に引き出しを開ける。最後の引き出しには、自分の番号である2が入っている。
• 囚人3は引き出し3と6を開け、そこで自分の番号を見つけた。
• 囚人4は引き出し4、8、2を開け、それぞれ自分の番号を見つけます。これは囚人2が遭遇したのと同じサイクルであり、囚人8もこれから同じサイクルに遭遇します。これらの囚人はそれぞれ、3番目に開けた引き出しの中に自分の番号を見つけることになります。
• 囚人5番から7番も、同様の方法で自分の番号を知ることになる。

この場合、囚人全員が自分の番号を見つけます。しかし、これは常に当てはまるわけではありません。例えば、引き出し5と8を入れ替えるというわずかな変更によって、囚人1は1、7、5、2を開けた後（そして自分の番号を見つけられなかった後）失敗します。

そして、以下の手順では、囚人1は引き出し1、3、7、4を開けますが、その時点で開けることができず、停止しなければなりません。

実際、6人目（直接成功する者）を除くすべての囚人が失敗する。

順列 (1  7  5)(2  4  8)(3  6) と (1  3  7  4  5  8  2)(6)のグラフ表現

刑務所長が囚人番号を引き出しに割り当てることは、数学的には1から100までの整数の順列として記述できます。順列を繰り返し適用すると最初の数に戻る数列を順列のサイクルと呼びます。すべての順列は、互いに素なサイクル、つまり共通要素を持たないサイクルに分解できます。上記の最初の例の順列は、サイクル表記で次のように書くことができます。

${\表示スタイル (1~7~5)(2~4~8)(3~6)}$

したがって、長さ3のサイクルが2つと長さ2のサイクルが1つから構成される。3番目の例の順列は、

${\displaystyle (1~3~7~4~5~8~2)(6)}$

そして、長さ 7 のサイクルと長さ 1 のサイクルから構成されます。サイクル表記は一意ではありません。長さ 7 のサイクルは、${\displaystyle l}$書き方${\displaystyle l}$サイクルの開始番号によって、さまざまな方法があります。上記の戦略を使用して引き出しを開ける際、各囚人は必ず自分の番号で終わる単一のサイクルをたどります。囚人が8人の場合、このサイクル追跡戦略は、順列の最長サイクルの長さが最大4である場合に限り成功します。順列に長さ5以上のサイクルが含まれている場合、そのようなサイクルに含まれる番号を持つすべての囚人は、4ステップ以内に自分の番号に到達できません。

最初の問題では、100人の囚人が成功するためには、順列の最長サイクルの長さが50以下でなければなりません。したがって、彼らの生存確率は、 1から100までの数字のランダムな順列に、長さが50を超えるサイクルが存在しない確率に等しくなります。この確率は次のように決定されます。

1から100までの数の順列は、長さのサイクルを最大で1つ含むことができる。${\displaystyle l>50}$正確には${\displaystyle {\tbinom {100}{l}}}$このようなサイクルの数字を選択する方法（組み合わせを参照）。このサイクル内では、これらの数字は次のように配置できます。${\displaystyle (l-1)!}$方法があるから${\displaystyle l}$長さの異なるサイクルを表す順列${\displaystyle l}$周期対称性のため。残りの数字は次のように並べることができます。${\displaystyle (100-l)!}$したがって、長さのサイクルを持つ1から100までの数の順列の数は${\displaystyle l>50}$に等しい

$\displaystyle {\binom {100}{l}}\cdot (l-1)!\cdot (100-l)!={\frac {100!}{l}}.}$

（一様分布の）ランダム順列に長さが 50 を超えるサイクルが含まれない確率は、単一事象の式と相補事象の式を用いて計算され、次のように与えられる。

${\displaystyle 1-{\frac {1}{100!}}\left({\frac {100!}{51}}+\ldots +{\frac {100!}{100}}\right)=1-\left({\frac {1}{51}}+\ldots +{\frac {1}{100}}\right)=1-(H_{100}-H_{50})\approx 0.31183,}$

どこ${\displaystyle H_{n}}$は${\displaystyle n}$の次高調波数。したがって、サイクル追跡戦略を使用すると、囚人は驚くべきことに31%のケースで生き残ります。^{[ 3 ]}

もし${\displaystyle 2n}$100人の囚人の代わりに、${\displaystyle n}$は任意の自然数であり、サイクル追従戦略による囚人の生存確率は次のように与えられる。

${\displaystyle 1-(H_{2n}-H_{n})=1-(H_{2n}-\ln 2n)+(H_{n}-\ln n)-\ln 2.}$

オイラー・マスケローニ定数を用いて${\displaystyle \gamma }$、 のために${\displaystyle n\to \infty }$

${\displaystyle \lim _{n\to \infty }(H_{n}-\ln n)=\gamma }$

が成り立ち、その結果、漸近生存確率は

${\displaystyle \lim _{n\to \infty }(1-H_{2n}+H_{n})=1-\gamma +\gamma -\ln 2=1-\ln 2\approx 0.30685.}$

確率の列は単調減少であるため、囚人の数に関係なく、サイクル追従戦略によって囚人が生き残る確率は30%以上である。^{[ 3 ]}

2006年、ユージン・カーティンとマックス・ウォーシャウアーは、サイクル追跡戦略の最適性の証明を与えた。この証明は、すべての囚人が部屋にいて引き出しの開閉を観察できるという関連問題との等価性に基づいている。数学的には、この等価性は、 （標準的な）サイクル表記と順列の1行表記の1対1対応であるフォアタの遷移補題に基づいている。2番目の問題では、生存確率は選択された戦略とは無関係であり、サイクル追跡戦略を用いた元の問題の生存確率と等しい。元の問題に対する任意の戦略を2番目の問題にも適用できるが、そこでより高い生存確率を達成することはできないため、サイクル追跡戦略が最適でなければならない。^{[ 2 ]}

当初、GálとMiltersenは論文の中で、箱の数がチームメンバーの数の2倍で、箱の半分が空である場合を検討した。これは、空の箱はどこにも繋がらないため、サイクル追跡戦略を適用できないという点で、より難しい問題である。この場合、チームメンバーの数が増えるにつれて勝利確率がゼロに近づくかどうかは未解決の問題である。 ^{[ 4 ]}

2005年、Navin GoyalとMichael Saksは、空の箱の割合と各チームメンバーが開けることができる箱の割合が可変である、より一般的な問題に対するサイクル追従戦略に基づいて、チームBの戦略を開発した。この場合、勝利確率は依然としてゼロに近づくが、GálとMiltersenが示唆したよりも遅い。チームメンバーの数と開けられる箱の割合が固定されている場合、空の箱がさらに追加されても、勝利確率は厳密にゼロより大きいままである。^{[ 10 ]}

刑務所長が引き出しに番号をランダムに割り当てる必要がなく、囚人が上記の戦略を用いる可能​​性があることを認識し、囚人が用いるであろう箱の番号付け（箱に示された番号など）を推測できる場合、刑務所長はその戦略を阻止することができる。そのためには、囚人の番号を引き出しに割り当てる際に、長さが 50 より大きい順列となるようにすればよい。囚人は、所長がこれを聞き取ったり、囚人が入る前に箱の番号を入れ替えたりしない限り、引き出しの特定のランダムな番号付けについて合意することでこれに対抗できる。^{[ 11 ]}

囚人のうち1人が最初に部屋に入り、すべての箱を調べ、2つの箱の中身を入れ替えた場合、すべての囚人が生き残る。これは、長さが50より大きいサイクルはすべて破ることができるため、すべてのサイクルの長さが最大でも50であることが保証されるからである。

十分な数の囚人に対して${\displaystyle N}$引き出しの半分よりはるかに少ない数を開けるだけで脱出できる。具体的には、各囚人は引き出しを半分だけ開ければよい。${\displaystyle O\left(N{\frac {\log \log N}{\log N}}\right)}$囚人全員の脱走を防ぐための引き出し。^{[ 12 ]}

自分の番号を見つけた囚人は誰でも釈放されるという条件の下では、ランダムな順列が与えられた場合の個人の生存確率の期待値は次のようになります。

戦略なし：${\displaystyle {\frac {1}{2}}}$

元の問題に対する戦略は以下のとおりです。${\displaystyle (1-\ln(2))\cdot 1+\sum _{k=\lfloor n/2\rfloor +1}^{N}{\frac {1}{k}}\left(1-{\frac {k}{n}}\right)=1-\ln(2)+\sum _{\lfloor n/2\rfloor +1}^{N}{\frac {1}{k}}-\sum _{k=\lfloor n/2\rfloor +1}^{N}{\frac {1}{n}}=1-\ln(2)+\ln(2)-{\frac {1}{2}}={\frac {1}{2}}}$

注目すべきは、期待値は同じであっても、それらが全く異なる分布から得られている点である。2番目の戦略では、特定の順列が与えられた場合、囚人の中には死ぬか生きるかが決まってしまっている者がいるのに対し、1番目の戦略（つまり、戦略なし）では、あらゆる順列に対して「真に」1/2の確率が存在する。

2009年、アダム・S・ランズバーグは、よく知られているモンティ・ホール問題を基にした、100人の囚人問題のより単純な変種を提案した。^{[ 13 ]}

3つの閉まったドアの後ろに、車、車の鍵、ヤギがランダムに配置されています。プレイヤーは2人います。1人目のプレイヤーは車を見つけ、2人目のプレイヤーは車の鍵を見つけなければなりません。両方のプレイヤーが成功した場合にのみ、車を運転して家に帰ることができます。1人目のプレイヤーは部屋に入り、3つのドアのうち2つを順番に開けることができます。成功した場合、ドアは再び閉じられ、2人目のプレイヤーが部屋に入ります。2人目のプレイヤーも3つのドアのうち2つを開けることができますが、1人目のプレイヤーとは一切コミュニケーションを取ることができません。両方のプレイヤーが最適に行動した場合、勝つ確率はどれくらいでしょうか？

プレイヤーがランダムにドアを選択した場合、勝つ確率はわずか4/9（約44%）です。最適な戦略では、最初のプレイヤーと車を番号1に、2番目のプレイヤーと鍵を番号2に、ヤギを番号3に割り当てます。基本的なアルゴリズムは次のとおりです。

• プレイヤー1はまずドア1を開けます。ドアの後ろに車があれば、プレイヤーは成功です。ドアの後ろに鍵があった場合は、次にドア2を開けます。逆にドアの後ろにヤギがあった場合は、次にドア3を開けます。
• プレイヤー2はまずドア2を開けます。鍵がドアの後ろにあれば、プレイヤーは成功です。車がドアの後ろにあった場合は、次にプレイヤーはドア1を開けます。一方、ヤギがドアの後ろにあった場合は、次にプレイヤーはドア3を開けます。

3つのドアの後ろに車、鍵、ヤギを配置する6つの可能な組み合わせにおいて、プレイヤーは以下のドアを開けます（緑色のケースでは、プレイヤーは成功しました）。

この戦略の成功は、 2 人のプレイヤーの成功と失敗の間に相関関係を構築することに基づいています。ここでは、勝率は2/3であり、最初のプレイヤーの勝率がこれより高くなることはないため、これは最適です。^{[ 13 ]}さらに別のバリエーションでは、3 つの賞品が 3 つのドアの後ろに隠されており、3 人のプレイヤーはそれぞれ2回の試行で割り当てられた賞品を独立して見つけなければなりません。この場合も、最適な戦略が採用されると、勝率は2/3になります。^{[ 14 ]}

最初の 50 回以内に自分の番号を見つける代わりに、テストは 50 回の奇数回の試行 ( 1、3、...、97、99 ) 以内に番号を見つけることとすることができます。各囚人は奇数回の試行で自分の番号を見つける確率が 50% です。囚人の順列に奇数長のサイクルのみが含まれている場合、メイン戦略はすべての囚人に対して有効です。100 人の囚人の場合、メイン戦略を使用して全員が成功する確率は約 7.9589% であり、各囚人が独立してランダムに引き出しを開けた場合に得られる確率(1/2) ^{100よりも大幅に優れています。}

囚人は1から99までの引き出しを開けることができ、全員が自分の番号を見つけるか、全員が自分の番号を見つけられないかのどちらかになります。彼らはこれを100日間連続で100回行わなければなりません。1日だけで囚人が自分の番号を見つけないことを選択した場合、つまり各囚人が自分の番号が書かれた引き出しだけを開けた場合、全員が36.79%の確率で成功します。しかし、これを100回連続で試すと、成功率はほぼ0%になります。しかし、各囚人がメイン戦略に従って99個の引き出しを開けると、1人の囚人が自分の番号を見つけられない唯一のケースは、長さ100の単一のサイクルを持つ順列であり、その場合、すべての囚人が同じ結果になります。^{[ 9 ]}