Renewal-reward processes

A large system is controlled by $n$ identical computers. Each computer independently alternates between an operational state and a repair state. The duration of the operational state, from completion of one repair until the next need for repair, is a random variable $X$ with finite expected duration $\mathbb {E}\left[X\right]$. The time required to repair a computer is an exponentially distributed random variable with density $\lambda e^{-\lambda t}$. All operating durations and repair durations are independent. Assume that all computers are in the repair state at time 0.

This problem provides another way of treating ensemble averages for renewal-reward problems. Assume for notational simplicity that $X$ is a continuous random variable.

This problem is designed to give you an alternate way of looking at ensemble averages for renewal-reward problems. First we find an exact expression for $\mathbb {P}\left(S_{N(t)}>s\right)$. We find this for arbitrary $s$ and $t$, $0<s<t$.

Consider a ferry that carries cars across a river. The ferry holds an integer number $k$ of cars and departs the dock when full. At that time, a new ferry immediately appears and begins loading newly arriving cars ad infinitum. The ferry business has been good, but customers complain about the long wait for the ferry to fill up.

Planes land at Heathrow airport at the times of a renewal process with interarrival time distribution function $F$. Each plane contains a random number of people with a given common distribution and finite mean. Assuming as much independence as usual, find an expression for the rate of arrival of passengers over a long time period.

If $X(t)$ is an irreducible positive recurrent Markov chain, and $u(\cdot )$ is a bounded function on the integers, show that

where $\mathbf{\pi }$ is the stationary distribution of $X(t)$.

Let $M(t)$ be an alternating renewal process, with interarrival pairs $\left\{ X_{r}, Y_{r}: r \geq 1\right\}$. Show that

Is this limit valid for an arbitrary joint distribution of independent pairs $\left(X_{i}, Y_{i}\right)$?

Let $C(s)$ be the current lifetime (or age) of a renewal process $N(t)$ with a typical interarrival time $X$. Show that

Find the corresponding limit for the excess lifetime.

Let $j$ and $k$ be distinct states of an irreducible discrete-time Markov chain $X$ with stationary distribution $\pi$. Show that

where $T_{i} = \min \left\{ n \geq 1: X_{n} = i\right\}$ is the first passage time to the state $i$. [Hint: Consider the times of return to $j$ having made an intermediate visit to $k$.]

Use the result of Exercise (10.5.2) to show that the limiting distribution function as $t \rightarrow \infty$ of the total life $D(t)$ of a renewal process is

where $f$ is the density function of a typical interarrival time $X$, and $\mu = \mathbb {E}\left[X\right]$. The integrand is called the size-biased (or length-biased) density for $X$.

A machine $M$ is repaired at time $t = 0$, and its uptime after any repair is exponentially distributed with parameter $\lambda$, at which point it breaks down (assume the usual independence). Following any repair at time $T$, say, it is inspected at times $T, T+m, T+2 m, \ldots$, and instantly repaired if found to be broken (the inspection schedule is then restarted). Show that the long run proportion of time that $M$ is working (the 'uptime ratio') is $m^{-1} \int_{0}^{m} e^{-\lambda x} d x$.

The interarrival times of this process are $Z_{0}, Y_{1}, Z_{1}, Y_{2}, \ldots$, where the $Y_{i}$ and $Z_{j}$ are independent with respective common moment generating functions $M_{Y}$ and $M_{Z}$. Let $p(t)$ be the probability that the epoch $t$ of time lies in an interval of type $Z$. Show that the Laplace-Stieltjes transform $p^{*}$ of $p$ satisfies

Bears arrive in a village at the instants of a renewal process; they are captured and confined at a cost of $\$ c$ per unit time per bear. When a given number $B$ bears have been captured, an expedition (costing $\$ d$) is organized to remove and release them a long way away. What is the long-run average cost of this policy?

Let $X = \left\{ X_{n}: n \geq 0\right\}$ be an ergodic Markov chain on a finite state space $S$, with stationary distribution $\pi$. Let $k \in S$, and let $T$ be a strictly positive stopping time with finite mean such that $X_{T} = k$. For $j \in S$, let $V_{j}(k)$ be the number of visits to $j$ by the chain started in $k$ and stopped at time $T$ (set $V_{k}(k) = 1$). Use the renewal-reward theorem to show that $\mathbb {E}\left[V_{j}(k)\right] = \pi_{j} \mathbb {E}_{k}\left[T\right]$.

For a given type of car, costing $c$ new, the number of years between its manufacture and being broken up for scrap is $X( \geq 1)$, where $X$ is a random variable with distribution function $F$. In its $k$ th year after manufacture (with $k \geq 1$), depreciation has reduced its resale value to $c \lambda^{k}$, and in that year it costs $r \mu^{k-1}$ in repairs and maintenance, where $\mu \neq 1$. (Usually, $\lambda < 1$ and $\mu > 1$.)

You buy a new car immediately your old car either is scrapped or reaches the age of $m$ years, whichever is the sooner. Show that, if you continue the policy indefinitely, in the long run you minimize your expected average cost by choosing $m$ such that

is as small as possible, where $G(s) = \mathbb {E}\left[s^{Y}\right]$ and $Y = \min \left\{ m, X\right\}$.

Consider the $M(\lambda ) / G / 1$ queue with no waiting room. Customers who arrive while the server is busy are lost. Show that the long run proportion of arrivals lost is $1 /\left(1+\rho^{-1}\right)$ where $\rho = \lambda \mathbb {E}\left[S\right]$ is the traffic intensity.

Consider an $M(\lambda ) / G / \infty$ queue. Use the renewal-reward theorem to show that the expected duration of a busy period is $\left(e^{\rho }-1\right) / \lambda$ where $\rho = \lambda \mathbb {E}\left[S\right]$.

After the level of an industrial process has been set at its desired value, it wanders in a random fashion. To counteract this the process is periodically reset to this desired value, at times $0, T, 2 T, \ldots$. If $W_{t}$ is the deviation from the desired level, $t$ units of time after a reset, then $\left\{ W_{t}: 0 \leq t < T\right\}$ can be modelled by a standard Wiener process. The behaviour of the process after a reset is independent of its behaviour before the reset. While $W_{t}$ is outside the range $(-a, a)$ the output from the process is unsatisfactory and a cost is incurred at rate $C$ per unit time. The cost of each reset is $R$. Show that the period $T$ which minimises the long-run average cost per unit time is $T^{*}$, where

Let $X_1, X_2, \ldots$ be the i.i.d. lifetimes of some component in some large machine. The simplest replacement policy is to change a component as soon as it fails. In this case it may be necessary to call a repairman at night, which might be costly. Another policy, called replacement based on age, is to replace at failure or at some given age, $a$, say, whichever comes first, in which case the interreplacement times are

Suppose that $c_1$ is the cost for replacements due to failure and that $c_2$ is the cost for replacements due to age. In addition, let $Y_k$ be the cost attached to replacement $k$, $k \geq 1$, and let $N(t)$ be the number of replacements made in the time interval $(0,t]$, where $\left\{ N(t), t \geq 0\right\}$ is a Poisson process, which is independent of $X_1, X_2, \ldots$. This means that

is the total cost caused by the replacements in the time interval $(0,t]$ (with $Z(t)=0$ whenever $N(t)=0$).