Markov 链中的赌徒问题和游走问题

赌徒问题

问题1

假设有一个赌徒，在每次赌博中以概率 $p$ 赢取一个单位，以概率 $q = 1 - p$ 输一个单位，并且每次赌博都是独立的，设赌徒开始时有 $i$ 个单位，财富到达 $0$ 或者 $N$ 时结束赌博，记 $P_{i}$ 为从初始财富 $i$ 出发，先到达 $N$ 而不是 $0$ 的概率

本质是有两个吸收壁的 Markov 链

由题目可以看出 $P_{0} = 0, P_{N} = 1$ ，由全概率公式，可以得到如下递推公式

P_{i} = p P_{i + 1} + q P_{i - 1}

于是

p P_{i} + q P_{i} = p P_{i + 1} + q P_{i - 1}

P_{i + 1} - P_{i} = \frac{q}{p} (P_{i} - P_{i - 1})

这是一个等比数列，因此

P_{i} - P_{i - 1} = \frac{q}{p} (P_{i - 1} - P_{i}) = (\frac{q}{p})^{i - 1} (P_{1} - P_{0})

累加得到

P_{i} - P_{1} = P_{1} [\frac{q}{p} + (\frac{q}{p})^{2} + \dots + (\frac{q}{p})^{i - 1}]

现在需要分两种情况计算
Case1: $p = q$ 时

P_{i} - P_{1} = P_{1} (i - 1)

代入 $P_{N} = 1$ 这一条件，解得 $P_{1} = \frac{1}{N}$ ，于是

P_{i} = \frac{i}{N}

Case2: $p \neq = q$ 时

P_{i} - P_{1} = P_{1} (\frac{1 - ( \frac{q}{p} ) ^{i}}{1 - \frac{q}{p}} - 1)

代入 $P_{N} = 1$ 这一条件，解得

P_{1} = \frac{1 - \frac{q}{p}}{1 - ( \frac{q}{p} ) ^{N}}

代入原式，即可得到

P_{i} = \frac{1 - ( \frac{q}{p} ) ^{i}}{1 - ( \frac{q}{p} ) ^{N}}

关于上面的递推公式，其实可以写成矩阵形式

(P_{i + 1} P_{i}) = (\frac{1}{p} 1 - \frac{q}{p} 0) (P_{i} P_{i - 1})

然后利用三对角行列式 > 针对特征方程法中通项公式的推导相同的方法，只需要求出矩阵的特征值即可，比如这里的特征值是 $\frac{q}{p}, 1$
当 $p \neq = q$ 时， $P_{i} = C_{1} (\frac{q}{p})^{i} + C_{2}$
当 $p = q$ 时， $P_{i} = (C_{1} + C_{2} n) 1^{n}$
然后分别代入初值条件 $P_{0} = 0, P_{N} = 1$ ，解出 $C_{1}, C_{2}$ 就是

P_{i} = ⎩ ⎨ ⎧ \frac{i}{N}, \frac{1 - ( q / p ) ^{i}}{1 - ( q / p ) ^{N}}, p = q = \frac{1}{2}, p \neq = q .

问题2

赌徒平均多少局结束赌博？即求期望

记 $M_{i}$ 为从 $i$ 到 $0$ 或者 $N$ 的平均时间，于是有 $M (0) = M (N) = 0$ ，由全期望公式，我们有

M_{i} = (1 + M_{i + 1}) p + (1 + M_{i - 1}) q = 1 + p M_{i + 1} + q M_{i - 1}

于是

p M_{i} + q M_{i} = p M_{i + 1} + q M_{i - 1} + 1

继续分两种情况计算

Case1: $p \neq = q$ 时
做变形得到

M_{i + 1} - M_{i} - \frac{1}{q - p} = \frac{q}{p} (M_{i} - M_{i - 1} - \frac{1}{q - p})

与上面的求解方式相同，累加得到:

M_{i} - M_{1} - \frac{i - 1}{q - p} = (M_{1} - \frac{1}{q - p}) (\frac{1 - ( \frac{q}{p} ) ^{i}}{1 - \frac{q}{p}} - 1)

代入 $M_{N} = 0$ 这一条件，得到

M_{1} = \frac{1}{q - p} - \frac{N}{q - p} (\frac{1 - \frac{q}{p}}{1 - ( \frac{q}{p} ) ^{N}})

代回原式，整理得到:

M_{i} = \frac{i}{q - p} - \frac{N}{q - p} \cdot \frac{1 - ( \frac{q}{p} ) ^{i}}{1 - ( \frac{q}{p} ) ^{N}}

Case2: $p = q$ 时，有

M_{i + 1} - M_{i} = M_{i} - M_{i - 1} - 2

因此

M_{2} - M_{1} = M_{1} - M_{0} - 2

M_{3} - M_{2} = M_{2} - M_{1} - 2

\dots

M_{i} - M_{i - 1} = M_{i - 1} - M_{i - 2} - 2

累加得到:

M_{i} - M_{i - 1} = M_{1} - 2 (i - 1)

与上面类似，再次累加得到:

M_{i} = i M_{1} - i (i - 1)

利用 $M_{N} = 0$ 这个条件，可以得到 $M_{1} = N - 1$
代入上式，解得:

M_{i} = i (N - i)

实际上，由三对角行列式 > 2. 利用分析学的极限思想导出重根公式，对于 $p \neq = q$ 的情形，我们只需要令 $q \to p$ 即可，由洛必达法则计算就有

q \to p lim \frac{i}{q - p} - \frac{N}{q - p} \cdot \frac{1 - ( \frac{q}{p} ) ^{i}}{1 - ( \frac{q}{p} ) ^{N}} = \frac{i ( N - i )}{2 p} = i (N - i)

游走问题

问题1

假设有一只蚂蚁在直线上爬行，原点处有一只蜘蛛捕食， $N$ 处有一挡板，当蚂蚁到达 $N$ 后，只能返回，蚂蚁向左和向右走一步的概率分别为 $p$ 和 $q (p + q = 1, p, q \neq = 0)$ ，开始时位于 $i (0 \leq i \leq N)$ ，计算蚂蚁被吃掉的概率

本质是有一个吸收壁，一个反射壁的Markov链

记 $P_{i}$ 为开始时的坐标为 $i$ , 且最终到达 $0$ 的概率，于是 $P_{0} = 1, P_{N} = P_{N - 1}$

P_{i} = q P_{i + 1} + p P_{i - 1} = p P_{i} + q P_{i}

于是

P_{i + 1} - P_{i} = \frac{p}{q} (P_{i} - P_{i - 1})

与上面的问题一样，累加得到:

P_{i} - P_{1} = (P_{1} - 1) [\frac{p}{q} + (\frac{p}{q})^{2} + \dots + (\frac{p}{q})^{i - 1}]

Case1: 当 $p = q = \frac{1}{2}$ 时

P_{i} - P_{1} = (P_{1} - 1) (i - 1)

由于 $P_{N} = P_{N - 1}$ ，于是可得 $P_{N} - P_{1} = (P_{1} - 1) (N - 1)$ 和 $P_{N - 1} - P_{1} = (P_{1} - 1) (N - 2)$
两式相减得到 $P_{1} = 1$ ，代回原式立即得到 $P_{i} = 1$

Case2. 当 $p \neq = q$ 时

P_{i} - P_{1} = (P_{1} - 1) (\frac{1 - ( \frac{p}{q} ) ^{i}}{1 - \frac{p}{q}} - 1)

令 $i = N, N - 1$ , 得到

P_{N} - P_{1} = (P_{1} - 1) (\frac{1 - ( \frac{p}{q} ) ^{N}}{1 - \frac{p}{q}} - 1)

以及

P_{N - 1} - P_{1} = (P_{1} - 1) (\frac{1 - ( \frac{p}{q} ) ^{N - 1}}{1 - \frac{p}{q}} - 1)

两式相减得到:

(P_{1} - 1) (\frac{p}{q})^{N - 1} = 0

从而 $P_{1} = 1$ ，代入原式立即得到 $P_{i} = 1$
因此蚂蚁一定会到达 0 点被吃掉

另一种方法

设 $X_{n}$ 为蚂蚁在时刻 $n$ 所处的位置，则可以写出其转移概率矩阵

P = 1 p 0 ⋮ 00 00 p ⋮ 00 0 q 0 ⋮ 00 0 \dots 0 0 \dots 0 q \dots 0 \dots 0 \dots p 0 \dots 0 000 ⋮ 01 000 ⋮ q 0

其中 $p_{ij} = Pr (X_{n + 1} = j ∣ X_{n} = i) .$
此 Markov 链有两类，分别为 ${0}$ 和 ${1, 2, \dots, N}$ 。由于 $1, 2, \dots, N$ 互通，从而同为常返或者非常返，于是考虑1状态
由于 1 会以 $p$ 的概率到 0，这意味着 1 将以 $p$ 的概率永远回不到 1，从而 1 为非常返
从而 ${1, 2, \dots, N}$ 为非常返,于是对于 $i \in {1, 2, \dots, N}$ , 有

n \to \infty lim p_{i 0}^{(n)} = n \to \infty lim (1 - j \neq = 0 \sum N p_{ij}^{(n)}) = 1 - j \neq = 0 \sum N n \to \infty lim p_{ij}^{(n)} = 1

从而一定会到达 $0$ 点

问题2

蚂蚁平均多长时间被吃掉，即求期望

记 $M_{i}$ 为从 $i$ 到 $0$ 的平均时间，于是有 $M (0) = 0$
由于在 $N$ 处会立即返回 $N - 1$ 处，因此 $M (N) = M (N - 1) + 1$
类似赌徒问题中的期望问题
Case1: $p \neq = q$ 时，可以得到

M_{i + 1} - M_{i} - \frac{1}{p - q} = \frac{p}{q} (M_{i} - M_{i - 1} - \frac{1}{p - q})

累加得到:

M_{i} - M_{1} - \frac{i - 1}{p - q} = (M_{1} - \frac{1}{p - q}) (\frac{1 - ( \frac{p}{q} ) ^{i}}{1 - \frac{p}{q}} - 1)

$令 i = N, N - 1$ , 分别得到

M_{N} - M_{1} - \frac{N - 1}{p - q} = (M_{1} - \frac{1}{p - q}) (\frac{1 - ( \frac{p}{q} ) ^{N}}{1 - \frac{p}{q}} - 1)

M_{N - 1} - M_{1} - \frac{N - 2}{p - q} = (M_{1} - \frac{1}{p - q}) (\frac{1 - ( \frac{p}{q} ) ^{N - 1}}{1 - \frac{p}{q}} - 1)

两式相减得

1 - \frac{1}{p - q} = (m_{1} - \frac{1}{p - q}) (\frac{( \frac{p}{q} ) ^{N - 1} - ( \frac{p}{q} ) ^{N}}{1 - \frac{p}{q}}) = (m_{1} - \frac{1}{p - q}) (\frac{p}{q})^{N - 1}

从而

M_{1} = (1 - \frac{1}{p - q}) (\frac{p}{q})^{1 - N} + \frac{1}{p - q}

代回原式整理得到

M_{i} = \frac{i}{p - q} + (1 - \frac{1}{p - q}) (\frac{p}{q})^{1 - N} \cdot \frac{1 - ( \frac{p}{q} ) ^{i}}{1 - \frac{p}{q}}

Case2: $p = q$ 时
同样可以在 Case1 中令 $q \to p$ , 然后用洛必达法则就能算出

M_{i} = i (2 N - i)

tags	数学, 随机过程
authors	blueraina
status	stable
owner	blueraina

群知识库

AI 找笔记

Explorer

Markov 链中的赌徒问题和游走问题

赌徒问题

游走问题

评论

Graph View

目录

反向链接