秘書問題（お見合い問題）とその解法

更新 2021/03/07

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

秘書問題とは

お見合い問題，結婚問題，最良選択問題などと言うこともあります。お見合いで説明します。現実的でない仮定もありますがご容赦ください。
nnn 人と順番にお見合いする。
お見合いした瞬間に交際するかしないか決めないといけない。
交際を申し込めば相手はOKしてくれる。
交際をスタートしたら他の人とは二度とお見合いはできない。
一回断った人とは二度と交際できない。
nnn 人の中で一番タイプな人と交際できる確率を最大にしたい。
どういう戦略を取ればよいか？

秘書問題の最適戦略

$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}\left(\dfrac{1}{k}+\dfrac{1}{k+1}+\cdots +\dfrac{1}{n-1}\right)$

これを最大にする $k$ を求めればよい。 $n$ が十分大きいとき

$\dfrac{1}{k}+\dfrac{1}{k+1}+\cdots +\dfrac{1}{n-1}\fallingdotseq \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}\fallingdotseq 0.37$

注： $n$ が十分大きいとき $1+\dfrac{1}{2}+\cdots +\dfrac{1}{n}\fallingdotseq \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:難しめの数学雑学・ネタまとめ

この記事の監修者

マスオ

高校数学の美しい物語の管理人。「わかりやすいこと」と「ごまかさないこと」の両立を意識している。著書に『高校数学の美しい物語』『超ディープな算数の教科書』。記事の誤植やわかりにくい等のご指摘はお気軽にメールください！