16.1 Elements of markov sequences  (Page 8/13)

There is a one-one relation between the transition diagram and the transition matrix P . The transition diagram not only aids in visualizing the dynamic evolution of a chain, but also displays certain structural properties.Often a chain may be decomposed usefully into subchains. Questions of communication and recurrence may be answered in terms of the transition diagram. Some subsets of states are essentially closed , in the sense that if the system arrives at any one state in the subset it cannever reach a state outside the subset. Periodicities can sometimes be seen, although it is usually easier to use the diagram to show that periodicitiescannot occur.

Classification of states

Many important characteristics of a Markov chain can be studied by considering the number of visits to an arbitrarily chosen, but fixed, state.

Definition . For a fixed state j , let

• $T_1=$ the time (stage number) of the first visit to state j (after the initial period).
• $F_k(i,j)=P(T_i=k|X_0=i)$ , the probability of reaching state j for the first time from state i in k steps.
• ${\displaystyle F(i,j)=P(T_i<\infty |X_0=i)=\sum _{k=1}^{\infty }{F}_k(i,j)}$ , the probability of ever reaching state j from state i .

A number of important theorems may be developed for F _k and F , although we do not develop them in this treatment. We simply quote them as needed.An important classification of states is made in terms of F .

Definition . State j is said to be transient iff $F(j,j)<1$ ,

and is said to be recurrent iff $F(j,j)=1$ .

Remark . If the state space E is infinite, recurrent states fall into one of two subclasses: positive or null. Only the positive case is common inthe infinite case, and that is the only possible case for systems with finite state space.

Sometimes there is a regularity in the structure of a Markov sequence that results in periodicities.

Definition . For state j , let

If $\delta >1$ , then state j is periodic with period δ ; otherwise, state j is aperiodic .

Usually if there are any self loops in the transition diagram (positive probabilities on the diagonal of the transition matrix P ) the system is aperiodic. Unless stated otherwise, we limit consideration to the aperiodic case.

Definition . A state j is called ergodic iff it is positive, recurrent, and aperiodic.

It is called absorbing iff $p(j,j)=1$ .

A recurrent state is one to which the system eventually returns, hence is visited an infinity of times. If it is absorbing, then once it is reached it returns each step(i.e., never leaves).

An arrow notation is used to indicate important relations between states.

Definition . We say

• State i reaches j , denoted $i\to j$ , iff $p^n(i,j)>0$ for some $n>0$ .
• States i and j communicate, denoted $i\leftrightarrow j$ iff both i reaches j and j reaches i .

By including j reaches j in all cases, the relation $\leftrightarrow$ is an equivalence relation (i.e., is reflexive, transitive, and idempotent). With thisrelationship, we can define important classes.

Definition . A class of states is communicating iff every state in the class may be reached from every other state in the class (i.e. every pair communicates). A class is closed if no state outside the class can be reached from within the class.