Supremum of sum of exponentially distributed random variables

Question

Let $(X_i)_{i\in\mathbb{N}}$ be independent, exponentially distributed random variables with parameter $\lambda$. Define for $t\gt0$ $N_t:=\sup\{n\in\mathbb{N}:\sum_{k=1}^{n} X_k\le t\}$. Show that $N_t$ is poisson distributed with parameter $\lambda t$.

My ideas: Since the sum of $n$ exponential random variables is gamma-distributed with parameters $n,\lambda$ we have: $P(N_t\le s)=P(\sum_{k=1}^{s}X_k\le t)=\int_{-\infty}^t \dfrac{\lambda^s}{\Gamma(s)}x^{s-1}\exp^{-\lambda x}dx$.
I want this to equal $\dfrac{(\lambda t)^s}{s!}\exp^{-\lambda t}$ to show it is poisson distributed, but I am having trouble evaluating the integral and would appreciate all help!

Answer 1

First of all, you're confused about a basic difference between PMFs and CDFs: if $N_t \sim \operatorname{Poisson}(\lambda t)$, then $$\Pr[N_t \le s] \ne \Pr[N_t = s] = e^{-\lambda t} \frac{(\lambda t)^s}{s!}.$$

If $N_t = s$, then what this means is that $\displaystyle \sum_{k=1}^s X_k \le t$, yet $\displaystyle \sum_{k=1}^{s+1} X_k > t$. What is the probability of such an event occurring? This involves an integration but not of the sort you were looking at. What you want is that the gamma variable $T_s \sim \operatorname{Gamma}(s,\lambda)$ is at most $t$, but adding on the next exponential variable $X_{s+1}$ will make $X_{s+1} + T_s > t$. How do you do this? $$\Pr[N_t = s] = \int_{x=0}^t f_{T_s}(x) S_{X_{s+1}}(t-x) \, dx.$$ The computation I leave to you.