最適秘書問題について
概要
- N人の候補者の中から最適な秘書を選ぶ最適戦略の問題
- 一度面接で落とした人は再び雇うことはできない
- N人の候補者は固定
- 最後の面接者になったら雇う
- 基本戦略
- K人までを結果のいかんに関わらず落とす
- K人までのそれまでの人より良かったら雇い、面接を終了する
- 最適なKがあるはず
- 留意点
- 最適な秘書を選ぶ確率の最大化問題であって、秘書の順位の期待値の最大化問題ではない
- 順位の最大化する点は別にある
- 最適な秘書を選ぶ確率の最大化問題であって、秘書の順位の期待値の最大化問題ではない
t番目に最も優れた人がいる確率
\[\frac{1}{N}\]基本戦略により、t番目の人を選ぶ確率
\[\frac{K}{t-1}\]よって成功する確率は
\[\frac{1}{N} \sum_{t=K+1}^{N} \frac{K}{t-1} = \frac{K}{N} \log \frac{N}{K}\]これをkについて微分する
\[k=\frac{n}{e}\]で最大となる
最適値と期待値の最大化は異なる
仮にN人までをランキングできるとすると、ランクの期待値の最大化を行いたいとき、サンプル数はN/10程度でよい
実験コード
import random
import numpy as np
import pandas as pd
N = 100
samples = []
for try_num in range(10000):
df = pd.DataFrame({"rank": list(range(N))})
df = df.sample(frac=1)
hisho = df["rank"].tolist()
for k in range(1, N):
# kまでの最大の点数
tmp = -1
for i in range(k):
tmp = max(hisho[i], tmp)
# select
for s in range(k+1, N):
if hisho[s] > tmp:
samples.append((k, hisho[s]))
break
if s == N-1:
samples.append((k, hisho[s]))
break
x = pd.DataFrame(samples)
x.columns = ["k", "selected_rank"]
x.groupby(by=["k"]).agg(mean_rank=("selected_rank", "mean"))
最大のランクの人を選ぼうとすると、その確率が最大化するのが、N/eのときである
x["is_best"] = x["selected_rank"].apply(lambda x: x == 99).astype(int)
x.groupby(by=["k"]).agg(best_prob=("is_best", "mean"))
with pd.option_context("display.max_rows", None, "display.max_columns", None):
display(x.groupby(by=["k"]).agg(best_prob=("is_best", "mean")))