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

\begin{equation} S_n = \sum_{i=1}^n a_i \tag{1} \end{equation}

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

\begin{equation} P(S_{2n}=0) \tag{2} \end{equation}

By decomposing $S_n$ into positive and negative parts:

\begin{equation} S_n = S_n^+ + S_n^- \tag{3} \end{equation}

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:

\begin{equation} 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} \end{equation}

This would imply that:

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

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.

  • 1
    $\begingroup$ Is $N$ fixed in your asymptotic regime? $\endgroup$ 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.)



Not the answer you're looking for? Browse other questions tagged .