Macintosh_HD:Users:toshi:myDocuments:classes:過去の非常勤:東工大非常勤2007(情報):Markov_chain:note.dvi

Size: px

Start display at page:

Download "Macintosh_HD:Users:toshi:myDocuments:classes:過去の非常勤:東工大非常勤2007(情報):Markov_chain:note.dvi"

ゆゆこやたけ
5 years ago
Views:

1 HMC HMC HMC HMC CTMC CTMC CTMC

2 1 1.1 T t T X t {X t,t T} (stocastic process) (Ω, F,P) ω Ω {X t (ω), t T} (sample pat) {X t } F (x 1,x 2,..., x n ; t 1,t 2,..., t n )=P(X t1 x 1,X t2 x 2,..., X tn x n ) (1.1) 1.2 (stationary process) F (x 1,x 2,..., x n ; t 1,t 2,..., t n )=F(x 1,x 2,..., x n ; t 1 +, t 2 +,..., t n + ) (1.2) p i = P (X t = i) p =(p i ) lim t P (X t = i) 1.3 t 0 Y (t) =X(t 0 t) {Y (t)} {X(t)} t F (x 1,x 2,..., x n ; t 1,t 2,..., t n )=F(x 1,x 2,..., x n ; t t 1,t t 2,..., t t n ) (1.3) 1 2

3 2 S S = {0, 1,...} T = {0, 1,...} {X n } X k {X n } k k {X n } (coupling) 2.1 (irreducibility) (periodicity) {X n } (discrete-time Markov cain) n 0, i 0,..., i n+1 S, P (X n+1 = i n+1 X n = i n,x n 1 = i n 1,X 0 = i 0 )=P(X n+1 = i n+1 X n = i n ) (Markov property) O e 1 P P O Pe = e (stocastic matrix) a a 0 ae =1 (stocastic vector) {X n } p (m, n) =P (X m+n = j X m = i) m i j n (transition probability) P (m, n) = (p (m, n)) m n (transition probability matrix) P (m, 0) = I m, n 0, P (m, n) =P (0,n)=P (n) =(p (n) ) (time-omogeneous Markov cain: HMC) HMC ; Capman-Kolmogorov equation n, k 0, P (n+k) = P (n) P (k) p (n+k) = l S p(n) il p(k) lj (2.1) P =(p )=P (1) P (n) = P n HMC P HMC a =(a i ),a i = P (X 0 = i) (initial distribution) a(n) =(a i (n)), a i (n) = P (X n = i) a(n) =ap (n) n HMC 2 A 3 3

4 2.1 HMC HMC a P a P P = HMC S {Z n } S i.i.d. X 0 {Z n } S f S S S X n+1 = f(x n,z n+1 ),n 0 {X n } HMC 4 Brémaud(1998) HMC S = Z 2 P (Z n =(1, 0)) = q 1, P (Z n =(0, 1)) = q 2, P (Z n =( 1, 0)) = q 3, P (Z n =(0, 1)) = q 4 =1 (q 1 + q 2 + q 3 ) X n+1 = X n + Z n+1 Z 2 {X n } HMC HMC 2.3 n 0 p (n) > 0 j i (reacable) i j i j j i i j (mutually reacable or communicate) i j p (0) ii =1 p (n) > 0 i 1,i 2,..., i n 1 S s.t. p ii1 p i1i 2...p in 1j > 0 S (class) HMC HMC 2.4 C S (1) i, j C, i j, (2) i C, j C p =1 4 U n {U n} U n+1 X n X n+1 f X n+1 = f(x n, U n+1 ),n 0 {X n} HMC HMC 4

5 C (irreducible set) (2) C (closed set) (absorbing state) 2.5 HMC (irreducible Markov cain) (reducible) 2.2 HMC S S S 1 = {0, 1, 2}, S 2 = {3, 4, 5, 6}, S 3 = {7}, S 4 = {8, 9} S 1,S 2,S HMC d 1 d HMC i S d i = g.c.d.{n 1 p (n) ii > 0} i (period) n 0 p (n) ii =0 d i = d i > 1 i (periodic) d i =1 (aperiodic) 2.3 i j d i = d j i j n, m 0 s.t. p (n) > 0, p (m) ji > 0 n, m p (n+m) ii p (n) p(m) ji > 0 n + m > 0 n + k + m d i d i p (k) jj > 0 k 1 p (n+k+m) ii p (n) p(k) jj p(m) ji k d i d j k d i d i d j d i = d j HMC i, j S n 0 n n 0 n p (n) > n d 1 P i, j S, m, n 0 0 s.t. p (m+nd) > 0 for all n n 0. (2.2) i = j A = {k 1 p (k) jj > 0} A d A A d n 0 0 s.t. p (nd) jj > 0 for all n n 0. i j i j m 0 s.t. p (m) > 0 p (m+nd) p (m) p (nd) jj > 0 for all n n 0. P n 0 0 s.t. P (n) > O for all n n 0. 5

6 2.2 d 1 HMC S d C 0,C 1,..., C d 1 0 k d 1, i C k, p =1 j C k+1 C d = C m 0 m d 1 i C k = {j S ; n 0 s.t. p (k+nd) > 0}, k=0, 1,..., d 1, HMC C 0 C 1... C d 1 C 0... d P d S 1 = {0, 1, 2}, S 2 = {3, 4, 5, 6}, S 3 = {7}, S 4 = {8, 9} S 1,S 3,S 4 1 S 2 2 S 2 {3, 4} {5, 6} Brémaud(1998) 2.5 S Z S a S = {ka k Z} c S 0 =c c S c =0 c S S a {ka k Z} S c S k Z c = ka+r, 0 r<a r >0 r = c ka S a r =0 S {ka k Z} 2.6 a 1,..., a k d n 1,..., n k Z s.t. d = k i=1 n ia i S = { k i=1 n ia i n 1,..., n k Z} S 2.5 a = k i=1 n ia i S = {ka k Z} a 1,..., a k d a d a d a i S a a 1,..., a k d a d = a = k i=1 n ia i 2.7 A = {a n n 1} d = g.c.d. A A d d >1 d d =1 1 A a 1,..., a k n 1,..., n k Zs.t. 1 = k i=1 n ia i 1 =M P, M, P A n P (P 1) n n = mp + r, 0 r<p m P 1 1 =M P m r 0 M, P A n = kp + r(m P )=(m r)p + rm A 2.2 HMC 5 d n = g.c.d.{a 1,..., a n} d n d n 1 1 a 1 a 1,..., a k 6

7 2.2.1 HMC π P P HMC π P 2.7 P πp = π π π P HMC (stationary distribution) xp = x xe =1 xp = x π 1 =( π 2 =( ), ), π 3 = ( ) π = q 1 π 1 + q 2 π 2 + q 3 π 3,q 1,q 2,q 3 0, q 1 + q 2 + q 3 =1 2.3 HMC HMC {X n } S τ τ = τ = n X 0,X 1,..., X n 1 {τ =n} X 0,X 1,..., X n {X n } (stopping time) 2.4 {X n } S HMC P =(p ) τ {X n } (strong Markov property) i, j S, P (X τ +1 = j X τ = i, X k, 0 k<τ)=p (X τ +1 = j X τ = i) =p 7

8 P (X τ +1 = j X τ = i, X k, 0 k<τ)= P (X τ +1 = j, X τ = i, X k, 0 k<τ) P (X τ = i, X k, 0 k<τ) = r 0 P (τ = r, X r+1 = j, X r = i, X k, 0 k<r) = r 0 P (X r+1 = j X r = i, τ = r, X k, 0 k<r)p (τ = r, X r = i, X k, 0 k<r) {τ = r} {X k, 0 k r} P (X r+1 = j X r = i, τ = r, X k, 0 k<r)=p (X r+1 = j X r = i) =p i S X τ = i (i) τ τ (ii) τ P HMC 2 Brémaud(1998) T j = inf{n 1 X n = j} j (first passage time) n 1, X n j T j = X 0 = j T j j (recurrence time) {T j = n} = {X n = j, X k j, 1 k n 1} i T j f (n) = P (T j = n X 0 = i) =P (X n = j, X k j, 1 k n 1 X 0 = i), n 1, f (0) =0 i j f = P (T j < X 0 = i) = n=1 f (n) f =1 i T j μ =E[T j X 0 = i] = n=1 nf (n) f < 1 μ = f μ 2.10 f ii =1 i (recurrent or persistent) f ii < 1 i (transient) i μ ii < (positive recurrent) μ ii = (null recurrent) n i j k i j j j k 2.8 n n p (n) = f (k) p(n k) jj,n 1 k=1 (2.3) 8

9 k >n P (X n = j, T j = k X 0 = i) =0 n p (n) = P (X n = j X 0 = i) = P (X n = j, T j = k X 0 = i) k=1 {T j = k} = {X k = j, X m j, 1 m k 1} P (X n = j, T j = k X 0 = i) =P (T j = k X 0 = i)p (X n = j T j = k, X 0 = i) = P (T j = k X 0 = i)p (X n = j X k = j) =f (k) p(n k) jj 2.5 j < p (n) n=0 p (n) jj n P (z) = z < 1 (2.3) p (0) P (z) =δ + F (z)p jj (z) n=0 zn p (n) (n) f = δ n F (z) = n=0 zn f (n) δ i = j 1 i j 0 i = j 1 P jj (z) = (2.4) 1 F jj (z) lim z 1 P jj (z) = n=0 p(n) jj, lim z 1 F jj (z) = n=1 f (n) jj = f jj j f jj < 1 n=0 p(n) jj < F jj (z) =1 1 P jj (z) n=0 p(n) jj < f jj < 1 j j = n=0 n=0 n=0 p (n) jj 6 [ p (n) jj = P (X n = j X 0 = j) = E[1 {Xn=j} X 0 = j] =E n=0 n=0 1 {Xn=j} ] X 0 = j. N j = n=0 1 {X n=j} j 2.5 N j j P (N j = ) =1 Brémaud(1998) 2.6 S P j S i S lim n p(n) =0 (2.3) n p (n) = f (k) p(n k) jj = n=1 n=1 k=1 k=1 n=k 6 A n A lim n E[A n] = E[lim n A n]=e[a]. f (k) p(n k) jj = f n=0 p (n) jj. 9

10 2.5 n=0 p(n) jj < n=0 p(n) < π =(π i ) j S π j > HMC {X n } k 0 P (X k = j) = π i p (k) p (k) <π j π j > 0 π j =0 2.9 i j i j i j n, m 0 p (n) n, m p (n+k+m) ii p (n) p(k) jj p(m) ji P (z) = n=0 zn p (n) 0 <z<1 for all k 0 p (n) > 0, p (m) ji > 0 n P ii (z) p (n) zn+m P jj (z)p (m) ji. (2.5) 2.5 i lim z 1 P ii (z) = n=0 p(n) ii 0, p (m) ji > 0 lim z 1 P jj (z) = n=0 p(n) jj < j j i i, j l S G l (z) = n=1 z n m=1 n=1 m=n f (m) ll lim z 1 G i (z) =G i (1) = μ ii, lim z 1 G j (z) =G j (1) = μ jj (2.4) m G i (z) = z n f (m) ii = z(1 F ii(z)) z = 1 z (1 z)p ii (z). G j (z) z G j (z) = (1 z)p jj (z). (2.5) p (n) zn+m G i (z)p (m) ji G j (z) j >μ jj = G j (1) p (n) G i(1)p (m) ji = p (n) μ iip (m) ji μ ii 0 i, j p (n) ji = 0 for all n 0 i j j / C f ji =0 i f ii f ii = p ii + p ik f ki p ii + p ik =1 p < 1 k i k i,j i C 10

11 2.3 C S C P =( p ) P P π =( π j ) S π =(π j ) j C π j = π j, j/ C π j =0 π πp = π HMC HMC 1 HMC S P =(p ) S x =(x i )(x 0) i S x i [0, ) x i = j S x j p ji x P (invariant measure) 2.10 S HMC {X n } P =(p ) i S 0 0 i x i T 0 0 [ T0 ] [ ] x i = E X 0 =0 = E X 0 =0. (2.7) n=1 1 {Xn=i} n=1 1 {Xn=i}1 {n T0} x =(x i ) i S, x i (0, ) (2.6) n = T 0 X n =0 x 0 = P (T 0 < X 0 =0)=1 0p (n) 0i =E[1 {Xn=i}1 {n T0} X 0 =0]=P (X 1 0,..., X n 1 0,X n = i X 0 = 0) (2.8) x i = n=1 0p (n) 0i 0 p (n) 0i n =1 0 p (1) 0i = p 0i n 2 n 1 0p (n) 0i = 0p (n 1) 0j p ji j 0 n 1 x i = p 0i + j 0 x j p ji (2.6) 11

12 x 0 =1 (2.6) x i > 0 (2.6) x = xp n x 0 =1 n x i = p (n) 0i + x j p (n) ji j 0 i 0 x i =0 n 1, p (n) 0i =0 i S, x i > 0 x i < x i > 0 1=x 0 = j S x j p (n) j0 j S n 0 p (n) j0 j S, x j < > 0 x j = HMC 0 1 {Xn=i}1 {n T0} = 1 {n T0} = T 0 n=1 n=1 [ ] E X 0 =0 =E[T 0 X 0 =0]=μ 00. (2.9) n=1 1 {Xn=i}1 {n T0} x i = HMC HMC 2.11 HMC P =(p ) y =(y i ) 2.10 x =(x i ) i S x = 1 y i y y =(y i ) y k > 0 y k x x i > 0 i S, y i > 0 Q =(q ) q = y j p ji y i Q n q (n) = y j p (n) ji y i P Q 2.5 P Q 0p (n) 0i P 2.10 g (n) 0p (n+1) 0i = 0p (n) 0j p ji. j 0 Q 0 p (n) 0i g (n+1) i0 = q g (n) j0 j 0 y 00 p (n) 0i y i g (n) i0 n 1 (y 00 p (n+1) 0i )= (y 00 p (n) 0j )p ji, j 0 (y i g (n+1) i0 )= (y j g (n) j0 )p ji. j 0 12

13 y 00 p (1) 0i = y 0 p 0i = y i q i0 = y i g (1) i0 n 1 0p (n) 0i = y i g (n) i0 y 0 Q x i = n=1 0p (n) 0i = y i y 0 n=1 g (n) i0 = y i y x > 0 7 HMC 2.12 S HMC {X n } P x =(x i ) {X n } x i < (2.9) x i = μ HMC HMC 2.7 HMC π π > x =(x i ) x i < 1 π = x x i π π =(π i ) i S, n 0, π i = π jp (n) ji 2.6 lim n p (n) ji =0 i S π i = lim π j p (n) n ji = lim π jp (n) n ji =0 HMC HMC π > P 2.10 π > 0 (finite Markov cain) 2.13 HMC HMC S = {0, 1,..., M} 2.6 M 1 = lim p (n) =0 n j=0 7 HMC Z + P (X 1 = i +1 X 0 = i) >P(X 1 = i 1 X 0 = i) =1 q 13

14 2.10 x =(x i ) > 0 M i=0 x i < HMC i S π i = 1. μ ii (2.10) 2.10 x xe < (2.9) π 0 = x 0 xe = 1 μ 00 0 i 2.4 P =(p ) S HMC {X n } a(n) =ap n 8 a(n) {X n } j S a 2.6 lim a j(n) = lim a i p (n) n n = a i lim n p(n) =0 {X n } {X n } a(n) {X n } r>1 2.2 S r {X n } 1 r (total variation distance) (coupling) HMC S a =(a i ) b =(b i ) (total variation distance) d(a, b) d(a, b) = 1 a i b i (2.11) 2 (2.11) d (2.11) 1 2 d(a, b) =0 a = b (elementwise) 0 d(a, b) 1 d(a, b) =0 d(a, b) =1 a b 8 HMC 14

15 S X Y d(x, Y )= 1 P (X = i) P (Y = i). 2 9 d(x, Y )=0 X = d Y 2.15 S X Y sup A S P (X A) P (Y A) = sup{p (X A) P (Y A)} = d(x, Y ). A S A S B = A B = A C P (X A) P (Y A) = P (X B) P (Y B) P (X A) P (Y A) A S A = {i S P (X = i) >P(Y = i)} A P (X = i) P (Y = i) = {P (X = i) P (Y = i)} = P (X = i) P (Y = i) i A i (A ) C i (A ) C S = A (A ) C sup{p (X A) P (Y A)} = P (X = i) P (Y = i) = 1 P (X = i) P (Y = i) = d(x, Y ) A S 2 i A S {X n (1) } {X n (2) } (coupling) 1 τ τ X n (1) = X n (2),n τ, τ (coupling) 2.16 τ {X n (1) } {X n (2) } d(x (1) n,x(2) n ) P (τ >n), n 0 (2.12) n 0, A S τ P (X (1) n A) P (X(2) n A) = P (X n (1) A, n < τ)+p (X n (1) A, n τ) {P (X n (2) A, n < τ)+p (X n (2) A, n τ)} = P (X (1) n A, n < τ) P (X(2) n A, n < τ) P (X n (1) A, n < τ) P (n <τ) 2.15 (2.12) 9 X = d Y X Y 15

16 2.4.3 HMC 2.14 HMC HMC (ergodic) HMC {X n } HMC {X n } {X n} {X n } HMC 2.17 S P =(p ) P a, b HMC {X n (1) } {X n (2) } {X n (3) } τ = inf{n 0 X (1) n = X(2) n }, X(3) { (2) X n = n X (1) n if n τ if n τ τ 1 {X n (1) } {X n (3) } τ {X n (3) } P b HMC {X n (2) } {X n (3) } S 2 2 {Z n }, Z n =(X (1) n,x (2) n ), n 0, τ {Z n } {Z n } HMC S S 2 {Z n } {X n (1) } {X n (2) } HMC {Z n } HMC P (Z n+1 =(j, l) Z n =(i, k)) = p p kl, (i, k), (j, l) S 2 (2.13) P 2.4 (i, j), (k, l) S 2 m 1 p (n) p(n) kl > 0, n m, 2.4 m HMC {Z n } P P π =(π i ) (2.13) (π i π j, (i, j) S 2 ) {Z n } {Z n } 2.7 τ {Z n } A = {(i, i) i S} {Z n } P (τ < ) =1 A 1 (0, 0) τ {Z n } {Z n } τ HMC τ {X n (1) } {X n (3) } P HMC {X n (3) } b HMC HMC 2.8 HMC P S π =(π i ) a =(a i ), b =(b i ) lim d(a(n), b(n)) = lim d(ap n, bp n )=0 n n a(n) b(n) π i, j S lim n p(n) = π j. (2.14) 16

17 P a, b HMC {X n (1) } {X n (2) } 2.17 {X n (1) } P b HMC {X n (3) } τ lim n d(x(1) n,x(2) n ) = lim d(a(n), b(n)) = lim d(ap n, bp n ) = lim n n n d(x(1) n,x(3) n ) lim P (τ >n)=0 n a, b b = π lim d(ap n, π) =0 n a i =1,a k =0,k i, (2.14) P n π lim P n = eπ. n HMC HMC 2.9 HMC S P =(p ) i, j S lim n p(n) =0. (2.15) {Z n } P a, b HMC {X n (1) } {X n (2) } S 2 2 {Z n } Z n =(X n (1),X n (2) ), n 0, 2.17 P {Z n } HMC P {Z n } {Z n } i, j S (i, i) (j, j) n (p (n) )2 (j, j) 2.6 lim n (p(n) )2 =0 {Z n } lim n p(n) =0 i, j S lim k p(n k) = x j > 0 and lim il = x l [0, 1], l j, {n k } {Z n } k p(n k) 2.8 i HMC 1 HMC lim k p(n k) il p (n k+1) il =0 p (n k+1) il = s S p(n k) is p sl x l = x s p sl s S x =(x l,l S) P n 0 l S p(n) il 1 l S x l P 17

18 2.4.5 HMC S 2 = {3, 4, 5, 6} r =2 P ( ) QC1 P = , Q = P 2 O = = O QC P C 1 = {3, 4} C 2 = {5, 6} Q P π π =( x C1 x C2 )=( ) x C1 x C2 2 π C1 =( ), π C 2 =( ) Q C1 Q C2 Q C1 P C k P C k HMC 2.18 HMC S r>1 P =(p ) π =(π i ), C k,k=0, 1,..., r 1, Q =(q )=P r Q Ck Q C k Q Ck C k Q π Ck Q Ck x Ck π k C k π Ck = r x Ck 2.2 l {0, 1,..., r 1}, n 0 { some nonnegative value if i p (nr+l) Ck and j C (k+l) mod r for some k {0, 1,..., r 1} = (2.17) 0 oterwise n =1,l { =0 some nonnegative value if i, j q = p (r) Ck for some k {0, 1,..., r 1} = (2.18) 0 oterwise (2.17) k {0, 1,..., r 1} i, j C k i j n n = mr p (mr) = q (m),m 0 i, j C k P i j Q i j 2.4 i C k m 0 m m 0 q (m) ii = p (rm) ii > 0 i Q C k C k,k=0, 1,..., r 1 Q Q Ck (2.17) k {0, 1,..., r 1} π j = π i p = π i p = π i p = π i j C k+1 j C k+1 j C k+1 i C k i C k j C k+1 i C k C r = C 0 x Ck+1 e = x Ck e r 1 k=0 x C k e = πe =1 (2.16) x Ck e = 1 r π P Q (2.18) k {0, 1,..., r 1}, j C k π j = π i q = π i q i C k 18

19 x Ck = x Ck QCk x Ck Q Ck π Ck = r x Ck Q Ck Q Ck P r 2.10 HMC S r>1 P =(p ) π =(π i ) C S x C π C a =(a i ) i C a i =1 lim d(ap rn,rx C )=0 (2.19) n i, j C lim n p(rn) = rπ j (2.20) Q = P d Q C Q C 2.18 a C ã C x C C x C Q C π C π C = r x C 2.8 lim d(ã C Q n C,r x C )=0 n a i =1,a l = 0, l i 19

20 3 S S = {0, 1,...} T =[0, ) {X(t)} P (t) =(p (t)), p (t) = P (X(t) =j X(0) = i) {X(t)} S {X(t)} t 0 (continuous-time Markov cain k 0, i, j, i 1,..., i k S, s, t 0, s 1,..., s k [0, )(0 s 1 <... < s k <s), P (X(t + s) =j X(s) =i, X(s k )=i k,..., X(s 1 )=i 1 )=P(X(s + t) =j X(s) =i) (3.1) (Markov property) s (time omogenous) (3.1) i, j S, P (X(t + s) =j X(s) =i, X(u), 0 u<s)=p (X(s + t) =j X(s) =i) p (t) =P (X(t) =j X(0) = i) CTMC p (t) P (t) =(p (t)), P (0) = I a =(a i ), a i = P (X(0) = i) a(t) =(a i (t)), a i (t) =P (X(t) =i) a(t) = ap (t) t CTMC a {P (t)} t 0 CTMC {P (t)} t 0 CTMC {P (t)} 3.1 ; Capman-Kolmogorov equation s, t 0, P (s + t) =P (s)p (t) p (s + t) = l S p il(s)p lj (t) CTMC CTMC (1) 3.2 N(s, t] (s, t] N(t) =N(0,t] {N(t)} t 0 (inteinsity) λ>0 (Poisson process) (i) k 2 0 t 1 t 2... t k N(t i,t i+1 ],i=1,..., k 1 ( (ii) (s, t] N(s, t] λ(t s) CTMC 20

21 3.1 λ>0 {N(t)} t 0 N + CTMC { e λt (λt) j i (j i)! if j i p (t) =P (N(t) =j i) = 0 if j0 {X(t)} t 0 (uniform Markov cain) X(t) = ˆX N(t),t S CTMC λt (λt)n P (t) = e K n,t 0 n! n=0 DTMC N(t) M/M/ 3.2 CTMC CTMC {P (t)} t 0 {P (t)} P (t) Q = lim 0 (P () I)/ P (t) (d/dt)p (t) = QP (t) =P (t)q P (t) = exp(qt) p (t) 3.5 lim P () =I 0 21

22 3.3 P (t) t 0 P (t) p ii () p () q i = lim [0, ], i S, q = lim [0, ), i,j S, j i. (3.2) 0 0 lim 0 1 p ii() P (t) = [ P ( t n )] n p ii (t) [ p ii ( t n )] n pii (0) = 1 n p ii ( t n ) > 0 t 0, p ii (t) > 0 f i (t) = log p ii (t) f i (t) lim 0 f i () =0 p ii (t + s) p ii (t) p ii (s) f i (t + s) f i (t)+f i (s) f i q i = sup t>0 f i (t)/t lim 0 f i ()/ = q i 1 p ii () 1 exp( f i ()) f i () lim = lim = q i (3.3) 0 0 f i () p lim () 0 c ( 1 2, 1) δ>0 t [0,δ] p ii (t) >c p jj (t) >c n < δ n, P () DTMC {X n } = {X(n)} p (n) i j n 1 p (n) P (X r = i, X k j, 1 k r 1 X 0 = i)p ()P (X n = j X r+1 = j) r=0 P (X n = j X r+1 = j) =p jj ((n r 1)) >c p () P (X r = i, X k j, 1 k r 1 X 0 = i) P (X r = i X 0 = i) P (X r 1 = j X 0 = i)p (X r = i X r 1 = j) c (1 c) =2c 1 1 c(2c 1) p (n) n t <δ <δ n = t lim sup 0 p () 1 p (n) 1 p (t) lim sup = < c(2c 1) 0 n c(2c 1) t p lim () 0 t lim inf t 0 c 1 lim sup 0 p () lim inf t 0 p (t) t q i = q i = j S, j i q ) 3.6 q i =0 i (absorbing) q i = i (instantaneous) 0 <q i < i (stable) P () I 3.7 q ii = q i, Q =(q ) = lim 0 matrix) (infinitesimal generator) (transition rate 22

23 3.2.2 P (t) 3.8 i S, q i < Q (stable) i S, q i = j S, j i q Q (conservative) j S p 1 p ii () p () () =1 q i = lim = lim 0 0 j S, j i q i j S, j i q P (X(t + ) =i X(t) =i) =1 q i + o() (3.4) P (X(t + ) =j X(t) =i) =q + o() Qe = 0 CTMC 3.9 (uniformizable) sup q ii < (3.5) 3.5 Q =(q ) CTMC {X (1) (t)} λ sup q ii λ< λ N(t) K = I + 1 λ Q DTMC { ˆX n } {X (2) (t)} = { ˆX N(t) } {X (1) (t)} (uniformization) λ CTMC 3.10 N + CTMC Q =(q ) (birt-and-deat process) μ i if i 1, j= i 1 λ i if i 0, j= i +1 q = λ i if i = j =0 (3.6) (λ i + μ i ) if i 1, j= i 0 oterwise 0 λ i < 0 μ i < i 1, μ i =0 M/M/1 M/M/ 23

24 3.2.3 P (t + ) P (t) = P () I P (t) =P (t) P () I P (t) 3.2 P Q d P (t) =QP (t) (3.7) dt p (t + ) p (t) = p ii() 1 p (t)+ p ik () p kj(t) (3.8) k S, k i k S, k i 2 p ik () N p p ik () kj(t) p kj(t) k=0,k i lim inf 0 N p ik () lim inf 0 p kj(t) q ik p kj (t) k S, k i k S, k i N >i p ik () N p p ik () kj(t) p kj(t)+ p ik () k S, k i k=0,k i k>n N p ik () = p kj(t)+ 1 p ii() k=0,k i N k=0,k i p ik () lim sup 0 N p ik () lim sup 0 p kj(t) q ik p kj (t)+q i q ik = q ik p kj (t) k S, k i p ik () lim 0 p kj(t) = k S, k i k S, k i k S, k i q ik p kj (t) k S, k i k S, k i (3.8) 0 p (t + ) p (t) lim = q i p (t)+ q ik p kj (t) (3.9) 0 k S, k i p (t) k S, k i q ik = q i 0 t 24

25 p kj () 1 p kk() q k (3.10) (3.12) lim 0 k S p ik(t)q kj p (t) (3.10) (3.10) (3.10) a(t) =(a i (t)) 3.4 P (t) Q t 0, a i (t)q i < d a(t) =a(t)q dt (3.13) (3.14) d dt a i(t) = a j (t)q ji a i (t)q i (3.15) j S, j i i a i (t) i i P (0) = I (tq) n P (t) = exp(tq) = (3.16) n! n=0 (3.16) (3.16) 3.3 S CTMC {X(t)} t 0 P (t) CTMC τ n n X n = X(τ n ),n 0, {X n } DTMC τ n+1 τ n X n

26 3.2 (regularity) s 0 {X(t)} t 0 [0,s] 1 τ 0 =0<τ 1 <τ 2 <... (0, ) (= n< ) k 1, τ n+k = τ = lim n τ n τ = τ n 3.3 τ n i j X(τ n )=j {X(t)} λ n =2 n DTMC CTMC [1] τ n 3.11 {X(t)} t 0 S τ τ = τ = t {X(s), s [0,t]} 1 {τ =t} {X(s), s [0,t]} {X(t)} (stopping time) τ n 3.5 (strong Markov property) S CTMC {X(t)} t 0 P (t) {X(t)} τ {X(t)} (i) X(τ) =k τ τ (ii) X(τ) =k τ CTMC P (t) [2] S CTMC {X(t)} t 0 P (t) {X(t)} {τ n } n 0 {X(t)} {X n } n 0 X n = X(τ n ),n 0 {X n } S DTMC τ n+1 τ n X n P =(p ), p = P (X 1 = j X 0 = i) i S 0 λ i t X 0,..., X n 1,X n = i, τ 1 τ 0,..., τ n τ n 1 )=p e λit (3.17) f i (t) =P (τ 1 >t X(0) = i) =P (X(u) =i, 0 u t X(0) = i) 26

27 f i (t + s) = P (X(u) =i, 0 u t + s X(0) = i) = P (X(u) =i, s u t + s X(s) =i) P (X(u) =i, 0 u s X(0) = i) =f i (t)f i (s) lim 0 f i () =f i (0) = P (τ 1 > 0 X(0) = i) =1 f i (t) 0 λ i < f i (t) =e λit (3.17) (3.17) τ n CTMC {X(s), s<τ n,x(τ n )=i} (3.17) = P (X n+1 = j, τ n+1 τ n >t X(s), s<τ n,x(τ n )=i) = P (X n+1 = j, τ n+1 τ n >t X(τ n )=i) = P (X 1 = j, τ 1 >t X(0) = i) = P (τ 1 >t X(0) = i)p (X 1 = j τ 1 >t,x(0) = i) =e λit P (X 1 = j τ 1 >t,x(0) = i) P (X 1 = j τ 1 >t,x(0) = i) = P ({X(t + s)} s 0 j X(s) =i, s [0,t]) = P ({X(t + s)} s 0 j X(t) =i) = P ({X(s)} s 0 j X(0) = i) = P (X(τ 1 )=j X(0) = i) =p DTMC (embedded Markov cain: EMC) EMC P =(p ) ( i S, p ii =0) 3.6 EMC CTMC t i i λ i EMC CTMC 3.6 EMC Δ S {Δ} p Δ,Δ =1 q i =0 i p iδ =1 (q i > 0) p iδ =0 EMC i p ii =0 t N(t) = sup{n ; τ n t} lim t N(t) = N(t) X(t) =X N(t) CTMC EMC 3.6 P =(p ), λ i, Q =(q ) [2] 3.7 CTMC CTMC {X t } t 0 Q =(q ) λ i = q i,, p = q,i,j S (3.18) q i q i =0 p =0 3.1 λ N(t) (0,t] 3.2 i.i.d. 27

28 {N(t)} i λ p i,i+1 =1 i +1 CTMC 3.2 ; M/M/1 λ μ L(t) t {L(t)} S = {0, 1,...} CTMC i>0 λ + μ 10 p i,i+1 = λ λ+μ i +1 p i,i 1 = μ λ+μ i 1 λ λ 0 0 μ (λ + μ) λ 0. Q = 0 μ (λ + μ) λ μ (λ + μ) {P (t)} t 0 t 0 πp(t) =π π π {P (t)} CTMC (stationary distribution) DTMC CTMC P (t) π =(π i ) Q =(q ) 3.4 π iq i < π πq = 0 λ DTMC K DTMC 3.14 t 0 s.t. p (t) > 0 j i (reacable) i j i j j i i j (mutually reacable or communicate) i j CTMC (irreducible Markov cain) CTMC q i =0 i i S, q i > 0 CTMC EMC 3.15 i T i = inf{t 0 X(t) i} t 0, X(t) =i T i = i (return time) R i = inf{t 0 t>t i,x(t) =i} T i = t T i,x(t) i R i = 10 T, H λ, μ min{t,h} λ + μ min{t,h} = T λ min{t,h} = H μ λ+μ λ+μ 28

29 T i, R i 3.16 P (R i < X(0) = i) =1 i (recurrent) P (R i < X(0) = i) < 1 i (transient) i E[R i X(0) = i] < (positive recurrent) E[R i X(0) = i] = (null recurrent) μ ii =E[R i X(0) = i] i q i > 0 i EMC i i i ν =(ν i )(ν 0) t 0 νp(t) =ν ν {P (t)} (invariant measure) 3.8 CTMC {X(t)} t 0 Q ν > 0 (i) 0 [ ] R0 ν i = E 1 {X(s)=i} ds X(0) = 0,. (3.19) 0 (ii) EMC x T 0 EMC 0 [ T0 ν i = x E i n=1 1 ] {X n=i} X(0) = 0 =,. (3.20) q i q i (iii) νq = 0. (3.21) [2] ν i =E[R 0 X(0)=0]=μ CTMC {X(t)} t 0 ν {X(t)} ν i <. (3.20) CTMC ν EMC x i S q i ν i = x i CTMC EMC CTMC 3.8 CTMC {X(t)} t 0 π π πq = 0 π π > 0 3.8, 3.9 π CTMC EMC lim t p (t) =0 lim t πp(t) =0 29

30 CTMC 3.9 CTMC π =(π i ) p (n) (t) =P (X(t) =j, t < τ n X(0) = i) t n p (1) (t) =δ e qit p (n) (t) =δ e qit + t (3.22) 0 k S, k j p(n 1) ik (u)q kj e qj(t u) du, n 2 (3.22) 2 1 t j 2 u (0,t] n j t j lim (t) =p (t), p (t) =1 n p(n) j S (3.22) 2 π i t π i p (n) (t) =π je qjt + e qj(t u) q kj π i p (n 1) ik (u)du 1 π j p (1) (t) =π je qjt π j 0 k S, k j π π i p (n) (t) π j,n 1 π i p (t) π j j 1 π t 0 πp(t) =π π > (3.22) xq = 0 xe =1 3.2 M/M/1 ρ = λ μ < 1 π n =(1 ρ)ρ n π i q i j 3.10 CTMC {X(t)} t 0 1 π i = q i E[R i X(0) = i] = 1 (3.23) q i μ ii (3.19) ν 0 = 1 q 0, ν i =E[R 0 X(0) = 0] π 0 =1/(q 0 E[R 0 X(0) = 0]) 0 CTMC EMC CTMC π =(π i ) EMC π =( π i ) π i q i i, j S, = π i π j q j π j 30

31 π π π π π i /q i π i q π i = j S π, π i = i j/q j j S π jq j CTMC CTMC (ergodic) 3.9 S CTMC {X(t)} P (t) =(p (t)) π =(π i ) i, j S, lim t p (t) =π j. (3.24) CTMC {X(n)} n 0 CTMC {X(n)} π {X(n)} {X(n)} 2.7 CTMC {X(n)} P (t) CTMC {X (1) (t)} {X (2) (t)} {X (1) (n)} n 0 {X (2) (n)} n 0 DTMC π τ X (1) (τ) =X (2) (τ) CTMC {X (1) (t)} {X (2) (t)} τ 2.17 {X (2) (t)} {X (1) (t)} CTMC {X (3) (t)} {X (1) (t)} {X (3) (t)} [1] D. P. Heyman and M. J. Sobel, Stocastic Models in Operations Researc Vol. I, McGraw-Hill (1982). [2] P. Brémaud, Markov Cains Gibbs Fields, Monte Carlo Simulation, and Queues, Springer (1999). 31

Part () () Γ Part ,

Part () () Γ Part , Contents a 6 6 6 6 6 6 6 7 7. 8.. 8.. 8.3. 8 Part. 9. 9.. 9.. 3. 3.. 3.. 3 4. 5 4.. 5 4.. 9 4.3. 3 Part. 6 5. () 6 5.. () 7 5.. 9 5.3. Γ 3 6. 3 6.. 3 6.. 3 6.3. 33 Part 3. 34 7. 34 7.. 34 7.. 34 8. 35