グーゴル問題をExcelで数値的にモンテカルロシミュレーションしてみた
グーゴル問題の具体例
食品商社のA社は新しい倉庫を探しています。
不動産会社に仲介を頼んだところ、条件に合う候補を20か所紹介してきました。
A社はその中から10か所に絞りこみました。
これら10か所はいずれも甲乙付け難いため、最終決定するために現地視察することにしました。
しかしA社の担当者は忙しく、すべての倉庫を視察する時間はありません。
視察する倉庫はできるだけ少ない数で済ましたいと考えています。
また、最近の倉庫は売り手市場で、現地視察をしたらその場でOKかNGかを判断しないと、他社に取られてしまいます。
このような状況で、A社の担当者が最善の選択するためにはどのようにすればいいでしょうか？
グーゴル問題とは？
A社の担当者にとって最善の選択とは、もちろん一番いい倉庫を選ぶことですね。
しかし、これは容易なことではありません。
例えば、A社の担当者が3つ目の倉庫に一目ぼれして、その場で即決OKを出したとします。
しかし実は4つ目にもっといい倉庫があったかもしれませんね。
1つ目と2つ目の倉庫があまりにも酷かったため、3つ目の倉庫が平凡でも良く見えただけかもしれないのです。
このようにマーケットがひっ迫していて自分にとって買い手市場でない時には、良い物件をキープしておけないため、最善の選択をすることが難しくなります。
この選択問題は次のようなゲームと同じと考えることができます。
一人が10枚の紙に好きな数字を書いて裏返しにしておきます。
そして、もう一人が一枚ずつめくっていき、最後にめくった紙に書いてある数字が10個の数字の最大値だったら勝ちというゲームです。
例えば1枚目が10、2枚目が5、3枚目が10,000だったとして、3枚目が最大に違いないと思ってそこでストップしたとしましょう。
でも残り7枚の中に10の100乗があったら負けですね。
これは先ほどの倉庫の例と同じで、1、2枚目があまりに小さい数だったため、3枚目の10,000が大きく見えて失敗したわけです。
10の100乗の単位をグーゴル（googol）といいます。
そのため、この問題はグーゴル問題といわれています。
米国のIT企業Googleはこの巨大数Googolが社名の由来だといわれています。
グーゴル問題の解
このグーゴル問題は数学的に解が得られています。
最初にめくる全体の３６.８％の紙に書いてある数字はどんなに大きな数字だと思っても見送って、それ以降にめくる数字が見送った数字の最大値よりも大きければそこでストップするという戦略を採る時に、一番勝率が高くなります。
例えば先ほどの倉庫探しの例でいうと、最初に視察する3件か4件目まではどんなに良いと思ってもOKは出さずに、一番良いと思った倉庫を覚えておきます。
そしてその後、一番良いと思った倉庫を上回る倉庫が現れたら、その倉庫を選択するのです。
なぜそうなるかというのは微分積分を使えば解析的に示せますが、少し難しいのでここではやりません。
その代わりに、モンテカルロシミュレーションで数値的（確率的）に示す方法を紹介します。
グーゴル問題を数値的に解く計算アルゴリズム
まずは見送る枚数を固定で考える
このような問題をモンテカルロシミュレーションする時は、人のやり方をそのまま再現するようにします。
10枚の紙から最大値を選ぶグーゴル問題では次のようになります。
- 見送る枚数を予め決めておいて（例えば最初の3枚は見送る等）、見送った数字の最大値を記憶しておく
- 残りの紙を1枚ずつめくっていく
- 最後までめくって、見送った数字の最大値を越える数がなければ失敗
- 見送った数字の最大値を越える数字があった場合、その数字が10個の数字の最大値なら成功。そうでないなら失敗
これを何回も繰り返せば、この戦略を採った時に最大値を選べる確率（成功する確率）を計算することができます。
見送る枚数を可変にする
しかしこれだと見送る枚数を固定しているので、その場合の勝つ確率しか計算することができません。
ですので、見送る枚数を１枚から９枚まで変化させます。
すると、何枚見送った時に成功したかがわかります。
多数回繰り返して成功回数を比べる
ある時は３～５枚を見送った時に成功し、ある時は８～９枚を見送った時に成功するかもしれません。
これを多数回、例えば１,０００回繰り返せば、それぞれの見送る枚数ごとの成功する回数が求まります。
グーゴル問題をExcelでモンテカルロシミュレーション
見送った数字の中の最大値を求める
これをExcelでやるために、まずはステップ1を入力してみましょう。
まずC10～C19セルに10個の数を乱数で生成します。
普通の人は好きな数を整数で書くと思いますが、ここでは0～1までの乱数をRAND関数で生成しています。
次に、見送る枚数を1～9枚として、その中の最大値を求めておきます。
これはD7～L7セルに入力しています。
例えば、1枚見送る場合も5枚見送る場合も、最大値は0.671692で変わりません。
1枚目に0.671692があるからです。
残りの中で見送った数字の最大値を越える数字を抜き出す
次に、残った数字の中から、見送った数字の中で最大値を越える数字を抜き出しておきます。
これは次のように入力すれば、すべて抜き出すことができます。
これにより、ステップ2の「残りの紙を1枚ずつめくっていく」ということができました。
最初に最大値を越えた数字を抜き出し、成功か失敗かを判断する
次に残った数字の中から、見送った数字の中の最大値（Max1）を越える最初の数字を抜き出します。
例えば上記の例だと、２枚を見送る時、見送った数字の中の最大値は0.817582（Max1=0.817582）ですが、これを越える最初の数字は３枚目にめくる0.88413256です。
もし３枚を見送る時は、３枚の中の最大値は３枚目にめくる0.88413256ですが、これを越える数字は９枚目の0.981664まで出てきません。
従ってこの場合は0.981664になります。
これをExcelで求めるには、次のように計算します。
すると、５行目に成功したら１が表示されます。
上記の例では、３～８枚を見送った時にはいつでも成功したということです。
なぜなら、３枚目に２番目に大きい数字0.826565があり、１番大きい数字は９枚目の0.864877524なので、例えば７枚を見送る場合はその中の最大値は0.826565で、それを越える数字である９枚目をめくったところでストップすれば全体の最大値0.864877524を当てることができるわけです。
多数回繰り返す
あとは、このシミュレーションで乱数を変えて何回も行って、結果の平均を取ります。
VBAを使って５行目の値を別シートにコピペしていけば良いでしょう。
１,０００回行った結果は次のようになりました。
これによって見送った枚数ごとの成功回数が２行目に計算されます。
シミュレーション結果
グラフにすると次のようになります。
見送り枚数が３～４枚のところで、成功回数が一番多くなっていることがわかります。
しかしこれでは３６.８％で最大化することまではわかりません。
そこで紙の枚数を１００枚に増やして同じモンテカルロシミュレーションを行ってみましょう。
そうすればもっと細かい数字がわかるはずです。
シミュレーション回数10,000回で行った結果は次のようになりました。
このように見送り枚数３６枚の時に成功する確率が最大になり、理論値の３６.８％とほぼ同じ結果になりました。
まとめ
これは中々面白い結果ですね。
あなたが二股恋愛ができない誠実な人で３０歳までに結婚しようと思っているなら、それまでに付き合うであろう異性の人数の最初の３６％は見送り、それ以降に付き合う人の中で、見送った人の中で一番良かった人を越えた最初の人、その人こそが運命の人です。
