大学数学の確率の問題で有名な秘書問題について解説！

こんにちは。

今回は、大学数学の確率の問題で有名な秘書問題について解説していきます。

まず秘書問題ってどんな問題なの？っていうところから見ていきましょう！

秘書問題とは

秘書問題とはいわゆる最適停止問題の一種です。

最適停止問題とはどこで止めるのが一番いいかということです。

日常でも例えば、今の彼氏、彼女と付き合ってるけど誰と結婚したら一番いいのだろう？

とか、ある会社で人を新たに雇いたいとします。応募者を面接するけど何人目で採用したら一番優秀な人を採用できるのだろう？

などと思ったことはありませんか？

この秘書問題はそんな悩みに対し、一種の数学的な答えを与えるものです。

ちなみに秘書問題とはこのような問題です。

あなたは秘書を1人雇いたいと思っています。

秘書募集の求人を出したところ、１００人の応募者があったとします。

このときこの１００人に対して１人ずつ面接を行っていきます。

つまり面接は最大１００回行えることになります。

しかし、以下のルールの元で雇うこととします。

・あなたは志望者に対して一人ずつ面接を行いますが、面接が終わったあとその人を採用するか、不採用にするかについて

その場で判断、つまり即決しなければなりません。

・一度不採用とした人については二度と採用することはできません。

・採用する人を決めたらそこで面接はすべて終了し、まだ面接を行っていない人については会うこともできず

帰ってもらいます。

このとき、どのようにすれば最も優秀な人を採用できる可能性が高くなるでしょうか？

これは直感的にあまり早すぎると後半でいい人がいる可能性が高いし、かといってあまり遅くても残った人では優秀でない人しかいない

という可能性も大いにありますよね？

ではどのように考えればいいのでしょうか？

以下で解説していきたいと思います。

解説の前に答えを先に発表してしまいます。

答えは、３７人目まではどんなに優秀な人がいても採用しない。ただし採用しない３７人について点数をつけ

一番点数の高い人と点数を記録しておく。

そして３８人目以降で３７人目までで一番優秀だった人を上回る優秀な人がいればその人を採用とする。

たったこれだけです。

３７人も無条件で不採用ってそんなことして大丈夫なの？と思いますよね？

では数学的にこれは最良であることを証明していきます。

いきなり一般的な証明を与えるのは困難なので、まずは具体的な数で考えてみましょう。

たとえば５０人目に最も優秀な人がいたとします。そして最初の１５人を無条件で不採用にするとします。

このとき一番優秀な人を選べるのはどのような場合なのでしょう？

これはこのような場合です。

１５人目までに２番目に優秀な人がいる場合

どういうことか解説します。

たとえば１０人目に２番目に優秀な人がいれば、その人の点数を記録します。

そして１５人目から４９人目を面接しますが、１０人目が２番目に優秀なので１０人目を超える点数の人は４９人目

までには現れない（１０人目の点数を超えるのは５０人目の人のみ）ので５０人目の最も優秀な人を採用することができるというわけです。

ではもし、１５人目から４９人目までの間で２番目に優秀な人が見つかったとします。このときは一番優秀な人を選ぶことができるのでしょうか？

答え　できない

なぜなら１５人目までで最も優秀な人を選んでも、この場合は４９人目までの２番目に優秀な人を採用してしまうので

一番優秀な人を採用できないのです。

つまり、５０番目が一番優秀で、１５人目から４９人目が次に優秀なら１５番目までで一番の人はその２人より点数

は下ということになりますよね？つまり２番目に優秀な人が一番だと勘違いして採用してしまうのです！

最後にもし１５人目までに一番優秀な人がいた場合は？この場合は当然ですがこの人より優秀な人はその後現れないので

採用できないということになります。

以上より、最も優秀な秘書を採用できるのは１５人目までに２番目に優秀な人がいる場合ということがわかりました。

ではこの議論を一般化してみましょう。

秘書の応募者がｎ人いて、一番優秀な人がｋ番目にいてなおかつｔ番目以前の応募者は全員不採用とする場合です。

最も優秀な人を選べるのはｔ番目までに（k-1）番目までの最高得点の人がいることとなります。

先ほどの例ですと１５番目までに４９番目までの最高得点の人がいるときとなります。

当然、１５番目までに一番優秀な人の次に優秀な人がいて、かつ一番優秀な人が現れる前にはその人を超える人がいないので

５０番目の人が選ばれます。

全体の２番手でかつ不採用の人をキープしておいて、後で１番の人がきたらその人に乗り換えるという方法です。

この方法で必ず１番優秀な人が採用できます。

この確率は(k-1)人中１番目の人がｔ人の中に入っていればいいので（t人以降に入っていればk番目の一番優秀な人を選ぶ前にその人を選んでしまう）

(k-1)人からｔ人選ぶのと同じことになるので

t /(k-1)となります。

ここで注意しないといけないのは一番優秀な人が不採用になるｔ人目までに入っている場合です。

このときは絶対に採用できないので確率は０となります。

よって

t≧kのとき　０

t<ｋのとき t/(k-1)

となります。

そして一番優秀な人がk番目にいる確率は、n人の中で一番優秀なのが１人より1/nとなります。

よって一番優秀な人がk番目にいて、かつ一番優秀な人が不採用になるｔ人目までに入っている確率は

1/n＊t/(k-1)となります。

一番優秀な人はどこにいるか指定されてないのですべての確率を足し合わせて

1/n＊Σ(k=t+1~n) t/(k-1)

注意　t<ｋのとき t/(k-1)なのでkはtより大きい。つまりkは(t+1)から始まってnまでいく。

よってkに関係ないtをくくりだして

t/n＊Σ(k=t+1~n) 1/(k-1)

=t/n＊(1/t+1/(t+1)・・・＋1/(n-1))

これを計算していきますが、この計算がやっかいです。

元記事には近似した答えしか載っていませんでしたが答えにlogが入っているので積分かな？という見当は付きそうです。

さて、y=1/xのグラフでx=tとx=nのところを見て長方形を作って、長方形の面積と積分する範囲の面積を比較すると

1/t+1/(t+1)・・・＋1/(n-1)>∫(x=t~n)1/x dx

            =logn-logt

            =log(n/t)

よって1/n＊Σ(k=t+1~n) t/(k-1)=t/n＊log(n/t)となり、

この式が最大となるtを求めることとなります。

f(t)=t/n＊log(n/t)とおきます。

これをtで微分して

f'(t)=(t/n)'＊log(n/t)+t/n＊(log n/t)'

     =1/n＊log(n/t)-1/n

これが0となるtを求めると

1/n＊log(n/t)-1/n=0

1/n＊log(n/t)=1/n

log(n/t)=1から

n/t=eとなり、

t=n/eとなります。

よってn/e(人)まで不採用にしてそれ以降でn/e人までで一番優秀な人より優秀な人が出れば

その人を採用すればいいことになります。

そして最も優秀な人を選べる確率はt/n＊log(n/t)にt=n/eを代入すればいいので代入すると

1/eとなり、約３７％となります。

いかがだったでしょうか？

注意

理想と現実は違う

この問題はあらかじめ何人と付き合うなど決めていますが、実際一生で何人と付き合うかなんてわかるはずもありません。

何十人と付き合う人もいますし、誰とも付き合えない人もいると思います。

あくまで数学的な理想論であって現実とはかけ離れている場合が多いことご了承ください。

大学数学の授業や数学書の内容が理解できない。そういった学生さんや社会人のために数学教室を運営しているのでぜひご検討ください。

大人の数学教室のホームページはこちら

参考文献

[1] 数学の面白いこと・役に立つことをまとめたサイトー秘書問題 – 結婚相手や恋人はこうやって選ぶのがベスト！