# Deriving condition to get correct asymptotic bound

Suppose that $$X\sim \text{Bin}(n,\theta)$$. Note that $$X$$ is the sum of $$n$$ $$iid$$ Bernoulli($$\theta$$) random variables. By the local limit theorem (Theorem 7 here) for the sum of discrete random variables, $$P(X=t)=\frac{1}{\sqrt{2\pi n\theta(1-\theta)}}\exp\left(-\frac{(t-n\theta)^2}{2n\theta(1-\theta)} \right)+o(n^{-1/2})$$ for all $$n\geq 1$$ and uniformly in the integers $$t$$.

Suppose $$t=n\theta+\sqrt{2\theta(1-\theta)n\log m+O(1)}$$. I am interested in the relationship between $$n$$ and $$m$$, where we can assume, $$m>>n>>1$$. For example, in my application, $$m\approx 20000$$ and $$n\approx 200$$ seems to work well. Intuitively, $$m$$ should grow much faster than $$n$$.

I'm interested in finding a theoretical relationship between $$n$$ and $$m$$ such that quantity $$mP(X=t)=O(1)$$. Now if the $$o(n^{-1/2})$$ remainder were not there, then I can reason the following,

\begin{align*} mP(X=t)&=O(mn^{-1/2}\exp(-O(\log m)))\\ &=O\left(\exp\left(\log m-\log n^{1/2}-O(\log m)\right)\right)\\ &= O\left(\exp\left(\log m^{r}-\log n^{1/2}\right)\right)\text{ for some constant r>0}\\ &= O\left(\frac{m^{r}}{n^{1/2}}\right) \end{align*}

This suggests that $$m\leq n^\gamma$$, where $$\gamma = \frac{1}{2r}>0$$ for $$r>0$$ can be a reasonable relationship.

How do I handle that remainder $$o(n^{-1/2})$$?

To get what you want, you can use the refinement of the local central limit theorem due to Esseen, Theorem 5, page 63, which in your case yields \begin{align} P(X=t)&=\frac1{\sqrt{npq}}\phi(x)\Big(1+\frac1{\sqrt n}\,Q_k(x,1/\sqrt n)\Big)+o(1/n^{(k-1)/2}) %\\ \tag{1} \end{align} as $$n\to\infty$$ uniformly in integer $$t$$, where $$p:=\theta\in(0,1)$$, $$q:=1-p$$, $$\phi(x):=\frac1{\sqrt{2\pi}}\,e^{-x^2/2}$$, $$\begin{equation} x:=\frac{t-np}{\sqrt{npq}}, \end{equation}$$ $$k$$ is any integer $$\ge3$$, and $$Q_k(x,1/\sqrt n)$$ is a polynomial in $$x,1/\sqrt n$$.

Suppose now that $$m=n^c$$, where $$c=c(n)$$ varies with $$n$$ so that $$c\to c_0$$ for some real $$c_0>0$$. Then for your $$t=np+\sqrt{2pqn\ln m+O(1)}$$ and $$x$$ as above we have $$\begin{equation} x=\sqrt{2\ln m+O(1/n)}=\sqrt{2c\ln n+o(1)}=o(n^a) \tag{2} \end{equation}$$ for any real $$a>0$$, whence $$\frac1{\sqrt n}\,Q_k(x,1/\sqrt n)=o(1)$$ in (1).

Using the first equality in (2), we also have
$$\begin{equation} \phi(x)\le e^{-x^2/2}\le\frac{1+O(1/n)}m=\frac{1+o(1)}m. \end{equation}$$ Using now (1) with $$k>2c_0+2$$ (so that $$n^{(k-1)/2}\ge n^{c+1/2}=m\sqrt n$$ for all large enough $$n$$), we have
$$\begin{equation} mP(X=t)=\frac m{\sqrt{npq}}\phi(x)(1+o(1))+o(m/n^{(k-1)/2}) =O\Big(\frac1{\sqrt{n}}\Big)+o\Big(\frac1{\sqrt{n}}\Big)=O\Big(\frac1{\sqrt{n}}\Big), \end{equation}$$ which is better than the $$O(1)$$ that you desired.

• No, I meant exactly as how it was written. Nov 25, 2018 at 11:56
• What I denoted by $P_k(x,1/\sqrt n)$ equals $\frac{\sqrt n}{\varphi(\xi)}\sum_{\nu=1}^{k-2}\frac{P_\nu(-\varphi(\xi))}{n^{\nu/2}}$ in Theorem 5 in Esseen's paper, with $x=\xi$, $\phi=\varphi$, and $P_\nu(-\cdot)$ defined by (4) on page 48 in that paper. To avoid confusion of my $P_k$ with Esseen's $P_\nu$, I have now replaced $P_k$ in my answer by $Q_k$. Nov 26, 2018 at 19:24
• Thanks! Two followup questions - 1) Would this result hold if $t=np+O(\sqrt{n\log m})$ instead of what was written in the question? The expression I'm having trouble generalizing is "$x≥\sqrt{2c\log n}$" since the $\sqrt{2}$ factor is not apparent when t has that form. 2) Regarding the Edgeworth expansion, $Q_k$, is it always the case that $Q_k=o(\sqrt{n})$ when $m=O(n^{c+1/2})$? This seems to be the case just by examining the leading term when $\nu=1$. Nov 27, 2018 at 17:18
• I have rewritten the answer with $t$ precisely as yours -- which is not a perfect match for just $mP(X=t)=O(1)$, though, because with that choice of $t$ you get something better: $mP(X=t)=O(1/\sqrt n)$. Nov 27, 2018 at 22:29
• If e.g. $t=np+O(1)$, then $P(X=t)$ is on the order of $1/\sqrt n$, so you will get $mP(X=t)=O(1)$ only if $m=O(n^{1/2})$, which is $<<n$, rather than $>>n$. Generally, the essence of my answers to this question is to draw your attention to Esseen's result, from which, as an independent researcher, you should be able to get complete answers to all your questions about $mP(X=t)$. Dec 2, 2018 at 16:42