Probability that binomial distribution is larger than a certain value.

Question

Let $X$ be random value taking values in $\{-1,1\}$, each with probability $\frac{1}{2}$, and let $X_n$ be the sum of $n$ independent copies of $X$. Then, if I interpreted it correctly, the central limit theorem says that $\frac{X_n}{\sqrt{n}}$ converges in distribution to $\mathcal{N}(0,1)$, that is, for each $k\in\mathbb{R}$, $P(X_n\geq k\sqrt{n})\to P(Y\geq k)$, where $Y$ has distribution $\mathcal{N}(0,1)$.

However, I am interested in how fast $P(X_n\geq k(n)\sqrt{n})$ decreases, where $k(n)$ is a sequence going to infinity. The cases $k(n)=\ln(n)$ and $k(n)=n^\alpha$, for small $\alpha$, should be enough.

Context: I ended up thinking about this while trying to solve a problem in a course about the probabilistic method. I know essentially nothing about statistics, so sorry if this is standard material in statistics courses.

Answer 1

If the normal approximation is appropriate in the tail then a reasonable approximation to that approximation might suggest $$P(X_n\geq k(n)\sqrt{n}) \approx \frac{\exp(-k(n)^2/2)}{\sqrt{2\pi} \, k(n)} \tag{1}$$

though the normal approximation is not so good in the tail in your $n^\alpha$ example when $\alpha$ is close to $\frac12$ and no good at all when $\alpha$ is larger than that.

Here is an illustration using R for $k(n)=\log_e(n)$: note the scale is logarithmic to display low probabilities, the actual probabilities are points showing the discreteness of the binomial distribution, the normal tail approximation is in red and the close approximation $(1)$ to that approximation is in blue.

thisfunction <- function(n){ log(n) }
maxn <- 200
n <- 1:maxn
plot(n, pbinom((n+thisfunction(n)*sqrt(n))/2, n, 1/2, lower.tail=FALSE), 
     log="y") 
curve(pnorm(thisfunction(x), lower.tail=FALSE), 
      from=1, to=maxn, add=TRUE, col="red")
curve(exp(-thisfunction(x)^2/2)/sqrt(2*pi)/thisfunction(x), 
      from=1, to=maxn, add=TRUE, col="blue")