# The golf model on Z'nZ and on Z

Zoé Varin

► To cite this version:

Zoé Varin. The golf model on Z'nZ and on Z. Electronic Journal of Probability, 2025, 30, 10.1214/25-EJP1298. hal-05138605

HAL Id: hal-05138605

https://hal.science/hal-05138605v1

Submitted on 1 Jul 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

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

Distributed under a Creative Commons Attribution 4.0 International License
# The golf model on $Z/nZ$ and on $Z$

Zoé Varin*

July 1, 2025

## Abstract

We introduce a particle model, which we call the *golf model*. Initially, on a graph $G$, balls and holes are placed at random on some distinct vertices. The balls then move one by one, doing a random walk on $G$, starting from their initial vertex and stopping at the first empty hole they encounter, which they fill. On finite graphs, under reasonable assumptions (if there are more holes than balls, and if the Markov chain characterizing the random walks is irreducible), a final configuration is reached almost surely. In this paper, we are mainly interested in $\mathbf{H}^1$, the set of remaining holes. We give the distribution of $\mathbf{H}^1$ on $Z/nZ$, and describe a phase transition for the largest distance between two consecutive holes when the number of remaining holes is of order $\sqrt{n}$. We show that the model on $Z$ is well-defined if each vertex contains either a ball with probability $d_b$, a hole with probability $d_h$, or nothing, independently of the other vertices, as long as $d_b \le d_h$, and we describe the law of $\mathbf{H}^1$ in this case.

# 1 Introduction

## 1.1 Foreword

In this paper, we define an interacting particle system called the golf model. It is defined on a connected graph $G$ (in the paper, $G$ is mainly $Z/nZ$ or $\mathbb{Z}$) which initially contains balls and free holes at distinct vertices. Each ball is given a random clock uniformly distributed over $[0, 1]$. When its clock rings (at time $t$), a ball located at some vertex $u$ at time 0 is randomly played by a clumsy player until it falls into a free hole $v$; it then remains in this hole until the end of the process (at time 1); at time $t$, the vertices $u$ and $v$ become neutral vertices, i.e. vertices without any free hole or ball (all steps of a ball's displacement are considered instantaneous, and correspond in distribution to an irreducible Markov chain on the graph).

On $Z/nZ$, this model is close to the parking model, for which the “block size process” has been studied intensively (it is the process of the distances between consecutive free parking spaces). In particular, a phase transition for this process has been established by Chassaing-Louchard [CL02] (we discuss this in more detail in Section 1.4).

In this paper, we mainly study two models: the golf model on $Z/nZ$ and on $\mathbb{Z}$.

On $Z/nZ$, this model is trivially well-defined; we are interested in $\mathbf{H}^1$, the set of free holes at time 1. We characterize the distribution of $\mathbf{H}^1$ (Theorem 1.2) and, equivalently, the joint distribution of the distances between consecutive holes (which we call the block sizes, and which play a similar role to the sizes between consecutive parking spaces in the parking model).

Computing the distribution of $\mathbf{H}^1$ reveals the algebraic structure of the block distribution, which turns out to be crucial for making combinatorial connections with models

<footnote>*Univ. Bordeaux, CNRS, Bordeaux INP, LaBRI, UMR 5800, F-33400 Talence, France</footnote>
of random forests, and for obtaining asymptotic results for the block sizes (as $n$ goes to infinity). In particular, we identify a phase transition for the distribution of the largest block sizes (see Theorem 1.3): when the number of free holes at time 1 is of order $\sqrt{n}$, the largest block sizes are of order $n$.

We can also define a golf process with balls that have more general moving strategies (instead of doing a random walk, they can, for example, choose to go to the right or to the left, depending on the parity of the distance to the first free hole on the right). Since the proofs are simpler to state for the golf process, and generalize straightforwardly to these variants, for pedagogical reasons, we give the results and the proofs for the golf process, and then explain in Section 1.6.1 how we can generalize these results.

We then study the golf model on $\mathbb{Z}$, this time defined by independently choosing the state of each vertex to be a hole with probability $d_h$ or a ball with probability $d_b$. Since, an infinite number of balls have moved before any time $t > 0$, an argument is needed to prove that the golf model is well-defined on $\mathbb{Z}$ (see the beginning Section 1.5). Finally, we compute the distribution of $\mathbf{H}^1$ on $\mathbb{Z}$ (see Theorem 1.8), using some of the results on $\mathbb{Z}/n\mathbb{Z}$.

## 1.2 Definition of the model

All along the paper, $G = (V, E)$ is a connected graph, with a finite or countable set of vertices $V$, and $P$ is the transition matrix of an irreducible and recurrent Markov chain on $G$ (that is, $P = (P_{u,v}, u, v \in V)$ and $P_{u,v} > 0$ implies that $\{u, v\}$ belongs to the edge set $E$). We call $P$-Random Walk a Markov chain with kernel $P$.

We define a random process $\eta = (\eta^t)_{t \in [0,1]}$, which we call a golf process, and which models the evolution of a particle system as time passes from 0 to 1. It is a process defined on $G$, with two distinct sources of randomness: the initial configuration $\eta^0$, and its evolution towards a final configuration. For each $t$, $\eta^t = (\eta_v^t, v \in V)$ encodes the states of all vertices. It takes its values in the configuration space $S = \{h, 0, b, **\}^V$. We say that (at time $t$):

- $v$ is a free hole (or simply a hole) if $\eta_v^t = h$,

- $v$ contains a ball if $\eta_v^t = b$

- $v$ is a neutral vertex if $\eta_v^t = 0$. As the process evolves over time, there are several types of neutral vertices: occupied holes, which were free holes at the beginning ($\eta_v^t = 0$ but $\eta_v^0 = h$), vertices that contained a ball that has moved before time $t$ ($\eta_v^t = 0$ but $\eta_v^0 = b$) and the original neutral vertices ($\eta_v^0 = 0$).

- $v$ is frozen when $\eta_v^t = **$. In this case, the whole process is frozen until the end: $\forall t' \ge t, \forall u \in V, \eta_u^{t'} = **$. This frozen state is a kind of cemetery state, where the whole process goes when something goes wrong. Well-defined golf processes will avoid this state with probability 1.

Finally, we define the set of free holes at time $t$, $\mathbf{H}^t := \{v : \eta_v^t = h\}$ and similarly the set of remaining balls $\mathbf{B}^t := \{v : \eta_v^t = b\}$. Note that, by definition, $\mathbf{B}^0 \cap \mathbf{H}^0 = \emptyset$. Sometimes, for simplicity, if a vertex $v$ is such that $\eta_v^t = b$, then we say that $v$ is a ball.

### Distribution of the initial configuration:

* The initial state $\eta^0$ can be either random or deterministic. We will only consider models for which $|\mathbf{B}^0| \le |\mathbf{H}^0|$, i.e. there are more holes than balls (when $G$ is infinite, we allow $|\mathbf{B}^0|$ and $|\mathbf{H}^0|$ to be both infinite).

* Each vertex $v$ has a random activation clock $C(v) \in (0, 1)$. We will mainly consider the case where the $C(v)$ are i.i.d. of uniform distribution on $[0, 1]$, hereafter denoted
$\mathcal{U}([0, 1])$ (which ensures that almost surely all the $\mathbf{C}(v)$ are different). We denote by $\mu^{\text{Clocks}} = \mathcal{L}(\mathbf{C}(v), v \in V)$ the clock distribution.<fnref n="1" />

**Random evolution of the configuration:** informally, we define the process $(\eta^t)_{t \in [0,1]}$ so that for each vertex $v$ containing a ball, when the clock rings at time $\mathbf{C}(v)$, the corresponding ball instantaneously does a $P$-Random Walk until it reaches a still free hole, which it fills (still at time $\mathbf{C}(v)$). Then $\eta^{\mathbf{C}(v)}$ is updated. We now give a definition of the process $\eta$ (the formal aspects concerning measurability will be discussed just before Definition 1):

We define a jump process $(\eta^t)$, whose jump times belong to the set $\{\mathbf{C}(v), v \in \mathbf{B}^0\}$. Let $t$ be the activation time of a ball: there exists $v$ such that $\mathbf{C}(v) = t$ and $\eta_v^t = \mathbf{b}$. We assume that $\eta^{t-} = (\eta_w^{t-})_{w \in V}$ is well-defined. Then, we consider $(W_k^v)_{k \ge 0}$ a $P$-random walk starting at $v$, and stopped when it hits a free hole, that is at time $\tau = \inf\{k \ge 0 : W_k^v \in \mathbf{H}_k^{t-}\}$. If $\tau = \infty$ (the ball has not found any free hole), the whole process is frozen until time 1 and we set $\eta_w^t := \mathbf{v}$, $\forall w \in V$ (and thus nothing happens after time $t$). Otherwise, the ball jumps to the hole $u := W_\tau^v$ (the first free hole it has reached) and we update the states so that the ball in $v$ fills the hole $u$: $\eta_u^t := 0$, $\eta_v^t := 0$ (both $v$ and $u$ become neutral) and the state of the other vertices do not change ($\forall w \notin \{v, u\}$, $\eta_w^t := \eta_w^{t-}$). (All the random walks of the balls are independent of each other and of the initial configuration).

**Final configuration:** At time 1, either the process is frozen or every ball has found a hole, so the process has reached a final configuration, characterized (if it is not frozen) by the set of free holes $\mathbf{H}^1$ and the set of occupied holes $\mathbf{H}^0 \setminus \mathbf{H}^1$.

**Golf model:** To define a golf process $\eta$, we need 5 parameters: the graph $G$, the kernel $P$ for the random walks, the clocks distribution $\mu^{\text{Clocks}}$, and $\mathbf{B}^0$ and $\mathbf{H}^0$ (the initial configuration $\eta^0$ is characterized by the set of balls $\mathbf{B}^0$ and the set of holes $\mathbf{H}^0$, with $\mathbf{H}^0 \cap \mathbf{B}^0 = \emptyset$).

The random variables $(\mathbf{C}(v))$, $\mathbf{B}^0$, $\mathbf{H}^0$ and the $P$-Random Walks are assumed to be defined on a common probability space $(\Omega, \mathcal{A}, \mathcal{P})$, which is assumed to be large enough to accommodate also all the random variables used in the sequel.

In the following, we are mainly interested in describing the distribution of $\mathbf{H}^1$, the set of free holes at time 1 (which contains the same information as $\eta^1$).

By nature, even if we are interested in the final configuration of the golf process, in order to get a formal definition we need to define this process as a continuous time process indexed by $[0, 1]$, equipped with an ad hoc sigma-field. This introduces some additional complications that can be ignored on $\mathbb{Z}/n\mathbb{Z}$ (because the process only has only a finite number of jumps).

Since $\eta$ is a continuous-time process which is not continuous, we decide to work on $D_S[0, 1]$ the Polish space of càdlàg functions from $[0, 1]$ to $S$, equipped with the Skorokhod topology, where the configuration space $S = \{\mathbf{h}, 0, \mathbf{b}, \mathbf{v}\}^V$ is equipped with the product topology. Recall that càdlàg means right-continuous with left limits.

**Definition 1.** We say that $(\eta^t)$ is valid if it satisfies the following conditions : it is almost surely well-defined and not frozen at time 1, it is measurable, and it almost surely belongs to $D_S[0, 1]$.

When there is a finite number of balls, since $\eta$ jumps only a finite number of times, the golf process $\eta$ is valid under reasonable assumptions:

<footnote n="1">¹We will not deal with the case when clocks can be equal, but if one wants to define the golf process without loss of generality, then it suffices to use new random variables to break ties when there are some.</footnote>
**Proposition 1.1.** We recall that we assume that $P$ is irreducible and recurrent. If $\eta$ is a golf process on a finite graph $G$, such that $|\mathbf{B}^0| \le |\mathbf{H}^0|$, then the process $\eta$ is valid.

The same results holds for infinite graphs, if $|\mathbf{B}^0| \le |\mathbf{H}^0|$ and $|\mathbf{B}^0|$ is finite.

**Remark 1 (Commutation property).** We have the following Commutation property: on finite graphs, the distribution of $\eta^1$ does not depend on $\mu^{\text{Clocks}}$. In fact, this property is even stronger : fix an initial configuration $\eta^0$. Then, the distribution of $\eta^1$ is the same for any choice of distinct clocks $(\mathbf{C}(v))_{v \in V}$.

This classical result is due to Diaconis-Fulton [DF91, Proposition 4.1] (see Section 1.6.3 for more details on their paper). A proof of this property relies on an alternative representation of the process: we associate to each vertex $u$ an infinite sequence $(V_i^u, i \ge 1)$, which we see as a stack of arrows/choices associated with $u$, such that $(V_i^u, i \ge 1)$ is a sequence of i.i.d.random neighbors of $u$ with common distribution $\mathbb{P}(V_1^u = v) = P_{u,v}$. Hence, for every $i$, $u \to V_i^u$ has the same distribution of a step of a random walk starting at $u$. Again, the balls move successively according to their clocks. When a ball at vertex $u$ has to take a step, it moves according to the first $V_i^u$ that has not yet been used. Diaconis and Fulton prove that for any realization of the $V_i^u$ (up to a negligible subset for which the balls move forever without finding holes), the final configuration is unchanged if we swap the clocks.

The Commutation property may help the reader to figure out that one can forget about the clocks (at least on finite graphs) if we are only interested in the final configuration. However, as we will see in Section 1.6.1, our analysis still applies to time dependent variants, which do not have the Commutation property.

Note that $\eta^1$ does not record the allocation of the balls (i.e. which ball fills which hole). If it did, Remark 1 would no longer hold. Similarly, if we consider the entire process $\eta$ instead of $\eta^1$, then it also depends on the $\mu^{\text{Clocks}}$.

**Remark 2.** We will see (for example in Section 1.5) that it becomes much more complicated when an infinite number of balls are involved. However, we will show that a golf process can be valid on $\mathbb{Z}$ under certain hypotheses (see Theorem 1.7 in Section 1.5).

## 1.3 Model and main results on $\mathbb{Z}/n\mathbb{Z}$

We now focus on the golf process on the cycle $G = (\mathbb{Z}/n\mathbb{Z}, E_n)$, with edge set $E_n = \{\{x, x+1\}, x \in \mathbb{Z}/n\mathbb{Z}\}$, for some $n \ge 1$. For simplicity, we often directly call this cycle $\mathbb{Z}/n\mathbb{Z}$.

We fix $N_b \le N_h$, and we let $C^{n,N_b,N_h}$ be the set of all initial configurations with $N_h$ holes and $N_b$ balls:

$$ C^{n,N_b,N_h} := \left\{ (y_0, \dots, y_{n-1}) \in \{\mathbf{h}, 0, \mathbf{b}\}^{\mathbb{Z}/n\mathbb{Z}} : |\{i : y_i = \mathbf{b}\}| = N_b \text{ and } |\{i : y_i = \mathbf{h}\}| = N_h \right\} \quad (1) $$

and thus $|C^{n,N_b,N_h}| = (N_b, N_h, n-N_b-N_h)$, the classical multinomial coefficient.

We draw the initial configuration $\eta^0$ uniformly in $C^{n,N_b,N_h}$. We also fix $p \in [0, 1]$, and consider $P$ such that $\forall x \in \mathbb{Z}/n\mathbb{Z}$, $P_{x,x+1} = p$ and $P_{x,x-1} = 1-p$, so that $P$ is the transition matrix of a biased random walk on $\mathbb{Z}/n\mathbb{Z}$. Finally, we let $N_f = N_h - N_b$ be the number of free holes at time 1.

**Remark 3 (Discussion on the distribution of the initial configuration).** We choose to study the golf model with this particular initial distribution because it is arguably the simplest exchangeable distribution that respects the constraint of having more holes than balls (and every distribution that verifies this is a mixture of uniform distributions on $C^{n,N_b,N_h}$, with $N_b \le N_h$). Moreover, it allows to study the golf process on $\mathbb{Z}$ (described in Section 1.5) as a limit of the golf process on $\mathbb{Z}/n\mathbb{Z}$. Actually, we will see in Section 1.6.1 that our approach also enables to study a wide range of initial configurations.
<figure><img src="image_2.png" /><figcaption>Figure 1: Illustration of our notation : for $n = 16$ and the set $X = \{2, 3, 10, 13\} \subseteq \mathbb{Z}/n\mathbb{Z}$ (orange points on the figure), which we identify with the nicely ordered sequence $(x_1, x_2, x_3, x_4) = (2, 3, 10, 13)$, we show the blocks (in blue) and their length $(\Delta_i X)_{i \in \mathbb{Z}/4\mathbb{Z}} = (x_{i+1} - x_i - 1 \bmod n)_{i \in \mathbb{Z}/4\mathbb{Z}}$. Notice that $B_0 = \{14, 15, 0, 1\}$.</figcaption></figure>

**Some notation.** We choose to encode subsets $X$ of $\mathbb{Z}/n\mathbb{Z}$ with cardinality $|X| = k$ as sequences indexed by $\mathbb{Z}/k\mathbb{Z}$, which describes the order in which we discover the elements of $X$ when turning around the circle (this will simplify some considerations further in the paper). Figure 1 illustrates this notation.

We denote by $\pi$ the canonical projection $\mathbb{Z}/n\mathbb{Z} \to [1, n]$ (here and below, $\llbracket a, b \rrbracket = [a, b] \cap \mathbb{Z}$). A sequence $x = (x_i)_{i \in \mathbb{Z}/k\mathbb{Z}} \in \mathbb{Z}/n\mathbb{Z}^k$ is said to be nicely ordered if $\pi(x_1) < \dots < \pi(x_{k-1}) < \pi(x_k) = \pi(x_0)$. For every set $X \subseteq \mathbb{Z}/n\mathbb{Z}$ such that $|X| = k$, there exists a unique nicely ordered sequence $x$ of size $k$ containing all the elements of $X$, and we identify $X$ with this sequence $x$.

For $i \in \mathbb{Z}/k\mathbb{Z}$, we define the *ith-block* associated to a nicely ordered sequence $x$ (and thus to $X$) as the interval $B_i = \llbracket x_i, x_{i+1} \rrbracket \setminus \{x_i, x_{i+1}\}$, where $\llbracket a, b \rrbracket$ is the set $\{a \bmod n, a + 1 \bmod n, \dots, a + i \bmod n\} \subseteq \mathbb{Z}/n\mathbb{Z}$ and where $i$ is the smallest non-negative integer such that $a + i \bmod n = b$ (thus $B_i$ is empty if $x_{i+1} = x_i + 1$). The size of the *ith* block is then $\Delta_i^{(n)} X = \Delta_i^{(n)} x = \pi(x_{i+1}) - \pi(x_i) - 1 \bmod n$.

Note that $0$ belongs to $B_0 \cup \{x_0\}$.

The following theorem is one of the key results of the paper, and is proved in Section 2.1. In the theorem and elsewhere in the paper, we will use the notation $\mathbb{P}^{n, N_b, N_h, p}$, to illustrate the dependence of the distribution of the golf process on the parameters of the model.

**Theorem 1.2. (Distribution of set of remaining holes $\mathbf{H}^1$.)** For every $X \subseteq \mathbb{Z}/n\mathbb{Z}$ of size $|X| = N_f > 0$ and every $i \in \mathbb{Z}/N_f\mathbb{Z}$, we set $\ell_i := \Delta_i^{(n)} X$. Then, we have:

$$ \mathbb{P}^{n, N_b, N_h, p} (\mathbf{H}^1 = X) = \frac{1}{\binom{n}{N_b, N_h, n-N_b-N_h}} \sum_{(b_i) \in \mathcal{B}^{(N_b, X)}} \prod_{i \in \mathbb{Z}/N_f\mathbb{Z}} \frac{1}{b_i+1} \binom{\ell_i}{b_i, b_i, \ell_i - 2b_i} \quad (2) $$

where $B^{(N_b, X)}$ is the finite set $\{(b_i)_{1 \le i \le N_f} : \sum_i b_i = N_b \text{ and } \forall i, 0 \le b_i \le \ell_i/2\}$, which corresponds to the set of possible assignments of $N_b$ balls into $N_f$ intervals (compatible with the given set $X$), having at most $\ell_i/2$ balls in the $i$th interval.

In particular, the distribution does not depend on $p$.

**Remark 4.** The identification of the product form of the distribution will allow to pass to the limit eventually. In particular, the multinomial coefficients in the product appear in combinatorial formulas counting trees and we can make connections with the distribution of random forests (this is what we do in the proof of Theorem 1.3).
We now describe the statistical properties of the block-size process $\Delta^{(n)}\mathbf{H}^1$ as $n$ goes to infinity, in two cases: when there is no neutral vertex at the beginning (i.e. $N_b + N_h = n$) and when $N_b$ and $N_h$ are fixed.

For any sequence $c = (c_i)_{i \in \mathbb{Z}/k\mathbb{Z}}$, we let $\text{Sorted}(c) = (\hat{c}_1, \dots, \hat{c}_k)$ be this sequence rearranged in decreasing order, so that $\text{Sorted}(\Delta^{(n)}\mathbf{H}^1)$ is the sequence of the block sizes at time 1, in decreasing order, and $\text{Max}(\Delta^{(n)}\mathbf{H}^1) := \text{Sorted}(\Delta^{(n)}\mathbf{H}^1)_1$ is the size of the largest block in $\mathbf{H}^1$.

The following theorem (proven in Section 2.5) allows one to see that there is a phase transition in the size of the largest block; “giant blocks” arise when there is an excess of $N_f = N_h - N_b \sim \lambda\sqrt{n}$ holes.

We will call the case where the number of balls goes to infinity, the *dense case*.

**Theorem 1.3 (Dense case).** Let $(N_h(n))$ and $(N_b(n))$ be two sequences such that $n = N_b(n) + N_h(n)$, $N_h(n) \to \infty$ and $N_b(n) \to \infty$. Under $\mathbb{P}^{n,N_b(n),N_h(n),p}$,

(i) if $N_f(n) = an + o(n)$ for some constant $a > 0$, then there exists two explicit constants $\alpha, \beta > 0$ such that $\mathbb{P}(\alpha \le \text{Max}(\Delta^{(n)}\mathbf{H}^1) / \log n \le \beta) \xrightarrow{n \to \infty} 1$;

(ii) if $N_f(n)/\sqrt{n} \to \lambda > 0$, then the process $(\text{Sorted}(\Delta^{(n)}\mathbf{H}^1)_i / n, i \ge 1)$ converges in distribution for the product topology to a process $(y_j^{(\lambda)}, j \ge 1)$, satisfying $y_j^{(\lambda)} > 0$ a.s., for all $j$, and which can be represented as the excursion sizes above the current minimum of a Brownian motion $B_t$ on $[0, 1]$ conditioned by hitting $-\lambda$ at time 1.<fnref n="2" />

(iii) if $N_f(n)/\sqrt{n} \to +\infty$, then $\text{Max}(\Delta^{(n)}\mathbf{H}^1)/n \to 0$ in probability,

(iv) if $N_f(n)/\sqrt{n} \to 0$, then $\text{Max}(\Delta^{(n)}\mathbf{H}^1)/n \to 1$ in probability.

The analysis relies on the fact that the sequences of block sizes in our model have the same distribution as the sequences of tree sizes in some uniform random forest with a marked node. We detail this correspondence in Section 2.4 and then prove Theorem 1.3 in Section 2.5.

Finally, we give another theorem about the asymptotic behavior of the golf process on $\mathbb{Z}/n\mathbb{Z}$, this time when $N_b$ and $N_h$ are fixed (the *sparse case*). Note that the last block is a deterministic function of the others (since the sum of all the block sizes is equal to $n - N_f$).

**Theorem 1.4 (Sparse case).** Let $N_b$ and $N_h$ be some fixed integers such that $N_b < N_h$. Under $\mathbb{P}^{n,N_b,N_h,p}$, the vector $(\Delta_i^{(n)}\mathbf{H}^1/n)_{0 \le i < N_f}$ converges in distribution to $\mathbf{D} = (\mathbf{D}_0, \dots, \mathbf{D}_{N_f-1})$ as $n \to \infty$, where $\mathbf{D}$ is a random variable taking values in

$$ \text{Simplex}(N_f) := \{ x = (x_i)_{0 \le i < N_f} : \sum x_i = 1 \text{ and } \forall i, x_i \ge 0 \}, $$

where $\mathbf{D}_{N_f-1} = 1 - \sum_{i=0}^{N_f-2} \mathbf{D}_i$ and $(\mathbf{D}_0, \dots, \mathbf{D}_{N_f-2})$ has density function (with respect to the Lebesgue measure on $\mathbb{R}^{N_f-1}$)

$$ f(x_0, \dots, x_{N_f-2}) := x_0 N_b! N_h! \sum_{(b_i): \sum_i b_i = N_b} \prod_{k \in \mathbb{Z}/N_f \mathbb{Z}} \frac{1}{b_k! (b_k+1)!} x_k^{2b_k} \mathbf{1}_{(x_0, \dots, x_{N_f-1}) \in \text{Simplex}(N_f)}, \quad (3) $$

where $x_{N_f-1} = 1 - \sum_{i < N_f-1} x_i$.

We prove this theorem in Section 2.7.1.

<footnote n="2">²A formal definition of this Brownian motion is given in Proposition 2.9.</footnote>
**Remark 5.** The distribution of $\mathbf{D}$ is a mixed Dirichlet distribution.

Recall that the Dirichlet distribution of parameters $K \ge 2$ and $\alpha = (\alpha_i)_{0\le i<K}$ is a distribution on Simplex($K$) with probability density function $f(x_0, \dots, x_{K-2}) = \frac{1}{B(\alpha)} \prod_{i=0}^{K-1} x_i^{\alpha_i-1}$, where $x_{K-1} = 1 - \sum_{i<K-1} x_i$ (see for example [Pit06, Section 0.3.2.]). The normalizing constant $B(\alpha) = \frac{\prod_{i=0}^{K-1} \Gamma(\alpha_i)}{\Gamma(\sum_{i=0}^{K-1} \alpha_i)}$ is called the multivariate beta function, as the Dirichlet distribution generalizes in higher dimensions the beta distribution.

**Remark 6.** This limit is the distribution of the final configuration of several continuous analogues of the golf process defined on the unit circle $C = \mathbb{R}\backslash\mathbb{Z}$. We describe them in Section 2.7.2.

## 1.4 The p-parking process on $\mathbb{Z}/n\mathbb{Z}$

We recall the definition of the **parking process**, which also appears in the computer science literature under the name “hashing with linear probing” (which is an important and efficient method to store data in an array).

We consider the usual cycle $\mathbb{Z}/n\mathbb{Z}$ and we take $m < n$. Each vertex of $\mathbb{Z}/n\mathbb{Z}$ is a parking space, which is available at time 0. We assume that at each time step $i$ (with $1 \le i \le m$), a car chooses uniformly at random a vertex $v_i \in [1, n]$ (independently of the other cars) and parks at the first available parking space to the right (i.e. the first among $v_i, v_i + 1 \bmod n, v_i + 2 \bmod n \dots$). This slot is then occupied until the end of the process.

Sometimes, the parking model is defined on a path instead of a cycle: a car chooses $v_i \in [1, n-1]$ (also uniformly at random, when we consider the probabilistic version of the process), and cannot park if it reaches the end of the path (vertex $n$) without finding an available parking space. Parking functions are the sequences $(v_1, \dots, v_m)$ that leave the vertex $n$ empty at the end. Parking on a path and on a cycle are two problems that are combinatorially equivalent since rotating the cycle with respect to the last empty place yields a linear parking.

This problem has a long history, see for example [CL02, Section 1.1] for a short summary. The reader will find some additional combinatorial information in [FPV97, Section 4] or in [Knu73] (in particular, the number of parking functions of size $n$ is $n^{n-2}$; it was obtained in [KW66]). One of the proofs of the importance of this model is that the distribution of the relative distances between consecutive free spaces in the partially filled parking is the same as the cluster sizes in the additive coalescent [CL02].

We now consider a variant of the parking process, which we call **the p-parking process**. As in the parking process, each vertex of $\mathbb{Z}/n\mathbb{Z}$ is initially a parking space. A $N_b$ cars enter successively in the system, the $i$th car chooses a vertex $v_i$ uniformly at random (independently of the other ones) and from this, performs a p-Random Walk (from $k$ it goes to $k+1 \bmod n$ with probability $p$, and to $k-1 \bmod n$ with probability $1-p$). Note that for $p=1$, the process is exactly the parking process.

In the following, we write $\mathbb{P}^{\text{Parking},n,N_b;p}$ to explicitly show the parameters of this model. As usual, $\mathbf{H}^1$ denotes the number of holes at the end of the process, after all the cars have moved.

We now give the distribution of $\mathbf{H}^1$ (which has size $N_f = n - N_b$).

**Theorem 1.5.** For every $X \subseteq \mathbb{Z}/n\mathbb{Z}$ of size $|X| = N_f > 0$, we set, for every $i \in \mathbb{Z}/N_f\mathbb{Z}$, $\ell_i := \Delta_i^{(n)} X$. Then, we have:

$$ \mathbb{P}^{\text{Parking},n,N_b,p}(\mathbf{H}^1 = X) = \frac{1}{n^{N_b}} \binom{N_b}{\ell_1, \dots, \ell_{N_f}} \prod_{i \in \mathbb{Z}/N_f\mathbb{Z}} (\ell_i + 1)^{\ell_i - 1}. \quad (4) $$

Once again, this result does not depend on $p$.
The proof of this theorem is very similar to the proof of Theorem 1.2, which gives the distribution of $\mathbf{H}^1$ for the golf model. We detail the main arguments of the proof in Section 2.3.

We can reinterpret this parking model as a golf process (replacing cars by balls and parking spaces by holes) where we allow the initial configuration to have, on each vertex, one hole along with a random non-negative number of balls. If there are more holes than balls, this model is again valid.<fnref n="3" />

For $p = 1$, this model is the usual parking process, for which asymptotics are already known (results due to [Pit87] and [CL02]) and are also valid when $p \neq 1$, thanks to Theorem 1.5.

**Corollary 1.6.** Let $(N_b(n))$ be a sequence such that $N_b(n) \to \infty$. For any $p$, under $\mathbb{P}^{\text{Parking},n,N_b,p}$,

(i) if $a := N_b(n)/n$ is bounded away from 0 and 1, then, in probability,

$$ \mathrm{Max} \left( \Delta^{(n)} \mathbf{H}^1 \right) = \frac{1}{a - 1 - \log a} \left( \log n - \frac{3}{2} \log \log n \right) + O(1), \quad (5) $$

(ii) if $N_b(n)/\sqrt{n} \to \lambda > 0$, then the process $(\mathrm{Sorted} (\Delta^{(n)} \mathbf{H}^1)_i /n, i \ge 1)$ converges in distribution for the product topology to a process $(y_j^{(\lambda)}, j \ge 1)$, satisfying $y_j^{(\lambda)} > 0$ a.s., for all $j$, and which can be represented as excursion sizes above the current minimum in a Brownian-like process $B = (e_t - \lambda t)_{t \in [0,1]}$, where $(e_t)_{t \in [0,1]}$ is a Brownian excursion,

(iii) if $N_b(n)/\sqrt{n} \to +\infty$, then $\mathrm{Max} (\Delta^{(n)} \mathbf{H}^1) /n \to 0$ in probability,

(iv) if $N_b(n)/\sqrt{n} \to 0$, then $\mathrm{Max} (\Delta^{(n)} \mathbf{H}^1) /n \to 1$ in probability.

*Proof.* Theorem 1.5 allows to treat only the case $p = 1$, and in this case the asymptotic behavior of the parking is known: (i) is due to Pittel [Pit87, Statement (1.3)], while (ii), (iii) and (iv) are due to Chassaing and Louchard [CL02, Theorems 1.1 and 1.2]. □

**Remark 7.** This corollary is very similar to Theorem 1.3 (although (i) is stronger in Corollary 1.6). The proof is different because the discrete objects are of a different nature. In the sublinear case (Theorem 1.3.(i)), we conjecture the same phenomenon as in Corollary 1.6.(i)), but we did not pursue in this direction. We will see in Subsection 2.6 that the limit Brownian processes appearing in (ii) are the same up to some transformation preserving the excursion sizes and it implies that the block-size processes $\Delta^{(n)} \mathbf{H}^1$ in the golf model and in the p-parking model have the same limit in law up to a rotation (see, in particular, Lemma 2.10).

## 1.5 Model and main results on $\mathbb{Z}$

We now turn our attention to the golf process on $\mathbb{Z}$. We let $G = (\mathbb{Z}, E)$ with edge set $E = \{\{x, x+1\}, x \in \mathbb{Z}\}$. We again fix $p \in [0, 1]$, and consider $P$ the transition matrix of a Markov chain such that $\forall x \in \mathbb{Z}, P_{x,x+1} = p$ and $P_{x,x-1} = 1-p$. For the initial

<footnote n="3">³In the golf process we defined at the beginning, the balls are present at time 0 and do not move until their clock rings. Here, the temporality is a bit different, but it does not change anything concerning the behavior of the process. Furthermore, there is again a commutation property, which we can state in this way: the distribution of $\mathbf{H}^1$ depends only on the vector $W = (W_1, \dots, W_n)$, such that $W_k = |\{i : v_i = k\}|$ is the number of cars that choose vertex $k$ (and does not depend on the order of arrival of the balls); this is again a consequence of [DF91, Proposition 4.1]. The vector $W$ has the multinomial distribution with parameter $(N_b; 1/n, \dots, 1/n)$.</footnote>
configuration, we draw the state of each vertex independently of the others: the $(\eta_x^0)_{x \in \mathbb{Z}}$ are i.i.d. with common distribution:

$$ \forall x \in \mathbb{Z}, \eta_x^0 = \begin{cases} 1 & \text{(a ball b)} \\ -1 & \text{(a hole h)} \\ 0 & \text{(a neutral vertex)} \end{cases} \quad \begin{array}{l} \text{with probability } d_b, \\ \text{with probability } d_h, \\ \text{with probability } 1 - d_b - d_h. \end{array} \qquad (6) $$

One can note that we have slightly changed our notation (replacing **b** by 1 for balls, and **h** by -1 for holes), so that the absorption of a ball by a hole corresponds algebraically to the operation "-1 + 1". Sometimes, for clarity purposes, we will still write **b** instead of 1, and **h** instead of -1.

The activation clocks are i.i.d. and uniform on $[0, 1]$ (and also independent of the affectation of the balls). Contrary to the finite case, the well-definition of $\eta$ is not trivial, since almost surely an infinite number of balls have moved before time $t$, for all $t > 0$, so it is not obvious that every ball can reach a free hole at its activation time and measurability issues arise (see Section 3.2, where we discuss examples with different initial conditions, showing that the golf process on $\mathbb{Z}$ is not always valid; it can even be frozen at time $0^+$). We thus give the following theorem, which we prove in Section 3.1.

**Theorem 1.7.** If $d_b \le d_h$, then for every $p$, the golf model $(\eta^t)_{t \in [0,1]}$ on $\mathbb{Z}$ is valid (in the sense of Definition 1).

For $p \in \{0, 1\}$, the P-Random Walks are not irreducible, but the golf model is valid in this case too.

We use the notation $\mathbb{P}^{\mathbb{Z},d_b,d_h,p}$ for the probabilities concerning the golf model on $\mathbb{Z}$, to make explicit the parameters of the model.

The following remark enables to define the block-size process.

**Remark 8.** Under $\mathbb{P}^{\mathbb{Z},d_b,d_h,p}$, either $\mathbf{H}^1$ is empty, or $\mathbf{H}^1$ has an infinite number of holes on the left and on the right of 0. In fact, if we let $L = \inf \mathbf{H}^1$ and $R = \sup \mathbf{H}^1$ be respectively the leftmost and rightmost holes of $\mathbf{H}^1$, then these variables have a distribution, which is invariant by translation, and thus must have their support outside $\mathbb{Z}$. It implies that either $L = +\infty$ and $R = -\infty$ ($\mathbf{H}^1$ is empty) or $L = -\infty$ and $R = +\infty$ ($\mathbf{H}^1$ has an infinite number of holes on the left and on the right of 0).

Under the hypotheses of Theorem 1.7, the golf process is valid, so the set of remaining holes $\mathbf{H}^1$ is also well-defined. In the following, when considering cases with an infinite number of remaining holes on the left and on the right of the origin, it will be convenient to view $\mathbf{H}^1 = (\mathbf{H}_i^1, i \in \mathbb{Z})$ as an increasing process indexed by $\mathbb{Z}$, where $\mathbf{H}_0^1$ is the largest non-positive hole. Thus, $\mathbf{H}^1$ is therefore viewed as a process taking its values in $\mathbb{Z}^\mathbb{Z}$ equipped with the product topology.

Finally, when $\mathbf{H}^1$ is empty, we have only one block (the block containing 0), of size $\Delta_0 \mathbf{H}^1 = \infty$. Otherwise, we define the block-size process $(\Delta_i \mathbf{H}^1, i \in \mathbb{Z})$ by $\Delta_i \mathbf{H}^1 = \mathbf{H}_i^1 - \mathbf{H}_i^1 - 1$, for all $i \in \mathbb{Z}$.

Since $\eta$ is translation invariant, it is equivalent to study $\Delta \mathbf{H}^1$ or $\mathbf{H}^1$ (but studying $\Delta \mathbf{H}^1$ is easier when doing the proofs).<fnref n="4" /> The following theorem gives the distribution of $\Delta \mathbf{H}^1$ on $\mathbb{Z}$ when $d_b + d_h = 1$; it is proven in Section 3.3.

**Theorem 1.8.** (Distribution of $\mathbf{H}^1$.) Under $\mathbb{P}^{\mathbb{Z},d_b,d_h,p}$, with $d_b + d_h = 1$ and $d_b < d_h$, the distribution of $(\Delta_i \mathbf{H}^1)_{i \in \mathbb{Z}}$ is characterized by its finite-dimensional distributions:

<footnote n="4">⁴Indeed, if one wants to find the set $\mathbf{H}^1$ instead of $\Delta \mathbf{H}^1$, it suffices to draw the process $(\Delta_i \mathbf{H}^1)_{i \in \mathbb{Z}}$, to choose the position of the first hole on the left of 0 uniformly in the interval $[-\Delta_0 \mathbf{H}^1, 0]$, and finally to define all the holes in the unique way that is consistent with the block-size process.</footnote>
For every $R > 0$, for every $(b_i) \in \mathbb{N}^{2R+1}$,

$$ \mathbb{P}^{\mathbb{Z},d_b,d_h,p} (\Delta_i \mathbf{H}^1 = 2b_i, -R \le i \le R) = \frac{(2b_0+1)C_{b_0}\lambda^{b_0}}{\mathcal{H}(\lambda)} \prod_{i=-R, i \ne 0}^{R} \frac{C_{b_i}\lambda^{b_i}}{\mathcal{G}(\lambda)} \quad (7) $$

where for every $k \ge 0$, $C_k = \binom{2k}{k}$ is the $k$th Catalan number, $\lambda = d_b d_h$, and for every $a \in (0, 1/4]$,

$$ \mathcal{G}(a) = \sum_{k \ge 0} C_k a^k = \frac{1 - \sqrt{1 - 4a}}{2a} \quad \text{and} \quad \mathcal{H}(a) = \sum_{k \ge 0} (2k + 1) C_k a^k = 2a \mathcal{G}'(a) + \mathcal{G}(a). $$

In particular, the $\Delta_i \mathbf{H}^1$ are independent with common distribution ($\forall i \ne 0, \forall b, \mathbb{P}(\Delta_i \mathbf{H}^1 = 2b) = C_b \lambda^b / \mathcal{G}(\lambda)$), except for $\Delta_0 \mathbf{H}^1$ which is size-biased ($\forall b, \mathbb{P}(\Delta_0 \mathbf{H}^1 = 2b) = (2b + 1)C_b \lambda^b / \mathcal{H}(\lambda)$).

**Remark 9.** • $\mathcal{G}$ is the generating function of the Catalan numbers.

* $\lambda$ is the unique number such that the average length of a block $\frac{2\lambda\mathcal{G}'(\lambda)}{\mathcal{G}(\lambda)}$ is compatible with the densities of holes and balls. Indeed, for every $i \ne 0$, if $B_i = [r_i, l_i]$ is the $i$th block, then set $I_i = [r_i, l_i + 1]$ (the intervals $I_i$ form a partitioning of $\mathbb{Z}$). Then, $I_i$ contains $\frac{\Delta_i \mathbf{H}^1}{2}$ balls, $\frac{\Delta_i \mathbf{H}^1}{2} + 1$ holes and has size $\Delta_i \mathbf{H}^1 + 1$. We therefore need to have: $\mathbb{E}[\frac{\Delta_i \mathbf{H}^1}{2}] = d_b (\mathbb{E}[\Delta_i \mathbf{H}^1] + 1)$ and $\mathbb{E}[\frac{\Delta_i \mathbf{H}^1}{2} + 1] = d_h (\mathbb{E}[\Delta_i \mathbf{H}^1] + 1)$. Solving this system gives $\mathbb{E}[\Delta_i \mathbf{H}^1] = \frac{2d_b}{2d_h - 1}$.

The equation $\frac{2\lambda\mathcal{G}'(\lambda)}{\mathcal{G}(\lambda)} = \frac{2d_b}{2d_h - 1}$ has a unique solution between 0 and 1/4 (because $x \mapsto \frac{2x\mathcal{G}'(x)}{\mathcal{G}(x)}$ is a continuous and increasing function mapping 0 to 0 and going to $+\infty$ as $x$ tends to 1/4), and it is straightforward to check that $\lambda = d_b d_h$ is a solution.

* The block containing 0 is size-biased: the origin 0 can be in $2k + 1$ positions in the block indexed by 0, if this block has size $2k$. We will see that on $\mathbb{Z}/n\mathbb{Z}$ the block containing 0 is also size-biased (see for example Equation (32)).

* It is heavier (in terms of computation) but also possible to obtain an analogous theorem for the distribution of $\Delta \mathbf{H}^1$ when $d_b + d_h < 1$. This will be discussed in Section 3.4.

It is somewhat remarkable that the critical case, in which the densities of balls and holes coincide, can be solved exactly:

**Theorem 1.9.** When $d_b = d_h$, under $\mathbb{P}^{\mathbb{Z},d_b,d_h,p}$, $\mathbf{H}^1 = \emptyset$ almost surely.

We prove this theorem in Section 3.5.

# 1.6 Related models

## 1.6.1 Variants and new results on them

**Different moving strategies in the golf process.** It is natural to wonder about the rigidity of the model: since the distribution of $\mathbf{H}^1$ does not depend on $p$, does it depend on the strategy of the ball ?

The strategy of a ball is, in full generality, the distribution of the trajectory that this ball will follow. It can be deterministic or not, and it can depend on the whole configuration $\eta^t$ at the time of its activation, or on a subset of it.
We now allow the balls to move with a more complex strategy than the random walk: it can move according to some deterministic or random function, but as before, at each step, it can only move from one vertex to one of its neighbors (in particular it cannot jump over a free hole). We borrow the following definitions from Nadeau [Nad25]. We say that a strategy is *shift invariant* if it is invariant by rotation on $Z/nZ$ or invariant by translation on $Z$. Moreover, a strategy is *local* if a ball has a strategy that depends only on its clock and of the state of the process between the closest hole on its right and the closest hole on its left.

The following examples correspond to shift invariant and local strategies:

1. Each ball independently chooses a unique direction (left with probability $q$ or right with probability $1-q$) and moves in this chosen direction until it finds a free hole.

2. Each ball goes to the closest hole (and chooses one of them uniformly at random if the two holes are at the same distance from the ball).

3. Or something completely arbitrary: A ball with clock $C$ goes to the left if the closest hole on the right is at an even distance, and otherwise it does a random walk with parameter $C$.

We can define a golf process with every shift invariant and local strategy on $Z/nZ$ (still specifying $n$, $N_b$ and $N_h$ if necessary) and on $Z$ (also specifying $d_b$ and $d_h$). We prove the following.

**Proposition 1.10.** We assume that each ball has a strategy that is shift invariant and local.

* For the golf process on $Z/nZ$ (with initial condition given at the beginning of Section 1.3), $H^1$ has the same distribution as in the golf process with random walks of parameter $p$: Theorems 1.2, 1.3 and 1.4 apply to this more general model.

* For the parking process on $Z/nZ$ (with initial configuration detailed in Section 1.4), $H^1$ has the same distribution as in the $p$-parking process: Theorem 1.5 and Corollary 1.6 apply to this more general model.

* On $Z$, the golf process with these strategies is valid, and again the distribution of $H^1$ is the same as in the golf process with random walks of parameter $p$: Theorems 1.7 and 1.8 hold for this model too.

We prove this proposition in Section 4.

**Remark 10.** The special case of the variant 1 for the parking process was already mentioned in the last section of [KW66] (with the parameter $q$ depending on the car). It was studied more thoroughly by Durmić et al. [DHH+23], who prove that the probability that a given vertex is free at the end does not depend on $p$ (which was already claimed by Konheim and Weiss [KW66]) and then study a statistic that does depend on $p$, namely the vertex at which the last car tries to park (conditional on the position of the last free hole, or equivalently, when the process is considered on the line).

Moreover, in [Nad25], Nadeau studies the parking process on $Z$ with a finite number of cars, by studying the parking on $Z/nZ$ that leave only one vertex free, and he shows that for any shift invariant and local strategy the number of parking functions is the same (in our setting, it says that the probability that some vertex is the only free one does not depend on the cars strategy).
**Golf process on $Z/nZ$ with several balls per site.** We have shown in Section 1.4 that the $p$-parking process can be seen as a variant of the golf process on $Z/nZ$ where we allow the initial configuration to have one hole along with a random non-negative number of balls at each vertex. In the case of the parking, Theorem 1.5 gives the distribution of $\mathbf{H}^1$.

Let $(N_j)_{-1 \le j < n}$ be such that $\sum_{j \ge -1} N_j = n$. We consider another variant, which consists in fixing $N_j$, the number of vertices containing $j$ balls, for every $j \ge -1$ (to simplify the notation, a hole is considered here as a $-1$) and then taking an initial configuration uniform in $\text{Ini}(N_j, -1 \le j < n)$ the set of configurations that satisfy these constraints. As long as $N_{-1} \ge \sum_{j \ge 0} jN_j$, the model is valid (Proposition 1.1 can be easily generalized).

The support of $\mathbf{H}^1$ depends on $(N_j)_{-1 \le j < n}$. Given $(N_j)_{-1 \le j < n}$ and $X$, the following proposition gives the probability that $\mathbf{H}^1 = X$. It is a sum over the possible assignments of the balls that are consistent with this event. We still use the convention that $\ell_i = \Delta^{(n)} X$ is the length of the $i$th interval. We denote by $b_j^i \ge 0$ the number of vertices in the $i$th interval containing $j$ balls.

If we consider the vector

$$B = (b_j^i, -1 \le j < n)_{i \in \mathbb{Z}/N_f\mathbb{Z}},$$

then $B$ is compatible with the event $\mathbf{H}^1 = X$ if and only if:

* The $i$th interval contains as many holes as balls: $b_{-1}^i = \sum_{j=0}^k j b_j^i$.

* There are $\ell_i$ vertices in the $i$th interval: $\sum_{j \ge -1} b_j^i = \ell_i$.

* The total number of vertices containing $j$ balls is $N_j$: $\forall j, \sum_{i \in \mathbb{Z}/N_f\mathbb{Z}} b_j^i = N_j$.

We let $B(X)$ be the set of all these compatible vectors.

This model can be studied with exactly the same tools as those presented above (we thus omit the proof here), and we can obtain the following formula.

**Proposition 1.11.** Let $(N_j)_{-1 \le j < n}$ be fixed non-negative integers such that $N_f := N_{-1} - \sum_{j \ge 0} jN_j > 0$ and $\sum_{j \ge -1} N_j = n$. Let $\mathbf{H}^1$ be the set of remaining holes in a golf model starting from a uniform configuration taken in $\text{Ini}(N_j, -1 \le j < n)$. Then, for any set $X \subseteq \mathbb{Z}/n\mathbb{Z}$ of cardinality $N_f$,

$$\mathbb{P}(\mathbf{H}^1 = X) = \frac{1}{\binom{n}{N_{-1}, \dots, N_n}} \sum_{B \in \mathcal{B}(X)} \prod_{i \in \mathbb{Z}/N_f\mathbb{Z}} \frac{1}{b_{-1}^i} \binom{\ell_i}{b_{-1}^i, b_0^i, \dots, b_n^i} \quad (8)$$

**Remark 11.**

* Here again, this proposition is valid for any ball moving strategy verifying the hypotheses given in Remark 10.

* This formula allows to compute the distribution of the remaining holes for all distribution on the set of configurations $\text{Ini}$ (as long as it is invariant by any permutation of the vertices). In fact, it suffices to compute the distribution of $(N_j)_{j \ge -1}$, and then conclude with the distribution of $\mathbf{H}^1$ conditional on this $(N_j)_{j \ge -1}$, given by Proposition 1.11.

### 1.6.2 Open questions

**Golf process on $Z/nZ$ with several holes per site.** We have seen in the previous paragraph that when there is at most one hole per vertex, we can compute the distribution of $\mathbf{H}^1$ under general hypotheses. When we allow a vertex to contain multiple holes (i.e.
$\mathbf{H}^0$ is a multiset), then it seems more complicated. We illustrate this fact with a small example.

We fix $N_b$ and $N_h$, the number of balls and holes, and let $m_i(\mathbf{H}^0)$ (esp. $m_i(\mathbf{B}^0)$) count the number of holes (resp. balls) at vertex $i$. We assume that $(m_i(\mathbf{H}^0), i \in \mathbb{Z}/n\mathbb{Z})$ has the multinomial distribution with parameters $(N_h; 1/n, \dots, 1/n)$ and similarly, $(m_i(\mathbf{B}^0), i \in \mathbb{Z}/n\mathbb{Z})$ has the multinomial distribution with parameters $(N_b; 1/n, \dots, 1/n)$ (as for the parking process). This initial configuration corresponds to the model where $N_h$ holes and $N_b$ balls successively choose uniformly at random a vertex of $\mathbb{Z}/n\mathbb{Z}$ (with repetitions allowed), independently of the other balls and holes.

In view of what we have said before, it is routine that the golf process with such an initial configuration is valid as long as $N_b \le N_h$, and thus that the multiset $\mathbf{H}^1$ is also well-defined.

When $n = 4$, $N_b = 2$ and $N_h = 4$, the distribution of $\mathbf{H}^1$ is quite complicated to compute by hand, but can be easily done with a computer algebra system (for a fixed initial configuration, it is possible to compute the probability that a ball will reach some hole before the others, and thus to compute the probability of some final configuration; it is then sufficient to sum these probabilities over all the possible initial configurations). We can obtain, for example, the probability that the two remaining holes are at position 0 is:

$$ \mathbb{P}(\mathbf{H}^1 = \{0,0\}) = \frac{106p^4 - 212p^3 + 322p^2 - 216p + 107}{1024(p^2 - p + 1)^2}, $$

while

$$ \mathbb{P}(\mathbf{H}^1 = \{0,1\}) = \frac{110p^4 - 220p^3 + 326p^2 - 216p + 109}{1024(p^2 - p + 1)^2}. $$

This time, these values depend non trivially on the parameter $p$. We leave as an open question the characterization of the distribution of $\mathbf{H}^1$ in general.

**Distribution of the occupied holes in the standard golf process** We focused on the distribution of $\mathbf{H}^1$, which does not depend on $p$ and is explicit (see Theorem 1.2). It is not the case for the set of occupied holes $\mathbf{H}^0\backslash\mathbf{H}^1$. It is easy to observe on small examples that the joint distribution of $(\mathbf{H}^0\backslash\mathbf{H}^1, \mathbf{H}^1)$ depends on $p$. We can give a simple example that shows this dependence on $p$ for $\mathbf{H}^0\backslash\mathbf{H}^1$ (also computed with a computer algebra system): if $n = 6$, $N_b = 2$ and $N_h = 4$, then

$$ \mathbb{P}^{n,N_b,N_h,p}(\mathbf{H}^0\backslash\mathbf{H}^1 = \{0,1\}) = \frac{-2p^6 + 6p^5 - 7p^4 + 4p^3 + 2p^2 - 3p + 1}{30(p^2 - p + 1)(p^2 - p + \frac{1}{2})}. $$

We also leave the characterization of $\mathbf{H}^0\backslash\mathbf{H}^1$ as an open question.

**Definition of the golf process on $\mathbb{Z}^d$.** A natural question that arises when reading Theorem 1.7, and that remains open, is the following.

**Question 1.12.** For $d \ge 2$, if $d_b \le d_h$, is the golf model on $\mathbb{Z}^d$ valid?

When $d_b < d_h$, it seems reasonable to conjecture that the golf process on $\mathbb{Z}^d$ is valid. On $\mathbb{Z}^2$, it is well-known that the standard random walk is irreducible and recurrent, thus intuitively “a ball can reach a free hole if such hole exists”; but as we explain in Section 3.2, it is not easy to prove that such hole always exists. The proof of validity on $\mathbb{Z}$ relies heavily on separators, that are holes that allow $\mathbb{Z}$ to be divided into independent finite intervals, and this proof cannot simply be generalized to higher dimensions. Question 1.12 thus remains open, even on $\mathbb{Z}^2$ with balls doing standard random walks.
### 1.6.3 Related models in the literature

In addition to the parking processes discussed in Section 1.4, we discuss other models that are close to the one we study here.

First, the name “golf model” comes from Fredes and Marckert [FM21], who introduced *golf sequences*, which are the sequences of trajectories of the balls. These golf sequences were introduced as a tool for a combinatorial proof of Aldous-Broder theorem.

We mentioned in Remark 1 the Commutation property, which can be seen as a consequence of [DF91, Proposition 4.1]. In this paper, Diaconis and Fulton defined a growth model in which some particles, starting at some positions $x_1, x_2, \dots$, stop at their first hitting time of a set $Y$ (as what we do here, when a particle at some vertex $y \in Y$ receives a particle, it loses its capacity to absorb another particle, and behaves as a standard non-absorbing vertex). For this general type of model, they show that the distribution of the eventually occupied vertices of $Y$ does not depend on the initial order of the balls.

The internal diffusion limited aggregation model is an instance of this type of growth model, where the graph is the lattice $\mathbb{Z}^d$ and all the balls start at the same position. We refer to Lawler et al. [LBG92] for the study of the asymptotic shape.

Several authors [DGJ$^+$19, PRS23] study a parking process on $\mathbb{Z}$, with an initial configuration similar to our golf process in the case $d_b + d_h = 1$: at the beginning, each vertex contains either a car (a ball) with probability $d_b$ or a parking space (a hole, with probability $d_h$) independently of the other vertices. But the dynamics is different: it is a discrete-time process, at time $k$ (for every $k \ge 0$), all the balls that have not yet reached a free hole do a random step (with random variables to break ties if several balls arrive at a free parking space at the same time). The process is clearly well-defined for all $k$, and in particular is well-defined regardless of the value of $d_b$. The question that Przykucki et al. study in [PRS23] is different from ours: their main results concern the average time that balls take to reach a hole. In fact, if $d_b \ge 1/2$, the expected time for a car to reach a parking space is infinite. When $d_b < 1/2$, every car reaches a parking space in almost surely finite time, but in fact no final configuration is reached in a finite time. Actually, we prove in Theorem 3.13 that for $d_b \le 1/2$, the final configuration in our model and in theirs (i.e. in their case the limit process as time goes to infinity) have the same distribution.

In the Activated Random Walk model, starting with infinitely many particles on $\mathbb{Z}^d$, the particles perform independent continuous-time random walks, falling asleep at rate $\lambda$ where they are alone at their location (see for example [CRS14] or this survey by Rolla [Rol20]). For $\lambda = \infty$, this model is a continuous-time version of the parking model. This model has also been studied on $\mathbb{Z}/n\mathbb{Z}$ by Basu et al. who focus on the time taken by the process to stabilize when $\lambda$ is finite [BGHR19]. Again, the models are close but have different time dynamics, since in the golf model the balls move only once; the authors are particularly interested in the average behavior of their models (typically, how many times the origin is visited on average), not in computing the distribution of the process (as we are, here), so that their results are of a different nature from those of the present paper.

We can also mention diffusion-limited annihilating systems (see for example [JJLS23]), where particles of two types are randomly placed on $\mathbb{Z}$, also perform continuous-time random walks (at a rate depending on their type) and annihilate when hitting a particle of the opposite type. When one type of particle does not move, the model amounts to the parking model of Przykucki et al. we described above.

Finally, in Nadeau & Tewari [NT23, Section 4] (see also Petrov [Pet18]), while studying some algebraic questions related to the basis of Schubert classes, the authors discussed combinatorial formulas arising when one computes the probability of some events related to the final configuration in a $p$-parking in which the initial configuration is fixed.
## 1.7 Contents of the paper

The paper is organized as follows.

**Section 2** contains the proofs of all the theorems concerning the golf model and the p-parking on $Z/nZ$. In Section 2.1, we prove Theorem 1.2 (for the distribution of $H^1$ in the golf model on $Z/nZ$), and we discuss the proof of Theorem 1.5 in Section 2.3 (for the distribution of $H^1$ in the p-parking model). Section 2.5 is devoted to the proof of the asymptotic results for the block-size process $\Delta^{(n)}H^1$ (Theorem 1.3), with a discussion on the combinatorial links between our block-size process and some combinatorial models of forests and paths in the previous section (Section 2.4). Then, in Section 2.6 connections are made between the asymptotics given in Theorems 1.3 and 1.6. Finally, Section 2.7 focuses on the block-size process with a fixed number of balls and holes, with the proof of Theorem 1.4 in Section 2.7.1.

**Section 3** contains the proofs of all the results concerning the golf model on $Z$. We prove that the golf model is valid (Theorem 1.7) in Section 3.1. In Section 3.2, we discuss the difficulty that arise when an infinite number of balls are involved. Theorem 1.8, giving the distribution of the block-size process when $d_b + d_h = 1$, is proved in Section 3.3. In the next Section (Section 3.4), we study the same process when $d_b + d_h < 1$. Finally, we prove Theorem 1.9 in Section 3.5 and couple the golf process with the parking process on $Z$ in Section 3.6.

# 2 Golf model on $Z/nZ$

## 2.1 Proof of Theorem 1.2

Before proving Theorem 1.2, we give two lemmas. The first one focuses on the case when $N_h = N_b + 1$, in which at the end there is exactly one remaining hole, and which we call the *mini-golf* case. This case in much simpler, and will appear to be crucial in the proof of Theorem 1.2.

**Lemma 2.1.** (Distribution of remaining holes - mini-golf case) We assume that $N_h = N_b + 1$. For every $x \in Z/nZ$,

$$ \mathbb{P}^{n,N_b,N_b+1,p}(\mathbf{H}^1 = \{x\}) = \frac{1}{n} \qquad (9) $$

and

$$ \mathbb{P}^{n,N_b,N_b+1,p}(\mathbf{H}^1 = \{x\}|x \in \mathbf{H}^0) = \frac{1}{N_b + 1}. \qquad (10) $$

Observe that $\mathbb{P}^{n,N_b,N_b+1,p}(\mathbf{H}^1 = \{x\}|\mathbf{H}^0 = H)$ (for some set $H \subseteq Z/nZ$) is different from (10), and strongly depends on the geometry of $H$.

*Proof of Lemma 2.1.* Equation (9) follows immediately from the fact that both the distribution of the initial configuration and $P$ are rotationally invariant, which implies that the final configuration is also rotationally invariant, hence the result. Equation (10) follows immediately from Equation (9). □

The second lemma is a crucial decomposition lemma, which is the key point of all the results concerning golf processes. At time 1, when the golf process achieves its final configuration $\eta^1$, the intervals (blocks) between the remaining empty holes of $H^1$ are equilibrated in the following sense: each of them must have contained as many balls than holes at time 0. The following lemma allows to decompose the probability that $H^1 = X$, conditional on the number of balls on each block at time 0, as the product of simpler probabilities on
<figure><img src="image_3.png" /><figcaption>Figure 2: Illustration of the block decomposition principle, and its use to compute $\mathbb{P}(\mathbf{H}^1 = X | X \subseteq \mathbf{H}^0 \text{ and } \forall i, |\mathbf{B}^0 \cap \mathcal{I}| x_i, x_{i+1}[| = b_i)$ given by Lemma 2.2. Here, we give an example for $n = 16$, $N_b = 5$ and $N_h = 8$. Moreover, we consider $X = \{x_0, x_1, x_2\}$ such that $\ell_0 = 4$, $\ell_1 = 6$ and $\ell_2 = 3$. The orange circled vertices correspond to the elements of $X$. Recall that $(b_0, b_1, b_2) \in B^{(N_b, X)} = \{(b_i)_{1 \le i \le N_f} : \sum_i b_i = N_b \text{ and } \forall i, 0 \le b_i \le \ell_i/2\}$. The notation $b_i \times \circ + b_i \times \bullet$ means that the corresponding block (in blue, between two consecutive elements of $X$) contains exactly $b_i$ balls and $b_i$ holes (assigned uniformly on the vertices of the block). Since no ball ever visits a hole of $\mathbf{H}^1$, the elements of $\mathbf{H}^1$ divide $\mathbb{Z}/n\mathbb{Z}$ into “independent” blocks that behave as mini-golfs, and this allows to decompose the probability that $\mathbf{H}^1 = X$ into a product of probabilities that mini-golfs leave 0 free.</figcaption></figure>

mini-golfs (on the blocks defined by $X$). It relies on the following **block decomposition principle**: the trajectory of any ball does not intersect with the set of final free holes, so the free holes of $\mathbf{H}^1$ allow to divide $\mathbb{Z}/n\mathbb{Z}$ into disjoint intervals, in the sense that no ball starting in one interval visit any vertex of another interval before finding a hole. Hence, when one considers an interval $[X_i, X_{i+1}]$ between two holes $X_i$ and $X_{i+1}$, if one activates only the balls in this interval, the probability that no ball gets out of it does not depend on the rest of the configuration, and better than that, this probability would be the same if the size $n$ of the circle $\mathbb{Z}/n\mathbb{Z}$ were different: we can then reduce this size as much as it is useful for us, and take $n$ so small that $X_i = X_{i+1} \mod n$. So this probability is the same as the probability that balls do not reach a specified hole on a circle (corresponding to the identification of the two holes on the extremities of the block, see Figure 2).

**Lemma 2.2.** We use the same notation as in Theorem 1.2: we consider $X \subseteq \mathbb{Z}/n\mathbb{Z}$ of size $|X| = N_f$, and for every $i \in \mathbb{Z}/N_f\mathbb{Z}$, we set $\ell_i := \Delta_i^{(n)}X$. We also let $x$ be the nicely ordered sequence containing all the elements of $X$ (recall that it is such that $\pi(x_1) < \dots < \pi(x_{k-1}) < \pi(x_0)$, where $\pi$ is the canonical projection $\mathbb{Z}/n\mathbb{Z} \to [1, n]$). For every finite sequence $(b_i)_{1 \le i \le N_f}$ such that $\sum_i b_i = N_b$ and $\forall i, 0 \le b_i \le \ell_i/2$,

$$ \mathbb{P}^{n, N_b, N_h, p} (\mathbf{H}^1 = X \mid \mathrm{Cond}(\mathbf{H}^0, \mathbf{B}^0, X, (b_i))) = \prod_{i \in \mathbb{Z}/N_f\mathbb{Z}} \mathbb{P}^{\ell_i, b_i, b_{i+1}, p} (\mathbf{H}^1 = \{0\} \mid 0 \in \mathbf{H}^0) \quad (11) $$

$$ = \prod_{i \in \mathbb{Z}/N_f\mathbb{Z}} \frac{1}{b_i + 1}, \quad (12) $$

where we define, for any $H, B, X$ and $(b_i)_{1 \le i \le N_f}$ the event $\mathrm{Cond}(H, B, X, (b_i))$ corresponding to the conjunction of the following events: $X \subseteq H, \forall i, |H \cap \mathcal{I}| x_i, x_{i+1}[| = b_i$ and $\forall i, |B \cap \mathcal{I}| x_i, x_{i+1}[| = b_i$

Figure 2 illustrates this lemma. We prove it in Section 2.2.

In what follows we identify $\mathbb{Z}/N_f\mathbb{Z}$ with $[1, N_f]$, and use the two notation equivalently. We now use these two lemmas to prove Theorem 1.2.
Proof of Theorem 1.2. We work under $\mathbb{P}^{n,N_b,N_h,p}$, but we write $\mathbb{P}$ for short, since there is no ambiguity in this proof.

Let $X$ be given, and recall that the set

$$B^{(N_b, X)} = \left\{ (b_i)_{1 \le i \le N_f} : \sum_i b_i = N_b \text{ and } \forall i, 0 \le b_i \le \ell_i/2 \right\}$$

corresponds to the set of possible allocations of $N_b$ balls into $N_f$ intervals, without having more than $\ell_i/2$ balls in the $i$th interval.

The event $\mathbf{H}^1 = X$ can occur only if $X \subseteq \mathbf{H}^0$ and there are exactly as many holes as balls in every block. It gives equations (13) and (14) in the computation below.

$$\mathbb{P}^{n,N_b,N_h,p}(\mathbf{H}^1 = X) = \sum_{(b_i)_{1 \le i \le N_f} \in B^{(N_b,X)}} \mathbb{P}(\mathbf{H}^1 = X \cap \mathrm{Cond}(\mathbf{H}^0, \mathbf{B}^0, X, (b_i))) \quad (13)$$

$$= \sum_{(b_i)_{1 \le i \le N_f} \in B^{(N_b,X)}} \mathbb{P}(\mathbf{H}^1 = X | \mathrm{Cond}(\mathbf{H}^0, \mathbf{B}^0, X, (b_i))) \mathbb{P}(\mathrm{Cond}(\mathbf{H}^0, \mathbf{B}^0, X, (b_i))) \quad (14)$$

A counting argument gives, for any $b_i$ in $B^{(N_b,X)}$,

$$\mathbb{P}(\mathrm{Cond}(\mathbf{H}^0, \mathbf{B}^0, X, (b_i))) = \frac{\prod_{i=1}^{N_f} \binom{\ell_i}{b_i, b_i, \ell_i-2b_i}}{\binom{n}{N_h, N_b, n-N_h-N_b}} \quad (15)$$

Finally, applying Lemma 2.2 and Equation (15) to Equation (14) gives the right member of Equation (2) and thus concludes the proof of Theorem 1.2. □

## 2.2 Proof of Lemma 2.2

This section is devoted to the proof of Lemma 2.2. We say that an interval $[a, b]$ is full if every ball initially in the interval $[a, b]$ fills a hole inside $[a, b]$, and no hole inside $[a, b]$ is free at the end of the process. The proof principle is rather simple: since no ball ever visit any remaining hole, the probability to reach a given final configuration is the product of the probabilities that each interval between two consecutive final holes is full.

To prove it formally, we introduce and study *golf sequences*, which, as we mentioned in the introduction, were introduced by Fredes and Marckert [FM21]. We borrow some of their notation, but for completeness we explain everything here. Golf sequences are informally the sequences of trajectories of the balls that respect the rules we gave (i.e. there are $N_b$ trajectories, each trajectory starting at a vertex initially containing a ball and ending at the first hole that have not been reached by a previous trajectory).

**Golf sequences** can be defined on any connected graph $G = (V, E)$. As before, $P$ is the transition matrix of an irreducible Markov chain on $G$.

Assume that $\mathbf{B}^0$ and the activation clocks $(C(v), v \in \mathbf{B}^0)$ are given. Build the sequence of balls $S = (S_1, \dots, S_{N_b})$ containing all the elements of $\mathbf{B}^0$, ordered by activation time. In what follows we use this notation.

For a set of holes $H$ (such that, as usual, $|H| \ge |\mathbf{B}^0|$) and any ordering of the balls $S = (S_1, \dots, S_{N_b})$, we define the set of golf sequences, $\text{GolfSequences}^G[H, S]$, as follows. A sequence of paths $(w^{(1)}, \dots, w^{(N_b)})$ of respective lengths $(L_1, \dots, L_{N_b})$ belongs to $\text{GolfSequences}^G[H, S]$ if and only if, for every $i \le N_b$:
• the ith ball starts from $S_i$, i.e. $w_0^{(i)} = S_i$, and follows the path $w_0^{(i)}, \dots, w_{L_i}^{(i)}$, where each step $(w_k^{(i)}, w_{k+1}^{(i)})$ is an edge of $G$,

• the ith ball stops at the first hole that has not been filled yet, i.e. $\forall k < L_i, w_k^{(i)} \notin H \setminus \{w_{L_j}^{(j)}, j < i\}$ and $w_{L_i}^{(i)} \in H \setminus \{w_{L_j}^{(j)}, j < i\}$.

Moreover, for a sequence $w \in \text{GolfSequences}^G[H, S]$, we define its weight as follows:

$$ \text{Weight}(w) := \prod_{i=1}^{N_b} \prod_{j=0}^{L_i-1} P_{w_j^{(i)}, w_{j+1}^{(i)}}. $$

It corresponds to the probability that all the balls starting successively from $S_1$ to $S_{N_b}$, and doing one by one a random walk stopped when hitting a still available hole, perform exactly the sequence of paths $w$. We can then extend the definition of the weight to a set of sequences, setting, for every $W \subseteq \text{GolfSequences}^G[H, S]$,

$$ \text{Weight}(W) := \sum_{w \in W} \text{Weight}(w). $$

In other words, Weight can be seen as a probability measure on the set of golf sequences, and in particular, since our process is valid, $\text{Weight}(\text{GolfSequences}^G[H, S]) = 1$ (thanks to Proposition 1.1, and because the weight of $\text{GolfSequences}^G[H, S]$ is exactly the probability that every ball finds a hole in finite time in the corresponding golf process).

We define

$$ \text{GolfSequences}^G[H, S, H^F] := \{w \in \text{GolfSequences}^G[H, S] : H \setminus \{w_{L_i}^{(i)}, 1 \le i \le N_b\} = H^F\} \quad (16) $$

the subset of $\text{GolfSequences}^G[H, S]$ that leave free exactly the subset $H^F \subseteq H$ (thus with cardinality $N_f = |H| - N_b$).

Then,

$$ \text{Weight}(\text{GolfSequences}^G[H, S, H^F]) = \mathbb{P}(\mathbf{H}^1 = H^F), \quad (17) $$

where the probability is for our golf model on the same graph $G$, the same transition matrix $P$, with deterministic initial condition given by $H$ and $S$.

**From golf to mini-golf: Block decomposition of the golf sequences on $\mathbb{Z}/n\mathbb{Z}$**. We now focus again on the golf on $\mathbb{Z}/n\mathbb{Z}$. Until the end of this section, we use the same notation as in Theorem 1.2 and Lemma 2.2: we consider $X \subseteq \mathbb{Z}/n\mathbb{Z}$ of size $|X| = N_f$, and for every $i \in \mathbb{Z}/N_f\mathbb{Z}$, $\ell_i = \Delta_i^{(n)}X$. We also let $x$ be the nicely ordered sequence containing all the elements of $X$.

Lemma 2.3 decomposes golf sequences on the cycle $\mathbb{Z}/n\mathbb{Z}$ into a family of golf sequences on intervals between two consecutive holes, which are also golf sequences on smaller cycles (and are actually “mini-golf sequences”, since they leave only one remaining hole, see Figure 3 that illustrates this last point).

**Lemma 2.3** (Block decomposition of the golf sequences on $\mathbb{Z}/n\mathbb{Z}$). We let $(b_i)_{1 \le i \le N_f}$ be such that $\sum_i b_i = N_b$ and $\forall i, 0 \le b_i \le \ell_i/2$, and we consider $B, H \subseteq \mathbb{Z}/n\mathbb{Z}$ such that $X \subseteq H$ and $\forall i, |B \cap \{x_i, x_{i+1}\}| = |H \cap \{x_i, x_{i+1}\}| = b_i$. We let $S$ be an ordering of $B$.

Then, there exists a weight-preserving bijection

$$ f: \text{GolfSequences}^{\mathbb{Z}/n\mathbb{Z}}[H, S, X] \to \prod_{i \in \mathbb{Z}/N_f\mathbb{Z}} \text{GolfSequences}^{\mathbb{Z}/(\ell_i+1)\mathbb{Z}}[H_i, S_i, \{0\}] \\ W \mapsto (W^1, \dots, W^{N_f}) $$

where:
<figure><img src="image_4.png" /><figcaption>Figure 3: From golf to mini-golf: Correspondence between the restriction of golf sequences between two holes (at distance $\ell + 1$) of a large cycle and golf sequences on a cycle of size $\ell + 1$ with one remaining hole.</figcaption></figure>

Here $\ell = 8$. A black vertex corresponds to the initial position of a ball, a white vertex to a free hole, and a grey vertex to a hole that is occupied by a ball at the end. A dotted arrow associates a ball to the hole it filled. Each dotted arrow on the large circle corresponds to a dotted arrow on the small circle, illustrating the bijection defined in Lemma 2.3.

The restriction of $S = (s_1, \dots, s_7, s_8, \dots, s_{12}, \dots)$ to the interval between $x_i$ and $x_{i+1}$ gives $S_i = (s_1, s_2, s_3, s_4)$.

* for every $i \in \mathbb{Z}/N_f\mathbb{Z}$, $H_i$ is the restriction of $H$ to elements of $[[x_i, x_{i+1}]]$, shifted by $-x_i$ (formally, $H_i = \{h - x_i : h \in H \cap [[x_i, x_{i+1}]]\}$ seen as a subset of $\mathbb{Z}/(\ell_i + 1)\mathbb{Z}$, that contains $0$),

* for every $i \in \mathbb{Z}/N_f\mathbb{Z}$, $S_i$ is the restriction of $S$ to elements of $[[x_i, x_{i+1}]]$, also shifted by $-x_i$.

* The weight of $(W^1, \dots, W^{N_f})$ is $\prod_{i=1}^{N_f} \text{Weight}(W^i)$.

Moreover, the map $(H, S) \mapsto \prod_{i \in \mathbb{Z}/N_f\mathbb{Z}} (H_i, S_i)$ is also a bijection.

**Proof of Lemma 2.3.** Showing that $(H, S) \mapsto \prod_{i \in \mathbb{Z}/N_f\mathbb{Z}} (H_i, S_i)$ is a bijection is immediate. We now focus on $f$.

This lemma is a deterministic version of the block decomposition principle (see Section 2.1), and allows to prove this principle: we decompose golf sequences on $\mathbb{Z}/n\mathbb{Z}$ leaving $H^F$ free into golf sequences on intervals between elements of $H^F$. Then, golf sequences on an interval with two free holes on its border are trivially in bijection with golf sequences on a cycle with vertex 0 free (see Figure 3).

Recall that the $i$th block is, here, the interval $[[x_i + 1, x_{i+1} - 1]]$. We let $W = (w^{(1)}, \dots, w^{(N_b)}) \in \text{GolfSequences}^{\mathbb{Z}/n\mathbb{Z}}[H, S, X]$. For every $i$, we build the $i$th golf sequence on $\mathbb{Z}/(\ell_i + 1)\mathbb{Z}$ as the restriction of $W$ to the $i$th block. More precisely, we let $W^i$ be the golf sequence that contains the paths of the balls that belong to the $i$th block, shifted so that they now belong to $\mathbb{Z}/\ell_i\mathbb{Z}$:

$$W^i = ((w_k^{(j)} - x_i)_{0 \le k \le L_j})_{j \in \alpha^i}$$

where $\alpha^i$ is the sorted sequence of the indices of the balls that belong to the $i$th block: $\exists j : \alpha^i = j \iff S_j \in [[x_i, x_{i+1}]]$.

We can easily verify that $(W^1, \dots, W^{N_f}) \in \prod_{i \in \mathbb{Z}/N_f\mathbb{Z}} \text{GolfSequences}^{\mathbb{Z}/(\ell_i+1)\mathbb{Z}}[H_i, S_i, \{0\}]$. In fact, the important point to note is that on any interval $[[x_i + 1, x_{i+1} - 1]]$, the order of
the balls is the one induced by the order of the balls on $\mathbb{Z}/n\mathbb{Z}$, so in particular the defined trajectories still end on the first free hole they reach.

The application $f$ is clearly bijective, and it is weight-preserving, since the weight of a trajectory only depends on the total number of steps to the right and to the left, so simple computation gives $\text{Weight}(W) = \prod_{k=1}^{N_f} \text{Weight}(W^k)$. $\square$

Now we can conclude by proving Lemma 2.2.

*Proof of Lemma 2.2.* Recall that we simply write $\mathbb{P}$ for $\mathbb{P}^{n,N_b,N_h,p}$, and otherwise we use the notation $\mathbb{P}^{\ell_i,b_i,b_{i+1},p}$.

We fix an arbitrary permutation $\sigma$ on $\mathbb{Z}/n\mathbb{Z}$. To any set of balls $B \subseteq \mathbb{Z}/n\mathbb{Z}$, we associate $S(B) = S(B, \sigma)$ the sequence of the elements of $B$ arranged in increasing order (with respect to $\sigma$). It corresponds to the order according to which the balls will be activated: during the whole computation below, we assume that the order induced by the clocks is compatible with $\sigma$, and we write the assumption $\text{Order}(\mathbf{C}) = \sigma$. Then, $\sigma_{[x_i,x_{i+1}]}$ is the permutation of $\mathbb{Z}/\ell_i\mathbb{Z}$ induced by the restriction of $\sigma$ to $\llbracket x_i, x_{i+1} \rrbracket$ (so that $S(B_i, \sigma_{[x_i,x_{i+1}]})$ is the sequence of elements of $b_i = B \cap \llbracket x_i, x_{i+1} \rrbracket$ arranged in increasing order with respect to $\sigma$, and then shifted by $-x_i$).

We give a sequence of identities now, and we will provide some explanations after. Fix some $(b_i)_{1 \le i \le N_f}$ such that $\sum_i b_i = N_b$ and $\forall i, 0 \le b_i \le \ell_i/2$. We have

$$ \mathbb{P} (\mathbf{H}^1 = X | \text{Cond}(\mathbf{H}^0, \mathbf{B}^0, X, (b_i)) \text{ and } \text{Order}(\mathbf{C}) = \sigma) \quad (18) $$

$$ = \frac{1}{\prod_{i=1}^{N_f} (b_i, b_i, \ell_i - 2b_i)} \sum_{H, B: \text{Cond}(H, B, X, (b_i))} \mathbb{P} \left( \mathbf{H}^1 = X \mid \begin{array}{l} \mathbf{H}^0 = H, \mathbf{B}^0 = B \\ \text{and } \text{Order}(\mathbf{C}) = \sigma \end{array} \right) \quad (19) $$

$$ = \frac{1}{\prod_{i=1}^{N_f} (b_i, b_i, \ell_i - 2b_i)} \sum_{H, B: \text{Cond}(H, B, X, (b_i))} \sum_{w \in \text{GolfSequences}^{\mathbb{Z}/n\mathbb{Z}}[H, S(B, \sigma), X]} \text{Weight}(w) \quad (20) $$

$$ = \frac{1}{\prod_{i=1}^{N_f} (b_i, b_i, \ell_i - 2b_i)} \prod_{i=1}^{N_f} \sum_{\substack{H_i, B_i \subseteq \mathbb{Z}/\ell_i\mathbb{Z}: \\ 0 \in H_i \text{ and } |H_i| = |B_i| = b_i}} \sum_{w_i \in \text{GolfSequences}^{\mathbb{Z}/(\ell_i+1)\mathbb{Z}}[H_i, S(B_i, \sigma), \{0\}]} \text{Weight}(w_i) \quad (21) $$

$$ = \prod_{i=1}^{N_f} \frac{1}{(b_i, b_i, \ell_i - 2b_i)} \sum_{\substack{H_i, B_i \subseteq \mathbb{Z}/\ell_i\mathbb{Z}: \\ 0 \in H_i \text{ and } |H_i| = |B_i| = b_i}} \mathbb{P}^{\ell_i, b_i, b_{i+1}, p} \left( \mathbf{H}^1 = \{0\} \mid \text{and } \begin{array}{l} \mathbf{H}^0 = H_i, \mathbf{B}^0 = B_i \\ \text{Order}(\mathbf{C}) = \sigma_{[x_i, x_{i+1}]} \end{array} \right) \quad (22) $$

$$ = \prod_{i=1}^{N_f} \mathbb{P}^{\ell_i, b_i, b_{i+1}, p} (\mathbf{H}^1 = \{0\} \mid 0 \in \mathbf{H}^0 \text{ and } \text{Order}(\mathbf{C}) = \sigma_{[x_i, x_{i+1}]}) . \quad (23) $$

**Details on the computation.** We obtain (19) from (18) by noting that every initial configuration (corresponding to the event $\{\mathbf{H}^0 = H, \mathbf{B}^0 = B\}$, for every $H, B$ appearing in the sum in (19)) has the same probability, and using the fact that if $A, B, (B_i)_i$ are events such that $B = \cup_{i=1}^K B_i$ (it is a disjoint union) and $\forall i, j, \mathbb{P}(B_i) = \mathbb{P}(B_j)$, then $\frac{1}{K} \sum_i \mathbb{P}(A|B_i) = \frac{1}{K \mathbb{P}(B_1)} \sum_i \mathbb{P}(A \cap B_i) = \frac{1}{K} \frac{\mathbb{P}(A|B)\mathbb{P}(B)}{\mathbb{P}(B_1)} = \mathbb{P}(A|B)$.

To go from (19) to (20), we use Equation (17) that gives the correspondence between weights and probabilities.

The passage from (20) to (21) uses Lemma 2.3.

We then recognize mini-golfs and do the same in the other way round.
**Conclusion.** We can then use the Commutation property (see Remark 1) to conclude directly that

$$ \mathbb{P}(\mathbf{H}^1 = X | \mathrm{Cond}(\mathbf{H}^0, \mathbf{B}^0, X, (b_i))) = \prod_{i=1}^{N_f} \mathbb{P}^{\ell_i, b_i, b_{i+1}, p}(\mathbf{H}^1 = \{0\} | 0 \in \mathbf{H}^0) = \prod_{i=1}^{N_f} \frac{1}{b_i + 1}. \qquad (24) $$

□

## 2.3 Proof of Theorem 1.5

The proof of Theorem 1.5 follows exactly the same reasoning as the proof of Theorem 1.2; we give the main arguments and computation here.

*Proof.* As in the statement of Theorem 1.5, we consider the p-parking model with parameters $n$, $N_b$ and $p$. Recall that here, the set of balls $\mathbf{B}^0$ is a multiset of vertices of $\mathbb{Z}/n\mathbb{Z}$. When $N_b = n - 1$, i.e. there is only one remaining hole at the end, then we have, as an analogue of Lemma 2.1 for the mini-golf case, $\forall x \in \mathbb{Z}/n\mathbb{Z}$,

$$ \mathbb{P}^{\mathrm{Parking},n,N_b,p}(\mathbf{H}^1 = \{x\} | x \notin \mathbf{B}^0) = \frac{n^{n-2}}{(n-1)^{n-1}}. \qquad (25) $$

The proof is similar to the proof of Lemma 2.1: invariance by rotation of the process gives $\mathbb{P}^{\mathrm{Parking},n,N_b,p}(\mathbf{H}^1 = \{x\}) = \frac{1}{n}$, and Equation (25) then comes from the fact that $\mathbb{P}^{\mathrm{Parking},n,N_b,p}(x \notin \mathbf{B}^0) = \left(\frac{n-1}{n}\right)^{n-1}$.

For general $n$, $N_b$ and $X \subseteq \mathbb{Z}/n\mathbb{Z}$ of size $|X| = N_f = n - N_b$, recall that we set $\ell_i := \Delta_i^{(n)} X$ for every $i \in \mathbb{Z}/N_f\mathbb{Z}$. Then, we have:

$$ \mathbb{P}^{\mathrm{Parking},n,N_b,p}(\mathbf{H}^1 = X) = \mathbb{P}\left(\mathbf{H}^1 = X \cap \left(\bigcap_{i=1}^{X \cap \mathbf{B}^0 = \emptyset} \mathbb{B}^0 \cap \mathbb{B}_{x_i, x_{i+1}}^0\right) \right) \qquad (26) $$

$$ = \mathbb{P}\left(\mathbf{H}^1 = X \mid \left(\bigcap_{i=1}^{X \cap \mathbf{B}^0 = \emptyset} \mathbb{B}^0 \cap \mathbb{B}_{x_i, x_{i+1}}^0\right) \right) \mathbb{P}\left(\left(\bigcap_{i=1}^{X \cap \mathbf{B}^0 = \emptyset} \mathbb{B}^0 \cap \mathbb{B}_{x_i, x_{i+1}}^0\right) \right) \qquad (27) $$

(where $\mathbb{P}$ refers to $\mathbb{P}^{\mathrm{Parking},n,N_b,p}$).

Then, we can do the same decomposition as we did in the proof of Lemma 2.2 (we do not prove it again, but the same proof with golf sequences works perfectly here too):

$$ \mathbb{P}\left(\mathbf{H}^1 = X \mid \text{and } \forall i, \left|\mathbf{B}^0 \cap \mathbb{B}_{x_i, x_{i+1}}^0\right| = b_i\right) = \prod_{i \in \mathbb{Z}/N_f\mathbb{Z}} \mathbb{P}^{\mathrm{Parking}, \ell_i+1, \ell_i, p}(\mathbf{H}^1 = \{0\} | 0 \notin \mathbf{B}^0) \qquad (28) $$

$$ = \prod_{i \in \mathbb{Z}/N_f\mathbb{Z}} \frac{(\ell_i + 1)^{\ell_i - 1}}{\ell_i^{\ell_i}}. \qquad (29) $$

Recall that $\mathbf{B}^0$ is characterized by the vector $W = (W_1, \dots, W_n)$, such that $W_k$ counts the multiplicity of $k$ in $\mathbf{B}^0$ ($W$ has the multinomial distribution with parameter $(N_b; 1/n, \dots, 1/n)$). Using Equation (25) and the fact that $\mathbb{P}\left(\text{and } \forall i, \left|\mathbf{B}^0 \cap \mathbb{B}_{x_i, x_{i+1}}^0\right| = b_i\right) = \binom{N_b}{\ell_1, \dots, \ell_{N_f}} \prod_{i \in \mathbb{Z}/N_f\mathbb{Z}} \left(\frac{\ell_i}{n}\right)^{\ell_i}$, we finally obtain:

$$ \mathbb{P}^{\mathrm{Parking},n,N_b,p}(\mathbf{H}^1 = X) = \frac{1}{n^{N_b}} \binom{N_b}{\ell_1, \dots, \ell_{N_f}} \prod_{i \in \mathbb{Z}/N_f\mathbb{Z}} (\ell_i + 1)^{\ell_i - 1}. \qquad (30) $$

□
We can notice that when $n = N_b + 1$ and $p = 1$, Equation (25) can be seen as a reformulation of the fact that the number of parking functions on the line of length $k$ is $(k+1)^{k-1}$ (see [KW66], or [Rio69] for a simpler proof, sometimes known as Pollak's proof, which we summarize here): on $\mathbb{Z}/n\mathbb{Z}$, the probability that vertex 0 is free at the end is equal to the number of parking functions on $\{1, \dots, n-1\}$ (leaving $n$ free, thus equal to $n^{n-2}$) divided by the total number of assignments of the balls (which is equal to $n^{n-1}$, each of the $n-1$ balls choosing a starting vertex among the $n$ vertices).

## 2.4 Critical window: combinatorial preliminaries for the proof of Theorem 1.3

Before giving the proof of Theorem 1.3, we discuss some useful combinatorial facts, that will lead us to deduce block-size statistics in the golf process, from the study of forests and of finite paths.

**From block sizes to sizes of trees in a marked forest.** Catalan numbers $C_m = \binom{2m}{m}/(m+1)$ are known to enumerate various combinatorial objects, including rooted planar trees with $m$ edges, Dyck paths with $2m$ steps, as well as rooted complete binary trees with $m$ internal nodes (i.e. trees with a total of $2m+1$ nodes, such that every internal node has exactly 2 children).

We let $\mathcal{F}(n, k)$ be the set of forests $(f_0, \dots, f_{k-1})$ with $k$ rooted complete binary trees and a total of $n$ nodes. We call tree-size vector of a forest $f = (f_0, \dots, f_{k-1}) \in \mathcal{F}(n, k)$ the sequence

$$|f| = (|f_0|, \dots, |f_{k-1}|),$$

where $|f_i|$ is the number of nodes of the tree $f_i$. We can note that $\sum_{i=0}^{k-1} |f_i| = n$.

In all what follows, we will have $k = N_f$ and $n = 2N_b + N_f$, so that the parameters correspond to those of the golf model. In particular, if $\sum_j (2b_j + 1) = n$, then there are $\prod_{j=0}^{k-1} C_{b_j}$ forests of $\mathcal{F}(n, k)$ such that the $j$th tree has $(2b_j + 1)$ nodes, for every $j$.

It is known that $|\mathcal{F}(n, k)| = \frac{k}{n} \binom{n}{\frac{n}{2}}$ (this formula is folklore in combinatorics, and can be computed using exactly the same reasoning as Pitman did in the case of plane forests without binarity condition [Pit06, section 6.3]).

We also define $\mathcal{F}^{\bullet}(n, k)$ as the set of forests $(f_0^{\bullet}, f_1^{\bullet}, \dots, f_{k-1}^{\bullet})$ such that $f_0^{\bullet} = (f_0, v)$ is a tree $f_0$ marked at one of its nodes $v$, and $(f_0, \dots, f_{k-1})$ is a forest of $\mathcal{F}(n, k)$. For every family $b_0, \dots, b_{k-1}$ such that $\sum_j (2b_j + 1) = n$, there are

$$(2b_0 + 1) \prod_{j=0}^{k-1} C_{b_j} \qquad (31)$$

forests of $\mathcal{F}^{\bullet}(n, k)$ such that the $i$th tree has $b_i$ internal nodes (hence $2b_i + 1$ nodes). The additional factor $2b_0 + 1$ is the number of ways to choose a vertex in $f_0$.

In the sequel, we let $\mathbf{F}_{n,k}^{\bullet}$ be a random forest taken uniformly in $\mathcal{F}^{\bullet}(n, k)$.

We now go back to our golf model on the circle. We have the following results, which is a corollary of Theorem 1.2, and justifies our focus on forests:

**Corollary 2.4.** We consider a golf process under the distribution $\mathbb{P}^{n,N_b,N_h,p}$, when $N_b + N_h = n$ and $N_f = N_h - N_b$. The distribution of the block sizes vector in this model corresponds to the tree sizes in the uniform random forests $\mathbf{F}_{n,N_f}^{\bullet}$:

$$\left(\Delta_i^{(n)} \mathbf{H}^1 + 1\right)_{0 \le i < N_f} \stackrel{d}{=} |\mathbf{F}_{n,N_f}^{\bullet}|.$$

Notice here that the block containing 0 is size-biased.
Proof. When $n = N_b + N_h$, Theorem 1.2 rewrites, for any $X$ such that $|X| = N_h - N_b$,

$$ \mathbb{P}^{n, N_b, N_h, p} (\mathbf{H}^1 = X) = \frac{1}{\binom{n}{N_b}} \prod_i \frac{1}{b_i + 1} \binom{2b_i}{b_i}, $$

where for every $i$, $b_i = \ell_i/2 = (\Delta_i^{(n)}X)/2$. We can notice here that this probability is proportional to $\prod_i C_{b_i}$.

Now we set $b_0, \dots, b_{N_f-1}$ such that $\sum b_i = N_b$. There are exactly $2b_0 + 1$ sets $X$ such that $\forall i, b_i = (\Delta_i^{(n)}X)/2$ (this is due to the fact that we indexed the process $\Delta^{(n)}X$ so that $\Delta_0^{(n)}X$ is the number of points in the block that “contains 0”). We thus finally obtain

$$ \mathbb{P}^{n, N_b, N_h, p} \left( \forall i, \Delta_i^{(n)} \mathbf{H}^1 = 2b_i \right) = \frac{2b_0 + 1}{\binom{n}{N_b}} \prod_i C_{b_i}. \quad (32) $$

Moreover, the probability $\mathbb{P}(|\mathbf{F}_{n, N_f}^\bullet| = (2b_0 + 1, \dots, 2b_{N_f-1} + 1))$ is proportional to $(2b_0 + 1) \prod_{j=0}^{N_f-1} C_{b_j}$ (see Equation (31)), so finally, since proportional probability distributions are equal$^5$,

$$ \mathbb{P}(|\mathbf{F}_{n, N_f}^\bullet| = (2b_0 + 1, \dots, 2b_{N_f-1} + 1)) = \mathbb{P}^{n, N_b, N_h, p} \left( \forall i, \Delta_i^{(n)} \mathbf{H}^1 = 2b_i \right). $$

□

**From marked forests to forests.** Corollary 2.4 links block sizes and sizes of trees in a marked forest (which thus exhibit a size bias). It can be useful here to understand further the role played by the mark, which is a bit subtle. In the next lemma, we assert that the sorted tree sizes of $\mathbf{F}_{n,k}$ and of $\mathbf{F}_{n,k}^\bullet$ have the same distribution: the reason is that it is equivalent to draw a marked forest uniformly at random in $\mathcal{F}^\bullet(n, k)$, and to draw a forest uniformly at random in $\mathcal{F}(n, k)$, to mark one of its nodes uniformly in the whole forest and shift the tree indices in $\mathbb{Z}/k\mathbb{Z}$ so that this node belongs to the first tree. Formally, we let $\mathbf{F}_{n,k} = (\mathbf{f}_0, \dots, \mathbf{f}_{k-1})$ be a forest taken uniformly in $\mathcal{F}(n, k)$, $\mathbf{u}$ be a node chosen uniformly in $\mathbf{F}_{n,k}$, and $\mathbf{i}$ be the index of the tree $\mathbf{f}_i$ that contains $\mathbf{u}$. The forest $R_{\mathbf{u}}(\mathbf{F}_{n,k}) = ((\mathbf{f}_i, \mathbf{u}), \mathbf{f}_{i+1} \bmod k, \dots, \mathbf{f}_{i+(k-1)} \bmod k)$ is the forest obtained by shifting the indices of $\mathbf{F}_{n,k}$, so that $\mathbf{f}_i$ is now the first tree.

**Lemma 2.5.** $R_{\mathbf{u}}(\mathbf{F}_{n,k})$ and $\mathbf{F}_{n,k}^\bullet$ have the same distribution. It implies that

$$ \text{Sorted}(|\mathbf{F}_{n,k}|) \stackrel{(d)}{=} \text{Sorted}(|\mathbf{F}_{n,k}^\bullet|). \quad (33) $$

Proof. Only the first statement needs to be proved, since the tree sizes of $R_{\mathbf{u}}(\mathbf{F}_{n,k})$ and $\mathbf{F}_{n,k}$ coincide (up to a rotation of the indices). For this, it suffices to observe that, for every $\mathbf{f}^\bullet = (f_1^\bullet, f_2^\bullet, \dots, f_k^\bullet) \in \mathcal{F}^\bullet(n, k)$,

$$ \mathbb{P}(R_{\mathbf{u}}(\mathbf{F}_{n,k}) = \mathbf{f}^\bullet) = \frac{k}{n} \frac{1}{|\mathcal{F}(n, k)|}. \quad (34) $$

Since this does not depend on $\mathbf{f}^\bullet$, this is the uniform distribution on $\mathcal{F}^\bullet(n, k)$.

□

From Equation (34), we deduce the following formula, which will be useful later:

$$ |\mathcal{F}^\bullet(n, k)| = \binom{n}{\frac{n-k}{2}}. \quad (35) $$

<footnote>$^5$since each of them has total mass equal to 1</footnote>
**From forests to paths, from sizes of trees in a forest to excursion lengths above the current minimum in a path.** It is well-known that forests are in bijection with some paths, and can be studied with them.

For a path $w = (w_i, 0 \le i \le M)$ starting at $w_0 = 0$, ending at time $M \ge 0$ (for some $M$), and with increments $w_i - w_{i-1} \in \{+1, -1\}$ for all $i$, denote by $\tau_k(w) = \inf\{n : w_n = k\}$ the hitting time of $k$ by $w$ (set $+\infty$, if $k$ is not reached). We simply write $\tau_k$ when $w$ is implicit.

For every $n \ge 0, k \ge 1$, there is a bijection between $\mathcal{F}(n, k)$ and the set of paths $P(n, k)$ with $n$ steps such that $\tau_{-k} = n$. This can be viewed as a simple consequence of the bijection that encodes a rooted complete binary tree by a Łukasiewicz walk: for a rooted complete binary tree $t$, we consider the order induced by a depth-first exploration of its nodes, and we let $n_i$ be the number of children of the $i$th node. Then we define the path $w$ such that for every $i$, $w_i = \sum_{j=1}^i (n_i - 1)$. This path $w$ is a Dyck path augmented by an additional $-1$ step. Notice that a tree reduced to its root is sent on a single down step. We can then extend the definition of the Łukasiewicz walk to a forest, by simply concatenating the paths associated to each tree of this forest. It is also a bijection, since we can uniquely decompose $w \in P(n, k)$ as the concatenation of $k$ augmented Dyck paths, the $i$th path being the restriction of $w$ between times $\tau_{-(i-1)}$ and $\tau_{-i}$. This bijection is illustrated on Subfigure 4a.

The uniform distribution on $\mathcal{F}(n, k)$ is then sent by this bijection onto the uniform distribution on $P(n, k)$, and this latter can be viewed as the distribution of a simple random walk ($W_i, 0 \le i \le n$) (with i.i.d. increments, and distribution $\mathbb{P}(W_i - W_{i-1} = +1) = p$ and $\mathbb{P}(W_i - W_{i-1} = -1) = 1-p$, for some $p \in (0, 1)$), conditioned<fnref n="6" /> by $\tau_{-k} = \tau_{-k}(W) = n$. We denote by $\mathbb{P}_p$ the associated probability measure on infinite random walks.

The tree sizes, in this representation, correspond to the $(\tau_{-j} - \tau_{-(j-1)})$, and often, in the literature, they are viewed as “excursion lengths above the current minimum process”. Namely, an excursion interval above the current minimum process of a function $f$ is defined as a maximal non empty interval $e = (\ell, r)$ such that $f(\ell) = f(r) = \min_{s \le \ell} f(s)$ (the corresponding excursion is then the restriction of $f$ to this interval). The length of an excursion interval $e = (\ell, r)$ is $|e| := r - \ell$. Excursions intervals are characterized by their left bound and their length, so we define the set of excursion intervals $\text{Exc}(f)$ as the set of these $(\ell, r - \ell)$. Then, for $W$ of length $n$ such that $\tau_{-k}(W) = n$, we have $\text{Exc}(W) = \{(\tau_{-j}, \tau_{-j} - \tau_{-(j-1)} - 1), 0 \le j < k\}$.

We can finally define **Sorted**($|\text{Exc}(W)|$) as the sequence of sorted lengths of excursion intervals. We then have the following corollary of Corollary 2.4, Lemma 2.5, and of what we have just said above:

**Corollary 2.6.** Let $\mathbf{H}^1$ be the set of remaining holes under $\mathbb{P}^{n, N_b, N_h, p}$, with $N_b + N_h = n$ and $N_f = N_h - N_b$, and let $W$ be a uniform path in $P(n, N_f)$. Then, the sorted block-size process have the same distribution as the sorted lengths of excursion intervals:

$$ \text{Sorted}(\Delta^{(n)}\mathbf{H}^1) \stackrel{d}{=} \text{Sorted}(|\text{Exc}(W)|) \qquad (36) $$

$$ \stackrel{(d)}{=} \text{Sorted} \left( \left( (\tau_{-j-1} - \tau_{-j} - 1) \right)_{0 \le j < N_f} \right). \qquad (37) $$

**Discussion on the paths associated to marked forests.** This paragraph is not required for the understanding of the proof of Theorem 1.3, except for the proof of (iii).

<footnote n="6">⁶This remarkable property, that any $p$ does the job, is a key point, since we can in particular choose the “best” $p$, according to the context, in order to bias the unconditioned walk so that it has a behavior similar to the conditioned walk (see for example Equation (53) in the proof of (i)).</footnote>
<figure><img src="image_5.png" /><figcaption>(a) Illustration of the bijection mapping forests of $\mathcal{F}(15, 3)$ to paths of $P(15, 3)$ (such that $\tau_{-3} = 15$), using the Łukasiewicz walk. The $i$th excursion above the current minimum has size $|t_i| - 1$.</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>(b) Illustration of the bijection mapping forests of $\mathcal{F}^{\bullet}(15, 3)$ to paths $W$ of length 15 ending at $-3$. The first path is again obtained doing a Łukasiewicz walk, then the path is rotated so that the first step of the path is the one associated to the marked vertex. Notice that the mark on the second path can be deleted, since it is necessarily on the first step of the path. Another important remark is that the excursions of the second path do not directly correspond to the sizes of trees of $F$, since the excursion corresponding to the first tree has basically been cut into two pieces.</figcaption></figure>

Figure 4: Illustration of the bijections between forests and paths.

It also strengthens our study of excursions and allows to understand more deeply the connections made with the asymptotics of Chassaing-Louchard in Section 2.6.

We define the (discrete) rotation of a function as:

$$ \mathrm{rot}^{(n)}(f, r) = t \mapsto \begin{cases} f(t+r) - f(r) & \text{if } t \le n-r, \\ f(n) - f(r) + f(t-(n-r)) & \text{if } t > n-r. \end{cases} \qquad (38) $$

We will also use its continuous analogue (sometimes known as the Vervaat transform, see Section 2.6 for a discussion on Vervaat's theorem):

$$ \mathrm{rot}(f, r) = t \mapsto \begin{cases} f(t+r) - f(r) & \text{if } t \le 1-r, \\ f(1) - f(r) + f(t-(1-r)) & \text{if } t > 1-r. \end{cases} \qquad (39) $$

We have proven in Equation (35) that there are $\binom{n}{(n-k)/2}$ marked forests with $(n-k)/2$ trees and $n$ nodes. It is also the cardinality of $B(n, k)$, the set of paths of length $n$ ending at $-k$, i.e. bridges. There is a bijection between $\mathcal{F}^{\bullet}(n, k)$ and $B(n, k)$: To a marked forest $F^{\bullet} = (F, v) \in \mathcal{F}^{\bullet}(n, k)$ we can associate a path $\mathcal{L}(F^{\bullet}) = \mathcal{L}(F)$ of $P(n, k)$ (with the Łukasiewicz walk, as for the bijection between $\mathcal{F}(n, k)$ and $P(n, k)$). Then if $v$ corresponds to the $i$th vertex in the first tree (in the bread-first search order, which is the order taken in the Łukasiewicz walk), one can consider the rotation of $\mathcal{L}(F^{\bullet})$, $p := \mathrm{rot}^{(n)}(\mathcal{L}(F^{\bullet}), i)$. This is a path ending at $-k$ at time $n$ (the condition $\tau_{-k} = n$ can be satisfied or not). Reciprocally, if $i$ is such that $n - i = \mathrm{argmin}(p)$, then $\mathrm{rot}^{(n)}(p, -i) \in P(n, k)$ (here and in what follows, if the minimum of a path $p$ is reached several times, then $\mathrm{argmin}(p)$ is the smallest $k$ such that $p_k = \mathrm{min}(p)$). As $i$ encodes the marked vertex $v$, $\mathrm{rot}^{(n)}(p, -i)$ encodes
a Łukasiewicz walk, hence a forest F (since the Łukasiewicz walk gives a bijection), thus $(F, v) \mapsto \text{rot}^{(n)}(\mathcal{L}(F^{\bullet}), i)$ is a bijection. It is illustrated on Subfigure 4b.

Thus, if $R^{(n,N_f)}$ is the Łukasiewicz walk associated to a uniform marked forest $\mathbf{F}^{\bullet}_{n,N_f}$ and $B^{(n,N_f)} \sim \mathcal{U}(B(n, N_f))$ (in the sequel, we will often denote the uniform distribution over a set $S$ by $\mathcal{U}(S)$), then

$$ \text{rot}^{(n)}(B^{(n,N_f)}, \text{argmin}(B^{(n,N_f)})) \sim R^{(n,N_f)} \quad (40) $$

and

$$ \text{rot}^{(n)}(R^{(n,N_f)}, \mathcal{U}(\llbracket 0, \tau_{-1}(R^{(n,N_f)}) \rrbracket)) \sim B^{(n,N_f)} \quad (41) $$

(here, the variable $\mathcal{U}(\llbracket 0, \tau_{-1}(R^{(n,N_f)}) \rrbracket)$ represents the uniform choice of a vertex in the first tree of the forest associated to $R^{(n,N_f)}$).

Together with Corollary 2.4, it implies:

**Corollary 2.7.** We consider $\mathbf{H}^1$ under $\mathbb{P}^{n,N_b,N_h,p}$, with $N_b + N_h = n$, $N_f = N_h - N_b$. We let $b \sim \mathcal{U}(B(n, N_f))$ and $p = \text{rot}^{(n)}(b, \text{argmin}(b))$, and then

$$ (\Delta_i^{(n)} \mathbf{H}^1)_{0 \le i < N_f} \stackrel{d}{=} |\text{Exc}(p)| \quad (42) $$

$$ \stackrel{(d)}{=} ((\tau_{-j-1}(p) - \tau_{-j}(p) - 1))_{0 \le j < N_f}. \quad (43) $$

It improves Corollary 2.6, since here the equality in distribution holds not only for the sorted sequences, but for the whole sequences.

**Remark 12.** As illustrated on Figure 4b, the tree sizes of a marked forest $F^{\bullet} = (F, v) \in \mathcal{F}^{\bullet}(n, k)$ cannot be directly obtained from excursions of the associated bridge $b = \text{rot}^{(n)}(\mathcal{L}(F), v)$, because the sub-path corresponding to the first tree may be cut into two pieces (at the beginning and the end of $b$). Yet, the size of the first tree is equal to $\tau_{-1}(b) + n - \tau_{-k}(b)$, while the size of the ith tree (for every $i \ne 1$) is still equal to $\tau_{-i-1}(b) - \tau_{-i}(b)$.

**Maximum size of a block as a non-increasing function of $N_f$.** The following corollary enables to compare (for the stochastic order) the maximum size of a block in the golf process $\text{Max}(\Delta^{(n,N_f)}\mathbf{H}^1)$, for different values of the parameters $n$ and $N_f$ (where we have adapted the notation, setting $\Delta^{(n,N_f)}\mathbf{H}^1 = \Delta^{(n)}\mathbf{H}^1$, in order to make explicit the dependence on $N_f$).

**Corollary 2.8.** We again assume that $n = N_b + N_h$, and write $N_f = N_h - N_b$. Then, for any fixed $n$, $\text{Max}(\Delta^{(n,N_f)}\mathbf{H}^1)$ is a non-increasing function of $N_f$ for the stochastic order.

*Proof.* Thanks to Corollary 2.4, it suffices to prove the same result for $\text{Max}(|\mathbf{F}^{\bullet}_{n,N_f}|)$, the maximum tree size in a random marked forest with $N_f$ (complete binary) trees and $n$ nodes. Recall that the set of marked forests $\mathcal{F}^{\bullet}(n, N_f)$ is in bijection with the set of bridges $B(n, N_f)$. The main idea is then to couple uniform bridges of lengths $n$ ending in $-N_f$ with uniform bridges of lengths $n$ ending in $-N_f + 2$, such that the maximum size of a tree in the corresponding forests can be compared.

We consider the random function $\phi_{n,N_f} : B(n, N_f) \times \{1, \dots, (n + N_f)/2\} \to B(n, N_f - 2)$ that changes some down step of a bridge ending in $-N_f$ to an up step, giving a bridge ending at $-N_f + 2$. Formally, if $b \in B(n, N_f)$ and $i \in \{1, \dots, (n + N_f)/2\}$, and if $k_i$ is the index of the ith down step, then $\phi_{n,N_f}(b, i)$ is the bridge of $B(n, N_f - 2)$ obtained by replacing the down step at index $k_i$ by an up step. This bijection is illustrated on Figure 5.
<figure><img src="image_7.png" /><figcaption>Figure 5: Illustration of the bijection $\phi_{n,N_f}$.</figcaption></figure>

Finally, it is straightforward to check that if $k_i$ belongs to the $j$th tree, the forest corresponding to $\phi_{n,N_f}(b, i)$ is the forest where the $j$th tree (modulo $N_f - 2$) has size equal to the sum of the sizes of the trees $j, j+1$ and $j+2$ (also modulo $N_f - 2$) in the forest coded by $b$, while the other trees remain unchanged, and in particular have the same size. (It can be done formally using Remark 12). It implies that the maximum size of a tree in $b$ is not greater than the maximum size of a tree in $\phi_{n,N_f}(b, i)$.

Moreover, if $b \sim \mathcal{U}(B(n, N_f))$ and $i \sim \mathcal{U}(\{1, \dots, (n + N_f)/2\})$, then

$$ \phi_{n,N_f}(b, i) \sim \mathcal{U}(B(n, N_f - 2)). $$

Combining this with the previous paragraph gives $\text{Max}(|\mathbf{F}_{n,N_f}|) \le \text{Max}(|\mathbf{F}_{n,N_f-2}|)$ for the stochastic order. $\square$

We now have all the combinatorial tools we need to prove Theorem 1.3. We end these preliminaries by stating the following proposition, which gives the convergence of a random walk conditioned by first hitting $-\lambda\sqrt{n}$ at time $n$, up to normalization, to a Brownian process $W^{(\lambda)}$ such that $\tau_{-\lambda}(W^{(\lambda)}) = 1$.

**Proposition 2.9.** We consider $k = k(n)$ such that $k(n)/\sqrt{n} \to \lambda \in (0, +\infty)$ (and $n$ and $k(n)$ have the same parity). We let $(W_i, i \ge 0)$ be a simple random walk. In what follows, we view $W = (W_t, t \ge 0)$ as a continuous process, obtained by linear interpolation of the sequence $(W_k, k \ge 0)$. For every $n$, we let $W^{(n,\lambda)}$ be a process distributed as $(W_{nt}/\sqrt{n}, 0 \le t \le 1)$ conditioned by $\tau_{-k(n)}(W) = n$. As $n$ goes to infinity, $W^{(n,\lambda)}$ converges in distribution in $C[0, 1]$ (equipped with the uniform topology), to $W^{(\lambda)}$ a Brownian motion $B$ conditioned by $\tau_{-\lambda}(B) = 1$, where $\tau_{-\lambda}(B) := \inf\{t > 0 : B_t = -\lambda\}$.

The process $W^{(\lambda)}$ is called a first passage bridge from 0 to $\lambda$. In Appendix A.3, we prove this proposition and we give a formal definition of a Brownian motion conditioned by $\tau_{-\lambda}(B) = 1$. Chassaing and Janson [BCP03] give some similar results, for random walks with different distribution, in Theorems 4.1, 4.2 and 4.3.

## 2.5 Critical window: proof of Theorem 1.3

*Proof of Theorem 1.3.* In all the proof, we let $k = k(n) = N_f(n)$. Notice that $n$ and $k(n)$ have the same parity (since this is always true for $n = N_b + N_h$ and $N_f = N_h - N_b$).

*Proof of (i).* We assume that $k(n) = an + o(\sqrt{n})$ for some constant $a > 0$. We will first show that

$$ \exists \alpha_a, \beta_a > 0, \mathbb{P} \left( \alpha_a \log n \le \text{Max} \left( \Delta^{(n)} \mathbf{H}^1 \right) \le \beta_a \log n \right) \to 1. \quad (44) $$
Then, to conclude when $k(n) = an + o(n)$, we consider some $\varepsilon > 0$, and we can conclude using (44) for $k^{-}(n) := a(1 - \varepsilon)n$ and $k^{+}(n) := a(1 + \varepsilon)n$, and the monotonicity of $\text{Max}(\Delta^{(n,k(n))}\mathbf{H}^{1})$ given in 2.8:

$$ \mathbb{P} \left( \alpha_{a(1+\varepsilon)} \log n \le \text{Max} \left( \Delta^{(n)} \mathbf{H}^{1} \right) \le \beta_{a(1-\varepsilon)} \log n \right) \to 1. \quad (45) $$

We consider $\mathbf{f} = (\mathbf{f}_1, \dots, \mathbf{f}_k)$ uniformly chosen in $\mathcal{F}(n, k(n))$ (we previously denoted this random variable as $\mathbf{F}_{n,k(n)}$, but we simplify the notation in the proof). Lemma 2.5 implies that $\text{Max}(\mathbf{f})$ has the same distribution as $\text{Max}(\mathbf{F}_{n,k(n)}^{\bullet})$, which has the same distribution as $\text{Max}(\Delta^{(n)}\mathbf{H}^{1}) + 1$ (by Corollary 2.4). Thus, to prove (44) it suffices to prove that

$$ \exists \alpha_a, \beta_a \in \mathbb{R}_+, \mathbb{P} (\alpha_a \log n \le |\text{Max}(\mathbf{f})| \le \beta_a \log n) \to 1. \quad (46) $$

The remaining of this proof focuses on proving (46).

**Computation of the upper bound:** We first focus on giving $\beta_a$ such that $\mathbb{P}(|\text{Max}(\mathbf{f})| \ge \beta_a \log n) \to 0$. We have, for any $C > 0$ and any $p_a \in (0, 1)$ (we fix $C$ and $p_a$ later in the proof), given the correspondence forest-path discussed previously,

$$ \mathbb{P}(|\mathbf{f}_1| \ge C \log n) = \sum_{m=[C \log n], m \text{ is odd}}^{n} \mathbb{P}(|\mathbf{f}_1| = m) \quad (47) $$

$$ = \sum_{m=[C \log n], m \text{ is odd}}^{n} \mathbb{P}_{p_a} (\tau_{-1} = m | \tau_{-k(n)} = n) \quad (48) $$

$$ = \sum_{m_0 = \frac{\lfloor C \log n \rfloor - 1}{2}}^{\frac{n-1}{2}} \frac{\mathbb{P}_{p_a}(\tau_{-1} = 2m_0 + 1) \mathbb{P}_{p_a}(\tau_{k(n)-1} = n - (2m_0 + 1))}{\mathbb{P}_{p_a}(\tau_{-k(n)} = n)} \quad (49) $$

$$ \le \sum_{m_0 = \frac{\lfloor C \log n \rfloor - 1}{2}}^{\frac{n-1}{2}} \frac{\mathbb{P}_{p_a}(\tau_{-1} = 2m_0 + 1)}{\mathbb{P}_{p_a}(\tau_{-k(n)} = n)}. \quad (50) $$

We know, thanks to the famous Rotation principle (sometimes also called Kemperman's formula, see e.g. [Pit06, equation (6.3) in Section 6.1]), that the denominator of (50) is such that

$$ \mathbb{P}_{p_a}(\tau_{-k(n)} = n) = \frac{k(n)}{n} \mathbb{P}_{p_a}(W_n = -k(n)) \ge \frac{c_a}{2\sqrt{n}}, \quad (51) $$

for $n$ large enough and $c_a = \frac{1}{\sqrt{2\pi p_a(1-p_a)}}$. Indeed, fix $p_a = \frac{a+1}{2}$ (until the end of the proof of (i)). Then, $\mathbb{E}_{p_a}[W_n] = (2p_a - 1)n = -an = -k(n) + o(\sqrt{n})$ and we can use the central local limit theorem (see (128) in Annex A.1 for more details) to prove that

$$ \mathbb{P}_{p_a}(W_n = -k(n)) \sim \frac{1}{\sqrt{2\pi np_a(1-p_a)}} \quad (52) $$

and thus that

$$ \mathbb{P}_{p_a}(\tau_{-k(n)} = n) \sim \frac{c_a}{\sqrt{n}}. \quad (53) $$
Moreover, we can compute, for every $m_0$, $\mathbb{P}_{p_a}(\tau_{-1} = 2m_0 + 1) = C_{m_0} p_a^{m_0} (1-p_a)^{m_0+1}$ and use the fact that $C_{m_0} \sim \frac{4^{m_0}}{m_0^{3/2} \sqrt{\pi}}$ (obtained by Stirling formula), which implies that $C_{m_0} \le 2 \frac{4^{m_0}}{m_0^{3/2} \sqrt{\pi}}$ for $m_0$ large enough. So for $n$ large enough:

$$ \mathbb{P}(|\mathbf{f}_1| \ge C \log n) \le \frac{4\sqrt{n}}{c_a} \sum_{m_0 = \lceil \frac{C \log n}{2} \rceil - 1}^{\frac{n-1}{2}} \frac{4^{m_0}}{m_0^{3/2} \sqrt{\pi}} p_a^{m_0} (1-p_a)^{m_0+1} \quad (54) $$

$$ \le \frac{4\sqrt{n}}{c_a} \frac{2^{3/2}(1-p_a)}{(C \log n - 1)^{3/2} \sqrt{\pi}} \sum_{m_0 = \lceil \frac{C \log n}{2} \rceil - 1}^{\frac{n-1}{2}} (4p_a(1-p_a))^{m_0} \quad (55) $$

and we conclude by noting that since $p_a = \frac{a+1}{2} \ne \frac{1}{2}$, $q_a := 4p_a(1-p_a) < 1$ hence this partial geometric sum can be easily bounded:

$$ \mathbb{P}(|\mathbf{f}_1| \ge C \log n) \le \frac{4\sqrt{n}}{c_a} \frac{2^{3/2}(1-p_a)}{(C \log n - 1)^{3/2} \sqrt{\pi}} \frac{q_a^{(C \log n - 1)/2}}{1 - q_a} \quad (56) $$

Finally, when $\beta_a > 0$ is such that $(\beta_a/2) \log q_a < -1 - 1/2$ (for example with $\beta_a = -(3+\varepsilon)/(\log q_a)$, for some $\varepsilon > 0$), noting that $q_a^{(\beta_a/2) \log n} = n^{(\beta_a/2) \log q_a}$, we get

$$ \mathbb{P}(|\mathbf{f}_1| \ge \beta_a \log n) = o(1/n). \quad (57) $$

Since the $f_i$ have same law, a union bound argument gives:

$$ \mathbb{P}(|\mathrm{Max}(\mathbf{f})| \ge \beta_a \log n) \le k(n) \mathbb{P}(|\mathbf{f}_1| \ge \beta_a \log n) \quad (58) $$

and this goes to 0 thanks to (57).

**Computation of the lower bound:** To prove that $\mathbb{P}(\alpha_a \log n \le |\mathrm{Max}(\mathbf{f})|) \xrightarrow{n} 1$ for some $\alpha_a > 0$, we will prove something much stronger:

$$ \exists \alpha_a > 0, \mathbb{P}(\exists i : |\mathbf{f}_i| = 2\lceil(\alpha_a/2) \log n\rceil + 1) \to 1. \quad (59) $$

For simplicity of notation, in all what follows, we write $\overline{\alpha_a \log n}$ instead of $2\lceil(\alpha_a/2) \log n\rceil + 1$, the closest odd integer, hence assuming that $\overline{\alpha_a \log n}$ is an odd integer in the computation. We do the same for $\overline{c \log n}$.

For every integer $i$ and every constant $c > 0$, we introduce the corresponding counting variable $A_c^i := 1_{|\mathbf{f}_i|=\overline{c \log n}}$ and $N_c = \sum_{i=1}^{k(n)} A_c^i$, and we let $f_n^c := \mathbb{P}(A_c^1 = 1)$. (We will fix later the value of $c$.)

As before, it is straightforward that

$$ f_n^c = \mathbb{P}(|\mathbf{f}_1| = \overline{c \log n}) = \frac{\mathbb{P}_{p_a}(\tau_{-1} = \overline{c \log n}) \mathbb{P}_{p_a}(\tau_{-k(n)+1} = n - \overline{c \log n})}{\mathbb{P}_{p_a}(\tau_{-k(n)} = n)} \quad (60) $$

For any $g_n = o(n)$, $\mathbb{P}_{p_a}(\tau_{-k(n)} = n + g_n) \sim \frac{c_a}{\sqrt{n}}$ (see (53) which is still valid in this case) and thus (60) can be simplified (recalling that, for every $m$, $\mathbb{P}_{p_a}(\tau_{-1} = 2m + 1) = C_m p_a^m (1-p_a)^{m+1}$ and using Stirling formula):

$$ f_n^c \sim \mathbb{P}_{p_a} (\tau_{-1} = \overline{c \log n}) \sim \frac{(1-p_a) (4p_a(1-p_a))^{(c/2) \log n}}{\sqrt{\pi} ((c/2) \log n)^{3/2}}. \quad (61) $$

We can do a similar computation to prove that

$$ \mathbb{P}(A_c^1 = A_c^2 = 1) \sim (f_n^c)^2. \quad (62) $$
Thus, $\mathrm{Cov}(A_c^1, A_c^2) = \mathbb{P}(A_c^1 = A_c^2 = 1) - \mathbb{P}(A_c^1 = 1)^2 = o((f_n^c)^2)$, so that

$$ \begin{aligned} \mathbb{E}[N_c] &= k(n)\mathbb{E}[A_c^1] \underset{n\to\infty}{\sim} anf_n^c \\ \mathrm{Var}(N_c) &= k(n)\mathrm{Var}(A_c^1) + k(n)(k(n)-1)\mathrm{Cov}(A_c^1, A_c^2) \\ &= k(n)f_n^c + o(n^2(f_n^c)^2). \end{aligned} $$

Recall that $q_a = 4p_a(1-p_a) < 1$. We now replace $c$ by $\alpha_a = -(2-\varepsilon)/\log q_a$, for some $\varepsilon > 0$. Then, $q_a^{c/2 \log n} = n^{-1+\varepsilon/2}$ and $f_n^{\alpha_a} \sim xn^{-1+\varepsilon/2}(\log n)^{3/2}$ (where $x = (1-p_a)/(\sqrt{\pi}(c/2)^{3/2})$). It implies that $nf_n^{\alpha_a} = xn^{\varepsilon/2}/(\log n)^{3/2} = o((nf_n^{\alpha_a})^2)$. Then, $\mathrm{Var}(N_{\alpha_a}) = o((nf_n^{\alpha_a})^2)$. We can use the Chebyshev's inequality to get

$$ \mathbb{P}(|N_{\alpha_a} - \mathbb{E}[N_{\alpha_a}]| \ge anf_n^{\alpha_a}/2) \le \frac{\mathrm{Var}(N_{\alpha_a})}{(anf_n^{\alpha_a}/2)^2} \underset{n\to\infty}{\to} 0. \quad (63) $$

Since $f_n^{\alpha_a} \gg 1/n$, we get $\mathbb{E}[N_{\alpha_a}] \gg 1$ and immediately deduce that $\mathbb{P}(N_{\alpha_a} = 0) = o(1)$: Equation (59) holds.

*Proof of (ii).* We consider $k(n)$ such that $k(n)/\sqrt{n} \to \lambda \in [0, +\infty)$.

Thanks to Corollary 2.6, it suffices to focus on the sizes of excursions of a uniform path of $P(n, k(n))$, and this latter has the same distribution as a simple random walk $W$ of length $n$ with i.i.d. increments $\mathbb{P}(W_i - W_{i-1} = \pm 1) = 1/2$, conditioned by $\tau_{-k(n)} = n$.

We use Proposition 2.9 to prove (ii). The key idea is that $W^{(n,\lambda)} \xrightarrow{d} W^{(\lambda)}$ in $C[0, 1]$, which implies the convergence of the sorted lengths of excursions of $W^{(n,\lambda)}$ above the current minimum, i.e. of the block sizes (in distribution, for the product topology) to the lengths of excursions of $W^{(\lambda)}$ above the current minimum. Indeed, Lemma 7 of [Ald97] applied to $W^{(\lambda)}$ and $(W^{(n,\lambda)})$ gives the desired result. It is stated for functions $[0, \infty) \to \mathbb{R}$, but can be adapted to functions $[0, 1] \to \mathbb{R}$. It is then quite straightforward to check that the hypotheses are verified. We then have: $\mathrm{Exc}(W^{(n,\lambda)})$ converges to $\mathrm{Exc}(W^{(\lambda)})$ as $n$ goes to infinity in distribution (as in Aldous [Ald97], we regard $\mathrm{Exc}(W^{(\lambda)})$ and $\mathrm{Exc}(W^{(n,\lambda)})$ as point processes on $[0, 1] \times (0, 1]$, and convergence holds for the vague convergence of counting measures on $[0, 1] \times (0, 1]$).

Thus, for every $k$, the lengths of the sorted $k$ largest excursions (they correspond to the sorted $k$ highest projections of $\mathrm{Exc}(W^{(n,\lambda)})$ onto the second coordinate) converge to their continuous counterpart. The result given in Theorem 1.3.(ii) is an immediate consequence of this.

*Proof of (iii).* We let $\varepsilon > 0, \delta > 0$. We are going to show that

$$ \mathbb{P}^{n,N_b,N_h,p} \left( \frac{\mathrm{Max} \left( \frac{\Delta^{(n)} \mathbf{H}^1}{n} \right) \ge \varepsilon}{n} \right) < \delta. \quad (64) $$

First, observe that for any continuous map $f: [0, 1] \to \mathbb{R}$ such that $f(0) = f(1) = 0$, and for any $\lambda > 0$, the largest excursion of $f^\lambda$ defined by $f^\lambda(s) = f(s) - \lambda s$ for $s \in [0, 1]$ is smaller than $\frac{\max f - \min f}{\lambda}$ (Figure 6 illustrates this, and we use this property to obtain (67) below).

This therefore applies to $b^\lambda$, a Brownian bridge ending at $-\lambda$, using that $b^\lambda \stackrel{(d)}{=} (b_s^0 - \lambda s, s \in [0, 1])$, where $b^0$ is the standard Brownian bridge ending at 0 (see [RY99, page 37]). In fact, there exist $m$ and $M$ such that $\mathbb{P}(\forall t, m \le b_t^0 \le M) \ge 1 - \delta$ (because the law of the range $[\min X, \max X]$ of a process $X$ taking its values in $C[0, 1]$ is a law in $\mathbb{R}^2$, and then is tight). We consider $\lambda > 0$ such that $\frac{M-m}{\lambda} \le \varepsilon$. Then, with probability at least $1 - \delta$, $b^\lambda$ has excursions smaller than $\frac{M-m}{\lambda}$, hence smaller than $\varepsilon$.

We consider, as in the previous point, the bridges $X^{(n,\lambda)}$ defined as $(\frac{W_{nt}}{\sqrt{n}}, 0 \le t \le 1)$ where $W$ is a simple random walk conditioned by $W_n = k(n) \sim \lambda\sqrt{n}$. We know that
$X^{(n,\lambda)} \xrightarrow{(d)} b^{\lambda}$ as $n$ goes to infinity, in distribution in $C[0, 1]$ (this is well-known, and easy to prove by proof of convergence of the FDD and tightness).

As a consequence,

$$ \left| \mathrm{Exc}(\mathrm{rot}(X^{(n,\lambda)}, \mathrm{argmin}(X^{(n,\lambda)}))) \right| \xrightarrow[n \to \infty]{(d)} \left| \mathrm{Exc}(\mathrm{rot}(b^{\lambda}, \mathrm{argmin}(b^{\lambda}))) \right| $$

for the vague convergence of counting measures on $[0, 1] \times (0, 1]$. The reasoning is close to what is done in the proof of (ii). It is possible to conclude with a continuity argument, using that $\mathrm{argmin} b^{\lambda}$ is unique almost surely, and Skorokhod representation theorem, to couple $X^{(n,\lambda)}$ and $b^{\lambda}$. Vervaat uses exactly this kind of reasoning in [Ver79].

Using Corollary 2.7, this implies the existence of $n_0$ such that, for every $n \ge n_0$,

$$ \mathbb{P}^{n, \lambda \sqrt{n}, p} \left( \frac{\mathrm{Max} \left( \frac{\Delta^{(n)} \mathbf{H}^1}{n} \right) > 2\varepsilon \right) = \mathbb{P} \left( \mathrm{Max} \left( \left| \mathrm{Exc}(\mathrm{rot}(X^{(n,\lambda)}, \mathrm{argmin}(X^{(n,\lambda)}))) \right| > 2\varepsilon \right) \quad (65) $$

$$ \le \mathbb{P} \left( \mathrm{Max} \left( \left| \mathrm{Exc}(\mathrm{rot}(b^{\lambda}, \mathrm{argmin}(b^{\lambda}))) \right| > \varepsilon \right) \quad (66) $$

$$ \le \mathbb{P} \left( \frac{\max b^0 - \min b^0}{\lambda} \ge \varepsilon \right) \quad (67) $$

$$ \le \delta. \quad (68) $$

To conclude, since $N_f(n)/\sqrt{n} \to +\infty$, then for any $n$ large enough, $N_f(n) \ge \lambda\sqrt{n}$ and Corollary 2.8 and the previous discussion imply that

$$ \mathbb{P}^{n, N_f(n), p} \left( \frac{\mathrm{Max} \left( \Delta^{(n)} \mathbf{H}^1 \right)}{n} > 2\varepsilon \right) \le \mathbb{P}^{n, \lambda \sqrt{n}, p} \left( \frac{\mathrm{Max} \left( \Delta^{(n)} \mathbf{H}^1 \right)}{n} > 2\varepsilon \right) \quad (69) $$

$$ \le \delta. \quad (70) $$

We have the desired result: $\mathrm{Max} \left( \Delta^{(n)} \mathbf{H}^1 \right) / n \to 0$ in probability, as $n$ goes to infinity.

### Proof of (iv).

We prove that, when $N_f \sim \lambda\sqrt{n}$, $\Delta_0 \mathbf{H}^1 / n$ the normalized size of the first block (marked, since it contains 0) converges in distribution to $N_{N^2+\lambda^2}^2$ (where $N$ is a standard Gaussian random variable with mean 0 and variance 1). We borrow arguments from Chassaing-Louchard [CL02], and use them to conclude that when $N_f = o(\sqrt{n})$, $\Delta_0 \mathbf{H}^1 / n \to 1$ (in probability, as $n$ goes to infinity). We now detail the main steps.

First, as a consequence of Corollary 2.4, for every $k$,

$$ \begin{aligned} \mathbb{P}^{n, N_b, N_h, p} (\Delta_0 \mathbf{H}^1 = 2k) &= \frac{(2k+1)C_k |\mathcal{F}(n-(2k+1), N_f(n)-1)|}{|\mathcal{F}^\bullet(n, N_f(n))|} \quad (71) \\ &= \frac{\sqrt{n}}{\sqrt{n-(2k+1)}} \frac{(2k+1)C_k 2^{-(2k+1)} \sqrt{n-(2k+1)} |\mathcal{F}(n-(2k+1), N_f(n)-1)| 2^{-n+(2k+1)}}{\sqrt{n} |\mathcal{F}^\bullet(n, N_f(n))| 2^{-n}} \quad (72) \end{aligned} $$

One can use this to compute, for any $x \in ([0, 1])$ and $\lambda$, with $k = \lfloor nx/2 \rfloor$ and $N_f(n) \sim \lambda\sqrt{n}$:

$$ \frac{n}{2} \mathbb{P}^{n, N_b, N_h, p} (\Delta_0 \mathbf{H}^1 = 2k) \sim n \frac{1}{\sqrt{1-x}} \frac{n x \frac{1}{2\sqrt{\pi}(nx/2)^{3/2}} \frac{\lambda\sqrt{n}}{n(1-x)} \frac{2\exp\left(\frac{-\lambda^2}{2(1-x)}\right)}{\sqrt{2\pi}}}{\frac{2\exp\left(\frac{-\lambda^2}{2}\right)}{\sqrt{2\pi}}} \quad (73) $$

$$ \sim \frac{1}{\sqrt{2\pi}} \frac{\lambda}{\sqrt{x}(1-x)^{3/2}} \exp\left(\frac{-\lambda^2 x}{2(1-x)}\right) =: f(\lambda, x) \quad (74) $$
<figure><img src="image_8.png" /><figcaption>Figure 6: Illustration of the proof that sizes of excursions of a Brownian bridge ending at $-\lambda$ (and its rotation) go to 0 when $\lambda$ goes to infinity. The function in bold represent a continuous map $f^\lambda$ defined as $f^\lambda(s) = f(s) - \lambda s$, for every $s \in [0, 1]$ and for $\lambda > 0$ ($f^\lambda$ can be seen as the Brownian bridge $b^\lambda = (b^0 - \lambda t, 0 \le t \le 1)$ ending at $-\lambda$, where $b^0$ is a standard Brownian bridge). It has been extended periodically, so that every rotation of $f^\lambda$ has the same graph up to some translation, and in particular the same excursion lengths. We assume that $\forall t, m \le f(t) \le M$. Then, $f^\lambda(t) = f(t) - \lambda t$ is always above the line $t \mapsto m - \lambda t$, and below the line $t \mapsto M - \lambda t$ (illustrated by the colored dotted lines on the figure). The excursions lengths of $f^\lambda$ are then always smaller by $\frac{M-m}{\lambda}$ (on the drawing, some excursions are represented by red arrows, while the orange dotted arrow, of length $\frac{M-m}{\lambda}$, illustrates what is the maximum size of an excursion).</figcaption></figure>

where we used that for any $n, r$, $|\mathcal{F}(n, r)| = \frac{r}{n} |\mathcal{F}^\bullet(n, r)|$ and $2^{-n} |\mathcal{F}^\bullet(n, r)|$ is the probability that a simple random walk of length $n$ ends at height $-r$. We then used the central local limit theorem to compute the asymptotic terms.

The limit $f(\lambda, \cdot)$ is in fact the density of $\frac{N^2}{\lambda^2 + N^2}$ (see the details in the proof of Theorem 2.1 of [CL02]). We then use a discrete version of Scheffé's lemma (see Corollary A.3 in Annex A.2, in which we take $a_n = n/2$), to get

$$ \frac{\Delta_0 \mathbf{H}^1}{n} \xrightarrow[n \to \infty]{(d)} \frac{N^2}{\lambda^2 + N^2}. $$

We can then conclude. We let $\varepsilon > 0$ and $\delta > 0$. For $\lambda > 0$ large enough,

$$ \mathbb{P} \left( \frac{N^2}{N^2 + \lambda^2} < 1 - \varepsilon/2 \right) \le \delta. $$

Thanks to the convergence in distribution we proved above, there exists $n_0$ such that, for all $n \ge n_0$, if $N_f(n) \sim \lambda\sqrt{n}$, then

$$ \mathbb{P}^{n, \lambda \sqrt{n}, p} \left( \Delta_0^{(n)} \mathbf{H}^1 / n < 1 - \varepsilon \right) \le \mathbb{P} \left( \frac{N^2}{N^2 + \lambda^2} < 1 - \varepsilon/2 \right) \le \delta. \quad (75) $$
Finally, since $N_f(n)/\sqrt{n} \to 0$, for any $n$ large enough, $N_f(n) \le \lambda\sqrt{n}$, and by Corollary 2.8:

$$ \mathbb{P}^{n, N_f(n), p} \left( \text{Max} \left( \Delta^{(n)} \mathbf{H}^1 \right) / n < 1 - \varepsilon \right) \le \mathbb{P}^{n, \lambda \sqrt{n}, p} \left( \text{Max} \left( \Delta^{(n)} \mathbf{H}^1 \right) / n < 1 - \varepsilon \right) \quad (76) $$

$$ \le \mathbb{P}^{n, \lambda \sqrt{n}, p} \left( \Delta_0^{(n)} \mathbf{H}^1 / n < 1 - \varepsilon \right) \quad (77) $$

$$ \le \delta. \quad (78) $$

So finally, $\text{Max} (\Delta^{(n)} \mathbf{H}^1) / n \to 1$ in probability, as $n$ goes to infinity. $\square$

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

## 2.6 Comparison between golf and parking asymptotic behavior

As we mentioned in Remark 7, Theorem 1.3 and Corollary 1.6 highlight very similar behaviors for the asymptotics of the golf process and the p-parking process, studied by Chassaing and Louchard for $p=1$ [CL02]. Let us shed more light on this connection.

In our study, the block sizes have the same distribution as sizes of trees in a uniform (marked) forest of unlabeled binary trees (see Corollary 2.4 and Lemma 2.5), while in parking process the block sizes have the same distribution as the sizes of trees in forests of Cayley trees (i.e. trees with vertices labeled from 1 to $n$), see [Knu73, Ex 6.4-31]. Hence, the combinatorial objects are different, but the reader familiar with this research domain could guess that the block sizes asymptotic behavior in both models are quite similar.

In addition, another small difference can be noted. The block-sizes in our process is biased by the size of the block containing 0, whereas parking blocks are also biased but in a subtle way: the parking process can be seen as a temporal process, and in [CL02] they consider the parking process rooted at the last empty place in the process.

Actually, we can prove that the limit laws of the block-sizes are the same for both models up to some random rotation, using the following arguments.

We let $e = (e_t)_{t \in [0,1]}$ be the standard Brownian excursion and $b = (b_t)_{t \in [0,1]}$ be the standard Brownian bridge (ending at 0). Then, for every $\lambda > 0$, we set again $b^\lambda = (b_t - \lambda t)_{t \in [0,1]}$, the Brownian bridge ending at $-\lambda$, and we define similarly $e^\lambda = (e_t - \lambda t)_{t \in [0,1]}$, the Brownian excursion above the line $x \mapsto -\lambda x$.

Vervaat's theorem states that, if $a = \text{argmin}_t b_t$, then $e \stackrel{(d)}{=} (b_{t+a \bmod 1} - b_a)_{t \in [0,1]}$ [Ver79]. Conversely, if $u \sim \mathcal{U}([0,1])$, then $b \stackrel{(d)}{=} (e_{t+u \bmod 1} - e_u)_{t \in [0,1]}$ [Bia86]. We can restate this using the rotation function $\text{rot}$ (defined in Equation (39)): $b \stackrel{(d)}{=} \text{rot}(e, u)$ and $e \stackrel{(d)}{=} \text{rot}(b, \text{argmin}_t b_t)$.

This result can be generalized for excursions and bridges with a linear drift: $b^\lambda \stackrel{(d)}{=} \text{rot}(e^\lambda, u)$ and $e^\lambda \stackrel{(d)}{=} \text{rot}(b^\lambda, \text{argmin}_t(b^\lambda + \lambda t))$ (this is a direct consequence of Vervaat's theorem and of the fact that the rotation and the addition of a linear drift commute: $(\text{rot}(e, u)(t) - \lambda t)_t = \text{rot}(e^\lambda, u)$).

We now consider two other processes. First, let $W^\lambda$ be a Brownian motion conditioned by $\tau_{-\lambda} = 1$ (see Proposition 2.9 for its definition). Second, we define $R^\lambda$ as the rescaled limit of $R^{(n, \lambda \sqrt{n})}$ (the Łukasiewicz walk associated to $F_{n, \lambda \sqrt{n}}$, see Equation (41)).

The following lemma implies that the processes $W^\lambda$, $e^\lambda$ and $R^\lambda$, up to some translation, have the same set of excursions, and therefore that the processes $\Delta^{(n)}\mathbf{H}^1$ in the golf model and in the p-parking model have asymptotically the same limit in law (up to a rotation).

**Lemma 2.10.** For any process $\xi \in \{W^\lambda, R^\lambda\}$,

$$ \bullet e^\lambda \stackrel{(d)}{=} \text{rot}(\xi, \text{argmin}_t(\xi_t + \lambda t)) $$
<figure><img src="image_10.png" /><figcaption>Figure 7: Illustration of Lemma 2.10. The graph in bold, from the origin O to the point with coordinates (1, − λ ) represents W $^{λ}$, a Brownian process such that τ$_{−}$$_{λ}$ = 1. It has been extended periodically, so that the parts in black (or in purple) are exactly the same up to a translation. Then, y is such that y = argmin$_{t}$$_{∈}$$_{[0}$$_{,}$$_{1]}$ W λ t + λt , and geometrically it means that the process W λ is always above the line of slope − λ passing through ( y, W λ y ) (drawn in blue on the figure). Therefore, the curve of rot ( W $^{λ}$, argmin$_{t}$ ( W λ t + λt )) is the same as that of W λ with a change of origin (the graph from O ′ = ( x, W λ x ) (with x = y − 1) to ( y, W λ y )). We can see on the figure that it is an excursion above the blue line. Lemma 2.10 states that it has the same distribution as e $^{λ}$.</figcaption></figure>

$$
\bullet b^{\lambda} \stackrel{(d)}{=} \mathrm{rot}(\xi, u), \text{ where } u \sim \mathcal{U}([0, 1]).
$$

Moreover,

$$
R^{\lambda} \stackrel{(d)}{=} \mathrm{rot} \left( b^{\lambda}, \operatorname{argmin}(b^{\lambda}) \right). \qquad (79)
$$

Therefore, the processes W $^{λ}$, R λ and e λ have the same excursion lengths (above the current minimum process) up to a rotation. This is also true for the process b λ extended periodically.

Figure 7 illustrates this lemma.

The interested reader can find results with the same flavor in [BCP03] and [CJ01]. Nevertheless, we think that our lemma is not proved in the literature, so we give the sketch of the proof.

Sketch of the proof. We do not give a full proof here, but we give the main idea behind it, that follows from the proof of Vervaat’s theorem [Ver79]. We focus on (79) (the other statements have similar proofs). Equation (41) is a discrete version of this. Moreover, if N$_{f}$ ∼ λ √$_{n}$$_{,}$ R ( n,N$_{f}$ ) converges to R λ (after a suitable rescaling), and similarly B ( n,N$_{f}$ ) (the uniform bridge of length n ending at − N$_{f}$ , see (41)) converges to b λ (also after a suitable rescaling). One can conclude using a continuous mapping theorem ([Bil99, Theorem 2.7]). The difficulty is that rot(., argmin(·)) is only continuous at functions f that reach their minimum value only once. Vervaat explains how to deal with this difficulty, and the same reasoning would work here.

2.7 Sparse Case

2.7.1 Proof of Theorem 1.4

Proof. We give some notation that enables us to deal properly with the fact that we have N$_{f}$ variables with a density function (with respect to the Lebesgue measure) on R N$_{f}$ − $^{1}$,
corresponding to the restriction to $N_f - 1$ variables (the last one is a deterministic function of the others, since the sum of the block sizes is equal to $n - N_f$). We define, for any $x = (x_0, \dots, x_{N_f-1}) \in \text{Simplex}(N_f)$, $\bar{x} = (x_0, \dots, x_{N_f-2})$, and $\overline{\text{Simplex}}(N_f) = \{\bar{x} : x \in \text{Simplex}(N_f)\}$, the restriction of $\text{Simplex}(N_f)$ to its first $N_f - 1$ coordinates. Notice that it is similar to consider $x \in \text{Simplex}(N_f)$ or $x \in \overline{\text{Simplex}}(N_f)$ with the additional value $x_{N_f-1} := 1 - \sum_{i=0}^{N_f-2} x_i$ (which we thus always consider to be defined).

For any $x \in \text{Simplex}(N_f)$ and for every $k$ such that $0 \le k < N_f - 1$, we set $\ell_k := \lfloor x_k(n - N_f) \rfloor$, and we fix $\ell_{N_f-1} := n - N_f - \sum_{i=0}^{N_f-2} \ell_i$. We will establish that, for any $(x_0, \dots, x_{N_f-2}) \in \overline{\text{Simplex}}(N_f)$,

$$f_n(x_0, \dots, x_{N_f-2}) := n^{N_f-1} \mathbb{P}^{n, N_b, N_h, p} (\Delta_i \mathbf{H}^1 = \ell_i, \forall i \in \mathbb{Z}/N_f \mathbb{Z}) \underset{n \to \infty}{\to} f(x_0, \dots, x_{N_f-2}) \quad (80)$$

and that

$$\int_{\overline{\text{Simplex}}(N_f)} f(x_0, \dots, x_{N_f-2}) \, dx_0 \dots dx_{N_f-2} = 1. \quad (81)$$

These two properties allow to conclude immediately: Corollary A.3 (which gives a discrete version of Scheffé's lemma) implies Theorem 1.4.

It suffices to prove (80) and (81) to complete the proof of Theorem 1.4.

**Proof of (80).** We let $c := |C^{m, N_b, N_h}|$. We just need the following computation: for $x = (x_0, \dots, x_{N_f-2}) \in \overline{\text{Simplex}}(N_f)$,

$$f_n(x) = \frac{n^{N_f-1} (\ell_0 + 1)}{c} \sum_{(b_i): \sum_i b_i = N_b} \prod_{\substack{k \in \mathbb{Z}/N_f \mathbb{Z} \\ \text{et } \forall i, 2b_i \le \ell_i}} \frac{1}{b_k + 1} \left( b_k, b_k, \ell_k - 2b_k \right) \quad (82)$$

$$\sim_{n \to \infty} \frac{n^{N_h - N_b} x_0 N_b! N_h!}{n^{N_b + N_h}} \sum_{(b_i): \sum_i b_i = N_b} \prod_{k \in \mathbb{Z}/N_f \mathbb{Z}} \frac{1}{b_k! (b_k + 1)!} \frac{\ell_k!}{(\ell_k - 2b_k)!} \quad (83)$$

$$\sim_{n \to \infty} n^{-2N_b} x_0 N_b! N_h! \sum_{(b_i): \sum_i b_i = N_b} \prod_{k \in \mathbb{Z}/N_f \mathbb{Z}} \frac{1}{b_k! (b_k + 1)!} (x_k n)^{2b_k} \quad (84)$$

$$\underset{n \to \infty}{\to} x_0 N_b! N_h! \sum_{(b_i): \sum_i b_i = N_b} \prod_{k \in \mathbb{Z}/N_f \mathbb{Z}} \frac{1}{b_k! (b_k + 1)!} x_k^{2b_k}. \quad (85)$$

**Proof of (81).** We now compute the integral below, using the formula given in Remark 5 and the fact that $2N_b + N_f = N_b + N_h$.

$$\int_{\overline{\text{Simplex}}(N_f)} f(x) \, dx = \int_{\overline{\text{Simplex}}(N_f)} x_0 N_b! N_h! \sum_{(b_i): \sum_i b_i = N_b} \prod_{k \in \mathbb{Z}/N_f \mathbb{Z}} \frac{1}{b_k! (b_k + 1)!} x_k^{2b_k} \, dx \quad (86)$$

$$= \frac{N_b! N_h!}{(N_h + N_b)!} \sum_{\sum_i b_i = N_b} (2b_0 + 1) C_{b_0} \prod_{k \in \mathbb{Z}/N_f \mathbb{Z}, k \neq 0} C_{b_k}. \quad (87)$$

We have seen (in Equation (31)) that $(2b_0 + 1)C_{b_0} \prod_{k=1}^{N_f-1} C_{b_k}$ is the number of forests of $\mathcal{F}^\bullet(N_b, N_f)$ such that for every $i$ the $i$th tree has $b_i$ internal nodes. Hence, by (35),

$$\int_{\overline{\text{Simplex}}(N_f)} f(x) \, dx = \frac{N_b! N_h!}{(N_h + N_b)!} |\mathcal{F}^\bullet(N_b, N_f)| = 1. \quad (88)$$

□
### 2.7.2 Discussion on the continuous model that appears as the limit of the golf process in the sparse case

In Theorem 1.4, the normalized block sizes converge in distribution to a mixed Dirichlet distribution. Actually, it can be seen as the distribution of the final configuration of several continuous analogues of the golf process defined on the unit circle $C = \mathbb{R} \setminus \mathbb{Z}$. We consider a finite number of balls $N_b$ and holes $N_h$ (that are random real points) chosen independently and uniformly on $C$, the balls being equipped with random clocks as usual (call $\mu_\infty(N_b, N_h)$ this initial distribution). We consider the two following variants:

(V$_1$) upon activation, a ball fills the first hole to its right;

(V$_2$) upon activation, a ball does a Brownian motion stopped at the first hitting time of a free hole, which it fills.

To show that the distribution of the block-size process in both variants (i.e. the distances between consecutive free holes in the final configuration) is given by $f$ (see Equation (3)), a coupling argument suffices: first, concerning the initial configuration, the unit circle appears as a limit when normalizing $\mathbb{Z}/n\mathbb{Z}$ by $n$, and by this scaling, the initial configuration converges to $\mu_\infty(N_b, N_h)$. Then there are two cases:

* When $p > 1/2$ (the case $p < 1/2$ can be dealt with similarly), the discrete trajectory of a generic ball is a random walk $(S_k)_{k \ge 0}$ on $\mathbb{Z}/n\mathbb{Z}$ of parameter $p$ starting at $S_0 = \lfloor nu \rfloor$. It is biased and has the following asymptotic behavior (it is driven by its mean):

$$ \left( \frac{S_{nt}}{n}, t \ge 0 \right) \xrightarrow{(d)} (u + (2p-1)t \mod 1, t \ge 0) \quad (89) $$

uniformly on each compact (this can be seen as a consequence of Donsker's theorem, which allows to control the error term). In other words, in the continuous limit, the balls almost surely go to the right at constant speed (which means that in the continuous golf model the balls jump instantaneously to the first hole on the right). This corresponds to variant (V$_1$).

* When $p = 1/2$ (corresponding to variant (V$_2$)), the discrete trajectory of a generic ball is, similarly, a random walk $(S_k)_{k \ge 0}$ on $\mathbb{Z}/n\mathbb{Z}$ of parameter $p = 1/2$ starting in $S_0 = \lfloor nu \rfloor$. This random walk converges to a Brownian motion:

$$ \left( \frac{S_{n^2 t}}{n}, t \ge 0 \right) \xrightarrow{(d)} ((u + B_t) \mod 1, t \ge 0) \quad (90) $$

in $C([0, M], C)$ the set of continuous functions from $[0, M]$ to $C$, equipped with the topology of uniform convergence, for any $M > 0$. Notice that we chose $n$ as space normalization because we want that, in the continuous limit, the Brownian travels across a macroscopic part of the circle, and this imposes the time normalization in $n^2$.

This informal justification can be made rigorous by the Skorokhod representation theorem.

# 3 Golf model on $\mathbb{Z}$

## 3.1 The model on $\mathbb{Z}$ is valid - proof of Theorem 1.7

*Proof.* We first prove the theorem when $d_b < d_h$.
**Case $d_b < d_h$:** The key idea in this case is to prove that almost surely, for a given initial configuration $\eta^0$, there exists an infinite set of holes Sep such that $Sep \subseteq H^1$, and Sep is independent of the balls trajectories. We call elements of Sep separators, and show that they allow to divide $\mathbb{Z}$ into finite disjoint intervals on which it is easy to define the golf process.

We consider the initial configuration $\eta^0$ taken at random as in Section 1.5.

First, we say that a vertex in $n \in \mathbb{Z}$ is a separator in $\eta^0$ if the following event $A_n$ is true:

$$A_n := \left\{ \forall k < n, \sum_{j=k}^{n-1} \eta_j^0 \le 0 \right\} \cap \{\eta_n^0 = -1\} \cap \left\{ \forall k > n, \sum_{j=n+1}^{k} \eta_j^0 \le 0 \right\}$$

(it is a hole, and there is a surplus of holes on any interval of the form $[a, n-1]$ or $[n+1, b]$). We let $Sep = \{k : A_k\}$ be the set of separators.

**Lemma 3.1.** *There is almost surely an infinite number of separators on the right and on the left of 0.*

Before proving this lemma, we define a coding between initial configurations and bi-infinite paths with steps 0, -1 and +1, illustrated on Figure 8.

To any $\eta^0 \in \{-1, 0, +1\}^{\mathbb{Z}}$, we associate a bi-infinite path $S = S(\eta^0) = (S_{k-1/2})_{k \in \mathbb{Z}}$ such that $S_{-1/2} = 0$ and $\forall k \in \mathbb{Z}, S_{k+1/2} = S_{k-1/2} + \eta_k^0$. We consider indices in the set of half-integers $\mathbb{Z} + 1/2$, so that a vertex of the initial configuration corresponds to an edge in the associated bi-infinite path. For example, if some vertex $n$ contains a ball, $\eta_n = 1$, thus $S_{n-1/2} = S_{n+1/2} + 1$, so the corresponding edge is a “+1 edge”.

We also define the height of a vertex $n$ as the height of (the middle of) its corresponding edge in the bi-infinite path $(S_{k-1/2})_{k \in \mathbb{Z}}$: $h(n) := \frac{S_{n-1/2}+S_{n+1/2}}{2}$. Observe that when the golf process is valid at time $t$, we can extend the definition of the corresponding bi-infinite path and of the height function, so as to define $S^t$ and $h^t$.

Then, $A_n$ is true if and only if $n$ is a hole, and there exists no $k \neq n$ such that $\{S_{k-1/2}, S_{k+1/2}\} = \{S_{n-1/2}, S_{n+1/2}\}$, and equivalently, if there is no $k \neq n$ such that $h_k = h_n$. As an example, the vertex $n$ on Figure 8 is a separator (if we assume that the bi-infinite path never comes back at the height of $n$). Figure 8 illustrates the reason why we focus on these separators.

*Proof of Lemma 3.1.* We denote by $\mu^{d_b, d_h}$ the product measure on $S$ which is the law of $\eta^0 = (\eta_k^0)_{k \in \mathbb{Z}}$ (see (6)). The measure $\mu^{d_b, d_h}$ is invariant under translation and ergodic. In particular, every event measurable with respect to $\sigma(\eta^0)$ and invariant under translation occurs with probability 0 or 1.

We now prove that almost surely, $\inf\{n : A_n\} = -\infty$ and $\sup\{n : A_n\} = +\infty$. By symmetry, it suffices to study $\inf\{n : A_n\}$. Since $\inf\{n : A_n\}$ is a random variable taking value in $\mathbb{Z} \cup \{-\infty, +\infty\}$ and invariant under translation, almost surely $\inf\{n : A_n\} \in \{-\infty, +\infty\}$. Moreover, the events $\inf\{n : A_n\} = -\infty$ and $\inf\{n : A_n\} = +\infty$ are invariant under translation, so by ergodicity they have probability 0 or 1. We can compute the probability of $A_0$:

$$\begin{aligned} \mu^{d_b, d_h}(A_0) &= \mu^{d_b, d_h}(\eta_0^0 = -1) \times \mu^{d_b, d_h}\left(\forall k \le 0, \sum_{j=k}^{0} \eta_j^0 \le 0\right) \times \mu^{d_b, d_h}\left(\forall k \ge 1, \sum_{j=1}^{k} \eta_j^0 \le 0\right) \\ &= (d_h) \times (p_0)^2 \end{aligned}$$
<figure><img src="image_11.png" /><figcaption>Figure 8: Illustration of the correspondence between initial configurations and bi-infinite paths with steps 0, -1 and +1. A ball (●) corresponds to a step +1, a hole (○) to a step -1, and a neutral vertex to a step 0.</figcaption></figure>

If a vertex is a separator (for example, the vertex $n$ in orange) the corresponding edge is such that no other edge is at its height, and we will show that the corresponding hole is in $\mathbf{H}^1$, whatever the ball trajectories (for a first intuition, the green and blue arrows pointing towards $n$ illustrate a kind of worst case, in which all the ball trajectories are oriented towards $n$). The vertex $n-1$, circled in red, is not a separator: there are other edges at the height of the red one, and balls can reach the corresponding hole.

(by independence of the $\eta_k$, and with $p_0 = \mu^{d_b, d_h} (\forall k \ge 1, \sum_{j=1}^k X_j \le 0) > 0$). The number $p_0$ corresponds to the probability that a random walk with steps $(\eta_k^0)_{k \ge 1}$ starting in $S_{1/2} = -1$ does not hit 0 after time $1/2$, and this probability is positive, since this random walk is transient (because $d_h > d_b$). It can actually be computed (we do it in the proof of Claim 3.11), but we do not need it here, since knowing its positivity suffices.

Finally, we know that $\mu^{d_b, d_h}(\inf\{n: A_n\} = -\infty) \ge \mu^{d_b, d_h}(A_0) > 0$, thus $\mu^{d_b, d_h}(\inf\{n: A_n\} = -\infty) = 1$. Similarly, $\mu^{d_b, d_h}(\sup\{n: A_n\} = +\infty) = 1$. $\square$

Until the end of the proof of the case $d_b < d_h$, we fix the initial configuration $(\eta_k^0)$ and assume that $\inf \text{Sep} = -\infty$ and $\sup \text{Sep} = +\infty$ (which is almost sure, thanks to Lemma 3.1).

For every $s \in \text{Sep}$, we define $\text{next}(s) = \inf\{s' \in \text{Sep} : s' > s\}$ (it is well defined), and we then let $I_s := [s, \text{next}(s)]$. For every separator $s \in \text{Sep}$, we say that $I_s$ is an *enclosed interval*. Enclosed intervals are such that, for every $x \in I_s$ such that $x \ne s$ and $x \ne \text{next}(s)$, $h(s) > h(x) > h(\text{next}(s))$.

For every interval $I$, we define the golf process restricted to $I$ as the golf process on $I$, with initial configuration $(\eta_i^0)_{i \in I}$, clocks $(C(i))_{i \in I}$ and transition matrix $P^p|_I$, which corresponds to $P^p$ on $I$, but reflected on the boundaries (the choice of the simple reflection is arbitrary, since we will see that the balls actually never hit these boundaries). We denote it by $\eta[I] := (\eta^t[I], t \in [0, 1])$. Note that in general, this is not valid, as there can be more balls than holes in this initial configuration.

We now give the following lemma, that shows that if we consider the process restricted to an enclosed interval, no ball exits this interval.

**Lemma 3.2.** Let $I = [s_1, s_2]$ be an enclosed interval (that is, $s_1 \in \text{Sep}$ and $s_2 = \text{next}(s_1)$). The golf process $\eta[I]$ is valid, and at time 1, $s_1$ and $s_2$ are free holes, that is $\eta[I]_{s_1}^1 = -1$ and $\eta[I]_{s_2}^1 = -1$.
<figure><img src="image_12.png" /><figcaption>(a) $S^t$: a ball in *b* is able to reach the holes $h_1$ and $h_2$, and fills $h_1$. It can't reach $s_1$ and $s_2$</figcaption></figure>

<figure><img src="image_13.png" /><figcaption>(b) $S^t$: only the height of edges corresponding to vertices between $h_1$ and $b$ (included) have changed, and are still smaller than $h(s_1)$ and greater than $h(s_2)$. The previous height function appears in dots</figcaption></figure>

**Figure 9:** We recall that a downward edge corresponds to a free hole, an upward edge to a ball, and a horizontal edge to a neutral vertex (which can be an occupied hole or the vertex of a ball that has already been activated). This figure illustrates the proof that restricting to a closed interval, no ball can reach a separator. The steps $s_1$ and $s_2$ (in orange) correspond to two separators.

*Proof.* The process $\eta[I]$ is valid, since an enclosed interval contains more holes than balls (since $\sum_{k=s_1+1}^{s_2-1} \eta_k^0 \le 0$) and this number of balls is finite (by Proposition 1.1).

For the second statement, we can consider the associated path and height (restricted to $I$) $(S_{k-1/2}^t)_{s_1 \le k \le s_2+1}$ and $(h^t(s))_{s_1 \le s \le s_2}$, defined for every $t \in [0, 1]$. We now show that every ball in $I$ finds a hole inside $I$, never hitting $s_1$ nor $s_2$.

More precisely, we show the three following properties, for every $t$:

(P1) if a ball starting at some vertex $b \in I$ is able to reach a free hole at vertex $h_1 \in I$ at time $t$, with $h_1 < b$ (respectively $h_2 \in I$ such that $h_2 > b$) then $h^t^{-}(h_1) \leq h^t^{-}(b)$ (respectively $h^t^{-}(h_2) \geq h^t^{-}(b)$),

(P2) for every $t' < t$, for every $x \in I$, $h^{t'}(s_1) > h^{t'}(x) > h^{t'}(s_2)$,

(P3) at time $t$, $s_1$ and $s_2$ are free holes.

Since $s_1$ and $s_2$ are free at time 0, then for every $t$, (P1) and (P2) imply (P3), and (P3) gives the desired result. So we only need to prove (P1) and (P2), and to prove it for $t \in C(B \cap I)$ (the set of clocks of balls that belong to $I$). The proof is illustrated on Figure 9.

Let $t \in C(B \cap I)$. First, (P1) is a direct consequence of the fact that for each $t$, $S^t$ is non-decreasing on intervals containing no holes. Let $h_1$ (resp. $h_2$) be the first hole on the right (resp. on the left) of $b$ (they exist since $s_1$ and $s_2$ are free). Since there is no hole between $h_1$ and $b$, $S_{h_1+1/2}^{-} \le S_{b-1/2}^{-}$. We immediately get $h^{-}(h_1) = S_{h_1+1/2}^{-} + 1/2 \le S_{b-1/2}^{-} + 1/2 = h^{-}(b)$. The proof is similar for $h_2$.

We can now focus on (P2) and on the modification of the height function $h$ at time $t$, when a ball starting at $b$ fills the first hole $h_1$ at its right (the left case is exactly the same). Subfigure 9b illustrates this modification.
If $b$ fills $h_1$ at time $t$: $\eta_{h_1}^t = 0$, $\eta_b^t = 0$, and the other vertices' state is unchanged. In terms of height we get $h^t(h_1) = h^{t-}(h_1) + 1/2$, $h^t(b) = h^{t-}(b) + 1/2$ and $\forall x \in (h_1, b)$, $h^t(x) = h^{t-}(x) + 1$ (and the other heights remain unchanged). So for every $x \in I$, $h^t(x) \ge h^{t-}(x) > h^{t-}(s_2) = h^t(s_2)$. Moreover, $h(s_1), h(b) \in \mathbb{Z} + 1/2$, so $h^{t-}(s_1) > h^{t-}(b)$ implies $h^{t-}(s_1) > h^{t-}(b) + 1/2 = h^t(b)$. In addition to that, for all $x \in [h_1, b)$, $h^t(x) \le h^t(b) < h^t(s_1)$, thus finally: for every $x \in I$, $h^t(x) < h^t(s_1)$

We can do exactly the same reasoning if $b$ fills $h_2$, so (P2) is true for every $t$. $\square$

We now conclude the proof in the case $d_b < d_h$ (of Theorem 1.7).

Almost surely, the initial configuration $\eta^0$ on $\mathbb{Z}$ can be divided into an infinite number of finite enclosed intervals (between consecutive separators). Therefore, conditional on $\eta^0$, the golf process can be divided into independent blocks. To be able to apply Lemma 3.2 (in order to conclude that no ball exit any of these enclosed intervals), we need to ensure that no ball come from outside an enclosed interval. One way of doing this is to introduce the alternative process with sinks, defined as the golf process with the subtlety that we allow the separators to be filled by an arbitrary number of balls (the separators are sinks). Here we can immediately apply Lemma 3.2, and it implies that almost surely no ball fills any separator. In particular if we go back to the initial process where separators are empty holes that can be filled by at most one ball, then when no separator are filled in the golf process with sinks, these two models coincide, and this happens with probability 1. It implies that our model is valid almost surely, and that the separators are almost surely not filled.

Concerning measurability, the separators enable to divide the golf process into finite golf processes, which are càdlàg, hence the golf process on $\mathbb{Z}$ is almost surely càdlàg (since we consider the product topology on $S$).

**Case** $d_b = d_h$: For any $t < 1$, we consider the golf process until time $t$, which we denote $\eta[< t]$, that corresponds to the golf process with same initial configuration and dynamics as before, but in which we have activated only the balls with a clock smaller than $t$. It is straightforward that the golf process on $\mathbb{Z}$ is valid until time $t$, for any $t < 1$ (because the density of balls is then $td_b < d_h$, so we can use the first part of the proof). If we consider a vertex $b$ containing a ball, its clock $C(b)$ is such that $C(b) < 1$ almost surely and thus, in the process $\eta[< (C(b) + 1)/2]$, this ball has been activated. Moreover, for any $s < t < 1$, $(\eta[< t])[< s] = \eta[< s]$, therefore, we can define the golf process on $\mathbb{Z}$ as $\eta = \eta[< 1] = \lim_{t \to 1, t<1} \eta[< t]$: the limit exists and corresponds to the process we have described.

Finally, it is also almost surely càdlàg: thanks to the previous paragraph it is straightforward that it is càdlàg before any time $t < 1$; the process is even continuous at $1^{-}$, since for the continuity on a product space it suffices to have the continuity for each projection, and each state is modified only once (at a time $< 1$). $\square$

From this proof we can deduce the two following corollaries:

**Corollary 3.3.** When $d_b < d_h$, the set of separators Sep is included in the set of remaining holes $\mathbf{H}^1$. In particular, there is an infinite number of holes on the left and on the right of 0.

It is a consequence of Lemma 3.1 and of the conclusion of the proof for the case $d_b = d_h$.

**Corollary 3.4.** If $d_b > d_h$, the golf process on $\mathbb{Z}$ is valid until time $d_h/d_b$ (included).

Indeed, the probability that a vertex contains a ball activated before time $d_h/d_b$ is $d_h$. The golf process until time $d_h/d_b$ is thus, up to a rescaling of time, similar to a golf process
<figure><img src="image_14.png" /></figure>

(a) $\eta(a)^0$ such that $\forall x \ge 0, \eta(a)_x^0 = h$ and $\forall x < 0, \eta(a)_x^0 = b$.

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

(b) $\eta(b)^0$ such that $\eta(b)_x^0 = h$ if $x \ge 0$ or $x = 0 \bmod 3$ and $\eta(b)_x^0 = b$ otherwise.

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

(c) $\eta(c)^0$ such that $\eta(c)_x^0 = h$ if $x \ge 0$ or $x = 0 \bmod 2$ and $\eta(c)_x^0 = b$ otherwise.

Figure 10: Three possible initial configurations on $\mathbb{Z}$ that illustrate the complexity of defining a golf process on $\mathbb{Z}$. The golf process with initial configuration $\eta(a)^0$ is not valid. The process with initial configuration $\eta(c)^0$ is valid, while the one with initial configuration $\eta(b)^0$ is only valid until time $1/2$.

with ball density equal to $d_h$, which we have proven to be valid. In Section 3.5, Corollary 3.12 allows us to prove that actually, after time $d_h/d_b$, the process is not valid anymore.

## 3.2 The golf process on $\mathbb{Z}$ is not always valid for different initial conditions

As we briefly mentioned earlier, building a well-defined golf process on infinite graphs such as $\mathbb{Z}$ is not that simple. In this subsection, we discuss and illustrate this complexity with several examples (detailed on Figure 10). For these examples, we fix the initial condition, and we still assume that the clocks are independent and drawn uniformly at random on $[0, 1]$.

We start with the first example, with initial condition defined on Subfigure 10a. For any $x < 0$, the ball in $x$ has clock $C(x)$, and there almost surely exists an infinite number of other balls with clock smaller than $C(x)$. It means that there cannot be any hole $y \ge 0$ free at time $C(x)$, and thus the ball in $x$ will not be able to find a hole. Thus, the process would be frozen at any time $t > 0$ (this prevents $(\eta^t, t \ge 0)$ to be càdlàg).

This example also illustrates a limit of the Commutation property (which we had on finite graphs, see Remark 1. In fact, if the clocks were not random but were, for example, an increasing function of $|x|$ (for example, if $C(x) = 1 - 1/(1 + |x|)$, $\forall x < 0$), then it is quite straightforward that the golf process would be valid: for every $x < 0$, the ball in $x$ would fill the hole in $|x| - 1$ at time $C(x)$.

Examples b and c (see Subfigures 10b and 10c for the definition of the initial configurations $\eta(b)^0$ and $\eta(c)^0$) are also very interesting. We can show (doing exactly as for Corollary 3.4, using the proof of Theorem 1.7, the key tool being the existence of separators at any time $t < 1$) that the golf process with initial configuration $\eta(c)^0$ is valid, whereas the one with initial configuration $\eta(b)^0$ is only valid until time $t = 1/2$ (as for example a, it is after that immediately frozen, thus not càdlàg at $t = 1/2$).

For the golf process with initial configuration $\eta(c)^0$, it would actually be possible to prove that $H^1 = \mathbb{Z}_{\ge 1}$.

All these examples illustrate the importance of separators, even when the initial configuration is not ergodic: when there are no separators anymore, the model is not valid. For the golf process with initial condition $\eta(c)^0$, there are no separators, but if we consider the process before time $t$ (with $t < 1$), thus considering only balls with clock smaller than
$t$, there is again an infinite number of separators. Similarly, on $\eta(b)^0$ there are separators until time $1/2$, and the process is valid until time $1/2$.

We can notice that the “proportion” of balls $\lim_{r\to\infty} \frac{|\{x\in[-r,r]:\eta_i^0=1\}|}{2r+1}$ is not invariant by translation. It does not enable to distinguish valid examples from non-valid ones.

## 3.3 Distribution of the block-size process - proof of Theorem 1.8

In this subsection, we prove Theorem 1.8. We thus fix $d_b$ and $d_h$, such that $d_b < d_h$ and $d_b + d_h = 1$.

We first give the main idea of the proof. It relies on a coupling between the golf model on $\mathbb{Z}$ and a golf model on $\mathbb{Z}/n\mathbb{Z}$, with $n$ large enough, and containing $N_h(n)$ holes and $N_b(n)$ balls, such that $N_h(n)/n \sim d_h$ and $N_b(n)/n \sim d_b$. We give and prove three key lemmas, and then we use them to conclude.

**Sketch of the proof.** We will see that we can fix some constant $M$ large enough such that, both on $\mathbb{Z}$ and on $\mathbb{Z}/n\mathbb{Z}$, the probability that $\mathbf{H}^1$ restricted to $[-M, M]$ contains at least $R+1$ holes on the left and on the right of 0 is arbitrarily close to 1 (the same $M$ being valid for all $n$ large enough, see Step 2 below). This implies (morally) that the positions of the $R$ first holes on the left (and on the right) of 0 only depend on the golf process restricted to $[-M, M]$. Moreover, when $N_h(n)/n \sim d_h$ and $N_b(n)/n \sim d_b$, the initial configuration on $\mathbb{Z}/n\mathbb{Z}$ restricted to $[-M, M]$ is close (in distribution) to the initial configuration on $\mathbb{Z}$, also restricted to $[-M, M]$ (see Step 3 below). It enables to construct a probability space on which the initial configurations coincide on $[-M, M]$ with high probability, as well as the paths of the balls on this interval, that leads to a coupling of the final configurations (still restricted to $[-M, M]$) that are then equal with high probability (Step 4 below gives the last lemma that enables to conclude properly). It then remains to study the distribution of the remaining holes on a large circle and show its convergence in distribution for the product topology. To do this, we show (in Step 1 below) that actually the process $\Delta^{(n)}\mathbf{H}^1$ has the same law as a family of independent variables conditioned by their sum, for which deriving the asymptotic distribution is routine.

Let us start the formal proof.

**Notation** For every $n$, we define $N_h(n) := \lfloor nd_h \rfloor$ and $N_b(n) := n - N_h(n)$, so that $N_b(n) + N_h(n) = n$, $N_b(n) \sim d_b n$ and $N_h(n) \sim d_h n$. As usual, $N_f = N_h(n) - N_b(n)$.

As we deal with several families of random variables, we use the following notation to avoid ambiguity:

• We write, as before $\Delta^{(n)}\mathbf{H}^1$ for the block sizes process on $\mathbb{Z}/n\mathbb{Z}$, and we write $\mathbb{P}^{n,N_b,N_h,p}$ for probabilities concerning the golf process on $\mathbb{Z}/n\mathbb{Z}$ when needed (sometimes, for compactness reasons, we omit it, but then the superscript “$(n)$” removes any ambiguity).

• Similarly, $\Delta\mathbf{H}^1$ refers to the block sizes process on $\mathbb{Z}$, and most of the time we write $\mathbb{P}^{\mathbb{Z},d_b,d_h,p}$ for the associated probabilities.

• Finally, we introduce variables $(L_i^{(\lambda)})_{i\in\mathbb{Z}}$, and we simply denote by $\mathbb{P}$ the associated probabilities.
**Step 1:** We let $\lambda = d_b d_h$ (as stated in Theorem 1.8). We begin by defining a family $(\mathbf{L}_i^{(\lambda)})_{i \in \mathbb{Z}}$ of independent random variables, taking non-negative even integer values, with

$$ \forall k \ge 0, \mathbb{P}(\mathbf{L}_0^{(\lambda)} = 2k) = \frac{(2k+1)C_k \lambda^k}{\mathcal{H}(\lambda)} $$

$$ \text{and } \forall i \neq 0, \forall k \ge 0, \mathbb{P}(\mathbf{L}_i^{(\lambda)} = 2k) = \frac{C_k \lambda^k}{\mathcal{G}(\lambda)}. $$

**Lemma 3.5.** We have the following equality for the golf process on $\mathbb{Z}/n\mathbb{Z}$:

$$ \mathcal{L}\left(\left(\Delta_i^{(n)}\mathbf{H}^1\right)_{0 \le i < N_f}\right) = \mathcal{L}\left(\left(\mathbf{L}_i^{(\lambda)}\right)_{0 \le i < N_f}\right) \left| \sum_i \mathbf{L}_i^{(\lambda)} = n - N_f \right|. \quad (91) $$

Moreover, the conditioning on the sum vanishes asymptotically:

$$ \left(\Delta_i^{(n)}\mathbf{H}^1\right)_{-R \le i < R} \xrightarrow{n \to \infty} \left(\mathbf{L}_i^{(\lambda)}\right)_{-R \le i < R}. \quad (92) $$

**Remark 13.** The variables $\mathbf{L}_i^{(\lambda)}$ ($i \neq 0$), conditioned by their sum have an expectation that tends to $\frac{2d_b}{2d_h - 1}$. In fact,

$$ (N_f - 1)\mathbb{E}\left[\mathbf{L}_1^{(\lambda)}\left|\sum_i \mathbf{L}_i^{(\lambda)} = n - N_f\right.\right] + \mathbb{E}\left[\mathbf{L}_0^{(\lambda)}\left|\sum_i \mathbf{L}_i^{(\lambda)} = n - N_f\right.\right] = n - N_f, $$

and finally

$$ \mathbb{E}\left[\mathbf{L}_1^{(\lambda)}\left|\sum_i \mathbf{L}_i^{(\lambda)} = n - N_f\right.\right] \sim_{n \to \infty} \frac{n - N_f}{N_f - 1} \\ \to_{n \to \infty} \frac{1 - d_h + d_b}{d_h - d_b} = \frac{2d_b}{2d_h - 1} = \mathbb{E}[\mathbf{L}_1^{(\lambda)}]. $$

It is consistent with the value of $\lambda$ chosen in Theorem 1.8, and it is the main reason why the conditioning on the sum vanishes asymptotically.

**Proof.** **Proof of (91).** It suffices to show that, for every sequence $(b_i)_{0 \le i < N_f}$ such that $\sum 2b_i = n - N_f$, then

$$ \mathbb{P}^{n, N_b(n), N_h(n), p}\left(\forall i, \Delta_i^{(n)}\mathbf{H}^1 = 2b_i\right) = \mathbb{P}\left(\forall i, \mathbf{L}_i^{(\lambda)} = 2b_i\left|\sum_i \mathbf{L}_i^{(\lambda)} = n - N_f\right.\right), \quad (93) $$

where everywhere (and also until the end of the proof, unless specified otherwise) $i$ belongs to $[0, N_f]$. Equation (32) in the proof of Corollary 2.4 implies that the probability $\mathbb{P}^{n, N_b(n), N_h(n), p}\left(\forall i, \Delta_i^{(n)}\mathbf{H}^1 = 2b_i\right)$ is proportional to $(2b_0 + 1) \prod_{j=0}^{N_f-1} C_{b_j}$. Moreover, it is immediate that:

$$ \mathbb{P}\left(\forall i, \mathbf{L}_i^{(\lambda)} = 2b_i\left|\sum_i \mathbf{L}_i^{(\lambda)} = n - N_f\right.\right) = \frac{\lambda^{n-N_f}(2b_0+1)C_{b_0}\prod_i C_{b_i}}{\mathbb{P}\left(\sum_i \mathbf{L}_i^{(\lambda)} = n - N_f\right) \mathcal{H}(\lambda) \mathcal{G}(\lambda)^{N_f-1}}. $$

In particular, both left and right members of Equation (93) are proportional, thus as they both sum to 1 (when summing over all the sequences $(b_i)_{0 \le i < N_f}$ such that $\sum 2b_i = n - N_f$) they are equal and finally Equation (93) is true.

**Proof of (92).** We know thanks to (91) that, for every $(b_i)_{-R \le i \le R}$,
$$ \mathbb{P}(\Delta_i^{(n)} \mathbf{H}^1 = 2b_i, -R \le i \le R) = \mathbb{P}\left(\mathbf{L}_i^{(\lambda)} = 2b_i, \forall i \in [-R, R-1] \middle| \sum_{i=-R}^{N_f-1-R} \mathbf{L}_i^{(\lambda)} = n - N_f\right) \quad (94) $$

$$ = \prod_{i=-R}^{R-1} \mathbb{P}(\mathbf{L}_i^{(\lambda)} = 2b_i) \frac{\mathbb{P}\left(\sum_{i=R}^{N_f-1-R} \mathbf{L}_i^{(\lambda)} = n - N_f - \sum 2b_i\right)}{\mathbb{P}\left(\sum_{i=-R}^{N_f-1-R} \mathbf{L}_i^{(\lambda)} = n - N_f\right)}. \quad (95) $$

The central local limit theorem (see (128) in Appendix A.1) implies that

$$ \frac{\sigma\sqrt{n}}{2} \mathbb{P}\left(\sum_{i=R}^{N_f-1-R} \mathbf{L}_i^{(\lambda)} = n - N_f - \sum 2b_i\right) \xrightarrow{n \to \infty} \frac{1}{\sqrt{2\pi}}, \quad (96) $$

where $\sigma^2 = \mathrm{Var}(\mathbf{L}_j^{(\lambda)}) \in (0, \infty)$, for every $j \ne 0$.

One could do the same for $\sum_{i=-R}^{N_f-1-R} \mathbf{L}_i^{(\lambda)}$, but since $\mathbf{L}_0^{(\lambda)}$ does not have the same distribution as the other $\mathbf{L}_i^{(\lambda)}$, we first need to “get rid of it” before applying the central local limit theorem.

Markov's inequality implies that $\mathbb{P}(\mathbf{L}_0^{(\lambda)} \ge n^{1/3}) \le c/n^{1/3}$ (with $c = \mathbb{E}[\mathbf{L}_0^{(\lambda)}]$). We can thus rewrite

$$ \mathbb{P}\left(\sum_{i=-R}^{N_f-1-R} \mathbf{L}_i^{(\lambda)} = n - N_f\right) = \mathbb{P}\left(\sum_{i=-R, i \ne 0}^{N_f-1-R} \mathbf{L}_i^{(\lambda)} = n - N_f - \mathbf{L}_0^{(\lambda)} \middle| \mathbf{L}_0^{(\lambda)} < n^{1/3}\right) (1 - O(n^{-1/3})) \\ + O(n^{-1/3}). $$

Then, recall that $\lambda$ is such that $\mathbb{E}[\mathbf{L}_i^{(\lambda)}] = \frac{2d_b}{2d_h-1}$, for every $i \ne 0$ and that $d_b + d_h = 1$. As a consequence, $\mathbb{E}[\sum_{i=-R}^{N_f-1-R} \mathbf{L}_i^{(\lambda)}] = \frac{2d_b}{2d_h-1} N_f \xrightarrow{n \to \infty} n - N_f$. We can thus use Equality (127) in Appendix A.1 (which is a consequence of the central local limit theorem) to prove that

$$ \frac{\sigma\sqrt{n}}{2} \mathbb{P}\left(\sum_{i=-R, i \ne 0}^{N_f-1-R} \mathbf{L}_i^{(\lambda)} = n - N_f - \mathbf{L}_0^{(\lambda)} \middle| \mathbf{L}_0^{(\lambda)} < n^{1/3}\right) \xrightarrow{n \to \infty} \frac{1}{\sqrt{2\pi}}. \quad (97) $$

(if it is not clear enough, write the LHS of (97) conditionally to $\{\mathbf{L}_0^{(\lambda)} = x\}$, for some $|x| < n^{1/3}$, and observe that the central local limit theorem gives the convergence to the limit uniformly for these $x$).

This implies that

$$ \frac{\sigma\sqrt{n}}{2} \mathbb{P}\left(\sum_{i=-R}^{N_f-1-R} \mathbf{L}_i^{(\lambda)} = n - N_f\right) \xrightarrow{n \to \infty} \frac{1}{\sqrt{2\pi}}. \quad (98) $$

Now, we can combine Equations (96) and (98) to see that the quotient in Equation (95) converges to 1, and finally we conclude:

$$ \mathbb{P}(\Delta_i \mathbf{H}^{1(n)} = 2b_i, -R \le i \le R-1) \xrightarrow{n \to \infty} \prod_{i=-R}^{R-1} \mathbb{P}(\mathbf{L}_i^{(\lambda)} = 2b_i). \quad (99) $$

□
**Step 2:** We show that with high probability (that is, up to a probability $\epsilon > 0$), the $R$ first holes on the right and on the left of 0 belong to some deterministic finite (though large enough) interval around 0, which we will denote as $[M, M]$ (both for the golf model on $\mathbb{Z}$ and on $\mathbb{Z}/n\mathbb{Z}$, for any $n$ large enough). It is proven in the following lemma, and we will see later that it implies that the process on $[M, M]$ suffices, with high probability, to determine the $R-1$ first free holes on the right and on the left of 0.

**Lemma 3.6.** Let $R > 0$ and $\epsilon > 0$. There exists $M \in \mathbb{N}$ and $n_0 \in \mathbb{N}$ such that,

$$ \mathbb{P}^{\mathbb{Z},d_b,d_h,p} (|\mathbf{H}^1 \cap [-M,0]| \ge R+2 \text{ and } |\mathbf{H}^1 \cap [1,M]| \ge R+2) > 1-\epsilon, \quad (100) $$

and for every $n \ge n_0$,

$$ \mathbb{P}^{n,N_b(n),N_h(n),p} (|\mathbf{H}^1 \cap [-M,0]| \ge R+2 \text{ and } |\mathbf{H}^1 \cap [1,M]| \ge R+2) > 1-\epsilon. \quad (101) $$

*Proof.* On $\mathbb{Z}$, we can define an ordering of $\mathbf{H}^1$: we define the random variables $\mathbf{H}_i^1$, for every $i \in \mathbb{Z}$, corresponding to the $i$th hole with respect to 0 (the hole indexed by 0 is the first hole on the left of 0: $\mathbf{H}_0^1 = \sup\{h \in \mathbf{H}^1: h \le 0\}$; the other holes are such that $\forall i \in \mathbb{Z}, \mathbf{H}_i^1 < \mathbf{H}_{i+1}^1$). In this way, it is consistent with the definition of $\Delta\mathbf{H}^1$, since $\Delta_0\mathbf{H}^1 = \mathbf{H}_1^1 - \mathbf{H}_0^1 - 1$. Similarly, we define the variables $(\mathbf{H}_i^{(n)})_{i \in \mathbb{Z}/N_f\mathbb{Z}}$ corresponding to the ordering of the elements of $\mathbf{H}_1^{(n)}$ on $\mathbb{Z}/n\mathbb{Z}$.

For the golf process on $\mathbb{Z}$, we have proven (see Corollary 3.3) that there is an infinite number of holes, on the left and on the right of 0. Thus $\mathbf{H}_i^1$, with $i \in [-R-1, R+2]$ are almost surely finite random variables, and this directly implies (100).

On $\mathbb{Z}/n\mathbb{Z}$, we can use Lemma 3.5 to prove that $(\mathbf{H}_i^{(n)})_{-R-1 \le i < R+2}$ converges in distribution (it is a consequence of (99) and of the fact that the point of index 0 is uniform in the block that contains 0, of size $\Delta_0^{(n)}\mathbf{H}^1$, that converges in distribution). $\square$

**Step 3:** In order to couple the golf model on $\mathbb{Z}$ with the golf model on $\mathbb{Z}/n\mathbb{Z}$ (on a large neighborhood of 0), we want to show that the distributions of the two initial configurations on this large neighborhood become arbitrarily close (when $n$ goes to infinity).

**Lemma 3.7 (uniformity of the approximation).** Let $I$ be some finite interval of $\mathbb{Z}$.

$$ \sup_{(x_i)_{i \in I} \in \{\mathbf{b}, \mathbf{h}\}^I} \left| \frac{\mathbb{P}^{n, N_b(n), N_h(n), p} (\forall i \in I, \eta_i^0 = x_i)}{\mathbb{P}^{\mathbb{Z}, d_b, d_h, p} (\forall i \in I, \eta_i^0 = x_i)} - 1 \right| \xrightarrow{n \to \infty} 0. $$

(Here, on $\mathbb{Z}/n\mathbb{Z}$, on the left of 0, the index $-i \in I$ with $-i \le 0$ needs to be seen as $-i = n - i \in \mathbb{Z}/n\mathbb{Z}$, so that on $\mathbb{Z}$ and $\mathbb{Z}/n\mathbb{Z}$, around 0, the indices can be identified).

*Proof.* Let $(x_i)_{i \in I} \in \{\mathbf{b}, \mathbf{h}\}^I$. One can easily compute:

$$ \mathbb{P}^{n, N_b(n), N_h(n), p} (\forall i \in I, \eta_i^0 = x_i) = \frac{\binom{n-|I|}{N_h(n)-\{|i \in I: x_i = \mathbf{h}|}}}{\binom{n}{N_h(n)}} \quad (102) $$

$$ \sim \frac{N_h(n)^{|\{i \in I: x_i = \mathbf{h}\}|} N_b(n)^{|\{i \in I: x_i = \mathbf{b}\}|}}{n^{|I|}} \quad (103) $$

$$ \xrightarrow{n \to \infty} d_h^{|\{i \in I: x_i = \mathbf{h}\}|} d_b^{|\{i \in I: x_i = \mathbf{b}\}|}. \quad (104) $$

And the right member of (104) is equal to $\mathbb{P}^{\mathbb{Z},d_b,d_h,p} (\forall i \in I, \eta_i^0 = x_i)$. $\square$
<figure><img src="image_17.png" /><figcaption>Figure 11: Illustration of Lemma 3.8. We show two golf processes $\eta$ and $\eta'$ (typically, one of them is the golf process on $\mathbb{Z}$ and the other one is on $\mathbb{Z}/n\mathbb{Z}$). A white circle corresponds to an empty hole in the final configuration, while the orange one represents a hole on which we do not do any assumption (but we will show that it is also free). The other vertices can contain holes, empty or not. We assume that the initial configurations restricted to $I$ coincide $(\eta_i^0 = \eta_i'^0, \forall i \in I)$ and that the trajectories of the balls are given by the same infinite paths, as explained in Lemma 3.8. Lemma 3.8 states that if $x$ and $y$ are free holes in $\eta'^1$ and $z \in [x, y]$ is free in $\eta^1$, then $z$ is also free in $\eta'^1$.</figcaption></figure>

**Step 4:** We give and prove the last technical lemma we need to conclude. It is a deterministic lemma, in the sense that it involves considerations on a fixed final configuration and states that something cannot happen. It is illustrated on Figure 11.

**Lemma 3.8.** We assume that $\eta$ and $\eta'$ are two golf processes (one on $\mathbb{Z}/n\mathbb{Z}$ and one on $\mathbb{Z}$) such that the initial configurations $\eta^0$ and $\eta'^0$ coincide on some interval $I = [x, y]$. We also assume that the clocks are the same on $I$, and that the trajectories of the balls of $I$ are given by the same infinite paths, in the following way: there is a family of infinite paths $(w^{(i)})_{i \in I}$ such that for every $i$, $w^{(i)}$ is a path on $\mathbb{Z}$ starting at $i$, and a ball starting at vertex $b$ at some time $t = C(b)$ does the walk given by $w^{(b)}$ stopped at the first empty hole it finds (and fills it, as usual).

If there is $z$ such that $x < z < y$, $x$ and $y$ are empty holes in $\eta'^1$ and $z$ is an empty hole in $\eta^1$, then $z$ is also empty in $\eta'^1$.

*Proof.* We prove this by contradiction.

We assume that $h_0 := z$ is not empty in $\eta'^1$. It means that there exists $b_1 \in I$ such that at time $t_1 := C(b_1)$, $h_0$ was the first hole of $w^{(b_1)}$ that was empty in $\eta'^{t_1}$. Notice that since $x$ and $y$ are empty, $b_1$ necessarily belongs to $I$. Since, in $\eta$, the ball in $b_1$ did not reach $h_0$, it means that there exists $h_1$ that was empty in $\eta^{t_1}$ but not empty in $\eta'^{t_1}$ (and such that $h_1$ appears before $h_0$ in $w^{(b_1)}$).

We apply this reasoning inductively: from a hole $h_i$ empty in $\eta^{t_i}$ but not empty in $\eta'^{t_i}$, we can obtain, with an identical reasoning, a ball $b_{i+1} \in I$ with clock $t_{i+1} := C(b_{i+1}) < t_i$, that fills $h_i$ in $\eta'$ at time $t_{i+1}$. It implies that there exists a hole $h_{i+1}$ which is empty in $\eta^{t_{i+1}}$ but not empty in $\eta'^{t_{i+1}}$. We thus build an infinite sequence $(b_k)_{k \ge 0}$ of balls such that for every $k$, $b_k \in I$ and $C(b_{k+1}) < C(b_k)$. As $I$ is finite, we have a contradiction, and deduce that $z$ is empty. $\square$

**Conclusion:** We can now prove Theorem 1.8.

*Proof of Theorem 1.8.* We let $R > 0$ and $\varepsilon > 0$ and take $M$ large enough so that Equations (100) and (101) hold.

As explained above, for $n$ large enough, it is possible to construct a coupling between the initial configurations on $\mathbb{Z}/n\mathbb{Z}$ and $\mathbb{Z}$ so that the initial configurations are equal on
<figure><img src="image_18.png" /><figcaption>Figure 12: Illustration of the fact that the $R + 2$ empty holes to the left of 0 (included) in $\eta^1$ coincide with the $R + 2$ empty holes to the left of 0 in $\eta'^1$: we let $k$ (resp. $k'$) be the position of the $R + 2$th hole to the left of 0 (included) in $\eta^1$ (resp. $\eta'^1$). We assume that $k \le k'$ (the case $k' \le k$ is symmetric). There are $R + 2$ empty holes in $[k', 0]$ in $\eta'^1$, and Lemma 3.8 implies that all these holes are also empty holes in $\eta^1$ (since we know that there exists a free hole to the right of 0 in $\eta$, at position $l$ on the picture): all the orange vertices in $\eta^1$ are empty holes. As there are exactly $R + 2$ empty holes in $[k, 0]$ in $\eta^1$, it implies that $k' = k$ and that in the interval $[k, 0]$, a hole is free in $\eta^1$ if and only if it is free in $\eta'^1$.</figcaption></figure>

$I = [-M, M]$ with high probability. We can then use Lemma 3.7: there exists $n$ (large enough) such that

$$ \sup_{(x_i)_{i \in I} \in \{\text{b,h}\}^I} \left| \mathbb{P}^{n, N_b(n), N_h(n), p} \left( \forall i \in I, \eta_i^{0(n)} = x_i \right) - \mathbb{P}^{\mathbb{Z}, d_b, d_h, p} \left( \forall i \in I, \eta_i^0 = x_i \right) \right| < \frac{\varepsilon/2}{2^{2M+1}} \quad (105) $$

(here and in the sequel, to avoid ambiguity, we write $\eta^{0(n)}$ for the initial configuration on $\mathbb{Z}/n\mathbb{Z}$).

It implies that there exists a coupling of $\eta^{0(n)}$ and $\eta^0$ such that<fnref n="7" />

$$ \mathbb{P} \left( \forall i \in I, \eta_i^{0(n)} = \eta_i^0 \right) \ge 1 - \varepsilon. \quad (106) $$

We assume in what follows that $\eta^{0(n)}$ and $\eta^0$ are coupled this way. We extend the coupling to the clocks, letting $C(v)$ (with $v \in \mathbb{Z}$) be independent with distribution $U([0, 1])$, and then defining the clocks on $\mathbb{Z}/n\mathbb{Z}$ by $\forall i \in I, C^{(n)}(v) := C(v)$, and for any $v \notin I, C^{(n)}(v) \sim U([0, 1])$ also independently of the other variables.

We then couple the trajectories of the balls. We define, for every $v \in \mathbb{Z}$, an infinite random walk $(w_k^{(v)})_{k \ge 0}$ with transition matrix $P$, starting at $w^{(v)} = 0 = v$. We then define the golf processes on $\mathbb{Z}$ so that a ball starting at $u$ at time $C(u)$ does a random walk with steps given by $w^{(u)}$ until it hits a free hole. Similarly, on $\mathbb{Z}/n\mathbb{Z}$, a ball starting at $u \in \mathbb{Z}/n\mathbb{Z}$ at time $C^{(n)}(u)$ uses $w^{(i)}$ for its random walk, where $i$ is the unique integer such that $-n/2 < i \le n/2$ and $i \bmod n = u$. We then have a coupling of the golf processes on $\mathbb{Z}$ and $\mathbb{Z}/n\mathbb{Z}$.

Therefore, combining this with Lemma 3.6, we deduce that with probability at least $1 - 3\varepsilon$, $\forall i \in I, \eta_i^{0(n)} = \eta_i^0$, $|\mathbf{H}^1 \cap [-M, 0]| \ge R + 2$ and $|\mathbf{H}^1 \cap [1, M]| \ge R + 2$. Lemma 3.8 enables to conclude that on this event, the positions of the remaining holes indexed from $-R$ to $R + 1$ also coincide (see Figure 12): $(\Delta_i \mathbf{H}^1)_{-R \le i \le R} = (\Delta_i^{(n)} \mathbf{H}^1)_{-R \le i \le R}$ with probability at least $1 - 3\varepsilon$.

<footnote n="7">⁷More precisely, there exists a probability space $(\Omega, \mathcal{A}, \mathbb{P})$ on which one can find copies $\bar{\eta}_i^0$ of $\eta_i^0$ under $\mathbb{P}^{\mathbb{Z}, d_b, d_h, p}$ and $\bar{\eta}_i^{0(n)}$ of $\eta_i^{0(n)}$ under $\mathbb{P}^{n, N_b, N_h, p}$ such that with probability at least $1 - \varepsilon$, $\forall i \in I, \bar{\eta}_i^0 = \bar{\eta}_i^{0(n)}$</footnote>
We can conclude about the distribution of $(\Delta_i \mathbf{H}^1)_{-R \le i \le R}$. We have seen (Lemma 3.5) that $(\Delta_i^{(n)} \mathbf{H}^1)_{-R \le i \le R}$ converges in distribution to $(\mathcal{L}_i^{(\lambda)})_{-R \le i \le R}$. In the previous paragraph, we showed that $(\Delta_i^{(n)} \mathbf{H}^1)_{-R \le i \le R}$ converges in probability to $(\Delta_i \mathbf{H}^1)_{-R \le i \le R}$. It implies that $(\Delta_i \mathbf{H}^1)_{-R \le i \le R}$ has the same distribution as $(\mathcal{L}_i^{(\lambda)})_{-R \le i \le R}$. $\square$

## 3.4 Distribution of the block-size process in general

We give the following theorem for the distribution of $\Delta \mathbf{H}^1$. Notice that we do not assume that $d_b + d_h = 1$ anymore.

**Theorem 3.9.** We assume that $0 < d_b < d_h$ and $d_b + d_h \le 1$. Then, under $\mathbb{P}^{\mathbb{Z},d_b,d_h,p}$, for every $\ell_0 \ge 0$,

$$ \mathbb{P}(\Delta_0 \mathbf{H}^1 = \ell_0) = (d_h - d_b) \sum_{b_0: 2b_0 \le \ell_0} \frac{\ell_0 + 1}{b_0 + 1} \binom{\ell_0}{b_0, b_0, \ell_0 - 2b_0} d_b^{b_0} d_h^{b_0+1} (1 - d_b - d_h)^{\ell_0 - 2b_0}. \quad (107) $$

One could obtain, with the same reasoning, a theorem for the distribution of the whole process $(\Delta_i \mathbf{H}^1)$ (similar to what we have in Theorem 1.8 when $d_b + d_h = 1$), but it would involve heavy computation that we leave as an exercise to the interested reader.

When $d_b + d_h = 1$, the theorem simplifies and gives: for every $k \ge 0$,

$$ \mathbb{P}(\Delta_0 \mathbf{H}^1 = 2k) = (d_h - d_b) \frac{2k+1}{k+1} \binom{2k}{k} d_b d_h^k. \quad (108) $$

which is consistent with Theorem 1.8.

**Proof of Theorem 3.9.** The idea of the proof is exactly the same as for the proof of Theorem 1.8: we show that, when $N_b = \lfloor d_b n \rfloor$ and $N_h = \lfloor d_h n \rfloor$, $\Delta_0^{(n)} \mathbf{H}^1 \xrightarrow{d} L_0$ as $n$ goes to infinity, for some random variable $L_0$ whose law is given by the right-hand side of (107); then, Lemmas 3.6 and 3.7 still hold and we can again do a coupling between the initial configurations on $\mathbb{Z}/n\mathbb{Z}$ (for some $n$ large enough) and $\mathbb{Z}$.

We thus only need to prove that $\Delta_0^{(n)} \mathbf{H}^1$ converges in distribution as $n$ goes to infinity. First, we can show the following claim:

**Claim 3.10.** For any integer $\ell_0 \ge 0$ such that $\ell_0 \le n - 2$,

$$ \mathbb{P}(\Delta_0^{(n)} \mathbf{H}^1 = \ell_0) \quad (109) $$

$$ = \sum_{b_0: b_0 \le N_b \text{ and } 2b_0 \le \ell_0} \frac{\ell_0 + 1}{b_0 + 1} \binom{\ell_0}{b_0, b_0, \ell_0 - 2b_0} \frac{\frac{N_f-1}{N_h - b_0 - 1} \binom{n-\ell_0-2}{N_b - b_0, N_h - b_0 - 2, n - \ell_0 - N_b - N_h + 2b_0}}{\binom{n}{N_b, N_h, n - N_b - N_h}}. \quad (110) $$

We postpone its proof to the end of the proof of Theorem 3.9.

Now, for every $n$, we let $N_b(n) := \lfloor d_b n \rfloor$ and $N_h(n) := \lfloor d_h n \rfloor$. Then, using the Claim and Stirling's formula, we can easily prove that for any $\ell_0$,

$$ \mathbb{P}(\Delta_0^{(n)} \mathbf{H}^1 = \ell_0) \xrightarrow{n \to \infty} f(\ell_0) \quad (111) $$

where we have defined, for every $\ell_0$, $f(\ell_0)$ as the right-hand side of Equation (107).

**Claim 3.11.** We have the following:

$$ \sum_{\ell_0 \ge 0} f(\ell_0) = 1. \quad (112) $$
The proof of this claim is quite technical (yet very interesting, since it involves some nice combinatorial interpretation of this sum), so we postpone it to the end of the subsection.

Thanks to these previous claims, we can deduce that the law of $\Delta_0^{(n)}\mathbf{H}^1$ converges to $f$. $\square$

**Proof of Claim 3.10.** The computation follows exactly the same reasoning as the proof of Theorem 1.2, and we detail the main subtleties. There are $\ell_0 + 1$ pairs $(x_0, x_1)$ such that $x_0 \le 0 < x_1$ and $x_1 - x_0 - 1 \mod n = \ell_0$. For any such $(x_0, x_1)$ we want to compute the probability of the event $A := \{\mathbf{H}^1 \cap [[x_0, x_1]] = \{x_0, x_1\}\}$ (and this will provide $\mathbb{P}(\Delta_0^{(n)}\mathbf{H}^1 = \ell_0) = (\ell_0 + 1)\mathbb{P}(A)$).

It is possible to obtain a decomposition result analogous to Equation (11) in Lemma 2.2, stating that if we condition on the number of holes and balls between $x_0$ and $x_1$ being $b_0$,

$$ \mathbb{P}(A|x_0, x_1 \in \mathbf{H}^0 \text{ and } |[[x_0, x_1]] \cap \mathbf{B}^0| = b_0) = \mathbb{P}^{\ell_0, b_0, b_0+1, p}(\mathbf{H}^1 = \{0\} | 0 \in \mathbf{H}^0) \quad (113) \\ \times \mathbb{P}^{n-\ell_0, N_b-b_0, N_h-b_0-1, p}(\mathbf{H}^1 = \{0\} | 0 \in \mathbf{H}^0) \quad (114) $$

(this key decomposition is illustrated on Figure 13). Then, as before, $\mathbb{P}^{\ell_0, b_0, b_0+1, p}(\mathbf{H}^1 = \{0\} | 0 \in \mathbf{H}^0) = \frac{1}{b_0+1}$. The difference that appears with the proof of Theorem 1.2 lies in the computation of $\mathbb{P}^{n-\ell_0, N_b-b_0, N_h-b_0-1, p}(\mathbf{H}^1 = \{0\} | 0 \in \mathbf{H}^0)$. Since there are $(N_h - b_0 - 1) - (N_b - b_0) = N_f - 1$ remaining holes in the associated golf model, it implies (by invariance by rotation, as in Lemma 2.1) that

$$ \mathbb{P}^{n-\ell_0, N_b-b_0, N_h-b_0-1, p}(\mathbf{H}^1 = \{0\}) = \frac{N_f - 1}{n - \ell_0} \quad (115) $$

and finally that

$$ \mathbb{P}^{n-\ell_0, N_b-b_0, N_h-b_0-1, p}(\mathbf{H}^1 = \{0\} | 0 \in \mathbf{H}^0) = \frac{N_f - 1}{N_h - b_0 - 1}. \quad (116) $$

The conclusion of the claim follows from a computation similar to Equations (13) and (14) $\square$

**Proof of Claim 3.11.** We consider the random walk $(W_i)_{i \ge 0}$ defined as $W_0 = 0$ and with independent increments such that the law of $W_{i+1} - W_i$ is $d_b\delta_1 + (1 - d_b - d_h)\delta_0 + d_h\delta_{-1}$, for any $i$. The key is the following equality

$$ \frac{f(\ell_0)}{d_h - d_b} = \sum_{b_0:2b_0 \le \ell_0} \frac{\ell_0 + 1}{b_0 + 1} \binom{\ell_0}{b_0, b_0, \ell_0 - 2b_0} d_b^{b_0} d_h^{b_0+1} (1 - d_b - d_h)^{\ell_0 - 2b_0} \quad (117) $$

$$ = \sum_{b_0:2b_0 \le \ell_0} \binom{\ell_0 + 1}{b_0, b_0 + 1, \ell_0 - 2b_0} d_b^{b_0} d_h^{b_0+1} (1 - d_b - d_h)^{\ell_0 - 2b_0} \quad (118) $$

$$ = \mathbb{P}(W_{\ell_0} = -1). \quad (119) $$

Therefore, if we define $N := \sum_{\ell_0=0}^{+\infty} \mathbb{1}_{W_{\ell_0=-1}}$ as the number of passages of $W$ at $-1$, we have

$$ \sum_{\ell_0 \ge 0} f(\ell_0) = (d_h - d_b) \sum_{\ell_0 \ge 0} \mathbb{E}[\mathbb{1}_{W_{\ell_0}=-1}] = (d_h - d_b)\mathbb{E}[N]. \quad (120) $$
<figure><img src="image_19.png" /><figcaption>Figure 13: Illustration of the computation of $\mathbb{P}(A|x_0, x_1 \in \mathbf{H}^0$ and $|[[x_0, x_1]] \cap \mathbf{B}^0| = b_0)$. Here, we give an example for $n = 16$, $N_b = 5$, $N_h = 9$ and $\ell_0 = x_1 - x_0 - 1 \pmod n = 4$. In the green interval (the smaller one), there need to be the same number of balls and holes (equal to $b_0$, which is either 1 or 2, hence the notation $b_0 \times \circ + b_0 \times \bullet$). This way, there are no remaining holes in the green interval. In the blue interval, there are $h_1 = N_h - b_0 - 2$ holes and $b_1 = N_b - b_0$ balls. Thus, at time 1, the number of holes in $\mathbf{H}^1$ in the blue interval is equal to $h_1 - b_1 = N_h - N_b - 2$ (equal to 2 in this example).</figcaption></figure>

To compute $\mathbb{E}[N]$, we let $N_{-1} \stackrel{(d)}{=} \sum_{\ell_0 > \tau_{-1}} \mathbb{1}_{W_{\ell_0}=-1}$ be the number of passages at -1 after time $\tau_{-1}$. We observe that $N \stackrel{(d)}{=} 1 + N_{-1}$ and we can decompose $N_{-1}$ according to the first step of the walk after time $\tau_{-1}$, which we denote by $X = W_{\tau_{-1}+1} - W_{\tau_{-1}}$:

$$ N_{-1} \stackrel{(d)}{=} \left\{ \begin{array}{ll} N & \text{with probability } d_b \quad (\text{if } X=1) \\ 1+N_{-1} & \text{with proba } 1-d_b-d_h \quad (\text{if } X=0) \\ 1+N_{-1} & \text{with proba } d_h p_{-2} \quad (\text{if } X=-1 \text{ and } W \text{ returns to } -1) \\ 0 & \text{with proba } d_h(1-p_{-2}) \quad (\text{if } X=-1 \text{ and } W \text{ never returns to } -1) \end{array} \right. \tag{121} $$

where $p_{-2} := \mathbb{P}_{-2}(\tau_{-1} < \infty)$ refers to the probability that $W$ returns to $-1$ after having reached $-2$. We now show that $\mathbb{P}_{-2}(\tau_{-1} < \infty) = \frac{d_b}{d_b+d_h} \mathcal{G}\left(\frac{d_b d_h}{(d_b+d_h)^2}\right)$ (recall that $\mathcal{G}$ is the Catalan generating function). We consider the walk $W'$, starting at $-2$ and with i.i.d. increments having distribution $\mathcal{L}(W'_{i+1} - W'_{i}) = \frac{d_b}{d_b+d_h} \delta_1 + \frac{d_h}{d_b+d_h} \delta_{-1}$. Then, since the return of $W$ to $-1$ (after time $\tau_{-2}$) does not depend on its steps 0, it means that $\mathbb{P}_{-2}(\tau_{-1} < \infty) = \mathbb{P}_{-2}(\tau_{-1}(W') < \infty)$. We can thus compute it:

$$ \mathbb{P}_{-2}(\tau_{-1} < \infty) = \sum_{k \ge 0} \mathbb{P}(\tau_{-1}(W') = 2k + 1) \tag{122} $$

$$ = \sum_{k \ge 0} C_k \left( \frac{d_b}{d_b + d_h} \right)^{k+1} \left( \frac{d_h}{d_b + d_h} \right)^k = \frac{d_b}{d_b + d_h} \mathcal{G} \left( \frac{d_b d_h}{(d_b + d_h)^2} \right). \tag{123} $$

In particular, it is straightforward to compute that $\mathcal{G}\left(\frac{d_b d_h}{(d_b+d_h)^2}\right) = \frac{d_b+d_h}{d_h}$ (since $d_h > d_b > 0$). Moreover, Equation (121) gives the following system:

$$ \left\{ \begin{array}{l} \mathbb{E}[N] = 1 + \mathbb{E}[N_{-1}], \\ \mathbb{E}[N_{-1}] = d_b \mathbb{E}[N] + \left(1 - d_b - d_h + \frac{d_b d_h}{d_b+d_h} \mathcal{G}\left(\frac{d_b d_h}{(d_b+d_h)^2}\right)\right) (1 + \mathbb{E}[N_{-1}]). \end{array} \right. \tag{124} $$

which can be solved to obtain $\mathbb{E}[N] = \frac{1}{d_h - d_b}$. Finally, $\sum_{\ell_0 \ge 0} f(\ell_0) = (d_h - d_b)\mathbb{E}[N] = 1$ as wanted. $\square$
## 3.5 Law of the set of remaining holes when $d_b = d_h$ - proof of Theorem 1.9

*Proof of Theorem 1.9.* We assume that $d_b = d_h$. The case $d_b = 0$ is trivial, so we assume that $d_b > 0$. We let $k \ge 1$ and $\varepsilon > 0$.

As $\mathbf{H}^t$ is well-defined for every $t$, we can consider the process $(\Delta_0 \mathbf{H}^t)_{t \in [0,1]}$. It is a non-decreasing process (since $\mathbf{H}^t$ is a set that decreases over time), and thus for any $t < 1$,

$$ \forall i, \mathbb{P}^{\mathbb{Z},d_h,d_h,p}(\Delta_0 \mathbf{H}^1 \le i) \le \mathbb{P}^{\mathbb{Z},d_h,d_h,p}(\Delta_0 \mathbf{H}^t \le i). $$

Then (also for any $t$), $\Delta_0 \mathbf{H}^t$ under $\mathbb{P}^{\mathbb{Z},d_h,d_h,p}$ has the same distribution as $\Delta_0 \mathbf{H}^1$ under $\mathbb{P}^{\mathbb{Z},td_h,d_h,p}$ (the key being that, in both cases, the probability that some vertex contains a ball that has been activated at the considered time is $td_h$). In particular, $\mathbb{P}^{\mathbb{Z},d_h,d_h,p}(\Delta_0 \mathbf{H}^t \le k) = \mathbb{P}^{\mathbb{Z},td_h,d_h,p}(\Delta_0 \mathbf{H}^1 \le k)$.

Equation (107) implies that for every $i$, $\mathbb{P}^{\mathbb{Z},d_h,d_h,p}(\Delta_0 \mathbf{H}^1 = i)$ goes to 0 as $d_b$ tends to $d_h$. Thus there exists $t_\varepsilon < 1$ large enough so that for every $i \in [0, k]$, $\mathbb{P}^{\mathbb{Z},t_\varepsilon d_h,d_h,p}(\Delta_0 \mathbf{H}^1 = i) \le \varepsilon$. It enables to conclude :

$$ \mathbb{P}^{\mathbb{Z},d_h,d_h,p}(\Delta_0 \mathbf{H}^1 \le k) \le \mathbb{P}^{\mathbb{Z},td_h,d_h,p}(\Delta_0 \mathbf{H}^1 \le k) \le (k+1)\varepsilon. \quad (125) $$

As this is true for any $\varepsilon$, it implies that $\mathbb{P}^{\mathbb{Z},d_h,d_h,p}(\Delta_0 \mathbf{H}^1 \le k) = 0$. Therefore, under $\mathbb{P}^{\mathbb{Z},d_h,d_h,p}$, $\Delta_0 \mathbf{H}^1 = +\infty$ almost surely. Finally, thanks to Remark 8, $\mathbf{H}^1 = \emptyset$ almost surely. $\square$

We therefore obtain the following results, completing Corollary 3.4: we know that when $d_b > d_h$ the process is valid until time $d_h/d_b$ (included), and this corollary tells us what happens after time $d_h/d_b$.

**Corollary 3.12.** If $d_b > d_h$, the golf process on $\mathbb{Z}$ is almost surely frozen at any time $t > d_h/d_b$.

Recall that a process is frozen when a ball cannot reach a hole. Theorem 1.9 implies that at time $d_h/d_b$ all the holes are filled, and thus the process becomes frozen as soon as other balls are activated.

## 3.6 Coupling with the parking on $\mathbb{Z}$

We described in Section 1.6.3 the parking process on $\mathbb{Z}$ (see [PRS23]), defined with the same initial configuration as the golf process on $\mathbb{Z}$ (i.e. each site contains a ball with probability $d_b$ or a hole with probability $d_h$, independently of the other sites). In the parking process, all the balls move simultaneously, doing one random step at each integer time, until they have reached a free hole, which becomes occupied, as usual. More precisely, each ball steps are independent, and such that a ball moves to the right with probability $p$, to the left with probability $1-p$. Recall that $\mathbf{H}^t$ is the set of free holes at time $t$ for the golf process. Similarly, we let $P^t$ be the set of free holes at time $t$ in the parking process. We should emphasize that the temporality in the golf and parking processes is completely different: the golf process ends at time $t = 1$, once every ball has moved (recall that they move only once, directly to a free hole) whereas the parking process almost surely do not reach a final configuration in finite time.

In the following theorem, we prove that when $d_b \le d_h$, the two processes have the same final configuration (asymptotically).

**Theorem 3.13** (Coupling with the parking process on $\mathbb{Z}$). When $d_b \le d_h$, $\lim_{t \to \infty} P^t \stackrel{(d)}{=} \mathbf{H}^1$. Moreover, the two processes can be coupled so that almost surely,

$$ \lim_{t \to \infty} P^t = \mathbf{H}^1. $$
*Proof.* As for Theorem 1.7, we first prove the result in the case $d_b < d_h$. We consider $\eta$ the golf process, and $\xi$ the parking process, coupled so that $\eta^0 = \xi^0$ (this is possible since the two initial configurations have the same distribution). We let, as in the proof of theorem 1.7, **Sep** be the set of separators in $\eta^0$. We use Lemma 3.1 and consider the processes $\eta$ and $\xi$ between two consecutive elements of **Sep**: it suffices to do a finite coupling between those two processes. This coupling comes directly thanks to Diaconis and Fulton argument ([DF91], see Remark 1), or equivalently from the space-based model introduced in [PRS23]: we associate to each vertex $u$ an infinite sequence $V^u = (V_1^u, V_2^u, \cdots)$ such that $\forall v, \mathbb{P}(V_i^u = v) = P_{u,v}$. We let $V$ be this sequence for the golf process $\eta$, and $W = V$ be a copy of this sequence, which is going to be used for the parking process. We then proceed as explained in Remark 1: when a ball at vertex $u$ needs to do a step in the golf process (respectively in the parking process), it moves according to the first $V_i^u$ (respectively $W_i^u$) that has not been used yet. For the parking case, we use random variables to break ties if needed. Then, we know from Diaconis-Fulton that whatever the order in which the balls move, the same steps of $V$ will be used, so in particular the same holes will be reached in both the golf and the parking processes. We thus have built a coupling of the two final configurations $\eta^1$ and $\lim_{t\to\infty} \xi^t$, between every pair of consecutive elements of **Sep**. This induces a coupling on the final configurations on $\mathbb{Z}$, since we have seen (Lemma 3.2) that separators are free holes, at any time step (and it is straight forward to check that it is also true for the parking process).

When $d_b = d_h$, we have proved that, for the golf process, every ball finds a hole and that at time 1, every hole is filled (see Theorem 1.9). It suffices to prove the same result for the parking process. First, every ball finds a hole almost surely (it is a direct consequence of Theorem 1.2 in [PRS23], applying Markov property to conclude that $\mathbb{P}(\tau > t) \le Ct^{-1/4}$, where $\tau$ is the time at which a ball finds a hole). Second, we can prove that $\lim_{t\to\infty} P^t = \emptyset$: we consider $P^t$ as a function of $d_b$, and now write $P^t(d_b)$, for the process in which we only have activated balls with clocks $< d_b$ (clocks being the same as clocks for the golf process, as in the previous paragraph). With this notation, we thus want to prove that $\lim_{t\to\infty} P^t(d_h) = \emptyset$. Since we do not care which ball fills which hole in the parking, it is straightforward that $P^t(d_b)$ is a decreasing function of both $d_b$ and $t$, and therefore

$$ \lim_{t \to \infty} P^t(d_h) = \lim_{t \to \infty} \lim_{d_b \to d_h, d_b < d_h} P^t(d_b) = \lim_{d_b \to d_h, d_b < d_h} \lim_{t \to \infty} P^t(d_b) $$

Finally, we use the proof for the case $d_b < d_h$ to couple $\lim_{t\to\infty} P^t(d_b)$ with $\mathbf{H}^1$ for the golf process with $d_b < d_h$. Similar reasoning as in the proof of Theorem 1.9 implies that, when the size of the block containing 0 in $\lim_{t\to\infty} P^t(d_b)$ converges to $\infty$ when $d_b \to d_h$, and in particular $\lim_{t\to\infty} P^t(d_h) = \lim_{d_b \to d_h, d_b < d_h} \lim_{t\to\infty} P^t(d_b) = \emptyset$. $\square$

# 4 Golf and parking with different moving strategies

In this section we prove Proposition 1.10. It is a kind of corollary of Theorems 1.2, 1.5 and 1.7, or rather can be proven by more or less the same proofs, therefore we only sketch the main arguments. We first give two reasons why the proof of Theorem 1.2 is robust and applies to all the variants of the golf process that are shift invariant and local. Then, we discuss how to conclude for the other results of Proposition 1.10.

**Robustness of the proof of Theorem 1.2 - exchangeability argument** We can use an exchangeability argument to prove that the distribution of $\mathbf{H}^1$ does not depend on the strategy of the balls (but it does not give this distribution). Exchangeability is a notion
discussed, in particular, by Aldous [Ald85]. Here, the block sizes are exchangeable (except for the size of the block containing 0, which is size-biased): $(\Delta_0\mathbf{H}^1, \Delta_1\mathbf{H}^1, \dots, \Delta_{N_f-1}\mathbf{H}^1) \stackrel{(d)}{=} (\Delta_0\mathbf{H}^1, \Delta_{\sigma_1}\mathbf{H}^1, \dots, \Delta_{\sigma_{N_f-1}}\mathbf{H}^1)$, for any permutation $\sigma$ of $\{1, \dots, N_f - 1\}$. This can be proven by showing that the blocks (that is, the restrictions of the golf process between two consecutive free holes) are exchangeable, at any time $t \le 1$ (this is the identity of the block that contains 0 which is not). This comes from the fact that the balls have shift invariant and local strategies.

Exchangeability implies that the strategy of the balls do not really matter: If at time $t$, a ball $b$, coming from a block $B_j(t^{-})$ existing at this time, becomes active, it will fill the space between $B_j(t^{-})$ and $B_k(t^{-})$ where $k = j + 1$ or $j - 1$ (that is an adjacent block) and this will produce the coalescence of $B_k(t^{-})$ and $B_j(t^{-})$ at time $t$. The distribution of $k$ depends on the position of the activated ball $b$ in its block and of the transition matrix of the Markov chain it used (or more generally, of the displacement politics it employed); nevertheless, since $|B_{j+1}(t)|, |B_{j-1}(t)|$ has same distribution as $|B_{j-1}(t)|, |B_{j+1}(t)|$) by exchangeability (recall that $|B_i(t)| = \Delta_i \mathbf{H}^t$, for any $i$), the distribution of the resulting coalescent process (seen at the level of the block sizes) does not depend on the displacement politics.

This reasoning can be made rigorous to deal with the size-bias of $\Delta_0 \mathbf{H}^t$, but we do not do it here.

**Robustness of the proof of Theorem 1.2 - digging into the details of the proof of Lemma 2.2** For every shift invariant strategy, it is straightforward that Lemma 2.1 is true. Lemma 2.2 relies on the block decomposition principle, and the property of “local decision” is the key that enables to see that Lemma 2.2 is also true here: this notion of local decision implies that a ball strategy does not depend on what is outside its block, and thus that we can decompose $\mathbb{Z}/n\mathbb{Z}$ as independent blocks, that we then treat independently.

At the end of the computation (to get Equation 24 in the proof of Lemma 2.2), we use the commutation property. We can still conclude if the commutation property is not true, as it suffices to sum over all the permutations of $\mathbb{Z}/n\mathbb{Z}$ (i.e. over every order of the balls) : the uniform distribution of clocks gives a uniform permutation of the balls, which induces a uniform permutation of the balls inside each interval between consecutive elements of $X$, and thus allows to conclude. Finally, if the strategy of a ball depends on its clock, the proof of Lemma 2.2 is a bit more subtle, because it involves to deal with continuous variables, but the same structure of proof works in this continuous setting.

**Conclusion** Once Theorem 1.2 is valid, with the same formula for the distribution of $\mathbf{H}^1$, it follows directly that Theorems 1.3 and 1.4 also apply for different moving strategies.

For the parking process, the proof of Theorem 1.5 follows exactly the same steps as the one of Theorem 1.2 for the golf process (see Section 2.3), and our two previous paragraphs justify why the theorem also applies to shift invariant and local variants.

On $\mathbb{Z}$, the proof of validity of the golf process relies on a notion of separators, that are holes that cannot be filled by any ball (almost surely, for a given initial distribution), regardless of the balls strategy, and thus applies to these variants. For the proof of Theorem 1.8, the reasoning also works for any variant, with the subtlety that the coupling defined in the conclusion of the proof needs to be slightly modified (so that the coupling of the trajectories becomes a coupling of the ball strategies, such that two balls on the same vertex with the same local information do the same choice). Notice that Lemma 3.8 can also be extended to any local variant.
Acknowledgments

The author would like to thank Jean-François Marckert for his great supervision, for the
many fruitful discussions we had together and for his guiding in the writing of this paper.

We also thank Laurent Tournier and Matthew Junge who communicated us additional
references that we were not aware of in a preliminary version of the paper.

Finally, we would like to express our gratitude to the reviewers for their careful reading
and their numerous corrections and suggestions, which allowed us to improve the quality
and clarity of the paper.

References

[Ald85] David J. Aldous. Exchangeability and related topics. In P. L. Hennequin, editor, *École d'Été de Probabilités de Saint-Flour XIII — 1983*, pages 1–198, Berlin, Heidelberg, 1985. Springer Berlin Heidelberg. 53

[Ald97] David Aldous. Brownian excursions, critical random graphs and the multiplicative coalescent. *Ann. Probab.*, 25(2):812–854, 1997. 30

[BCP03] Jean Bertoin, Loic Chaumont, and Jim Pitman. Path transformations of first passage bridges. *Electronic Communications in Probability*, 8(none):155 – 166, 2003. 27, 34

[BGHR19] Riddhipratim Basu, Shirshendu Ganguly, Christopher Hoffman, and Jacob Richey. Activated random walk on a cycle. *Annales de l'Institut Henri Poincaré, Probabilités et Statistiques*, 55(3):1258 – 1277, 2019. 14

[Bia86] Philippe Biane. Relations entre pont et excursion du mouvement brownien réel. *Ann. Inst. H. Poincaré Probab. Statist.*, 22(1):1–7, 1986. 33

[Bil95] Patrick Billingsley. *Probability and measure*. Wiley Series in Probability and Mathematical Statistics. John Wiley & Sons, Inc., New York, third edition, 1995. A Wiley-Interscience Publication. 56

[Bil99] Patrick Billingsley. *Convergence of probability measures*. Wiley Series in Probability and Statistics: Probability and Statistics. John Wiley & Sons, Inc., New York, second edition, 1999. 34, 57, 58, 59

[CJ01] Philippe Chassaing and Svante Janson. A Vervaat-like path transformation for the reflected brownian bridge conditioned on its local time at 0. *The Annals of Probability*, 29(4):1755 – 1779, 2001. 34

[CL02] Philippe Chassaing and Guy Louchard. Phase transition for parking blocks, brownian excursion and coalescence. *Random Structures & Algorithms*, 21(1):76–119, 2002. 1, 7, 8, 31, 32, 33

[CRS14] M. Cabezas, L. T. Rolla, and V. Sidoravicius. Non-equilibrium phase transitions: Activated random walks at criticality. *Journal of Statistical Physics*, 155(6):1112–1125, March 2014. 14

[DF91] Persi Diaconis and William Fulton. A growth model, a game, an algebra, Lagrange inversion, and characteristic classes. *Rend. Sem. Mat. Univ. Pol. Torino*, 49(1):95–119, 1991. 4, 8, 14, 52
[DGJ$^{+}$19] Michael Damron, Janko Gravner, Matthew Junge, Hanbaek Lyu, and David Sivakoff. Parking on transitive unimodular graphs. *The Annals of Applied Probability*, 29(4):2089 – 2113, 2019. 14

[DHH$^{+}$23] Irfan Durmić, Alex Han, Pamela E. Harris, Rodrigo Ribeiro, and Mei Yin. Probabilistic parking functions. *Electron. J. Comb.*, 30(3):research paper p3.18, 25, 2023. 11

[FM21] Luis Fredes and Jean-François Marckert. Aldous-Broder theorem: extension to the non reversible case and new combinatorial proof, 2021. 14, 17

[FPV97] Philippe Flajolet, Patricio Poblete, and Alfredo Viola. On the Analysis of Linear Probing Hashing. Research Report RR-3265, INRIA, 1997. 7

[JJLS23] Tobias Johnson, Matthew Junge, Hanbaek Lyu, and David Sivakoff. Particle density in diffusion-limited annihilating systems. *The Annals of Probability*, 51(6):2301 – 2344, 2023. 14

[JM05] Svante Janson and Jean-François Marckert. Convergence of discrete snakes. *Journal of Theoretical Probability*, 18:615–645, 07 2005. 58

[Knu73] Donald E. Knuth. *The art of computer programming. Volume 3*. Addison-Wesley Series in Computer Science and Information Processing. Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont., 1973. Sorting and searching. 7, 33

[KW66] Alan G. Konheim and Benjamin Weiss. An occupancy discipline and applications. *Siam Journal on Applied Mathematics*, 14:1266–1274, 1966. 7, 11, 22

[LBG92] Gregory F. Lawler, Maury Bramson, and David Griffeath. Internal diffusion limited aggregation. *The Annals of Probability*, pages 2117–2140, 1992. 14

[Nad25] Philippe Nadeau. Bilateral parking procedures. working paper or preprint, January 2025. 11

[NT23] Philippe Nadeau and Vasu Tewari. The permutahedral variety, mixed Eulerian numbers, and principal specializations of Schubert polynomials. *Int. Math. Res. Not.* IMRN, (5):3615–3670, 2023. 14

[Pet18] F. Petrov. Combinatorial and probabilistic formulae for divided symmetrization. *Discrete Mathematics*, 341(2):336–340, 2018. 14

[Pit87] Boris Pittel. Linear probing: the probable largest search time grows logarithmically with the number of records. *Journal of algorithms*, 8(2):236–249, 1987. 8

[Pit06] Jim Pitman. *Combinatorial stochastic processes: Ecole d'été de probabilités de saint-flour xxxii-2002*. Springer, 2006. 7, 22, 28

[PRS23] Michał Przykucki, Alexander Roberts, and Alex Scott. Parking on the integers. *Ann. Appl. Probab.*, 33(2):876–901, 2023. 14, 51, 52

[Rio69] John Riordan. Ballots and trees. *Journal of Combinatorial Theory*, 6(4):408–411, 1969. 22

[Rol20] Leonardo T. Rolla. Activated random walks on $\mathbb{Z}^d$. *Probability Surveys*, 17(none), January 2020. 14
[RY99] Daniel Revuz and Marc Yor. *Continuous martingales and Brownian motion*, volume 293 of *Grundehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]*. Springer-Verlag, Berlin, third edition, 1999. 30

[Ver79] Wim Vervaat. A relation between Brownian bridge and Brownian excursion. *Ann. Probab.*, 7(1):143–149, 1979. 31, 33, 34

# A Useful theorems

## A.1 Central local limit theorem

We use the following central local limit theorem :

**Theorem A.1 (Central local limit theorem).** Let $(X_i)_{i \in \mathbb{N}}$ be a sequence of i.i.d. random variables, such that $\mathbb{E}[X_1] = \mu$ and $\text{Var}(X_1) = \sigma^2 \in (0, \infty)$. We assume that the support of $X_1$ is included in the set $b + h\mathbb{Z}$, for some $b$ and $h$, with $h$ maximal for this property. Then,

$$ \sup_x \left| \frac{\sigma \sqrt{n}}{h} \mathbb{P} \left( \frac{\sum_{i=1}^n X_i}{\sigma \sqrt{n}} = x + \sqrt{n} \frac{\mu}{\sigma} \right) - \frac{\exp - \frac{x^2}{2}}{\sqrt{2\pi}} \right| \underset{n \to \infty}{\to} 0 \quad (126) $$

where $x$ takes values in $\frac{b-\mu}{\sigma}\sqrt{n} + \frac{h}{\sigma\sqrt{n}}\mathbb{Z}$.

We can deduce that, under the same hypothesis, for any $(X_i)_{i \in \mathbb{N}}$ a sequence of i.i.d. random variables with $\mathbb{E}[X_1] = \mu$ and for any sequence $K_n = o(\sqrt{n})$,

$$ \sup_{x \in b - \mu n + h \mathbb{Z}} \left| \frac{\sigma \sqrt{n}}{h} \mathbb{P} \left( \sum_{i=1}^{n} X_i = x + n\mu \right) - \frac{1}{\sqrt{2\pi}} \right| \underset{n \to \infty}{\to} 0. \quad (127) $$

In particular, for any sequence $x_n = o(\sqrt{n})$,

$$ \frac{\sigma \sqrt{n}}{h} \mathbb{P} \left( \sum_{i=1}^{n} X_i = n\mu + x_n \right) \underset{n \to \infty}{\to} \frac{1}{\sqrt{2\pi}}. \quad (128) $$

## A.2 Scheffé's lemma and its use to prove convergence of rescaled discrete random variables

We recall the classical Scheffé's lemma (see [Bil95]):

**Lemma A.2 (Scheffé's lemma).** Let $f, f_0, f_1 \dots$ be a sequence of probability density functions on $\mathbb{R}^d$. If $(f_n)$ converges almost everywhere to $f$, and if the random variables $X_n$ and $X$ have respective densities $f_n$ and $f$, then $X_n \xrightarrow{(d)} X$.

We will use the following corollary, which is folklore:

**Corollary A.3 (Discrete Scheffé's lemma).** We consider a sequence of random variables $(X_n)_n$ on $\mathbb{Z}^d$, and a sequence $(a_n)_n \in (\mathbb{R}_+)^N$ such that $a_n \to +\infty$ as $n$ goes to infinity. We also let $X$ be a random variable with probability density function $f$, defined on $\mathbb{R}^d$. If for almost every $x \in \mathbb{R}^d$, $\lim_n a_n^d \mathbb{P}(X_n = \lfloor a_n x \rfloor) = f(x)$, then $X_n/a_n \xrightarrow{(d)} X$ as $n \to \infty$.

*Proof.* It suffices to notice that if we set, for every $n$,

$$ Y_n := \frac{X_n + U}{a_n} $$