Stochastic Processes – Problem 42: Prove that

Let $X_{1},\cdots X_{n}\stackrel{iid}{\sim}X$, and define $S_{n}=\sum_{i=1}^{n}X_{i}$, $N(t)=\inf\{n:S_{n}>t\}$, so that $N(t)$ is a renewal process.

(1) Prove that $\mathbb{P}(X_{N(t)}>x)\geq\mathbb{P}(X>x),\forall x\geq0$.

(2) If $X$ has distribution function $F(x)=1-e^{-x}$, find the exact analytic expression for $\mathbb{P}(X_{N(t)}>x)$.

(3) Using the key renewal theorem, find $\lim_{t\to\infty}\mathbb{E}X_{N(t)}$.

(1) Step 1. Let $H(t, x) = \mathbb{P}(X_{N(t)} > x)$. By conditioning on the first renewal time $X_1$, we establish a renewal equation for $H(t, x)$. When $X_1 > t$, $N(t) = 1$ and $X_{N(t)} = X_1$, so $\mathbb{P}(X_{N(t)} > x | X_1 > t) = \mathbb{P}(X_1 > x | X_1 > t)$. When $X_1 \leq t$, the process restarts from $t - X_1$, so $X_{N(t)}$ has the same distribution as $X_{N(t-X_1)}$. Thus: $H(t, x) = \mathbb{P}(X_1 > \max(t, x)) + \int_0^t H(t-y, x) dF(y).$

Step 2. Let $\bar{F}(x) = 1 - F(x) = \mathbb{P}(X > x)$. Set $\Delta(t) = H(t, x) - \bar{F}(x)$. Substituting into the renewal equation and simplifying, $\Delta(t)$ satisfies a renewal equation $\Delta(t) = z(t) + \int_0^t \Delta(t-y) dF(y)$ with source term $z(t) = \bar{F}(\max(t, x)) - \bar{F}(x) + \bar{F}(x)F(t)$.

Step 3. Analyze the sign of $z(t)$. When $t < x$: $z(t) = \bar{F}(x)F(t) \geq 0$. When $t \geq x$: $z(t) = \bar{F}(t)F(x) \geq 0$. So $z(t) \geq 0$ for all $t \geq 0$.

Step 4. By the renewal equation solution, $\Delta(t) = \int_0^t z(t-y) dU(y)$ where $U(t) = \sum_{n=0}^\infty F^{*n}(t)$ is the renewal function. Since $z(t) \geq 0$ and $dU(y)$ is a non-negative measure, $\Delta(t) \geq 0$, i.e., $\mathbb{P}(X_{N(t)} > x) \geq \mathbb{P}(X > x)$. QED.

(2) Since $F(x) = 1 - e^{-x}$, $X$ is exponential with rate 1. The renewal function is $U(t) = 1 + t$. Using the renewal equation solution and computing the integrals for the cases $x > t$ and $x \leq t$: When $x > t$: $H(t, x) = e^{-x}(1 + t)$. When $x \leq t$: $H(t, x) = e^{-x}(1 + x)$. In compact form: $\mathbb{P}(X_{N(t)} > x) = e^{-x}(1 + \min(x, t))$.

(3) Define $g(t) = \mathbb{E}[X_{N(t)}]$. Conditioning on $X_1$ yields the renewal equation $g(t) = h(t) + \int_0^t g(t-y) dF(y)$ where $h(t) = \int_t^\infty y dF(y)$. We have $\int_0^\infty h(t) dt = \mathbb{E}[X^2]$. Assuming $\mathbb{E}[X^2] < \infty$, $h(t)$ is directly Riemann integrable. By the key renewal theorem: $\lim_{t \to \infty} g(t) = \frac{1}{\mu} \int_0^\infty h(t) dt = \frac{\mathbb{E}[X^2]}{\mathbb{E}[X]}$.

(1) QED. (2) $\mathbb{P}(X_{N(t)} > x) = e^{-x}(1 + \min(x, t))$. (3) $\dfrac{\mathbb{E}[X^2]}{\mathbb{E}[X]}$