返回题库

赌徒破产问题

Gambler's Ruin Problem

专题
Strategy / 策略
难度
L4

题目详情

玩家 M 有 1 美元，玩家 N 有 2 美元。每局赢家从输家处赢走 1 美元。M 更强，每局获胜概率为 2/32/3。一直玩到一方破产为止。问：M 最终获胜的概率是多少？

Player M has $1, and player N has $2. Each round, the winner takes $1 from the loser. Player M is better and wins each round with probability 2/32/3. They play until one player is ruined (bankrupt). What is the probability that M wins?

解析

把状态定义为 M 当前拥有的美元数：{0,1,2,3}\{0,1,2,3\}。

  • 状态 0、3 是吸收态。
  • 从 1 到 0 的概率 1/31/3，从 1 到 2 的概率 2/32/3。
  • 从 2 到 1 的概率 1/31/3，从 2 到 3 的概率 2/32/3。

设 aia_i 为从状态 ii 出发 M 最终获胜（到达 3）的概率，则

{a0=0,a3=1,a1=13⋅0+23a2,a2=13a1+23⋅1.\begin{cases} a_0=0,\\ a_3=1,\\ a_1=\tfrac{1}{3}\cdot 0+\tfrac{2}{3}a_2,\\ a_2=\tfrac{1}{3}a_1+\tfrac{2}{3}\cdot 1. \end{cases}

解得 a1=47a_1=\frac{4}{7}，因此 M 初始为 1 美元时获胜概率为 47\boxed{\frac{4}{7}}。

Original Explanation

  • State space can be represented by how many dollars M has: {0,1,2,3}\{0,1,2,3\}.
  • States 0 and 3 are absorbing (once M has 0 or 3 dollars, the game ends).
  • The transition probabilities are:
    • From 1 to 0 with probability 1/31/3, and from 1 to 2 with probability 2/32/3.
    • From 2 to 1 with probability 1/31/3, and from 2 to 3 with probability 2/32/3.
  • Solving the absorption probability equations {a0=0,a3=1,a1=13⋅0+23 a2,a2=13 a1+23⋅1,\begin{cases} a_0 = 0,\\ a_3 = 1,\\ a_1 = \tfrac{1}{3}\cdot 0 + \tfrac{2}{3}\,a_2,\\ a_2 = \tfrac{1}{3}\,a_1 + \tfrac{2}{3}\cdot 1, \end{cases} yields a1=47,a2=67.a_1 = \frac{4}{7}, \quad a_2 = \frac{6}{7}.

Thus, if M starts with $1, the probability that M wins is 4/74/7.