連續(xù)N次十連抽卡中，存在連續(xù)至少M(fèi)(M≤N)次十連都不出最高稀有度卡的概率

2022-11-20 21:17 作者:涼風(fēng)_青葉 0人讀過 | 我要投稿

問題描述

????????考慮這一種抽卡系統(tǒng)：每進(jìn)行一次叫做“十連抽卡”（也可能是十一連，不過后面統(tǒng)稱為“十連”）的操作，就有 $1-p(0%3Cp%3C1)$ 的概率抽出“最高稀有度的卡”（具體到某種抽卡系統(tǒng)中，它可能被叫做“UR卡”“SSR式神”“四星卡”“五星從者”“六星干員”等等），當(dāng)然，也就有 $p(0%3Cp%3C1)$ 的概率抽不出“最高稀有度的卡”。

????????現(xiàn)在在這個(gè)系統(tǒng)中抽卡 $N$ （ $N$ 是正整數(shù)）次，考慮這樣的一個(gè)事件：在這連續(xù)的 $N$ 次抽卡中，存在連續(xù)的至少 $M$ （ $M%5Cleq%20N$ ，并且 $M$ 也是正整數(shù)）次“十連抽卡”（比如說，這 $N$ 次抽卡中的第4,5,6,7,…,M+3次抽卡），使得這 $M$ 次抽卡都沒有抽出“最高稀有度的卡”，或者在下文中簡(jiǎn)稱，沒有“出貨”。

????????本文給出了該問題以矩陣形式表示的解，并給出了部分具體問題中，該問題的數(shù)值解。

求解過程

1.“沒出十連次數(shù)計(jì)數(shù)器”

????????在進(jìn)行這 $N$ 次“十連抽卡”的過程中，假想我們?cè)谕瑫r(shí)操作一個(gè)“沒出十連次數(shù)計(jì)數(shù)器”（后簡(jiǎn)稱“計(jì)數(shù)器”）。計(jì)數(shù)器在這 $N$ 次“十連抽卡”開始前的初始值為 $0$ ，隨后每抽一次十連，如果沒出最高稀有度的卡，就把計(jì)數(shù)器的值 $%2B1$ ；如果出了最高稀有度的卡，就把計(jì)數(shù)器的值重置為 $0$ 。以一次 $N%3D10$ 的抽卡為例：

????????這個(gè)計(jì)數(shù)器將幫助我們統(tǒng)計(jì)“最多有連續(xù)幾次十連沒出貨”，在這個(gè)問題中，我們只關(guān)心計(jì)數(shù)器曾到達(dá)過的最大值是多少。原題所要求的是“存在連續(xù)至少 $M$ 次十連不出貨的概率”，其實(shí)也就等價(jià)于，“計(jì)數(shù)器曾到達(dá)過的某個(gè)值≥M的概率”。

2.定義關(guān)于計(jì)數(shù)器的數(shù)列{Mn}，考察Mn隨n的變化規(guī)律

????????接下來我們定義數(shù)列 $%5C%7Bc_n%5C%7D$ 為抽卡次數(shù)為 $n(0%5Cleq%20n%5Cleq%20N)$ 時(shí)，計(jì)數(shù)器所顯示的數(shù)字；由遞推關(guān)系再定義一關(guān)于 $c_n$ 的數(shù)列：

$M_n%3D%5Cleft%5C%7B%5Cbegin%7Balign%7D%26M%2CM_%7Bn-1%7D%3DM%5C%5C%26c_n%2Celse%5Cend%7Balign%7D%5Cright.$

????????原題要求“計(jì)數(shù)器曾到達(dá)過的某個(gè)值≥M的概率”，也就等價(jià)于“ $M_N%3DM$ 的概率”。因?yàn)楫?dāng) $%5Cexists%20n%2Cc_n%5Cgeq%20M$ 時(shí)，就意味著 $%5Cexists%20n'%5Cleq%20n%2Cc_%7Bn'%7D%3DM%2Cc_%7Bn'-1%7D%3DM-1$ ，于是 $M_%7Bn'%7D%3DM%5Cimplies%20%5Cforall%20i%5Cgeq%20n'%2CM_i%3DM%5Cimplies%20M_N%3DM$ 。反過來，如果已知 $M_N%3DM$ ，則必然 $%5Cexists%20n%5Cleq%20N%2Cs.t.%20%20M_%7Bn-1%7D%3DM-1%2CM_n%3DM$ ，于是 $c_n%3DM%5Cgeq%20M$ 。兩個(gè)條件可以相互推出，因此相互等價(jià)。

????????現(xiàn)來考慮 $P(M_%7Bn%2B1%7D%3Di%7CM_n%3Dj)$ 的值，即在已知 $M_n%3Dj$ 的情況下，式 $M_%7Bn%2B1%7D%3Di$ 成立的概率。我們將分 $j%3DM$ 與 $j%3CM$ 兩種情況來討論。

????????當(dāng) $j%3DM$ 時(shí)，顯然有：

$%20P(M_%7Bn%2B1%7D%3Di%7CM_n%3Dj)%3D%5Cleft%5C%7B%5Cbegin%7Balign%7D1%2Ci%3DM%5C%5C0%2Ci%5Cneq%20M%5Cend%7Balign%7D%5Cright.$

????????當(dāng) $j%3CM$ 時(shí)，由 $M_n%5Cneq%20M$ 容易推出 $M_0%2CM_1%2C%E2%80%A6%2CM_%7Bn-1%7D%5Cneq%20M$ ，因此 $M_i%3Dc_i%2Ci%3D0%2C1%2C2%2C%E2%80%A6%2Cn$ 。又因?yàn)?img type="latex" class="latex" src="http://api.bilibili.com/x/web-frontend/mathjax/tex?formula=M_n%5Cneq%20M%5Cimplies%20M_%7Bn%2B1%7D%3Dc_%7Bn%2B1%7D" alt="M_n%5Cneq%20M%5Cimplies%20M_%7Bn%2B1%7D%3Dc_%7Bn%2B1%7D">（否則 $M_%7Bn%2B1%7D%5Cneq%20c_%7Bn%2B1%7D%5Cimplies%20M_%7Bn%2B1%7D%3DM%2C%20c_%7Bn%2B1%7D%5Cneq%20M$ ，由 $M_n%5Cneq%20M$ 知 $M_n%3Dc_n%3DM-1$ ，故 $c_%7Bn%2B1%7D$ 不能為 $M$ 只能為 $0$ ，又與 $M_%7Bn%2B1%7D%3DM$ 矛盾），所以：

$P(M_%7Bn%2B1%7D%3Di%7CM_n%3Dj)%3DP(c_%7Bn%2B1%7D%3Di%7Cc_n%3Dj)%3D%5Cleft%5C%7B%5Cbegin%7Balign%7Dp%2C%5C%20%26i%3Dj%2B1%5C%5C1-p%2C%5C%20%26i%3D0%5C%5C0%2C%5C%20%26else%5Cend%7Balign%7D%5Cright.$

3.狀態(tài)，概率分布與轉(zhuǎn)移矩陣

????????我們知道 $M_n$ 只能在 $%5C%7B0%2C1%2C2%2C%E2%80%A6%2CM-1%2CM%5C%7D$ 共 $M%2B1$ 個(gè)正整數(shù)中取值。我們把這些值叫做 $M_n$ 所處的狀態(tài)。

????????對(duì)于值 $M_n$ ，我們定義一個(gè) $M%2B1$ 維的向量 $p_n%3D(p_%7Bn0%7D%2Cp_%7Bn1%7D%2Cp_%7Bn2%7D%2C%E2%80%A6%2Cp_%7BnM%7D)$ ，稱作 $M_n$ 的概率分布，其中 $p_%7Bni%7D(i%3D0%2C1%2C2%2C%E2%80%A6%2CM)$ 是 $M_n$ 的值取 $i$ 的概率大小。自然， $p_0%3D(1%2C0%2C0%2C%E2%80%A6%2C0)$ （有 $M$ 個(gè) $0$ ）。

????????再定義 $(M%2B1)$ 行 $(M%2B1)$ 列的， $M_n$ 的轉(zhuǎn)移矩陣如下：

$P%3D%5Cleft(%5Cbegin%7Balign%7D%0A1-p%20%26%26%20p%20%26%26%200%20%20%26%26%20%E2%80%A6%20%26%26%200%20%26%26%200%5C%5C%0A1-p%20%26%26%200%20%26%26%20p%20%26%26%20%E2%80%A6%20%26%26%200%20%26%26%200%5C%5C%0A%E2%80%A6%20%26%26%20%E2%80%A6%20%26%26%20%E2%80%A6%20%26%26%20%E2%80%A6%20%26%26%20%E2%80%A6%20%26%26%20%E2%80%A6%5C%5C%0A1-p%20%26%26%200%20%26%26%200%20%26%26%20%E2%80%A6%20%26%26%200%20%26%26%20p%5C%5C%0A0%20%26%26%200%20%26%26%200%20%26%26%20%E2%80%A6%20%26%26%200%20%26%26%201%0A%5Cend%7Balign%7D%5Cright)$

????????位于這個(gè)矩陣的第 $j%2B1$ 行第 $i%2B1$ 列的元素的值，就是 $P(M_%7Bn%2B1%7D%3Di%7CM_n%3Dj)$ 的值。

????????因此我們有遞推關(guān)系： $p_%7Bn%2B1%7D%3Dp_nP$ 。該問題的答案即

$p_n%3Dp_0P%5EN$

的最后一個(gè)元素的值，或者說，位于矩陣 $P%5EN$ 最右上角的值。問題到此解決。很遺憾，這個(gè)問題的答案并不能用簡(jiǎn)單的公式表示，大多數(shù)時(shí)候也不能手算。

實(shí)際情景

1.公式驗(yàn)證

????????我們首先用一個(gè)簡(jiǎn)單的情形驗(yàn)證答案的正確性。連拋5次正面朝上概率為二分之一的硬幣，則結(jié)果中存在連續(xù)至少兩次正面朝上的概率是多少？

????????這個(gè)問題可以手算。連拋5次硬幣，共有 $2%5E5%3D32$ 種可能的結(jié)果。反面朝上次數(shù)為0或1時(shí)，結(jié)果一定符合題意（證略）。反面朝上次數(shù)為2時(shí)，有且僅有“正反正反正” $1$ 種結(jié)果不合題意。反面朝上次數(shù)為3時(shí)，有“正反正反反”“正反反正反”“正反反反正”“反正反正反”“反正反反正”“反反正反正”共 $6$ 種結(jié)果不合題意。反面朝上次數(shù)為4或5時(shí)，結(jié)果一定不合題意，其中，反面朝上次數(shù)為4的結(jié)果有 $5$ 種，朝上次數(shù)為5的結(jié)果有 $1$ 種。因此，問題的答案是：

$1-%5Cfrac%7B1%2B6%2B5%2B1%7D%7B32%7D%3D%5Cfrac%7B19%7D%7B32%7D$

????????再用本文提到的方法計(jì)算。把“硬幣正面朝上”看作是“沒出貨”，取:

$p%3D%5Cfrac%7B1%7D%7B2%7D%2CN%3D5%2CM%3D2$

則 $P%3D%5Cleft(%5Cbegin%7Balign%7D%0A0.5%20%26%26%200.5%20%26%26%200%5C%5C%0A0.5%20%26%26%200%20%26%26%200.5%5C%5C%0A0%20%26%26%200%20%26%26%201%0A%5Cend%7Balign%7D%5Cright)$ ，由此可得：

$P%5EN%3D%5Cleft(%5Cbegin%7Balign%7D%0A%5Cfrac%7B1%7D%7B4%7D%20%26%26%20%5Cfrac%7B5%7D%7B32%7D%20%26%26%20%5Cfrac%7B19%7D%7B32%7D%5C%5C%0A%5Cfrac%7B5%7D%7B32%7D%20%26%26%20%5Cfrac%7B3%7D%7B32%7D%20%26%26%20%5Cfrac%7B3%7D%7B4%7D%5C%5C%0A0%20%26%26%200%20%26%26%201%0A%5Cend%7Balign%7D%5Cright)$

????????該矩陣最右上角的值正是 $%5Cfrac%7B19%7D%7B32%7D$ ，與我們手算得到的答案一致，因此這個(gè)計(jì)算方法是正確無誤的。

2.程序編寫

????????由于計(jì)算過于復(fù)雜，我們首先編寫一段Python程序替代人工進(jìn)行計(jì)算并輸出結(jié)果。程序中N、M、p的含義都與上文相同。

????????通過以下代碼，再次計(jì)算前文提到的拋硬幣問題：

????????得到輸出：

????????0.59375就是 $%5Cfrac%7B19%7D%7B32%7D$ 的小數(shù)形式，可見該程序工作正常。

3.投入實(shí)戰(zhàn)

????????對(duì)于“連續(xù)不出貨問題”，現(xiàn)在不但有了經(jīng)驗(yàn)證的理論，還根據(jù)理論編寫好了程序。萬(wàn)事俱備，現(xiàn)在我們可以嘗試解決一些真實(shí)的抽卡問題了。當(dāng)然，這里假設(shè)所有游戲的抽卡系統(tǒng)都乖乖采用了宇宙無敵真隨機(jī)算法來決定抽卡結(jié)果，至少，也得看起來像是獨(dú)立事件。

3.1? 在《陰陽(yáng)師》中，從零開始用10000張藍(lán)票達(dá)成大陰陽(yáng)師成就的概率

????????《陰陽(yáng)師》中最高的稀有度為SSR。根據(jù)已知信息：大陰陽(yáng)師成就需要連續(xù)500次藍(lán)票抽卡不出SSR，而《陰陽(yáng)師》每次藍(lán)票抽卡抽出SSR的概率是1%，即不出貨的幾率為0.99。

????????根據(jù)題目條件，編寫并運(yùn)行如下代碼：

????????輸出結(jié)果為：

????????即，能用10000張藍(lán)票從零開始達(dá)成大陰陽(yáng)師成就的概率，大概是47.9%。另外，如果藍(lán)票數(shù)量縮減到5000，2000，1000張，則達(dá)成概率會(huì)分別縮減到約26.8%，10.3%，3.9%。約35K張藍(lán)票可以保證90%以上的達(dá)成率。

????????盡管問題的答案是一個(gè)定值（甚至可以確定是一個(gè)有理數(shù)），但依靠程序求出其準(zhǔn)確值實(shí)在是很困難，只好求其近似值。好在近似值也大概夠用。

3.2? 在《BanG Dream!》《世界計(jì)劃》等游戲中，如果連續(xù)抽十連20次，那么出現(xiàn)連續(xù)幾次以內(nèi)的“不出彩”是正常的？

????????《BanG Dream！》和《世界計(jì)劃》本來是兩款完全不同的游戲，但正好兩款游戲的最高稀有度都是4星（彩色），且單抽出彩色的概率都恰好是3%（Fes活動(dòng)期間可以是6%），所以放在一起討論。

????????首先考慮任意一次十連不出彩的可能性。一次十連抽出的每一張卡是不是彩色，都是獨(dú)立事件，因此十連不出彩的可能性是 $(1-3%5C%25)%5E%7B10%7D%5Capprox%2073.7%5C%25$ ，或者在Fes活動(dòng)期間為 $(1-6%5C%25)%5E%7B10%7D%3D53.9%5C%25$ 。