设共有 \(n\) 个人,放弃前 \(k\) 个人,若按此策略最终选到最优的人的概率为 \(P(k)\),则
\[\begin{aligned} P(k)&=P(\text{第 }(k+1)\text{ 个人是最优的})+P(\text{第 }(k+2)\text{ 个人是最优的}+\cdots+P(\text{第 }n\text{ 个人是最优的}) \\ &=\frac1n+\frac1n\cdot\frac k{k+1}+\frac1n+\frac k{k+2}+\cdots+\frac1n\cdot\frac k{n-1} \\ &=\frac kn\left(\frac1k+\frac1{k+1}+\frac1{k+2}+\cdots+\frac1{n-1}\right) \\ &=\frac kn\sum_{i=k}^{n-1}\frac1i \end{aligned} \]则问题转化为超简单的规划问题
\[\max\ \ \frac kn\sum_{i=k}^{n-1}\frac1i\quad(k\le n,k\in\mathbf N_+) \]在 \(n\) 较小时,直接一波非线性规划求整数解。
在 \(n\) 很大时,注意到 \(k/n\sum_{i=k}^{n-1}1/i\) 即是 \(y=1/x\) 将区间 \((k/n,1)\) 分割成宽度为 \(1/n\) 的小区间后的黎曼和。令 \(x=k/n\),易知
\[P(k)=\frac kn\sum_{i=k}^{n-1}\frac1i\approx x\int_x^1\frac1x\mathrm dt=-x\ln x \]为求 \(P(k)\) 最大值,令 \(P'(k)=-(1+\ln x)=0\),有 \(x=1/\mathrm e\approx36.8\%\)。此时 \(P(k)=-1/\mathrm e\ln1/\mathrm e=1/\mathrm e\approx36.8\%\)。
在存在拒绝概率 \(p\) 的变体情况下,最优策略需满足
\[\prod_{i=k+1}^{n-1}\left(1+\frac pi\right)\le\frac1{1-p} \]目标函数变为
\[P(k)=\frac{1-p}{pn}\left[(k+p)\prod_{i=k+1}^{n-1}\left(1+\frac pi\right)-k\right] \]容易发现
\[\left(\frac{i+1}i\right)^p<1+\frac pi<\left(\frac{i+p}{i-1+p}\right)^p \]下一步我不是特别懂,照抄文献了
\[\left(\frac n{k+1}\right)^p<\frac1{1-p}<\left(\frac{n-1+p}{k-1+p}\right)^p \]由此
\[n(1-p)^{1/p}<k+1<n(1-p)^{1/p}+1+(1-p)\left[1-(1-p)^{1/p}\right] \]从而最优策略应该舍弃的位置以及选到最优秀的人的概率极其简洁
\[\lim_{n\to\infty}P(k)=\lim_{n\to\infty}\frac kn=\lim_{n\to\infty}\frac{k+1}n=(1-p)^{1/p} \]在 \(p\) 趋向于 \(0\) 时,即不会被拒绝,问题化为原始的 37% 法则
\[\lim_{p\to0}~(1-p)^{1/p}=\frac1{\mathrm e}\approx36.8\% \] 标签:概率,frac,text,right,黎曼,条件,frac1,mathrm,left From: https://www.cnblogs.com/laoshan-plus/p/18365009