Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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)$.

share|cite|improve this question
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
up vote 1 down vote accepted

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.

share|cite|improve this answer
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}$$

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.