看比特币白皮书看到的一个比较有意思的概率问题,比特币白皮书上的问题和这个类似,讨论的是比特币的安全性,回滚攻击的概率。
庄家有n个筹码,每次有概率p赢得一个筹码,或者概率q(q=1-p)输掉一个筹码。庄家输掉所有钱后,即终止游戏。假设各次赌博都是独立的,求庄家把所有筹码输光的概率。
设概率为f(n)
,显然我们有f(0) = 1
和 f(+\infty) = 0
,又根据题意和全概率公式,我们有如下递推方程
\begin{alignedat}{1}
f(n) &= pf(n+1) + qf(n-1)
\end{alignedat}
所以,特征方程为
x = px^2 + q
解得
\begin{alignedat}{1}
x &= \frac{1\pm\sqrt{1-4pq}}{2p}
\end{alignedat}
注意到q=1-p
\begin{alignedat}{1}
x &= \frac{1\pm\sqrt{(2p-1)^2}}{2p}
\end{alignedat}
考虑p>0.5
时x_1=1,x_2=(1-p)/p
,此时
\begin{alignedat}{1}
f(n) = A + B(\frac{1-p}{p})^n
\end{alignedat}
注意到p>0.5
\displaystyle\lim_{n \to +\infty}(\frac{1-p}{p})^n = 0
代入f(0) = 1
和 f(+\infty) = 0
,我们立刻就能得到A=0,B=1
\begin{alignedat}{1}
f(n) = (\frac{1-p}{p})^n
\end{alignedat}
另一方面,p \le 0.5
时,x_1=1,x_2=(1-p)/p
(因为不影响结果,两个解交换了顺序),我们惊奇的发现,两组情况下的解竟然如此一致
\begin{alignedat}{1}
f(n) = A + B(\frac{1-p}{p})^n
\end{alignedat}
此时我们只需注意
\displaystyle\lim_{n \to +\infty}(\frac{1-p}{p})^n = +\infty
代入f(0) = 1
和 f(+\infty) = 0
,就能得到A=1,B=0
\begin{alignedat}{1}
f(n) = 1
\end{alignedat}
因此
\begin{alignedat}{2}
f(n) &= (q/p)^n ,\ \ &p>0.5\\
f(n) &= 1,\ &p \le 0.5
\end{alignedat}
对此我又进一步的做了概率分析,输入的参数要在0.5~1之间,发现庄家基本不会输。
You always said the cards would never do you wrong; The trick you said was never play the game too long.——Bob Seger
赌徒进去赌场后,在有钱的庄家面前,玩着不超过50%胜率的游戏,赢钱就只是一个美丽的泡沫。
关于这个问题也很多种解法,这里有一个构造差分方程解的,当然还有一个更为详细的分析。但是我觉得使用特征方程来解才是计算机专业学生的一般做法。