每次隨機殺掉一個奇數位的人後的存活概率問題
600 個人站一排,每次隨機殺掉一個奇數位的人,幾號最安全?
在最前面,為了簡單,我們用一個簡記符號,其中 $ \lceil x\rceil $ 表示上取整:
$$ \tau_{x} = \lceil \frac{x}{2} \rceil $$
現在我們假設有 $n$ 個人,第 $k$ 個人存活到最後的概率為 $p(n,k)$ 。考慮第一個殺死的人的位置,很容易我們就能得到遞推式子:
$$ p(n, k) = \frac{\tau_{k-1}}{\tau_n} \times p(n-1,k-1) + \frac{\tau_n-\tau_k}{\tau_n} \times p(n-1, k)$$
到這裏之後可以用計算機程序快速算出數值結果。但這裏有個奇妙的地方在於,它的符號解也特別簡單:
$$ p(n, k) = \frac{\tau_{k-1}}{\tau_{n-1}\tau_n} $$
更直觀的看,每個人存活的概率為 0, 1, 1, 2, 2, 3, 3, 這樣一直下去,最後再標準化(使得概率總和為 1 )。結果非常優美。
很容易驗證上面的結果和遞推式。但如果不是提前知道答案,直接從上面的遞推式子很難猜到。我們可以換一種方法,注意到下面這個事實:前面的 $m$ 個人的存活(相對)概率分佈和後面有多少人沒有關係,這樣我們只用把最後一個人的存活概率算出來,然後再往前推,就可以獲得所有的存活概率。
最後一個人存活概率 $p(n) = p(n, n)$ 有一個簡單遞推式:
$$ p(2n) = p(2n-1)$$
$$p(2n+1) = \frac{n}{n+1} p(2n)$$
結合 $p(1) = p(2) = 1 $ ,很簡單就可以得出:
$$ p(n) = \frac{1}{\tau_n}$$
然後我們算倒數第二個人:
$$ p(n,n-1)=(1-p(n))\times p(n-1) = \frac{\tau_{n-2}}{\tau_{n-1}\tau_n}$$
然後有一個特別好的遞歸式:
$$ \tau_0 + \tau_2 + \cdots + \tau_{n-1} = \tau_{n-1} \tau_n$$
$$ \tau_{k-1}\tau_k + \tau_k + \tau_{k+1} + \cdots + \tau_{n-1} = \tau_{n-1} \tau_n$$
用上面式子類似地往前推,可以得出:
$$\begin{equation}\begin{split} p(n,k)&=(1-p(n,k+1)-p(n,k+2)-\cdots-p(n,n))\times p(k,k) \\ &= \frac{\tau_{n-1} \tau_n-\tau_k-\tau_{k+1}-\cdots-\tau_{n-1}}{\tau_{n-1} \tau_n} \times\frac{1}{\tau_k} \\ &= \frac{\tau_{k-1}\tau_k}{\tau_{n-1} \tau_n}\times\frac{1}{\tau_k } \\ &= \frac{\tau_{k-1}}{\tau_{n-1}\tau_n} \end{split} \end{equation}$$
Q. E. D.
「其他文章」