作者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://www.ptt.cc/bbs/Prob_Solve/M.1651745431.A.553.html
※ 編輯: ddavid (114.32.17.60 臺灣), 05/05/2022 18:11:04
推 FRAXIS: 我看到這問題直覺覺得是 Markov Chain 05/05 23:06
推 FRAXIS: n 個 column, m 個 row, 起點是 (0, 0) 05/05 23:09
→ FRAXIS: 在(i, j) 點 拿到 v1 球就 transit 到 (0, j+1) 05/05 23:09
→ FRAXIS: 拿到 v2 球就 transit 到 (i+1, j) 05/05 23:10
→ FRAXIS: 先算出 k 步後每個 state 的 probability 05/05 23:11
→ FRAXIS: 就可以算期望值了, 因為(i, j) state 表示拿到 j 個 v1 球 05/05 23:11
我忽然發現我看錯題目了,以為他要算最終取球價值加總的期望值XD
所以你說的對XD
※ 編輯: ddavid (114.44.37.217 臺灣), 05/06/2022 00:39:15