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$
$\endgroup$
3
asked Aug 24, 2016 at 22:08
-
$\begingroup$ How are you counting? For $A = \{1,-1\}$ and $n=2$ is the answer 1 or 2? $\endgroup$– Nate EldredgeCommented Aug 24, 2016 at 22:30
-
$\begingroup$ 2. Counting with order $\endgroup$– Jörg NeunhäusererCommented 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$– Nate EldredgeCommented Aug 24, 2016 at 22:37
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
0
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.
