Stochastic Process

HW6

如有错误，烦请指正.

1

判断二维对称随机游动的常返性.

$i=0$ 常返的充分必要条件是

\sum_{n = 0}^{\infty} p_{00}^{(n)} = \infty,

所以只需要判断这个级数的敛散性即可.

因为

\sum_{n = 0}^{\infty} p_{00}^{(n)} = \sum_{n = 0}^{\infty} p_{00}^{(2 n)} + \sum_{n = 0}^{\infty} p_{00}^{(2 n + 1)},

$0$ ）出发只有转移偶数步才能回到原点，所以

p_{00}^{(2 n + 1)} = 0.

所以

\sum_{n = 0}^{\infty} p_{00}^{(n)} = \sum_{n = 0}^{\infty} p_{00}^{(2 n)} .

$p_{ii}^{(2n)},n\in\N$ $2n$ $2l_1$ $x$ $2l_2$ $y$ 方向移动，则

n = l_{1} + l_{2}, l_{1}, l_{2} \in N .

$l_1,l_2$ $2n$ $4$ $l_1,l_2,l_3=l_1,l_4=l_2$ $l_1+l_2+l_3+l_4=2n$ ，则把它们排成一列共有

\frac{(2 n)!}{(l_{1}!) (l_{2}!) (l_{3}!) (l_{4}!)} = \frac{(2 n)!}{(l_{1}!)^{2} (l_{2}!)^{2}}

$2n$ $4$ $4^{2n}$ 种分法，所以

\begin{aligned} p_{00}^{(2 n)} & = \sum_{l_{1} + l_{2} = n} \frac{(2 n)!}{(l_{1}!)^{2} (l_{2}!)^{2} 4^{2 n}} \\ = \sum_{i = 0}^{n} \frac{(2 n)!}{(i!)^{2} ((n - i)!)^{2} 4^{2 n}} \\ = \frac{(2 n)!}{(n!)^{2} 4^{2 n}} \sum_{i = 0}^{n} \frac{n!}{i! (n - i)!} \cdot \frac{n!}{i! (n - i)!} \\ = \frac{(2 n)!}{(n!)^{2} 4^{2 n}} \sum_{i = 0}^{n} (\binom{n}{i}) (\binom{n}{n - i}) \\ = \frac{(2 n)!}{(n!)^{2} 4^{2 n}} (\binom{2 n}{n}) \\ = \frac{1}{4^{2 n}} {(\binom{2 n}{n})}^{2} . \end{aligned}

证明
$\sum_{i = 0}^{n} (\binom{n}{i}) (\binom{n}{n - i}) = (\binom{2 n}{n}) .$
考虑恒等式
$(1 + x)^{n} (1 + x)^{n} = (1 + x)^{2 n} .$
左边展开，
$\begin{matrix} (1 + x)^{n} = \sum_{i = 0}^{n} (\binom{n}{i}) x^{i}, \\ (1 + x)^{n} (1 + x)^{n} = \sum_{i = 0}^{n} (\binom{n}{i}) x^{i} \cdot \sum_{j = 0}^{n} (\binom{n}{j}) x^{j} = \sum_{i = 0}^{n} \sum_{j = 0}^{n} (\binom{n}{i}) (\binom{n}{j}) x^{i} x^{j}; \end{matrix}$
右边展开，
$(1 + x)^{2 n} = \sum_{k = 0}^{2 n} (\binom{2 n}{k}) x^{k} .$
比较两边系数就有
$\sum_{i = 0}^{k} (\binom{n}{i}) (\binom{n}{k - i}) = (\binom{2 n}{k}) .$
特别，
$\sum_{i = 0}^{n} (\binom{n}{i}) (\binom{n}{n - i}) = \sum_{i = 0}^{n} {(\binom{n}{i})}^{2} = (\binom{2 n}{n}) .$

下面对这个结果进行估计. 根据 Stirling 公式，

\begin{matrix} n! \sim \sqrt{2 π n} {(\frac{n}{e})}^{n} = \sqrt{2 π} \frac{n^{n + 1 / 2}}{e^{n}}, \\ (2 n)! \sim 2 \sqrt{π n} \frac{(2 n)^{2 n}}{e^{2 n}} = \sqrt{π} 2^{2 n + 1} \frac{n^{2 n + 1 / 2}}{e^{2 n}}, \\ (\binom{2 n}{n}) = \frac{(2 n)!}{(n!)^{2}} \sim \frac{4^{n}}{\sqrt{π n}}, \\ \frac{1}{4^{2 n}} {(\binom{2 n}{n})}^{2} \sim \frac{1}{π n}, n \to \infty, \end{matrix}

所以

\sum_{n = 0}^{\infty} p_{00}^{(n)} = \sum_{n = 0}^{\infty} p_{00}^{(2 n)} \sim \sum_{n = 1}^{\infty} \frac{1}{π n} = \infty,

$i=0$ 是常返的，进而二维对称随机游动是常返的.

$\forall k\in\N$ ，

$n=2k+1$ 时，
$p_{00}^{(n)} = p_{00}^{(2 k + 1)} = 0;$
$n=2k$ 时，
$p_{00}^{(n)} = p_{00}^{(2 k)} = \frac{1}{4^{2 k}} {(\binom{2 k}{k})}^{2} \sim \frac{1}{π k} \to 0, k \to \infty .$

所以，

lim_{n \to \infty} p_{00}^{(n)} = 0,

即这个过程是零常返的.

2

证明：

首先证明

p_{i j}^{(n)} = \sum_{k = 1}^{n} f_{i j}^{(k)} p_{i j}^{(n - k)} .

观察到

\begin{matrix} p_{i j}^{(n)} = P (X_{m + n} = j | X_{m} = i), \\ f_{i j}^{(k)} = P (X_{m + k} = j, X_{m + v} \neq j, 1 ⩽ v ⩽ k - 1 | X_{m} = i), \\ p_{j j}^{(n - k)} = P (X_{m + n} = j | X_{m + k} = j) . \end{matrix}

设事件

\begin{matrix} A = {X_{m + n} = j}, \\ B = {X_{m} = i}, \\ C_{k} = {X_{m + v} \neq j, 1 ⩽ v ⩽ k - 1}, \\ D_{k} = {X_{m + k} = j}, \end{matrix}

$1\leqslant k\leqslant n$ .

于是

\begin{matrix} p_{i j}^{(n)} = P (X_{m + n} = j | X_{m} = i) = P (A | B), \\ f_{i j}^{(k)} = P (X_{m + k} = j, X_{m + v} \neq j, 1 ⩽ v ⩽ k - 1 | X_{m} = i) = P (C_{k} D_{k} | B), \\ p_{j j}^{(n - k)} = P (X_{m + n} = j | X_{m + k} = j) = P (A | D_{k}) . \end{matrix}

所以

\begin{aligned} p_{i j}^{(n)} & = P (A | B) \\ = \sum_{k = 1}^{n} P (A C_{k} D_{k} | B) \\ = \sum_{k = 1}^{n} \frac{P (A B C_{k} D_{k})}{P (B)} \\ = \sum_{k = 1}^{n} \frac{P (A B C_{k} D_{k})}{P (B C_{k} D_{k})} \frac{P (B C_{k} D_{k})}{P (B)} \\ = \sum_{k = 1}^{n} P (A | B C_{k} D_{k}) P (C_{k} D_{k} | B) \\ = \sum_{k = 1}^{n} P (X_{m + n} = j | X_{m} = i, X_{m + v} \neq j, X_{m + k} = j) P (X_{m + v} \neq j, X_{m + k} = j | X_{m} = i) (1 ⩽ v ⩽ k - 1) \\ = \sum_{k = 1}^{n} P (X_{m + n} = j | X_{m + k} = j) P (X_{m + v} \neq j, 1 ⩽ v ⩽ k - 1, X_{m + k} = j | X_{m} = i) & (马 氏 性) \\ = \sum_{k = 1}^{n} p_{j j}^{(n - k)} f_{i j}^{(k)} . \end{aligned}

再证明

p_{i j}^{(n)} = \sum_{k = 0}^{n} f_{i j}^{(n - k)} p_{j j}^{(k)} .

注意到

\begin{matrix} p_{i j}^{(n)} = P (X_{m + n} = j | X_{m} = i), \\ f_{i j}^{(n - k)} = P (X_{m + n - k} = j, X_{m + v} \neq j, 1 ⩽ v ⩽ n - k - 1 | X_{m} = i), \\ p_{j j}^{(k)} = P (X_{m + n} = j | X_{m + n - k} = j) . \end{matrix}

设事件

\begin{matrix} A = {X_{m + n} = j}, \\ B = {X_{m} = i}, \\ C_{k} = {X_{m + v} \neq j, 1 ⩽ v ⩽ n - k - 1}, \\ D_{k} = {X_{m + n - k} = j}, \end{matrix}

$k\geqslant 0$ .

于是

\begin{matrix} p_{i j}^{(n)} = P (X_{m + n} = j | X_{m} = i) = P (A | B), \\ f_{i j}^{(n - k)} = P (X_{m + n - k} = j, X_{m + v} \neq j, 1 ⩽ v ⩽ n - k - 1 | X_{m} = i) = P (C_{k} D_{k} | B), \\ p_{j j}^{(k)} = P (X_{m + n} = j | X_{m + n - k} = j) = P (A | D_{k}) . \end{matrix}

与前面类似，有

\begin{aligned} p_{i j}^{(n)} & = P (A | B) \\ = \dots \\ = \sum_{k = 0}^{n} P (A | B C_{k} D_{k}) P (C_{k} D_{k} | B) \\ = \sum_{k = 0}^{n} P (X_{m + n} = j | X_{m} = i, X_{m + v} \neq j, X_{m + n - k} = j) P (X_{m + v} \neq j, X_{m + n - k} = j | X_{m} = i), 1 ⩽ v ⩽ n - k - 1 \\ = \sum_{k = 0}^{n} P (X_{m + n} = j | X_{m + n - k} = j) P (X_{m + v} \neq j, 1 ⩽ v ⩽ n - k - 1, X_{m + n - k} = j | X_{m} = i) & (马 氏 性) \\ = \sum_{k = 0}^{n} p_{j j}^{(k)} f_{i j}^{(n - k)} . \end{aligned}

3

因为
$\sum_{n = 0}^{\infty} p_{00}^{(n)} = \sum_{n = 0}^{\infty} 1 = \infty,$
$0$ 是常返的.
又因为
$lim_{n \to \infty} p_{00}^{(n)} = 1 > 0,$
$0$ 是正常返的.
因为
$p_{11}^{(n)} = q^{n}, 0 < q < 1,$
所以
$\sum_{n = 0}^{\infty} p_{11}^{(n)} = \sum_{n = 0}^{\infty} q^{n} = \frac{1}{1 - q} < \infty,$
$1$ 是瞬过的（非常返的）.
因为
$\sum_{n = 0}^{\infty} p_{22}^{(n)} = \sum_{n = 0}^{\infty} 1 = \infty,$
$2$ 是常返的.
又因为
$lim_{n \to \infty} p_{22}^{(n)} = 1 > 0,$
$2$ 是正常返的.

易知

\begin{matrix} P^{(1)} = P = (\begin{matrix} 1 & 0 & 0 \\ p & q & r \\ 0 & 0 & 1 \end{matrix}), \\ P^{(2)} = P \cdot P^{(1)} = (\begin{matrix} 1 & 0 & 0 \\ p & q & r \\ 0 & 0 & 1 \end{matrix}) (\begin{matrix} 1 & 0 & 0 \\ p & q & r \\ 0 & 0 & 1 \end{matrix}) = (\begin{matrix} 1 & 0 & 0 \\ p + p q & q & q r + r \\ 0 & 0 & 1 \end{matrix}) = (\begin{matrix} 1 & 0 & 0 \\ p (1 + q) & q^{2} & r (1 + q) \\ 0 & 0 & 1 \end{matrix}) . \end{matrix}

猜想

\begin{matrix} P^{(n)} = (\begin{matrix} 1 & 0 & 0 \\ p Q (n) & q^{n} & r Q (n) \\ 0 & 0 & 1 \end{matrix}), \end{matrix}

$Q(n)=1+q+\cdots+q^{n-1}$ . 用归纳法证明.

$n=1,2$ 时，假设成立；
$n=k,k\in \N^*$ 时，假设成立，即
$\begin{matrix} P^{(k)} = (\begin{matrix} 1 & 0 & 0 \\ p Q (k) & q^{k} & r Q (k) \\ 0 & 0 & 1 \end{matrix}), \end{matrix}$
$Q(k)=1+q+\cdots+q^{k-1}$ $n=k+1$ 时，
$\begin{matrix} P^{(k + 1)} = P \cdot P^{(k)} = (\begin{matrix} 1 & 0 & 0 \\ p & q & r \\ 0 & 0 & 1 \end{matrix}) (\begin{matrix} 1 & 0 & 0 \\ p Q (k) & q^{k} & r Q (k) \\ 0 & 0 & 1 \end{matrix}) = (\begin{matrix} 1 & 0 & 0 \\ p + p q Q (k) & q^{k + 1} & r + r q Q (k) \\ 0 & 0 & 1 \end{matrix}), \end{matrix}$
其中
$\begin{matrix} p + p q Q (k) = p (1 + q Q (k)) = p (1 + q + q^{2} + \dots + q^{k}) = p Q (k + 1), \\ r + r q Q (k) = r (1 + q Q (k)) = r (1 + q + q^{2} + \dots + q^{k}) = r Q (k + 1), \end{matrix}$
所以
$\begin{matrix} P^{(k + 1)} = (\begin{matrix} 1 & 0 & 0 \\ p + p q Q (k) & q^{k + 1} & r + r q Q (k) \\ 0 & 0 & 1 \end{matrix}) = (\begin{matrix} 1 & 0 & 0 \\ p Q (k + 1) & q^{k + 1} & r Q (k + 1) \\ 0 & 0 & 1 \end{matrix}), \end{matrix}$
假设仍然成立.

所以

\begin{matrix} P^{(n)} = (\begin{matrix} 1 & 0 & 0 \\ p Q (n) & q^{n} & r Q (n) \\ 0 & 0 & 1 \end{matrix}), \forall n \in N^{*}, \end{matrix}

其中

Q (n) = 1 + q + \dots + q^{n - 1} = \sum_{i = 0}^{n - 1} q^{i} \to \frac{1}{1 - q}, n \to \infty .

所求极限为

\begin{matrix} P^{(n)} = (\begin{matrix} 1 & 0 & 0 \\ p Q (n) & q^{n} & r Q (n) \\ 0 & 0 & 1 \end{matrix}) \to (\begin{matrix} 1 & 0 & 0 \\ \frac{p}{1 - q} & 0 & \frac{r}{1 - q} \\ 0 & 0 & 1 \end{matrix}), n \to \infty . \end{matrix}

$1-q=p+r$ ，所以这个极限也可以表示为

(\begin{matrix} 1 & 0 & 0 \\ \frac{p}{p + r} & 0 & \frac{r}{p + r} \\ 0 & 0 & 1 \end{matrix}) .