The following result relates the differential transcendence of $Q(x, y; t)$ and the differential transcendence of $r_x(\omega; t)$ and $r_y(\omega; t)$.

**Proposition 3.14.** The following statements are equivalent.

* The generating function $Q(x, y; t)$ is differentially algebraic in its three variables.

* The series $F_1(x; t)$ and $F_2(y; t)$ are differentially algebraic in their two variables.

* The meromorphic continuations $r_x(\omega; t)$ and $r_y(\omega; t)$ are differentially algebraic in their two variables.

*Proof.* If $Q(x, y; t)$ is differentially algebraic then $Q(x, 0; t)$ is differentially algebraic. Since $K(x, 0; t)$ is differentially algebraic, we use the ring property of Lemma 3.2 to deduce that $F_1(x; t) = K(x, 0; t)Q(x, 0; t)$ is differentially algebraic. (The reasoning is similar for the differential algebraicity of $F_2(y; t)$). Conversely, if $F_1(x; t)$ and $F_2(y; t)$ are differentially algebraic, then, by evaluation, so is $Q(0, 0; t)$. As the right-hand side of the expression in Lemma 2.1 is a sum and product of elements that are differentially algebraic, it is differentially algebraic (by the field property in Lemma 3.2). Therefore, $K(x, y; t)Q(x, y; t)$ is differentially algebraic. Thus, $Q(x, y; t)$ is differentially algebraic. So the first two points are equivalent.

Assume that the series $F_1(x; t)$ is differentially algebraic in its two variables. Recall that $F_1(x(\omega; t); t) = r_x(\omega; t)$ where $x(\omega; t)$ is differentially algebraic; see Corollary 3.8. By composition of differentially algebraic functions, see Lemma 3.2, $r_x(\omega; t)$ is differentially algebraic. Conversely, on a domain where $x(\omega; t)$ is invertible, its inverse is also differentially algebraic; see Lemma 3.2. We conclude similarly that if $r_x(\omega; t)$ is differentially algebraic then $F_1(x; t)$ is differentially algebraic. A similar reasoning holds for the $y$ variable and we find that $F_2(y; t)$ is differentially algebraic if and only if $r_y(\omega; t)$ is differentially algebraic. This proves the equivalence between the last two points. $\square$

# 4. DIFFERENTIAL ALGEBRAICITY OF THE GENERATING FUNCTION

The goal of this section is to prove Theorem 1.1 (the $\partial_x$, $\partial_y$, and $\partial_t$ differential algebraicity are equivalent). By Lemma 2.4, the result holds for all degenerate cases. By Lemma 2.6 and Proposition 2.5, it also holds when $\bar{E}_t$ is not an elliptic curve. So we now prove the case where $\bar{E}_t$ is an elliptic curve. Let $G$ be the group of the walk (see Definition 2.7). Our proof handles separately the cases $|G| < \infty$ and $|G| = \infty$.

## 4.1. Finite group case.

**Proposition 4.1.** Let us consider a nondegenerate model of walks, assume that $\bar{E}_t$ is an elliptic curve and $|G| < \infty$. Then, $Q(x, y; t)$ is $\partial_x$-algebraic, $\partial_y$-algebraic and $\partial_t$-algebraic.

*Proof.* By Proposition 3.14, it suffices to show that $r_x(\omega; t)$ and $r_y(\omega; t)$ are differentially algebraic in their two variables. Let us only consider $r_x(\omega; t)$, the proof for $r_y(\omega; t)$ is similar. Recall that the $\omega_i(t)$ are continuous and that $\omega_3(t) \in (0, \omega_2(t))$ (see Equation (2.2)). Since $|G| < \infty$ and $\tilde{\sigma}(\omega) = \omega + \omega_3(t)$, there exist $k, \ell \in \mathbb{N}^*$ with $\gcd(k, \ell) = 1$ such that $\omega_3(t)/\omega_2(t) = k/\ell$. By (2.4), we have $r_x(\omega + \omega_3(t); t) = r_x(\omega; t) + b_x(\omega; t)$, where $b_x(\omega; t) = y(-\omega; t)(x(\omega; t) - x(\omega + \omega_3(t); t))$. Let us recall some notations borrowed from the proof of [11, Theorem 4.1]. It is shown that we may write a decomposition of the form

$$r_x(\omega; t) = \psi(\omega; t) + \Phi(\omega; t)\phi(\omega; t). \quad (4.1)$$
More precisely,

• $\Phi(\omega; t) = \sum_{i=0}^{\ell-1} b_x(\omega + i\omega_3(t); t);$

• $\phi(\omega; t) = \frac{\omega_1(t)}{2i\pi} \zeta(\omega; t) - \frac{\omega}{i\pi} \zeta(\omega_1(t)/2; t)$, where $\zeta$ is an opposite of the antiderivative of the Weierstrass function with periods $\omega_1(t)$ and $k\omega_2(t)$, that is

$$ \zeta(\omega; t) = \frac{1}{\omega} + \sum_{(\ell_1, \ell_2) \in \mathbb{Z}^2 \setminus \{(0,0)\}} \left( \frac{1}{\omega + \ell_1 \omega_1(t) + \ell_2 k \omega_2(t)} - \frac{1}{\ell_1 \omega_1(t) + \ell_2 k \omega_2(t)} + \frac{\omega}{(\ell_1 \omega_1(t) + \ell_2 k \omega_2(t))^2} \right); $$

• for all $t \in (0, 1)$, the function $\omega \mapsto \psi(\omega; t)$ is $(\omega_1(t), k\omega_2(t))$-periodic.

The idea is to prove successively that $\Phi(\omega; t)$, $\phi(\omega; t)$ and $\psi(\omega; t)$ are differentially algebraic. We will also see them as functions of $\omega$ and study their poles and principal parts.

**Step 1: Study of $\Phi(\omega; t)$**.

**Lemma 4.2.** *The following holds:*

• There are countably many elements of $\mathfrak{D}$, whose union forms the set of poles of $\omega \mapsto \Phi(\omega; t)$.

• The coefficients of the principal parts of $\omega \mapsto \Phi(\omega; t)$ are in $\mathfrak{D}$.

• $\Phi$ is differentially algebraic in its two variables.

*Proof.* Recall, see Lemma 3.3, that $\omega_3(t) \in \mathfrak{D}$. We may combine Corollary 3.9 and Lemma 3.2, to deduce that the poles and the coefficients of the principal parts of $\omega \mapsto \Phi(\omega; t)$ are $\partial_t$-algebraic. Furthermore by Lemma 3.2 and Proposition 3.4, $\Phi$ is differentially algebraic in its two variables. $\square$

**Step 2: Study of $\phi(\omega; t)$**.

Before proving that $\phi(\omega; t)$ is differentially algebraic, let us study $\zeta(\omega; t)$.

**Lemma 4.3.** *The following holds:*

• There are countably many elements of $\mathfrak{D}$, whose union forms the set of poles of $\omega \mapsto \zeta(\omega; t)$.

• The coefficients of the principal parts of $\omega \mapsto \zeta(\omega; t)$ are in $\mathfrak{D}$.

• $\zeta$ is differentially algebraic in its two variables.

*Proof.* In virtue of Lemma 3.3, the periods $\omega_1(t), \omega_2(t)$ are differentially algebraic. Then, the poles and the coefficients of the principal parts of $\omega \mapsto \zeta(\omega; t)$ belong to $\mathfrak{D}$.

Let $\tilde{\rho}$ be the Weierstrass function with periods $\omega_1(t), k\omega_2(t)$ and let us write the classical differential equation

$$ \partial_{\omega} \tilde{\rho}(\omega; t)^2 = 4 \tilde{\rho}(\omega; t)^3 - \tilde{g}_2(t) \tilde{\rho}(\omega; t) - \tilde{g}_3(t). \quad (4.2) $$

By Remark 3.5, $\tilde{\rho}(\omega; t) = -\partial_{\omega}\zeta(\omega; t)$ is differentially algebraic in its two variables. Then, $\zeta(\omega; t)$ is $\partial_{\omega}$-algebraic too. Let us prove the $\partial_t$-algebraicity. Let us differentiate (4.2) with respect to $\partial_{\omega}$ and simplify by $\partial_{\omega}\tilde{\rho}(\omega; t)$, to find

$$ 2\partial_{\omega}^2 \tilde{\rho}(\omega; t) = 12\tilde{\rho}(\omega; t)^2 - \tilde{g}_2(t). $$
By Lemma 3.2, for all $k \ge 0$, the derivatives $\partial_{\omega}^k \tilde{\phi}(\omega; t)$ are $\partial_t$-algebraic. Since the $\partial_t$-algebraic functions form a ring, see Lemma 3.2, we deduce that $\tilde{g}_2(t)$ is $\partial_t$-algebraic. Using again the ring property of Lemma 3.2 in (4.2), we deduce that $\tilde{g}_3(t)$ is $\partial_t$-algebraic too. We may see the elliptic functions as functions of $\omega$ and $\tilde{g}_2, \tilde{g}_3$. By [1, (18.6.19)],

$$ (\tilde{g}_2^3 - 27\tilde{g}_3^2)\partial_{\tilde{g}_3} \tilde{\phi} = (3\tilde{g}_2\zeta - \frac{9}{2}\tilde{g}_3\omega)\partial_{\omega} \tilde{\phi} + 6\tilde{g}_2^2 \tilde{\phi}^2 - 9\tilde{g}_3\tilde{\phi} - \tilde{g}_2^2. \quad (4.3) $$

We have $\partial_t \tilde{\phi} = \partial_t \tilde{g}_3 \partial_{\tilde{g}_3} \tilde{\phi}$. If $\partial_t \tilde{g}_3 = 0$ then $\tilde{\phi}$ does not depend on $t$. In particular, its poles are independent of $t$, which implies that the periods $\omega_1(t)$ and $k\omega_2(t)$ are independent of $t$. Then, $\zeta(\omega; t)$ is independent of $t$ and therefore $\partial_t$-algebraic. We similarly deal with the case $\partial_t \tilde{g}_2 = 0$. So let us consider the situation where both functions $\partial_t \tilde{g}_2$ and $\partial_t \tilde{g}_3$ are not identically zero. By the derivation property of Lemma 3.2, we deduce that $\partial_t \tilde{\phi}, \partial_t \tilde{g}_3$ are $\partial_t$-algebraic. Since the $\partial_t$-algebraic functions form a field, see Lemma 3.2, we then find that $\partial_{\tilde{g}_3} \tilde{\phi} = \partial_t \tilde{\phi} / \partial_t \tilde{g}_3$ is $\partial_t$-algebraic. Since $\partial_t \tilde{g}_2 \ne 0$, we are in the situation where $\tilde{g}_2$ is not identically zero. With (4.3), and the field property of Lemma 3.2, we deduce that $\zeta(\omega; t)$ is $\partial_t$-algebraic. This completes the proof of the lemma. $\square$

**Lemma 4.4.** *The following holds:*

* There are countably many elements of $\mathfrak{D}$, whose union forms the set of poles of $\omega \mapsto \phi(\omega; t)$.

* The coefficients of the principal parts of $\omega \mapsto \phi(\omega; t)$ are in $\mathfrak{D}$.

* $\phi$ is differentially algebraic in its two variables.

*Proof.* In virtue of Lemma 3.3, the period $\omega_1(t)$ is differentially algebraic. By Lemma 3.2, and Lemma 4.3, we find that $\phi(\omega; t)$ is differentially algebraic in its two variables. Furthermore, the poles and the coefficients of the principal parts of $\omega \mapsto \phi(\omega; t)$ belong to $\mathfrak{D}$. $\square$

**Step 3: Study of $\psi(\omega; t)$**

Let us now study $\psi(\omega; t)$. By Lemma 3.13 there exists $a(t) \in \mathfrak{D}$ such that $r_x(a(t); t) \in \mathfrak{D}$. Furthermore, the poles and the coefficients of the principal parts of $\omega \mapsto r_x(\omega; t)$ are $\partial_t$-algebraic.

With (4.1), Lemma 4.2 and Lemma 4.4, we deduce that the poles of $\omega \mapsto \psi(\omega; t)$ are $\partial_t$-algebraic, and the coefficients of the principal parts are $\partial_t$-algebraic. Recall that for all $t$, $\omega \mapsto \psi(\omega; t)$ is $(\omega_1(t), k\omega_2(t))$-periodic. By Remark 3.12, we may build $\omega \mapsto \psi_0(\omega; t)$, that is differentially algebraic and $(\omega_1(t), k\omega_2(t))$-periodic, with same principal parts as $\omega \mapsto \psi(\omega; t)$. We have

$$ r_x(\omega; t) = \psi(\omega; t) - \psi_0(\omega; t) + \Phi(\omega; t)\phi(\omega; t) + \psi_0(\omega; t). \quad (4.4) $$

Note that by construction $\omega \mapsto \psi(\omega; t) - \psi_0(\omega; t)$ has no poles. Since $\omega \mapsto r_x(\omega; t)$ has no poles at $a(t)$, we deduce with (4.4), that $\omega \mapsto \Phi(\omega; t)\phi(\omega; t) + \psi_0(\omega; t)$ has no poles at $a(t)$. Since $\Phi(\omega; t)\phi(\omega; t) + \psi_0(\omega; t)$ is differentially algebraic (as the sum of two differentially algebraic functions, see Lemma 3.2), with no poles at $a(t)$, we find that its evaluation at $a(t)$ is differentially algebraic. Since $r_x(a(t); t) \in \mathfrak{D}$ we use the ring property in Lemma 3.2 to deduce that $\psi(a(t); t) - \psi_0(a(t); t)$ is differentially algebraic.
Then, $\psi(\omega; t) - \psi_0(\omega; t)$ satisfies the assumptions of Theorem 3.10 (with $\omega_2(t)$ replaced by $k\omega_2(t)$) and we deduce that it is differentially algebraic by Remark 3.12. By Lemma 3.2, and the differential algebraicity of $\psi_0(\omega; t)$, we deduce that $\psi(\omega; t)$ is differentially algebraic.

**Step 4: Study of $r_x(\omega; t)$**.

Let us now finish the proof of Proposition 4.1. Since $\psi(\omega; t)$, $\Phi(\omega; t)$, and $\phi(\omega; t)$ are differentially algebraic in their two variables, we conclude that $r_x(\omega; t) = \psi(\omega; t) + \Phi(\omega; t)\phi(\omega; t)$ is differentially algebraic as the sum and product of differentially algebraic functions; see Lemma 3.2. $\square$

**4.2. Infinite group case.** It now remains to handle the case where the group has infinite order. So let us consider a nondegenerate model of walks and assume that $\bar{E}_t$ is an elliptic curve and $|G| = \infty$. The equivalence between the $\partial_x$-algebraicity and the $\partial_y$-algebraicity can be straightforwardly deduced in this weighted context from the proof of [8, Proposition 3.10]. Let us see that the $\partial_t$-algebraicity implies the $\partial_x$-algebraicity. If $Q(x, y; t)$ is $\partial_t$-algebraic, then $Q(x, 0; t)$ is $\partial_t$-algebraic. By [7, Theorem 3.12], if $Q(x, 0; t)$ is $\partial_t$-algebraic, then it is $\partial_x$-algebraic. In virtue of Lemmas 2.1 and 3.2, we find that if $Q(x, 0; t)$ is $\partial_x$-algebraic, then $Q(x, y; t)$ is $\partial_x$-algebraic. So to prove Theorem 1.1, it now suffices to show the following result.

**Theorem 4.5.** Let us consider a nondegenerate model of walks, assume that $\bar{E}_t$ is an elliptic curve and $|G| = \infty$. If $Q(x, y; t)$ is $\partial_x$-algebraic, then it is $\partial_t$-algebraic.

*Proof.* By Proposition 3.14, it suffices to show that $r_x(\omega; t)$ and $r_y(\omega; t)$ are differentially algebraic. Let us consider $r_x(\omega; t)$, the proof for $r_y(\omega; t)$ is similar. By Proposition 2.5, for all $t \in (0, 1)$ fixed, $\bar{E}_t$ is an elliptic curve. Let $G_t$ be the group $G$ specialized at $t$. The order of the group $G_t$ may depend upon $t$. However by [8, Proposition 2.6], see also [19, Proposition 14], which can be straightforwardly extended in the weighted framework, the set of $t \in (0, 1)$ such that $G_t$ has infinite order is dense. By assumption, for such $t$ fixed, $x \mapsto F_1(x; t)$ is $\partial_x$-algebraic. By [16, Theorem 3.8], for all such $t$ fixed there exists a $(\omega_1(t), \omega_2(t))$-periodic function $\tilde{g}(\omega; t)$, such that

$$b_x(\omega; t) = \tilde{g}(\omega + \omega_3(t); t) - \tilde{g}(\omega; t). \qquad (4.5)$$

By [16, Proposition 3.9], there exist $g(x; t) \in \mathbb{C}(x, t)$ and $h(y; t) \in \mathbb{C}(y, t)$ such that $g(x(\omega; t); t) = \tilde{g}(\omega; t)$ and for all $(x, y) \in \bar{E}_t$,

$$xy = g(x; t) + h(y; t).$$

Since $g(x(\omega; t); t) = \tilde{g}(\omega; t)$, we use Corollary 3.8 to deduce that we may continue $\tilde{g}(\omega; t)$ in the $t$ variable.

**Step 1: Study of $\tilde{g}(\omega; t)$**.

**Lemma 4.6.** The following holds:

* There are countably many elements of $\mathfrak{D}$, whose union forms the set of poles of $\omega \mapsto \tilde{g}(\omega; t)$.

* The coefficients of the principal parts of $\omega \mapsto \tilde{g}(\omega; t)$ are in $\mathfrak{D}$.

* $\tilde{g}$ is differentially algebraic in its two variables.
Proof. We claim that the poles of $\omega \mapsto \tilde{g}(\omega; t)$ are of the form $\omega_0(t) + \ell\omega_3(t)$, where $\omega_0(t)$ is a pole of $\omega \mapsto b_x(\omega; t)$ and $\ell \in \mathbb{Z}$. To the contrary, assume that $a(t)$ is a pole that is not of this form. Then $a(t) - \omega_3(t)$ is a pole of $\omega \mapsto \tilde{g}(\omega + \omega_3(t); t)$, that is not a pole of $\omega \mapsto b_x(\omega; t)$. With (4.5), we find that $a(t) - \omega_3(t)$ is a pole of $\omega \mapsto \tilde{g}(\omega; t)$. We prove successively that for all $\ell \ge 0$, $a(t) - \ell\omega_3(t)$ is a pole of $\omega \mapsto \tilde{g}(\omega; t)$. Since $\tilde{g}(\omega; t)$ is $(\omega_1(t), \omega_2(t))$-periodic, $a(t) - \omega_3(t)\mathbb{N} + \omega_1(t)\mathbb{Z} + \omega_2(t)\mathbb{Z}$ are poles of $\omega \mapsto \tilde{g}(\omega; t)$. Since $|G| = \infty$ and $\tilde{\sigma}(\omega) = \omega + \omega_3(t)$, the sets $A_\ell := \{a(t) - \ell\omega_3(t) + \omega_1(t)\mathbb{Z} + \omega_2(t)\mathbb{Z}\}$, with $\ell \in \mathbb{N}$, are disjoint. Then, the set of poles of $\omega \mapsto \tilde{g}(\omega; t)$ possesses an accumulation point which contradicts that the function is meromorphic. This proves the claim.

By Corollary 3.9, the poles of $\omega \mapsto b_x(\omega; t)$ are $\partial_t$-algebraic. By Lemma 3.3, $\omega_3(t)$ is $\partial_t$-algebraic too. With the claim, it follows that the poles of $\omega \mapsto \tilde{g}(\omega; t)$ are $\partial_t$-algebraic. By Corollary 3.8, the coefficients of the principal parts of $\omega \mapsto x(\omega; t)$ are $\partial_t$-algebraic. With $g(x(\omega; t); t) = \tilde{g}(\omega; t)$, and $g(x; t) \in \mathbb{C}(x, t)$, we deduce that the coefficients of the principal parts of $\omega \mapsto \tilde{g}(\omega; t)$ are $\partial_t$-algebraic. Finally $\tilde{g}(\omega; t)$ is differentially algebraic, as the composition of differentially algebraic functions; see Lemma 3.2. $\square$

Step 2: Study of $\tilde{f}(\omega; t) := r_x(\omega; t) - \tilde{g}(\omega; t)$.

By (2.4) and (4.5), we find

$$ \begin{aligned} \tilde{f}(\omega + \omega_3(t); t) &= r_x(\omega + \omega_3(t); t) - \tilde{g}(\omega + \omega_3(t); t) \\ &= r_x(\omega; t) + b_x(\omega; t) - (\tilde{g}(\omega; t) + b_x(\omega; t)) = \tilde{f}(\omega; t). \end{aligned} $$

Then, $\tilde{f}(\omega; t)$ is $\omega_3(t)$-periodic. Recall that $\tilde{g}(\omega; t)$ is $\omega_1(t)$-periodic. By (2.5), $r_x(\omega; t)$ is also $\omega_1(t)$-periodic. Therefore, $\omega \mapsto \tilde{f}(\omega; t)$ is elliptic with periods $(\omega_1(t), \omega_3(t))$. Recall that the poles and the coefficients of the principal parts of $\omega \mapsto \tilde{g}(\omega; t)$ are $\partial_t$-algebraic. By Lemma 3.13, the same holds for $r_x(\omega; t)$ and there exists $a(t) \in \mathfrak{D}$ such that $r_x(a(t); t)$ is differentially algebraic. By Remark 3.12, we may build $\omega \mapsto \tilde{f}_0(\omega; t)$, that is differentially algebraic, $(\omega_1(t), \omega_3(t))$-periodic, and with same principal parts as $\omega \mapsto \tilde{f}(\omega; t)$. Let us write

$$ \tilde{f}(\omega; t) - \tilde{f}_0(\omega; t) = r_x(\omega; t) - \tilde{g}(\omega; t) - \tilde{f}_0(\omega; t). $$

The function $-\tilde{g}(\omega; t) - \tilde{f}_0(\omega; t)$ is differentially algebraic, as the sum of two differentially algebraic functions; see Lemma 3.2. Since $\tilde{f}(\omega; t) - \tilde{f}_0(\omega; t)$ has no poles and $a(t)$ is not a pole of $\omega \mapsto r_x(\omega; t)$, we deduce that $a(t)$ is not a pole of $\omega \mapsto -\tilde{g}(\omega; t) - \tilde{f}_0(\omega; t)$. Therefore, its evaluation at $a(t)$ is still differentially algebraic. Then, the same holds for $\omega \mapsto \tilde{f}(\omega; t) - \tilde{f}_0(\omega; t)$, which satisfies the assumptions of Theorem 3.10 (with $\omega_2(t)$ replaced with $\omega_3(t)$) and we deduce that it is differentially algebraic by Remark 3.12. Hence, $r_x(\omega; t) = (\tilde{f}(\omega; t) - \tilde{f}_0(\omega; t)) + \tilde{g}(\omega; t) + \tilde{f}_0(\omega; t)$ is differentially algebraic as the sum of differentially algebraic functions, see Lemma 3.2. This concludes the proof. $\square$

**Acknowledgments.** This project has received funding from the ANR de rerum natura ANR-19-CE40-0018.
REFERENCES

[1] Milton Abramowitz, Irene A. Stegun, and Robert H. Romer. *Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables*. National Bureau of Standards, 10th edition, 1972.

[2] Olivier Bernardi, Mireille Bousquet-Mélou, and Kilian Raschel. Counting quadrant walks via Tutte's invariant method. *Combinatorial Theory*, 1(3):1-77, 2021.

[3] Alin Bostan and Manuel Kauers. The complete generating function for Gessel walks is algebraic. *Proceedings of the American Mathematical Society*, 138(9):3063-3078, 2010.

[4] Mireille Bousquet-Mélou and Marni Mishna. Walks with small steps in the quarter plane. In *Algebraic probability and combinatorics*, volume 520 of *Contemp. Math.*, pages 1-39. Amer. Math. Soc., 2010.

[5] Mireille Bousquet-Mélou and Marko Petkovšek. Walks confined in a quadrant are not always d-finite. *Theoretical Computer Science*, 307(2):257-276, 2003.

[6] Denis Denisov and Vitali Wachtel. Random walks in cones. *Annals of Probability*, 43(3):992-1044, 2015.

[7] Thomas Dreyfus and Charlotte Hardouin. Length derivative of the generating series of walks confined in the quarter plane. *Confluentes Mathematici*, 13(2):39-92, 2021.

[8] Thomas Dreyfus, Charlotte Hardouin, Julien Roques, and Michael F. Singer. On the nature of the generating series of walks in the quarter plane. *Inventiones mathematicae*, pages 139-203, 2018.

[9] Thomas Dreyfus, Charlotte Hardouin, Julien Roques, and Michael F. Singer. Walks in the quarter plane: Genus zero case. *Journal of Combinatorial Theory, Series A*, 174(105251):1-25, 2020.

[10] Thomas Dreyfus, Charlotte Hardouin, Julien Roques, and Michael F. Singer. On the kernel curves associated with walks in the quarter plane. In *Transcendence in Algebra, Combinatorics, Geometry and Number Theory*, pages 61-89. Springer Proceedings in Mathematics and Statistics, 2021.

[11] Thomas Dreyfus and Kilian Raschel. Differential transcendence & algebraicity criteria for the series counting weighted quadrant walks. *Publications Mathématiques de Besançon*, 1:41-80, 2019.

[12] Thomas Dreyfus and Amélie Trotignon. On the nature of four models of symmetric walks avoiding a quadrant. *Annals of Combinatorics*, pages 1-28, 2021.

[13] Johannes Jisse Duistermaat. *Discrete Integrable Systems: QRT Maps and Elliptic Surfaces*, volume 304 of Springer Monographs in Mathematics. Springer, 2010.

[14] Guy Fayolle, Roudolf Iasnogorodski, and Vadim Malyshev. *Random walks in the quarter plane*. Springer, second edition, 2017.

[15] Guy Fayolle and Kilian Raschel. Random walks in the quarter-plane with zero drift: an explicit criterion for the finiteness of the associated group. *Markov Processes and Related Fields*, 17(4):619-636, 2011.

[16] Charlotte Hardouin and Michael F. Singer. On differentially algebraic generating series for walks in the quarter plane. *Selecta Mathematica*, 27(5):1-49, 2021.

[17] Manuel Kauers and Rika Yatchak. Walks in the quarter plane with multiple steps. In *Proceedings of FPSAC 2015*, Discrete Mathematics and Theoretical Computer Science Proceedings, pages 25-36, 2015.

[18] Ellis Robert Kolchin. *Differential algebra and algebraic groups*. Academic Press, 1973.

[19] Irina Kurkova and Kilian Raschel. On the functions counting walks with small steps in the quarter plane. *Publications mathématiques de l'IHÉS*, 116(1):69-114, 2012.

[20] Stephen Melczer and Marni Mishna. Singularity analysis via the iterated kernel method. *Combinatorics, Probability and Computing*, 23(5):861-888, 2014.

[21] Marni Mishna and Andrew Rechnitzer. Two non-holonomic lattice walks in the quarter plane. *Theoretical Computer Science*, 410(38-40):3616-3630, 2009.

[22] Kilian Raschel. Counting walks in a quadrant: a unified approach via boundary value problems. *Journal of the European Mathematical Society*, 14(3):749-777, 2012.

[23] Elias M. Stein and Rami Shakarchi. *Complex Analysis*. Princeton University Press, 2010.
# THE GENERATING FUNCTION OF THE SURVIVAL PROBABILITIES IN A CONE IS NOT RATIONAL

RODOLPHE GARBIT<fnref n="1" /> ID AND KILIAN RASCHEL<fnref n="2" /> ID

**Abstract.** We look at multidimensional random walks $(S_n)_{n \ge 0}$ in convex cones, and address the question of whether two naturally associated generating functions may define rational functions. The first series is the one of the survival probabilities $P(\tau > n)$, where $\tau$ is the first exit time from a given cone; the second series is that of the excursion probabilities $P(\tau > n, S_n = y)$. Our motivation to consider this question is twofold: first, it goes along with a global effort of the combinatorial community to classify the algebraic nature of the series counting random walks in cones; second, rationality questions of the generating functions are strongly associated with the asymptotic behaviors of the above probabilities, which have their own interest. Using well-known relations between rationality of a series and possible asymptotics of its coefficients, recent probabilistic estimates immediately imply that the excursion generating function is not rational. Regarding the survival probabilities generating function, we propose a short and self-contained proof that it cannot be rational neither.

**Keywords:** random walks in cones, survival probabilities, generating functions, rational functions, Laplace transform, univariate singularity analysis.

## 1. INTRODUCTION

**Main result and our approach.** For a $d$-dimensional random walk $(S_n)_{n \ge 0}$ with integrable and independent increments $X_n = S_n - S_{n-1}$ having common distribution $\mu$, we consider the generating function

$$F(t) = \sum_{n \ge 0} a_n t^n = \sum_{n \ge 0} \mathbb{P}^x(\tau > n) t^n, \qquad (1.1)$$

where $\mathbb{P}^x$ is a probability distribution under which the random walk starts at $S_0 = x$, and $\tau$ denotes the first exit time from a given cone $K$, i.e.,

$$\tau = \inf\{n > 0 : S_n \notin K\}.$$

See (1.7) for an explicit computation of (1.1) in a simple one-dimensional example. Our first main result can be stated as follows:

**Theorem 1.1.** If the drift $m = \mathbb{E}X_1$ is not interior to the cone $K$, and if four further assumptions (A1)-(A4) (to be introduced below) are satisfied, then the generating function $F(t)$ in (1.1) is not a rational function.

<footnote n="1">¹UNIVERSITÉ D'ANGERS, FRANCE; https://www.math.univ-angers.fr/~garbit/</footnote>

<footnote n="2">²CNRS, UNIVERSITÉ D'ANGERS, FRANCE; http://www.lmpt.univ-tours.fr/~raschel/</footnote>
Let us emphasize that in Theorem 1.1, the distribution of $X_1$ is not assumed to be a discrete measure. This theorem covers, amongst other cases, the class of walks with small steps in orthants (with arbitrary weights on the steps), a model that has attracted a lot of attention from the combinatorial community, but is much more general.

The non-rationality of the generating function (1.1) is based on the fact that the numbers $a_n$ don't have an asymptotic behavior that is compatible with the Taylor coefficients of a rational function. More precisely, we identify in Theorem 1.3 a rate $\rho \in (0, 1]$ such that

$$a_n = \rho^n B_n, \qquad (1.2)$$

with $B_n$ satisfying

$$(i) \sqrt[n]{B_n} \to 1,$$

$$(ii) B_n \to 0.$$

Using then classical analytic combinatorics techniques (see in particular Theorem 4.1 and Lemma 4.2), one will directly deduce that the generating function (1.1) cannot be rational.

In this paper, we provide proofs of estimates (i) and (ii) which are self-contained, and as simple and elementary as possible. Only item (ii) is new. Item (i) (in particular the value of the rate $\rho$ in (1.2)) is already obtained in [11], but for the reader's convenience, we shall give here a detailed proof in a simplified setting, that covers the cases which are relevant to combinatorialists. In a special case (when the drift is, in some sense, directed towards the vertex of the cone), the precise asymptotics of the survival probability (hence in particular items (i) and (ii)) is derived in [8].

**Drift inside of the cone.** In case of a drift $m = \mathbb{E}X_1$ interior to the cone, the probabilistic behavior is rather constrained as we have $\mathbb{P}^x(\tau > n) \to \mathbb{P}^x(\tau = \infty) > 0$. The positivity of the escape probability is intuitively clear, based on the law of large numbers and the fluctuations of the random walk; see Lemma 3.1 for a precise statement. Equivalently, in the neighborhood of $t = 1$, one has

$$F(t) \sim \frac{\mathbb{P}^x(\tau = \infty)}{1-t},$$

which contains no contradiction with $F$ being a rational function. However, for one-dimensional walks with bounded jumps, it is proved in [1, Thm 4] that $\mathbb{P}^x(\tau > n) = \mathbb{P}^x(\tau = \infty) + \frac{c\rho^n}{n^{3/2}} + \dots$, with $\rho \in (0, 1)$, which is not compatible with $F$ being rational.

One of the simplest examples for which the rationality of $F$ in (1.1) was an open question before the present paper is the following: in the quarter plane $K = \mathbb{N}^2$, take a uniform distribution $\mu$ on $\{(1,0), (0,-1), (-1,0), (0,1), (1,1)\}$. Here, we answer this question and, more generally, solve the problem for the orthant $K = [0, \infty)^d$ and any (weighted) small step walk, i.e., random walk with increments $X_k$ that belong to $\{-1, 0, 1\}^d$ almost surely. If $\mathbb{P}(X_k \in K) = 1$, then the random walk is trapped forever in $K$ and $a_n = \mathbb{P}^x(\tau > n) = 1$ for all $n$, so that $F(t) = \frac{1}{1-t}$ is a rational function. Let us say the walk is not trapped if $\mathbb{P}(X_k \notin K) > 0$. Our second main result is the following:

**Theorem 1.2.** For all $d$-dimensional weighted small step walks with a drift interior to the orthant $K = [0, \infty)^d$, not trapped and satisfying (A2), the generating function $F(t)$ in (1.1) is not rational.
Here again, the non-rationality of the generating $F(t)$ is obtained as a consequence of estimates on $a_n = \mathbb{P}^x(\tau > n)$. More precisely, in Theorem 1.4, we prove that

$$ \mathbb{P}^x(\tau > n) = \mathbb{P}^x(\tau = \infty) + \Theta(\rho^n B_n), \qquad (1.3) $$

where $\rho \in (0, 1)$ and $B_n$ satisfies $\sqrt[n]{B_n} \to 1$ and $B_n \to 0$, and the notation $f_n = \Theta(g_n)$ means that there exist constants $0 < c < C$ such that $cg_n \le f_n \le Cg_n$.

We could have unified the presentation of the interior and non-interior drift estimates, since $\mathbb{P}^x(\tau = \infty) = 0$ when the drift is not in $K^o$. However, we choose not to do so, because the last double-sided estimate (1.3) is obtained only in the small step walk setting. We leave open the general case of this interesting interior drift problem.

In the papers [12, 13] (see also [7]), the authors prove the non-rationality of $F(t)$, for certain models of singular walks in the quarter plane, by proving that $F(t)$ admits infinitely many poles.

**Combinatorial motivations.** Up to a scaling of the $t$-variable, our framework is equivalent to a more combinatorial question, related to the enumeration of walks. More precisely, in case $\mu$ is a uniform distribution on a finite set $S$ (with cardinality $|S|$), one has

$$ F(|S|t) = \sum_{n \ge 0} q_n t^n, $$

where $q_n$ denotes the number of walks starting from $x$, having length $n$ and staying in the cone $K$. More generally, when $\mu$ is any distribution, the series $F(t)$ counts the numbers of $\mu$-weighted walks of length $n$ staying in the cone $K$. Accordingly, all our results admit direct combinatorial interpretations.

Recently, in the combinatorial literature, the seminal paper [3] inspired the following question, which has attracted a lot of attention: given an orthant $K = \mathbb{N}^d = \{0, 1, \dots\}^d$ and a distribution $\mu$ on $\mathbb{Z}^d$ (a step set in the combinatorial terminology), is the generating function (1.1), or its refined version

$$ F(x_1, \dots, x_d; t) = \sum_{n \ge 0} \sum_{(n_1, \dots, n_d) \in \mathbb{N}^d} \mathbb{P}^x(\tau > n, S_n = (n_1, \dots, n_d)) x_1^{n_1} \cdots x_d^{n_d} t^n \quad (1.4) $$

a rational function? An algebraic function? A function satisfying a linear (or non-linear) differential equation? A hypertranscendental function, meaning that like Euler's $\Gamma$ function it does not satisfy any differential equation? In the present article, we look at the possible rationality of the generating function.

Notice the following relation between (1.1) and (1.4):

$$ F(1, \dots, 1; t) = F(t). $$

On the other hand, $F(0, \dots, 0; t)$ is the generating function of the excursion sequence

$$ F(0, \dots, 0; t) = \sum_{n \ge 0} \mathbb{P}^x(\tau > n, S_n = (0, \dots, 0)) t^n, $$

which will be studied (based on earlier literature [5]) in Section 5.
<figure><img src="image_116.png" /><figcaption>FIGURE 1. A cone K (in red) and its dual cone cone K* (in blue)</figcaption></figure>

**Technical assumptions.** In order to present the hypotheses in the statement of our main results, we need to introduce two objects, through which the exponential rate $\rho$ in (1.2) will be determined:

• the Laplace transform $L$ of the increment distribution $\mu$:

$$L(t) = \mathbb{E}(e^{\langle t, X_k \rangle}) = \int_{\mathbb{R}^d} e^{\langle t, y \rangle} \mu(dy),$$

• the dual cone $K^*$ associated with $K$ (see Figure 1 for an example):

$$K^* = \{x \in \mathbb{R}^d : \langle x, y \rangle \ge 0 \text{ for all } y \in K\}. \quad (1.5)$$

Obviously, $K^*$ is a closed convex cone.

Throughout this paper, we make the following assumptions on the cone $K$ and on the distribution $\mu$ of the random walk increments:

(A1) The cone $K$ is closed, convex, with non-empty interior.

(A2) The random walk is truly $d$-dimensional, i.e., there is no $u \ne 0$ such that $\langle u, X_1 \rangle = 0$ almost surely. Moreover, the random walk started at zero can reach the interior $K^o$ of the cone: there exists $k > 0$ such that $\mathbb{P}^0(\tau > k, S_k \in K^o) > 0$.

(A3) The random walk increments are $L^1$. We call $m = \mathbb{E}X_1 = \int y\mu(dy)$ the drift.

(A4) There exists a point $t_0 \in K^*$ and a neighborhood $V$ of $t_0$ such that the Laplace transform $L$ of $\mu$ is finite in $V$ and $t_0$ is a minimum point of $L$ restricted to $K^* \cap V$.

We would like to give some intuition on the hypothesis (A4), which is designed to perform an exponential change of measure adapted to the geometry of the problem (see Subsection 2.1). First, (A4) implies the existence of some exponential moments, but not all; it is even not necessary that the increments have a moment of order one.
For example, consider a random variable $X$ with probability density function

$$f(x) = c_{\gamma} \left( \frac{e^{-x^2}}{1+x^2} 1_{\{x>0\}} + \frac{e^{\gamma^2}}{1+x^2} 1_{\{x\le 0\}} \right),$$

where $\gamma > 0$ is some fixed parameter and $c_\gamma$ is the normalizing constant. Since the negative part of $X$ has a half-Cauchy distribution, the variable $X$ is not integrable. However, its Laplace transform

$$L(t) = \mathbb{E}(e^{tX}) = c_{\gamma} \int_{0}^{\infty} \frac{e^{-tx}e^{\gamma^2} + e^{tx}e^{-x^2}}{1+x^2} dx$$

is finite and differentiable for all $t > 0$, and its derivative

$$L'(t) = c_{\gamma} \int_{0}^{\infty} (e^{2tx-x^2} - e^{\gamma^2}) \frac{xe^{-tx}}{1+x^2} dx$$

is negative for $t \in (0, \gamma)$. Thus $L$ reaches a minimum at some $t_0 > 0$ (clearly $L(t) \to \infty$ as $t \to \infty$). Now taking a random vector $Z = (X, Y)$ with density $f(x)f(y)$ gives a two-dimensional example where $Z$ is not integrable but its Laplace transform is finite in the quadrant $[0, \infty)^2$ and reaches a global minimum inside the quadrant.

Regarding the existence of a local minimum in $K^*$, hypothesis (A4) is discussed in [11] (see its subsection 2.3; the condition is called (H2) there), where an equivalent geometric condition is given: in the presence of all exponential moments, condition (A4) is satisfied if and only if the support of the distribution $\mu$ is not included in any ‘bad’ half-space $\{x \in \mathbb{R}^d : \langle x, u \rangle \le 0\}$, with $u$ in the dual cone $K^* \setminus \{0\}$.

Under assumptions (A1)–(A4), we proved in [11] that the exponential rate $\rho$ of the survival probability is equal to $L(t_0)$, meaning that for all $x \in K$,

$$\lim_{n \to \infty} \mathbb{P}^x(\tau > n)^{1/n} = L(t_0).$$

Furthermore, $L(t_0) < 1$ if and only if the drift $m$ does not belong to the closed cone $K$. Here, we shall prove a little bit more:

**Theorem 1.3.** Assume hypotheses (A1)–(A4) above. If $m \notin K^o$, then

$$\mathbb{P}^x(\tau > n) = \rho^n B_n,$$

where $\rho = L(t_0) \in (0, 1]$, $\sqrt[n]{B_n} \to 1$ and $B_n \to 0$.

Regarding the interior drift case, we shall prove the following estimate, in the setting of small step walks in orthants:

**Theorem 1.4.** For all $d$-dimensional weighted small step walks with a drift interior to the orthant $K = [0, \infty)^d$, not trapped and satisfying (A2), we have for all $x \in \mathbb{N}^d$

$$\mathbb{P}^x(\tau > n) - \mathbb{P}^x(\tau = \infty) = \Theta(\rho^n B_n),$$

where $\rho \in (0, 1)$ and $B_n$ satisfies $\sqrt[n]{B_n} \to 1$ and $B_n \to 0$.
**A one-dimensional example.** We now illustrate our previous results on the example of the simple random walk on $\mathbb{Z}$, with jump probabilities $q$ to the left $(-1)$ and $p = 1 - q$ to the right $(+1)$ and let $K = [0, \infty)$. In this setting,

$$ \tau = \inf\{n > 0 : S_n < 0\} = \inf\{n > 0 : S_n = -1\}. \qquad (1.6) $$

It is well known that, for any positive starting point $x \in \mathbb{N}$, the series (1.1) equals

$$ F(t) = \frac{1 - \phi(t)^{x+1}}{1 - t}, \quad \text{with } \phi(t) = \frac{1 - \sqrt{1 - 4pqt^2}}{2pt}. \qquad (1.7) $$

We may directly observe on (1.7) that, as stated in our Theorems 1.1 and 1.2, the function $F(t)$ is not rational. Indeed $F(t) \in \mathbb{R}(t)$ if and only if $(1 - \sqrt{1 - 4pqt^2})^{x+1} \in \mathbb{R}(t)$. But an expression like $(1 - \sqrt{P})^n$ where $P$ is a polynomial belongs to $\mathbb{R}(t)$ if and only if $\sqrt{P}$ belongs to $\mathbb{R}(t)$, as seen by a binomial expansion, and $\sqrt{P}$ is rational if and only if $P$ is a square in $\mathbb{R}[t]$. This is not the case here with $P(t) = 1 - 4pqt^2$, unless $p$ or $q$ equals 0. However, $F(t)$ defines an algebraic function (as usual for one-dimensional random walks; see [1]).

In the zero drift case (meaning that $p = q = \frac{1}{2}$), expanding (1.7) at $t = 1$ and using singularity analysis, one finds

$$ \mathbb{P}^x(\tau > n) \sim (x+1)\sqrt{\frac{2}{\pi}} \frac{1}{n^{1/2}} \quad (\text{in particular } \rho = 1). $$

If the drift is negative ($q > p$), the function $F$ in (1.7) is analytic at $1$ as $\phi(1) = 1$, and the singularities $t = \pm \frac{1}{2\sqrt{pq}}$ will both contribute to the asymptotics, which reads

$$ \mathbb{P}^x(\tau > n) \sim (x+1)\left(\frac{q}{p}\right)^{(x+1)/2} \left( \frac{1}{\frac{1}{2\sqrt{pq}} - 1} + \frac{(-1)^{x+n}}{\frac{1}{2\sqrt{pq}} + 1} \right) \frac{(2\sqrt{pq})^n}{\sqrt{2\pi n^{3/2}}}. $$

Finally, when the drift is positive ($p > q$), the probability of survival admits the following two-term asymptotics (observe the similarity with the negative drift situation)

$$ \mathbb{P}^x(\tau > n) = \left(1 - \left(\frac{q}{p}\right)^{x+1}\right) + (x+1)\left(\frac{q}{p}\right)^{(x+1)/2} \left(\frac{1}{\frac{1}{2\sqrt{pq}} - 1} + \frac{(-1)^{x+n}}{\frac{1}{2\sqrt{pq}} + 1}\right) \frac{(2\sqrt{pq})^n}{\sqrt{2\pi n^{3/2}}} + \dots $$

The three asymptotics above, which illustrate our Theorems 1.3 and 1.4, are obtained by studying the singularities of the generating function (1.7) and by using classical transfer theorems on the coefficients.

## 2. SURVIVAL PROBABILITY IN THE NON-INTERIOR DRIFT CASE: PROOF OF THEOREM 1.3

### 2.1. Basics on the Laplace transform.
Let us first recall some basic properties. The Laplace transform of a random vector $X = (X^{(1)}, \dots, X^{(d)}) \in \mathbb{R}^d$ with probability distribution $\mu$ is the function $L$ defined for $t \in \mathbb{R}^d$ by

$$ L(t) = \mathbb{E}(e^{\langle t, X \rangle}) = \int_{\mathbb{R}^d} e^{\langle t, y \rangle} \mu(dy). $$
It is finite in some neighborhood of the origin if and only if $\mathbb{E}(e^{\alpha\|X\|})$ is finite for some $\alpha > 0$. If $L$ is finite in some neighborhood of the origin, say $\overline{B}(0, r)$, then $L$ is infinitely differentiable in $B(0, r)$ and its partial derivatives are given there by

$$ \frac{\partial L(t)}{\partial t_i} = \mathbb{E}(X^{(i)} e^{\langle t, X \rangle}). $$

Therefore, the expectation $\mathbb{E}X = (\mathbb{E}X^{(1)}, \dots, \mathbb{E}X^{(d)})$ of $X$ is equal to the gradient of $L$ at the origin $\nabla L(0)$. Notice that $X$ is centered (i.e., $\mathbb{E}X = 0$) if and only if 0 is a critical point of $L$. Since $L$ is a convex function, this means that 0 is a minimum point of $L$ in $\overline{B}(0, r)$. Now suppose that $L$ is finite in some ball $\overline{B}(t_0, r)$, and define a new probability measure $\mu_*$ by

$$ \mu_*(dy) = \frac{e^{\langle t_0, y \rangle}}{L(t_0)} \mu(dy). $$

The Laplace transform $L_*$ of $\mu_*$ is linked to that of $\mu$ by the relation $L_*(t) = L(t_0+t)/L(t_0)$, and therefore $L_*$ is finite in some neighborhood of the origin. As a consequence, applying the results above shows that any random vector $X_*$ with distribution $\mu_*$ satisfies:

* $\mathbb{E}(e^{\alpha\|X_*\|}) < \infty$ for some $\alpha > 0$;

* $\mathbb{E}X_* = \nabla L(t_0)/L(t_0)$.

As we shall see later, the relevant value of $L$ for our problem is its minimum on the dual cone $K^*$ defined by (1.5).

We now investigate further properties of $\mathbb{E}X_*$ when $t_0$ satisfies the assumption (A4), i.e., $t_0$ is a local minimum point of $L$ restricted to $K^*$. By convexity of $L$, the point $t_0$ is necessarily a global minimum on $K^*$; we don't assume $t_0$ to be a global minimum on $\mathbb{R}^d$. Define the two sets

$$ S = \{u \in \mathbb{R}^d : \exists \varepsilon > 0, \forall s \in [-\varepsilon, \varepsilon], t_0 + su \in K^*\}, $$

$$ S^+ = \{u \in \mathbb{R}^d : \exists \varepsilon > 0, \forall s \in [0, \varepsilon], t_0 + su \in K^*\}. $$

Of course $S \subset S^+$. Since $K^*$ is a convex cone, the set $S$ contains at least $t_0$, while the set $S^+$ contains at least $K^*$. Assuming (A4), we observe the following:

* if $u$ belongs to $S^+$, then the function $\phi(s) = L(t_0 + su)$ defined on some small interval $[0, \varepsilon]$ reaches a minimum at $s = 0$, hence $\phi'(0) = \langle \nabla L(t_0), u \rangle \ge 0$. This holds for all $u \in K^*$ since $K^* \subset S^+$, therefore $\nabla L(t_0)$ belongs to the dual cone $(K^*)^*$ associated with $K^*$;

* if $u$ belongs to $S$, the function $\phi(s)$ defined on some small interval $[-\varepsilon, \varepsilon]$ reaches its minimum at $s = 0$, hence $\phi'(0) = 0$. Therefore $\nabla L(t_0)$ is orthogonal to $S$ (and so at least to $t_0$ itself).

Translating these observations in terms of the expectation of $X_*$, we obtain:

**Lemma 2.1.** Assume (A1) and (A4). The expectation $\mathbb{E}X_*$ of any random vector with distribution $\mu^*$ belongs to the cone $K$ and is orthogonal to $t_0$.

*Proof.* Since $K$ is a closed convex cone, it is well known that $(K^*)^* = K$ (see Exercise 2.31 in [4] for example). Everything now follows from the relation $\mathbb{E}X_* = \nabla L(t_0)/L(t_0)$. □
2.2. **Proof of Theorem 1.3.** We shall use the preceding $t_0$ and $\mu_*$ in order to perform an exponential change of measure. For any non-negative and measurable function $f: \mathbb{R}^n \to [0, \infty)$, elementary algebraic manipulations give:

$$
\begin{align*}
\mathbb{E}^x(f(S_1, \dots, S_n)) &= \int_{\mathbb{R}^n} f\left(x + x_1, x + \sum_{i=1}^2 x_i, \dots, x + \sum_{i=1}^n x_i\right) \prod_{i=1}^n \mu(dx_i) \\
&= \rho^n \int_{\mathbb{R}^n} f\left(x + x_1, x + \sum_{i=1}^2 x_i, \dots, x + \sum_{i=1}^n x_i\right) e^{-\langle t_0, \sum_{i=1}^n x_i \rangle} \prod_{i=1}^n \mu_*(dx_i) \\
&= \rho^n e^{\langle t_0, x \rangle} \mathbb{E}_*^x \left(f(S_1, \dots, S_n) e^{-\langle t_0, S_n \rangle}\right),
\end{align*}
$$

where

• $\rho = L(t_0)$,

• $\mathbb{E}_*^x$ is the expectation with respect to $\mathbb{P}_*^x$, a probability distribution under which $(S_n)_{n \ge 0}$ is a random walk with increment distribution $\mu_*$ and started at $S_0 = x$.

Taking $f(s_1, \dots, s_n) = \prod_{i=1}^n 1_K(s_i)$ leads to

$$
\mathbb{P}^x(\tau > n) = \rho^n e^{\langle t_0, x \rangle} \mathbb{E}_*^x \left( e^{-\langle t_0, S_n \rangle}, \tau > n \right),
$$

so that Theorem 1.3 will follow from the two lemmas below:

**Lemma 2.2.** Assume (A1)–(A4). Then, for all $x \in K$,

$$
\lim_{n \to \infty} \sqrt[n]{\mathbb{E}_{*}^{x}\left(e^{-\langle t_0, S_n \rangle}, \tau > n\right)} = 1.
$$

**Lemma 2.3.** Assume (A1)–(A4). If the drift $m = \mathbb{E}X_1$ does not belong to $K^o$, then for all $x \in K$,

$$
\lim_{n \to \infty} \mathbb{E}_*^x \left( e^{-\langle t_0, S_n \rangle}, \tau > n \right) = 0.
$$

Lemma 2.2 is fully proved in [11]. However, to make our paper self-contained, we propose here a short proof of it in a simplified setting. Instead of (A2) we will work under the following hypothesis: there exist $k > 0$ and $z \in K^o$ such that $\mathbb{P}(\tau > k, S_k = z) > 0$. In the majority of classical lattice random walks, the previous hypothesis is satisfied, as for instance for all 74 non-singular small step random walks considered in [3].

Proof of Lemma 2.2. First observe that on the event $\{\tau > n\}$, we have $S_n \in K$, hence $\langle t_0, S_n \rangle \ge 0$ since $t_0 \in K^*$. As a consequence $\mathbb{E}_*^x(e^{-\langle t_0, S_n \rangle}, \tau > n) \le \mathbb{P}_*(\tau > n) \le 1$, and what remains to prove is that

$$
\liminf_{n \to \infty} \sqrt[n]{\mathbb{E}_*^x \left( e^{-\langle t_0, S_n \rangle}, \tau > n \right)} \ge 1.
$$

By inclusion of events and basic properties of the $n$-th root limit, it suffices to prove the result for $x=0$, in which case we get rid of the $x$ superscript on $\mathbb{E}_*$ and $\mathbb{P}_*$. We compute a lower bound of the expectation as follows:

$$
\mathbb{E}_* \left( e^{-\langle t_0, S_n \rangle}, \tau > n \right) \ge e^{-a_n} \mathbb{P}_* \left( |\langle t_0, S_n \rangle| \le a_n, \tau > n \right),
$$

with $a_n = n^{3/4}$. The $e^{-a_n}$ term goes to 1 in the $n$-th root limit, thus we focus on the probability in the right-hand side.
Using our hypothesis, we can use the first $k\lfloor\sqrt{n}\rfloor$ steps to push the walk $\lfloor\sqrt{n}\rfloor$ times in the direction $z$ without leaving the cone: by inclusion of events and the Markov property, we have

$$ \mathbb{P}_* (|\langle t_0, S_n \rangle| \le a_n, \tau > n) \ge \alpha^{b_n} \mathbb{P}_*^{b_n z} (|\langle t_0, S_{n-kb_n} \rangle| \le a_n, \tau > n - kb_n), $$

where $\alpha = \mathbb{P}(\tau > k, S_k = z) > 0$ and $b_n = \lfloor\sqrt{n}\rfloor$. Here again, the $\alpha^{b_n}$ term will disappear in the $n$-th root limit, and the $-kb_n$ does not play any significant role in $n - kb_n$, so we are left to consider the probability

$$ \mathbb{P}_*^{b_n z} (|\langle t_0, S_n \rangle| \le a_n, \tau > n). $$

At this point, we take into account the “new drift” $d = \mathbb{E}_*X_1$ of the random walk under $\mathbb{P}_*$, and consider the centered random walk $\tilde{S}_n = S_n - nd$. Lemma 2.1 asserts that:

* $d$ is orthogonal to $t_0$, so that $\langle t_0, S_n \rangle = \langle t_0, \tilde{S}_n \rangle$,

* $d$ belongs to $K$, hence

$$ \{\tau(\tilde{S}_\ell) > n\} = \{\tilde{S}_1, \dots, \tilde{S}_n \in K\} \subset \{S_1, \dots, S_n \in K\} = \{\tau > n\}. $$

Due to these facts, our probability can be bounded from below by

$$ \begin{aligned} \mathbb{P}_*^{b_n z} (|\langle t_0, \tilde{S}_n \rangle| \le a_n, \tau(\tilde{S}_\ell) > n) &= \mathbb{P}_* (|\langle t_0, b_n z + \tilde{S}_n \rangle| \le a_n, \tau(b_n z + \tilde{S}_\ell) > n) \\ &= \mathbb{P}_* (|\langle t_0, z + \tilde{S}_n b_n^{-1} \rangle| \le a_n b_n^{-1}, \tau(z + \tilde{S}_\ell b_n^{-1}) > n) \\ &\ge \mathbb{P}_* (\|\tilde{S}_\ell b_n^{-1}\| < \varepsilon \text{ for all } \ell = 1, \dots, n), \end{aligned} $$

where we have used the homogeneity of the cone, namely $K/b_n = K$ on the second line, and then chosen $\varepsilon > 0$ so that the ball $B(z, \varepsilon) \subset K$. Now recall that, under $\mathbb{P}_*$, the increments $X_n$ of the random walk $S_n$ have a distribution $\mu^*$ with some exponential moments, hence the $X_n$'s are in $L^2$, and so do the increments $X_n - d$ of the centered random walk $\tilde{S}_n$. Therefore, the functional central limit theorem [2, Thm 8.2] is in force and, in conjunction with Portmanteau theorem [2, Thm 2.1], we obtain

$$ \liminf_{n \to \infty} \mathbb{P}_*^{b_n z} (|\langle t_0, \tilde{S}_n \rangle| \le a_n, \tau(\tilde{S}_\ell) > n) \ge \mathbb{P}_* (\|B_t\| < \varepsilon \text{ for all } t \in [0, 1]) > 0, $$

where $(B_t)_{t \in [0,1]}$ is the image of a standard Brownian motion started at 0 under a (possibly degenerate) linear transformation. This concludes the proof of Lemma 2.2. $\square$

*Proof of Lemma 2.3.* The proof will be done separately, according to whether $t_0$ is zero or not. First assume $t_0 \ne 0$. On the event $\{\tau > n\}$, for all $k = 1, \dots, n$, we have that $S_k \in K$, hence $R_k = \langle t_0, S_k \rangle \ge 0$ since $t_0 \in K^*$. Therefore

$$ \mathbb{E}_*^x (e^{-\langle t_0, S_n \rangle}, \tau > n) \le \mathbb{P}_*^x (R_k \ge 0 \text{ for all } k = 1, \dots, n). $$

Now, under $\mathbb{P}_*^x$, the process $R_k = \langle t_0, S_k \rangle$ is a random walk with increments $Y_k = \langle t_0, X_k \rangle$ having mean $\langle t_0, \mathbb{E}_*X_1 \rangle = 0$ (see Lemma 2.1). Since the initial distribution $\mu$ is truly $d$-dimensional and $\mu_*$ is absolutely continuous with respect to $\mu$, the new distribution $\mu_*$ is also truly $d$-dimensional.

Thus, under $\mathbb{P}_*^x$, the increments $Y_k$ are non-degenerate (i.e., it does not hold that $Y_k = 0$ almost surely). It is well known (see [9, Thm 1 & 2 of XII,2]) that for such a
one-dimensional random walk, almost surely,

$$-\infty = \liminf R_n < \limsup R_n = +\infty.$$

Accordingly,

$$\lim_{n \to \infty} \mathbb{P}_*^x (R_k \ge 0 \text{ for all } k = 1, \dots, n) = \mathbb{P}_*^x (R_k \ge 0 \text{ for all } k \ge 1) = 0.$$

We now turn to the case $t_0 = 0$. This time $\langle t_0, S_n \rangle = 0$, so we don't learn anything by considering this specific one-dimensional random walk. The idea is to replace $t_0$ with an appropriate $\tilde{t}_0$ and apply the same argument as before. To do this, observe that we know from Lemma 2.1 that $\mathbb{E}_*X_1$ belongs to the cone $K$, but when $t_0 = 0$ the change of measure has no effect: $\mu_* = \mu$. Hence the original drift $m = \mathbb{E}X_1$ belongs to $K$. Since we assumed $m \notin K^o$, we are left with a drift $m$ on the boundary $\partial K$ of the cone $K$.

If $C$ is a closed cone, the interior of its dual cone has the following description:

$$(C^*)^o = \{x \in \mathbb{R}^d : \langle x, y \rangle > 0 \text{ for all } y \in C \setminus \{0\}\}$$

(see Exercise 2.31(d) in [4] for example). As a consequence, the boundary is given by

$$\partial C^* = \{x \in C^* : \langle x, y \rangle = 0 \text{ for some } y \in C \setminus \{0\}\},$$

and applying this to the closed convex cone $C = K^*$ gives

$$\partial K = \{x \in K : \langle x, y \rangle = 0 \text{ for some } y \in K^* \setminus \{0\}\},$$

since $(K^*)^* = K$. Going back to our drift $m \in \partial K$, there exists some $\tilde{t}_0 \in K^* \setminus \{0\}$ such that $\langle \tilde{t}_0, m \rangle = 0$. Setting $\tilde{R}_k = \langle \tilde{t}_0, S_k \rangle$, we obtain a centered and non-degenerate one-dimensional random walk such that $S_k \in K$ implies $\tilde{R}_k \ge 0$. Therefore

$$\mathbb{E}_*^x (e^{-\langle t_0, S_n \rangle}, \tau > n) = \mathbb{P}^x (\tau > n) \le \mathbb{P}_*^x (\tilde{R}_k \ge 0 \text{ for all } k = 1, \dots, n),$$

and the conclusion follows as in the first case. $\square$

The proof of Theorem 1.3 is complete.

### 3. SURVIVAL PROBABILITY IN THE INTERIOR DRIFT CASE: PROOF OF THEOREM 1.4

In this section, we restrict our attention to the cone $K = [0, \infty)^d$ and small step walks, i.e., random walks on $\mathbb{Z}^d$ with increments $X_k$ satisfying $X_k \in \{-1, 0, 1\}^d$ almost surely. For such walks, we investigate the case of a drift $m = \mathbb{E}X_k$ interior to the cone $K$, i.e., such that $\langle m, e_i \rangle > 0$ for $i = 1, \dots, d$, where $(e_1, \dots, e_d)$ denotes the standard basis of $\mathbb{R}^d$. We will use the notation $X_k^{(i)} = \langle X_k, e_i \rangle$. Since the drift is in the interior of $K$, we know that

$$\lim_{n \to \infty} \mathbb{P}^x (\tau > n) = \mathbb{P}^x (\tau = \infty) > 0$$

for all $x \in K$; see Lemma 3.1 for a precise statement and a proof.

Here we wish to estimate the error term $\delta_n = \mathbb{P}^x(\tau > n) - \mathbb{P}^x(\tau = \infty)$. We exclude the case where $\delta_n = 0$ for all $n$ by assuming that the random walk is not trapped, i.e., the increments satisfy $\mathbb{P}(X_k \notin K) > 0$. Under this assumption we will prove Theorem 1.4, namely that

$$\mathbb{P}^x(\tau > n) - \mathbb{P}^x(\tau = \infty) = \Theta(\rho^n B_n).$$

Before going into the proof, we collect preliminary estimates on $\mathbb{P}^x(\tau = \infty)$.
3.1. **Exact formula for a one-dimensional small step walk.** First of all, we consider the one-dimensional setting with $p = \mathbb{P}(X_k = 1)$, $r = \mathbb{P}(X_k = 0)$, $q = \mathbb{P}(X_k = -1)$, $p+r+q = 1$. Let $\tau$ be as in (1.6) and assume $m = p - q > 0$. Then it is known that, for all $x \in \mathbb{N}$,

$$ \mathbb{P}^x(\tau = \infty) = 1 - \left(\frac{q}{p}\right)^{x+1}. $$

If $q > 0$, this can be rewritten as

$$ \mathbb{P}^x(\tau = \infty) = 1 - \gamma e^{-sx}, \quad (3.1) $$

where $\gamma = q/p$ and $s > 0$ is the unique solution to $e^{-s} = q/p$.

One way to obtain the formula above is to use the discrete harmonicity of the function $u_x = \mathbb{P}^x(\tau = \infty)$: by the Markov property, we have $u_x = qu_{x-1} + ru_x + pu_{x+1}$ for all $x \ge 1$, which is solved in $u_x = a + b \left(\frac{q}{p}\right)^x$. Then $a$ and $b$ are determined through initial and limit behaviors of $u_x$.

For future use, we notice the following fact: let

$$ L(t) = \mathbb{E}(e^{tX_k}) = pe^t + r + qe^{-t} $$

be the Laplace transform associated with the random walk increments. Its derivative is given by $L'(t) = pe^t - qe^{-t}$. Evaluating at $t = -s$, where $s$ is as above the solution to $e^{-s} = q/p$, leads to

$$ L(-s) = 1 \quad \text{and} \quad L'(-s) = q - p = -m < 0. \quad (3.2) $$

The last value is exactly the opposite of the drift.

3.2. **Estimate for $\mathbb{P}^x(\tau < \infty)$ in the $d$-dimensional small step case.** Let us go back to our $d$-dimensional small step walk $(S_n)_n$ with drift $m$ interior to the cone $K = [0, \infty)^d$ and such that $\mathbb{P}(X_k \notin K) > 0$. The simple inclusion of events

$$ \{\exists n > 0, \langle S_n, e_i \rangle < 0\} \subset \{\tau < \infty\} \subset \bigcup_{i=1}^{d} \{\exists n > 0, \langle S_n, e_i \rangle < 0\} $$

leads to the bounds

$$ \frac{g(x)}{d} \le \mathbb{P}^x(\tau < \infty) \le g(x), \quad (3.3) $$

where $g(x) = \sum_{i=1}^d \mathbb{P}^x(\exists n > 0, \langle S_n, e_i \rangle < 0)$. Now, for each $i$, the one-dimensional small step walk $(\langle S_n, e_i \rangle)_n$ with increments $X_k^{(i)}$ has a drift $\mathbb{E}X_k^{(i)} = \langle m, e_i \rangle > 0$. Since $\mathbb{P}(X_k \notin K) > 0$, the set $I$ of indices $i$ for which $\mathbb{P}(X_k^{(i)} = -1) > 0$ is non-empty, and applying the exact formula (3.1) of the preceding paragraph, we obtain:

$$ g(x) = \sum_{i \in I} \gamma_i e^{-s_i \langle x, e_i \rangle}, $$

where $\gamma_i = \mathbb{P}(X_k^{(i)} = -1)/\mathbb{P}(X_k^{(i)} = 1) \in (0, 1)$ and $s_i > 0$ is the unique solution to $e^{-s_i} = \gamma_i$.
### 3.3. Proof of Theorem 1.4.
Fix $x \in \mathbb{N}^d$ and set

$$ \delta_n = \mathbb{P}^x(\tau > n) - \mathbb{P}^x(\tau = \infty) = \mathbb{P}^x(\tau > n, \text{ but } S_m \notin K \text{ for some } m > n). $$

By the Markov property of the random walk, we can express $\delta_n$ as follows:

$$ \delta_n = \mathbb{E}^x \left( \tau > n, \mathbb{P}^{S_n}(\tau < \infty) \right), $$

so that inequality (3.3) leads to $\delta_n = \Theta(g_n)$, where $g_n = \mathbb{E}^x(\tau > n, g(S_n))$. It remains to estimate

$$ g_n = \sum_{i \in I} \gamma_i \mathbb{E}^x \left( \tau > n, e^{\langle S_n, -s_i e_i \rangle} \right). $$

To do this, we apply to each term in the sum a specific exponential change of measure. Set

$$ \mu_{*i}(dy) = \frac{e^{\langle -s_i e_i, y \rangle}}{L(-s_i e_i)} \mu(dy), $$

where $\mu$ is the common distribution of the increments $X_k$ of the random walk, and $L(t) = \mathbb{E}(e^{\langle t, X_k \rangle})$ is their Laplace transform. Then basic algebraic manipulations as in Section 2.2 lead to

$$ \mathbb{E}^x \left( \tau > n, e^{\langle S_n, -s_i e_i \rangle} \right) = L(-s_i e_i)^n e^{\langle -s_i e_i, x \rangle} \mathbb{P}_{*i}^x (\tau > n). $$

Now observe that $t \mapsto L(te_i) = \mathbb{E}(e^{tX_k^{(i)}})$ is the one-dimensional Laplace transform of the increments $X_k^{(i)}$. Since $s_i$ is the solution to $e^{-s_i} = \gamma_i = \frac{\mathbb{P}(X_k^{(i)}=-1)}{\mathbb{P}(X_k^{(i)}=1)}$, we are in the same situation as in (3.2), so that

$$ L(-s_i e_i) = 1 \quad \text{and} \quad \frac{\partial L}{\partial t_i}(-s_i e_i) = -\langle m, e_i \rangle < 0. $$

Therefore, equation (3.3) reads

$$ \mathbb{E}^x \left( \tau > n, e^{\langle S_n, -s_i e_i \rangle} \right) = e^{\langle -s_i e_i, x \rangle} \mathbb{P}_{*i}^x (\tau > n), $$

and the new drift under $\mathbb{P}_{*i}^x$, which is given by the gradient of $L$ at the point $-s_i e_i$, has a strictly negative i-th coordinate. As a consequence, this drift does not belong to the cone $K = [0, \infty)^d$, and it follows from Theorem 1.3 that

$$ \mathbb{P}_{*i}^x (\tau > n) = \rho_i^n B_{i,n}, $$

where $\rho_i \in (0, 1)$, $\sqrt[n]{B_{i,n}} \to 1$ and $B_{i,n} \to 0$ as $n \to \infty$. Finally, we get

$$ g_n = \sum_{i \in I} \gamma_i \rho_i^n B_{i,n}, $$

which can be rewritten in the form $g_n = \rho^n B_n$, by selecting

$$ \rho = \max\{\rho_i : i \in I\} < 1. $$

It is then clear that $\sqrt[n]{B_n} \to 1$ and $B_n \to 0$, and the proof is complete.
### 3.4. Positivity of the escape probability.

**Lemma 3.1.** Assume (A1) and (A2). If the drift $m = \mathbb{E}X_1$ belongs to $K^o$, then the function $h(x) = \mathbb{P}^x(\tau = \infty)$ satisfies:

(1) $h$ is harmonic for the killed random walk, i.e.,

$$h(x) = \mathbb{E}^x(h(S_n), \tau > n).$$

(2) $h(x) > 0$ for all $x \in K$.

(3) $\lim_{t \to \infty} h(tu) = 1$ for all $u \in K^o$.

*Proof.* Item (1) is just the Markov property applied at time $n$. The relation is valid disregarding the position of the drift. We now prove (2).

*First step.* We begin with a simple geometric fact. For any $z \in K^o$, the non-decreasing sequence of sets $K - kz$ will ultimately cover the whole space, i.e., $\cup_{k \ge 0} (K - kz) = \mathbb{R}^d$. To see this, select $\varepsilon > 0$ such that $B(z, \varepsilon) \subset K$. For any $x \in \mathbb{R}^d$, there exists $k > 0$ such that $\|x/k\| < \varepsilon$, hence $z + \frac{x}{k}$ belongs to $K$. By homogeneity of $K$, it follows that $kz + x \in K$, i.e., $x \in K - kz$.

*Second step.* Let us consider the random walk $(S_n)$ with drift $m \in K^o$ and select $\varepsilon > 0$ such that $B(m, \varepsilon) \subset K$. By the strong law of large numbers $S_n/n \to m$ almost surely, therefore, for almost all $\omega$, there exists $n_0 = n_0(\omega)$ such that

$$n \ge n_0 \Rightarrow \left\| \frac{S_n(\omega)}{n} - m \right\| < \varepsilon \Rightarrow S_n(\omega) \in K.$$

Considering now the first positions $S_1(\omega), S_2(\omega), \dots, S_{n_0-1}(\omega)$, the first step of the proof ensures that there exists $k \ge 0$ such that they all belong to $K - kz$, where $z \in K^o$ is to be fixed in the last step of the proof. Since one has

$$K \subset K - kz \text{ (recall that } K + K \subset K),$$

all positions $S_n(\omega)$, $n \ge n_0$, also belong to $K - kz$ and we obtain the following:

$$\mathbb{P}(\cup_{k \ge 0} \{S_n \in K - kz \text{ for all } n \ge 0\}) = 1.$$

Since the events inside the probability above form a non-decreasing sequence, it follows that

$$\lim_{k \to \infty} \mathbb{P}(S_n \in K - kz \text{ for all } n \ge 0) = 1. \quad (3.4)$$

*Last step.* To conclude, we invoke hypothesis (A2), that claims the existence of an integer $\ell \ge 1$ such that

$$\mathbb{P}(\tau > \ell, S_\ell \in K^o) > 0.$$

Fix some $u \in K^o$. Since $K^o = \cup_{\lambda > 0} (K + \lambda u)$, there is a $z = \lambda u \in K^o$ such that

$$\mathbb{P}(\tau > \ell, S_\ell \in K + z) = p > 0.$$

By the Markov property, a concatenation of $m$ such $\ell$-steps leads to

$$\mathbb{P}(\tau > m\ell, S_{m\ell} \in K + mz) \ge p^m > 0.$$

On the other hand, it follows from (3.4) that there exists $k \ge 0$ such that

$$\mathbb{P}(S_n \in K - kz \text{ for all } n \ge 0) \ge 1/2.$$
Now choose $m \ge k$. Since $S_{ml} \in K + mz$ and $S_n - S_{ml} \in K - kz$ imply $S_n \in K$, we obtain

$$ \mathbb{P}(\tau = \infty) \ge \mathbb{P}(\tau > ml, S_{ml} \in K + mz) \times \mathbb{P}(S_n \in K - kz \text{ for all } n \ge 0) > 0. $$

We have just proved that $g(0) > 0$. The result follows since $g(x) \ge g(0)$ for all $x \in K$, by inclusion of events.

We conclude with the proof of (3). The limit (3.4) obtained in the second step of Item (2) can be recast as:

$$ \lim_{k \to \infty} \mathbb{P}^{kz}(\tau = \infty) = 1, $$

where $z$ is any vector in $K^o$. Since $g(x) = \mathbb{P}^x(\tau = \infty)$ is non-decreasing in every direction, the proof is completed. $\square$

### 4. PROOF OF THEOREMS 1.1 AND 1.2

In this section, we show that our estimates on $a_n = \mathbb{P}^x(\tau > n)$ given in Theorems 1.3 and 1.4 are not compatible with the generating function $F(t) = \sum_{n \ge 0} a_n t^n$ being rational, using classical singularity analysis for rational functions. The starting point is Theorem IV.9 in [10], which asserts the following:

**Theorem 4.1.** If $F(z) = \sum_{n \ge 0} a_n z^n$ is a rational function that is analytic at 0 and has poles at points $\alpha_1, \alpha_2, \dots, \alpha_k$, then its coefficients are sums of exponential-polynomials: there exist $k$ polynomials $P_j$ such that, for $n$ larger than some fixed $n_0$,

$$ a_n = \sum_{j=1}^{k} P_j(n) \alpha_j^{-n}. $$

Both estimates in Theorems 1.3 and 1.4 have the following form:

$$ a_n = a + \Theta(\rho^n B_n), $$

where $a \ge 0$, $\rho \in (0, 1]$, $\sqrt[n]{B_n} \to 1$ and $B_n \to 0$. Therefore Theorems 1.1 and 1.2 asserting the non-rationality of $F$ will follow in both cases from the following elementary lemma.

**Lemma 4.2.** Let $c_1, \dots, c_k$ be distinct non-zero complex numbers and $P_1, \dots, P_k$ be non-zero complex polynomials. Set $a_n = \sum_{j=1}^k P_j(n) c_j^n$. If $a_n = a + \Theta(\rho^n B_n)$ for some $a \ge 0$, $\rho > 0$ and $B_n > 0$ such that $\sqrt[n]{B_n} \to 1$, then necessarily $B_n \not\to 0$.

*Proof.* If $a_n = \sum_{j=1}^k P_j(n) c_j^n$, then $a_n - a$ has the same form, thus, without loss of generality, we can assume $a = 0$. Write $c_j = r_j z_j$ with $r_j > 0$ and $|z_j| = 1$. Let $r = \max\{r_j : j = 1, \dots, k\}$ and let $J$ be the subset of indices $j$ such that $r_j = r$. Then

$$ a_n = \sum_{j=1}^{k} P_j(n) c_j^n = r^n \left( \sum_{j \in J} P_j(n) z_j^n + o(t^n) \right), $$

where $0 < t < 1$. For future use, note that the numbers $z_j, j \in J$ are all distinct (this is so since we kept at most one $c_j$ in any fixed “direction” $z_j$: the one with maximum modulus).

We first show that $r = \rho$. Since $a_n = \Theta(\rho^n B_n)$ and $\sqrt[n]{B_n} \to 1$, it follows that $a_n/\rho^n$ goes to one in the $n$-th root limit. Thus, for any $\varepsilon > 0$,

$$ ((1 - \varepsilon)\rho)^n \le a_n \le ((1 + \varepsilon)\rho)^n $$
for $n$ large enough. Therefore

$$ \left( \frac{(1 - \varepsilon)\rho}{r} \right)^n \le \left| \sum_{j \in J} P_j(n) z_j^n + o(t^n) \right| \le \left( \frac{(1 + \varepsilon)\rho}{r} \right)^n \quad (4.1) $$

for $n$ large enough. If $\rho > r$ then we can choose $\varepsilon > 0$ such that the lower bound is $A^n$ for some $A > 1$. But then we would have

$$ A^n \le \left| \sum_{j \in J} P_j(n) z_j^n + o(t^n) \right| \le \sum_{j \in J} |P_j(n)| + |o(t^n)| $$

and this is impossible since $\sum_{j \in J} |P_j(n)|$ grows polynomially. On the other hand, if $\rho < r$ then we can choose $\varepsilon > 0$ such that the upper bound in (4.1) is $A^n$ for some $A < 1$. This implies

$$ \sum_{j \in J} P_j(n) z_j^n \to 0. $$

Dividing this by $n^p$, where $p$ stands for the maximum degree of polynomials $P_j$, leads to the convergence

$$ \sum_{j \in J'} a_j z_j^n \to 0, $$

where $J' \subset J$ is a non-empty subset of indices (those $j$ for which $P_j$ has degree $p$) and the $a_j$'s are non-zero complex numbers. Since the numbers $z_j$ are distinct complex numbers with modulus 1, this contradicts Lemma 4.3 below. The assertion $r = \rho$ is now established, hence we have

$$ \left| \sum_{j \in J} P_j(n) z_j^n + o(t^n) \right| = \frac{a_n}{\rho^n} = \Theta(B_n). $$

We have seen just before that this expression cannot go to zero as $n \to \infty$, thus $B_n \not\to 0$. $\square$

**Lemma 4.3.** Let $z_1, \dots, z_k$ be distinct complex numbers with modulus $\ge 1$. If

$$ \lim_{n \to \infty} \sum_{j=1}^{k} a_j z_j^n = 0, $$

then necessarily $a_1 = \dots = a_k = 0$.

*Proof.* Denote by $A_n$ the quantity $\sum_{j=1}^k a_j z_j^n$. Clearly, given any complex numbers $\alpha_0, \dots, \alpha_{k-1}$,

$$ \sum_{i=0}^{k-1} \alpha_i A_{n+i} = \sum_{j=1}^{k} a_j P(z_j) z_j^n, \quad (4.2) $$

where $P(z) = \sum_{i=0}^{k-1} \alpha_i z^i$. We can choose the polynomial $P$ so as to have $P(z_1) = 1$ and all other $P(z_j) = 0$. We then take the limit of (4.2) as $n \to \infty$, using the assumption of Lemma 4.3. We find that the term $a_1 z_1^n$ should go to zero, which implies that $a_1 = 0$, since $|z_1| \ge 1$. A similar reasoning gives that all $a_j = 0$, and thus Lemma 4.3 is proved. $\square$
## 5. THE EXCURSION GENERATING FUNCTION

In this section, we look at lattice random walks in convex cones. Besides the generating function of the survival probabilities (1.1), it is natural to ask whether the excursion generating function

$$E(t) = \sum_{n \ge 0} \mathbb{P}^x(\tau > n, S_n = y)t^n \quad (5.1)$$

can be rational, for given starting and ending points $x, y \in K$. When the cone $K$ is an orthant $\mathbb{N}^d$ and $x = y = (0, \dots, 0)$, the function $E(t)$ reduces to the series $F(0, \dots, 0; t)$ of (1.4). In order to state the result of this section, we introduce the following assumption:

(A4') There exists a point $\tilde{t}_0 \in \mathbb{R}^d$ and a neighborhood $V$ of $\tilde{t}_0$ such that the Laplace transform $L$ of $\mu$ is finite in $V$ and $\tilde{t}_0$ is a minimum point of $L$ restricted to $V$.

Since $L$ is a convex function, the point $\tilde{t}_0$ above is necessarily a global minimum. If $\mu$ is truly $d$-dimensional (as assumed in (A2)), the function $L$ is strictly convex and a necessary and sufficient condition for the existence of a global minimum is that the support of $\mu$ is not included in any closed half-space.

**Theorem 5.1.** For any distribution satisfying to (A1)-(A3), (A4') and such that the random walk takes its values on a lattice, the generating function $E(t)$ in (5.1) is not a rational function.

Contrary to our elementary and self-contained proof of Theorem 1.1, we don't have any elementary argument to prove Theorem 5.1. Instead, we may give a one-line proof based on earlier literature. Indeed, Denisov and Wachtel provide the following estimate in [5, Eq. (10)] (we use the generalization to convex cones as in [6, Cor. 1.3]): $\mathbb{P}^x(\tau > n, S_n = y)$ is either 0 (for periodicity reasons) or asymptotic to

$$C(x, y) \tilde{\rho}^n n^{-p-d/2},$$

where $\tilde{\rho} = L(\tilde{t}_0)$ with $\tilde{t}_0$ as in (A4'), $d$ is the dimension and $p > 0$ is a geometric quantity related to the cone. One immediately concludes because the exponent of $n$ is negative.

**Acknowledgments.** KR would like to thank Cyril Banderier, Mireille Bousquet-Mélou, Thomas Dreyfus and Éric Fusy for preliminary discussions. We thank Vitali Wachtel and Michael Wallner for interesting discussions. We further thank Christophe Devulder for the elegant proof of Lemma 4.3. Finally, we thank the anonymous referees for their careful reading and their suggestions, which helped us to improve our presentation.

## REFERENCES

[1] Cyril Banderier and Philippe Flajolet. Basic analytic combinatorics of directed lattice paths. Theor. Comput. Sci., 281(1-2):37-80, 2002.

[2] Patrick Billingsley. Convergence of Probability Measures. Wiley, 2nd edition, 1999.

[3] Mireille Bousquet-Mélou and Marni Mishna. Walks with small steps in the quarter plane. In Algorithmic probability and combinatorics. Papers from the AMS special sessions, Chicago, IL, USA, October 5-6, 2007 and Vancouver, BC, Canada, October 4-5, 2008, pages 1-39. American Mathematical Society, 2010.

[4] Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004.
[5] Denis Denisov and Vitali Wachtel. Random walks in cones. *Ann. Probab.*, 43(3):992–1044, 2015.

[6] Denis Denisov and Vitali Wachtel. Alternative constructions of a harmonic function for a random walk in a cone. *Electron. J. Probab.*, 24:26 pp., 2019.

[7] Thomas Dreyfus, Charlotte Hardouin, Julien Roques, and Michael F. Singer. Walks in the quarter plane: genus zero case. *J. Comb. Theory, Ser. A*, 174:24 pp., 2020.

[8] Jetlir Duraj. Random walks in cones: the case of nonzero drift. *Stochastic Processes Appl.*, 124(4):1503–1518, 2014.

[9] William Feller. *An Introduction to Probability Theory and Its Applications. Vol II*. John Wiley & Sons, 2nd edition, 1971.

[10] Philippe Flajolet and Robert Sedgewick. *Analytic combinatorics*. Cambridge University Press, 2009.

[11] Rodolphe Garbit and Kilian Raschel. On the exit time from a cone for random walks with drift. *Rev. Mat. Iberoam.*, 32(2):511–532, 2016.

[12] Stephen Melczer and Marni Mishna. Singularity analysis via the iterated kernel method. *Comb. Probab. Comput.*, 23(5):861–888, 2014.

[13] Marni Mishna and Andrew Rechnitzer. Two non-holonomic lattice walks in the quarter plane. *Theor. Comput. Sci.*, 410(38-40):3616–3630, 2009.
HEIGHT OF WALKS WITH RESETS, THE MORAN MODEL, AND
THE DISCRETE GUMBEL DISTRIBUTION

RAFIK AGUECH<fnref n="1" />, ASMA ALTHAGAFI<fnref n="2" />, AND CYRIL BANDERIER<fnref n="3" />

**Abstract.** In this article, we consider several models of random walks in one or several dimensions, additionally allowing, at any unit of time, a reset (or “catastrophe”) of the walk with probability $q$. We establish the distribution of the final altitude. We prove algebraicity of the generating functions of walks of bounded height $h$ (showing in passing the equivalence between Lagrange interpolation and the kernel method). To get these generating functions, our approach offers an algorithm of cost $O(1)$, instead of cost $O(h^3)$ if a Markov chain approach would be used. The simplest nontrivial model corresponds to famous dynamics in population genetics: the Moran model.

We prove that the height of these Moran walks asymptotically follows a discrete Gumbel distribution. For $q = 1/2$, this generalizes a model of carry propagation over binary numbers considered e.g. by von Neumann and Knuth. For generic $q$, using a Mellin transform approach, we show that the asymptotic height exhibits fluctuations for which we get an explicit description (and, in passing, new bounds for the digamma function). We end by showing how to solve multidimensional generalizations of these walks (where any subset of particles is attributed a different probability of dying) and we give an application to the soliton wave model.

**Keywords:** Random walks, renewal process, Moran model, analytic combinatorics, discrete Gumbel distribution, Mellin transform, kernel method, digamma function.

<footnote n="1">¹ DEPARTMENT OF STATISTICS AND OPERATIONS RESEARCH, KING SAUD UNIV., SAUDI ARABIA, AND DEPARTMENT OF MATHEMATICS, UNIVERSITY OF MONASTIR, TUNISIA; https://faculty.ksu.edu.sa/en/raguech</footnote>

<footnote n="2">² DEPARTMENT OF STATISTICS AND OPERATIONS RESEARCH, KING SAUD UNIV., SAUDI ARABIA; https://www.researchgate.net/profile/Asma-Althagafi</footnote>

<footnote n="3">³ LABORATOIRE D'INFORMATIQUE DE PARIS NORD, UNIV. SORBONNE PARIS NORD, FRANCE; http://lipn.fr/~banderier</footnote>
CONTENTS

<table><tr><td>1. Introduction</td><td>264</td></tr><tr><td>2. Walks with resets: final altitude and height</td><td>266</td></tr><tr><td>2.1. Final altitude Y<sub>n</sub></td><td>267</td></tr><tr><td>2.2. The height H<sub>n</sub></td><td>269</td></tr><tr><td>3. Asymptotic height of Moran walks</td><td>274</td></tr><tr><td>3.1. Localization of the dominant singularity</td><td>274</td></tr><tr><td>3.2. Limit distribution of the height: the discrete Gumbel distribution</td><td>276</td></tr><tr><td>3.3. Waiting time</td><td>281</td></tr><tr><td>4. Mean and variance of the height</td><td>282</td></tr><tr><td>4.1. Fundamental properties of the Mellin transform</td><td>282</td></tr><tr><td>4.2. Average height of Moran walks</td><td>283</td></tr><tr><td>4.3. Variance of the height of Moran walks</td><td>286</td></tr><tr><td>4.4. Height of excursions</td><td>287</td></tr><tr><td>4.5. Fourier series: bounds and infinite differentiability</td><td>288</td></tr><tr><td>5. Some results for the Moran model in dimension m > 1</td><td>292</td></tr><tr><td>5.1. Joint distribution of ages for the Moran model with m > 1</td><td>292</td></tr><tr><td>5.2. A multidimensional generalization of the Moran model</td><td>294</td></tr><tr><td>5.3. Application to the soliton wave model</td><td>295</td></tr><tr><td>6. Conclusion and future works</td><td>296</td></tr><tr><td>References</td><td>297</td></tr></table>

1. INTRODUCTION

The height of random walks is a fundamental parameter which occurs in many domains: in computer science (evolution of a stack, tree traversals, or cache algorithms [39]), in reliability or failure theory (maximal age of a component and inference statistics on the longevity before replacement [24]), in queueing theory (maximal length of the queue, with e.g. applications to traffic jam analysis [37]), in mathematical finance (e.g. in risk theory [28]), in bioinformatics (pattern matching and sequence alignment [2]), etc.

In combinatorics, random walks are studied via the corresponding notion of *lattice paths*, which play a central role, not only for intrinsic properties of such paths, but also as they are in bijection with many fundamental structures (trees, words, maps, ...). We refer to the nice *magnum opus* of Flajolet and Sedgewick on analytic combinatorics [22] for many enumerative and asymptotic examples.

While the behavior of an extremal parameter such as the height is well understood for walks corresponding to Brownian motion theory, it becomes more subtle when a notion of reset/renewal/reseting/catastrophe [8, 9, 14, 29, 33, 40, 42] is introduced in the model: indeed, typical behaviors in this model are often established by conditioning on events of probability zero in the model without reset, leading to possibly counterintuitive results.
In this article, we give several enumerative and asymptotic results on different statistics (final altitude, waiting time, height) of walks with resets, focusing on the so-called Moran walks (walks related to biological/population models considered by Moran in 1958; see Section 5 for more on this).

**Plan of the article.**

In Section 2, we consider a generic model of walks with resets (allowing any finite set of steps and a reset step). We describe the behavior of their final altitude (at finite time, and asymptotically). We obtain an algebraic closed form for the bivariate generating function (length/final altitude) for walks of bounded height $h$. Our approach uses a variant of the so-called kernel method, which has the advantage to avoid any case-by-case computation based on Markov chains/transfer matrices of size $h \times h$. In passing, we show the intimate link between Lagrange interpolation and the kernel method.

In Section 3, we consider Moran walks, a model described in Figure 1, for which we generalize an enumerative formula due to Pippenger [45]. We show that their height asymptotically follows a distribution which involves non-trivial fluctuations. We prove that this distribution is a *discrete Gumbel distribution*, and we clarify its links with the *continuous Gumbel distribution*. We give an application to the waiting time for reaching any given altitude.

In Section 4, we begin with a brief presentation of the Mellin transform method, and then use it to derive a precise analysis of the asymptotic average and variance of the height. The second asymptotic term involves some $O(1)$ fluctuations given by a Fourier series (which we prove to be infinitely differentiable, and for which we also derive generic bounds of independent interest). This extends (and fixes some error terms) in earlier analyses by von Neumann, Knuth, Flajolet and Sedgewick [13, 22, 38].

In Section 5, we tackle some multidimensional generalizations of Moran walks, with applications to a model in population genetics and to a wave propagation model (a soliton model), as considered by Itoh, Mahmoud, and Takahashi in [34, 35].

In Section 6, we conclude with a few possible extensions for future work.

<figure><img src="image_117.png" /><figcaption>FIGURE 1. A Moran walk is a random walk which makes a jump +1 with probability $p$, and a reset (a jump to 0) with probability $1-p$. Above, one sees such a walk of length $n = 30$. Its final altitude is $Y_n = 1$, the height is $H_n = 5$ (reached twice, in red), having 7 resets (the 7 blue dots). In this article, we tackle the enumeration and asymptotics of such paths (and of generalizations involving more general step sets and higher dimension). We also prove that this simple model of walks leads to some noteworthy nontrivial asymptotic behavior of their height $H_n$.</figcaption></figure>
## 2. WALKS WITH RESETS: FINAL ALTITUDE AND HEIGHT

We consider walks with steps in $\mathcal{S}$ (where $\mathcal{S}$ is a nonempty finite subset of $\mathbb{Z}$), which can additionally have a reset at any altitude. That is, we have the following process on $\mathbb{Z}$:

$$Y_0 = 0$$

$$Y_{n+1} = \begin{cases} Y_n + k, & \text{with probability } p_k \quad (\text{for each } k \in \mathbb{Z}, \text{ with } p_k := 0 \text{ if } k \notin \mathcal{S}), \\ 0, & \text{with probability } q \quad (\text{with } q + \sum_{k \in \mathcal{S}} p_k = 1). \end{cases}$$

(So if $Y_n = 0$ we have $Y_{n+1} = 0$ with probability $p_0 + q$.)

Thus, $Y_n$ is the altitude of the process after $n$ steps and $H_n := \max(Y_0, \dots, Y_n)$ is its height. It is convenient to encode the steps and their probabilities by the Laurent polynomial

$$P(u) := \sum_{k=c}^{d} p_k u^k \quad (\text{with } c := \min \mathcal{S} \text{ and } d := \max \mathcal{S}). \qquad (2.1)$$

We assume $0 < q < 1$ to avoid degenerate cases. We do not require that $c < 0$ or $d > 0$. Of course, if $c \ge 0$, the walk will live by design in $\mathbb{N}$ (it is e.g. the case for Moran walks of Figure 1). In Section 2.1, we determine the distribution of the final altitude (as illustrated in Figure 2 for different families of steps) and we investigate the height in Section 2.2.

<figure><img src="image_118.png" /><figcaption>FIGURE 2. Plot of $P(Y_n = k)$, the distribution of the altitudes of walks with resets, for $n = 100$ and different $P(u)$. It has its support in the $\mathbb{N}$-linear combinations of steps from $\mathcal{S}$. The final altitude is of order $O(1)$ and the probability to end at higher altitudes decreases exponentially fast (see Theorem 2.1 for closed-form expressions of the mean and the distribution).</figcaption></figure>
2.1. **Final altitude** $Y_n$. Let us start with a simple result which paves the way for the more subtle generating function manipulations for the height that we tackle later in Section 2.2. We use the classical convenient notations:

• $[z^n]G(z)$ stands for the coefficient of $z^n$ in the power series $G(z)$,

• $\partial_u^j F(z, 1)$ is the $j$-th derivative of $F(z, u)$ with respect to $u$, evaluated at $u = 1$.

**Theorem 2.1 (Final altitude at finite time).** The final altitude of walks with resets follows a discrete law with probability generating function

$$F(z, u) = \sum_{n \ge 0} \mathbb{E}[u^{Y_n}] z^n = \frac{1 + qz/(1-z)}{1 - zP(u)}, \qquad (2.2)$$

where $P(u)$ is the Laurent polynomial encoding the allowed steps (a finite subset of $\mathbb{Z}$). Equivalently, for $k \in \mathbb{Z}$, we have

$$\mathbb{P}(Y_n = k) = [u^k]P(u)^n + q[u^k] \sum_{j=0}^{n-1} P(u)^j. \qquad (2.3)$$

Let $\delta := P'(1)$ be the drift<fnref n="1" /> of the walk without reset, and $V := P''(1)$ its second factorial moment. The mean and the variance of the final altitude of the walk with resets are given by

$$\mathbb{E}[Y_n] = \delta/q + (1-q)^{n-1}(\delta - \delta/q), \\ \mathrm{Var}[Y_n] = \frac{(V+\delta)q + \delta^2}{q^2} + (1-q)^n \left(2 \frac{\delta^2 n}{(q-1)q} - \frac{V+\delta}{q}\right) - (1-q)^{2n} \frac{\delta^2}{q^2}.$$

For Moran walks (i.e., $P(u) = pu$ and $p = 1-q$), the mean and the variance simplify to

$$\mathbb{E}[Y_n] = \frac{p}{q}(1-p^n) \quad \text{and} \quad \mathrm{Var}[Y_n] = \frac{p}{q^2}(1-p^n(p^{n+1} + (1+2n)q)).$$

*Proof.* The probability generating function can be written as

$$F(z, u) = \sum_{n \ge 0} \left( \sum_{k \in \mathbb{Z}} \mathbb{P}(Y_n = k) u^k \right) z^n = \sum_{n \ge 0} f_n(u) z^n,$$

where the $f_n(u)$'s are Laurent polynomials encoding the location of the walk at time $n$; thus we have $f_{n+1}(u) = P(u)f_n(u) + qf_n(1)$, with $f_0(u) = 1$. Multiplying both sides of this recurrence by $z^{n+1}$, and summing over $n$, one gets

$$F(z, u)(1 - zP(u)) = 1 + qzF(z, 1).$$

As $F(z, 1) = 1/(1-z)$, one obtains Formula (2.2). Note that the generating function can also be obtained by using a regular expression encoding these walks (by factorizing the walk in factors ending by a reset): $(S^*q)^*(S)^*$, which translates to

$$F(z, u) = \frac{1}{1 - qz \frac{1}{1 - zP(1)}} \frac{1}{1 - zP(u)},$$

where the occurrences of $P(1)$ and $P(u)$ reflect that only the altitudes after the last reset contribute to the final altitude of the full walk. Using $P(1) = 1-q$, we get Formula (2.2).

The mean of $Y_n$ is then obtained via $\mu_n := \mathbb{E}[Y_n] = [z^n]\partial_u F(z, 1)$, while its variance is obtained via a second-order derivative: $\mathrm{Var}[Y_n] = [z^n]\partial_u^2 F(z, 1) + \mu_n - \mu_n^2$. $\square$

<footnote n="1">¹We recall that $P(1) = 1-q$, so another convention could have been to call drift the quantity $P'(1)/(1-q)$, i.e., we would then condition on having no reset (instead of considering walks without reset, weighted by the initial model (2.1)). This alternative convention does not simplify the subsequent formulas.</footnote>
We can now establish the corresponding limit distribution.

**Theorem 2.2** (Final altitude: asymptotics). Consider walks with $0 \notin S$, $\gcd S = 1$, and $d = \max S > 0$ (these three constraints bring no loss of generality<fnref n="2" />). Therefore the support of the walk is either $\mathbb{Z}$ (with all altitudes being reachable), or $\mathbb{N}$ (with a finite set of altitudes impossible to reach, known as the unreachable set in the coin-exchange problem of Frobenius). The final altitude of these walks with resets behaves asymptotically according to these two cases.

a) For walks with $\min S \ge 0$, we have for $k \in \mathbb{N}$ (not in the Frobenius unreachable set):

$$q \cdot (\min_{i \in S} p_i)^k \le \lim_{n} \mathbb{P}(Y_n = k) \le q \cdot (\max_{i \in S} p_i)^{k/d}.$$

In particular, for Moran walks, we have $\mathbb{P}(Y_n = k) = q p^k$ for $0 \le k < n$ and $\mathbb{P}(Y_n = n) = p^n$ so $\lim_{n} Y_n = \text{Geom}(q) - 1$.

b) For walks with $\min S < 0$ and $\max S > 0$, we have for $k \in \mathbb{Z}$:

$$\mathbb{P}(Y_n = k) = qW_k(1-q) + (1-q) \frac{1}{\tau^{k+1}} \frac{1}{\sqrt{2\pi n P''(\tau)}} + O\left(\frac{1}{n}\right).$$

Moreover, both in Case a) and in Case b), $\mathbb{P}(Y_n = k)$ has a geometric decay for large $k$.

*Proof.* In Case a), we have $\min S \ge 1$; the definition of $P(u)$ in (2.1) then entails $[u^k]P(u)^j = 0$ for large $j$. The limit of Equation (2.3) thus gives

$$\lim_{n \to +\infty} \mathbb{P}(Y_n = k) = q[u^k] \sum_{j=0}^{k} P(u)^j.$$

In particular, when it is not 0, this quantity is lower bounded by $q \cdot (\min_{i \in S} p_i)^k$ and upper bounded by $q \cdot (\max_{i \in S} p_i)^{k/d}$, and therefore decreases geometrically.

In Case b), the proof is more complicated and will recycle ingredients of the asymptotics of walks without reset. To this aim, first set $\tilde{P}(u) := P(u)/P(1)$, i.e., the step set probabilities are renormalized to have global mass $\tilde{P}(1) = 1$. Let $W_k(z)$ be the probability generating function of walks without reset, i.e., $W_k(z) = [u^k] \frac{1}{1-z\tilde{P}(u)} = \sum_{n \ge 0} w_{n,k}z^n$. We then rewrite Equation (2.3) as

$$\begin{aligned}
\mathbb{P}(Y_n = k) &= P(1)^n[u^k]\tilde{P}(u)^n + q[u^k]\sum_{j=0}^{n-1} P(1)^j\tilde{P}(u)^j \\
&= (1-q)P(1)^n w_{n,k} + q\sum_{j=0}^{n} P(1)^j w_{j,k} \\
&= (1-q)P(1)^n w_{n,k} + qP(1)^n[z^n]\frac{1}{1-z/P(1)}W_k(z). \quad (2.4)
\end{aligned}$$

If $\min S < 0$ and $\max S > 0$, then there is a unique real $\tau > 0$ such that $\tilde{P}'(\tau) = 0$. It is proven in [5] that $\rho = 1/\tilde{P}(\tau)$ is the radius of convergence of $W_k(z)$ and that $w_{n,k} \sim \tau^{-k}C\tilde{P}(\tau)^n/\sqrt{2\pi n}$, where $C := \frac{1}{\tau}\sqrt{\tilde{P}(\tau)/\tilde{P}''(\tau)}$.

<footnote n="2">²There is no loss of generality. Indeed, if the walk as a periodic support (i.e., if $\gcd(S) = g$ with $g > 1$) we rescale (without loss of generality) the step set $S$ by dividing each step by $g$. Now, if $\max S < 0$, then we multiply each step by $-1$. Last, if $0 \in S$ we consider instead the equivalent model $S := S \setminus \{0\}$ and $q := q + p_0$.</footnote>
Note that, as we have a probability generating function, we have $\rho = \tilde{P}(\tau) = 1$. The asymptotics of (2.4) then follows by singularity analysis, as $1/(1 - z/P(1))$ is singular at $z = P(1) = 1 - q$, that is, before $W_k(z)$ which is singular at $z = 1$:

$$ \mathbb{P}(Y_n = k) = qW_k(1-q) + (1-q)\tau^{-k}C\frac{P(\tau)^n}{\sqrt{2\pi n}} + O\left(\frac{1}{n}\right). $$

Note that Formulas (10) and (11) in [5, Theorem 1] give a closed form for $W_k(z)$. It implies in particular

$$ 0 < W_k(1-q) < (1-q)(c+d)C_1/C_2^{|k|+1}, $$

where $C_1 > 0$ and $C_2 > 1$ are constants independent of $k$; thus $W_k(1-q)$ decays geometrically for $k \to \pm\infty$. This concludes our analysis of Case b) and gives the theorem. $\square$

These limiting behaviors are thus in sharp contrast with the asymptotic behavior of the final altitude of walks on $\mathbb{Z}$ with no resets, which is $\delta n \pm O(\sqrt{n})$, with fluctuations given by a continuous distribution (Rayleigh or Gaussian; see [5]).

## 2.2. The height $H_n$.
In order to study the height of these walks with resets, one considers the subset of them made of walks conditioned to have a height smaller than $h$. We want to obtain an explicit formula for their generating function

$$ F^{\leq h}(z, u) := \sum_{n=0}^{+\infty} \mathbb{E} \left( u^{Y_n} \prod_{\{Y_1 \leq h, Y_2 \leq h, \dots, Y_n \leq h\}} \right) z^n. $$

If these walks are generated by a step set $S$ having only positive jumps, a natural but naive approach to enumerate them would be to create a deterministic finite automaton (a finite discrete Markov chain) with $h$ states encoding the possible altitudes of the process. It leads to a system of linear equations which would allow us to get the corresponding rational generating function. However, this approach to obtain the generating function (given $h$ and the transition probabilities) suffers from three drawbacks:

* it would be of complexity $h^3$ (computing determinants of $h \times h$ matrices),

* it would be a case-by-case approach (new computations are needed for each $h$),

* it would fail if the step set $S$ has some negative steps (then the support of the walk is $[-\infty, +h]$, and thus one would need an automaton with an infinite number of states).

So, we prefer here to use a more efficient approach, which relies on a powerful method (namely, the kernel method [7]): the complexity to obtain a closed-form formula for $F^{\leq h}(z, u)$ then drops<fnref n="3" /> from $O(h^3)$ to $O(1)$ for any finite step set $S \subset \mathbb{Z}$! This leads to the following theorem.

<footnote n="3">³The PhD thesis of Louis Dumont [17] compares the cost of different methods to compute the coefficients of such generating functions (which can be related to diagonals of rational functions); the full analysis has to take into account the space and time complexities, and some precomputation steps, of cost of course higher than $O(1)$, but in all cases it is more efficient than a Markov chain approach (see however Bacher [3] for a clever use of a transfer matrix point of view).</footnote>
**Theorem 2.3.** Let $F^{\le h}(z, u)$ be the probability generating function of walks on $\mathbb{Z}$ of height $\le h$ with resets, where the length and the final altitude of the walks are respectively encoded by the exponents of $z$ and $u$. Let $P(u)$ encode the allowed jumps as in (2.1). One has

$$F^{\le h}(z, u) = \sum_{n=0}^{+\infty} \mathbb{E} \left( u^{Y_n} \prod_{\{Y_1 \le h, Y_2 \le h, \dots, Y_n \le h\}} \right) z^n = \frac{W^{\le h}(z, u)}{1 - zqW^{\le h}(z, 1)}, \quad (2.5)$$

where

$$W^{\le h}(z, u) := \frac{1 - \sum_{i=1}^{d} \left(\frac{u}{u_i}\right)^{h+1} \prod_{1 \le j \le d, j \ne i} \frac{u_j - u}{u_j - u_i}}{1 - zP(u)} \quad (2.6)$$

is the generating function of walks of height $\le h$ without reset, and where $u_1, \dots, u_d$ are the roots of $1 - zP(u) = 0$ such that $\lim_{z \to 0} |u_i(z)| = +\infty$.

**Remark 2.4** (A rational simplification). These generating functions are algebraic, as they rationally depends on the roots $u_i(z)$, which are themselves algebraic functions. Now, when the step set $S$ has only positive steps, $W^{\le h}$ is a polynomial and $F^{\le h}$ simplifies to a rational function (despite the fact that their closed forms (2.6) and (2.5) involve algebraic functions!). This simplification can be seen either by the automaton point of view and the Kleene theorem, or by using the Vieta formulas on Newton sums (as, when one has only positive jumps, the $u_i$'s are then all the roots of the kernel $1 - zP(u)$). For example, for $P(u) = u/3 + u^2/2$ and $h = 3$, we have

$$u_1(z) = \frac{-z + \sqrt{z^2 + 18z}}{3z} \quad \text{and} \quad u_2(z) = \frac{-z - \sqrt{z^2 + 18z}}{3z}$$

(the Vieta formulas are here: $u_1(z) + u_2(z) = -2/3$ and $u_1(z)u_2(z) = -2/z$); then, the quotient (2.5) involving these algebraic functions $u_1$ and $u_2$ simplifies, leading to

$$W^{\le 3}(z, u) = \frac{1}{1 - zP(u)} \left( 1 - \left( \frac{u}{u_1(z)} \right)^4 \frac{u_2(z) - u}{u_2(z) - u_1(z)} - \left( \frac{u}{u_2(z)} \right)^4 \frac{u_1(z) - u}{u_1(z) - u_2(z)} \right) \\ = 1 + z \left( \frac{u^2}{2} + \frac{u}{3} \right) + z^2 \left( \frac{u^3}{3} + \frac{u^2}{9} \right) + \frac{z^3 u^3}{27},$$

$$F^{\le 3}(z, u) = \frac{\left(1 + z\left(\frac{u^2}{2} + \frac{u}{3}\right) + z^2\left(\frac{u^3}{3} + \frac{u^2}{9}\right) + \frac{z^3 u^3}{27}\right)}{1 - zq\left(1 + \frac{5z}{6} + \frac{4z^2}{9} + \frac{z^3}{27}\right)}.$$

**Proof of Theorem 2.3.** The probability generating function can be written as

$$F^{\le h}(z, u) = \sum_{n \ge 0} f_n^{\le h}(u) z^n = \sum_{k=0}^{h} F_k^{\le h}(z) u^k,$$

where $f_n^{\le h}(u)$ encodes the possible values of $Y_n$ (constrained to be bounded by $h$ over the full process), and where

$$F_k^{\le h}(z) = \sum_{n=0}^{+\infty} f_{n,k}^{\le h} z^n = \sum_{n=0}^{+\infty} \mathbb{P} \left( Y_1 \le h, Y_2 \le h, \dots, Y_{n-1} \le h, Y_n = k \le h \right) z^n$$

is the probability generating function of bounded walks ending at altitude $k$.
The dynamics of the process then entails the recurrence

$$f_{n+1}^{\le h}(u) = P(u)f_n^{\le h}(u) - \{u^{>h}\}P(u)f_{n,h}^{\le h}u^h + qf_n^{\le h}(1),$$

where $\{u^{>h}\}$ extracts monomials having a degree in $u$ strictly larger than $h$. This mimics that at time $n+1$, either, with probability $p_k$, we increase by $k$ the altitude of where we were at time $n$ (that is, we multiply by $u^k$, and this is allowed as long as the walk stays at some altitude $\le h$, thus we removed here the cases corresponding to the walks which would reach an altitude $> h$ at time $n+1$); or, with probability $q$, we have a reset to altitude 0 (i.e., all the mass of the walks at any altitude $k$, corresponding to the coefficient of $u^k$, is sent back to $u^0$; this is thus captured by the substitution $u=1$).

This directly translates to the functional equation

$$F^{\le h}(z, u) = 1 + zP(u)F^{\le h}(z, u) - \sum_{k=0}^{d-1} F_{h-k}^{\le h}(z)u^{h-k} \left( z \sum_{j=k+1}^{d} p_j u^j \right) + zqF^{\le h}(z, 1).$$

Setting $q=0$, we get the functional equation for the generating function $W^{\le h}$ of walks of height $\le h$ without reset:

$$W^{\le h}(z, u) = 1 + zP(u)W^{\le h}(z, u) - \sum_{k=0}^{d-1} W_{h-k}^{\le h}(z)u^{h-k} \left( z \sum_{j=k+1}^{d} p_j u^j \right). \quad (2.7)$$

Of course, the factorization of walks with resets into $(S^*q)^*(S)^*$ entails $F^{\le h}(z, u) = \text{Seq}(W^{\le h}(z, 1)q)W^{\le h}(z, u)$, which is Formula (2.5). So if we find a closed form for $W^{\le h}$, we are happy as this also solves the initial problem for $F^{\le h}$. Now, on the right-hand side of (2.7), the sum for $k$ from 0 to $d-1$ is a polynomial in $u$, which we conveniently rewrite as

$$W^{\le h}(z, u)(1 - zP(u)) = 1 - u^h \sum_{k=1}^{d} G_k(z)u^k. \quad (2.8)$$

It is possible to solve such an equation via the kernel method: the kernel is the factor $1-zP(u)$ in (2.8), and if one considers the equation on the variety defined by $1-zP(u)=0$, this brings additional equations which will allow us to get a closed form for $W^{\le h}(z, u)$. First, observe that this kernel is a (Laurent) polynomial in $u$ of “positive” degree $d$. Then, from an analysis of its Newton polygon, one gets that it has $d$ roots $u_1(z), \dots, u_d(z)$ such that $u_i(z) \approx z^{-1/d}$ for $z \sim 0^+$ (the other roots being convergent at $z \sim 0^+$; see [5] for more on this issue). Thus, setting $u = u_i(z)$ (for $i=1, \dots, d$) in the functional equation (2.8) gives $d$ new equations. Some care is required in this step: we have to check that one does not create series involving an infinite number of monomials with negative exponents$^4$.

<footnote>$^4$Let $R$ be the ring of series $\sum_{n \in \mathbb{Z}} a_n z^n$. The Cauchy product of two series in $R$ is well defined only with some additional convergence conditions, and, even if we restrict ourselves to series for which the product is well defined, we have to take care to the fact that they do not form an integral ring: indeed, we have many divisors of zero (e.g. for $S(z) := \sum_{n \in \mathbb{Z}} z^n$, we have $zS = S$ and thus $(z-1)S = 0$). Most algebraic manipulations in this ring, if they are temporarily handling quantities which are not in the subring of power series (or Laurent/Puiseux/Fourier series), would lead to invalid identities in $\mathbb{C}[[z]]$.</footnote>
In fact, in our case, the substitution $u = u_i$ is legitimate as $W^{\leq h}(z, u_i)$ becomes a well-defined Puiseux series in $z$: this follows from the fact that the coefficients $f_n^{\leq h}(u)$ are (Laurent) polynomials with “positive” degree bounded by $h$ (and “negative” degree lower bounded by $-cn$), so $f_n^{\leq h}(u_i(z))$ is a Puiseux series with exponents from $-h/d$ to $+\infty$. Then, multiplying by $z^n$ and summing over $n$, only a finite number of summands contribute to each monomial of $W^{\leq h}(z, u_i)$, which is thus well defined. Via these substitutions $u = u_i$, we obtain a linear system of $d$ equations (which only contains the $G_k$'s as unknowns). Then, by Cramer's rule, we get $G_k = \det(V_k)/\det(V)$, where

$$V = \begin{pmatrix} u_1^{h+1} & u_1^{h+2} & \dots & u_1^{h+d} \\ u_2^{h+1} & u_2^{h+2} & \dots & u_2^{h+d} \\ \vdots & \vdots & \ddots & \vdots \\ u_d^{h+1} & u_d^{h+2} & \dots & u_d^{h+d} \end{pmatrix} \quad \text{and} \quad V_k = \begin{pmatrix} u_1^{h+1} & \dots & u_1^{h+k-1} & 1 & u_1^{h+k+1} & \dots & u_1^{h+d} \\ u_2^{h+1} & \dots & u_2^{h+k-1} & 1 & u_2^{h+k+1} & \dots & u_2^{h+d} \\ \vdots & \vdots & \ddots & \vdots & \vdots & \ddots & \vdots \\ u_d^{h+1} & \dots & u_d^{h+k-1} & 1 & u_d^{h+k+1} & \dots & u_d^{h+d} \end{pmatrix},$$

that is, $V_k$ is the matrix $V$ with its $k$-th column entries replaced by 1. Thus, as $V$ is a Vandermonde matrix, its determinant is

$$\det(V) = \left(\prod_{i=1}^{d} u_i^{h+1}\right) \prod_{1 \leq i < j \leq d} (u_j - u_i).$$

Now, to compute $\det(V_k)$, one first proves that

$$\Delta = \det \begin{pmatrix} u_1^1 & \dots & u_1^{k-1} & 1 & u_1^{k+1} & \dots & u_1^d \\ u_2^1 & \dots & u_2^{k-1} & 1 & u_2^{k+1} & \dots & u_2^d \\ \vdots & \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ u_d^1 & \dots & u_d^{k-1} & 1 & u_d^{k+1} & \dots & u_d^d \end{pmatrix} = e_{d-k}(u_1, \dots, u_d) \prod_{1 \le i < j \le d} (u_j - u_i), \quad (2.9)$$

where we used the classical notation for the elementary symmetric polynomials:

$$e_k(x_1, \dots, x_d) := [t^k] \prod_{i=1}^{d} (1 + t x_i), \quad (2.10)$$

e.g., $e_3(x_1, \dots, x_5) = x_1x_2x_3 + x_1x_2x_4 + x_1x_2x_5 + x_1x_3x_4 + x_1x_3x_5 + x_1x_4x_5 + x_2x_3x_4 + x_2x_3x_5 + x_2x_4x_5 + x_3x_4x_5$. Formula (2.9) follows from 2 facts:

* If $u_i = u_j$, then two rows of $V_k$ are equal and thus the determinant is 0; this explains the Vandermonde product $\Pi := \prod_{1 \le i < j \le d} (u_j - u_i)$ on the right-hand side of Formula (2.9).

* Now writing the determinant as a sum over the $d!$ permutations of the entries gives a sum of monomials, each of total degree $(1+2+\dots+d)-k$ in the $u_i$'s. $\Pi$ being of total degree $\binom{d}{2} = d(d-1)/2$, it implies that $\Delta/\Pi$ is a polynomial which is symmetric and homogeneous of total degree $d-k$. Up to a constant factor (determined to be 1, by comparing any monomial), this polynomial has to be $e_{d-k}$, which captures exactly the missing $u_i$'s in each of the $d!$ summands.

Then, performing a Laplace expansion of $\det(V_k)$ on its $k$-th column and using Formula (2.9), one gets (after simplification in the Cramer formula):

$$G_k(z) = \sum_{\ell=1}^{d} u_{\ell}^{-h-1} (-1)^{k+d} e_{d-k}(u_1, \dots, u_d)|_{u_{\ell}=0} \prod_{\substack{1 \le j \le d \\ j \ne \ell}} \frac{1}{u_{\ell} - u_j}.$$
Now, using $\sum_{k=0}^{d} (-1)^{d-k} e_{d-k}(u_1, \dots, u_d)u^k = \prod_{i=1}^{d}(u - u_i)$ (which is equivalent to the definition (2.10)), and regrouping the powers $u_k^{-h-1}$, we get

$$ \sum_{k=1}^{d} G_k(z)u^{k-1} = \sum_{k=1}^{d} u_k^{-h-1} \prod_{1 \le j \le d, j \ne k} \frac{u_j - u}{u_j - u_k}. \qquad (2.11) $$

Combining Equations (2.11) and (2.7), we get Formula (2.6) for $W^{\le h}(z, u)$, and thus the closed form for $F^{\le h}(z, u)$. $\square$

**Remark 2.5** (Link with Lagrange interpolation). As we know the evaluation of the right-hand side of (2.8) in each of the $u_k$, Formula (2.11) is also equivalent to the Lagrange interpolation formula (which we thus reproved *en passant*). Moreover, this Lagrange interpolation approach offers a nice advantage: it is circumventing the fact that the factorization argument used to get the closed forms for the generating functions in [5, 12] works only if the walks start at altitude 0.

Now, if we go back to Moran walks (i.e., for $P(u) = pu$; see Figure 1), the generating function simplifies to the following noteworthy shape.

**Corollary 2.6.** The probability generating function of Moran walks of height $\le h$ is

$$ F^{\le h}(z, u) = \frac{(1 - pz)(1 - (pzu)^{h+1})}{(1 - puz)(1 - z + (pz)^{h+1}zq)}, \qquad (2.12) $$

where, in the power series, the length and the final altitude of the walks are respectively encoded by the exponents of z and u. Accordingly,

$$ \mathbb{P}(H_n \le h) = [z^n] F^{\le h}(z, 1) = [z^n] \frac{1 - (pz)^{h+1}}{1 - z + (pz)^{h+1}zq} \qquad (2.13) $$

$$ = \sum_{k=0}^{\lfloor \frac{n}{h+1} \rfloor} (-qp^{h+1})^k \left( \binom{n-k(h+1)}{k} - p^{h+1} \binom{n-(k+1)(h+1)}{k} \right), \qquad (2.14) $$

with the convention that $\binom{m}{k} = 0$ if $m < 0$.

*Proof.* The closed form (2.14) is obtained via the power series expansion $1/(1-T) = \sum T^j$ by applying the binomial theorem to each term $T^j$, with $T = z + (pz)^{h+1}zq$. $\square$

The binomial sum (2.14) generalizes a formula obtained (for $p = 1/2$) by Pippenger in [45]. Therein, it is derived by an inclusion-exclusion principle (guided by the combinatorics of the carry propagation in binary words); for his problem, the generating function, and thus the corresponding binomial sum, are a little bit simpler than (2.13) and (2.14), and are then used to perform some real analysis for the asymptotics of the expected length.

In our case, equipped with this explicit expression for the probability generating function of Moran walks of bounded height, we can now tackle the question of the asymptotic distribution of this extremal parameter.
### 3. ASYMPTOTIC HEIGHT OF MORAN WALKS

In this section, we establish a local limit law for the distribution of the height of Moran walks. One noteworthy consequence of the generating function explicit formula that we get in the previous section is that it allows us to have very efficient computations and simulations of the process at time $n$, for large $n$, as stressed by the following remark.

*Remark 3.1* (Fast computation scheme for any given $n$ and $h$). One does not need to run the process for $n$ steps to have the exact distribution of $H_n$. Indeed, using the rational generating function from Corollary 2.6, for any $p, h$, and $n$, it is possible to get the exact value of $\mathbb{P}(H_n = h) = [z^n] (F^{\le h}(z, 1) - F^{\le h-1}(z, 1))$ in time $O(\ln(n))$ via binary exponentiation.

This allows us to plot the distribution $H_n$, for quite large values of $n$ (as an example, see Figure 3). Note that for our other generating functions, which are algebraic, there exists a fast algorithm of cost $\sqrt{n}\ln(n)$ to compute their $n$-th coefficient (this algorithm works more generally for all D-finite functions). This algorithm due to the brothers Chudnovsky is e.g. implemented in the Maple computer algebra system via the package Gfun; see [49]

<figure><img src="image_119.png" /><figcaption>FIGURE 3. The distribution of $H_n$, for $n = 2^{25}$ (for $p = 1/2$ on the left and $p = 1/4$ on the right). One observes a sharp concentration around the height 25 for $p = 1/2$ and 12.5 for $p = 1/4$, suggesting a logarithmic link in base $1/p$ between $n$ and $H_n$. We prove and refine this claim in the next pages.</figcaption></figure>

**3.1. Localization of the dominant singularity.** As $F^{\le h}(z, 1)$ (as given by Equation (2.12)) is a rational function, all its singularities are poles. The asymptotic behavior of the coefficients of $F^{\le h}(z, 1)$ is governed by the closest pole(s) to zero (also called “dominant singularities” of $F^{\le h}$). A natural candidate for being such a dominant singularity of $F^{\le h}(z, 1)$ would be $z = 1/p$, but it is in fact a removable singularity, as one has (e.g. via L'Hôpital's rule) $F^{\le h}(1/p, 1) = \frac{p^{(h+1)}}{2^{2p-1-qh}}$. Thus, we can focus on the other roots of the denominator $D(z)$ of $F^{\le h}(z, 1)$.
**Lemma 3.2** (Localization of the singularities of $F^{\le h}$). For $p \in (0, 1)$, the $h+2$ roots $z_1(h), \dots, z_{h+2}(h)$ of $D(z) = 1 - z + qp^{h+1}z^{h+2}$ are such that we have for $h$ large enough:

(i) $z_1(h)$ is the unique root strictly between 1 and $1/p$;

(ii) $z_2(h) = 1/p$ is the unique root of modulus $1/p$;

(iii) the remaining $h$ roots $z_3(h), \dots, z_{h+2}(h)$ are all of modulus $> 1/p$, and arbitrarily close (in modulus) to $1/p$ (for $h \to +\infty$);

(iv) all the roots are simple.

Accordingly, $z_1(h)$ is the dominant singularity of $F^{\le h}(z, 1)$.

*Proof.* Let $z_*(h)$ be the unique positive zero of $D'(z) = -1 + (h+2)qp^{h+1}z^{h+1}$ given by

$$z_*(h) = \frac{1}{p} \left( \frac{1}{q(h+2)} \right)^{\frac{1}{h+1}}.$$

As $z_*(h)$ tends to $\frac{1}{p}$ from the left, we thus have $0 < z_*(h) < 1/p$ for $h$ large enough. Moreover, $D(z)$ is decreasing for all $z$ in the interval $[0, z_*(h)]$ and increasing in the interval $[z_*(h), +\infty]$. As $D(1/p) = 0$, one thus has $D(z_*(h)) < 0$. And since $D(1) > 0$, the intermediate value theorem implies the existence of (at least) one zero of $D$ between 1 and $z_*(h)$. Combined with the (non)decreasing properties of $D$, this entails the unicity of this zero; let us call it $z_1(h)$. Then, Pringsheim's theorem (see e.g. [22]) asserts that $F^{\le h}$ has a real positive dominant singularity which is thus $z_1(h)$, the first real positive zero of $D$. As $F^{\le h}(z)$ is a probability generating function, all its singularities are of modulus $\ge 1$. So we have $1 < z_1(h) < z_*(h) < 1/p$ and thus proved (i).

We now prove (ii). The fact that $z_2(h) = 1/p$ is a root follows from $1 - 1/p + q/p = 0$. Is there any other root of the same modulus? If $z = \exp(i\theta)/p$ (with $\theta \in [0, 2\pi]$) would be a root of $D(z)$, then this would imply $p = \exp(i\theta) - q\exp(i(h+2)\theta)$. By the reverse triangle inequality $|x| - |y| \le |x - y|$ (with equality only if $xy = 0$ or $x/y \in \mathbb{R}^+$), this would entail $\theta = 0$.

To prove (iii), we use the following version of Rouché's theorem: if $|D - g| < |g|$ on the boundary of a disk $D$, then $D$ and $g$ have the same number of roots inside $D$. We can apply this theorem to $D$ with $g(z) := 1 - z$, for the disk $D(0, \frac{1-\epsilon}{p})$: on its boundary, one indeed has $|D(z) - g(z)| = \frac{q}{p}|pz|^{h+2} \le \frac{q}{p}|1 - \epsilon|^{h+2} < \frac{q}{p}|1 - \epsilon|^{2/q} < \frac{q-\epsilon}{p} \le |g(z)|$, where the first strict inequality holds for $h \ge 2/q$ and the next strict inequality holds for any small enough $\epsilon$ (independently of $h$), as we have then $\frac{\ln(1-\epsilon/q)}{\ln(1-\epsilon)} < 2/q$. As the constraint on $h$ is independent of $\epsilon$, letting $\epsilon \to 0$, we infer that $D$ has only one root strictly inside $D(0, \frac{1}{p})$.

Now we can also apply this theorem to $D$ with $g(z) := 1 + z^{h+2}$: on the boundary of the disk $D(0, \frac{1+\epsilon}{p})$, one indeed has, for $h$ large enough (depending on $\epsilon$),

$$|D(z) - g(z)| \le \left( \frac{1 + \epsilon}{p} \right)^{h+2} (1 - qp^{h+1}) + \frac{1 + \epsilon}{p} < \left( \frac{1 + \epsilon}{p} \right)^{h+2} - 1 \le |g(z)|,$$

where the last $-1$ is just a crude bound of the term $-\frac{q}{p}(1 + \epsilon)^{h+2} + \frac{1+\epsilon}{p}$ which converges to $-\infty$ for $h \to +\infty$. So $D$, like $g$, has $h+2$ roots inside this disk.

To prove (iv), note that the equation $D(z) = D'(z) = 0$ is forcing $z = 1 + \frac{1}{h+1}$, but $D'(1 + \frac{1}{h+1}) \to -1$ for $h \to +\infty$, therefore all the zeros are simple for $h$ large enough. $\square$

See Figure 5 on page 277 for an illustration of the location of the roots.
### 3.2. Limit distribution of the height: the discrete Gumbel distribution.
The height distribution exhibits some a priori surprising asymptotic aspects, having a flavor of number theory/Diophantine approximation. Such phenomena, however, appear for a few other probabilistic processes where some statistics could have different asymptotic behaviors depending on some resonance between $\ln p$ and $\ln q$ (see e.g. Janson [36] or Flajolet, Vallée, and Roux [21] for some examples related to tries or binary search trees). In our case, it appears that a resonance between $\ln p$ and $\ln n$ plays a role.

**Theorem 3.3 (Distribution of the height of Moran walks).** We have

$$ \mathbb{P}(H_n \le h) = \exp(-qnp^{h+1}) \left(1 + O\left(\frac{(\ln n)^3}{n}\right)\right), \qquad (3.1) $$

where the error term is uniform for $h \in [0, n]$. Accordingly, $\mathbb{P}(H_n = h)$ is unimodal, with a peak at $h = h^*(n)$, the closest integer to $c^*(n) \frac{\ln(n)}{\ln(1/p)}$, where $c^*(n) := 1 - \frac{\ln(\ln(1/p)/q^2)}{\ln(n)}$, and we have

$$ \mathbb{P}(H_n = h^*(n)) \sim p^{p/q} - p^{1/q}. $$

Moreover, the mass is sharply concentrated around $\frac{\ln n}{\ln(1/p)}$, as better seen by the following result, with a uniform error term in $k$:

$$ \mathbb{P} \left( H_n \le \left\lfloor \frac{\ln n}{\ln(1/p)} \right\rfloor + k \right) = \exp(-q\alpha(n)p^{k+1}) \left(1 + O\left(\frac{(\ln n)^3}{n}\right)\right), $$

with $\alpha(n) := p^{-\frac{\ln n}{-\ln p}}$ (where $\{x\}$ stands for the fractional part of $x$, and where $\lfloor x \rfloor$ stands for the floor function of $x$). [See Figure 3 on page 274 for an illustration of the distribution of $H_n$ and Figure 4 for the behavior of the function $\alpha(n)$.]

<figure><img src="image_120.png" /><figcaption>FIGURE 4. Plot of the function $\alpha(n) = p^{-\frac{\ln n}{-\ln p}}$ (for $p = 1/2$), which occurs in the fluctuations of the height of Moran walks (as stated in Theorem 3.3). The function $\alpha(n)$ is taking values in $[1, 1/p)$ for integers $n \ge 1$. It has a sawtooth wave shape, with frequencies getting larger and larger (with peaks at powers of $1/p$).</figcaption></figure>
Proof. In the sequel, as the context is explicit, we simply denote by $z_1, \dots, z_{h+2}$ the zeros $z_1(h), \dots, z_{h+2}(h)$ of $D(z) = 1 - z + qp^{h+1}z^{h+2}$. From Lemma 3.2, for $h$ large enough, all these zeros $z_i$ are simple; the partial fraction decomposition of $1/D$ is then

$$ \frac{1}{D(z)} = \sum_{i=1}^{h+2} \frac{1}{D'(z_i)(z-z_i)} $$

and as $D'(z_i) = -1 + (h+2)(z_i - 1)/z_i$, one thus gets

$$ \begin{aligned} F^{\le h}(z, 1) &= \frac{1 - (pz)^{h+1}}{D(z)} = \sum_{i=1}^{h+2} \frac{1 - (pz)^{h+1}}{D'(z_i)(z-z_i)} \\ &= \sum_{i=1}^{h+2} \left( \frac{1}{z_i - (z_i - 1)(h+2)} \left( \sum_{n=0}^{+\infty} z_i^{-n} z^n \right) - \frac{p^{h+1}}{z_i - (z_i - 1)(h+2)} \sum_{n=h+1}^{+\infty} z_i^{-n+h+1} z^n \right) \\ &= \sum_{i=1}^{h+2} \left( \frac{1}{z_i - (z_i - 1)(h+2)} \left( \sum_{n=0}^{h} z_i^{-n} z^n \right) + \frac{1 - (pz_i)^{h+1}}{z_i - (z_i - 1)(h+2)} \sum_{n=h+1}^{+\infty} z_i^{-n} z^n \right). \end{aligned} $$

It is combinatorially obvious that $\mathbb{P}(H_n \le h) = 1$ for all $n \le h$. So we now focus on $n > h$, for which we have, as $(pz_i)^{h+1} = \frac{z_i - 1}{qz_i}$ and $1 - \frac{z_i - 1}{qz_i} = \frac{1 - pz_i}{qz_i}$:

$$ \begin{aligned} \mathbb{P}(H_n \le h) &= [z^n] F^{\le h}(z, 1) = \sum_{i=1}^{h+2} \frac{1 - (pz_i)^{h+1}}{z_i - (z_i - 1)(h+2)} z_i^{-n} \\ &= \sum_{i=1}^{h+2} \frac{1 - pz_i}{q(1 + (1 - z_i)(h+1))} z_i^{-n-1} \\ &= Z_1(n, h) + O(hMp^{n+1}), \end{aligned} \quad (3.2) $$

where $M = \max_{i=3, \dots, h+2} \left| \frac{1 - pz_i}{q(1 + (1 - z_i)(h+1))} \right| = O(1)$ (note that the summand involving $z_2 = 1/p$ cancels), and where $Z_1(n, h) := \frac{1 - pz_1}{q[1 + (1 - z_1)(h+1)]} z_1^{-n-1}$ is the contribution coming from the pole $z_1$.

<figure><img src="image_121.png" /><figcaption>FIGURE 5. The roots of $D(z) = 1 - z + qp^{h+1}z^{h+2}$ (here, with $p = 1/3$ and $h = 51$). For large $h$, $D(z)$ has one dominant root $z_1$ just after 1, one root at $z = 1/p$, and the other roots have a slightly larger modulus, all asymptotically close to the circle $|z| = 1/p$; see Lemma 3.2.</figcaption></figure>
Set $z_1 := 1 + \varepsilon_h$. Then $D(z_1) = 1 - (1 + \varepsilon_h) + qp^{h+1} (1 + \varepsilon_h)^{h+2} = 0$, thus this implies $\varepsilon_h = qp^{h+1} (1 + \varepsilon_h)^{h+2}$; therefore we have $z_1 = 1 + \varepsilon_h = 1 + qp^{h+1} + O(hp^{2h})$. Now, for $h = h(n)$ tending to $+\infty$, this entails that the contribution $Z_1(n, h)$ of the pole $z_1$ (as given by Equation (3.2)) satisfies

$$
\begin{align*}
Z_1(n, h) &= \frac{1 - p^{h+2} + O(hp^{2h})}{1 - (h+1)qp^{h+1} + O(h^2p^{2h})} (1 + \varepsilon_h)^{-n-1} \\
&= (1 + q(h+1)p^{h+1} - p^{h+2} + O(h^2p^{2h})) \exp\left((n+1) \ln\left(\frac{1}{1+\varepsilon_h}\right)\right) \\
&= (1 + q(h+1)p^{h+1} - p^{h+2} + O(h^2p^{2h})) \exp\left(-(n+1)\varepsilon_h + \Theta((n+1)\varepsilon_h^2)\right). \tag{3.3}
\end{align*}
$$

Observe that

$$
\text{if} \quad h = c \frac{\ln(n)}{\ln(1/p)} + c' \frac{\ln(\ln(n))}{\ln(1/p)} \quad \text{then} \quad p^h = \frac{1}{n^c \ln(n)^{c'}}. \quad (3.4)
$$

(Here and in the sequel we always consider $c > 1/2$ and $c' \ge 0$. In fact, $c' > 0$ is not needed
right now, but this will be required for the asymptotics of the mean of $H_n$ in Section 4.)

For such values of $h$, the asymptotics of the first factor in Equation (3.3) is

$$
1 + q(h + 1)p^{h+1} - p^{h+2} + O(h^2 p^{2h}) = 1 + O\left(\frac{1}{n^c \ln(n)^{c'-1}}\right), \quad (3.5)
$$

and the asymptotics of the second factor in Equation (3.3) is

$$
\begin{align*}
\exp\left(-(n+1)\varepsilon_h + O((n+1)\varepsilon_h^2)\right)
  &= \exp\left(-nqp^{h+1} + O(nhp^{2h}) - \varepsilon_h + \Theta(n^{1-2c}/\ln(n)^{2c'})\right) \\
  &= \exp\left(-nqp^{h+1}\right) \left(1 + O\left(n^{1-2c}\ln(n)^{1-2c'}\right) - O(n^{-c}\ln(n)^{-c'}) + \Theta(n^{1-2c}/\ln(n)^{2c'})\right).
\end{align*}
$$

In this expansion, one now has to check which error term dominates. It is the big-oh term
with $n^{-c}$ if $c > 1$ and the big-oh with $n^{1-2c}$ if $c \le 1$. Multiplying with the asymptotic
expansion from Equation (3.5) and using the approximation (3.2), we get the following
result (in which we simplified the ln part of the error term in a non-optimal way which
will be enough for our purpose):

$$
\mathbb{P}(H_n \le h) = \exp(-nqp^{h+1}) \left(1 + O\left(\frac{\ln n}{n^{\min(c, 2c-1)}}\right)\right). \quad (3.6)
$$

Moreover, this approximation holds for all $h \in [0, n]:$ first, for $h \ll \frac{1}{2} \ln(n)/\ln(1/p)$ this follows from the fact that $\mathbb{P}(H_n \le h)$ is increasing with respect to $h$, and then for $h \gg c \ln(n)$ this follows from the bound (4.8) hereafter.

In conclusion, for $h = \lfloor \frac{\ln n}{\ln(1/p)} \rfloor + k$, for any $k$ such that $h \in [c_1 \frac{\ln n}{\ln(1/p)}, c_2 \frac{\ln n}{\ln(1/p)}]$ (with $1/2 < c_1 < c_2$), we have uniformly in $k$ (when $n \to +\infty$):

$$
\begin{align*}
\mathbb{P}(H_n \le h) &= \exp\left(-nqp^{\lfloor \frac{\ln n}{\ln(1/p)} \rfloor + k + 1}\right) \left(1 + O\left(\frac{(\ln n)^3}{n}\right)\right) \\
&= \exp\left(-qp^{-\left\{\frac{\ln n}{-\ln p}\right\} + k + 1}\right) \left(1 + O\left(\frac{(\ln n)^3}{n}\right)\right),
\end{align*}
$$

and we get Theorem 3.3 by setting $\alpha(n) := p^{-\left\{\frac{\ln n}{-\ln p}\right\}}$. $\square$

<figure><img src="image_122.png" /></figure>
If $p = q = 1/2$, we have $\alpha(n) = 2^{\{\lg(n)\}}$ (where the symbol lg stands for the binary logarithm, $\lg(x) = \log_2(x)$). This subcase of particular interest corresponds to a problem initially considered in 1946 by Burks, Goldstine, and von Neumann [13]: the study of carry propagation in computer binary arithmetic; it constitutes one of the first analyses of the cost of an algorithm! They gave crude bounds which were deeply improved by Knuth in 1978 [38]. This problem can also be seen as runs in binary words, and, as such, is analyzed by Flajolet and Sedgewick [22, Theorem V.1]. Therein, the analysis unfortunately contains a few typos which affect some of the error terms. Our proofs are incidentally fixing this issue.

These extremal parameters (runs, longest carry) are archetypal examples of problems leading to a Gumbel distribution (or a discrete version of it). This distribution indeed often appears in combinatorics as the distribution of parameters encoding a maximal value: e.g., maximum of i.i.d. geometric distributions [51], longest repetition of a pattern in lattice paths [46], runs in integer compositions [23], carry propagation in signed digit representations [30], largest part in some integer compositions, longest chain of nodes with a given parity in trees, maximum degree in some families of trees [47], the maximum protection number in simply generated trees [31]. For some of these examples, it was proven only for some specific families of structures, but there is no doubt that it holds generically. A general framework leading to such double exponential laws is given by Gourdon [26, Theorem 4] for the largest component in supercritical composition schemes (see also Bender and Gao [10]). We refer to Figure 6 for an illustration of some of these parameters.

<figure><img src="image_123.png" /><figcaption>FIGURE 6. Many combinatorial structures have some parameters which asymptotically follow a discrete Gumbel distribution.</figcaption></figure>

The Gumbel distribution is also called the “double exponential distribution”, or the “type-I generalized extreme value distribution”, and can also be expressed as a subcase of the Fisher–Tippett distribution. Let us give a formal definition.
**Definition 3.4 (Gumbel distribution).** A continuous random variable $X$ with support $[-\infty, +\infty]$ follows a Gumbel distribution (of parameters $\mu$ and $\beta$), denoted by $\text{Gumbel}(\mu, \beta)$, if

$$ \mathbb{P}(X \leq x) = \exp\left(-\exp\left(-\frac{x-\mu}{\beta}\right)\right). $$

Its mean satisfies $\mathbb{E}[X] = \mu + \gamma\beta$ (where $\gamma = 0.5772...$ is Euler's constant) and its variance satisfies $\text{Var}[X] = \frac{\pi^2}{6}\beta^2$. It is unimodal with a peak at $x = \mu$ and its median is at $x = \mu - \beta \ln(\ln(2))$.

**Definition 3.5 (Discrete Gumbel distribution).** A discrete random variable $Y$ follows a discrete Gumbel distribution of parameters $\mu$ and $\beta$, which we denote $\text{Gumbel}(\mu, \beta)^5$, if

$$ \mathbb{P}(Y \leq h) = \exp\left(-\exp\left(-\frac{h-\mu}{\beta}\right)\right), \quad \text{for all } h \in \mathbb{Z}. \qquad (3.7) $$

In particular, one can always write $Y = \lfloor X \rfloor$, where $X$ follows a continuous $\text{Gumbel}(\mu, \beta)$; note on the other side that $\lfloor X \rfloor$ follows a discrete $\text{Gumbel}(\mu - 1, \beta)$.

To obtain a nice formula for the mean and variance of a discrete Gumbel distribution remains an open problem: for example, for $Y \stackrel{d}{=} \text{Gumbel}(0, 1)$, we have

$$ \mathbb{E}[Y] = \sum_{h=-\infty}^{\infty} h (\exp(-\exp(-h)) - \exp(-\exp(-h+1))) = 1.077240905953631072609... $$

(and it takes 5 seconds to get thousands of digits, as the terms decrease doubly exponentially fast), but will anybody find a closed form for this mysterious constant? Some insight on the variance of the discrete distribution $Y$ can be obtained from the continuous distribution $X$ via the following trivial but useful bounds which hold more generally as soon as $|X-Y| < 1$:

$$ |\mathbb{E}[Y] - \mathbb{E}[X]| < 1 \quad \text{and} \quad |\text{Var}[Y] - \text{Var}[X]| < 2 + 4|\mathbb{E}[X]|. \qquad (3.8) $$

We can now restate our previous theorem in terms of this discrete Gumbel distribution.

**Corollary 3.6 (Gumbel limit law).** The sequence of random variables $\lfloor H_n - \frac{\ln(pqn)}{\ln(1/p)} \rfloor$ converges for $n \to +\infty$ (in distribution and in moments) to the discrete Gumbel(0, $\beta$) distribution with $\beta = \frac{1}{\ln(1/p)}$. Accordingly, it implies that

$$ \mathbb{E}[H_n] \sim \frac{\ln(pqn)}{\ln(1/p)} + \gamma\beta + \text{an error smaller than } 1, $$

$$ \text{Var}[H_n] \sim \frac{\pi^2}{6 \ln(p)^2} + \text{an error smaller than } 2 + 4\gamma\beta. $$

*Proof.* Consider the sequence of random variables $Y_n := [H_n - \mu_n]$. Then, the change of variable $h \mapsto h + \mu_n$ in Equation (3.1), with $\mu_n = \frac{\ln(pqn)}{\ln(1/p)}$ allows us to match $Y := \lim_n Y_n$ (where the limit is in distribution) with the discrete Gumbel defined in (3.7), for $\mu = 0$ and $\beta = \frac{1}{\ln(1/p)}$. Due to the exponentially small uniform error term in (3.1) on the support $[0, n]$ of $H_n$, we have a convergence in moments of $Y_n$ to $Y$. Then, the asymptotics of the moments follow by applying the bounds (3.8) on the link between the mean/variance of the discrete and continuous Gumbel distribution. $\square$

<footnote n="5">⁵With a slight abuse of notation, we use the same notation $\text{Gumbel}(\mu, \beta)$ for both the continuous distribution and the discrete distribution, adding the right adjective if needed to remove any ambiguity.</footnote>
These moment asymptotics already constitute a notable result (falling as a good ripe fruit!), but a very interesting phenomenon is hidden in these imprecise errors terms: some bodacious fluctuations, that we fully describe in Section 4.

### 3.3. Waiting time.
Let us end this section with an application to a natural statistic: the waiting time $\tau_h$, i.e., the number of steps spent by the random walk when it reaches a given altitude $h$ for the first time. There is an intimate relationship between height and waiting time (stated more formally in Equation (3.11) hereafter); it is thus natural that they have enumerative and asymptotic formulas of a similar nature, as better shown by the following corollary.

**Corollary 3.7.** The waiting time $\tau_h$ for reaching height $h$ satisfies

$$ \mathbb{P}(\tau_h = n) = [z^n] \frac{(1 - p z) p^h z^h}{1 - z + q p^{h-1} z^h}. \quad (3.9) $$

The distribution function of $\tau_h$ satisfies

$$ \mathbb{P}(\tau_h \le n) = 1 - \exp\left(-q\alpha(n)^2 np^h\right) + O\left(\frac{(\ln n)^3}{n}\right). \quad (3.10) $$

*Proof.* Consider a walk reaching for the first time altitude $h$ at time $n$. Cut it after each reset. It gives a sequence of factors of length $k \le h$, followed by a last factor with $h$ up steps. This translates into the combinatorial formula

$$ \mathbb{P}(\tau_h = n) = [z^n] \frac{p^h z^h}{1 - \sum_{k=1}^{h-1} p^{k-1} q z^k}, $$

which simplifies to Formula (3.9). Now, for the distribution function, instead of redoing a full analysis based on a partial fraction decomposition of this generating function, it is more convenient to use the relation

$$ \mathbb{P}(\tau_h = n) = \mathbb{P}(H_n = h \text{ and } H_{n-1} < h), \quad (3.11) $$

thus this waiting time also satisfies

$$ \mathbb{P}(\tau_h \le n) = \mathbb{P}(H_n \ge h) = 1 - \mathbb{P}(H_n \le h - 1). \quad (3.12) $$

Then, using Theorem 3.3, we also have

$$ \begin{aligned} \mathbb{P}(H_n \le h - 1) &= \mathbb{P}\left(H_n \le \left\lfloor \frac{\ln n}{\ln(1/p)} \right\rfloor + h - 1 - \left\lfloor \frac{\ln n}{\ln(1/p)} \right\rfloor\right) \\ &= \exp\left(-q\alpha(n) p^{h-\left\lfloor \frac{\ln n}{\ln(1/p)} \right\rfloor}\right) + O\left(\frac{(\ln n)^3}{n}\right) \\ &= \exp\left(-q\alpha(n)^2 p^{h+\frac{\ln n}{\ln p}}\right) + O\left(\frac{(\ln n)^3}{n}\right). \end{aligned} $$

Via Formula (3.12) linking the waiting time $\tau_h$ and the height $H_n$, this entails (3.10). $\square$

We now turn to a finer analysis of the mean and variance of $H_n$.
## 4. MEAN AND VARIANCE OF THE HEIGHT

**4.1. Fundamental properties of the Mellin transform.** In order to get a fine estimation of the average height, we use a Mellin transform, which, as we shall see, is the key tool to handle the corresponding asymptotics. We now present the needed definitions and formulas. We refer e.g. to Flajolet, Gourdon, and Dumas [19] or to the book *Analytic Combinatorics* [22, Appendix B.7] for more on the Mellin transform and numerous applications to asymptotics of harmonic sums, digital sums, and divide-and-conquer recurrences.

**Definition 4.1 (Mellin transform).** Let $f(t)$ be a continuous function defined on the positive real axis $0 < t < +\infty$. The Mellin transform $f^*$ of $f$ is the function defined by

$$f^*(s) := \int_{0}^{+\infty} f(t) t^{s-1} dt.$$

This integral exists only for $s$ such that the function $f(t)t^{s-1}$ is integrable on $(0, +\infty)$. Thus, if there exist two real numbers $a$ and $b$, such that $a > b$ and

$$f(t) = \begin{cases} O(t^a), & \text{if } t \to 0 \\ O(t^b), & \text{if } t \to +\infty, \end{cases} \qquad (4.1)$$

then the function $f^*$ is well defined for any complex number $s$ with real part such that $-a < \Re(s) < -b$; this domain is called the fundamental strip of $f^*$. Moreover, for all $c$ in this domain, if $f^*(s)$ converges uniformly to 0 for $s = c \pm i\infty$, then the function $f$ can be expressed for $t \in (0, +\infty)$ as the following inverse Mellin transform:

$$f(t) = \frac{1}{2i\pi} \int_{c-i\infty}^{c+i\infty} f^*(s) t^{-s} ds. \qquad (4.2)$$

As an example, let us consider the gamma function, which illustrates well the role of the fundamental strip (and this example will also play a role in the next pages).

**Example 4.2 (The gamma function as a Mellin transform).** The gamma function satisfies

$$\Gamma(s) = \int_{0}^{+\infty} \exp(-t) t^{s-1} dt \quad (\text{for } 0 < \Re(s) < +\infty), \\ \Gamma(s) = \int_{0}^{+\infty} (1 - \exp(-t)) t^{s-1} dt \quad (\text{for } -1 < \Re(s) < 0). \qquad (4.3)$$

An important consequence of Formula (4.2) is that, if $f$ is a meromorphic function on $\mathbb{C}$, and if $\lim_{c \to +\infty} \int_{c-i\infty}^{c+i\infty} f^*(s) t^{-s} ds = 0$, then one can push the integration contour of Formula (4.2) to the right (taking $\lim_{c \to +\infty}$) and one then collects in passing the contributions from the residue at each pole $s_k$ to the right of the fundamental strip. Now, for $t > 0$ and $a \in \mathbb{C}$, multiplying $t^{-s} = t^{-a} \sum_{\ell \ge 0} \ln(t)^\ell (a-s)^\ell / \ell!$ by the Laurent series of $f^*(s)$ at $s=s_k$, we see that $\text{Res}[f^*(s)t^{-s}, s_k]$ can be expressed<fnref n="6" /> as a sum of order($s_k$) terms, and one gets

$$f(t) = \sum_{\substack{s_k \text{ pole of } f^*(s) t^{-s} \\ \Re(s_k) \ge -b}} \text{Res}[f^*(s) t^{-s}, s_k] \\ = \sum_{s_k \text{ pole of } f^*} \sum_{\substack{j=1 \\ \Re(s_k) \ge -b}}^{\text{order}(s_k)} \text{Res}[(s - s_k)^{j-1} f^*(s), s_k] t^{-s_k} \frac{(-1)^j}{(j-1)!} (\ln t)^{j-1}. \qquad (4.4)$$

<footnote n="6">⁶The notation $\text{Res}[g(s), s_k]$ stands for the residue of $g(s)$ at $s = s_k$.</footnote>
4.2. **Average height of Moran walks.** We now state the main result of this section.

**Theorem 4.3 (Average height).** The average height of Moran walks of length $n$ is given by

$$ \mathbb{E}[H_n] = \frac{\ln n}{\ln(1/p)} - \frac{\gamma}{\ln p} - \frac{1}{2} - \frac{\ln q}{\ln p} + \frac{Q(\ln(qn))}{\ln p} + O\left(\frac{(\ln n)^4}{n}\right), \quad (4.5) $$

where $\gamma = .57721...$ is Euler's constant, and where $Q$ is an oscillating function (a Fourier series of period $\ln(1/p)$) given by

$$ Q(x) := \sum_{k \in \mathbb{Z} \setminus \{0\}} \Gamma(s_k) \exp(-s_k x) \quad \text{where } s_k := \frac{2ik\pi}{\ln p}. \quad (4.6) $$

*Remark 4.4 (Fourier series representation).* The fact that $Q$ is a Fourier series of period $\ln(1/p)$ and is real for $x \in \mathbb{R}$ is better seen via the alternative equivalent expression

$$ Q(x) = 2 \sum_{k \ge 1} \left( \Re(\Gamma(s_k)) \cos \left( \frac{2k\pi x}{\ln(p)} \right) + \Im(\Gamma(s_k)) \sin \left( \frac{2k\pi x}{\ln(p)} \right) \right), $$

where $\Re$ and $\Im$ stands for the real and imaginary parts. This is illustrated in Figure 7. *Remark 4.5 (Fourier series differentiability).* Such asymptotics involving fluctuations dictated by a Fourier series are typical of results obtained via Mellin transforms. They often appear in the asymptotic cost of divide-and-conquer algorithms, or of expressions involving digital sums, harmonic sums, or finite differences (see the work of de Bruijn, Knuth, and Rice [15, 38], or Flajolet, Gourdon, and Dumas [19]). It is sometimes also possible to get them via some real analysis (like Pippenger did [45]), or like in the seminal work of Delange [16] on the sum of digits. Note that the Delange series is nowhere differentiable, while our Fourier series is infinitely differentiable, as proven in Theorem 4.10.

<figure><img src="image_124.png" /><figcaption>FIGURE 7. The height of Moran walks involves asymptotic fluctuations encoded by a Fourier series $Q(x)$, of period $\ln(1/p)$, and weak amplitude. More precisely, it involves $Q(\ln(px))$ which thus oscillates an infinite number of times for $x \to 0^+$, and these oscillations get larger and larger for $x \to +\infty$. Moreover, $Q$ oscillates faster when $p$ tends to 1. We shall encounter later another Fourier series, $R(x)$, which shares all these properties.</figcaption></figure>
Proof of Theorem 4.3. The proof exploits the fact that the mean $\mathbb{E}[H_n]$ asymptotically behaves like $\sum_{h=0}^{+\infty} (1 - \exp(-nqp^{h+1}))$; this is proven by rewriting $\mathbb{E}[H_n]$ as follows:

$$ \mathbb{E}[H_n] = \sum_{h=0}^{n} (1 - \mathbb{P}(H_n \le h)) = \Sigma_0 + \Sigma_1 + \Sigma_2 + \Sigma_3 - \Sigma_4 + \Sigma_{\infty}, \quad (4.7) $$

with

$$ \Sigma_0 := \sum_{0 \le h < h_1} (\exp(-nqp^{h+1}) - \mathbb{P}(H_n \le h)), $$

$$ \Sigma_1 := \sum_{h_1 \le h < h_2} (\exp(-nqp^{h+1}) - \mathbb{P}(H_n \le h)), $$

$$ \Sigma_2 := \sum_{h_2 \le h < h_3} (\exp(-nqp^{h+1}) - \mathbb{P}(H_n \le h)), $$

$$ \Sigma_3 := \sum_{h_3 \le h \le n} (1 - \mathbb{P}(H_n \le h)), $$

$$ \Sigma_4 := \sum_{h=h_3}^{+\infty} (1 - \exp(-nqp^{h+1})), $$

$$ \Sigma_{\infty} := \sum_{h=0}^{+\infty} (1 - \exp(-nqp^{h+1})). $$

The key is to prove that, for some $h_1$, $h_2$, and $h_3$ adequately chosen, the sums $\Sigma_0$, $\Sigma_1$, $\Sigma_2$, $\Sigma_3$, and $\Sigma_4$ are asymptotically negligible, while the main contribution to $\mathbb{E}[H_n]$ comes from the last sum (namely, $\Sigma_{\infty}$), which we will evaluate via a Mellin transform approach.

The reader not enjoying delta-epsilon proofs could have the feeling that “cutting epsilons into 5 parts” like above is a little bit discouraging but this is the price to pay to get the $O((\ln(n)^4/n)$ error term in Formula (4.5). In fact, in Equation (4.7) for $\mathbb{E}[H_n]$, it is possible to cut the sum into only 4 parts, but then this would lead to a final weaker $O(1/\sqrt{n})$ error term.

So let's be brave and begin with $\Sigma_0$. Here, for the range $0 \le h < h_1$, with $h_1 := \frac{3 \ln(n)}{4 \ln(1/p)}$, we get

$$ \begin{aligned} |\Sigma_0| & \le h_1 \times \left( \max_{0 \le h < h_1} \left( \exp(-nqp^{h+1}) + \max_{0 \le h < h_1} \mathbb{P}(H_n \le h) \right) \right) \\ &= h_1 \times \left( \exp(-nqp^{h_1+1}) + \mathbb{P}(H_n \le h_1) \right) \\ &= h_1 \times \left( 2 \exp(-qpn^{1/4}) + O\left( \frac{(\ln n)^3}{n} \right) \right) \\ &= O\left( \frac{(\ln n)^4}{n} \right), \end{aligned} $$

where, for the second line we used that the sequences are increasing with respect to $h$, and for the third line we used Formula (3.4) for $p^h$ and the approximation of Theorem 3.3. Note that this bound for $|\Sigma_0|$ also implies the uniform bound

$$ \mathbb{P}(H_n \le h) = O\left(\frac{(\ln n)^4}{n}\right) \quad (\text{for } h < h_1). $$

Now, for $\Sigma_1$, in the range $h_1 \le h < h_2$, with $h_2 := \frac{\ln(n)}{\ln(1/p)} + \frac{\ln(\ln(n))}{\ln(1/p)}$, we rewrite $h$ as $h := (1-t)h_1 + th_2$. Such values of $h$ correspond to using $c = (t+3)/4$ and $c' = t$ in the Formula (3.4) for $p^h$.
Via the exponential bound on $H_n$ from Formula (3.6), we get

$$ \begin{aligned} |\Sigma_1| &\le (h_2 - h_1) \times \left( \max_{h_1 \le h < h_2} \left( \exp(-nqp^{h+1}) + \max_{h_1 \le h < h_2} \mathbb{P}(H_n \le h) \right) \right) \\ &\le h_2 \times \left( \exp(-nqp^{h_2+1}) + \mathbb{P}(H_n \le h_2) \right) = O((\ln n)^4/n). \end{aligned} $$

Then, for $\Sigma_2$, in the range $h_2 \le h_3$, with $h_3 := \frac{4\ln(n)}{\ln(1/p)}$, we rewrite $h$ as $h := (1-t)h_2 + th_3$. Such values of $h$ correspond to using $c = 1 + 3t$ and $c' = 1 - t$ in the Formula (3.4) for $p^h$. Via Formula (3.6), we get $|\Sigma_2| = O((\ln n)^3/n)$.

For the next sum, using the power series expansion of the exponential in Equation (3.3) (and keeping in mind that our choice of $h_3$ implies $p^{h_3} = 1/n^4$), we get

$$ \begin{aligned} \Sigma_3 &= \sum_{h=h_3}^{n} (1 - \mathbb{P}(H_n \le h)) \le (n+1-h_3)(1 - \mathbb{P}(H_n \le h_3)) \\ &\le n(1 - \exp(-(n+1)qp^{h_3+1}))(1 + o(1)) = O\left(\frac{1}{n^2}\right). \end{aligned} \quad (4.8) $$

Finally, for the sum $\Sigma_4$, we use the power series expansions of $\exp(x)$ and of $1/(1-p)$ and we get:

$$ \Sigma_4 = \sum_{h \ge h_3} (1 - \exp(-nqp^{h+1})) = \frac{nqp^{h_3+1}}{1-p} - \sum_{h \ge h_3} \sum_{k \ge 2} \frac{(-nqp^{h+1})^k}{k!} < np^{h_3+1} = O\left(\frac{1}{n^3}\right). $$

We got that $\Sigma_0$, $\Sigma_1$, $\Sigma_2$, $\Sigma_3$, and $\Sigma_4$ are $o(1)$. It remains to evaluate $\Sigma_\infty = \sum_{h \ge 0}(1 - e^{-nqp^{h+1}})$. Such a sum is typical of expressions which can be evaluated by Mellin transform techniques. To this aim, let $\phi(t) = \sum_{h \ge 0}(1 - e^{-tqp^{h+1}})$ and set $f(t) := 1 - e^{-tpq}$ and $\mu_h := p^h$, then

$$ \phi(t) = \sum_{h \ge 0} f(\mu_h t). $$

Let $\phi^*$ and $f^*$ be, respectively, the Mellin transform of the functions $\phi$ and $f$. Using Identity (4.3) given in Example 4.2, we have $f^*(s) = -(pq)^{-s}\Gamma(s)$ on its fundamental strip $-1 < \Re(s) < 0$ and, as $\phi$ is a harmonic sum, its Mellin transform is

$$ \phi^*(s) = f^*(s) \sum_{h \ge 0} \mu_h^{-s} = \frac{q^{-s}\Gamma(s)}{1 - p^s}. \quad (4.9) $$

This function extends analytically to the full complex plane, with isolated poles at the negative integers (due to poles of $\Gamma(s)$ there), and with another set of isolated poles (the roots of $p^s = 1$). These two sets of poles have $s = 0$ in common. This implies that for $\Re(s) > -1$ the poles of $\phi^*$ are

$$ \left\{ \begin{array}{ll} s_k = \frac{2ik\pi}{\ln p} & \text{for } k \in \mathbb{Z}, k \neq 0 \quad (\text{all are poles of order 1}), \\ s_0 = 0 & \text{(the only pole of order 2)}. \end{array} \right. $$

Using Formula (4.4) for the inverse Mellin transform, we obtain

$$ \begin{aligned} \phi(t) &= \operatorname{Res}[s\phi^*, 0] \ln t - \operatorname{Res}[\phi^*, 0] - \sum_{k \in \mathbb{Z} \setminus \{0\}} \operatorname{Res}[\phi^*, s_k] t^{-s_k} \\ &= \frac{\ln t}{-\ln p} - \left( \frac{\gamma}{\ln p} + \frac{1}{2} + \frac{\ln q}{\ln p} \right) + \frac{1}{\ln p} \sum_{k \in \mathbb{Z} \setminus \{0\}} \Gamma(s_k) q^{-s_k} t^{-s_k}. \end{aligned} $$

We finally get the claim of the theorem by noting that $\mathbb{E}[H_n] = \phi(n) + O\left(\frac{(\ln n)^4}{n}\right)$. $\square$
**4.3. Variance of the height of Moran walks.** We now prove that the height of Moran walks, despite a mean of order $O(\ln n)$ and a second moment of order $O((\ln n)^2)$, has a variance which involves surprising cancellations at these two orders, leading to an oscillating function of order $O(1)$ (in $n$), as implied by the following much more precise asymptotics.

**Theorem 4.6.** The variance of the height of Moran walks satisfies

$$ \mathrm{Var}[H_n] = \frac{1}{\ln(p)^2} \left( Q^2(\ln(qn)) + 2\gamma Q(\ln(qn)) + 2R(\ln(qn)) + \frac{\pi^2}{6} \right) + \frac{1}{12} + O\left( \frac{(\ln n)^5}{n} \right), $$
where $Q$ and $R$ are Fourier series of small amplitudes given by Formulas (4.6) and (4.11).

*Proof.* To obtain the variance of $H_n$ we first consider the second moment

$$ \mathbb{E}[H_n^2] = \sum_{h \ge 0} \mathbb{P}(H_n = h)h^2 = \sum_{h \ge 0} \mathbb{P}(H_n^2 > h), \quad (4.10) $$

where we know from Theorem 3.3 that the summand can be approximated by

$$ \mathbb{P}(H_n^2 > h) = 1 - \mathbb{P}(H_n \le \sqrt{h}) = 1 - \exp\left(-nqp^{\lfloor\sqrt{h}\rfloor+1}\right) + O\left(\frac{(\ln n)^3}{n}\right). $$

Then, partitioning the last sum in (4.10) into the same intervals as in Formula (4.7), we get that $\mathbb{E}[H_n^2] = \phi_{\mathrm{var}}(n) + O\left(\frac{(\ln n)^4}{n}\right)$, where $\phi_{\mathrm{var}}$ is the function defined by

$$ \phi_{\mathrm{var}}(x) = \sum_{h \ge 0} \left( 1 - \exp\left( -xqp^{\lfloor \sqrt{h} \rfloor + 1} \right) \right). $$

From the behavior of $\phi_{\mathrm{var}}(x)$ at $x = 0$ and $x = +\infty$, using the property given in (4.1), we get that the Mellin transform of $\phi_{\mathrm{var}}$ is defined on the fundamental strip $(-1, 0)$. Using the harmonic sum summation (4.9), one gets for $s$ in this strip:

$$ \phi_{\mathrm{var}}^*(s) = f^*(s) \sum_{h \ge 0} (p^{\lfloor \sqrt{h} \rfloor})^{-s} = -\Gamma(s) (pq)^{-s} \sum_{h \ge 0} (p^{\lfloor \sqrt{h} \rfloor})^{-s}. $$

Here, as we have

$$ \sum_{h \ge 0} (p^{\lfloor \sqrt{h} \rfloor})^{-s} = \sum_{n \ge 0} \sum_{h=n^2}^{(n+1)^2-1} (p^{-s})^n = \sum_{n \ge 0} (2n+1) (p^{-s})^n = \frac{1+p^{-s}}{(1-p^{-s})^2}, $$

we finally get

$$ \phi_{\mathrm{var}}^*(s) = \frac{-\Gamma(s)q^{-s}(1+p^s)}{(p^s-1)^2}. $$

What are the poles of $\phi_{\mathrm{var}}(s)$? These are $s = 0$ (a pole of order 3) and $s = s_k = 2ik\pi$ (for $k \in \mathbb{Z}, k \ne 0$, which are poles of order 2). Using Formula (4.4) for the inverse Mellin transform, one thus obtains

$$ \phi_{\mathrm{var}}(t) = \frac{\ln(t)^2}{\ln(p)^2} + \ln(t) \frac{\ln(p) + 2\ln(q) + 2\gamma - 2Q(\ln(qt))}{\ln(p)^2} \\ - \frac{\ln(p) + 2\ln(q)}{\ln(p)^2} Q(\ln(qt)) + \frac{2}{\ln(p)^2} R(\ln(qt)) \\ + \frac{1}{3} + \frac{\gamma + \ln(q)}{\ln(p)} + \frac{\pi^2/6 + \gamma^2}{\ln(p)^2} + \frac{2\gamma \ln(q) + \ln(q)^2}{\ln(p)^2}, $$
with the same $Q(x)$ as in (4.6), and where $R(x)$ is another Fourier series given by

$$R(x) = \sum_{k \in \mathbb{Z} \setminus \{0\}} \Gamma'(s_k) \exp(-s_k x). \qquad (4.11)$$

(Similarly to $Q(x)$, this Fourier series $R(x)$ is always real, as can be seen by replacing $\Gamma$ by $\Gamma'$ in Remark 4.4.)

Now that we obtained the asymptotic behavior of $\mathbb{E}[H_n^2]$, we conclude and obtain Theorem 4.6 via $\mathrm{Var}[H_n] = \mathbb{E}[H_n^2] - \mathbb{E}[H_n]^2$, where $\mathbb{E}[H_n]$ was computed in Theorem 4.3. $\square$

**4.4. Height of excursions.** Excursions are walks in $\mathbb{N}^2$ ending at altitude 0 (where, as previously, time is encoded by the $x$-axis, and altitude by the $y$-axis). As in previous sections, let $Y_n$ and $H_n$ be the final altitude and height of a walk, and let the random variable $\tilde{H}_n$ be the height of a walk of length $n$ conditioned to be an excursion, that is, $\tilde{H}_n = H_n|\{Y_n = 0\}$. For Moran walks, we get the following behavior.

**Theorem 4.7 (Distribution and moments of the height of Moran excursions).** The distribution of the height of excursions satisfies (for a uniform error term in $k$)

$$\mathbb{P}\left(\tilde{H}_n \le \left\lfloor \frac{\ln n}{\ln(1/p)} \right\rfloor + k\right) = \exp\left(-q\alpha(n-1)p^{k+1}\right) + O\left(\frac{(\ln n)^3}{n}\right),$$

with $\alpha(n) := p^{-\frac{\ln n}{\ln(1/p)}}$ (where $\{x\}$ stands for the fractional part of $x$, and where $\lfloor x \rfloor$ stands for the floor function of $x$).

Introducing temporarily the quantity $\ell_n := \ln(q(n-1))$, and with the same Fourier series $Q$ and $R$ as in Theorems 4.3 and 4.6, the average and the variance are given by

$$\mathbb{E}[\tilde{H}_n] = \frac{\ln n}{\ln(1/p)} - \frac{\gamma}{\ln p} - \frac{1}{2} - \frac{\ln q}{\ln p} + \frac{Q(\ell_n)}{\ln p} + O\left(\frac{(\ln n)^4}{n}\right),$$

$$\mathrm{Var}[\tilde{H}_n] = \frac{1}{\ln(p)^2} \left( Q^2(\ell_n) + 2\gamma Q(\ell_n) + 2R(\ell_n) + \frac{\pi^2}{6} \right) + \frac{1}{12} + O\left( \frac{(\ln n)^5}{n} \right).$$

*Proof.* As a Moran excursion necessarily ends by a reset, we have

$$\mathbb{P}(\tilde{H}_n \le h) = \mathbb{P}(H_n \le h | \{Y_n = 0\}) = q\mathbb{P}(H_{n-1} \le h) / \mathbb{P}(Y_n = 0). \qquad (4.12)$$

Thus, we have $\mathbb{P}(\tilde{H}_n \le h) = \mathbb{P}(H_{n-1} \le h)$, $\mathbb{E}[\tilde{H}_n] = \mathbb{E}[H_{n-1}]$, and $\mathrm{Var}[\tilde{H}_n] = \mathrm{Var}[H_{n-1}]$, we can therefore directly recycle the results of Theorems 3.3, 4.3, and 4.6 to get the asymptotic distribution/mean/variance.

In this recycling, some care has to be brought while performing the substitution $n \to n-1$ in the asymptotic formulas for the walks: indeed, this could impact intermediate asymptotic terms (smaller than the main asymptotic term, but larger than the error term); however, in our case, all is safe as we have

$$\frac{(\ln(n \pm 1))^m}{(n \pm 1)^{m'}} = \frac{(\ln n)^m}{n^{m'}} + O\left(\frac{(\ln n)^m}{n^{m'+1}}\right). \quad \square$$

This result is a simple consequence of the combinatorially obvious identity (4.12), so this direct link between the asymptotics of walks and excursions holds in wider generality for any model of walks with resets for which the step set $S$ contains only positive steps.
**4.5. Fourier series: bounds and infinite differentiability.** In his seminal work [38], Knuth mentions at the end of his Section 3 that if one assumes that $\ln(qn)$ is equidistributed mod 1, then the sum $Q(\ln(qn))$ is of “average 0”. Let us amend a little bit Knuth’s assertion. Indeed, Weyl’s criterion asserts that a sequence $a_n$ is equidistributed mod 1 if and only if, for any positive integer $\ell$, we have

$$ \lim_{N \to +\infty} \frac{1}{N} \sum_{n=1}^{N} \exp(2i\pi\ell a_n) = 0. $$

Considering this sum with $\ell = 1$ and $a_n = \ln(qn)$, and applying the Euler-Maclaurin formula to it, one gets that it does not converge to 0, and therefore $\ln(qn)$ is not equidistributed mod 1.

However, it is indeed true that the oscillating $Q(x)$ and $R(x)$ are of mean value zero over their period (i.e., $\int_0^{\ln(1/p)} Q(x)dx = 0$; see Figure 7 on page 283), and that $Q(\ln(qn))$ and $R(\ln(qn))$ are “almost” of mean value zero and that they possess small fluctuations. Let us give an explicit bound on their amplitude. To this aim, we first need to bound the digamma function$^7$, defined by

$$ \psi(z) := \Gamma'(z)/\Gamma(z). $$

The function $\psi$ can be seen as an analytic continuation of harmonic numbers and satisfies $\psi(t+1) = \psi(t) + 1/t$. While several bounds for $\psi(z)$ exist in the literature (see e.g. [52]), most of them are dedicated to $z \in \mathbb{R}$ (for example we have $\psi(t) < \ln(t) - 1/(2t)$ for $t > 0$), so we now establish a lemma for $z \in i\mathbb{R}$ (which we believe to be new, and which has its own interest beyond our application hereafter to bounds of Fourier series).

**Lemma 4.8** (A bound for the digamma function on the imaginary axis). For $t > 0$, we have

$$ |\psi(it)| \le \frac{1}{2} \ln(1 + t^2) + \left(\frac{\pi}{2} + 1 - \gamma\right) + \frac{1}{t}, \quad (4.13) $$

which also implies the bound

$$ |\psi(it)| \le \left( \frac{\pi}{2} + 1 - \gamma + \frac{\ln 2}{2} \right) + \left( \ln(t) \mathbb{1}_{\{t \ge 1\}} + \frac{1}{t} \right). $$

*Proof.* Using Euler’s representation of the gamma function as an infinite product, i.e.,

$$ \Gamma(z) = \frac{1}{z} \prod_{k \ge 1} \frac{(1 + 1/k)^z}{(1 + z/k)} = \frac{\exp(-\gamma z)}{z} \prod_{k \ge 1} \frac{\exp(z/k)}{1 + z/k}, $$

we get that its logarithmic derivative, $\psi(z) = \Gamma'(z)/\Gamma(z)$, satisfies, for $z \in \mathbb{C}, z \notin -\mathbb{N}$:

$$ \psi(z) = -\frac{1}{z} - \gamma + \sum_{k=1}^{+\infty} \frac{z}{k(k+z)}. $$

<footnote>$^7$This is a rather misleading name: indeed, the digamma function is traditionally denoted by the letter psi (i.e., $\psi$), while it should logically be denoted by the Greek letter digamma (i.e., $\digamma$, a letter which looks like a big $\Gamma$ stack on a small $\Gamma$, which later gave birth to the more familiar letter $F$ in the Latin alphabet). This paradox is due to the fact that Stirling, who introduced this function, did initially use the notation digamma $F$, but later authors switched the notation to $\psi$, while the initial name remained.</footnote>
We refer to [18, Section 1.1] for more details on these formulas. Now, setting $z = it$ (with $t > 0$), and regrouping the imaginary and real parts gives

$$ \psi(it) = i \left( \frac{1}{t} + \sum_{n=1}^{+\infty} \frac{t}{n^2 + t^2} \right) + \left( \sum_{n=1}^{+\infty} \frac{t^2}{n(n^2 + t^2)} - \gamma \right), $$

and thus, by the triangle inequality

$$ |\psi(it)| \le \left( \frac{1}{t} + \sum_{n=1}^{+\infty} \frac{t}{n^2 + t^2} \right) + \left( \sum_{n=1}^{+\infty} \frac{t^2}{n(n^2 + t^2)} - \gamma \right). \quad (4.14) $$

Here, note that for all $n \le u < n + 1$, we have $n^2 + t^2 \le u^2 + t^2 < (n + 1)^2 + t^2$, and thus

$$ \frac{t}{(n+1)^2 + t^2} \le \int_n^{n+1} \frac{t}{u^2 + t^2} du \le \frac{t}{n^2 + t^2}. $$

Summing for $n$ from 0 to $+\infty$, we obtain

$$ \sum_{n=1}^{+\infty} \frac{t}{n^2 + t^2} \le \sum_{n=0}^{+\infty} \int_{n}^{n+1} \frac{t}{u^2 + t^2} du = \int_{0}^{+\infty} \frac{t}{u^2 + t^2} du = \frac{\pi}{2}. $$

So the first infinite sum in (4.14) is bounded by $\pi/2$. For the second infinite sum, it is convenient to split it in the contribution from the summand for $n = 1$, which is bounded by

$$ \max_{t \ge 0} \left( \frac{t^2}{1 + t^2} \right) = 1, $$

plus the remaining part (i.e., the sum of the terms for $n \ge 2$):

$$ \sum_{n=2}^{+\infty} \frac{t^2}{n(n^2 + t^2)} \le \int_{t^{-1}}^{+\infty} \frac{1}{u(u^2 + 1)} du = \frac{1}{2} \ln(1 + t^2). $$

Plugging these two bounds in (4.14) proves our lemma. $\square$

Equipped with the previous lemma, we can now give our bounds for $Q(x)$ and $R(x)$.

**Proposition 4.9 (Uniform bounds for the oscillations).** *The oscillating functions $Q(x)$ and $R(x)$ are uniformly bounded by*

$$ \sup_{x \in \mathbb{R}^+} |Q(x)| \le \frac{\ln(p)}{\pi} \ln \exp \left( p, \frac{4}{5} \pi^2 \right), \\ \sup_{x \in \mathbb{R}^+} |R(x)| \le \frac{\ln(p)}{\pi} \left[ \ln \exp \left( p, \frac{4}{5} \pi^2 \right) + \left( \frac{\pi}{2} + 1 - \gamma - \frac{\ln(p)}{2\pi} \right) \ln \exp \left( p, \frac{114}{155} \pi^2 \right) \right], \quad (4.15) $$

where

$$ \ln \exp(p, \beta) := \ln \left( 1 - \exp \left( \frac{\beta}{\ln(p)} \right) \right). $$

*For $p = 1/2$, we have more precisely*

$$ \sup_{x \in \mathbb{R}^+} |Q(x)| = 1.090430 \cdots \times 10^{-6} \quad \text{and} \quad \sup_{x \in \mathbb{R}^+} |R(x)| = 2.987768 \cdots \times 10^{-6}. $$
Proof. Applying the triangle inequality on the definition of $Q(x)$ in (4.6), we get

$$|Q(x)| \leq \sum_{k \in \mathbb{Z} \setminus \{0\}} |\Gamma(s_k)| \times |\exp(-s_k x)| \leq 2 \sum_{k \geq 1} |\Gamma(s_k)|$$

(a quantity independent of $x$, as $|\exp(-s_k x)| = 1$). Then, using the complement formula for the gamma function, we have $\Gamma(-z)\Gamma(z) = \frac{\pi}{z\sin(\pi(z+1))}$ (for $z \notin \mathbb{Z}$). Using this relation for $z = it$ (with $t \in \mathbb{R}$) together with the relation $\bar{\Gamma}(z) = \Gamma(\bar{z})$, we infer that

$$|\Gamma(it)|^2 = \Gamma(it)\Gamma(-it) = \frac{\pi}{t \sinh(\pi t)}. \qquad (4.16)$$

Thus, for $t = \frac{2\pi}{-\ln p}$, this gives

$$\sup_{x \in \mathbb{R}^+} |Q(x)| \leq 2 \sum_{k \geq 1} \sqrt{\frac{\pi}{kt \sinh(\pi k t)}} = \sqrt{\frac{\ln(1/p)}{2}} \sum_{k \geq 1} \sqrt{\frac{1}{k \sinh(\pi k t)}}. \qquad (4.17)$$

As, for $x \geq 0$, we have $\sinh(x) \geq (1/4)x \exp(4x/5)$, we get

$$\begin{aligned} \sup_{x \in \mathbb{R}^+} |Q(x)| &\leq \sqrt{\frac{\ln(1/p)}{2}} \sum_{k \geq 1} \sqrt{\frac{1}{(1/4)\pi k^2 t \exp(4\pi k t/5)}} \\ &= \ln(1/p) \sum_{k \geq 1} \frac{1}{\pi k \exp\left(\frac{2}{5}\pi k t\right)} \end{aligned} \qquad (4.18)$$

$$= \frac{\ln(p)}{\pi} \ln \left( 1 - \exp \left( \frac{4\pi^2}{5 \ln(p)} \right) \right). \qquad (4.19)$$

Note that the more relaxed bound (4.19) is quite close to the stricter bound (4.17): e.g. for $p = 1/2$ the bound (4.17) gives the upper bound $1.090430 \cdots \times 10^{-6}$ (and one can numerically check that these first digits also constitute a lower bound), while the bound (4.19) gives the upper bound $2.49 \times 10^{-6}$.

Now, for bounding $R(x)$, we use the identity $\Gamma'(z) = \psi(z)\Gamma(z)$, with the bound (4.13) from Lemma 4.8 for $|\psi(it)|$, and the bound (4.18) for $|\Gamma(it)|$:

$$\begin{aligned} |R(x)| &\leq 2 \sum_{k \geq 1} |\Gamma'(s_k)| = 2 \sum_{k \geq 1} |\psi(s_k)| |\Gamma(s_k)| \\ &\leq \sum_{k \geq 1} \left( \frac{1}{2} \ln \left( 1 + \left( \frac{2\pi k}{\ln(p)} \right)^2 \right) + \frac{\pi}{2} + 1 - \gamma - \frac{\ln p}{2\pi k} \right) \frac{\ln(1/p)}{\pi k \exp \left( -\frac{4}{5}\pi^2 k / \ln(p) \right)}. \end{aligned} \qquad (4.20)$$

Now, it is easy to check that we have $\frac{1}{2} \ln(1 + x^2) \leq \exp(\frac{1}{31}\pi x)$ for all $x > 0$. Then, noting $t = -2\pi / \ln(p)$, we get

$$\begin{aligned} \sum_{k \geq 1} \frac{1}{2} \ln \left(1 + (kt)^2\right) \frac{\ln(1/p)}{\pi k \exp\left(\frac{2}{5}\pi k t\right)} &\leq \sum_{k \geq 1} \frac{\ln(1/p)}{\pi k \exp\left(\frac{57}{155}\pi k t\right)} \\ &= \frac{\ln(p)}{\pi} \ln \left(1 - \exp\left(\frac{114\pi^2}{155 \ln(p)}\right)\right). \end{aligned}$$

Together with the contribution of the remaining summands in (4.20), this gives the bound (4.15) for $|R(x)|$. $\square$

From this, we can establish the infinite differentiability of our fluctuations.
**Theorem 4.10** (Fourier series infinite differentiability). *The Fourier series*

$$Q(x) = \sum_{k \in \mathbb{Z} \setminus \{0\}} \Gamma(s_k) \exp(-s_k x) \quad \text{and} \quad R(x) = \sum_{k \in \mathbb{Z} \setminus \{0\}} \Gamma'(s_k) \exp(-s_k x)$$

(where $s_k = \frac{2ik\pi}{\ln p}$) are infinitely differentiable on $\mathbb{R}$.

*Proof.* A Fourier series $f(x) = \sum_{k \in \mathbb{Z}} c_k \exp(-ikx)$ satisfies the Weierstrass M-test if there exists a sequence $M_n$ such that $|c_k \exp(-ikx)| + |c_{-k} \exp(ikx)| < M_k$ (for all $x \in \mathbb{R}$) and $\sum_{k \ge 0} M_k$ converges. If $f(x)$ and $g(x) := -i \sum_{k \in \mathbb{Z}} kc_k \exp(-ikx)$ both satisfy the Weierstrass M-test, then they converge absolutely and uniformly in $\mathbb{R}$, and $f' = g$.

Thus, by successive application of this M-test, if the coefficients decay polynomially, i.e., we have $|c_{-k}| + |c_k| = O(|k|^{-d-1})$, then $f(x)$ is in $C^d$ (that is, $d$ times differentiable) and $f(x)$ is in $C^\infty$ (that is, infinitely differentiable) if its coefficients decay faster than any polynomial rate. By Equation (4.16), the coefficients $\Gamma(s_k)$ decay like $\approx \exp(-k\pi/\ln(p))$, so $Q(x)$ is in $C^\infty$. By Equation (4.20), the coefficients $\Gamma'(s_k)$ also decay like an exponential, so $R(x)$ is in $C^\infty$. $\square$

It is interesting to compare this smoothness result with the situation observed by Delange [16] in his seminal work on the sum of digits of $n$ in base $1/p$ (when $1/p$ is an integer). Therein, he proved an asymptotic behavior involving fluctuations dictated by a Fourier series, which can also be obtained by a Mellin transform approach, quite similarly to the road followed in our article. It appears that his Fourier series (already mentioned in Remark 4.5) has coefficients $\zeta(s_k)/((1+s_k)s_k) \approx k^{-1.5}$; it is thus not surprising that the Delange series is nowhere differentiable, in sharp contrast with the smoothness of our Fourier series (see Figure 8).

This concludes our analysis of the height and the corresponding fluctuations.

<figure><img src="image_125.png" /><figcaption>FIGURE 8. Our Fourier series $Q$ and $R$ are infinitely differentiable, while the Fourier series obtained by Delange is nowhere differentiable. This follows from the asymptotics of their coefficients, as explained in the proof of Theorem 4.10.</figcaption></figure>
5. SOME RESULTS FOR THE MORAN MODEL IN DIMENSION $m > 1$

5.1. Joint distribution of ages for the Moran model with $m > 1$. Moran processes are models of population evolution (or mutation transmission) where the population is of constant size (some individuals could die but are then immediately replaced by a new individual). Depending on the applications, several variants were considered in the literature starting with the seminal work of Moran himself [43, 44], up to more recent extensions (for example to spatially structured population [41]).

Motivated by the model with resets of Itoh, Mahmoud, and Takahashi [34, 35], we now define the Moran model with $m$ individuals. It is a process parametrized by some probabilities $p$ and $p_i$'s such that $p + \sum_{i=0}^{m} p_i = 1$, and which starts at time 0 with $m$ individuals of age 0. Then, at each new unit of time,

* either, with probability $p$, all survive (their age increases by 1),

* either, with probability $p_i$ (for $1 \le i \le m$), the $i$-th individual dies (it is then replaced by a new $i$-th individual of age 0), while the age of the $m-1$ surviving individuals increases by 1,

* either, with probability $p_0$, all die and are replaced by $m$ new individuals of age 0.

Now, we define the sequence of multivariate polynomials $f_n(x_1, \dots, x_m)$ (for $n \in \mathbb{N}$) by the fact that the coefficient of $x_1^{k_1} \cdots x_m^{k_m}$ in $f_n(x_1, \dots, x_m)$ is the probability that, at time $n$, the $i$-th individual has age $k_i$ (for $i = 1, \dots, m$). Accordingly, $F(t, x_1, \dots, x_m) := \sum_{n \ge 0} f_n(x_1, \dots, x_m) t^n$ is the probability generating function associated to the above Moran model, where the time is encoded by the exponent of $t$.

**Theorem 5.1.** The probability generating function of the Moran model is a rational function, and it admits the closed form

$$F(t, x_1, \dots, x_m) = \frac{\sum_{k=0}^{2^m-1} (-1)^k P_k t^k}{\Delta}, \quad (5.1)$$

where the $P_k$'s are polynomials (given in the proof) in the $x_i$'s, $p, p_i$'s, and where $\Delta$ is the following polynomial of degree $2^m$ in $t$:

$$\Delta = \prod_{I \subseteq \{1, \dots, m\}} \left( 1 - t \left( p + p_0 \left[ I = \{1, \dots, m\} \right] + \sum_{i \in I} p_i \right) \prod_{i \notin I} x_i \right).$$

*Proof.* The Moran model evolution is encoded by the following functional equation for the probability generating function $F$:

$$F(t, x_1, \dots, x_m) = 1 + tpx_1 \cdots x_m F(t, x_1, \dots, x_m) + tp_0 F(t, 1, \dots, 1) \\ + t \left( \sum_{i=1}^{m} p_i \frac{x_1 \cdots x_m}{x_i} F(t, x_1, \dots, x_m) \Big|_{x_i=1} \right), \quad (5.2)$$

where $F|_{x_i=1}$ means $F$ evaluated at $x_i = 1$.

To solve this single functional equation (which has $m+2$ unknowns$^8$), the trick is to transform it into a linear system of equations with... $2^m$ unknowns! Indeed, by substituting $x_i = 1$ (in all the possible ways) in the functional equation (5.2), we get a system of $2^m$ equations.

<footnote>$^8$We temporarily count $F(t, 1, \dots, 1)$ as unknown, even if it is obviously equal to $1/(1-t)$, as $F$ is a probability generating function.</footnote>
Then, we encode this system by a matrix $M$, where we cleverly (sic!) choose the order in which unknowns are associated to the lines/columns of $M$. Let us define this order; to this aim consider the Cartesian product $\mathcal{X} := \{1, x_1\} \times \cdots \times \{1, x_m\}$. For any pair of $m$-tuples $\mathbf{X}$ and $\mathbf{Y}$ from $\mathcal{X}$, one writes $\mathbf{X} \prec \mathbf{Y}$ if the number of 1's in $\mathbf{X}$ is less than the number of 1's in $\mathbf{Y}$, or, when they have the same number of 1's, if $\mathbf{X}$ is smaller than $\mathbf{Y}$ in the lexicographical order induced by $x_1 \prec \cdots \prec x_m \prec 1$. For example, we have $(x_1, x_2) \prec (x_1, 1) \prec (1, x_2) \prec (1, 1)$. Listing all the elements of $\mathcal{X}$ in increasing order, we get a list of $2^m$ tuples $X_1, \dots, X_{2^m}$. The matrix $M$ encoding the aforementioned system of equations is constructed such that the $i$-th line of the matrix $M$ corresponds to the unknown $F(t, X_i)$ and the $j$-th column corresponds to the unknown $F(t, X_j)$.

With this order, the matrix $M$ is an upper triangular matrix (as each of the substitution of some $x_i$'s by some 1's in Equation (5.2) leads from some tuple $\mathbf{X}$ to $m+2$ larger tuples $\mathbf{Y}$), and thus the determinant of $M$ is the product of its diagonal terms:

$$ \det M = \prod_{I \subseteq \{1, \dots, m\}} \left( 1 - t \left( p + p_0 \left[ I = \{1, \dots, m\} \right] \right) + \sum_{i \in I} p_i \prod_{i \notin I} x_i \right), $$

where we use Iverson's bracket notation<fnref n="9" />.

As this determinant $\Delta := \det M$ is not zero, this entails by Cramer's rule that $F(t, x_1, \dots, x_m)$ can be written as a rational function with denominator $\Delta$ (note that, for some specific real values of $p$ and the $p_i$'s, it is not excluded that the numerator could have a shared factor with $\Delta$). Of course, computing the determinant of each comatrix, and using the relation $p_0 = 1 - (p + p_1 + \cdots + p_m)$, we get symmetric polynomial expressions for the $P_k$'s occurring in (5.1), e.g.:

$$ P_0 = 1, $$

$$ P_1 = p \left( \prod_{i=1}^{m} (1 + x_i) - \prod_{i=1}^{m} x_i \right) + \sum_{i=1}^{m} x_i \sum_{\substack{j=1, \dots, m \\ j \neq i}} p_j, $$

∴

$$ P_{2^m-1} = \left( \prod_{i=1}^{m} x_i^m \right) \prod_{I \subseteq \{1, \dots, m\}} \left( p + \sum_{i \in I} p_i \right). \quad \square $$

Note that the case $p_0 = 0$, $p_i = 1/m$ for $i = 1, \dots, m$ (with $m \ge 2$) was analyzed by Itoh and Mahmoud [34]: they proved that the age of each individual converges to a shifted geometric distribution, namely $\text{Geom}(1/m) - 1$. They also show that the number of individuals of age $k$ at time $n$ converges to a Bernoulli distribution, namely $\text{Ber}((m/(m-1))^k)$. Our Theorem 5.1 constitutes a joint law version of these results, at discrete times, for generic $p_i$'s. For example, introducing $G(t, v) := \sum_{j=1}^{m} \binom{m}{j} v^j [x_1^k \dots x_j^k] F(t, x_1, \dots, x_m)$, the coefficient $[t^n]\partial_v G(t, 1)$ gives the average number of individuals of age $k$ at time $n$. (Note that the sum with the binomial coefficients $\binom{m}{j}$ has to be replaced by a sum over the subsets of $\{1, \dots, m\}$ if the $p_i$'s and the initial conditions for the $x'_i$s are not symmetric.)

<footnote n="9">⁹This notation, [[assertion]], is 1 if the assertion is true, and 0 if not. It was introduced in the semantics of the language APL by its founder, Kenneth Iverson. It was later popularized in mathematics by Graham, Knuth, and Patashnik [27].</footnote>
**5.2. A multidimensional generalization of the Moran model.** Interestingly, the same strategy of proof allows us to solve a wide generalization of the Moran model, where

• with probability $p_I$, all the individuals from the subset $I$ of $\{1, \dots, m\}$ die (they are then replaced by new individuals of age 0), while the age of each surviving individual increases by 1.

• the process starts with $m$ individuals of any (possibly distinct) ages, encoded by a monomial $f_0(x_1, \dots, x_m)$.

This translates to the following single functional equation, involving $2^m$ unknowns:

$$F(t, x_1, \dots, x_m) = f_0(x_1, \dots, x_m) + t \sum_{I \in \{1, \dots, m\}} p_I F(t, \mathbf{X}_I) \prod_{i \notin I} x_i,$$

where $\mathbf{X}_I = (x_1, \dots, x_m)_{|x_i = 1 \text{ for all } i \in I}$.

Obviously, by taking $f_0 = 1$, $p_\emptyset = p$, $p_{\{1, \dots, m\}} = p_0$, $p_{\{i\}} = p_i$, and all other $p_I = 0$, the generalized model simplifies to the classical Moran model of Theorem 5.1. Another natural set of probabilities is $p_I = q^k(1-q)^{m-k}$, where $k$ is the number of elements in $I$. It encodes the model where, at each unit of time, each individual dies with probability $q$. More generally, for any set of $p_I$'s, one gets the following result.

**Theorem 5.2.** *The probability generating function of the generalized Moran model is a rational function:*

$$F(t, x_1, \dots, x_m) = \frac{\sum_{k=0}^{2^m-1} (-1)^k Q_k t^k}{\Delta}, \quad (5.3)$$

where the $Q_k$'s are polynomials in the $x_i$'s and $p_I$'s for $I \subset \{1, \dots, m\}$, and where $\Delta$ is the following polynomial of degree $2^m$ in $t$:

$$\Delta = \prod_{I \subseteq \{1, \dots, m\}} \left( 1 - t \left( p_{\emptyset} + p_{\{1, \dots, m\}} [I = \{1, \dots, m\}] + \sum_{i \in I} p_{\{i\}} \right) \prod_{i \notin I} x_i \right).$$

Note that, for this generalized model, the denominator $\Delta$ is the same as in Theorem 5.1, and the $Q_k$'s are a lifting of the $P_k$'s from Theorem 5.1, involving more terms and variables (namely, all the $p_I$'s). For these two models, these polynomials $P_k$ and $Q_k$ are variants of symmetric functions. We comment more on this fact now.

**Remark 5.3** (Links with bi-indexed families of symmetric functions). Many problems related to lattice paths lead to generating functions expressible in terms of symmetric functions; this results from the kernel method, which involves a Vandermonde-like determinant, and thus leads to variants of Schur functions [4, 6, 11]. For the generalized Moran model we also get symmetric expressions, as the problem is by design symmetric, but in a more subtle way: one does not get formulas nicely expressible in terms of classical symmetric functions. This is due to the fact that we have to play with two distinct sets of variables (the $p_i$'s and the $x_i$'s), the occurrences of which are not fully independent. It appears that these subtle dependencies are well encoded by the *MacMahon elementary symmetric functions*, defined by $e_{j,k} := [t_x^j t_p^k] \prod_{i=1}^m (1+t_x x_i + t_p p_i)$. For example, we have $e_{2,1} = x_1 x_2 p_3 + x_2 x_3 p_1 + x_3 x_1 p_2$. They allow us to provide more compact formulas for our generating functions, like $P_1 = e_{1,1} + p \sum_{j=1}^m e_{j,0}$. We plan to study these aspects in a forthcoming work. Note that these MacMahon symmetric functions also appear in problems a priori unrelated to our multidimensional Moran walks, see e.g. the articles of Gessel [25] and Rosas [48].
**5.3. Application to the soliton wave model.** The soliton wave model (as considered by Itoh, Mahmoud, and Takahashi [35]) is a stochastic system of particles encoding a unidirectional wave. The number of particles is constant during the full process: we have $m$ particles on $\mathbb{Z}$ which can only moves to the left as follows. At time $n = 0$, the initial configuration consists of $m$ particles, at $x$-coordinates $1, \dots, m$. Then, at each unit of time $n = 1, 2, \dots$, uniformly at random, one of the $m$ particles jumps just to the left of the first particle (the wave front), thus leaving an empty space at its starting position:

<figure><img src="image_126.png" /></figure>

Note that at time $n$ the location of the leftmost particle has thus $x$-coordinate $1-n$. See Figure 9 for an illustration of 6 iterations of this process, where, for drawing convenience, we shift the origin of the $x$-axis after each step, so that the first particle is always at $x$-coordinate 1.

Then, applying Theorem 5.2 to this model, we get the following proposition.

**Proposition 5.4.** The joint distribution $F(t, x_1, \dots, x_m)$ of the time/positions of the particles in the soliton wave model is given by Formula (5.3), by taking as initial condition $f_0 = x_1^1 x_2^2 \dots x_m^m$, and, as probabilities of transition, $p_{\{i\}} = 1/m$ and all other $p_I = 0$; what is more, the denominator of $F(t, x_1, \dots, x_m)$ thus simplifies to

$$ \Delta = \prod_{I \subseteq \{1, \dots, m\}} \left(1 - t \frac{|I|}{m}\right) \prod_{i \notin I} x_i, $$

where $|I|$ stands for the number of elements of the set $I$.

<table><caption>FIGURE 9. The soliton wave model: a wave is a sequence of particles (the sequence may have some inner holes), and at each unit of time, one particle is selected and jumps at the very start of the wave (and thus leaves an empty slot where it was). Trailing empty slots are ignored (this occurs when the last particle is selected, e.g. from step 3 to 4 above).</caption><thead><tr><th>Wave</th><th>Time n</th><th>Length L<sub>n</sub></th></tr></thead><tbody><tr><td></td><td>0</td><td>4</td></tr><tr><td></td><td>1</td><td>5</td></tr><tr><td></td><td>2</td><td>6</td></tr><tr><td></td><td>3</td><td>6</td></tr><tr><td></td><td>4</td><td>4</td></tr><tr><td></td><td>5</td><td>5</td></tr><tr><td></td><td>6</td><td>6</td></tr></tbody></table>
Figure 9 also shows that this model has one degree of freedom, that is, the soliton wave model with $m$ particles can be modeled as $m-1$ interactive urns $U_1, \dots, U_{m-1}$: the urn $U_k$ contains the number of white cells between the $k$-th and $(k+1)$-th blue particle. Accordingly, this interactive urn process starts with $U_k(0) = 0$ for all $k$, and then, at each unit of time, we have one of the following $m$ events (with probability $1/m$):

* $U_1(n+1) = U_1(n) + 1$ and other urns are unchanged.

* for $k = 2, \dots, m-1$: $U_1(n+1) = 0$, $U_j(n+1) := U_{j-1}(n)$ (for $j = 2, \dots, k-1$), $U_k(n+1) := U_{k-1}(n) + U_k(n) + 1$, and remaining urns are unchanged.

* $U_1(n+1) = 0$ and, for $k \ge 2$, $U_k(n+1) := U_{k-1}(n)$.

The length of the soliton is then given by $L_n = m + U_1(n) + \dots + U_{m-1}(n)$; it can equivalently be viewed as the maximum of the $x$-coordinates (at time $n$) of each particle.

## 6. CONCLUSION AND FUTURE WORKS

In this article, we considered several statistics (final altitude, waiting time, height) associated to walks with resets, for any given finite step set. For the case of the simplest non-trivial model (namely, for Moran walks), we prove that the asymptotic height exhibits some subtle behavior related to the discrete Gumbel distribution. In a forthcoming article, we plan to consider the asymptotic analysis of the height for more general walks.

In our formulas for walks of length $n$, taking $q' := q/n$ (and more generally $q' = q(n)$) as the probability of reset leads to models which can counterbalance the infinite negative drift of the initial model, and thus present a different type of asymptotic behavior. Studying these models and their phase transitions in more detail would be interesting.

In Section 5, we considered several multidimensional extensions of such walks, with applications to the soliton wave model, or to models in genetics. More multidimensional variants of Moran models allowing both positive and negative jumps (and with or without resets) can be handled using the approach presented in this article (see [1]). One interesting example is the one where each dimension evolves like a Motzkin path, this model was e.g. considered in the haploid Moran model [32], where the authors use a Markov chain approach, using duality/reversibility to establish links with Ornstein-Uhlenbeck processes. Note that even if one adds resets to such Motzkin-like models, one keeps nice links with continuous fractions associated to birth and death processes; see [20]. The analysis becomes much more complicated as soon as jumps of amplitude $\ge 2$ are allowed; in such cases, our approach based on the kernel method strikes again.

Another natural extension is to consider walks in the quarter plane with resets (a natural model of two queues evolving in parallel); even for walks with jumps of amplitude 1, the exact enumeration and the asymptotic behavior of the (maximal) height remain open. Other more ad hoc extensions consider some age-dependent probabilities $p_i$'s, then leading to partial differential equations for the corresponding generating functions. Some specific cases lead to closed-form solutions.

All these variants of Moran models are parametrized by the $p_i$'s. One can then turn to the tuning of several statistical tests: having some experimental data, it is natural to look for maximum likelihood estimators of the $p_i$'s, and to study if they are unbiased, sufficient, and consistent (for more on these notions, see e.g. [50]). In conclusion, the Moran model offers a large variety of interesting models, with many aspects to explore!
**Acknowledgement:** The work of the first author is supported by the Researchers Supporting Project RSPD2023R987 of King Saud University. We thank Hosam Mahmoud for introducing us to the Moran walks, and asking us about the distribution of their height. We are indebted to Rosa Orellana and Mike Zabrowski for pinpointing us that our bi-indexed symmetric functions of Remark 5.3 occur in the literature under the name *MacMahon symmetric functions*. Last but not least, we also deeply thank the two referees for their kind detailed reports, which helped to improve several parts of this article.

## REFERENCES

[1] Asma Althagafi. *Maximum Age Attained by a Moran Population and Some Applications*. PhD thesis, King Saud University, 2023.

[2] Stephen F. Altschul and Samuel Karlin. Methods for assessing the statistical significance of molecular sequence features by using general scoring schemes. *Proc. Natl. Acad. Sci. USA*, 87:2264–2268, 1990.

[3] Axel Bacher. Generalized Dyck paths of bounded height. *Sém. Lothar. Combin.*, 2023 (to appear).

[4] Cyril Banderier. *Combinatoire analytique des chemins et des cartes*. PhD thesis, Univ. Paris VI, 2001.

[5] Cyril Banderier and Philippe Flajolet. Basic analytic combinatorics of directed lattice paths. *Theor. Comput. Sci.*, 281(1-2):37–80, 2002.

[6] Cyril Banderier, Marie-Louise Lackner, and Michael Wallner. Latticepathology and symmetric functions. In *Proceedings of AofA’2020*, volume 159, pages 21:1–21:16. Leibniz International Proceedings in Informatics (LIPIcs), 2020.

[7] Cyril Banderier and Pierre Nicodème. Bounded discrete walks. *Discrete Math. Theor. Comput. Sci.*, AM:35–48, 2010.

[8] Cyril Banderier and Michael Wallner. Lattice paths with catastrophes. *Discrete Math. Theor. Comput. Sci.*, 19(1):32, 2017. Id/No 23.

[9] Iddo Ben-Ari, Alexander Roitershtein, and Rinaldo B. Schinazi. A random walk with catastrophes. *Electron. J. Probab.*, 24:21, 2019. Id/No 28.

[10] Edward A. Bender and Zhicheng Gao. Part sizes of smooth supercritical compositional structures. *Comb. Probab. Comput.*, 23(5):686–716, 2014.

[11] Mireille Bousquet-Mélou. Discrete excursions. *Sém. Lothar. Combin.*, 57:23 pp., 2008.

[12] Mireille Bousquet-Mélou and Marko Petkovšek. Linear recurrences with constant coefficients: the multivariate case. *Discrete Math.*, 225(1-3):51–75, 2000.

[13] Arthur W. Burks, Herman H. Goldstine, and John von Neumann. Preliminary discussion of the logical design of an electronic computing instrument. *Report to U.S. Army Ordnance Department*, 1946. Reprinted in “Collected Works of John von Neumann”, vol. 5, pp. 34–79, The Macmillan Company, 1963.

[14] Iva Chang, Alan Krinik, and Randall J. Swift. Birth-multiple catastrophe processes. *Journal of Statistical Planning and Inference*, 137(5):1544–1559, 2007.

[15] Nicolaas Govert de Bruijn, Donald E. Knuth, and Stephen O. Rice. The average height of planted plane trees. In R. C. Read, editor, *Graph Theory and Computing*, pages 15–22. Academic Press, 1972.

[16] Hubert Delange. Sur la fonction sommatoire de la fonction 'somme des chiffres'. *Enseign. Math. (2)*, 21:31–47, 1975.

[17] Louis Dumont. *Algorithmes rapides pour le calcul symbolique de certaines intégrales de contour à paramètre*. PhD thesis, Univ. Paris Saclay, 2016.

[18] Arthur Erdélyi, W. Magnus, F. Oberhettinger, and Francesco G. Tricomi. *Higher transcendental functions. Vol. I*. McGraw-Hill Book Co., 1953. Bateman Manuscript Project.

[19] Philippe Flajolet, Xavier Gourdon, and Philippe Dumas. Mellin transforms and asymptotics: Harmonic sums. *Theor. Comput. Sci.*, 144(1-2):3–58, 1995.

[20] Philippe Flajolet and Fabrice Guillemin. The formal theory of birth-and-death processes, lattice path combinatorics and continued fractions. *Advances in Applied Probability*, 32(3):750–778, 2000.
[21] Philippe Flajolet, Mathieu Roux, and Brigitte Vallée. Digital trees and memoryless sources: from arithmetics to analysis. *Discrete Math. Theor. Comput. Sci.*, AM:233–260, 2010.

[22] Philippe Flajolet and Robert Sedgewick. *Analytic Combinatorics*. Cambridge University Press, 2009.

[23] Ayla Gafni. Longest run of equal parts in a random integer composition. *Discrete Math.*, 338(2):236–247, 2015.

[24] Ilya B. Gertsbakh. *Statistical Reliability Theory*. Marcel Dekker, Inc., 1989.

[25] Ira M. Gessel. Enumerative applications of symmetric functions. *Sém. Lothar. Combin.*, B17a:17 pp., 1987.

[26] Xavier Gourdon. Largest component in random combinatorial structures. *Discrete Math.*, 180(1-3):185–209, 1998.

[27] Ronald L. Graham, Donald E. Knuth, and Oren Patashnik. *Concrete Mathematics. A Foundation for Computer Science*. Addison-Wesley, 1994. Second edition (1st ed: 1988).

[28] Jan Grandell. *Aspects of Risk Theory*. Springer, 1991.

[29] Rosemary J. Harris and Hugo Touchette. Phase transitions in large deviations of reset processes. *J. Phys. A*, 50(10):10LT01, 13, 2017.

[30] Clemens Heuberger and Helmut Prodinger. Carry propagation in signed digit representations. *Eur. J. Comb.*, 24(3):293–320, 2003.

[31] Clemens Heuberger, Sarah Selkirk, and Stephan Wagner. The distribution of the maximum protection number in random trees. *arXiv*, 2023.

[32] Thierry Huillet and Martin Möhle. Duality and asymptotics for a class of nonneutral discrete Moran models. *J. Appl. Probab.*, 46(3):866–893, 2009.

[33] Blake Hunter, Alan Krinik, Chau Nguyen, Jennifer M. Switkes, and Hubertus F. Von Bremen. Gambler’s ruin with catastrophes and windfalls. *Journal of Statistical Theory and Practice*, 2008.

[34] Yoshiaki Itoh and Hosam M. Mahmoud. Age statistics in the Moran population model. *Stat. Probab. Lett.*, 74(1):21–30, 2005.

[35] Yoshiaki Itoh, Hosam M. Mahmoud, and Daisuke Takahashi. A stochastic model for solitons. *Random Struct. Algorithms*, 24(1):51–64, 2004.

[36] Svante Janson. Renewal theory in the analysis of tries and strings. *Theor. Comput. Sci.*, 416:33–54, 2012.

[37] Boris S. Kerner. *Introduction to Modern Traffic Flow Theory and Control. The Long Road to Three-Phase Traffic Theory*. Springer, 2009.

[38] Donald E. Knuth. The average time for carry propagation. *Nederl. Akad. Wet., Proc., Ser. A*, 81:238–242, 1978.

[39] Donald E. Knuth. *The Art of Computer Programming. Vol. 3: Sorting and searching*. Addison-Wesley, 1997 (2nd edition, 1st edition in 1973).

[40] Lukasz Kusmierz, Satya N. Majumdar, Sanjib Sabhapandit, and Grégory Schehr. First order transition for the optimal search time of Lévy flights with resetting. *Phys. Rev. Lett.*, 113:220602, 2014.

[41] Erez Lieberman, Christoph Hauert, and Martin A. Nowak. Evolutionary dynamics on graphs. *Nature*, 433(7023):312–316, 2005.

[42] Satya N. Majumdar, Sanjib Sabhapandit, and Grégory Schehr. Random walk with random resetting to the maximum position. *Phys. Rev. E*, 92(5):052126, 13, 2015.

[43] Patrick A. P. Moran. Random processes in genetics. *Proc. Camb. Philos. Soc.*, 54:60–71, 1958.

[44] Patrick A. P. Moran. *The Statistical Processes of Evolutionary Theory*. Oxford University Press, 1962.

[45] Nicholas Pippenger. Analysis of carry propagation in addition: an elementary approach. *J. Algorithms*, 42(2):317–333, 2002.

[46] Helmut Prodinger and Stephan Wagner. Minimal and maximal plateau lengths in Motzkin paths. *Discrete Math. Theor. Comput. Sci.*, AH:353–362, 2007.

[47] Helmut Prodinger and Stephan Wagner. Bootstrapping and double-exponential limit laws. *Discrete Math. Theor. Comput. Sci.*, 17(1):123–144, 2015.

[48] Mercedes H. Rosas. MacMahon symmetric functions, the partition lattice, and Young subgroups. *J. Comb. Theory, A*, 96(2):326–340, 2001.
[49] Bruno Salvy and Paul Zimmermann. GFUN: A Maple package for the manipulation of generating and holonomic functions in one variable. *ACM Trans. Math. Softw.*, 20(2):163–177, 1994.

[50] Aris Spanos. *Probability Theory and Statistical Inference. Empirical Modeling with Observational Data*. Cambridge University Press, 2019.

[51] Wojciech Szpankowski and Vernon Rego. Yet another application of a binomial recurrence. Order statistics. *Computing*, 43(4):401–410, 1990.

[52] Zhen-Hang Yang, Yu-Ming Chu, and Xiao-Hui Zhang. Sharp bounds for psi function. *Appl. Math. Comput.*, 268:1055–1063, 2015.
Cyril Banderier, Christian Krattenthaler, Michael Wallner, *Editors*.

**Lattice Path Combinatorics and Interactions**

Lattice paths are a fundamental concept in combinatorics, providing a geometric perspective on many counting problems. By mapping problems onto a lattice, mathematicians can exploit symmetry, recursion, and combinatorial identities to derive elegant solutions. Lattice paths are also interesting *per se*, serving as a powerful tool to model scenarios ranging from simple random walks to more intricate probability processes. Their study opens up new avenues for understanding many combinatorial structures, capturing universal phenomena such as limit laws and limiting objects.

This volume contains twelve contributions of experts on different aspects of lattice paths. It covers the analysis of several parameters (height, area, peaks, ascents, ...), paths with different step sets, paths constrained to be in some domains. All these contributions illustrate a variety of methods, such as approaches from bijective and enumerative combinatorics, the kernel method for solving functional equations, analytic combinatorics to establish asymptotic behaviors, differential Galois theory to prove the transcendence of generating functions, non-commutative operators to enumerate walk parameters, *q*-analogues, special functions, and continued fractions.

This volume also provides links to probability theory, queueing theory, computer algebra, and illustrates interactions with models coming from physics (statistical mechanics), biology (population genetics), or computer science (analysis of algorithms).

*Contributors:*

R. Aguech

A. Althagafi

D. W. Ash

C. Banderier

A. Blecher

T. Dreyfus

S. Elizalde

R. Flórez

R. Garbit

A. J. Guttmann

J. S. Kim

A. Knopfmacher

V. Kotěšovec

C. Krattenthaler

T. Mansour

S. Ouvry

A. Polychronakos

H. Prodinger

J. L. Ramírez

K. Raschel

D. Stanton

M. Vamvakari

F. A. Velandia

D. Villamizar

M. Wallner

ISBN: 979-8-868-34062-8

<figure><img src="image_127.png" /></figure>