Why does this random walk generating function admit an analytic continuation?

71 Views Asked by At

For $n = 0, 1, 2, \dots$, let $q_{n}:=\binom{2n}{n}^{2}\frac{1}{4^{2n}}$, so that $q_{n}$ is the probability that a simple random walk on the two-dimensional integer lattice $\mathbb{Z}^{2}$ started from the origin is at the origin after $2n$ steps. Let $Q(z)=\sum_{n=0}^{\infty}q_{n}z^{n}$ be the ordinary generating function for this sequence of probabilities.

For $n \geq 1$, let $p_{n}$ be the probability that this random walk experiences its first return to the origin after $2n$ steps. Define the generating function $P(z) = \sum_{n=1}^{\infty}p_{n}z^{n}$.

Then $P$ and $Q$ satisfy the relationship $Q(z) = \frac{1}{1-P(z)}$, equivalently $P(z) = \frac{Q(z)-1}{Q(z)}$.

In Flajolet and Sedgwick's Analytic Combinatorics Example VI.14, they establish that $Q(z)$ is analytic on a $\Delta$-region, which is an indented disc of the form

$$\Delta(\phi, R):=\{z\,:\,|z| < R,\,z\neq 1,\,|\text{arg}(z-1)|>\phi\}$$

for some $R > 1$ and $0 < \phi < \frac{\pi}{2}$. This results from recognizing $Q(z)$ as the Hadamard product $\frac{1}{\sqrt{1-z}} \odot \frac{1}{\sqrt{1-z}}$ (with $\frac{1}{\sqrt{1-z}}$ generating the sequence $\binom{2n}{n}\frac{1}{2^{2n}}$) and using a general theorem.

They claim that $P(z)$ is analytic on a $\Delta$-region as well, which is the source of my confusion. Their argument goes: if $P(z)$ is not continuable to a $\Delta$-region, then

there would be complex poles arising from zeros of the function $Q$ on the unit disc, and this would entail in $p_{n}$ the presence of terms oscillating around $0$, a fact that contradicts the necessary positivity of probabilities.

It is clear to me that if $Q(z)$ has no zeros on the closed unit disc (excluding $z = 1$), then $P(z)$ can be extended to an analytic function on some $\Delta$-region. But I don't see why the positivity of the coefficients of $P(z)$ enforces this. It is easy to come up with generating functions with strictly positive coefficients which have complex poles: for instance, $F(z) = \frac{1}{(1-z^{3})(1-z)}$ obviously satisfies this.

Why is the reasoning in Flajolet and Sedgwick correct?