Stochastic Process

HW5

如有错误，烦请指正.

证明 C-K 方程

p_{i j}^{(n)} = \sum_{k \in I} p_{i k}^{(l)} p_{k j}^{(n - l)} .

记事件

\begin{matrix} A = {X_{m + n} = j}, \\ B = {X_{m} = i}, \\ C_{k} = {X_{m + l} = k}, \end{matrix}

则

\begin{matrix} p_{i j}^{(n)} = P (X_{m + n} = j | X_{m} = i) = P (A | B), \\ p_{i k}^{(l)} = P (X_{m + l} = k | X_{m} = i) = P (C_{k} | B), \\ p_{k j}^{(n - l)} = P (X_{m + n} = j | X_{m + l} = k) = P (A | C_{k}) . \end{matrix}

$A^*,B_k^*$ $\set{B^*_k}$ 构成一个划分，

P (A^{*}) = \sum_{k} P (A^{*} | B_{k}^{*}) P (B_{k}^{*}) = \sum_{k} P (A^{*} B_{k}^{*}) .

所以，

\begin{aligned} p_{i j}^{(n)} & = P (A | B) \\ = \sum_{k \in I} P (A C_{k} | B) \\ = \sum_{k \in I} \frac{P (A B C_{k})}{P (B)} \\ = \sum_{k \in I} \frac{P (A B C_{k})}{P (B C_{k})} \frac{P (B C_{k})}{P (B)} \\ = \sum_{k \in I} P (A | B C_{k}) P (C_{k} | B) \\ = \sum_{k \in I} P (X_{m + n} = j | X_{m} = i, X_{m + l} = k) P (X_{m + l} = k | X_{m} = i) \\ = \sum_{k \in I} P (X_{m + n} = j | X_{m + l} = k) P (X_{m + l} = k | X_{m} = i) \\ = \sum_{k \in I} p_{k j}^{(n - l)} p_{i k}^{(l)} \\ = \sum_{k \in I} p_{i k}^{(l)} p_{k j}^{(n - l)} . \end{aligned}

(1)

X_{n + 1} = max {Z_{1}, Z_{2}, \dots, Z_{n}, Z_{n + 1}} = max {max {Z_{1}, Z_{2}, \dots, Z_{n}}, Z_{n + 1}} = max {X_{n}, Z_{n + 1}} = max {X_{n}, Z_{1}} .

所以

\begin{aligned} P (X_{n + 1} = i_{n + 1} | X_{0} = i_{0}, X_{1} = i_{1}, \dots, X_{n} = i_{n}) & = P (max {X_{n}, Z_{1}} = i_{n + 1} | X_{0} = i_{0}, X_{1} = i_{1}, \dots, X_{n} = i_{n}) \\ = \frac{P (max {X_{n}, Z_{1}} = i_{n + 1}, X_{0} = i_{0}, X_{1} = i_{1}, \dots, X_{n} = i_{n})}{P (X_{0} = i_{0}, X_{1} = i_{1}, \dots, X_{n} = i_{n})} \\ = \frac{P (max {X_{n}, Z_{1}} = i_{n + 1}, X_{n} = i_{n}) P (X_{0} = i_{0}, X_{1} = i_{1}, \dots, X_{n - 1} = i_{n - 1})}{P (X_{0} = i_{0}, X_{1} = i_{1}, \dots, X_{n - 1} = i_{n - 1}) P (X_{n} = i_{n})} \\ = \frac{P (max {X_{n}, Z_{1}} = i_{n + 1}, X_{n} = i_{n})}{P (X_{n} = i_{n})} \\ = P (max {X_{n}, Z_{1}} = i_{n + 1} | X_{n} = i_{n}) \\ = P (X_{n + 1} = i_{n + 1} | X_{n} = i_{n}) . \end{aligned}

$\set{X_n,n\geqslant0}$ 为马尔可夫链.

$p_{ij}(n)=P(X_{n+1}=j|X_n=i)$ .

$j>i$ 时，

p_{i j} (n) = P (X_{n + 1} = j | X_{n} = i) = P (max {X_{n}, Z_{1}} = j | X_{n} = i) = P (Z_{1} = j | X_{n} = i) = P (Z_{1} = j) = p_{j};

$j<i$ 时，

p_{i j} (n) = P (X_{n + 1} = j | X_{n} = i) = P (max {X_{n}, Z_{1}} = j | X_{n} = i) = 0.

$j=i$ 时，

p_{i j} (n) = P (X_{n + 1} = j | X_{n} = i) = P (max {X_{n}, Z_{1}} = j | X_{n} = i) = P (Z_{1} ⩽ j | X_{n} = i) = P (Z_{1} ⩽ j) = \sum_{k = 0}^{j} p_{k} .

所以，

\begin{matrix} p_{i j} (n) = P (X_{n + 1} = j | X_{n} = i) = {\begin{cases} p_{j} & , j > i, \\ \sum_{k = 0}^{j} p_{k} & , j = i, \\ 0 & , j < i \end{cases} = p_{i j} . \end{matrix}

转移概率矩阵为

\begin{matrix} P = (\begin{matrix} p_{00} & p_{01} & p_{02} & \dots \\ p_{10} & p_{11} & p_{12} & \dots \\ p_{20} & p_{21} & p_{22} & \dots \\ ⋮ & ⋮ & ⋮ & ⋱ \end{matrix}) = (\begin{matrix} p_{0} & p_{1} & p_{2} & \dots \\ 0 & p_{0} + p_{1} & p_{2} & \dots \\ 0 & 0 & p_{0} + p_{1} + p_{2} & \dots \\ ⋮ & ⋮ & ⋮ & ⋱ \end{matrix}) . \end{matrix}

(2)

因为

X_{n + 1} = \sum_{i = 1}^{n + 1} Z_{i} = \sum_{i = 1}^{n} Z_{i} + Z_{i + 1} = X_{n} + Z_{n + 1} = X_{n} + Z_{1},

所以

\begin{aligned} P (X_{n + 1} = i_{n + 1} | X_{0} = i_{0}, X_{1} = i_{1}, \dots, X_{n} = i_{n}) & = P (X_{n} + Z_{1} = i_{n + 1} | X_{0} = i_{0}, X_{1} = i_{1}, \dots, X_{n} = i_{n}) \\ = \frac{P (X_{n} + Z_{1} = i_{n + 1}, X_{0} = i_{0}, X_{1} = i_{1}, \dots, X_{n} = i_{n})}{P (X_{0} = i_{0}, X_{1} = i_{1}, \dots, X_{n} = i_{n})} \\ = \frac{P (X_{n} + Z_{1} = i_{n + 1}, X_{n} = i_{n}) P (X_{0} = i_{0}, X_{1} = i_{1}, \dots, X_{n - 1} = i_{n - 1})}{P (X_{0} = i_{0}, X_{1} = i_{1}, \dots, X_{n - 1} = i_{n - 1}) P (X_{n} = i_{n})} \\ = \frac{P (X_{n} + Z_{1} = i_{n + 1}, X_{n} = i_{n})}{P (X_{n} = i_{n})} \\ = P (X_{n} + Z_{1} = i_{n + 1} | X_{n} = i_{n}) \\ = P (X_{n + 1} = i_{n + 1} | X_{n} = i_{n}) . \end{aligned}

$\set{X_n,n\geqslant0}$ 为马尔可夫链.

其转移概率为

\begin{aligned} p_{i j} (n) & = P (X_{n + 1} = j | X_{n} = i) \\ = P (X_{n} + Z_{1} = j | X_{n} = i) \\ = \frac{P (X_{n} + Z_{1} = j, X_{n} = i)}{P (X_{n} = i)} \\ = \frac{P (Z_{1} = j - i, X_{n} = i)}{P (X_{n} = i)} \\ = \frac{P (Z_{1} = j - i) P (X_{n} = i)}{P (X_{n} = i)} \\ = P (Z_{1} = j - i) \\ = {\begin{cases} 0 & , j < i \\ p_{j - i} & , j ⩾ i . \end{cases} \\ = p_{i j} . \end{aligned}

状态转移矩阵为

\begin{matrix} P = (\begin{matrix} p_{00} & p_{01} & p_{02} & \dots \\ p_{10} & p_{11} & p_{12} & \dots \\ p_{20} & p_{21} & p_{22} & \dots \\ ⋮ & ⋮ & ⋮ & ⋱ \end{matrix}) = (\begin{matrix} p_{0} & p_{1} & p_{2} & \dots & \dots \\ 0 & p_{0} & p_{1} & \dots & \dots \\ 0 & 0 & p_{0} & \dots & \dots \\ ⋮ & ⋮ & ⋮ & ⋱ & \dots \\ 0 & 0 & 0 & 0 & p_{0} \end{matrix}) . \end{matrix}

\begin{array}{r} p_{i j} (n) = P (X_{n + 1} = j | X_{n} = i) . \end{array}

$j=i+1$ $B$ $A,B$ $A$ $A$ $i$ $B$ $N-i$ $B$ 罐的概率为
$P (B) = P (被选取的球位于 B 罐) = \frac{N - i}{N},$
$A$ 罐的概率为
$P (A) = P (被选取的球位于 A 罐) = \frac{i}{N} .$
所以
$p_{i j} (n) = P (X_{n + 1} = j | X_{n} = i) = P (B) \cdot p = \frac{p (N - i)}{N} = p_{i j}, j = i + 1.$
$j=i$ $A,B$ 两罐里选择取出球的罐放置. 所以，
$p_{i j} (n) = P (X_{n + 1} = j | X_{n} = i) = P (A) \cdot p + P (B) \cdot q = \frac{p i}{N} + \frac{q (N - i)}{N} = p_{i j}, j = i .$
$j=i-1$ $A$ $A,B$ $B$ 罐放置. 所以，
$p_{i j} (n) = P (X_{n + 1} = j | X_{n} = i) = P (A) \cdot q = \frac{q i}{N} = p_{i j}, j = i - 1.$
$p_{ij}(n)=p_{ij}=0$ .

状态转移矩阵为

\begin{matrix} P = (\begin{matrix} p_{00} & p_{01} & p_{02} & \dots \\ p_{10} & p_{11} & p_{12} & \dots \\ p_{20} & p_{21} & p_{22} & \dots \\ ⋮ & ⋮ & ⋮ & ⋱ \end{matrix}) = (\begin{matrix} \frac{p i}{N} + \frac{q (N - i)}{N} & \frac{p (N - i)}{N} & 0 & \dots & 0 \\ \frac{q i}{N} & \frac{p i}{N} + \frac{q (N - i)}{N} & \frac{p (N - i)}{N} & \dots & 0 \\ 0 & \frac{q i}{N} & \frac{p i}{N} + \frac{q (N - i)}{N} & \dots & 0 \\ ⋮ & ⋮ & ⋮ & ⋱ & \dots \\ 0 & 0 & 0 & 0 & \frac{p i}{N} + \frac{q (N - i)}{N} \end{matrix}) . \end{matrix}