マクドナルドでアルバイトの採用を数理的に最適化【解説編】

この記事はマクドナルドでアルバイトの採用を数理的に最適化したら衝撃の結果に！の解説記事です。細かいミスがあるかとは思いますが雰囲気だけでもお伝えできればと思います。

条件

志望者は$n$人、うち採用は1人
1人ずつ面接を行い、各面接の終わりに合否を決める。あとで覆すことはできない。
面接した中で最も得点の高い人がいたら採用
採用が決まった時点で全ておしまい。

目的

何人目までを無条件に不採用としたら最も高得点な人を採用できる確率が高いか。

定式化

まず$i$番目が最も高得点である確率は、
$$\frac{1}{n}$$
です。次に、$r-1$番目までを不採用としたとき、$i$番目を採用するための確率は、先頭$r-1$人の中に最も高得点がいなければいけない（$r$番目から$i-1$番目までに最高得点がいたら$i$番目にたどりつかずに終了してしまう）ので、
$$
\begin{cases}
0 & (i \leq r-1)\\
\displaystyle \frac{r-1}{i-1} & (i > r-1)
\end{cases}
$$

です。
よって、$𝑟−1$番目までを不採用としたとき、最も高得点な$𝑖$番目を採用する確率は$Q(i)$は
$$
\begin{eqnarray}
Q(i)=
\begin{cases}
0 & (i \leq r-1)\\
\displaystyle \frac{1}{n}\frac{r-1}{i-1} & (i > r-1)
\end{cases}
\end{eqnarray}
$$
です。
最も高得点な人が取れる確率$P(r)$は、
$$
\begin{align}
P(r)=&Q(1)+\dots+Q(r-1)+Q(r)+\dots+Q(n)\\
& = \frac{1}{n}\sum_{i=1}^{r-1} 0 + \frac{1}{n}\sum_{i=r}^{n}\frac{r}{i-1}\\
& =\frac{1}{n}\sum_{i=r}^{n}\frac{r}{i-1}\\
& =\frac{r-1}{n}\left( \frac{1}{r-1}+\frac{1}{r}+\ldots+\frac{1}{n-1} \right) 　ただしr>1
\end{align}
$$
となります。（$r=1$の時は$\displaystyle P(1)=\frac{1}{n}$になります。）

寄り道

問題はかっこの中の計算方法です。調和関数の部分和と言えばそれまでですが、念のために近似式を導出します。
まず、$\displaystyle \frac{1}{1}+\frac{1}{2}+\ldots+\frac{1}{n-1}$は、$ \displaystyle\int_{1}^{n} \frac{1}{x} dx = \log n $より大きいはずです。

次に、$\displaystyle \frac{1}{1}+\frac{1}{2}+\ldots+\frac{1}{n-1}$は、$ \displaystyle\ 1+\int_{1}^{n-1} \frac{1}{x} dx = 1+\log(n-1)$より小さいはずです。

つまり、
$$
\displaystyle \log n < \frac{1}{1}+\frac{1}{2}+\ldots+\frac{1}{n-1} < 1 + \log(n-1)
$$
です。よって$n$が十分大きいときは、
$$
\sum_{i=1}^{n}\frac{1}{i} \simeq \log n
$$
となります。これを用いれば$n$が十分大きいときは、
$$
\begin{align}
\sum_{i=r}^{n}\frac{1}{i} & = \displaystyle\sum_{i=1}^{n}\frac{1}{i} – \sum_{i=1}^{r}\frac{1}{i} \\
& \simeq \log\frac{n}{r}
\end{align}
$$
となります。

本題にもどります

最も高得点な人が取れる確率$P(r)$は
$$P(r)=\frac{r}{n}\log\frac{n}{r}$$
です。

解く

この$P(r)$を最大にする$r$を求めます。$P(r)$は上に凸で、$r$が0に近づけば0に近づき、$r$が$n$に近づいても0に近づきます。
$P(r)$を$r$で微分すると、
\begin{align}
&\frac{1}{n}\log\frac{n}{r}+\frac{r}{n} \left( -\frac{1}{r} \right)\\
&=\frac{1}{n}\log\frac{n}{r} – \frac{1}{n}
\end{align}
です。これが0の時に$P(r)$が最大になります。
それは、
$$
r=\frac{n}{e}
$$
の時です。
つまり$\displaystyle\frac{n}{e}$人目までを無条件に不採用としたら最も高得点な人を採用できる確率が最大になります。