CHAPTER 11. MARKOV CHAINS

Exercise 8 Page 414

A certain calculating machine uses only the digits 0 and 1. It is supposed to transmit one of these digits through several stages. However, at every stage, there is a probability p that the digit that enters this stage will be changed when it leaves and a probability q = 1−p that it won’t. Form a Markov chain to represent the process of transmission by taking as states the digits 0 and 1. What is the matrix of transition probabilities?

Solution

Taking as states the digits 0 and 1 we identify the following Markov chain:

At each stage, \(X_i\) can take values: \(X_i = \{0, 1\}\).

\[ \begin{array}{c c} & \begin{array}{c c} 0 & 1 \\ \end{array} \\ \begin{array}{c c} 0\\ 1 \end{array} & \left( \begin{array}{c c} q & p \\ p & q \end{array} \right) \end{array} \]

where p + q = 1. Thus, the transition matrix is as follows:

\[ P = \begin{pmatrix} q & p \\ p & q \end{pmatrix} = \begin{pmatrix} 1 - p & p \\ p & 1 - p \end{pmatrix} \]