作者xxxx9659 (嘎嘎嘎嘎嘎)
看板Math
标题Re: [机统] 手游抽箱问题
时间Sat Nov 14 01:13:44 2020
※ 引述《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://webptt.com/cn.aspx?n=bbs/Math/M.1605287626.A.C89.html
1F：推 Hsiehshun : 请问24,42,58,74是怎麽来的呢 我照这方法跑模拟结 11/14 08:42
2F：→ Hsiehshun : 果差不多 有时候最佳解会差1 11/14 08:42
3F：→ Hsiehshun : 还有就是平均10.5抽就一定比5/90好这点我也不太懂 11/14 08:43
4F：→ Hsiehshun : 用动态规划+叠代会收敛 算是能说服自己这是最佳解 11/14 12:23
5F：推 kevinmath : 看不懂,在没预算限制之下原po的策略应该比较好吧 11/14 14:11
6F：推 LPH66 : 我好像抓到差别了: 我们要追的是「抽出下一个所花费 11/14 15:10
7F：→ LPH66 : 次数的期望值」, 当它降到比重新来的少时重抽 11/14 15:11
8F：→ LPH66 : 不是用机率来看的原因是这期望值是几何分布 11/14 15:11
9F：→ LPH66 : 也就是机率的倒数, 而机率平均跟机率倒数平均不同 11/14 15:12
10F：→ LPH66 : 所以不能用机率来看, 而要去看这几何分布的期望值 11/14 15:13
11F：→ LPH66 : 没细算过是不是数字上能合, 但或许是个可能解释 11/14 15:14
12F：推 terio : 这不是几何分布，每次抽去机率都会因上一次抽取结 11/14 16:21
13F：→ terio : 果而变化 11/14 16:21
14F：推 terio : 原来是超几何分布，所以求不同剩余B状况下对应90剩 11/14 17:06
15F：→ terio : 五个的期望值就好 11/14 17:06
16F：→ xxxx9659 : 24,42,58,74 我在excel拉一个表 然後乱填看结果... 11/14 17:55
17F：→ xxxx9659 : 然後调到这个参数最好 多一份太肥 少一分太瘦 11/14 17:56
20F：→ xxxx9659 : 你原本的策略 18,36,54,72 期望值也很高 11/14 18:20
21F：推 LPH66 : 超几何...好吧, 是个我只听过名字的东西 orz 11/14 19:20