Irreducibility y is accessible from x: access t,Pt(x,y)>0 communicate .x communicates with y: 。x is accessible from y ·y is accessible from x MC is irreducible:all pairs of states communicate communicating classes
Irreducibility • y is accessible from x: • x communicates with y: • x is accessible from y • y is accessible from x • MC is irreducible: all pairs of states communicate x y access communicate 1 2 1 2 1 3 2 3 3 4 1 4 3 4 1 4 communicating classes 9t, Pt (x, y) > 0
Reducible Chains component component P = PA A B stationary distributions:π=λπA+(1-)πB component component A B stationary distribution:=(0,TB)
Reducible Chains component A component B P = PA 0 0 PB ⇥ component A component B stationary distributions: ⇥ = ⇥A + (1 )⇥B stationary distribution: = (0, B)
Aperiodicity period of state x: da=gcd{t Pr(x,x)>0 aperiodic chain:all states have period 1 period:the gcd of lengths of cycles da 3 x □□△□□△□□△·
Aperiodicity • period of state x: • aperiodic chain: all states have period 1 • period: the gcd of lengths of cycles x dx = gcd{t | Pt (x, x) > 0} dx = 3
Lemma (period is a class property) x and y communicate da dy ni V cycle of y x y m n2 gl0g时}。→运
x y n1 n2 n Lemma (period is a class property) x and y communicate dx = dy 8 cycle of y dx | (n1 + n2) dx | (n1 + n2 + n) o ) dx | n ) dx dy
Fundamental Theorem of Markov Chain: If a finite Markov chain=(,P)is irreducible and aperiodic,then initial distribution(0) limπ(o)Pt=π →00 where is a unique stationary distribution satisfying πP=π finiteness existence irreducibility uniqueness Perron-Frobenius ergodicity > convergence
If a finite Markov chain is irreducible and aperiodic, then ∀ initial distribution M = (⌦, P) ⇡(0) lim t!1 ⇡(0)Pt = ⇡ where is a ⇡ unique stationary distribution satisfying ⇡P = ⇡ Fundamental Theorem of Markov Chain: finiteness existence irreducibility uniqueness ergodicity convergence Perron-Frobenius }