Grinstead-Snell-Probability · Problem 29

Markov Chains

Mathematics · engel-algorithm-fixed-vector

Problem

In his book, Wahrscheinlichkeitsrechnung und Statistik, A. Engle proposes an algorithm for finding the fixed vector for an ergodic Markov chain when the transition probabilities are rational numbers. Here is his algorithm: For each state

i

, let

a_i

be the least common multiple of the denominators of the non-zero entries in the

i

th row. Start by putting

a_i

chips on state

i

for all

i

. Then, at each state, redistribute the

a_i

chips, sending

a_i p_{ij}

to state

j

. The number of chips at state

i

after this redistribution need not be a multiple of

a_i

. For each state

i

, add just enough chips to bring the number of chips at state

i

up to a multiple of

a_i

. Then redistribute the chips in the same manner. This process will eventually reach a point where the number of chips at each state, after the redistribution, is the same as before redistribution. At this point, we have found a fixed vector. Here is an example:

\mathbf{P} = \begin{pmatrix} 1 & 2 & 3 \\ 1 & 1/2 & 1/4 & 1/4 \\ 2 & 1/2 & 0 & 1/2 \\ 3 & 1/2 & 1/4 & 1/4 \end{pmatrix}.

We start with

\mathbf{a} = (4, 2, 4)

. We find that

\mathbf{a} = (20, 8, 12)

is a fixed vector. (a) Write a computer program to implement this algorithm. (b) Prove that the algorithm will stop. Hint: Let

\mathbf{b}

be a vector with integer components that is a fixed vector for

\mathbf{P}

and such that each coordinate of the starting vector

\mathbf{a}

is less than or equal to the corresponding component of

\mathbf{b}

. Show that, in the iteration, the components of the vectors are always increasing, and always less than or equal to the corresponding component of

\mathbf{b}

Browse the problem library