# 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.)
{"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 34, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}