最良選択問題とか秘書問題とか結婚問題とか~? | ガミーのブログ

ガミーのブログ

勘ぐりと空耳とファンタジー

秘書を採用することとする。
採用条件は、
1)n人の応募者が居る。
2)そのn人の応募者と順番に面接試験をする。
3)面接の都度、採否を決定する。

4)面接は一度だけである。
5)一度断った応募者は二度と面接しない。
<問題>これらの条件下で「一番優秀な応募者を採用できる確率を最大にする」にはどうすれば良いか?そこで、k人目まで無条件で断り、k+1人目以降で「今までで一番優秀な人」が現れたら採用する、という戦略を取ることにした場合、このkをどの様に計算するか?
<答え>
一番優秀な応募者がいる確率は、1/n。(当然、一人しか居ないから)
t人目の応募者を採用とする(tより前の面接者を採用しない)事のできる(つまりtが最優秀である)確率は、
 

t≦k のとき 0 (k人目まで無条件で断るから)
t>kのとき k/(t-1)

従って、求める確率p(k)は、p(k)=Σ(1/n)(k/(t-1))、t=k+1、k+2、・・・・・、n (積の法則)
今、十分に大きい任意の正数Nに対し、n>Nならば
p(k)=(k/n){1/k+1/(k+2)+・・・・・・+1/n}≒(k/n)log(n/k)
※【S(x)=1+1/2+1/3+・・・・1/x、limS(x)≒log(x)】
p(k)に最大値が存在するとすれば、dp(k)/dk=0となるkの値を求めればよいから、
p´(k)=(k/n)´log(n/k)+(k/n)log´(n/k)=(1/n)log(n/k)+(k/n)(-1/k)=0
即ち、(1/n)log(n/k)=(1/n) ∴log(n/k)=1 よって、n/k=e。(ここでeは、自然対数の底≒2.71828)
従って、k=n/eのとき、求める確率p(k)は最大となり、その値は、
p(k)=(1/e)log(e)=1/e≒0.367879 と計算できる。

結論:この方式は、何人応募者が来ようと、初めから約37%の人(例えば100人の応募者があった場合、初めから37人)を無条件で不採用とし、38%目の応募者からそれまでの応募者より、より優秀なのを採用すれば、一番優秀な応募者を採用できる確率を最大(約37%)にする事が出来る、ということを示している。