最適停止問題と秘書問題（37%の法則）

Q: 最適停止問題と秘書問題（37%の法則）とは何ですか？

**秘書問題（Secretary Problem / 最適停止問題）**とは、n 人の候補者がランダムな順序で1人ずつ現れ、各候補者についてその場で採用か不採用かを即座に決定しなければならず（後戻りは不可）、全体の中で真の第1位（最優秀者）を採用できる確率を最大化する問題である。

Q: 最適停止問題と秘書問題（37%の法則）は社会やプログラミングでどのように使われていますか？

モンテカルロ法による最適停止戦略のシミュレーション: 様々な見送り比率において最優秀者を選択できる確率を実験的に検証するPythonコードです。

面接・結婚・物件探し — いつ決断すべきか？数学が導く人生の最適戦略

この単元の発見をシェア

3行要約（Key Takeaways / AIOサマリー）

1: 全体人数の最初の 37%（正確には 1/e ≈ 36.8%）は『基準作りのための見送り期間』として絶対に採用しない
2: 37%を過ぎた後、それまでに見送りした全員の中で最高だった人物を上回った最初の応募者を即決採用する
3: この戦略を取ることで、何百人もの候補者の中から最も優秀な1人を採用できる確率が最大（約37%）になる

なぜこれを学ぶのか？ — 現実社会とテクノロジーでの価値

Purpose & Motivation

なぜ生まれたのか？

『もっと良い人が現れるかもしれない（後悔の恐怖）』と『今決めないと逃してしまう（機会損失）』の葛藤。日常生活のあらゆる『一度断ったら戻れない選択（物件探し・就活・パートナー選び）』に数学が明快な答えを授けます。

身につく武器・思考力

探索と活用のトレードオフ（Exploration vs. Exploitation）の理解、ネイピア数 $e$ の日常応用、合理的な意思決定力

実社会・ITでの活躍現場

•不動産・賃貸マンション探し（何件内見して決めるべきか）
•企業の採用面接・オーディションの選考設計
•クラウドインフラの動的スポットインスタンス購入アルゴリズム
•オークションの入札タイミング最適化

Layer 1 — 直感・シミュレーター

候補者の総数を設定し、「見送り率（何%まで見送るか）」のスライダーを動かしてシミュレーションを実行してみましょう。1000回以上の試行を回すと、見送り率が37%付近のときにベストな候補者を選べる成功率が最も高くなることがグラフで確かめられます。

数学が導く「最高の決断」タイミング

秘書問題（37%の法則）：なぜ最初の37%を見送ると成功率が最大になるのか？

面接に来た候補者はその場で合否を告げねばならず後戻りは不可。早すぎると基準が低すぎて凡人を掴み、遅すぎると真の最高人材を見送り期間で逃してしまう。情報収集と決断の黄金比 $1/e \\approx 36.8\\%$ をインタラクティブに体験しましょう。

候補者総数20 人

見送り比率（探索期間）37% ★理論的最適値 (1/e)

直感チェック！ミニクイズ

100日間の婚活・面談期間があるとき、最適停止理論（37%ルール）に従うと、最初の何日間は見送って基準作りに充てるべきか？

Layer 2 — 定義・受験・証明

定義

**秘書問題（Secretary Problem / 最適停止問題）**とは、 $n$ 人の候補者がランダムな順序で1人ずつ現れ、各候補者についてその場で採用か不採用かを即座に決定しなければならず（後戻りは不可）、全体の中で真の第1位（最優秀者）を採用できる確率を最大化する問題である。

公式・数理モデル

P(r) = \frac{r-1}{n} \sum_{i=r}^{n} \frac{1}{i-1} \approx - x \ln(x) \quad \left(x = \frac{r}{n}\right) \text{成功確率最大値: } x^* = \frac{1}{e} \approx 0.367879... \quad (36.8\%)

証明・導出

**1/e（37%）の導出**

最初の $r-1$ 人を見送り、それ以降で過去最高を更新した候補者を採用する戦略をとる。第 $i$ 番目の候補者（ $i \ge r$ ）が最優秀であり、かつ採用されるための条件は： 1. 第 $i$ 番目が全体 $n$ 人の中で最優秀である（確率 $1/n$ ） 2. 第 $1$ 番目から第 $i-1$ 番目までの最優秀者が、最初の見送り枠 $r-1$ 人の中に含まれている（さもないと $r$ から $i-1$ の誰かが採用されてしまう。条件付き確率 $\frac{r-1}{i-1}$ ）

これらを $i = r$ から $n$ まで足し合わせると：

P(r) = \sum_{i=r}^n \frac{1}{n} \frac{r-1}{i-1} = \frac{r-1}{n} \sum_{i=r}^n \frac{1}{i-1}

$n \to \infty$ において $x = r/n$ と置き、区分求積法（積分）で近似すると：

P(x) = x \int_x^1 \frac{1}{t} dt = -x \ln(x)

これを $x$ で微分して極値を求めると：

P'(x) = -\ln(x) - 1 = 0 \implies \ln(x) = -1 \implies x = e^{-1} = \frac{1}{e} \approx 0.368

このとき最大成功確率は $P(1/e) = -(1/e) \ln(1/e) = 1/e \approx 36.8\%$ となる。

押さえておきたいポイント

見送りが少なすぎると（例: 5%）、基準が甘すぎて序盤の平凡な人で妥協してしまう
見送りが多すぎると（例: 80%）、本物の最優秀者を見送り枠で逃してしまい、残りの誰でもない人を掴まされる
数学的黄金比 $1/e \approx 36.8\%$ こそが、情報収集（見極め）と決断（採用）の完全な境界線である

参照基準・学習指導要領との対応

本トピックの内容・数理モデルは、文部科学省学習指導要領（算数・数学・情報）および国際標準カリキュラムに準拠し、エンジニアリング現場の実装事例と照らし合わせてMath World Lab編集部により検証・作成されています。

Layer 3 — 工学応用・現場実装

モンテカルロ法による最適停止戦略のシミュレーション

様々な見送り比率において最優秀者を選択できる確率を実験的に検証するPythonコードです。

1import random
2import numpy as np
3
4def simulate_secretary_problem(n_candidates=100, trials=10000):
5    best_rate = 0
6    best_k = 0
7    
8    # 探索率 k/n を 0.05 から 0.95 まで走査
9    for split_ratio in np.linspace(0.05, 0.95, 19):
10        k = int(n_candidates * split_ratio)
11        success_count = 0
12        
13        for _ in range(trials):
14            # 候補者の真の実力値（重複なしスコア）
15            candidates = list(range(1, n_candidates + 1))
16            random.shuffle(candidates)
17            
18            # 見送り期間中の最高スコア
19            baseline_max = max(candidates[:k])
20            
21            # 見送り期間以降で最初の基準超えを採用
22            chosen = candidates[-1] # 誰も超えなければ最後の人
23            for c in candidates[k:]:
24                if c > baseline_max:
25                    chosen = c
26                    break
27                    
28            if chosen == n_candidates: # 真の最高得点者を採用できたか
29                success_count += 1
30                
31        success_rate = success_count / trials
32        print(f"見送り率: {split_ratio:.2f} -> 成功率: {success_rate:.3f}")