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

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?

• This is $\int \frac{1}{ 1- x \sum_k p(k) y^k} \frac{dy}{y}$ with the integral taken over the unit circle and expressing that integral as a sum of residues at poles in the unit disc should give algebraicity. Feb 24 at 23:18

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