Markov chains

The future development of the system only depends on the current state, not on any previous states.

It is homogeneous if the transition probabilities are constant.

The transition probabilities make a stochastic matrix, each row sums to 1 and all entries are between 0 and 1 inclusive.

i communicates with j if each can be reached from the other

It partitions the set into communication classes.

closed classes have no way out. Finding the communication classes is easiest done using the diagram.

The period is the gcd of the n's with non zero probability.

irreducible means the whole state space is one communicating class.

h_i^A is the probability of hitting A starting from i.

The vector h satisfies eqns h=hP if I not in A, 1 if it is. and is the smallest non-negative solution.

Expected time before absorbtion. The vector of mean hitting times satisfies
k_i = 0 if i ∈ A
k_i = 1 + Σ P_ij k_j otherwise

A state is recurrent if the prob of returning is 1, transient otherwise.

First passage time is the first time to return to element i.