37%ルール

候補者が一人ずつ、無作為な順番で現れます。それまでに会った人との優劣はわかりますが、選ぶか見送るかはその場で決めなければならず、呼び戻すこともできません。まず、最初に何人を見送るか決めましょう。その後は、見送った全員より優れた候補者が初めて現れたところで選びます。

k人を見送って最良を選ぶ確率	$P(k)=\frac{k}{n}\sum_{i=k+1}^{n}\frac{1}{i-1}$
nが大きいときの最適な見送り数	$k^*\approx\frac{n}{e}$
そのときの成功確率	$P(k^*)\to\frac{1}{e}\approx0.3679$

計算例 — 37%ルール

4人を見送って最良を選ぶ確率	39.84%
最適な見送り数 k*	4
k*で最良を選ぶ確率	39.84%
比較用の値 n/e	4.05
無作為に選んで最良を得る確率	9.09%
最良の候補者を最初に見送る確率	36.36%
最後の候補者まで選考が続く確率	40%
この見送り数で選ぶ人の順位の期待値（1が最良）	3.38

ページを開いたときに計算機が表示する値です。上の入力を変えると再計算されます。

インタラクティブシミュレーションを読み込んでいます...

レッスン

理論 — 37%ルール

秘書問題では、n人の候補者が無作為な順番で現れます。わかるのは、それまでに会った人との優劣だけ。選ぶか見送るかはその場で決め、一度決めたら変更できません。閾値戦略では、最初のk人を見送り、その全員より優れた候補者が初めて現れたところで選びます。

公式の導き方

最良の候補者が現れる位置で場合分けします。最良の候補者の位置をB、その人を選ぶ事象をWとします。Bが1からnまでのどの値を取る確率も同じです。
$P(B=i)=\frac{1}{n},\qquad i=1,\dots,n$
最良の候補者が最初のk人にいれば、選べません。見送った人には戻れないので、これらの位置は成功確率に寄与しません。
$B\le k:\quad P(W\mid B)=0$
最良の候補者がi > kの位置にいるとき、その人を選ぶには、k + 1番目からi − 1番目までを誰も選んでいないことが必要です。これは、最初のi − 1人の中で最良の候補者が、最初のk人に含まれることと同値です。その場合に限り、間に現れる候補者が誰も基準を超えないからです。i − 1人のうち、誰が最良である確率も同じです。
$B=i>k:\quad P(W\mid B=i)=\frac{k}{i-1}$
位置ごとの確率を足し合わせます。
$P(k)=\sum_{i=k+1}^{n}\frac{1}{n}\cdot\frac{k}{i-1}=\frac{k}{n}\sum_{i=k+1}^{n}\frac{1}{i-1}$
nを大きくしていきます。x = k/nとおくと、和は積分に、成功確率は−x ln xに近づきます。導関数−ln x − 1が0になるのはx = 1/eで、このときの成功確率も1/e ≈ 36.79%です。
$P\approx x\int_{x}^{1}\frac{dt}{t}=-x\ln x,\qquad\frac{d}{dx}\left(-x\ln x\right)=-\ln x-1=0\iff x=\frac{1}{e}$

前提: 得点は見えず、順位だけがわかるものとします。候補者の順番は、すべての並び方が等確率で生じます。見送った人は呼び戻せず、選んだ人には必ず承諾してもらえます。また、最良の候補者を選べなければ失敗と数えます。

全プロセスの詳細解説

候補者3人の並び順をすべて調べる 3 ステップ
3人の候補者が無作為な順番で現れます。現れる順に順位を並べて表しましょう（1が最良）。最初の1人を見送り、その後は、それまでの全員より優れた候補者が初めて現れたところで選びます。6通りの並び順のうち、最良の候補者を選べるのは何通りでしょうか。公式でも確かめてください。

この問題をツールで開く
1. 並び順は次の6通りです。
  
  $123,\quad 132,\quad 213,\quad 231,\quad 312,\quad 321$
2. 最初の候補者が比較の基準になります。213と231では、最良の候補者が2位の候補者を上回るので選ばれます。312では、2番目に現れる1位の候補者を選びます。123と132では、最初に見送った1位の候補者を上回る人がいないので、最後の候補者を選びます。321では、1位の候補者が現れる前に、3位を上回る2位の候補者を選んでしまいます。
  
  $213\to1,\quad 231\to1,\quad 312\to1;\qquad 123\to3,\quad 132\to2,\quad 321\to2$
3. 公式にn = 3、k = 1を代入すると、
  
  $P(1)=\frac{1}{3}\left(\frac{1}{1}+\frac{1}{2}\right)=\frac{1}{3}\cdot\frac{3}{2}=\frac{1}{2}$
解答

6通りのうち3通りで、確率は1/2。最初の候補者を選ぶ場合は1/3です。

$P(1)=\frac{3}{6}=\frac{1}{2}>\frac{1}{3}=P(0)$
候補者4人で、見送り数を比べる 2 ステップ
候補者が4人のとき、見送り数k = 0, 1, 2, 3のそれぞれについて、最良の候補者を選ぶ確率を求めましょう。最適な見送り数はいくつでしょうか。

この問題をツールで開く
解答を表示
1. k = 0では最初の候補者を選ぶので、その人が最良である確率は1/4です。k ≥ 1では公式を使います。
  
  $P(1)=\frac{1}{4}\left(1+\frac{1}{2}+\frac{1}{3}\right)=\frac{11}{24},\quad P(2)=\frac{2}{4}\left(\frac{1}{2}+\frac{1}{3}\right)=\frac{5}{12},\quad P(3)=\frac{3}{4}\cdot\frac{1}{3}=\frac{1}{4}$
2. 4つの値を比べると、
  
  $P(0)=\frac{6}{24},\quad P(1)=\frac{11}{24},\quad P(2)=\frac{10}{24},\quad P(3)=\frac{6}{24}$
解答

最初の1人を見送り、その人を上回る候補者が初めて現れたところで選びます。成功確率は11/24 ≈ 45.83%です。

$k^*=1,\qquad P(1)=\frac{11}{24}\approx0.4583$
ケプラーの11人 3 ステップ
1611年、ヨハネス・ケプラーは再婚相手を探し始め、二年近くかけて11人の候補者を検討しました。n = 11で閾値戦略を使うとき、最適な見送り数と成功確率を求めましょう。また、このルールで選べる最初の候補者は何人目でしょうか。

この問題をツールで開く
解答を表示
1. n/e = 11/e ≈ 4.05の前後で、公式の値を計算します。
  
  $P(4)=\frac{4}{11}\left(\frac{1}{4}+\frac{1}{5}+\dots+\frac{1}{10}\right)=\frac{4}{11}\times1.0956=0.3984$
2. 成功確率が最大になるのはk = 4です。k = 3でもk = 5でも、それより小さくなります。
  
  $P(3)=\frac{3}{11}\left(\frac{1}{3}+\dots+\frac{1}{10}\right)=0.3897,\qquad P(5)=\frac{5}{11}\left(\frac{1}{5}+\dots+\frac{1}{10}\right)=0.3844$
3. 4人を見送ると、選べる最初の候補者は5人目です。ケプラーが結婚したのも5人目でしたが、このルールに従ったわけではありません。ファーガソンが紹介するケプラーの手紙によると、5人目に会った後、周囲に勧められて4人目に求婚し、断られてから5人目に戻ったそうです。このルールでは、一度見送った人には戻れません。
解答

最初の4人を見送り、成功確率は39.84%。選べる最初の候補者は5人目です。

$k^*=4,\qquad P(4)\approx0.3984$
候補者が多いとき、1/eはどこから現れるか 3 ステップ
nが大きいとき、見送る割合をx = k/nとして、最適なxとその成功確率を求めましょう。n = 100の場合とも比べてください。

この問題をツールで開く
解答を表示
1. この和は、区間[x, 1]上の関数1/tのリーマン和として書けます。
  
  $\frac{k}{n}\sum_{i=k+1}^{n}\frac{1}{i-1}=x\sum_{j=k}^{n-1}\frac{1}{n}\cdot\frac{1}{j/n}\approx x\int_{x}^{1}\frac{dt}{t}=-x\ln x$
2. 導関数を0とおくと、
  
  $\frac{d}{dx}\left(-x\ln x\right)=-\ln x-1=0\ \Rightarrow\ x=\frac{1}{e},\qquad -\frac{1}{e}\ln\frac{1}{e}=\frac{1}{e}\approx0.3679$
3. n = 100ではn/e ≈ 36.79で、厳密に求めた最適な見送り数は37です。
  
  $P(36)=0.37101,\qquad P(37)=0.37104,\qquad P(38)=0.37080$
解答

見送る割合は1/e ≈ 36.79%が最適で、成功確率も1/eに近づきます。n = 100での最適な見送り数は37で、成功確率は37.1%です。

$x^*=\frac{1}{e},\qquad P\to\frac{1}{e}\approx0.3679;\qquad n=100:\ k^*=37,\ P(37)\approx0.3710$
最後の候補者を選ぶことになる確率 3 ステップ
候補者100人のうち、最初の37人を見送ります。最良の候補者を最初に見送る確率、最後の候補者まで選考が続く確率、そして最後まで選考が続き、その最後の候補者が最良である確率を求めましょう。

この問題をツールで開く
解答を表示
1. 最良の候補者がどの位置にいる確率も同じなので、最初の37人に含まれる確率は、
  
  $\frac{k}{n}=\frac{37}{100}=0.37$
2. 100番目の候補者まで選考が続くのは、38番目から99番目までを誰も選ばなかった場合に限ります。これは、最初の99人の中で最良の候補者が、最初の37人に含まれる場合です。
  
  $\frac{k}{n-1}=\frac{37}{99}\approx0.3737$
3. この差が、選考が最後まで続き、しかも最後の候補者が全体で最良である確率です。
  
  $\frac{37}{99}-\frac{37}{100}=\frac{37}{9900}\approx0.0037$
解答

それぞれ37%、37.37%、0.37%です。選考の3回に1回以上は最後の候補者を選びますが、その人が最良であることはめったにありません。

$0.37,\qquad 0.3737,\qquad 0.0037$
候補者3人で、順位の期待値を最小にする 3 ステップ
候補者は3人です。今度は最良の候補者を選ぶことではなく、選ぶ人の順位の期待値を最小にすることを目指します（1が最良）。後ろ向き帰納法で最適なルールと順位の期待値を求めましょう。

この問題をツールで開く
解答を表示
1. i番目に現れた候補者が、それまでの候補者の中でj位なら、その人の全体での順位の期待値はj(n + 1)/(i + 1)です。3人目まで進むと必ずその人を選ぶことになり、その順位の期待値は(n + 1)/2です。
  
  $\frac{j(n+1)}{i+1}=\frac{4j}{i+1},\qquad c_2=\frac{3+1}{2}=2$
2. 2人目の候補者では、その人の順位の期待値が2以下なら選び、それより大きければ次に進みます。
  
  $i=2:\ \ j=1:\ \tfrac{4}{3}<2,\quad j=2:\ \tfrac{8}{3}>2;\qquad c_1=\frac{1}{2}\left(\frac{4}{3}+2\right)=\frac{5}{3}$
3. 最初の候補者を選ぶと順位の期待値は2で、5/3より大きいので、次に進みます。
  
  $i=1:\ \ \frac{4}{2}=2>\frac{5}{3}\ \Rightarrow\ c_0=c_1=\frac{5}{3}$
解答

最初の候補者を見送り、2人目が最初の人より優れていれば選びます。そうでなければ3人目を選びます。順位の期待値は5/3 ≈ 1.67。候補者が3人なら、これはk = 1の閾値戦略と一致します。

$c_0=\frac{5}{3}\approx1.6667$
候補者2人で、得点がわかる場合 2 ステップ
2人の候補者の得点は、それぞれ独立に0から1の一様分布に従い、候補者が現れるたびに得点がわかります。得点の高い人を選ぶ確率が最大になるルールと、その確率を求めましょう。順位だけがわかる場合とも比べてください。

この問題をツールで開く
解答を表示
1. 最初の候補者の得点をxとします。この人を見送ると2人目を選ぶことになり、その得点がxより高ければ成功なので、成功確率は1 − xです。最初の候補者を選ぶなら、2人目の得点がxより低ければ成功なので、成功確率はxです。
  
  $S(x)=x,\qquad C(x)=1-x;\qquad S(x)\ge C(x)\iff x\ge\tfrac{1}{2}$
2. したがって、x ≥ 1/2なら最初の候補者を選びます。xについて平均を取ると、
  
  $\int_{0}^{1/2}(1-x)\,dx+\int_{1/2}^{1}x\,dx=\frac{3}{8}+\frac{3}{8}=\frac{3}{4}$
解答

最初の候補者の得点が1/2以上なら選び、成功確率は3/4です。順位しかわからない場合、候補者が2人なら、どのルールでも成功確率は1/2です。

$P=\frac{3}{4}>\frac{1}{2}$

補充問題（答えのみ）

候補者が5人のとき、最適な見送り数と成功確率を求めましょう。

答えを表示

最初の2人を見送り、13/30 ≈ 43.33%です。

$k^*=2,\qquad P(2)=\frac{2}{5}\left(\frac{1}{2}+\frac{1}{3}+\frac{1}{4}\right)=\frac{13}{30}\approx0.4333$
候補者が2人で順位しかわからないとき、どのルールでも最良の候補者を選ぶ確率が半分になることを示しましょう。

答えを表示

最初の候補者を選べば成功確率は1/2。見送れば2人目を選ぶことになり、やはり1/2です。

$P(0)=\frac{1}{2},\qquad P(1)=\frac{1}{2}\cdot\frac{1}{1}=\frac{1}{2}$
候補者10人で最適な見送り数を使うとき、最良の候補者を最初に見送る確率と、最後の候補者まで選考が続く確率を求めましょう。

答えを表示

k = 3で、それぞれ30%と3/9 ≈ 33.33%です。

$k^*=3:\quad\frac{3}{10}=0.3,\qquad\frac{3}{9}\approx0.3333$
nが大きくなる極限で、候補者の5分の1を見送る場合と、5分の3を見送る場合の成功確率を求めましょう。

答えを表示

それぞれ−0.2 ln 0.2 ≈ 32.19%、−0.6 ln 0.6 ≈ 30.65%です。

$-0.2\ln0.2\approx0.3219,\qquad-0.6\ln0.6\approx0.3065$
候補者が4人のとき、あらゆるルールで達成できる順位の期待値の最小値を求めましょう。

答えを表示

15/8 = 1.875です。

$c_0=\frac{15}{8}=1.875$

4分の1を見送っても、半数を見送っても、成功確率は同じ

曲線の頂上付近は平らです。このおかげで、ルールを多少おおまかに使っても役に立ちます。4分の1を見送るを押すと35.04%、半数を見送るなら34.91%。100人の場合、最適な見送り数は37人で、成功確率は37.1%です。見送る割合が4分の1から半数の間なら、下がる幅は最大でも2.2ポイントに収まります。nが大きくなると、曲線は見送る割合をxとして−x ln xに近づきます。4分の1と半数では、¼ ln 4 = ½ ln 2 ≈ 34.66%となり、値はぴったり一致します。候補者の総数を正確に知らなくてもかまいません。実際より3分の1多く、あるいは3分の1少なく見積もり、その37%を見送っても、nが大きければ成功確率は少なくとも34.5%あります。

最良だけを狙うと、3回に1回以上は最後の候補者を選ぶ

このルールは、最良の候補者を選ぶことにすべてを賭けています。最良の候補者を最初に見送ってしまうと、その後は基準を超える人が現れません。選考は最後まで続き、最後に来た人を選ぶことになります。100人の場合、その確率は37%です。100人中37人を見送るを押してみましょう。選ばれる人の順位の期待値は20.01です。1964年、チョウ、森口、ロビンズ、サミュエルズは、順位の期待値を最小にするルールを考えました。このルールでは、それまでに会った中で上位に入っていれば選ぶことがあり、残りの候補者が減るにつれて基準を緩めます。n = 100での順位の期待値は3.60。このページで扱うどのnでも4を下回り、極限では3.8695に近づきます。一方、37%ルールの順位の期待値はnとともに増え続け、1,000人では185.54になります。

得点がわかれば、成功確率は58%に上がる

37%ルールで使う情報は、誰が誰より優れているかという順位だけです。各候補者の実際の得点が見え、得点の分布もわかるとしましょう。たとえば、0から1の一様分布です。ギルバートとモステラーが1966年に解いたこの問題では、初めに全員を見送る期間はなくなります。最初の候補者から選ぶ可能性があり、それまでで最良、かつ得点が閾値を超えていれば選びます。残りの候補者が減るにつれて閾値は下がり、残り1人なら0.5、2人なら0.6899、10人なら0.9240です。最良の候補者を選べる確率は、11人で60.6%、100人で58.29%。極限では58.02%に近づきます。順位だけがわかる場合の極限値は36.79%ですから、どのくらいの得点なら優秀かを知るだけで、約21ポイントの差が生まれます。

学習の道すじ

得られた情報をもとに選ぶ

参考文献 (4)

The problem as now studied (n known, random order, relative ranks only, no recall, only the best counts), the cutoff rule and its chance, and the history the page uses: Kepler, after losing his first wife in 1611, spent nearly two years over at least eleven candidates, described in a letter to Baron Strahlendorf of 23 October 1613; friends persuaded him to propose to the fourth after he met the fifth, the fourth turned him down, and he chose the fifth. Ferguson notes that for n = 11 the rule's chance is largest when the fifth is the first candidate it may take, and that Kepler's recall breaks the problem's assumptions: T. S. Ferguson, Who solved the secretary problem? Statistical Science 4(3), 282–289 (1989). doi:10.1214/ss/1177012493
The classical secretary problem solved by backward induction, the limits the page quotes in insight blocks 2 and 3: the least expected rank tends to 3.8695 (Chow, Moriguti, Robbins and Samuels), and with the values revealed and their distribution known the chance of the best tends to 0.58016 (Gilbert and Mosteller), 'to be compared to the limiting value e⁻¹ when the intrinsic values are not revealed': T. S. Ferguson, Optimal Stopping and Applications, Chapter 2, Finite Horizon Problems, §§2.1–2.3. Mathematics Department, UCLA (online text).
The rank-minimising rule of insight block 2 and solved problem 6: accept a candidate whose relative rank is within a threshold that rises as the candidates run out, with expected rank tending to 3.8695: Y. S. Chow, S. Moriguti, H. Robbins and S. M. Samuels, Optimal selection based on relative rank (the "secretary problem"). Israel Journal of Mathematics 2(2), 81–90 (1964). doi:10.1007/BF02759948
The full-information problem of insight block 3 and solved problem 7: values seen, independent with a known distribution; the optimal rule takes a best-so-far above a threshold that depends on how many remain, and the chance of the best tends to 0.5802: J. P. Gilbert and F. Mosteller, Recognizing the maximum of a sequence. Journal of the American Statistical Association 61(313), 35–73 (1966). doi:10.1080/01621459.1966.10502008

7 Raven Room チーム · 公表された資料と照合しています。訂正のご指摘を歓迎します。

37%ルール

公式の導き方

補充問題（答えのみ）

4分の1を見送っても、半数を見送っても、成功確率は同じ 🖖

最良だけを狙うと、3回に1回以上は最後の候補者を選ぶ 🖖

得点がわかれば、成功確率は58%に上がる 🖖

4分の1を見送っても、半数を見送っても、成功確率は同じ

最良だけを狙うと、3回に1回以上は最後の候補者を選ぶ

得点がわかれば、成功確率は58%に上がる