Suppose that we have a sequence of trials, each of which results in either success or failure. Our basic assumption is that if there have been \( x \in \N \) consecutive successes, then the probability of success on the next trial is \( p(x) \), independently of the past, where \( p: \N \to (0, 1) \). Whenever there is a failure, we start over, independently, with a new sequence of trials. Appropriately enough, \( p \) is called the success function. Let \( X_n \) denote the length of the run of successes after \( n \) trials.
\( \bs{X} =(X_0, X_1, X_2, \ldots) \) is a Markov chain with state space \( \N \) and transition probability matrix \( P \) given by
\[ P(x, x + 1) = p(x), \; P(x, 0) = 1 - p(x); \quad x \in \N \]This Markov chain is called the success-runs chain. The state graph of is given below:
Now let \( T \) denote the trial number of the first failure, starting with a fresh sequence of trials. Note that in the context of the success-runs chain \( \bs{X} \), \( T = T_0 \), the first return time to state 0, starting in 0. Note that \( T \) takes values in \( \N_+ \cup \{\infty\} \), since, presumably, it is possible that no failure occurs. Let \( r(n) = \P(T \gt n) \) for \( n \in \N \), the probability of at least \( n \) consecutive successes, starting with a fresh set of trials. Let \( f(n) = \P(T = n) \) for \( n \in \N_+ \), the probability of exactly \( n - 1 \), consecutive successes, starting with a fresh set of trails.
The functions \( p \), \( r \), and \( f \) are related as follows:
Thus, the functions \( p \), \( r \), and \( f \) give equivalent information. If we know one of the functions, we can construct the other two, and hence any of the functions can be used to define the success-runs chain. The function \( r \) is the reliability function associated with \( T \).
The function \( r \) is characterized by the following properties:
The function \( f \) is characterized by the following properties:
Essentially, \( f \) is the probability density function of \( T \), except that it may be defective in the sense that the sum of its values may be less than 1. The leftover probability, of course, is the probability that \( T = \infty \). This is the critical consideration in the classification of the success-runs chain, which we consider in the next paragraph.
Verify that each of the following functions has the appropriate properties, and then find the other two functions:
The success-runs applet is a simulation of the success-runs chain based on Bernoulli trials. Run the simulation 1000 times for various values of \( p \), and note the limiting behavior of the chain.
The success-runs chain is irreducible and aperiodic.
The chain is irreducible, since 0 leads to every other state, and every state leads back to 0. The chain is aperiodic since \( P(0, 0) \gt 0 \).
Recall that \( T \) has the same distribution as the first return time to 0 starting at state 0. Thus, the classification of the chain as recurrent or transient depends on \( \alpha = \P(T = \infty) \). Specifically, the success-runs chain is transient if \( \alpha \gt 0 \) and recurrent if \( \alpha = 0 \). Thus, we see that the chain is recurrent if and only if a failure is sure to occur. We can compute the parameter \( \alpha \) in terms of each of the three functions that define the chain.
In terms of \( p \), \( r \), and \( f \),
\[ \alpha = \prod_{x=0}^\infty p(x) = \lim_{n \to \infty} r(n) = 1 - \sum_{x=1}^\infty f(x) \]When the success-runs chain \( \bs{X} \) is recurrent, we can define a related random process. Let \( Y_n \) denote the number of trials remaining until the next failure, after \( n \) trials.
\( \bs{Y} = (Y_0, Y_1, Y_2, \ldots) \) is a Markov chain with state space \( \N \) and transition probability matrix \( Q \) given by
\[ Q(0, x) = f(x + 1), \; Q(x + 1, x) = 1; \quad x \in \N \]The Markov chain \( \bs{Y} \) is called the remaining life chain and has the state graph below.
\( \bs{Y} \) is also irreducible, aperiodic, and recurrent.
Compute \( \alpha \) and determine whether the success-runs chain \( \bs{X} \) is transient or recurrent for each of the cases in Exercise 5.
Run the simulation of the success-runs chain 1000 times for various values of \( p \), starting in state 0. Note the return times to state 0.
Let \( \mu = \E(T) \), the expected trial number of the first failure, starting with a fresh sequence of trials.
The success-runs chain \( \bs{X} \) is positive recurrent if and only if \( \mu \lt \infty \), in which case the invariant distribution has probability density function \( g \) given by
\[ g(x) = \frac{r(x)}{\mu}, \quad x \in \N \]\( \mu \) is related to \( \alpha \), \( f \), and \( r \) as follows:
Suppose that \( \alpha = 0 \), so that the remaining life chain \( \bs{Y} \) is well defined. Then \( \bs{Y} \) is also positive recurrent if and only if \( \mu \lt \infty \), with the same invariant distribution as \( \bs{X} \) (with probability density function \( g \) given in the Theorem 13).
Determine whether the success-runs chain \( \bs{X} \) is transient, null recurrent, or positive recurrent for each of the cases in Exercise 5. If the chain is positive recurrent, find the invariant probability density function.
The success-runs chain corresponding to Bernoulli trials has a geometric distribution as the invariant distribution. Run the simulation of the success-runs chain 1000 times for various values of \( p \). Note the apparent convergence of the empirical distribution to the invariant distribution.
Suppose that \( \mu \lt \infty \), so that the success-runs chain \( \bs{X} \) and the remaining-life chain \( \bs{Y} \) are positive recurrent.
\( \bs{X} \) and \( \bs{Y} \) are time reversals of each other.
Run the simulation of the success-runs chain 1000 times for various values of \( p \), starting in state 0. If you imagine watching the simulation backwards in time, then you can see a simulation of the remaining life chain.