秘書問題(最良選択問題)
秘書問題(最良選択問題)
あなたは秘書を1人雇いたいと思っています。
このとき、以下の条件で雇います。
・応募者は全員で\(n\)人いることが分かっています。
・応募者は1位から\(n\)位まで順位を付けることができ、同順はありません。
・1人ずつ面接をしてその場で採用か不採用かを決めなければいけません。
・次に面接をする人は完全にランダムに選ばれます。
・それまでに面接をした人の順位だけで採用・不採用を決めなければいけません。
・一度不採用にした人をあとから採用することはできません。
\(n\)は十分多いとします。
\(n\)人中1位の応募者を採用することを最優先する場合はどのような戦略をとれば良いでしょうか?
またその戦略で1位の応募者を採用する確率を求めよ。
あなたは秘書を1人雇いたいと思っています。
このとき、以下の条件で雇います。
・応募者は全員で\(n\)人いることが分かっています。
・応募者は1位から\(n\)位まで順位を付けることができ、同順はありません。
・1人ずつ面接をしてその場で採用か不採用かを決めなければいけません。
・次に面接をする人は完全にランダムに選ばれます。
・それまでに面接をした人の順位だけで採用・不採用を決めなければいけません。
・一度不採用にした人をあとから採用することはできません。
\(n\)は十分多いとします。
\(n\)人中1位の応募者を採用することを最優先する場合はどのような戦略をとれば良いでしょうか?
またその戦略で1位の応募者を採用する確率を求めよ。
秘書問題は結婚問題やお見合い問題ともいいます。
最良の1位の人を選択する問題なので最良選択問題ともいいます。
最良の1位の人を選択する問題なので最良選択問題ともいいます。
1位の人を採用するには現段階での暫定1位(今までで1番いい人)を採用しなければいけません。
まず\(k\)人目までを無条件で断りそれ以降の人で暫定1位を採用するのがいい方法となります。
この\(k\)を求めます。
1位の人が\(t\)番目の面接者だとするとこの確率は\(\frac{1}{n}\)となります。
\(t\leq k\)のとき、\(k\)人目までは無条件で断るので1位の人を選べる確率は0となります。
\(k<t\)のとき、1位の人を選ぶにはそれまでの\(t-1\)人中の1位の人が始めの\(k\)人の中に入っていなければいけない。
なぜなら1位の人の面接の前に他の人が採用されてしまうからである。
これより、1位の人が\(t\)番目なら選ばれる確率\(P\left(t\right)\)は\(P\left(t\right)=\frac{k}{t-1}\)となる。
また、1位の人が\(t\)番目の面接者となる確率は\(\frac{1}{n}\)となります。
従って、\(P\left(t\right)\)に\(t\)番目の面接者となる確率\(\frac{1}{n}\)を掛け、\(t\)について\(k+1\)から\(n\)までの和をとると、1位の人を選べる確率\(P\)となる。
\begin{align*} P & =\sum_{t=k+1}^{n}\frac{P\left(t\right)}{n}\\ & =\frac{1}{n}\sum_{t=k+1}^{n}\frac{k}{t-1}\\ & =\frac{k}{n}\sum_{t=k}^{n-1}\frac{1}{t}\\ & =\frac{k}{n}\frac{1}{n}\sum_{t=k}^{n-1}\frac{1}{\frac{t}{n}}\\ & \fallingdotseq\frac{k}{n}\int_{\frac{k}{n}}^{1}\frac{1}{x}dx\\ & =\frac{k}{n}\left[\log x\right]_{\frac{k}{n}}^{1}\\ & =-\frac{k}{n}\log\frac{k}{n} \end{align*} となるので、\(P\)を最大にする\(k\)を求めればいい。
\(P\)を\(k\)で微分すると、
\begin{align*} \frac{dP}{dk} & =-\frac{d}{dk}\frac{k}{n}\log\frac{k}{n}\\ & =-\frac{1}{n}\left[\frac{d}{dx}x\log x\right]_{x=\frac{k}{n}}\\ & =-\frac{1}{n}\left[\log x+1\right]_{x=\frac{k}{n}} \end{align*} となるので増減表は
\[ \begin{array}{|c|c|c|c|c|c|} \hline x & 0 & \cdots & \frac{1}{e} & \cdots & \infty\\ \hline P' & & + & 0 & - & \\ \hline P & & \nearrow & \frac{1}{e} & \searrow & \\\hline \end{array} \] となる。
これより、\(k=\frac{n}{e}\)のとき確率\(P=-\frac{1}{e}\log\frac{1}{e}=\frac{1}{e}\fallingdotseq0.368\)で1位の人を選ぶことができる。
まず\(k\)人目までを無条件で断りそれ以降の人で暫定1位を採用するのがいい方法となります。
この\(k\)を求めます。
1位の人が\(t\)番目の面接者だとするとこの確率は\(\frac{1}{n}\)となります。
\(t\leq k\)のとき、\(k\)人目までは無条件で断るので1位の人を選べる確率は0となります。
\(k<t\)のとき、1位の人を選ぶにはそれまでの\(t-1\)人中の1位の人が始めの\(k\)人の中に入っていなければいけない。
なぜなら1位の人の面接の前に他の人が採用されてしまうからである。
これより、1位の人が\(t\)番目なら選ばれる確率\(P\left(t\right)\)は\(P\left(t\right)=\frac{k}{t-1}\)となる。
また、1位の人が\(t\)番目の面接者となる確率は\(\frac{1}{n}\)となります。
従って、\(P\left(t\right)\)に\(t\)番目の面接者となる確率\(\frac{1}{n}\)を掛け、\(t\)について\(k+1\)から\(n\)までの和をとると、1位の人を選べる確率\(P\)となる。
\begin{align*} P & =\sum_{t=k+1}^{n}\frac{P\left(t\right)}{n}\\ & =\frac{1}{n}\sum_{t=k+1}^{n}\frac{k}{t-1}\\ & =\frac{k}{n}\sum_{t=k}^{n-1}\frac{1}{t}\\ & =\frac{k}{n}\frac{1}{n}\sum_{t=k}^{n-1}\frac{1}{\frac{t}{n}}\\ & \fallingdotseq\frac{k}{n}\int_{\frac{k}{n}}^{1}\frac{1}{x}dx\\ & =\frac{k}{n}\left[\log x\right]_{\frac{k}{n}}^{1}\\ & =-\frac{k}{n}\log\frac{k}{n} \end{align*} となるので、\(P\)を最大にする\(k\)を求めればいい。
\(P\)を\(k\)で微分すると、
\begin{align*} \frac{dP}{dk} & =-\frac{d}{dk}\frac{k}{n}\log\frac{k}{n}\\ & =-\frac{1}{n}\left[\frac{d}{dx}x\log x\right]_{x=\frac{k}{n}}\\ & =-\frac{1}{n}\left[\log x+1\right]_{x=\frac{k}{n}} \end{align*} となるので増減表は
\[ \begin{array}{|c|c|c|c|c|c|} \hline x & 0 & \cdots & \frac{1}{e} & \cdots & \infty\\ \hline P' & & + & 0 & - & \\ \hline P & & \nearrow & \frac{1}{e} & \searrow & \\\hline \end{array} \] となる。
これより、\(k=\frac{n}{e}\)のとき確率\(P=-\frac{1}{e}\log\frac{1}{e}=\frac{1}{e}\fallingdotseq0.368\)で1位の人を選ぶことができる。
ページ情報
タイトル | 秘書問題(最良選択問題) |
URL | https://www.nomuramath.com/zrqth7vf/ |
SNSボタン |
毒入りワイン
毒入りワインを特定するのに何人が必要?
4枚カード問題(ウェイソン選択課題)
仮説を検証するにはどのカードの裏面を確認する必要があるか?
連続で2段上れないときには階段の上り方は何通りあるか?
1回で1段または2段上れるが連続で2段上ることができないとき何通りの上り方があるか。
点灯パズル
全てのマスのライトを付けるにはどうすればいいでしょうか?