# Problem about the sum of independent exponential variable

Let $X_1,\ldots,X_{n}$ be independent exponential variables with mean 1, and let $S_k = X_1+\cdots+ X_k$, it is not hard to get $\mathbb{E}(S_k)=k$.

Let random variable $Y_k=|S_k-k|$,

My first question is: what is the probability of $Y>t$ for some $t>0$, in another word: $\Pr(Y>t)$?

Define another random variable $Z=\max_{k=1}^n Y_k$

The second question is: how to calculate $\Pr(Z>t)$ for some $t>0$ or $\mathbb {E} (Z)$.

-
what distribution are you dealing with? exponential? gaussian? binomial? are the variable identically and independently distributed? Please clarify this and I am sure there'll be someone who can answer your question! – David Heider Dec 11 '11 at 15:22
@DavidHeider Sorry, I forget it is exponential variables. – Fan Zhang Dec 11 '11 at 15:24
Do you know the distribution of $S_k$? Note that $\mathbb P(Y_k > t) = \mathbb P(S_k > t + k) + \mathbb P(S_k < k - t)$. Be careful, since the second term on the right-hand side can be (trivially) zero. – cardinal Dec 11 '11 at 16:37
Your expression $\max_{i=1}^n Y_k$ doesn't make a lot of sense. Might you have meant $\max_{k=1}^n Y_k$? – Michael Hardy Dec 11 '11 at 16:45
@MichaelHardy I have revised. – Fan Zhang Dec 11 '11 at 16:46

Let $U_k=X_k-1$. Then $(U_k)_k$ is i.i.d. and centered and, for large values of $n$, $S_n-n=\sum\limits_{k=1}^nU_k$ is approximately $\sqrt{n}$ times a centered gaussian with variance $\mathrm E(U_1^2)=1$. As such, the central limit theorem yields that, for every nonnegative $x$, $\mathrm P(Y_n\geqslant x\sqrt{n})\to\mathrm P(W_1\geqslant x)$ when $n\to\infty$, where $W_1$ denotes a standard gaussian random variable.

Likewise, the functional central limit theorem asserts that the path $(W_n(t))_{0\leqslant t\leqslant 1}$ behaves more and more like the path of a standard Brownian motion $(W_t)_{0\leqslant t\leqslant 1}$. Here $W_n(k/n)=(S_k-k)/\sqrt{n}$ for every integer $0\leqslant k\leqslant n$ and $(W_n(t))_{0\leqslant t\leqslant 1}$ is the linear interpolation of these values.

In particular $\mathrm P(Z_n\geqslant x\sqrt{n})\to\mathrm P(\tau_x\leqslant 1)$ when $n\to\infty$, where $\tau_x=\inf\{t\geqslant0\ ;\, |W_t|\geqslant x\}$.

The distribution of $\tau_x$ is well known and best described by its Laplace transform which is, if I remember correctly, $$\mathrm E_0(\mathrm e^{-\lambda\tau_x})=1/\cosh(x\sqrt{2\lambda}),$$ from which the density of $\tau_x$ may be deduced. For a reference, I would check these lecture notes by Yuval Peres and Peter Mörters or one of Rick Durrett's textbooks.

-
What does $(U_k)_k$ represent? – Fan Zhang Dec 12 '11 at 13:55
$U_k=X_k-1$...  – Did Dec 12 '11 at 14:41
It seems that the results has nothing to with $X_k$'s distribution as long as it is iid and centered? – Fan Zhang Dec 14 '11 at 15:53
i.i.d., centered and has variance 1. The results then follow from the Central Limit Theorem. Of course, this is an approximation that only holds for large $n$... – Craig Dec 15 '11 at 19:28
Are there any non asymptotic approaches? – Fan Zhang Dec 16 '11 at 6:31

We can use the fact that a density of $S_k$ is $f(x)=\frac{x^{k-1}}{(k-1)!}e^{-x}\mathbf 1_{x\geq 0}$. We have after integrations by parts $$P(S_k-k>t)=e^{-(t+k)}\sum_{j=0}^{k-1}\frac{(t+k)^j}{j!},$$ and $$P(S_k<k-t)=\begin{cases} 1-e^{k-t}\sum_{j=0}^{k-1}\frac{(t-j)^j}{j!}&\mbox{ if } t \leq k\\ 0&\mbox{ otherwise}, \end{cases}$$ hence $$P(|S_k-k|>t)=\begin{cases} e^{-(t+k)}\sum_{j=0}^{k-1}\frac{(t+k)^j}{j!}+1-e^{k-t}\sum_{j=0}^{k-1}\frac{(t-j)^j}{j!}&\mbox{ if } t \leq k\\ e^{-(t+k)}\sum_{j=0}^{k-1}\frac{(t+k)^j}{j!}&\mbox{ otherwise}. \end{cases}$$

-
Just to add, the distribution could be obtained from the fact that the a sum of $k$ independent exponential variables with mean $1/\lambda$ has a Gamma distribution with parameters $\alpha=k$ and $\lambda$ (the density of a Gamma variable with parameters $\alpha>0, \lambda>0$ is $f(x)={\lambda e^{-\lambda x}(\lambda x)^{\alpha-1}\over \Gamma(\alpha)}\cdot\bf 1_{x\ge0}$. – David Mitra Dec 11 '11 at 16:59
I think you may have misread the definition of $Z_n$. :) – cardinal Dec 11 '11 at 17:15
@cardinal You are right. – Davide Giraudo Dec 11 '11 at 17:16