秘書問題
最良の応募者を選択できるのは、 1 , 2 , ... , k {\displaystyle 1,2,\ldots ,k} 人目の中で最も良い応募者が 1 , 2 , ... , r {\displaystyle 1,2,\ldots ,r} 人目の中にいるときであり、 その事象の生起確率は r / k {\displaystyle r/k} . ゆえに成功確率は
P ( r ) = ∑ k = r n − 1 ( ( 1 n ) ( r k ) ) {\displaystyle P(r)=\sum _{k=r}^{n-1}\left(\left({\frac {1}{n}}\right)\left({\frac {r}{k}}\right)\right)}
= ( r n ) ( 1 r + 1 r + 1 + ⋯ + 1 n − 1 ) {\displaystyle =\left({\frac {r}{n}}\right)\left({\frac {1}{r}}+{\frac {1}{r+1}}+\cdots +{\frac {1}{n-1}}\right)}
≃ ( r n ) ( log  n − log  r ) = − ( r n ) log  ( r n ) {\displaystyle \simeq \left({\frac {r}{n}}\right)(\log n-\log r)=-\left({\frac {r}{n}}\right)\log \left({\frac {r}{n}}\right)}