Renewal processes

Let $X_{1}, X_{2}, \ldots$ be a sequence of IID inter-renewal rv s. Let $S_{n} = X_{1}+\cdots +X_{n}$ be the corresponding renewal epochs for each $n \geq 1$. Assume that each $X_{i}$ has a finite expectation $\overline{X}>0$ and, for any given $t>0$, use the WLLN to show that $\lim_{n \rightarrow \infty } \mathbb {P}\left(S_{n} \leq t\right) = 0$.

Use (a) to show that $\lim_{n \rightarrow \infty } \mathbb {P}\left(N(t) \geq n\right) = 0$ for each $t>0$ and explain why this means that $N(t)$ is a rv, i.e., is not defective.

Now suppose that the $X_{i}$ do not have a finite mean. Consider truncating each $X_{i}$ to $\check{X}_{i}$, where for any given $b>0$, $\check{X}_{i} = \min (X_{i}, b)$. Let $\check{N}(t)$ be the renewal counting process for the inter-renewal intervals $\check{X}_{i}$. Show that $\check{N}(t)$ is non-defective for each $t>0$. Show that $N(t) \leq \check{N}(t)$ and thus that $N(t)$ is non-defective.

Let the inter-renewal intervals have the CDF $\mathsf{F}_{X}(x)$, with, as usual, $\mathsf{F}_{X}(0) = 0$. Using whatever combination of mathematics and common sense is comfortable for you, show that for any $\epsilon$, $0<\epsilon <1$, there is a $\delta >0$ such that $\mathsf{F}_{X}(\delta ) \leq 1-\epsilon$. In other words, you are to show that a positive rv must lie in some range of positive values bounded away from 0 with positive probability.

Show that $\mathbb {P}\left(S_{n} \leq \delta \right) \leq (1-\epsilon )^{n}$.

Show that $\mathbb {E}\left[N(\delta )\right] \leq 1/\epsilon$.

For the $\epsilon , \delta$ of (a), show that for every integer $k$, $\mathbb {E}\left[N(k \delta )\right] \leq k/\epsilon$ and thus that $\mathbb {E}\left[N(t)\right] \leq (t+\delta )/\epsilon \delta$ for any $t>0$.

Use the result here to show that $N(t)$ is non-defective.

Find the CDF of each $Y_{i}$ in terms of that of the $X_{i}$.

Find the PMF of the number of arrivals of the generalized renewal process at each epoch at which arrivals occur.

Explain how to view the generalized renewal process as an ordinary renewal process with inter-renewal intervals $\left\{ Y_{i}; i \geq 1\right\}$ and bulk arrivals at each renewal epoch.

When a generalized renewal process is viewed as an ordinary renewal process with bulk arrivals, what is the distribution of the bulk arrivals? (The point of this part is to illustrate that bulk arrivals on an ordinary renewal process are considerably more general than generalized renewal processes.)

$N(t)<n$ if and only if $S_{n}>t$?

$N(t) \leq n$ if and only if $S_{n} \geq t$?

$N(t)>n$ if and only if $S_{n}<t$?

Show that if $\lim_{n \rightarrow \infty } Y_{n}(\omega ) = 0$ for some given $\omega$, then (for any given $k$) $\omega \in A(m, k)$ for some positive integer $m$.

Show that for all $k \geq 1$

Show that, for all $m \geq 1$, $A(m, k) \subseteq A(m+1, k)$. Use this (plus (1.9)) to show that

Show that if $\omega \in A(m, k)$, then $\left|Y_{m}(\omega )\right| \leq 1/k$. Use this (plus (c)) to show that

Since $k \geq 1$ is arbitrary, this shows that $\left\{ Y_{n}; n \geq 1\right\}$ converges in probability.

Find $\mathbb {E}\left[Z_{n}\right]$ as a function of $n$ and find $\lim_{n \rightarrow \infty } \mathbb {E}\left[Z_{n}\right]$.

Let $W_{n} = \log_{2} X_{n}$. Find $\mathbb {E}\left[W_{n}\right]$ and $\mathbb {E}\left[\log_{2}(Z_{n}/Z_{0})\right]$ as a function of $n$.

There is a constant $\alpha$ such that $\lim_{n \rightarrow \infty }(1/n)[\log_{2}(Z_{n}/Z_{0})] = \alpha$ WP1. Find $\alpha$ and explain how this follows from the SLLN.

Using (c), show that $\lim_{n \rightarrow \infty } Z_{n} = \beta$ WP1 for some $\beta$ and evaluate $\beta$.

Explain carefully how the result in (a) and the result in (d) are compatible. What you should learn from this problem is that the expected value of the log of a product of IID rv s might be more significant than the expected value of the product itself.

Let $\left\{ Y_{n}; n \geq 1\right\}$ be a sequence of rv s. Using the definition of convergence for a sequence of numbers, justify the following set equivalences:

Explain how this shows that $\left\{ \omega : \lim_{n} Y_{n}(\omega ) = 0\right\}$ must be an event.

Use De Morgan's laws to show that the complement of the above equivalence is

Show that for $\left\{ Y_{n}; n \geq 1\right\}$ to converge WP1, it is necessary and sufficient to satisfy

Show that for $\left\{ Y_{n}; n \geq 1\right\}$ to converge WP1, it is necessary and sufficient to satisfy

Show that

Show that if $\sum_{m=1}^{\infty } \mathbb {P}\left(A_{m}\right)<\infty$, then $\lim_{m \rightarrow \infty } \mathbb {P}\left(\bigcup_{n \geq m} A_{n}\right) = 0$.

Show that if $\sum_{m=1}^{\infty } \mathbb {P}\left(A_{m}\right)<\infty$, then $\mathbb {P}\left(\bigcap_{m \geq 1} \bigcup_{n \geq m} A_{n}\right) = 0$. This well-known result is called the Borel–Cantelli lemma.

The set $\left\{ \bigcap_{m} \bigcup_{n \geq m} A_{n}\right\}$ is often referred to as the set of $\omega$ that are contained in infinitely many of the $A_{n}$. Without trying to be precise about what this latter statement means, explain why it is a good way to think about $\left\{ \bigcap_{m} \bigcup_{n \geq m} A_{n}\right\}$.

Show that for any constant $M>0$, there is a $b$ sufficiently large so that $\mathbb {E}\left[\check{X}_{i}\right] \geq M$.

Let $\left\{ \check{N}(t); t \geq 0\right\}$ be the renewal counting process with inter-renewal intervals $\left\{ \check{X}_{i}; i \geq 1\right\}$ and show that for all $t>0$, $\check{N}(t) \geq N(t)$.

Show that for all sample functions $N(t, \omega )$, except a set of probability 0, $N(t, \omega )/t \leq 2/M$ for all sufficiently large $t$. Note: Since $M$ is arbitrary, this means that $\lim_{t \rightarrow \infty } N(t)/t = 0$ with probability 1.

For any $x>0$, show that $x^{m} \leq 1+x^{n}$.

For any rv $X$, show that if $\mathbb {E}\left[\left|X^{n}\right|\right]<\infty$, then $\mathbb {E}\left[\left|X^{m}\right|\right] \leq 1+\mathbb {E}\left[\left|X^{n}\right|\right]$.

the time average of $Y(t)$;

the time average of $Y^{2}(t)$ (i.e., $\lim_{T \rightarrow \infty }(1/T) \int_{0}^{T} Y^{2}(t) \, dt$).

Show that the sequence of times $S_{1}, S_{2}, \ldots$ at which successive successful customers enter service are the renewal times of a renewal process. Show that each inter-renewal interval $X_{i} = S_{i}-S_{i-1}$ (where $S_{0} = 0$) is the sum of two independent rv s, $Y_{i}+U_{i}$ where $Y_{i}$ is the $i$th service time; find the probability density of $U_{i}$.

Assume that a reward (actually a cost in this case) of one unit is incurred for each customer turned away. Sketch the expected reward function as a function of time for the sample function of inter-renewal intervals and service intervals shown below; the expectation is to be taken over those (unshown) arrivals of customers that must be turned away. {#fig-1 width="70%"}

Let $\int_{0}^{t} R(\tau ) \, d\tau$ denote the accumulated reward (i.e., cost) from 0 to $t$ and find the limit as $t \rightarrow \infty$ of $(1/t) \int_{0}^{t} R(\tau ) \, d\tau$. Explain (without any attempt to be rigorous or formal) why this limit exists with probability 1.

In the limit of large $t$, find the expected reward from time $t$ until the next renewal. Hint: Sketch this expected reward as a function of $t$ for a given sample of inter-renewal intervals and service intervals; then find the time average.

Now assume that the arrivals are deterministic, with the first arrival at time 0 and the $n$th arrival at time $n-1$. Does the sequence of times $S_{1}, S_{2}, \ldots$ at which subsequent customers start service still constitute the renewal times of a renewal process? Draw a sketch of arrivals, departures, and service time intervals. Again find $\lim_{t \rightarrow \infty }\left(\int_{0}^{t} R(\tau ) \, d\tau \right)/t$.

$\mathbb {P}\left(Y(t)>x \mid Z(t) = s\right)$;

$\mathbb {P}\left(Y(t)>x \mid Z(t+x/2) = s\right)$;

$\mathbb {P}\left(Y(t)>x \mid Z(t+x)>s\right)$ for a Poisson process.

Let $J$ be a stopping rule and $\mathbb {I}_{\left\{ J \geq n\right\} }$ be the indicator rv of the event $\left\{ J \geq n\right\}$. Show that $J = \sum_{n \geq 1} \mathbb {I}_{\left\{ J \geq n\right\} }$.

Show that $\mathbb {I}_{\left\{ J \geq 1\right\} } \geq \mathbb {I}_{\left\{ J \geq 2\right\} } \geq \ldots$, i.e., show that for each $n \geq 1$, $\mathbb {I}_{\left\{ J \geq n\right\} }(\omega ) \geq \mathbb {I}_{\left\{ J \geq n+1\right\} }(\omega )$ for each $\omega \in \Omega$ (except perhaps for a set of probability 0).

Use Wald's equality to compute the expected number of trials of a Bernoulli process up to and including the $k$th success.

Use elementary means to find the expected number of trials up to and including the first success. Use this to find the expected number of trials up to and including the $k$th success. Compare with (a).

Let $J$ be the number of plays until the gambler loses all his money. Is the weak law of large numbers sufficient to argue that $\lim_{n \rightarrow \infty } \mathbb {P}\left(J>n\right) = 0$ (i.e., that $J$ is a random variable) or is the strong law necessary?

Find $\mathbb {E}\left[J\right]$.

Is $J$ a stopping rule? Why or why not?

What are the possible values of $S_{J}$?

Find an expression for $\mathbb {E}\left[S_{J}\right]$ in terms of $p$, $a$, and $b$, where $p = \mathbb {P}\left(S_{J} \geq a\right)$.

Find an expression for $\mathbb {E}\left[S_{J}\right]$ from Wald's equality. Use this to solve for $p$.

Let $Z_{n} = \sum_{i=1}^{n}(X_{i}-V_{i-1})$ and let $I_{n}$ be the sum of the intervals between 0 and $S_{n} = \sum_{i=1}^{n} X_{i}$ during which the server is empty. Show that $I_{n} \geq Z_{n}$ and explain the difference between them. Show that if arrival $n$ enters an empty system, then $I_{n} = Z_{n}$.

Assume that the inter-arrival distribution is bounded in the sense that for some $b<\infty$, $\mathbb {P}\left(X>b\right) = 0$. Show that the duration of each idle period for the G/G/1 queue has a duration less than or equal to $b$.

Show that the number of idle intervals for the server up to time $S_{n}$ is at least $Z_{n}/b$. Show that the number of renewals up to time $S_{n}$ ($N^{r}(S_{n})$) at which an arrival sees an empty system is at least $(Z_{n}/b)$.

Show that the renewal counting process satisfies $\lim_{t \rightarrow \infty } N^{r}(t)/t = a$ WP1 for some $a>0$. Show that the mean number of arrivals per arrival to an empty system is $1/a<\infty$.

Assume everything above except to remove the assumption that $\mathbb {P}\left(X>b\right) = 0$ for some $b$. Use the truncation method on $X$ to establish (d) for this new case.

Use Wald's equality to find $\mathbb {E}\left[T\right]$.

Compute $\mathbb {E}\left[\sum_{i=1}^{J} X_{i} \mid J = n\right]$ and show that it is not equal to $\mathbb {E}\left[\sum_{i=1}^{n} X_{i}\right]$.

Use (b) for a second derivation of $\mathbb {E}\left[T\right]$.

Find $\mathbb {E}\left[T\right]$ if the company tells successive programmers which approaches have been tried unsuccessfully earlier.

Consider a renewal process for which the inter-renewal intervals have the PMF $\mathsf{p}_{X}(1) = \mathsf{p}_{X}(2) = 1/2$. Let $m(t) = \mathbb {E}\left[N(t)\right]$ and use elementary combinatorics to show that $m(1) = 1/2$, $m(2) = 5/4$, and $m(3) = 15/8$.

Use elementary means to show that $\mathbb {E}\left[S_{N(1)}\right] = 1/2$ and $\mathbb {E}\left[S_{N(1)+1}\right] = 9/4$. Verify (5.37) in this case (i.e., for $t = 1$) and show why $N(1)$ is not a stopping trial. Note also that the expected duration, $\mathbb {E}\left[S_{N(1)+1}-S_{N(1)}\right]$ is not equal to $\overline{X}$.

Generalize (a) so that $\mathbb {P}\left(X = 1\right) = 1-p$ and $\mathbb {P}\left(X = 2\right) = p$. Let $W_{n} = N(n)-N(n-1)$, i.e., $W_{n}$ is 1 if an arrival occurs at time $n$ and is 0 if no arrival occurs at $n$. Show that $\overline{W}_{n}$ satisfies the difference equation $\overline{W}_{n} = 1-p \overline{W}_{n-1}$ for $n \geq 1$ where by convention $\overline{W}_{0} = 1$. Use this to show that

From this, solve for $m(n)$ for $n \geq 1$ and verify the result in (a).

Sketch a typical sample function of $\left\{ N(t); t>0\right\}$. Note that $N(0)$ can be non-zero (i.e., $N(0)$ is the number of zero interarrival times that occur before the first non-zero interarrival time).

Evaluate $\mathbb {E}\left[N(t)\right]$ as a function of $t$.

Sketch $\mathbb {E}\left[N(t)\right]/t$ as a function of $t$.

Evaluate $\mathbb {E}\left[S_{N(t)+1}\right]$ as a function of $t$ (do this directly, and then use Wald's equality as a check on your work).

Sketch the lower bound $\mathbb {E}\left[N(t)\right]/t \geq 1/\mathbb {E}\left[X\right]-1/t$ on the same graph with (c).

Sketch $\mathbb {E}\left[S_{N(t)+1}-t\right]$ as a function of $t$ and find the time average of this quantity.

Evaluate $\mathbb {E}\left[S_{N(t)}\right]$ as a function of $t$; verify that $\mathbb {E}\left[S_{N(t)}\right] \neq \mathbb {E}\left[X\right] \mathbb {E}\left[N(t)\right]$.

For all $x>0$ and $t>x$ show that $\mathbb {E}\left[N(t) \mid X_{1} = x\right] = \mathbb {E}\left[N(t-x)\right]+1$.

Use (a) to show that $m(t) = \mathsf{F}_{X}(t)+\int_{0}^{t} m(t-x) \, d\mathsf{F}_{X}(x)$ for $t>0$. This equation is the renewal equation, derived differently in (5.55).

Suppose that $X$ is an exponential rv of parameter $\lambda$. Evaluate $L_{m}(s)$ from (5.57); verify that the inverse Laplace transform is $\lambda t$; $t \geq 0$.

Let the inter-renewal interval of a renewal process have a second-order Erlang density, $\mathsf{f}_{X}(x) = \lambda^{2} x \exp (-\lambda x)$. Evaluate the Laplace transform of $m(t) = \mathbb {E}\left[N(t)\right]$.

Use this to evaluate $m(t)$ for $t \geq 0$. Verify that your answer agrees with (5.59).

Evaluate the slope of $m(t)$ at $t = 0$ and explain why that slope is not surprising.

View the renewals here as being the even numbered arrivals in a Poisson process of rate $\lambda$. Sketch $m(t)$ for the process here and show one half the expected number of arrivals for the Poisson process on the same sketch. Explain the difference between the two.

Let $N(t)$ be the number of arrivals in the interval $(0, t]$ for a Poisson process of rate $\lambda$. Show that the probability that $N(t)$ is even is $[1+\exp (-2 \lambda t)]/2$.

Let $\widetilde{N}(t)$ be the number of even numbered arrivals in $(0, t]$. Show that $\widetilde{N}(t) = N(t)/2-\mathbb {I}_{\mathrm{odd}}(t)/2$ where $\mathbb {I}_{\mathrm{odd}}(t)$ is a random variable that is 1 if $N(t)$ is odd and 0 otherwise.

Use (a) and (b) to find $\mathbb {E}\left[\widetilde{N}(t)\right]$. Note that this is $m(t)$ for a renewal process with second-order Erlang inter-renewal intervals.

Consider a function $r(z) \geq 0$ defined as follows for $0 \leq z<\infty$: For each integer $n \geq 1$ and each integer $k, 1 \leq k<n$, $r(z) = 1$ for $n+k/n \leq z \leq n+k/n+2^{-n}$. For all other $z$, $r(z) = 0$. Sketch this function and show that $r(z)$ is not directly Riemann integrable.

Evaluate the Riemann integral $\int_{0}^{\infty } r(z) \, dz$.

Suppose $r(z)$ is decreasing, i.e., that $r(z) \geq r(y)$ for all $y>z>0$. Show that if $r(z)$ is Riemann integrable, it is also directly Riemann integrable.

Suppose $f(z) \geq 0$, defined for $z \geq 0$, is decreasing and Riemann integrable and that $f(z) \geq r(z)$ for all $z \geq 0$. Show that $r(z)$ is Directly Riemann integrable.

Let $X$ be a nonnegative rv for which $\mathbb {E}\left[X^{2}\right]<\infty$. Show that $x \mathsf{F}_{X}^{c}(x)$ is directly Riemann integrable.

$\mathsf{f}_{Y(t)}(y \mid Z(t+s/2) = s)$ for given $s>0$;

$\mathsf{f}_{Y(t), Z(t)}(y, z)$;

$\mathsf{f}_{Y(t) \mid \widetilde{X}(t)}(y \mid x)$;

$\mathsf{f}_{Z(t) \mid Y(t-s/2)}(z \mid s)$ for given $s>0$;

$\mathsf{f}_{Y(t)}(y \mid Z(t+s/2) \geq s)$ for given $s>0$.

Find $\lim_{t \rightarrow \infty }\left\{ \mathbb {E}\left[N(t)\right]-t/\overline{X}\right\}$ for a renewal counting process $\left\{ N(t); t>0\right\}$ with inter-renewal times $\left\{ X_{i}; i \geq 1\right\}$.

Evaluate your result for the case in which $X$ is an exponential rv (you already know what the result should be in this case).

Evaluate your result for a case in which $\mathbb {E}\left[X\right]<\infty$ and $\mathbb {E}\left[X^{2}\right] = \infty$. Explain (very briefly) why this does not contradict the elementary renewal theorem.

Draw a sketch of a sample function of $R(t)$.

Given that the first bus arrives at time $X_{1} = x$, find the expected number of customers picked up; then find $\mathbb {E}\left[\int_{0}^{x} R(t) \, dt\right]$, again given the first bus arrival at $X_{1} = x$.

Find $\lim_{t \rightarrow \infty } \frac{1}{t} \int_{0}^{t} R(\tau ) \, d\tau$ (with probability 1). Assuming that $\mathsf{F}_{X}$ is a non-arithmetic distribution, find $\lim_{t \rightarrow \infty } \mathbb {E}\left[R(t)\right]$. Interpret what these quantities mean.

Use (c) to find the time-average expected wait per customer.

Find the fraction of time that there are no customers at the bus stop. (Hint: this part is independent of (a), (b), and (c); check your answer for $\mathbb {E}\left[X\right] \ll 1/\lambda$.)

Is $N_{A}(t)$ a renewal counting process? Explain your answer and if you are not sure, look at several examples for $N_{2}(t)$.

Find $\lim_{t \rightarrow \infty } \frac{1}{t} N_{A}(t)$ and explain why the limit exists with probability 1. Hint: Use symmetry -- i.e., look at $N_{1}(t)-N_{A}(t)$. To show why the limit exists, use the renewal-reward theorem. What is the appropriate renewal process to use here?

Now suppose that $\left\{ N_{1}(t); t>0\right\}$ is a non-arithmetic renewal counting process but not a Poisson process and let the expected inter-renewal interval be $1/\lambda$. For any given $\delta$, find $\lim_{t \rightarrow \infty } \mathbb {E}\left[N_{A}(t+\delta )-N_{A}(t)\right]$ and explain your reasoning. Why does your argument in (b) fail to demonstrate a time average for this case?

Find the fraction of time that the system is empty as a function of $\lambda$ and $\mathbb {E}\left[Z\right]$. State carefully what you mean by such a fraction.

Apply Little's theorem, not to the system as a whole, but to the number of customers in the server (i.e., 0 or 1). Use this to find the fraction of time that the server is busy.

Combine your results in (a) and (b) to find $\mathbb {E}\left[Z\right]$ in terms of $\lambda$ and $\mathbb {E}\left[Y\right]$; give the fraction of time that the system is idle in terms of $\lambda$ and $\mathbb {E}\left[Y\right]$.

Find the expected duration of a busy period.