5
$\begingroup$

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

  • 0
    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!2011-12-11
  • 0
    @DavidHeider Sorry, I forget it is exponential variables.2011-12-11
  • 1
    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.2011-12-11
  • 0
    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$?2011-12-11
  • 0
    @MichaelHardy I have revised.2011-12-11

2 Answers 2

1

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.

  • 0
    What does $(U_k)_k$ represent?2011-12-12
  • 0
    $U_k=X_k-1$... $ $2011-12-12
  • 0
    It seems that the results has nothing to with $X_k$'s distribution as long as it is iid and centered?2011-12-14
  • 0
    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$...2011-12-15
  • 0
    Are there any non asymptotic approaches?2011-12-16
  • 0
    Hi Didier, how to get the $mathbb(Z)$ from your current result?2012-01-27
  • 0
    Fan: ?? What are you talking about?2012-01-27
1

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_kt)=\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}$$

  • 3
    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}$.2011-12-11
  • 1
    I think you may have misread the definition of $Z_n$. :)2011-12-11
  • 0
    @cardinal You are right.2011-12-11