[機統] 河邊撿石頭問題，撿到最大顆的機率？

[grassboy2 (小胖子．吳草兒)]

河道上有 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://www.ptt.cc/bbs/Math/M.1628741141.A.9B7.html
推 LPH66       : 解法 A 沒算到前 n/2 顆出了不是第二大
→ LPH66       : 但後 n/2 中第一個比較大的就是最大的狀況
→ LPH66       : 例如前半有第三大, 但第二大排在最大的後面
！！懂了！！
原來有這個盲點！太感謝了m(_ _)m
→ LPH66       : 啊, 我是在說 25% 算法的問題沒錯 @@
推 arrenwu     : 其實我不太懂這問題的「策略」長什麼樣子
→ arrenwu     : 不然只是要最大機率，不就把n科都看完選最大的？
→ Ricestone   : 走過去不能回頭  只能撿一次
→ Ricestone   : 這就麥穗問題
→ mantour     : 37%的解法的前提是假設石頭大小跟排列順序完全無關
→ mantour     : 。所以還有進階題：如果是兩人對賭，對方可以猜測
→ mantour     : 你可能的策略來排石頭的順序，盡量讓你拿不到最大
→ mantour     : 的，又因應對方可能的策略，你也可以對應的調整策
→ mantour     : 略，那雙方的最佳策略為何？
降子變因不會太多嗎？我針對你針對我的策略擬定新的策略降子？
→ HeterCompute: 這問題真的問到爛了，各種包裝這問題的都看過，還有
→ HeterCompute: 每次看這問題都期待到底有沒有其他變形好玩
推 arrenwu     : 這個問題對於石頭大小相關的 Prior Distribution
→ arrenwu     : 是啥樣子啊？
推 LPH66       : 最一開始的問題的話就是 n! 種大小排列等機率吧
※ 編輯: grassboy2 (122.116.92.241 臺灣), 08/13/2021 11:56:48
→ charlie1667 : 為什麼兩人要互相 一人排一人撿就好啦
→ charlie1667 : 兩邊石頭set一樣的話等撿自己set裡最大那顆就好啦