Markov chains irreducible

Irreducible chain. Perhaps the most important class of Markov chains is the class of irreducible chains. An irreducible chain is one in which all pairs of states communicate, i.e., pjk(n) > 0 for some integer n where j, k = 1, 2,..., Z the latter is the number of states. In other words, every state can be reached from every other state. The following matrix, corresponding to example 2.32... 

Some sufficient conditions for a finite Markov chain to be ergodic are based on the following theorems, given without proof [17, pp.247-255]. The first one states that A finite irreducible aperiodic Markov chain is ergodic. Let ... 

On the basis of the following theorem, i.e., if the transition matrix P for a finite irreducible aperiodic Markov chain with Z states is doubly stochastic, then the stationary probabilities are given by... 

Dennition. Closed sets of states. A non empty set C of states is called a closed set if each state in C communicates only with other states in C. In other words, no state outside C can be reached from any state in C. A single state Sk forming a closed set is an absorbing state. Once a closed set is entered it is never vacated. If j belongs to a closed set C then pjk = 0 for all k outside C. Hence, if all rows and columns of P corresponding to states outside C are deleted from P, we are still left with a stochastic matrix obeying Eqs.(2-17) and (2-18). A Markov chain is irreducible if there exists no closed set other than the set of all states. 

These are called the steady-state equations. A Markov chain is said to be inedudble if any state can be reached from any other through a sequence of transitions whose probabdities are positive. For irreducible chains, there is precisely one steady-state distribution ir, and it is the only vector x that satisfies the steady-state equations xP = x and also satisfies the condition x, -f Xj H-. . . H- = 1. 

This chain is irreducible because each state may be reached from the other. Its steady-state distribufion may be computed by solving (22) to give iTj = 2/3 and iTj = 1/3. Figure 1(b) represents a Markov chain that is not irreducible because, for example, state 1 caimot be reached from state 3. 

We summarize the discussion of steady-state behavior of Markov chains as follows. For well-behaved chains, such as irreducible, aperiodic, finite-state chains, there is a unique steady-state distribution that is also the limiting distribution. Furthermore, this distribution gives the long-run fraction of time spent in each state. It may be computed easily, by solving the steady-state equations (22). The steady-state behavior of the chain does not depend on the initial state. 

Let us briefly describe the long-run behavior of continuous-time, finite-state Markov chains. We assume irreducibility as before, which in this case means simply that the entries of P(t) are all positive fort > 0. Periodicity does not arise in continuous time. There is a unique distribution w satisfying... 

TMs relates it to the parameters of the cham—the entries of its generator Q. These are the steady-state equations in the continuous-time case. For finite-state irreducible chains, these equations have a unique solution whose components add to 1, and this solution is the steady-state distribution v. As in the discrete-time case, it is also the limiting distribution of the Markov chain and gives the long-run proportion of time spent in each state. These results extend to the infinite-state case, assuming positive recurrence, as in Subsection 3.3. 

These equations are called the traffic equations. Invertibility of I - P implies that these equations have a unique solution in the Suppose now that p < s , > 0 and fjL > 0 for each m = 1, 2,. . . , Af. These conditions ensure that the network is an irreducible, positive recurrent Markov chain. Jackson proved the following result The steady-state distribution of the number of jobs at each station in the Jackson network is the same as that of M independent stations, the mth being an MIMIs queue with arrival rate and service rate... 

This condition is known as the capacity condition. It ensures that sufficient service capacity is available to handle the arriving work. Special cases of this condition have arisen at several earlier points in this chapter. If the station service rates and the class total arrival rates are aU positive, then (57) implies that the standard multiclass product-form network is an irreducible, positive recurrent Markov chain. Remarkably, an explicit formula for the steady-state distribution of this network is known (Kelly 1979). While the formula is complicated, it has a simple description in words. 

Fig. 6.6 A Markov matrix (left) and its graph representation (right). In this example, the Markov Chain is not irreducible...

A very useful representation of the Markov Chain ttansition matrix II is by use of a weighted directed graph in which each node represents a state of the Markov Chain and the weights represent transition probabilities. Then one may understand irreducibility as expressing the connectedness of this graph (see Fig. 6.6). 

The fundamental result for Markov chains is the following If a given Markov chain is both irreducible and aperiodic, then it can be shown that there is a unique invariant distribution such that... 

It is easy to show that this choice of transition probabilities satisfies Eq. (16) and the Markov chain will be irreducible provided that -rij > 0 for all statesy, and the underlying symmetric Markov chain is irreducible. An alternative set of transition probabilities referred to as Barker sampling has also been used from time to time, i.e.. 

Two states accessible from each other in a Markov chain are said to communicate. A class of stafes is a group of sfafes fhaf communicafe wifh each other. If a Markov chain has only one class, fhen if is said to be irreducible. The period in a Markov chain is fhe minimum number of fransifions required to return to a state upon leaving it. A Markov chain of period one is called aperiodic. 

An abstract equivalence classes (AEC), denoted by ( = l,2,...,m ), is a set of literals by which all members of this set communicate with one another, k corresponds to the number of Cj. C a . If the abstract literal space oj consists of a single AEC (i.e. k = 1), is called irreducible to be consistent with the terminology used in Markov Chains (Kao 1997). Therefore, irreducibility implies that the literals of the original literal space Q all communicate with one another. Because AECs are developed based on an equivalence relation (i.e. communication), then the following must hold ... 

Recall the well-known theorem of the standard theory of the ergodic Markov chains one can state the following (e.g. Feller [4]) In any finite irreducible, aperiodic Markov chain with the transition matrix P, the limit of the power matrices/ exists if r tends to infinity. This limit matrix has identical rows, its rows are the stationary probability vector of the Markov chain, y = [v,Vj,...,v,...,v ], that is v = v P, fiuthermore v, >0 ( = 1,...,R) and... 

In Section 5.1 we introduce the stochastic processes. In Section 5.2 we will introduce Markov chains and define some terms associated with them. In Section 5.3 we find the n-step transition probability matrix in terms of one-step transition probability matrix for time invariant Markov chains with a finite state space. Then we investigate when a Markov ehain has a long-run distribution and discover the relationship between the long-run distribution of the Markov chain and the steady state equation. In Section 5.4 we classify the states of a Markov chain with a discrete state space, and find that all states in an irreducible Markov chain are of the same type. In Section 5.5 we investigate sampling from a Markov chain. In Section 5.6 we look at time-reversible Markov chains and discover the detailed balance conditions, which are needed to find a Markov chain with a given steady state distribution. In Section 5.7 we look at Markov chains with a continuous state space to determine the features analogous to those for discrete space Markov chains. 

State j is reachable from state i if > 0 for some n. When state j is reachable from state i, and state i is reachable from state j, then the pair of states are said to communicate with each other. A set of states such that every pair of slates inside the class communicate with each other, and no state outside the set is reachable from inside the set, is called a communicating class of states. It is a minimal closed set of states. A Markov chain consisting of a single communicating class is called an irreducible chain. Otherwise, it is called a reducible chain. 

We will consider time-invariant Markov chains that are irreducible and aperiodic and where all states are positive recurrent. Chains having these properties are called ergodic. This type of chain is important as there are theorems which show that for this type of chain, the time average of a single realization approach the average of all possible realizations of the same Markov chain (called the ensemble) at some... 

Equation 5.16 says that the Uj area solution of the steady state equation. Thus the theorem says that if a unique non-zero solution of the steady state equation exists the chain is ergodic, and vice-versa. A consequence of this theorem is that time averages from an ergodic Markov chain will approach the steady state probabilities of the chain. Note, however, for an aperiodic irreducible Markov chain that has all null recurrent states, the mean recurrence times are infinite, and hence Uj = 0 for such a chain. The only solution to the steady state equation for such a chain is Uj = 0 for all j. It is very important that we make sure all chains that we use are ergodic and contain only positive recurrent states Note also that the theorem does not say anything about the rate the time averages converges to the steady state probabilities. 

All states of an irreducible Markov chain are the same type transient, null recurrent, or positive recurrent. 

AH states in an eigodic (irreducible and aperiodic) Markov chain are positive recurrent if and only if there is a unique non-zero solution to the steady state Equation 5.18. 

A Markov chain is irreducible if every state j can be reached fiom every other state i. 

An aperiodic irreducible Markov chain with positive recurrent states has a unique non-zero solution to the steady state equation, and vice-versa. These are known as ergodic Markov chains. 

For an irreducible Markov chain with null recurrent states, the only solution to the steady state equation is identically equal to zero. 

E. Nummelin, General Irreducible Markov Chains and Non-Negative Operators (Cambridge University Press, Cambridge, UK, 1984). 

With the exception of the case of uj V, both the poly-converge as N —> oo to the same limit distribution of an irreducible Markov chain on Z. This Markov chain is ... 

By the Ergodic Theorem for irreducible aperiodic Markov chains one also has that... 

---