Problem Sheet 4

根据马尔可夫链和转移概率 $p_{1,2} = a$ 以及 $p_{2,1} = b$ 的条件，可以写出完整的转移矩阵。状态空间是 ${1,2}$，所以有两种状态。因为从一个状态到另一个状态的概率之和必须等于 1，所以 $p_{1,1} = 1-a$ 和 $p_{2,2} = 1-b$​。因此，转移矩阵为：

$$P = \begin{pmatrix} 1-a & a \\ b & 1-b \end{pmatrix}$$

这里，$p_{1,1} = 1-a$ 和 $p_{2,2} = 1-b$​ 是因为转移概率必须满足总和为1的条件。

首先，定义马尔可夫链的转移矩阵。对于状态空间$\{1,2\}$，给定 $p_{1,2} = a$ 和 $p_{2,1} = b$，其中 $a, b \in (0,1)$，转移矩阵 $P$ 可以表示为：

$$P = \begin{bmatrix} 1-a & a \\ b & 1-b \\ \end{bmatrix}$$

这里，$p_{1,1} = 1-a$ 和 $p_{2,2} = 1-b$ 是因为转移概率必须满足总和为1的条件。

接下来，使用 Chapman-Kolmogorov 方程来证明给定的 $n$ 步转移概率公式。Chapman-Kolmogorov 方程表达了 $n$ 步转移概率与中间步骤的关系：

$$p^n_{i,j} = \sum_{k=1}^2 p^n_{i,k} p^1_{k,j}$$

目标是证明：

$$p^n_{1,1} = \frac{a(1-a-b)^n + b}{a+b}.$$

基础情况（n=1）：

当 $n=1$ 时，有 $p^1_{1,1} = 1-a$ 。可以看到，当 $n=1$ 时，上述公式变为：

$$\frac{a(1-a-b) + b}{a+b} = \frac{a-a^2-ab + b}{a+b} = \frac{a-a^2-ab + b}{a+b} = 1-a = p^1_{1,1},$$

这符合期望。

归纳步骤：

假设对于某个 $n=k$，公式成立，即：

$$p^k_{1,1} = \frac{a(1-a-b)^k + b}{a+b}.$$

需要证明当 $n=k+1$ 时，公式也成立。使用 Chapman-Kolmogorov 方程，我们有：

$$p^{k+1}_{1,1} = p^k_{1,1}p^1_{1,1} + p^k_{1,2}p^1_{2,1}$$

将已知的转移概率和归纳假设带入上式：

$$p^{k+1}_{1,1} = \frac{a(1-a-b)^k + b}{a+b}(1-a) + \left(1 - \frac{a(1-a-b)^k + b}{a+b}\right)b$$

简化上式，可以得到：

$$p^{k+1}_{1,1} = \frac{a(1-a-b)^{k+1} + b}{a+b},$$

这证明了给定的公式对于 $n=k+1$ 也成立，完成了归纳证明。

求解其他 $n$ 步转移概率：

• 对于$p^n_{1,2}$，有：

$$p^n_{1,2} = 1 - p^n_{1,1} = 1 - \frac{a(1-a-b)^n + b}{a+b}$$

• 对于$p^n_{2,1}$，可以使用相同的方法证明：

$$p^n_{2,1} = \frac{b(1-a-b)^n + a}{a+b}$$

• 最后，对于 $p^n_{2,2}$，有：

$$p^n_{2,2} = 1 - p^n_{2,1} = 1 - \frac{b(1-a-b)^n + a}{a+b}$$

这样，就找到了所有 $n$ 步转移概率的表达式。

通过分析两种策略：大胆策略和谨慎策略，来找出达到 €8 而不破产的概率。

大胆策略

在大胆策略下，总是下最大的赌注，但不会超过赢了之后会超过 €8 的金额。这意味着，如果当前财富是 €x，你会下赌注 €min(€8-€x, €x)。这样做的目的是尽可能地快速达到 €8，但同时避免因为一次游戏的输赢直接破产或超过目标。

我们设 $p = 0.4$ 为单次游戏赢的概率，$1-p = 0.6$ 为输的概率。让我们定义 $P(x)$ 为从 €x 开始最终达到 €8 的概率，在不破产的情况下。

当有 €3 时，会下 €3 的赌注（因为如果赢了，就会有 €6，这是不会超过 €8 的最大赌注）。如果输了，你就破产了。所以，从 €3 开始，你有一次机会赢得 €6，然后从 €6 开始，你会下 €2 的赌注，以便在赢的情况下达到 €8。

• 从 €3 开始赢到 €8 的概率是 $P(3) = p \times P(6)$​ ，因为必须先从 €3 赢到 €6。
• 从 €6 开始，你再次下赌注 €2，所以 $P(6) = p \times P(8)$​。

但是，$P(8) = 1$，因为一旦有 €8，你就达到了目标。因此，我们可以反向工作来找出 $P(3)$。

首先，注意到从 €6 到 €8 的过程只涉及一次赌注，所以 $P(6) = p$。

因此，$P(3) = p^2 = 0.4^2 = 0.16$。