A Markov chain is a data sequence which has a special kind of dependence. For example, a fair coin is tossed repetitively by a player who begins with $2. If “heads” appear, the player receives one dollar; otherwise, she pays one dollar. The game stops when the player has either $0 or $5. The amount of money that the player has before any coin flip can be recorded – this is a Markov chain. A possible sequence of plays is as follows:
Note that all we need to know in order to determine the player’s fortune at any time is the fortune at the previous time as well as the coin flip result at the current time. The probability of an increase in the fortune is 0.5 and the probability of a decrease in the fortune is 0.5. The transition probabilities can be summarized in a transition matrix:
The (i, j ) entry of this matrix is the probability of making a change from the value i to the value j . Here, the possible values of i and j are 0, 1, 2,..., 5. According to the matrix, there is a probability of 0 of making a transition from $2 to $4 in one play, since the (2, 4) element is 0; the probability of moving from $2 to $1 in one transition is 0.5, since the (2, 1) element is 0.5.
The following function can be used to simulate N values of a Markov chain sequence, with transition matrix P:
Simulate 15 values of the coin flip game, starting with an initial value of $2. Repeat the simulation several times.