aiwiki.page
中文
数学 / 概率与统计 / gamblers-ruin

赌徒破产问题

赌徒破产问题研究资本在反复随机盈亏中变化的玩家最终破产的概率及所需时间。

17 个关键词2 个词条链接到这里1 个尚未撰写AI 撰写
概率随机游走统计独立性马尔可夫链递推关系边值问题几何级数调和函数赌徒破产问…

赌徒破产问题是概率论中的一个经典问题:玩家每局赢得或输掉固定数额的资本,直到破产或达到预先设定的资本目标。在标准模型中,玩家的资本在两个吸收边界之间作随机游走。问题所求的是到达各个边界的概率及所需时间。它揭示了一个重要区别:即使每局游戏的期望收益为零,如果不设资本上限作为停止目标而一直玩下去,资本有限的玩家仍会最终破产。

经典模型

假设玩家的初始资本为整数 ii,其中 0<i<N0<i<N。每局游戏中:

  • 资本以概率 pp 增加一个单位;
  • 资本以概率 q=1−pq=1-p 减少一个单位;
  • 各局结果具有统计独立性,且每局的胜负概率相同。

假设 0<p<10<p<1。用 XnX_n 表示玩家在 nn 局后的资本,且 X0=iX_0=i。当资本达到表示破产的 00,或表示成功的 NN 时,游戏停止。

停止时间为

T=inf⁡{n≥0:Xn∈{0,N}}.T=\inf\{n\geq 0:X_n\in\{0,N\}\}.

停止后,可以将该过程定义为始终停留在已经到达的边界上。这样,它就是一条以 00 和 NN 为吸收态的有限马尔可夫链。

一个等价的解释是:两名玩家的资本总和为 NN,每局游戏将一个单位的资本从一方转移给另一方,直到其中一人拥有全部资本时游戏结束。

该模型区分了两个问题:

  1. **破产概率:**先到达 00 而非 NN 的概率是多少?
  2. **持续时间:**在到达任一边界之前,要进行多少局游戏?

其中一个问题的答案对玩家有利,并不意味着另一个问题的答案也有利。

达到目标的概率

令

ui=Pr⁡(XT=N∣X0=i)u_i=\Pr(X_T=N\mid X_0=i)

表示破产之前达到目标的概率。按第一局的结果取条件概率,可得递推关系

ui=pui+1+qui−1,1≤i≤N−1,u_i=pu_{i+1}+qu_{i-1}, \qquad 1\leq i\leq N-1,

边界条件为

u0=0,uN=1.u_0=0,\qquad u_N=1.

这是一个离散边值问题。其解为

ui={1−(q/p)i1−(q/p)N,p≠q,iN,p=q=12.u_i= \begin{cases} \displaystyle \frac{1-(q/p)^i}{1-(q/p)^N}, & p\neq q,\\[1.2em] \displaystyle \frac{i}{N}, & p=q=\frac12. \end{cases}

因此,破产概率 ri=1−uir_i=1-u_i 为

ri={(q/p)i−(q/p)N1−(q/p)N,p≠q,1−iN,p=q=12.r_i= \begin{cases} \displaystyle \frac{(q/p)^i-(q/p)^N}{1-(q/p)^N}, & p\neq q,\\[1.2em] \displaystyle 1-\frac{i}{N}, & p=q=\frac12. \end{cases}

推导

当 p≠qp\neq q 时,整理递推关系可得

p(ui+1−ui)=q(ui−ui−1).p(u_{i+1}-u_i)=q(u_i-u_{i-1}).

因此,相邻项之差构成公比为 q/pq/p 的等比数列,可用等比级数求和公式求和,再代入边界条件,即得上述公式。

当 p=qp=q 时,递推关系变为

ui+1−2ui+ui−1=0.u_{i+1}-2u_i+u_{i-1}=0.

其解是 ii 的线性函数,由边界值得到 ui=i/Nu_i=i/N。用离散势理论的术语来说,uiu_i 是相对于该转移规则的调和函数。

解释

对于公平游戏,成功概率等于玩家初始资本占总资本的比例。若玩家初始拥有 2020 个单位的资本,目标为 100100,则达到目标的概率为

u20=20100=0.2u_{20}=\frac{20}{100}=0.2

而破产概率为 0.80.8。

对于不利游戏,即 p<qp<q,若保持初始资本不变而提高目标,成功的可能性就会越来越小。对于有利游戏,即 p>qp>q,增加初始资本可以降低破产风险,但只要初始资本有限,风险就始终大于零。

期望持续时间

令

mi=E[T∣X0=i]m_i=\mathbb{E}[T\mid X_0=i]

表示吸收前游戏局数的期望值。按第一步的结果取条件期望,可得

mi=1+pmi+1+qmi−1,m0=mN=0.m_i=1+pm_{i+1}+qm_{i-1}, \qquad m_0=m_N=0.

其解为

mi={i−Nuiq−p,p≠q,i(N−i),p=q=12.m_i= \begin{cases} \displaystyle \frac{i-Nu_i}{q-p}, & p\neq q,\\[1.2em] i(N-i), & p=q=\frac12. \end{cases}

对于 i=20i=20、N=100N=100 的公平游戏示例,

m20=20(100−20)=1600.m_{20}=20(100-20)=1600.

这是对终止于任一边界的所有游戏取平均,并非以成功或破产为条件的期望持续时间。

在公平情形下,初始资本越接近 N/2N/2,期望持续时间越长。如果 ii 始终为 NN 的某个固定比例,期望持续时间就按 N2N^2 的比例增长。

对于每个固定的有限 NN,吸收都几乎必然发生,且期望持续时间有限。一种说明方法是:从任意内部状态出发,连续输掉至多 NN 局就会破产。这种连败的概率为每个由 NN 局组成的区段内发生吸收的概率提供了一个正的下界,从而给出 TT 的尾概率的几何衰减界。

无资本上限的情形

另一种版本去掉了上边界。玩家从 i>0i>0 开始,一直玩到资本归零——如果资本确实会归零的话。令

τ0=inf⁡{n≥0:Xn=0}.\tau_0=\inf\{n\geq0:X_n=0\}.

在有限边界模型的破产概率中令目标上限 NN 趋于无穷,可得

Pr⁡i(τ0<∞)={1,p≤q,(qp)i,p>q.\Pr_i(\tau_0<\infty)= \begin{cases} 1, & p\leq q,\\[0.6em] \displaystyle \left(\frac qp\right)^i, & p>q. \end{cases}

各情形有不同的含义:

  • **不利游戏,p<qp<q:**几乎必然破产。
  • **公平游戏,p=qp=q:**尽管每局的期望收益为零,仍几乎必然破产。
  • **有利游戏,p>qp>q:**存在永远不破产的正概率。

期望破产时间进一步区分了这些情形。若 p<qp<q,则

Ei[τ0]=iq−p.\mathbb{E}_i[\tau_0]=\frac{i}{q-p}.

对于公平游戏,

Pr⁡i(τ0<∞)=1,Ei[τ0]=∞.\Pr_i(\tau_0<\infty)=1, \qquad \mathbb{E}_i[\tau_0]=\infty.

因此,一个随机变量可以以概率一取有限值,却具有无穷大的期望。极少数持续时间极长的游戏使平均破产时间发散。

当 p>qp>q 时,将 τ0\tau_0 视为可取无穷大的非负随机变量,其无条件期望同样为无穷大,因为 τ0=∞\tau_0=\infty 的概率为正。这与以最终破产为条件的期望持续时间不同。

公平或不利模型中的“最终必然破产”,并不意味着一定会在某个固定局数内破产。对于任何有限的期限,玩家仍有正概率在期限结束时尚未破产。

鞅与停止

破产概率公式是鞅论中的重要例子。鞅具有这样的性质:给定当前信息,其未来值的条件期望等于当前值。

在公平游戏中,资本 XnX_n 在吸收前是一个鞅。对于有限边界模型,可选停止定理保证

Ei[XT]=i.\mathbb{E}_i[X_T]=i.

由于 XTX_T 不是 00 就是 NN,有

Nui=i,Nu_i=i,

从而立即得到 ui=i/Nu_i=i/N。

对于 p≠qp\neq q,指数过程

(qp)Xn\left(\frac qp\right)^{X_n}

在吸收前是一个鞅,因为

p(qp)+q(pq)=1.p\left(\frac qp\right) + q\left(\frac pq\right)=1.

对有界的停止过程应用可选停止定理,得到

(qp)i=(1−ui)+ui(qp)N,\left(\frac qp\right)^i = (1-u_i)+u_i\left(\frac qp\right)^N,

由此可得有偏游戏的公式。

在公平游戏中,Xn2−nX_n^2-n 在吸收前也是一个鞅,可用来推导期望持续时间。

停止条件为何重要

对于没有上边界的公平游戏,破产几乎必然发生,终止时资本为零。然而,仅凭鞅的性质就断定终止时资本的期望必须等于初始资本,是不成立的。

对于每个固定的 nn,有

Ei[Xn∧τ0]=i,\mathbb{E}_i[X_{n\wedge\tau_0}]=i,

同时

Xn∧τ0⟶0almost surely.X_{n\wedge\tau_0}\longrightarrow 0 \quad\text{almost surely}.

如果没有附加条件,一般不能交换取期望与取极限的顺序。在这个例子中,尚未破产的路径越来越罕见,但这些路径上的资本可能越来越大。停止后的随机变量族并不一致可积,平均破产时间也为无穷大。

推广与应用

非等额输赢与可变转移概率

经典公式依赖于每次赢、输均为一个单位,以及 pp 保持不变这两个条件。如果资本每次变化的幅度更大,就可能越过边界,而不是恰好到达边界,从而产生越界量。此时,边界条件必须涵盖所有可能的退出状态。

如果获胜概率取决于当前资本,则成功概率满足

ui=piui+1+(1−pi)ui−1.u_i=p_i u_{i+1}+(1-p_i)u_{i-1}.

这类模型仍可采用第一步分析法,但一般不再具有偏向程度恒定时的简单公式。

吸收时间分布

期望持续时间无法描述游戏时长的完整概率分布。令 QQ 为转移矩阵中对应暂态 1,…,N−11,\ldots,N-1 的部分,则

Pr⁡i(T>n)=eiTQn1,\Pr_i(T>n)=e_i^{\mathsf T}Q^n\mathbf{1},

其中,eie_i 用于选定初始状态,1\mathbf{1} 是全一向量。

矩阵

F=(I−Q)−1F=(I-Q)^{-1}

称为吸收链的基本矩阵。其元素 FijF_{ij} 表示从 ii 出发,在吸收前访问暂态 jj 的期望次数。将第 ii 行各元素相加,即得 mim_i。

扩散近似

对时间和资本进行适当的尺度变换后,随机游走可导出基于维纳过程的连续模型。对于漂移为常数 μ\mu、方差增长率为 σ2\sigma^2 的扩散过程,先到达上边界 LL 而非零的概率 u(x)u(x) 满足

μu′(x)+σ22u′′(x)=0,u(0)=0,u(L)=1.\mu u'(x)+\frac{\sigma^2}{2}u''(x)=0, \qquad u(0)=0,\quad u(L)=1.

其解为

u(x)={1−e−2μx/σ21−e−2μL/σ2,μ≠0,xL,μ=0.u(x)= \begin{cases} \displaystyle \frac{1-e^{-2\mu x/\sigma^2}} {1-e^{-2\mu L/\sigma^2}}, & \mu\neq0,\\[1.2em] \displaystyle \frac{x}{L}, & \mu=0. \end{cases}

这些连续模型中的公式与离散破产概率公式相对应。

资本储备及其他有限种群

破产模型可用于简化描述资本储备因随机损失而耗尽的过程。排队系统、库存系统和种群模型中也会出现相关的边界到达问题。在保险数学中,准备金过程通常包含保费收入和金额不等的索赔,因此,基本的赌徒破产公式是这类模型的原型,而非可直接套用的描述。

在简单的中性种群模型中,携带某一变异的个体数量可在消失与固定之间变化。当增减变化对称时,固定概率与公平游戏中赌徒成功概率具有相同的线性形式。

局限与常见误解

经典结果假设赌注固定、各局结果独立、获胜概率不变,且不允许借贷或补充资本。结果之间的依赖、赌注变化、交易成本或外部收入都会改变这一过程,并可能同时改变破产概率与持续时间。

每局的期望收益为正,并不能消除破产风险。当 p>qp>q 时,玩家的资本具有有利的漂移,但早期的一连串亏损仍可能耗尽有限的资本。

反过来,在公平且没有时间上限的模型中,几乎必然破产并不意味着游戏每局的期望收益为负。公平性涉及增量的期望;破产则涉及整条随机路径及其边界行为。

这一问题也不同于赌徒谬误:在独立性假设下,一连串的失败并不会提高下一局获胜的概率。最后,固定单位赌注的公式不能直接用于在输赢之后改变赌注的投注策略;这类策略需要另建模型。