[解説]乱択アルゴリズムの強さ

乱択アルゴリズム

乱択アルゴリズムがどのようなものだったかは前回の記事を読んでみてください。

ロッカー問題

さて、前回はどう頑張っても0.4%くらいまでしか成功率を上げられませんでした。

では、どのようにして作戦を立てるのが最も成功率を上げられるでしょうか?

ここで、例の乱択アルゴリズムの出番というわけです。

乱数表であける(??%)

まず最初に1~10の適当な乱数表を作り、それを全員で共有します。

乱数表とロッカーの対応表

そして、全員が同じ規則性に従ってロッカーをあけます。

例えば、1のカードを持っている人は乱数表に従って左から5番目のロッカーをあけます。すると7のカードが入っているので、乱数表に従って次は左から6番目のロッカーをあけます。

これを繰り返していくと、

  • 5番目のロッカーをあける→7
  • 6番目のロッカーをあける→3
  • 3番目のロッカーをあける→2
  • 2番目のロッカーをあける→1

というように1のカードを発見することができました。

同じようにやっていくと全員が5回以内でカードを見つけられることがわかります。

でも賢明な読者の方は思うかもしれませんね。

「いや、これ偶然でしょ?」と。

では、実際にこのあけ方がどのくらいの成功率なのか考えてみることにしましょう。

成功率を計算する

この作戦は成功率よりも失敗率を計算したほうが楽だったりします。

まず最初に「何故この作戦が成功したか?」を考えてみましょう。

そのために、全員がどの順番でロッカーをあけたかをメモします。

  1. 7→3→2→1
  2. 6→8→9→5→2
  3. 10→1→7→3
  4. 4
  5. 2→6→8→9→5
  6. 8→9→5→2→6
  7. 3→10→1→7
  8. 9→5→2→6→8
  9. 5→2→6→8→9
  10. 1→7→3→10

すると、(1, 7, 3, 10), (6, 8, 9, 5, 2), (4) という三つのループができていることがわかります。実は、この作戦をとると必ずこのようにいくつかのループができるのです。

そして「5回以内で当たりを見つけられる」というのは「長さ6以上のループが存在しない」ということと等しいのです。

異なる10の数字が書かれたカードの並べ方は順列を考えればいいので10!通りあるのはすぐにわかります。

10枚から6枚をとってくるのは210通りで、それを並び替えるので6!倍します。ただし、円順列なのでそれを6で割る必要があります。

つまり、(5, 2, 6, 8, 9) と (2, 6, 8, 9, 5) は同じものと考えるということです。最後に残った4枚は好きに分けていいので4!通りあります。

これを計算すると、長さ6のループができる確率はちょうど1/6であることがわかります。どうように計算すると、長さ7のループができる確率は1/7と続くので、結局長さが6以上のループができる確率は、

となり、およそ64.6%になります。

長さ6以上のループができなければ5回以内でアタリを見つけられるので、この作戦の成功率は、

つまり、この作戦の成功率は35.4%であるということです。

従来の作戦に比べて100倍くらい成功率が高いわけですね。

一応、乱数表を使わなくても「最初に左から自分のカード番目のロッカーをあけて、それ以降は左から中のカード番目のロッカーをあける」という作戦でも同様の成功率がでます。

ただ、このときは意地悪な人がロッカーの中のカードの順番を長さ6以上のループができるように仕組んでいる可能性があるので、相手がどんな意地悪なことを考えていても確率35.4%が期待できる乱数表の作戦のほうが優秀です。

ほとんど書いてしまっていますが、より詳細が知りたい方は以下のPDFを参考にしてください。

まとめ

乱択アルゴリズムのいいところは、しっかりと乱数を用意することができれば相手がどんなに意地悪なことを考えていても無効化できる上に、期待値がそれ以外の方法よりも下がらないというところですね。

自分は乱択アルゴリズムを勉強する上でこのロッカー問題がすごく面白いと感じたので前回記事にさせていただきました。

次はまたまた情報理論分野の話で記事を書きたいなと思っているので、ぜひぜひ楽しみにしていてください。

しかし、こういう系統のハナシどのくらい需要があるか微妙ですな(笑)

記事は以上。