# Asymptotic estimate of the cardinality of $H_{2n}=\{\vec{a} \in [-N,N]^{2n}:\sum_{i=1}^{2n} a_i = 0\}$

Let's suppose $$a_i \sim \mathcal{U}([-N,N])$$ where $$[-N,N] \subset \mathbb{Z}$$. We may then define:

$$$$S_n = \sum_{i=1}^n a_i \tag{1}$$$$

Now, in order to estimate $$\lvert H_{2n} \rvert$$ we may try to find an asymptotic estimate of:

$$$$P(S_{2n}=0) \tag{2}$$$$

By decomposing $$S_n$$ into positive and negative parts:

$$$$S_n = S_n^+ + S_n^- \tag{3}$$$$

where $$S_n^+$$ defines the sum of positive terms and $$S_n^-$$ defines the sum of negative terms I reasoned that the average positive and negative step length should be approximately $$\Delta = \frac{N}{2}$$ when $$n$$ is large so:

$$$$P(S_{2n}=0) \sim \frac{1}{2^{2n}} {2n \choose n} \sim \frac{1}{2^{2n}} \frac{\sqrt{4 \pi n}(\frac{2n}{e})^{2n}}{2 \pi n (\frac{n}{e})^{2n}} \sim \frac{1}{\sqrt{n}} \tag{4}$$$$

This would imply that:

$$$$\lvert H_{2n} \rvert \sim \frac{(2N+1)^{2n}}{\sqrt{n}} \tag{5}$$$$

but I must admit that my reasoning wasn't very rigorous here. Might there be a rigorous estimate of $$\lvert H_{2n} \rvert$$ using a probabilistic method?

Note: $$N$$ is assumed to be fixed in the asymptotic regime.

• Is $N$ fixed in your asymptotic regime? – Fedor Petrov Aug 28 '19 at 14:19

According to the local central limit theorem (see e.g. Esseen, Theorem 5, page 63), for any fixed natural $$N$$, $$|H_{2n}|\sim\frac{(2N+1)^{2n}}{2s\sqrt{\pi n}}$$ as $$n\to\infty$$, where $$s$$ is the standard deviation of the uniform distribution on the set $$\{-N,\dots,N\}$$.
(The definition of the condition $$(L_d)$$ used in the mentioned theorem by Esseen is given at the bottom of page 54 of Esseen's paper.)