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$ – 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.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.