# 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 .. Apr 25, 2018 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, 2018 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})$. Apr 25, 2018 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.

• This illustrates that Chebyshev's inequality (while crude) is fine for bounding the 'typical' behaviour of $X-\mu$, so $P(|X-\mu|>d)<\epsilon$ when $\epsilon$ is not very small and $d$ is a few standard deviations. Chebyshev's inequality is often too crude when you want a bound like this for small $\epsilon$ and moderately large $d$ Sep 21, 2021 at 22:54

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{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}

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{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}

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.