為何需要新的刻畫方法
上一篇筆記先在有限區間上求解賭徒破產問題,再對事件取極限,計算無限狀態空間中的到達概率。這個方法依賴只能走到相鄰狀態的幾何結構。本節建立一種更一般的方法,適用於任意有限或可數狀態空間。
到達概率和平均到達時間都滿足首步方程,但這些方程往往有多個解。在所有非負解之中,概率論所定義的量總是最小的。因此,選出到達概率靠的是解之間的大小關係,而非唯一性;這兩點都不可忽略。
設定與約定
設 S S S 為有限或可數集合,P = ( P i j ) i , j ∈ S P=(P_{ij})_{i,j\in S} P = ( P ij ) i , j ∈ S 滿足對每個 i i i 都有 P i j ≥ 0 P_{ij}\ge 0 P ij ≥ 0 和 ∑ 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 的函數;換言之,在 A A A 上 g = 1 g=1 g = 1 ,而在 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) 的非負解。對 (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 的第二行為零,因此是奇異矩陣。有限狀態空間並不保證逆矩陣存在;在無限空間中,有限維的求逆論證不能自動套用,算子可逆性需要額外假設。
加入額外假設後,可以在受限制的函數類別中恢復唯一性。
若對每個 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 ] . 右邊等於 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 ] ,因為只要 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 。聲稱得證。
因此對每個 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 } 上,路徑到達 0 0 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 } ,事件隨 N N N 遞增。
這些事件的聯集是 { 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 < ∞ ,到達前的路徑有有限最大值 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<0 b < 0 ,其值趨向 − ∞ -\infty − ∞ ,所以非負解必須有 b ≥ 0 b\ge0 b ≥ 0 。在 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 ;該狀態是常返的。到達概率小於一,本身並不表示暫留。
在 { 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 。