#  The permuton limit of random recursive separable permutations

Valentin Féray1 Kelvin Rivera-Lopez2

(1 Université de Lorraine, CNRS, IECL, F-54000, Nancy, France,
<EMAIL_ADDRESS>
2 Gonzaga University<EMAIL_ADDRESS>)

###### Abstract

We introduce and study a simple Markovian model of random separable
permutations. Our first main result is the almost sure convergence of these
permutations towards a random limiting object in the sense of permutons, which
we call the recursive separable permuton. We then prove several results on
this new limiting object: a characterization of its distribution via a fixed-
point equation, a combinatorial formula for its expected pattern densities, an
explicit integral formula for its intensity measure, and lastly, we prove that
its distribution is absolutely singular with respect to that of the Brownian
separable permuton, which is the large size limit of uniform random separable
permutations.

##  Introduction

###  1.1 Our model

Fix $p\in(0,1)$. We consider a sequence of random permutations
$(\sigma^{(n),p})_{n\geq 1}$ starting from the unique permutation of $1$ and
defined recursively. Given $\sigma^{(n),p}$, a permutation of $n$, we obtain
$\sigma^{(n+1),p}$, a permutation of $n+1$, by the following procedure.

  1. 1.

Take $j$ uniformly at random between $1$ and $n$.

  2. 2.

In the one line notation of $\sigma^{(n),p}$, we increase all values bigger
than $j$ by $1$.

  3. 3.

With probability $p$ (resp. $1-p$), we replace $j$ by $j,\,j\\!+\\!1$ (resp.
by $j\\!+\\!1,\,j$).

An example is given on Fig. 1, where permutations are represented by their
diagrams (the diagram of a permutation $\pi$ of $n$ is the set of dots
$(j,\pi(j))$ drawn in an $n\times n$ grid). This operation of replacing a
point in the diagram by two consecutive points (consecutive at the same time
in value and in position) will be referred to as inflation. We call the
inflation increasing or decreasing, depending on the relative position of the
two new points.

Figure 1: Examples of an inflation step from $\tau:=\sigma^{(n),p}$ to
$\rho:=\sigma^{(n+1),p}$. For $i=1$ or $2$, the point of $\tau_{i}$ chosen
uniformly at random, as well as the two new adjacent points in $\rho_{i}$
replacing it, are painted in red. In $\rho_{1}$, these two new points are in
increasing order (we say that we have performed an increasing inflation),
while, in $\rho_{2}$, they are in decreasing order (in this case, we have
performed a decreasing inflation).

The set of permutations which can be obtained from the permutation $1$ by
repeated inflations (either increasing or decreasing) is known as the set of
separable permutations. Alternatively, separable permutations are those
permutations that avoid the patterns $3142$ and $2413$, see, e.g., [BBL98]. By
construction, the permutations $(\sigma^{(n),p})_{n\geq 1}$ are separable and
any given separable permutation will appear in this sequence with nonzero
probability. We therefore refer to $\sigma^{(n),p}$ as the _random recursive
separable permutation (of size $n$ and parameter $p$)_. This model differs
from the model of uniform random separable permutations (studied, e.g. in
[BBF+18, Pin21]) and, as we will see in Proposition 1.4, it yields a different
object in the limit.

######  Remark 1.1.

It was asked in a recent survey on permutons whether uniform separable
permutations can be sampled in a Markovian way [Grü22, Section 5.4]. Though we
do not answer this question here, this served as an additional motivation to
study a natural Markovian model of random separable permutations.

######  Remark 1.2.

Our work can be compared to that of Curien and LeGall [CLG11], who consider
recursive models of random noncrossing sets of chords in a regular $n$-gon. As
$n$ tends to infinity, these random sets converge to a random limiting object
$L_{\infty}$. This random set $L_{\infty}$ is different from the limit of
uniform random triangulations of the $n$-gon, previously identified by Aldous
and known as the Brownian triangulation [Ald94]. Our work shows that the same
is true for separable permutations – namely, that uniform and recursive models
can lead to two different, nontrivial limit objects.

###  1.2 The limiting permuton

Throughout the paper, let $\operatorname{Leb}$ be the Lebesgue measure on
$[0,1]$. Recall that if $\nu$ is a measure on $A$ and $g$ is a measurable map
from $A$ to $B$, then the formula $g_{\\#}\nu(C)=\nu(g^{-1}(C))$ for any
measurable subset $C$ of $B$ defines a measure $g_{\\#}\nu$ on $B$, called the
push-forward measure. Finally, we denote by $\pi_{1}$ and $\pi_{2}$ the
projection map from $[0,1]^{2}$ to $[0,1]$ on the first and second
coordinates, respectively.

By definition, a permuton is a probability measure $\mu$ on the unit square
$[0,1]^{2}$ whose projections on the horizontal and vertical axes are both
uniform, i.e. $(\pi_{1})_{\\#}\mu=(\pi_{2})_{\\#}\mu=\operatorname{Leb}$.
Permutons are natural limit objects for permutations of large sizes, see
[Grü22] for a recent survey on the topic. Indeed, we can encode a permutation
$\pi$ of $n$ by a permuton
$\mu_{\pi}=\frac{1}{n}\sum_{i=1}^{n}\lambda(i,\pi(i))$, where
$\lambda(i,\pi(i))$ is the measure of mass $1$ uniformly spanned on the square
$[\frac{i-1}{n};\frac{i}{n}]\times[\frac{\pi(i)-1}{n};\frac{\pi(i)}{n}]$.
Equivalently, $\mu_{\pi}$ has a piecewise constant density

$g(x,y)=\begin{cases}n&\text{ if }\pi(\lceil nx\rceil)=\lceil ny\rceil;\\\
0&\text{ otherwise.}\end{cases}$

A sequence of permutations $\pi^{(n)}$ then converges to a permuton $\mu$ if
the associated measures $\mu_{\pi^{(n)}}$ converge to $\mu$, in the sense of
the weak convergence of measures. We can now state the first main result of
this paper.

######  Theorem 1.3.

The random permutations $(\sigma^{(n),p})_{n\geq 1}$ converge a.s. to a random
permuton. We call this permuton the recursive separable permuton (of parameter
$p$) and denote it by $\bm{\mu}^{\text{\tiny rec}}_{p}$.

A sample of $\sigma^{(n),p}$ for $n\in\\{10,100,1000\\}$ and $p=1/2$ is given
in Fig. 2. In this simulation, the three permutations are taken from the same
realization of the random process $(\sigma^{(n),p})_{n\geq 1}$. The a.s.
convergence towards a limiting permuton is visible on this simulation.

Figure 2: A sample of permutations $\sigma^{(10),{\,0.5}}$,
$\sigma^{(100),{\,0.5}}$, $\sigma^{(1000),{\,0.5}}$ corresponding to the same
realization of the process $(\sigma^{(n),{\,0.5}})_{n\geq 1}$.

This theorem should be compared with the limit result for uniform random
separable permutations obtained in [BBF+18]. In the latter case, the limit is
the so-called Brownian separable permuton. This Brownian separable permuton
belongs to the larger family of biased Brownian separable permutons, also
indexed by a parameter $p$ in $(0,1)$, and denoted $\bm{\mu}^{\text{\tiny
Br}}_{p}$ (we will often drop the word biased in the latter).

The constructions of the recursive and Brownian separable permutons share some
similarities, but these are different distributions on the set of permutons.
In fact, we prove in Section 4.4 the following stronger statement.

######  Proposition 1.4.

Let $p\neq q$ be fixed in $(0,1)$. Then the distributions of the four
permutons $\bm{\mu}^{\text{\tiny rec}}_{p}$, $\bm{\mu}^{\text{\tiny
rec}}_{q}$, $\bm{\mu}^{\text{\tiny Br}}_{p}$ and $\bm{\mu}^{\text{\tiny
Br}}_{q}$ are pairwise singular111We recall that two measures $\mu$ and $\nu$
are singular if there exists a measurable set $A$ such that $\mu(A)=1$ but
$\nu(A)=0$..

Thus our model of increasing separable permutations yields a much different
limiting object than the uniform separable permutations. This is in contrast
with the result of [BBF+20], where the Brownian separable permuton was shown
to be the limit of uniform random permutations in many permutation classes. It
seems that going from the uniform model to a Markovian model as the one
studied here allows to escape the universality class of the Brownian separable
permuton.

Another difference with the setting of uniform permutations is that the
convergence in Theorem 1.3 holds in the almost sure sense. In particular, we
cannot use the criterium stating that convergence of permutons in distribution
is equivalent to the convergence of expected pattern densities. Instead, we
need to construct the limiting permuton on the same probability space as the
process $(\sigma^{(n),p})_{n\geq 1}$ of random permutations and to prove the
convergence with adhoc arguments.

######  Remark 1.5.

In the theory of permutons (see, e.g., [HKM+13, Lemma 4.2]), there is an
explicit construction for permutations that converge almost surely to a given
permuton. It is natural to compare the permutations obtained by applying this
construction to the random permuton $\bm{\mu}^{\text{\tiny rec}}_{p}$ with the
recursive separable permutations. As sequences, these two objects are clearly
different: the recursive separable permutations are constructed via repeated
inflations while the other sequence is not. However, we shall see in Section
4.2 that these sequences do have the same marginal distributions.

###  1.3 Properties of the recursive separable permuton

####  1.3.1 Self-similarity

The distribution of the recursive separable permuton $\bm{\mu}^{\text{\tiny
rec}}_{p}$ can be characterized by a fixed-point equation. To state this
property, we first need to introduce some notation.

Given two permutons $\mu$ and $\nu$, a real number $u$ in $[0,1]$ and a sign
$S$ in $\\{\oplus,\ominus\\}$, we construct a new permuton
$\rho=\mu\otimes_{(u,S)}\nu$ as follows. If $S=\oplus$, we let $\rho$ be
supported on $[0,u]^{2}\cup[u,1]^{2}$ such that the restriction
$\rho|_{[0,u]^{2}}$ (resp. $\rho|_{[u,1]^{2}}$) is a rescaled version of $\mu$
of total weight $u$ (resp. a rescaled version of $\nu$ of total weight $1-u$).
If $S=\ominus$, then $\rho$ is defined similarly, but is supported on
$[0,u]\times[1-u,1]\cup[u,1]\times[0,1-u]$. We refer to Fig. 3 for an
illustration.

Figure 3: The permuton $\mu\otimes_{(u,S)}\nu$.

Now, given a random permuton $\bm{\mu}$, we denote by $\Phi_{p}(\bm{\mu})$ the
random permuton $\bm{\mu}_{0}\otimes_{(U,S)}\bm{\mu}_{1}$, where
$\bm{\mu}_{0}$ and $\bm{\mu}_{1}$ are two copies of $\bm{\mu}$, $U$ is a
uniform r.v. in $[0,1]$ and $S$ is a random sign in $\\{\oplus,\ominus\\}$
with $\mathbb{P}(S=\oplus)=p$, all variables $\bm{\mu}_{0}$, $\bm{\mu}_{1}$,
$U$ and $S$ being independent.

######  Proposition 1.6.

For any $p$ in $[0,1]$, we have $\bm{\mu}^{\text{\tiny
rec}}_{p}\stackrel{{\scriptstyle d}}{{=}}\Phi_{p}(\bm{\mu}^{\text{\tiny
rec}}_{p})$. Moreover, the distribution of $\bm{\mu}^{\text{\tiny rec}}_{p}$
is characterized by this property, in the following sense: if a random
permuton $\nu$ satisfy $\nu\stackrel{{\scriptstyle d}}{{=}}\Phi_{p}(\nu)$,
then $\nu\stackrel{{\scriptstyle d}}{{=}}\bm{\mu}^{\text{\tiny rec}}_{p}$.

####  1.3.2 Expected pattern densities

We recall that if $\pi$ is a pattern (i.e. a permutation) of size $k$ and
$\mu$ a permuton, we can define the random permutation
$\operatorname{Sample}(\mu;k)$ and the pattern density
$\operatorname{dens}(\pi,\mu)$ of $\pi$ in $\mu$ as follows. Let
$(x_{i},y_{i})$ be i.i.d. points in $[0,1]^{2}$ with distribution $\mu$. We
reorder them as $(x_{(1)},y_{(1)})$,…, $(x_{(k)},y_{(k)})$ such that
$y_{(1)}<\dots<y_{(k)}$. Then there exists a unique (random) permutation
$\tau$ such that $x_{(\tau_{1})}<\dots<x_{(\tau_{k})}$. This random
permutation $\tau$ is denoted $\operatorname{Sample}(\mu;k)$. We also write

$\operatorname{dens}(\pi,\mu)=\mathbb{P}\big{(}\operatorname{Sample}(\mu;k)=\pi\big{)}.$

These functionals plays a key role in the theory of permutons. In particular,
convergence of permutons is equivalent to convergence of all pattern
densities, see [HKM+13]. Also the distribution of a random permuton is
uniquely determined by its expected pattern densities [BBF+20, Proposition
2.4]. The next proposition provides combinatorial descriptions of these
expected pattern densities in the case of the recursive separable permuton.

To state it, we introduce some terminology. Let $\pi$ and $\sigma$ be two
permutations of respective sizes $k$ and $\ell$. Their _direct sum_ and _skew
sum_ are the permutations of $k+\ell$ defined in one-line notation as follows

$\displaystyle\pi\oplus\sigma=$
$\displaystyle\pi_{1}\ldots\pi_{k}(\sigma_{1}+k)\ldots(\sigma_{\ell}+k);$
$\displaystyle\pi\ominus\sigma=$
$\displaystyle(\pi_{1}+\ell)\ldots(\pi_{k}+\ell)\sigma_{1}\ldots\sigma_{\ell}.$

Examples with $k=3$ and $\ell=2$ are provided in Fig. 4. They illustrate the
graphical interpretation of these operations on permutation diagrams.

Figure 4: Direct sum and skew sum of permutations.

In the following, we consider rooted (complete) binary trees, meaning that
every internal node has exactly two ordered children. Additionally, internal
nodes are labeled with numbers from $1$ to some $k$ (where each integer in
this range is used exactly once). The tree is said to be increasing if labels
are increasing on any path from the root to a leaf. Finally, each internal
node carries a decoration, which is either $\oplus$ or $\ominus$. To such a
tree $T$, we associate a permutation $\sigma=\operatorname{Perm}(T)$ as
follows (an example of a rooted increasing binary tree and the associated
permutation is given in Fig. 5).

Figure 5: A rooted increasing binary tree and the associated permutation. The
permutation associated to the left subtree of the root is $4132$, the one
associated to its right-subtree $1243$. Since the root has decoration
$\oplus$, the permutation associated to the whole tree is $4132\oplus 1243$,
which is equal to $41325687$.

  * •

If $T$ is reduced to a single leaf, then $\sigma$ is the one-element
permutation $1$.

  * •

Otherwise, the root of $T$ has two (ordered) children and we call $T_{1}$ and
$T_{2}$ the subtree rooted at these children. Let $\sigma_{1}$ and
$\sigma_{2}$ be the permutations associated with $T_{1}$ and $T_{2}$. Then we
associate $\sigma_{1}\otimes\sigma_{2}$ with $T$, where $\otimes$ is the
decoration of the root of $T$ ($\otimes\in\\{\oplus,\ominus\\}$).

We note that $\operatorname{Perm}(T)$ does not depend on the labeling of the
internal nodes of $T$ (only on the shape of $T$ and on the decorations of its
internal nodes). By construction, $\operatorname{Perm}(T)$ is always a
separable permutation. A separable permutation $\sigma$ is in general
associated with more than one tree $T$. We note that, except for the labeling
of internal nodes of $T$, this is a standard construction in the theory of
separable permutations, see, e.g., [BBL98].

######  Proposition 1.7.

For any pattern $\pi$ of size $n$, we have

$\mathbb{E}\big{[}\operatorname{dens}(\pi,\bm{\mu}^{\text{\tiny
rec}}_{p})\big{]}=\mathbb{P}\big{[}\sigma^{(n),p}=\pi\big{]}=\frac{N_{inc}(\pi)}{(n-1)!}\,(1-p)^{\operatorname{des}(\pi)}\,p^{n-1-\operatorname{des}(\pi)},$

where $\operatorname{des}(\pi)$ is the number of descents in $\pi$ and
$N_{inc}(\pi)$ the number of increasing binary trees $T$ such that
$\operatorname{Perm}(T)=\pi$.

If $\pi$ is not a separable pattern, then $N_{inc}(\pi)=0$, implying
$\operatorname{dens}(\pi,\bm{\mu}^{\text{\tiny rec}}_{p})=0$ a.s.

######  Remark 1.8.

The fact that $\operatorname{dens}(\pi,\bm{\mu}^{\text{\tiny rec}}_{p})=0$
a.s. for non-separable patterns $\pi$ implies that the distribution of
$\bm{\mu}^{\text{\tiny rec}}_{p}$ is also singular with respect to that of the
so-called skew Brownian permutons $\mu_{\rho,q}$ with parameter $(\rho,q)$ in
$(-1,1)\times(0,1)$. Indeed, the latter satisfy
$\operatorname{dens}(\pi,\bm{\mu}^{\text{\tiny rec}}_{p})>0$ a.s., see
[BHSY23, Theorem 1.10].

####  1.3.3 The intensity measure

Permutons are measures, so that random permutons are random measures. Given a
random measure $\bm{\mu}$, one can define its intensity measure $I\bm{\mu}$,
sometimes also denoted $\mathbb{E}\bm{\mu}$ as follows: for any measurable set
$A$ of the ground space, we have $I\bm{\mu}(A)=\mathbb{E}[\bm{\mu}(A)]$.

Our next result is a simple description of the intensity measure of the random
permuton $\bm{\mu}^{\text{\tiny rec}}_{p}$ in terms of beta distributions.
Recall that the distribution $\beta(a,b)$ with positive parameters $a$ and $b$
is given by

$\frac{\Gamma(a+b)}{\Gamma(a)\,\Gamma(b)}x^{a-1}(1-x)^{b-1}\,dx.$

######  Proposition 1.9.

The intensity measure $I\bm{\mu}^{\text{\tiny rec}}_{p}$ of the recursive
separable permuton is the distribution of

$(U,\,UX_{p}+(1-U)X^{\prime}_{p}),$

where $U$, $X_{p}$ and $X^{\prime}_{p}$ are independent random variables in
$[0,1]$, with distribution $\operatorname{Leb}$, $\beta(p,1-p)$ and
$\beta(1-p,p)$ respectively.

From this, we can get an explicit formula for the density of
$I\bm{\mu}^{\text{\tiny rec}}_{p}$.

######  Corollary 1.10.

$I\bm{\mu}^{\text{\tiny rec}}_{p}$ is absolutely continuous with respect to
Lebesgue measure on $[0,1]^{2}$ and has density

$\frac{1}{\Gamma(p)^{2}\Gamma(1-p)^{2}}\,\int_{\max(x+y-1,0)}^{\min(x,y)}\frac{dz}{z^{1-p}(x-z)^{p}(y-z)^{p}(1-x-y+z)^{1-p}}.$

Fig. 6 shows 3D plots of the density of $I\bm{\mu}^{\text{\tiny rec}}_{p}$ for
$p=0.5$ and $p=0.6$ (obtained with Mathematica). We note that the density
diverges for $x=y$ when $p\geq 1/2$ and for $x+y=1$ when $p\leq 1/2$. This is
different from the Brownian separable permuton case where the density of the
intensity measure diverges in the corners (i.e. when both $x$ and $y$ are $0$
or $1$; see [Maa20] for an explicit formula for the density in this case).

Figure 6: 3D plots of the density of $I\bm{\mu}^{\text{\tiny rec}}_{p}$ for
$p=0.5$ (left) and $p=0.6$ (right).

We conclude this paragraph with a discussion presenting the intensity measure
of the recursive separable permuton as a limit of a natural discrete object.
This interpretation is a motivation for computing the intensity measure, and
is not needed later in the article. Note also that this is not specific to the
recursive separable permutation; a similar discussion could be made for other
models of permutations converging to random permutons.

For $n\geq 1$ and $N\geq 1$, let $\sigma^{(n),p}_{1}$, …, $\sigma^{(n),p}_{N}$
be independent copies of the recursive random separable permutation
$\sigma^{(n),p}$. We then consider the average of the associated permutons:

$\mu^{(n),p}_{N}=\frac{1}{N}\sum_{i=1}^{N}\mu_{\sigma^{(n),p}_{i}}.$ (1)

This is a measure on $[0,1]^{2}$ with piecewise constant density

$g^{(n),p}_{N}(x,y)=\frac{n}{N}\sum_{i=1}^{N}\mathbbm{1}\Big{[}\sigma^{(n),p}_{i}\big{(}\lceil
nx\rceil\big{)}=\lceil ny\rceil\Big{]}.$

When $N$ tends to infinity, $\mu^{(n),p}_{N}$ converges to
$I\,\mu_{\sigma^{(n),p}}$, the intensity measure of the random permuton
associated to $\sigma^{(n),p}$. This measure $I\,\mu_{\sigma^{(n),p}}$ in turn
converges to $I\,\bm{\mu}^{\text{\tiny rec}}_{p}$ as $n$ tends to $+\infty$,
as a consequence of Theorem 1.3. Therefore, for large $n$ and $N$ with $N\gg
n$, the empirical average measures $\mu^{(n),p}_{N}$ defined in (1) can be
seen as a discrete approximation of $I\,\bm{\mu}^{\text{\tiny rec}}_{p}$. On
Fig. 7, we plot the density $g^{(n),p}_{N}$ for $n=200$, $N=10000$ and
$p\in\\{.5,.6\\}$. The convergence to that of $I\,\bm{\mu}^{\text{\tiny
rec}}_{p}$ (Fig. 6) is plausible on the pictures.

Figure 7: 3D plots of the density $g^{(n),p}_{N}$ for $n=200$, $N=10000$ and
$p$ being either $0.5$ (left) or $0.6$ (right).

###  1.4 Analog results for cographs

With a permutation $\sigma$ of $n$, it is standard to associate its inversion
graph $G_{\sigma}$ on vertex set $\\{1,\dots,n\\}$. By definition, $\\{i,j\\}$
is an edge of $G_{\sigma}$ if and only if it is an inversion in $\sigma$, i.e.
if and only if $(i-j)(\sigma(i)-\sigma(j))<0$. Inversion graphs of separable
permutation are called cographs. Cographs can alternatively be described as
graphs avoiding the path $P_{4}$ on four vertices as induced subgraph, or as
graphs that can be obtained starting from single vertex graphs and iterating
“disjoint union” and “taking the complement” operations. We refer to the
introduction of [BBF+22] for more background on cographs.

Uniform random cographs have recently been studied in [Stu21, BBF+22, BBD+22].
Considering the inversion graphs of random recursive separable permutations
yields a natural Markovian model of random cographs. It can be described
directly on graphs, without going through permutations.

Namely, we consider a sequence of random graphs $(G^{(n),p})_{n\geq 1}$
starting from the unique graph with one vertex and defined recursively. Given
$G^{(n),p}$, a graph with $n$ vertices, we obtain $G^{(n+1),p}$, a graph with
$n+1$ vertices, by the following procedure.

  1. 1.

Let $v$ be a uniform random vertex of $G^{(n),p}$.

  2. 2.

Add a new vertex $v^{\prime}$ to $G^{(n),p}$, with the same set of neighbours
as $v$.

  3. 3.

With probability $1-p$, we connect $v$ and $v^{\prime}$ with an edge.

Figure 8: A sample of graphs $G^{(10),{\,0.5}}$, $G^{(100),{\,0.5}}$,
$G^{(1000),{\,0.5}}$ corresponding to the same realization of the process
$(G^{(n),{\,0.5}})_{n\geq 1}$.

A simulation of this random graph process for $p=1/2$ is shown on Fig. 8. Here
graphs are represented by a collection of dots, namely two dots at coordinates
$(i,j)$ and $(j,i)$ for each edge $\\{i,j\\}$ in the graph (in some sense,
this is a pictorial version of the adjacency matrix of the graph). We now
state a convergence result for $G^{(n),p}$, which is the analogue of Theorem
1.3. We assume the reader to be familiar with the notion of graphon
convergence.

######  Theorem 1.11.

The random graphs $(G^{(n),p})_{n\geq 1}$ converge a.s. to a random graphon,
which we call recursive cographon (of parameter $p$) and denote by
$\bm{W}^{\text{\tiny rec}}_{p}$.

A representative of the limiting graphon $\bm{W}^{\text{\tiny rec}}_{p}$ can
be constructed using the random order $\prec$ on $[0,1]$, which we define
later in Section 3. Namely, for $x<y$ in $[0,1]$ we set

$\bm{W}^{\text{\tiny rec}}_{p}(x,y)=\bm{W}^{\text{\tiny
rec}}_{p}(y,x)=\begin{cases}0&\text{ if }x\prec y;\\\ 1&\text{ if }y\prec
x.\end{cases}$

Moreover, $\bm{W}^{\text{\tiny rec}}_{p}$ has the following properties, which
are analogues of Propositions 1.4, 1.6 and 1.7.

######  Proposition 1.12.

Let $p\neq q$ be fixed in $(0,1)$. Then the distributions of the four random
graphons $\bm{W}^{\text{\tiny rec}}_{p}$, $\bm{W}^{\text{\tiny rec}}_{q}$,
$\bm{W}^{\text{\tiny Br}}_{p}$ and $\bm{W}^{\text{\tiny Br}}_{q}$ are pairwise
singular, where $\bm{W}^{\text{\tiny Br}}_{p}$ is the Brownian cographon of
parameter $p$ introduced in [Stu21, BBF+22].

######  Proposition 1.13.

Fix $p$ in $[0,1]$, and let $W_{1}$ and $W_{2}$ be independent copies of
$\bm{W}^{\text{\tiny rec}}_{p}$. Let also $U$ be a uniform random variable in
$[0,1]$ and $S$ be a Bernoulli random variable of parameter $1-p$, independent
from each other and from $(W_{1},W_{2})$. We define a graphon $W$ by

$W(x,y)=\begin{cases}W_{1}(x/U,y/U)&\text{ if }x,y\leq U;\\\
W_{2}((x-U)/(1-U),(y-U)/(1-U))&\text{ if }x,y>U;\\\ S&\text{ if }x\leq
U<y\text{ or }y\leq U<x.\end{cases}$

Then $W$ has the same law as $\bm{W}^{\text{\tiny rec}}_{p}$. Moreover the law
of $\bm{W}^{\text{\tiny rec}}_{p}$ is characterized by this property.

For the last statement, we write $\operatorname{dens}(H,W)$ for the (induced)
density of $H$ in a graphon $W$. We also recall that cographs can be encoded
by decorated trees called cotrees, see, e.g., [BBF+22, Section 2.2]. Here, we
will consider cotrees where internal nodes are labeled by integers from $1$ to
some $k$, and say that a cotree is increasing if labels are increasing from
the root to the leaves.

######  Proposition 1.14.

For any graph $H$ of size $n$, we have

$\mathbb{E}\big{[}\operatorname{dens}(H,\bm{W}^{\text{\tiny
rec}}_{p})\big{]}=\mathbb{P}\big{[}G^{(n),p}=H\big{]}=\frac{N_{inc}(H)}{(n-1)!}\,p^{Z(H)}\,(1-p)^{n-1-Z(H)},$

where $N_{inc}(H)$ the number of increasing binary cotrees $T$ encoding $H$,
and $Z(H)$ is the number of decorations $0$ in any binary cotree encoding $H$.

All these results are easily obtained, either by applying the inversion graph
mapping to the permutation results, or by adapting the proofs. Since the space
of graphons has no natural convex structure, there is no natural notion of
expectation of the random graphon $\bm{W}^{\text{\tiny rec}}$, and 1.9 and
Corollary 1.10 have no analogues for $\bm{W}^{\text{\tiny rec}}$.

###  1.5 Outline of the paper

The remainder of this paper is organized as follows. In Section 2, we discuss
some background material that is needed later. In Section 3, we go through an
explicit construction of the recursive separable permuton and prove Theorem
1.3. In Section 4, we investigate the properties of the recursive separable
permuton and prove all of our other results.

##  Background

This section gathers some material needed in the rest of the paper. The first
two items (permutation patterns and the Wasserstein metric) consist of
standard material. The last item (push-forward permutons) is more specific to
this project.

###  2.1 Permutation patterns.

If $\sigma$ is a permutation of $n$ and $I$ a subset of $\\{1,\dots,n\\}$ with
$k$ elements, then the pattern induced by $\sigma$ on the set of positions $I$
is the unique permutation $\tau=\operatorname{pat}_{I}(\sigma)$ of $k$ with
the following property: writing $I=\\{i_{1},\dots,i_{k}\\}$ with
$i_{1}<\dots<i_{k}$, we have, for all $g,h\leq k$,

$\sigma(i_{g})<\sigma(i_{h})\ \Leftrightarrow\ \tau(g)<\tau(h).$

In other words, $\tau$ is obtained by considering the subsequence
$\sigma(i_{1})\,\sigma(i_{2})\,\ldots\,\sigma(i_{k})$ of $\sigma$ and
replacing the smallest element by $1$, the second smallest by $2$, and so on.
For example, the pattern induced by $3\,2\,5\,6\,4\,7\,1$ on positions
$\\{2,3,5\\}$ is $132$.

###  2.2 Wasserstein metric.

Some arguments in Sections 4.1 and 4.3 use the notion of the Wasserstein
distance between probability distributions. We briefly recall some main facts
about it.

Let $X$ be a complete metric space with distance $d_{X}$. For each $p\geq 1$,
consider the space $\mathcal{M}^{p}_{1}(X)$ of probability measures on $X$
with a finite $p$-th moment. This space can be endowed with the so-called
$p$-th Wasserstein distance (also called the optimal cost distance or the
Kantorovich-Rubinstein distance):

$d_{W,p}(\nu,\nu^{\prime})^{p}\hskip
1.0pt\raisebox{0.4pt}{:}=\inf_{\begin{subarray}{c}\bm{X},\bm{X}^{\prime}:\\\
\bm{X}\sim\nu,\,{\bm{X}^{\prime}}\sim\nu^{\prime}\end{subarray}}\mathbb{E}[d_{X}(\bm{X},{\bm{X}^{\prime}})^{p}],$

where the infimum is taken over all pairs $(\bm{X},{\bm{X}^{\prime}})$ of
random variables defined on the same probability space with distributions
$\nu$ and $\nu^{\prime}$, respectively. It is well-known that this defines a
metric on $\mathcal{M}^{p}_{1}(X)$; see, e.g., [CD08].

In this article, we will be interested in the cases $X=[0,1]$ and
$X=[0,1]^{2}$. In these cases, and more generally whenever $X$ is compact, we
have $\mathcal{M}^{p}_{1}(X)=\mathcal{M}_{1}(X)$ for all $p$. Also,
convergence in the Wasserstein metric is equivalent to the weak convergence of
measures (in general, on non necessarily compact spaces, it is equivalent to
weak convergence and convergence of the $p$-th moment). In particular, it is
sometimes fruitful to think of permuton convergence as convergence for the
(first) Wasserstein distance.

###  2.3 Push-forward permutons.

Given a function $f:[0,1]\to[0,1]$, we can consider the measure
$\mu_{f}:=(\,\cdot\,,f(\,\cdot\,))_{\\#}\operatorname{Leb}$ on $[0,1]^{2}$,
i.e. the push-forward of the Lebesgue measure on $[0,1]$ by the map
$x\mapsto(x,f(x))$. The projection of $\mu_{f}$ on the first coordinate is
always the Lebesgue measure on $[0,1]$, while its projection on the second
coordinate is $f_{\\#}\operatorname{Leb}$. Thus, if $f$ preserves the Lebesgue
measure, then $\mu_{f}$ is a permuton. Such permutons will be referred here as
push-forward permutons. Both the recursive and the Brownian separable
permutons are push-forward permutons (for random functions $f$).

The permuton $\mu_{\pi}$ associated to a permutation is not a push-forward
permuton. We can, however, approximate it by a push-forward measure easily.
Given a permutation $\pi$ of $n$, let us define the function
$f_{\pi}\colon[0,1]\to[0,1]$ by $f_{\pi}(0)=0$ and, for $x>0$,

$f_{\pi}(x)=\frac{\pi(\lceil nx\rceil)}{n}.$

We also write
$\hat{\mu}_{\pi}=\mu_{f_{\pi}}=(\,\cdot\,,f_{\pi}(\,\cdot\,))_{\\#}\operatorname{Leb}.$
The measure $\hat{\mu}_{\pi}$ is not a permuton (its projection on the
$y$-axis is not uniform), but it resembles the permuton $\mu_{\pi}$: while
$\mu_{\pi}$ has, for each $i$, a mass $1/n$ uniformly distributed on the
square
$[\frac{i-1}{n};\frac{i}{n}]\times[\frac{\pi(i-1)}{n};\frac{\pi(i)}{n}]$, the
measure $\hat{\mu}_{\pi}$ has the same mass distributed on the segment
$[\frac{i-1}{n};\frac{i}{n}]\times\big{\\{}\frac{\pi(i)}{n}\big{\\}}$. This
clearly implies

$d_{W,1}\left(\hat{\mu}_{\pi},\mu_{\pi}\right)\leq\frac{1}{n}$ (2)

for any permutation $\pi$ of $n$. It follows that, given a sequence of
permutations $\pi^{(n)}$ of increasing size, the sequences
$\\{\hat{\mu}_{\pi^{(n)}}\\}_{n\geq 1}$ and $\\{\mu_{\pi^{(n)}}\\}_{n\geq 1}$
have the same limit points in $\mathcal{M}_{1}([0,1]^{2})$.

We end this section with a convergence criterium for push-forward measures
$\mu_{f}$, which will be used in the proof of our main result. Since
particular cases of push-forward permutons have been studied in the literature
[BBF+18, Bor21, BGS22], it might also be useful in other contexts. We also
refer the reader to a paper of Bhattacharya and Mukherjee [BM17], for a
related result connecting pointwise convergence of random permutations seen as
functions, and convergence of the associated random permutons.

######  Proposition 2.1.

Let $f,f_{1},f_{2},\ldots$ be measurable functions on $[0,1]$ with values in
$[0,1]$. Then the following statements are equivalent:

  1. (i)

$f_{n}\to f$ in $L^{p}$ for some $p\in[1,\infty)$,

  2. (ii)

$f_{n}\to f$ in $L^{p}$ for all $p\in[1,\infty)$,

  3. (iii)

$(\,\cdot\,,f_{n}(\,\cdot\,))_{\\#}\operatorname{Leb}\to(\,\cdot\,,f(\,\cdot\,))_{\\#}\operatorname{Leb}$
weakly.

###### Proof.

We first assume (i), i.e. that $\|f_{n}-f\|_{p}\to 0$ for some
$p\in[1,\infty)$. Applying Hölder’s inequality with
$\frac{1}{q}=1-\frac{1}{p}$, we obtain the convergence in $L^{1}$:

$\|f_{n}-f\|_{1}\leq\|f_{n}-f\|_{p}\|1\|_{q}.$

Now let $r\geq 1$. Since each $|f_{n}-f|$ takes its values in $[0,1]$, we have
that

$\|f_{n}-f\|_{r}^{r}=\int_{0}^{1}|f_{n}(x)-f(x)|^{r}dx\leq\int_{0}^{1}|f_{n}(x)-f(x)|dx=\|f_{n}-f\|_{1},$

establishing (ii).

Suppose now that $\|f_{n}-f\|_{p}\to 0$ for all $p\in[1,\infty)$. Let
$u\colon[0,1]\to\mathbb{R}$ be continuous, $v\colon[0,1]\to\mathbb{R}$ be
Lipschitz continuous, say with Lipschitz constant $L$, and set
$w(x,y)=u(x)v(y)$. Then

$\displaystyle\left|(\,\cdot\,,f_{n}(\,\cdot\,))_{\\#}\operatorname{Leb}(w)-(\,\cdot\,,f(\,\cdot\,))_{\\#}\operatorname{Leb}(w)\right|$
$\displaystyle=\left|\int_{0}^{1}u(x)\,(v(f_{n}(x))-v(f(x)))\,dx\right|$
$\displaystyle\leq\int_{0}^{1}\|u\|_{\infty}\,|v(f_{n}(x))-v(f(x))|\,dx$
$\displaystyle\leq\int_{0}^{1}\|u\|_{\infty}\,L|f_{n}(x)-f(x)|\,dx$
$\displaystyle=\|u\|_{\infty}L\|f_{n}-f\|_{1}.$

This upper bound tends to $0$ as $n\to\infty$, and thus the left-hand side
also does. This convergence then extends to any continuous function $w$ on
$[0,1]^{2}$, establishing (iii).

Finally, suppose that
$(\,\cdot\,,f_{n}(\,\cdot\,))_{\\#}\operatorname{Leb}\to(\,\cdot\,,f(\,\cdot\,))_{\\#}\operatorname{Leb}$
weakly. Then, as $n\to\infty$, we have the convergence

$\int_{0}^{1}u(x)\,(v(f_{n}(x))-v(f(x)))\,dx\longrightarrow 0,$

for all continuous function $u,v$ on $[0,1]$. However, a density argument
shows that $u$ can also be taken from $L^{1}[0,1]$. Recalling that $f\in
L^{1}[0,1]$, we can apply the above to $u_{1}(x)\equiv 1$, $v_{1}(y)=y^{2}$,
$u_{2}(x)=f(x)$, and $v_{2}(y)=y$. We get

$\displaystyle\|f_{n}-f\|_{2}^{2}$
$\displaystyle=\int_{0}^{1}(f_{n}(x)-f(x))^{2}\,dx$
$\displaystyle=\int_{0}^{1}f_{n}^{2}(x)-f^{2}(x)-2f(x)(f_{n}(x)-f(x))\,dx$
$\displaystyle=\int_{0}^{1}u_{1}(x)\,(v_{1}(f_{n}(x))-v_{1}(f(x)))\,dx-2\int_{0}^{1}u_{2}(x)\,(v_{2}(f_{n}(x))-v_{2}(f(x)))\,dx$
$\displaystyle\longrightarrow 0$

as $n\to\infty$. This establishes (i) and concludes the proof. ∎

##  Construction and convergence

In this section, we construct the recursive separable permutations and the
recursive separable permuton on a common probability space and establish the
almost sure convergence of the permutations to the permuton.

Fix $p$ in $(0,1)$. Throughout the section, we consider two independent random
i.i.d. sequences $(U_{j})_{j\geq 1}$ and $(S_{j})_{j\geq 1}$, where the
$U_{j}$ are uniform in $[0,1]$ and the $S_{j}$ are random signs in
$\\{\oplus,\ominus\\}$ with $\mathbb{P}(S_{j}=\oplus)=p$. For convenience, the
signs $\oplus$ and $\ominus$ will often be regarded as $1$ and $-1$,
respectively, and we set $U_{0}=0$ and $U_{-1}=1$.

###  3.1 The Glivenko-Cantelli theorem and some consequences

We consider the following objects, for any $n\geq 1$:

  * •

the ordered statistics of $\\{U_{-1},U_{0},\ldots,U_{n}\\}$,

$0=U_{(0,n)}\leq U_{(1,n)}\leq\ldots\leq U_{(n,n)}\leq U_{(n+1,n)}=1;$

  * •

the length of the largest interval in
$[0,1]\setminus\\{U_{1},\ldots,U_{n}\\}$,

$\Delta_{n}=\max_{1\leq j\leq n+1}U_{(j,\,n)}-U_{(j-1,\,n)},$

and

  * •

the empirical measures

${P_{n}}=\frac{1}{n}\sum_{j=0}^{n-1}\delta_{U_{j}},$

where $\delta_{x}$ is the Dirac measure at $x$.

In addition, we consider the event

$\mathcal{E}=\Bigg{\\{}(U_{j})_{j\geq 1}\text{ are
distinct},\,\sup_{x\in[0,1]}\bigg{|}x-\frac{1}{n}\sum_{j=1}^{n}\mathbbm{1}(U_{j}\leq
x)\bigg{|}\xrightarrow[n\to\infty]{}0\Bigg{\\}}.$ (3)

The following result summarizes the properties of these objects that will be
useful to us.

######  Proposition 3.1.

The event $\mathcal{E}$ occurs almost surely and on $\mathcal{E}$, the
following statements hold (all limits are to be taken as $n\to\infty$):

  1. (i)

$\sup_{t\in[0,1]}\left|U_{(\lceil nt\rceil,\,n-1)}-t\right|\longrightarrow 0,$

  2. (ii)

$\Delta_{n}\to 0,$

  3. (iii)

for every $k\geq 1$,
$\sup_{J\in\mathcal{A}_{k}}\left|\operatorname{Leb}(J)-{P_{n}}(J)\right|\longrightarrow
0,$ where $\mathcal{A}_{k}$ consists of all subsets of $[0,1]$ that are a
disjoint union of at most $k$ intervals.

###### Proof.

The fact that $\mathcal{E}$ occurs almost surely is a classical result known
as the Glivenko-Cantelli Theorem. We assume for the remainder of the proof
that $\mathcal{E}$ occurs.

Since $U_{(\lceil nt\rceil,\,n-1)}\in[0,1]$ for all $t\in[0,1]$ and $n\geq 1$,
we can apply the limit in (3): as $n\to\infty$, we have the convergence

$\sup_{t\in[0,1]}\left|U_{(\lceil
nt\rceil,\,n-1)}-\frac{1}{n}\sum_{j=1}^{n}\mathbbm{1}(U_{j}\leq U_{(\lceil
nt\rceil,\,n-1)})\right|\longrightarrow 0.$ (4)

Recalling that the sequence $(U_{j})_{j\geq 1}$ contains distinct values, we
obtain the estimate

$\left|\frac{1}{n}\sum_{j=1}^{n}\mathbbm{1}(U_{j}\leq U_{(\lceil
nt\rceil,\,n-1)})-t\right|\leq\frac{1}{n}+\left|\frac{1}{n}\sum_{j=1}^{n-1}\mathbbm{1}(U_{j}\leq
U_{(\lceil nt\rceil,\,n-1)})-t\right|\leq\frac{2}{n}$

which shows that $t$ can replace
$\frac{1}{n}\sum_{j=1}^{n}\mathbbm{1}(U_{j}\leq U_{(\lceil nt\rceil,\,n-1)})$
in the convergence (4). This establishes (i). Writing

$\left|U_{(j,\,n)}-U_{(j-1,\,n)}\right|\leq\left|U_{(j,\,n)}-\frac{j}{n}\right|+\left|\frac{j}{n}-\frac{j-1}{n}\right|+\left|\frac{j-1}{n}-U_{(j-1,\,n)}\right|$

for $n\geq 1$ and $1\leq j\leq n+1$, we see that (ii) follows immediately from
(i).

For $x\in[0,1]$, we can write

$\displaystyle\left|\operatorname{Leb}([0,x])-{P_{n}}([0,x])\right|$
$\displaystyle=\Bigg{|}x-\frac{1}{n}\sum_{j=0}^{n-1}\mathbbm{1}(U_{j}\leq
x)\Bigg{|}$
$\displaystyle\leq\Bigg{|}x-\frac{1}{n}\sum_{j=1}^{n}\mathbbm{1}(U_{j}\leq
x)\Bigg{|}+\frac{1}{n}\left|\mathbbm{1}(U_{n}\leq x)-\mathbbm{1}(U_{0}\leq
x)\right|$

and apply the limit in (3) to see that

$\sup_{x\in[0,1]}\left|\operatorname{Leb}([0,x])-{P_{n}}([0,x])\right|\longrightarrow
0$

as $n\to\infty$. Using the decomposition

$\nu((x,y])=\nu([0,y])-\nu([0,x])$

for any probability measure $\nu$ on $[0,1]$ and $x<y$ in $[0,1]$, we then
obtain the convergence

$\sup_{x<y}\left|\operatorname{Leb}((x,y])-{P_{n}}((x,y])\right|\longrightarrow
0$

as $n\to\infty$. Recalling that the sequence $(U_{j})_{j\geq 1}$ contains
distinct values, we have the bound

$P_{n}\\{x\\}=\frac{1}{n}\sum_{j=0}^{n-1}\mathbbm{1}(U_{j}=x)\leq\frac{1}{n}$

for any $x\in[0,1]$. In particular, we can add or remove the endpoints of the
interval $(x,y]$ above while maintaining the convergence. This establishes the
result for $k=1$. The extension to general $k$ follows from the additivity
property of measures. ∎

###  3.2 The permuton

We now construct the random permuton that will serve as the limit of our
permutation model. Our construction is inspired by the construction of the
Brownian separable permuton (see [Maa20], or Section 4.4 here).

To begin, we define a random relation $\prec$ on $[0,1]$ as follows. Given
$x<y$ in $[0,1]$ such that $(x,y]\cap\\{U_{j}\\}_{j\geq 1}\neq\emptyset,$ we
consider the minimal $j\geq 1$ such that $U_{j}\in(x,y].$ We set

$\begin{cases}x\prec y&\text{ if }S_{j}=\oplus;\\\ y\prec x&\text{ if
}S_{j}=\ominus.\end{cases}$

Letting

$\displaystyle\mathcal{I}_{x,y}$
$\displaystyle=\Big{(}\\!\min(x,y),\,\max(x,y)\Big{]},\qquad x,y\in[0,1],$
$\displaystyle i_{x,y}$ $\displaystyle=\inf\left\\{j\geq
1:U_{j}\in\mathcal{I}_{x,y}\right\\},\qquad x,y\in[0,1],$

and

$S_{\infty}=0,$

we can describe this relation concisely as

$x\prec y\qquad\Longleftrightarrow\qquad(y-x)S_{i_{x,y}}>0.$

We then define a random function $\phi\colon[0,1]\to[0,1]$ and a random
measure on $[0,1]^{2}$ by

$\displaystyle\phi(x)$
$\displaystyle=\operatorname{Leb}\left(\\{y\in[0,1]:y\prec x\\}\right),$
$\displaystyle\bm{\mu}^{\text{\tiny rec}}_{p}$
$\displaystyle=\mu_{\phi}=(\,\cdot\,,\phi(\,\cdot\,))_{\\#}\operatorname{Leb},$

where, in the last equation, we use the notation $\mu_{f}$ of Section 2.

In Proposition 3.6, we will see that the following properties hold almost
surely: the relation $\prec$ is a total order on $[0,1]$, the function $\phi$
is Lebesgue-preserving, and the measure $\bm{\mu}^{\text{\tiny rec}}_{p}$ is a
permuton. We define the recursive separable permuton (of parameter $p$) as the
random measure $\bm{\mu}^{\text{\tiny rec}}_{p}$ on $[0,1]^{2}$.

The remainder of this section is dedicated to analyzing the relation $\prec$
and the function $\phi$. Not only will this allow us to establish the above
properties, but it will prepare us for the convergence argument. We begin with
the basic properties of the relation $\prec$.

######  Lemma 3.2.

Let $x,y,z\in[0,1]$. Then $i_{x,y},$ $i_{y,z},$ and $i_{x,z}$ can be assigned
the labels $a$, $b$, and $c$ so that

$a=b\leq c.$

Moreover, if

$i_{x,y}=i_{y,z}<\infty,$

then

$y\prec x,z\qquad\text{or}\qquad x,z\prec y.$

###### Proof.

The intervals $\mathcal{I}_{x,y}$, $\mathcal{I}_{y,z}$, and
$\mathcal{I}_{x,z}$ can be assigned the labels $A$, $B$, and $C$ so that they
satisfy

$A=B\sqcup C.$ (5)

It follows immediately that

$\displaystyle\inf\left\\{j\geq 1:U_{j}\in A\right\\}$
$\displaystyle=\inf\left\\{j\geq 1:U_{j}\in B\sqcup C\right\\}$
$\displaystyle=\min\\!\big{(}\inf\left\\{j\geq 1:U_{j}\in
B\right\\}\\!,\,\inf\left\\{j\geq 1:U_{j}\in C\right\\}\\!\,\big{)},$

establishing the first claim. Assume now that $i_{x,y}=i_{y,z}<\infty,$ or
equivalently,

$\inf\left\\{j\geq 1:U_{j}\in\mathcal{I}_{x,y}\right\\}=\inf\left\\{j\geq
1:U_{j}\in\mathcal{I}_{y,z}\right\\}<\infty.$

Then the intervals $\mathcal{I}_{x,y}$ and $\mathcal{I}_{y,z}$ are not
disjoint $(U_{i_{x,y}}\in\mathcal{I}_{x,y}\cap\mathcal{I}_{y,z}).$ This
implies that $y$ is either the minimum or maximum of $\\{x,y,z\\}$. In
particular, the inequality $(y-z)/(y-x)>0$ holds. From this, we obtain the
equivalence

$x\prec y\ \Longleftrightarrow\ (y-x)S_{i_{x,y}}>0\ \Longleftrightarrow\
(y-z)S_{i_{y,z}}>0\ \Longleftrightarrow\ z\prec y.$

The equivalence

$y\prec x\quad\Longleftrightarrow\quad y\prec z$

can be obtained similarly. Recalling that $y\neq x$ and $i_{x,y}<\infty$, it
follows that $(y-x)S_{i_{x,y}}\neq 0$, so either $x\prec y$ or $y\prec x$.
Applying one of the above equivalences concludes the proof. ∎

######  Corollary 3.3.

The relation $\prec$ is a partial order.

###### Proof.

Irreflexivity and asymmetry are straightforward to prove, let us consider
transitivity. Suppose that $x\prec y$ and $y\prec z$. Since $y\not\prec x,$
$z\not\prec y,$ and $i_{x,y},\,i_{y,z}<\infty,$ Lemma 3.2 implies that
$i_{x,y}\neq i_{y,z}.$ Applying Lemma 3.2 again reveals that
$i_{x,z}=\min(i_{x,y},i_{y,z})$ and $x\prec z$. This shows that $\prec$ is
transitive. ∎

Now we turn our attention to the function $\phi$. For this analysis, we make
use of the functions

$\phi_{k}(x)=\operatorname{Leb}\big{(}\big{\\{}y\in[0,1]:y\prec
x,\,i_{x,y}\leq k\big{\\}}\big{)},\qquad k\geq 0,$

which serve as approximations to $\phi$. Indeed, the continuity of measure
property implies that $\phi_{k}\nearrow\phi$ pointwise as $k\to\infty$. The
basic properties of these functions are summarized in the following result.

######  Proposition 3.4.

Let $x,y\in[0,1]$ and $k\geq 0$. The following statements hold:

  1. (i)

$i_{x,y}>k\qquad\Longleftrightarrow\qquad\phi_{k}(x)=\phi_{k}(y),$

  2. (ii)

$x\prec y,\,i_{x,y}\leq
k\qquad\Longleftrightarrow\qquad\phi_{k}(x)<\phi_{k}(y),$

  3. (iii)

$\phi_{k}(x)=\operatorname{Leb}\big{(}\big{\\{}y\in[0,1]:\phi_{k}(y)<\phi_{k}(x)\big{\\}}\big{)};$

  4. (iv)

$\phi_{k}$ is constant on each of the intervals

$\left[0,U_{(1,k)}\right),\left[U_{(1,k)},U_{(2,k)}\right),\ldots,\left[U_{(k-1,k)},U_{(k,k)}\right),\left[U_{(k,k)},1\right],$

and assumes different values on distinct intervals.

###### Proof.

(i) $(\Longrightarrow)$ Let $x,y\in[0,1]$ and $k\geq 0$. Suppose that
$i_{x,y}>k$. Let us show that $L_{x}=L_{y},$ where

$L_{t}=\\{s:s\prec t,\,i_{s,t}\leq k\\},\qquad t\in[0,1].$

Let $z\in L_{x}$. This implies $i_{x,z}\leq k$, and in particular
$i_{x,z}<i_{x,y}$. From this, Lemma 3.2 gives us that $i_{y,z}=i_{x,z}\leq k$
and $z\prec y.$ Therefore, $z\in L_{y}$, establishing the containment
$L_{x}\subset L_{y}.$ The reverse containment holds by symmetry. Writing
$\phi_{k}(x)=\operatorname{Leb}(L_{x})=\operatorname{Leb}(L_{y})=\phi_{k}(y)$
establishes the desired result.

(i) $(\Longleftarrow)$ Suppose now that $i_{x,y}\leq k$. It follows that
$x\neq y$ and $S_{i_{x,y}}\neq 0$, so either $x\prec y$ or $y\prec x$. Without
loss of generality, we can assume that $x\prec y$. Let us show that
$L_{x}\subset L_{y}$. Take $z\in L_{x}$. Since $z\prec x\prec y$, Corollary
3.3 implies that $z\prec y$ and Lemma 3.2 implies that $i_{x,z}\neq i_{x,y}.$
Applying Lemma 3.2 again, we find that $i_{y,z}=\min(i_{x,z},i_{x,y})\leq k,$
and consequently, $z\in L_{y}$. This establishes the containment $L_{x}\subset
L_{y}$.

Thus we can write $\phi_{k}(y)=\phi_{k}(x)+\operatorname{Leb}(L_{y}\setminus
L_{x}),$ and it only remains to show that $L_{y}\setminus L_{x}$ has positive
Lebesgue measure. To this end, we define

$U^{-}=\begin{cases}\max\\{U_{j}:-1\leq j\leq k,\,U_{j}\leq x\\},&x\neq 1,\\\
\max\\{U_{j}:0\leq j\leq k\\}&x=1,\end{cases}$

and

$U^{+}=\begin{cases}\min\\{U_{j}:-1\leq j\leq k,\,x<U_{j}\\},&x\neq 1,\\\
1&x=1,\end{cases}$

and will show that $(U^{-},U^{+})$ is a nonempty interval contained in
$L_{y}\setminus L_{x}$. It should be clear that $(U^{-},U^{+})$ is nonempty,
that $x\in[U^{-},U^{+})$ (except when $x=1$) and that

$(U^{-},U^{+})\cap\\{U_{1},\ldots,U_{k}\\}=\emptyset.$

Now take $z\in(U^{-},U^{+})$. We have $\mathcal{I}_{x,z}\subset(U^{-},U^{+})$
(except in the case $x=1$, where $U^{+}$ should be included). Recalling that
$U_{j}\in(0,1)$ for $j\geq 1$, it can be verified that

$\mathcal{I}_{x,z}\cap\\{U_{1},\ldots,U_{k}\\}\subset(U^{-},U^{+})\cap\\{U_{1},\ldots,U_{k}\\}=\emptyset.$

It follows immediately that $i_{x,z}>k$, so $z\notin L_{x}$. Since
$i_{x,y}\leq k$ and $x\prec y$, we have $i_{x,y}<i_{x,z}$ and Lemma 3.2 gives
us that $i_{y,z}=i_{x,y}\leq k$ and $z\prec y$, so $z\in L_{y}$. This
establishes the containment $(U^{-},U^{+})\subset L_{y}\setminus L_{x},$
concluding the proof.

(ii) $(\Longrightarrow)$ This statement was proved in the proof of (i)
$(\Longleftarrow)$.

(ii) $(\Longleftarrow)$ Let $x,y\in[0,1]$ and $k\geq 0$ and suppose that
$\phi_{k}(x)<\phi_{k}(y).$ Using (i), we have that $i_{x,y}\leq k.$ As before,
we must have that $x\prec y$ or $y\prec x$. However, the forward implication
in (ii) implies that $y\not\prec x.$ Therefore, $x\prec y$.

(iii) This claim follows from the definition of $\phi_{k}$ and (ii)

(iv) This claim follows immediately from (i). ∎

The above result leads to the following estimate for $\phi$, which plays a
crucial role in the convergence argument.

######  Corollary 3.5.

Let $k\geq 1$ and $\nu$ be a probability measure on $[0,1]$. The following
inequality holds:

  1. (i)

$\displaystyle\sup_{x\in[0,1]}\big{|}\nu\\{y:y\prec
x\\}-\nu\\{y:\phi_{k}(y)<\phi_{k}(x)\\}\big{|}\leq\Delta_{k}+\sup_{J\in\mathcal{A}_{1}}|\operatorname{Leb}(J)-\nu(J)|.$

Consequently, the following convergence holds on $\mathcal{E}$:

  1. (ii)

$\displaystyle\sup_{x\in[0,1]}\left|\phi(x)-{P_{n}}\\{y:y\prec
x\\}\right|\longrightarrow 0$ as $n\to\infty$.

###### Proof.

Let $k\geq 1$ and $\nu$ be a probability measure on $[0,1]$. Using Proposition
3.4, we have that

$\left|\nu\\{y:y\prec
x\\}-\nu\\{y:\phi_{k}(y)<\phi_{k}(x)\\}\right|=\nu\\{y:y\prec
x,\,i_{x,y}>k\\}\\\
\leq\nu\\{y:i_{x,y}>k\\}=\nu\\{y:\phi_{k}(y)=\phi_{k}(x)\\}=\nu(\phi_{k}^{-1}(\phi_{k}(x))).$

From Proposition 3.4(iv), $\phi_{k}^{-1}(\phi_{k}(x)),$ is an interval between
two consecutive values in the set $\\{U_{-1},U_{0},\cdots,U_{k}\\}$. Therefore

$\displaystyle\operatorname{Leb}(\phi_{k}^{-1}(\phi_{k}(x)))\leq\Delta_{k}\text{
and
}|\nu(\phi_{k}^{-1}(\phi_{k}(x)))-\operatorname{Leb}(\phi_{k}^{-1}(\phi_{k}(x)))|\leq\sup_{J\in\mathcal{A}_{1}}|\operatorname{Leb}(J)-\nu(J)|,$

establishing (i). Taking $\nu=\operatorname{Leb}$ and $\nu={P_{n}}$ in (i)
gives us that

$\displaystyle\sup_{x\in[0,1]}\big{|}\operatorname{Leb}\\{y:y\prec
x\\}-\operatorname{Leb}\\{y:\phi_{k}(y)<\phi_{k}(x)\\}\big{|}\leq\Delta_{k},\qquad
k\geq 1,$ (6)

and

$\displaystyle\sup_{x\in[0,1]}\big{|}{P_{n}}\\{y:y\prec
x\\}-{P_{n}}\\{y:\phi_{k}(y)<\phi_{k}(x)\\}\big{|}\leq\Delta_{k}+\sup_{J\in\mathcal{A}_{1}}|\operatorname{Leb}(J)-{P_{n}}(J)|,\qquad
n,k\geq 1.$

Note that $\mathcal{A}_{1}$ can be replaced by $\mathcal{A}_{k}$ above since
$\mathcal{A}_{1}\subset\mathcal{A}_{k}$ for all $k\geq 1$. Observe also that
the set $\\{y:\phi_{k}(y)<\phi_{k}(x)\\}$ lies in $\mathcal{A}_{k}$ for every
$x\in[0,1]$ (see Proposition 3.4(iv)), from which we obtain the inequalities

$\displaystyle\sup_{x\in[0,1]}\big{|}\operatorname{Leb}\\{y:\phi_{k}(y)<\phi_{k}(x)\\}-{P_{n}}\\{y:\phi_{k}(y)<\phi_{k}(x)\\}\big{|}\leq\sup_{J\in\mathcal{A}_{k}}|\operatorname{Leb}(J)-{P_{n}}(J)|,\qquad
n,k\geq 1.$

Collecting these bounds, we obtain the estimates

$\displaystyle\sup_{x\in[0,1]}\big{|}\operatorname{Leb}\\{y:y\prec
x\\}-{P_{n}}\\{y:y\prec x\\}\big{|}\leq
2\,\Delta_{k}+2\sup_{J\in\mathcal{A}_{k}}|\operatorname{Leb}(J)-{P_{n}}(J)|,\qquad
n,k\geq 1.$

Since $\operatorname{Leb}\\{y:y\prec x\\}=\phi(x)$, applying Proposition 3.1
(items (ii) and (iii)) concludes the proof. ∎

Finally, we establish the main properties of the objects $\prec$, $\phi$, and
$\bm{\mu}^{\text{\tiny rec}}_{p}$.

######  Proposition 3.6.

On $\mathcal{E}$, the following statements hold:

  1. (i)

the relation $\prec$ is a total order,

  2. (ii)

$\phi_{k}\to\phi$ uniformly on $[0,1]$ as $k\to\infty$,

  3. (iii)

$\phi$ is continuous on $[0,1]\setminus\\{U_{j}\\}_{j\geq 1}$,

  4. (iv)

$\phi$ preserves the measure $\operatorname{Leb}$, and thus $\mu_{\phi}$ is a
permuton.

###### Proof.

Take $x\neq y$ in $[0,1]$ and suppose that $\mathcal{E}$ occurs. From
Proposition 3.1, we know that the maximal gap $\Delta_{k}$ of the sequence
$(U_{j})_{j\leq k}$ tends to $0$, so the infinite sequence $(U_{j})_{j\geq 1}$
must intersect the nonempty interval $\mathcal{I}_{x,y}$. It follows that $x$
and $y$ are comparable in the order $\prec$. This establishes (i).

The uniform convergence in (ii) follows immediately from Proposition 3.4(iii),
Eq. 6 and Proposition 3.1(ii). The continuity in (iii) then follows from the
uniform convergence in (ii) and from Proposition 3.4(iv), which describes the
continuity of each $\phi_{k}$.

It remains to prove (iv), i.e. that $\phi$ preserves the Lebesgue measure. Let
$b\in(0,1)$. From Proposition 3.4(iii) and (iv), we see that each $\phi_{k}$
attains only finitely many values and that the gap between consecutive values
is bounded by $\Delta_{k}$. In particular, defining $y_{k}$ such that
$\phi_{k}(y_{k})$ is the smallest element in the range of $\phi_{k}$ above $b$
(which exists for large $k$), we have $\lim_{k\to+\infty}\phi_{k}(y_{k})=b$.
Also, using Proposition 3.4(iii), we have

$\displaystyle\phi_{k}(y_{k})=\operatorname{Leb}\big{(}\big{\\{}z:\phi_{k}(z)<\phi_{k}(y_{k})\big{\\}}\big{)}=\operatorname{Leb}\big{(}\big{\\{}z:\phi_{k}(z)\leq
b\big{\\}}\big{)}.$

Recalling that $\phi_{k}\nearrow\phi$, we have that

$\displaystyle(\phi_{\\#}\operatorname{Leb})([0,b])=\operatorname{Leb}\big{(}\big{\\{}z:\phi(z)\leq
b\big{\\}}\big{)}=\lim_{k\to\infty}\operatorname{Leb}\big{(}\big{\\{}z:\phi_{k}(z)\leq
b\big{\\}}\big{)}=\lim_{k\to\infty}\phi_{k}(y_{k})=b.$

Since this holds for every $b\in(0,1)$, the measures
$\phi_{\\#}\operatorname{Leb}$ and $\operatorname{Leb}$ are the same, and (iv)
holds.

∎

###  3.3 The permutations

We continue our construction by realizing the recursive separable permutations
on our probability space. Since $(U_{j})_{j\geq 1}$ is a sequence of i.i.d.
uniform random variables, they are a.s. distinct and different from 0 and 1.
Throughout this section, we assume that this event indeed holds.

Suppose that $E$ is a finite set and that $<$ and $\prec$ are two total orders
on $E$. Using the first order, we can write $E=\\{x_{1},\dots,x_{k}\\}$ where
$k=|E|$ and $x_{1}<\dots<x_{k}$. Then there exists a unique permutation
$\sigma$ satisfying

$\sigma(j)<\sigma(k)\quad\Longleftrightarrow\quad x_{j}\prec x_{k}.$ (7)

We denote this permutation by $\sigma=\operatorname{Perm}(E,<,\prec)$. For
example, if $E=\\{a,b,c,d,e\\}$, with $a<b<c<d<e$ and $d\prec b\prec e\prec
c\prec a$, then $\sigma=52413$. To visualize this construction, we can
represent elements of $E$ as points in the plane, so that $<$ compares the
$x$-coordinates, while $\prec$ compares the $y$-coordinates. Then $E$
ressembles the diagram of $\sigma$, see Fig. 9.

$a$$b$$c$$d$$e$ Figure 9: A set of points $E=\\{a,b,c,d,e\\}$; comparing
$x$-coordinates and $y$-coordinates yield two orders $<$ and $\prec$ on $E$.
The associated permutation $\sigma=\operatorname{Perm}(E,<,\prec)$ is $52413$.

Taking patterns is simple with this viewpoint. If $E=\\{x_{1},\dots,x_{k}\\}$
is as above (in particular, we assume $x_{1}<\dots<x_{k}$) and $I$ is a subset
of $\\{1,...,k\\}$, then

$\operatorname{pat}_{I}\big{(}\operatorname{Perm}(E,<,\prec)\big{)}=\operatorname{Perm}\big{(}\\{x_{i},i\in
I\\},<,\prec\big{)}.$

We will use this repeatedly below.

Finally $\sigma=\operatorname{Perm}(E,<,\prec)$ is also given by an explicit
formula. As above, let $x_{k}$ be the $k$-th smallest element in $E$ for the
first order $<$. Then, if $x_{k}$ is the $\ell$-th smallest element for the
order $\prec$, we have

$\sigma(k)=\ell=1+\sum_{x\in E}\bm{1}[x\prec x_{k}].$ (8)

For each $n\geq 1$, we consider the random set $E_{n}=\\{U_{j},\,0\leq j\leq
n-1\\}$, endowed with the natural order $<$ and the random order $\prec$.
Since the $(U_{j})_{j\geq 1}$ are assumed to be distinct and different from 0,
the set $E_{n}$ has size $n$. Moreover, it is easy to see that the restriction
of $\prec$ to $E_{n}$ is always a total order. This allows us to define the
following random permutation of size $n$:

$\lambda_{n}=\operatorname{Perm}\Big{(}\big{\\{}U_{j},\,0\leq j\leq
n-1\big{\\}},<,\prec\Big{)},\qquad n\geq 1.$ (9)

Loosely speaking, the permutation $\lambda_{n}$ can be viewed as describing
the shape of the graph of $\phi_{n-1}$ (recall 3.4 (ii)). This perspective
suggests that $f_{\lambda_{n}}$ will resemble $\phi_{n-1}$ and consequently,
be close to $\phi$ for large $n$ – this heuristic is at the heart of our
convergence argument in the next section. Before that, in this section, we
prove that the sequence $(\lambda_{n})_{n\geq 1}$ is a realization of the
process $(\sigma^{(n),p})_{n\geq 1}$ constructed in the introduction, in the
sense that both have the same distribution (3.8 below).

To this end, we first establish a recursion for $\lambda_{n}$, for which we
need some notation. Given a permutation $\tau$ of $n$, a sign
$s\in\\{\oplus,\ominus\\}$, and an integer $k\in\\{1,\ldots,n\\}$, let
$\tau_{s,k}$ be the permutation obtained by writing $\tau$ in one-line
notation, increasing all values bigger than $j=\tau(k)$, and replacing $j$ by
$j\,j\\!\\!+\\!\\!1$ if $s=\oplus$ or by $j\\!\\!+\\!\\!1\,j$ if $s=\ominus$.
For a permutation $\sigma$ of $n$ and an integer $k$, we denote by
$\sigma^{\downarrow k}$ the pattern induced by $\sigma$ on the set of
positions $\\{1,\dots,n\\}\setminus\\{k\\}$ (in other words, we erase
$\sigma_{k}$ in the one-line notation and decrease by 1 all values bigger than
$\sigma_{k}$ to get a permutation).

With this notation in hand, it can be verified that $\tau_{s,k}$ is the unique
permutation $\sigma$ of $n+1$ satisfying the following properties:

  1. (i)

$\sigma^{\downarrow k}$ and $\sigma^{\downarrow(k+1)}$ are both equal to
$\tau$;

  2. (ii)

$\sigma(k+1)>\sigma(k)$ if $s=\oplus$ (resp. $\sigma(k+1)<\sigma(k)$ if
$s=\ominus$).

######  Proposition 3.7.

Suppose that the elements $(U_{j})_{j=1}^{n}$ are distinct. Let $R_{n}$ denote
the rank of $U_{n}$ in $\\{U_{j}\\}_{j=1}^{n}$ (i.e. the unique integer
satisfying $U_{(R_{n},\,n)}=U_{n}).$ The following recursion holds:

$\lambda_{n+1}=(\lambda_{n})_{S_{n},R_{n}},\qquad n\geq 1.$

###### Proof.

We will verify that $\lambda_{n+1}$ satisfies the three conditions that
characterize $(\lambda_{n})_{S_{n},R_{n}}$. Writing $k=R_{n}$, we note that
$U_{n}$ corresponds to the $(k+1)$-st point from the left in $\lambda_{n+1}$
(note that the index $j$ starts from $0$ in eq. (9)). Therefore we have

$(\lambda_{n+1})^{\downarrow
k+\\!1}=\operatorname{Perm}\big{(}\\{U_{j},\,0\leq j\leq
n-1\\},<,\prec\big{)}=\lambda_{n}.$

Let us consider the pattern $(\lambda_{n+1})^{\downarrow k}$. The $k$-th point
from the left in $\lambda_{n+1}$ corresponds to $U_{(k-1,n)}$, so that

$(\lambda_{n+1})^{\downarrow k}=\operatorname{Perm}\big{(}\\{U_{j},\,0\leq
j\leq n\\}\setminus\\{U_{(k-1,n)}\\},<,\prec\big{)}.$

To show that this is also $\lambda_{n}$, we need to show that $U_{n}$ and
$U_{(k-1,n)}$ compare in the same way with other $U_{j}$’s ($j\leq n$), both
for the natural order $<$ and for the random order $\prec$.

The case of the natural order $<$ is trivial by definition of the ordered
statistics, since $U_{n}=U_{(k,n)}$. Consider the random order $\prec$. Since
$U_{n}=U_{(k,n)}$, the element $U_{n}$ is the $U$ with smallest index in the
interval $(U_{(k-1,n)},U_{n}]$, i.e. $i_{U_{(k-1,n)},U_{n}}=n$. On the other
hand, for $j<n$ and $U_{j}\neq U_{(k-1,n)}$, the interval
$\mathcal{I}_{U_{(k-1,n)},U_{j}}$ contains either $U_{j}$ or $U_{(k-1,n)}$, so
that $i_{U_{(k-1,n)},U_{j}}<n$. Applying Lemma 3.2, we then find that
$i_{U_{(k-1,n)},U_{j}}=i_{U_{j},U_{n}}<\infty,$ and $U_{(k-1,n)}$ and $U_{n}$
compare in the same way with $U_{j}$ in the order $\prec$, which is what we
needed to show. Thus $\lambda_{n+1}$ verifies the first condition in the
characterization of $(\lambda_{n})_{S_{n},R_{n}}$.

It remains to show that $\lambda_{n+1}(k)<\lambda_{n+1}(k+1)$ if
$S_{n}=\oplus$ (resp. $\lambda_{n+1}(k)>\lambda_{n+1}(k+1)$ if $s=\ominus$).
We consider the case $S_{n}=\oplus$. Since the $k$-th and $(k+1)$-st points
from the left in $\lambda_{n+1}$ correspond to $U_{(k-1,n)}$ and $U_{n}$
respectively, it suffices to show that $U_{(k-1,n)}\prec U_{n}$. This follows
from the fact that $i_{U_{(k-1,n)},U_{n}}=n$ (see above) and the assumption
$S_{n}=\oplus$ (recall that $U_{(k-1,n)}<U_{n}$ for the natural order).

We have proved that $\lambda_{n+1}$ verifies the second condition in the
characterization of $(\lambda_{n})_{S_{n},R_{n}}$, implying
$\lambda_{n+1}=(\lambda_{n})_{S_{n},R_{n}}$, as desired. ∎

######  Proposition 3.8.

The permutations $(\lambda_{n})_{n\geq 1}$ are recursive separable
permutations. In other words,

$(\lambda_{n})_{n\geq 1}\stackrel{{\scriptstyle
d}}{{=}}(\sigma^{(n),p})_{n\geq 1}.$

###### Proof.

We start with the following observation.

  * •

To compare $U_{j}$ and $U_{k}$ in the order $\prec$, we need to look at the
sign $S_{i_{U_{j},U_{k}}}$. If $j,k<n$ and $U_{j}\neq U_{k}$, then the
interval $\mathcal{I}_{U_{j},U_{k}}$ contains either $U_{j}$ or $U_{k}$, and
thus $i_{U_{j},U_{k}}<n$. Therefore, the restriction of $\prec$ to
$\\{U_{0},\dots,U_{n-1}\\}$ only depends on the restriction of the natural
order $<$ to $\\{U_{0},\dots,U_{n-1}\\}$ and on the signs
$S_{1},\ldots,S_{n-1}$. Consequently, the tuple of permutations
$(\lambda_{1},\dots,\lambda_{n})$ only depends on this data as well.

  * •

On the other hand, $R_{n}$ describes how $U_{n}$ fits into the gaps of the set
$\\{U_{0},\dots,U_{n-1}\\}$, and is independent of its order structure.

Therefore the random variables $(\lambda_{1},\dots,\lambda_{n})$, $S_{n}$, and
$R_{n}$ are independent. Combining this with Proposition 3.7, this implies
that $(\lambda_{n})_{n\geq 1}$ is a Markov process and we can compute its
transition kernel. If $\pi$ and $\tau$ are permutations of $n$ and $n+1$
respectively, one has

$\displaystyle\mathbb{P}(\lambda_{n+1}=\tau|\lambda_{n}=\pi)$
$\displaystyle=\sum_{j=1}^{n}\sum_{s\in\\{\oplus,\ominus\\}}\mathbbm{1}(\pi_{s,j}=\tau)\mathbb{P}(R_{n}=j,S_{n}=s)$
$\displaystyle=\sum_{j=1}^{n}\left(\frac{p}{n}\,\mathbbm{1}(\pi_{\oplus,j}=\tau)+\frac{1-p}{n}\,\mathbbm{1}(\pi_{\ominus,j}=\tau)\right)$
$\displaystyle=\mathbb{P}(\sigma^{(n+1),\,p}=\tau|\sigma^{(n),\,p}=\pi)$

Since $(\lambda_{n})_{n\geq 1}$ and $(\sigma^{(n),\,p})_{n\geq 1}$ are both
Markov chains with the same transition kernel and the same initial
distribution ($\lambda_{1}$ and $\sigma^{(1),\,p}$ are both equal to the
unique permutation of $1$ a.s.), they have the same distribution. ∎

The following result is the last one in this section. Here, we show that our
permutation model satisfies another type of recursion, referred to as
consistency. It is not needed for the convergence argument, but it is useful
in the next section for studying the expected pattern densities of
$\bm{\mu}^{\text{\tiny rec}}_{p}$.

######  Proposition 3.9.

The sequence $(\lambda_{n})_{n\geq 1}$ is a consistent family of random
permutations, in the sense of [BBF+20, Definition 2.8]: namely, for $n\geq 1$,
the permutation obtained by removing a uniformly random point from
$\lambda_{n+1}$ is distributed as $\lambda_{n}$.

###### Proof.

To avoid repetition, let us take the following convention throughout the
proof: each new random variable introduced in this proof should be assumed to
be independent of all previously defined random variables.

The $n=1$ case of the proposition is trivial. Proceeding by induction, we fix
$n>1$ and assume that the result holds for $n-1$. Let $j$ be a uniformly
random integer in $\\{1,\ldots,n+1\\}$ and $A$ be the event $\\{R_{n}\leq
j\leq R_{n}+1\\}.$ As we will show later, the following statements hold:

  1. (i)

$\lambda_{n}$ is independent of $A$,

  2. (ii)

$\lambda_{n+1}^{\downarrow j}=\lambda_{n}$ on $A$, and

  3. (iii)

conditionally given $A^{c}$, $\lambda_{n+1}^{\downarrow j}$ is distributed as
$\lambda_{n}.$

The result follows from these statements. Indeed, if $\tau$ is a permutation
of $n$, then

$\mathbb{P}(\lambda_{n+1}^{\downarrow
j}=\tau)=\mathbb{P}(\lambda_{n+1}^{\downarrow
j}=\tau|A^{c})\mathbb{P}(A^{c})+\mathbb{P}(\lambda_{n+1}^{\downarrow
j}=\tau|A)\mathbb{P}(A).$

Provided that Item (iii) holds, we have $\mathbb{P}(\lambda_{n+1}^{\downarrow
j}=\tau|A^{c})=\mathbb{P}(\lambda_{n}=\tau)$, while Items (i) and (ii) would
imply $\mathbb{P}(\lambda_{n+1}^{\downarrow
j}=\tau|A)=\mathbb{P}(\lambda_{n}=\tau|A)=\mathbb{P}(\lambda_{n}=\tau)$.
Therefore, given Items (i), (ii) and (iii), one has

$\mathbb{P}(\lambda_{n+1}^{\downarrow
j}=\tau)=\mathbb{P}(\lambda_{n}=\tau)\mathbb{P}(A^{c})+\mathbb{P}(\lambda_{n}=\tau)\mathbb{P}(A)=\mathbb{P}(\lambda_{n}=\tau).$

It remains, then, to verify the above statements. As explained in the proof of
Proposition 3.8, $\lambda_{n}$ is independent from $R_{n}$. Moreover, by
construction, $j$ is independent from $(\lambda_{n},R_{n})$. Thus
$\lambda_{n}$ is independent from $(j,R_{n})$ and hence from the event $A$,
proving Item (i).

Moreover it follows from 3.7 that, a.s., $\lambda_{n+1}^{\downarrow
R_{n}}=\lambda_{n+1}^{\downarrow R_{n}\\!+\\!1}=\lambda_{n}$, implying Item
(ii). For the third statement, we introduce the random variables

$\displaystyle X$ $\displaystyle=j-\mathbbm{1}(j>R_{n}),$ $\displaystyle Y$
$\displaystyle=R_{n}-\mathbbm{1}(R_{n}>j).$

Using 3.7 and an obvious commutation relation between the operator $\downarrow
j$ and $(\cdot)_{s,k}$, we have

$\lambda_{n+1}^{\downarrow
j}=\big{(}(\lambda_{n})_{S_{n},R_{n}}\big{)}^{\downarrow
j}=(\lambda_{n}^{\downarrow X})_{S_{n},Y},\quad\text{on }A^{c}.$

Notice also that $S_{n}$, $\lambda_{n}$, $X$, and $Y$ are mutually independent
given $A^{c}$, $S_{n}$ and $\lambda_{n}$ are independent of $A^{c}$, $X$ is
uniformly distributed in $\\{1,\ldots,n\\}$ conditionally given $A^{c}$, and
$Y$ is uniformly distributed in $\\{1,\ldots,n-1\\}$ conditionally given
$A^{c}$. Therefore, the conditional distribution of $(S_{n},\lambda_{n},X,Y)$
given $A^{c}$ is exactly the distribution of $(S_{n},\lambda_{n},k,\ell)$,
where $k$ is a uniformly random integer in $\\{1,\dots,n\\}$ and $\ell$ is a
uniformly random integer in $\\{1,\dots,n-1\\}$. Recalling from Proposition
3.8 that $\lambda_{n-1}$, $S_{n-1}$, and $R_{n-1}$ are mutually independent
and making use of the induction hypothesis, we find that conditionally given
$A^{c}$,

$\lambda_{n+1}^{\downarrow j}=(\lambda_{n}^{\downarrow
X})_{S_{n},Y}\stackrel{{\scriptstyle d}}{{=}}(\lambda_{n}^{\downarrow
k})_{S_{n},\ell}\stackrel{{\scriptstyle
d}}{{=}}(\lambda_{n-1})_{S_{n-1},\ell}\stackrel{{\scriptstyle
d}}{{=}}\lambda_{n}.$

This establishes the third fact and concludes the proof. ∎

###  3.4 The convergence argument

###### Proof of Theorem 1.3.

We recall that the event

$\mathcal{E}=\Bigg{\\{}(U_{j})_{j\geq 1}\text{ are
distinct},\,\sup_{x\in[0,1]}\bigg{|}x-\frac{1}{n}\sum_{j=1}^{n}\mathbbm{1}(U_{j}\leq
x)\bigg{|}\xrightarrow[n\to\infty]{}0\Bigg{\\}}$

holds almost surely. Also, since the permutations $(\lambda_{n})_{n\geq 1}$
are recursive separable permutations (see Proposition 3.8), it suffices to
show the permuton convergence

$\mu_{\lambda_{n}}\xrightarrow[n\to\infty]{}\bm{\mu}^{\text{\tiny
rec}}_{p}\quad\text{on }\mathcal{E}.$

Making use of (2), the identity $\bm{\mu}^{\text{\tiny
rec}}_{p}=(\,\cdot\,,\phi(\,\cdot\,))_{\\#}\operatorname{Leb},$ and
Proposition 2.1, we can reformulate this convergence as the convergence of
functions

$f_{\lambda_{n}}\longrightarrow\phi\quad\text{in }L^{1}[0,1]\quad\text{on
}\mathcal{E}.$

We will establish this convergence by showing that $f_{\lambda_{n}}\to\phi$
pointwise almost everywhere in $[0,1]$ whenever $\mathcal{E}$ occurs.

To this end, fix $x\in(0,1]\setminus\\{U_{j}\\}_{j\geq 1}$ and suppose that
$\mathcal{E}$ occurs. Since $x>0$, the quantity $\lceil nx\rceil$ lies in
$\\{1,\ldots,n\\}$ and we can write

$\left|f_{\lambda_{n}}(x)-\phi(x)\right|\leq\left|f_{\lambda_{n}}(x)-P_{n}(\left\\{y:y\prec
U_{(\lceil nx\rceil-1,n-1)}\right\\})\right|\\\ +\left|P_{n}(\left\\{y:y\prec
U_{(\lceil nx\rceil-1,n-1)}\right\\})-\phi(U_{(\lceil
nx\rceil-1,n-1)})\right|+\left|\phi(U_{(\lceil
nx\rceil-1,n-1)})-\phi(x)\right|.$ (10)

Corollary 3.5(ii) tells us that the second term above will converge to zero as
$n\to\infty$. The third term also converges to zero: indeed, Proposition 3.1
implies that

$\displaystyle\left|x-U_{(\lceil nx\rceil-1,n-1)}\right|$
$\displaystyle\leq\left|x-U_{(\lceil nx\rceil,n-1)}\right|+\left|U_{(\lceil
nx\rceil,n-1)}-U_{(\lceil nx\rceil-1,n-1)}\right|$
$\displaystyle\leq\left|x-U_{(\lceil nx\rceil,n-1)}\right|+\Delta_{n-1}$
$\displaystyle\quad\xrightarrow[n\to\infty]{}0,$

and $\phi$ is continuous at $x$ (see Proposition 3.6(iii)). It only remains,
then, to show that the first term in the upper bound (10) also converges to
zero. This follows from the definition of $\lambda_{n}$ and Eq. 8, which
allows us to write

$f_{\lambda_{n}}(x)=\frac{\lambda_{n}(\lceil
nx\rceil)}{n}=\frac{1}{n}+\frac{1}{n}\sum_{j=0}^{n-1}\mathbbm{1}\left(U_{j}\prec
U_{(\lceil nx\rceil-1,\,n-1)}\right)=\frac{1}{n}+{P_{n}}(\left\\{y:y\prec
U_{(\lceil nx\rceil-1,n-1)}\right\\}).$

Hence, whenever $\mathcal{E}$ occurs, for any
$x\in(0,1]\setminus\\{U_{j}\\}_{j\geq 1}$, the quantity $f_{\lambda_{n}}(x)$
tends to $\phi(x)$. This concludes the proof. ∎

##  Properties of the recursive separable permuton

###  4.1 Self-similarity

Fix $p\in(0,1)$ and let $\mathcal{P}$ denote the set of permutons. We first
prove the uniqueness of a probability distribution $\mathbb{P}_{p}$ on the
space of permutons such that, if $\bm{\mu}$ has distribution $\mathbb{P}_{p}$,
then $\Phi_{p}(\bm{\mu})$ has the same distribution. For this we see, with a
small abuse of notation, $\Phi_{p}$ as a map from the set
$\mathcal{M}_{1}(\mathcal{P})$ of probability measures on the set of permutons
to itself. Both $\mathcal{P}$ and $\mathcal{M}_{1}(\mathcal{P})$ are endowed
with the first Wasserstein distance; to avoid confusion, we will use a
boldface notation $\bm{d_{W}}$ for the distance on
$\mathcal{M}_{1}(\mathcal{P})$ and a standard $d_{W}$ for that on
$\mathcal{P}$.

######  Lemma 4.1.

The map $\Phi_{p}:\mathcal{M}_{1}(\mathcal{P})\to\mathcal{M}_{1}(\mathcal{P})$
is a contraction with Lipschitz constant at most $2/3$.

###### Proof.

Let $\mathbb{P}$ and $\mathbb{Q}$ be two probability measures on the set
$\mathcal{P}$ of permutons and call $d:=\bm{d_{W}}(\mathbb{P},\mathbb{Q})$
their Wasserstein distance. Fix $\varepsilon>0$. By definition of Wasserstein
distance, one can find random permutons $\bm{\mu}$ and $\bm{\nu}$ on the same
probability space such that $\bm{\mu}$ has distribution $\mathbb{P}$,
$\bm{\nu}$ has distribution $\mathbb{Q}$ and

$\mathbb{E}(d_{W}(\bm{\mu},\bm{\nu}))<d+\varepsilon.$

We consider two independent copies $(\bm{\mu}_{0},\bm{\nu}_{0})$ and
$(\bm{\mu}_{1},\bm{\nu}_{1})$ of the pair $(\bm{\mu},\bm{\nu})$. We also
consider a single pair $(U,S)$, where $U$ is a uniform random variable in
$[0,1]$ and $S$ a random sign with $\mathbb{P}(S=\oplus)=p$, such that $U$ and
$S$ are independent from each other and from $(\bm{\mu}_{0},\bm{\nu}_{0})$ and
$(\bm{\mu}_{1},\bm{\nu}_{1})$. By definition of $\Phi_{p}$, the measure
$\Phi_{p}(\mathbb{P})$ (resp. $\Phi_{p}(\mathbb{Q})$) is the distribution of
the random permuton $\bm{\mu}_{0}\otimes_{(U,S)}\bm{\mu}_{1}$ (resp.
$\bm{\nu}_{0}\otimes_{(U,S)}\bm{\nu}_{1}$). Therefore

$\bm{d_{W}}(\Phi_{p}(\mathbb{P}),\Phi_{p}(\mathbb{Q}))\leq\mathbb{E}\big{(}d_{W}(\bm{\mu}_{0}\otimes_{(U,S)}\bm{\mu}_{1},\bm{\nu}_{0}\otimes_{(U,S)}\bm{\nu}_{1})\big{)}.$
(11)

It is easy to see that, a.s.,

$d_{W}\big{(}\bm{\mu}_{0}\otimes_{(U,S)}\bm{\mu}_{1},\bm{\nu}_{0}\otimes_{(U,S)}\bm{\nu}_{1}\big{)}\leq
U^{2}d_{W}\big{(}\bm{\mu}_{0},\bm{\nu}_{0}\big{)}+(1-U)^{2}d_{W}\big{(}\bm{\mu}_{1},\bm{\nu}_{1}\big{)},$
(12)

where the factor $U^{2}$ is explained by the rescaling of distances and of
weights of $\bm{\mu}_{0}$, both by a factor $U$ in the construction of
$\bm{\mu}_{0}\otimes_{(U,S)}\bm{\mu}_{1}$ (and similarly the factor
$(1-U)^{2}$ comes from the rescaling of distances and weigths in
$\bm{\mu}_{1}$ by $1-U$). From Eqs. (11) and (12), using the independence of
$U$ from $(\bm{\mu}_{0},\bm{\nu}_{0})$ and $(\bm{\mu}_{1},\bm{\nu}_{1})$ and
the equality $(\bm{\mu}_{0},\bm{\nu}_{0})\stackrel{{\scriptstyle
d}}{{=}}(\bm{\mu}_{1},\bm{\nu}_{1})$, we get

$\bm{d_{W}}(\Phi_{p}(\mathbb{P}),\Phi_{p}(\mathbb{Q}))\leq\mathbb{E}\big{(}U^{2}+(1-U)^{2}\big{)}\,\mathbb{E}\big{(}d_{W}\big{(}\bm{\mu}_{0},\bm{\nu}_{0}\big{)}\big{)}<\tfrac{2}{3}(d+\varepsilon).$

Since this holds for any $\varepsilon>0$, we have

$\bm{d_{W}}(\Phi_{p}(\mathbb{P}),\Phi_{p}(\mathbb{Q}))\leq\tfrac{2}{3}\,d=\tfrac{2}{3}\bm{d_{W}}(\mathbb{P},\mathbb{Q}).$

This proves the lemma. ∎

Lemma 4.1 implies in particular the existence and uniqueness of a probability
measure $\mathbb{P}_{p}$ on the set of permutons such that
$\mathbb{P}_{p}=\Phi_{p}(\mathbb{P}_{p})$. We still need to identify
$\mathbb{P}_{p}$ with the distribution of the recursive separable permuton
$\bm{\mu}^{\text{\tiny rec}}_{p}$. To do this, we first show that the
recursive separable permutations exhibit self-similarity and then use Theorem
1.3 to carry this property over to the limit. It might be possible to
establish the self-similarity of the permuton directly, but we think that the
self-similarity of the permutations is of its own interest.

Below, we denote the distribution of a random variable $X$ by
$\operatorname{Law}(X)$. In addition, we use the notion of skew sums and
direct sums of permutations introduced in Section 1.3.2.

######  Proposition 4.2.

Let $(\sigma^{(n),p})_{n\geq 1}$, $(\tau^{(n),p})_{n\geq 1}$ and
$(\rho^{(n),p})_{n\geq 1}$ be independent copies of the permutation process
defined in Section 1.1, and let $I$ be a uniform integer in
$\\{1,\dots,n-1\\}$. Then, for any fixed $n\geq 1$, we have

$\operatorname{Law}(\sigma^{(n),p})=p\,\operatorname{Law}(\tau^{(I),p}\oplus\rho^{(n-I),p})+(1-p)\operatorname{Law}(\tau^{(I),p}\ominus\rho^{(n-I),p}).$

We note that this is an equality for fixed $n\geq 1$, and it does not extend
to a recursive description of the law of the process $(\sigma^{(n),p})_{n\geq
1}$.

###### Proof.

For $n=2$, we have $\sigma^{(2),p}=12$ with probability $p$ and
$\sigma^{(2),p}=21$ with probability $1-p$. We will show that conditionally on
$\sigma^{(n),p}=12$, we have

$\operatorname{Law}(\sigma^{(n),p}|\sigma^{(2),p}=12)=\operatorname{Law}(\tau^{(I),p}\oplus\rho^{(n-I),p}).$
(13)

We recall that $(\sigma^{(n),p})_{n\geq 1}$ is defined recursively via
inflation operations, where one point is replaced by two adjacent points
(either in ascending or descending positions). In such operations, we will
think at the two new points as the “children” of the point they replace. This
defines an ascendant/descendant relation on the set of points of all
$\sigma^{(n),p}$ for $n\geq 1$.

In particular, points in $\sigma^{(n),p}$ can be split in two parts, defined
as the descendants of the points $1$ and $2$ in $\sigma^{(2),p}$. Let us call
$\tau$, resp. $\rho$, the pattern formed the descendants of $1$, resp. $2$.
Since points are always replaced by pairs of adjacent points, when
$\sigma^{(2),p}=12$, we have $\sigma^{(n),p}=\tau\oplus\rho$. Conditionally of
its size, which we call $k$, the permutation $\tau$ has the same distribution
as $\tau^{(k),p}$ since it is obtained from $1$ by successive random
inflations. Similarly, $\rho$ has the same distribution as $\rho^{(n-k),p}$.
Moreover, both are independent conditionally on $k$.

Therefore, the only remaining thing to be proven in order to establish (13) is
that $k$ is uniformly distributed in $\\{1,\dots,n-1\\}$. Letting $I_{j}$
being the number of descendants of $1$ in $\sigma^{(j),p}$, we see that
$(I_{j})_{j\geq 1}$ has the Markov property and

$\begin{cases}\mathbb{P}(I_{j}=k|I_{j-1}=k-1)=\frac{k-1}{j-1}\\\
\mathbb{P}(I_{j}=k|I_{j-1}=k)=\frac{j-1-k}{j-1}\end{cases}$

Using this and the base case $I_{2}=1$ a.s., an immediate induction shows
that, for any $j\geq 2$, the random variable $I_{j}$ is uniformly distributed
in $\\{1,\dots,j-1\\}$ (we remark that this is a basic model of Pólya urn.)
This concludes the proof of Eq. (13).

With similar arguments, one can prove

$\operatorname{Law}(\sigma^{(n),p}|\sigma^{(2),p}=21)\stackrel{{\scriptstyle
d}}{{=}}\operatorname{Law}(\tau^{(I),p}\ominus\rho^{(n-I),p}).$ (14)

Since $\mathbb{P}(\sigma^{(n),p}=12)=p=1-\mathbb{P}(\sigma^{(n),p}=21)$, the
proposition follows from Eqs. (13) and (14). ∎

###### Proof of Proposition 1.6.

Taking the limit $n\to+\infty$ in Proposition 4.2 gives $\bm{\mu}^{\text{\tiny
rec}}_{p}\stackrel{{\scriptstyle d}}{{=}}\Phi_{p}(\bm{\mu}^{\text{\tiny
rec}}_{p})$ (recall from Theorem 1.3 that $\sigma^{(n),p}$ converge a.s., and
hence in distribution to $\bm{\mu}^{\text{\tiny rec}}_{p}$). The uniqueness
statement in Proposition 1.6 follows from Lemma 4.1. ∎

###  4.2 Expected pattern densities

###### Proof of 1.7.

From 3.9, we know that $(\sigma^{(n),p})_{n\geq 1}$ is a consistent family of
random permutations. By [BBF+20, Proposition 2.9], there exists a random
permuton $\bm{\mu}$ such that $\sigma^{(n),p}$ converge to $\bm{\mu}$ in
distribution and, for each $n\geq 1$, the random permutation
$\operatorname{Sample}(\bm{\mu},n)$ has the same distribution as
$\sigma^{(n),p}$. On the other hand, $\sigma^{(n),p}$ converges almost surely
to $\bm{\mu}^{\text{\tiny rec}}_{p}$ (Theorem 1.3), so $\bm{\mu}$ and
$\bm{\mu}^{\text{\tiny rec}}_{p}$ must be equal in distribution. Therefore,

$\sigma^{(n),p}\stackrel{{\scriptstyle
d}}{{=}}\operatorname{Sample}(\bm{\mu},n)\stackrel{{\scriptstyle
d}}{{=}}\operatorname{Sample}(\bm{\mu}^{\text{\tiny rec}}_{p},n),\qquad n\geq
1.$

Together with [BBF+20, Theorem 2.5], this implies that

$\mathbb{E}\big{[}\operatorname{dens}(\pi,\bm{\mu}^{\text{\tiny
rec}}_{p})\big{]}=\mathbb{P}\big{[}\operatorname{Sample}(\bm{\mu}^{\text{\tiny
rec}}_{p},n)=\pi\big{]}=\mathbb{P}\big{[}\sigma^{(n),p}=\pi\big{]},\qquad\pi\in
S_{n}.$

This proves the first part of 1.7.

For the second part, we associate with a realization of the random sequence
$(\sigma^{(k),p})_{k\leq n}$ a (rooted binary increasing decorated) tree
$T_{n}$ such that $\operatorname{Perm}(T_{n})=\sigma^{(n),p}$ (where we use
the map $\operatorname{Perm}$ from trees to permutations introduced in Section
1.3.2). We proceed by induction on $n$. For $n=1$, the tree $T_{1}$ is reduced
to a single leaf. For $n\geq 1$, assume that $T_{n}$ is constructed and that
in the sampling process for $\sigma^{(n+1),p}$ (Section 1.1), we have chosen
some integer $j$ and some sign $s$ (where $s=+1$ means that $j$ is replaced by
$j\,j\\!+\\!1$ and $s=-1$ means that $j$ is replaced by $j\\!+\\!1\,j$). Then
$T_{n+1}$ is obtained by replacing the $j$-th leaf of $T_{n}$ by an internal
node with label $n$ and decoration $s$, with two children which are leaves. It
can be verified, using the induction hypothesis
$\operatorname{Perm}(T_{n})=\sigma^{(n),p}$, that
$\operatorname{Perm}(T_{n+1})=\sigma^{(n+1),p}$. Informally, $T_{n}$ encodes
the history of the construction of $\sigma^{(n),p}$. An example is given on
Fig. 10.

Figure 10: A realization of the process $(\sigma^{(k),p})_{k\leq 8}$ and the
associated tree $T_{8}$. Colors indicate points which have been selected for
inflation at each step, and the internal node created in the corresponding
step in the construction of $T_{n}$.

The above construction yields a random tree $T_{n}$ living in the same
probability space as $(\sigma^{(k),p})_{k\leq n}$. For a fixed (rooted binary
increasing decorated) tree $T$, the event $T_{n}=T$ amounts to making specific
choices of integers $j$ and signs $s$ at each step of the construction of
$(\sigma^{(k),p})_{k\leq n}$. Thus we have

$\mathbb{P}[T_{n}=T]=\frac{1}{(n-1)!}p^{\oplus(T)}(1-p)^{\ominus(T)},$

where $\oplus(T)$ and $\ominus(T)$ denote the number of $\oplus$ decorations
and $\ominus$ decorations in $T$ respectively. Since
$\operatorname{Perm}(T_{n})=\sigma^{(n),p}$, this implies that for a given
permutation $\pi$ of $n$,

$\mathbb{P}\big{[}\sigma^{(n),p}=\pi\big{]}=\frac{1}{(n-1)!}\sum_{T:\operatorname{Perm}(T)=\pi}p^{\oplus(T)}(1-p)^{\ominus(T)}.$

But an immediate inductive argument shows that whenever
$\operatorname{Perm}(T)=\sigma$, we have
$\ominus(T)=\operatorname{des}(\sigma)$, and consequently
$\oplus(T)=n-1-\operatorname{des}(\sigma)$. Therefore, all terms in the above
sum are equal, and we obtain

$\mathbb{P}\big{[}\sigma^{(n),p}=\pi\big{]}=\frac{N_{inc}(\pi)}{(n-1)!}\,(1-p)^{\operatorname{des}(\pi)}\,p^{n-1-\operatorname{des}(\pi)}.\qed$

###  4.3 Intensity measure

Recall that the intensity measure of $\bm{\mu}^{\text{\tiny rec}}_{p}$,
denoted $I\bm{\mu}^{\text{\tiny rec}}_{p}$, is a probability measure on
$[0,1]^{2}$ defined as follows: for all Borel subsets $A$ of $[0,1]^{2}$, we
have $I\bm{\mu}^{\text{\tiny rec}}_{p}(A)=\mathbb{E}[\bm{\mu}^{\text{\tiny
rec}}_{p}(A)]$. The goal of this section is to compute this intensity measure.
We start with a lemma.

######  Lemma 4.3.

The intensity measure $I\bm{\mu}^{\text{\tiny rec}}_{p}$ of the recursive
separable permuton is the distribution of $(U,\phi(U))$, where $U$ is a
uniform random variable in $[0,1]$, and $\phi$ the random function of Section
3.2.

###### Proof.

This is a straightforward analogue of [Maa20, Lemma 6.1]. ∎

####  4.3.1 Distributional equations

To go further, we consider the following map $\Psi_{p}$ from the set
$\mathcal{M}_{1}([0,1])$ of probability measures on $[0,1]$ to itself. If
$\nu$ is a probability measure on $[0,1]$, we let $X$ be a r.v. with
distribution $\nu$, and set

$Y=B\,V+(1-V)\,X,$

where $B$ is a Bernoulli variable with parameter $p$, $V$ is a uniform random
variable in $[0,1]$, and the two are independent from each other and from $X$.
We then define $\Psi_{p}(\nu)$ as the distribution of $Y$.

######  Lemma 4.4.

The equation $\nu=\Psi_{p}(\nu)$ has a unique solution in
$\mathcal{M}_{1}([0,1])$.

This solution will be denoted $\nu_{p}$ from now on.

###### Proof.

We will prove that $\Psi_{p}$ is a contracting map from
$\mathcal{M}_{1}([0,1])$ to itself, when we equip it with the first
Wasserstein metric. Namely, we let $\nu_{1}$ and $\nu_{2}$ be two probability
measures of $[0,1]$ and we shall prove that

$d_{W,1}\big{(}\Psi_{p}(\nu_{1}),\Psi_{p}(\nu_{2})\big{)}\leq\tfrac{1}{2}d_{W,1}\big{(}\nu_{1},\nu_{2}\big{)}.$
(15)

Fix $\varepsilon>0$ and choose r.v. $(X_{1},X_{2})$ on the same probability
space such that

$\mathbb{E}\big{[}\,|X_{1}-X_{2}|\,\big{]}\leq
d_{W,1}\big{(}\nu_{1},\nu_{2}\big{)}+\varepsilon.$

We then take a Bernoulli variable $B$ with parameter $p$ and a uniform random
variable $V$ in $[0,1]$, independent from each other and from $(X_{1},X_{2})$.
We set

$Y_{1}=V\cdot B+(1-V)\,X_{1},\qquad Y_{2}=V\cdot B+(1-V)\,X_{2}.$

Note that the variables $V$ and $B$ used to define $Y_{1}$ and $Y_{2}$ are the
same. We have

$\mathbb{E}\big{[}\,|Y_{1}-Y_{2}|\,\big{]}\leq\mathbb{E}\big{[}\,|1-V|\cdot|X_{1}-X_{2}|\,\big{]}\leq\tfrac{1}{2}\mathbb{E}\big{[}\,|X_{1}-X_{2}|\,\big{]}\leq\tfrac{1}{2}d_{W,1}\big{(}\nu_{1},\nu_{2}\big{)}+\tfrac{1}{2}\varepsilon.$

The random variables $Y_{1}$ and $Y_{2}$ are defined on the same probability
space, and have distributions $\Psi_{p}(\nu_{1})$ and $\Psi_{p}(\nu_{2})$
respectively. By definition of the Wasserstein distance, we have

$d_{W,1}\big{(}\Psi_{p}(\nu_{1}),\Psi_{p}(\nu_{2})\big{)}\leq\mathbb{E}\big{[}\,|Y_{1}-Y_{2}|\,\big{]}\leq\tfrac{1}{2}d_{W,1}\big{(}\nu_{1},\nu_{2}\big{)}+\tfrac{1}{2}\varepsilon.$

Since this holds for any $\varepsilon>0$, we have proved Eq. 15. We conclude
with Banach fixed point theorem that $\Psi_{p}$ has exactly one fixed point,
concluding the proof of the lemma. ∎

######  Proposition 4.5.

The intensity measure $I\bm{\mu}^{\text{\tiny rec}}_{p}$ of the recursive
separable permuton is the distribution of

$(U,\,UX_{p}+(1-U)X_{1-p}),$

where $U$, $X_{p}$ and $X_{1-p}$ are independent r.v. with distribution
$\operatorname{Leb}([0,1])$, $\nu_{p}$ and $\nu_{1-p}$ distribution
respectively.

###### Proof.

From Lemma 4.3, $I\bm{\mu}^{\text{\tiny rec}}_{p}$ is the distribution of
$(U,\phi(U))$, where $U$ is a uniform random variable in $[0,1]$ and $\phi$
the random mapping constructed in Section 3.2. We write $\phi(U)=Y_{1}+Y_{2}$,
with

$\begin{cases}Y_{1}=\operatorname{Leb}\big{(}\\{y:(y<U)\wedge(y\prec
U)\big{)};\\\ Y_{2}=\operatorname{Leb}\big{(}\\{y:(y>U)\wedge(y\prec
U)\big{)};\end{cases}$

In each of these equations, the first comparison is for the natural order on
$[0,1]$, while the second is for the random order $\prec$.

We shall describe the distribution of $Y_{2}$, conditionally on $U$. Let
$V_{1}$ be the first $U_{i}$ larger than $U$, “first” meaning here the one
with smallest index. We then denote $V_{2}$ to be the first $U_{i}$ between
$U$ and $V_{1}$ and define $V_{3},V_{4}\ldots$ similarly. Clearly, setting for
convenience $V_{0}=1$, we have

$(V_{j+1}-U)_{j\geq 0}\stackrel{{\scriptstyle
d}}{{=}}\big{(}T_{j+1}\,(V_{j}-U)\big{)}_{j\geq 0},$

where $(T_{1},T_{2},\cdots)$ is a sequence of i.i.d. uniform random variable
in $[0,1]$, independent from $U$. This implies

$(V_{j})_{j\geq 0}\stackrel{{\scriptstyle d}}{{=}}\big{(}U+(1-U)T_{1}\cdots
T_{j}\big{)}_{j\geq 0}.$

Each $V_{j}$ inherits a sign, i.e. if $V_{j}=U_{i}$, we set
$\varSigma_{j}=S_{i}$. By construction, if $\varSigma_{j}=\ominus$, every $y$
in the interval $[V_{j},V_{j-1}]$ satisfies $y\prec U$. On the other hand,
$\varSigma_{j}=\oplus$, every $y$ in the interval $[V_{j},V_{j-1}]$ satisfies
$y\succ U$. Hence

$Y_{2}=\sum_{j\geq 1:\ \varSigma_{j}=\ominus}(V_{j-1}-V_{j})=(1-U)\sum_{j\geq
1:\ \varSigma_{j}=\ominus}T_{1}\cdots T_{j-1}(1-T_{j}).$

Setting $\tilde{Y}_{2}=Y_{2}/(1-U)$ and interpreting $\oplus$ as $1$ and
$\ominus$ as $0$, we have

$\tilde{Y}_{2}=(1-\varSigma_{1})(1-T_{1})+T_{1}\left(\sum_{j\geq 2:\
\varSigma_{j}=\ominus}T_{2}\cdots(1-T_{j})\right).$

Note that $\tilde{Y}_{2}$ is independent from $U$. Moreover, the variable
$1-\varSigma_{j}$ is a Bernoulli r.v. of parameter $1-p$, while $T_{1}$ is
uniform in $[0,1]$. Finally, the sum in parentheses has the same distribution
as $\tilde{Y}_{1}$, and is independent from $\varSigma_{1}$ and $T_{1}$. This
shows that the distribution of $\tilde{Y}_{2}$ is a fixed point of
$\Psi_{1-p}$. From Lemma 4.4, $\tilde{Y}_{2}$ has distribution $\nu_{1-p}$.

With similar arguments, one can show that $Y_{1}=U\tilde{Y}_{1}$, where
$\tilde{Y}_{1}$ has distribution $\nu_{p}$ and is independent from $U$ (and
from $\tilde{Y}_{2}$). This ends the proof of the proposition. ∎

####  4.3.2 Explicit formulas for densities

######  Lemma 4.6.

The unique solution $\nu_{p}$ of the equation $\nu_{p}=\Psi(\nu_{p})$ is the
beta distribution of parameters $(p,1-p)$. Explicitly it is given by

$\nu_{p}(dx)=\frac{1}{\Gamma(p)\,\Gamma(1-p)}x^{p-1}(1-x)^{-p}\,dx,$

where $\Gamma$ is the usual gamma function.

###### Proof.

Let $X$ be a random variable with beta distribution of parameter $(p,1-p)$,
and set $Y=V\cdot B+(1-V)\,X$, where $B$ and $V$ are as above. We want to show
that $Y\stackrel{{\scriptstyle d}}{{=}}X$, which would imply the distribution
of $X$ is a fixed point of $\Psi$ as wanted.

Let $f$ be a continuous function on $[0,1]$. Setting
$Z=\Gamma(p)\,\Gamma(1-p)$, we have

$\displaystyle\mathbb{E}[f(Y)]$
$\displaystyle=\frac{p}{Z}\int_{[0,1]^{2}}f\big{(}v+(1-v)x\big{)}x^{p-1}(1-x)^{-p}\,dvdx$
$\displaystyle\qquad\qquad\qquad+\frac{1-p}{Z}\int_{[0,1]^{2}}f\big{(}(1-v)x\big{)}x^{p-1}(1-x)^{-p}\,dvdx$
$\displaystyle=\frac{p}{Z}\int_{0}^{1}f(u)\left(\int_{0}^{u}x^{p-1}(1-x)^{-p-1}dx\right)du+\frac{1-p}{Z}\int_{0}^{1}f(u)\left(\int_{u}^{1}x^{p-2}(1-x)^{-p}dx\right)du.$
(16)

(In the first integral, we have performed the change of variables
$u=v+(1-v)x$, yielding $dv=\frac{dx}{1-x}$; in the second, we set $u=(1-v)x$,
yielding $dv=\frac{du}{x}$.)

We claim that there exists a constant $A$ in $\mathbb{R}$, such that, for
every $u$ in $(0,1)$,

$p\int_{0}^{u}x^{p-1}(1-x)^{-p-1}dx+(1-p)\int_{u}^{1}x^{p-2}(1-x)^{-p}dx=u^{p-1}(1-u)^{-p}+A.$

Indeed, one checks easily that both sides have the same derivative. With this
equality in hand, (16) rewrites as

$\displaystyle\mathbb{E}[f(Y)]$
$\displaystyle=\frac{1}{Z}\int_{0}^{1}f(u)u^{p-1}(1-u)^{p-1}du+\frac{A}{Z}\int_{0}^{1}f(u)du$
$\displaystyle=\mathbb{E}[f(X)]+\frac{A}{Z}\int_{0}^{1}f(u)du.$

Choosing for $f$ the function constant equal to 1 shows that necessarily
$A=0$. Thus we have that $\mathbb{E}[f(Y)]=\mathbb{E}[f(X)]$ for any
continuous function $f$ of $[0,1]$, implying that $X$ and $Y$ have the same
distribution. This ends the proof of the lemma. ∎

Propostion 4.5 and Lemma 4.6 imply Proposition 1.9. It remains to prove
Corollary 1.10.

###### Proof of Corollary 1.10..

Let $f$ be a continuous function from $[0,1]^{2}$ to $\mathbb{R}$. From
Proposition 1.9, we have

$\int f(x,y)\,I\bm{\mu}^{\text{\tiny rec}}_{p}(dx,dy)\\\
=\frac{1}{\Gamma(p)^{2}\Gamma(1-p)^{2}}\int_{[0,1]^{3}}f\big{(}u,ua+(1-u)b\big{)}\,du\,a^{p-1}(1-a)^{-p}da\,b^{-p}(1-b)^{p-1}db$

We perform the change of variable

$x=u;\quad y=ua+(1-u)b;\quad z=ua$

This maps bijectively the $(u,a,b)$-domain $[0,1]^{3}$ to the set

$\\{(x,y,z):\,\max(x+y-1,0)\leq z\leq\min(x,y)\\}.$

The Jacobian matrix of the transformation is

$J:=\frac{\partial(x,y,z)}{\partial(u,a,b)}=\begin{pmatrix}1&0&0\\\
a-b&u&1-u\\\ a&u&0\end{pmatrix},$

whose determinant satisfies $|\det(J)|=u(1-u)=x(1-x)$. Therefore we have

$\int f(x,y)\,I\bm{\mu}^{\text{\tiny
rec}}_{p}(dx,dy)=\frac{1}{\Gamma(p)^{2}\Gamma(1-p)^{2}}\int_{[0,1]^{2}}\Bigg{[}f(x,y)\cdot\\\
\cdot\left(\int_{\max(x+y-1,0)}^{\min(x,y)}\,\big{(}\tfrac{z}{x}\big{)}^{p-1}\big{(}1-\tfrac{z}{x}\big{)}^{-p}\,\big{(}\tfrac{y-z}{1-x}\big{)}^{-p}\big{(}1-\tfrac{y-z}{1-x}\big{)}^{p-1}dz\right)\frac{dx\,dy}{x(1-x)}\bigg{]}.$

After elementary simplifications, we get

$\int f(x,y)\,I\bm{\mu}^{\text{\tiny
rec}}_{p}(dx,dy)=\frac{1}{\Gamma(p)^{2}\Gamma(1-p)^{2}}\int_{[0,1]^{2}}\Bigg{[}f(x,y)\cdot\\\
\left(\int_{\max(x+y-1,0)}^{\min(x,y)}\frac{dz}{z^{1-p}(x-z)^{p}(y-z)^{p}(1-x-y+z)^{1-p}}\right)dx\,dy\bigg{]}.$

This proves Corollary 1.10. ∎

###  4.4 Mutual singularity of the limiting permutons

In this section, we prove 1.4 in two independent steps. First, we prove the
singularity of separable Brownian or recursive separable permutons associated
with different values $p$ and $q$ of the parameter. Then we compare
specifically Brownian and recursive separable permutons $\bm{\mu}^{\text{\tiny
rec}}_{p}$ and $\bm{\mu}^{\text{\tiny Br}}_{p}$, associated with the same
value $p$ of the parameter.

Before starting the proof, let us recall briefly the construction of
$\bm{\mu}^{\text{\tiny Br}}_{p}$, given in [Maa20]. We start with a Brownian
excursion $\operatorname{\mathfrak{e}}$ on $[0,1]$ and a sequence
$(S_{m})_{m\in\operatorname{Min}(\operatorname{\mathfrak{e}})}$ of signs
indexed by local minima of $\operatorname{\mathfrak{e}}$. Conditionally on
$\operatorname{\mathfrak{e}}$, the variables
$(S_{m})_{m\in\operatorname{Min}(\operatorname{\mathfrak{e}})}$ are i.i.d.
with the following distribution:
$\mathbb{P}(S_{m}=\oplus)=p=1-\mathbb{P}(S_{m}=\ominus)$. Given such a
sequence we define a partial order $\prec_{\text{Br}}$ as follows: for $x<y$
in $[0,1]$, we let $m$ be the position of the minimum of
$\operatorname{\mathfrak{e}}$ on the interval $[x,y]$ and set

$\begin{cases}x\prec_{\text{Br}}y&\text{ if }S_{m}=\oplus;\\\
y\prec_{\text{Br}}x&\text{ if }S_{m}=\ominus.\end{cases}$

Note that, if $m\in\\{x,y\\}$, then $m$ might not be a local minimum, in which
case $S_{m}$ is ill-defined and $x$ and $y$ are incomparable by convention.
This happens only for a measure $0$ subset of pairs $(x,y)$ (w.r.t. Lebesgue
measure).

The rest of the construction is then similar to that of the recursive
separable permuton: we define

$\phi_{\text{Br}}(x)=\operatorname{Leb}(\\{y\in[0,1]:y\prec_{\text{Br}}x\\}),$

and let $\bm{\mu}^{\text{\tiny Br}}_{p}$ be the push-forward of the Lebesgue
measure on $[0,1]$ by the map $x\mapsto(x,\phi_{\text{Br}}(x))$.

####  4.4.1 Comparing permutons with different values of $p$

We recall from Section 1.3.2 that given a permuton $\mu$ and an integer $n\geq
1$, we can define a random permutation $\operatorname{Sample}(\mu,n)$ by
sampling independent points according to $\mu$. Also, for a permutation $\pi$,
we let $\operatorname{des}(\pi)$ be its number of descents. We start with a
lemma.

######  Lemma 4.7.

Let $p$ be in $(0,1)$. Then the random variable

$D_{n}=D_{n}(\bm{\mu}^{\text{\tiny
rec}}_{p}):=\frac{1}{n-1}\mathbb{E}\big{[}\operatorname{des}(\operatorname{Sample}(\bm{\mu}^{\text{\tiny
rec}}_{p},n))\big{|}\,\bm{\mu}^{\text{\tiny rec}}_{p}\big{]}.$

converges to $1-p$ a.s. Moreover, the same holds replacing
$\bm{\mu}^{\text{\tiny rec}}_{p}$ by $\bm{\mu}^{\text{\tiny Br}}_{p}$.

###### Proof.

We have

$\mathbb{E}(D_{n})=\frac{1}{n-1}\mathbb{E}\big{[}\operatorname{des}(\operatorname{Sample}(\bm{\mu}^{\text{\tiny
rec}}_{p},n))\big{]}.$

From the proof of 1.7, the permutation
$\operatorname{Sample}(\bm{\mu}^{\text{\tiny rec}}_{p},n)$ has the same
distribution as the permutation represented by a uniform random increasing
binary tree $T_{n}$, where each internal node is decorated with $\oplus$
independently with probability $p$. As already observed, if $\pi$ is encoded
by a binary decorated tree $T$, then $\operatorname{des}(\pi)$ is the number
of $\ominus$ signs in $T$. Hence
$\operatorname{des}(\operatorname{Sample}(\bm{\mu}^{\text{\tiny rec}}_{p},n))$
is the number of minus signs in $T_{n}$, and its law is that of a binomial
random variable $\operatorname{Bin}(n-1,1-p)$. We deduce that
$\mathbb{E}(D_{n})=1-p$.

To get a.s. convergence, we consider the fourth centered moment of $D_{n}$. We
have, using Jensen’s inequality for conditional expectation,

$\displaystyle\mathbb{E}\big{[}(D_{n}-(1-p))^{4}\big{]}$
$\displaystyle=\mathbb{E}\bigg{[}\mathbb{E}\Big{(}\tfrac{1}{n-1}\operatorname{des}(\operatorname{Sample}(\bm{\mu}^{\text{\tiny
rec}}_{p},n))-(1-p)\big{|}\,\bm{\mu}^{\text{\tiny
rec}}_{p}\Big{)}^{4}\bigg{]}$
$\displaystyle\leq\mathbb{E}\bigg{[}\mathbb{E}\Big{[}\Big{(}\tfrac{1}{n-1}\operatorname{des}(\operatorname{Sample}(\bm{\mu}^{\text{\tiny
rec}}_{p},n))-(1-p)\Big{)}^{4}\Big{|}\,\bm{\mu}^{\text{\tiny
rec}}_{p}\Big{]}\bigg{]}$
$\displaystyle=\mathbb{E}\bigg{[}\Big{(}\tfrac{1}{n-1}\operatorname{des}(\operatorname{Sample}(\bm{\mu}^{\text{\tiny
rec}}_{p},n))-(1-p)\Big{)}^{4}\bigg{]}.$

The expectation in the right-hand side is the centered fourth moment of the
average of $n-1$ independent Bernoulli random variables of parameter $1-p$,
which is known to behave as $O(n^{-2})$. We get that

$\mathbb{E}\big{[}(D_{n}-(1-p))^{4}\big{]}=O(n^{-2}),$

and hence it is a summable quantity. By a classical application of
Borel–Cantelli lemma, this implies that $D_{n}$ converges a.s. to $1-p$.

The proof for the Brownian separable permuton is similar. Indeed, from [Maa20,
Definition 2], we know that the quantity
$\operatorname{des}(\operatorname{Sample}(\bm{\mu}^{\text{\tiny Br}}_{p},n))$
is also distributed as a binomial random variable
$\operatorname{Bin}(n-1,1-p)$. ∎

######  Corollary 4.8.

If $p\neq q$ are in $(0,1)$, then $\bm{\mu}^{\text{\tiny rec}}_{p}$ and
$\bm{\mu}^{\text{\tiny rec}}_{q}$ are mutually singular. The same holds,
replacing either $\bm{\mu}^{\text{\tiny rec}}_{p}$ or $\bm{\mu}^{\text{\tiny
rec}}_{q}$, or both, by $\bm{\mu}^{\text{\tiny Br}}_{p}$ or
$\bm{\mu}^{\text{\tiny Br}}_{q}$.

###### Proof.

Let $E_{p}$ be the set of permutons $\mu$ such that
$D_{n}(\mu):=\frac{1}{n-1}\mathbb{E}\big{[}\operatorname{des}(\operatorname{Sample}(\mu,n))\big{]}$
converges to $1-p$ (we do not take a conditional expectation here, since $\mu$
is deterministic). By Lemma 4.7, $\bm{\mu}^{\text{\tiny rec}}_{p}$ and
$\bm{\mu}^{\text{\tiny Br}}_{p}$ belongs to $E_{p}$ a.s. Since $E_{p}$ and
$E_{q}$ are disjoint for $p\neq q$, the corollary follows. ∎

####  4.4.2 Comparing the Brownian and recursive separable permutons with the
same parameter

We now want to prove that $\bm{\mu}^{\text{\tiny rec}}_{p}$ and
$\bm{\mu}^{\text{\tiny Br}}_{p}$ are singular. Since both
$D_{n}(\bm{\mu}^{\text{\tiny rec}}_{p})$ and $D_{n}(\bm{\mu}^{\text{\tiny
Br}}_{p})$ converge to the same value $1-p$ a.s., we need to find another
distinguishing feature. We will prove that in the Brownian separable permuton,
all corners of the square a.s. carry some mass, which is not the case for the
recursive separable permuton.

To this end, for $\varepsilon>0$, we introduce the following events (we recall
that $\mathcal{P}$ is the set of permutons):

$\displaystyle\operatorname{BL}_{\varepsilon}$
$\displaystyle=\\{\mu\in\mathcal{P}:\mu([0,\varepsilon]^{2})>0\\}$
$\displaystyle\operatorname{TL}_{\varepsilon}$
$\displaystyle=\\{\mu\in\mathcal{P}:\mu([0,\varepsilon]\times[1-\varepsilon,1])>0\\}.$

In words, $\operatorname{BL}_{\varepsilon}$ is the set of permutons that have
some mass in an $\varepsilon$-neighbourhood of the bottom-left corner;
$\operatorname{TL}_{\varepsilon}$ is the same using the top-left corner.

We now prove two lemmas, showing that the Brownian and recursive separable
permutons behave differently with respect to these events. We start with the
recursive separable permuton.

######  Lemma 4.9.

Fix $p\in(0,1)$ and $\varepsilon>0$. We have

$\mathbb{P}\big{(}\bm{\mu}^{\text{\tiny
rec}}_{p}\in\operatorname{BL}_{\varepsilon}\cap\operatorname{TL}_{\varepsilon}\big{)}\leq
2\varepsilon.$

###### Proof.

We recall the construction of $\bm{\mu}^{\text{\tiny rec}}_{p}$ from Section
3.2, and use the notation introduced there.

We temporarily assume that $U_{1}$ is in $(\varepsilon,1-\varepsilon)$ and
that $S_{1}=\oplus$. We consider some $x<\varepsilon$. For any $y\geq U_{1}$,
we have $U_{1}\in(x,y]$, and therefore $i_{x,y}=1$ with the notation of
Section 3.2. Since $x<y$ and $S_{1}=\oplus$, this implies $x\prec y$. Taking
the contraposition, $y\prec x$ implies $y<U_{1}$. Therefore,

$\phi(x)=\operatorname{Leb}(\\{y\in[0,1]:y\prec
x\\})\leq\operatorname{Leb}(\\{y\in[0,1]:y<U_{1}\\}\leq U_{1}<1-\varepsilon.$

Thus there does not exists $x$ such that
$(x,\phi(x))\in[0,\varepsilon]\times[1-\varepsilon,1]$. Consequently, under
the assumptions $U_{1}\in(\varepsilon,1-\varepsilon)$ and $S_{1}=\oplus$, we
have

$\bm{\mu}^{\text{\tiny
rec}}_{p}([0,\varepsilon]\times[1-\varepsilon,1])=0,\text{ or equivalenlty,
}\bm{\mu}^{\text{\tiny rec}}_{p}\notin\operatorname{TL}_{\varepsilon}.$

Similarly, one can prove that, if $U_{1}$ is in $(\varepsilon,1-\varepsilon)$
and $S_{1}=\ominus$, then $\bm{\mu}^{\text{\tiny
rec}}_{p}\notin\operatorname{BL}_{\varepsilon}$. Therefore we have

$\mathbb{P}\big{(}\bm{\mu}^{\text{\tiny
rec}}_{p}\in\operatorname{BL}_{\varepsilon}\cap\operatorname{TL}_{\varepsilon}\big{)}\leq\mathbb{P}\big{(}U_{1}\notin(\varepsilon,1-\varepsilon)\big{)}\leq
2\varepsilon.\qed$

Considering the Brownian separable permuton instead, we have the following.

######  Lemma 4.10.

Fix $p\in(0,1)$ and $\varepsilon>0$. We have

$\mathbb{P}\big{(}\bm{\mu}^{\text{\tiny
Br}}_{p}\in\operatorname{BL}_{\varepsilon}\big{)}=1.$

###### Proof.

As recalled above, $\bm{\mu}^{\text{\tiny Br}}_{p}$ can be constructed
starting from a Brownian excursion $\operatorname{\mathfrak{e}}$ and a
sequence of sign
$(S_{m})_{m\in\operatorname{Min}(\operatorname{\mathfrak{e}})}$ indexed by the
(positions of) the local minima of $\operatorname{\mathfrak{e}}$. We fix a
realization of $\operatorname{\mathfrak{e}}$ and
$\bm{S}=(S_{m})_{m\in\operatorname{Min}(\operatorname{\mathfrak{e}})}$ (and
hence of $\bm{\mu}^{\text{\tiny Br}}_{p}$); most quantities below, including
the random order $\prec_{\text{Br}}$ and the function $\phi_{\text{Br}}$,
depend implicitly on $\operatorname{\mathfrak{e}}$ and $\bm{S}$. Our first
goal is to find a local minimum $m_{0}$ of $\operatorname{\mathfrak{e}}$, such
that $S_{m_{0}}=\oplus$, $m_{0}<\varepsilon/2$ and
$\operatorname{\mathfrak{e}}(m_{0})<\min_{t\in[m_{0},1-\varepsilon/2]}\operatorname{\mathfrak{e}}(t)$.
Since the proof involves quite a bit of notation, we illustrate it on Fig. 11.

Figure 11: Illustration of the notation involved in the proof of Lemma 4.10.
For readability, we only represented an initial segment of the Brownian
excursion $\operatorname{\mathfrak{e}}$. In the picture, we have
$S_{x_{1}}=\ominus$ so that we have to find another candidate $x_{2}$ as
explained in the proof. This time we have $S_{x_{2}}=\oplus$ and we set
$m_{0}=x_{2}$.

To do, let
$b=\min_{t\in[\varepsilon/2,1-\varepsilon/2]}\operatorname{\mathfrak{e}}(t)$.
and $x_{0}=\sup\\{t<\varepsilon/2:\operatorname{\mathfrak{e}}(t)=m\\}$. A.s.,
we can then find $a_{0}<x_{0}$ such that $\operatorname{\mathfrak{e}}$ reaches
its minimum on $[a_{0},x_{0}]$ somewhere in the interior of this interval (if
it was not the case, $\operatorname{\mathfrak{e}}$ would be increasing on an
initial segment $[0,\delta]$ for some $\delta$, which is known to happen with
probability $0$). Let $x_{1}$ be the point where $\operatorname{\mathfrak{e}}$
is minimal on $[a_{0},x_{0}]$. This is a local minimum, and therefore carries
a sign $S_{x_{1}}$. If $S_{x_{1}}=\oplus$, we define $m_{0}=x_{1}$, and we
verify easily that it satisfies the desired properties.

Otherwise, we iterate the process: a.s., we can then find $a_{1}<x_{1}$ such
that $\operatorname{\mathfrak{e}}$ reaches its minimum on $[a_{1};x_{1}]$
somewhere in the interior of this interval. We call $x_{2}$ the point where
this minimum is reached. If $S_{x_{2}}=\oplus$, we define $m_{0}=x_{2}$. If
not, we iterate another time. Doing so, we will construct a sequence of local
minima $x_{1},x_{2},\dots$, and since the associated signs are i.i.d. and
equal to $\oplus$ with positive probability, we will eventually find $x_{i}$
with $S_{x_{i}}=\oplus$. Then we set $m_{0}=x_{i}$, and verify easily that
$m_{0}$ satisfies the desired properties.

Having found $m_{0}$, we look for the last time $t_{0}$ before $m_{0}$ with
$\operatorname{\mathfrak{e}}(t_{0})=\operatorname{\mathfrak{e}}(m_{0})$. By
construction, if we take $x$ in $(t_{0},m_{0})$ and $y$ in
$(m_{0},1-\varepsilon/2)$ the minimum of $\operatorname{\mathfrak{e}}$ in the
interval $[x,y]$ is reached in $m_{0}$. Since $S_{m_{0}}=\oplus$, we have
$x\prec_{\text{Br}}y$, where $\prec_{\text{Br}}$ is the order appearing in the
construction of the Brownian separable permuton. Therefore, for $x$ in
$(t_{0},m_{0})$, we have

$\phi_{\text{Br}}(x)=\operatorname{Leb}(\\{y\in[0,1]:y\prec_{\text{Br}}x\\})\leq
1-\operatorname{Leb}((m_{0},1-\varepsilon/2))=m_{0}+\varepsilon/2<\varepsilon.$

Letting $U$ be a uniform random variable in $[0,1]$, we have, a.s.,

$\bm{\mu}^{\text{\tiny
Br}}_{p}([0,\varepsilon]^{2})=\mathbb{P}\big{(}(U,\phi_{\text{Br}}(U))\in[0,\varepsilon]^{2}|(\operatorname{\mathfrak{e}},\bm{S})\big{)}\geq\mathbb{P}\big{(}U\in(t_{0},m_{0})|(\operatorname{\mathfrak{e}},\bm{S})\big{)}=m_{0}-t_{0}>0;$

(recall that $m_{0}$ and $t_{0}$ depends on
$(\operatorname{\mathfrak{e}},\bm{S})$ and thus are random variables
themselves). This proves the lemma. ∎

######  Corollary 4.11.

Fix $p$ in $(0,1)$. Then the distributions of $\bm{\mu}^{\text{\tiny
rec}}_{p}$ and $\bm{\mu}^{\text{\tiny Br}}_{p}$ are mutually singular.

###### Proof.

We consider the decreasing intersection

$E:=\bigcap_{\varepsilon>0}(\operatorname{BL}_{\varepsilon}\cap\operatorname{TL}_{\varepsilon}).$

From Lemma 4.9, we know that $\mathbb{P}\big{(}\bm{\mu}^{\text{\tiny
rec}}_{p}\in E)=0$. On the other hand, Lemma 4.10 tells us that, for any
$\varepsilon>0$, we have

$\mathbb{P}\big{(}\bm{\mu}^{\text{\tiny
Br}}_{p}\in\operatorname{BL}_{\varepsilon}\big{)}=1.$

By symmetry, the same holds replacing $\operatorname{BL}_{\varepsilon}$ by
$\operatorname{TL}_{\varepsilon}$, and thus, for any $\varepsilon>0$,

$\mathbb{P}\big{(}\bm{\mu}^{\text{\tiny
Br}}_{p}\in\operatorname{BL}_{\varepsilon}\cap\operatorname{TL}_{\varepsilon}\big{)}=1.$

Consequently, $\mathbb{P}\big{(}\bm{\mu}^{\text{\tiny rec}}_{p}\in E)=1$,
proving the corollary. ∎

######  Remark 4.12.

The difference between recursive and Brownian separable permutons which we
exhibited in the proof can be observed on simulations. Fig. 12 shows
simulations of a random recursive separable permutation with parameter $p=1/2$
(on the left) and of a uniform random separable permutation (on the right),
both of size 1000. From the result of this paper and of [BBF+18], the
corresponding limiting permutons are the recursive and Brownian separable
permutons, respectively, each time of parameter $p=1/2$. We see that in the
Brownian case (picture on the right), there are some points relatively close
to each one of the four corners of the square, which is not the case in the
recursive case (picture on the left).

Figure 12: Diagram of random separable permutations of 1000: on the left, the
permutation has been generated via the recursive algorithm given in Section
1.1; on the right it is a uniform random separable permutation of size 1000
(sampled via the so-called recursive method).

## Acknowledgements

An important part of this work was conducted while the second author (KRL) was
a postdoctoral fellow at Université de Lorraine founded by the I-Site Lorraine
Université d’Excellence (LUE). Both authors are grateful to LUE for this
opportunity.

The authors would like to thank Cyril Marzouk for a discussion about recursive
models of tree-like structures, and in particular for pointing out reference
[CLG11].

Finally, simulations of Figs. 2, 7 and 12 were done with the computer algebra
software SageMath [Sag21]. The authors are grateful to its developers for
their wonderful job.

## References

  * [Ald94] D. Aldous.  Triangulating the circle, at random.  Am. Math. Mon., 101(3):223–233, 1994.
  * [BBD+22] F. Bassino, M. Bouvel, M. Drmota, V. Féray, L. Gerin, M. Maazoun, and A. Pierrot.  Linear-sized independent sets in random cographs and increasing subsequences in separable permutations.  Combin. Th., 2(3):35 pages, 2022.
  * [BBF+18] F. Bassino, M. Bouvel, V. Féray, L. Gerin, and A. Pierrot.  The Brownian limit of separable permutations.  Ann. Probab., 46(4):2134–2189, 2018.
  * [BBF+20] F. Bassino, M. Bouvel, V. Féray, L. Gerin, M. Maazoun, and A. Pierrot.  Universal limits of substitution-closed permutation classes.  J. Eur. Math. Soc., 22(11):3565–3639, 2020.
  * [BBF+22] F. Bassino, M. Bouvel, V. Féray, L. Gerin, M. Maazoun, and A. Pierrot.  Random cographs: Brownian graphon limit and asymptotic degree distribution.  Random Structures & Algorithms, 60(2):166–200, 2022.
  * [BBL98] P. Bose, J. F. Buss, and A. Lubiw.  Pattern matching for permutations.  Inf. Process. Lett., 65(5):277–283, 1998.
  * [BGS22] J. Borga, E. Gwynne, and X. Sun.  Permutons, meanders, and SLE-decorated Liouville quantum gravity, 2022\.  preprint arXiv:2207.0239.
  * [BHSY23] J. Borga, N. Holden, X. Sun, and P. Yu.  Baxter permuton and liouville quantum gravity.  Probability Theory and Related Fields, pages 1–49, 2023.
  * [BM17] B. B. Bhattacharya and S. Mukherjee.  Degree sequence of random permutation graphs.  Ann. Appl. Probab., 27(1):439–484, 2017.
  * [Bor21] J. Borga.  The skew Brownian permuton: a new universality class for random constrained permutations, 2021.  preprint arXiv:2112.00156.
  * [CD08] P. Clement and W. Desch.  An elementary proof of the triangle inequality for the Wasserstein metric.  Proc. Am. Math. Soc., 136(1):333–339, 2008.
  * [CLG11] N. Curien and J.-F. Le Gall.  Random recursive triangulations of the disk via fragmentation theory.  Ann. Probab., 39(6):2224–2270, 2011.
  * [Grü22] R. Grübel.  Ranks, copulas, and permutons.  preprint arXiv:2206.12153, 2022.
  * [HKM+13] C. Hoppen, Y. Kohayakawa, C. G. Moreira, B. Ráth, and R. Menezes Sampaio.  Limits of permutation sequences.  J. Combin. Theory Ser. B, 103(1):93–113, 2013.
  * [Maa20] M. Maazoun.  On the Brownian separable permuton.  Combinatorics, Probability and Computing, 29(2):241–266, 2020.
  * [Pin21] R. G. Pinsky.  The infinite limit of separable permutations.  Random Struct. & Algo., 59(4):622–639, 2021.
  * [Sag21] Sage Developers.  SageMath, the Sage Mathematics Software System (Version 9.4), 2021.  https://www.sagemath.org.
  * [Stu21] B. Stufler.  Graphon convergence of random cographs.  Random Structures & Algorithms, 59(3):464–491, 2021.