Re: [機統] 定額下注的賠光機率

看板Math作者Desperato (Farewell)時間5年前 (2019/01/03 11:05)推噓4(4推 0噓 2→)

留言6則, 5人參與討論串2/3 (看更多)

※ 引述《leondemon (狗狗)》之銘言： : 有一個賭盤，勝率是53%，贏的話1賠2；負率為 47%，輸的話賠光。 : 理論上，每次賭局的獲利期望值是 53%*2 + 47%*0 = 106% (也就是獲利 6%) : 只要本金充足，那賭無限次後，是贏錢的。 : 但今天這個賭局只有本金 100 元，且每次下注只能固定下 6 元，並只賭 100 次。 : 且100次中，保證53次贏，47次輸，只是輸贏次序是隨機的。 : 理論上的期望獲益，應該是 6元 * 6%收益 * 100次 = 36 元。 : 但是上面卻忽略了因爲連續輸而導致本金輸光的可能性。 : 因爲一旦在賭局中途發生「輸出現次數比贏出現次數多 16 次」， : 就會發生賭本不足而無法完成剩下賭盤 (只剩4元)。 : 那問題來了，在100局保證輸贏次數情況下 (就當做是100格紙板戳戳樂、不重複取樣)， : 1) 在勝率 53% 下，有多少機率在100次賭局完成前，就輸光本金？ : 2) 假設賭局獲勝機率改為 60%，那有多少機率會輸光本金？ : 在不保證實際輸贏比的情況下 (重複取樣) : 3) 如果是無限次賭局 (勝率 60%)，有多少機會在賭金累積到 600 前，輸光本金？ : 4) 若是賭無限次 (勝率 60%)，不管賭金累積到多少都繼續賭，有多少機會賠光本金？ : 求解答 p.s. 文長 Catalan's trapezoids 雖然是叫梯形，不過我喜歡叫三角形而且英文wiki也是標題 Catalan's triangle A. 定義首先 Catalan's triangle C(n, k) 表示有 n 個 X 和 k 個 Y 的字串數量，且 Y 數量不超過 X Catalan's triangle 可以由作圖得到先示範一次 Pascal's triangle 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 4 1 基本上 Catalan's triangle 就是加了一條不能越過的柵欄因此圖形就變成了 1 | 1 | 1 1 | 1 2 | 1 3 2 | 1 4 5 | 然後將 ↘ 方向視為一列(同一個 n) 就會得到 Catalan's triangle Catalan's number 是正中間的垂直行 C_n = C(n, n) 現在 Catalan's trapezoids 就只是那條柵欄往右挪 C_m(n, k) 表示有 n 個 X 和 k 個 Y 的字串數量且 Y 數量不能比 X 多 m 個或更多顯然 m = 1 的時候 C_1(n, k) = C(n, k) 以下示範一次 m = 3 的樣子 1 | 1 1 | 1 2 1 | 1 3 3 | 1 4 6 3 | 1 5 10 9 | 左邊(具體來說是 ↙ 方向的三行)會跟原本的 Pascal's triangle 一樣其他地方顯然就被 truncate 掉了由於要計算，以下列出公式但不證明 binom(n, k) 表示二項式係數，(1+x)^n 中 x^k 的係數 C_m(n, k) | = binom(n+k, k) 0 <= k < m | | = binom(n+k, k) - binom(n+k, k-m) m <= k < n+m | | = 0 n+m <= k B. 計算現在本金 100 元，賭金 6 元贏了 X 場每場 +6 元，輸了 Y 場每場 -6 元在 Y = X+16 的時候，會輸到只剩 4 塊錢而無法繼續遊戲代表這時候已經超出線外了，因此可以取 m = 16 以下不考慮簡易算法，只會直接暴力炸開，讚嘆wolframalpha 1) 勝率 53%，100格戳戳樂，有多少機率在戳完之前就輸光了 (已訂正感謝ownlai板友) 即考慮 53 個 X 和 47 個 Y 排列每個 X 和 Y 算作不同，比較不容易搞錯每個字串有 100 個字元，擷取前任意長度的話 Y 都不能比 X 多 16 個或更多 C_16(n, n+15) 是輸光前一刻再多一個 Y 就掰了設 P(n, k) = n(n-1)(n-2)...(n-k+1) permutation 則組合數為 C_16(n, n+15) P(53, n) P(47, n+16) (84-2n)! 選 X 選 Y 包括剩下的無所謂了輸光那次由天然條件可得 n <= 53, n+16 <= 47, 84-2n >= 0 因此 n <= 31，輸光的機率為 1 31 ---- sum C_16(n, n+15) P(53, n) P(47, n+16) (84-2n)! 100! n=0 1 31 2n+15 2n+15 84-2n = ----- sum ( ( ) - ( ) ) * ( ) 100 n=0 n+15 n-1 53- n ( ) 47 ~= 0.000785711 2) 勝率 60%，100格戳戳樂，有多少機率在戳完之前就輸光了 (已訂正) (已訂正2) 上述變成 X 有 60 個，Y 有 40 個注意到 n 現在只能 <= 24，機率為 1 24 ---- sum C_16(n, n+15) P(60, n) P(40, n+16) (84-2n)! 100! n=0 1 24 2n+15 2n+15 84-2n = ----- sum ( ( ) - ( ) ) * ( ) 100 n=0 n+15 n-1 60- n ( ) 40 ~= 0.00000580349 4) 勝率 60%，隨機取樣，有多少機會賠光本金由於 3) 太麻煩先來算 4) (已訂正) 這個才是往左 p = 0.6，往右 q = 0.4 的情況 C_16(n, n+15) 是輸光前一刻再多一個就輸光了機率是 q * C_16(n, n+15) p^n q^(n+15) 因此輸光的機率為 inf sum C_16(n, n+15) p^n q^(n+16) n=0 ~= 0.00152244 具體來說就是把以下這行丟給計算機 sum_(n=0)^oo ( ( binom(2n+15, n) - binom(2n+15, n-1) ) 0.6^n 0.4^(n+16) ) C. 計算第三題 3) 勝率 60%，隨機取樣，有多少機會在賭金累積到 600 前輸光本金也就是 X = Y+84 時勝出(本金602) Y = X+16 時敗北(本金4) 這代表有左右兩條線，只要出線就出界最根本的問題是 Catalan's number 沒辦法用了WWW 姑且有一個無敵暴力的方式就是設立 (84, 83, 82, ..., -16) 一共 101 個 state 然後寫成 Markov's chain (馬可夫鏈) [ 1 p ] [ p ] T = [ q p ] [ q ... ] [ ... p ] [ q ] [ q 1 ] 為了方面計算，排成(84, -16, 83, 82, ..., -15)好了 [ 1 p ] [ 1 q ] T = [ p ] = [ I B ] [ q p ] [ O C ] [ q ... ] [ ... p ] [ q ] 其中 C 目測(欸)是 invertible 且目測(喂) lim_(n->inf) C^n = O 因此 T^n = [ I B_n ] [ O C_n ] 其中 C_n = C^n B_n = B + BC + ... + BC^(n-1) = B (I-C^n) (I-C)^(-1) 所以 T_inf = lim_(n->inf) T^n = [ I B'] [ O O ] 其中 B' = B (I-C)^(-1) 好了，現在麻煩來了，(I-C)^(-1)是三小wwwww 嘛，由於 B 很簡單，實際上只需要 (I-C)^(-1) 的幾個單項那麼先回到原題好了，如果算出 T_inf 的話取初始狀態 v_0 = (0,..., 1,..., 0)^t 因為 state 0 是第 86 個位置，所以 1 在那邊因此 T_inf v_0 就是取第 86 行出來看然後因為題目要問敗北的情況，所以會取第 2 列的值也就是說，答案是 T_inf 的第 2 列第 86 行這個位置是 B' 的第 2 列第 84 行由 B' = B (I-C)^(-1) 可知(注意 B 是有一堆 0 的 2x99 矩陣) 就是 q 乘上 (I-C)^(-1) 的第 99 列第 84 行這樣的話反矩陣公式也許會有點用處也就是說要來算 (I-C) 和相關矩陣的 det (行列式) 畢竟 (I-C) 是 99x99 的矩陣，那就令 D_99 = I - C 然後 D_n (n < 99) 就是取出左上 nxn 的矩陣，其他丟掉 [ 1 -p ] [-q 1 -p ] D_n = [ -q 1 ... ] [ ... ... ] [ ... 1 -p ] [ -q 1 ] 遞迴式 det(D_n) = det(D_(n-1)) - pq det(D_(n-2)) 初始項 det(D_1) = 1 det(D_2) = 1 - pq 特徵方程式 x^2 - x + pq = (x-p)(x-q) = 0 (p+q = 1) 因此 det(D_n) = A p^n + B q^n 代入初始項可得 A = p/(p-q), B = -q/(p-q) 得到 det(D_n) = (p^(n+1) - q^(n+1))/(p - q) (但是這個結果下面沒有用到XD) 現在回到計算 (I-C)^(-1) 的第 99 列第 84 行也就是 I-C 砍掉第 84 行和第 99 列後取行列式再加個負號除以 det(I-C) 之後的值 ...原本想這樣做的，但實際上有點麻煩=A= 後來才發覺高斯消去法可能比較快XD 總之一開始的矩陣是這個 [ 1 -p ] [-q 1 -p ] I-C = [ -q 1 ... ] [ ... ... ] [ ... 1 -p ] [ -q 1 ] 要把 I-C 變成 I 的話要進行以下步驟 (1) 對角線第一項 d_1 = 1，將第 1 列乘以 q 加到第 2 列 (2) 對角線第二項 d_2，將第 2 列乘以 q/d_2 加到第 3 列 (3) 對角線第二項 d_3，將第 3 列乘以 q/d_3 加到第 4 列 ...... (98)對角線第98項d_98，將第 98列乘以 q/d_98加到第 99列 (99)對角線第99項d_99 現在的矩陣變成了 [d_1 -p ] [ d_2 -p ] Mid = [ d_3 -p ] [ ... ] [ d_98 -p ] [ d_99 ] 其中對角線項有遞迴式 d_n = 1 - pq/d_(n-1), d_1 = 1 p^(n+1)-q^(n+1) det(D_n) 解得 d_n = --------------- = ------------ p^n - q^n det(D_(n-1)) 老實說這個遞迴式我解不出來，這是 wolframalpha 算的(跪) 繼續高斯消去法，進行以下步驟 (1) 第 99列乘以 p/d_99 加到第 98列 (2) 第 98列乘以 p/d_98 加到第 97列 ...... (98)第 2 列乘以 p/d_2 加到第 1 列最後第 n 列除以 d_n，就可以得到 I 啦因此，(I-C)^(-1) 可以透過從 I 開始，進行以上步驟得到可以輕易得到，完成第一部份之後 Mid 的第 99 列第 84 行 = (q/d_84)(q/d_85)...(q/d_98) 接著第二部分毫無影響，最後再除以 d_99 就好答案是這個數字再乘上 q，也就是說 99 1 答案 = q^16 prod --- n=84 d_n p^84 - q^84 = q^16 ------------- p^100 - q^100 ~= 0.00152243884 啊奇怪這個答案好像跟 4) 沒什麼兩樣因為大概可以猜的到，如果把左邊界改成 X = Y+N 的話 p^N - q^N 那答案九成九就會變成 q^16 ------------------- p^(N+16) - q^(N+16) 然後把 N 拉到無限大去就會變成 4) 了 q^16 從這裡也能得到 4) 的答案就是 ---- p^16 D. 結論四題的答案近似值分別為 1) ~= 0.000785711 2) ~= 0.00000580349 | 3) ~= 0.00152243884034744235876... 4) ~= 0.00152243884034744481467... | 結果花了超級多時間www 3) 實在太坑了，而且我也懶的檢查，幸好答案很合理 2) 遠比 3) 低的原因，是因為 2) 是抽選制一開始就大爆走狂抽到 Y 的機率會顯著下降是說 3) 和 4) 答案這麼乾淨，其實應該有更簡單的算法吧? 嘛管他的ow o -- 嗯嗯ow o -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.25.25 ※ 文章網址: https://www.ptt.cc/bbs/Math/M.1546484755.A.5D7.html ※ 編輯: Desperato (140.112.25.25), 01/03/2019 11:09:03

推

cutekid

01/03 11:11, 5年前 , 1^F

01/03 11:11, 1^F

啊啊啊原來如此 a_n = C + D/a_(n-1) 的題型可以設 a_n = b_n / b_(n-1) 就會得到 b_n = C b_(n-1) + D b_(n-2) 了這誰想的到啊=A=

推

leondemon

01/03 12:29, 5年前 , 2^F

01/03 12:29, 2^F

推

ownlai

01/03 14:17, 5年前 , 3^F