作者ddavid (谎言接线生)
看板Prob_Solve
标题Re: [问题] 机率问题-取得特定值即重置的期望值
时间Thu May 5 18:10:29 2022
※ 引述《hackerick4 (窝颗颗)》之铭言：
: 一个箱子有 m 颗球，其中前1～n颗球价值为v1，後续 m-n 颗球价值为 v2。 抽取k次，取後
: 不放回。 但如果取到 v1 价值的球，就要把刚刚取过的球再放回去箱子，下次抽的时候就是
: 回归 m 颗球的条件
: 请问这样的命题，如果不跑模拟的状况之下，v1球的期望值是多少
: 我能想到的是用生成函数去解递回，但计算量十分庞大，有没有高手可以分享做法呢？
: 推 FRAXIS: 你能不能先把递回式写出来阿? 04/29 23:33
: 推 alan23273850: 这语意也写得太不清楚... 05/02 10:37
x1 = (m - n) # 第 1 抽时价值为 v2 的球数量
第 1 次抽取随机事件 X1 = v1 机率 (n / (n + x1))
v2 机率 (x1 / (n + x1))
E(X1) = (n/(n + x1))v1 + (x1/(n + x1))v2
xi = (m - n) if X(i-1) = v1 # 前次抽到 v1 球会 reset 所有球
x(i-1) - 1 if X(i-1) = v2 # v2 球量在前次抽到 v2 球时会减一
# 注意 v1 球量永远会是 n，因为一抽到
# v1 就所有球 reset
第 i 次抽取随机事件 Xi = v1 机率 (n / (n + xi))
v2 机率 (xi / (n + xi))
E(Xi) = E(X(i-1)) + (n/(n + xi))v1 + (xi/(n + xi))v2
这麻烦在每一次的随机事件机率会被前面事件的连续抽到 v2 球次数决定。换个
方式写的话，第 i 次的随机事件 Xi 是这样：
ci = 到第 (i-1) 次为止连续抽到 v2 的次数（即 X(i-ci-1) = v1，X(i-ci) 到
X(i-1) 连续 = v2）
第 i 次抽取随机事件 Xi = v1 机率 (n / (m - ci))
v2 机率 ((n - ci - n) / (m - ci))
要展开 E(Xi) 需要知道 ci，而 ci 不是一个定值，而是之前事件发生的结果决
定。我写到这里就知识不足不知道怎麽解下去了XD
--
「传说的最後，魔王总是被勇者封印。但勇者会逝去、封印会衰弱，魔王却永远
不灭。传说呢？传说持续着。只是，变质了。所以对於传说而言，只有反覆无常的自
己是主角，而魔王只是配角。勇者？勇者不过是消耗品罢了，封印则什麽也不是。你
好不容易有机会当上配角，怎麽走回头路想成为消耗品？你早晚会什麽也不是的。」
－－星．幻．梦的传说
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 114.32.17.60 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1651745431.A.553.html
※ 编辑: ddavid (114.32.17.60 台湾), 05/05/2022 18:11:04
1F：推 FRAXIS: 我看到这问题直觉觉得是 Markov Chain 05/05 23:06
2F：推 FRAXIS: n 个 column, m 个 row, 起点是 (0, 0) 05/05 23:09
3F：→ FRAXIS: 在(i, j) 点 拿到 v1 球就 transit 到 (0, j+1) 05/05 23:09
4F：→ FRAXIS: 拿到 v2 球就 transit 到 (i+1, j) 05/05 23:10
5F：→ FRAXIS: 先算出 k 步後每个 state 的 probability 05/05 23:11
6F：→ FRAXIS: 就可以算期望值了, 因为(i, j) state 表示拿到 j 个 v1 球 05/05 23:11
我忽然发现我看错题目了，以为他要算最终取球价值加总的期望值XD
所以你说的对XD
※ 编辑: ddavid (114.44.37.217 台湾), 05/06/2022 00:39:15