Discrete-time Markov chain: Difference between revisions

Revision as of 15:23, 1 August 2020

Revision as of 19:15, 1 August 2020

Line 12:

:<math>\Pr(X_{n+1}=x\mid X_1=x_1, X_2=x_2, \ldots, X_n=x_n) = \Pr(X_{n+1}=x\mid X_n=x_n),</math> if both [[conditional probability|conditional probabilities]] are well defined, that is, if <math>\Pr(X_1=x_1,\ldots,X_n=x_n)>0.</math>

The possible values of ''X''_''i'' form a [[countable set]] ''S'' called the state space of the chain.<ref name="PRS">{{cite book | title=Probability and Random Processes | first2=D. R. | last2=Stirzaker | first1=G. R. | last1=Grimmett | author-link=Geoffrey Grimmett | year=1992 |edition=second | publisher=Oxford University Press|ISBN=0198572220 |chapter=6}}</ref>

Markov chains are often described by a sequence of [[directed graph]]s, where the edges of graph ''n'' are labeled by the probabilities of going from one state at time ''n'' to the other states at time ''n''&nbsp;+&nbsp;1, <math>\Pr(X_{n+1}=x\mid X_n=x_n).</math> The same information is represented by the transition matrix from time ''n'' to time ''n''&nbsp;+&nbsp;1. However, Markov chains are frequently assumed to be time-homogeneous (see variations below), in which case the graph and matrix are independent of ''n'' and are thus not presented as sequences.

These descriptions highlight the structure of the Markov chain that is independent of the initial distribution <math>\Pr(X_1=x_1).</math> When time-homogeneous, the chain can be interpreted as a [[Finite-state machine|state machine]] assigning a probability of hopping from each vertex or state to an adjacent one. The probability <math>\Pr(X_n=x\mid X_1=x_1)</math> of the machine's state can be analyzed as the statistical behavior of the machine with an element <math>x_1</math> of the state space as input, or as the behavior of the machine with the initial distribution <math>\Pr(X_1=y)=[x_1=y]</math> of states as input, where <math>[P]</math> is the [[Iverson bracket]].{{cn|date=August 2020}}

The fact that some sequences of states might have zero probability of occurring corresponds to a graph with multiple [[connected component (graph theory)|connected components]], where we omit edges that would carry a zero transition probability. For example, if ''a'' has a nonzero probability of going to ''b'', but ''a'' and ''x'' lie in different connected components of the graph, then <math>\Pr(X_{n+1}=b\mid X_n=a)</math> is defined, while <math>\Pr(X_{n+1}=b\mid X_1=x, \ldots, X_n=a)</math> is not.

====Variations====

*{{Anchor|homogeneous}}Time-homogeneous Markov chains (or stationary Markov chains) are processes where

::<math>\Pr(X_{n+1}=x\mid X_n=y) = \Pr(X_n=x\mid X_{n-1}=y)</math>

:for all ''n''. The probability of the transition is independent of ''n''.<ref name="PRS"/>

*A Markov chain with memory (or a Markov chain of order ''m'')

:where ''m'' is finite, is a process satisfying

Line 34 ⟶ 32:

</math>

:In other words, the future state depends on the past ''m'' states. It is possible to construct a chain <math>(Y_n)</math> from <math>(X_n)</math> which has the 'classical' Markov property by taking as state space the ordered ''m''-tuples of ''X'' values, ie. <math>Y_n= \left( X_n,X_{n-1},\ldots,X_{n-m+1} \right)</math>.{{cn|date=August 2020}}

==Properties==

===Reducibility===

A Markov chain is said to be irreducible if it is possible to get to any state from any state.<ref name=":0">{{cite book|title=Markov Chains: From Theory to Implementation and Experimentation|last=Gagniuc|first=Paul A.|publisher=John Wiley & Sons|year=2017|isbn=978-1-119-38755-8|___location=USA, NJ|pages=1–235}}</ref> The following explains this definition more formally.

==Communicating classes and properties==

A state ''j'' is said to be accessible from a state ''i'' (written ''i''&nbsp;→&nbsp;''j'') if a system started in state ''i'' has a non-zero probability of transitioning into state ''j'' at some point. Formally, state ''j'' is accessible from state ''i'' if there exists an integer ''n_ij''&nbsp;≥&nbsp;0 such that

:<math> \Pr(X_{n_{ij}}=j \mid X_0=i) = p_{ij}^{(n_{ij})} > 0.</math>

A state ''i'' is said to communicate with state ''j'' (written ''i''&nbsp;↔&nbsp;''j'') if both ''i''&nbsp;→&nbsp;''j'' and ''j''&nbsp;→&nbsp;''i''. A communicating class is a maximal set of states ''C'' such that every pair of states in ''C'' communicates with each other. Communication is an [[equivalence relation]], and communicating classes are the [[equivalence class]]es of this relation.<ref name="PRS"/>

This integer is allowed to be different for each pair of states, hence the subscripts in n_ij.

Allowing ''n'' to be zero means that every state is accessible from itself by definition. The accessibility relation is reflexive and transitive, but not necessarily symmetric.

A communicating class is closed if the probability of leaving the class is zero, namely if ''i'' is in ''C'' but ''j'' is not, then ''j'' is not accessible from&nbsp;''i''.<ref name="PRS"/> The set of communicating classes forms a [[directed acyclic graph|directed, acyclic graph]] by inheriting the arrows from the original state space. A communicating class is closed if and only if it has no outgoing arrows in this graph.

A state ''i'' is said to communicate with state ''j'' (written ''i''&nbsp;↔&nbsp;''j'') if both ''i''&nbsp;→&nbsp;''j'' and ''j''&nbsp;→&nbsp;''i''. A communicating class is a maximal set of states ''C'' such that every pair of states in ''C'' communicates with each other. Communication is an [[equivalence relation]], and communicating classes are the [[equivalence class]]es of this relation.

A communicating class is closed if the probability of leaving the class is zero, namely if ''i'' is in ''C'' but ''j'' is not, then ''j'' is not accessible from&nbsp;''i''. The set of communicating classes forms a [[directed acyclic graph|directed, acyclic graph]] by inheriting the arrows from the original state space. A communicating class is closed if and only if it has no outgoing arrows in this graph.

A state ''i'' is said to be essential or final if for all ''j'' such that ''i''&nbsp;→&nbsp;''j'' it is also true that ''j''&nbsp;→&nbsp;''i''. A state ''i'' is inessential if it is not essential.<ref>{{cite book|last=Asher Levin|first=David|title=Markov chains and mixing times|page=[https://archive.org/details/markovchainsmixi00levi_364/page/n31 16]|title-link= Markov Chains and Mixing Times |isbn=978-0-8218-4739-8|year=2009}}</ref> A state is final if and only if its communicating class is closed.

A Markov chain is said to be irreducible if its state space is a single communicating class; in other words, if it is possible to get to any state from any state.<ref name="PRS"/><ref name=":0">{{cite book|title=Markov Chains: From Theory to Implementation and Experimentation|last=Gagniuc|first=Paul A.|publisher=John Wiley & Sons|year=2017|isbn=978-1-119-38755-8|___location=USA, NJ|pages=1–235}}</ref>

===Periodicity===

Line 60 ⟶ 52:

:<math> k = \gcd\{ n > 0: \Pr(X_n = i \mid X_0 = i) > 0\}</math>

(where <math>\gcd</math> is the [[greatest common divisor]]) provided that this set is not empty. Otherwise the period is not defined.<ref name="PRS"/> Note that even though a state has period <math>k</math>, it may not be possible to reach the state in <math>k</math> steps. For example, suppose it is possible to return to the state in <math>\{6,~8,~10,~12,\dots\}</math> time steps; <math>k</math> would be <math>2</math>, even though <math>2</math> does not appear in this list.

If <math>k = 1</math>, then the state is said to be aperiodic. Otherwise (<math> k > 1</math>), the state is said to be periodic with period&nbsp;<math>k</math>. Periodicity is a class property—that is, if a state has period <math>k</math> then every state in its communicating class has period <math>k</math>.<ref name="PRS"/>

If <math>k = 1</math>, then the state is said to be aperiodic.

Otherwise (<math> k > 1</math>), the state is said to be periodic with period&nbsp;<math>k</math>. A Markov chain is aperiodic if every state is aperiodic. An irreducible Markov chain only needs one aperiodic state to imply all states are aperiodic.

Every state of a [[bipartite graph]] has an even period.

==={{anchor|Transience}}{{anchor|Recurrence}}Transience and recurrence===

Line 81 ⟶ 70:

:<math> \Pr(T_i < \infty \mid X_0 = i) = \sum_{n=1}^\infty f_{ii}^{(n)} < 1. </math>

State ''i'' is recurrent (or persistent) if it is not transient. Recurrence and transience are class properties, that is, they either hold or do not hold equally for all members of a communicating class.<ref name="PRS"/>

Recurrent states are guaranteed (with probability 1) to have a finite hitting time.

Recurrence and transience are class properties, that is, they either hold or do not hold equally for all members of a communicating class.

It can be shown that aA state ''i'' is recurrent [[if and only if]] the expected number of visits to this state''i'' is infinite:<ref name="PRS"/>

====Mean recurrence time====

Even if the hitting time is finite with probability ''1'', it need not have a finite [[expected value|expectation]]<!-- Should provide example later for this and reference it here -->.

The mean recurrence time at state ''i'' is the expected return time ''M_i'':

:<math> M_i = E[T_i]=\sum_{n=10}^\infty n\cdot f_p_{ii}^{(n)} = \infty.</math>

====MeanPositive recurrence time====

State ''i'' is positive recurrent (or non-null persistent) if ''M_i'' is finite; otherwise, state ''i'' is null recurrent (or null persistent).

Even if the hitting time is finite with probability ''1'', it need not have a finite [[expected value|expectation]]<!-- Should provide example later for this and reference it here -->. The mean recurrence time at state ''i'' is the expected return time ''M_i'':

:<math> M_i = E[T_i]=\sum_{n=01}^\infty p_n\cdot f_{ii}^{(n)} = \infty.</math>

====Expected number of visits====

It can be shown that a state ''i'' is recurrent [[if and only if]] the expected number of visits to this state is infinite:

State ''i'' is positive recurrent (or non-null persistent) if ''M_i'' is finite; otherwise, state ''i'' is null recurrent (or null persistent). Positive and null recurrence are classes properties.<ref name="PRS"/>

:<math>\sum_{n=0}^\infty p_{ii}^{(n)} = \infty.</math>

====Absorbing states====

Line 110 ⟶ 95:

:<math>\pi_i \Pr(X_{n+1} = j \mid X_{n} = i) = \pi_j \Pr(X_{n+1} = i \mid X_{n} = j)</math>

for all times ''n'' and all states ''i'' and ''j''. This condition is known as the '''[[detailed balance]]''' condition (some books call it theor local balance equation).

Considering a fixed arbitrary time ''n'' and using the shorthand

Line 118 ⟶ 103:

the detailed balance equation can be written more compactly as

:<math>\pi_i p_{ij} = \pi_j p_{ji}\,.</math><ref name="PRS"/>

The single time-step from ''n'' to ''n''&nbsp;+&nbsp;1 can be thought of as each person ''i'' having {{pi}}_''i'' dollars initially and paying each person ''j'' a fraction ''p_ij'' of it. The detailed balance condition states that upon each payment, the other person pays exactly the same amount of money back.<ref name="Durrett2012">{{cite book|url=https://books.google.com/books?id=i_Ovy6OvI54C&pg=PA37|title=Essentials of Stochastic Processes|author=Richard Durrett|date=19 May 2012|publisher=Springer Science & Business Media|isbn=978-1-4614-3615-7|page=37|archiveurl=https://web.archive.org/web/20170206031627/https://books.google.com/books?id=i_Ovy6OvI54C&pg=PA37|archivedate=6 February 2017|url-status=live}}</ref> Clearly the total amount of money '''{{pi}}''' each person has remains the same after the time-step, since every dollar spent is balanced by a corresponding dollar received. This can be shown more formally by the equality

Line 159 ⟶ 144:

:<math>p_{ij}^{(n)} = \sum_{r \in S} p_{ir}^{(k)} p_{rj}^{(n-k)}</math>

where ''S'' is the state space of the Markov chain.<ref name="PRS"/>

The [[marginal distribution]] Pr(''X''_''n''&nbsp;=&nbsp;''x'') is the distribution over states at time ''n''. The initial distribution is Pr(''X''₀&nbsp;=&nbsp;''x''). The evolution of the process through one time step is described by

Line 168 ⟶ 153:

===Hitting times===

{{Main|Phase-type distribution}}The hitting time is the time, starting in a given set of states until the chain arrives in a given state or set of states. The distribution of such a time period has a phase type distribution. The simplest such distribution is that of a single exponentially distributed transition.{{cn|date=August 2020}}

====Expected hitting times====