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?

  • 2
    $\begingroup$ 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. $\endgroup$
    – Will Sawin
    Feb 24 at 23:18

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.