当前位置：首页 > news >正文

离散数学---随机漫步

news 来源：原创 2025/6/18 15:48:24

本文根据 MIT 计算机科学离散数学课程整理（Lecture 25）。

赌徒破产问题（Gambler's Ruin）

问题描述

初始为 n 元，对于每一次独立的赌注，都有 p 的概率赢得 1 元，(1-p) 的概率输掉 1 元。当输完 n 元或赢得 m 元（总资产 m+n 元）结束赌注。当 $0 < p \le \frac{1}{2}$ ，求玩家赢得 m 元的概率和玩家输掉 n 元期望赌注次数。

引理

解决问题之前先补充关于一般齐次线性递归式和一般非齐次线性递归式的解法，离散的情况和连续的情况类似，可以类比高等数学中的常系数齐次线性微分方程。

一般齐次线性递归式

若函数 $f(n)$ 满足递推式： $f(n)=\sum_{i=1}^{d} a_if(n-i)$

且有 d-1 个边界条件： $f(i)=b_i \,for \,\, 0 \le i < d$

令 $f(n)=\alpha^n$ ，代入得特征方程 $\alpha^d-a_1\alpha ^{d-1}-...- a_d =0$ ，解得 $\alpha_1 ,\alpha_2 , ... , \alpha_d$

如果结果没有重根，则有 $f(n)=\sum_{i=1}^{d} c_i\alpha_i^n$ ，代入边界条件即可求得 $c_i$ ；如果某一个 $\alpha$ 解为 r 重根，则 $\alpha^n ,n\alpha^n , n^2\alpha^n , ... , n^{r-1}\alpha^n$ 都是线性解， $f(n)$ 需要写成这些解的线性和。

例如得到特征方程的解为：1,2,2,2,3,4，其中 2 为 3 重根，通解就是 $f(n)=c_1\cdot 1^n+c_2\cdot 2^n+c_3\cdot n\cdot 2^n+c_4\cdot n^2\cdot 2^n+c_5\cdot 3^n+c_6\cdot4^n$

一般非齐次线性递归式

若函数 $f(n)$ 满足递推式： $f(n)-\sum_{i=1}^{d} a_if(n-i)=g(n)$

先按照齐次线性递归式的方法求出 $f(n)-\sum_{i=1}^{d} a_if(n-i)=0$ 时的通解，在求出满足非齐次方程的一个特解。非齐次方程的通解是齐次方程的通解加上特解。

Solution

用 W 表示事件：在 n 使用完之前赢得 m 。

D 表示初始美元的值。 $x_n$ 表示在初始为 n 的情况下最终赢得 m 的概率。

则有： $x_n=P(W|D=n)$

可以求得 $x_i$ 有如下递推式：

$x_i=\left\{\begin{matrix} 0 & ,i=0 \\ 1 & ,i=n+m \\ p\cdot x_{i+1}+(1-p)\cdot x_{i-1} & , 0< i< n+m \end{matrix}\right.$

类似于动态规划中划分状态的思路： $x_i$ 可以分为第一次赌注成功的情况和失败的情况，成功的情况赢得 1 元，转换到状态 $x_{i+1}$ ，失败就转换到状态 $x_{i-1}$ 。

严格推理证明如下：

用事件 A 表示赢得第一次赌注。

$x_i=P(W|D=i)=p(W\bigwedge A|D=i)+P(W\bigwedge \neg A|D=i) \\ =P(A|D=i) \cdot P(W|A\bigwedge D=i)+P(\neg A|D=i) \cdot P(W|\neg A\bigwedge D=i)\\ =p\cdot x_{i+1} + (1-p) \cdot x_{i-1}$

用 S 表示玩家直到输掉 n 元的赌注次数， $E_n$ 表示输掉 n 元期望赌注次数，即： $E_n=E(S|D=n)$

同理， $E_n$ 可以分为第一次赌注成功的情况和失败的情况，成功的情况转换到状态 $E_{i+1}$ ，失败就转换到状态 $E_{i-1}$ ，则有下面递推式：

$E_i=\left\{\begin{matrix} 0 & ,i=0 \bigvee i=n+m \\ 1+p\cdot E_{i+1}+(1-p)\cdot E_{i-1} & , 0< i< n+m \end{matrix}\right.$

$x_i$ 递推式满足一般齐次线性递归式， $E_i$ 递推式满足一般非齐次线性递归式，均可以转换为先求齐次方程通解，特征方程为： $r^2\cdot p-r+1-p=0$

解得： $r_1=\frac{1-p}{p},r2=1$

公平游戏

先考虑 $p=\frac{1}{2}$ ，即完全公平游戏的情况，此时解为 2 重根 $r_1=r_2=1$ 。

先求齐次方程 $x_n$ 通解为： $x_n=(c_1\cdot n+c_2)\cdot 1^n$ ，代入 $x_0=0,x_{n+m}=1$ 解得， $c_1=\frac{1}{n+m},c_2=0$

故： $x_n=\frac{n}{m+n}$

齐次方程 $E_n$ 表示为齐次方程通解加上特解：

$E_n=c_1\cdot n+c_2+E^*_n$

令特解为： $E^{*}_n=a\cdot n^2+b\cdot n +c$ ，代入递推式得到 $a=-1,b=c=0$

$E_n=c_1\cdot n+c_2-n^2$

代入边界条件求得结果为：

$E_n=n\cdot m$

从结果来看，公平游戏赢得游戏概率于 m 和 n 有关，对于在高赌注少收益的情况概率高，例如 n=1000,m=100 的情况赢得游戏概率高达 $\frac{10}{11}$ 。对于 m 很大的情况，虽然根据推理出的输掉的期望步数很大，然而可以证明如果一直玩下去，输掉 n 赌注的概率为 1。

从极限的角度考虑， $m\to \infty , x_n \to 0$

课程中给出关于公平游戏一定会输掉赌注的证明如下：

反证法，假设 $\exists n,\xi >0$ ，使得 $P(\text{go broke}) \le 1- \xi$

则有： $\forall m ,1-x_n \le 1- \xi$

$\forall m ,\frac{m}{m+n} \le 1- \xi$

$\forall m ,m \le \frac{1-\xi}{\xi} \cdot n$ ，推出了矛盾式。

非公平游戏

对于不公平游戏， $p<\frac{1}{2}$ ， $r_1>1$ ，解为两个不同的根。

先求齐次方程 $x_n$ ，通解表示为：

$x_n=c_1\cdot (\frac{1-p}{p})^n+c_2$

$x_0=0,x_{n+m}=1 \to c_1=\frac{1}{(\frac{1-p}{p})^{n+m}-1},c_2=\frac{-1}{(\frac{1-p}{p})^{n+m}-1}$

代入得到： $x_n=\frac{(\frac{1-p}{p})^n-1}{(\frac{1-p}{p})^{n+m}-1}$

非齐次方程 $E_n$ 表示为：

$E_n=c_1\cdot (\frac{1-p}{p})^n+c_2+E^*_n$

令特解为： $E^{*}_n=a\cdot n+b$ ，代入递推式得到 $a=\frac{1}{1-2p},b=0$

$E_0=0,E_{n+m}=0$ 代入求得 $c_1,c_2$ ，最后得到结果：

$E_n=\frac{n}{1-2p} -\frac{n+m}{1-2p} \cdot\frac{(\frac{1-p}{p})^n-1}{(\frac{1-p}{p})^{n+m}-1}$

可以看到，非公平游戏赢得游戏概率于收到 m 的指数级别的影响，会比公平游戏小得多。这里可以放缩分析：由于 $\frac{1-p}{p}>1$ ，故 $x_n \le \frac{(\frac{1-p}{p})^n}{(\frac{1-p}{p})^T}=(\frac{p}{1-p})^m$ 。假设 $p=\frac{9}{19}$ ，n=1000,m=100 的情况赢得游戏概率比 $\frac{1}{37648}$ 还小，该数据代入期望步数结果约为 18999.44。实际上，对于不公平游戏赌注较大时，期望输掉游戏结果主要取决于 n ，即： $m\to \infty , E_n \to \frac{n}{1-2p}$

赌徒破产问题中的随机漫步

下面写一个针对赌徒破产问题的脚本：

#!/usr/bin/env python3
from argparse import ArgumentParser
import numpy as np
import matplotlib.pyplot as plt
def SetParser():parser=ArgumentParser(prog="Gambler's Ruin.",description="Simulation of Gambler's Ruin.")parser.add_argument("-n","--N",default=0,help="Initial bet in dollars.",type=int)parser.add_argument("-m","--M",default=0,help="Desired winnings from the bet in dollars.",type=int)parser.add_argument("-s","--maxsteps",default=100000,help="Maximum number of bets.",type=int)parser.add_argument("-p","--prob",default=0.5,help="The probability to win the game",type=float)return parser.parse_args()
def check_args(args):if args.N<0:raise ValueError("Initial bet (-n/--N) must be a non-negative integer.")if args.M<0:raise ValueError("Desired winnings (-m/--M) must be a non-negative integer.")if args.maxsteps<0:raise ValueError("Maximum number of bets (-s/--maxsteps) must be a non-negative integer.")if not (0<args.prob<=0.5):raise ValueError("Probability (-p/--prob) must be a float between 0 and 0.5 (exclusive).")
class Gambler_Ruin:def __init__(self,n,m,s,p):self.n=nself.m=mself.s=sself.p=pdef Simulate_process(self):val=self.nY=[self.n]for i in range(self.s):if val<=0 or val>=self.n+self.m: breakif np.random.rand()<self.p: val+=1else: val-=1Y.append(val)return Ydef Plot(self,Y):plt.figure(figsize=(10,6))plt.plot(range(len(Y)),Y,label="dollars over time")plt.axhline(self.n, color='blue',linestyle='--',label="Initial bet (n)")plt.axhline(self.n+self.m,color='green',linestyle='--',label="Desired winnings (n+m)")plt.axhline(0,color='red',linestyle='--',label="Bankruptcy")if self.p!=0.5:y_drift=[-(1-2*self.p)*x+self.n for x in range(len(Y))]plt.plot(y_drift,label="Drift",color="orange",linestyle="--")plt.title(f"Gambler's Ruin for n={self.n},m={self.m},p={self.p}")plt.xlabel("number of bets")plt.ylabel("dollars")plt.legend()plt.grid(True)plt.show()plt.annotate(f"End Value: {Y[-1]}",xy=(len(Y)-1,Y[-1]),xytext=(len(Y)-1,Y[-1]+5),arrowprops=dict(facecolor='black',arrowstyle='->'))if __name__ == '__main__':try:args=SetParser()check_args(args)except ValueError as e:print(f"Error: {e}")exit(1)except SystemExit:print("Invalid input. Use '--help' for usage instructions.")exit(1)try:g=Gambler_Ruin(args.N,args.M,args.maxsteps,args.prob)Y=g.Simulate_process()g.Plot(Y)except Exception as e:print(f"Error: {e}")exit(1)

编写脚本命名为 gambler_ruin.py，添加可执行权限即可。

vi gambler_ruin.py
chmod +x gambler_ruin.py

分别模拟不同的情况：

python gambler_ruin.py -n 1000 -m 100 -s 10000000 -p 0.5
python gambler_ruin.py -n 2000 -m 1000 -s 10000000 -p 0.5
python gambler_ruin.py -n 1000 -m 100 -s 10000000 -p 0.45
python gambler_ruin.py -n 2000 -m 1000 -s 10000000 -p 0.45