秘書問題(最良選択問題)

1位の人を採用するには現段階での暫定1位(今までで1番いい人)を採用しなければいけません。
まず\(k\)人目までを無条件で断りそれ以降の人で暫定1位を採用するのがいい方法となります。
この\(k\)を求めます。
1位の人が\(t\)番目の面接者だとするとこの確率は\(\frac{1}{n}\)となります。
\(t\leq k\)のとき、\(k\)人目までは無条件で断るので1位の人を選べる確率は0となります。
\(k<t\)のとき、1位の人を選ぶにはそれまでの\(t-1\)人中の1位の人が始めの\(k\)人の中に入っていなければいけない。
なぜなら1位の人の面接の前に他の人が採用されてしまうからである。
これより、1位の人が\(t\)番目なら選ばれる確率\(P\left(t\right)\)は\(P\left(t\right)=\frac{k}{t-1}\)となる。
また、1位の人が\(t\)番目の面接者となる確率は\(\frac{1}{n}\)となります。
従って、\(P\left(t\right)\)に\(t\)番目の面接者となる確率\(\frac{1}{n}\)を掛け、\(t\)について\(k+1\)から\(n\)までの和をとると、1位の人を選べる確率\(P\)となる。
\begin{align*} P & =\sum_{t=k+1}^{n}\frac{P\left(t\right)}{n}\\ & =\frac{1}{n}\sum_{t=k+1}^{n}\frac{k}{t-1}\\ & =\frac{k}{n}\sum_{t=k}^{n-1}\frac{1}{t}\\ & =\frac{k}{n}\frac{1}{n}\sum_{t=k}^{n-1}\frac{1}{\frac{t}{n}}\\ & \fallingdotseq\frac{k}{n}\int_{\frac{k}{n}}^{1}\frac{1}{x}dx\\ & =\frac{k}{n}\left[\log x\right]_{\frac{k}{n}}^{1}\\ & =-\frac{k}{n}\log\frac{k}{n} \end{align*} となるので、\(P\)を最大にする\(k\)を求めればいい。
\(P\)を\(k\)で微分すると、
\begin{align*} \frac{dP}{dk} & =-\frac{d}{dk}\frac{k}{n}\log\frac{k}{n}\\ & =-\frac{1}{n}\left[\frac{d}{dx}x\log x\right]_{x=\frac{k}{n}}\\ & =-\frac{1}{n}\left[\log x+1\right]_{x=\frac{k}{n}} \end{align*} となるので増減表は
\[ \begin{array}{|c|c|c|c|c|c|} \hline x & 0 & \cdots & \frac{1}{e} & \cdots & \infty\\ \hline P' & & + & 0 & - & \\ \hline P & & \nearrow & \frac{1}{e} & \searrow & \\\hline \end{array} \] となる。
これより、\(k=\frac{n}{e}\)のとき確率\(P=-\frac{1}{e}\log\frac{1}{e}=\frac{1}{e}\fallingdotseq0.368\)で1位の人を選ぶことができる。