Approximating the probability that two Binomial variables are equal

Question

Let $X,Y\sim Bin(n,p)$ be independent R.V.s and let $z\in[n]$ be integer. My goal is to approximate the probability that $P[X-Y=2z]$.

What i need is a tight enough bound with error that is at most $o(\sqrt{n})$. The best bound i seen using basically CLT gives error of exactly $O(\sqrt{n})$.

The best i could think of is the following sum expansion. But i have no real idea how to proceed from there. \begin{align} P[X-Y=2z] & =\sum_{i=0}^{n} P[X=i+z, Y=i-z] \\\\ & = \sum_{i=0}^{n} P[X=i+z] P[Y=i-z] \\\\ & = \sum_{i=0}^{n} \binom{n}{i+z} p^{i+z} (1-p)^{n-i-z} \binom{n}{i-z} p^{i-z} (1-p)^{n-i+z} \\\\ & = \sum_{i=0}^{n} \binom{n}{i+z} \binom{n}{i-z} p^{2i} (1-p)^{2n-2i} \end{align}

Any ideas how to continue from here?

For clarification i want to approximate this from above and from below. By the same term, and even the same constants, but with error of at most $o(\sqrt{n})$.

Edit: $p$ can be a constant or dependent on $n$ tending to zero as $n$ tends to infinity. For constant $p=1/2$ the question is easy to answer, but what about other cases?

Answer 1

Note that $X-Y=\sum_1^n X_i$, where the $X_i$'s are i.i.d. random variables with $P(X_i=1)=(1-p)p=P(X_i=-1)$ and $P(X_i=0)=1-2(1-p)p$.

So, assuming that $0<p<1$, by the local limit theorem -- see e.g. Theorem 1 in Chapter VII, $$P(X-Y=k)=\frac1{\sigma\sqrt n}f\Big(\frac k{\sigma\sqrt n}\Big)+o\Big(\frac 1{\sqrt n}\Big)$$ as $n\to\infty$ uniformly in all integers $k$, where $f$ is the standard normal p.d.f. and $\sigma:=\sqrt{2(1-p)p}$.

Answer 2

I just thought I'd record a cute "answer". $$ \operatorname{Prob}(X-Y=k) = \frac{1}{2\pi} \int_{-\pi}^\pi \cos(k\theta)\,(2P\cos\theta+1-2P)^n\,d\theta, $$ where $P=p(1-p)$.

If $k$ is not too large compared to $nP$ (a fractional power will do), expanding the integrand around $\theta=0$ as $\exp\bigl((-Pn-k^2/2)\theta^2 + \cdots\bigr)$ gives a pretty good estimate.

Proof outline:

From Iosif's observation, we need the coefficient of $x^k$ in the expansion of $(P/x + 1-2P + Px)^n$. Write the Cauchy integral using the unit circle $x=e^{i\theta}$. Since the answer is real, we can take the real part of the integrand, which is easy since $P/x+1-2P+Px$ is already real on the unit circle.

The unit circle only hits the real axis near the saddle-point for small-ish $k$. To handle larger $k$ (such as a fraction of $nP$), a circle of larger radius works better. The perfect radius satisfies a quadratic equation.