赌徒破产问题

2023-10-04 16:01

文章标签 问题赌徒破产

本文主要是介绍赌徒破产问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

上算法课老师讲了赌徒破产问题，回来在网上找了相关资料，感觉是个有趣的概率题，于是也写了篇作为总结。

一个赌徒开始有h枚金币，每次赢得一枚金币的概率为a，输掉一枚金币的概率为1-a，直到其所有的金币总数达到N或0则游戏结束，求赌徒最终赢得N枚金币的概率P(N|h)。

对于当前拥有金币数h，下一时刻有两种可能，即h+1和h-1。于是有

$P(N|h)=a\times P(N|h+1) +(1-a)\times P(N|h-1)$

（这个概率问题服从二项分布，准确点说是0-1分布。这个公式要注意的是概率a对应h+1，1-a对应h-1）

联系高中数学的二次递推数列，得特征方程为

$p=ap^2+1-a$

整理得

$ap^2-p+1-a=0$

解得

$p_1=1,p_2=\frac{1-a}{a}$

所以通项公式为

$P(N|h)=A\times 1^h+B\times (\frac{1-a}{a})^h$

由题意可知

$P(N|N)=1,P(N|0)=0$

带入方程解得

$P(N|h)= \left\{\begin{matrix} \frac{(\frac{1-a}{a})^h-1}{(\frac{1-a}{a})^N-1} &, a\neq \frac{1}{2}\\ \frac{h}{N}&,a=\frac{1}{2} \end{matrix}\right.$

可能从以上公式看不出明显的结果，我们将问题具体化：

一个赌徒开始有10枚金币，每次赢得一枚金币的概率为0.4，输掉一枚金币的概率为0.6，直到其所有的金币总数达到100或0则游戏结束，求赌徒最终赢得100枚金币的概率P(100|10)。

带入后计算得

$P(100|10)=1.39\times 10^{-16}$

可以看出，赌徒赢得100枚金币的概率接近于0.

从公式中我们可以看出，当赢得金币的概率小于等于1/2时，当 $N\sim +\infty$ 时， $P\sim 0$ 。特别的，对于a=0.5时，于是便有了赌徒输光定理（在“公平”的赌博中，任一个拥有有限赌本的赌徒，只要长期赌下去，必然有一天会输光）。

这篇关于赌徒破产问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！