Of interest in many problems of applied probability theory is the evolution in time of the state of a random phenomenon. For example, suppose one has two urns (I and II), each of which contains one white and one black ball. One ball is drawn simultaneously from each urn and placed in the other urn. One is often concerned with questions such as, what is the probability that after 100 repetitions of this procedure urn I will contain two white balls? The theory of Markov ¹ chains is applicable to questions of this type.

The theory of Markov chains relates to every field of physical and social science (see the forthcoming book by A. T. Bharucha-Reid, Introduction to the Theory of Markov Processes and their Applications ; for applications of the theory of Markov chains to the description of social or psychological phenomena, see the book by Kemeny and Snell cited in the next paragraph). There is an immense literature concerning the theory of Markov chains. In this section and the next we can provide only a brief introduction.

Excellent elementary accounts of this theory are to be found in the works of W. Feller, An Introduction to Probability Theory and Its Applications , second edition, Wiley, New York, 1957, and J. G. Kemeny and J. L. Snell, Finite Markov Chains , Van Nostrand, Princeton, New Jersey, 1959. The reader is referred to these books for proof of the assertions made in section 6 .

The natural generalization of the notion of independent Bernoulli trials is the notion of Markov dependent Bernoulli trials. Given \(n\) trials of an experiment, which has only two possible outcomes (denoted by \(s\) or \(f\) , for “success” or “failure”), we recall that they are said to be independent Bernoulli trials if for any integer \(k(1\) to \(n-1)\) and \(k+1\) events \(A_{1}\) , \(A_{2}, \ldots, A_{k+1}\) , depending, respectively, on the first, second,…, \((k+1)\) st trials, \[P\left[A_{k+1} \mid A_{k}, A_{k-1}, \ldots, A_{1}\right]=P\left[A_{k+1}\right] \tag{5.1}\] We define the trials as Markov dependent Bernoulli trials if, instead of (5.1) , it holds that \[P\left[A_{k+1} \mid A_{k}, A_{k-1}, \ldots, A_{1}\right]=P\left[A_{k+1} \mid A_{k}\right] \tag{5.2}\] In words, (5.2) says that at the \(k\) th trial the conditional probability of any event \(A_{k+1}\) , depending on the next trial, will not depend on what has happened in past trials but only on what is happening at the present time. One sometimes says that the trials have no memory.

Suppose that the quantities \begin{align} P(s, s)= & \text { probability of success on the }(k+1) \text {st trial, } \\ & \text { given that there was success on the } k \text {th trial, } \\ P(f, s)= & \text { probability of success at the }(k+1) \text {st trial, } \\ & \text { given that there was failure at the } k \text {th trial, } \tag{5.3} \\ P(f, f)= & \text { probability of failure at the }(k+1) \text {st trial, } \\ & \text { given that there was failure at the } k \text {th trial, } \\ P(s, f)= & \text { probability of failure at the }(k+1) \text {st trial, } \\ & \text { given that there was success at the } k \text {th trial, } \end{align} are independent of \(k\) . We then say that the trials are Markov dependent repeated Bernoulli trials .

In the case of independent repeated Bernoulli trials the probability function \(P[\cdot]\) on the sample description space of the \(n\) trials is completely specified once we have the probability \(p\) of success at each trial. In the case of Markov dependent repeated Bernoulli trials it suffices to specify the quantities \begin{align} p_{1}(s) & =\text { probability of success at the first trial, } \\ p_{1}(f) & =\text { probability of failure at the first trial, } \tag{5.4} \end{align} as well as the conditional probabilities in (5.3) . The probability of any event can be computed in terms of these quantities. For example, for \(k=1,2, \ldots, n\) let \begin{align} p_{k}(s) & =\text { probability of success at the } k \text { th trial, } \\ p_{k}(f) & =\text { probability of failure at the } k \text { th trial. } \tag{5.5} \end{align} 

The quantities \(p_{k}(s)\) satisfy the following equations for \(k=2,3, \ldots, n\) : \begin{align} p_{k}(s) & =p_{k-1}(s) P(s, s)+p_{k-1}(f) P(f, s) \tag{5.6} \\ & =p_{k-1}(s) P(s, s)+\left[1-p_{k-1}(s)\right][1-P(f, f)] \\ & =p_{k-1}(s)[P(s, s)+P(f, f)-1]+[1-P(f, f)] \end{align} 

To justify (5.6) , we reason as follows: if \(A_{k}\) is the event that there is success on the \(k\) th trial, then \[P\left[A_{k}\right]=P\left[A_{k-1}\right] P\left[A_{k} \mid A_{k-1}\right]+P\left[A_{k-1}^{c}\right] P\left[A_{k} \mid A^{c}_{k-1}\right] . \tag{5.7}\] 

From (5.7) and the fact that (5.8) \(P(s, f)=1-P(s, s) \quad P(f, s)=1-P(f, f), \quad p_{k}(f)=1-p_{k}(s)\) one obtains (5.6) .

Equation (5.6) constitutes a recursive relationship for \(p_{k}(s)\) , known as a difference equation. Throughout this section we make the assumption that \[|P(s, s)+P(f, f)-1|<1. \tag{5.9}\] 

By using theoretical exercise 4.5, it follows from (5.6) and (5.9) that for \(k=1,2, \ldots, n\) \begin{align} p_{k}(s)=\left[p_{1}(s)\right. & \left.-\frac{1-P(f, f)}{2-P(s, s)-P(f, f)}\right][P(s, s)+P(f, f)-1]^{k-1} \tag{5.10} \\ & +\left[\frac{1-P(f, f)}{2-P(s, s)-P(f, f)}\right]. \end{align} 

By interchanging the role of \(s\) and \(f\) in (5.10) , we obtain, similarly, for \(k=1,2, \ldots, n\) \begin{align} p_{k}(f)=\left[p_{1}(f)\right. & \left.-\frac{1-P(s, s)}{2-P(s, s)-P(f, f)}\right][P(s, s)+P(f, f)-1]^{k-1} \tag{5.11} \\ & +\left[\frac{1-P(s, s)}{2-P(s, s)-P(f, f)}\right]. \end{align} 

It is readily verifiable that the expressions in (5.10) and (5.11) sum to one, as they ought.

In many problems involving Markov dependent repeated Bernoulli trials we do not know the probability \(p_{1}(s)\) of success at the first trial. We can only compute the quantities

\begin{align} P_{k}(s, s)= & \text { conditional probability of success at the } \\ & (k+1) \text { st trial, given success at the first trial, } \\ P_{k}(s, f)= & \text { conditional probability of failure at the } \\ & (k+1) \text { st trial, given success at the first trial, } \\ P_{k}(f, f)= & \text { conditional probability of failure at the } \tag{5.12} \\ & (k+1) \text { st trial, given failure at the first trial, } \\ P_{k}(f, s)= & \text { conditional probability of success at the } \\ & (k+1) \text { st trial, given failure at the first trial. } \end{align} 

Since \[P_{k}(s, f)=1-P_{k}(s, s), \quad P_{k}(f, s)=1-P_{k}(f, f) \tag{5.13}\] it suffices to obtain formulas for \(P_{k}(s, s)\) and \(P_{k}(f, f)\) .

In the same way that we obtained (5.6) we obtain \begin{align} P_{k}(s, s) & =P_{k-1}(s, s) P(s, s)+P_{k-1}(s, f) P(f, s) \tag{5.14} \\ & =P_{k-1}(s, s) P(s, s)+\left[1-P_{k-1}(s, s)\right][1-P(f, f)] \\ & =P_{k-1}(s, s)[P(s, s)+P(f, f)-1]+[1-P(f, f)] \end{align} 

By using theoretical exericse 4.5, it follows from (5.14) and (5.9) that for \(k=1,2, \ldots, n\) \begin{align} P_{k}(s, s) & =\left[P_{1}(s, s)-\frac{1-P(f, f)}{2-P(s, s)-P(f, f)}\right] \tag{5.15} \\ & \times[P(s, s)+P(f, f)-1]^{k-1}+\left[\frac{1-P(f, f)}{2-P(s, s)-P(f, f)}\right] \end{align} which can be simplified to \begin{align} P_{k}(s, s)=\frac{1-P(s, s)}{2-P(s, s)-P(f, f)} & {[P(s, s)+P(f, f)-1]^{k} } \tag{5.16} \\ + & {\left[\frac{1-P(f, f)}{2-P(s, s)-P(f, f)}\right] . } \end{align} 

By interchanging the role of \(s\) and \(f\) , we obtain, similarly, \begin{align} P_{k}(f, f)=\frac{1-P(f, f)}{2-P(s, s)-P(f, f)}[P(s, s)+P(f, f)-1]^{k} \tag{5.17}\\ \quad+\frac{1-P(s, s)}{2-P(s, s)-P(f, f)} \end{align} By using (5.13) , we obtain \begin{align} P_{k}(s, f)=-\frac{1-P(s, s)}{2-P(s, s)-P(f, f)}&[P(s, s)+P(f, f)-1]^{k}\\ & +\frac{1-P(s, s)}{2-P(s, s)-P(f, f)} \tag{5.18} \end{align} \begin{align} P_{k}(f, s)=-\frac{1-P(f, f)}{2-P(s, s)-P(f, f)}&[P(s, s)+P(f, f)-1]^{k} \\ & +\frac{1-P(f, f)}{2-P(s, s)-P(f, f)}.\tag{5.19} \end{align} Equations (5.16) to (5.19) represent the basic conclusions in the theory of Markov dependent Bernoulli trials (in the case that (5.9) holds).

Statistical Equilibrium. For large values of \(k\) the values of \(p_{k}(s)\) and \(p_{k}(f)\) are approximately given by \begin{align} p_{k}(s) & =\frac{1-P(f, f)}{2-P(s, s)-P(f, f)} \tag{5.24} \\ p_{k}(f) & =\frac{1-P(s, s)}{2-P(s, s)-P(f, f)} \end{align} 

To justify (5.24) , use (5.10) and (5.11) and the fact that (5.9) implies that \[\lim _{k \rightarrow \infty}[P(s, s)+P(f, f)-1]^{k-1}=0.\] 

Equation (5.24) has the following significant interpretation: After a large number of Markov dependent repeated Bernoulli trials has been performed, one is in a state of statistical equilibrium, in the sense that the probability \(p_{k}(s)\) of success on the kth trial is the same for all large values of \(k\) and indeed is functionally independent of the initial conditions, represented \(b y\) \(p_{1}(s)\) .

From (5.24) one sees that the trials are asymptotically fair in the sense that approximately \[p_{k}(s)=p_{k}(f)=\frac{1}{2} \tag{5.25}\] for large values of \(k\) if and only if \[P(s, s)=P(f, f) \tag{5.26}\] 

Exercises