2015/08/28

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

分野: データの分析,確率  レベル: マニアック

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

秘書問題とは

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

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

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

秘書問題の最適戦略

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

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

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

証明

$t$ 人目に一番好きな人がいる確率は $\dfrac{1}{n}$,このとき戦略 $S_k$ で $t$ 人目の人を選べる確率は,
$t\leq k$ のとき $0$
$t> k$ のとき $\dfrac{k}{t-1}$(「最初の $t-1$ 人の中で一番好きな人」が先頭 $k$ 人の中にいないと,その人と交際してしまい「全体の中で一番好きな人」までたどりつかない)

よって,成功する確率は
$\dfrac{1}{n}\displaystyle\sum_{t=k+1}^{n}\dfrac{k}{t-1}\\
=\dfrac{k}{n}(\dfrac{1}{k}+\dfrac{1}{k+1}+\cdots +\dfrac{1}{n-1})$

これを最大にする $k$ を求めればよい。 $n$ が十分大きいとき
$\dfrac{1}{k}+\dfrac{1}{k+1}+\cdots +\dfrac{1}{n-1}\simeq \log \dfrac{n}{k}$ なので(→注),$\dfrac{k}{n}\log \dfrac{n}{k}$ を最大にする $k$ を求めればよい。

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

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

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

考察,補足

  • 今回は「 $n$ 人の中で一番タイプな人と交際できる確率を最大化する」という最良選択問題を考えました。一方「交際する人の順位の期待値を最小化する」という順位最小化問題も考えられます。
    順位最小化問題の方が現実的な気がしますが,最適停止問題の方が解析が簡単で結果も美しいので有名です。
  • $n$ がどんなに大きくても $37$ %くらいの確率で一番好きな人と交際できるというのは驚きです。
  • 現実はこんなに単純ではありません。人の性格や好みは時間変化します。タイプじゃなかったけど長年付き合ってみると好きになった,嫌いになったなんてこともあるでしょう。
なお,$n$ が小さい人にはこの理論は通用しません。

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

分野: データの分析,確率  レベル: マニアック