Markov Chain

• A stochastic process is said to be Markovian or has the Markov Property if the next state is only dependent on the previous state. That is, if we let be the state at time then

• A Markov process is memoryless. It does not remember the history of past states beyond the current state.

• A Markov Chain can be expressed using a transition Matrix . In this case represents the probability of moving from state to state in steps.

  Each distribution on states can be represented with a probability vector

  • A transition matrix is called regular if it only contains positive entries.

• (Friedberg 5.20) Let such that it has nonnegative entries; having nonnegative coordinates and be the column vector in which each coordinate equals . Then

  • is a transition matrix if and only if
  • is a probability vector if and only if
  • (Friedberg 5.20.1a) The product of two transition matrices is an transition matrix. In particular, any power of a transition matrix is a transition matrix.
  • (Friedberg 5.20.1b) The product of a transition matrix and a probability vector is a probability vector.

• (Friedberg 5.21.3) If is an eigenvalue of a transition matrix, then

  • Follows from Gerschgorin’s Disk Theorem

• (Friedberg 5.22) Every transition matrix has as an eigenvalue.

• (Friedberg 5.23.2) Let be a transition matrix in which each entry is positive and let denote any eigenvalue of other than . Then . Moreover, the dimension of the eigenspace corresponding to the eigenvalue is .

• (Friedberg 5.24) Let be a regular transition matrix

  • If is an eigenvalue of then
  • If , then and .
  • (Friedberg 5.24.1) Let be a regular transition matrix that is diagonalizable. Then .

• (Friedberg 5.25) Let be an regular transition matrix. Then

  • The algebraic multiplicity of as an eigenvalue of is
  • exists
  • is a transition matrix
  • The columns of are identical. Each column of is equal to the unique probability vector that is also an eigenvector corresponding to eigenvalue of .
  • For any probability vector
    We call the fixed probability vector. Also called the stationary vector of the regular transition matrix .

Links §

• Friedberg, Insel and Spence