Limiting Sum of i.i.d. Gamma variates

Question

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?

Answer 1

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.

Answer 2

As an alternative to whuber's excellent answer, I will try to derive the exact limit of the probability in question. One of the properties of the gamma distribution is that sums of independent gamma random variables with the same rate/scale parameter are also gamma random variables with shape equal to the sum of the shapes of those variables. (That can be proved using the generating functions of the distribution.) In the present case we have $X_1,...X_n \sim \text{IID Gamma}(3,1)$, so we obtain the sum:

$$S_n \equiv X_1 + \cdots + X_n \sim \text{Gamma}(3n, 1).$$

We can therefore write the exact probability of interest using the CDF of the gamma distribution. Letting $a = 3n$ denote the shape parameter and $x = 3(n-\sqrt{n})$ denote the argument of interest, we have:

$$\begin{equation} \begin{aligned} H(n) &\equiv \mathbb{P}(S_n \geq 3(n-\sqrt{n})) \\[12pt] &= \frac{\Gamma(a, x)}{\Gamma(a)} \\[6pt] &= \frac{a \Gamma(a)}{a \Gamma(a) + x^a e^{-x}} \cdot \frac{\Gamma(a+1, x)}{\Gamma(a+1)}. \\[6pt] \end{aligned} \end{equation}$$

To find the limit of this probability, we first note that we can write the second parameter in terms of the first as $x = a + \sqrt{2a} \cdot y$ where $y = -\sqrt{3/2}$. Using a result shown in Temme (1975) (Eqn 1.4, p. 1109) we have the asymptotic equivalence:

$$\begin{aligned} \frac{\Gamma(a+1, x)}{\Gamma(a+1)} &\sim \frac{1}{2} + \frac{1}{2} \cdot \text{erf}(-y) + \sqrt{\frac{2}{9a \pi}} (1+y^2) \exp( - y^2). \end{aligned}$$

Using Stirling's approximation, and the limiting definition of the exponential number, it can also be shown that:

$$\begin{aligned} \frac{a \Gamma(a)}{a \Gamma(a) + x^a e^{-x}} &\sim \frac{\sqrt{2 \pi} \cdot a \cdot (a-1)^{a-1/2}}{\sqrt{2 \pi} \cdot a \cdot (a-1)^{a-1/2} + x^a \cdot e^{a-x-1}} \\[6pt] &= \frac{\sqrt{2 \pi} \cdot a \cdot (1-\tfrac{1}{a})^{a-1/2}}{\sqrt{2 \pi} \cdot a \cdot (1-\tfrac{1}{a})^{a-1/2} + \sqrt{x} \cdot (\tfrac{x}{a})^{a-1/2} \cdot e^{a-x-1}} \\[6pt] &= \frac{\sqrt{2 \pi} \cdot a \cdot e^{-1}}{\sqrt{2 \pi} \cdot a \cdot e^{-1} + \sqrt{x} \cdot e^{x-a} \cdot e^{a-x-1}} \\[6pt] &= \frac{\sqrt{2 \pi} \cdot a}{\sqrt{2 \pi} \cdot a + \sqrt{x}} \\[6pt] &\sim \frac{\sqrt{2 \pi a}}{\sqrt{2 \pi a} + 1}. \\[6pt] \end{aligned}$$

Substituting the relevant values, we therefore obtain:

$$\begin{equation} \begin{aligned} H(n) &= \frac{a \Gamma(a)}{a \Gamma(a) + x^a e^{-x}} \cdot \frac{\Gamma(a+1, x)}{\Gamma(a+1)} \\[6pt] &\sim \frac{\sqrt{2 \pi a}}{\sqrt{2 \pi a} + 1} \cdot \Bigg[ \frac{1}{2} + \frac{1}{2} \cdot \text{erf} \Big( \sqrt{\frac{3}{2}} \Big) + \sqrt{\frac{2}{9a \pi}} \cdot \frac{5}{2} \cdot \exp \Big( \frac{3}{2} \Big) \Bigg]. \\[6pt] \end{aligned} \end{equation}$$

This gives us the limit:

$$\lim_{n \rightarrow \infty} H(n) = \frac{1}{2} + \frac{1}{2} \cdot \text{erf} \Big( \sqrt{\frac{3}{2}} \Big) = 0.9583677.$$

This gives us the exact limit of the probability of interest, which is larger than one-half.