趣味の数学とプログラム。楽しい数学の世界へようこそ!

秘書問題

秘書問題と呼ばれる、ちょっと面白い数学の問題です。

秘書を募集したところ、たくさんの応募者がありました。

採用するのは1名のみ

一人ずつ面接して、その場で採用か不採用か決めます(ちょっと乱暴ですが)

最初の何人かを無条件に不採用にして、採点だけしておきます。

その後は、それまでの面接者の採点結果と比較して、今回の方がよければ採用し、以降の面接はストップ(一旦不採用になった人の復活はありません)

この方法で、一番いい人を採用する確率は?

 

最初に断る人の中に、一番の人が入っている可能性もあります

 

一番の人が後ろの方にいる場合、それまでに他の人を採用してしまう可能性もありますね。たとえば、二番の人が前の方にいるとか。

 

応募者の人数に左右されるでしょうか。

応募者が20人、100人、1000人、それぞれの場合に、最初に断る人数ごとに確率を計算してみました。グラフにすると

法則がありそうですね。

実は、人数をn人とすると、\(k = \large{\frac{n}{e}}\)(eはネイピア数 2.718・・・)のときに、確率は最大になりその確率は、人数によらず \(\large{\frac{1}{e}}\)と導き出されます。

人数に、小数点以下はありえないので、20人なら最初の7人、100人なら37人、1000人なら368人を断ることにすると、約37%の確率で一番の人を採用することができます。

MEMO

n人:応募人数
k人:断る人数
 
・全体で一番いい人が、k+1番目にいる場合 条件クリア! その確率は\(\large{\frac{1}{n}}\)
k+2番目にいる場合 k+1番目を断る必要がある、即ち、(k+1)番目までの一番いい人は、断った中にいる必要がある。その確率は、\(\large{\frac{1}{n}\times\frac{k}{k+1}}\)
 
t番目にいる場合 (t-1)番目までの一番いい人は、断った中にいる必要があり、その確率は、\(\large{\frac{1}{n}\times\frac{k}{t-1}}\)
 
全て(k+1番目~n番目)足した
\(\large{\frac{k}{n}(\frac{1}{k}+\frac{1}{k+1}+・・・+\frac{1}{n-1})}\)を最大にするkを求める。
 
nが十分大きいとき、
\(\large{\frac{1}{k}+\frac{1}{k+1}+・・・+\frac{1}{n-1}}\normalsize{≒\log}\large{\frac{n}{k}}\)
となるので \(\large{\frac{k}{n}}\normalsize{\log}\large{\frac{n}{k}}\)を最大にするkを求める。
 
kで微分すると\(\large{\frac{1}{n}}\normalsize{\log}\large{\frac{n}{k}-\frac{1}{n}}\)となり\(\large{\frac{n}{k}}=e\)のときに最大で、成功確率は
 
\(\large{\frac{1}{n}}\normalsize{\log}\large{\frac{n}{k}}\normalsize{=\log}\large{\frac{e}{e}=\frac{1}{e}}\normalsize{≒0.37}\)

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です