I Advanced Analysis I Markov Processes on Discrete Graphs (13:00-14:30) ( (Basics of Probability Theory) (Probability Spaces

I Advanced Analysis I Markov Processes on Discrete Graphs 7 4 2 5-6 (3:-4:3) ( 22 6 (Basics of Probability Theory). (Probability Spaces and Random Variables)..........2, (Expectations, Means)........................ 2.3 (LLNLaw of Large Numbers)...................... 3 2 (Discrete-time Markov Chains) 6 2. (Basic Examples)............................. 6 2.2 (Time Homogeneous Markov Chain)........... 6 2.3 d (d-dimensional Random Walks).............. 2.4 - (Galton-Watson Process).................. 4 3 (Continuous-time Markov Chain) 7 3. (Exponential Times)............................ 7 3.2 (Poisson Process).......................... 8 3.3 (Continuous-time Random Walk)............ 22 3.4 (Continuous-time Markov Chain & Transition Probability)....................................... 23 4 - (Continuous-time Galton-Watson Processes) 26 5 (Branching Random Walk) 27 6 (Contact Process) 32

7 35 7................................... 35 7.2 (Characteristic Functions & Convergence of Distributions) 38 7.3 (CLTCentral Limit Theorem).................... 4, Z 2 T d,,.,,,.,,.,. R. B. (2 )

Markov Processes on Graphs (Basics of Probability Theory),.,.,,.. (Probability Spaces and Random Variables),, (Ω, F, P ),, X X(ω) ( ). (Ω, F, P ) (probability space). Ω ( ω Ω ) F ( 2 Ω ) Ω σ (σ-field); (2 Ω Ω ) () Ω F (2) A F A c F (3) A n F (n, 2,... ) A n F P P (dω) (Ω, F) (probability measure), i.e., ; P : F [, ]. () P (Ω) (2) A n F (n, 2,... ) P ( A n ) P (A n ) (σ ). (Ω, F, P ),. () σ-., F σ- A, B, A n F F, A B, A \ B, A B : (A \ B) (B \ A), A n. lim A n lim sup A n : A n, lim A n lim inf A n : N n N N. (lim inf sup, lim sup inf.) n n N A n F (2) P ( ), A k F (k, 2,..., n) P ( n k A k) n k P (A k) ( ). (3) A, B F; A B P (A) P (B) ( ). ( ) (4) A n F, A n P An lim P (A n). n ( ) (5) A n F, A n P An lim P (A n).. n

Markov Processes on Graphs 2 ( ) (6) A n F (n ) P An P (A n ) ( ). (7) (Borel-Cantelli ) A n F (n ), ( ) P (A n ) < P lim sup A n, i.e., ( ) n P lim inf n Ac n. (Ω, F, P ) X X(ω) : Ω R {X a} : {ω Ω; X(ω) a} F ( a R). (random variable). X S {a j } j R, {X a j } F ( j ). X k (Ω, F, P ) (k, 2,..., n). {X k } n k (independent) P (X a,, X n a n ) P (X a ) P (X n a n ) ( a k R, k,..., n). n {X k } k N {X k } N k. X k S {a j } j, : P (X b,, X n b n ) P (X b ) P (X n b n ) (b k S, k,..., n). µ X (A) P (X A) X (distribution), F (x) P (X x) X (distribution function)..2, (Expectations, Means) (Ω, F, P ) X (expectation) or (mean) EX E[X] : XdP X(ω)P (dω) P Lebesgue., X Z : Z {± }. EX. () X EX : np (X n) + P (X ). n (P (X ) P (X ). P (X ) > EX.) (2) X X + : X, X : ( X) ( X ±, X X + X.) EX : EX + EX.,. EX np (X n), f : Z R, n Z Ef(X) f(n)p (X n). ( n Z.) Ω n;f(n)> n;f(n)< X, V (X) : E[(X EX) 2 ] E[X 2 ] (EX) 2 ( ). (EX) 2 E[X 2 ].

Markov Processes on Graphs 3. (Chebichev ) p. a >, P ( X a) E[ X p ] a p. [ ] P ( X a) P ( X p a p ) p. E X n np ( X n) n a np ( X n) a n a P ( X n) ap ( X a)..2 X,..., X n Z, E[Xk 2 ] < (k,..., n). X,..., X n, E[X j X k ] E[X j ]E[X k ] (j k). E[X k ] ( n ) 2 E X k E[Xk]. 2 k [ ] () j k P (X j m, X k n) P (X j m)p (X k n) k E[X j X k ] m,n mnp (X j m, X k n) m,n mnp (X j m)p (X k n) E[X j ]E[X k ]. ( n ) 2 (2) X k X j X k () j k E[X j X k ] E[X j ]E[X k ] k. k X 2 k + j k.3 (LLNLaw of Large Numbers), /2.,. n, X n, X n. EX n /2 ( V (X n ) /2 ). n, X k, n, /2 n k..3 ( (Weak Law of Large Numbers)) X, X 2,... EX n m v : sup n V (X n ) < ε >, ( ) lim P X n k m n ε k, i.e., lim n P ( n ) X k m < ε. [ ] {X n } { X n X n m} ( ). n X k m n k (X k m) k k

Markov Processes on Graphs 4, X n X n m, i.e., E[X n ] V (X n ) E[Xn] 2, ( n ) 2 E X k E[Xk] 2 k k k V (X k ) n sup V (X n ) nv. n ε >, ( ) P X k ε n k P ( ) X k εn k nv ε 2 n 2 v ε 2 n E[( n k X k) 2 ] ε 2 n 2 (n ).,...4 ( (Strong Law of Large Numbers)) X, X 2,... EX n m v : sup n V (X n ) < P ( lim n n ) X k m. k.,,. ( ) P lim (X k EX k ). n n k,.. [sup E[Xn] 4 <.4 ] X n X n m ( n ) 4 m, i.e., E[X n ] X k, E[X 2 ] (E[X 4 ]) /2 ( n ) 4 E X k E[Xk] 4 + n k k k n k i j, i,j n k E[Xi 2 ]E[Xj 2 ] n 2 sup E[Xk] 4 k (or Fubini ) ( ) 4 ( E n ) 4 X k n n 4 E X k n 2 sup E[Xk] 4 < k P ( lim n n ) X k k,,. n

Markov Processes on Graphs 5.5 (CLT) {X n } (independent identically distributed i.i.d.). EX m, V (X ) v n (X k m) n, v N(, v), i.e., a < b, ( ) lim P a < n (X k m) < b b e x2 2v dx. n n 2πv, nv n k k a k (X k m), N(, ),,. B B(R ) Borel. X,..., X n, X (X,..., X n ), µ X (A A n ) P (X A,..., X n A n ) (A i B )..6 X,..., X n, X (X,..., X n ), µ X n µ Xi i.e., µ X (A A n ) µ X (A ) µ Xn (A n ). i (, a] σ B..7 X, Y, Borel f(x, y), E[f(X, Y )] E [E[f(x, Y )] xx ] E [E[f(X, y)] yy ]., f(x, y)µ (X,Y ) (dx, dy) f(x, y)µ X (dx)µ Y (dy) R 2 R 2,.. X, Y, P (X < Y ) R P (x < Y )µ X (dx).

Markov Processes on Graphs 6 2 (Discrete-time Markov Chains),. 2. (Basic Examples),,.,, 2.,.,,. 2. Z (random walk) (X n, P ),, O ; X O. < p <,, + p, q p., n x n +, x + p, x q ; P (X n+ x + X n x) p, P (X n+ x X n x) q. n, n,.. 2, - (BGW or GW ), Bienaymé, Galton, Watson 3,. 2.2, - (Bienaymé-Galton-Watson process) (Z n, P ),, Y., Y k,, 2,..., P (Y k) p k (p k, p k, p k ). Z n n. ; Z. Y.,, m kp k. 2.2 (Time Homogeneous Markov Chain). 2. S,.,,,.,.

Markov Processes on Graphs 7,,,,.. S, S (X n, P ) (X n (ω), P (dω)) (n,, 2,... ) (Markov Chain) : (M) [ ] n, j, j,..., j n, k S, P (X n+ k X j, X j,..., X n j n ) P (X n+ k X n j n ).. (M2) [ ] n, j, k S, P (X n+ k X n j) P (X k X j) (: q(j, k) ).,. X µ {µ j }; µ j P (X j) (initial distribution),, j S, P (X j) P P j, (X n, P j ) j. ( P (X j) >, P j ( ) : P ( X j),.) n, j, k S, q n (j, k) P (X n k X j), Q n (q n (j, k)) n ( ) (n-step transition probability (matrix)),, Q Q (q(j, k)),, ( ). 2.. (i) q n (j, k), k q n(j, k) (j S), (ii) n, j, j,..., j n S P (X j, X j,..., X n j n ) µ j q(j, j ) q(j n, j n ), (iii) m, n, j,..., j m, k, k,..., k n S P (X n+ j,..., X n+m j m X k, X k,..., X n k n ) q(k n, j )q(j, j 2 ) q(j m, j m ). (iv) Q I : (δ jk ) ( ), Q n Q n (n ),, δ jk (j k), (j k). 2.2 µ {µ j } X n. P (X n k) µ j q n (j, k). j S, j S (recurrence time): T j : T j inf{n ; X n j} ( if { } ).

Markov Processes on Graphs 8 j (recurrent) j (transient) def P j (T j < ), def P j (T j < ) <. j (or ) (X n ) (or ). {X n } Q (q(j, k)) (irreducible) j, k, n, q n (j, k) >.,,. (,,.), : 2.2 j, k S. (i) j : a) q n (j, j). n b) P j ({X n } j ). (ii) j : a) q n (j, j) <. n b) P j ({X n } j ). (iii) {X n },, (i), (ii) b), a), (iii). 2. O- m, n, j,..., j m, k, k,..., k n S P (X n+ j,..., X n+m j m X k, X k,..., X n k n ) P (X n+ j,..., X n+m j m X n k n ). O-2 {B k } n k, A, C, P (A B k) P (A C) ( k n). P (A B k ) P (A C). 2. (i) j S P j ({X n } j ). (ii) j S P j ({X n } j )..,,,.,. m j T (m) j. T () j T j, T (m) j min{n > T (m ) j ; X n j} ( if { } ).

Markov Processes on Graphs 9 P j (T (m) j, < ) P j (T j < ) m. s, t, P j (T (m) j s + t T (m ) j s) P j (T j t) (, [ ] P (X s+t j, X s+u j ( u t ) T (m ) j s), {X u j} k u S;k u j {X u k u } {T (m ) j s} {X,..., X s ( j)}, 2 O-, O-2.) P (A B) P (B A)P (A)., P j (T (m) j P j (T (m ) j s, T (m) j P j (T (m) j < ) P j (T (m ) j s + t) P j (T (m ) j s)p j (T j t) sm t < T (m) j < ) P j (T (m ) j P j (T (m ) j < )P j (T j < ) < ) P j (T j < ) m. P j ({X n } j ) P j ( m P j (T j < ),. s, T (m) j s + t) {T (m) j < }) lim m P j(t (m) j < ) lim m P j(t j < ) m.,. f m (j, k) : P j (T k m) (m ) Q jk (s) : q n (j, k)s n ( s < ), F jk (s) : n f m (j, k)s m ( s ) m j, k S,. {q n (j, k)} n, {f m (j, k)} m (generating functions). lim Q jk (s) q n (j, k) F jk () P j (T k < ). s n 2. j, k S, : q n (j, k) f m (j, k)q n m (k, k) (n ), Q jk (s) δ jk + F jk (s)q kk (s) ( s < ). m {T k m} {X m k, X s k ( s m )} f (m) j,k q n m(k, k) P j (T k m)p j (X n k X m k) m m P j (T k m)p j (X n k T k m) m P j (X n k, T k m) m P j (X n k) q n (j, k).

Markov Processes on Graphs ( ) n m m nm Q jk (s) δ jk + q n (j, k)s n δ jk + n n m δ jk + F jk (s)q kk (s). f m (j, k)q n m (k, k)s n 2.2 j S q n (j, j). n Q jj (s)( F jj (s)) ( s < ) F jj () P j (T j < ) lim Q jj (s) q n (j, j) s n s. ( : q n (j, j)( P j (T j < )). P j (T j < ) n q n (j, j), P j (T j < ) < n 2.3 j k j S n q n (k, j) < ( k S) q n (j, j) <.) n. (, : [ k S; q n (k, j) j : ].) n ( n q n(k, j) F kj () n q n(j, j).) 2.2 j j k [i.e., n; q n (j, k) > ] P k (T j < )., i, j S,. P i (T j < ) q(i, j) + q(i, k)p k (T j < ). k S;k j (, [, P i (A B) P (A B {X i}) (.) ] P i (T j n X k) P (T j n X i, X k) P (T j n X k) P k (T j n ), P i (X k, T j n) q(i, k)p k (T j n ) P i (T j < ) P i (X k, T j n) P i (X j) + P i (X k, T j n) n k S n2 k j.), q n (j, k) > (k,..., k n ); q(j, k )q(k, k 2 )q(k 2, k 3 ) q(k n, k) >, i j j, k; q(j, k) >, P k (T j < ). k k, i k, k k 2, q(k, k 2 ) >, P k2 (T j < ).,.

Markov Processes on Graphs 2.4 2.3 : j, j k n q n (k, j). j, k S j k k j j k. 2.3 j, k S; j k, j, k.,,. j k, l, m ; q l (j, k) >, q m (k, j) >. n q l+m+n (j, j) q l (j, k)q n (k, k)q m (k, j) (n ) Q jj (s) q n (j, j)s n q l+m+n (j, j)s l+m+n s l+m q l (j, k)q m (k, j)q kk (s). j, n lim Q jj (s) s q n (j, j) < n q n (k, k) <, k. j, k. n 2. 2.3, 2.4 j, k S, n q n(j, k). j, k S, n q n(j, k) <., j, k S, n q n(j, k),. 2.3 d (d-dimensional Random Walks) S Z d ( j (j,..., j d )), d (lattice). {p k } k Z d p k, p k Z d (distribution). 2. (X n, P ) d (d-dim. random walk), {p k } k Z d Z d, {X, X X, X 2 X,... }, P (X n X n k) p k (n, k Z d ) ( {p k } ). k k Z d, p k /(2d) (simple random walk). k (k,..., k d ), k k 2 + + k2 d. P j (X k,..., X n k n ) : P (X k,..., X n k n X j) P j (X n, P j ) j d.

Markov Processes on Graphs 2 2.2 P (A B) : P (A B)/P (B) P (B) >. A, B F P (A B) P (A)., d. Q (q(j, k)) q(j, k) p k j.. 2.5. [,,, ] 2.5 (X n, P ) d. () X n+ X n (X, X,..., X n ), i.e., P (X n+ X n j, X k, X k,..., X n k n ) P (X n+ X n j)p (X k, X k,..., X n k n ). k, k,..., k n Z d, X n+ X n X n. (2) P (X n+ j X k, X k,..., X n k n ) P (X n+ j X n k n ) p j kn. {X n }, q(j, k) p k j. (3). ( j k : j k + + j d k d j k, j k.), Q (q(j, k)) (p k j ),,., : 2.3 d () d, 2 (i.e., P j (T j < )), (2) d 3. 3., q n (, ) n., q 2n+ (, ), q 2n (, ).. ( 2.2.) 2.4 d Q (q(j, k)) () d, 2 n q 2n (, ) { / πn (d ) /(πn) (d 2) a n b n (n ) def a n /b n (n ).

Markov Processes on Graphs 3 (2) d 3 C q 2n (, ) Cn 3/2. 2.6 {a n }, {b n }, a n b n (n ) c, c 2 > ; c b n a n c 2 b n ( n ). 2.3,, : (d 3 (3/π) 3 /4) q 2n (, ) 2 d d d/2 (πn) d/2 (n ).. [ (Stirling s formula)] n! 2πn n+/2 e n (n ). 2.4 d, : d 2, j d 3 q 2n (, ) ( ) 2 n k, 3 q 2n (, ) j,k ;j+kn ( ) 2n 2 2n n πn (2n)! (j!k!) 2 4 2n ( 2n n (n ). ) n j ( ) 2n. n q 2n (, ) j,k,m ;j+k+mn (2n)! (j!k!m!) 2 6 2n ( ) 2 n 4 2n k (2n)! q 2n (, ) c n 3 n 6 2n n!. c n max j,k,m ;j+k+mn (j!k!m!). c n,,. (2.) c n c3 n+3/2 n n 3/2 e n (c > n )., n 3 (m!) 3 (n 3m) (2.2) c n (m!) 2 ((m + )!) (n 3m + ) (m!) ((m + )!) 2 (n 3m + 2),, c, c 2 >. c n n+/2 e n n! c 2 n n+/2 e n 2.7 2. 2.8 (2.2), (2.), d 3 ( ).

Markov Processes on Graphs 4 2.4 - (Galton-Watson Process) Galton-Watson,. n Z n Z + {,, 2,... }., Z. Y. Y Z + (p k ) k, i.e., P (Y k) p k (k ) {Z n }, : i p(i, j) P (Z n+ j Z n i) P ( Y k j) (i, j ). {Y k } (p k ). Z n, p(, i) (i ), p(, ). (p k ),. m : kp k (, )., q GW, q P ( Z ) P ( n ; Z n Z ) P ( Y k)p (Y k) q k p k. k k k k. q, q [, ). f(s) E[s Y ] p k s k ( s ). s, s <. f() p, f(), f () kp k m. k k 2.4 GW {Z n } : m < or m, p > P ( n Z ), i.e., q m > P ( n Z ) >, i.e., q < q m > f(s) s [, ). 2.4 (i) p q ( m ). p m q. (ii) m, p > p + p <., p + p m <. (iii) m > p + p < (p + p m ).

Markov Processes on Graphs 5, P ( ) P ( Z ). E.. f, f f, f n+ f f n (n ). f n (s). 2.5 n, Z, Z n f n, i.e., E [s Zn ] g n (s) E [s Zn ] k sk P (Z n k). n {Z } Z Y, g (s) E[s Y ] f(s). n, g n f n. {Z n k} Z n+ k i Y i, {Y i } Y k E[s Zn+ Z n k] E[ s Yi Z n k] k i k E[s Yi ] f(s) k. g n+ (s) E[s Zn+ Z n k]p (Z n k) f(s) k P (Z n k) g n (f(s)). k, g n+ (s) g n (f(s)) f n (f(s)) f n+ (s). 2.6 E [Z n ] m n (n ). m E[Y ] E [Z ] E[Z n Z n k] E[ k i Y i] km, E [Z n ] k E[Z n Z n k]p (Z n k) k kmp (Z n k) me [Z n ]. i E [Z n ] m k E [Z ] m k. [ 2.4 ] P Z n f n, P (Z n ) f n (). {Z n }, q P ( n ; Z n ) P ( n {Z n }) lim n f n(). f n+ () f(f n ()), n, f, q f(q). (m < ) P (Z n ) E [Z n ] m n, {Z n }, lim P (Z n ) P ( {Z n }) P ( n, Z n ) i.e., q. n n (m ) 2.4 (ii) p > p + p <, k 2; p k >, f (s) k kp k s k < f () k kp k m ( < s < ). s (, ), c (s, ); f() f(s) f (c)( s) < s. f(),, f(s) > s ( < s < ). f() p >, f(s) s [, ] s. q.

Markov Processes on Graphs 6 (m > ) p + p < ( 2.4 (iii)). f () m > f η > ; η < s <, < f (s) < f () m (, ). η < s < f(s) < s. f() p, g(s) f(s) s, s [, ); f(s ) s.. s 2 [, ); s < s 2, f(s 2 ) s 2, g(s i ), f(), g()., s < ξ < s 2 < ξ 2 < ; g (ξ ) g (ξ 2 ), i.e., f (ξ ) f (ξ 2 )., p + p <, s (, ) f (s) k(k )p k s k 2 >. k 2 f (s) s (, ), f (ξ ) f (ξ 2 ). f(s) s q s or q. q q lim n f n (), n ( ), f n () > η. f n+ () f(f n ()) < f n (), f n (n ). q s [, ). 2.3 p p 2 /2,,, 2,, m,. 2.4 Lotka (939). P (Y ) 2, P (Y k) 5 ( ) k 3 (k ). 5 m ( ) k 3 k 5 5 5 4 >. k, q s f(s) 2 + 5 k ( ) k 3 s k,, 3 5 5 s2 s + 2. s 5/6,, q 5/6. /6. 2.9, m 5/4 s f(s) s 5/6,.

Markov Processes on Graphs 7 3 (Continuous-time Markov Chain) t, S ( ) (X t ) t,. s, t, i, j, k ul S, u l < s (l l ), P (X t+s j X s i, X ul k ul (l l )) P (X t+s j X s i).,. P (X t+s j X s i) P (X t j X i). q t (i, j) P (X t j X i),. 3. (Exponential Times),,. ( ). 3. α >, T T (ω) α P (T > t) t αe αs ds e αt. T f(s) αe αs. T α- or (exponential time).,. E[T ] αse αs ds α, V (T ) E[T 2 ] (E[T ]) 2 α 2. 3.. 3. T, (memoryless property). t, s, P (T > t + s T > s) P (T > t). P (T > t + s T > s) P (T > t + s) P (T > s) e (t+s) e s e t P (T > t). 3.2 T, T 2,... T n, α, α 2,..., α n, min{t, T 2,... T n } α + α 2 + + α n -. P (min{t, T 2,... T n } T k ) α k α + α 2 + + α n.

Markov Processes on Graphs 8 n 2, k. P (min{t, T 2 } > t) P (T > t, T 2 > t) P (T > t)p (T 2 > t) e (α +α 2 )t. T, T 2,,. P (min{t, T 2 } T ) P (T < T 2 ) dsα e α s P (s < T 2 ) dsα e α s e α 2s α α + α 2. 3. A B, A -, B 2-.,,.. 3-, /3. 3.2 (Poisson Process),. 3.2 λ >, (X t ) t λ ( λ- ). () X, (2) s < t X t X s λ(t s)., P (X t X s k) e λ(t s) λk (t s) k k! (k,, 2,... ). (3) X t., < t < t 2 < < t n, X t, X t2 X t,..., X tn X tn. 3... 3.2 S,,.

Markov Processes on Graphs 9 X t. t < t 2 < < t n < t n+, X t, X t2 X t,..., X tn+ X tn,, X tn+ X tn (X t,..., X tn ), X tn+ X tn X tn.. P (X tn+ j n+ X tk j k, k n) P (X tn+ X tn j n+ j n X tk j k, k n) P (X tn+ X tn j n+ j n ) P (X tn+ X tn j n+ j n X tn j n ) P (X tn+ j n+ X tn j n ). 3.2 ( ) σ, σ 2,..., λ-. τ n n k σ k, τ, X t n τ n t < τ n+, X t : λ-. n [τn,τ n+)(t) max{n; τ n t},., (X t ) t λ-, τ, τ 2,.... τ, τ 2 τ, τ 3 τ 2,..., λ-. i.e.,. 3.3 n λ- σ k τ n k σ k Γ(n, λ), P (τ < t) t (σ n ), P (σ + + σ n < t) n (n )! λn s n e λs ds. s + s n <t λ n e λ(s + s n ) ds ds n u k s + s k (k,..., n), s u n, s + s n <t λ n e λ(s + s n ) ds ds n t t t t du n un u2 du n un du n du n u3 du n (n )! un n λ n e λu n ds (n )! λn s n e λs du λ n e λu n du 2 u 2 λ n e λu n

Markov Processes on Graphs 2 3.2 τ n σ n+ Γ(n, λ) P (X t n) P (τ n t < τ n+ τ n + σ n+ ) t t ds ds e λt λ n (n )! (n )! λn s n e λs P (t < s + σ n+ ) (n )! λn s n e λs e (t s)λ t s n ds e λt λn t n. n! P (τ n+ > t + s, X t n) P (τ n+ > t + s, τ n t < τ n+ ) P (τ n + σ n+ > t + s, τ n t) t t du du (n )! λn u n e λu P (u + σ n+ > t + s) (n )! λn u n e λu e λ(t+s u) e λ(t+s) λn t n n! (3.) P (τ n+ > t + s X t n) e λs P (τ > s). m,. P (τ n+m > t + s X t n) P (τ m > s). m m + m, P (τ n+m t + s < τ n+m+ X t n) P (τ m s < τ m+ ) P (X s m)., n, m, P (X t n, X t+s X t m) P (X t n, X t+s n + m) n, P (X t n)p (X t+s n + m X t n) P (X t n)p (τ n+m t + s < τ n+m+ X t n) P (X t n)p (X s m) P (X t+s X t m) P (X s m) e λ λm s m. m! m P (X t+s X t m) e λs,.,, (3.), P (τ n > t + s X t n) P (τ n > t + s τ n t < τ n+ ) P (X t+s n X t n) P (τ n t + s < τ n+ X t n) e λs.

Markov Processes on Graphs 2, P (X t n, X t+s X t ) P (X t n, X t+s n) P (X t n)p (X t+s n X t n) P (X t n)e λs. n P (X t+s X t ) e λs., t < < t k, P (X t n, X t X t n,..., X tk X tk n k ) P (X t n, X t N + n,..., X tk n + + n k ) P (X t n )P (X t t n,..., X tk t n + + n k ),. P (X t n, X t X t n,..., X tk X tk n k ) P (X t n )P (X t t n ) P (X tk t k n k ) P (X t n )P (X t X t n ) P (X tk X tk n k ) 3.2 2, 2.,,,, 4. 3.4 X t λ-. X t I II 2, p p. (,,,.) I Y t, II Z t λp, λ( p). X t Y t + Z t, X t n + k, Y t k n + k, k p ( ) n + k P (Y t k, Z t n X t n + k) P (Y t k X t n + k) p k ( p) n. k P (Y t k, Z t n) P (Y t k, Z t n X t n + k)p (X t n + k) ( n + k )p k ( p) n λt (λt)n+k e k (n + k)! λpt (λpt)k λ( p)t (λ( p)t)n e e. k! n!

Markov Processes on Graphs 22 3.3. n k 3 λpt (λpt)k P (Y t k) e. k! λ( p)t (λ( p)t)n P (Z t n) e. n! P (Y t k, Z t n) P (Y t k)p (Z t n). Y t, Z t, λp, λ( p). Y t Y s,, P (Y t+s Y s k) n P (Y t+s Y s k X t+s X s n + k)p (X t+s X s n + k) ( n + k )p k ( p) n λt (λt)n+k e k (n + k)! n λpt (λpt)k e. k! P (Y t+s Y s k) P (Y t k)., (3.2) P (Y s k, Y t+s Y s k 2, Z s n, Z t+s Z s n 2 ) P (Y s k )P (Y t+s Y s k 2 )P (Z s n )P (Z t+s Z s n 2 ), ({X s k + n, X t+s X s k 2 + n 2 }, ) (Y t ), (Z t ), (Y t ) λp-, (Z t ) λ( p)-., (3.3) P (Y s k, Y t+s k + k 2, Z s n, Z t+s n + n 2 ) P (Y s k, Y t+s k + k 2 )P (Z s n, Z t+s n + n 2 ) {Y s, Y s+t } {Z s, Z s+t }, t < t 2 < < t m, {Y t,..., Y tn } {Z t,..., Z tn }. (Y t ), (Z t ). 3.4 (3.2), (3.3). 3.3 (Continuous-time Random Walk), (p j ) j S, i S i + j p j (X t ) t. (X t ) t, (p j ) (Y n ) n (S t ) X t : Y St. (Y n ) (S t ), (X t ), 3.2,.

Markov Processes on Graphs 23 3.4 (Continuous-time Markov Chain & Transition Probability) S (X t ) t,., p(i, j) (Y n ) n - (S t ) t, X t : Y St. s, t, i, j, k ul S ( u l < s) (l l ), P (X t+s j X s i, X ul k ul (l l )) P (X t j X i) : q t (i, j). q t (i, j) Y n n p n (i, j),. q t (i, j) n t tn e n! p n(i, j). [X t : Y St ], q t (i, j), l. u < s, l n. ( (3.4) P X t+s j X s i S s n, X ) ( u k P X t+s j X ) s i S u l S s n q t (i, j). (Y n ) (S t ), (Y n ), (S t ) ( P X t+s j X s i S s n, X ) u k S u l ( P X t+s j, S t+s n + m X s i, S s n, X ) u k, S u l m m P m ( Y n+m j, S t+s S s m Y n i, S s n, Y l k, S u l P (Y n+m j, Y n i, Y l k)p (S t+s S s m)p (S s n, S u l) P (Y n i, Y l k)p (S s n, S u l) m P (Y n+m j Y n i, Y l k)p (S t+s S s m) ) m P (Y m j Y i)p (S t m) q t (i, j)., P (X t+s j X s i, S s n) m P (X t+s j, S t+s S s m X s i, S s n) m P (Y n+m j, Y n i)p (S t+s S s m)p (S s n) P (Y n i)p (S s n) m P (Y n+m j Y n i)p (S t m) q t (i, j). (3.4). q t (i, j) l n, k S, u < s, l n, ( ).. P (X t+s j X s i, X u k) P (X t+s j X s i) q t (i, j).

Markov Processes on Graphs 24. q t (i, j) P (X t j X i) q t (i, j).,. 3.5 {B n }, A, q, P (A B k ) q ( n ). P (A B n ) q. 3.5 ( - ) q t+s (i, j) k S q t (i, k)q s (k, j). [ ] k S P (X t k X i)p (X t+s j X t k) k S P (X t k X i)p (X t+s j X t k, X i) k S P (X t+s j, X t k, X i) P (X i) P (X t+s j, X i) P (X i) P (X t+s j X i) [ ] 3.6 Y n Z + λ i, µ i (i Z +, X t Y Zt. ( µ, λ i >, i µ i >.) q h (i, i + ) λ i h + o(h) q h (i, i ) µ i h + o(h) (i ) q h (i, i) (λ i + µ i )h + o(h) q (i, j) δ ij. lim h q h (i, i). q h (, ), q h (, ). q h (i, j) Y n n p n (i, j), t. q h (i, j) h hn e n! p n(i, j) n e h ( δ ij + hp(i, j) + O(h 2 ) ) δ ij + hp(i, j) + O(h 2 ). p(i, i + ) λ i, p(i, i ) µ i,, p(i, i) (λ i + µ i ) (X t ) S, f : S R, ( Gf(i) lim E i [f(x t )] f(i) ) lim h h h h Ei [f(x t ) f(x )] G (X t ) (generator)., E i [ ] E[ X i].

Markov Processes on Graphs 25 3.3, f : Z + R, Gf(i) λ i f(i + ) + µ i f(i ) (λ i + µ i )f(i). E i [f(x t ) f(x )] t E i [Gf(X s )]ds. h >, E i [f(x h )] f(i + )q h (i, i + ) + f(i )q h (i, i ) + f(i)q h (i, i) + o(h) f(i) + h [λ i f(i + ) + µ i f(i ) (λ i + µ i )f(i)] + o(h) Gf(i)., E i [f(x t ) f(x )] t t t t lim h h Ei [f(x s+h ) f(x s )]ds lim [ h h Ei E Xs [f(x h ) f(x )] ] ds [ ] E i lim h h EX s [f(x h ) f(x )] ds E i [Gf(X s )] ds., lim h E i, f < λ i, µ i <,. f(i) rate λ i f(i + ), rate µ i f(i ), rate λ i µ i. G, (X t ). G (X t ). S,.

Markov Processes on Graphs 26 4 - (Continuous-time Galton- Watson Processes) λ >.,, λ- p k k (k ).,,. t Z t, -. {X n } (p k ) -, {S t } λ-, Z t : X St. m : kp k k. 4. < p + p <. P ( t, Z t ) > m >. t, E[Z t Z ] e λ(m )t.,. E [ ] : E[ Z ], Z t X St E [X n ] m n,. E [Z t ] E [Z t S t n]p (S t n) E [X n S t n]p (S t n) n n n n E [X n ]P (S t n) m n λt (λt)n e e λ(m )t n!

Markov Processes on Graphs 27 5 (Branching Random Walk),,,,. S, O S,. λ >, x S, t. {p(x, y)} y S S, i.e., p(x, y), y p(x, y)., x p(x, y) > y, i.e., x S, #{y S; p(x, y) > } <. 5. [ {b x t b x,λ t }] x, ( ) σ x.,, σ x,y y. σ x.,,. t b x,λ t.,. P (σ x > t) e t, P (σ x,y > t) e tλp(x,y) p(x, y) σ x,y., p(x, y) x y., τ : min{σ x, σ x,y ; y S} + y λp(x, y) +λ. τ σx x, τ σ x,y ( y S) x y. p, τ x min y σ x,y λ-, f P (τ σ x ) P (σ x < τ x ) b x,λ t. b x,λ t, b x,λ t y bx,λ t P (s < τ x )e s ds e λs e s ds + λ. x t (y) b x,λ t y b x,λ t {b x,λ t (y)} y S (y). O S, ρ(λ) : P ( ) t >, b O,λ t. 2. { ( ) λ : inf {λ > ; ρ(λ) > }, λ 2 : inf λ > ; P lim sup b O,λ t (O) t λ λ 2 (lim sup t b O,λ t } >. (O) t >, b O,λ ). 5. S O S {b O,λ t }, γ [, ]; λ, λ 2 γ, γ λ 2. γ > 2. γ [, ] p(x, y),.. 5. ( (super additive theorem)) [, ) f(t), i.e., f(t + s) f(t) + f(s). t

Markov Processes on Graphs 28 lim t t f(t) sup t> f(t) (, ]. t s >. t > s, t s k s,t t k s,t s + (t k s,t s) t k s,t s < s., f(t) k s,t f(s) + f(t k s,t s). m(s) : inf r<s f(r), f, t f(t) t k s,tf(s) + t m(s). t k s,t s < s st, t, s k s,t t < t,, k s,t t s, lim inf t,. t f(t) s f(s) ( s > ). lim inf t lim sup t f(t) sup t s> s f(s). f(t) sup t s> s f(s). P t (x, y) -, x y p(x, y) x, t y P t (x, y) n t tn e n! p n(x, y). P t (O, O) t,, - P t+s (O, O) y S P t (O, y)p s (y, O) P t (O, O)P s (O, O). f(t) log P t (O, O) (super additive ft.)., lim t t log P t(o, O) sup t> t log P t(o, O) : γ (γ ). P t (O, O) e t, γ,, γ. γ > P t (O, O), 2. [λ ] Z t b O,λ t -. ( + λ)-, p /( + λ), p 2 λ/( + λ),, 2. m m 2λ + λ

Markov Processes on Graphs 29. - m, m >. λ m ρ(λ),, λ > m > ρ(λ) >. λ. λ 2 2. 5. E[b x,λ t (O)] e (λ )t P λt (x, O). m(t, x) : E[b x t (O)], m(t+h, x), τ min{σ x, σ x,y ; y S}: ( + λ)-, [, h],,. m(t + h, x) E[b x t+h(o); σ x τ h] + y S E[b x t+h(o); σ x,y τ h] + E[b x t+h(o); τ > h] y S E[b x t (O) + b y t (O)]P (σ x,y τ h) + E[b x t (O)]P (τ > h) y S{m(t, x) + m(t, y)}p (σ x,y h) + m(t, x)p (τ > h) + o(h) y S{m(t, x) + m(t, y)}( e λp(x,y)h ) + m(t, x)e (+λ)h + o(h) y S{m(t, x) + m(t, y)}λp(x, y)h + m(t, x){ ( + λ)h} + o(h). t m(t, x) y S{m(t, x) + m(t, y)}λp(x, y) m(t, x)( + λ) y S λp(x, y)m(t, y) m(t, x)., P t (x, O) n t tn e n! p n(x, O) p n (x, O) p(x, y)p n (y, O) y S t P t (x, O) y S p(x, y)p t (y, O) P t (x, O), P (x, O) δ x,o,, m(t, x) m(, x) δ x,o,. m(t, x) e (λ )t P λt (x, O) 5.2 T > ; E[b O,λ (O)] > lim sup P (b O,λ t (O) ) >. T t b O t b O,λ t b O t, Z n : b x nt (O) ( ) -. t < T b O t b O t,

Markov Processes on Graphs 3 t T O, O b O T., t kt O t [kt, (k + )T ) b O t, t (k + )T, O. Z, Z n b O nt (O), Z n Z n k Y n,k ; (d) (d) Y n,k Z b O T (O),. -, EZ E[ b O T (O)] E[bO T (O)] >., c : P (Z n, n ) >. b O t (x) b O t (x), < c P (Z n, n ) P (b O nt (O), n ) lim sup P (b O t (O) ). t 5. [λ 2 /( γ)] () γ < λ 2 /( γ) λ > /( γ). λ λ 2. ( P (lim sup b O,λ t (O) ) >.) ε > ; λ > /( γ ε). γ t lim t t log P t(o, O) sup t> t log P t(o, O) γ T ; /(λt ) log P λt (O, O) > γ ε. D : λ( γ ε + ) >, E[b O,λ T (O)] e(λ )T P λt (O, O) e DT >. < lim sup t P (b O,λ t (O) ) P (lim sup t b O,λ t (O) ). λ λ 2. λ 2 /( γ). γ, P λt (O, O) e γλt, E[b x,λ t (O)] e (λ )t P λt (x, O) k N, E[b O,λ k (O)] e Ck., C : λ λγ λ( γ) (C ). (2) γ <, /( γ) λ 2. ( () λ 2 /( γ) ). λ < /( γ), C <. A k {b O,λ k (O) }, P (A k ) E[b O,λ k (O)] e Ck k eck <, Borel-Cantelli, P (lim sup A k ). P (lim sup b O,λ t (O) )., P (lim inf A c k ), i.e., t P ( N; k N, b O,λ k (O) ), P (lim sup b O,λ t (O) ) > t k (k, k + ); b O,λ t k (O) k N, t k O k +.,, O, P (σ ) e,, Borel-Cantelli 2,,.. P (lim sup b O,λ t (O) ). λ λ 2, /( γ) λ 2 t. t (3) γ C, λ >, λ λ 2,, λ 2. 5.3 (Borel-Cantelli 2 ) A n F, P (A n ), {A n } P (lim sup A n ). {A c n} ( ), m < n, [ ] n n n P ( A c k) ( P (A k )) e P (Ak) exp P (A k ). km km km km

Markov Processes on Graphs 3 e u u (u ). n, P (A k ) [ ] n P ( A c k) lim P ( A c k) lim exp P (A k ). n n km km km, m, P ( A k ). m k m A k m km k m A k lim sup A k, P (lim sup A k ) lim P ( m k m A k ). {A k } n k {Ac k }n k. 2. 5. ( ) S Z, p(x, x+) p, p(x, x ) p : q.. x λp x +, λq x,. p 2n (O, O) O 2n O p 2n (O, O) (4pq) n / πn (n ),. (5.) lim t t log P t(o, O) 2 pq γ,, γ 2 pq. λ 2 /( γ) /(2 pq), p /2 γ, λ 2 λ. p q 2. (5.) p 2n (O, O) (4pq) n / πn (n ), < C < < C 2 < ; p 2n+ (O, O), C (4pq) n / πn p 2n (O, O) C 2 (4pq) n / πn (n ). P t (O, O) n t 2n e t t2n (2n)! p 2n(O, O) P t (O, O) e t + (2n)! C 2(4pq) n / πn n e t t 2n + C 2 e t (2n)! (2 pq) 2n (/ πn < ) n C 2 e t+2 pqt C 2 e t( +2 pq) (C 2 > ) n t 2n+ (2n + )! et e t et 2 4 if t

Markov Processes on Graphs 32 C 3 C / π <, n 2n + 2 pq t P t (O, O) e t + (2n)! C (4pq) n / πn n e t C 3 t 2n+ + C 3 t t (2n + )! (2 pq) 2n+ n C 3 4t et( +2. t 2n C t 2n+ 3 t e t (2n + )! (2 pq) 2n+ n C pq) 3 4t et( +2. pq) P t (O, O) C 2 e t+2 pqt C 2 e t( +2 pq). 5.2 ( ) d 3, S T d ( T d ) d. (d 2 T 2 Z, d, T d ) x d y, p(x, y) /d. R : 2 d /d, p 2n (O, O) CR 2n n 3/2 (n ).. lim t t log P t(o, O) R γ,, γ R. λ 2 /( γ) /R d/(2 d ), d 3 λ 2 > λ, 2. 6 (Contact Process),,,,,.,,,,.. d 2, S T d T d d. d 2 S Z. O T d. {ηt x η x,λ t } x T d.,, λ >.., P (σ x > t) e t, y x P (σ x,y > t) e tλ, y,. ( 5.2, λ dλ,.).. λ : inf{λ; P ( η O,λ t, t > ) > } λ 2 : inf{λ; P (lim sup η O,λ t (O) ) > } t

Markov Processes on Graphs 33 6. T d T d O T d {η O,λ t },. d λ d 2, λ 2 2 d. λ /d, λ 2 /(2 d ). ( λ/d λ, 5.2 d.),. ( λ > λ λ /d, λ /d, λ 2 /(2 d ).) λ, η t, -. d d, λ,,,, 2. η t η O,λ, O k Z k, i.e., Z, Z k η t (S k ) (x S k P (σ x,y < σ x ) t def, EZ (d )λ/( + λ)., λ > /(d 2) λ λ. λ /(d 2). x k), {Z k } -. dsλe λs P (s < σ x ) λ (d ) + λ > λ > d 2 dsλe λs e s < P (Z k, k ) P ( η O,λ t, t > ). λ + λ 6. Liggett [7] Stacey [],, d 3 λ < λ 2. λ 2. d d+, λ 2 λ 2 (d) in T d T d+ (d ) T d T d+, λ 2 () λ 2 (2) λ 2 (3). λ 2 (d) /(2 d). Liggett, d (T T 2 Z ), λ 2 () 2 ([5], λ 2 ().942, [6])., λ 2 ().639. d 2 λ 2 (d) λ 2 () {/( d )} [8]. /( 2 ) 2 + >.942 > /( 3 ) ( 3 + )/2.366, d 2. d 5,, ( d Grillenberger-Ziezold [4], d 2 Liggett [7], d 3 Pemantle [9]) d.539 λ 2 λ.942, d 2.69 λ 2.942, d 3.425 λ 2 ( 3 + )/2.366254, d 4.354 λ 2, d 5.39 λ 2 ( 5 + )/4.8969.. d,, λ 2 (d) /(2 d) (d ).

Markov Processes on Graphs 34 d, dλ 2 (d) /2 d 2 λ 2, d 3 d 2. Liggett λ 2 (d) /( d )., I [a, b], (a, b], (a, b), [a, b), x η(i) x η s for s I.,, x x, x x.. {x, x 2..., x d, x d+ } O. x i O P (τ O < σ O ) λ/(λ + ), ). {ξ O t } {η t } O x d+. {ξ x i t } (i,..., d) x i O. {ξ x i t }. n 2 ε > r >, t r,. f(t; n) : P O ( O ξ O ([t, t + nr)) ) d ( P O xi ξs O for some s [t, t + (n )r) and O ξ O ((s, t + nr)) ) i d ( P O xi ξ O ([ε, r)) ) ( P xi xi ξ O ([t ε, t ε + (n )r)) ) i ( P xi O ξ O ((, r)) ) ( ) 2 d λ P xi (x i ξ x i ([t ε, t ε + (n )r))) λ + i ( ) 2 λ d f(t ε; n ) λ +, dλ/(λ + ) >, ε > r >,., λ > /( d ), P λ O(lim sup t λ 2 (d) /( d ). f(t; n) f(t ε; n ). η t (O) ) PO(lim λ sup ξt O (O) ) t lim sup f(r + kε; k + ) f(r; ) e r >. k

Markov Processes on Graphs 35 7. 7.. 2. X n, X, ε >, P ( X n X ε) (n ), X n X in pr., X n X. P (X n X), X n X, P -a.s., X n X. (a.s. almost surely ) 7., i.e., X n X, P -a.s. X n X in pr.. ( P (X n X) P { X n X < } P k k N n N k N n N k, lim P { X n X } P N k n N N n N ( k, lim P X N X ) lim N k P N n N (, /k ε >. ) { X n X k } { X n X k } { X n X k } 7.,.,.,,. 7.2, i.e., X n X in pr. {n k }; X nk X a.s.. (, (?) {n k }; P ( X nk X 2 ) k 2 k. Borel-Cantelli P { X nk X < 2 } k. N.) k N.,,. 7. ( (Strong Law of Large Numbers)) X, X 2,... EX n m v : sup n V (X n ) < P ( lim n n ) X k m. k

Markov Processes on Graphs 36 [ ] EX n, S n (X k /k), () Kolmogorov sup k n S k S n (n ) in pr. k (2), {S n } Cauchy,. (3) Kronecker n X k P -a.s. k. Kolmogorov Kronecker,. 7. (Kolmogorov ) {X n }, EX n. S n X n, k a > a 2 P ( max n N S n a) E[ S N 2 ; max n N S n a] E[ S N 2 ] [ ] A k { S k a, S < a,..., S k < a}, S (k+) X k+ + +X N, S (k+) N S k Ak E[S k S (k+) ; A k ] E[S k Ak ]E[S (k+) ]. A A k ( ). E[ S N 2 ; max n N S n a] N E[(S k + S (k+) ) 2 ; A k ] k k N E[Sk 2 + 2S k S (k+) + (S (k+) ) 2 ; A k ] k N E[Sk; 2 A k ] k N a 2 P (A k ) k a 2 P ( max n N S n a) (A k S k a ) 7.2 (Kronecker ) {x n } {a n }; < a n, [ ] s, s n, a n k x k lim n k x k a k exists lim n (x k /a k ) s. k k a k a n x k a k k a n k x k n a k (s k s k ) s n a n k a k+ a k a n s k.

Markov Processes on Graphs 37 s n s n (a k+ a k )s k s a n k. s sup m s m < ε >, N; k N, s k s < ε, n > N, N n (a k+ a k )s k s a n k a n n kn ( s a n n kn (a k+ a k ) s k s + N a n ε a n a N + s a N a a n a n ε (n ) ε >. + a N a n s k (a k+ a k )s + a N a n s (a k+ a k )(sup m ) s m ) + a N a n s [ (.4) ] X n X n X n EX n { X n } V ( X n ) V (X n ) v, EX n. E[X n X m ] E[X n ]E[X m ] (m n), E[Xn] 2 X k V (X n ) v. S n k, Kolmogorov, a >, a 2 P ( max n<k N S k S n a) E[ S N S n 2 ] N, n, N kn+ E[X 2 k ] k 2 k>n k v k 2. lim P (sup S k S n a), i.e., sup k>n S k S n (n ) in pr. n k>n {n j } N; n j, n k lim sup S k S nj j k n j P -a.s. n, m n j S n S m S n S nj + S m S nj (j ) P -a.s.,, {S n } X k Cauchy, lim k lim S n. Kronecker n, lim n n X k P -a.s.. k. 7. {X n }.. V (X k ) < lim 7.2, δ >,. lim n n +δ k (X k EX k ) P -a.s. k X k n k

Markov Processes on Graphs 38 S n (X k / k +δ ). k δ ( ),., Fourier,.,,. 7.2 (Characteristic Functions & Convergence of Distributions) X, φ φ X : R C X (characteristic function). φ(z) φ X (z) : E [ e izx] (z R ). X (distribution) µ(a) µ X (A) : P (X A),. φ(z) R e izx µ(dx) R µ ( (dist.) ), φ(z) µ.. R µ(dx) g(x)dx g(x) ] (x m)2 exp [ 2πv 2v, m, v (normal dist.), (Gauss dist.), N(m, v) ( ).. φ(z) e izx 2πv exp [ ] ] (x m)2 dx exp [imz vz2. 2v 2 7.3. (, ), 3 (, ), (, ), (, ) T (x), i.e., T (x) ( x + + x 2 x ). 2 < a < b <, h >, (a, b) h ( ( 2 T a,b;h (x) ht x a + b )) b a 2

Markov Processes on Graphs 39. h > D a,b;h. D a,b;h (x) min{t a,b;h (x), } T a,b;h (x) T a+(b a)/(2h),b (b a)/(2h);h (x).. 7.4 U, V [, a] (a > ), X U V T a,a;/a.. φ X (z) 2( cos az) a 2 z 2. 7. X φ(z),, E[T a,b;h (X)]. (7.) E[T (X)] π φ(z) cos z z 2 dz, 2h (b a)z i(a+b)z/2 cos 2 φ(z)e π(b a) z 2 e izx T (x)dx 2( cos z) z 2. izx cos z e dz πt (x)., x X,, Fubini E[T (X)] [ ] π E izx cos z e z 2 dz φ X (z) cos z π z 2 dz. z 2 E[T a,b;h (X)],. (7.). ( cos z)/z 2 cos zx( cos z) cos zx (cos z(x + ) + cos z(x )) 2, (7.). cos zx cos z z 2 dz 2 cos z(x + ) z 2 dz + 2 cos z z 2 dz cos z z 2 dz cos z z 2 dz π (7.). 7.5 (i) I(t) (ii) I(t)dt sin z z dz. cos z(x ) z 2 dz ( ) ( x + + x ) x. 2 e tz sin zdz dz,. (iii) (ii) (t > ). cos z z 2 dz π.

Markov Processes on Graphs 4 X, Y a R, P (X > a) P (Y > a), X (d) Y. (X Y in the sense of distribution ) 7.2 X, Y φ X, φ Y, i.e., X (d) Y., φ X (z) φ Y (z) (z R) X Y T a,b;h, E[T a,b;h (X)] E[T a,b;h (Y )], D a,b;h E[D a,b;h (X)] E[D a,b;h (Y )]. lim h D a,b;h(x) I (a,b) (x) Lebesgue P (a < X < b) P (a < Y < b). X (d) Y. 7.3 X {X n } φ(z), {φ n (z)}. lim n φ n(z) φ(z) (z R ) [ ], a < b; P (X a) P (X b), lim n P (X n > a) P (X > a). φ n (z), Lebesgue, lim n i(a+b)z/2 cos((b a)z/2) φ n (z)e z 2 dz i(a+b)z/2 cos((b a)z/2) φ(z)e dz. 7., lim n E[T a,b;h(x n )] E[T a,b;h (X)]. D a,b;h lim n E[D a,b;h(x n )] E[D a,b;h (X)]. h >, a < b, I (a,b) (x) D a,b;h (x) I [a+(b a)/(2h),b (b a)/(2h)] (x) (x R) lim inf n P (a < X n < b) lim n E[D a,b;h(x n )] E[D a,b;h (X)] P h, b, a R, lim inf n P (X n > a) P (X > a). z 2 ( a + b a 2h X b b a ). 2h h, a, b a, a R, lim inf P (X n < a) P (X < a). n lim sup P (X n > a) lim inf P (X n < a) P (X < a) P (X a) n n a R; P (X a), lim n P (X n > a) P (X > a). lim sup P (X n > a) P (X > a). n 7.3 (CLTCentral Limit Theorem) 7.4 (CLT) {X n } (i.i.d.). EX m, V (X ) v n (X k m), N(, ), nv i.e., a < b, lim P n k ( a < nv n k (X k m) < b ) b 2π a e x2 2 dx.

Markov Processes on Graphs 4. 7.3 EX, V (X) E(X 2 ) X, g(z) φ X ( z n ) ) ( z2 o 2n ( ) n (n ). e iz iz + z2 2 z2 g(z) g(z), lim g(z).,, z θ (, ); e iz iz z2 2 eiθz g(z), (t )., exp izx n + izx n z2 X 2 φ X ( z n ) z2 2n + E X 2 g 2n + z2 X 2 n [ z 2 X 2 n ( ) zx g n ( )] zx g n. ( ) ( ) zx zx n X 2, lim g n n, Lebesgue, n.. [CLT ] X n (X n m)/ v E X n, V ( X n ) { X n } i.i.d., m, v. Y n : ( n k X k)/ n, {X k } i.i.d., [ ( iz φ n (z) E exp n n k X k )] n k φ Xk ( z n ) φ X ( z n ) n., z R, ( )) n lim φ n(z) lim ( z2 n n 2n + o exp[ z 2 /2]. n ( z2 2n + o ( n )) n ) n ( z2 + R n (z) 2n R n (z) R n (z) o() (n ) ( )., φ n (z) N(, ) φ(z) exp[ z 2 /2] ( 7.3),,. 7.6 R n (z) o() (n ).

Markov Processes on Graphs 42 [] R. B., (2) [2] (978, 985 5 ) [3] (2) [4] Grillenberger, C. and Ziezold, H. (988). On the critical infection relate of the one dimensional basic contact process: numerical results, J. Appl. Probab. 25, 8. [5] Liggett, T. (985). Interacting Particle Systems, Springer-Verlag. [6] Liggett, T. (995). Improved upper bounds for the contact process critical value, Ann. Probab. 23, 697 723. [7] Liggett, T. (996). Multiple transition points for the contact process on the binary tree, Ann. Probab. 24, 675 7. [8] Liggett, T. (999). Stochastic Interacting Contact, Voter and Exclusion Processes, Springer- Verlag. [9] Pemantle, R. (992). Contact process on trees, Ann. Probab. 2, 289 26. [] Stacey, A. (996). The existence of an intermediates phase for the contact process on trees, Ann. Probab. 24, 7 726.