Loading...

​​Discussion 13B

​​Markov Chains

​​A Markov chain is irreducible when you can go from any state to any other state. 

​​In general directed graphs, this is called strongly connected. A set of vertices that is strongly connected is a strongly connected component. A directed graph can be decomposed into what’s called a SCC metagraph, which is a graph where each vertex represents a strongly connected component in the original graph.

​​This is why a Markov chain that doesn’t satisfy the above property is called reducible. 

​​

• ​​If a Markov chain is finite and irreducible, then there exists a unique stationary distribution.

​​

​​A Markov chain is periodic with period ​​$d$​ if the greatest common divisor of all tour lengths is ​​$d$​.

​​

• ​​If a Markov chain is finite, irreducible, and aperiodic, then the distribution of ​​$X_n$​ approaches the stationary distribution as ​​$n$​ increases. 

​​Absorption Probabilities

​​What’s the probability of reaching state ​​$A$​ before state ​​$B$​?

​​Define ​​$\alpha(i)$​ as the probability of reaching ​​$A$​ before ​​$B$​ if you start at ​​$i$​. Then ​​$\alpha(i) = \sum_j P_{i,j} \alpha(j)$​.

​​This can be extended to deal with sets of states ​​$\mathcal{A}$​ and ​​$\mathcal{B}$​.

​​Hitting Times

​​What’s the expected number of transitions required to reach state ​​$A$​?

​​Define ​​$\beta(i)$​ as the expected number of transitions required to reach ​​$A$​ if you start at ​​$i$​. Then ​​$\beta(i) = \sum_j P_{i,j} (1 + \beta(j)) = 1 + \sum_j P_{i,j} \beta(j)$​.

​​This can be extended to deal with a set of states ​​$\mathcal{A}$​.

​​