No.379 - 高校数学で理解する秘書問題 [科学]
\(\newcommand{\bs}[1]{\boldsymbol{#1}} \newcommand{\mr}[1]{\mathrm{#1}} \newcommand{\br}[1]{\textbf{#1}} \newcommand{\ol}[1]{\overline{#1}} \newcommand{\sb}{\subset} \newcommand{\sp}{\supset} \newcommand{\al}{\alpha} \newcommand{\sg}{\sigma}\newcommand{\cd}{\cdots}\)
No.376「高校数学で理解するマッチング問題」に関連する話題を取り上げます。関連といっても "答が同じ数値になる" という意味の関連で、問題の性質は違います。
No.376 では、一般的にマッチング問題（出会いの問題）と言われるものを「席替えの成功確率」という形で提示しました。次のような問題です。
No.376 ではこの確率がおよそ 0.368 であること、また人数が増えると \(\dfrac{1}{e}=0.3678794411\cd\) に収束していくことを見ました（\(e\) は自然対数の底＝ネイピア数）。席替えが成功する確率はクラスの人数が少なければ低く、クラスの人数が多ければ高いと考えるのが普通でしょう。しかし実際にはクラスの人数にかかわらず（６人以上のクラスであれば）ほぼ 0.368 であり、それより成功確率が大きくなることはない。これが少々意外な結論でした。
この \(\dfrac{1}{e}\) という値が答になる別の確率の問題があります。「秘書問題（secretary problem）」です。これも少々意外な確率が答になります。
秘書問題
一般的に「秘書問題」と言われているものは次のようなものです。
もし、全員と面接してからそのうちの一人に採用を通知するなら話は簡単です。全員の相対的な優先順位をつけられるので、１位の人に通知すればよい。しかしこの問題では「面接した直後に採用するか採用しないかを通知する」必要があります。このとき「もし仮に全員と面接したとしたら優先順位が１位になるはずの人を採用できる確率」を最も大きくするのが問題です。面接の順序はランダムであることにも注意します。この問題を数学的に解析します。
最大値のカードを選択する戦略
説明の都合上、カードを選択する問題にします。秘書問題と等価です。
まず、\(\bs{n=5}\) の場合で、とりうる戦略と確率を分析します。裏返しのカードは順に \(C_1\)、\(C_2\)、\(C_3\)、\(C_4\)、\(C_5\) です。それぞれのカードの表に書かれている実数値を \(V(C_n)\) とします（\(V\::\) value）。戦略立案の条件は、
です。\(T\) を選択する確率を最大化する問題なので、この条件は必須です。この条件に合致する戦略は、以降で検討するように５種類あるので、それを \(S_n\:\:(n=0,\:1,\:2,\:3,\:4)\) で表します（\(S\::\) strategy）。また、戦略 \(S_n\) のときに 最大カード・\(T\) を選択できる確率を \(P(S_n)\) とします（\(P\::\) probability）。
戦略：\(S_0\)
最初のカード \(C_1\) は「無条件に選択するか、無条件に選択しないかのどちらか」です。利用できる情報は \(V(C_1)\) だけですが、\(V(C_1)\) を見ても全体の中での順位は全く判断できないからです。たとえ \(V(C_1)=0.00001\) などであっても、実数値はいくらでも小さくできるので、それが最大カードの可能性があります。
そこで、最初のカード \(\bs{C_1}\) を必ず選択する戦略を \(S_0\) とします。\(T\) の位置はランダムなので、
戦略：\(S_1\)
戦略：\(S_1\) では、\(\bs{C_1}\) は必ず選択せずに "様子見" とし、その後の \(C_2\)、\(C_3\)、\(C_4\) の状況で選択するカードを決めます。もし \(V(C_1) < V(C_2)\) なら \(C_2\) を選択します。もちろん、\(C_2\) が最大カード・\(T\) かどうかは分かりません。しかし、\(\bs{C_1}\) は \(\bs{T}\) ではない確証を得たので、\(\bs{C_1}\) を選択せずに済んだ（＝ \(T\) を選択する確率を高めた）という効果が出ました。なお「\(V(C_1) < V(C_2)\) であっても \(C_2\) を選択しない戦略」もありますが、その場合、\(C_1\) と \(C_2\) は必ず選択しないので、それは次項の "戦略：\(S_2\)" です。
もし \(\bs{V(C_1) > V(C_2)}\) なら、\(\bs{C_2}\) は \(\bs{T}\) でありません。従って \(C_2\) を選択せずに \(C_3\) を表にします。そして \(V(C_1) < V(C_3)\) であれば \(C_3\) を選択します。もちろん \(C_3\) が \(T\) かどうかは分かりませんが、\(\bs{C_2}\) に加えて \(\bs{C_1}\) も \(\bs{T}\) ではない確証を得たという効果が生じました。
もし \(V(C_1) > V(C_3)\) なら \(C_3\) は \(T\) ではないことが分かったので、\(C_4\) を表にします。なお「\(V(C_1) < V(C_3)\) であっても \(C_3\) を選択しない」という戦略も考えられますが、その場合、\(C_1\)、\(C_2\)、\(C_3\) は必ず選択しないので、それは後で述べる "戦略：\(S_3\)" です。
以下、同様の考え方で \(C_4\) を選択するかどうかを決めます。つまり、\(\bs{V(C_1)}\) より大きな実数値が出たとき、そのカードを選択します。この方針で \(C_4\) も選択しなければ、最終的にどれか１枚を選択する必要があるので \(C_5\) を選択します。
ここで、戦略：\(S_1\) で \(T\) を選択できる確率、\(P(S_1)\) を計算します。
\(\bs{C_1=T}\) のとき、\(C_1\) は選択しないので、
\(P(S_1)=0\)
\(\bs{C_2=T}\) のとき、必ず \(C_2\) を選択することになります。\(C_2=T\) となる確率は \(\dfrac{1}{5}\) なので、
\(P(S_1)=\dfrac{1}{5}\)
\(\bs{C_3=T}\) のとき、\(C_3\) を選択するのは \(V(C_1) > V(C_2)\) のとき（＝ \(C_2\) を選択しないとき）です。カードの並べ方はランダムなので、\(V(C_1) > V(C_2)\) となるか \(V(C_1) < V(C_2)\) かは半々です。従って、
\(P(S_1)=\dfrac{1}{5}\times\dfrac{1}{2}\)
\(\bs{C_4=T}\) のとき、\(C_4\) を選択するのは \(C_2\)、\(C_3\) を選択しない場合です。\(V(C_1)\)、\(V(C_2)\)、\(V(C_3)\) のうちの最大値がどれかは３つの場合がありますが、\(C_2\) か \(C_3\) が選択されないのは、最大値が \(V(C_1)\) のときだけです。つまり割合として \(\dfrac{1}{3}\) の場合です。従って、
\(P(S_1)=\dfrac{1}{5}\times\dfrac{1}{3}\)
\(\bs{C_5=T}\) のとき、\(C_5\) を選択するのは \(C_2\)、\(C_3\)、\(C_4\) を選択しない場合だけです。\(V(C_1)\)、\(V(C_2)\)、\(V(C_3)\)、\(V(C_4)\) のうちの最大値がどれかは４つの場合がありますが、\(C_2\)、\(C_3\)、\(C_4\) のどれもが選択されないのは、最大値が \(V(C_1)\) のときだけです。つまり割合として \(\dfrac{1}{4}\) の場合です。従って、
\(P(S_1)=\dfrac{1}{5}\times\dfrac{1}{4}\)
以上の５つケースは排他的なので、
\(\begin{eqnarray}
&&\:\:P(S_1)&=\dfrac{1}{5}\left(1+\dfrac{1}{2}+\dfrac{1}{3}+\dfrac{1}{4}\right)\\
&&&=\dfrac{1}{5}\cdot\dfrac{25}{12}\\
&&&=0.4167\\
\end{eqnarray}\)
が \(T\) を選択できる確率です。\(S_0\) よりは \(2\)倍以上の確率になりました。
戦略：\(S_2\)
この戦略では、\(C_1\)、\(C_2\) は様子見として選択せず（＝たとえ \(V(C_1) < V(C_2)\) であっても \(C_2\) を選択しない）、\(C_3\)、\(C_4\) の状況で判断します。選択の判断は \(S_1\) と同様です。つまり、様子見のカード、\(\bs{V(C_1)}\)、\(\bs{V(C_2)}\) より大きな実数値のカードを選択します。
\(C_1=T\) または \(C_2=T\) のとき、\(T\) は選択されません。
\(C_3=T\) のときは必ず \(T\) が選択されます。
\(C_4=T\) のとき、\(C_4\) が選択されるのは \(V(C_1)\)、\(V(C_2)\)、\(V(C_3)\) のうちの最大値が \(V(C_1)\)、\(V(C_2)\) のどちらかの場合です。\(V(C_3)\) が最大値だと \(C_3\) を選択してしまうからです。つまり \(\dfrac{2}{3}\) の割合です。
\(C_5=T\) のとき、\(C_5\) が選択されるのは \(V(C_1)\)、\(V(C_2)\)、\(V(C_3)\)、\(V(C_4)\)のうちの最大値が \(V(C_1)\)、\(V(C_2)\) のどちらかの場合です。そうでなければ \(C_3\) か \(C_4\) を選択してしまうからです。つまり \(\dfrac{2}{4}=\dfrac{1}{2}\) の割合です。まとめると、
\(\begin{eqnarray}
&&\:\:P(S_2)&=\dfrac{1}{5}\left(1+\dfrac{2}{3}+\dfrac{1}{2}\right)\\
&&&=\dfrac{1}{5}\cdot\dfrac{13}{6}\\
&&&=0.4333\\
\end{eqnarray}\)
となります。\(P(S_1)\) より大きい値です。
戦略：\(S_3\)
この戦略では、\(C_1\)、\(C_2\)、\(C_3\) は様子見として選択せず、\(C_4\) の状況で判断します。\(V(C_1)\)、\(V(C_2)\)、\(V(C_3)\) より \(V(C_4)\) が大きな実数値のときに、\(C_4\) を選択します。
\(C_1=T\) または \(C_2=T\) または \(C_3=T\) のとき、\(T\) は選択されません。
\(C_4=T\) のときは必ず \(T\) が選択されます。
\(C_5=T\) のとき、\(C_5\) が選択されるのは \(V(C_1)\)、\(V(C_2)\)、\(V(C_3)\)、\(V(C_4)\) のうちの最大値が\(V(C_4)\) ではない場合です。\(V(C_4)\) が最大値だと \(C_4\) を選択してしまうからです。つまり \(C_5\) が選択されるのは \(\dfrac{3}{4}\) の場合です。まとめると、
\(\begin{eqnarray}
&&\:\:P(S_3)&=\dfrac{1}{5}\left(1+\dfrac{3}{4}\right)\\
&&&=\dfrac{1}{5}\cdot\dfrac{7}{4}\\
&&&=0.3500\\
\end{eqnarray}\)
となり、\(P(S_2)\) より小さくなりました。
戦略：\(S_4\)
この戦略では \(C_1\)、\(C_2\)、\(C_3\)、\(C_4\) を選択せず、必ず \(C_5\) を選択します。\(C_5=T\) である確率は \(\dfrac{1}{5}\) であり、
\(P(S_4)=0.2\)
となって、\(P(S_0)\) と同じ確率です。
\(n=5\) の場合のまとめ
以上の検討結果により \(n=5\) の場合で可能な戦略は、「最大カード・\(T\) ではないとの確証を得たカードは選択しない」という条件のもとで \(S_0\) ～ \(S_4\) の５種であり、これ以外にはありません。各戦略ごとの確率をまとめると、
\(P(S_0)=0.2\)
\(P(S_1)=0.4167\)
\(P(S_2)=0.4333\)
\(P(S_3)=0.35\)
\(P(S_4)=0.2\)
で、\(n=5\) では「戦略：\(S_2\)」が最大カード・\(T\) を選択する確率を最大化します。この "確率最大化" の検討過程から、次のようなことが分かります。
一般化
\(n=5\) のときの考察を一般化し、\(n\) を \(n\geq2\) の任意の数とします。一般化された戦略は、
です。また、
とします。もし \(1\leq t\leq k\) なら \(T\) を選択することはないので、確率は \(0\) です。
\(\bs{k < t\leq n}\) のとき、\(\bs{T}\) を選択するのは、\(\bs{V(C_1)}\)、\(\bs{V(C_2)}\)、\(\bs{\cd}\)、\(\bs{V(C_{t-1})}\) の中での最大が、\(\bs{V(C_1)}\)、\(\bs{V(C_2)}\)、\(\bs{\cd\:V(C_k)}\) の中にある場合だけです。そうでなければ \(\bs{T}\) にたどりつく前に \(\bs{C_{k+1}}\)、\(\bs{\cd\:C_{t-1}}\) のどれかを選択してしまうからです。つまり \(T\) を選択するのは、割合としては \(\dfrac{k}{t-1}\) の場合です。
\(t\) 番目に \(T\) がある確率は \(\dfrac{1}{n}\) なので、\(T\) を選択する確率は、
\(\dfrac{1}{n}\cdot\dfrac{k}{t-1}\)
です。全体の確率は、この式を \(t\) の範囲 \((k < t\leq n)\) で合計し、
\(\begin{eqnarray}
&&\:\:P(S_k)&=\displaystyle\sum_{t=k+1}^{n}\dfrac{1}{n}\cdot\dfrac{k}{t-1}\\
&&&=\dfrac{k}{n}\displaystyle\sum_{t=k+1}^{n}\cdot\dfrac{1}{t-1}\\
&&&=\dfrac{k}{n}\displaystyle\sum_{t=k}^{n-1}\cdot\dfrac{1}{t}\\
&&&=\dfrac{k}{n}\left(\dfrac{1}{k}+\dfrac{1}{k+1}+\:\cd\:+\dfrac{1}{n-1}\right)\\
\end{eqnarray}\)
となります。
\(n=5\) のときには、上で計算したように戦略：\(S_2\) が最大確率になりました。では、一般の場合に最大確率になる戦略 \(S_k\) は何か。\(n=5,\:10,\:15,\:\cd\:,\:100\) の場合をパソコンで計算してみると、次の表の通りです。
\(n\) が大きくなれば、\(T\) を選択する確率が最大になるのは、様子見をしたカードが全体の \(36\%\)～\(37\%\) 程度のときであり、そのときの確率は \(0.37\) 程度であることが分かります。
\(n\) が十分に大きいとき
\(n\) が十分に大きい前提で、最大確率となる \(S_k\) を数学的に求めます。そのために \(P(S_k)\) の式を簡便な形に変換します。上で計算したように、
\(P(S_k)=\dfrac{k}{n}\displaystyle\sum_{t=k}^{n-1}\dfrac{1}{t}\)
であり、図２でグレーで示した部分の面積に \(\dfrac{k}{n}\) を掛けたものが \(P(S_k)\) です。
従って、積分で計算可能な "図２の赤色の部分" に \(\dfrac{k}{n}\) を掛けると \(P(S_k)\) の下限値になり、
\(P(S_k) > \dfrac{k}{n}\displaystyle\int_{k}^{n}\dfrac{1}{t}\,dt\)
です。置換積分を使うために、
\(\begin{eqnarray}
&&\:\:t&=ns\\
&&\:\:s&=\dfrac{t}{n}\\
&&\:\:dt&=n\,ds\\
\end{eqnarray}\)
と置くと、
\(\begin{eqnarray}
&&\:\:P(S_k)& > \phantom{-}\dfrac{k}{n}\displaystyle\int_{1}^{\tfrac{k}{n}}\dfrac{1}{ns}\cdot n\,ds\\
&&&=\phantom{-}\dfrac{k}{n}\displaystyle\int_{1}^{\tfrac{k}{n}}\dfrac{1}{s}\,ds\\
&&&=-\dfrac{k}{n}\mr{log}\left(\dfrac{k}{n}\right) \br{①}\\
\end{eqnarray}\)
となります。
図２のグレーの部分を \(1\) だけ左にずらしたのが下の図３です。左へずらすことで \(k\) ～ \(n\) の範囲からはみ出た部分の面積は \(\dfrac{1}{k}\) です。
従って、積分を使って \(P(S_k)\) の上限値を求めると、
\(\begin{eqnarray}
&&\:\:P(S_k)& < \dfrac{k}{n}\left(\dfrac{1}{k}+\displaystyle\int_{k}^{n-1}\dfrac{1}{t}\,dt\right)\\
&&&=\dfrac{k}{n}\left(\dfrac{1}{k}+\displaystyle\int_{\tfrac{k}{n}}^{1-\tfrac{1}{n}}\dfrac{1}{s}\,ds\right)\\
&&&=\dfrac{k}{n}\left(\dfrac{1}{k}+\mr{log}\left(1-\dfrac{1}{n}\right)-\mr{log}\left(\dfrac{k}{n}\right)\right)\\
&&&=\dfrac{1}{n}+\dfrac{k}{n}\mr{log}\left(1-\dfrac{1}{n}\right)-\dfrac{k}{n}\mr{log}\left(\dfrac{k}{n}\right)\\
\end{eqnarray}\)
と計算できます。ここで、
\(\al=\dfrac{1}{n}+\dfrac{k}{n}\mr{log}\left(1-\dfrac{1}{n}\right)\)
と置くと、
\(\begin{eqnarray}
&&\:\:\dfrac{1}{n}\rightarrow0 &(n\rightarrow\infty)\\
&&\:\:\mr{log}\left(1-\dfrac{1}{n}\right)\rightarrow0 &(n\rightarrow\infty)\\
\end{eqnarray}\)
\(0 < \dfrac{k}{n} < 1\)
なので、
\(P(S_k) < \al-\dfrac{k}{n}\mr{log}\left(\dfrac{k}{n}\right)\) \(\br{②}\)
\(\al\rightarrow0\:\:(n\rightarrow\infty)\)
となります。下限値の \(\br{①}\) 式と、上限値の \(\br{②}\) 式 を合わせると、
\(-\dfrac{k}{n}\mr{log}\left(\dfrac{k}{n}\right) < P(S_k) < \al-\dfrac{k}{n}\mr{log}\left(\dfrac{k}{n}\right)\)
\(\al\rightarrow0\:\:(n\rightarrow\infty)\)
となって、\(n\) が十分大きいときには、
\(P(S_k)=-\dfrac{k}{n}\mr{log}\left(\dfrac{k}{n}\right)\) \(\br{③}\)
とみなしてよいことが分かりました。ここで \(x=\dfrac{k}{n}\) とすると、
\(P(S_k)=-x\mr{log}(x)\)
となります。\(P(S_k)\) が最大値となる \(x\) を求めるために、右辺を微分して \(0\) とおくと、
\(\begin{eqnarray}
&&\:\:-&\mr{log}(x)-1&=\phantom{-}0\\
&&&\mr{log}(x)&=-1\\
\end{eqnarray}\)
\(\longrightarrow\:x=\dfrac{1}{e}\)
です。つまり、\(\dfrac{k}{n}=\dfrac{1}{e}\) のときに \(P(S_k)\) は最大値をとります。このときの \(P(S_k)\) を \(\br{③}\) 式で求めると、
\(P(S_k)\) の最大値\(=\dfrac{1}{e}\)
と計算できます。この \(\dfrac{1}{e}\) はマッチング問題と全く同じで、\(\fallingdotseq0.368\) です。かつ、この問題では答に現れる２つの数値が共に \(\dfrac{1}{e}\) です。
\(n\) が十分に大きいときは、\(P(S_k)\) の最大値は \(\dfrac{1}{e}\) ですが、上のパソコンでの計算例を見ると、\(n\) を増やしたときに \(\dfrac{1}{e}=0.3678794411\cd\) に収束する様子は、マッチング問題と違って非常に緩慢なことが分かります。
秘書問題の結論
最大値のカードを選択する戦略の結論は次のようになります。
当初の「秘書問題」の文脈でこの結論を書くと、
となります。この結論は \(n\) が十分に大きくても成り立ちます。\(\bs{n}\) がどんなに大きくても、４割程度の高確率で最良の選択ができるというのが、少々意外な結果なのでした。
No.376「高校数学で理解するマッチング問題」に関連する話題を取り上げます。関連といっても "答が同じ数値になる" という意味の関連で、問題の性質は違います。
No.376 では、一般的にマッチング問題（出会いの問題）と言われるものを「席替えの成功確率」という形で提示しました。次のような問題です。
小学校の 40人のクラスで、席替えを "くじ引き" でやるとします。まず、現在の席に 1 ～ 40 の席番号を割り振ります。担任の先生は、1～40 の数字を書いた紙を40枚用意し、その紙を数字が見えないように折って、箱の中に入れてかき混ぜます。生徒は順に箱から紙を１枚ずつ引き、そこに書かれている数字がその子の新しい席となります。 もちろんこのやり方だと、今の自分の席番号の紙を引く子が現れる可能性があります。そして「すべての子が現在の席番号と違う番号を引いたとき、席替えは成功」と定義します。40人のクラスで、席替えが（１回のくじ引きで）成功する確率はどれほどでしょうか。 |
No.376 ではこの確率がおよそ 0.368 であること、また人数が増えると \(\dfrac{1}{e}=0.3678794411\cd\) に収束していくことを見ました（\(e\) は自然対数の底＝ネイピア数）。席替えが成功する確率はクラスの人数が少なければ低く、クラスの人数が多ければ高いと考えるのが普通でしょう。しかし実際にはクラスの人数にかかわらず（６人以上のクラスであれば）ほぼ 0.368 であり、それより成功確率が大きくなることはない。これが少々意外な結論でした。
この \(\dfrac{1}{e}\) という値が答になる別の確率の問題があります。「秘書問題（secretary problem）」です。これも少々意外な確率が答になります。
秘書問題
一般的に「秘書問題」と言われているものは次のようなものです。
| 秘書を一人採用する。 | |
| 応募者は n 人あった。この n 人とランダムな順で面接する。すべての人と面接するとは限らない。 | |
| 面接した直後に、採用するか採用しないかを通知する。採用の通知をしたら、以降の面接はしない。採用しない場合は次の面接を行う。 | |
| 採用しないと通知した人に対して、その通知を覆して採用することはない。 | |
| 面接を行った人すべてに相対的な優先順位をつけることができる。その相対順位に基づいて、直近に面接した人を採用するかしないを判断できる。 | |
| この前提で、n 人の中で最も優先順位の高い人を採用する確率を最大にするには、どういう戦略をとるべきか。またその戦略をとったとき、n 人の中で最も優先順位の高い人を採用できる確率はいくらか。 |
もし、全員と面接してからそのうちの一人に採用を通知するなら話は簡単です。全員の相対的な優先順位をつけられるので、１位の人に通知すればよい。しかしこの問題では「面接した直後に採用するか採用しないかを通知する」必要があります。このとき「もし仮に全員と面接したとしたら優先順位が１位になるはずの人を採用できる確率」を最も大きくするのが問題です。面接の順序はランダムであることにも注意します。この問題を数学的に解析します。
最大値のカードを選択する戦略
説明の都合上、カードを選択する問題にします。秘書問題と等価です。
| \(n\) 枚のカードがあります。それぞれのカードの表には、相異なる正の実数値が一つずつ書いてあります。 | |
| 実数値の範囲は全く不明です。\(n\) 個の実数値には最大と最小があるはずですが、実数値はどんなに大きくも、また小さくもできるので、１枚のカードを見ただけでは最大や最小の判断はできません。\(100,000\) のような数値でも、それが最小値かも知れない。もちろん、複数のカードを見ればその大小関係を判断することができます。 | |
| 最大の実数値が書かれたカードを「最大カード」とよび、\(T\) で表します（\(T\::\) target）。 | |
| この \(n\) 枚のカードをよくシャッフルし、裏返しにして、一列に並べます。順に \(C_1\)、\(C_2\)、\(\cd\)、\(C_n\) とします（\(C\::\) card）。このうちのどれかが \(T\) です。\(T\) を選択するのが問題です。 | |
| \(C_1\)、\(C_2\)、\(\cd\) と順にカードを表にしていき、表にしたカードの最新のものを選択するかどうかを判断します。このとき、表にしてある全部のカードの実数値を比較検討できますが、選択できるのは最新に表にしたカードだけです。また、最終的にはどれかのカードを必ず選択しなければなりません。 | |
| 「最大カード」\(T\) を選択できる確率を最も大きくする戦略と、そのときの確率を求めるのが問題です。 |
まず、\(\bs{n=5}\) の場合で、とりうる戦略と確率を分析します。裏返しのカードは順に \(C_1\)、\(C_2\)、\(C_3\)、\(C_4\)、\(C_5\) です。それぞれのカードの表に書かれている実数値を \(V(C_n)\) とします（\(V\::\) value）。戦略立案の条件は、
最大カード・\(\bs{T}\) ではないとの確証を得たカードは選択しない
です。\(T\) を選択する確率を最大化する問題なので、この条件は必須です。この条件に合致する戦略は、以降で検討するように５種類あるので、それを \(S_n\:\:(n=0,\:1,\:2,\:3,\:4)\) で表します（\(S\::\) strategy）。また、戦略 \(S_n\) のときに 最大カード・\(T\) を選択できる確率を \(P(S_n)\) とします（\(P\::\) probability）。
戦略：\(S_0\)
最初のカード \(C_1\) は「無条件に選択するか、無条件に選択しないかのどちらか」です。利用できる情報は \(V(C_1)\) だけですが、\(V(C_1)\) を見ても全体の中での順位は全く判断できないからです。たとえ \(V(C_1)=0.00001\) などであっても、実数値はいくらでも小さくできるので、それが最大カードの可能性があります。
そこで、最初のカード \(\bs{C_1}\) を必ず選択する戦略を \(S_0\) とします。\(T\) の位置はランダムなので、
\(P(S_0)=\dfrac{1}{5}=0.2\)
です。戦略：\(S_1\)
戦略：\(S_1\) では、\(\bs{C_1}\) は必ず選択せずに "様子見" とし、その後の \(C_2\)、\(C_3\)、\(C_4\) の状況で選択するカードを決めます。もし \(V(C_1) < V(C_2)\) なら \(C_2\) を選択します。もちろん、\(C_2\) が最大カード・\(T\) かどうかは分かりません。しかし、\(\bs{C_1}\) は \(\bs{T}\) ではない確証を得たので、\(\bs{C_1}\) を選択せずに済んだ（＝ \(T\) を選択する確率を高めた）という効果が出ました。なお「\(V(C_1) < V(C_2)\) であっても \(C_2\) を選択しない戦略」もありますが、その場合、\(C_1\) と \(C_2\) は必ず選択しないので、それは次項の "戦略：\(S_2\)" です。
もし \(\bs{V(C_1) > V(C_2)}\) なら、\(\bs{C_2}\) は \(\bs{T}\) でありません。従って \(C_2\) を選択せずに \(C_3\) を表にします。そして \(V(C_1) < V(C_3)\) であれば \(C_3\) を選択します。もちろん \(C_3\) が \(T\) かどうかは分かりませんが、\(\bs{C_2}\) に加えて \(\bs{C_1}\) も \(\bs{T}\) ではない確証を得たという効果が生じました。
もし \(V(C_1) > V(C_3)\) なら \(C_3\) は \(T\) ではないことが分かったので、\(C_4\) を表にします。なお「\(V(C_1) < V(C_3)\) であっても \(C_3\) を選択しない」という戦略も考えられますが、その場合、\(C_1\)、\(C_2\)、\(C_3\) は必ず選択しないので、それは後で述べる "戦略：\(S_3\)" です。
以下、同様の考え方で \(C_4\) を選択するかどうかを決めます。つまり、\(\bs{V(C_1)}\) より大きな実数値が出たとき、そのカードを選択します。この方針で \(C_4\) も選択しなければ、最終的にどれか１枚を選択する必要があるので \(C_5\) を選択します。
ここで、戦略：\(S_1\) で \(T\) を選択できる確率、\(P(S_1)\) を計算します。
\(\bs{C_1=T}\) のとき、\(C_1\) は選択しないので、
\(P(S_1)=0\)
\(\bs{C_2=T}\) のとき、必ず \(C_2\) を選択することになります。\(C_2=T\) となる確率は \(\dfrac{1}{5}\) なので、
\(P(S_1)=\dfrac{1}{5}\)
\(\bs{C_3=T}\) のとき、\(C_3\) を選択するのは \(V(C_1) > V(C_2)\) のとき（＝ \(C_2\) を選択しないとき）です。カードの並べ方はランダムなので、\(V(C_1) > V(C_2)\) となるか \(V(C_1) < V(C_2)\) かは半々です。従って、
\(P(S_1)=\dfrac{1}{5}\times\dfrac{1}{2}\)
\(\bs{C_4=T}\) のとき、\(C_4\) を選択するのは \(C_2\)、\(C_3\) を選択しない場合です。\(V(C_1)\)、\(V(C_2)\)、\(V(C_3)\) のうちの最大値がどれかは３つの場合がありますが、\(C_2\) か \(C_3\) が選択されないのは、最大値が \(V(C_1)\) のときだけです。つまり割合として \(\dfrac{1}{3}\) の場合です。従って、
\(P(S_1)=\dfrac{1}{5}\times\dfrac{1}{3}\)
\(\bs{C_5=T}\) のとき、\(C_5\) を選択するのは \(C_2\)、\(C_3\)、\(C_4\) を選択しない場合だけです。\(V(C_1)\)、\(V(C_2)\)、\(V(C_3)\)、\(V(C_4)\) のうちの最大値がどれかは４つの場合がありますが、\(C_2\)、\(C_3\)、\(C_4\) のどれもが選択されないのは、最大値が \(V(C_1)\) のときだけです。つまり割合として \(\dfrac{1}{4}\) の場合です。従って、
\(P(S_1)=\dfrac{1}{5}\times\dfrac{1}{4}\)
以上の５つケースは排他的なので、
\(\begin{eqnarray}
&&\:\:P(S_1)&=\dfrac{1}{5}\left(1+\dfrac{1}{2}+\dfrac{1}{3}+\dfrac{1}{4}\right)\\
&&&=\dfrac{1}{5}\cdot\dfrac{25}{12}\\
&&&=0.4167\\
\end{eqnarray}\)
が \(T\) を選択できる確率です。\(S_0\) よりは \(2\)倍以上の確率になりました。
戦略：\(S_2\)
この戦略では、\(C_1\)、\(C_2\) は様子見として選択せず（＝たとえ \(V(C_1) < V(C_2)\) であっても \(C_2\) を選択しない）、\(C_3\)、\(C_4\) の状況で判断します。選択の判断は \(S_1\) と同様です。つまり、様子見のカード、\(\bs{V(C_1)}\)、\(\bs{V(C_2)}\) より大きな実数値のカードを選択します。
\(C_1=T\) または \(C_2=T\) のとき、\(T\) は選択されません。
\(C_3=T\) のときは必ず \(T\) が選択されます。
\(C_4=T\) のとき、\(C_4\) が選択されるのは \(V(C_1)\)、\(V(C_2)\)、\(V(C_3)\) のうちの最大値が \(V(C_1)\)、\(V(C_2)\) のどちらかの場合です。\(V(C_3)\) が最大値だと \(C_3\) を選択してしまうからです。つまり \(\dfrac{2}{3}\) の割合です。
\(C_5=T\) のとき、\(C_5\) が選択されるのは \(V(C_1)\)、\(V(C_2)\)、\(V(C_3)\)、\(V(C_4)\)のうちの最大値が \(V(C_1)\)、\(V(C_2)\) のどちらかの場合です。そうでなければ \(C_3\) か \(C_4\) を選択してしまうからです。つまり \(\dfrac{2}{4}=\dfrac{1}{2}\) の割合です。まとめると、
\(\begin{eqnarray}
&&\:\:P(S_2)&=\dfrac{1}{5}\left(1+\dfrac{2}{3}+\dfrac{1}{2}\right)\\
&&&=\dfrac{1}{5}\cdot\dfrac{13}{6}\\
&&&=0.4333\\
\end{eqnarray}\)
となります。\(P(S_1)\) より大きい値です。
戦略：\(S_3\)
この戦略では、\(C_1\)、\(C_2\)、\(C_3\) は様子見として選択せず、\(C_4\) の状況で判断します。\(V(C_1)\)、\(V(C_2)\)、\(V(C_3)\) より \(V(C_4)\) が大きな実数値のときに、\(C_4\) を選択します。
\(C_1=T\) または \(C_2=T\) または \(C_3=T\) のとき、\(T\) は選択されません。
\(C_4=T\) のときは必ず \(T\) が選択されます。
\(C_5=T\) のとき、\(C_5\) が選択されるのは \(V(C_1)\)、\(V(C_2)\)、\(V(C_3)\)、\(V(C_4)\) のうちの最大値が\(V(C_4)\) ではない場合です。\(V(C_4)\) が最大値だと \(C_4\) を選択してしまうからです。つまり \(C_5\) が選択されるのは \(\dfrac{3}{4}\) の場合です。まとめると、
\(\begin{eqnarray}
&&\:\:P(S_3)&=\dfrac{1}{5}\left(1+\dfrac{3}{4}\right)\\
&&&=\dfrac{1}{5}\cdot\dfrac{7}{4}\\
&&&=0.3500\\
\end{eqnarray}\)
となり、\(P(S_2)\) より小さくなりました。
戦略：\(S_4\)
この戦略では \(C_1\)、\(C_2\)、\(C_3\)、\(C_4\) を選択せず、必ず \(C_5\) を選択します。\(C_5=T\) である確率は \(\dfrac{1}{5}\) であり、
\(P(S_4)=0.2\)
となって、\(P(S_0)\) と同じ確率です。
\(n=5\) の場合のまとめ
以上の検討結果により \(n=5\) の場合で可能な戦略は、「最大カード・\(T\) ではないとの確証を得たカードは選択しない」という条件のもとで \(S_0\) ～ \(S_4\) の５種であり、これ以外にはありません。各戦略ごとの確率をまとめると、
\(P(S_0)=0.2\)
\(P(S_1)=0.4167\)
\(P(S_2)=0.4333\)
\(P(S_3)=0.35\)
\(P(S_4)=0.2\)
で、\(n=5\) では「戦略：\(S_2\)」が最大カード・\(T\) を選択する確率を最大化します。この "確率最大化" の検討過程から、次のようなことが分かります。
| 性急にカードを選択するのは損である。いくつかは "様子見" をして、そのあとに全体的な判断をすべきである。 | |
| しかし、様子見をし過ぎるのも損である。様子見の中に最大カード・\(T\) が含まれる可能性が高まるからである。 | |
| この２つのトレードオフで、確率を最大化する戦略が決まる。 |
一般化
\(n=5\) のときの考察を一般化し、\(n\) を \(n\geq2\) の任意の数とします。一般化された戦略は、
戦略 \(S_0\)
戦略 \(S_k\:\:(1\leq k\leq n-1)\)
最初のカードを選択する。
戦略 \(S_k\:\:(1\leq k\leq n-1)\)
\(k\) 番目までのカードは選択せず、\(k+1\) 番目以降で、\(V(C_1)\)～\(V(C_k)\) の最大値より大きな数値のカードを選択する。大きな数値が出ない場合は最後のカードを選択する。
です。また、
最大カード \(T\) の位置：\(t\) 番目
とします。もし \(1\leq t\leq k\) なら \(T\) を選択することはないので、確率は \(0\) です。
\(\bs{k < t\leq n}\) のとき、\(\bs{T}\) を選択するのは、\(\bs{V(C_1)}\)、\(\bs{V(C_2)}\)、\(\bs{\cd}\)、\(\bs{V(C_{t-1})}\) の中での最大が、\(\bs{V(C_1)}\)、\(\bs{V(C_2)}\)、\(\bs{\cd\:V(C_k)}\) の中にある場合だけです。そうでなければ \(\bs{T}\) にたどりつく前に \(\bs{C_{k+1}}\)、\(\bs{\cd\:C_{t-1}}\) のどれかを選択してしまうからです。つまり \(T\) を選択するのは、割合としては \(\dfrac{k}{t-1}\) の場合です。
|
図１：最大カード・\(T\) を選択できる場合 |
\(C_1\)、 \(\cd\) 、\(C_{t-1}\) のうちの最大値のカードが \(C_{k+1}\)、 \(\cd\) 、\(C_{t-1}\) の中にあれば、そのカードを選択してしまって、\(T\) にはたどり着かない。最大値のカードが \(C_1\)、\(\cd\) 、\(C_k\) の範囲にあれば、\(T\) が選択される。もちろん、\(k < t\) であることが大前提である。 |
\(t\) 番目に \(T\) がある確率は \(\dfrac{1}{n}\) なので、\(T\) を選択する確率は、
\(\dfrac{1}{n}\cdot\dfrac{k}{t-1}\)
です。全体の確率は、この式を \(t\) の範囲 \((k < t\leq n)\) で合計し、
\(\begin{eqnarray}
&&\:\:P(S_k)&=\displaystyle\sum_{t=k+1}^{n}\dfrac{1}{n}\cdot\dfrac{k}{t-1}\\
&&&=\dfrac{k}{n}\displaystyle\sum_{t=k+1}^{n}\cdot\dfrac{1}{t-1}\\
&&&=\dfrac{k}{n}\displaystyle\sum_{t=k}^{n-1}\cdot\dfrac{1}{t}\\
&&&=\dfrac{k}{n}\left(\dfrac{1}{k}+\dfrac{1}{k+1}+\:\cd\:+\dfrac{1}{n-1}\right)\\
\end{eqnarray}\)
となります。
\(n=5\) のときには、上で計算したように戦略：\(S_2\) が最大確率になりました。では、一般の場合に最大確率になる戦略 \(S_k\) は何か。\(n=5,\:10,\:15,\:\cd\:,\:100\) の場合をパソコンで計算してみると、次の表の通りです。
| \(5\) | \(S_{2}\) | \(0.43333\) | \(0.40\) |
| \(10\) | \(S_{3}\) | \(0.39869\) | \(0.30\) |
| \(15\) | \(S_{5}\) | \(0.38941\) | \(0.33\) |
| \(20\) | \(S_{7}\) | \(0.38421\) | \(0.35\) |
| \(25\) | \(S_{9}\) | \(0.38092\) | \(0.36\) |
| \(30\) | \(S_{11}\) | \(0.37865\) | \(0.37\) |
| \(35\) | \(S_{13}\) | \(0.37700\) | \(0.37\) |
| \(40\) | \(S_{15}\) | \(0.37574\) | \(0.38\) |
| \(45\) | \(S_{16}\) | \(0.37493\) | \(0.36\) |
| \(50\) | \(S_{18}\) | \(0.37428\) | \(0.36\) |
| \(55\) | \(S_{20}\) | \(0.37371\) | \(0.36\) |
| \(60\) | \(S_{22}\) | \(0.37321\) | \(0.37\) |
| \(65\) | \(S_{24}\) | \(0.37278\) | \(0.37\) |
| \(70\) | \(S_{26}\) | \(0.37239\) | \(0.37\) |
| \(75\) | \(S_{27}\) | \(0.37210\) | \(0.36\) |
| \(80\) | \(S_{29}\) | \(0.37186\) | \(0.36\) |
| \(85\) | \(S_{31}\) | \(0.37163\) | \(0.36\) |
| \(90\) | \(S_{33}\) | \(0.37142\) | \(0.37\) |
| \(95\) | \(S_{35}\) | \(0.37122\) | \(0.37\) |
| \(100\) | \(S_{37}\) | \(0.37104\) | \(0.37\) |
\(n\) が大きくなれば、\(T\) を選択する確率が最大になるのは、様子見をしたカードが全体の \(36\%\)～\(37\%\) 程度のときであり、そのときの確率は \(0.37\) 程度であることが分かります。
\(n\) が十分に大きいとき
\(n\) が十分に大きい前提で、最大確率となる \(S_k\) を数学的に求めます。そのために \(P(S_k)\) の式を簡便な形に変換します。上で計算したように、
\(P(S_k)=\dfrac{k}{n}\displaystyle\sum_{t=k}^{n-1}\dfrac{1}{t}\)
であり、図２でグレーで示した部分の面積に \(\dfrac{k}{n}\) を掛けたものが \(P(S_k)\) です。
|
図２：\(P(S_k)\) の下限値の計算 |
従って、積分で計算可能な "図２の赤色の部分" に \(\dfrac{k}{n}\) を掛けると \(P(S_k)\) の下限値になり、
\(P(S_k) > \dfrac{k}{n}\displaystyle\int_{k}^{n}\dfrac{1}{t}\,dt\)
です。置換積分を使うために、
\(\begin{eqnarray}
&&\:\:t&=ns\\
&&\:\:s&=\dfrac{t}{n}\\
&&\:\:dt&=n\,ds\\
\end{eqnarray}\)
と置くと、
\(\begin{eqnarray}
&&\:\:P(S_k)& > \phantom{-}\dfrac{k}{n}\displaystyle\int_{1}^{\tfrac{k}{n}}\dfrac{1}{ns}\cdot n\,ds\\
&&&=\phantom{-}\dfrac{k}{n}\displaystyle\int_{1}^{\tfrac{k}{n}}\dfrac{1}{s}\,ds\\
&&&=-\dfrac{k}{n}\mr{log}\left(\dfrac{k}{n}\right) \br{①}\\
\end{eqnarray}\)
となります。
図２のグレーの部分を \(1\) だけ左にずらしたのが下の図３です。左へずらすことで \(k\) ～ \(n\) の範囲からはみ出た部分の面積は \(\dfrac{1}{k}\) です。
|
図３：\(P(S_k)\) の上限値の計算 |
従って、積分を使って \(P(S_k)\) の上限値を求めると、
\(\begin{eqnarray}
&&\:\:P(S_k)& < \dfrac{k}{n}\left(\dfrac{1}{k}+\displaystyle\int_{k}^{n-1}\dfrac{1}{t}\,dt\right)\\
&&&=\dfrac{k}{n}\left(\dfrac{1}{k}+\displaystyle\int_{\tfrac{k}{n}}^{1-\tfrac{1}{n}}\dfrac{1}{s}\,ds\right)\\
&&&=\dfrac{k}{n}\left(\dfrac{1}{k}+\mr{log}\left(1-\dfrac{1}{n}\right)-\mr{log}\left(\dfrac{k}{n}\right)\right)\\
&&&=\dfrac{1}{n}+\dfrac{k}{n}\mr{log}\left(1-\dfrac{1}{n}\right)-\dfrac{k}{n}\mr{log}\left(\dfrac{k}{n}\right)\\
\end{eqnarray}\)
と計算できます。ここで、
\(\al=\dfrac{1}{n}+\dfrac{k}{n}\mr{log}\left(1-\dfrac{1}{n}\right)\)
と置くと、
\(\begin{eqnarray}
&&\:\:\dfrac{1}{n}\rightarrow0 &(n\rightarrow\infty)\\
&&\:\:\mr{log}\left(1-\dfrac{1}{n}\right)\rightarrow0 &(n\rightarrow\infty)\\
\end{eqnarray}\)
\(0 < \dfrac{k}{n} < 1\)
なので、
\(P(S_k) < \al-\dfrac{k}{n}\mr{log}\left(\dfrac{k}{n}\right)\) \(\br{②}\)
\(\al\rightarrow0\:\:(n\rightarrow\infty)\)
となります。下限値の \(\br{①}\) 式と、上限値の \(\br{②}\) 式 を合わせると、
\(-\dfrac{k}{n}\mr{log}\left(\dfrac{k}{n}\right) < P(S_k) < \al-\dfrac{k}{n}\mr{log}\left(\dfrac{k}{n}\right)\)
\(\al\rightarrow0\:\:(n\rightarrow\infty)\)
となって、\(n\) が十分大きいときには、
\(P(S_k)=-\dfrac{k}{n}\mr{log}\left(\dfrac{k}{n}\right)\) \(\br{③}\)
とみなしてよいことが分かりました。ここで \(x=\dfrac{k}{n}\) とすると、
\(P(S_k)=-x\mr{log}(x)\)
となります。\(P(S_k)\) が最大値となる \(x\) を求めるために、右辺を微分して \(0\) とおくと、
\(\begin{eqnarray}
&&\:\:-&\mr{log}(x)-1&=\phantom{-}0\\
&&&\mr{log}(x)&=-1\\
\end{eqnarray}\)
\(\longrightarrow\:x=\dfrac{1}{e}\)
です。つまり、\(\dfrac{k}{n}=\dfrac{1}{e}\) のときに \(P(S_k)\) は最大値をとります。このときの \(P(S_k)\) を \(\br{③}\) 式で求めると、
\(P(S_k)\) の最大値\(=\dfrac{1}{e}\)
と計算できます。この \(\dfrac{1}{e}\) はマッチング問題と全く同じで、\(\fallingdotseq0.368\) です。かつ、この問題では答に現れる２つの数値が共に \(\dfrac{1}{e}\) です。
\(n\) が十分に大きいときは、\(P(S_k)\) の最大値は \(\dfrac{1}{e}\) ですが、上のパソコンでの計算例を見ると、\(n\) を増やしたときに \(\dfrac{1}{e}=0.3678794411\cd\) に収束する様子は、マッチング問題と違って非常に緩慢なことが分かります。
秘書問題の結論
最大値のカードを選択する戦略の結論は次のようになります。
最初からの \(36.8\%\) のカードは選択せずに "様子見" とし、それ以降のカードで、様子見のカードの最大値よりも大きな値が出たら選択するのがベストの戦略である。この戦略により \(36.8\%\) の確率で \(n\) 枚の中の最大カードを選択できる。 |
当初の「秘書問題」の文脈でこの結論を書くと、
\(n\) 人の応募者とランダムに面接するとき、「最初から \(0.368n\) 人までの応募者」は不採用とし、それ以降の応募者で「最初から \(0.368n\) 人までのすべての応募者よりも秘書にふさわしいと判断した人」を採用する。これにより \(36.8\%\) の確率で全応募者の中のベストの人（＝全員を面接したとしたらベストと判断できるはずの人）を採用できる。 |
となります。この結論は \(n\) が十分に大きくても成り立ちます。\(\bs{n}\) がどんなに大きくても、４割程度の高確率で最良の選択ができるというのが、少々意外な結果なのでした。
2024-11-03 10:51
nice!(0)
