为什么需要新的刻画?
上一节先在有限区间上求解赌徒破产问题,再对事件取极限,从而计算无限空间上的到达概率。那个方法依赖每步只走到相邻状态的几何结构。本节给出一个更一般的方法,适用于任意有限或可数状态空间。
到达概率和平均到达时间都满足首步方程,但这些方程往往有多个解。在所有非负解之中,相应的概率量总是最小的。因此,确定到达概率的是解之间的大小关系,而非解的唯一性。这两个方面同样重要。
设定与约定
设 S S S 为有限或可数集合,P = ( P i j ) i , j ∈ S P=(P_{ij})_{i,j\in S} P = ( P ij ) i , j ∈ S 满足 P i j ≥ 0 P_{ij}\ge 0 P ij ≥ 0 ,且对每个 i i i 都有 ∑ j P i j = 1 \sum\limits_j P_{ij}=1 j ∑ P ij = 1 。令 ( X n ) n ≥ 0 (X_n)_{n\ge0} ( X n ) n ≥ 0 为具有这些转移概率的马尔可夫(Markov)链,以 P i , E i P_i,E_i P i , E i 表示从 X 0 = i X_0=i X 0 = i 出发的概率和期望。固定非空集合 A ⊆ S A\subseteq S A ⊆ S ,定义
T A = inf { n ≥ 0 : X n ∈ A } , inf ∅ = + ∞ . T_A=\inf\{n\ge 0: X_n\in A\},\qquad \inf\emptyset=+\infty . T A = inf { n ≥ 0 : X n ∈ A } , inf ∅ = + ∞.
因此 T A T_A T A 的取值属于 { 0 , 1 , 2 , … } ∪ { + ∞ } \{0,1,2,\dots\}\cup\{+\infty\} { 0 , 1 , 2 , … } ∪ { + ∞ } ,且恰在 X 0 ∈ A X_0\in A X 0 ∈ A 时 T A = 0 T_A=0 T A = 0 。定义
h i = P i ( T A < ∞ ) , m i = E i [ T A ] ∈ [ 0 , ∞ ] . h_i=P_i(T_A<\infty),\qquad m_i=E_i[T_A]\in[0,\infty]. h i = P i ( T A < ∞ ) , m i = E i [ T A ] ∈ [ 0 , ∞ ] .
取值于 [ 0 , ∞ ] [0,\infty] [ 0 , ∞ ] 的随机变量的期望总有定义。特别地,若 P i ( T A = ∞ ) > 0 P_i(T_A=\infty)>0 P i ( T A = ∞ ) > 0 ,则 m i = ∞ m_i=\infty m i = ∞ 。我们不预先假设到达时间有限。
广义运算。 在 [ 0 , ∞ ] [0,\infty] [ 0 , ∞ ] 上约定 a + ∞ = ∞ a+\infty=\infty a + ∞ = ∞ 、当 c > 0 c>0 c > 0 时 c ⋅ ∞ = ∞ c\cdot\infty=\infty c ⋅ ∞ = ∞ ,以及 0 ⋅ ∞ = 0 0\cdot\infty=0 0 ⋅ ∞ = 0 。对非负广义数 a j a_j a j ,和 ∑ j a j \sum\limits_j a_j j ∑ a j 定义为其有限部分和的上确界。这个和不依赖于 S S S 的枚举次序,并且对每一项单调。它还满足单调收敛:若对每个 j j j 都有 a j ( n ) ↑ a j a^{(n)}_j\uparrow a_j a j ( n ) ↑ a j ,则 ∑ j a j ( n ) ↑ ∑ j a j \sum\limits_j a^{(n)}_j\uparrow\sum\limits_j a_j j ∑ a j ( n ) ↑ j ∑ a j 。
约定 0 ⋅ ∞ = 0 0\cdot\infty=0 0 ⋅ ∞ = 0 恰好使得 c = 0 c=0 c = 0 时仍有 c a ( n ) ↑ c a c\,a^{(n)}\uparrow c\,a c a ( n ) ↑ c a 。它也有概率意义:链不可能跳到的状态不作贡献。例如,取 S = { 0 , 1 , 2 } S=\{0,1,2\} S = { 0 , 1 , 2 } 、A = { 0 } A=\{0\} A = { 0 } ,且 P 00 = P 10 = P 22 = 1 P_{00}=P_{10}=P_{22}=1 P 00 = P 10 = P 22 = 1 。则 m 2 = ∞ m_2=\infty m 2 = ∞ 而 m 1 = 1 m_1=1 m 1 = 1 。首步方程
m 1 = 1 + P 10 m 0 + P 12 m 2 = 1 + 0 + 0 ⋅ ∞ m_1=1+P_{10}m_0+P_{12}m_2=1+0+0\cdot\infty m 1 = 1 + P 10 m 0 + P 12 m 2 = 1 + 0 + 0 ⋅ ∞
只有在上述约定下才成立。
首步分解。 若 X 0 ∉ A X_0\notin A X 0 ∈ / A ,则 T A ≥ 1 T_A\ge1 T A ≥ 1 且 T A = 1 + T A ∘ θ 1 T_A=1+T_A\circ\theta_1 T A = 1 + T A ∘ θ 1 。这里 T A ∘ θ 1 T_A\circ\theta_1 T A ∘ θ 1 是平移后路径 ( X n + 1 ) n ≥ 0 (X_{n+1})_{n\ge0} ( X n + 1 ) n ≥ 0 的到达时间。时间一的马尔可夫性质给出
P i ( T A ∘ θ 1 ∈ B ) = ∑ j P i j P j ( T A ∈ B ) , P_i(T_A\circ\theta_1\in B)=\sum_j P_{ij}P_j(T_A\in B), P i ( T A ∘ θ 1 ∈ B ) = j ∑ P ij P j ( T A ∈ B ) ,
对 T A ∘ θ 1 T_A\circ\theta_1 T A ∘ θ 1 的非负函数取期望,也有相同形式的等式。
到达概率是最小非负解
对 g : S → [ 0 , ∞ ] g:S\to[0,\infty] g : S → [ 0 , ∞ ] ,定义
( Φ g ) i = { 1 , i ∈ A , ∑ j P i j g j , i ∉ A . (\Phi g)_i=\begin{cases}1,&i\in A,\\ \sum_j P_{ij}g_j,&i\notin A.\end{cases} ( Φ g ) i = { 1 , ∑ j P ij g j , i ∈ A , i ∈ / A .
到达方程组 (H) 的解是满足 g = Φ g g=\Phi g g = Φ g 的函数。等价地,函数 g g g 满足 g = 1 g=1 g = 1 在 A A A 上成立,在 A A A 之外满足 g i = ∑ j P i j g j g_i=\sum\limits_jP_{ij}g_j g i = j ∑ P ij g j 。
函数 h i = P i ( T A < ∞ ) h_i=P_i(T_A<\infty) h i = P i ( T A < ∞ ) 是 (H) 的非负解。任何非负解 g g g 都满足对每个 i ∈ S i\in S i ∈ S ,g i ≥ h i g_i\ge h_i g i ≥ h i 。
此外,令 h i ( n ) = P i ( T A ≤ n ) h^{(n)}_i=P_i(T_A\le n) h i ( n ) = P i ( T A ≤ n ) ,则 h ( 0 ) = 1 A h^{(0)}=\mathbf 1_A h ( 0 ) = 1 A 、h ( n + 1 ) = Φ h ( n ) h^{(n+1)}=\Phi h^{(n)} h ( n + 1 ) = Φ h ( n ) ,并且对每个 i i i 有 h i ( n ) ↑ h i h^{(n)}_i\uparrow h_i h i ( n ) ↑ h i 。
有限时域。 有 h i ( 0 ) = P i ( T A = 0 ) = 1 A ( i ) h^{(0)}_i=P_i(T_A=0)=\mathbf 1_A(i) h i ( 0 ) = P i ( T A = 0 ) = 1 A ( i ) 。
若 i ∈ A i\in A i ∈ A ,则 h i ( n + 1 ) = 1 h^{(n+1)}_i=1 h i ( n + 1 ) = 1 。
若 i ∉ A i\notin A i ∈ / A ,则 { T A ≤ n + 1 } = { T A ∘ θ 1 ≤ n } \{T_A\le n+1\}=\{T_A\circ\theta_1\le n\} { T A ≤ n + 1 } = { T A ∘ θ 1 ≤ n } 。马尔可夫性质给出 h i ( n + 1 ) = ∑ j P i j h j ( n ) h^{(n+1)}_i=\sum\limits_jP_{ij}h^{(n)}_j h i ( n + 1 ) = j ∑ P ij h j ( n ) 。
因此 h ( n + 1 ) = Φ h ( n ) h^{(n+1)}=\Phi h^{(n)} h ( n + 1 ) = Φ h ( n ) 。
取极限。 事件 { T A ≤ n } \{T_A\le n\} { T A ≤ n } 递增,其并集为 { T A < ∞ } \{T_A<\infty\} { T A < ∞ } 。由概率的下连续性,h i ( n ) ↑ h i h^{(n)}_i\uparrow h_i h i ( n ) ↑ h i 。对递推式 h ( n + 1 ) = Φ h ( n ) h^{(n+1)}=\Phi h^{(n)} h ( n + 1 ) = Φ h ( n ) 使用级数的单调收敛,得到 h = Φ h h=\Phi h h = Φ h ,所以 h h h 解 (H)。
最小性。 算子 Φ \Phi Φ 单调:若逐点有 g ≤ g ′ g\le g' g ≤ g ′ ,则由于所有系数 P i j P_{ij} P ij 非负,Φ g ≤ Φ g ′ \Phi g\le\Phi g' Φ g ≤ Φ g ′ 。设 g ≥ 0 g\ge0 g ≥ 0 且 g = Φ g g=\Phi g g = Φ g 。
因为 g = 1 g=1 g = 1 在 A A A 上成立,且 g ≥ 0 g\ge0 g ≥ 0 在 A A A 外成立,故 g ≥ 1 A = h ( 0 ) g\ge\mathbf 1_A=h^{(0)} g ≥ 1 A = h ( 0 ) 。
若 g ≥ h ( n ) g\ge h^{(n)} g ≥ h ( n ) ,则 g = Φ g ≥ Φ h ( n ) = h ( n + 1 ) g=\Phi g\ge\Phi h^{(n)}=h^{(n+1)} g = Φ g ≥ Φ h ( n ) = h ( n + 1 ) 。
归纳可得对每个 n n n 都有 g ≥ h ( n ) g\ge h^{(n)} g ≥ h ( n ) 。令 n → ∞ n\to\infty n → ∞ ,得到 g ≥ h g\ge h g ≥ h 。
证明透视
哪个假设负责哪一步 证明分三个阶段,每个阶段用到不同的成分。有限时域的递推用到时间一的马尔可夫性质,以及 T A T_A T A 把时间 0 0 0 计算在内的约定:在 A A A 上每个迭代值都等于一。取极限只用到事件 { T A ≤ n } \{T_A\le n\} { T A ≤ n } 递增,因此不需要任何有限性或唯一性假设。
不明显的是最小性这一步。系数非负使 Φ \Phi Φ 单调;比较对象 g g g 需要两条性质才能开始归纳:在 A A A 上 g = 1 g=1 g = 1 ,在 A A A 外 g ≥ 0 g\ge0 g ≥ 0 ,两者合起来给出 g ≥ 1 A g\ge\mathbf 1_A g ≥ 1 A 。带符号的解可以低于 h h h ;在下面的向上游走中,a < 0 a\lt 0 a < 0 时的 3 − i + a ( 1 − 3 − i ) 3^{-i}+a(1-3^{-i}) 3 − i + a ( 1 − 3 − i ) 就是一例。所以比较只在非负解之间进行。
迭代值 h ( n ) h^{(n)} h ( n ) 只计算在 n n n 步内到达 A A A 的路径。另一个解可以给逃向无穷远、或一直留在与 A A A 不相交的封闭集内的路径赋予正值;局部平均方程无法察觉这一点,而从 1 A \mathbf 1_A 1 A 开始的迭代绝不会引入它。改从 1 \mathbf 1 1 开始迭代没有帮助,因为 Φ 1 = 1 \Phi\mathbf 1=\mathbf 1 Φ 1 = 1 。
边界条件。 A A A 上的条件 g = 1 g=1 g = 1 表示从 A A A 内出发的链在时间 0 0 0 已经到达 A A A ,这也是用 n ≥ 0 n\ge0 n ≥ 0 定义 T A T_A T A 的原因。我们不在 A A A 上施加平均方程。若没有边界条件,g ≡ 0 g\equiv0 g ≡ 0 会在所有状态满足平均方程,却不携带到达信息。
最小不等于唯一
P P P 的每行之和为一,所以 1 \mathbf 1 1 总是 (H) 的解。因此,只要某个 h i < 1 h_i<1 h i < 1 ,(H) 就至少有两个有界非负解。仅凭首步方程无法确定 h h h 。
反例模式
具有连续无穷多个解的有限链 令 S = { 0 , 1 , 2 } S=\{0,1,2\} S = { 0 , 1 , 2 } 、A = { 0 } A=\{0\} A = { 0 } ,并设 P 00 = 1 P_{00}=1 P 00 = 1 、P 10 = P 12 = 1 2 P_{10}=P_{12}=\tfrac12 P 10 = P 12 = 2 1 、P 22 = 1 P_{22}=1 P 22 = 1 。方程组 (H) 为
g 0 = 1 , g 1 = 1 2 + 1 2 g 2 , g 2 = g 2 . g_0=1,\qquad g_1=\tfrac12+\tfrac12g_2,\qquad g_2=g_2 . g 0 = 1 , g 1 = 2 1 + 2 1 g 2 , g 2 = g 2 . 每个 c ∈ [ 0 , ∞ ) c\in[0,\infty) c ∈ [ 0 , ∞ ) 都给出一个解 ( 1 , 1 + c 2 , c ) (1,\tfrac{1+c}2,c) ( 1 , 2 1 + c , c ) 。最小解对应 c = 0 c=0 c = 0 ,即 h = ( 1 , 1 2 , 0 ) h=(1,\tfrac12,0) h = ( 1 , 2 1 , 0 ) 。这与直接计算一致:从 1 1 1 出发时,第一步就决定了是否到达 0 0 0 。
把 A A A 外的未知数写成 ( g 1 , g 2 ) (g_1,g_2) ( g 1 , g 2 ) ,方程组变为 ( I − Q ) g = b (I-Q)g=b ( I − Q ) g = b ,其中
Q = ( 0 1 2 0 1 ) , b = ( 1 2 0 ) . Q=\begin{pmatrix}0&\tfrac12\\0&1\end{pmatrix},\qquad b=\begin{pmatrix}\tfrac12\\0\end{pmatrix}. Q = ( 0 0 2 1 1 ) , b = ( 2 1 0 ) . 这里 I − Q I-Q I − Q 的第二行全为零,故它是奇异矩阵。有限状态空间不保证存在逆矩阵;在无限空间上不能自动套用有限维求逆论证;作为算子的可逆性需要另行假设。
增加假设后,可以在受限的函数类中恢复唯一性。
定理 16.1.2
(几乎必然到达时的有界解唯一性)
若对每个 i i i 都有 h i = 1 h_i=1 h i = 1 ,则 (H) 唯一的有界实值解为 1 \mathbf 1 1 。
设 g g g 是有界解,令 d = g − 1 d=g-\mathbf 1 d = g − 1 。则对某个 K K K 有 ∣ d ∣ ≤ K |d|\le K ∣ d ∣ ≤ K ,且 d = 0 d=0 d = 0 在 A A A 上成立、在 A A A 外满足 d i = ∑ j P i j d j d_i=\sum\limits_jP_{ij}d_j d i = j ∑ P ij d j 。我们证明
d i = E i [ d ( X n ) ; T A > n ] 对所有 n ≥ 0. d_i=E_i[d(X_n);T_A>n]\quad\text{对所有 } n\ge0 . d i = E i [ d ( X n ) ; T A > n ] 对所有 n ≥ 0. 初始情形 n = 0 n=0 n = 0 。 若 i ∈ A i\in A i ∈ A ,事件 { T A > 0 } \{T_A>0\} { T A > 0 } 为空且 d i = 0 d_i=0 d i = 0 ;若 i ∉ A i\notin A i ∈ / A ,该事件必然发生。
归纳步骤。 在 { T A > n } \{T_A>n\} { T A > n } 上有 X n ∉ A X_n\notin A X n ∈ / A 。该事件由 X 0 , … , X n X_0,\dots,X_n X 0 , … , X n 决定。时间 n n n 的马尔可夫性质给出
E i [ d ( X n ) ; T A > n ] = E i [ ∑ k P X n k d k ; T A > n ] = E i [ d ( X n + 1 ) ; T A > n ] . E_i[d(X_n);T_A>n]=E_i\Big[\sum_kP_{X_nk}d_k;\,T_A>n\Big]=E_i[d(X_{n+1});T_A>n]. E i [ d ( X n ) ; T A > n ] = E i [ k ∑ P X n k d k ; T A > n ] = E i [ d ( X n + 1 ) ; T A > n ] . 只要 X n + 1 ∈ A X_{n+1}\in A X n + 1 ∈ A 就有 d ( X n + 1 ) = 0 d(X_{n+1})=0 d ( X n + 1 ) = 0 ,因此右边等于 E i [ d ( X n + 1 ) ; T A > n + 1 ] E_i[d(X_{n+1});T_A>n+1] E i [ d ( X n + 1 ) ; T A > n + 1 ] 。归纳式得证。
于是对每个 n n n 有 ∣ d i ∣ ≤ K P i ( T A > n ) |d_i|\le K\,P_i(T_A>n) ∣ d i ∣ ≤ K P i ( T A > n ) 。当 n → ∞ n\to\infty n → ∞ ,这个上界趋于 K P i ( T A = ∞ ) = 0 K\,P_i(T_A=\infty)=0 K P i ( T A = ∞ ) = 0 。故 d = 0 d=0 d = 0 。
证明透视
有界性与几乎必然到达在哪里起作用 证明从不直接把 g g g 与 1 \mathbf 1 1 比较。关键一步是表示式 d i = E i [ d ( X n ) ; T A > n ] d_i=E_i[d(X_n);T_A>n] d i = E i [ d ( X n ) ; T A > n ] :平均方程沿着尚未到达 A A A 的路径把 d d d 向前传递,而 A A A 上的边界条件 d = 0 d=0 d = 0 在每条路径的到达时刻把它去掉。有界性把这个恒等式化为估计 ∣ d i ∣ ≤ K P i ( T A > n ) |d_i|\le K\,P_i(T_A>n) ∣ d i ∣ ≤ K P i ( T A > n ) ,几乎必然到达再使这个估计趋于零。没有有界性,恒等式依然成立,却推不出任何结论:在下面的向下漂移例子中,d i = b ( 3 i − 1 ) d_i=b(3^i-1) d i = b ( 3 i − 1 ) 是非零的差,尽管 P i ( T A > n ) → 0 P_i(T_A>n)\to0 P i ( T A > n ) → 0 。
两个假设都重要。若不是几乎必然到达,则 1 \mathbf 1 1 与 h h h 不同;若不要求有界,仍可能存在无界非负解,如第二个例子所示。
平均到达时间是最小广义非负解
对 g : S → [ 0 , ∞ ] g:S\to[0,\infty] g : S → [ 0 , ∞ ] ,依照上述广义运算约定定义
( Ψ g ) i = { 0 , i ∈ A , 1 + ∑ j P i j g j , i ∉ A , (\Psi g)_i=\begin{cases}0,&i\in A,\\ 1+\sum_jP_{ij}g_j,&i\notin A,\end{cases} ( Ψ g ) i = { 0 , 1 + ∑ j P ij g j , i ∈ A , i ∈ / A ,
方程组 (M) 即 g = Ψ g g=\Psi g g = Ψ g 。
函数 m i = E i [ T A ] ∈ [ 0 , ∞ ] m_i=E_i[T_A]\in[0,\infty] m i = E i [ T A ] ∈ [ 0 , ∞ ] 解 (M)。任何解 g : S → [ 0 , ∞ ] g:S\to[0,\infty] g : S → [ 0 , ∞ ] 都满足 g ≥ m g\ge m g ≥ m 。
令 m i ( n ) = E i [ T A ∧ n ] m^{(n)}_i=E_i[T_A\wedge n] m i ( n ) = E i [ T A ∧ n ] ,则 m ( 0 ) = 0 m^{(0)}=0 m ( 0 ) = 0 、m ( n + 1 ) = Ψ m ( n ) m^{(n+1)}=\Psi m^{(n)} m ( n + 1 ) = Ψ m ( n ) ,且 m i ( n ) ↑ m i m^{(n)}_i\uparrow m_i m i ( n ) ↑ m i 。
有限时域。 显然 m ( 0 ) = 0 m^{(0)}=0 m ( 0 ) = 0 。
若 i ∈ A i\in A i ∈ A ,则 T A ∧ n = 0 T_A\wedge n=0 T A ∧ n = 0 ,故 m i ( n ) = 0 m^{(n)}_i=0 m i ( n ) = 0 。
若 i ∉ A i\notin A i ∈ / A ,则 T A ∧ ( n + 1 ) = ( 1 + T A ∘ θ 1 ) ∧ ( n + 1 ) = 1 + ( T A ∘ θ 1 ∧ n ) T_A\wedge(n+1)=(1+T_A\circ\theta_1)\wedge(n+1)=1+(T_A\circ\theta_1\wedge n) T A ∧ ( n + 1 ) = ( 1 + T A ∘ θ 1 ) ∧ ( n + 1 ) = 1 + ( T A ∘ θ 1 ∧ n ) 。这是平移路径的有界函数。马尔可夫性质给出 m i ( n + 1 ) = 1 + ∑ j P i j m j ( n ) m^{(n+1)}_i=1+\sum\limits_jP_{ij}m^{(n)}_j m i ( n + 1 ) = 1 + j ∑ P ij m j ( n ) 。
每个 m ( n ) m^{(n)} m ( n ) 都有限,且以 n n n 为上界。
取极限。 对每条路径,T A ∧ n ↑ T A T_A\wedge n\uparrow T_A T A ∧ n ↑ T A ,极限取于 [ 0 , ∞ ] [0,\infty] [ 0 , ∞ ] ;这也包括 T A = ∞ T_A=\infty T A = ∞ 的路径,此时 T A ∧ n = n ↑ ∞ T_A\wedge n=n\uparrow\infty T A ∧ n = n ↑ ∞ 。由单调收敛定理,m i ( n ) ↑ m i m^{(n)}_i\uparrow m_i m i ( n ) ↑ m i 。在递推式中取极限,使用级数的单调收敛及 0 ⋅ ∞ = 0 0\cdot\infty=0 0 ⋅ ∞ = 0 ,便得 m = Ψ m m=\Psi m m = Ψ m 。这样无需假设平均时间有限,就推导出了均值的首步方程。
最小性。 算子 Ψ \Psi Ψ 单调。任何解 g g g 都满足 g ≥ 0 = m ( 0 ) g\ge0=m^{(0)} g ≥ 0 = m ( 0 ) 。若 g ≥ m ( n ) g\ge m^{(n)} g ≥ m ( n ) ,则 g = Ψ g ≥ Ψ m ( n ) = m ( n + 1 ) g=\Psi g\ge\Psi m^{(n)}=m^{(n+1)} g = Ψ g ≥ Ψ m ( n ) = m ( n + 1 ) 。因此 g ≥ m g\ge m g ≥ m 。
等价地,m i = ∑ k ≥ 0 P i ( T A > k ) m_i=\sum\limits_{k\ge0}P_i(T_A>k) m i = k ≥ 0 ∑ P i ( T A > k ) ;这是 ∑ k < n P i ( T A > k ) = m i ( n ) \sum\limits_{k<n}P_i(T_A>k)=m^{(n)}_i k < n ∑ P i ( T A > k ) = m i ( n ) 的尾和形式。
概念视角 代数
目标以外状态上的诺伊曼(Neumann)级数 令 Q = ( P i j ) i , j ∉ A Q=(P_{ij})_{i,j\notin A} Q = ( P ij ) i , j ∈ / A ,并对 i ∉ A i\notin A i ∈ / A 令 b i = P i ( X 1 ∈ A ) b_i=P_i(X_1\in A) b i = P i ( X 1 ∈ A ) 。在 A A A 以外,迭代写成 h ( n + 1 ) = b + Q h ( n ) h^{(n+1)}=b+Qh^{(n)} h ( n + 1 ) = b + Q h ( n ) (h ( 0 ) = 0 h^{(0)}=0 h ( 0 ) = 0 )以及 m ( n + 1 ) = 1 + Q m ( n ) m^{(n+1)}=\mathbf 1+Qm^{(n)} m ( n + 1 ) = 1 + Q m ( n ) 。因此在 A A A 以外,
h = ∑ k ≥ 0 Q k b , m = ∑ k ≥ 0 Q k 1 , ( Q k 1 ) i = P i ( T A > k ) . h=\sum_{k\ge0}Q^kb,\qquad m=\sum_{k\ge0}Q^k\mathbf 1,\qquad (Q^k\mathbf 1)_i=P_i(T_A>k). h = k ≥ 0 ∑ Q k b , m = k ≥ 0 ∑ Q k 1 , ( Q k 1 ) i = P i ( T A > k ) . 这些非负级数的和总在 [ 0 , ∞ ] [0,\infty] [ 0 , ∞ ] 中。即使 I − Q I-Q I − Q 奇异,它们仍然起着 ( I − Q ) − 1 b (I-Q)^{-1}b ( I − Q ) − 1 b 与 ( I − Q ) − 1 1 (I-Q)^{-1}\mathbf 1 ( I − Q ) − 1 1 的作用:在三状态链中,∑ k Q k b = ( 1 2 , 0 ) \sum\limits_kQ^kb=(\tfrac12,0) k ∑ Q k b = ( 2 1 , 0 ) 。
方程组 (M) 也有虚假解。假设每个 i ∉ A i\notin A i ∈ / A 都有某个 j ∉ A j\notin A j ∈ / A 满足 P i j > 0 P_{ij}>0 P ij > 0 ,则在 A A A 上等于 0 0 0 、在 A A A 外等于 ∞ \infty ∞ 的函数解 (M)。真正的平均时间仍可能有限;排除这个无穷候选解要依靠最小性。另请注意,m i < ∞ m_i<\infty m i < ∞ 必然推出 h i = 1 h_i=1 h i = 1 ,但反过来不成立。
例题
例题 16.1.4
(向上漂移:到达概率为 ( 1 / 3 ) i (1/3)^i ( 1/3 ) i ,平均时间无限)
令 S = { 0 , 1 , 2 , … } S=\{0,1,2,\dots\} S = { 0 , 1 , 2 , … } ,P 00 = 1 P_{00}=1 P 00 = 1 ,且对 i ≥ 1 i\ge1 i ≥ 1 令 P i , i + 1 = 3 4 P_{i,i+1}=\tfrac34 P i , i + 1 = 4 3 、P i , i − 1 = 1 4 P_{i,i-1}=\tfrac14 P i , i − 1 = 4 1 。取 A = { 0 } A=\{0\} A = { 0 } 。
有限边界。 对 N ≥ 2 N\ge2 N ≥ 2 、0 ≤ i ≤ N 0\le i\le N 0 ≤ i ≤ N ,令 u i N = P i ( T 0 < T N ) u^N_i=P_i(T_0<T_N) u i N = P i ( T 0 < T N ) 。由于 T 0 = 0 < T N T_0=0<T_N T 0 = 0 < T N ,有 u 0 N = 1 u^N_0=1 u 0 N = 1 ;由于 T N = 0 T_N=0 T N = 0 ,有 u N N = 0 u^N_N=0 u N N = 0 。当 0 < i < N 0<i<N 0 < i < N 时,两个到达时间都至少为 1 1 1 ,首步分析给出 u i = 3 4 u i + 1 + 1 4 u i − 1 u_i=\tfrac34u_{i+1}+\tfrac14u_{i-1} u i = 4 3 u i + 1 + 4 1 u i − 1 。
特征方程 3 4 λ 2 − λ + 1 4 = 0 \tfrac34\lambda^2-\lambda+\tfrac14=0 4 3 λ 2 − λ + 4 1 = 0 即 ( 3 λ − 1 ) ( λ − 1 ) = 0 (3\lambda-1)(\lambda-1)=0 ( 3 λ − 1 ) ( λ − 1 ) = 0 。二阶递推由前两项确定,故每个解形如 a + b 3 − i a+b\,3^{-i} a + b 3 − i 。边界条件为
a + b = 1 , a + b 3 − N = 0. a+b=1,\qquad a+b\,3^{-N}=0 . a + b = 1 , a + b 3 − N = 0. 其行列式 3 − N − 1 ≠ 0 3^{-N}-1\ne0 3 − N − 1 = 0 ,因此解唯一:
u i N = 3 − i − 3 − N 1 − 3 − N . u^N_i=\frac{3^{-i}-3^{-N}}{1-3^{-N}}. u i N = 1 − 3 − N 3 − i − 3 − N . 事件的极限。 固定 i ≥ 1 i\ge1 i ≥ 1 并取 N > i N>i N > i 。在 { T 0 < T N } \{T_0<T_N\} { T 0 < T N } 上,路径在 T 0 T_0 T 0 之前一直低于 N N N ,因此不可能先到达 N + 1 N+1 N + 1 。故 { T 0 < T N } ⊆ { T 0 < T N + 1 } \{T_0<T_N\}\subseteq\{T_0<T_{N+1}\} { T 0 < T N } ⊆ { T 0 < T N + 1 } ,这些事件递增。
它们的并集是 { T 0 < ∞ } \{T_0<\infty\} { T 0 < ∞ } 。一方面,严格不等式 T 0 < T N T_0<T_N T 0 < T N 迫使 T 0 T_0 T 0 有限;另一方面,若 T 0 < ∞ T_0<\infty T 0 < ∞ ,则 T 0 T_0 T 0 之前的路径有有限最大值 M M M ,当 N > M N>M N > M 时便有 T 0 < T N T_0<T_N T 0 < T N 。由下连续性,
h i = lim N → ∞ u i N = 3 − i . h_i=\lim_{N\to\infty}u^N_i=3^{-i}. h i = N → ∞ lim u i N = 3 − i . 特别地,h 1 = 1 3 h_1=\tfrac13 h 1 = 3 1 、h 2 = 1 9 h_2=\tfrac19 h 2 = 9 1 。这里没有使用无限时域的可选停止定理。
用最小性核对。 (H) 的每个有限值解都形如 h i ( a ) = a + ( 1 − a ) 3 − i = 3 − i + a ( 1 − 3 − i ) h_i(a)=a+(1-a)3^{-i}=3^{-i}+a(1-3^{-i}) h i ( a ) = a + ( 1 − a ) 3 − i = 3 − i + a ( 1 − 3 − i ) 。这样的解恰在 a ≥ 0 a\ge0 a ≥ 0 时非负:
若 a < 0 a<0 a < 0 ,各值趋于 a < 0 a<0 a < 0 ;
若 0 ≤ a ≤ 1 0\le a\le1 0 ≤ a ≤ 1 ,每个值都是 1 1 1 与 3 − i 3^{-i} 3 − i 的凸组合;
若 a > 1 a>1 a > 1 ,每个值都至少为 1 1 1 。
由于 h i ( a ) h_i(a) h i ( a ) 随 a a a 递增,最小非负有限值解对应 a = 0 a=0 a = 0 ,与事件极限一致。另一个广义解在 0 0 0 处为 1 1 1 、所有正状态处为 ∞ \infty ∞ ,它更大。取 a = 1 a=1 a = 1 得到有界常数解 1 \mathbf 1 1 ,它不是到达概率。
均值。 对 i ≥ 1 i\ge1 i ≥ 1 ,P i ( T 0 = ∞ ) = 1 − 3 − i > 0 P_i(T_0=\infty)=1-3^{-i}>0 P i ( T 0 = ∞ ) = 1 − 3 − i > 0 ,故 E i [ T 0 ] = ∞ E_i[T_0]=\infty E i [ T 0 ] = ∞ 。把这与 (M) 比较。特解 c i ci c i 要求 0 = 1 + c ( 3 4 − 1 4 ) 0=1+c(\tfrac34-\tfrac14) 0 = 1 + c ( 4 3 − 4 1 ) ,故 c = − 2 c=-2 c = − 2 。因此满足 g 0 = 0 g_0=0 g 0 = 0 的每个有限解形如 − 2 i + A ( 1 − 3 − i ) -2i+A(1-3^{-i}) − 2 i + A ( 1 − 3 − i ) ,最终必为负。
若某个 i ≥ 1 i\ge1 i ≥ 1 有 g i = ∞ g_i=\infty g i = ∞ ,由于相应转移系数均为正,相邻正状态处的方程也迫使这些状态的值为无穷。这会传播到所有正状态;边界值仍为 g 0 = 0 g_0=0 g 0 = 0 。故唯一的广义非负解为 ( 0 , ∞ , ∞ , … ) (0,\infty,\infty,\dots) ( 0 , ∞ , ∞ , … ) 。在这里 (M) 有唯一非负解,(H) 却有连续无穷多个解。
例题 16.1.5
(向下漂移:几乎必然到达且平均时间为 2 i 2i 2 i )
现在设 i ≥ 1 i\ge1 i ≥ 1 时 P i , i + 1 = 1 4 P_{i,i+1}=\tfrac14 P i , i + 1 = 4 1 、P i , i − 1 = 3 4 P_{i,i-1}=\tfrac34 P i , i − 1 = 4 3 ,且 P 00 = 1 P_{00}=1 P 00 = 1 。特征根为 1 1 1 和 3 3 3 。
到达方程组。 (H) 的有限值解为 1 + b ( 3 i − 1 ) 1+b(3^i-1) 1 + b ( 3 i − 1 ) 。这样的解只有在 b ≥ 0 b\ge0 b ≥ 0 时才非负,因为负的 b b b 会使值趋于 − ∞ -\infty − ∞ 。在 0 0 0 处为 1 1 1 、所有正状态处为 ∞ \infty ∞ 的广义解更大。最小解对应 b = 0 b=0 b = 0 ,故 h ≡ 1 h\equiv1 h ≡ 1 。由有界解唯一性定理,1 \mathbf 1 1 是唯一有界解;b > 0 b>0 b > 0 的无界非负解仍然存在。
均值方程组。 特解 c i ci c i 需要满足 0 = 1 + c ( 1 4 − 3 4 ) 0=1+c(\tfrac14-\tfrac34) 0 = 1 + c ( 4 1 − 4 3 ) ,因此 c = 2 c=2 c = 2 。有限解为 g i = 2 i + B ( 3 i − 1 ) g_i=2i+B(3^i-1) g i = 2 i + B ( 3 i − 1 ) 。对所有 i i i 非负要求对每个 i i i 都有 B ≥ − 2 i / ( 3 i − 1 ) B\ge-2i/(3^i-1) B ≥ − 2 i / ( 3 i − 1 ) 。这些下界均为负并趋于 0 0 0 ,所以 B ≥ 0 B\ge0 B ≥ 0 。
上一例的传播论证说明,唯一并非处处有限的解是在 0 0 0 之外均为 ∞ \infty ∞ 的解。因此最小广义解是 E i [ T 0 ] = 2 i E_i[T_0]=2i E i [ T 0 ] = 2 i 。这与上一节的 i / ( q − p ) i/(q-p) i / ( q − p ) 一致,此处却无需停止时刻论证。
几乎必然到达、有限均值、暂留与局限
考虑状态 s , 0 , 1 , 2 , … s,0,1,2,\dots s , 0 , 1 , 2 , … ,取 A = { 0 } A=\{0\} A = { 0 } 。链从 s s s 以概率 1 k ( k + 1 ) \tfrac1{k(k+1)} k ( k + 1 ) 1 跳到 k ≥ 1 k\ge1 k ≥ 1 ;望远镜求和说明这些概率之和为一。链从 k ≥ 1 k\ge1 k ≥ 1 确定地走到 k − 1 k-1 k − 1 ,而 0 0 0 是吸收状态。
于是 m k = k m_k=k m k = k ,所以 h s = 1 h_s=1 h s = 1 。但
m s = 1 + ∑ k ≥ 1 k k ( k + 1 ) = ∞ . m_s=1+\sum_{k\ge1}\frac{k}{k(k+1)}=\infty . m s = 1 + k ≥ 1 ∑ k ( k + 1 ) k = ∞. 因此 P i ( T A < ∞ ) = 1 P_i(T_A<\infty)=1 P i ( T A < ∞ ) = 1 和 E i [ T A ] < ∞ E_i[T_A]<\infty E i [ T A ] < ∞ 确实是不同条件。
在向上游走中,回到 1 1 1 的概率为 f 1 = 3 4 ⋅ 1 3 = 1 4 f_1=\tfrac34\cdot\tfrac13=\tfrac14 f 1 = 4 3 ⋅ 3 1 = 4 1 。这里的 1 3 \tfrac13 3 1 是从 2 2 2 下降到 1 1 1 的概率,相当于把 h 1 h_1 h 1 的问题平移一格。因此状态 1 1 1 是暂留的:概率质量逃向无穷远。相比之下,三状态反例中的 h 1 = 1 2 h_1=\tfrac12 h 1 = 2 1 源于链被困在吸收状态 2 2 2 ;状态 2 2 2 是常返的。到达概率小于一,本身并不表示暂留。
在 { 0 , 1 , 2 , … } \{0,1,2,\dots\} { 0 , 1 , 2 , … } 上,人们很容易想用 i → ∞ i\to\infty i → ∞ 时 h i → 0 h_i\to0 h i → 0 来确定 (H) 中的自由常数。在向上游走中,这碰巧给出 3 − i 3^{-i} 3 − i 。但在向下漂移的游走中 h ≡ 1 h\equiv1 h ≡ 1 ,而且没有任何有限值解 1 + b ( 3 i − 1 ) 1+b(3^i-1) 1 + b ( 3 i − 1 ) 会趋于零。这里证明的选取准则是非负解中的最小性;在无穷远处的行为是它的推论,而不是额外条件。
定理的适用范围。 定理讨论非负解;(H) 或 (M) 的带符号解与结论无关。最小性确定了 h h h 和 m m m ,但不会直接提供公式。上面的明确答案来自先解递推,再施加非负性。
数值计算的局限。
迭代值 h ( n ) h^{(n)} h ( n ) 和 m ( n ) m^{(n)} m ( n ) 是单调递增的下界,但定理不提供误差估计。
在 N N N 处截断给出下界 u i N ≤ h i u^N_i\le h_i u i N ≤ h i ,因为 { T 0 < T N } ⊆ { T 0 < ∞ } \{T_0<T_N\}\subseteq\{T_0<\infty\} { T 0 < T N } ⊆ { T 0 < ∞ } 。
从 1 \mathbf 1 1 开始迭代 (H) 会一直停在该不动点;在 h i < 1 h_i<1 h i < 1 的状态,它给出错误的值。
在任何有限计算中,m ( n ) m^{(n)} m ( n ) 不断增长都不足以区分很大的有限均值与无限均值。
练习
快速检查
(对 P i , i + 1 = 2 3 P_{i,i+1}=\tfrac23 P i , i + 1 = 3 2 、P i , i − 1 = 1 3 P_{i,i-1}=\tfrac13 P i , i − 1 = 3 1 且 0 0 0 为吸收状态的游走,计算 u 1 3 u^3_1 u 1 3 和 u 2 3 u^3_2 u 2 3 ,再求 h i h_i h i 和 E 1 [ T 0 ] E_1[T_0] E 1 [ T 0 ] 。)
解答 · 答案 方程为 u 1 = 2 3 u 2 + 1 3 u_1=\tfrac23u_2+\tfrac13 u 1 = 3 2 u 2 + 3 1 和 u 2 = 1 3 u 1 u_2=\tfrac13u_1 u 2 = 3 1 u 1 。代入得 7 9 u 1 = 1 3 \tfrac79u_1=\tfrac13 9 7 u 1 = 3 1 ,故 u 1 3 = 3 7 u^3_1=\tfrac37 u 1 3 = 7 3 、u 2 3 = 1 7 u^3_2=\tfrac17 u 2 3 = 7 1 。特征根为 1 1 1 和 1 2 \tfrac12 2 1 ,所以一般地 u i N = ( 2 − i − 2 − N ) / ( 1 − 2 − N ) u^N_i=(2^{-i}-2^{-N})/(1-2^{-N}) u i N = ( 2 − i − 2 − N ) / ( 1 − 2 − N ) 。递增事件取极限得到 h i = 2 − i h_i=2^{-i} h i = 2 − i 。由于 P 1 ( T 0 = ∞ ) = 1 2 > 0 P_1(T_0=\infty)=\tfrac12>0 P 1 ( T 0 = ∞ ) = 2 1 > 0 ,有 E 1 [ T 0 ] = ∞ E_1[T_0]=\infty E 1 [ T 0 ] = ∞ 。
快速检查
(在向上游走的例子中(p = 3 4 p=\tfrac34 p = 4 3 ),计算 h 1 ( 1 ) h^{(1)}_1 h 1 ( 1 ) 、h 1 ( 2 ) h^{(2)}_1 h 1 ( 2 ) 、h 1 ( 3 ) h^{(3)}_1 h 1 ( 3 ) 和 h 1 ( 4 ) h^{(4)}_1 h 1 ( 4 ) ,并与 h 1 h_1 h 1 比较。)
解答 · 答案 h 1 ( 1 ) = 1 4 h^{(1)}_1=\tfrac14 h 1 ( 1 ) = 4 1 。接着,h 2 ( 1 ) = 0 h^{(1)}_2=0 h 2 ( 1 ) = 0 给出 h 1 ( 2 ) = 1 4 h^{(2)}_1=\tfrac14 h 1 ( 2 ) = 4 1 。再由 h 2 ( 2 ) = 1 4 ⋅ 1 4 = 1 16 h^{(2)}_2=\tfrac14\cdot\tfrac14=\tfrac1{16} h 2 ( 2 ) = 4 1 ⋅ 4 1 = 16 1 得 h 1 ( 3 ) = 1 4 + 3 4 ⋅ 1 16 = 19 64 h^{(3)}_1=\tfrac14+\tfrac34\cdot\tfrac1{16}=\tfrac{19}{64} h 1 ( 3 ) = 4 1 + 4 3 ⋅ 16 1 = 64 19 ;这里计入了路径 D D D 和 U D D UDD U D D 。从 1 1 1 出发,游走只能在奇数步后到达 0 0 0 ,故 h 1 ( 4 ) = 19 64 h^{(4)}_1=\tfrac{19}{64} h 1 ( 4 ) = 64 19 也成立。这些值从下方缓慢趋于 1 3 \tfrac13 3 1 ,这里并没有误差界。
快速检查
(令 S = { 0 , 1 , 2 } S=\{0,1,2\} S = { 0 , 1 , 2 } 、A = { 0 } A=\{0\} A = { 0 } 、P 00 = 1 P_{00}=1 P 00 = 1 、P 10 = P 11 = P 12 = 1 3 P_{10}=P_{11}=P_{12}=\tfrac13 P 10 = P 11 = P 12 = 3 1 且 P 21 = 1 P_{21}=1 P 21 = 1 。求 h h h 、(M) 的所有广义非负解及 E 1 [ T 0 ] E_1[T_0] E 1 [ T 0 ] 。)
解答 到达概率。 h 2 = h 1 h_2=h_1 h 2 = h 1 且 h 1 = 1 3 + 2 3 h 1 h_1=\tfrac13+\tfrac23h_1 h 1 = 3 1 + 3 2 h 1 ,故 h = ( 1 , 1 , 1 ) h=(1,1,1) h = ( 1 , 1 , 1 ) 。
均值方程组。 方程为 g 2 = 1 + g 1 g_2=1+g_1 g 2 = 1 + g 1 和 g 1 = 1 + 1 3 g 1 + 1 3 g 2 g_1=1+\tfrac13g_1+\tfrac13g_2 g 1 = 1 + 3 1 g 1 + 3 1 g 2 。若其中一个值无限,则两者都无限。若两者有限,则 g 1 = 4 3 + 2 3 g 1 g_1=\tfrac43+\tfrac23g_1 g 1 = 3 4 + 3 2 g 1 ,因此 g 1 = 4 g_1=4 g 1 = 4 、g 2 = 5 g_2=5 g 2 = 5 。
结论。 两个解为 ( 0 , 4 , 5 ) (0,4,5) ( 0 , 4 , 5 ) 和 ( 0 , ∞ , ∞ ) (0,\infty,\infty) ( 0 , ∞ , ∞ ) 。最小解为 ( 0 , 4 , 5 ) (0,4,5) ( 0 , 4 , 5 ) ,故 E 1 [ T 0 ] = 4 E_1[T_0]=4 E 1 [ T 0 ] = 4 。
核对。 每次从 1 1 1 出发尝试,成功概率为 1 3 \tfrac13 3 1 。失败的一次持续 1 1 1 或 2 2 2 步,平均为 3 2 \tfrac32 2 3 步。预期失败次数为 2 2 2 ,因此平均时间为 2 ⋅ 3 2 + 1 = 4 2\cdot\tfrac32+1=4 2 ⋅ 2 3 + 1 = 4 。
快速检查
(对 P i , i + 1 = 1 3 P_{i,i+1}=\tfrac13 P i , i + 1 = 3 1 、P i , i − 1 = 2 3 P_{i,i-1}=\tfrac23 P i , i − 1 = 3 2 的游走,用最小性求 E i [ T 0 ] E_i[T_0] E i [ T 0 ] 。)
解答 · 答案 特征根为 1 1 1 和 2 2 2 。特解 c i ci c i 要求 0 = 1 + c ( 1 3 − 2 3 ) 0=1+c(\tfrac13-\tfrac23) 0 = 1 + c ( 3 1 − 3 2 ) ,故 c = 3 c=3 c = 3 。有限解为 3 i + B ( 2 i − 1 ) 3i+B(2^i-1) 3 i + B ( 2 i − 1 ) 。非负性要求对所有 i i i 有 B ≥ − 3 i / ( 2 i − 1 ) B\ge-3i/(2^i-1) B ≥ − 3 i / ( 2 i − 1 ) ;这些下界均为负并趋于 0 0 0 ,所以 B ≥ 0 B\ge0 B ≥ 0 。唯一的其他解是在 0 0 0 之外均为 ∞ \infty ∞ 。因此最小解给出 E i [ T 0 ] = 3 i E_i[T_0]=3i E i [ T 0 ] = 3 i 。