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

HAL
open science

# Growing conditioned BGW trees with log-concave offspring distributions

William Fleurat

► To cite this version:

William Fleurat. Growing conditioned BGW trees with log-concave offspring distributions. 2025. [https://hal.science/hal-04879782v1](https://hal.science/hal-04879782v1)

HAL Id: hal-04879782

[https://hal.science/hal-04879782v1](https://hal.science/hal-04879782v1)

Preprint submitted on 10 Jan 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_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Growing conditioned BGW trees with
log-concave offspring distributions

William FLEURAT*†

November 5, 2024

Abstract

We show that given a log-concave offspring distribution, the correspond-
ing sequence of Bienaymé–Galton–Watson trees conditioned to have $n \ge 1$
vertices admits a realization as a Markov process $(T_n)_{n \ge 1}$ which adds a
new “right-leaning” leaf at each step. This applies for instance to offspring
distributions which are Poisson, binomial, geometric, or any convolution of
those. By a negative result of Janson, the log-concavity condition is opti-
mal in the restricted case of offspring distributions supported in $\{0, 1, 2\}$.
We then prove a generalization to the case of an offspring distribution sup-
ported on an arithmetic progression, if we assume log-concavity along that
progression.

As an application, we deduce the existence of increasing couplings in an
inhomogeneous model of random subtrees of the Ulam–Harris tree.

These results generalize a construction of Luczak and Winkler which
applies to uniformly sampled subtrees with *n* vertices of the infinite com-
plete *d*-ary trees. Our proofs are elementary and we tried to make them as
self-contained as possible.

<figure><img src="image_3.png" /><figcaption>Figure 1: An increasing sequence of rooted plane trees as obtained in Theorem 1. The root is at the bottom and the children of a vertex are ordered left-to-right. At each step, a new *right-leaning* leaf is added.</figcaption></figure>

<footnote>*ENS de Lyon, UMPA, France</footnote>

<footnote>†Université Paris-Saclay, LMO, France</footnote>

<footnote>william.fleurat@ens-lyon.fr</footnote>
# Contents

<table><tbody><tr><td>1</td><td>Introduction</td><td>3</td></tr><tr><td>1.1</td><td>Context</td><td>4</td></tr><tr><td>1.2</td><td>Main results</td><td>7</td></tr><tr><td>1.3</td><td>Perspectives</td><td>10</td></tr><tr><td>1.4</td><td>Organization of the paper</td><td>11</td></tr><tr><td>2</td><td>Growing random compositions</td><td>12</td></tr><tr><td>2.1</td><td>The model</td><td>12</td></tr><tr><td>2.2</td><td>Key lemma</td><td>15</td></tr><tr><td>2.3</td><td>Admissibility and shifted a-weights</td><td>16</td></tr><tr><td>3</td><td>Growing conditioned BGW trees I: the non-arithmetic case</td><td>18</td></tr><tr><td>3.1</td><td>Simply generated trees</td><td>18</td></tr><tr><td>3.2</td><td>Relationship with random compositions</td><td>19</td></tr><tr><td>3.3</td><td>Log-concavity and the Toeplitz TP2 property</td><td>21</td></tr><tr><td>3.4</td><td>Checking the inequalities</td><td>22</td></tr><tr><td>3.5</td><td>Proof of Theorems 1 and 4</td><td>25</td></tr><tr><td>4</td><td>Growing conditioned BGW trees II: the arithmetic case</td><td>25</td></tr><tr><td>4.1</td><td>Random compositions with arithmetic conditions</td><td>25</td></tr><tr><td>4.2</td><td>Admissibility and shifted a-weights, revisited</td><td>28</td></tr><tr><td>4.3</td><td>Simply generated trees in the arithmetic case</td><td>30</td></tr><tr><td>4.4</td><td>Relationship with compositions satisfying arithmetic conditions</td><td>31</td></tr><tr><td>4.5</td><td>Checking the inequalities</td><td>31</td></tr><tr><td>4.6</td><td>Proof of Theorems 2 and 5</td><td>36</td></tr><tr><td>5</td><td>Application to a model of random subtrees</td><td>36</td></tr><tr><td>5.1</td><td>Moving subtrees around</td><td>36</td></tr><tr><td>5.2</td><td>A bijection with some decorated plane trees</td><td>39</td></tr><tr><td>5.3</td><td>Probabilistic consequences</td><td>41</td></tr><tr><td>5.4</td><td>Growing the plane trees</td><td>42</td></tr><tr><td>5.5</td><td>Growing the decorations</td><td>43</td></tr><tr><td>5.6</td><td>Matching the growths by shuffling the decorated plane trees</td><td>45</td></tr><tr><td>5.7</td><td>Proof of Theorem 3</td><td>47</td></tr><tr><td>A</td><td>Decoration-dependent shufflings of decorated plane trees</td><td>49</td></tr></tbody></table>
<figure><img src="image_4.png" /><figcaption>Figure 2: An increasing sequence of rooted subtrees of the infinite complete d-ary tree, as in Luczak and Winkler’s coupling, here with $d = 3$.</figcaption></figure>

# 1 Introduction

Twenty years ago, Luczak and Winkler [LW04] showed that for every $d \ge 2$, the uniform distributions on rooted subtrees with $n$ vertices, $n \ge 1$, of the infinite complete $d$-ary tree $\mathbb{U}^{(d)}$ admit a coupling<fnref n="1" /> as an increasing process $(\mathcal{T}_n)_{n \ge 1}$, in the sense that for this process we have the inclusions

$$ \mathcal{T}_1 \subset \mathcal{T}_2 \subset \mathcal{T}_3 \subset \dots \subset \mathbb{U}^{(d)}. $$

This says in a precise sense that these distributions of random trees form a sequence which is stochastically increasing. This result has been applied to various problems relating to the number of spanning trees in the Erdös–Rényi random graphs [LPS08], stochastic ordering for infinite Bienaymé–Galton–Watson trees [LPS08, Bro14, Bro16], the parking problem on random trees [GP19], growth procedures for random planar maps [Add14, CS23], or the edge flip chain on quadrangulations [CS20]. In the case $d = 2$, the construction has been made more explicit in [CS20], and a detailed analysis of its asymptotic behaviour has been performed in [CCS24], uncovering multifractal properties of the random measure which describes where the tree $\mathcal{T}_n$ grows new vertices for every $n$.

Among the most natural and well-studied models of random trees reside Bienaymé–Galton–Watson trees conditioned on having $n$ vertices, $n \ge 1$, with some fixed offspring distribution $\mu$. It would be desirable that such sequences of random trees be stochastically increasing, too. Unfortunately that is not the case in general, as was shown by Janson [Jan06]. Still, some partial results in this direction can be deduced from Luczak and Winkler’s couplings, as we shall recall.

In this paper we give a handy sufficient condition relying on the notion of log-concavity, for the existence of increasing couplings for conditioned Bienaymé–Galton–Watson trees. We then give an application to increasing couplings in a natural inhomogeneous model of random subtrees.

<footnote n="1">¹We recall that a coupling of a collection of probability distributions $(\mathcal{L}_i)_i$ is a collection of random variables $(X_i)_i$ on a probability space $(\Omega, \mathcal{F}, \mathbf{P})$ such that for every $i$, the random variable $X_i$ has law $\mathcal{L}_i$.</footnote>
## 1.1 Context

All our trees will be represented as subsets of the Ulam-Harris tree $\mathbb{U}$,

$$ \mathbb{U} = \bigcup_{h \ge 0} \{1, 2, \dots\}^h. $$

The empty word is denoted by $\emptyset$, which is the *root vertex* of a natural *rooted tree* structure underlying the set $\mathbb{U}$: we declare that a *vertex* $\mathbf{u} \in \mathbb{U}$ is an ancestor of $\mathbf{v} \in \mathbb{U}$ if $\mathbf{u}$ is a prefix of $\mathbf{v}$. Related genealogical notions such as *parents*, *siblings*, *children* follow. For $\mathbf{u} = (u_1, \dots, u_h) \in \mathbb{U}$, the integer $h$ is called the *height* of $\mathbf{u}$, and its *ancestral line* is the sequence of vertices $(u_0, u_1, \dots, u_h)$, where $u_0 = \emptyset$ and $u_\ell = (u_1, \dots, u_\ell)$, $1 \le \ell \le h$. For $\mathbf{u}, \mathbf{v} \in \mathbb{U}$, we denote by $uv$ the *concatenation* of the words $\mathbf{u}$ and $\mathbf{v}$, and we write $\mathbf{ui}$ instead of $\mathbf{u}(i)$ when $\mathbf{v}$ is the singleton $(i)$. In particular, a *child* of $\mathbf{u} \in \mathbb{U}$ is a vertex $\mathbf{ui}$ for $i \in \{1, 2, \dots\}$.

**Plane trees and BGW measures** In Neveu's formalism [Nev86], a *plane tree* is a non-empty finite subset $T \subset \mathbb{U}$ which is closed under “taking parents” and “taking siblings to the left”, or in other words which is such that:

$$ \forall \mathbf{u} \in \mathbb{U}, \forall i \in \{1, 2, \dots\}, \quad \mathbf{ui} \in T \quad \Rightarrow \quad \begin{cases} \mathbf{u} \in T, \\ \mathbf{uj} \in T \quad 1 \le j \le i. \end{cases} $$

The set of plane trees is denoted by $\mathbb{T}$ and we let $\mathbb{T}_n$ be the subset of plane trees with $n$ vertices, $n \ge 1$. For $T \in \mathbb{T}$ and $\mathbf{u} \in T$, we let $k_\mathbf{u}(T)$ be the number of children of $\mathbf{u}$ which are in $T$. A *leaf* of $T$ is a vertex with no children in $T$.

Given some probability distribution $\mu$ on $\mathbb{Z}_+ = \{0, 1, 2, \dots\}$, with $0 < \mu(0) < 1$, the corresponding Bienaymé-Galton-Watson measure, or the $\mu$-BGW measure for short, is defined by:

$$ \forall T \in \mathbb{T}, \quad \mathbf{BGW}^\mu(T) = \prod_{\mathbf{u} \in T} \mu(k_\mathbf{u}(T)). \qquad (1.1) $$

This is a probability measure on $\mathbb{T}$ when $\mu$ has mean at most one, and a sub-probability measure otherwise. For $n \ge 1$, as long as $\mathbb{T}_n$ gets non-zero weight under the $\mu$-BGW measure, we can condition on the event $\{\#T = n\}$ to define the *probability distribution* $\mathbf{BGW}_n^\mu$ on $\mathbb{T}_n$.

**Rooted subtrees** More generally, a *rooted subtree* of $\mathbb{U}$ is a non-empty finite subset $\tau$ of $\mathbb{U}$ which is closed under “taking parents” only, that is:

$$ \forall \mathbf{u} \in \mathbb{U}, \forall i \in \{1, 2, \dots\}, \quad \mathbf{ui} \in \tau \quad \Rightarrow \quad \mathbf{u} \in \tau. $$

The set of rooted subtrees of $\mathbb{U}$ is denoted by $\mathbb{t}$ and we let $\mathbb{t}_n$ be the subset of rooted subtrees with $n$ vertices for $n \ge 1$.

<footnote n="2">²In this work we let $\mathbb{Z}_+ = \{0, 1, 2, \dots\}$ and $\mathbb{N} = \{1, 2, 3, \dots\}$.</footnote>
<figure><img src="image_5.png" /><figcaption>Figure 3: An illustration of the action of the mappings push and comp(d), here with d = 3. Notice that comp(d) preserves the order ⊆ while push does not.</figcaption></figure>

**Luczak and Winkler's couplings** For every $d \ge 2$, the infinite complete $d$-ary tree $U^{(d)}$ and its rooted subtrees can be viewed as subsets of $U$:

$$ U^{(d)} = \bigcup_{h \ge 0} \{1, 2, \dots, d\}^h, \quad \text{and} \quad t_n^{(d)} = \{\tau \in t_n : \tau \subset U^{(d)}\}, \quad n \ge 1. $$

The main result in [LW04], their Theorem 4.1, states that for $d \ge 2$, the distributions$^3$ **Unif**($t_n^{(d)}$), $n \ge 1$, admit a coupling $(\mathcal{T}_n)_{n \ge 1}$ which is an increasing process with respect to the inclusion order $\subseteq$. This also gives the existence of increasing couplings for some related models which we shall now review. A summary is presented in Table 1.

A plane tree $T$ is said to be a complete $d$-ary tree if every $u \in T$ has either $d$ or $0$ children in $T$. The set of complete $d$-ary trees with $nd + 1$ vertices, $n \ge 0$, is denoted by $\hat{\mathbb{T}}_{nd+1}^{(d)}$. The Luczak–Winkler couplings imply that the distributions **Unif**($\hat{\mathbb{T}}_{nd+1}^{(d)}$), $n \ge 0$, also admit a coupling as an increasing process, with respect to the inclusion order $\subseteq$. Indeed, given $\tau$ a rooted subtree with $n$ vertices, $n \ge 1$, of $U^{(d)}$, $d \ge 2$, we may define its completion $T = \text{comp}^{(d)}(\tau)$ by adding all the vertices $u_i$ for $u \in \tau$ and $i \in \{1, \dots, d\}$. This yields a complete $d$-ary tree with $nd+1$ vertices, and $\tau$ is recovered by removing all the leaves of $T$. It is easily seen that for $\mu = (1 - \frac{1}{d})\delta_0 + \frac{1}{d}\delta_d$ we have $\text{BGW}_{nd+1}^{\mu} = \text{Unif}(\hat{\mathbb{T}}_{nd+1}^{(d)})$ for all $n \ge 0$.

Rooted subtrees of $U$ naturally come with an associated plane tree.$^4$ In Neveu's formalism, this plane tree can be obtained by "pushing to the left" as much as possible the rooted subtree of $U$. This induces a mapping **push**: $t \to \mathbb{T}$, which we describe in detail in Section 5. Let $d \ge 2$. It is easily seen that the image of **Unif**($t_n^{(d)}$), $n \ge 1$, under this mapping is $\text{BGW}_n^\mu$ with $\mu = \text{Binom}(d, 1/d)$, see for instance Proposition 5.17. Hence the Luczak–Winkler coupling is mapped

<footnote>$^3$Given a finite set $S$, we denote by $\text{Unif}(S)$ the uniform probability distribution on it.</footnote>

<footnote>$^4$Rooted plane trees are often defined as unlabeled vertex-rooted trees, in the sense of graph theory, with an ordering of the children of each vertex. The plane tree associated to an arbitrary subtree of $U$ is then the one where we "forget" the names of the vertices, only remembering the relative ordering of the children of each vertex.</footnote>
<table><caption>Table 1: Summary of the models of random trees for which the results of [LW04] allow to build increasing couplings. The right-hand column specifies with respect to which order relation the resulting couplings are increasing. The second and third line describe the same model.</caption><thead><tr><th>PARAMETERS</th><th>MODEL</th><th>OFFSPRING DISTR.</th><th>ORDER REL.</th></tr></thead><tbody><tr><td>d ≥ 2</td><td>(Unif(t<sub>n</sub><sup>(d)</sup>))<sub>n≥1</sub></td><td>N/A</td><td>⊆</td></tr><tr><td>d ≥ 2</td><td>(Unif(T<sub>nd+1</sub><sup>(d)</sup>))<sub>n≥0</sub></td><td>N/A</td><td>⊆</td></tr><tr><td>d ≥ 2</td><td>(BGW<sub>nd+1</sub><sup>μ</sup>)<sub>n≥0</sub></td><td>μ = (1 - 1/d)δ<sub>0</sub> + 1/dδ<sub>d</sub></td><td>⊆</td></tr><tr><td>d ≥ 2, p ∈ (0, 1)</td><td>(BGW<sub>n</sub><sup>μ</sup>)<sub>n≥1</sub></td><td>μ = Binom(d, p)</td><td>⊂</td></tr><tr><td>λ > 0</td><td>(BGW<sub>n</sub><sup>μ</sup>)<sub>n≥1</sub></td><td>μ = Poisson(λ)</td><td>⊂</td></tr><tr><td>p ∈ (0, 1)</td><td>(BGW<sub>n</sub><sup>μ</sup>)<sub>n≥1</sub></td><td>μ = Geom(p)</td><td>⊆</td></tr></tbody></table>

to a coupling of these distributions. However, the image coupling is no longer increasing with respect to $\subseteq$, but only with respect to a weaker order $\preceq$ defined by $T \preceq T' \Leftrightarrow \exists \tau \subset \tau', T = \text{push}(\tau), T' = \text{push}(\tau')$.

It was observed by Lyons, Peled and Schramm in [LPS08] that by taking $d \to \infty$ in the preceding coupling of the distributions $(BGW_n^\mu)_{n \ge 1}$ with $\mu = \text{Binom}(d, 1/d)$, we get an $\preceq$-increasing$^5$ coupling in the $\mu = \text{Poisson}(1)$ case.

In the case $d = 2$, the above coupling for the distributions $(\text{Unif}(\hat{T}_{nd+1}^{(d)}))_{n \ge 0}$ is an $\subseteq$-increasing coupling for uniformly sampled complete binary trees with $n$ interior vertices respectively. By applying the so-called *rotation correspondence* between complete binary trees and plane trees, we obtain a coupling for uniformly random plane trees with $n$ vertices, $n \ge 1$, see also [LW04, p. 427]. This coupling is easily seen to be increasing with respect to $\subseteq$. Uniformly random plane trees with $n$ vertices are well-known to be distributed as $BGW_n^\mu$ with $\mu = \text{Geom}(1/2)$.

We recall that for every offspring distribution $\mu$, the laws $BGW_n^\mu$, $n \ge 1$, are unchanged by exponential tilting$^6$ of $\mu$. Hence the above couplings cover the cases $\text{Binom}(d, p)$, $\text{Poisson}(\lambda)$, $\text{Geom}(p)$ for any $d \ge 2$, $\lambda > 0$, $p \in (0, 1)$ instead of the specific values we gave.

**Janson's negative result** In [Jan06], Janson investigated several conditions related to the existence of increasing couplings for conditioned BGW trees. In particular, it is justified in Section 3 therein that if for $\varepsilon \in (0, 1)$ one considers the offspring distribution $\mu$ supported on $\{0, 1, 2\}$ such that

$$ \mu(0) = \frac{1 - \varepsilon}{2}, \quad \mu(1) = \varepsilon, \quad \mu(2) = \frac{1 - \varepsilon}{2}, \qquad (1.2) $$

then when $\varepsilon < 1/3$, the expected number of children of the root vertex is strictly larger under $BGW_3^\mu$ than under $BGW_4^\mu$. Hence, the distributions $(BGW_n^\mu)_{n \ge 1}$ cannot be coupled increasingly with respect to $\subseteq$ nor with respect to $\preceq$.

<footnote>$^5$The authors do not mention the order $\preceq$ or the operation $\text{push}$, simply because they do not use Neveu's formalism.</footnote>

<footnote>$^6$We recall that an *exponential tilt* of a probability distribution $\nu$ on $\mathbb{Z}_+$ is a probability distribution $\tilde{\nu}$ on $\mathbb{Z}_+$ of the form $\tilde{\nu}(k) = x^k \nu(k) / (\sum_j x^j \nu(j))$, $k \ge 0$ for some $x > 0$ such that $\sum_j x^j \nu(j) < \infty$.</footnote>
<figure><img src="image_6.png" /><figcaption>Figure 4: An example of an increasing sequence of rooted plane trees, as in Theorem 1. Observe that the new leaves at each step (in yellow) must be right-leaning. For convenience, we only represented a portion of the Ulam-Harris tree, namely the bottom part of its subset $\mathcal{U}^{(3)}$.</figcaption></figure>

## 1.2 Main results

Central to our results will be the notion of log-concavity, which has a rich history in combinatorics, algebra and geometry, see the classical surveys [Sta89, Bre89, Bre94], as well as the more recent ones [Brä15, Huh18]. A non-negative sequence $(x_i)_{i \ge 0}$ is said to be log-concave if the following conditions are satisfied.

1. The inequality $x_i^2 \ge x_{i-1}x_{i+1}$ holds for all $i \ge 1$.

2. It has no internal zeros. That is if $x_ix_j \ne 0$, $i < j$, then $x_ix_{i+1} \cdots x_j \ne 0$.

Some authors do not enforce the second condition when defining log-concavity, but we insist that it will be needed in our case. Convolutions of log-concave sequences are log-concave, as well as pointwise limits of log-concave sequences. Basic examples comprise binomial coefficients $\left(\binom{d}{k}\right)_{k \ge 0}$ with $d \ge 2$, geometric sequences $(q^k)_{k \ge 0}$ with $q > 0$, or the inverse factorials $(1/k!)_{k \ge 0}$. As another important example, if a polynomial with non-negative coefficients has only real roots then said coefficients are log-concave. This can be derived using the preservation under convolution, or using Newton's inequalities, which are recalled in Lemma 5.18.

**Main result on conditioned BGW trees** Note that if an offspring distribution $\mu$ has no internal zeros, and $0 < \mu(0) < 1$, then $\mu(1) > 0$. Hence for $n \ge 1$, the tree with $n$ vertices arranged in a line gets non-zero $\mu$-BGW weight and so does $T_n$. The distributions $(\textbf{BGW}_n^\mu)_{n \ge 1}$ are therefore well-defined. Our first main result goes as follows.

**Theorem 1.** Let $\mu$ be a probability measure on $\mathbb{Z}_+$ with $0 < \mu(0) < 1$. If the sequence $(\mu(k))_{k \ge 0}$ is log-concave, then the distributions $(\textbf{BGW}_n^\mu)_{n \ge 1}$ can be coupled as a Markov process $(T_n)_{n \ge 1}$ such that $T_1 \subset T_2 \subset T_3 \subset \dots$.

Let us make a few comments. First, notice that in the sequence $(T_n)_{n \ge 1}$, the new vertex $\mathbf{u} \in T_{n+1} \setminus T_n$ which is added at each step must be a *leaf*, which must be *right-leaning*, that is of the form $\mathbf{u} = \mathbf{v}\mathbf{i}$ with $i = k_v(T_n) + 1$, for some $\mathbf{v} \in T_n$. This is illustrated in Figure 4. Since a plane tree is completely determined by its genealogy together with the relative order of the children of each vertex, it is
sufficient on a drawing to represent this data, without representing the “ambient”
Ulam-Harris tree U. This is what we did to illustrate Theorem 1 in Figure 1.

The fact that in our coupling the new leaves are right-leaning allows a lot of flexibility to make new couplings out of it. For instance, using the symmetries of the BGW distributions, we can perform random independent permutations of the subtrees of descendants above each node, so as to obtain another coupling of the same conditioned BGW distributions, in which the new leaves are in a controlled position. This strategy underpins the proof of Theorem 3 below.

Theorem 1 covers notably the cases of binomial, Poisson, and geometric off-
spring distributions listed in Table 1. Indeed the binomial coefficients, the inverse
factorials, and the geometric sequences all form log-concave sequences. But since
log-concavity is preserved under convolution, Theorem 1 also applies to arbitrary
convolutions of these distributions, with different parameters. Note that Theo-
rem 1 is already a substantial improvement in the binomial and Poisson cases,
since the inclusion order ⊆ is stronger than the order ≲.

Let us mention another example, which is not<sup>7</sup> a convolution of binomial, Poisson, or geometric distributions. The measure $\mu = \text{Unif}(\{0, 1, 2, \dots, d\})$, $d \ge 2$, satisfies the log-concavity assumption, so that Theorem 1 applies to the corresponding sequence of conditioned BGW trees, which are uniformly distributed in the set of plane trees with $n$ vertices having at most $d$ children per node.

Lastly, let us insist on the fact that in our definition of log-concavity the condi-
tion of having no internal zeros is essential. In fact, the conclusion of Theorem 1
never holds when the sequence $(\mu(k))_{k \ge 0}$ possesses an internal zero.<fnref n="8" />

In the case where the support of $\mu$ is included in $\{0, d, 2d, \dots\}$ for some $d \ge 2$, it is trivial that the conclusions of Theorem 1 do not hold since the conditioned $\mu$-BGW measures are not well-defined when $n$ has residue different from 1 modulo $d$, see below. Still, we can adapt our approach and the statement of Theorem 1 in this setting, which leads us to our next result.

**Extension to arithmetic offspring distributions** Let $\mu$ be a probability distribution on $\mathbb{Z}_+$ whose support is included in the arithmetic progression $d\mathbb{Z}_+ = \{0, d, 2d, \dots\}$ for some $d \ge 2$, and with $0 < \mu(0) < 1$. Then the $\mu$-BGW measure is still well-defined, but the conditional distribution $\text{BGW}_n^\mu$ may only be possibly defined when $n$ has residue 1 modulo $d$. Indeed if for $T \in \text{T}_n$, $n \ge 1$, all vertices in $T$ have a number of children which is a multiple of $d$, then the $n-1$ non-root vertices can be split in groups of $d$ vertices.

If the sequence $(\mu(kd))_{k \ge 0}$ has no internal zeros, then $\text{T}_{nd+1}$ does indeed get non-zero weight for all $n \ge 0$, so that the conditional distribution $(\text{BGW}_{nd+1}^\mu)_{n \ge 0}$ are well-defined. Our generalization of Theorem 1 in the arithmetic case goes as follows.

<footnote n="7"><sup>7</sup>This is easily seen at the level of generating functions, say by looking at their complex roots.</footnote>

<footnote n="8">⁸Indeed, let (T_n)_{n≥1} be as in the conclusion of Theorem 1 and let k ∈ supp(μ). Then T_{k+1} is with non-zero probability the “k-star” {Ø} ∪ {(1), (2), ..., (k)}. This forces T_{j+1} to be a j-star for 0 ≤ j ≤ k, so that kØ(T_{j+1}) = j with non-zero probability and j ∈ supp(μ).</footnote>
<figure><img src="image_7.png" /><figcaption>Figure 5: An example of an increasing sequence of rooted plane trees as obtained in Theorem 2 with $d = 3$. Observe that at each step, a new right-leaning bouquet of $d$ leaves is added (in yellow). For convenience, we only represented a portion of the Ulam-Harris tree, namely the bottom part of its subset $\mathbb{U}^{(6)}$.</figcaption></figure>

**Theorem 2.** Let $\mu$ be a probability measure on $\mathbb{Z}_+$ with $0 < \mu(0) < 1$ and whose support is included in $d\mathbb{Z}_+$ for some $d \ge 1$. If the sequence $(\mu(kd))_{k \ge 0}$ is log-concave, then the distributions $(\text{BGW}_{nd+1}^\mu)_{n \ge 1}$ can be coupled as a Markov process $(T_{nd+1})_{n \ge 1}$ such that $T_1 \subset T_{d+1} \subset T_{2d+1} \subset \dots$.

For a rooted plane tree $T$ and an integer $d \ge 1$, we call right-leaning bouquet of $d$ leaves in $T$ a set of $d$ leaves which are siblings and which additionally are the $d$ rightmost vertices among their siblings. More formally, a right-leaning bouquet of $d$ leaves in $T$ is a family of leaves of $T$ which consists in the vertices $\mathbf{u}(k_{\mathbf{u}}(T) - (d-1))$ and $\mathbf{u}(k_{\mathbf{u}}(T) - (d-2))$ up to $\mathbf{u}(k_{\mathbf{u}}(T))$, for some $\mathbf{u} \in T$. Then, as for Theorem 1, a sequence of plane trees which is increasing with respect to $\subseteq$ must grow “on the right”, so that in the sequence $(T_{nd+1})_{n \ge 1}$ of Theorem 2, a new right-leaning bouquet of $d$ leaves is added at each step. This is illustrated in Figure 5.

Notice that the $d=1$ case of Theorem 2 corresponds precisely to Theorem 1. Theorem 2 applies notably when $\mu = \frac{d-1}{d}\delta_0 + \frac{1}{d}\delta_d$ for some $d \ge 2$, in which case for all $n \ge 0$ the tree $T_{nd+1}$ has the distribution of a uniformly sampled complete $d$-ary tree with $n$ interior vertices. This recovers Luczak and Winkler’s main result<fnref n="9" /> from [LW04], namely their Theorem 4.1.

Theorem 2 also applies for instance when $\mu = \text{Unif}(\{0, d, 2d, \dots, rd\})$ for some $r \ge 1$. In this case, for every $n \ge 0$, the distribution $\text{BGW}_{nd+1}^\mu$ is uniform in the set of plane trees with $nd+1$ vertices satisfying that the number of children of each node belongs to the arithmetic progression $\{0, d, 2d, \dots, rd\}$.

**Application to a model of random subtrees** As a testament to the flexibility we have to generate new couplings from those of Theorems 1 and 2, we shall construct increasing couplings for a natural *inhomogeneous* model of random subtrees of the Ulam-Harris tree $\mathbb{U}$. For background on models of random subtrees of a graph, we refer the reader to the recent survey of Fredes and Marckert [FM23] and references therein.

Let $\boldsymbol{\theta} = (\theta_1, \theta_2, \dots)$ be a non-negative sequence such that $0 < \sum_i \theta_i < \infty$. For

<footnote n="9">⁹We recall that their statement, which is about subtrees of $\mathbb{U}^{(d)}$, is equivalent to a statement for complete $d$-ary trees using the bijection $\text{comp}^{(d)}$ described above.</footnote>
a non-root<fnref n="10" /> vertex $\mathbf{u} \in \mathbb{U}$, we say that it is a vertex of type $i \in \{1, 2, \dots\}$ if it is the $i$-th child of its parent, that is $\mathbf{u} = \mathbf{v}i$ for some $\mathbf{v} \in \mathbb{U}$. For $i \in \{1, 2, \dots\}$ and $\tau \in \mathfrak{t}$, we let $V_i(\tau)$ denote the set of $\mathbf{u} \in \tau$ of type $i$, and we write $N_i(\tau) = \# V_i(\tau)$. For every $n \ge 1$, we define a measure $\mathbf{ST}_n^\theta$ on $\mathfrak{t}_n$ as follows:

$$ \forall \tau \in \mathfrak{t}_n, \quad \mathbf{ST}_n^\theta(\tau) = \frac{\prod_{i \ge 1} \theta_i^{N_i(\tau)}}{ST_n^\theta}, \qquad \mathbf{ST}_n^\theta = \sum_{\tau \in \mathfrak{t}_n} \prod_{i \ge 1} \theta_i^{N_i(\tau)}. \qquad (1.3) $$

Notice that for $d \ge 2$, if $\theta$ satisfies $\theta_i = 0$ for all $i > d$, then the supports of the distributions $\mathbf{ST}_n^\theta$, $n \ge 1$, are included in $\mathfrak{t}_n^{(d)}$ respectively, so that this yields a model of random subtrees of the complete $d$-ary tree $\mathbb{U}^{(d)}$. We will deduce from Theorem 1 the following statement.

**Theorem 3.** Let $\theta = (\theta_1, \theta_2, \dots)$ be a non-negative sequence such that $0 < \sum_i \theta_i < \infty$. The distributions $\mathbf{ST}_n^\theta$, $n \ge 1$, can be coupled as a Markov process $(\mathcal{T}_n)_{n \ge 1}$ such that $\mathcal{T}_1 \subset \mathcal{T}_2 \subset \mathcal{T}_3 \subset \dots \subset \mathbb{U}$.

Note that in Theorem 3, the new vertices at each step must be leaves, but which are not necessarily right-leaning. However, our construction will rely crucially on the fact that the couplings in Theorem 1 add leaves which are right-leaning.

In the case of the sequence $\theta = (1, 1, \dots, 1, 0, 0, \dots)$, where the first $d$ terms equal 1 and the others are zero, notice that for every $n \ge 1$, the distribution $\mathbf{ST}_n^\theta$ is uniform on the set $\mathfrak{t}_n^{(d)}$ of random subtrees with $n$ vertices of the complete $d$-ary tree $\mathbb{U}^{(d)}$. In particular, in the case of sequences of the form $\theta = (1, 1, \dots, 1, 0, 0, \dots)$, we recover [LW04, Theorem 4.1], that is the statement that uniformly random subtrees of $\mathbb{U}^{(d)}$ can be coupled increasingly.

Roughly, we will observe that the application push maps the distributions $\mathbf{ST}_n^\theta$, $n \ge 1$, onto some conditioned BGW distributions satisfying the log-concavity assumption in Theorem 1, which yields some coupling $(\mathcal{T}_n)_{n \ge 1}$. The core of the proof of Theorem 3 then consists in constructing an embedding of the plane trees $(\mathcal{T}_n)_{n \ge 1}$ into $\mathbb{U}$ such that their images form an increasing coupling of the distributions $\mathbf{ST}_n^\theta$, $n \ge 1$.

## 1.3 Perspectives

In light of our results, it is natural to ask whether a converse statement to our main theorem holds. Let $\mu$ be a probability distribution on $\mathbb{Z}_+$ with $0 < \mu(0) < 1$.

**Problem 1.** Suppose that there exists a coupling of the distributions $\text{BGW}_n^\mu$, $n \ge 1$, which is increasing with respect to $\subseteq$. Does this imply that the sequence $(\mu(k))_{k \ge 0}$ is log-concave?

Note that the answer to Problem 1 is positive when $\mu$ has support included in $\{0, 1, 2\}$. Indeed, by possibly performing an exponential tilt,<fnref n="11" /> we may assume

<footnote n="10">¹⁰We do not assign a type to the root vertex $\emptyset$.</footnote>

<footnote n="11">¹¹This leaves unchanged the corresponding conditioned BGW measures, and log-concavity of the sequence $(\mu(k))_{k \ge 0}$ is equivalent to log-concavity of its tilted version.</footnote>
that $\mu$ takes the form (1.2) for some $\varepsilon \in (0, 1)$. Then the $\varepsilon < 1/3$ regime, where no increasing couplings can exist by [Jan06], is exactly the regime where the sequence $(\mu(k))_{k \ge 0}$ fails to be log-concave. Problem 1 remains open otherwise.

In a different direction, it would be interesting to see if the statements of stochastic increase for infinite BGW trees in [LPS08, Bro14, Bro16], which were proved using the results of [LW04], hold beyond the geometric, binomial, and Poisson cases.

## 1.4 Organization of the paper

We consider in Section 2 a general model of random compositions of integers and the problem of coupling them in a suitable increasing way. Ultimately, we extract a set of inequalities whose satisfaction is sufficient to ensure that there exist such increasing couplings, see Corollary 2.9.

Sections 3 and 4 are then dedicated to the proof of Theorems 1 and 2, which are conveniently re-formulated in terms of *simply generated trees*, see Theorems 4 and 5.

In Section 3, we relate the model of random compositions studied in Section 2 to simply generated trees, and explain how to construct increasing couplings for them using the increasing couplings for random compositions. To complete the proof of Theorem 1, or equivalently Theorem 4, we show that the sufficient set of inequalities we alluded to above is satisfied in this setting, by proving an even stronger set of inequalities, see Proposition 3.8, which vastly generalizes Corollary 5.4 in [LW04].

Then, Section 4 generalizes the results of Sections 2 and 3 to the arithmetic case, in order to prove Theorem 2. The global approach is similar but the proof is more technical, and the set of inequalities we obtain in this setting has a more subtle structure, see Proposition 4.13.

Lastly, we apply our results by proving Theorem 3 in Section 5. Our approach is to relate bijectively rooted subtrees of $\mathbb{U}$ to some decorated plane trees. We can then “grow” the plane trees and their decorations separately. The last step consists in making the two “growths” match. This involves performing some decoration-dependent “shuffling operations”.

We collect in Appendix A some technical lemmas about these decoration-dependent “shuffling operations”, which may be of independent interest.

## Acknowledgments

The author would like to express his deep gratitude to Grégory Miermont for many discussions and helpful advice, and for his careful reading of several versions of this article.

This work has been carried for the most part at the ENS de Lyon (UMPA), and it has been finished at the Université Paris-Saclay (LMO) with support from SuPerGRandMa (ERC Consolidator Grant no 101087572).
## 2 Growing random compositions

We start by introducing a model of random compositions which is closely related to BGW trees, and we study a notion of increasing couplings for this model, which will be instrumental to our constructions of increasing couplings for conditioned BGW trees.

As is usual in probability theory, by standard extension theorems we may assume that we have at our disposal a sufficiently big probability space $(\Omega, \mathcal{F}, \mathbf{P})$, together with realizations on it of all the random variables we may need. Unless we expressly mention the probability distribution we are working with, our random variables will be defined on $(\Omega, \mathcal{F}, \mathbf{P})$.

### 2.1 The model

**Compositions of integers** A composition of an integer $n \ge 0$ is a word $c = n_1 \cdots n_r$ with $r \ge 0$ letters on the alphabet $\{1, 2, \dots\}$ such that $n_1 + \cdots + n_r = n$. The integers $(n_i)$ are called the parts of $c$, and we underline them when writing a composition in order to avoid possible confusions. We write $c \models n$ to mean that $c$ is a composition of $n$. By convention, the empty word $\emptyset$ is the only composition of the integer 0. The set of compositions of an integer $n \ge 0$ will be denoted by $\text{Comp}(n)$.

**Covering and order relations** We say that a composition $c$ is covered by a composition $c'$ and write $c \prec c'$ if we can obtain $c'$ from $c$ by either adding 1 to one of its parts or by adding a new part with value 1 on its right. More precisely, if $c = \underline{n_1} \cdots \underline{n_r}$ then $c'$ covers $c$ if it is either one of the following compositions

$$ (\underline{n_1} \cdots \underline{n_{i-1}} \underline{n_i} + 1 \underline{n_{i+1}} \cdots \underline{n_r}), $$

for some $i \in \{1, \dots, r\}$, or if it is the following composition

$$ \underline{n_1} \cdots \underline{n_r} \underline{1}. $$

Notice that if $c$ is a composition of $n \ge 0$, then a composition $c'$ which covers $c$ is a composition of $n+1$. The relation $\prec$ is extended by transitivity into a partial order $\preceq$ on the set of all compositions of integers.

**Weight pairs** A pair $(\mathbf{a}, \mathbf{b})$ where $\mathbf{a} = (a_0, a_1, \dots)$ and $\mathbf{b} = (b_1, b_2, \dots)$ are non-negative sequences will be called a *weight pair*. It is *non-degenerate* if

1. we have $a_0 a_1 > 0$ and the sequence $\mathbf{a}$ has no internal zeros, or equivalently its support is $\{\ell: 0 \le \ell \le r\}$ for some $r = r(\mathbf{a}) \in \{1, 2, \dots\} \cup \{\infty\}$; and,

2. the sequence $\mathbf{b}$ is positive, or equivalently its support is $\{1, 2, \dots\}$.
<figure><img src="image_8.png" /><figcaption>Figure 6: A graphical representation of the composition $c = \mathbf{4}\mathbf{1}\mathbf{2}\mathbf{5}\mathbf{3}$ as piles of square bricks. The parts of the composition are the numbers of bricks in each column.</figcaption></figure>

<figure><img src="image_9.png" /><figcaption>Figure 7: An example of how a sequence $C_0 \prec C_1 \prec C_2 \prec \dots$ may begin. At each step, the newly added brick is colored in yellow.</figcaption></figure>

<figure><img src="image_10.png" /><figcaption>Figure 8: An illustration of the action of $\text{proj}_1$ and $\text{proj}_{>1}$ on compositions.</figcaption></figure>
**Random compositions** Given a non-degenerate weight pair (a, b) and for every $n \ge 0$, we define a probability distribution on Comp($n$) by letting for $\underline{n_1} \dots \underline{n_r} \in \text{Comp}(n)$,

$$ \mathbf{P}_n^{\mathbf{a},\mathbf{b}}(\underline{n_1} \cdots \underline{n_r}) = \frac{a_r \cdot (b_{n_1} \cdots b_{n_r})}{Z_n^{\mathbf{a},\mathbf{b}}}, \quad Z_n^{\mathbf{a},\mathbf{b}} = \sum_{\substack{i \ge 0 \\ \underline{n_1} \cdots \underline{n_i} = n}} a_i \cdot (b_{n_1} \cdots b_{n_i}). \quad (2.1) $$

Consistently with the usual convention that an empty product equals 1, the case $n = 0$ reads

$$ \mathbf{P}_0^{\mathbf{a},\mathbf{b}}(\emptyset) = \frac{a_0}{Z_0^{\mathbf{a},\mathbf{b}}} = 1, \quad \text{where} \quad Z_0^{\mathbf{a},\mathbf{b}} = a_0. \quad (2.2) $$

Obviously $a_0$ plays no role in the definition of $\mathbf{P}_0^{\mathbf{a},\mathbf{b}}$, or of the $(\mathbf{P}_n^{\mathbf{a},\mathbf{b}})_{n \ge 1}$ for that matter, but having a consistently defined $n = 0$ case will allow for cleaner statements later on when some compositions we deal with may be empty, such as in Proposition 2.7. The assumption that $(\mathbf{a}, \mathbf{b})$ is non-degenerate ensures that $Z_n^{\mathbf{a},\mathbf{b}}$ is non-zero for every $n \ge 0$ so that the above probability distributions are well-defined.

**Remark 2.1.** The model of random compositions defined by (2.1) can be seen as a variant on a model of random allocation called the *balls-in-boxes* or *balls-in-bins* model, but where the number of boxes is also allowed to be random. We refer the reader to Janson's survey [Jan12, Sect. 11] for background on the model with a fixed number of boxes.

**Remark 2.2.** Another related model is Gnedin and Pitman's model of *exchangeable Gibbs partitions* [GP05]. The authors associate to these random partitions some random compositions, whose distributions have a similar structure as the ones we defined in (2.1), see [GP05, Def. 1].

Our aim is to find *admissible* weight pairs $(\mathbf{a}, \mathbf{b})$, in the following sense.

**Definition 2.3 (Admissibility).** A non-degenerate weight pair $(\mathbf{a}, \mathbf{b})$ will be called *admissible* if there exists a coupling of the random compositions $(C_n)_{n \ge 0}$ with distributions $(\mathbf{P}_n^{\mathbf{a},\mathbf{b}})_{n \ge 1}$ respectively, in such a way that

$$ C_0 \prec C_1 \prec C_2 \prec \dots \prec C_n \prec C_{n+1} \prec \dots $$

**Lemma 2.4.** *The set of admissible weight pairs is closed in the set of non-degenerate weight pairs equipped with the topology of pointwise convergence.*

*Proof.* Let $n \ge 0$ and let $A_n$ be the subset of Comp($n$) $\times$ Comp($n+1$) consisting of those pairs $(C, C')$ for which $C \prec C'$. The mapping which maps a probability measure $\mathbf{m}$ on Comp($n$) $\times$ Comp($n+1$) to the value $\mathbf{m}(A_n)$ is clearly continuous with respect to convergence in distribution since we work with finite spaces. Hence if we take $(\mathbf{a}_i, \mathbf{b}_i) \to_{i \to \infty} (\mathbf{a}, \mathbf{b})$ in a sequence $(C_n(\mathbf{a}_i, \mathbf{b}_i), C_{n+1}(\mathbf{a}_i, \mathbf{b}_i))_{i \ge 1}$ of $A_n$-supported couplings of the distributions $\mathbf{P}_n^{\mathbf{a}_i, \mathbf{b}_i}$ and $\mathbf{P}_{n+1}^{\mathbf{a}_i, \mathbf{b}_i}$, then any subsequential limit we may obtain is also supported in $A_n$. Such a subsequential limit exists by
compactness, and forms a coupling of $\mathbf{P}_n^{a,b}$ and $\mathbf{P}_{n+1}^{a,b}$ since the mappings $(\mathbf{a}, \mathbf{b}) \mapsto \mathbf{P}_n^{a,b}(c)$ and $(\mathbf{a}, \mathbf{b}) \mapsto \mathbf{P}_{n+1}^{a,b}(c)$ are continuous for every composition $c$ (as rational functions in the coordinates of $\mathbf{a}$ and $\mathbf{b}$, with non-vanishing$^{12}$ denominators). This holds for all $n \ge 0$, so that taking a limit $(\mathbf{a}_i, \mathbf{b}_i) \to_{i \to \infty} (\mathbf{a}, \mathbf{b})$ of admissible weight pairs inside the set of non-degenerate ones yields a weight pair $(\mathbf{a}, \mathbf{b})$ which is admissible. $\square$

## 2.2 Key lemma

It is well-known that two real variables $X$ and $Y$ can be coupled in such a way that $X \le Y$ if and only if their cumulative distribution functions $F_X: t \mapsto \mathbf{P}(X \le t)$ and $F_Y: t \mapsto \mathbf{P}(Y \le t)$ satisfy $F_X \ge F_Y$ on $\mathbb{R}$. The latter is clearly necessary. Conversely, denote by $F^{-1}$ the generalized inverse of a function $F: \mathbb{R} \to [0, 1]$, that is

$$F^{-1}: u \in [0, 1] \mapsto F^{-1}(u) = \inf\{t \in \mathbb{R}: F(t) \ge u\}.$$

Then assuming that $F_X \ge F_Y$ on $\mathbb{R}$, the coupling $(X', Y') = (F_X^{-1}(U), F_Y^{-1}(U))$ satisfies $X' \le Y'$, where $U$ is uniformly random in $[0, 1]$. If now $F_X \ge F_Y \ge F_{X+1}$, then for $u \in [0, 1]$,

$$\{t \in \mathbb{R}: F_X(t) > u\} \subset \{t \in \mathbb{R}: F_Y(t) > u\} \subset \{t \in \mathbb{R}: F_{X+1}(t) > u\},$$

and therefore by taking infima and observing that $F_{X+1}$ is $t \mapsto F_X(t-1)$, we get

$$X' \le Y' \le X' + 1.$$

The following lemma is equivalent to Lemma 3.1 in [LW04].

**Lemma 2.5 (Key lemma).** Let $n \ge 1$ and let $\mu_n$ and $\mu_{n+1}$ be two probability measures on $\{1, 2, \dots, n\}$ and $\{1, 2, \dots, n+1\}$ respectively. Assume that for $m = 1, \dots, n$ we have

$$\mu_{n+1}(m) \le \mu_n(m) \ge \mu_{n+1}(m+1). \qquad (2.3)$$

Then, there exists a coupling $(X_n, X_{n+1})$ of the probability measures $\mu_n$ and $\mu_{n+1}$ such that $X_{n+1} \in \{X_n, X_n+1\}$ almost surely.

*Proof.* Let $X_n$, resp. $X_{n+1}$, have distribution $\mu_n$, resp. $\mu_{n+1}$. By summing the first inequality in (2.3) for $m \le k$ and the second one for $m > k$ we get for $1 \le k \le n$,

$$F_{X_{n+1}}(k) \le F_{X_n}(k) \quad \text{and} \quad 1 - F_{X_n}(k) \ge 1 - F_{X_{n+1}}(k+1),$$

that is $F_{X_{n+1}}(k) \le F_{X_n}(k) \le F_{X_{n+1}}(k+1)$. Hence by the discussion above, the variables $X_n$ and $X_{n+1}$ can be coupled in such a way that $X_n \le X_{n+1} \le X_n + 1$, or equivalently $X_{n+1} \in \{X_n, X_n+1\}$ since $X_n$ and $X_{n+1}$ are integer-valued. $\square$

<footnote>$^{12}$To be precise, the denominators are non-vanishing on the set of non-degenerate weight pairs.</footnote>
**Corollary 2.6.** Let $(\mu_n)_{n \ge 1}$ be a sequence of probability measures with support included in $\{1, \dots, n\}$ respectively. If the inequalities (2.3) of Lemma 2.5 are satisfied for every $1 \le m \le n$, then there exists a coupling $(X_n)_{n \ge 1}$ of the measures $(\mu_n)_{n \ge 1}$ such that $X_{n+1} \in \{X_n, X_n+1\}$ for every $n$ almost surely.

*Proof.* For every $n \ge 1$, let $(X_n^{(n)}, X_{n+1}^{(n)})$ be a coupling of the distributions $\mu_n$ and $\mu_{n+1}$ given by Lemma 2.5, hence satisfying $X_{n+1}^{(n)} \in \{X_n^{(n)}, X_n^{(n)}+1\}$ almost surely. Let us denote by $p_n(x_n, x_{n+1})$ the probability that $X_{n+1}^{(n)} = x_{n+1}$ given $X_n^{(n)} = x_n$. This suffices to define a time-inhomogeneous Markov chain $(X_n)_{n \ge 1}$ started at $X_1 = 1$ and with transition probabilities

$$ \mathbf{P}(X_{n+1} = x_{n+1} | X_n = x_n) = p_n(x_n, x_{n+1}). $$

Then $(X_n)_{n \ge 1}$ is a coupling of the measures $(\mu_n)_{n \ge 1}$ such that $X_{n+1} \in \{X_n, X_n+1\}$ for every $n$ almost surely. $\square$

## 2.3 Admissibility and shifted a-weights

For a sequence $\mathbf{a} = (a_0, a_1, \dots)$ of non-negative numbers, we denote by $\mathbf{a}^+$ the same sequence shifted by one unit to the left, that is $(a_0^+, a_1^+, a_2^+, \dots) = (a_1, a_2, a_3, \dots)$. For a composition $c = \underline{n_1} \cdots \underline{n_r}$ of $n \ge 1$, we let

$$ \mathrm{proj}_1(c) = n_1 \in \{1, 2, \dots\} \quad \text{and} \quad \mathrm{proj}_{>1}(c) = \underline{n_2} \cdots \underline{n_r} \in \mathrm{Comp}(n - n_1). $$

**Proposition 2.7.** Let $(\mathbf{a}, \mathbf{b})$ be a non-degenerate weight pair, with $r(\mathbf{a}) \ge 2$ so that $(\mathbf{a}^+, \mathbf{b})$ is also non-degenerate. Let $C_n$ be a $\mathbf{P}_{n-X_n}^{\mathbf{a},\mathbf{b}}$-distributed random composition for some fixed $n \ge 1$. If we let $X_n = \mathrm{proj}_1(C_n)$ and $C'_n = \mathrm{proj}_{>1}(C_n)$, then $X_n$ has distribution given by

$$ \mathbf{P}(X_n = m) = \frac{b_m \cdot Z_{n-m}^{\mathbf{a}^+, \mathbf{b}}}{Z_n^{\mathbf{a}, \mathbf{b}}}, \quad m = 1, \dots, n, \qquad (2.4) $$

and conditionally on $X_n$, the composition $C'_n$ has distribution $\mathbf{P}_{n-X_n}^{\mathbf{a}^+, \mathbf{b}}$.

*Proof.* For $m = 1, \dots, n$ and a composition $c = \underline{n_1} \cdots \underline{n_i}$ in $\mathrm{Comp}(n-m)$, we have

$$ \mathbf{P}(X_n = m, C'_n = c) = \mathbf{P}(C_n = \underline{mc}) = \frac{a_{i+1} \cdot (b_m b_{n_1} \cdots b_{n_i})}{Z_n^{\mathbf{a}, \mathbf{b}}}. \qquad (2.5) $$

In particular, by summing over $c \models n-m$ we get

$$ \mathbf{P}(X_n = m) = \sum_{\substack{i \ge 0 \\ \underline{n_1} \cdots \underline{n_i} \models n-m}} \frac{a_{i+1} \cdot (b_m b_{n_1} \cdots b_{n_i})}{Z_n^{\mathbf{a}, \mathbf{b}}} = \frac{b_m \cdot Z_{n-m}^{\mathbf{a}^+, \mathbf{b}}}{Z_n^{\mathbf{a}, \mathbf{b}}}, $$

which is (2.4). Dividing (2.5) by the latter expression we get for $m = 1, \dots, n$ and $c = \underline{n_1} \cdots \underline{n_i}$ in $\mathrm{Comp}(n-m)$,

$$ \mathbf{P}(C'_n = c | X_n = m) = \frac{a_{i+1} \cdot (b_{n_1} \cdots b_{n_i})}{Z_{n-m}^{\mathbf{a}^+, \mathbf{b}}} = \mathbf{P}_{n-m}^{\mathbf{a}^+, \mathbf{b}}(c), $$

as claimed. Observe that the above expressions still hold when $n = m$, with the convention that an empty product evaluates to 1. $\square$
**Proposition 2.8.** Let $(\mathbf{a}, \mathbf{b})$ be a non-degenerate weight pair.

1. If $\mathbf{a} = (a_0, a_1, 0, 0, \dots)$ with $a_0, a_1 > 0$ then $(\mathbf{a}, \mathbf{b})$ is admissible.

2. If $(\mathbf{a}^+, \mathbf{b})$ is admissible and if the inequalities

$$ \frac{Z_{n+1-m}^{\mathbf{a}^+, \mathbf{b}}}{Z_{n-m}^{\mathbf{a}^+, \mathbf{b}}} \le \frac{Z_{n+1}^{\mathbf{a}, \mathbf{b}}}{Z_n^{\mathbf{a}, \mathbf{b}}} \ge \frac{b_{m+1}}{b_m}, \qquad (2.6) $$

are satisfied for $m = 1, \dots, n$, then $(\mathbf{a}, \mathbf{b})$ is admissible.

*Proof.* In the first case, the fact that $a_i = 0$ for $i \ge 2$ imposes that a sample of $\mathbf{P}_n^{\mathbf{a}, \mathbf{b}}$ is a composition of $n$ into one part, for every $n \ge 1$. There is only one such composition, namely the trivial composition $\underline{n}$. In particular $(\mathbf{a}, \mathbf{b})$ is trivially admissible in that case.

Let us now focus on the second case and assume that $(\mathbf{a}^+, \mathbf{b})$ is admissible and that the inequalities (2.6) are satisfied. We will leverage the basic observation that for two compositions $c$ and $c'$ we have the equivalence

$$ c \preceq c' \iff \mathrm{proj}_1(c) \le \mathrm{proj}_1(c') \quad \text{and} \quad \mathrm{proj}_{>1}(c) \preceq \mathrm{proj}_{>1}(c'). \qquad (2.7) $$

Since $(\mathbf{a}^+, \mathbf{b})$ is admissible, there exists a coupling $(C_n^+)$, of the probability distributions $(\mathbf{P}_n^{\mathbf{a}^+, \mathbf{b}})$, such that $C_0^+ \prec C_1^+ \prec \dots$. For $n \ge 1$, define the image measure $\mu_n = (\mathrm{proj}_1)_*(\mathbf{P}_n^{\mathbf{a}, \mathbf{b}})$. Then by (2.4) in Proposition 2.8, we have for $m = 1, \dots, n$,

$$ \mu_n(k) = \frac{b_m \cdot Z_{n-m}^{\mathbf{a}^+, \mathbf{b}}}{Z_n^{\mathbf{a}, \mathbf{b}}}. $$

The inequalities (2.6), which are assumed to hold, precisely tell that for all $1 \le m \le n$,

$$ \mu_{n+1}(m) \le \mu_n(m) \ge \mu_{n+1}(m+1). $$

Hence by Corollary 2.6, there exists a coupling $(X_n)_{n \ge 1}$ of the distributions $(\mu_n)_{n \ge 1}$ such that $X_{n+1} \in \{X_n, X_n + 1\}$ for every $n$ almost surely, which may and will take independent from the sequence $(C_n^+)_{n \ge 0}$. The fact that $X_{n+1} \in \{X_n, X_n + 1\}$ for every $n$ yields that $(n - X_n)_{n \ge 1}$ is non-decreasing so that by construction of the coupling $(C_n^+)_{n \ge 0}$ we have $C_{n-X_n}^+ \preceq C_{n+1-X_n+1}^+$ for every $n \ge 1$. For $n \ge 1$ we define the composition $C_n = \underline{X_n} C_{n-X_n}^+$. Then by (2.7) we have

$$ C_1 \preceq C_2 \preceq \dots $$

By Proposition 2.7, the sequence $(C_n)_{n \ge 1}$ is indeed a coupling of the distributions $(\mathbf{P}_n^{\mathbf{a}, \mathbf{b}})_{n \ge 1}$. If we finally add the deterministic composition $C_0 = \emptyset$, which trivially satisfies $C_0 \preceq C_1$, we obtain a coupling $(C_n)_{n \ge 0}$ of $(\mathbf{P}_n^{\mathbf{a}, \mathbf{b}})_{n \ge 0}$ such that $C_0 \preceq C_1 \preceq C_2 \preceq \dots$. Now notice that for every $n \ge 0$, if $c \in \mathrm{Comp}(n)$ and $c' \in \mathrm{Comp}(n+1)$ are such that $c \preceq c'$, then $c$ is actually covered by $c'$. Hence we actually have $C_0 \prec C_1 \prec C_2 \prec \dots$, and therefore $(\mathbf{a}, \mathbf{b})$ is admissible. $\square$
For $\ell$ in $\{0, \dots, r-1\}$, we denote by $\mathbf{a}^{+\ell}$ the sequence obtained by shifting $\ell$ times to the left the sequence $\mathbf{a}$, that is $(a_0^{+\ell}, a_1^{+\ell}, \dots) = (a_\ell, a_{\ell+1}, \dots)$.

**Corollary 2.9.** Let $(\mathbf{a}, \mathbf{b})$ be a non-degenerate weight pair and assume that $r = r(\mathbf{a})$ is finite. Assume that the following inequalities hold for all $n \ge 0$ and all $\ell \in \{0, \dots, r-1\}$,

$$ \frac{b_{n+1}}{b_n} \le \frac{Z_{n+1}^{\mathbf{a}^{+\ell}, \mathbf{b}}}{Z_n^{\mathbf{a}^{+\ell}, \mathbf{b}}} \le \frac{b_{n+2}}{b_{n+1}}, \qquad (2.8) $$

where we omit the ill-defined inequality on the left when $n=0$. Then $(\mathbf{a}, \mathbf{b})$ is admissible, as well as the pairs $(\mathbf{a}^{+\ell}, \mathbf{b})$ for $\ell=0, \dots, r-1$.

*Proof.* Since $\mathbf{a}^{+(r-1)} = (a_{r-1}, a_r, 0, 0, \dots)$ with $a_{r-1}a_r > 0$, the first case of Proposition 2.8 gives that $(\mathbf{a}^{+(r-1)}, \mathbf{b})$ is admissible. If $r=1$ we are done, so let us consider the case $r \ge 2$. Notice that for $n \ge 1$, the inequalities (2.8) start with $\frac{b_{n+1}}{b_n}$ and end with $\frac{b_{n+2}}{b_{n+1}}$, so that they can be chained as $n$ increases to relate the inequalities corresponding to different values of $n$ together. We read in the inequalities we obtain in this way that for $1 \le m \le n$ and $0 \le \ell \le r-2$,

$$ \frac{Z_{n+1-m}^{\mathbf{a}^{+(\ell+1)}, \mathbf{b}}}{Z_{n-m}^{\mathbf{a}^{+(\ell+1)}, \mathbf{b}}} \le \frac{b_{n+2-m}}{b_{n+1-m}} \le \frac{b_{n+1}}{b_n} \le \frac{Z_{n+1}^{\mathbf{a}^{+\ell}, \mathbf{b}}}{Z_n^{\mathbf{a}^{+\ell}, \mathbf{b}}} \quad \text{and} \quad \frac{Z_{n+1}^{\mathbf{a}^{+\ell}, \mathbf{b}}}{Z_n^{\mathbf{a}^{+\ell}, \mathbf{b}}} \ge \frac{b_{n+1}}{b_n} \ge \frac{b_{m+1}}{b_m}. $$

Since $(\mathbf{a}^{+(r-1)}, \mathbf{b})$ is admissible, the last displayed inequalities imply through repeated applications of Proposition 2.8 that $(\mathbf{a}^{+(r-2)}, \mathbf{b}), \dots, (\mathbf{a}^{+0}, \mathbf{b})$ are also admissible, as claimed. $\square$

# 3 Growing conditioned BGW trees I: the non-arithmetic case

## 3.1 Simply generated trees

For convenience we will use the framework of simply generated trees in the sense of Meir and Moon [MM78], see also Janson's survey [Jan12]. For $\mathbf{w} = (w_0, w_1, \dots)$ a non-negative sequence, we denote by $\omega$ the following function on trees, which we interpret as a $\sigma$-finite measure,

$$ \forall T \in \mathbb{T}, \quad \omega(T) = \prod_{u \in T} w_{k_u(T)}, \qquad (3.1) $$

where we recall that $k_u(T)$ denotes the number of children of a vertex $u$ in a plane tree $T$. The dependence in $\mathbf{w}$ is implicit in the notation $\omega$ but will always be clear from context. The distribution of the simply generated tree with $n$ vertices associated to the weight sequence $\mathbf{w}$ is defined for $n \ge 1$ by

$$ \forall T \in \mathbb{T}, \quad \mathbf{SG}_n^\mathbf{w}(T) = \frac{\omega(T)}{b_n^\mathbf{w}}, \quad \text{where} \quad \text{and} \quad b_n^\mathbf{w} = \sum_{T \in \mathbb{T}_n} \omega(T). \qquad (3.2) $$
This definition only makes sense when $b_n^w \neq 0$, which is the case for every $n \ge 1$ under the assumption that $w_0w_1 > 0$, since in this case the tree $T \in \mathbb{T}_n$ consisting of a single ancestral line with $n$ vertices has $\omega(T) > 0$. When $\mu$ is a probability distribution, the distribution $\mathbf{SG}_n^w$ corresponding to $\mathbf{w} = (\mu(i))_{i \ge 0}$ is precisely the conditioned Bienaymé–Galton–Watson distribution $\mathbf{BGW}_n^\mu$, for all $n \ge 1$ such that $b_n^w \neq 0$. Conversely, given a non-negative sequence $\mathbf{w}$ such that the power series $\sum_i x^i w_i$ has non-zero radius of convergence, there exist $a, b > 0$ such that the definition $\mu(i) = ab^i w_i$ for all $i \ge 0$ yields a probability distribution $\mu$ which satisfies $\mathbf{BGW}_n^\mu = \mathbf{SG}_n^w$ for all $n \ge 1$ such that $b_n^w \neq 0$. See [Jan12] for details.

In this context, Theorem 1 can be reformulated in the following way.

**Theorem 4.** Let $\mathbf{w} = (w_0, w_1, \dots)$ be a non-negative sequence with $w_0w_1 > 0$. If $\mathbf{w}$ is log-concave, then the random trees with respective distributions $(\mathbf{SG}_n^w)_{n \ge 1}$ can be realized as a Markov process $(\mathbb{T}_n)_{n \ge 1}$ in which at each step a right-leaning leaf is added.

This version may look stronger than Theorem 1 since simply generated trees generalize Bienaymé–Galton–Watson trees, but both versions are actually strictly equivalent. Indeed if $\mathbf{w}$ is log-concave, then $w_{n+1} \le w_n w_1 / w_0$ for all $n \ge 0$ so that the power series $\sum_i x^i w_i$ has non-zero radius of convergence. As mentioned above, this entails that there exist $a, b > 0$ such that setting $\mu(i) = ab^i w_i$ for all $i \ge 0$ defines a probability distribution $\mu$ which satisfies $\mathbf{BGW}_n^\mu = \mathbf{SG}_n^w$. But $\mu$ thus defined is log-concave and Theorem 1 applies. The remainder of Section 3 is devoted to proving Theorem 4 and thus equivalently Theorem 1.

## 3.2 Relationship with random compositions

For $n \ge 1$ and a tree $T \in \mathbb{T}_n$ whose root has $i = k_\emptyset(T) \ge 0$ children, we write $\varphi(T) = (T^{[1]}, \dots, T^{[i]})$ for the possibly empty collection where for $1 \le j \le i$, we denote by $T^{[j]}$ the subtree of descendants of the $j$-th child of the root from left to right, that is, in Neveu's formalism:

$$ \varphi(T) = (T^{[1]}, \dots, T^{[i]}), \quad T^{[j]} = \{u \in \mathbb{U} : ju \in T\}, \quad 1 \le j \le i, \quad i = k_{\emptyset}(T). $$

Note that the mapping $\varphi$ is a bijection whose inverse mapping associates to any finite sequence of plane trees $(T^1, \dots, T^i)$, $i \ge 0$, the plane tree

$$ \varphi^{-1}(T^1, \dots, T^i) = \{\emptyset\} \cup \bigcup_{1 \le j \le i} jT^j, $$

where $jV = \{ju: u \in V\}$ for every $j \ge 1$ and every $V \subset \mathbb{U}$. The preceding allows to associate to any plane tree $T$ a composition

$$ c(T) = \underline{n}_1 \cdots \underline{n}_i \quad \text{where} \quad n_j = \# T^{[j]}, \quad 1 \le j \le i. $$

Notice that $c(T)$ is a composition of $n-1$ since the sets $jT^{[j]}$, $1 \le j \le i$, partition the non-root vertices of $T$. Consistently, if $T$ is the tree with one vertex then $c(T) = \emptyset$ since in this case the collection $(T^{[1]}, \dots, T^{[i]})$ is empty.
**Proposition 3.1.** Let $\mathbf{w} = (w_0, w_1, \dots)$ be a non-negative sequence which has no internal zeros and such that $w_0 w_1 > 0$. Set $\mathbf{b} = (b_n^\mathbf{w})_{n \ge 1}$. Then $(\mathbf{w}, \mathbf{b})$ is a non-degenerate weight pair. For $n \ge 1$ we have $b_n^\mathbf{w} = Z_{n-1}^{\mathbf{w}, \mathbf{b}}$, and for $T \in \mathbb{T}_n$ if we write $c(T) = \underline{n}_1 \cdots \underline{n}_i$ and $\varphi(T) = (T^{[1]}, \dots, T^{[i]})$, then

$$ \mathbf{SG}_n^\mathbf{w}(T) = \mathbf{P}_{n-1}^{\mathbf{w},\mathbf{b}}(c(T)) \cdot (\mathbf{SG}_{n_1}^\mathbf{w}(T^{[1]}) \cdots \mathbf{SG}_{n_i}^\mathbf{w}(T^{[i]})) \quad (3.3) $$

*Proof.* Since $w_0 w_1 > 0$, the sequence $\mathbf{b}$ is positive as mentioned after (3.2). Since additionally $\mathbf{w}$ has no internal zeros, the weight pair $(\mathbf{w}, \mathbf{b})$ is indeed non-degenerate. Let $n \ge 1$ and let $T \in \mathbb{T}_n$ and $\varphi(T) = (T^{[1]}, \dots, T^{[i]})$. The vertices of $T$ may be partitioned into the root vertex (which has $i$ children) on the one hand, and on the other hand the elements of the sets $jT^{[j]}$, $1 \le j \le i$. Hence, by the product form (3.1) for $\omega(T)$, and the easy verification that for $1 \le j \le i$ we have $k_{ju}(T) = k_u(T^{[j]})$, we get:

$$ \omega(T) = w_i \cdot \omega(T^{[1]}) \cdots \omega(T^{[i]}). \quad (3.4) $$

In particular if $c(T) = \underline{n}_1 \cdots \underline{n}_i$ then by the definition (3.2), the latter rewrites as follows:

$$ \mathbf{SG}_n^\mathbf{w}(T) = \frac{w_i \cdot \omega(T^{[1]}) \cdots \omega(T^{[i]})}{b_n^\mathbf{w}} = \frac{w_i \cdot (b_{n_1}^\mathbf{w} \cdots b_{n_i}^\mathbf{w})}{b_n^\mathbf{w}} \cdot \mathbf{SG}_{n_1}^\mathbf{w}(T^{[1]}) \cdots \mathbf{SG}_{n_i}^\mathbf{w}(T^{[i]}), $$

and thus by using the definition of $\mathbf{P}_{n-1}^{\mathbf{w},\mathbf{b}}$ in (2.1),

$$ \mathbf{SG}_n^\mathbf{w}(T) = \frac{Z_{n-1}^{\mathbf{w},\mathbf{b}}}{b_n^\mathbf{w}} \cdot \mathbf{P}_{n-1}^{\mathbf{w},\mathbf{b}}(\underline{n}_1 \cdots \underline{n}_i) \cdot \mathbf{SG}_{n_1}^\mathbf{w}(T^{[1]}) \cdots \mathbf{SG}_{n_i}^\mathbf{w}(T^{[i]}). \quad (3.5) $$

Since the measures $(\mathbf{SG}_k^\mathbf{w})_{k \ge 1}$ are probability measures, we get for all $c \models n-1$, by summing over all $T \in \mathbb{T}_n$ such that $c(T) = c$,

$$ \mathbf{SG}_n^\mathbf{w}(\{T: c(T) = c\}) = \frac{Z_{n-1}^{\mathbf{w},\mathbf{b}}}{b_n^\mathbf{w}} \cdot \mathbf{P}_{n-1}^{\mathbf{w},\mathbf{b}}(c), $$

and by summing again on all $c \models n-1$ and using that $\mathbf{SG}_n^\mathbf{w}$ and $\mathbf{P}_{n-1}^{\mathbf{w},\mathbf{b}}$ are also probability measures we find $b_n^\mathbf{w} = Z_{n-1}^{\mathbf{w},\mathbf{b}}$, and (3.5) becomes (3.3). $\square$

The following proposition reduces the proof of Theorem 4 to verifying that $(\mathbf{w}, \mathbf{b})$ is an admissible weight pair. This is the counterpart in our setting to [LW04, Proposition 2.1].

**Proposition 3.2.** Let $\mathbf{w} = (w_0, w_1, \dots)$ be a non-negative sequence such that $w_0 w_1 > 0$ and let $\mathbf{b} = (b_n^\mathbf{w})_{n \ge 1}$. If $(\mathbf{w}, \mathbf{b})$ is an admissible weight pair then the random trees with respective distributions $(\mathbf{SG}_n^\mathbf{w})_{n \ge 1}$ can be realized as a Markov process $(T_n)_{n \ge 1}$ such that $T_1 \subset T_2 \subset T_3 \subset \dots$

*Proof.* Our Markov process is initialized at $T_1$ the deterministic tree with one vertex. We may now construct recursively the transition probabilities $p_n(T, T')$
for $n \ge 1$ and $(T, T') \in \mathbb{T}_n \times \mathbb{T}_{n+1}$. It is actually sufficient to construct $p_n(T, T')$ when $T$ and $T'$ are respectively in the supports of $\mathbf{SG}_n^w$ and $\mathbf{SG}_{n+1}^w$.

Let $n \ge 1$ and assume that $p_1, \dots, p_{n-1}$ have been constructed, so that we obtain a Markov process $(T_1, \dots, T_n)$ which is a coupling of $(\mathbf{SG}_m^w)_{1 \le m \le n}$ such that $T_1 \subset T_2 \subset \dots \subset T_n$. We take independent copies $(T_m^{(j)})_{1 \le m \le n}$ indexed by $j \ge 1$ of this coupling. By the assumption that $(\mathbf{w}, \mathbf{b})$ is an admissible weight pair, there exists a coupling $(C_n, C_{n+1})$ of the distributions $\mathbf{P}_n^{\mathbf{w}, \mathbf{b}}$ and $\mathbf{P}_{n+1}^{\mathbf{w}, \mathbf{b}}$ such that $C_n \prec C_{n+1}$. We choose such a coupling, independently of previously constructed random variables. We write $C_n = \underline{n}_1 \cdots \underline{n}_i$ and $C_{n+1} = \overline{n}'_1 \cdots \overline{n}'_{i'}$ and we set $T = \varphi^{-1}(T_{n_1}^{(1)}, \dots, T_{n_i}^{(i)})$ and $T' = \varphi^{-1}(T_{n_1}^{(1)}, \dots, T_{n_{i'}}^{(i')})$, that is more explicitly:

$$ T = \{\emptyset\} \cup \bigcup_{1 \le j \le i} j T_{n_j}^{(j)}, \qquad T' = \{\emptyset\} \cup \bigcup_{1 \le j \le i'} j T_{n_j}^{(j)}. \qquad (3.6) $$

Since $C_n \prec C_{n+1}$, we have $i \le i'$, as well as $n_j \le n'_j$ for every $1 \le j \le i$. This observation, combined with the fact that $(T_m^{(j)})_{1 \le m \le n}$ is increasing with respect to inclusion for every $j \ge 1$, gives that $T \subseteq T'$ using the expressions (3.6).

Hence, we constructed two random plane trees $T$ and $T'$ satisfying $T \subset T'$, and such that $T$ and $T'$ have respective distributions $\mathbf{SG}_n^w$ and $\mathbf{SG}_{n+1}^w$ by Proposition 3.1. To complete the inductive construction of the transition probabilities, it suffices to set $p_n(T, T') = \mathbf{P}(T' = T' | T = T)$ for all plane trees $T$ and $T'$ in the support of $\mathbf{SG}_n^w$ and $\mathbf{SG}_{n+1}^w$ respectively. $\square$

## 3.3 Log-concavity and the Toeplitz TP2 property

Proposition 3.3 below states the well-known fact that the Toeplitz matrix $(x_{i-j})_{i,j}$ of a log-concave sequence $(x_i)_i$ is totally positive of order two (TP2), which means that it has non-negative entries and that all its $2 \times 2$ minors are non-negative.

**Proposition 3.3.** Let $\mathbf{x} = (x_i)_{i \ge 0}$ be a non-negative sequence. If it is log-concave then we have

$$ \forall i \le i', \quad \forall j \le j', \quad x_{i-j}x_{i'-j'} \ge x_{i-j'}x_{i'-j}, $$

with the convention that $x_{-1} = x_{-2} = \dots = 0$.

*Proof.* Let $0 \le i < i'$ and $0 \le j < j'$. If $x_{i-j'}x_{i'-j} = 0$ then the inequality is trivial. Otherwise the support of $\mathbf{x}$ contains $\{i - j', i - j' + 1, \dots, i' - j\}$, since $\mathbf{x}$ has no internal zeros, even after extending with $x_{-1} = x_{-2} = \dots = 0$. For $\ell \in \{i, i+1, \dots, i'\}$ we have

$$ \frac{x_{\ell-j}}{x_{\ell-j'}} = \left( \frac{x_{\ell-j'+1}}{x_{\ell-j'+0}} \right) \cdot \left( \frac{x_{\ell-j'+2}}{x_{\ell-j'+1}} \right) \cdots \left( \frac{x_{\ell-j'+(j'-j)}}{x_{\ell-j'+(j'-j-1)}} \right). $$

Notice that all indices in the last display belong to $\{i-j', i-j'+1, \dots, i'-j\}$, hence the denominators are non-zero. By log-concavity of $\mathbf{x}$, each factor in the right-hand side is non-increasing in $\ell \in \{i, i+1, \dots, i'\}$. Hence we have $\frac{x_{i-j}}{x_{i-j'}} \ge \frac{x_{i'-j}}{x_{i'-j'}}$ since $i < i'$. $\square$
## 3.4 Checking the inequalities

Consider $\mathbf{w} = (w_0, w_1, \dots)$ a non-negative sequence with $w_0 w_1 > 0$. For $n, k \ge 1$, we denote by $\mathbb{F}_{n,k}$ the set of ordered forests $F = (T_1, \dots, T_k)$ made of $k$ plane trees $T_1, \dots, T_k$ having $n$ vertices in total, in the sense that $\sum_j \# T_j = n$. Given a forest $F = (T_1, \dots, T_k) \in \mathbb{F}_{n,k}$, we write $\omega(F) = \omega(T_1)\omega(T_2)\cdots\omega(T_k)$. Then, for $n, k \ge 1$, we may set

$$f_{n,k}^{\mathbf{w}} = \sum_{\underline{n}_1 \cdots \underline{n}_k = n} b_{n_1}^{\mathbf{w}} \cdots b_{n_k}^{\mathbf{w}} = \sum_{F \in \mathbb{F}_{n,k}} \omega(F). \quad (3.7)$$

Note in particular that $f_{n,k}^{\mathbf{w}} = 0$ when $k > n$.

**Lemma 3.4.** *The array $(f_{n,k}^{\mathbf{w}})_{n,k \ge 1}$ satisfies the recursion*

$$f_{n,k}^{\mathbf{w}} = \sum_{i \ge 0} w_i f_{n-1,k+i-1}^{\mathbf{w}}, \quad n, k \ge 2. \quad (3.8)$$

*Proof.* Let $n, k \ge 2$, and consider a forest of $k$ trees $F = (T_1, \dots, T_k)$ having $n$ vertices in total. Consider the forest $F' = (T_1^{[1]}, \dots, T_1^{[i]}, T_2, \dots, T_k)$, where $\varphi(T_1) = (T_1^{[1]}, \dots, T_1^{[i]})$ using the notation of section 3.2. As in (3.4), we get:

$$\begin{aligned} \omega(F) &= \omega(T_1)\omega(T_2)\cdots\omega(T_k) \\ &= w_i \cdot \omega(T^{[1]})\cdots\omega(T^{[i]})\omega(T_2)\cdots\omega(T_k) \\ &= w_i \cdot \omega(F'). \end{aligned}$$

The mapping $F \mapsto (i, F')$ is a bijection from $\mathbb{F}_{n,k}$ onto $\bigsqcup_{i \ge 0} \{i\} \times \mathbb{F}_{n-1,k+i-1}$, where the inverse mapping is $(i, T_1, \dots, T_{k+i-1}) \mapsto (\varphi^{-1}(T_1, \dots, T_i), T_{i+1}, \dots, T_{k+i-1})$. Therefore,

$$f_{n,k}^{\mathbf{w}} = \sum_{F \in \mathbb{F}_{n,k}} \omega(F) = \sum_{F' \in \mathbb{F}_{n-1,k+i-1}} w_i \cdot \omega(F') = \sum_{i \ge 0} w_i f_{n-1,k+i-1}^{\mathbf{w}},$$

which is the claimed recursion. $\square$

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

In the theory of total positivity and production matrices, the recursion (3.4) implies the following corollary, which is not new since it is a direct consequence of a result by Pétréolle, Sokal and Zhu [PSZ23, Theorem 9.15].

**Corollary 3.5.** *If $\mathbf{w}$ is log-concave, then the array $(f_{n,k}^{\mathbf{w}})_{n,k \ge 1}$ is TP2, that is*

$$\forall 1 \le n \le n', \quad \forall 1 \le k \le k', \quad f_{n,k}^{\mathbf{w}} f_{n',k'}^{\mathbf{w}} \ge f_{n,k'}^{\mathbf{w}} f_{n',k}^{\mathbf{w}}. \quad (3.9)$$

We choose to include a self-contained proof of a statement tailored to our needs, taking inspiration from the proof of [PSZ23, Theorems 9.4].
**Proposition 3.6.** Let $\mathbf{x} = (x_i)_{i \ge 0}$ be a non-negative sequence and let $(F_{n,k})_{n,k \ge 0}$ be an array of non-negative numbers such that $F_{n,k} = 0$ when $k > n$ and satisfying the following recursion, where we make the convention $F_{n,-1} = 0$ for all $n \ge 0$,

$$F_{n,k} = \sum_{i \ge 0} x_i F_{n-1,k+i-1}, \quad n \ge 1, \quad k \ge 0. \qquad (3.10)$$

If $\mathbf{x}$ is log-concave then the array $(F_{n,k})_{n,k \ge 0}$ is TP2, that is for every $0 \le n \le n'$ and every $0 \le k \le k'$ we have

$$F_{n,k} F_{n',k'} \ge F_{n,k'} F_{n',k}. \qquad (3.11)$$

*Proof.* First, in the case $n = 0$, we have $F_{n,k'} = 0$ for all $k' \ge 1$, so that the right-hand side of (3.11) is zero unless $k' = 0$, but then $k = k'$ and there is equality in (3.11). Let us now prove by induction on $N \ge 0$ the statement $\mathcal{H}_N$ that the inequalities (3.11) hold for all $0 \le n \le n' \le N$ and all $0 \le k \le k'$. The base case $N = 0$ follows from the preceding discussion. Consider now $N \ge 1$ and assume that $\mathcal{H}_{N-1}$ holds true. Let $1 \le n \le n' \le N$ and $0 \le k \le k'$. We extend the sequence $\mathbf{x}$ with $x_{-1} = x_{-2} = \dots = 0$. The sequence $(x_i)_{i \in \mathbb{Z}}$ thus obtained is still log-concave. Consider the following sum:

$$\sum_{i,i' \ge 0} (x_{i-k} x_{i'-k'} - x_{i-k'} x_{i'-k}) (F_{n-1,i-1} F_{n'-1,i'-1} - F_{n-1,i'-1} F_{n'-1,i-1}). \qquad (3.12)$$

By Proposition 3.3 and by the induction hypothesis $\mathcal{H}_{N-1}$, each term in the sum is a product of two factors which are both non-negative when $i \le i'$ and both non-positive when $i \ge i'$. As a consequence, the sum in (3.12) is non-negative, which means by expanding the products that

$$2 \left[ \sum_{i} x_{i-k} F_{n-1,i-1} \right] \left[ \sum_{i'} x_{i'-k'} F_{n'-1,i'-1} \right] \\ - 2 \left[ \sum_{i} x_{i-k'} F_{n-1,i-1} \right] \left[ \sum_{i'} x_{i-k} F_{n'-1,i'-1} \right] \ge 0,$$

where the sums run over $i \ge 0$ and $i' \ge 0$. By the recursion (3.10) this is equivalent to

$$F_{n,k} F_{n',k'} \ge F_{n,k'} F_{n',k}.$$

Hence inequality (3.11) holds when $1 \le n \le n' \le N$ and $0 \le k \le k'$, and it also holds in the case $n = 0$ by the discussion at the beginning of the proof. This concludes the inductive proof. $\square$

In particular, by Lemma 3.4, we can apply Proposition 3.6 to the array $(f_{n,k}^w)_{n,k \ge 1}$, which yields Corollary 3.5.
**Remark 3.7.** The results of Pétréolle, Sokal and Zhu in [PSZ23] are actually far more general than what we need here and deal with total positivity of arbitrary order, for combinatorially defined arrays related to lattice paths with height-dependent weights. Their theorem 10.15 is obtained using the theory of production matrices. Starting from a “production matrix”, one builds a so-called “output matrix”, and the construction has the property that the output matrix is totally positive of order $r \ge 2$, whenever the production matrix is. We refer the reader to [Kar68, pp. 132–134], [Pin09, Theorem 1.11] and [PSZ23, Theorems 9.4]. In this language, the recursion (3.10) says that $(F_{n,k})_{n,k \ge 0}$ is the output matrix with production matrix (a slight variant of) the Toeplitz matrix $(x_{i-j})_{i,j \ge 0}$ of $x$.

We are now in a position to show that the compositions defined in Proposition 3.1 satisfy the hypotheses of Corollary 2.9. We assumed that $w_0w_1 > 0$ at the beginning of this section, hence if additionally $w$ has no internal zeros then its support has the form $\{\ell: 0 \le \ell \le r\}$ for some $r = r(w) \in \{1, 2, \dots\} \cup \{\infty\}$. Write then $b = (b_n^w)_{n \ge 1}$ and for $\ell = 0, \dots, r-1$ let $w^{+\ell} = (w_{i+\ell})_{i \ge 0}$ be the $\ell$-th shift of $w$ to the left.

**Proposition 3.8.** Assume that $w$ is log-concave and that $r = r(w)$ is finite. Then the following holds for all $n \ge 0$,

$$ \frac{b_{n+1}^w}{b_n^w} = \frac{Z_{n+1}^{w^{+(r-1)},b}}{Z_n^{w^{+(r-1)},b}} \le \frac{Z_{n+1}^{w^{+(r-2)},b}}{Z_n^{w^{+(r-2)},b}} \le \dots \le \frac{Z_{n+1}^{w^{+1},b}}{Z_n^{w^{+1},b}} \le \frac{Z_{n+1}^{w^{+0},b}}{Z_n^{w^{+0},b}} = \frac{b_{n+2}^w}{b_{n+1}^w}, \quad (3.13) $$

where we omit the ill-defined equality on the left when $n = 0$.

*Proof.* Since $w^{+(r-1)} = (w_{r-1}, w_r, 0, 0, \dots)$, we have $Z_n^{w^{+(r-1)},b} = w_r \cdot b_n^w$ for $n \ge 1$, by the definition from (2.1). Therefore the equality on the left of (3.13) holds for all $n \ge 1$. Now by Proposition 3.1, we also have that $b_{n+1}^w = Z_n^{w,b}$ for all $n \ge 0$, which gives that the equality on the right of (3.13) also holds for all $n \ge 0$. Let us check the inequalities in (3.13) in the case $n = 0$. By definition from (2.1), they read

$$ \frac{w_r \cdot b_1^w}{w_{r-1}} \le \frac{w_{r-1} \cdot b_1^w}{w_{r-2}} \le \dots \le \frac{w_2 \cdot b_1^w}{w_1} \le \frac{w_1 \cdot b_1^w}{w_0}, $$

or equivalently $(w_i)^2 \ge w_{i-1}w_{i+1}$ for $1 \le i \le r-1$, which holds by log-concavity of $w$. We finally verify the inequalities in (3.13) when $n \ge 1$. Let $n \ge 1$ and consider, for some $\ell = 0, \dots, r-2$, the sum

$$ \sum_{i,j \ge 0} (w_{i+\ell+1} w_{j+\ell} - w_{i+\ell} w_{j+\ell+1}) (f_{n,i}^w f_{n+1,j}^w - f_{n+1,i}^w f_{n,j}^w). \quad (3.14) $$

By Proposition 3.3 and by Corollary 3.5, each term in the sum is a product of two factors which are both non-negative when $i \le j$ and both non-positive when $i \ge j$, as in the proof of Proposition 3.6. Thus the expression in (3.14) is non-negative, and by developing the products and using that by definition we have

$$ Z_n^{w^{+\ell},b} = \sum_{i \ge 0} w_{i+\ell} f_{n,i}^w \quad n \ge 1, \quad \ell \in \{0, \dots, r-1\}, $$
one obtains for $n \ge 1$ and $\ell = 0, \dots, r-2$ the inequality $Z_{n+1}^{\mathbf{w}^{+(\ell+1)},\mathbf{b}} Z_n^{\mathbf{w}^{+\ell},\mathbf{b}} \le Z_{n+1}^{\mathbf{w}^{+\ell},\mathbf{b}} Z_n^{\mathbf{w}^{+(\ell+1)},\mathbf{b}}$, which once re-written as

$$ \frac{Z_{n+1}^{\mathbf{w}^{+(\ell+1)},\mathbf{b}}}{Z_n^{\mathbf{w}^{+(\ell+1)},\mathbf{b}}} \le \frac{Z_{n+1}^{\mathbf{w}^{+\ell},\mathbf{b}}}{Z_n^{\mathbf{w}^{+\ell},\mathbf{b}}}, $$

are precisely the inequalities we need to conclude. $\square$

## 3.5 Proof of Theorems 1 and 4

We recall that Theorems 1 and 4 are equivalent, so that we only need to prove the latter. Let $\mathbf{w} = (w_0, w_1, \dots)$ be a non-negative log-concave sequence with $w_0 w_1 > 0$. By Proposition 3.2, it is sufficient to show that $(\mathbf{w}, \mathbf{b})$ is an admissible weight pair where $\mathbf{b} = (b_n^{\mathbf{w}})_{n \ge 0}$. If $\mathbf{w}$ has finite support, that is if $r(\mathbf{w}) < \infty$, then this follows from Proposition 3.8 and Corollary 2.9. Otherwise $\mathbf{w}$ is the pointwise limit $i \to \infty$ of the log-concave and finitely supported sequences $\mathbf{w}_i = (w_0, w_1, \dots w_i, 0, 0, \dots)$, $i \ge 1$, and we conclude by Lemma 2.4. $\square$

# 4 Growing conditioned BGW trees II: the arithmetic case

## 4.1 Random compositions with arithmetic conditions

**Arithmetic conditions on compositions** Let $d \ge 1$ and $s \in \{0, \dots, d-1\}$. For $n \ge 0$ and a composition $c = \underline{n}_1 \dots \underline{n}_i \models n$, we say that $c$ satisfies the $(d, s)$-arithmetic condition if its number $i$ of parts has residue $s$ modulo $d$, and if each of its parts $(n_j)_{1 \le j \le i}$ has residue $1$ modulo $d$. In this case we write $c \models_{d,s} n$ and we denote by $\text{Comp}_{d,s}(n)$ the set of such compositions. In particular for $n \ge 0$, the set $\text{Comp}_{d,s}(n)$ is non-empty if and only if $n$ has residue $s$ modulo $d$.

**Modified covering and order relations** Let $d \ge 1$. We say that a composition $c$ is $d$-covered by a composition $c'$ and write $c \prec^d c'$ if we can obtain $c'$ from $c$ by either incrementing by $d$ one of its parts or by adding $d$ new parts with value $1$ on its right. More precisely, if $c = \underline{n}_1 \cdots \underline{n}_r$ then $c'$ covers $c$ if it is either one of the following compositions

$$ (\underline{n}_1 \cdots \underline{n}_{i-1} \underline{n}_i + d \underline{n}_{i+1} \cdots \underline{n}_r), $$

for some $i \in \{1, \dots, r\}$, or if it is the following composition

$$ \underline{n}_1 \cdots \underline{n}_r \underbrace{\underline{1} \cdots \underline{1}}_{d \text{ times}}. $$

Notice that if $c \in \text{Comp}_{d,s}(n)$ for $n \ge 0$ with residue $s$ modulo $d$, then a composition $c'$ which $d$-covers $c$ also satisfies the $(d, s)$-arithmetic condition and thus is in $\text{Comp}_{d,s}(n+d)$. The relation $\prec^d$ is extended by transitivity into a partial order $\preceq^d$ on the set of all compositions of integers.
**Arithmetic conditions on weight pairs** Let $d \ge 1$ and let $s \in \{0, \dots, d-1\}$. A weight pair $(\mathbf{a}, \mathbf{b})$ will be called a $(d, s)$-non-degenerate weight pair if the following conditions hold.

1. The sequence $\mathbf{a}$ satisfies $a_s \neq 0$ and its support is an interval in $\{s, d+s, 2d+s, \dots\}$, not reduced to $\{0\}$ when $s=0$. More precisely its support is $\{\ell d + s: 0 \le \ell \le r\}$ for some $r = r_{d,s}(\mathbf{a}) \in \{0, 1, 2, \dots\} \cup \{+\infty\}$, with the requirement that $r_{d,s}(\mathbf{a}) \ge 1$ when $s=0$.

2. The sequence $\mathbf{b}$ has support $\{1, d+1, 2d+1, \dots\}$.

**Corresponding random compositions** Consider $d \ge 1$ and $s \in \{0, 1, \dots, d-1\}$, and let $(\mathbf{a}, \mathbf{b})$ be a $(d, s)$-non-degenerate weight pair. Consider as in the non-arithmetic case the partition function $Z_n^{\mathbf{a},\mathbf{b}}$ for every $n \ge 0$,

$$Z_n^{\mathbf{a},\mathbf{b}} = \sum_{\substack{i \ge 0 \\ \underline{n_1} \cdots \underline{n_i} = n}} a_i \cdot (b_{n_1} \cdots b_{n_i}). \qquad (4.1)$$

The $(d, s)$-non-degeneracy of $(\mathbf{a}, \mathbf{b})$ implies that compositions which do not satisfy the $(d, s)$-arithmetic condition do not contribute to the sum. Hence $n$ must have residue $s$ modulo $d$ for the last display to be non-zero. Conversely if $n$ has residue $s$ modulo $d$, then $Z_n^{\mathbf{a},\mathbf{b}} \neq 0$ since when $s \neq 0$ the composition $\underline{n} - (\underline{s}-1)\underline{1} \cdots \underline{1}$ (with $s-1$ parts $\underline{1}$ after the first part) contributes a non-zero term in the sum, while when $s=0$ the composition $\underline{n} - (\underline{d}-1)\underline{1} \cdots \underline{1}$ does. All in all, we have for all $n \ge 0$ and all $s' \in \{0, \dots, d-1\}$,

$$Z_{nd+s'}^{\mathbf{a},\mathbf{b}} \neq 0 \iff s' = s.$$

And in this case, for all $n \ge 0$ and all $\underline{n_1} \cdots \underline{n_i} \models_{d,s} (nd+s)$, we can define

$$\mathbf{P}_{nd+s}^{\mathbf{a},\mathbf{b}}(\underline{n_1} \cdots \underline{n_i}) = \frac{a_i \cdot (b_{n_1} \cdots b_{n_i})}{Z_{dn+s}^{\mathbf{a},\mathbf{b}}}, \qquad Z_{nd+s}^{\mathbf{a},\mathbf{b}} = \sum_{\substack{i \ge 0 \\ \underline{n_1} \cdots \underline{n_i} = d,s, n+s}} a_i \cdot (b_{n_1} \cdots b_{n_i}). \qquad (4.2)$$

Notice that the last sum runs over compositions satisfying the $(d, s)$-arithmetic condition. Observe, as in the non-arithmetic case that when $s=0$, the case $n=0$ is still well-defined if we make the convention that an empty product evaluates to 1.

**Definition 4.1 (Modified admissibility).** For $d \ge 1$ and $s \in \{0, 1, \dots, d-1\}$, we call $(d, s)$-admissible the $(d, s)$-non-degenerate weight pairs $(\mathbf{a}, \mathbf{b})$ for which the random compositions $(C_{nd+s})_{n \ge 0}$ with distributions $(\mathbf{P}_{nd+s}^{\mathbf{a},\mathbf{b}})_{n \ge 0}$ can be coupled in such a way that

$$C_s \prec^d C_{d+s} \prec^d C_{2d+s} \prec^d \dots \prec^d C_{nd+s} \prec^d C_{(n+1)d+s} \prec^d \dots$$

A counterpart of Lemma 2.4 then holds as follows.
<figure><img src="image_12.png" /><figcaption>Figure 9: A graphical representation of compositions satisfying respectively the (3,0), (3,1) and (3,2) arithmetic conditions, as piles of square bricks. These square bricks have been grouped by 3 except possibly the bottom left one, so that the arithmetic conditions are clearly visible. The parts of the composition are the numbers of *squares* in each column.</figcaption></figure>

<figure><img src="image_13.png" /><figcaption>Figure 10: An example of how of a sequence $C_2 \prec^3 C_5 \prec^3 C_8 \prec^3 \dots$ may begin. At each step, the newly added group of 3 bricks is colored in yellow.</figcaption></figure>

<figure><img src="image_14.png" /><figcaption>Figure 11: An illustration of the action of $\text{proj}_1$ and $\text{proj}_{>1}$ on compositions satisfying the (3, s)-arithmetic condition with $s \in \{0, 1, 2\}$. Notice how the value of s changes when applying $\text{proj}_{>1}$.</figcaption></figure>
**Proposition 4.2.** for $d \ge 1$ and $s \in \{0, \dots, d-1\}$, the set of $(d, s)$-admissible weight pairs is closed in the set of $(d, s)$-non-degenerate weight pairs equipped with the topology of pointwise convergence.

*Proof.* The proof of Lemma 2.4 adapts easily. □

## 4.2 Admissibility and shifted a-weights, revisited

We recycle from Section 2.3 the notation $\mathbf{a}^+$ for the sequence $\mathbf{a}$ shifted one unit to the left, $\mathrm{proj}_1(c)$ for the first part of a composition $c$, and $\mathrm{proj}_{>1}$ for the remaining parts, and we shall now provide adaptations of the results proved there. First, note that for $d \ge 1$ and $s \in \{0, \dots, d-1\}$, the application $\mathrm{proj}_1$ induces on each $\mathrm{Comp}_{d,s}(nd + s)$ for $n \ge 0$ an application

$$ \mathrm{proj}_1: \mathrm{Comp}_{d,s}(nd + s) \to \{1, d+1, 2d+1, \dots\}. $$

Also for $n \ge 1$ and a composition $\underline{n}_1 \dots \underline{n}_i \models_{d,s} (nd + s)$, if we write $n_1 = n'_1 d + 1$ then $\mathrm{proj}_{>1}(\underline{n}_1 \dots \underline{n}_i) = \underline{n}_2 \dots \underline{n}_i$ is an element of

$$ \left\{ \begin{array}{ll} \mathrm{Comp}_{d,s-1}((n-n'_1)d + (s-1)) & \text{if } s \neq 0, \\ \mathrm{Comp}_{d,d-1}((n-n'_1-1)d + (d-1)) & \text{if } s = 0, \end{array} \right. $$

as illustrated in Figure 11. Clearly, if $(\mathbf{a}, \mathbf{b})$ is a $(d, s)$-non-degenerate weight pair with $r_{d,s}(\mathbf{a}) \ge 1$ if $s \neq 0$ or $r_{d,s}(\mathbf{a}) \ge 2$ if $s = 0$, then $(\mathbf{a}^+, \mathbf{b})$ is $(d, \overline{s-1})$-non-degenerate, where we use for all $m \in \mathbb{Z}$ the notation $\overline{m}$ to designate the residue of $m$ modulo $d$, which is an element of $\{0, \dots, d-1\}$. Proposition 2.7 becomes the following.

**Proposition 4.3.** Let $d \ge 1$ and $s \in \{0, \dots, d-1\}$. Consider $(\mathbf{a}, \mathbf{b})$ a $(d, s)$-non-degenerate weight pair for which $(\mathbf{a}^+, \mathbf{b})$ is $(d, \overline{s-1})$-non-degenerate. Let $C_{nd+s}$ be a $\mathbf{P}_{nd+s}^{\mathbf{a},\mathbf{b}}$-distributed random composition for some fixed $n \ge 0$. If we let $X_{nd+s} = \mathrm{proj}_1(C_{nd+s})$ and $C'_{nd+s} = \mathrm{proj}_{>1}(C_{nd+s})$, then when $s \neq 0$ the variable $X_{nd+s}$ has distribution given by

$$ \mathbf{P}(X_{nd+s} = md + 1) = \frac{b_{md+1} \cdot Z_{(n-m)d+(s-1)}^{\mathbf{a}^{+},\mathbf{b}}}{Z_{nd+s}^{\mathbf{a},\mathbf{b}}}, \quad m = 1, \dots, n, \quad (4.3) $$

while when $s = 0$ the variable $X_{dn}$ has distribution given by

$$ \mathbf{P}(X_{dn} = md + 1) = \frac{b_{md+1} \cdot Z_{(n-m-1)d+(d-1)}^{\mathbf{a}^{+},\mathbf{b}}}{Z_{nd+s}^{\mathbf{a},\mathbf{b}}}, \quad m = 1, \dots, n-1, \quad (4.4) $$

Conditionally on $X_{nd+s}$, the composition $C'_{nd+s}$ has distribution $\mathbf{P}_{nd+s-X_n}^{\mathbf{a}^{+},\mathbf{b}}$.

*Proof.* The proof adapts *mutatis mutandi* from that of Proposition 2.7. □

Then, Proposition 2.8 is turned into the following.
**Proposition 4.4.** Let $d \ge 1$ and $s \in \{0, 1, \dots, d-1\}$. Let $(\mathbf{a}, \mathbf{b})$ be $a(d,s)$-non-degenerate weight pair. Then there holds the following.

1. (a) If $d = 1, s = 0$ and $r_{1,0}(\mathbf{a}) = 1$, that is if $\mathbf{a} = (a_0, a_1, 0, 0, \dots)$, then $(\mathbf{a}, \mathbf{b})$ is $(1, 0)$ admissible.

(b) If $d \ge 2, s = 1$ and $r_{d,s}(\mathbf{a}) = 0$, that is if $\mathbf{a} = (0, a_1, 0, 0, \dots)$, then $(\mathbf{a}, \mathbf{b})$ is $(d, 1)$-admissible.

2. (a) If $s \ne 0$ and the weight pair $(\mathbf{a}^+, \mathbf{b})$ is $(d, s-1)$-admissible and if the inequalities

$$ \frac{Z_{(n+1-m)d+(s-1)}^{\mathbf{a}^+, \mathbf{b}}}{Z_{(n-m)d+(s-1)}^{\mathbf{a}^+, \mathbf{b}}} \le \frac{Z_{(n+1)d+s}^{\mathbf{a}, \mathbf{b}}}{Z_{nd+s}^{\mathbf{a}, \mathbf{b}}} \ge \frac{b_{md+1}}{b_{(m-1)d+1}}, \quad (4.5) $$

are satisfied for $m = 1, \dots, n$, then $(\mathbf{a}, \mathbf{b})$ is $(d, s)$-admissible.

(b) If $s = 0$ and the weight pair $(\mathbf{a}^+, \mathbf{b})$ is $(d, d-1)$-admissible and if the inequalities

$$ \frac{Z_{(n+1-m-1)d+(d-1)}^{\mathbf{a}^+, \mathbf{b}}}{Z_{(n-m-1)d+(d-1)}^{\mathbf{a}^+, \mathbf{b}}} \le \frac{Z_{(n+1)d}}{Z_{dn}^{\mathbf{a}, \mathbf{b}}} \ge \frac{b_{md+1}}{b_{(m-1)d+1}}, \quad (4.6) $$

are satisfied for $m = 1, \dots, n-1$, then $(\mathbf{a}, \mathbf{b})$ is $(d, 0)$-admissible.

*Proof.* In cases 1.(a) and 1.(b), a sample of $P_{nd+s}^{\mathbf{a},\mathbf{b}}$ is a composition of $nd+s$ into one part for every $n \ge 0$, that is the trivial composition $nd+s$. Thus $(\mathbf{a}, \mathbf{b})$ is trivially admissible in that case, since at each step the first and only part of the composition gets an increment of $d$. Now for two compositions $c$ and $c'$ satisfying the $(d, s)$-arithmetic condition, we have the equivalence

$$ c \preceq^d c' \iff \mathrm{proj}_1(c) \le \mathrm{proj}_1(c') \quad \text{and} \quad \mathrm{proj}_{>1}(c) \preceq^d \mathrm{proj}_{>1}(c'). \quad (4.7) $$

This generalizes (2.7). The proof of the second case in Proposition 2.8 then adapts seamlessly to prove 2.(a) and 2.(b), using Proposition 4.4 instead of Proposition 2.8. $\square$

If $(\mathbf{a}, \mathbf{b})$ is a $(d, 0)$-non-degenerate weight pair with $d \ge 1$ and if we write $r = r_{d,0}(\mathbf{a})$, then we can consider for every $\ell \in \{0, \dots, rd-1\}$ the $\ell$-th shift of $\mathbf{a}$ to the left, which we notate $\mathbf{a}^{+\ell}$. For every $q$ in $\{0, \dots, r-1\}$ and $s \in \{0, \dots, d-1\}$, the weight pair $(\mathbf{a}^{+((qd+s))}, \mathbf{b})$ is then $(d, d-s)$-non-degenerate. Corollary 2.9 may be adapted as follows.

**Corollary 4.5.** Let $(\mathbf{a}, \mathbf{b})$ be $a(d, 0)$-non-degenerate weight pair with $d \ge 1$ and assume that $r = r_{d,0}(\mathbf{a})$ is finite. Assume that the following inequalities hold for all $n \ge 0$, all $q \le q'$ in $\{0, \dots, r-1\}$, and all $s \le s'$ in $\{0, \dots, d-1\}$,

$$ \frac{b_{nd+1}}{b_{(n-1)d+1}} \le \frac{Z_{nd+(d-s')}^{\mathbf{a}^{+(q'd+s')}, \mathbf{b}}}{Z_{(n-1)d+(d-s')}^{\mathbf{a}^{+(q'd+s')}, \mathbf{b}}} \le \frac{Z_{nd+(d-s)}^{\mathbf{a}^{+(qd+s)}, \mathbf{b}}}{Z_{(n-1)d+(d-s)}^{\mathbf{a}^{+(qd+s)}, \mathbf{b}}} \le \frac{b_{(n+1)d+1}}{b_{nd+1}}, \quad (4.8) $$
where we omit the ill-defined inequality on the left when $n = 0$. Then $(\mathbf{a}, \mathbf{b})$ is $(d, 0)$-admissible, and $(\mathbf{a}^{+(qd+s)}, \mathbf{b})$ is $(d, \overline{d-s})$-admissible for every $s \in \{0, \dots, d-1\}$ and $q \in \{0, \dots, r-1\}$.

**Proof.** The proof is almost the same as that of Corollary 2.9. That is, the first case of Proposition 4.4 proves that $(\mathbf{a}^{+((r-1)d+(d-1))}, \mathbf{b})$ is $(d, 1)$-admissible, and then one propagates admissibility to the weight pairs $(\mathbf{a}^{+\ell}, \mathbf{b})$ in descending order of $\ell = qd+s$ using the second case of Proposition 4.4 when $s \neq 0$ and the third case when $s = 0$. We let the reader check that by chaining the inequalities (4.8) as $n$ varies, just as in the proof of Corollary 2.9, we indeed have all necessary inequalities to apply Proposition 4.4 to the weight pairs $(\mathbf{a}^{+\ell}, \mathbf{b})$ for $\ell < (r-1)d + (d-1)$. $\square$

## 4.3 Simply generated trees in the arithmetic case

For $d \geq 1$ and $n \geq 0$, we let $\mathbb{T}_{nd+1}^{[d]}$ denote the set of rooted plane trees with $nd+1$ vertices in which all vertices have a number of children which is divisible by $d$, and $\mathbb{T}^{[d]} = \bigcup_{n \geq 0} \mathbb{T}_{nd+1}^{[d]}$. Such trees must indeed have a number of vertices whose residue modulo $d$ is 1 since one may partition their vertex sets into first the root vertex and then the set of all vertices which are children of some vertex, the latter set having cardinality a multiple of $d$. Conversely, any complete $d$-ary tree with $n \geq 0$ interior vertices is an element of $\mathbb{T}_{nd+1}^{[d]}$.

**Definition 4.6.** For $d \geq 1$, a non-negative sequence $\mathbf{w}$ whose support takes the form $\{\ell d: 0 \leq \ell \leq r\}$ for some $r = r_d(\mathbf{w}) \in \{1, 2, \dots\} \cup \{+\infty\}$ will be called a $d$-arithmetic sequence.

The corresponding simply generated tree distributions are then supported in $\mathbb{T}^{[d]}$ and given for $n \geq 0$ and $T \in \mathbb{T}_{nd+1}^{[d]}$ by

$$ \mathbf{SG}_{nd+1}^{\mathbf{w}}(T) = \frac{\omega(T)}{b_{dn+1}^{\mathbf{w}}}, \quad \text{where} \quad b_{nd+1}^{\mathbf{w}} = \sum_{T \in \mathbb{T}_{nd+1}^{[d]}} \omega(T), $$

where $\omega(T) = \prod_{u \in T} w_{ku}(T)$ for every $T \in \mathbb{T}$. Notice that the sum in the last display runs over $\mathbb{T}_{nd+1}^{[d]}$, since $\omega(T)$ may be non-zero only for $T \in \mathbb{T}_{nd+1}^{[d]}$, by $d$-arithmeticity of $\mathbf{w}$. The other terms of the sequence $(b_n^{\mathbf{w}})_{n \geq 0}$ are zero, that is

$$ b_{nd+s}^{\mathbf{w}} = 0 \quad \text{for} \quad n \geq 0, \ s \in \{0, \dots, d-1\} \setminus \{1\}. $$

In Section 3.1 we explained how Theorems 1 and 4 are equivalent. Similarly, Theorem 2 is equivalent to the following statement in terms of simply generated trees.

**Theorem 5.** Let $d \geq 1$ and let $\mathbf{w}$ be a non-negative $d$-arithmetic sequence with $w_0 w_d > 0$. $(w_0, w_d, w_{2d}, \dots)$ is log-concave, then the random trees with respective distributions $(\mathbf{SG}_{nd+1}^{\mathbf{w}})_{n \geq 0}$ can be realized as a Markov process $(T_{nd+1})_{n \geq 0}$ such that $T_1 \subset T_{d+1} \subset T_{2d+1} \subset \dots$.

The remainder of Section 4 is dedicated to proving Theorem 5, by providing suitable adaptations to the proof of Theorem 4.
## 4.4 Relationship with compositions satisfying arithmetic conditions

We recall from Section 3.2 some notation. For $n \ge 1$ and $T \in \mathbb{T}_n$ whose root has $i \ge 0$ children, $\varphi(T) = (T^{(1)}, \dots, T^{(i)})$ is the possibly empty collection where $T^{(j)} = \{u \in \mathbb{U}: ju \in T\}$ is the subtree of descendants of the $j$-th child of the root, $1 \le j \le i$. Recall also the definition of the composition $c(T) = \underline{n}_1 \cdots \underline{n}_i$ where $n_j = \#T^{(j)}$ for $1 \le j \le i$.

**Proposition 4.7.** Let $\mathbf{w}$ be a $d$-arithmetic weight sequence, $d \ge 1$, and let $\mathbf{b} = (b_n^\mathbf{w})_{n \ge 0}$. Then $(\mathbf{w}, \mathbf{b})$ is a $(d, 0)$-non-degenerate weight pair.

*Proof.* The sequence $(b_n^\mathbf{w})_{n \ge 0}$ has support included in $\{1, d+1, 2d+1, \dots\}$ from Section 4.3. Conversely, any complete $d$-ary tree with $n \ge 0$ interior vertices, and thus $nd+1$ vertices in total, gets non-zero $\omega$-weight since $w_0w_d > 0$. Thus the support of $\mathbf{b}$ is precisely $\{1, d+1, 2d+1, \dots\}$. Since additionally $\mathbf{w}$ has support $\{\ell d: 0 \le \ell \le r\}$ for some $r \in \{1, 2, \dots\} \cup \{+\infty\}$, we have that $(\mathbf{w}, \mathbf{b})$ is indeed a $(d, 0)$-non-degenerate weight pair. $\square$

**Proposition 4.8.** Under the assumptions of Proposition 4.7, we have for $n \ge 0$ the identity $b_{nd+1}^\mathbf{w} = Z_{nd}^{\mathbf{w}, \mathbf{b}}$, and for $T \in \mathbb{T}_{nd+1}^{[d]}$ if we write $c(T) = \underline{n}_1 \cdots \underline{n}_i$ and $\varphi(T) = (T^{[1]}, \dots, T^{[i]})$, then

$$ \mathbf{SG}_{nd+1}^{\mathbf{w}}(T) = \mathbf{P}_{n-1}^{\mathbf{w}, \mathbf{b}}(c(T)) \cdot (\mathbf{SG}_{n_1}^{\mathbf{w}}(T^{[1]}) \cdots \mathbf{SG}_{n_i}^{\mathbf{w}}(T^{[i]})). \quad (4.9) $$

*Proof.* The proof of Proposition 3.1 still works. $\square$

**Proposition 4.9.** Let $\mathbf{w}$ be a non-negative $d$-arithmetic sequence, $d \ge 1$, such that $w_0w_d > 0$ and let $\mathbf{b} = (b_n^\mathbf{w})_{n \ge 1}$. If the weight pair $(\mathbf{w}, \mathbf{b})$ is $(d, 0)$-admissible the random trees with respective distributions $(\mathbf{SG}_{nd+1}^\mathbf{w})_{n \ge 0}$ can be realized as a Markov process $(T_{nd+1})_{n \ge 0}$ in which at each step a right-leaning bouquet of $d$ leaves is added.

*Proof.* The proof of Proposition 3.2 adapts with appropriate adjustments. In particular, for $n \ge 0$ the compositions $C_n \prec C_{n+1}$ in the proof are now replaced by $C_{nd} \prec^d C_{(n+1)d}$ obtained by $(d, 0)$-admissibility of $(\mathbf{w}, \mathbf{b})$. $\square$

## 4.5 Checking the inequalities

Let $d \ge 1$ and fix $\mathbf{w} = (w_i)_{i \ge 0}$ a non-negative $d$-arithmetic sequence. The notation from Section 3.4 is imported and we additionally denote by $\mathbb{F}_{nd+s, kd+s}^{[d]}$ the set of forests containing $kd+s$ trees form $\mathbb{T}^{[d]}$, with $nd+s$ vertices in total. We have now for $s, \in \{0, \dots, d-1\}$ and for all $n, k \ge 0$,

$$ f_{nd+s, kd+s}^{\mathbf{w}} = \sum_{\underline{n}_1 \cdots \underline{n}_{kd+s} \models_{d,s} nd+s} b_{n_1}^{\mathbf{w}} \cdots b_{n_{kd+s}}^{\mathbf{w}} = \sum_{F \in \mathbb{F}_{nd+s, kd+s}^{[d]}} \omega(F), \quad (4.10) $$
and we also have $f_{nd+s,kd+s'}^w = 0$ for $s \neq s'$ in $\{0, \dots, d-1\}$. In order to lighten notation, for $s \in \{0, \dots, d-1\}$ and $n, k \ge 0$, we let

$$F_{n,k}^s = f_{nd+s,kd+s'}^w.$$

We let also $\mathbf{W} = (W_0, W_1, W_2, \dots) = (w_0, w_d, w_{2d}, \dots)$ be the sequence defined by $W_j = w_{jd}$ for all $j \ge 0$.

**Lemma 4.10.** The arrays $(F_{n,k}^s)_{n,k \ge 0}$ corresponding to adjacent values of $s \in \{0, \dots, d-1\}$ are linked by the following relations

$$F_{n,k}^s = \sum_{j \ge 0} W_j F_{n,k+j}^{s-1}, \quad n \ge 0, \ k \ge 0, \ s \in \{1, \dots, d-1\}, \quad (4.11)$$

$$F_{n,k}^0 = \sum_{j \ge 0} W_j F_{n-1,k+j-1}^{d-1}, \quad n \ge 1, \ k \ge 1 \quad s = 0. \quad (4.12)$$

*Proof.* These identities may be written

$$f_{nd+s,kd+s}^{\mathbf{w}} = \sum_{j \ge 0} w_{jd} f_{nd+(s-1),(k+j)d+(s-1)}^{\mathbf{w}}, \quad n \ge 0, \ k \ge 0, \ 1 \le s < d,$$

$$f_{nd,kd}^{\mathbf{w}} = \sum_{j \ge 0} w_{jd} f_{(n-1)d+(d-1),(k+j-1)d+(d-1)}^{\mathbf{w}}, \quad n \ge 1, \ k \ge 1 \quad s = 0.$$

Those correspond to (3.8) after taking into account that $\mathbf{w}$ is $d$-arithmetic. The proof of (3.8) adapts without change. $\square$

For $\ell \ge 1$ we denote by $\mathbf{W}^{*\ell} = (W_j^{*\ell})_{j \ge 0}$ the $\ell$-fold self-convolution of the sequence $\mathbf{W}$.

**Corollary 4.11.** For $s \in \{0, \dots, d-1\}$, the array $(F_{n,k}^s)_{n,k \ge 0}$ satisfies the recursion

$$F_{n,k}^s = \sum_{j \ge 0} W_j^{*d} F_{n-1,k+j-1}^s, \quad n, k \ge 1. \quad (4.13)$$

*Proof.* Let $s \in \{0, \dots, d-1\}$ and $n, k \ge 1$. By applying $s$ times the relation (4.11) then one time the relation (4.12) and finally the relation (4.11) another $d-s-1$ times, we get

$$F_{n,k}^s = \sum_{j \ge 0} W_j^{*s} F_{n,k+j}^0 = \sum_{j \ge 0} W_j^{*(s+1)} F_{n-1,k+j-1}^{d-1} = \sum_{j \ge 0} W_j^{*d} F_{n-1,k+j-1}^{d-1-(d-s-1)},$$

which is precisely (4.13). $\square$

We may now adapt Corollary 3.5, in the form of the following proposition.

**Proposition 4.12.** Assume that $\mathbf{w}$ is $d$-arithmetic and that $\mathbf{W} = (w_0, w_d, w_{2d}, \dots)$ is a log-concave sequence. Then for all $s \in \{0, \dots, d-1\}$, we have

$$\forall 0 \le n < n', \quad \forall 0 \le k < k', \quad F_{n,k}^s F_{n',k'}^s \ge F_{n,k'}^s F_{n',k'}^s. \quad (4.14)$$
Proof. The sequence $\mathbf{W}^{*d}$ is log-concave since convolution preserves log-concavity. Hence the result follows from Corollary 4.11 and Proposition 3.6. $\square$

Let us introduce a bit of notation for readability. Assume that $\mathbf{w}$ is $d$-arithmetic and that $r = r_d(\mathbf{w})$ is finite, and write $\mathbf{b} = (b_n^\mathbf{w})_{n \ge 1}$. For every $\ell \in \{0, \dots, rd-1\}$, we let $\mathbf{w}^{+\ell}$ be the $\ell$-th shift of $\mathbf{w}$ to the left. For $q$ in $\{0, \dots, r-1\}$ and every $s \in \{0, \dots, d-1\}$, the weight pair $(\mathbf{w}^{+(qd+s)}, \mathbf{b})$ is then $(d, \overline{d-s})$-non-degenerate. We set for $n \ge 0$,

$$R_n(q, s) = \frac{Z_{nd+(d-s)}^{\mathbf{w}^{+(qd+s)}, \mathbf{b}}}{Z_{(n-1)d+(d-s)}^{\mathbf{w}^{+(qd+s)}, \mathbf{b}}}, \quad \begin{cases} q \in \{0, \dots, r-1\}, s \in \{0, \dots, d-1\} & \text{if } n \ge 1, \\ q \in \{0, \dots, r-1\}, s = 0 & \text{if } n = 0. \end{cases}$$

We can now provide a generalization of Proposition 3.8.

**Proposition 4.13.** Assume that $\mathbf{w}$ is $d$-arithmetic, that $\mathbf{W} = (w_0, w_d, w_{2d,\dots})$ is a log-concave sequence, and that $r = r_d(\mathbf{w})$ is finite. Then we have

$$\frac{b_{d+1}^{\mathbf{w}}}{b_1^{\mathbf{w}}} = R_0(0,0) \ge R_0(1,0) \ge \dots \ge R_0(r-1,0), \quad (4.15)$$

and for all $n \ge 1$, we have the following long chain of inequalities, where each line continues the preceding one,

$$\begin{aligned} & R_n(0,0) \ge R_n(1,0) \ge \dots \ge R_n(r-1,0) \\ \ge & R_n(0,1) \ge R_n(1,1) \ge \dots \ge R_n(r-1,1) \\ \vdots & \vdots \vdots \\ \ge & R_n(0,d-2) \ge R_n(1,d-2) \ge \dots \ge R_n(r-1,d-2) \\ \ge & R_n(0,d-1) \ge R_n(1,d-1) \ge \dots \ge R_n(r-1,d-1). \end{aligned}$$

The first and last term of this chain of inequalities read as follows:

$$R_n(0,0) = \frac{b_{(n+1)d+1}^{\mathbf{w}}}{b_{nd+1}^{\mathbf{w}}} \quad \text{and} \quad R_n(r-1,d-1) = \frac{b_{nd+1}^{\mathbf{w}}}{b_{(n-1)d+1}^{\mathbf{w}}}.$$

Before proceeding with the proof of Proposition 4.13, we will need the two following lemmas.

**Lemma 4.14.** For $n \ge 0$ we have the expressions

$$Z_{nd+(d-s)}^{\mathbf{w}^{+(qd+s)}, \mathbf{b}} = \sum_{i \ge 0} W_{i+q+1} F_{n,i}^{d-s}, \quad q \in \{0, \dots, r-1\}, \quad s \in \{1, \dots, d-1\}, \quad (4.16)$$

$$Z_{nd+(d-0)}^{\mathbf{w}^{+(qd+0)}, \mathbf{b}} = \sum_{i \ge 0} W_{i+q} F_{n+1,i}^{0}, \quad q \in \{0, \dots, r-1\}, \quad s = 0. \quad (4.17)$$

**Lemma 4.15.** For $n \ge 1$ we have the expressions

$$Z_{nd+(d-s)}^{\mathbf{w}^{+((r-1)d+s)}, \mathbf{b}} = W_r \sum_{i \ge 0} W_i F_{n,i}^{d-s-1}, \quad s \in \{0, \dots, d-1\}. \quad (4.18)$$
The proofs of Lemmas 4.14 and 4.15 are postponed to the end of this section.

**Proof of Proposition 4.13.** By Proposition 4.8, we have $b_{nd+1}^{\mathbf{w}} = Z_{nd}^{\mathbf{w},\mathbf{b}}$ for all $n \ge 0$. This yields the claimed identity for the first term of the sequence of inequalities,

$$R_n(0, 0) = \frac{b_{(n+1)d+1}^{\mathbf{w}}}{b_{nd+1}^{\mathbf{w}}}, \quad n \ge 0.$$

Now notice that $\mathbf{w}^{+((r-1)d+d-1)} = \mathbf{w}^{+(rd-1)}$ is of the form $(w_{rd-1}, w_{rd}, 0, 0, \dots)$ if $d=1$ or $(0, w_{rd}, 0, 0, \dots)$ if $d \ge 2$. Thus we have $Z_{(n-1)d+1}^{\mathbf{w}^{+(rd-1)},\mathbf{b}} = w_{dr} \cdot b_{(n-1)d+1}^{\mathbf{w}}$ for all $n \ge 1$ by definition in (4.2). Hence the claimed identity for the last term of the sequence of inequalities,

$$R_n(r-1, d-1) = \frac{b_{nd+1}^{\mathbf{w}}}{b_{(n-1)d+1}^{\mathbf{w}}}, \quad n \ge 1.$$

Now the inequalities in (4.15) correspond by definition to the inequalities

$$\frac{w_d \cdot b_1^{\mathbf{w}}}{w_0} \ge \frac{w_{2d} \cdot b_1^{\mathbf{w}}}{w_d} \ge \dots \ge \frac{w_{(r-1)d} \cdot b_1^{\mathbf{w}}}{w_{(r-2)d}} \ge \frac{w_{rd} \cdot b_1^{\mathbf{w}}}{w_{(r-1)d}},$$

which are equivalent to the statement that $\mathbf{W} = (w_0, w_d, w_{2d}, \dots)$ is log-concave. In order to conclude we are left with proving the following

1. The inequality $R_n(q, s) \ge R_n(q+1, s)$ for all $n \ge 1$, $q \in \{0, \dots, r-2\}$, and $s \in \{0, \dots, d-1\}$. Using Lemma 4.14, this reads as follows when $s \ne 0$,

$$\frac{\sum_{i \ge 0} W_{i+q+1} F_{n,i}^{d-s}}{\sum_{i \ge 0} W_{i+q+1} F_{n-1,i}^{d-s}} \ge \frac{\sum_{i \ge 0} W_{i+q+2} F_{n,i}^{d-s}}{\sum_{i \ge 0} W_{i+q+2} F_{n-1,i}^{d-s}}, \quad (4.19)$$

while when $s=0$ it reads

$$\frac{\sum_{i \ge 0} W_{i+q} F_{n+1,i}^{0}}{\sum_{i \ge 0} W_{i+q} F_{n+1,i}^{0}} \ge \frac{\sum_{i \ge 0} W_{i+q+1} F_{n+1,i}^{0}}{\sum_{i \ge 0} W_{i+q+1} F_{n+1,i}^{0}}, \quad (4.20)$$

2. The inequality $R_n(r-1, s) \ge R_n(0, s+1)$ for all $n \ge 1$ and all $s \in \{0, \dots, d-2\}$. Using Lemma 4.15 to express $R_n(r-1, s)$ and Lemma 4.14 to express $R_n(0, s+1)$, this reads

$$\frac{\sum_{i \ge 0} W_i F_{n,i}^{d-s-1}}{\sum_{i \ge 0} W_i F_{n-1,i}^{d-s-1}} \ge \frac{\sum_{i \ge 0} W_{i+1} F_{n,i}^{d-s-1}}{\sum_{i \ge 0} W_{i+1} F_{n-1,i}^{d-s-1}}, \quad (4.21)$$

The inequalities (4.19), (4.20) and (4.21) which we need to prove are all instances of the following inequalities

$$\frac{\sum_{i \ge 0} W_{i+q} F_{n,i}^{s}}{\sum_{i \ge 0} W_{i+q} F_{n-1,i}^{s}} \ge \frac{\sum_{i \ge 0} W_{i+q+1} F_{n,i}^{s}}{\sum_{i \ge 0} W_{i+q+1} F_{n-1,i}^{s}}, \quad n \ge 1, \ 0 \le q < r, \ 0 \le s < d. \quad (4.22)$$
The proof of these inequalities is similar to the proof of (3.13) in Proposition 3.8. Namely we can consider the expression

$$ \sum_{i,j \ge 0} (W_{i+q+1} W_{j+q} - W_{i+q} W_{j+q+1}) (F_{n-1,i}^s F_{n,j}^s - F_{n,i}^s F_{n-1,j}^s), $$

and then use Proposition 3.3 for the log-concave sequence $\mathbf{W} = (w_0, w_d, w_{2d}, \dots)$ as well as Proposition 4.12 for the array $(F_{n,k}^s)_{n,k \ge 0}$ to deduce as in the proof of Proposition 3.8 that this expression is non-negative. By developing the products we obtain the desired inequalities (4.22). $\square$

It remains to prove Lemmas 4.14 and 4.15.

*Proof of Lemma 4.14.* Let $n \ge 0$ and $\ell \in \{0, \dots, rd - 1\}$. By comparing the expressions (4.10) and (4.2) we see that

$$ Z_{nd+(d-s)}^{\mathbf{w}^{+\ell}, \mathbf{b}} = \sum_{i \ge 0} w_{i+\ell} f_{nd+(d-s),i}^{\mathbf{w}}. $$

Since $\mathbf{w}$ is $d$-arithmetic, the indices $i$ in the sum for which the corresponding term may be non-zero are those for which $i + \ell$ is a multiple of $d$. If $\ell = qd + s$ for some $q \in \{0, \dots, r-1\}$ and $s \in \{1, \dots, d-1\}$, then they have the form $i = i'd + (d-s)$ for some $i' \ge 0$, and we have

$$ Z_{nd+(d-s)}^{\mathbf{w}^{+(qd+s)}, \mathbf{b}} = \sum_{i \ge 0} w_{i+(qd+s)} f_{nd+(d-s),i}^{\mathbf{w}} = \sum_{i' \ge 0} w_{(i'+q+1)d} f_{nd+(d-s),i'd+(d-s)}, $$

which is precisely (4.16). If now $\ell = qd$ for some $q \in \{0, \dots, r-1\}$, then the aforementioned indices have the form $i = i'd$ for some $i' \ge 0$, and we have

$$ Z_{nd+d}^{\mathbf{w}^{+(qd)}, \mathbf{b}} = \sum_{i \ge 0} w_{i+qd} f_{nd+d,i}^{\mathbf{w}} = \sum_{i' \ge 0} w_{(i'+q)d} f_{(n+1)d,i'd}, $$

which gives (4.16). $\square$

*Proof of Lemma 4.15.* Let $n \ge 0$. We first treat the case $s \in \{1, \dots, d-1\}$. By definition of $r = r_d(\mathbf{w})$, the sequence $(W_{i+r})_{i \ge 0}$ has the form $(W_r, 0, 0, \dots)$ so that (4.16) becomes for $s \in \{1, \dots, d-1\}$,

$$ Z_{nd+(d-s)}^{\mathbf{w}^{+((r-1)d+s)}, \mathbf{b}} = \sum_{i \ge 0} W_{i+r} F_{n,i}^{d-s} = W_r F_{n,0}^{d-s}, $$

and we obtain (4.18) by applying (4.11) from Lemma 4.10. Similarly the sequence $(W_{i+r-1})_{i \ge 0}$ has the form $(W_{r-1}, W_r, 0, 0, \dots)$ so that (4.17) becomes for $s = 0$,

$$ Z_{nd+(d-0)}^{\mathbf{w}^{+(qd+0)}, \mathbf{b}} = \sum_{i \ge 0} W_{i+q} F_{n+1,i}^0 = W_{r-1} F_{n+1,0}^0 + W_r F_{n+1,1}^0 = W_r F_{n+1,1}, $$

where the last equality comes from the fact that $F_{n+1,0}^0 = 0$. We therefore obtain the $s = 0$ case of (4.18) by applying (4.12) from Lemma 4.10. $\square$
## 4.6 Proof of Theorems 2 and 5

Theorems 2 and 5 are equivalent, so let us prove the latter. The proof is similar to that of Theorem 4, but using our modified intermediary results. Let $d > 1$ and let $\mathbf{w}$ be a non-negative $d$-arithmetic sequence with $w_0 w_d > 0$ such that $\mathbf{W} = (w_0, w_d, w_{2d}, 0, 0, \dots)$ is log-concave. By Proposition 4.9, it is sufficient to show that $(\mathbf{w}, \mathbf{b})$ is a $(d, 0)$-admissible weight pair where $\mathbf{b} = (b_n^\mathbf{w})_{n \ge 0}$. If $\mathbf{w}$ has finite support, that is if $r_d(\mathbf{w}) < \infty$, then this follows from Proposition 4.13 and Corollary 4.5. Otherwise $\mathbf{w}$ is the pointwise limit $i \to \infty$ of the log-concave, $d$-arithmetic, and finitely supported sequences $w_i = (w_0, w_1, \dots w_i, 0, 0, \dots)$, $i \ge 1$, and we conclude by Proposition 4.2. □

# 5 Application to a model of random subtrees

Let us recall some of the definitions from the introduction. A *rooted subtree* of $\mathbb{U}$ is a non-empty finite subset $\tau$ of $\mathbb{U}$ such that:

$$ \forall u \in \mathbb{U}, \forall i \in \{1, 2, \dots\}, \quad \mathbf{u}_i \in \tau \quad \Longrightarrow \quad \mathbf{u} \in \tau. $$

We also recall that a *plane tree* is a rooted subtree $T$ of $\mathbb{U}$ such that:

$$ \forall u \in \mathbb{U}, \forall i \in \{1, 2, \dots\}, \quad \mathbf{u}_i \in T \quad \Longrightarrow \quad \mathbf{u}_j \in T, \quad 1 \le j \le i. $$

The set of *rooted subtrees* of $\mathbb{U}$, resp. the set of those having $n$ vertices, is denoted by $\mathfrak{t}$, resp. $\mathfrak{t}_n$, $n \ge 1$, while the set of *plane trees*, resp. the set of those having $n$ vertices, is denoted by $\mathfrak{T}$, resp. $\mathfrak{T}_n$, $n \ge 1$.

Lastly, let us recall the probabilistic model we introduced on rooted subtrees of $\mathbb{U}$. For $\theta = (\theta_1, \theta_2, \dots)$ a non-negative sequence such that $0 < \sum_i \theta_i < \infty$, and for $n \ge 1$, the measure $\mathbf{ST}_n^\theta$ on $\mathfrak{t}_n$ is defined as follows:

$$ \forall \tau \in \mathfrak{t}_n, \quad \mathbf{ST}_n^\theta(\tau) = \frac{\prod_{i \ge 1} \theta_i^{\#V_i(\tau)}}{ST_n^\theta}, \quad \mathbf{ST}_n^\theta = \sum_{\tau \in \mathfrak{T}_n} \prod_{i \ge 1} \theta_i^{\#V_i(\tau)}, \quad (5.1) $$

where we recall that $N_i(\tau) = \#V_i(\tau)$, where $V_i(\tau)$ is the set of vertices of type $i$ in $\tau$, that is those vertices $v \in \tau$ which have the form $v = \mathbf{u}_i$ for some $\mathbf{u} \in \mathbb{U}$.

## 5.1 Moving subtrees around

**Definition 5.1.** For $\tau \in \mathfrak{t}$ and a vertex $u \in \tau$, we define $C(\tau) = (C_u(\tau))_{u \in \tau}$ the collection of *children-positions*, where:

$$ C_u(\tau) = \{i \in \{1, 2, \dots\} : \mathbf{u}_i \in \tau\}, \quad \mathbf{u} \in \tau. $$

*Remark 5.2.* Notice that $\tau \in \mathfrak{t}$ is a *plane tree* if and only if for every $u \in \tau$, the set of *children-positions* $C_u(\tau)$ has the form $\{1, 2, \dots, k\}$ for some $k \ge 1$.
Now, if for every $\mathbf{u} \in \tau$ we are given an injective mapping $g_{\mathbf{u}}: C_{\mathbf{u}}(\tau) \to \{1, 2, \dots\}$, then we can “shuffle” $\tau$ using the collection $\mathbf{g} = (g_{\mathbf{u}})_{\mathbf{u} \in \tau}$ by “re-positioning” the children of each vertex $\mathbf{u}$ using $g_{\mathbf{u}}$. Let us formalize this idea.

For a finite subset $S \subset \{1, 2, \dots\}$, we denote by $\mathbb{G}_S$ the set of injective mappings $g: S \to \{1, 2, \dots\}$. We will use the notation:

$$ \mathbb{G} = \bigsqcup_{S \subset \{1, 2, \dots\}, |S| < \infty} \mathbb{G}_S. $$

For $\tau \in \mathbb{t}$, we denote by $\mathbb{G}(\tau)$ the set of collections $\mathbf{g} = (g_{\mathbf{u}})_{\mathbf{u} \in \tau}$ such that for all $\mathbf{u} \in \tau$ we have $g_{\mathbf{u}} \in \mathbb{G}_{C_{\mathbf{u}}(\tau)}$. In this setup, for $\tau \in \mathbb{t}$ and $\mathbf{g} \in \mathbb{G}(\tau)$, and for every $\mathbf{u} = (u_1, \dots, u_h) \in \tau$, with ancestral line $\mathbf{u}_i = (u_1, \dots, u_i)$, $0 \le i \le h$, we can define

$$ \mathbf{g} \cdot \mathbf{u} = (g_{\mathbf{u}_0}(u_1), g_{\mathbf{u}_1}(u_2), \dots, g_{\mathbf{u}_{h-1}}(u_h)). \quad (5.2) $$

It is easily verified that $\mathbf{g} \cdot \tau$ is a rooted subtree of $\mathbb{U}$, where for $V \subseteq \tau$, we write $\mathbf{g} \cdot V = \{\mathbf{g} \cdot \mathbf{u}: \mathbf{u} \in V\}$.

For some finite $S \subset \{1, 2, \dots\}$ and some $g \in \mathbb{G}_S$, since $g$ is injective, it admits an inverse on its image, which we denote by $g^{-1}: g(S) \to \{1, 2, \dots\}$, thus forming an element of $\mathbb{G}_{g(S)} \subset \mathbb{G}$. Our first observation, in the following lemma, is that the “shuffling” operation we have defined is bijective, with an explicit inverse.

**Lemma 5.3.** For every $\tau \in \mathbb{t}$ and $\mathbf{g} \in \mathbb{G}(\tau)$, there exists a unique $\mathbf{g}^{-1} \in \mathbb{G}(\mathbf{g} \cdot \tau)$ such that $\mathbf{g}^{-1} \cdot (\mathbf{g} \cdot \mathbf{u}) = \mathbf{u}$ for all $\mathbf{u} \in \tau$, and $\mathbf{g} \cdot (\mathbf{g}^{-1} \cdot \mathbf{u}') = \mathbf{u}'$ for all $\mathbf{u}' \in \mathbf{g} \cdot \tau$.

*Proof.* Let $\tau \in \mathbb{t}$ and $\mathbf{g} = (g_{\mathbf{u}})_{\mathbf{u} \in \tau} \in \mathbb{G}(\tau)$. Let $\mathbf{u} = (u_1, \dots, u_h) \in \tau$ with ancestral line $\mathbf{u}_i = (u_1, \dots, u_i)$, $0 \le i \le h$, and form $\mathbf{u}' = \mathbf{g} \cdot \mathbf{u}$, that is $\mathbf{u}' = (u'_1, \dots, u'_h)$ with $u'_j = g_{\mathbf{u}_{j-1}}(u_j)$ for $1 \le j \le h$. Then $u_1 = g_{\mathbb{G}}^{-1}(u'_1)$ and by an immediate induction we have

$$ u_j = g_{\mathbf{u}_{j-1}}^{-1}(u'_j), \quad 1 \le j \le h. \quad (5.3) $$

Hence $\mathbf{u}$ is completely determined by $\mathbf{g}$ and $\mathbf{u}'$, and the last display tells that $\mathbf{u} = \mathbf{g}' \cdot \mathbf{u}'$ where $\mathbf{g}' = (g'_{v'})_{v' \in g \cdot \tau}$ is obtained by setting for every $\mathbf{v}' \in \mathbf{g} \cdot \tau$ the value $g'_{v'} = g_{\mathbf{v}}^{-1}$, where $\mathbf{v}$ is the only preimage of $\mathbf{v}'$ by $\mathbf{v} \mapsto \mathbf{g} \cdot \mathbf{v}$. Then $\mathbf{g}' \cdot (\mathbf{g} \cdot \mathbf{u}) = \mathbf{g}' \cdot \mathbf{u}' = \mathbf{u}$ for all $\mathbf{u} \in \tau$, and $\mathbf{g} \cdot (\mathbf{g}' \cdot \mathbf{u}') = \mathbf{g} \cdot \mathbf{u} = \mathbf{u}'$ for all $\mathbf{u}' \in \mathbf{g} \cdot \tau$. $\square$

*Remark 5.4.* The algebraic structure we obtain is that of a *groupoid*, which morally generalizes the notion of a group by lifting the restriction that all pairs of elements can be multiplied. In our case, the elements of the groupoid are the $\mathbf{g} \in \bigsqcup_{\tau \in \mathbb{t}} \mathbb{G}(\tau)$, which are all invertible, but which can only be multiplied with elements satisfying the natural compatibility conditions.

**The push-forward operation** For the remainder of this section, we fix some $\tau \in \mathbb{t}$. For any set $\mathcal{X}$ and for all $\mathbf{g} \in \mathbb{G}(\tau)$, Lemma 5.3 allows to define a mapping $\mathcal{X}^{\tau} \to \mathcal{X}^{g \cdot \tau}$ which to $\mathbf{x} = (x_{\mathbf{u}})_{\mathbf{u} \in \tau}$ associates its *push-forward* $\mathbf{g}_{*}\mathbf{x}$, defined as follows:

$$ \mathbf{g}_{*}\mathbf{x} = (x_{\mathbf{g}^{-1} \cdot \mathbf{u}'})_{\mathbf{u}' \in \mathbf{g} \cdot \tau}. \quad (5.4) $$
This definition of the push-forward also makes sense when $\mathbb{X} = \mathbb{G}$, and this actually allows to give a concise description of $\mathbf{g}^{-1}$ for $\mathbf{g} \in \mathbb{G}(\tau)$, as in Lemma 5.5 below. Given $\mathbf{g} \in \mathbb{G}(\tau)$, we let

$$ \bar{\mathbf{g}} = (g_u^{-1})_{u \in \tau}, $$

which belongs<fnref n="13" /> to the set $\mathbb{G}^{\tau}$, for every $\mathbf{g} \in \mathbb{G}(\tau)$. We collect here a series of easy but useful lemmas on this push-forward operation. The following lemma is a mere reformulation of the identity (5.3), while the next one follows from Lemma 5.3.

**Lemma 5.5.** For $\mathbf{g} \in \mathbb{G}(\tau)$, we have $\mathbf{g}^{-1} = \mathbf{g}_* \bar{\mathbf{g}}$.

**Lemma 5.6.** Given a set $\mathbb{X}$ and $\mathbf{g} \in \mathbb{G}(\tau)$, we have $\mathbf{g}_*^{-1}(\mathbf{g}_* \mathbf{x}) = \mathbf{x}$ for every $\mathbf{x} \in \mathbb{X}^{\tau}$ and $\mathbf{g}_*(\mathbf{g}_*^{-1} \mathbf{x}') = \mathbf{x}'$ for every $\mathbf{x}' \in \mathbb{X}^{\mathbf{g} \cdot \tau}$.

Next, we have a convenient description of the action of an element of $\mathbb{G}(\tau)$ on the sets of children-positions.

**Lemma 5.7.** For every $\mathbf{g} \in \mathbb{G}(\tau)$ and $\mathbf{u} \in \tau$, we have $C_{\mathbf{g}-\mathbf{u}}(\mathbf{g} \cdot \tau) = g_{\mathbf{u}}(C_{\mathbf{u}}(\tau))$ and in particular we have the identity $\# C_{\mathbf{g}-\mathbf{u}}(\mathbf{g} \cdot \tau) = \# C_{\mathbf{u}}(\tau)$.

*Proof.* It is easily verified from the definitions that given $\mathbf{u}, \mathbf{v} \in \tau$ and $i \in \{1, 2, \dots\}$, we have $\mathbf{v} = \mathbf{u}i$ if and only if $\mathbf{g} \cdot \mathbf{v} = (\mathbf{g} \cdot \mathbf{u})g_{\mathbf{u}}(i)$. Hence the first identity. The second follows since $g_{\mathbf{u}}$ is injective for every $\mathbf{u} \in \tau$. $\square$

Given two sets $\mathbb{X}$ and $\mathbb{Y}$, and some mapping $f: \mathbb{X} \to \mathbb{Y}$, we denote by $f(\mathbf{x})$ the pointwise evaluation of $f$ on $\mathbf{x} = (x_{\mathbf{u}})_{\mathbf{u} \in \tau} \in \mathbb{X}^{\tau}$, that is

$$ f(\mathbf{x}) = (f(x_{\mathbf{u}}))_{\mathbf{u} \in \tau}, $$

which is an element of $\mathbb{Y}^{\tau}$.

**Lemma 5.8.** Given two sets $\mathbb{X}$ and $\mathbb{Y}$, and a mapping $f: \mathbb{X} \to \mathbb{Y}$, we have the identity $\mathbf{g}_*(f(\mathbf{x})) = f(\mathbf{g}_* \mathbf{x})$ for every $\mathbf{x} \in \mathbb{X}^{\tau}$ and every $\mathbf{g} \in \mathbb{G}(\tau)$.

This follows from the observation that both sides of the identity consist of the collection $(f(x_{\mathbf{g}^{-1}, \mathbf{u}'}))_{\mathbf{u}' \in \mathbf{g} \cdot \tau}$, where $\mathbf{x} = (x_{\mathbf{u}})_{\mathbf{u} \in \tau}$. In particular, if we apply this with $f: \mathbb{G} \to \mathbb{G}$, $g \mapsto g^{-1}$, we obtain the following.

**Lemma 5.9.** For every $\mathbf{g}, \mathbf{h} \in \mathbb{G}(\tau)$, we have $\overline{(\mathbf{g}_* \mathbf{h})} = \mathbf{g}_* \overline{\mathbf{h}}$.

This concludes our series of lemmas on the push-forward operation.

<footnote n="13">¹³Note that $\bar{\mathbf{g}}$ is not necessarily an element of $\mathbb{G}(\tau)$. Indeed, for $\mathbf{u} \in \tau$ we have $g_u^{-1} \in \mathbb{G}_{g_u(C_u(\tau))}$, which is different from $\mathbb{G}_{C_u(\tau)}$ unless $g_u(C_u(\tau)) = C_u(\tau)$.</footnote>
## 5.2 A bijection with some decorated plane trees

Let $T \in \mathbb{T}$ and let $\mathcal{X}$ be a set. We call $T$-tuple of elements of $\mathcal{X}$ an element in the Cartesian product

$$ \mathcal{X}^T = \{(x_v)_{v \in T} : \forall v \in T, x_v \in \mathcal{X}\}. $$

**Definition 5.10.** An $\mathcal{X}$-decorated plane tree is a pair $(T, \boldsymbol{x})$ with $T \in \mathbb{T}$ and $\boldsymbol{x} = (x_v)_{v \in T} \in \mathcal{X}^T$. The set of $\mathcal{X}$-decorated plane trees $(T, \boldsymbol{x})$ such that $T \in \mathbb{T}_n$, $n \ge 1$, is denoted by $\mathbb{T}_n[\mathcal{X}]$, and we set $\mathbb{T}[\mathcal{X}] = \bigcup_{n \ge 1} \mathbb{T}_n[\mathcal{X}]$.

In practice, we often need the decorations to satisfy some compatibility conditions with respect to the degree of the vertex they are assigned to, in the following sense. We call graded set a set $\mathcal{X}$ with a decomposition as a disjoint union $\mathcal{X} = \bigsqcup_{k \ge 0} \mathcal{X}_k$, called the grading of $\mathcal{X}$, which will often be implicit. Then a $T$-tuple of elements of $\mathcal{X}$ is said to be grading-compatible if it belongs to

$$ \mathcal{X}_T = \{(x_v)_{v \in T} : \forall v \in T, x_v \in \mathcal{X}_{k_v(T)}\} \subset \mathcal{X}^T. $$

**Definition 5.11.** Let $\mathcal{X} = \bigsqcup_k \mathcal{X}_k$ be a graded set. An $\mathcal{X}$-decorated plane tree $(T, \boldsymbol{x})$ is said to be grading-compatible if $\boldsymbol{x} \in \mathcal{X}_T$. The set of grading-compatible $\mathcal{X}$-decorated plane trees is denoted by $\mathbb{T}^{\mathrm{gr}}[\mathcal{X}]$, and we set $\mathbb{T}^{\mathrm{gr}}[\mathcal{X}] = \bigcup_{n \ge 1} \mathbb{T}^{\mathrm{gr}}_n[\mathcal{X}]$.

We will be particularly interested in plane trees decorated by finite subsets of $\{1, 2, \dots\}$. Hence, let us consider the graded set of finite subsets of $\{1, 2, \dots\}$,

$$ \mathcal{S} = \bigsqcup_{k \ge 0} \mathcal{S}_k, $$

where $\mathcal{S}_k$ is the set of $k$-element subsets of $\{1, 2, \dots\}$, for every $k \ge 0$. For $S$ a finite subset of $\{1, 2, \dots\}$, we let $p_S \in \mathbb{G}_S$ be the unique (injective) non-decreasing mapping $p_S: S \to \{1, 2, \dots\}$ such that $p_S(S) = \{1, 2, \dots, |S|\}$. Morally, $p_S$ “pushes” the elements of $S$ as far to the left as possible, while the inverse mapping $p_S^{-1}: \{1, 2, \dots, |S|\} \to \{1, 2, \dots\}$ corresponds to listing the elements of $S$ from left to right. Then for $T \in \mathbb{T}$ and $\boldsymbol{S} = (S_u)_{u \in T} \in \mathcal{S}_T$, we set:

$$ p_S = (p_{S_u})_{u \in T}, \qquad (5.5) $$

that is $p_S$ is obtained from $\boldsymbol{S}$ by pointwise evaluation of the mapping $\mathcal{S} \to \mathbb{G}$ given by $S \mapsto p_S$. For $\tau \in \mathfrak{t}$, we will use the shorthand notation:

$$ \boldsymbol{p}_{\tau} = p_{C(\tau)}. \qquad (5.6) $$

**Enriching the mapping “push”** With the above notation, the mapping push which we alluded to in the introduction is simply push: $\tau \mapsto \boldsymbol{p}_{\tau} \cdot \tau$. It is indeed easily verified that push($\tau$) thus defined is a plane tree for every $\tau \in \mathfrak{t}$. In order to retrieve $\tau$ from push($\tau$), we need to keep the information given by the collection $\mathcal{C}(\tau)$, using the push-forward operation defined in (5.4). Hence we consider an “enriched” version of the mapping push, as follows:

$$ \mathfrak{P}: \tau \mapsto (\boldsymbol{p}_{\tau} \cdot \tau, (\boldsymbol{p}_{\tau})_* \mathcal{C}(\tau)). $$
**Lemma 5.12.** This defines a mapping $\mathfrak{P}: t \to \mathbb{T}^{\text{gr}}[S]$.

*Proof.* For $\tau \in t$, if we write $\mathfrak{P}(\tau) = (T, S)$ with $S = (S_u)_{u \in T}$, then we have $T = \text{push}(\tau) \in \mathbb{T}$. We need to justify that $S$ is grading-compatible. For $u \in T$, we have $S_u = C_{p_{\tau}^{-1} \cdot u}(\tau)$ by definition. Now by Lemma 5.7, we have the identity $\# C_{p_{\tau}^{-1} \cdot u}(\tau) = \# C_u(p_{\tau} \cdot \tau) = k_u(T)$. Wrapping up, for every $u \in T$ we have $\# S_u = k_u(T)$, so that $S_u \in S_{k_u(T)}$ and $S$ is indeed grading-compatible. $\square$

There is a natural candidate to be an inverse of the mapping $\mathfrak{P}$, namely the mapping $(T, S) \mapsto \overline{p_S} \cdot T$. This is verified by the following proposition.

**Proposition 5.13.** The mappings

$$ \mathfrak{P}: \left( \begin{array}{r@{\quad}c@{\quad}l@{\quad}r} t & \longrightarrow & \mathbb{T}^{\text{gr}}[S] & \\ \tau & \longmapsto & (\boldsymbol{p}_{\tau} \cdot \tau, (\boldsymbol{p}_{\tau})_* \boldsymbol{C}(\tau)) & \end{array} \right), \qquad \mathfrak{P}^{-1}: \left( \begin{array}{r@{\quad}c@{\quad}l@{\quad}r} \mathbb{T}^{\text{gr}}[S] & \longrightarrow & t & \\ (T, \boldsymbol{S}) & \longmapsto & \overline{p_{\boldsymbol{S}}} \cdot T & \end{array} \right), $$

are inverse of each other.

*Proof.* Let us temporarily write $\mathfrak{Q}: (T, S) \mapsto \overline{p_S} \cdot T$, and prove that it is indeed an inverse of $\mathfrak{P}$. For $\tau \in t$, if we write $\mathfrak{P}(\tau) = (T, S)$, then Lemma 5.8 applied to the mapping $S \to \mathbb{G}$, $S \mapsto p_S$ gives that:

$$ p_S = p_{(p_\tau)_* C(\tau)} = (p_\tau)_* (p_{C(\tau)}) \stackrel{(5.6)}{=} (p_\tau)_* p_\tau $$

In particular, using Lemmas 5.9 and 5.3, we have that $\overline{p_S} = (p_\tau)_* \overline{p_\tau} = p_\tau^{-1}$. Hence $\overline{p_S} \cdot T = p_\tau^{-1} \cdot T = \tau$, since $T = \overline{p_S} \cdot T$. Hence we have proven:

$$ \mathfrak{Q}(\mathfrak{P}(\tau)) = \tau, \quad \tau \in t. \qquad (5.7) $$

On the other hand, for $(T, S) \in \mathbb{T}^{\text{gr}}[S]$ with $S = (S_u)_{u \in T}$, if we set $\tau = \mathfrak{Q}(T, S)$, then for every $u \in T$, we have by Lemma 5.7 applied with $g = \overline{p_S} = (p_{S_u}^{-1})_{u \in T}$,

$$ C_{\overline{p_S} \cdot u}(\tau) = C_{\overline{p_S} \cdot u}(\overline{p_S} \cdot T) = p_{S_u}^{-1}(C_u(T)). $$

Now since $T$ is a plane tree, we necessarily have that $C_u(T) = \{1, 2, \dots, k_u(T)\}$. By definition, $p_{S_u}^{-1}$ is such that $p_{S_u}^{-1}(\{1, 2, \dots, |S_u|\}) = S_u$. Since $S$ is grading-compatible we have $|S_u| = k_u(T)$. The conclusion of these observations is that $p_{S_u}^{-1}(C_u(T)) = S_u$. Plugging this into the last display we have

$$ C_{\overline{p_S} \cdot u}(\tau) = S_u, \quad u \in T. $$

This expresses that $S = (\overline{p_S})_*^{-1}C(\tau)$, or equivalently $C(\tau) = (\overline{p_S})_*S$. Now, as above, we can apply Lemma 5.8 with the mapping $S \to \mathbb{G}$, $S \mapsto p_S$ to obtain the identity $p_{C(\tau)} = (\overline{p_S})_*^{-1}p_S$, that is $p_\tau = (\overline{p_S})^{-1}$ using the definition (5.6) and Lemma 5.3. Hence, $p_\tau \cdot \tau = (\overline{p_S})^{-1} \cdot \tau = T$, since $\tau = \overline{p_S} \cdot T$. Also, we have $(p_\tau)_*C(\tau) = (\overline{p_S})_*^{-1}C(\tau) = S$, since we justified that $C(\tau) = (\overline{p_S})_*S$. Wrapping up, we have $p_\tau \cdot \tau = T$ and $(p_\tau)_*C(\tau) = S$, so that we have proven:

$$ \mathfrak{P}(\mathfrak{Q}(T, S)) = (T, S), \quad (T, S) \in \mathbb{T}^{\text{gr}}[S]. \qquad (5.8) $$

The combination of (5.7) and (5.8) gives the desired result. $\square$

*Remark 5.14.* The mappings $\mathfrak{P}: t \to \mathbb{T}^{\text{gr}}[S]$ and $\mathfrak{P}^{-1}: \mathbb{T}^{\text{gr}}[S] \to t$ actually induce mappings $\mathfrak{P}: t_n \to \mathbb{T}_n^{\text{gr}}[S]$ and $\mathfrak{P}^{-1}: \mathbb{T}_n^{\text{gr}}[S] \to t_n$ respectively, for every $n \ge 1$. Indeed, if $\tau = p_S \cdot T$, then $\tau$ and $T$ must have the same number of vertices since $u \mapsto p_S \cdot u$ maps bijectively $T$ onto $\tau$.
## 5.3 Probabilistic consequences

**Definition 5.15.** We call a non-negative sequence $\theta = (\theta_1, \theta_2, \dots)$ such that $0 < \sum_i \theta_i < \infty$ a summable weight sequence, and the number of elements in the support of a summable weight sequence $\theta$ is denoted by $N_\theta \in \mathbb{N} \cup \{\infty\}$.

When $\theta$ is a summable weight sequence, in order to treat in a unified way the cases $N_\theta < \infty$ and $N_\theta = \infty$, we make the convention that “ $i \le N_\theta$ ” means “ $i$ is finite” and at most equal to $N_\theta$”.

**A model of random subsets** Let $\theta$ be a summable weight sequence. We denote by $e(\theta) = (e_0(\theta), e_1(\theta), e_2(\theta), \dots)$ the elementary symmetric functions evaluated at the coefficients of $\theta$, that is:

$$e_0(\theta) = 1 \quad \text{and} \quad e_k(\theta) = \sum_{1 \le i_1 < i_2 < \dots < i_k} \theta_{i_1} \theta_{i_2} \dots \theta_{i_k}, \quad k \ge 1.$$

Notice that for $k \ge 1$ we have $e_k(\theta) \le (\sum_i \theta_i)^k < \infty$, and also that $e_k(\theta) > 0$ when $0 \le k \le N_\theta$, while $e_k(\theta) = 0$ for every $k > N_\theta$. In particular, the sequence $e(\theta)$ has no internal zeros. There is a natural model of random subsets of $\{1, 2, \dots\}$ associated to $\theta$, which we define as follows. For$^{14}$ $0 \le k \le N_\theta$, the probability distribution $B_k^\theta$ on $S_k$ is defined by

$$B_k^\theta(S) = \frac{\prod_{i \in S} \theta_i}{e_k(\theta)}, \quad S \in S_k. \qquad (5.9)$$

In particular, $B_k^\theta$ is supported on finite subsets of the support of $\theta$.

**Remark 5.16.** The use of the letter $B$ in the notation $B_k^\theta$ is motivated by an alternative description of the corresponding probability distribution in terms of a Bernoulli vector, as follows. Consider independent random variables $(B_i)_{i \ge 1}$ with respective distributions $(\text{Ber}(\frac{\theta_i}{1+\theta_i}))_{i \ge 1}$. The function $i \mapsto B_i$ is the indicator function of a random finite subset $S(B_1, B_2, \dots) \subset \{1, 2, \dots\}$, and for $S \in \mathcal{S}$ we have $S(B_1, B_2, \dots) = S$ with probability $C \cdot \prod_{i \in S} \theta_i$, where $C$ is the constant $C = 1/\prod_i (1+\theta_i)$. Hence the conditional distribution of $S(B_1, B_2, \dots)$ given that it has $k$ elements is $B_k^\theta(dS)$, for every $0 \le k \le N_\theta$.

**Proposition 5.17.** Let $n \ge 1$ and let $\theta$ be a summable sequence. Fix some $\tau \in \mathbb{t}$ and $(T, S) \in \mathbb{T}_n^{\text{gr}}[\mathbb{S}]$ such that $\mathfrak{P}(\tau) = (T, S)$. If we write $S = (S_u)_{u \in T}$, then for every $n \ge 1$ the following identity holds:

$$\mathbf{S}T_n^\theta(\tau) = \mathbf{S}G_n^{e(\theta)}(T) \cdot \prod_{u \in T} \mathbf{B}_{k_u(T)}^\theta(S_u). \qquad (5.10)$$

*Proof.* By construction, for all $i \in \{1, 2, \dots\}$ we have

$$\#V_i(\tau) = \#\{u \in \tau : i \in C_{\tau}(u)\} = \#\{u \in T : i \in S_u\} = \sum_{u \in T} 1_{i \in S_u}.$$

<footnote>$^{14}$Recall our convention that when $N_\theta = \infty$, we only consider finite values of $k$.</footnote>
Hence we obtain

$$ \prod_{i \ge 1} \theta_i^{\#V_i(\tau)} = \prod_{i \ge 1} \prod_{u \in T} \theta_i^{\mathbb{1}_{\{i \in S_u\}}} = \prod_{u \in T} \prod_{i \in S_u} \theta_i, \qquad (5.11) $$

Now by Prop 5.13 and Remark 5.14, summing the left-hand side over $\tau \in t_n$ and summing the right-hand side over $(T, S) \in \mathbb{T}_n^{\text{gr}}[S]$ gives the same result. Hence,

$$ \sum_{\tau \in t_n} \prod_{i \ge 1} \theta_i^{\#V_i(\tau)} = \sum_{(T, (S_u)_{u \in T}) \in \mathbb{T}_n^{\text{gr}}[S]} \prod_{u \in T} \prod_{i \in S_u} \theta_i. $$

Using (1.3) and the definition of $\mathbb{T}_n^{\text{gr}}[S]$, we can re-write the last display as

$$ ST_n^{\theta} = \sum_{T \in \mathbb{T}_n} \sum_{\substack{(S_u)_{u \in T} \\ \forall u, S_u \in \mathbb{S}_{k_u(T)}}} \prod_{u \in T} \prod_{i \in S_u} \theta_i = \sum_{T \in \mathbb{T}_n} \prod_{u \in T} \left( \sum_{S_u \in \mathbb{S}_{k_u(T)}} \prod_{i \in S_u} \theta_i \right) = \sum_{T \in \mathbb{T}_n} \prod_{u \in T} e_{k_u(T)}. $$

But by the definition (3.2), the right-hand side is none other than $b_n^{e(\theta)}$. Hence we have proved that $ST_n^{\theta} = b_n^{e(\theta)}$.

We now return to (5.11), for some fixed $\tau \in t_n$ and $(T, S) \in \mathbb{T}_n^{\text{gr}}[S]$. Suppose first that $k_u(T) \le N_\theta$ for all $u \in T$. In this case, we can factor in the right-hand side of (5.11) by $e_{k_u(T)} \ne 0$ to get

$$ \prod_{i \ge 1} \theta_i^{\#V_i(\tau)} = \prod_{u \in T} \prod_{i \in S_u} \theta_i = \prod_{u \in T} e_{k_u(T)} \cdot \mathbf{B}_{k_u(T)}^{\theta}(S_u), $$

where we used the definition (5.9). Since we proved that $ST_n^{\theta} = b_n^{e(\theta)}$, we can divide the left-hand side by $ST_n^{\theta}$ and the right-hand side by $b_n^{e(\theta)}$ to obtain the claimed identity (5.10), using the definitions (1.3) and (3.2).

We supposed above that $k_u(T) \le N_\theta$ for all $u \in T$. Let us justify that when this condition is not met, the result is trivial. Hence suppose that $k_v(T) > N_\theta$ for some vertex $v \in T$. Then we get that $\prod_{i \in S_v} \theta_i = 0$ since the inequality $k_v(T) > N_\theta$ says that $\#S_v > \#\text{supp}(\theta)$. Therefore $ST_n^{\theta}(\tau) = (ST_n^{\theta})^{-1} \prod_{u \in T} \prod_{i \in S_u} \theta_i = 0$, and the left-hand side of (5.10) is zero. On the other hand, remember that $e_k(\theta) = 0$ whenever $k > N_\theta$, so that in particular $e_{k_v(T)}(\theta) = 0$. Hence $\mathbf{S}G_n^{e(\theta)}(T) = (b_n^{e(\theta)})^{-1} \prod_{u \in T} e_{k_u(T)}(\theta) = 0$, and the right-hand side of (5.10) is also zero. $\square$

## 5.4 Growing the plane trees

The fact that our subtree model admits a description in terms of simply generated trees with weight sequence $e(\theta)$ is particularly nice for our purposes, thanks to the well-known Newton's inequalities.

**Lemma 5.18** (Newton's inequalities). Let $(\alpha_1, \dots, \alpha_m)$ be a non-negative and non-zero sequence with finite length $m \ge 1$, and let $(e_k)_{0 \le k \le m}$ be the sequence of the elementary symmetric polynomials in the $(\alpha_1, \dots, \alpha_m)$, or equivalently let
$e_k = e_k(\alpha_1, \dots, \alpha_m, 0, 0, \dots)$ for $0 \le k \le m$. Then the sequence $(e_k)_{0 \le k \le m}$ satisfies the ultra-log-concavity inequality, that is

$$ \frac{e_k^2}{\binom{m}{k}} \ge \frac{e_{k-1}}{\binom{m}{k-1}} \cdot \frac{e_{k+1}}{\binom{m}{k+1}}, \quad k \in \{1, \dots, m-1\}. \qquad (5.12) $$

In particular, $e(\alpha_1, \dots, \alpha_m, 0, 0, \dots)$ is log-concave.<fnref n="15" />

Proofs of Lemma 5.18 may be found in many references. See for instance Theorem 51 in [HLP52], or Lemma 7.1.1 in the more recent reference [Brä15].

**Corollary 5.19.** The sequence $e(\theta)$ is log-concave for every a summable weight sequence $\theta$.

*Proof.* For $\theta$ a summable weight sequence, the sequence $e(\theta)$ is log-concave since it is the pointwise limit $\ell \to \infty$ of the sequences $e(\theta_1, \dots, \theta_\ell, 0, 0, \dots)$, $\ell \ge 1$, which are log-concave by Lemma 5.18. $\square$

**Corollary 5.20.** The distributions $(\text{SG}_n^{e(\theta)})_{n \ge 1}$ can be coupled as a Markov process $(T_n)_{n \ge 1}$ such that $T_1 \subset T_2 \subset T_3 \subset \dots$.

*Proof.* Apply Theorem 4 together with Corollary 5.19. $\square$

## 5.5 Growing the decorations

In order to construct increasing couplings for the distributions $(\text{ST}_n^\theta)_{n \ge 1}$ using Proposition 5.17 and Corollary 5.20, we will need a way to couple in an increasing way the distributions $(\mathbf{B}_k^\theta)_{0 \le k \le N_\theta}$. This is accomplished as follows.

**Proposition 5.21.** Let $\theta$ be a summable weight sequence. There exists a random sequence $X = (X_1, X_2, \dots, X_{N_\theta})$ of distinct elements of $\{1, 2, \dots\}$ such that for every $0 \le k \le N_\theta$, the random set $S_k = \{X_1, X_2, \dots, X_k\}$ has distribution $\mathbf{B}_k^\theta$.

By Remark 5.16, this is equivalent to the statement that if $\mathcal{B} = (B_i, i \ge 1)$ is a sequence of independent Bernoulli random variables whose sum is finite almost surely, then the distributions of $\mathcal{B}$ conditionally on $\sum_i B_i = k$, $0 \le k \le N$, admit an increasing coupling, i.e. one which is coordinate-wise non-decreasing. Here $N$ is the number of $i \in \{1, 2, \dots\}$ such that $B_i$ is not almost surely zero.

In the case $N < \infty$, this result is already known, with several proofs. Jonasson and Nerman leverage in [JN96, Proposition 6.2] a Markov chain whose stationary distributions are the ones we need to couple. Broman, van de Brug and Kager exhibit in [Bro+12, Lemma 2.2] an explicit Markov kernel which builds the coupling. More generally, Pemantle proves in [Pem00, Lemma 3.3] a similar statement for a class of negatively dependent measures which contains products of Bernoulli

<footnote n="15">¹⁵This is deduced from the inequality $(\binom{m}{k})^2 \ge (\binom{m}{k-1})(\binom{m}{k+1})$ for $0 < k < m$, which holds by log-concavity of the binomial coefficients. Note that in this paper we require log-concave sequences to have no internal zeros, but we already justified that this is the case for sequences having the form $e(\theta)$ with $\theta$ a summable weight sequence.</footnote>
measures. Lastly, Borcea, Brändén and Liggett generalize the latter, in [BBL09, Thm. 4.19], to a large class of negatively dependent measures.

Still, we feel it is useful to give a self-contained proof of Proposition 5.21. Our proof has close similarities with that of [Pem00, Lemma 3.3]. For $i \in \{1, 2, \dots\}$, we consider the event:

$$ \mathcal{E}_i = \{S \in \mathbb{S}: i \in S\}. $$

We will need the following lemma, which resembles Lemma 3.2.(i) in the latter reference.

**Lemma 5.22.** Let $\theta$ be a summable weight sequence and let $0 \le k < N_{\theta}$. Then,

$$ \mathbf{B}_k^{\theta}(\mathcal{E}_i) \le \mathbf{B}_{k+1}^{\theta}(\mathcal{E}_i), \quad i \in \{1, 2, \dots\}. \qquad (5.13) $$

*Proof.* Let $i \in \{1, 2, \dots\}$, which we assume to be in $\text{supp}(\theta)$ to avoid trivialities. The $k=0$ case is trivial since $\mathbf{B}_0^{\theta}(\mathcal{E}_i) = 0$, so let $0 < k < N_{\theta}$. Observe that if we write $\theta^{(i)} = (\theta_1, \dots, \theta_{i-1}, 0, \theta_{i+1}, \dots)$, then the inequality (5.13) we need to prove may be written as follows:

$$ \frac{\theta_i \cdot e_{k-1}(\theta^{(i)})}{e_k(\theta)} \le \frac{\theta_i \cdot e_k(\theta^{(i)})}{e_{k+1}(\theta)}. $$

Note that $e_{\ell}(\theta) = e_{\ell}(\theta^{(i)}) + \theta_i \cdot e_{\ell-1}(\theta^{(i)})$ for $\ell \ge 1$. Hence the last display reads

$$ \frac{\theta_i \cdot e_{k-1}(\theta^{(i)})}{e_k(\theta^{(i)}) + \theta_i \cdot e_{k-1}(\theta^{(i)})} \le \frac{\theta_i \cdot e_k(\theta^{(i)})}{e_{k+1}(\theta^{(i)}) + \theta_i \cdot e_k(\theta^{(i)})}, $$

or $e_k(\theta^{(i)})^2 \ge e_{k+1}(\theta^{(i)})e_{k-1}(\theta^{(i)})$ after re-writing. This inequality follows from Corollary 5.19. $\square$

*Proof of Proposition 5.21.* It is sufficient to treat the case when $\theta$ is finitely supported since we can deduce the general case by a limiting argument.<fnref n="16" /> We do so by induction on $1 \le N_{\theta} < \infty$. The base case $N_{\theta} = 1$ is trivial, so assume that $N_{\theta} > 1$. Let $i \in \text{supp}(\theta)$ and $\theta^{(i)} = (\theta_1, \dots, \theta_{i-1}, 0, \theta_{i+1}, \dots)$. Since $N_{\theta^{(i)}} = N_{\theta} - 1$, we get by induction an increasing coupling $(S_k^+)$$_{0 \le k \le N_{\theta} - 1}$ of the distributions $(\mathbf{B}_k^{\theta^{(i)}})$$_{0 \le k \le N_{\theta} - 1}$. We set $p_k = \mathbf{B}_k^{\theta}(\mathcal{E}_i)$, $0 \le k \le N_{\theta}$. Lastly, we let $U$ be uniformly random in $[0, 1]$, independently from all other variables. We set<fnref n="17" />

$$ S_0 = \emptyset, \quad \text{and} \quad \forall 1 \le k \le N_{\theta}, \quad S_k = \begin{cases} S_{k-1}^+ \cup \{i\} & \text{if } U \le p_k, \\ S_k^+ & \text{if } U > p_k. \end{cases} \qquad (5.14) $$

By construction $S_0 = \emptyset$ as needed, and if we let $1 \le k \le N_{\theta}$ and $S \in \mathbb{S}_k$, then if $i \in S$, we have

$$ \mathbf{P}(S_k = S) = \mathbf{P}(S_{k-1}^{+} = S \setminus \{i\}, U \le p_k) = p_k \cdot \mathbf{B}_{k-1}^{\theta^{(i)}}(S \setminus \{i\}), $$

<footnote n="16">¹⁶Say, using a suitable adaptation of Lemma 2.4 in our context.</footnote>

<footnote n="17">¹⁷When $k = N_{\theta}$, we have $p_k = 1$ by definition. Hence we do not use $S_{N_{\theta}}^+$, which is undefined.</footnote>
while if $i \notin S$, we have

$$ \mathbf{P}(S_k = S) = \mathbf{P}(S_k^+ = S, U > p_k) = (1 - p_k) \cdot \mathbf{B}_k^{\theta^{(i)}}(S). $$

Let $\theta_S = \prod_{j \in S} \theta_j$. The two last displays give that

$$ \begin{aligned} \mathbf{P}(S_k = S) &= \mathbb{1}_{i \in S} \cdot p_k \cdot \mathbf{B}_{k-1}^{\theta^{(i)}}(S \setminus \{i\}) + \mathbb{1}_{i \notin S} \cdot (1 - p_k) \cdot \mathbf{B}_k^{\theta^{(i)}}(S) \\ &= \mathbb{1}_{i \in S} \cdot \frac{\theta_i \cdot e_{k-1}(\theta^{(i)})}{e_k(\theta)} \cdot \frac{\theta_S/\theta_i}{e_{k-1}(\theta^{(i)})} + \mathbb{1}_{i \notin S} \cdot \frac{e_k(\theta^{(i)})}{e_k(\theta)} \cdot \frac{\theta_S}{e_k(\theta^{(i)})}. \end{aligned} $$

This simplifies to $\mathbf{P}(S_k = S) = \theta_S/e_k(\theta^{(i)}) = \mathbf{B}_k^{\theta}(S)$, as needed.

Now let $1 \le k < N_\theta$. By Lemma 5.22, we have $p_k \le p_{k+1}$, so that in order to verify that $S_k \subset S_{k+1}$, we only need to verify it on the events $\{U \le p_k\}$, $\{p_k < U \le p_{k+1}\}$, and $\{U > p_{k+1}\}$. Since $(S_\ell^+)$$_{0 \le \ell \le N_\theta}$ is increasing, we have $S_k \subset S_{k+1}$ on the events $\{U \le p_k\}$ and $\{U > p_{k+1}\}$. On the remaining event $\{p_k < U \le p_{k+1}\}$, we have $S_k = S_k^+ \subset S_k^+ \cup \{i\} = S_{k+1}$. Hence we have verified that $S_0 \subset S_1 \subset \cdots \subset S_{N_\theta}$. Since $\# S_k = k$ for $0 \le k \le N_\theta$, we can set $X_k$ to be the unique element in $S_k \setminus S_{k-1}$ for $1 \le k \le N_\theta$, and the proof is complete. $\square$

## 5.6 Matching the growths by shuffling the decorated plane trees

Fix $\theta = (\theta_1, \theta_2, \dots)$ a non-negative sequence such that $0 < \sum_i \theta_i < \infty$. Let us first describe a naive attempt to combine the increasing couplings for $(\mathbf{S}\mathbf{G}_n^{\mathbf{e}(\theta)})_{n \ge 1}$ and for $(\mathbf{B}_k^\theta)_{0 \le k \le N_\theta}$.

**Naive coupling** Consider mutually independent copies

$$ X_u = (X_{1,u}, \dots, X_{N_\theta,u}), \quad u \in \mathbb{U}, $$

of the random sequence $X = (X_1, \dots, X_{N_\theta})$ given by Proposition 5.21. Independently, let $(T_n)_{n \ge 1}$ be the coupling given by Corollary 5.20. For $n \ge 1$, we let $S_n = (S_{k_u(T_n),u})_{u \in T_n}$, where $S_{k_u(T_n),u} = \{X_{1,u}, \dots, X_{k_u,T_n}\}$ for every $u \in T_n$ and every $0 \le k \le N_\theta$. This yields an element $S_n \in \mathbb{S}_{T_n}$.

**Proposition 5.23 (Naive coupling).** In the above setting, if one sets

$$ \mathcal{T}_n = \mathfrak{P}^{-1}(T_n, \mathbf{S}_n), \quad n \ge 1, $$

then the sequence $(\mathcal{T}_n)_{n \ge 1}$ is a coupling of the distributions $(\mathbf{S}\mathbf{T}_n^\theta)_{n \ge 1}$.

*Proof.* This is a direct consequence of Proposition 5.17. $\square$

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

At first sight, the coupling in Proposition 5.23 may look increasing, since the ones in Corollary 5.20 and Proposition 5.21 are, but in fact it is not. The problem is that $(T_n)_{n \ge 1}$ “grows from the right” while for $u \in \mathbb{U}$ the sets $(S_{k,u})_{0 \le k \le N_\theta}$, can in principle “grow at any place”. At the cost of properly shuffling the plane trees $(T_n)_{n \ge 1}$ given the history of the couplings $(S_{k,u})_{0 \le k \le N_\theta}$, $u \in \mathbb{U}$, we can “align” the two growths and obtain a new coupling $(\mathcal{T}_n)_{n \ge 1}$ which is actually increasing.
**Shuffling decorated plane trees** We specialize to the context of decorated plane trees the shuffling operations we defined in Section 5.1 for arbitrary rooted subtrees of $\mathbb{U}$, as follows. For $k \ge 0$, we let $\mathfrak{S}_k$ be the set of permutations of $\{1, 2, \dots, k\}$, where $\mathfrak{S}_0$ is a singleton containing the empty permutation of the empty set. We denote by $\mathfrak{S}$ the graded set

$$ \mathfrak{S} = \bigsqcup_{k \ge 0} \mathfrak{S}_k. $$

An element $\boldsymbol{\sigma}$ of the set $\mathfrak{S}_T$ of grading-compatible $T$-tuples of elements of $\mathfrak{S}$ is then just a collection $\boldsymbol{\sigma} = (\sigma_u)_{u \in T}$ such that $\sigma_u \in \mathfrak{S}_{k_u(T)}$ for all $u \in T$. Note that for every $T \in \mathbb{T}$, we have that $\mathfrak{S}_T \subset \mathbb{G}(T)$. Indeed, since $T$ is a plane tree, we have $C_u(T) = \{1, 2, \dots, k_u(T)\}$ for all $u \in T$, so that for every $\boldsymbol{\sigma} = (\sigma_u)_{u \in T} \in \mathfrak{S}_T$ and every $u \in T$, the permutation $\sigma_u$ is indeed an injective mapping $C_u(T) \to \{1, 2, \dots, |C_u(T)|\}$, that is an element of $\mathbb{G}_{C_u(T)}$.

In particular, for $T \in \mathbb{T}$ and $\boldsymbol{\sigma} \in \mathfrak{S}_T$, and for every $u = (u_1, \dots, u_h) \in T$ with ancestral line $u_i = (u_1, \dots, u_i)$, $0 \le i \le h$, we can consider as in Section 5.1,

$$ \boldsymbol{\sigma} \cdot u = (\sigma_{\emptyset}(u_1), \sigma_{u_1}(u_2), \dots, \sigma_{u_{h-1}}(u_h)). $$

This is just a sub-case of the definition (5.2), and we can directly import the relevant notation and use the properties proved in this section.

*Remark 5.24.* For $T \in \mathbb{T}$ and $\boldsymbol{\sigma} \in \mathfrak{S}_T$, observe that $\boldsymbol{\sigma} \cdot T$ is also a plane tree. More generally, given any set $\mathcal{X}$, if $(T, \boldsymbol{x})$ is an $\mathcal{X}$-decorated plane tree, then so is $(\boldsymbol{\sigma} \cdot T, \boldsymbol{\sigma}_* \boldsymbol{x})$ for every $\boldsymbol{\sigma} \in \mathfrak{S}T$. Observe also that the “inverse” $\boldsymbol{\sigma}^{-1} \in \mathbb{G}(\boldsymbol{\sigma} \cdot T)$ given by Lemma 5.3 is actually in $\mathfrak{S}_{\boldsymbol{\sigma} \cdot T}$ for every $\boldsymbol{\sigma} \in \mathfrak{S}_T$, $T \in \mathbb{T}$.

**Choosing the permutations** Let us consider the set $\mathcal{X}_{\text{seq}}$ of sequences made of $N_{\theta}$ pairwise distinct elements of $\{1, 2, \dots\}$. Given any $x = (x_1, \dots, x_{N_{\theta}}) \in \mathcal{X}_{\text{seq}}$ and some $0 \le k \le N_{\theta}$, we let

$$ g_{k,x}(\ell) = x_{\ell}, \quad 1 \le \ell \le k, \qquad (5.15) $$

which defines an injective mapping $g_{k,x}: \{1, 2, \dots, k\} \to \{x_1, \dots, x_k\}$ since by definition of $\mathcal{X}_{\text{seq}}$, the elements $(x_1, \dots, x_{N_{\theta}})$ are pairwise distinct. This means that $g_{k,x} \in \mathbb{G}_{\{1, 2, \dots, k\}}$. Then, we set

$$ \sigma_{k,x} = p_{\{x_1, \dots, x_k\}} \circ g_{k,x}, \qquad (5.16) $$

where $p_{\{x_1, \dots, x_k\}}: \{x_1, \dots, x_k\} \to \{1, 2, \dots, k\}$ is the injective mapping which we defined in (5.5). By composition of injective mappings, this defines an injective mapping $\sigma_{k,x}: \{1, \dots, k\} \to \{1, \dots, k\}$, that is a permutation $\sigma_{k,x} \in \mathfrak{S}_k$.

**A better coupling strategy** The construction begins as in the “naive coupling”. Consider again mutually independent copies

$$ X_u = (X_{1,u}, \dots, X_{N_{\theta},u}), \quad u \in \mathbb{U}, $$
of the random sequence $X = (X_1, \dots, X_{N_\theta})$ given by Proposition 5.21. Independently, let $(T_n)_{n \ge 1}$ be the coupling given by Corollary 5.20. As in the “naive coupling”, for $n \ge 1$, we let $S_n = (S_{k_u(T_n),u})_{u \in T_n}$, where $S_{k_u, u} = \{X_{1,u}, \dots, X_{k_u, u}\}$ for every $u \in T_n$ and every $0 \le k \le N_\theta$. Now comes the difference with the “naive coupling”. For every $n \ge 1$, we let:

$$ \sigma_n = (\sigma_{k_u(T_n), X_u})_{u \in T_n}, $$

where the notation $\sigma_{k,x}$ is defined in (5.16). This gives an element $\sigma_n \in \mathcal{S}_{T_n}$.

**Lemma 5.25.** In the above setting, the random pair $(\sigma_n \cdot T_n, (\sigma_n)_* S_n)$ has the same joint distribution as $(T_n, S_n)$, for every $n \ge 1$.

The proof of Lemma 5.25 relies on some material collected in Appendix A, more precisely Corollary A.8, which proves a result similar to Lemma 5.25, but for a more general class of “decoration-dependent” shuffling operations.

*Proof of Lemma 5.25.* For $T \in \mathbb{T}$, for $\boldsymbol{x} = (x_u)_{u \in T} \in \mathbb{X}_{\text{seq}}^T$, and for $u \in T$, we let $\psi(T, \boldsymbol{x}, u) = \sigma_{k_u(T),x_u}$, where the notation $\sigma_{k,x}$ is introduced in (5.16). Then for every $\boldsymbol{\pi} \in \mathcal{S}_T$, we have

$$ \psi(\boldsymbol{\pi} \cdot T, \boldsymbol{\pi}_* \boldsymbol{x}, \boldsymbol{\pi} \cdot u) = \sigma_{k,x} |_{\substack{k=k_{\boldsymbol{\pi} \cdot u}(\boldsymbol{\pi} \cdot T) \\ x=x_{\boldsymbol{\pi}^{-1}(\boldsymbol{\pi} \cdot u)}}} = \sigma_{k,x} |_{x=x_u}^{k=k_u(T)} = \psi(T, \boldsymbol{x}, u), $$

where we used that $k_{\boldsymbol{\pi} \cdot u}(\boldsymbol{\pi} \cdot T) = k_u(T)$ by Lemma 5.7. In the language of Appendix A, this means that $\psi$ is a $\mathcal{S}$-equivariant $\mathbb{X}_{\text{seq}}$-shuffling rule. If we let $\nu$ be the distribution of the sequence $(X_1, \dots, X_{N_\theta})$ of Proposition 5.21, then Corollary A.8 gives the result, with these choices of $\psi$ and $\nu$. $\square$

**Corollary 5.26** (Final coupling). In the above setting, if one sets for $n \ge 1$,

$$ \mathcal{T}'_n = \mathfrak{P}^{-1}(\sigma_n \cdot T_n, (\sigma_n)_* S_n), \qquad (5.17) $$

then the sequence $(\mathcal{T}'_n)_{n \ge 1}$ is a coupling of the distributions $(\mathbf{S}\mathbf{T}_n^\theta)_{n \ge 1}$.

*Proof.* Let $n \ge 1$. By Lemma 5.25, the pairs $(\sigma_n \cdot T_n, (\sigma_n)_* S_n)$ and $(T_n, S_n)$ have the same distribution, so that $\mathcal{T}'_n = \mathfrak{P}^{-1}(\sigma_n \cdot T_n, (\sigma_n)_* S_n)$ has the same distribution as $\mathcal{T}_n = \mathfrak{P}^{-1}(T_n, S_n)$, which is $\mathbf{S}\mathbf{T}_n^\theta$ by Proposition 5.23. $\square$

## 5.7 Proof of Theorem 3

We first prove two deterministic lemmas. Let $(x_u)_{u \in \mathbb{U}}$ be an arbitrary fixed collection of elements of $\mathbb{X}_{\text{seq}}$, where $x_u = (x_{1,u}, x_{2,u}, \dots, x_{N_\theta, u})$ for every $u \in \mathbb{U}$. For every plane tree $T \in \mathbb{T}$, we set:

$$ \mathbf{S}_T = (S_{k_u(T),u})_{u \in T}, \qquad \sigma_T = (\sigma_{k_u(T),x_u})_{u \in T}, \qquad g_T = (g_{k_u(T),x_u})_{u \in T}, \qquad (5.18) $$

where the notation $g_{k,x}$ and $\sigma_{k,x}$ are defined in (5.16), and where we write $S_{k,u} = \{x_{1,u}, \dots, x_{k,u}\}$ for $u \in T$ and $0 \le k \le N_\theta$.
**Lemma 5.27.** Let $T \in \mathbb{T}$. For every $u \in T$, we have

$$ \overline{p(\sigma_T)_* S_T} \cdot (\sigma_T \cdot u) = g_T \cdot u. $$

*Proof.* In order to lighten notation, let us write $S_u = S_{k_u(T),u}$, and $\sigma_u = \sigma_{k_u(T),x_u}$, as well as $g_u = g_{k_u(T),x_u}$, for every $u \in T$. Notice that by (5.16), we have

$$ g_u = p_{S_u}^{-1} \circ \sigma_u, \quad u \in T. \qquad (5.19) $$

For every $u' = (u'_1, \dots, u'_h) \in \sigma_T \cdot T$ with ancestral line $(u'_\ell)_{0 \le \ell \le h}$, we have by definition:

$$ \overline{p(\sigma_T)_* S_T} \cdot u' = \left( p_{S_{\sigma_T^{-1} \cdot u'_0}}^{-1}(u'_1), p_{S_{\sigma_T^{-1} \cdot u'_1}}^{-1}(u'_2), \dots, p_{S_{\sigma_T^{-1} \cdot u'_{h-1}}}^{-1}(u'_h) \right). \qquad (5.20) $$

Let $u = (u_1, \dots, u_h) \in T$, with ancestral line $(u_\ell)_{0 \le \ell \le h}$. We have by definition:

$$ \sigma_T \cdot u = (\sigma_{u_0}(u_1), \sigma_{u_1}(u_2), \dots, \sigma_{u_{h-1}}(u_h)). \qquad (5.21) $$

If we combine (5.20) and (5.21) with $u' = \sigma_T \cdot u$, whose ancestral line in $\sigma_T \cdot T$ is given by $u'_\ell = \sigma_T \cdot u_\ell$, $0 \le \ell \le h$, we obtain:

$$ \begin{aligned} \overline{p(\sigma_T)_* S_T} \cdot (\sigma_T \cdot u) &= \left( p_{S_{u_0}}^{-1}(\sigma_{u_0}(u_1)), p_{S_{u_1}}^{-1}(\sigma_{u_0}(u_2)), \dots, p_{S_{u_{h-1}}}^{-1}(\sigma_{u_0}(u_h)) \right) \\ &= (g_{u_0}(u_1), g_{u_1}(u_2), \dots, g_{u_{h-1}}(u_h)) \\ &= g_T \cdot u, \end{aligned} $$

where the second equality uses (5.19). This concludes the proof. $\square$

**Lemma 5.28.** If $T$ and $\tilde{T}$ be two plane trees such that $T \subseteq \tilde{T}$, then we have

$$ \mathfrak{P}^{-1} (\sigma_T \cdot T, (\sigma_T)_* S_T) \subseteq \mathfrak{P}^{-1} (\sigma_{\tilde{T}} \cdot \tilde{T}, (\sigma_{\tilde{T}})_* S_{\tilde{T}}). $$

*Proof.* By (5.18), we have $g_T = (g_{k_u(T),x_u})_{u \in T}$ for every $T \in \mathbb{T}$. Thanks to how we defined $g_{k,x}$ in (5.15), we have for every $T \in \mathbb{T}$ and every $u \in T$ with ancestral line $(u_\ell)_{0 \le \ell \le h}$ the expression:

$$ g_T \cdot u = (x_{u_0}(u_1), x_{u_1}(u_2), \dots, x_{u_{h-1}}(u_h)), $$

where for clarity we have written $x_u(k)$ as a substitute for the notation $x_{k,u}$. Note that the right-hand side does not depend on $T$. In particular, given two plane trees $T$ and $\tilde{T} \in \mathbb{T}$ such that $T \subseteq \tilde{T}$, we have $g_T \cdot u = g_{\tilde{T}} \cdot u$ for every $u \in T$. Since by assumption we have $T \subseteq \tilde{T}$, we get:

$$ g_T \cdot T = g_{\tilde{T}} \cdot T \subseteq g_{\tilde{T}} \cdot \tilde{T}. $$

Using Lemma 5.27 and the expression $\mathfrak{P}^{-1}: (T, S) \mapsto \overline{p_S} \cdot T$ of Proposition 5.13, this means that

$$ \mathfrak{P}^{-1} (\sigma_T \cdot T, (\sigma_T)_* S_T) \subseteq \mathfrak{P}^{-1} (\sigma_{\tilde{T}} \cdot \tilde{T}, (\sigma_{\tilde{T}})_* S_{\tilde{T}}), $$

which concludes the proof. $\square$
We are now equipped to prove Theorem 3. It is sufficient to verify that the coupling $(\mathcal{T}'_n)_{n \ge 1}$ of the distributions $(\mathbf{ST}_n^\theta)_{n \ge 1}$ given by Corollary 5.26 is indeed increasing. The Markov property we refer to in Theorem 3 can then be enforced by successively resampling $\mathcal{T}'_{n+1}$ conditionally on $\mathcal{T}'_n$ for $n = 1, 2, \dots$.

We have to verify that $\mathcal{T}'_n \subset \mathcal{T}'_{n+1}$ for all $n \ge 1$, where $(\mathcal{T}'_n)_{n \ge 1}$ are given by the expression (5.17), that is:

$$ \mathcal{T}'_n = \mathfrak{P}^{-1}(\sigma_n \cdot \mathbf{T}_n, (\sigma_n)_* \mathbf{S}_n), \quad n \ge 1. $$

If we reason conditionally on the collection $(X_u)_{u \in \mathcal{U}}$, thus treating it as a deterministic collection $(x_u)_{u \in \mathcal{U}}$, then with the notation (5.18) we have $\mathbf{S}_n = \mathbf{S}_{\mathbf{T}_n}$, and $\sigma_n = \sigma_{\mathbf{T}_n}$. In particular, Lemma 5.28 gives that $\mathcal{T}'_n \subset \mathcal{T}'_{n+1}$ for every $n \ge 1$, as needed. This concludes the proof of Theorem 3. $\square$

## A Decoration-dependent shufflings of decorated plane trees

Given a probability space $(\mathcal{X}, \mathcal{X}, \nu)$ and some non-negative sequence $\mathbf{w} = (w_0, w_1, \dots)$ with $w_0 w_1 > 0$, the probability distribution $\mathbf{SG}_n^\mathbf{w}(dT) \cdot \nu^{\otimes T}(d\mathbf{x})$ is morally left invariant by “shuffling” the subtrees of descendants at every vertex. Such a symmetry has been used for instance by Addario-Berry and Albenque in [AA21], where the shuffling operation is performed uniformly at random. The main goal of this section is to arrive at Corollary A.8, which states that the measure $\mathbf{SG}_n^\mathbf{w}(dT) \cdot \nu^{\otimes T}(d\mathbf{x})$ is left invariant by some more general “shuffling operations” which are allowed to depend on the tree and its decorations.

As in Section 5.6, for $T \in \mathcal{T}$, we denote by $\mathcal{S}_T$ the set of collections $\boldsymbol{\sigma} = (\sigma_u)$, where $\sigma_u$ is a permutation belonging to $\mathcal{S}_{k_u(T)}$ for every $u \in T$. Also, as in Sections 5.1 and 5.6, for every $u = (u_1, \dots, u_h) \in T$ with ancestral line $u_\ell = (u_1, \dots, u_\ell)$, $0 \le i \le h$, we let

$$ \boldsymbol{\sigma} \cdot \mathbf{u} = (\sigma_{\emptyset}(u_1), \sigma_{u_1}(u_2), \dots, \sigma_{u_{h-1}}(u_h)), $$

and $\boldsymbol{\sigma} \cdot T = \{\boldsymbol{\sigma} \cdot \mathbf{u} : \mathbf{u} \in T\}$. We have proven in Section 5, see Lemma 5.3 and Remark 5.24, that there exists $\boldsymbol{\sigma}^{-1} \in \mathcal{S}_{\boldsymbol{\sigma},T}$ such that $\boldsymbol{\sigma}^{-1} \cdot (\boldsymbol{\sigma} \cdot \mathbf{u}) = \mathbf{u}$ for all $\mathbf{u} \in \boldsymbol{\tau}$, and $\boldsymbol{\sigma} \cdot (\boldsymbol{\sigma}^{-1} \cdot \mathbf{u}') = \mathbf{u}'$ for all $\mathbf{u}' \in \boldsymbol{\sigma} \cdot \boldsymbol{\tau}$. Given a set $\mathcal{X}$, this allows to define a push-forward mapping $\boldsymbol{\sigma}_* : \mathcal{X}^T \to \mathcal{X}^{\boldsymbol{\sigma} \cdot T}$ by setting $\boldsymbol{\sigma}_* \mathbf{x} = (x_{\boldsymbol{\sigma}^{-1}, \mathbf{u}'})_{\mathbf{u}' \in \boldsymbol{\sigma} \cdot T}$. Other related properties have been established in Section 5.1, which we will refer to when necessary.

**Shuffling rules** Let $\mathcal{X}$ be a fixed set. We consider the set of pointed $\mathcal{X}$-decorated plane trees:

$$ \mathcal{T}^*[\mathcal{X}] = \{(T, \mathbf{x}, \mathbf{u}) : T \in \mathcal{T}, \mathbf{x} \in \mathcal{X}^T, \mathbf{u} \in T\}. $$

**Definition A.1.** An $\mathcal{X}$-shuffling rule is a mapping $\psi: \mathcal{T}^*[\mathcal{X}] \to \mathcal{S}$ such that for every $(T, \mathbf{x}, \mathbf{u}) \in \mathcal{T}^*[\mathcal{X}]$, its image $\psi(T, \mathbf{x}, \mathbf{u})$ is an element of $\mathcal{S}_{k_u(T)}$. Given an
X-shuffling rule, for every $T \in \mathbb{T}$ and every $\boldsymbol{x} \in \mathbb{X}^T$, we set:

$$ \sigma_{T, \boldsymbol{x}}^{\psi} = (\psi(T, \boldsymbol{x}, \mathbf{u}))_{\mathbf{u} \in T}, $$

which defines an element of $\mathfrak{S}_T$

Without additional conditions on $\psi$, there is no guarantee that the mapping $T \mapsto (\sigma_{T, \boldsymbol{x}}^{\psi}) \cdot T$ is even bijective. For instance, we can choose $\psi$ so that the action of $\sigma_{T, \boldsymbol{x}}^{\psi}$ on the tree $T$ is to switch the positions of the leftmost, resp. the biggest, subtree of descendants of the root. We then cannot “go back” since the information of where the biggest subtree was is lost. We therefore introduce a natural condition on X-shuffling rules, as follows.

**Definition A.2.** Let $\psi$ be an X-shuffling rule. We say that $\psi$ is $\mathfrak{S}$-equivariant<fnref n="18" /> if for every $(T, \boldsymbol{x}, \mathbf{u}) \in \mathbb{T} \cdot [\mathbb{X}]$ and every $\boldsymbol{\sigma} \in \mathfrak{S}_T$ we have:

$$ \psi(T, \boldsymbol{x}, \mathbf{u}) = \psi(\boldsymbol{\sigma} \cdot T, \boldsymbol{\sigma}_* \boldsymbol{x}, \boldsymbol{\sigma} \cdot \mathbf{u}). $$

Observe that given $\psi$ an X-shuffling rule, we have the equivalence:

$$ \psi \text{ is } \mathfrak{S}\text{-equivariant} \iff \forall \boldsymbol{\pi} \in \mathfrak{S}_T, \quad \boldsymbol{\sigma}_{\boldsymbol{\pi} \cdot T, \boldsymbol{\pi}_* \boldsymbol{x}}^{\psi} = \boldsymbol{\pi}_* (\boldsymbol{\sigma}_{T, \boldsymbol{x}}^{\psi}). \quad (A.1) $$

The following lemma elucidates the structure of the “reverse” shuffling operation.

**Lemma A.3 (Unshuffling lemma).** Let $\mathbb{X}$ be a set and let $\psi$ be an X-shuffling rule. If $\psi$ is $\mathfrak{S}$-equivariant, then for all $T, T' \in \mathbb{T}$, $\boldsymbol{x} \in \mathbb{X}^T$, $\boldsymbol{x}' \in \mathbb{X}^{T'}$, $\boldsymbol{\pi} \in \mathfrak{S}_T$, we have the equivalence

$$ \left\{ \begin{array}{l} T' = (\boldsymbol{\sigma}_{T, \boldsymbol{x}}^{\psi}) \cdot T \\ \boldsymbol{x}' = (\boldsymbol{\sigma}_{T, \boldsymbol{x}}^{\psi})_* \boldsymbol{x} \end{array} \right. \iff \left\{ \begin{array}{l} T = (\bar{\boldsymbol{\sigma}}_{T', \boldsymbol{x}'}^{\psi}) \cdot T' \\ \boldsymbol{x} = (\bar{\boldsymbol{\sigma}}_{T', \boldsymbol{x}'}^{\psi})_* \boldsymbol{x}' \end{array} \right. \quad (A.2) $$

and if one of these equivalent conditions is satisfied then $\boldsymbol{\sigma}_{T', \boldsymbol{x}'}^{\psi} = (\bar{\boldsymbol{\sigma}}_{T, \boldsymbol{x}}^{\psi})^{-1}$.

*Proof.* Suppose that the left-hand side of (A.2) holds. Since $\psi$ is $\mathfrak{S}$-equivariant, if we let $\boldsymbol{\pi} = \boldsymbol{\sigma}_{T, \boldsymbol{x}}^{\psi}$, then by (A.1), we have $\boldsymbol{\sigma}_{\boldsymbol{\pi} \cdot T, \boldsymbol{\pi}_* \boldsymbol{x}}^{\psi} = \boldsymbol{\pi}_* (\boldsymbol{\sigma}_{T, \boldsymbol{x}}^{\psi})$, that is,

$$ \boldsymbol{\sigma}_{T', \boldsymbol{x}'}^{\psi} = (\boldsymbol{\sigma}_{T, \boldsymbol{x}}^{\psi})_* (\boldsymbol{\sigma}_{T, \boldsymbol{x}}^{\psi}). $$

By Lemma 5.9, this yields that

$$ \bar{\boldsymbol{\sigma}}_{T', \boldsymbol{x}'}^{\psi} = (\boldsymbol{\sigma}_{T, \boldsymbol{x}}^{\psi})_* (\bar{\boldsymbol{\sigma}}_{T, \boldsymbol{x}}^{\psi}). $$

By Lemma 5.5, this means that $\bar{\boldsymbol{\sigma}}_{T', \boldsymbol{x}'}^{\psi} = (\boldsymbol{\sigma}_{T, \boldsymbol{x}}^{\psi})^{-1}$, which gives $T = (\bar{\boldsymbol{\sigma}}_{T', \boldsymbol{x}'}^{\psi}) \cdot T'$ and $\boldsymbol{x} = (\bar{\boldsymbol{\sigma}}_{T', \boldsymbol{x}'}^{\psi})_* \boldsymbol{x}'$ using Lemmas 5.3 and 5.6. Hence the left-hand side implies the right-hand side in (A.2). The converse implication is proven similarly. We have already justified above that $\boldsymbol{\sigma}_{T', \boldsymbol{x}'}^{\psi} = (\bar{\boldsymbol{\sigma}}_{T, \boldsymbol{x}}^{\psi})^{-1}$ when one of the two equivalent conditions is satisfied. $\square$

<footnote n="18">¹⁸The motivation for this name is the equivalence (A.1), by analogy with the notion of equivariance of some mapping with respect to some group action, which means commutation of that mapping with the group action.</footnote>
For purely technical reasons, we will need to rephrase Lemma A.3 as follows.

**Corollary A.4.** Let $\mathcal{X}$ be a set and let $\psi$ be an $\mathcal{X}$-shuffling rule. If $\psi$ is $\mathcal{S}$-equivariant, then for every $T, T' \in \mathcal{T}$, $\boldsymbol{x} \in \mathcal{X}^T$, and $\boldsymbol{\pi} \in \mathcal{S}_{T'}$, we have

$$ \left\{ \begin{array}{l} \boldsymbol{\sigma}_{T, \boldsymbol{x}}^{\psi} \cdot T = T', \\ \boldsymbol{\sigma}_{T, \boldsymbol{x}}^{\psi} = \boldsymbol{\pi}^{-1} \end{array} \right. \iff \left\{ \begin{array}{l} T = \boldsymbol{\pi} \cdot T', \\ \boldsymbol{\sigma}_{T', \boldsymbol{\pi}_*^{-1} \boldsymbol{x}}^{\psi} = \bar{\boldsymbol{\pi}}. \end{array} \right. \qquad (A.3) $$

*Proof.* Let $T, T' \in \mathcal{T}$, $\boldsymbol{x} \in \mathcal{X}^T$, and $\boldsymbol{\pi} \in \mathcal{S}_{T'}$. Then, Lemma A.3 applied with $\boldsymbol{x}' = \boldsymbol{\pi}_*^{-1} \boldsymbol{x}$ gives the equivalence:

$$ \left\{ \begin{array}{l} (\boldsymbol{\sigma}_{T, \boldsymbol{x}}^{\psi}) \cdot T = T', \\ (\boldsymbol{\sigma}_{T, \boldsymbol{x}}^{\psi})_* \boldsymbol{x} = \boldsymbol{\pi}_*^{-1} \boldsymbol{x} \\ \boldsymbol{\sigma}_{T, \boldsymbol{x}}^{\psi} = \boldsymbol{\pi}^{-1} \end{array} \right. \iff \left\{ \begin{array}{l} T = (\bar{\boldsymbol{\sigma}}_{T', \boldsymbol{\pi}_*^{-1} \boldsymbol{x}}^{\psi}) \cdot T', \\ \boldsymbol{x} = (\bar{\boldsymbol{\sigma}}_{T', \boldsymbol{\pi}_*^{-1} \boldsymbol{x}}^{\psi})_* (\boldsymbol{\pi}_*^{-1} \boldsymbol{x}) \\ \boldsymbol{\sigma}_{T', \boldsymbol{\pi}_*^{-1} \boldsymbol{x}}^{\psi} = \bar{\boldsymbol{\pi}}. \end{array} \right. $$

But the left/right-hand sides of the last display are clearly equivalent to the left/right-hand sides of (A.3) respectively. In particular, the last display expresses the same equivalence as (A.3). $\square$

**Invariance under shuffling** Given a measurable space $(\mathcal{X}, \mathcal{X})$, we turn $\mathcal{T}[\mathcal{X}]$ into a measurable space by endowing it with the $\sigma$-algebra generated by the sets $\{T\} \times A$ for $T \in \mathcal{T}$ and $A \in \mathcal{X}^{\otimes T}$. We similarly endow $\mathcal{T}^{\bullet}[\mathcal{X}]$ with the $\sigma$-algebra generated by the sets $\{T\} \times A \times \{\mathbf{u}\}$ for $T \in \mathcal{T}$, $A \in \mathcal{X}^{\otimes T}$, and $\mathbf{u} \in T$.

**Definition A.5.** A collection $(\mathfrak{m}_T)_{T \in \mathcal{T}}$ of finite measures on $\mathcal{X}^T$, $T \in \mathcal{T}$, respectively will be called $\mathcal{S}$-consistent if the image measure with respect to the mapping $\boldsymbol{x} \mapsto \boldsymbol{\sigma}_* \boldsymbol{x}$ of the measure $\mathfrak{m}_T$ is the measure $\mathfrak{m}_{\boldsymbol{\sigma}, T}$, for every $T \in \mathcal{T}$ and every $\boldsymbol{\sigma} \in \mathcal{S}_T$.

This notion of $\mathcal{S}$-consistency allows to generate invariant measures on the set of decorated trees, which are invariant with respect to our “decoration-dependent” shuffling operations.

**Proposition A.6.** Let $(\mathcal{X}, \mathcal{X})$ be a measurable space. Let $\psi$ be a measurable $\mathcal{X}$-shuffling rule, and let $(\mathfrak{m}_T)_{T \in \mathcal{T}}$ be a collection of finite measures on $\mathcal{X}^T$ respectively. If $\psi$ is $\mathcal{S}$-equivariant and $(\mathfrak{m}_T)_{T \in \mathcal{T}}$ is $\mathcal{S}$-consistent, then the measure $\mathfrak{m}$ on $\mathcal{T}[\mathcal{X}]$ given by

$$ \mathfrak{m}(dT, d\boldsymbol{x}) = \sum_{T_0 \in \mathcal{T}} \delta_{T_0}(dT) \mathfrak{m}_T(d\boldsymbol{x}) \qquad (A.4) $$

is invariant<fnref n="19" /> under the mapping $F^{\psi}: (T, \boldsymbol{x}) \mapsto ((\boldsymbol{\sigma}_{T, \boldsymbol{x}}^{\psi}) \cdot T, (\boldsymbol{\sigma}_{T, \boldsymbol{x}}^{\psi})_* \boldsymbol{x})$.

*Proof.* Let $T' \in \mathcal{T}$ and let $\varphi$ be a bounded measurable function on $\mathcal{X}^T$, and let $\Phi: \mathcal{T}[\mathcal{X}] \to \mathbb{R}$ be the bounded measurable function $(T, \boldsymbol{x}) \mapsto 1_{\{T=T'\}}\varphi(\boldsymbol{x})$. Such

<footnote n="19">¹⁹We say that a measure $m$ is invariant under $f$ if we have $m \circ f^{-1} = m$.</footnote>
functions suffice to characterize measures on $T[X]$, so that we only need to check
that $\int \Phi \circ F^{\psi} d\mathbf{m} = \int \Phi d\mathbf{m}$. Notice that

$$
\int_{\mathbb{T}[X]} \Phi \circ F^{\psi} \mathrm{d}\mathbf{m} = \int_{\mathbb{T}[X]} \mathbf{m}(dT, d\mathbf{x}) \mathbb{1}\{\sigma_{T,x}^{\psi} \cdot T = T'\} \cdot \varphi((\sigma_{T,x}^{\psi})_* \mathbf{x}) = \sum_{\pi \in \mathcal{S}_{T'}} I(\pi), \tag{A.5}
$$

where for $\boldsymbol{\pi} \in \mathcal{S}_{T'}$, we denote

$$
I(\boldsymbol{\pi}) = \int_{\mathbb{T}[X]} \mathbf{m}(dT, d\boldsymbol{x}) \mathbb{1}\{\boldsymbol{\sigma}_{T,x}^{\psi} \cdot T = T'\} \cdot \mathbb{1}\{\boldsymbol{\sigma}_{T,x}^{\psi} = \boldsymbol{\pi}^{-1}\} \cdot \varphi(\boldsymbol{\pi}_{*}^{-1} \boldsymbol{x}).
$$

Let $\boldsymbol{\pi} \in \mathcal{S}_{T'}$. By Corollary A.4, we have

$$
\begin{align*}
I(\boldsymbol{\pi}) &= \int_{\mathbb{T}[X]} \mathbf{m}(dT, d\boldsymbol{x}) \mathbb{1}_{\{T=\boldsymbol{\pi} \cdot T'\}} \cdot \mathbb{1}_{\{\boldsymbol{\sigma}_{T', \pi_*^{-1}x}^{\psi}=\bar{\pi}\}} \cdot \varphi(\boldsymbol{\pi}_*^{-1}\boldsymbol{x}) \\
&= \int_{\mathbb{X}\boldsymbol{\pi} \cdot T'} \mathbf{m}_{\boldsymbol{\pi} \cdot T'}(d\boldsymbol{x}) \mathbb{1}_{\{\boldsymbol{\sigma}_{T', \pi_*^{-1}x}^{\psi}=\bar{\pi}\}} \cdot \varphi(\boldsymbol{\pi}_*^{-1}\boldsymbol{x}),
\end{align*}
$$

where the last equality uses that $\mathbf{m}$ takes the form (A.4). Since by $\mathcal{S}$-consistency,
the measure $\mathbf{m}_{T'}$ is the push-forward with respect to $\mathbf{x} \mapsto \boldsymbol{\pi}_*^{-1}\mathbf{x}$ of the measure
$\mathbf{m}_{\boldsymbol{\pi} \cdot T'}$, we obtain

$$
I(\boldsymbol{\pi}) = \int_{\mathbb{X}T'} \mathbf{m}_{T'}(d\boldsymbol{x}') \mathbb{1}\{\boldsymbol{\sigma}_{T', \boldsymbol{x}'}^{\psi} = \bar{\pi}\} \cdot \varphi(\boldsymbol{x}').
$$

By summing over all $\boldsymbol{\pi} \in \mathcal{S}_{T'}$ and using (A.5), we get

$$
\int_{\mathbb{T}[X]} \Phi \circ F^{\psi} \mathrm{d}\mathbf{m} = \sum_{\boldsymbol{\pi} \in \mathcal{S}_{T'}} \int_{\mathbb{X}T'} \mathbf{m}_{T'}(d\mathbf{x}') \mathbb{1}_{\{\boldsymbol{\sigma}_{T', \mathbf{x}'}^{\psi} = \bar{\pi}\}} \cdot \varphi(\mathbf{x}') = \int_{\mathbb{X}T'} \mathbf{m}_{T'}(d\mathbf{x}') \varphi(\mathbf{x}')
$$

Since $\mathbf{m}$ takes the form (A.4), the right-hand side equals $\int \Phi \, d\mathbf{m}$. Hence we have
$\int \Phi \circ F^{\psi} \, d\mathbf{m} = \int \Phi \, d\mathbf{m}$, as needed to conclude. $\square$

**Lemma A.7.** Let $(\mathcal{X}, \mathcal{X}, \nu)$ be a probability space. The collection $(\nu^{\otimes T})_{T \in \mathbb{T}}$ of probability measures is $\mathcal{S}$-consistent.

Proof. Let $T \in \mathbb{T}$ and $\boldsymbol{\sigma} \in \mathcal{S}_T$. For every collection $(\varphi_{u'})_{u' \in \boldsymbol{\sigma} \cdot T}$ of bounded measurable functions on $\mathcal{X}$, we have

$$
\int \nu^{\otimes T}(d\mathbf{x}) \prod_{u' \in \boldsymbol{\sigma} \cdot T} \varphi_{u'}(x_{\boldsymbol{\sigma}^{-1} \cdot u'}) = \prod_{u' \in \boldsymbol{\sigma} \cdot T} \int \varphi_{u'} d\nu = \int \nu^{\otimes (\boldsymbol{\sigma} \cdot T)}(d\mathbf{x}') \prod_{u' \in \boldsymbol{\sigma} \cdot T} \varphi_{u'}(x'_{u'}),
$$

which gives that the image measure of $\nu^{\otimes T}$ with respect to the mapping $\mathbf{x} \mapsto \boldsymbol{\sigma}_* \mathbf{x}$ is the measure $\nu^{\otimes (\boldsymbol{\sigma} \cdot T)}$. Hence $(\nu^{\otimes T})_{T \in \mathbb{T}}$ is $\mathcal{S}$-consistent. $\square$

**Corollary A.8.** Let $(\mathcal{X}, \mathcal{X}, \nu)$ be a probability space, and let $\psi$ be a measurable $\mathcal{X}$-shuffling rule. If $\psi$ is $\mathcal{S}$-equivariant, then for every non-negative sequence $\mathbf{w} = (w_0, w_1, \dots)$ with $w_0 w_1 > 0$, and for every $n \ge 1$, the probability measure

$$
\mathbf{S}\mathbf{G}_{n}^{\mathbf{w}}(dT) \cdot \nu^{\otimes T}(d\mathbf{x})
$$

is invariant under the mapping $F^{\psi}: (T, \mathbf{x}) \mapsto ((\boldsymbol{\sigma}_{T, \mathbf{x}}^{\psi}) \cdot T, (\boldsymbol{\sigma}_{T, \mathbf{x}}^{\psi})_{*} \mathbf{x})$.
*Proof*. Fix $n \ge 1$. For $T \in \mathbb{T}$, we let $\mathfrak{m}_T = \mathbf{SG}_n^w(T) \cdot \nu^{\otimes T}(d\mathbf{x})$. By Proposition A.6, it suffices to verify that the collection $(\mathfrak{m}_T)_{T \in \mathbb{T}}$ is $\mathfrak{S}$-consistent. Let $T \in \mathbb{T}$ and $\boldsymbol{\sigma} \in \mathfrak{S}_T$. We deduce from Lemma 5.7 and from the definition (3.2) of the distribution $\mathbf{SG}_n^w(T)$ that we have $\mathbf{SG}_n^w(T) = \mathbf{SG}_n^w(\boldsymbol{\sigma} \cdot T)$. Combining this with Lemma A.7, we get that the image under $\mathbf{x} \mapsto \boldsymbol{\sigma}_* \mathbf{x}$ of $\mathfrak{m}_T$ is $\mathfrak{m}_{\boldsymbol{\sigma} \cdot T}$, and therefore the collection $(\mathfrak{m}_T)_{T \in \mathbb{T}}$ is $\mathfrak{S}$-consistent, as needed. □

## References

[AA21] L. Addario-Berry and M. Albenque. "Convergence of non-bipartite maps via symmetrization of labeled trees". en *Annales Henri Lebesgue* 4 (2021), pp. 653-683. DOI: 10.5802/ahl.84.

[Add14] L. Addario-Berry. "Growing random 3-connected maps". *Electron. Commun. Probab.* 19 (2014), no. 54, 12. DOI: 10.1214/ECP.v19-3314.

[BBL09] J. Borcea, P. Brändén, and T. M. Liggett. "Negative dependence and the geometry of polynomials". *J. Amer. Math. Soc.* 22.2 (2009), pp. 521–567. DOI: 10.1090/S0894-0347-08-00618-8.

[Brä15] P. Brändén. "Unimodality, log-concavity, real-rootedness and beyond". In: *Handbook of enumerative combinatorics*. CRC Press, Boca Raton, FL, 2015, pp. 437–483. Draft available at https://arxiv.org/abs/1410.6601.

[Bre89] F. Brenti. "Unimodal, log-concave and Pólya frequency sequences in combinatorics". *Mem. Amer. Math. Soc.* 81.413 (1989), pp. viii+106. DOI: 10.1090/memo/0413.

[Bre94] F. Brenti. "Log-concave and unimodal sequences in algebra, combinatorics, and geometry: an update". In: *Jerusalem combinatorics '93*. Vol. 178. Contemp. Math. Amer. Math. Soc., Providence, RI, 1994, pp. 71–89. DOI: 10.1090/conm/178/01893. URL: https://doi.org/10.1090/conm/178/01893.

[Bro+12] E. I. Broman et al. "Stochastic domination and weak convergence of conditioned Bernoulli random vectors". *ALEA Lat. Am. J. Probab. Math. Stat.* 9.2 (2012), pp. 403–434.

[Bro14] E. I. Broman. "Stochastic ordering of infinite binomial Galton-Watson trees". *ALEA Lat. Am. J. Probab. Math. Stat.* 11.1 (2014), pp. 209–227.

[Bro16] E. I. Broman. "Stochastic ordering of infinite geometric Galton-Watson trees". *J. Theoret. Probab.* 29.3 (2016), pp. 1069–1082. DOI: 10.1007/s10959-015-0608-x.

[CCS24] A. Caraceni, N. Curien, and R. Stephenson. *Where do (random) trees grow leaves?* 2024. arXiv: 2401.07891 [math.PR].
[CS20] A. Caraceni and A. Stauffer. "Polynomial mixing time of edge flips on quadrangulations". *Probability Theory and Related Fields* 176 (2020). DOI: 10.1007/s00440-019-00913-5.

[CS23] A. Caraceni and A. Stauffer. "Growing uniform planar maps face by face". *Random Structures Algorithms* (2023), pp. 1–26. DOI: 10.1002/rsa.21165.

[FM23] L. Fredes and J.-F. Marckert. "Models of random subtrees of a graph". *Probability Surveys* 20 none (2023), pp. 722–801. DOI: 10.1214/23-PS22.

[GP05] A. Gnedin and J. Pitman. "Exchangeable Gibbs partitions and Stirling triangles". *Zap. Nauchn. Sem. S.-Peterburg. Otdel. Mat. Inst. Steklov. (POMI)* 325 (2005), pp. 83–102, 244–245. DOI: 10.1007/s10958-006-0335-z.

[GP19] C. Goldschmidt and M. Przykucki. "Parking on a random tree". *Combinatorics, Probability and Computing* 28.1 (2019), pp. 23–45. DOI: 10.1017/S0963548318000457.

[HLP52] G. H. Hardy, J. E. Littlewood, and G. Pólya. *Inequalities*. 2d ed. Cambridge, at the University Press, 1952.

[Huh18] J. Huh. "Combinatorial applications of the Hodge-Riemann relations". In: *Proceedings of the International Congress of Mathematicians—Rio de Janeiro 2018. Vol. IV. Invited lectures*. World Sci. Publ., Hackensack, NJ, 2018, pp. 3093–3111. URL: https://www.math.ias.edu/~junehuh/ApplicationsHR.pdf.

[Jan06] S. Janson. "Conditioned Galton-Watson trees do not grow". In: *Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities*. Vol. AG. Discrete Math. Theor. Comput. Sci. Proc. Assoc. Discrete Math. Theor. Comput. Sci., Nancy, 2006, pp. 331–334. DOI: 10.46298/dmtcs.3483.

[Jan12] S. Janson. "Simply generated trees, conditioned Galton-Watson trees, random allocations and condensation: extended abstract". In: *23rd International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12)*. Vol. AQ. Discrete Math. Theor. Comput. Sci. Proc. Assoc. Discrete Math. Theor. Comput. Sci., Nancy, 2012, pp. 479–490. DOI: 10.1214/11-PS188.

[JN96] J. Jonasson and O. Nerman. "On maximum entropy πps-sampling with fixed sample size". Report 13, Chalmers University of Technology and Gothenburg University (1996). available at http://www.math.chalmers.se/Math/Research/Preprints/1996/13.pdf.

[Kar68] S. Karlin. *Total Positivity*. Total Positivity vol. 1. Stanford University Press, 1968.
[LPS08] R. Lyons, R. Peled, and O. Schramm. “Growth of the Number of Spanning Trees of the Erdős–Rényi Giant Component”. *Combinatorics, Probability and Computing* 17.5 (2008), pp. 711–726. doi: 10.1017/S0963548308009188.

[LW04] M. Luczak and P. Winkler. “Building uniformly random subtrees”. *Random Structures Algorithms* 24.4 (2004), pp. 420–443. doi: 10.1002/rsa.20011.

[MM78] A. Meir and J. W. Moon. “On the Altitude of Nodes in Random Trees”. *Canadian Journal of Mathematics* 30.5 (1978), pp. 997–1015. doi: 10.4153/CJM-1978-085-0.

[Nev86] J. Neveu. “Arbres et processus de Galton-Watson”. *Ann. Inst. H. Poincaré Probab. Statist.* 22.2 (1986), pp. 199–207.

[Pem00] R. Pemantle. “Towards a theory of negative dependence”. In: vol. 41. 3. Probabilistic techniques in equilibrium and nonequilibrium statistical physics. 2000, pp. 1371–1390. doi: 10.1063/1.533200. URL: https://doi.org/10.1063/1.533200.

[Pin09] A. Pinkus. *Totally Positive Matrices*. Cambridge Tracts in Mathematics. Cambridge University Press, 2009.

[PSZ23] M. Pétréolle, A. D. Sokal, and B.-X. Zhu. “Lattice paths and branched continued fractions: an infinite sequence of generalizations of the Stieltjes–Rogers and Thron-Rogers polynomials, with coefficientwise Hankel-total positivity”. *Mem. Amer. Math. Soc.* 291.1450 (2023), pp. v+154. doi: 10.1090/memo/1450.

[Sta89] R. P. Stanley. “Log-concave and unimodal sequences in algebra, combinatorics, and geometry”. In: *Graph theory and its applications: East and West (Jinan, 1986)*. Vol. 576. Ann. New York Acad. Sci. New York Acad. Sci., New York, 1989, pp. 500–535. doi: 10.1111/j.1749-6632.1989.tb16434.x.