統計学の勉強をしているときに出会ったのが「最良選択問題」という、ある条件のもとで最も良い選択をするときにどうすればよいか、という問題です。
こう書くとなんのことがわからないのですが、たとえば次のように説明できます。
- あなたは秘書を雇う必要があり、すでに候補者が$n$人いる。一人ずつ面接し、その場で採用か不採用かを決める。このような状況で最良の応募者を選ぶにはどうすれば良いか。
- あなたは最良の結婚相手を見つけたい。人生で付き合える$n$人の異性の中で、あなたは何人目の異性と結婚すべきか。
定式化
この問題は、「最良選択問題」や「秘書問題」と言われるもので、wikipedia:秘書問題にも詳細の記載があります。これを定式化すると次のようになります。
- あなたは$n$人の候補者の中から一人を選ぶ必要がある
- $n$人の評価には優劣をつけることができ、その順位は重複しない
- 面接前までは候補者の順位は分からず、ランダムに面接順を決める
- 面接後、その応募者を採用するか否かは即座に決めなければならない。また、その判断は後で変更できない
このような状況で、最も評価の高い候補者を採用できるか。
何人目の候補者を採用するかを決め打ちする
もう運を天に任せて、最初の候補者を採用する!という場合、その候補者が最も良い候補者である確率は$\frac{1}{n}$です。これは、最も良い候補者が最初に面接される確率と同じです。
最初の$k$人は様子見して、$k+1$番目以降の候補者でそれまでの面接者よりも良い候補者がいれば採用する
こちらの戦略が秘書問題に置けるターゲットです。考え方は単純で、次の2つの場合分けになります。
1. 採用を見送る最初の$k$人の中に「最も良い候補者」が入っている場合
前者の場合、「最も良い候補者」を採用できる確率は0ですね。
2. $k+1$番以降に面接する人の中に「最も良い候補者」が入っている場合
後者の場合、「最も良い候補者」を採用できる確率はどうなるでしょうか。
最も良い候補者との面接順が$t \;(k<t \leq n)$番目であると仮定します。
「$t-1$番目までの面接の中で最も優秀な人」が$k$番目までの候補者に入っていれば、その人を基準に面接評価が行われるので、$t$番目までの面接が行われ、最良の候補者が採用されます。
逆に「$t-1$番目までの面接の中で最も優秀な人」が$k+1$番目以降に面接される場合、その人がすぐに採用されることになり、「最も良い候補者」の面接は行われません。結果として「最も良い候補者」を採用できないことになります。
つまり、「最も良い候補者」が$t$番目である場合、その人が採用される確率は$\displaystyle \frac{k}{t-1}$になります。「$t-1$番目までの面接の中で最も優秀な人」が最初の$k$番目までに面接されれば、「最も良い候補者」が採用できる分けですから。
解
$t$の範囲は$k < t \leq n$なので、最も良い候補者を採用できる確率$P(k)$は次のようになります。
$$ \begin{align} P(k) &= \sum _{t=k+1}^{n} \frac{k}{t-1} \frac{1}{n} \newline &= \frac{k}{n} \sum _{t=k+1}^{n} \frac{1}{t-1} \newline &= \frac{k}{n} \left( \frac{1}{k} + \frac{1}{k+1} + \cdots + \frac{1}{n-1} \right) \newline &= \frac{k}{n} \sum _{t=k}^{n-1} \frac{1}{t} \newline &= \frac{k}{n} \frac{1}{n} \sum _{t=k}^{n-1} \frac{1}{\frac{t}{n}} \newline \end{align} $$
ここで$n \rightarrow \infty$とすると、区分求積法の考え方から、$\displaystyle \frac{1}{n} \sum _{t=k}^{n-1} \frac{1}{\frac{t}{n}}$は次のようになります。
$$ \begin{align} P(k) &= \frac{k}{n} \int _{\frac{k}{n}} ^{1} \frac{1}{x} dx \newline &= \frac{k}{n} \left[ \log x \right] _{\frac{k}{n}} ^{1} \newline &= - \frac{k}{n} \log \frac{k}{n} \newline &= \frac{k}{n} (\log n - \log k) \end{align} $$
これで「最も良い候補者」を採用できる確率がもとまったので、この確率を最大化する条件を考えましょう。この式が最大になるとき、$\displaystyle \frac{dP(k)}{dk}=0$となります。この方程式を変形していくと、$\displaystyle \frac{n}{k}=e$が導けます。
$$ \begin{align} \frac{dP(k)}{dk} &= \frac{1}{n} (\log n - \log k) - \frac{k}{n} \frac{1}{k} \newline &= \frac{1}{n} (\log n - \log k - 1) = 0 \newline \therefore \log n - \log k = \log \frac{n}{k} = 1 \newline \therefore \frac{n}{k} = e \newline \end{align} $$
この式を$P(k)$の式に代入すれば、最も良い候補者を採用できる確率は次のようになります。
$$ P\left(\frac{e}{n}\right) = - \frac{1}{e} \log \frac{1}{e} = \frac{1}{e} $$
以上から、面接は$k=\frac{n}{e} \approx 0.368 n$番目まで行い、その後に面接した候補者の中で最も良い候補者を採用することで、最も良い候補者を採用できる確率は$\frac{1}{e} \approx 0.368 = 36.8\%$まで上がることになります。
まとめ
採用を考えた時、最初の$\displaystyle \frac{n}{e}$人を問答無用で不採用にするということは仁義に反するので、この戦略をそのまま採用できなさそうです。
