The probability that iid draws from a mean zero random variable sum to zero

Question

Suppose we have a probability distribution $p(\cdot)$ supported on the integers between $-m$ and $m$ for some positive integer $m$, with $\sum_k kp(k) = 0$. Suppose furthermore that all $p(k)$ are rational. Let $q_n$ (for $n \geq 0$) be the probability that $X_1 + \dots + X_n = 0$ where $X_1,\dots,X_n$ are iid draws from $p(\cdot)$ (so $q_0 = 1$ trivially).

Example: $m=1$, $p(1)=p(-1)=1/2$, $p(0)=0$. Then $q_n$ equals 0 for $n$ odd and equals ${n \choose n/2} 2^{-n}$ for $n$ even.

Question: Must the generating function $\sum_{n=0}^{\infty} q_n x^n$ be algebraic? $D$-finite?

Answer 1

I guess I can convert my comment to an answer.

Recall that for a bivariate power series $F(x,y) = \sum_{i,j \geq 0} f(i,j) x^i y^j$, its diagonal is the univariate power series $\operatorname{diag} F(x,y) = \sum_{n \geq 0} f(n,n) x^{n}$. In other words, we extract the coefficients of $x^ny^n$ and make them into a new power series.

Since your $q_n$ is the coefficient of $x^0$ in $(\sum_{k=-m}^{m} p(k) x^k)^n$, it follows that your generating function $\sum_{n \geq 0} q_n x^n = \operatorname{diag} F(x,y)$ where $F(x,y) = 1/(1-(xy\sum_{k=-m}^{m}p(k) x^k)$).

Now, it is well known that if $F(x,y)$ is rational, then $\operatorname{diag} F(x,y)$ is algebraic: see for example Theorem 6.3.3 of Stanley's EC 2. Since the above $F(x,y)$ is clearly rational, it follows that your $\sum_{n \geq 0} q_n x^n$ is algebraic. And notice that we never used the fact that the mean of your random variable is zero, or that the $p(k)$ are rational.

(In fact, there is a very strong connection between diagonals of bivariate rational generating functions and contour integrals - see the relevant section of Stanley - so this approach ends up being more-or-less the same as Will Sawin's.)