作者grassboy2 (小胖子．吴草儿)
看板Math
标题[机统] 河边捡石头问题，捡到最大颗的机率？
时间Thu Aug 12 12:05:39 2021
河道上有 n 个石头，依序去看，看到一颗你觉得最大颗的石头就捡，
只有一次机会，只能捡一颗，放弃的石头不能回头捡
用什麽方法捡，可以尽可能让捡到的石头是最大颗的？
解法A：
先看完前 n/2 颗石头，後 n/2 颗石头只要遇到比前 n/2 颗都大的话就捡
假设有 n 颗石头，第二大颗出现在前一半的机率是 50%，
最大颗出现在後一半的机率是 50%
所以这个策略共有 50%*50% = 25% 的机率捡到最大颗
最近看过有影片在讨论这个问题
https://www.youtube.com/watch?v=GXjlYWw7ZPI
里面也有完整算式导出答案是 37%
不过从这个影片回头检视解法A的策略
假设最大颗出现在第 (n/2)+1 颗，机率 1/n*( (n/2)/(n/2 ))
： (n/2)+2 ： 1/n*( (n/2)/(n/2 + 1 ))
： (n/2)+3 ： 1/n*( (n/2)/(n/2 + 2 ))
： ：
： ：
假设最大颗出现在第 (n/2)+(n/2) 颗，机率 1/n*( (n/2)/(n/2 + (n/2 - 1) ))
故采解法 A 的策略，捡到最大颗的机率为上面所有机率加总
即
1/2 * (1/(n/2) + 1/(n/2+1) + 1/(n/2+2) + ... + 1/(n-2) + 1/(n - 1))
= 1/2 * (ln(n) - ln(n/2))
= 1/2 * ln(2)
= 0.3465...
也就是 34.7% 的机率
为什麽策略A用两种不同的思路算机率，会得出差异如此大(25% vs 34.7%)的结果？
有人可以协助点出算出 25% 的盲点吗？
谢谢 m(_ _)m
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 122.116.92.241 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Math/M.1628741141.A.9B7.html
1F：推 LPH66 : 解法 A 没算到前 n/2 颗出了不是第二大 08/12 12:29
2F：→ LPH66 : 但後 n/2 中第一个比较大的就是最大的状况 08/12 12:29
3F：→ LPH66 : 例如前半有第三大, 但第二大排在最大的後面 08/12 12:30
！！懂了！！
原来有这个盲点！太感谢了m(_ _)m
4F：→ LPH66 : 啊, 我是在说 25% 算法的问题没错 @@ 08/12 12:35
5F：推 arrenwu : 其实我不太懂这问题的「策略」长什麽样子 08/12 13:07
6F：→ arrenwu : 不然只是要最大机率，不就把n科都看完选最大的？ 08/12 13:07
7F：→ Ricestone : 走过去不能回头 只能捡一次 08/12 13:07
8F：→ Ricestone : 这就麦穗问题 08/12 13:08
9F：→ mantour : 37%的解法的前提是假设石头大小跟排列顺序完全无关 08/12 15:48
10F：→ mantour : 。所以还有进阶题：如果是两人对赌，对方可以猜测 08/12 15:48
11F：→ mantour : 你可能的策略来排石头的顺序，尽量让你拿不到最大 08/12 15:48
12F：→ mantour : 的，又因应对方可能的策略，你也可以对应的调整策 08/12 15:48
13F：→ mantour : 略，那双方的最佳策略为何？ 08/12 15:48
降子变因不会太多吗？我针对你针对我的策略拟定新的策略降子？
14F：→ HeterCompute: 这问题真的问到烂了，各种包装这问题的都看过，还有 08/12 22:05
15F：→ HeterCompute: 每次看这问题都期待到底有没有其他变形好玩 08/12 22:05
16F：推 arrenwu : 这个问题对於石头大小相关的 Prior Distribution 08/12 22:26
17F：→ arrenwu : 是啥样子啊？ 08/12 22:26
18F：推 LPH66 : 最一开始的问题的话就是 n! 种大小排列等机率吧 08/13 00:43
※ 编辑: grassboy2 (122.116.92.241 台湾), 08/13/2021 11:56:48
19F：→ charlie1667 : 为什麽两人要互相 一人排一人捡就好啦 08/13 12:05
20F：→ charlie1667 : 两边石头set一样的话等捡自己set里最大那颗就好啦 08/13 12:07