Mathematics — Probability · ergodic-markov-chains-engle-algorithm
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 ai be the least common multiple of the denominators of the non-zero entries in the ith row. Engle describes his algorithm in terms of moving chips around on the states. Start by putting ai chips on state i for all i. Then, at each state, redistribute the ai chips, sending aipij to state j. The number of chips at state i after this redistribution need not be a multiple of ai. For each state i, add just enough chips to bring the number of chips at state i up to a multiple of ai. 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:
P=112321/21/21/231/401/41/41/21/4.
We start with a=(4,2,4). The chips after successive redistributions are shown in Table 11.4. We find that 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 b be a vector with integer components that is a fixed vector for P and such that each coordinate of the starting vector a is less than or equal to the corresponding component of 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 b.