Considering certain random walks I came up with the following question: Given a finite set $A$ containing positive and negative integers, how many representations of zero as the sum of $n$ integers in $A$ exist. In the case that $A$ has two elements the question is easy to answer but for set with larger cardinality the answer seems (to me) not obvious. Perhaps the question is to general, so I like to ask for which classes of sets $A$ there is closed formal or an asymptotics for the number of representations.

  • $\begingroup$ How are you counting? For $A = \{1,-1\}$ and $n=2$ is the answer 1 or 2? $\endgroup$ Aug 24, 2016 at 22:30
  • $\begingroup$ 2. Counting with order $\endgroup$ Aug 24, 2016 at 22:31
  • $\begingroup$ So it seems that random walk can help. If $\xi_i$ are iid uniformly distributed in $A$ and $X_n = \xi_1 + \dots + \xi_n$ then your number should be $|A|^n P(X_n = 0)$ for which there should be lots of reasonable estimates. In particular you should expect qualitatively different answers depending on whether the walk is mean zero, i.e. whether $\sum A = 0$ or not. $\endgroup$ Aug 24, 2016 at 22:37

1 Answer 1


This is basically covered in section VII.8.1 of Flajolet and Sedgewick's "Analytic Combinatorics". You're looking at the generating function for bridges in their terminology and the form of the generating function is given by equation (97) on page 511 and is obtained using the kernel method.


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.