秘書問題 – 結婚相手や恋人はこうやって選ぶのがベスト！
秘書問題とは、”たくさんの秘書志望者の中から一番いい秘書を雇える確率を最も高めるにはどうしたらよいか？”という問題です。
秘書選びでなくとも日常生活には一番いい人、一番いい物を選びたい場面が多々あると思いますが、この問題はそんな場面に使える興味深いものです。
ここでは、秘書問題とその解答を詳しく説明しています。
数学的にも非常に美しいものですので、楽しんでくださね。
最適停止問題
ここで、紹介する”秘書問題”とは最適停止問題の一種です。
「最適停止問題？」
なんだが難しそうな単語が出てきましたが、意味は簡単です。
最適停止問題を言い換えると、
どこで止めるのが一番イイか？
ということです。
日常でもこんなことを思うときが結構ありますよね。
パチンコやポーカー、スロットゲームなどで、
「いますごい勝ってるけど、いつやめよう？損しないうちに終わりたいけど、これからもっと当たるかも知れないし…」
という感じです。
こんなモヤモヤに対して、
「このときにやめるのが一番賢い！」
と理論的に決定するのが”最適停止問題”を解くということです。
理論的に最適停止問題が解ければ、日常生活に役に立つと思いませんか？
止めるタイミングで悩むことって結構多いですよね。
ここで紹介した方法がギャンブルに役に立つかは分かりませんが、日常生活で必ず使えるシーンはあると思います。
スポンサーリンク
秘書問題
では、本題の秘書問題を紹介しましょう。
秘書問題とは簡単に言うと、
秘書を選ぶときにもっとも良い秘書を選ぶためにはどうしたらよいか？
という問題です。以下で具体的に問題を紹介しましょう。
あなたは秘書を雇いたいと思っています。しかも、できるだけ優秀な秘書です。
秘書募集の広告を出したところ、100人の秘書志望者が集まってきました。
この100人の志望者に対して、今から一人ひとり面接を行っていきます。つまり最大で100回面接を行います。
しかし、このとき以下のルールを守らなければいけません。
- あなたは志望者に対して一人ひとり面接を行いますが、一人の面接が終了後、その人を採用か不採用かをその場で決断しなければなりません。
- 一度、不採用とした人は二度と採用することはできません。
- 採用を決めたら、そこで面接会は終了し、まだ面接を行っていない人達については会うこともなく帰っていただきます。
この三つです。
どのようにすれば、志望者の中で一番優秀な秘書を採用できる可能性が高くなるでしょうか？
実際に面接を行ったとしましょう。
そして、50人目で「この人、結構いいなぁ～」となったとします。
ここで決断を迫られます。
まだ、51人目から100人目の50人が面接を控えてます。
ここでこの人に決めてしまうと、残りの50人は見ることができません。もしかすると、この人よりもいい人が残りの50人の中にいるかもしれないのです。
ここでこの人を不採用にすると、とりあえずは51人目から先を見ることができます。しかし、これ以降、この人よりもいい人がいない可能性だってあるのです。
一度不採用と決めたら、もう決断は変えてはいけないので、慎重に選ぶ必要があります。
う～ん、悩ましい。どうするのが一番良い選択なのでしょうか？
私の直観だと、”真ん中少し後ろぐらい(70人目～80人目)でこれまでで一番いい人が現れたら、その人を採用する”のがいい気がしますが…
これは完全にわたしの直観です。みなさんはどう考えますか？
正解と解説
正解を発表します。
一番良い秘書を選ぶ確率をもっとも高くするには、
- 37人までは何があっても採用しない（ただし、点数は付けておいて、37人目までで一番良い点を記録しておく）。
- 38人目以降で、37人目までの最高得点を超えた人が現れれば、その人に決定する
です。
この選び方をすると、なんと37%の確率で一番良い秘書を選ぶことができるのです。
37%って高いと思いませんか？三回に一回はナンバー１秘書を採用できるのですから。
なんでそうなるの？
なぜ、上で説明した方法が最適なのでしょうか。それを考えていきましょう。
少し確率と数学の知識が必要になってきます。
具体的な数を仮定して考えてみよう
数学の複雑な問題は、まず具体的な数を仮定してイメージしやすくしてから考えるのが良いです。
ここでは、具体的に40番目にナンバーワン（1番良い人）がいると仮定しましょう。
そして、先頭から20番目の人までは、絶対に採用しないという戦略を立てたとします。
このときにナンバーワンを選べるときはどのような場合でしょう？
それは、39番目までの最高得点が20番目までに含まれていることが必要です。
例えば、18番目に39番目までの最高得点の人がいたとします。この人のことを暫定ナンバーワンと呼びましょう。※暫定ナンバーワンは本当のナンバーワンではないことに注意です
すると、20番目まで無条件に不採用にしたときに、最高得点はこの暫定ナンバーワンの点数になっています。
39番目までの最高得点が暫定ナンバーワンの点数ということは、その後40番目の本当のナンバーワンへたどり着くまで、この点数を超える人はいませんね。
では、暫定ナンバーワンが20番目までにいない場合はどうでしょうか？例えば、38番目に暫定ナンバーワンがいたとします。
このときは、40番目の本当のナンバーワンまでたどり着けません。
なぜかというと、20番目までで決まった最高得点が必ず38番目の暫定ナンバーワンで更新されてしまい、暫定ナンバーワンを選んでしまうことになるからです。
つまり、40番目にナンバーワンがいて、20番目までを無条件に不採用とする場合、
ナンバーワンを選ぶための条件は、
20番目までに39番目までの最高得点者いること
となるのです。
一般的議論に発展させよう
上の条件を一般的に表現しましょう。するとこうなります。
ナンバーワンが\(k\)番目にいて、\(t\)番目までを無条件に不採用とする場合、
ナンバーワンを選ぶための条件は、
\(t\)番目までに、\(k-1\)番目までの最高得点者いること
です。
また、いまは面接に来た志望者は100人ですが、一般性を持たせるために\(n\)人として議論を進めます。
これより、この条件を満たすための確率は、\(k-1\)から\(t\)を選ぶ確率と同じですので、
$$\frac{t}{k-1}$$
となります。
ただし、忘れてはいけないのが、ナンバーワンが無条件に不採用とする\(t\)番目までに含まれてしまっている場合(\(t \geq k\))です。
この時はもちろん、選べる確率は\(0\)なので、ここまでをまとめると、ナンバーワンを選べる確率は、
\begin{align}
& t \geq k \text{のとき} 0 \\
& t < k \text{のとき} \frac{t}{k-1} \\
\end{align}
そして、ナンバーワンがk番目にいる確率は\(\frac{1}{n}\)です。
よって、ナンバーワンがk番目にいて、なおかつナンバーワンを選べる確率は、
$$\frac{1}{n} \frac{t}{k-1}$$
となります。
ナンバーワンはどこにいるかは分からないわけですから、すべての場合について足すと、
$$\frac{1}{n} \sum_{k=t+1}^{n} \frac{t}{k-1}$$
となります。
ここで、シグマの開始が\(k=t+1\)となっていることに注意です。上で見たように、\(t \geq k\)では、選べる確率が\(0\)だからですね。
よって、ナンバーワンを選べる確率は、
\begin{align}
& \frac{1}{n} \sum_{k=t+1}^{n} \frac{t}{k-1} \\
& = \frac{t}{n} \left( \frac{1}{t} + \frac{1}{t+1} + \cdots + \frac{1}{n-1} \right) \tag{1}
\end{align}
となります。
ここで、この確率を最大とする\(t\)を求めればよいですが、
$$\frac{1}{t} + \frac{1}{t+1} + \cdots + \frac{1}{n-1}$$
の部分は、\(n\)が十分に大きいとき、
$$\frac{1}{t} + \frac{1}{t+1} + \cdots + \frac{1}{n-1} \sim \log{\frac{n}{t}}$$
と書けます。近似ですね。
なので、式(1)は次のように書き直すことができます。
$$\frac{1}{n} \sum_{k=t+1}^{n} \frac{t}{k-1} = \frac{t}{n} \log{\frac{n}{t}}$$
です。
これはナンバーワンを選べる確率ですので、この右辺を最大とする\(t\)を求めましょう。
最大を求めるという行為は、微分したものが\(0\)になるということです。
したがって、上の式の右辺を\(t\)で微分して、
$$\left( \frac{t}{n} \log{\frac{n}{t}} \right)^\prime= \frac{1}{n} \log{\frac{n}{t}} – \frac{1}{n}$$
とし、これが\(0\)になる\(t\)を求めると、
\begin{align}
\frac{1}{n} \log{\frac{n}{t}} – \frac{1}{n} & = 0 \\
\frac{1}{n} \log{\frac{n}{t}} & = \frac{1}{n}\\
\log{\frac{n}{t}} & = 1 \\
\frac{n}{t} & = e
\end{align}
つまり、
$$t = \frac{n}{e}$$
の時にナンバーワンを選ぶ確率が最大となるのです。\(t\)というのは”何人目までを不採用にするか”という人数のことでした。
自然対数の底であるネイピア数\(e\)が登場したのが面白いですね。
いま、志望者\(n\)は100人でしたので、この式に\(n=100\)を代入し、\(e=2.72\)として計算すると、
$$t = \frac{n}{e} = \frac{100}{2.72} = 36.765 \simeq 37$$
です。
よって、100人の秘書志望者から、もっとも良い秘書を選びたい場合の最良の選択は、
37人目までを無条件に不採用とし、その後今まで（37人目まで）の最高記録を上回った人を採用する
というふうになります。
ナンバーワンを選べる確率は？
ついでにナンバーワンを選べる確率も出しておきましょう。
ここまで導出してきた過程の式を見直してください。途中に、”ナンバーワンを選べる確率”の式があったと思います。
それは、以下のような式でした。
$$\text{ナンバーワンを選べる確率} = \frac{1}{n} \sum_{k=t+1}^{n} \frac{t}{k-1} = \frac{t}{n} \log{\frac{n}{t}}$$
この式に\(n=100\)と\(t=37\)、そして\(\frac{n}{t}=e\)を代入して計算すると、
$$\text{ナンバーワンを選べる確率} = \frac{t}{n} \log{\frac{n}{t}} = \frac{37}{100} \log{e} = 37\%$$
となります。
確率は1/3よりも少し高いくらいです。
これは驚きですね。100人の中からナンバーワン秘書を選べる確率は3回に1回よりも多いのです。
最後にまとめておきましょう。
志望者が\(n\)人の場合、無条件に不採用とする人数は、
$$\text{無条件に不採用とする人数} = \frac{n}{e}$$
であり、このときナンバーワン秘書を選べる確率は、
$$\text{ナンバーワンを選べる確率} = \frac{1}{e} = 37\%$$
となります。
ナンバーワン秘書を選べる確率は志望者の人数によらず37%で一定です。
1000人でも1万人でも、37%なんです。面白いですね。
スポンサーリンク
まとめ
- 秘書問題とは、どこで止めるのが一番良いかを考える”最適停止問題”である
- もっとも選び方は、志望者が\(n\)人の場合、\(n/e\)人目までを不採用とし、その後に最高得点の人が現れたら採用する
- この方法で最も良い秘書を雇える可能性は37%である。これは志望者の数にはよらない
- さあ、この方法を使ってベストな恋人・結婚相手を選ぼう！