秘書問題(お見合い問題)とその解法

もし人生で nn 人の異性と付き合うことが分かっていて nn が十分大きいなら,最初の ne\dfrac{n}{e} 人とは別れてその後で「今までで一番いい人」がいたら結婚するべきである。

秘書問題とは

お見合い問題,結婚問題,最良選択問題などと言うこともあります。お見合いで説明します。現実的でない仮定もありますがご容赦ください。

  • nn 人と順番にお見合いする。
  • お見合いした瞬間に交際するかしないか決めないといけない。
  • 交際を申し込めば相手はOKしてくれる。
  • 交際をスタートしたら他の人とは二度とお見合いはできない。
  • 一回断った人とは二度と交際できない。
  • nn 人の中で一番タイプな人と交際できる確率を最大にしたい。

どういう戦略を取ればよいか?

秘書問題の最適戦略

kk 人目まで無条件で断り,k+1k+1 人目以降で「今までで一番いい人」が現れたら交際する,というタイプの戦略(戦略 SkS_k と呼ぶ)を取ることにします。直感的に自然な戦略です。 kk をどのように定めればよいかを考えます。

nn が十分大きいとき,k=nek=\dfrac{n}{e}(の近く)が最適。このとき,nn 人の中で一番タイプな人と交際できる確率は約 3737 %。

ネイピア数 e=2.718e=2.718\cdots が登場するのが面白いですね。

証明

tt 人目に一番好きな人がいる確率は 1n\dfrac{1}{n},このとき戦略 SkS_ktt 人目の人を選べる確率は,

tkt\leq k のとき 00

t>kt> k のとき kt1\dfrac{k}{t-1} (「最初の t1t-1 人の中で一番好きな人」が先頭 kk 人の中にいないと,その人と交際してしまい「全体の中で一番好きな人」までたどりつかない)

よって,成功する確率は

1nt=k+1nkt1=kn(1k+1k+1++1n1)\dfrac{1}{n}\displaystyle\sum_{t=k+1}^{n}\dfrac{k}{t-1}\\ =\dfrac{k}{n}\left(\dfrac{1}{k}+\dfrac{1}{k+1}+\cdots +\dfrac{1}{n-1}\right)

これを最大にする kk を求めればよい。nn が十分大きいとき

1k+1k+1++1n1lognk\dfrac{1}{k}+\dfrac{1}{k+1}+\cdots +\dfrac{1}{n-1}\fallingdotseq \log \dfrac{n}{k}

なので(→注),knlognk\dfrac{k}{n}\log \dfrac{n}{k} を最大にする kk を求めればよい。

kk で微分すると 1nlognk1n\dfrac{1}{n}\log\dfrac{n}{k}-\dfrac{1}{n} より nk=e\dfrac{n}{k}=e で最大。つまり k=nek=\dfrac{n}{e} のとき最大でそのときの成功確率は

logee=1e0.37\dfrac{\log e}{e}=\dfrac{1}{e}\fallingdotseq 0.37

注: nn が十分大きいとき 1+12++1nlogn1+\dfrac{1}{2}+\cdots +\dfrac{1}{n}\fallingdotseq \log n であることは覚えておきましょう。→調和級数1+1/2+1/3…が発散することの証明

例えば y=1xy=\dfrac{1}{x} のグラフを描くことで log(n+1)<k=1n1k<logn+1\log (n+1)< \displaystyle\sum_{k=1}^n\dfrac{1}{k} < \log n+1 が分かります。

考察,補足

  • 今回は「nn 人の中で一番タイプな人と交際できる確率を最大化する」という最良選択問題を考えました。一方「交際する人の順位の期待値を最小化する」という順位最小化問題も考えられます。順位最小化問題の方が現実的な気がしますが,最適停止問題の方が解析が簡単で結果も美しいので有名です。

  • nn がどんなに大きくても 3737 %くらいの確率で一番好きな人と交際できるというのは驚きです。

  • 現実はこんなに単純ではありません。人の性格や好みは時間変化します。タイプじゃなかったけど長年付き合ってみると好きになった,嫌いになったなんてこともあるでしょう。

なお,nn が小さい人にはこの理論は通用しません。

Tag:難しめの数学雑学・ネタまとめ