Question

Wald's equation can be used as the basis of a proof of the elementary renewal theorem. Let \(X_{1}, X_{2}, \ldots\) denote the interarrival times of a renewal process and let \(N(t)\) be the number of renewals by time \(t\). (a) Show that whereas \(N(t)\) is not a stopping time, \(N(t)+1\) is. Hint: Note that $$ N(t)=n \Leftrightarrow X_{1}+\cdots+X_{n} \leqslant t \text { and } X_{1}+\cdots+X_{n+1}>t $$ (b) Argue that $$ E\left[\sum_{i=1}^{N(t)+1} X_{i}\right]=\mu[m(t)+1] $$ (c) Suppose that the \(X_{i}\) are bounded random variables. That is, suppose there is a constant \(M\) such that \(P\left[X_{i}

Short answer

In summary, we proved that \(N(t)\) is not a stopping time, but \(N(t)+1\) is. We then showed that \(E\left[\sum_{i=1}^{N(t)+1} X_{i}\right]=\mu[m(t)+1]\) and that if the interarrival times are bounded, we have \(t<\sum_{i=1}^{N(t)+1} X_{i}<t+M\). Finally, we used these properties to prove the elementary renewal theorem for bounded interarrival times, which states that \(\lim_{t\to\infty}\frac{m(t)}{t}=\frac{1}{\mu}\).

Step-by-step solution

(a) Show that whereas N(t) is not a stopping time, N(t)+1 is

To show that \(N(t)\) is not a stopping time, we need to show that the event \(\{ N(t) = n \}\) is not in the sigma-algebra generated by the random variables \(X_1, X_2, ... , X_n\). To show that \(N(t) + 1\) is a stopping time, we need to show that the event \(\{ N(t) + 1 = n+1 \}\) is in that sigma-algebra. Consider the event \(\{ N(t) = n \}\). By the given hint, we have: $$ N(t) = n \Leftrightarrow X_1 + \cdots + X_n \leq t \text{ and } X_1 + \cdots + X_{n+1} > t $$ The event that the sum of the first \(n\) interarrival times is less than or equal to \(t\) is in the sigma-algebra, as it only involves the first \(n\) variables. However, the event that the sum of the first \(n+1\) interarrival times is greater than \(t\) is not in the sigma-algebra, as the sum involves \(X_{n+1}\), which is not part of the first \(n\) variables. Thus, the event \(\{ N(t) = n \}\) is not in the sigma-algebra, and \(N(t)\) is not a stopping time. On the other hand, consider the event \(\{ N(t) + 1 = n+1 \}\). This event is equivalent to: $$ X_1 + \cdots + X_n \leq t < X_1 + \cdots + X_{n+1} $$ Notice that both the sum of the first \(n\) interarrival times and the sum of the first \(n+1\) interarrival times involve only variables up to \(X_{n+1}\), which are part of the first \((n+1)\) variables. Thus, this event is in the sigma-algebra, and \(N(t) + 1\) is a stopping time.

(b) Determine E(sum from i=1 to N(t)+1 of X_i)=μ[m(t)+1]

To find the expected value of the sum of the interarrival times, we can apply Wald's equation, which is given by: $$ E\left[\sum_{i=1}^{N(t)+1} X_i\right] = E[X_1]E[N(t) + 1] = \mu E[N(t) + 1] $$ Here, \(\mu\) is the expected value of the interarrival times, \(E[X_i]\). Recall that \(m(t) = E[N(t)]\) represents the expected number of renewals by time \(t\). Thus, we have: $$ E[N(t) + 1] = E[N(t)] + 1 = m(t) + 1 $$ So, the desired expression becomes: $$ E\left[\sum_{i=1}^{N(t)+1} X_i\right] = \mu[m(t) + 1] $$

(c) Show if the X_i's are bounded, t

Given that the \(X_i\) are bounded random variables, there exists a constant \(M\) such that \(P[X_i < M] = 1\) for all \(i\). We need to show that if \(X_i\)'s are bounded, then: $$ t < \sum_{i=1}^{N(t)+1} X_i < t+M $$ First, we can easily see that \(t < \sum_{i=1}^{N(t)+1} X_i\) because if this sum was less than or equal to \(t\), then \(N(t) \geq N(t)+1\) which is a contradiction. Now we need to show that \(\sum_{i=1}^{N(t)+1} X_i < t+M\). Notice that the last term of the sum, \(X_{N(t)+1}\), must be smaller than \(M\), because: $$ X_{N(t)+1} < M \Rightarrow X_1 + \cdots + X_{N(t)} + X_{N(t)+1} < X_1 + \cdots +X_{N(t)} + M \Rightarrow \sum_{i=1}^{N(t)+1} X_i < t+M $$ Thus, if the \(X_i\)'s are bounded, we have shown that: $$ t < \sum_{i=1}^{N(t)+1} X_i < t+M $$

(d) Prove the elementary renewal theorem when interarrival times are bounded

Now, we will use parts (a), (b), and (c) to prove the elementary renewal theorem when the interarrival times are bounded. Recall that the elementary renewal theorem states that: $$ \lim_{t\to\infty}\frac{m(t)}{t} = \frac{1}{\mu} $$ where \(\mu\) is the expected value of the interarrival times. We already know from part (b) that: $$ E\left[\sum_{i=1}^{N(t)+1} X_i\right] = \mu[m(t) + 1] $$ and from part (c) that when the interarrival times are bounded: $$ t < \sum_{i=1}^{N(t)+1} X_i < t+M $$ Taking expectations of the inequalities in part (c), we get: $$ t < E\left[\sum_{i=1}^{N(t)+1} X_i\right] < t + M \\ t < \mu[m(t) + 1] < t + M $$ Divide all parts of the inequality by \(t\): $$ 1 < \frac{\mu[m(t) + 1]}{t} < 1+\frac{M}{t} \\ \Rightarrow \frac{1}{\mu} < \frac{m(t)+1}{t} < \frac{1}{\mu}+\frac{M}{\mu t} $$ As \(t \to \infty\), the terms \(\frac{1}{t}\) and \(\frac{M}{\mu t}\) both go to zero: $$ \lim_{t\to\infty}\frac{1}{\mu} = \lim_{t\to\infty}\frac{m(t)+1}{t} = \lim_{t\to\infty}\frac{1}{\mu}+\lim_{t\to\infty}\frac{M}{\mu t} \Rightarrow \frac{1}{\mu} = \lim_{t\to\infty}\frac{m(t)+1}{t} $$ Since \(m(t) + 1\) is asymptotically the same as \(m(t)\), we can rewrite the above expression as: $$ \lim_{t\to\infty}\frac{m(t)}{t} = \frac{1}{\mu} $$ which is the statement of the elementary renewal theorem for bounded interarrival times.

Key concepts

Wald's Equation

Wald's equation is a fundamental result in the theory of stochastic processes that relates the expected value of a sum of random variables to the expected value of the individual random variables and the expected stopping time. It formulates as:
\[ E\left[\sum_{i=1}^{N}X_i\right] = E[X_1]E[N] \]
where \(X_1, X_2, \ldots\) are identically distributed independent random variables with a common expected value, and \(N\) is a stopping time that is independent of the \(X_i\)'s. This theorem is immensely useful as it allows for the calculation of the expected sum without directly summing over potentially unbounded random variables. In the context of renewal processes, which we'll explore next, Wald's Equation is particularly powerful in providing a concise representation of the expected sum of renewal intervals up to a certain point.

Renewal Process

A renewal process is a sequence of events that occur at random time intervals. Each time an event occurs, it 'renews' the process. Mathematically, a renewal process is characterized by the interarrival times \(X_1, X_2, \ldots\), which are the times between consecutive renewals, and are assumed to be independent, identically distributed random variables. The number of renewals by a certain time \(t\), denoted by \(N(t)\), is crucial in understanding the behavior of such processes. Understanding the distribution of renewals over time allows for the analysis of various stochastic systems, such as inventory management, risk assessment, and the scheduling of maintenance for machinery.
The elementary renewal theorem gives a long-term average rate of renewal, which is pivotal for long-term planning and analysis in such systems. Grasping the dynamics governed by the renewal process is critical for students as it provides a basis for more complex models in operations research and reliability engineering.

Stopping Time

In the realm of stochastic processes, a stopping time is a random variable that signifies the time at which a given stochastic process meets a specific condition. Formally, a stopping time with respect to a sequence of random variables \(X_1, X_2, \ldots\) is a time \(N\) for which the occurrence of the event \(N=n\) can be determined solely by the values of \(X_1, X_2, \ldots, X_n\) and not by any future values \(X_{n+1}, X_{n+2}, \ldots\).
Understanding stopping times is imperative as they are widely used in various areas of probability theory, including decision making under uncertainty and financial mathematics. For example, in option pricing, a 'stopping time' can represent the optimal time to exercise an option. For students, a clear grasp of what constitutes a stopping time allows them to frame and solve problems that involve decision points, particularly when the decisions are to be made based on partial information available up to that time.

Expected Value

The expected value, denoted as \(E[X]\), is a fundamental concept in probability and statistics that provides a measure of the central tendency, or 'average', of a random variable. It is a weighted average of all possible values that a random variable can take on, with each value weighted according to its probability of occurrence.
For students tackling problems involving random variables, understanding expected value is crucial since it allows them to predict long-term outcomes of random phenomena. For example, in economics, the expected value is used to determine fair prices for goods or financial instruments that have uncertain future payouts. Notably, the expected value has prominent implications in decision-making processes, risk assessment, and various disciplines that utilize probabilistic models.

Bounded Random Variables

Bounded random variables are variables that have an upper and/or lower bound. Formally, a random variable \(X\) is said to be bounded above if there exists a finite number \(M\) such that \(P[X \leq M] = 1\) and similarly bounded below if there’s a number \(m\) such that \(P[X \geq m] = 1\). For practical purposes, this means that the values of \(X\) will not exceed certain thresholds, which can be greatly beneficial when analyzing and drawing conclusions about the behavior of stochastic models.
Understanding the properties of bounded random variables enables students to make substantial simplifications when calculating probabilities, expected values, and variances. Additionally, boundedness is a significant attribute in the context of the Law of Large Numbers and Central Limit Theorem, which are mainstays of statistical theory. It helps guarantee certain convergence properties and enables more robust predictions and estimates, which are pivotal for applications in domains like insurance, risk management, and various fields of engineering.