Is $\mathbb{P}(S_n/n>p+a)$ a decreasing function of n?

Question

In my question, I have i.i.d random variables $X_1,...,X_n$ $\sim \text{Bern}(p)$ (Bernoulli distribution with parameter $p$). Denote $S_n = \sum_{i=1}^{n} X_i$. Does $\mathbb{P}(S_n/n>p+a)$ decrease when $n$ increases, where $a$ is a fixed positive value?

Update: or when $n$ is big enough?

Answer 1

No, it does not decrease, but oscillates. Here is a graph of the probability in question for $p=1/2, a=1/10$, for $n=1$ up to $n=100$. A rigorous proof can be achieved by analysing the probability in question, given by

$$P\{\frac{S_n}{n}>p+a\}=\sum_{k>n(p+a)}{n\choose k}p^k(1-p)^{n-k}$$ which follows from the fact that $S_n/n$ takes the value $k/n$ with probability ${n\choose k}p^k(1-p)^{n-k}$.

Answer 2

This probability does decrease as $n$ grows.

A heuristic justification is that as $n \rightarrow \infty$, $S_n/n \rightarrow p$, in probability. That is for any $\epsilon > 0$

$$\lim_{n\rightarrow \infty} \mathbf{P}(|S_n/n - p| > \epsilon) = 0.$$

I'm sure its possible to prove this for small $n$ using direct calculation using inequalities for binomial coefficients (I'll leave that to someone else).

Since the sum of $n$ independent Bernoulli $p$ variables has a binomial $\text{Bin}(n,p)$ distribution, an argument for the limiting case is that the De Moivre - Laplace Theorem asserts as $n \rightarrow \infty$

$$ \text{Bin}(n,p) \sim N\big(np,np(1-p) \big)$$

Therefore (using properties of expectations and variance)

$$\left( \frac{1}{n}S_n -p \right) \sim N \left( 0, \frac{p(1-p)}{n}\right).$$

So that in the limit $n \rightarrow \infty$ your question is

$$\lim_{n\rightarrow \infty} \mathbf{P}\left( N \left( 0, \frac{p(1-p)}{n}\right) > a \right) = 0.$$

One can of course show that the probability for the normal distribution above is decreasing in $n$, though you need to be careful with the fact that the Binomial approximation to the Normal holds only in the limit.

Answer 3

I'd like to add very simple observation which works for every sequence with bounded variance. Let $p_n = \mathbb{P}\left({S_n \over n} > p + \alpha\right)$. Let's calculate $\mathbb{D} {S_n \over n} = {1 \over n^2} \mathbf{Var} (S_n) = {1 \over n} \mathbf{Var} (X_1)$. Thus, by the Chebyshov's inequality $p_n \le {\mathbb{D} {S_n \over n} \over \alpha^2} = \mathbf{Var}(X_1) {1 \over n \alpha^2}$. Thus $p_n$ is bounded by a decreasing sequence, hence it contains a decreasing subsequence.