Markov Dependent Bernoulli Trials

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 trials of an experiment, which has only two possible outcomes (denoted by or , for “success” or “failure”), we recall that they are said to be independent Bernoulli trials if for any integer to and events , , depending, respectively, on the first, second,…, st trials, We define the trials as Markov dependent Bernoulli trials if, instead of (5.1) , it holds that In words, (5.2) says that at the th trial the conditional probability of any event , 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 . We then say that the trials are Markov dependent repeated Bernoulli trials .

In the case of independent repeated Bernoulli trials the probability function on the sample description space of the trials is completely specified once we have the probability 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 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 satisfy the following equations for : \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 is the event that there is success on the th trial, then  

From (5.7) and the fact that (5.8) one obtains (5.6) .

Equation (5.6) constitutes a recursive relationship for , known as a difference equation. Throughout this section we make the assumption that  

By using theoretical exercise 4.5, it follows from (5.6) and (5.9) that for \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 and in (5.10) , we obtain, similarly, for \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 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 it suffices to obtain formulas for and .

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 \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 and , 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 the values of and 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

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 of success on the kth trial is the same for all large values of and indeed is functionally independent of the initial conditions, represented .

From (5.24) one sees that the trials are asymptotically fair in the sense that approximately for large values of if and only if  

Exercises