Prove that $P(\xi_{n+1}>t) = e^{-\lambda t} \sum_{k=0}^n \frac{(\lambda t)^k}{k!}$

Question

Let $\xi_n = \eta_1 + \dots + \eta_n$ where $\eta_i$ are iid random variables exponentially distributed with the rate $\lambda>0$. In the book there is a proof that $P(\xi_{n+1}>t) = e^{-\lambda t} \sum_{k=0}^n \frac{(\lambda t)^k}{k!}$. I have troubles with understanding its steps.

$$P(\xi_{n+1}>t)=P(\xi_n+\eta_{n+1} >t)=$$ $$=P(\eta_{n+1}>t)+P(\xi_n>t-\eta_{n+1}, t \ge \eta_{n+1}> 0)$$ $$= e^{-\lambda t} + \int_{0}^t P(\xi_n>t-s) f_{\eta_{n+1}}(s)ds$$ $$=e^{-\lambda t} + \int_0^te^{-\lambda(t-s)} \sum_{k=0}^{n-1} \frac{(\lambda(t-s))^k}{k!} \lambda e^{-\lambda s} ds$$

I don't understand what happened in the 2,3 and 4th line. Thanks for the explanation.

Answer 1

The second line follows by splitting the event into two disjoint events:

\begin{align*} \{ \xi_{n+1} > t \} &= \{ \xi_{n+1} > t, \eta_{n+1} > t \} \cup \{ \xi_{n+1} > t, \eta_{n+1} \leq t \} \\ &= \{ \eta_{n+1} > t \} \cup \{ \xi_n > t - \eta_{n+1}, \eta_{n+1} \leq t \}. \end{align*}

Here, we used the fact that $\xi_{n+1} > t$ is always true given $\eta_{n+1} > t$. Since two events are disjoint, this gives the second line.

For the third line, we utilized the independence between $\xi_n$ and $\eta_{n+1}$ to write

\begin{align*} \Bbb{P}(\xi_n > t - \eta_{n+1}, \eta_{n+1} \leq t) &= \Bbb{E}[ \Bbb{P}( \xi_n > t - \eta_{n+1}, \eta_{n+1} \leq t \mid \eta_{n+1}) ] \\ &= \int_{0}^{\infty} \Bbb{P}( \xi_n > t - u, u \leq t) f_{\eta_{n+1}}(u) \, du \\ &= \int_{0}^{u} \Bbb{P}( \xi_n > t - u) f_{\eta_{n+1}}(u) \, du. \end{align*}

If you have trouble understanding machinery used in this explanation (because it uses a form of law of iterated expectation), we may argue as follows: Since $\xi_n$ and $\eta_{n+1}$ are independent and have density, they have a joint density $f_{\xi_n, \eta_{n+1}}$ which is the product of $f_{\xi_n}$ and $f_{\eta_{n+1}}$. Thus

\begin{align*} \Bbb{P}(\color{blue}{\xi_n} > t - \color{red}{\eta_{n+1}}, \color{red}{\eta_{n+1}} \leq t) &= \int\limits_{\substack{\color{blue}{x} > t - \color{red}{u} \\ \color{red}{u} \leq t}} f_{\color{blue}{\xi_n}, \color{red}{\eta_{n+1}}}(\color{blue}{x}, \color{red}{u}) \, dx du \\ &= \int_{0}^{t} \int_{t-u}^{\infty} f_{\xi_n}(x) f_{\eta_{n+1}}(u) \, dx du \\ &= \int_{0}^{t} \Bbb{P}(\xi_n > t - u) f_{\eta_{n+1}}(u) \, du. \end{align*}

Finally, for the last line, we are using induction hypothesis to prove the formula inductively.

Answer 2

The second equality is an application of the law of total probability. More precisely, \begin{align} \mathbb{P}(\xi_n+\eta_{n+1}>t) &= \mathbb{P}(\xi_n > t-\eta_{n+1} \ | \ \eta_{n+1}>t)\mathbb{P}(\eta_{n+1}>t) + \mathbb{P}(\xi_n > t-\eta_{n+1} \ | \ \eta_{n+1} \leq t)\mathbb{P}(\eta_{n+1} \leq t) \\ &= \mathbb{P}(\eta_{n+1}>t) + \underbrace{\mathbb{P}(\xi_n > t-\eta_{n+1}, \eta_{n+1} \leq t)}_{(2)} \end{align} Note that $\mathbb{P}(\xi_n > t-\eta_{n+1} \ | \ \eta_{n+1}>t) = 1$. The reason is that given $\eta_{n+1}>t: t-\eta_{n+1}<0$. However, $\xi_n >0$ since it is the sum of exponential random variables. The other equality $(2)$ follows immediately from the definition of conditional probability.

Answer 3

The explanation given by @Siron is good.

The reason for this "answer" is that there is an appealing and simple proof of your equality.

In fact, you may have notice that the terms in the RHS refer to Poisson distribution (and in the LHS to a Gamma distribution).

This gives an hint for a connection between the LHS and RHS that is simply described by the equivalence between the two following sentences:

• (LHS) The event numbered $n+1$ has occurred after time $t$.

• (RHS) At most $n$ events have occurred in time interval $\left[0,t\right]$.

(Think you are on the border of a road counting how many cars are passing by...).