Re: [機統] 手遊抽箱問題

[xxxx9659 (嘎嘎嘎嘎嘎)]

※ 引述《Hsiehshun (金毛獅王)》之銘言：
: 這是在某個手遊遇到的問題，情況如下
: 簡化版：
: 一個箱子內有 90 個物品，其中有 5 個「物品 B」
: 每次隨機自箱中取出一個物品，取後不放回
: 每抽結束後有兩種選擇
: 1. 繼續抽原本的箱子
: 2. 前進到下一個箱子，重新從 5 / 90 開始抽
: 問題：給定 N 抽 (N >> 90) 的情況下，找出最佳策略使得獲得「物品 B」的期望值最大
: 因為 N 夠大，我會覺得策略只和箱內剩餘數及剩下「物品 B」的個數有關，
: 直覺上我會認為最佳策略是當剩下「物品 B」比例小於 5/90 時就該重置，
: 但不知是否正確

這樣的最佳策略不正確，我找個反例給你看

假設有個箱子剩 20 個物品，其中只有 1 個「物品 B」
這個箱子的下一次抽到的機率是1/20 < 5/90，會被重置
但是如果你繼續抽，平均再10.5抽就會抽到「物品 B」

我猜的最佳策略是長這樣 (沒有嚴謹的證明，可能有錯)
一個箱子內有 n 個物品，其中有 k 個「物品 B」

case k = 5:  n > 90 重置
case k = 4:  n > 74 重置
case k = 3:  n > 58 重置
case k = 2:  n > 42 重置
case k = 1:  n > 24 重置
case k = 0:  重置

這樣的話，給你抽 N 次， 平均可獲得「物品 B」的數量
= 2.048273569 / 26.57544954 * N 個
= 0.07707390107 * N 個


你的最佳策略
= 1.800168412 / 23.50768259 * N 個
= 0.07657787644 * N 個


--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 125.227.45.150 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1605287626.A.C89.html
推 Hsiehshun   : 請問24,42,58,74是怎麼來的呢 我照這方法跑模擬結
→ Hsiehshun   : 果差不多 有時候最佳解會差1
→ Hsiehshun   : 還有就是平均10.5抽就一定比5/90好這點我也不太懂
→ Hsiehshun   : 用動態規劃+疊代會收斂 算是能說服自己這是最佳解
推 kevinmath   : 看不懂,在沒預算限制之下原po的策略應該比較好吧
推 LPH66       : 我好像抓到差別了: 我們要追的是「抽出下一個所花費
→ LPH66       : 次數的期望值」, 當它降到比重新來的少時重抽
→ LPH66       : 不是用機率來看的原因是這期望值是幾何分布
→ LPH66       : 也就是機率的倒數, 而機率平均跟機率倒數平均不同
→ LPH66       : 所以不能用機率來看, 而要去看這幾何分布的期望值
→ LPH66       : 沒細算過是不是數字上能合, 但或許是個可能解釋
推 terio       : 這不是幾何分佈，每次抽去機率都會因上一次抽取結
→ terio       : 果而變化
推 terio       : 原來是超幾何分佈，所以求不同剩餘B狀況下對應90剩
→ terio       : 五個的期望值就好
→ xxxx9659    : 24,42,58,74 我在excel拉一個表 然後亂填看結果...
→ xxxx9659    : 然後調到這個參數最好 多一份太肥 少一分太瘦
→ xxxx9659    : https://i.imgur.com/HuRmLNR.png
→ xxxx9659    : https://reurl.cc/EzyolR
→ xxxx9659    : 你原本的策略 18,36,54,72 期望值也很高
推 LPH66       : 超幾何...好吧, 是個我只聽過名字的東西 orz