返回题库

赌徒破产

Gambler’s Ruin Problem

专题
Probability / 概率
难度
L4

题目详情

赌徒初始有 ii 美元。每次下注：以概率 pp 赢 1 美元（以概率 q=1−pq=1-p 输 1 美元）。

当资金到达 0（破产）或到达 NN（目标）时停止。

问：从 ii 出发最终到达 NN 的概率 PiP_i 是多少？

英文原题

A gambler starts with ii dollars. Each bet, the gambler wins $1 with probability pp (and thus loses $1 with probability q=1−pq = 1-p). The game stops upon reaching $0 (ruin) or $N (goal). What is the probability PiP_i of eventually reaching $Nstartingfromstarting fromi$?

解析

满足递推

Pi=pPi+1+qPi−1,P0=0, PN=1.P_i=pP_{i+1}+qP_{i-1},\quad P_0=0,\ P_N=1.

解得：

  • 若 p=12p=\frac12，Pi=iNP_i=\frac{i}{N}；
  • 若 p≠12p\ne\frac12，
Pi=1−(qp)i1−(qp)N.P_i=\frac{1-\left(\frac{q}{p}\right)^i}{1-\left(\frac{q}{p}\right)^N}.

英文解析

Let PiP_i = probability of ending with $N when starting with $i. Then
Pi=p Pi+1+q Pi−1,P0=0,PN=1.P_i = p\,P_{i+1} + q\,P_{i-1}, \quad P_0 = 0, \quad P_N = 1.

  1. If p=12p = \frac{1}{2}, then
    Pi=iN.P_i = \frac{i}{N}.
  2. If p≠12p \neq \frac{1}{2}, then
    Pi=1−(qp)i1−(qp)N.P_i = \frac{1 - \bigl(\tfrac{q}{p}\bigr)^i}{1 - \bigl(\tfrac{q}{p}\bigr)^N}.