Re: [機統] 魷魚遊第五關的通關人數期望值怎麼算

[arrenwu (不是綿芽的錯)]

※ 引述《ntpuisbest (阿龍)》之銘言：
: 如題
: 魷魚遊戲第五關玻璃橋
: 到達終點總共要經過18塊玻璃
: 而每次的經過都是兩片玻璃二選一
: 選對了就是強化玻璃
: 選錯了就是掉下去
: 假設選對選錯的機率都是二分之一
: 然後選手總共20位好了
: 再假設每位選手都有超凡記憶力
: 都有辦法記得自己前面的人經過哪些玻璃
: 而且可以趨吉避凶
: 那麼在不互相殘殺的狀況下
: 20位選手的期望通關人數是多少呢
: 我覺得這個問題很複雜
: 因為加入了人有記憶性這個條件後
: 感覺只有用程式模擬
: 配合大數法則才有可能算出來?
: 但是程式感覺rule也不太好寫

從 Linearity of Expectation 我們可以知道，

                   20
通關人數的期望值 = Σ P(第 i 位選手安穩地站在第18塊上)
                   i=1

讓隨機變數 X_i 代表第i位選手最終所能安穩站的玻璃
我舉幾個例子方便大家理解：
        X_1 = 0 的意思是第1位選手死在第1塊玻璃上
        X_1 = 2 的意思是第1位選手死在第3塊玻璃上
        X_3 = 4 的意思是第3位選手死在第5塊玻璃上
        X_5 = 18的意思是第5位選手成功地站在第18塊玻璃上

                       20
所以通關人數期望值就是 Σ P(X_i=18)
                       i=1

怎麼算這些 P(X_i=x) 呢？


P(X_1=x) = (1/2)^(x+1)      , 0<=x<=17
            1/2^18          , x =18
              0             ,otherwise

幸運的是 X_1,X_2, ... 有 Markovianity，所以可以用下面這方式算出來：


         P(X_i=x) = Σ P(X_{i-1}=y)P( X_i=x | X_{i-1}=y)
                   0<=y<=18

對於 i>=2, 我們有

(i) y <= 17
Pr( X_i=x | X_{i-1} = y) =  (1/2)^(x-y)              , y+1<=x<=17
                            (1/2)^(17-y)             , x = 18
                                0                    , otherwise

(ii) y = 18
Pr( X_i=x | X_{i-1} = y) = 1    , x= 18
                           0    , otherwise

我用程式算出來是 11 。



實際上，這其實只要算到第18個人就可以了。
因為第19跟第20個人從前面的人的結果絕對可以安全通過。

然後我通過計算發現看起來有下面這個情況
        for 1<=i<=18 ,    P(X_i=18) + P(X_{19-i}=18) = 1


弄得更General一點，如果總共有 n 塊玻璃要通過，
for 1<=i<=n,   P(X_i=n) + P(X_{n+1-i}=n) = 1

如果上面那個猜想是對的，那應該有個不錯的解讀方式可以省下這些計算
這就交給大家想了

--
因為有大家的支持，才有角卷綿芽的Sololive
https://i.imgur.com/CbO6fr2.jpg
直到台灣時間 2021/11/12 (星期五) 下午 9:59 為止都可以在SPWN觀看喔！
SPWN連結：https://spwn.jp/events/21101201-jpwatame

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 98.45.135.233 (美國)
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1634872344.A.D16.html
推 fragmentwing: 推公布程式算 良心碼農
推 ntpuisbest  : 拜讀一下，感恩
推 llrabel     : 讚讚 跟我設的隨機變數一樣
→ llrabel     : 不過原文下已經有人給出另一個「不錯的解讀方式」
→ llrabel     : 改成用第 i 塊玻璃有沒有死人設隨機變數 Y_i
→ llrabel     : Y_i = 1 表示有死, Y_i = 0 表示沒有 秒殺
你們有誰方便寫一篇用這方式的分析嗎？XD

然後我 Python的程式碼放在這邊，有興趣的可以看看

M = 18      # 玻璃數量
T = 20      # 參加者人數

# 玻璃的數量和參加者人數也可以改成其他的數字

dp = [[0]*(M+1) for _ in range(T+1)]        # dp[i][x] = P(X_i=x)

for x in range(M):
    dp[1][x] = 0.5**(x+1)
dp[1][M] = 0.5**M

for t in range(2,T+1):
    #calculating dp[t][.]

    # dp[t][M]
    for y in range(0,M):
        dp[t][M] += 0.5**(M-1-y)*dp[t-1][y]
    dp[t][M] += dp[t-1][M]

    for x in range(0,M):
        for y in range(0,x):
            dp[t][x] += 0.5**(x-y)*dp[t-1][y]

result = 0

for t in range(1,T+1):
    result+=dp[t][M]

print(result)
推 fragmentwing: 你文章死在玻璃上的舉例中間兩個是不是打錯啦
是第一個打錯XD
※ 編輯: arrenwu (98.45.135.233 美國), 10/22/2021 14:09:31
→ fragmentwing: 原來如此 看懂了 很像國小的以上超過陷阱題XD