# Limiting Sum of i.i.d. Gamma variates

Let $X_1,X_2,\ldots$ be a sequence of independently and identically distributed random variables with the probability density function; $$f(x) = \left\{ \begin{array}{ll} \frac{1}{2}x^2 e^{-x} & \mbox{if x>0};\\ 0 & \mbox{otherwise}.\end{array} \right.$$ Show that $$\lim_{n\to \infty} P[X_1+X_2+\ldots+X_n\ge 3(n-\sqrt{n})] \ge \frac{1}{2}$$

What I attempted

At first sight I thought it should use Chebyshev's inequality as the question is asking show a lower bound $X_1+X_2+\ldots +X_n$. However, I thought about the limit sign which is clearly indicating that the problem can be somehow related to Central Limit Theorem (CLT)

Let $S_n=X_1+X_2+\ldots +X_n$
$$E(S_n)=\sum_{i=0}^{n} E(X_i)=3n \ (\text{since } E(X_i)=3) \\ V(S_n)=\sum_{i=0}^{n} V(X_i)=3n \ (\text{since } V(X_i)=3 \text{ and } X_i \text{ are i.i.d})$$

Now, Using CLT, for large $n$, $X_1+X_2+........+X_n \sim N(3n,3n)$
Or, $$z=\frac{S_n-3n}{\sqrt{3n}} \sim N(0,1) \text{ as } n\to \infty$$

Now, $$\lim_\limits{n\to \infty} P[X_1+X_2+........+X_n\ge 3(n-\sqrt{n})] = \lim_\limits{n\to \infty}P(S_n-3n \ge -3\sqrt{n}) = \lim_\limits{n\to \infty} P\left(\frac{S_n-3n}{\sqrt{3n}} \ge -\sqrt{3}\right) =P(z\ge -\sqrt{3}) =P\left(-\sqrt{3}\le z<0\right)+P(z\ge 0 ) =P\left(-\sqrt{3}\le z<0\right)+\frac{1}{2}\cdots(1)$$

Since $P(-\sqrt{3}\le z<0) \ge 0$, thus from $(1)$, $$\lim_\limits{n\to \infty} P[X_1+X_2+........+X_n\ge 3(n-\sqrt{n})]\ge \frac{1}{2}$$

Am I correct?

• CLT seems a reasonable approach but "$\lim_\limits{n\to \infty} P[X_1+X_2+........+X_n\ge 3(n-\sqrt{n})] =P(S_n-3n \ge -3\sqrt{n})$" doesn't make sense .. – P.Windridge Apr 25 '18 at 15:49
• I think it should be $$\lim_\limits{n\to \infty} P[X_1+X_2+........+X_n\ge 3(n-\sqrt{n})] =\lim_\limits{n\to \infty}P(S_n-3n \ge -3\sqrt{n}) =\lim_\limits{n\to \infty}P\left(\frac{S_n-3n}{\sqrt{3n}} \ge -\sqrt{3}\right) =P(z\ge -\sqrt{3})$$ – user159457 Apr 25 '18 at 16:06
• As an alternative, consider that iid $X_i \sim\Gamma(3,1)$ and so $X_1+X_2+\cdot+X_n \sim \Gamma(3n,1)$. The median of a Gamma random variable is not known in closed form but it is known (cf. Wikipedia) that for large $n$, the median of a $\Gamma(3n,1)$ random variable lies between $3n-\frac 13$ and $3n$. Since $3(n-\sqrt{n}) < 3n-\frac 13$, it must be that at least half of the probability mass lies to the right of $3(n-\sqrt{n})$. – Dilip Sarwate Apr 25 '18 at 16:28

You were correct that Chebyshev's Inequality will work. It provides a somewhat crude but effective bound which applies to many such sequences, revealing that the crucial feature of this sequence is that the variance of the partial sums grows at most linearly with $n$.

Consider, then, the extremely general case of any sequence of uncorrelated variables $X_i$ with means $\mu_i$ and finite variances $\sigma_i^2.$ Let $Y_n$ be the sum of the first $n$ of them,

$$Y_n = \sum_{i=1}^n X_i.$$

Consequently the mean of $Y_n$ is

$$m_n = \sum_{i=1}^n \mu_n$$

and its variance is

$$s_n^2 = \operatorname{Var}(Y_n) = \sum_{i=1}^n \operatorname{Var}(X_i) + 2\sum_{j > i}\operatorname{Cov}(X_i,X_j) = \sum_{i=1}^n \sigma_i^2.$$

Suppose $s_n^2$ grows at most linearly with $n$: that is, there exists a number $\lambda\gt 0$ such that for all sufficiently large $n,$ $s_n^2 \le \lambda^2 n.$ Let $k\gt 0$ (yet to be determined), observe that

$$m - k \sqrt{n} \le m - \frac{k}{\lambda}s_n,$$

and apply Chebyshev's Inequality to $Y_n$ to obtain

\eqalign{ \Pr(Y_n \ge m_n - k\sqrt{n}) &\ge \Pr(Y_n \ge m_n - \frac{k}{\lambda}s_n) \\ &\ge \Pr(|Y_n - m_n| \le \frac{k}{\lambda} s_n) \\ &\ge 1 - \frac{\lambda^2}{k^2}. }

The first two inequalities are basic: they follow because each successive event is a subset of the preceding one.

In the case at hand, where $X_i$ are independent (and therefore uncorrelated) with means $\mu_i=3$ and variances $\sigma_i^2=3,$ we have $m_n=3n$ and

$$s_n = \sqrt{3}\sqrt{n},$$

whence we may take $\lambda$ as small as $\sqrt{3}.$ The event in the question $3(n-\sqrt{n}) = \mu_n - 3\sqrt{n}$ corresponds to $k=3,$ where

$$\Pr(Y_n \ge 3n - 3\sqrt{n}) \ge 1 - \frac{\sqrt{3}^{\ 2}}{3^2} = \frac{2}{3}\gt \frac{1}{2},$$

QED.