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, \mathbb{N}, \left(0 , 1\right))$. 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=\left(\begin{array}{c}X_{0}\\ X_{1}\\ X_{2}\\ \end{array}\right)$ is a Markov chain with state space $\mathbb{N}$ and transition probability function

$$P(x, x+1)=p(x)\text{,\hspace{0.5em}}P(x, 0)=1-p(x)\text{,\hspace{1em}}x\in \mathbb{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 $X$, $T=T_{0}$, the first return time to state 0, starting in 0. Note that $T$ takes values in $\cup \{\infty \}$, since, presumably, it is possible that no failure occurs. Let $r(n)=(T> n)$ for $n\in \mathbb{N}$, the probability of at least $n$ consecutive successes, starting with a fresh set of trials. Let $f(n)=(T=n)$ for $n\in $, the probability of exactly $n-1$, consecutive successes, starting with a fresh set of trails.

Show that

- $p(x)=\frac{r(x+1)}{r(x)}$ for $x\in \mathbb{N}$
- $r(n)=\prod_{x=0}^{n-1} p(x)$ for $n\in \mathbb{N}$
- $f(n)=(1-p(n-1))\prod_{x=0}^{n-2} p(x)$ for $n\in $
- $r(n)=1-\sum_{x=1}^{n} f(x)$ for $n\in \mathbb{N}$
- $f(n)=r(n-1)-r(n)$ for $n\in $

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:

- $r$ is positive.
- $r(0)=1$
- $r$ is strictly decreasing.

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

- $f$ is positive.
- $\sum_{x=1}^{\infty} f(x)\le 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=\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:

- $p$ is a constant in $\left(0 , 1\right)$. Thus, the trials are Bernoulli trials.
- $r(n)=\frac{1}{n+1}$ for $n\in \mathbb{N}$.
- $r(n)=\frac{n+1}{2n+1}$ for $n\in \mathbb{N}$.
- $p(x)=\frac{1}{x+2}$ for $x\in \mathbb{N}$.

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.

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 $\alpha =(T=\infty )$. Specifically, the success-runs chain is transient if $\alpha > 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.

Show that

$$\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 $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=\left(\begin{array}{c}Y_{0}\\ Y_{1}\\ Y_{2}\\ \end{array}\right)$ is a Markov chain with state space $\mathbb{N}$ and transition probability function

$$Q(0, x)=f(x+1)\text{,\hspace{0.5em}}Q(x+1, x)=1\text{,\hspace{1em}}x\in \mathbb{N}$$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.

Compute $\alpha $ 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.

Let $\mu =(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 $\mu < \infty $, in which case the invariant distribution has probability density function $g$ given by

$$g(x)=\frac{r(x)}{\mu}\text{,\hspace{1em}}x\in \mathbb{N}$$Show that

- If $\alpha > 0$ then $\mu =\infty $
- If $\alpha =0$ then $\mu =\sum_{n=1}^{\infty} nf(n)$
- $\mu =\sum_{n=0}^{\infty} r(n)$

Suppose that $\alpha =0$, so that the remaining life chain $Y$ is well-defined. Show that this chain is also positive recurrent if and only if $\mu < \infty $, 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.

Suppose that $\mu < \infty $, 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.