0485-1993 东大工 数学 WEB

概率统计 马尔可夫链 随机游走 赌徒破产问题

A,B 二人が合わせて $n$ 個のリンゴを持っており、ゲームごとに、勝った方は負けた方からリンゴを 1 つもらえるとする。ゲームには引き分けはなく、A が勝つ確率を $p$、B が勝つ確率を $q$ とする。このゲームを A または B、どちらかが手持ちのリンゴが無くなるまで続ける試合を考える。全てのリンゴを集めた方を勝者、リンゴを無くした方を敗者とする、また、A または B がリンゴを $z$ 個持っているとき、それぞれが勝者になる確率を $p_z,q_z$ とする。このとき、以下の問に答えよ。

(1) $p_z$ を $p_{z-1}$ および $p_{z+1}$ で表せ。

(2) $p_z$ および $q_z$ を求めよ。

(3) 試合が永遠に続く確率が 0 であることを示せ。

---

解答：

(1)
ゲームに引き分けはないため、$p+q=1$ である。
Aがリンゴを $z$ 個 $(1\le z\le n-1)$ 持っている状態から1回のゲームを行った後、確率 $p$ でAのリンゴは $z+1$ 個になり、確率 $q$ で $z-1$ 個になる。
全確率の定理より、次式が成り立つ。

$$\boxed{p_z=p{p}_{z+1}+q{p}_{z-1}}$$

(2)
(1)の漸化式と $p+q=1$ より、

$$\begin{array}{rl}(p+q)p_z& =p{p}_{z+1}+q{p}_{z-1}\\ p(p_{z+1}-p_z)& =q(p_z-p_{z-1})\\ p_{z+1}-p_z& =\frac{q}{p}(p_z-p_{z-1})\end{array}$$

境界条件は、Aがリンゴを0個持っている場合はすでに敗北しているため $p_0=0$、Aがリンゴを $n$ 個持っている場合は勝利しているため $p_n=1$ である。

(i) $p\ne q$ のとき（すなわち $p\ne \frac{1}{2}$）
数列 $\{p_{z+1}-p_z\}$ は公比 $\frac{q}{p}$ の等比数列であるから、

$$p_z-p_{z-1}={\left(\frac{q}{p}\right)}^{z-1}(p_1-p_0)={\left(\frac{q}{p}\right)}^{z-1}{p}_1$$

よって、$z\ge 1$ のとき

$$p_z=p_0+\sum _{k=1}^z(p_k-p_{k-1})=p_1\sum _{k=1}^z{\left(\frac{q}{p}\right)}^{k-1}=p_1\frac{1-{\left(\frac{q}{p}\right)}^z}{1-\frac{q}{p}}$$

$p_n=1$ より、

$$p_n=p_1\frac{1-{\left(\frac{q}{p}\right)}^n}{1-\frac{q}{p}}=1⟹p_1=\frac{1-\frac{q}{p}}{1-{\left(\frac{q}{p}\right)}^n}$$

したがって、

$$p_z=\frac{1-{\left(\frac{q}{p}\right)}^z}{1-{\left(\frac{q}{p}\right)}^n}$$

$q_z$ はBが $z$ 個のリンゴを持った状態からの勝率である。AとBの立場は対称であるため、$p_z$ の式で $p$ と $q$ を入れ替えることで得られる。

$$q_z=\frac{1-{\left(\frac{p}{q}\right)}^z}{1-{\left(\frac{p}{q}\right)}^n}$$

(ii) $p=q=\frac{1}{2}$ のとき
$p_{z+1}-p_z=p_z-p_{z-1}$ となり、数列 $\{p_z\}$ は等差数列である。
$p_0=0,p_n=1$ より、一般項は

$$p_z=\frac{z}{n}$$

対称性より、同様に

$$q_z=\frac{z}{n}$$

以上より、

$$\boxed{\begin{array}{rl}& p\ne q\text{ のとき: }{p}_z=\frac{1-{\left(\frac{q}{p}\right)}^z}{1-{\left(\frac{q}{p}\right)}^n},q_z=\frac{1-{\left(\frac{p}{q}\right)}^z}{1-{\left(\frac{p}{q}\right)}^n}\\ & p=q=\frac{1}{2}\text{ のとき: }{p}_z=\frac{z}{n},q_z=\frac{z}{n}\end{array}}$$

(3)
ある時点でAがリンゴを $z$ 個持っているとき、Bは $n-z$ 個のリンゴを持っている。
試合が誰かの勝利で終了する確率 $P_{\text{end}}$ は、Aが勝つ確率とBが勝つ確率の和である。
すなわち、$P_{\text{end}}=p_z+q_{n-z}$ である。

(i) $p\ne q$ のとき

$$\begin{array}{rl}{P}_{\text{end}}& =p_z+q_{n-z}\\ & =\frac{1-{\left(\frac{q}{p}\right)}^z}{1-{\left(\frac{q}{p}\right)}^n}+\frac{1-{\left(\frac{p}{q}\right)}^{n-z}}{1-{\left(\frac{p}{q}\right)}^n}\\ & =\frac{1-{\left(\frac{q}{p}\right)}^z}{1-{\left(\frac{q}{p}\right)}^n}+\frac{1-{\left(\frac{p}{q}\right)}^{n-z}}{1-{\left(\frac{p}{q}\right)}^n}\cdot \frac{{\left(\frac{q}{p}\right)}^n}{{\left(\frac{q}{p}\right)}^n}\\ & =\frac{1-{\left(\frac{q}{p}\right)}^z}{1-{\left(\frac{q}{p}\right)}^n}+\frac{{\left(\frac{q}{p}\right)}^n-{\left(\frac{q}{p}\right)}^z}{{\left(\frac{q}{p}\right)}^n-1}\\ & =\frac{1-{\left(\frac{q}{p}\right)}^z-{\left(\frac{q}{p}\right)}^n+{\left(\frac{q}{p}\right)}^z}{1-{\left(\frac{q}{p}\right)}^n}\\ & =\frac{1-{\left(\frac{q}{p}\right)}^n}{1-{\left(\frac{q}{p}\right)}^n}\\ & =1\end{array}$$

(ii) $p=q=\frac{1}{2}$ のとき

$$\begin{array}{rl}{P}_{\text{end}}& =p_z+q_{n-z}\\ & =\frac{z}{n}+\frac{n-z}{n}\\ & =1\end{array}$$

いずれの場合も、試合が終了する確率 $P_{\text{end}}$ は常に 1 である。
したがって、試合が永遠に続く確率（どちらも勝利しない確率）は $1-P_{\text{end}}=0$ である。
(証明終)

---

本题考察了概率统计中的经典“赌徒破产问题”（Gambler’s Ruin Problem），涉及随机游走和马尔可夫链的吸收概率计算。

第一问要求写出状态转移的差分方程。由于没有平局，单局胜负概率之和为1。通过全概率公式，从当前状态出发，考虑下一步胜负两种可能的走向，可以将当前的胜率表示为前后两个相邻状态胜率的线性组合。

第二问求解一维齐次线性常系数差分方程。结合题意的边界条件（持有0个苹果时意味着已经破产，胜率为0；持有n个苹果时意味着已经赢下所有筹码，胜率为1），即可解出特解。需要注意的是，当单局胜负概率相等时，差分方程的特征方程会出现重根，其通解会从指数形式退化为线性形式，因此需要分情况讨论。对于B的胜率，只需要利用对称性互换两人初始状态和单局胜率变量即可直接得出答案。

第三问要求证明游戏必然结束。只需将某一时刻下A最终获胜的概率与B最终获胜的概率相加，通过简单的代数化简证明其和始终等于1。既然必定有一方获胜的总概率为1，那么永远分不出胜负（即游戏永远无休止进行下去）的概率自然就是0了。