秘書問題

方針：いちばん良い人の位置 $k$ で場合を分ける。各場合の確率を、記録更新の回数 の補題「相対順位の列と並べ方の 1 対 1 の対応」を使って、相対順位の列を数えて求める。
段 1（成功の言いかえ）。$r\ge2$ とする。いちばん良い人（値 $n$）が $k$ 番目にいるとする。$k< r$ なら、その人は見送られるので失敗である。$k\ge r$ のとき、成功するのは、$r$ 番目から $k-1$ 番目までに記録が 1 つもないときであり、そのときに限る。実際、記録がなければ、$k$ 番目は記録（それまでの誰よりも良い）なので、そこで採用して成功する。記録があれば、最初の記録の人を採用して終わり、その人は $k$ 番目の人ではないので失敗する。
段 2（相対順位で書く）。「値 $n$ が $k$ 番目にある」ことは、「$k$ 番目が記録で、$k+1$ 番目から $n$ 番目は記録でない」ことと同じである（$k$ 番目より後に記録があれば、その人は値 $n$ より良いことになり矛盾し、逆に $k$ 番目の後に記録がなければ $k$ 番目の値は全体の最大である）。よって、$k$ 番目にいちばん良い人がいて成功する事象は、相対順位の列が
$$ r_k=1,\qquad r_j\ne1\quad(j=r,\ldots,k-1\text{ と }j=k+1,\ldots,n) $$
を満たす事象である。
段 3（列を数える）。$1\le r_j\le j$ を満たす列のうち、段 2 の条件を満たすものを数える。$r_k$ は $1$ の 1 通り、条件のついた $j$ では $r_j$ は $2,\ldots,j$ の $j-1$ 通り、それ以外の $j$（$j< r$）では $j$ 通りである。並べ方と相対順位の列は 1 対 1 に対応し、並べ方は $n!$ 通りで同様に確からしいので、確率は
$$ \frac1k\prod_{j=r}^{k-1}\frac{j-1}j\prod_{j=k+1}^{n}\frac{j-1}j $$
である（列の個数を $n!=1\cdot2\cdots n$ で割ると、各 $j$ について「選べる個数 $\mathbin{÷}\,j$」の積になる）。積は隣どうしで約分されて
$$ \prod_{j=r}^{k-1}\frac{j-1}j=\frac{r-1}r\cdot\frac r{r+1}\cdots\frac{k-2}{k-1}=\frac{r-1}{k-1},\qquad\prod_{j=k+1}^{n}\frac{j-1}j=\frac kn $$
となる（$k=r$ のとき 1 つ目の積は項がなく $1$ で、右辺も $\dfrac{r-1}{r-1}=1$ である。$k=n$ のときの 2 つ目の積も同じく $1$ である）。よって確率は
$$ \frac1k\cdot\frac{r-1}{k-1}\cdot\frac kn=\frac{r-1}{n(k-1)} $$
である。
段 4（足す）。$k=r,r+1,\ldots,n$ の事象は互いに排反なので、足して
$$ P_n(r)=\sum_{k=r}^{n}\frac{r-1}{n(k-1)}=\frac{r-1}n\sum_{k=r}^{n}\frac1{k-1} $$
を得る。$r=1$ のときは 1 人目を採るので、1 人目がいちばん良い確率 $\dfrac1n$ である。$\square$

1. $r\ge2$ とする。$T_{r-1}=\dfrac1{r-1}+T_r$ なので
   $$ P_n(r)=\frac{r-1}n\left(\frac1{r-1}+T_r\right)=\frac1n+\frac{r-1}nT_r $$
   である。一方 $P_n(r+1)=\dfrac rnT_r$ なので、引いて $P_n(r+1)-P_n(r)=\dfrac1nT_r-\dfrac1n$ である。$r=1$ のときは、$P_n(2)=\dfrac1nT_1$、$P_n(1)=\dfrac1n$ から同じ式になる。
2. $r< r^*$ なら、$r^*$ の決め方から $T_r>1$ なので、(1) により $P_n(r+1)>P_n(r)$ である。$r=r^*$ なら $T_{r^*}\le1$ なので $P_n(r^*+1)\le P_n(r^*)$ である。$r>r^*$ なら、$T_r< T_{r^*}\le1$ なので $P_n(r+1)< P_n(r)$ である。$\square$

$y=\dfrac1x$ は $x>0$ で減少するので、正の整数 $m$ について、$m< x< m+1$ なら $\dfrac1{m+1}<\dfrac1x<\dfrac1m$ である。区間 $[m,m+1]$ で積分して
$$ \frac1{m+1}<\int_m^{m+1}\frac{dx}x<\frac1m $$
を得る。右の不等式を $m=r,\ldots,n-1$ で足すと $\displaystyle\int_r^n\frac{dx}x=\log\frac nr< T_r$ である。左の不等式を $m=r-1,\ldots,n-2$ で足すと $T_r=\dfrac1r+\cdots+\dfrac1{n-1}<\displaystyle\int_{r-1}^{n-1}\frac{dx}x=\log\frac{n-1}{r-1}$ である。$\square$

方針：$r^*$ の決め方「$T_{r^*}\le1< T_{r^*-1}$」に lem-sec-log を当てはめる。
段 1（左の不等式）。$T_{r^*}\le1$ である。$r^*\le n-1$ で、$r^*=1$ とすると $T_1=1+\dfrac12+\cdots+\dfrac1{n-1}>1$ となり $T_{r^*}\le1$ に反するので $r^*\ge2$ である。lem-sec-log の左側から $\log\dfrac n{r^*}< T_{r^*}\le1$、つまり $\dfrac n{r^*}< e$ で、$r^*>\dfrac ne$ である。
段 2（右の不等式）。$n\ge6$ なので、段 1 から $r^*>\dfrac6e=2.2\ldots$、つまり $r^*\ge3$ で、$r^*-1\ge2$ である。$r^*$ は $T_r\le1$ となる最小の $r$ なので $T_{r^*-1}>1$ である。lem-sec-log の右側を $r=r^*-1$ で使うと $1< T_{r^*-1}<\log\dfrac{n-1}{r^*-2}$、つまり $\dfrac{n-1}{r^*-2}>e$ で、$r^*<\dfrac{n-1}e+2$ である。
段 3（成功の確率）。$P_n(r^*)=\dfrac{r^*-1}nT_{r^*-1}$ で、$T_{r^*-1}=\dfrac1{r^*-1}+T_{r^*}$ である。$1< T_{r^*-1}$ と $T_{r^*}\le1$ から
$$ 1< T_{r^*-1}\le1+\frac1{r^*-1} $$
である。各辺に $\dfrac{r^*-1}n$ を掛けて $\dfrac{r^*-1}n< P_n(r^*)\le\dfrac{r^*-1}n+\dfrac1n=\dfrac{r^*}n$ を得る。
段 4（極限）。段 1〜3 から
$$ P_n(r^*)>\frac{r^*-1}n>\frac{n/e-1}n=\frac1e-\frac1n,\qquad P_n(r^*)\le\frac{r^*}n<\frac{(n-1)/e+2}n<\frac1e+\frac2n $$
である。$n\to\infty$ で両端は $\dfrac1e$ に近づくので、はさみうちの原理により $P_n(r^*)\to\dfrac1e$ である。$\dfrac{r^*}n$ も (1) を $n$ で割った $\dfrac1e<\dfrac{r^*}n<\dfrac1e+\dfrac{2-1/e}n$ から $\dfrac1e$ に近づく。$\square$