]> Reliability Chains
  1. Virtual Laboratories
  2. 15. Markov Chains
  3. 1
  4. 2
  5. 3
  6. 4
  7. 5
  8. 6
  9. 7
  10. 8
  11. 9
  12. 10
  13. 11
  14. 12

8. Reliability Chains

The Success-Runs Chain

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 consecutive successes, then the probability of success on the next trial is p x where p 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.

Argue that X X 0 X 1 X 2 is a Markov chain with state space and transition probability function

P x x 1 p x ,  P x 0 1 p x ,  x

This Markov chain is called the success-runs chain. The state graph of is given below:

SuccessRuns.png

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 X , T T 0 , the first return time to state 0, starting in 0. Note that T takes values in , since, presumably, it is possible that no failure occurs. Let r n T n for n , the probability of at least n consecutive successes, starting with a fresh set of trials. Let f n T n for n , the probability of exactly n 1 , consecutive successes, starting with a fresh set of trails.

Show that

  1. p x r x 1 r x for x
  2. r n x 0 n 1 p x for n
  3. f n 1 p n 1 x 0 n 2 p x for n
  4. r n 1 x 1 n f x for n
  5. f n r n 1 r n for n

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 . Show that it is characterized by the following properties:

  1. r is positive.
  2. r 0 1
  3. r is strictly decreasing.

Show that the function f is characterized by the following properties:

  1. f is positive.
  2. x 1 f x 1

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 . 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:

  1. p is a constant in 0 1 . Thus, the trials are Bernoulli trials.
  2. r n 1 n 1 for n .
  3. r n n 1 2 n 1 for n .
  4. p x 1 x 2 for x .

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.

Recurrence and the Remaining Life Chain

From the state graph, show that the success-runs chain is irreducible and aperiodic.

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 α T . Specifically, the success-runs chain is transient if α 0 and recurrent if α 0 . Thus, we see that the chain is recurrent if and only if a failure is sure to occur. We can compute the parameter α in terms of each of the three functions that define the chain.

Show that

α x 0 p x n r n 1 x 1 f x

When the success-runs chain 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.

Argue that Y Y 0 Y 1 Y 2 is a Markov chain with state space and transition probability function

Q 0 x f x 1 ,  Q x 1 x 1 ,  x

The Markov chain Y is called the remaining life chain. Verify the state graph below and show that this chain is also irreducible, aperiodic, and recurrent.

Image: RemainingLife.png

Compute α and determine whether the success-runs chain 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.

Positive Recurrence and Limiting Distributions

Let μ T , the expected trial number of the first failure, starting with a fresh sequence of trials.

Show that the success-runs chain X is positive recurrent if and only if μ , in which case the invariant distribution has probability density function g given by

g x r x μ ,  x

Show that

  1. If α 0 then μ
  2. If α 0 then μ n 1 n f n
  3. μ n 0 r n

Suppose that α 0 , so that the remaining life chain Y is well-defined. Show that this chain is also positive recurrent if and only if μ , with the same invariant distribution as X (with probability density function g given in the previous exercise).

Determine whether the success-runs chain 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.

Time Reversal

Suppose that μ , so that the success-runs chain X and the remaining-life chain Y are positive recurrent.

Show that X and Y are time reversals of each other, and use this fact to show again that g is the invariant probability density function.

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.