专栏文章

苏格拉底的雕像

aaleph_
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minwgldx
此快照首次捕获于
2025/12/02 09:28
3 个月前
此快照最后确认于
2025/12/02 09:28
3 个月前
查看原文
设歌剧院内有 nn 座雕像，则雕像的编号依次为 1∼n1\sim n，假设雕像体积在一定范围内均匀随机。目前他们制定的策略为：
  1. 从前 rr 个雕像中找出体积最大的雕像，设其体积为 max⁡\max。（第三个弟子的策略改进版即取 r=n3r=\frac{n}{3}）
  2. 从后 r+1∼nr+1\sim n 个雕像中选出第一个体积大于等于 max⁡\max 的雕像（和第三个弟子的情况不同，每次只能检查 11 个雕像，因为歌剧院内部没有通电，伸手不见五指）
  3. 否则就自认倒霉，选最后一个雕像。
设 P(r)P(r) 按此策略成功选出最大雕像的概率，显然：
P(r)=P(第r+1个雕像是最大的，且第r+1个雕像被选择)P(r)=P(第r+1个雕像是最大的，且第r+1个雕像被选择)
+P(第r+2个雕像是最大的，且第r+2个雕像被选择)+P(第r+2个雕像是最大的，且第r+2个雕像被选择)
+⋯+\cdots
+P(第n个雕像是最大的，且第n个雕像被选择)+P(第n个雕像是最大的，且第n个雕像被选择)
可记作
P(r)=∑k=r+1nP(第k个雕像是最大的，且第k个雕像被选择)P(r)=\sum_{k=r+1}^nP(第k个雕像是最大的，且第k个雕像被选择)
考虑如何求出
P(第k个雕像是最大的，且第k个雕像被选择)P(第k个雕像是最大的，且第k个雕像被选择)
这等价于
P(第k个雕像是最大的)×P(第k个雕像是最大的∥第k个雕像被选择)P(第k个雕像是最大的)\times P(第k个雕像是最大的\|第k个雕像被选择)
前者即 1n\frac{1}{n}（因为雕像体积是均匀随机的，任何一个雕像都可能成为最大体积的雕像）。
而后者的条件成立，当且仅当前 k−1k-1 个雕像中，最大的雕像在前 rr 个中，概率为 rk−1\frac{r}{k-1}。
证明比较容易，使用反证法：如果最大的雕像位于第 r+1∼k−1r+1\sim k-1 个中，那么根据策略，这个最大的雕像就会被提前选择，也就轮不到再选择第 kk 个雕像了。
那么
P(r)=∑k=r+1n1n⋅rk−1P(r)=\sum_{k=r+1}^{n} \frac{1}{n}\cdot\frac{r}{k-1}
将与 kk 无关的部分移到求和外面去，并把 kk 看作 k−1k-1，得
P(r)=rn∑k=rn−11kP(r)=\frac{r}{n}\sum_{k=r}^{n-1}\frac{1}{k}
(r≤n,r∈N+)(r\le n,r\in \N^+)
当 nn 很大时，求和符号即可化为黎曼和形式。
P(r)≈rn∫rn1kdkP(r)\approx\frac{r}{n}\int_{r}^n \frac{1}{k}dk
令 x=rn(0<x<1)x=\frac{r}{n}(0<x<1)，把 kk 替换成 xx，则有
P(r)≈x∫x11xdx=xln⁡1−xln⁡xP(r)\approx x\int_{x}^1\frac{1}{x}dx=x\ln 1-x\ln x
P(r)≈−xln⁡xP(r)\approx -x\ln x
求导得
P′(r)=−(x⋅1x+ln⁡x⋅1)=−(1+ln⁡x)P'(r)=-(x\cdot\frac{1}{x}+\ln x\cdot 1)=-(1+\ln x)
当 P(r)P(r) 取得极值时，应有导数为 00，解方程
−(1+ln⁡x)=0-(1+\ln x)=0
x=1e≈36.8%x=\frac{1}{e}\approx 36.8\%
分析单调性可发现此时取得最大值，且在定义域内。
带回可得 P(r)=1e≈36.8%P(r)=\frac{1}{e}\approx 36.8\%。
还记得 xx 的意义吗？等于 rn\frac{r}{n}，也就是观察阶段占整体的比值。经过X的一番分析，发现观察期的长度为整体的 36.8%36.8\% 时最优，且之后选取到最大值的概率也为 36.8%36.8\%。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...