Why do we need Markov chain


Next page:Stationary initial distributions Upwards:Ergodicity and Stationarity Previous page:Estimation of the speed of convergence; Perron-Frobenius theorem & nbsp content


Irreducibility and aperiodicity

proof
 
Notice
 
  • The property of accessibility is
  • The quality of communicating is one Equivalence relationbecause it applies
    (a)
    (Reflexivity),
    (b)
    exactly when (Symmetry),
    (c)
    and imply that (Transitivity).
  • This means in particular
Examples
 


In addition to the irreducibility, we need another property of the states, namely the so-called Aperiodicityin order to be able to characterize the ergodicity of Markov chains in a simple way.

definition
 


We now show that the periods and match if the states belong to the same equivalence class of communicating states. We use the notation if .

Theorem 2.8 If the states communicate, then applies .
proof
 
Corollary 2.5   The Markov chain be irreducible. Then all of the states of the same period.


To be able to show

  • that the characterization of the ergodicity of Markov chains considered in Section 2.2.1 (cf.Theorem 2.4) is synonymous with their irreducibility and aperiodicity,
  • we still need the following elementary proposition from Number theory.
Lemma 2.3 Be any, but fixed, natural number. Then there is a natural number , so that
proof
 
Theorem 2.9   The transition matrix is quasi-positive if and only if is irreducible and aperiodic.
proof
 
  • We first assume that the transition matrix is irreducible and aperiodic.
    • For each let's look at the crowd , whose greatest common divisor is due to the aperiodicity of equal is.
    • From the inequalities in Corollary 2.2 it follows that
      and thus
          (50)

  • We show the crowd contains two consecutive numbers.
  • Be now . Because of (50) then also holds and for any , in which
    (51)

  • However, we show
    • that there are then natural numbers there so the difference between and less than is.
    • From (51) it follows that
      and thus for
  • That is why the crowd contains two consecutive numbers.
  • From (50) and from Lemma 2.3 it follows that for each a there so that
    (52)

  • From this, from the irreducibility of and from the inequality (25) in Corollary 2.2, i.e.,
    that it follows for every couple of states is a natural number there so that
    i.e., is quasi-positive.
  • Conversely, the irreducibility and aperiodicity of quasi-positive transition matrices result directly from the definitions of these terms.

Notice
 
  • A simple example of a Markov chain that Not is irreducible,
    • can through the model of the Weather forecast given, where and
    • If or , then the associated Markov chain is obviously not irreducible (and therefore also not ergodic because of Theorem 2.9).
  • It is still possible that the linear system of equations
    (53)

    one (or infinitely many) probabilistic solutions owns.
  • We now give examples of Markov chains to the Not are aperiodic.
    • Here are the random variables Not by a stochastic recursion equation given the shape (14), so that the "increments" are independent and identically distributed random variables.
    • We only assume that the random variables are "conditionally independent" in the following sense.
    • As shown in Section 2.1.3, however, one can always choose to Construct stochastically equivalent Markov chains, the increments of which are independent, cf. the construction principle considered in (17) - (19).
  • So be and arbitrary finite (or countably infinite) sets, be any function, and be or. Random variables,
  • One can show (see exercise 4.2) that the sequence given recursively by (54) is a Markov chain whose transition matrix is given by
    if for each .
example
(Diffusion model)
see P. Brémaud (1999) Markov Chains. Springer-Verlag, New York, p.76
Notice
 
  • The Ehrenfest diffusion model is a special case of the following class of Markov chains used in the literature Birth and death processes with two reflective barriers to be named.
  • The state space becomes again here considered while the transition matrix is given by
    (58)

    in which , and for each .
  • The linear system of equations then has the form
    • One can show (see exercise 4.3) that
    • in which by the normalization condition is given, i.e.
      or.
  • Because we assume that and for each holds true, birth and death processes are apparently irreducible with two reflective barriers.
  • If in addition for a holds, then birth and death processes with two reflective barriers are also aperiodic (and thus ergodic because of Theorem 2.9), see exercise 4.3.


Next page:Stationary initial distributions Upwards:Ergodicity and Stationarity Previous page:Estimation of the speed of convergence; Perron-Frobenius theorem & nbsp content Ursa Pantle 2003-09-29