# Cutoff for the Asymmetric Riffle Shuffle

Mark Sellke  Department of Mathematics, Stanford University.

###### Abstract

In the Gilbert-Shannon-Reeds shuffle, a deck of $N$ cards is cut into two
approximately equal parts which are riffled together uniformly at random.
Bayer and Diaconis [BD92] famously showed that this Markov chain undergoes
cutoff in total variation after $\frac{3\log(N)}{2\log(2)}$ shuffles. We
establish cutoff for the more general _asymmetric_ riffle shuffles in which
one cuts the deck into differently sized parts. The value of the cutoff point
confirms a conjecture of [Lal00]. Some appealing consequences are that
asymmetry always slows mixing and that total variation mixing is strictly
faster than separation and $L^{\infty}$ mixing.

###### Contents

  1. 1 Introduction
    1. 1.1 Main Result
  2. 2 Preliminaries
    1. 2.1 Intuition Based on an Independent Point Process
    2. 2.2 Notation
  3. 3 Upper Bound Approach
    1. 3.1 High-Level Approach
    2. 3.2 Proof of Lemmas 3.1 and 3.5
  4. 4 Upper Bounding the Expected Shared Edges
    1. 4.1 Preparation for the Upper Bound Proof
    2. 4.2 Proof Outline for Proposition 4.1
    3. 4.3 The Partition into Stable Blocks
    4. 4.4 No Edge Intersections in Expectation
    5. 4.5 Informal Derivation of the Value $C_{\operatorname{\mathbf{p}}}$
  5. 5 Proof of Lemma 3.8
    1. 5.1 Preparatory Lemmas
    2. 5.2 The Edge-Exploration Process
    3. 5.3 Proof of Lemma 3.8
  6. 6 Proof of the Mixing Time Lower Bound
    1. 6.1 Preparation and Proof Idea
    2. 6.2 Lower Bounding the Number of $G$-Edges Inside $H$

##  1 Introduction

The riffle shuffle is among the most common methods to randomize a deck of
cards. We study a parameterized model for riffle shuffles called $p$-shuffles,
defined as follows for any $p\in(0,1)$. From a sorted deck of $N$ cards, first
remove the top $\text{\tt{Bin}}(N,p)$ cards to create a top and a bottom pile.
Next, interleave the two piles according to the following rule. If the piles
currently have sizes $A$ and $B$, the next card is dropped from the first pile
with probability $\frac{A}{A+B}$. Conditioned on the pile sizes, this rule
gives a uniformly random interleaving.

The case $p=\frac{1}{2}$, known as the Gilbert-Shannon-Reeds (GSR) shuffle, is
perhaps the most natural model for riffle shuffling. It was analyzed by Bayer
and Diaconis in [BD92] following work of Aldous ([Ald83, Example 4.17]); they
proved that $\left(\frac{3}{2\log(2)}\pm o(1)\right)\log(N)$ shuffles are
necessary and sufficient to randomize a deck. More precisely for any
$\varepsilon>0$, as $N\to\infty$ the total variation distance of the deck from
a uniform permutation tends to $1$ after
$\left\lfloor\left(\frac{3}{2\log(2)}-\varepsilon\right)\log(N)\right\rfloor$
shuffles, and tends to $0$ after
$\left\lfloor\left(\frac{3}{2\log(2)}+\varepsilon\right)\log(N)\right\rfloor$
shuffles. In fact they showed that the total variation distance decays
exponentially in $C$ after $\frac{3\log(N)}{2\log(2)}+C$ shuffles.

By contrast, determining the mixing time for general $p$-shuffles has remained
open. This discrepancy is because of a special property underpining the
analysis in [BD92]: the deck order after a fixed number of GSR shuffles is
uniformly random conditioned on its number of _rising sequences_. Therefore to
understand the mixing time it suffices to understand how the number of rising
sequences is distributed. This distribution turns out to admit a simple closed
form, which enables explicit analysis and a sharp understanding of the rate of
convergence. When $p\neq\frac{1}{2}$ this conditional uniformity no longer
holds and the problem becomes more complicated.

$p$-shuffles were introduced in [DFP92, Example 7] and further studied in
[Lal96, Ful98, Lal00]. These works established upper and lower bounds of order
$\log(N)$ on the mixing time, but with differing constant factors.
Interestingly the eigenvalues of the $p$-shuffle chain are given explicitly by
certain power sum symmetric functions. This follows from general results
regarding random walks on hyperplane arrangements — see [BHR99, BD98, Sta01]
or the survey [Zha09].

Several aspects of riffle shuffles are surveyed in [Dia03]. Other interesting
models arise from modifying the interleaving probabilities, such as the Thorpe
shuffle [Tho73, Mor09, Mor13] and clumpy shuffle [JM15].

###  1.1 Main Result

In this paper we prove that all $p$-shuffles exhibit cutoff. More generally,
let $\operatorname{\mathbf{p}}=(p_{0},\dots,p_{k-1})$ be a discrete
probability distribution with $p_{i}>0$ for each $i$. We show cutoff for the
more general $\operatorname{\mathbf{p}}$-shuffles, which were also introduced
in [DFP92]. To define such a shuffle, one first generates a multinomial
$(N,\operatorname{\mathbf{p}})$ vector $(n_{0},\dots,n_{k-1})$ so that each
$n_{i}$ has marginal distribution $n_{i}\sim\text{\tt{Bin}}(N,p_{i})$ and
$\sum_{i=0}^{k-1}n_{i}=N$ holds almost surely. One then splits the $N$ cards
into $k$ piles by taking the top $n_{0}$ cards off the top to form the first
pile, the next $n_{1}$ cards to form the second pile, and so on.

Interleaving the $k$ piles into a single pile is done similarly to the $k=2$
case. Namely, if the current remaining pile sizes are $A_{0},\dots,A_{k-1}$,
then the next card is dropped from pile $i$ with probability

$\frac{A_{i}}{A_{0}+A_{1}+\dots+A_{k-1}}.$ (1.1)

This latter phase is again equivalent to interleaving the $k$ piles uniformly
at random conditioned on their sizes. Note that the asymmetry of
$\operatorname{\mathbf{p}}$ appears only in the first phase to determine the
pile sizes and does not directly enter the second phase. When
$\operatorname{\mathbf{p}}=\left(\frac{1}{k},\frac{1}{k},\dots,\frac{1}{k}\right)$,
we recover the $k$-shuffle which is the $k$-partite analog of the GSR shuffle.
$k$-shuffles exhibit cutoff after $\frac{3\log(N)}{2\log k}\pm O(1)$ steps by
the same rising sequence analysis as in the $k=2$ case ([BD92]).

To state our main result for general $\operatorname{\mathbf{p}}$-shuffles, we
must define several constants. With arbitrary tie-breaking, set
$i_{\text{\tt{max}}}=\arg\max_{i\in\\{0,1,\dots,k-1\\}}(p_{i})$ and
$p_{\text{\tt{max}}}=p_{i_{\text{\tt{max}}}}$. Similarly define
$i_{\text{\tt{min}}}$ and $p_{\text{\tt{min}}}$. Define the functions

$\phi_{\operatorname{\mathbf{p}}}(t)=\sum_{i=0}^{k-1}p_{i}^{t},\quad\quad\psi_{\operatorname{\mathbf{p}}}(t)=-\log\phi_{\operatorname{\mathbf{p}}}(t).$

Define the positive constant $\theta_{\operatorname{\mathbf{p}}}$ by the
identity
$\psi_{\operatorname{\mathbf{p}}}(\theta_{\operatorname{\mathbf{p}}})=2\psi_{\operatorname{\mathbf{p}}}(2)$,
i.e.

$\phi_{\operatorname{\mathbf{p}}}(\theta_{\operatorname{\mathbf{p}}})=\sum_{i=0}^{k-1}p_{i}^{\theta_{\operatorname{\mathbf{p}}}}=\left(\sum_{i=0}^{k-1}p_{i}^{2}\right)^{2}=\phi_{\operatorname{\mathbf{p}}}(2)^{2}.$

This uniquely determines $\theta_{\operatorname{\mathbf{p}}}$ because
$\phi_{\operatorname{\mathbf{p}}}$ and $\psi_{\operatorname{\mathbf{p}}}$ are
strictly monotone. Finally define the constants
$C_{\operatorname{\mathbf{p}}},\widetilde{C}_{\operatorname{\mathbf{p}}},$ and
$\overline{C}_{p}$ as follows.

$\displaystyle C_{\operatorname{\mathbf{p}}}$
$\displaystyle=\frac{3+\theta_{\operatorname{\mathbf{p}}}}{4\psi_{\operatorname{\mathbf{p}}}(2)}=\frac{3+\theta_{\operatorname{\mathbf{p}}}}{2\psi_{\operatorname{\mathbf{p}}}(\theta_{\operatorname{\mathbf{p}}})},$
$\displaystyle\widetilde{C}_{\operatorname{\mathbf{p}}}$
$\displaystyle=\frac{1}{\log(1/p_{\text{\tt{max}}})},$
$\displaystyle\overline{C}_{\operatorname{\mathbf{p}}}$
$\displaystyle=\max(\widetilde{C}_{\operatorname{\mathbf{p}}},C_{\operatorname{\mathbf{p}}}).$

We can now state our main result.

######  Theorem 1.

The $\operatorname{\mathbf{p}}$-shuffles undergo total variation cutoff after
$\overline{C}_{\operatorname{\mathbf{p}}}\log(N)$ steps. That is, for any
$\varepsilon>0$,

$\displaystyle\lim_{N\to\infty}d_{N}(\lfloor(1-\varepsilon)\overline{C}_{\operatorname{\mathbf{p}}}\log(N)\rfloor)$
$\displaystyle=1,$ (1.2)
$\displaystyle\lim_{N\to\infty}d_{N}(\lfloor(1+\varepsilon)\overline{C}_{\operatorname{\mathbf{p}}}\log(N)\rfloor)$
$\displaystyle=0.$ (1.3)

Here $d_{N}(K)$ denotes the total variation distance from uniform after
$\operatorname{\mathbf{p}}$-shuffling $K$ times.

It is easy to see that $\overline{C}_{\operatorname{\mathbf{p}}}$ is symmetric
and continuous in the entries of $\operatorname{\mathbf{p}}$. In the next
proposition we show that for any $k$, the fastest possible mixing for any
$\operatorname{\mathbf{p}}=(p_{0},\dots,p_{k-1})$ occurs in the symmetric case
$\operatorname{\mathbf{p}}=\left(\frac{1}{k},\frac{1}{k},\dots,\frac{1}{k}\right)$.

######  Proposition 1.1.

For any $k$, $\overline{C}_{\operatorname{\mathbf{p}}}$ has minimum value
$\frac{3}{2\log k}$ achieved uniquely at
$\operatorname{\mathbf{p}}=\left(\frac{1}{k},\frac{1}{k},\dots,\frac{1}{k}\right)$.
Moreover for any $\operatorname{\mathbf{p}}$,

$C_{\operatorname{\mathbf{p}}}\in\bigg{[}\frac{3}{2\psi_{\operatorname{\mathbf{p}}}(2)},\frac{7}{4\psi_{\operatorname{\mathbf{p}}}(2)}\bigg{)}\quad\text{
and
}\quad\widetilde{C}_{\operatorname{\mathbf{p}}}\in\bigg{[}\frac{1}{\psi_{\operatorname{\mathbf{p}}}(2)},\frac{2}{\psi_{\operatorname{\mathbf{p}}}(2)}\bigg{)}.$

It also follows from Proposition 1.1 that for any $\operatorname{\mathbf{p}}$,
cutoff occurs in total variation occurs strictly sooner than in the
$L^{\infty}$ and separation distances. Quite precise results for these
alternative notions of mixing are shown in [ADS12] by different methods, for
the same asymmetric riffle shuffles that we study. In particular, cutoff
occurs in both of these distances after
$\frac{2\log(N)}{\psi_{\operatorname{\mathbf{p}}}(2)}\pm O(1)$ shuffles.
Recall that separation and $L^{\infty}$ distance always upper-bound total
variation distance, so only the strictness of the resulting inequality

$\frac{2}{\psi_{\operatorname{\mathbf{p}}}(2)}>\overline{C}_{\operatorname{\mathbf{p}}}$

between mixing time growth rates is non-trivial.

###### Proof of Proposition 1.1.

When
$\operatorname{\mathbf{p}}=\left(\frac{1}{k},\frac{1}{k},\dots,\frac{1}{k}\right)$
it is easy to see that $\theta_{\operatorname{\mathbf{p}}}=3$ and
$\phi_{\operatorname{\mathbf{p}}}(2)=\frac{1}{k}$. Therefore

$C_{\operatorname{\mathbf{p}}}=\frac{3}{2\log k}>\frac{1}{\log
k}=\widetilde{C}_{\operatorname{\mathbf{p}}}.$

The value $\phi_{\operatorname{\mathbf{p}}}(2)$ is symmetric and strictly
convex in $\operatorname{\mathbf{p}}$, hence achieves unique minimum at
$\operatorname{\mathbf{p}}=\left(\frac{1}{k},\frac{1}{k},\dots,\frac{1}{k}\right)$.
Moreover $\theta_{\operatorname{\mathbf{p}}}\geq 3$ always holds as
Cauchy–Schwarz implies

$\phi_{\operatorname{\mathbf{p}}}(2)^{2}=\left(\sum_{i=0}^{k-1}p_{i}^{2}\right)^{2}\leq\left(\sum_{i=0}^{k-1}p_{i}^{3}\right)\cdot\left(\sum_{i=0}^{k-1}p_{i}\right)=\sum_{i=0}^{k-1}p_{i}^{3}=\phi_{\operatorname{\mathbf{p}}}(3).$

Therefore $C_{\operatorname{\mathbf{p}}}$ achieves unique minimum at
$\operatorname{\mathbf{p}}=\left(\frac{1}{k},\frac{1}{k},\dots,\frac{1}{k}\right)$,
hence the first result. Moreover $\theta_{\operatorname{\mathbf{p}}}<4$ also
holds because

$\phi_{\operatorname{\mathbf{p}}}(2)^{2}=\left(\sum_{i=0}^{k-1}p_{i}^{2}\right)^{2}>\sum_{i=0}^{k-1}p_{i}^{4}=\phi_{\operatorname{\mathbf{p}}}(4).$

This shows that
$C_{\operatorname{\mathbf{p}}}\in\bigg{[}\frac{3}{2\psi_{\operatorname{\mathbf{p}}}(2)},\frac{7}{4\psi_{\operatorname{\mathbf{p}}}(2)}\bigg{)}$.
It remains to estimate $\widetilde{C}_{\operatorname{\mathbf{p}}}$, and the
claimed bounds amount to showing

$\sum_{i=0}^{k-1}p_{i}^{2}\leq
p_{\text{\tt{max}}}<\sqrt{\sum_{i=0}^{k-1}p_{i}^{2}}.$

The left inequality holds because

$\sum_{i=0}^{k-1}p_{i}^{2}\leq\sum_{i=0}^{k-1}p_{i}p_{\text{\tt{max}}}=p_{\text{\tt{max}}}$

and the right inequality is clear. ∎

The primary focus of this paper is showing the upper bound (1.3), i.e. that
the mixing time is at most $\overline{C}_{\operatorname{\mathbf{p}}}\log(N)$.
In Section 3 we reduce (1.3) to the estimation of a certain exponential
moment, which occupies Sections 4 and 5. In the other direction, Lalley showed
mixing time lower bounds of both
$\widetilde{C}_{\operatorname{\mathbf{p}}}\log(N)$ and
$C_{\operatorname{\mathbf{p}}}\log(N)$ in [Lal00]. However the latter result
required
$\operatorname{\mathbf{p}}\approx\left(\frac{1}{k},\frac{1}{k},\dots,\frac{1}{k}\right)$
to be close to uniform. ([Lal00] only considered the case $k=2$, but the
arguments work identically for larger $k$.) In Section 6 we generalize the
$C_{\operatorname{\mathbf{p}}}\log(N)$ lower bound to all
$\operatorname{\mathbf{p}}=(p_{0},\dots,p_{k-1})$ by refining Lalley’s
approach. For the sake of continuity, several of our notational choices, such
as the constants $C_{\operatorname{\mathbf{p}}}$ and
$\widetilde{C}_{\operatorname{\mathbf{p}}}$, are adopted from [Lal00]. However
we reversed the sign of $\psi_{\operatorname{\mathbf{p}}}$ from [Lal00] so
that $\psi_{\operatorname{\mathbf{p}}}(t)>0$ for all $t>1$.

Approximate Mixing Times $\overline{C}_{\operatorname{\mathbf{p}}}\log N$ for
$p$-Shuffles
---
Deck Size |  $p=0.5$ |  $p=0.6$ |  $p=0.7$ |  $p=0.8$ |  $p=0.9$ |  $p=0.95$
52 |  8.6 |  9.2 |  11.3 |  18 |  37 |  77
104 |  10.1 |  10.8 |  13.3 |  21 |  44 |  90
208 |  11.6 |  12.4 |  15.3 |  24 |  51 |  104
520 |  13.5 |  14.5 |  17.9 |  28 |  59 |  122
$N$ |  $2.16\log N$ |  $2.32\log N$ |  $2.86\log N$ |  $4.5\log N$ |  $9.5\log N$ |  $19.5\log N$
Table 1: The values $\overline{C}_{\operatorname{\mathbf{p}}}\log N$ are shown
for varying deck sizes $N$ and $\operatorname{\mathbf{p}}=(p,1-p)$. These
values should be taken as a rough guide because our results are asymptotic in
$N$. Figure 1: The values $\overline{C}_{\operatorname{\mathbf{p}}}$ for
$\operatorname{\mathbf{p}}=(p,1-p)$ are shown. The blue and red depict the
transitions between $C_{\operatorname{\mathbf{p}}}$ and
$\widetilde{C}_{\operatorname{\mathbf{p}}}$, which occur at $p\approx 0.28$
and $p\approx 0.72$. As $p\to 0$, the divergence is
$\overline{C}_{\operatorname{\mathbf{p}}}=\frac{1}{\log(1/(1-p))}=\frac{1}{p}+O(1)$.

##  2 Preliminaries

Let $P_{\operatorname{\mathbf{p}}}$ denote the probability measure on the
symmetric group $\operatorname{\mathfrak{S}}_{N}$ given by applying a
$\operatorname{\mathbf{p}}$-shuffle to the identity. Given two discrete
probability vectors $\operatorname{\mathbf{p}}=(p_{0},\dots,p_{k-1})$ and
$\mathbf{q}=(q_{0},\dots,q_{\ell-1})$ define their convolution

$\operatorname{\mathbf{p}}*\operatorname{\mathbf{q}}\equiv(p_{0}q_{0},p_{0}q_{1},\dots,p_{0}q_{\ell-1},p_{1}q_{0},\dots,p_{k-1}q_{\ell-1}).$

This convolution turns out to correspond to shuffle composition.

######  Proposition 2.1 ([DFP92, Example 7]).

Performing a $\mathbf{q}$-shuffle followed by a
$\operatorname{\mathbf{p}}$-shuffle is equivalent to performing a
$(\operatorname{\mathbf{p}}*\operatorname{\mathbf{q}})$-shuffle. That is,

$P_{\operatorname{\mathbf{p}}}*P_{\operatorname{\mathbf{q}}}=P_{\operatorname{\mathbf{p}}*\operatorname{\mathbf{q}}}.$

Proposition 2.1 yields an explicit description for the distribution
$P_{\operatorname{\mathbf{p}}^{*K}}$ of a deck after $K$ shuffles. For
instance in the “symmetric” setting of [BD92], it implies that composing a
$k_{1}$-shuffle and a $k_{2}$-shuffle results in a $k_{1}k_{2}$-shuffle. It
will actually be more convenient for us to work with the inverse permutations.
We now explain how to do this, following [Lal00]. First define a distribution
on sequences

$S=(s_{1},\dots,s_{N})$

of length $K$ strings as follows. Generate $N$ strings of length $K$, all with
i.i.d. $\operatorname{\mathbf{p}}$-random digits in

$[k]_{0}=\\{0,\dots,k-1\\}.$

$S$ is obtained by sorting these strings into increasing lexicographic order

$s_{1}\leq_{\text{\tt{lex}}}s_{2}\leq_{\text{\tt{lex}}}\dots\leq_{\text{\tt{lex}}}s_{N}.$

Recall that the lexicographic order on strings of the same length is just
given by comparing their base $k$ values. In general, the lexicographically
smaller of two different $[k]_{0}$-strings is the one with the smaller digit
at the first place where their digits differ, or is the shorter string if one
string is a prefix of the other.

Next define the associated _shuffle graph_ $G=G(S)$ on vertex set

$[N]=\\{1,2,\dots,N\\}$

in which $i,i+1\in V(G)$ are neighbors if and only if $s_{i}=s_{i+1}$, and no
other edges are in $G$. Hence $G$ is a union of disjoint paths, which we call
_$G$ -components_. (We say $S$ and $G=G(S)$ are
$\operatorname{\mathbf{p}}$-random when they are constructed in this way.)
Finally choose a uniformly random permutation
$\pi\in\operatorname{\mathfrak{S}}_{N}$ and define its $G$-modification
$\pi^{G}$ by, within each $G$-component, sorting the values $\pi(i)$ into
increasing order. The next proposition states that $\pi^{G}$ is exactly the
inverse permutation of a $\operatorname{\mathbf{p}}^{*K}$-shuffled deck.

Figure 2: In this example with $N=10$ strings in $[k]_{0}^{K}=[2]_{0}^{3}$,
the lexiographically sorted sequence of strings $S$ leads to the shuffle graph
$G=G(S)$. The permutation $\pi\in\operatorname{\mathfrak{S}}_{N}$ is then
transformed into $\pi^{G}$ by sorting within each $G$-component. By
Proposition 2.2, the inverse $(\pi^{G})^{-1}$ of the resulting permutation has
distribution $P_{\operatorname{\mathbf{p}}^{*K}}$.

######  Proposition 2.2 ([Lal00, Lemma 3]).

Let $\pi\in\operatorname{\mathfrak{S}}_{N}$ be uniformly random and $G=G(S)$
be $\operatorname{\mathbf{p}}$-random as defined above, for some fixed
positive integers $N$ and $K$. Then the distribution of $(\pi^{G})^{-1}$ is
exactly $P_{\operatorname{\mathbf{p}}^{*K}}$. In particular, the total
variation distance of $\pi^{G}$ from uniform equals $d_{N}(K)$.

In other words, the inverse permutation of a shuffled deck can be generated by
starting with a uniformly random permutation $\pi$, and then modifying $\pi$
to create $\pi^{G}$ which is increasing on an independently random set of
subintervals in $[N]$. After more and more shuffles, these subintervals shrink
in distribution, leading eventually to mixing. In fact, $L^{\infty}$ and
separation mixing both correspond to $G$ having no edges with high
probability, see [Lal00, Corollary 3] and [ADS12]. However because $G$ is
random, total variation mixing can and does occur sooner. We refer the reader
to [Lal00, Section 2] for more explanation and examples regarding Proposition
2.2. In brief, the $N$ sequences $s_{i}\in[k]_{0}^{K}$ correspond to the
sequences of pile-types that each of the $N$ cards in the deck appears in
during the shuffles. The sorting within $G$-components corresponds to the fact
that if two cards are in the same pile during all $K$ of the riffle shuffles,
then their relative order must be preserved.

Throughout the remainder of this paper, we work entirely with this transformed
problem. Namely we will show that for
$K\geq(1+\varepsilon)\overline{C}_{p}\log N$ the permutation $\pi^{G}$ has
total variation distance $o(1)$ from uniform, while for
$K\leq(1-\varepsilon)\overline{C}_{p}\log N$ this distance is $1-o(1)$.

###  2.1 Intuition Based on an Independent Point Process

There are two main obstructions to mixing which lead to the separate lower
bounds of $\widetilde{C}_{\operatorname{\mathbf{p}}}$ and
$C_{\operatorname{\mathbf{p}}}$. The simpler obstruction is that if
$K\leq(\widetilde{C}_{\operatorname{\mathbf{p}}}-\varepsilon)\log(N)$, then
some strings will typically occur many times, so $\pi^{G}$ will contain an
abnormally long increasing substring of length $N^{\Omega(1)}$. Indeed, from
the definition
$\widetilde{C}_{\operatorname{\mathbf{p}}}=\frac{1}{\log(1/p_{\text{\tt{max}}})}$
it follows that after
$K\leq(\widetilde{C}_{\operatorname{\mathbf{p}}}-\varepsilon)\log(N)$
shuffles, the expected number of strings with $s_{j}=i_{\text{\tt{max}}}^{K}$
is

$\displaystyle\mathbb{E}\left|\\{j\in[N]:s_{j}=i_{\text{\tt{max}}}^{K}\\}\right|$
$\displaystyle=p_{\text{\tt{max}}}^{K}N$ $\displaystyle\geq
N^{-(\widetilde{C}_{\operatorname{\mathbf{p}}}-\varepsilon)\log(1/p_{\text{\tt{max}}})+1}$
$\displaystyle\geq N^{\Omega_{\varepsilon}(1)}.$

Since the number of such strings is binomially distributed, it is well-
concentrated around its mean. Therefore with probability $1-o(1)$ the
$\operatorname{\mathbf{p}}$-random shuffle graph $G$ contains a length
$N^{\Omega_{\varepsilon}(1)}$ path, and so $\pi^{G}$ contains an increasing
contiguous substring of the same length. However in a uniformly random
permutation $\pi$, the probability to have an increasing substring of length
$\ell\geq\log N$ is at most $N/(\ell!)=o(1)$. Therefore the total variation
distance from uniform is $1-o(1)$ when
$K\leq(\widetilde{C}_{\operatorname{\mathbf{p}}}-\varepsilon)\log(N)$.

The more complicated obstruction to mixing comes from a fractal set of
predictable locations (referred to as “cold spots” in [Lal00]) which tend to
contain many $G$-edges. This obstruction, as well as our approach to the upper
bound, can be motivated by an independent point process heuristic. (See also
the last section of [Lal00].) Suppose we observe
$\sigma\in\operatorname{\mathfrak{S}}_{N}$ which is generated by either
$\sigma=\pi$ or $\sigma=\pi^{G}$ for uniformly random
$\pi\in\operatorname{\mathfrak{S}}_{N}$ and $\operatorname{\mathbf{p}}$-random
$G$. Since the transformation $\pi\to\pi^{G}$ simply arranges small
subintervals into increasing order, let us suppose that we observe only the
ascent set $A(\sigma)=\\{i:\sigma(i)<\sigma(i+1)\\}$. As a heuristic, we may
treat $A(\sigma)$ as an independent point process on edges in both the uniform
$\sigma=\pi$ and shuffled $\sigma=\pi^{G}$ distributions. Specifically, for
each $i\in[N-1]$ let

$\eta_{i}\equiv\mathbb{P}[(i,i+1)\in E(G)].$

be the probability for $(i,i+1)$ to be an edge in $G$. Then

$\mathbb{P}[(i,i+1)\in A(\pi)]=\frac{1}{2}$

while, roughly speaking,

$\mathbb{P}[(i,i+1)\in A(\pi^{G})]\approx\frac{1+\eta_{i}}{2}.$

(Technically $\mathbb{P}[(i,i+1)\in A(\pi^{G})]$ should also depend on
$\eta_{i-1}$ and $\eta_{i+1}$ but we will ignore this point.) This heuristic
suggests that the likelihood ratio

$\frac{\mathbb{P}^{\pi\in\operatorname{\mathfrak{S}}_{N}}[\pi^{G}=\sigma]}{\mathbb{P}^{\pi\in\operatorname{\mathfrak{S}}_{N}}[\pi=\sigma]}$

evaluated at a uniformly random $\sigma\in\operatorname{\mathfrak{S}}_{N}$
behaves like the random product

$\prod_{i\in[N-1]}(1\pm\eta_{i})$

where the $\pm$ signs are i.i.d. uniform. This product is close to $0$ in
probability (so mixing has not occured) if $\sum_{i}\eta_{i}^{2}\gg 1$, and is
close to $1$ in probability (so mixing has occured) if
$\sum_{i}\eta_{i}^{2}\ll 1$.

Next observe that even without heuristic assumptions,

$\sum_{i}\eta_{i}^{2}=\mathbb{E}[E(G,G^{\prime})]$

is the expected size of the edge-intersection

$E(G,G^{\prime})\equiv E(G)\cap E(G^{\prime})$

of two independent $\operatorname{\mathbf{p}}$-random shuffle graphs $G$ and
$G^{\prime}$. Therefore it is natural to guess that mixing occurs once
$|E(G,G^{\prime})|$ is typically small. Indeed, the quantity
$|E(G,G^{\prime})|$ will be crucial throughout. Let us finally summarize how
it and related quantities appear in the proofs.

To lower bound the mixing time, one identifies deterministic “cold spot” sets
$H\subseteq[N]$ which typically contain at least $|H|^{\frac{1}{2}+\delta}$
$G$-edges and shows that this implies non-mixing (see Proposition 6.1). The
existence of such sets $H$ implies in general that
$\mathbb{E}[|E(G,G^{\prime})|]\gg 1$ (Remark 6.1). Moreover in the independent
point process model, the existence of such sets $H$ is essentially equivalent
to $\sum_{i}\eta_{i}^{2}\gg 1$. Indeed, if $\sum_{i}\eta_{i}^{2}\gg
N^{\delta}$ then by the dyadic pigeonhole principle it follows that for some
positive integer $n$ there are at least $\Omega(2^{2n}N^{\delta/3})$ values
$i\in[N-1]$ with $\eta_{i}\in[2^{-n},2^{-n+1}]$. These values of $i$ can be
taken for the set $H$.

On the other hand, it can happen that $\mathbb{E}[|E(G,G^{\prime})|]\ll 1$
holds strictly before the onset of total variation mixing. This requires that
$p_{\text{\tt{max}}}>\max(p_{0},p_{k-1})$ and in particular $k\geq 3$ — see
Remark 5.1. Instead as explained in Section 3, we reduce the mixing time upper
bound (1.3) to showing that suitably truncated exponential moments of
$|E(G,G^{\prime})|$ are small. Estimating these exponential moments is rather
involved. Our strategy is outlined just before the start of Subsection 3.2,
and the proof occupies Sections 4 and 5.

These exponential moments arise naturally from considering (after some
truncation) a chi-squared upper bound for total variation distance (see Lemma
3.3). In fact this seems to be a generally applicable method to upper-bound
the total variation distance from a mixture of distributions with “random
hidden structure” to a “null distribution” by controlling the interaction
between two independent copies of the “structure” (in our setting, the graph
$G$). For instance, a related observation was made in [MP12, Proposition 3.2]
and later exploited in [LS16, LS17] to analyze information percolation for the
Ising model (see also [LS15]).

###  2.2 Notation

For any $M\geq 1$ the set $[k]_{0}^{M}$ consists of all length $M$ strings
with digits in $[k]_{0}$. (All strings throughout the paper will have digits
in $[k]_{0}$.) Let

$\mathcal{S}\subseteq([k]_{0}^{K})^{N}$

denote the set of all lexicographically non-decreasing sequences
$S=(s_{1},\dots,s_{N})$ of $N$ strings with length $K$ each. Let $\mathcal{G}$
denote the set of all shuffle graphs, i.e. subgraphs of the path graph on $N$
vertices. For $G\in\mathcal{G}$, let $\mathcal{C}(G)$ be the set of
$G$-components, i.e. connected components of $G$.

Define $\mu_{\operatorname{\mathbf{p}},M}$, often abbreviated as just
$\mu_{\operatorname{\mathbf{p}}}$, to be the probability measure on
$[k]_{0}^{M}$ with each digit independently
$\operatorname{\mathbf{p}}$-random. By abuse of notation, we also use
$\mu_{\operatorname{\mathbf{p}},M}$ or simply
$\mu_{\operatorname{\mathbf{p}}}$ to denote the associated
$\operatorname{\mathbf{p}}$-random distributions on $\mathcal{S}$ or
$\mathcal{G}$. We sometimes use square brackets to denote strings written out
by their digits. For instance $[(k-1)(k-1)]$ indicates the string with two
digits of $(k-1)$ while $[(k-1)(k-1)0^{K-2}]$ denotes the string with two
initial $(k-1)$-digits followed by $K-2$ final $0$-digits. We also
occasionally use brackets to denote digits of a string, so for instance the
digit expansion of a string $x$ may be written

$x=x[1]x[2]\dots x[M]\in[k]_{0}^{M}.$

We write $\mathbb{E}^{\sigma},\mathbb{E}^{\pi},\mathbb{P}^{\sigma},$ and
$\mathbb{P}^{\pi}$ to denote expectations or probabilities taken over
uniformly random permutations $\sigma$ or $\pi$ in
$\operatorname{\mathfrak{S}}_{N}$. We similarly write $\mathbb{E}^{S}$ to
indicate expectation over $S\sim\mu_{\operatorname{\mathbf{p}},K}$. We will
continue to use $E(G,G^{\prime})=E(G)\cap E(G^{\prime})$ to denote the edge-
intersection of $G,G^{\prime}\in\mathcal{G}$. $S^{\prime}$ and
$G^{\prime}=G(S^{\prime})$ will always denote independent copies of $S$ and
$G$.

The following definitions are used to prove Lemma 3.9 at the end of Section 3,
and otherwise do not appear until Section 4. For each string

$x=x[1]x[2]\dots x[M]\in[k]_{0}^{M}$

with $M\geq 1$ a positive integer, define

$\displaystyle t_{x}$
$\displaystyle\equiv\mathbb{P}^{y\sim\mu_{\operatorname{\mathbf{p}},M}}[y<_{\text{\tt{lex}}}x],$
(2.1) $\displaystyle\lambda_{x}$
$\displaystyle\equiv\mathbb{P}^{y\sim\mu_{\operatorname{\mathbf{p}},M}}[y=x]=\prod_{i=1}^{M}p_{x[i]},$
(2.2) $\displaystyle J_{x}$ $\displaystyle\equiv[t_{x},t_{x}+\lambda_{x}).$
(2.3)

Hence the intervals $(J_{x})_{x\in[k]_{0}^{M}}$ partition $[0,1)$ for any
fixed $M$. Note that

$t_{x}+\lambda_{x}=\mathbb{P}^{y\sim\mu_{\operatorname{\mathbf{p}},M}}[y\leq_{\text{\tt{lex}}}x].$

It will often be useful to observe that to sample a
$\operatorname{\mathbf{p}}$-random string $x\in[k]_{0}^{M}$, one may
equivalently sample a uniform random variable $a\in[0,1]$ and take the unique
$x$ with $a\in J_{x}$. Similarly to sample
$(s_{1},\dots,s_{N})\in\mathcal{S}$, one may instead sample uniform i.i.d.

$a_{1}^{\prime},\dots,a_{N}^{\prime}\in[0,1],$

sort them into increasing order

$0\leq a_{1}\leq\dots\leq a_{N}\leq 1,$

and finally choose $s_{i}\in[k]_{0}^{K}$ such that $a_{i}\in J_{s_{i}}$ for
each $i\in[N]$.

Figure 3: The partition $[0,1)=\bigcup_{x\in[k]_{0}^{M}}J_{x}$ with $k=2,M=2$,
and $(p_{0},p_{1})=\left(\frac{1}{3},\frac{2}{3}\right)$.

##  3 Upper Bound Approach

Here we explain some of the ingredients used to prove the mixing time upper
bound (1.3). In Subsection 3.1 we present the more conceptual parts,
ultimately reducing (1.3) to a certain exponential moment estimate. In
Subsection 3.2 we prove a few other lemmas used in Subsection 3.1. This
section might be viewed as an extended setup for the more difficult parts of
the proof. For instance the constant $C_{\operatorname{\mathbf{p}}}$ does not
explicitly enter until the next section. However we emphasize that the results
of this section are both specific to the particular problem considered and
essential to understand the remainder of the paper.

###  3.1 High-Level Approach

We begin by carefully examining the Radon–Nikodym derivative between the
distributions of $\pi^{G}$ and $\pi$ where $\pi$ is a uniformly random
permutation. For each $G\in\mathcal{G}$, let
$\mathcal{C}(G)=\\{G_{1},\dots,G_{j}\\}$ be the $G$-components, and suppose
that each $G_{i}$ contains $v_{i}$ vertices. Then it is easy to see that the
map $\operatorname{\mathfrak{S}}_{N}\to\operatorname{\mathfrak{S}}_{N}$ given
by $\pi\to\pi^{G}$ is $\left(\prod_{i=1}^{j}v_{i}!\right)$ to $1$. Moreover
its image consists of those $\sigma$ with $\sigma^{G}=\sigma$. Therefore

$\mathbb{P}^{\pi}[\pi^{G}=\sigma]=1_{\sigma=\sigma^{G}}\cdot\frac{\prod_{i=1}^{j}v_{i}!}{N!},\quad\sigma\in\operatorname{\mathfrak{S}}_{N}.$

As a consequence, for fixed $G\in\mathcal{G}$ the Radon–Nikodym derivative
$f_{G,\sigma}$ of $\pi^{G}$ with respect to $\pi$ is given by

$\displaystyle f_{G,\sigma}$
$\displaystyle\equiv\frac{\mathbb{P}^{\pi}[\pi^{G}=\sigma]}{\mathbb{P}^{\pi}[\pi=\sigma]}$
$\displaystyle=N!\cdot\mathbb{P}^{\pi}[\pi^{G}=\sigma]$
$\displaystyle=1_{\sigma^{G}=\sigma}\cdot\prod_{i=1}^{j}v_{i}!$
$\displaystyle=\frac{1_{\sigma^{G}=\sigma}}{\mathbb{P}^{\pi}[\pi^{G}=\pi]}.$

Observe that for fixed $G\in\mathcal{G}$,

$\mathbb{E}^{\sigma}[f_{G,\sigma}]=1.$ (3.1)

On the other hand for fixed $\sigma$ and
$\mu_{\operatorname{\mathbf{p}},K}$-random $G=G(S)$, we may apply the law of
total expectation to the second definition of $f_{G,\sigma}$ above. This
implies that for fixed $\sigma$,

$\mathbb{P}^{\pi,S}[\pi^{G(S)}=\sigma]=\frac{\mathbb{E}^{S}[f_{G(S),\sigma}]}{N!}.$

Therefore the total variation distance to uniform after $K$ shuffles is given
by

$d_{N}(K)=\frac{1}{2}\cdot\mathbb{E}^{\sigma}\left|\mathbb{E}^{S}[f_{G(S),\sigma}-1]\right|.$

Next, we use a chi-squared upper bound for total variation distance after
removing exceptional sequences from $\mathcal{S}$. To carry this out, given a
partition $\mathcal{S}=\mathcal{S}_{1}\cup\mathcal{S}_{0}$ (where
$\mathcal{S}_{1}$ consists of “typical” sequences), write

$\displaystyle\mathbb{E}^{\sigma}\left|\mathbb{E}^{S}[f_{G(S),\sigma}-1]\right|$
$\displaystyle\leq\mathbb{E}^{\sigma}\left|\mathbb{E}^{S}[(f_{G(S),\sigma}-1)1_{S\in\mathcal{S}_{1}}]\right|+\mathbb{E}^{\sigma}\left|\mathbb{E}^{S}[(f_{G(S),\sigma}-1)1_{S\in\mathcal{S}_{0}}]\right|$
$\displaystyle\leq\mathbb{E}^{\sigma}\left|\mathbb{E}^{S}[(f_{G(S),\sigma}-1)1_{S\in\mathcal{S}_{1}}]\right|+\mathbb{E}^{\sigma,S}[(f_{G(S),\sigma}+1)1_{S\in\mathcal{S}_{0}}]$
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:EFG}}}{{=}}\mathbb{E}^{\sigma}\left|\mathbb{E}^{S}[(f_{G(S),\sigma}-1)1_{S\in\mathcal{S}_{1}}]\right|+2\mu_{\operatorname{\mathbf{p}}}(\mathcal{S}_{0}).$
(3.2)

Take $S^{\prime}$ to be an independent copy of $S$ and define for any shuffle
graphs $G,G^{\prime}\in\mathcal{G}$

$f_{G,G^{\prime}}\equiv\mathbb{E}^{\sigma}[f_{G,\sigma}f_{G^{\prime},\sigma}].$

We now use the Cauchy–Schwarz inequality to upper-bound the main term of (3.2)
via

$\displaystyle\left(\mathbb{E}^{\sigma}\left|\mathbb{E}^{S}[(f_{G(S),\sigma}-1)1_{S\in\mathcal{S}_{1}}]\right|\right)^{2}$
$\displaystyle\leq\mathbb{E}^{\sigma}\left[\left(\mathbb{E}^{S}[(f_{G(S),\sigma}-1)1_{S\in\mathcal{S}_{1}}]\right)^{2}\right]$
$\displaystyle=\mathbb{E}^{\sigma}\mathbb{E}^{S,S^{\prime}}[(f_{G(S),\sigma}-1)(f_{G(S^{\prime}),\sigma}-1)1_{S,S^{\prime}\in\mathcal{S}_{1}}]$
$\displaystyle=\mathbb{E}^{\sigma}\mathbb{E}^{S,S^{\prime}}[(f_{G(S),\sigma}f_{G(S^{\prime}),\sigma}-1)1_{S,S^{\prime}\in\mathcal{S}_{1}}]$
$\displaystyle=\mathbb{E}^{S,S^{\prime}}\left[(f_{G,G^{\prime}}-1)1_{S,S^{\prime}\in\mathcal{S}_{1}}\right].$
(3.3)

The second equality holds by switching the order of expectation and using
(3.1). Starting from (3.3) and throughout the remainder of the paper, we set
$G=G(S),G^{\prime}=G(S^{\prime})$. Based on (3.3), to establish mixing it
remains to show that $f_{G,G^{\prime}}$ rarely exceeds $1$ in an $L^{1}$ sense
(modulo choosing $\mathcal{S}_{1}$ and $\mathcal{S}_{0}$).

We will upper-bound $f_{G,G^{\prime}}$ using the number $|E(G,G^{\prime})|$ of
edges shared by $G$ and $G^{\prime}$. As motivation for why such a
relationship should exist, observe that if no vertex $i\in[N]$ is incident to
both a $G$-edge and a $G^{\prime}$-edge, then $f_{G,\sigma}$ and
$f_{G^{\prime},\sigma}$ are exactly independent for
$\sigma\in\operatorname{\mathfrak{S}}_{N}$ uniformly random. Hence in this
case we have the exact equality

$f_{G,G^{\prime}}=\mathbb{E}^{\sigma}[f_{G,\sigma}f_{G^{\prime},\sigma}]=\mathbb{E}^{\sigma}[f_{G,\sigma}]\mathbb{E}^{\sigma}[f_{G^{\prime},\sigma}]\stackrel{{\scriptstyle\eqref{eq:EFG}}}{{=}}1.$

In fact Lemma 3.1 below implies that $f_{G,G^{\prime}}\leq 1$ holds whenever
$|E(G,G^{\prime})|=0$. In essence, incident but non-overlapping edges only
reduce $f_{G,G^{\prime}}$. It is now unsurprising that $f_{G,G^{\prime}}$ can
be bounded above by some function of $|E(G,G^{\prime})|$. We show in Lemma 3.3
that this dependence is at most exponential when a condition called
$L$-sparsity holds for both $G$ and $G^{\prime}$. The requirement of
$L$-sparsity will be part of the eventual definition of $\mathcal{S}_{1}$.

In general, for any shuffle graphs $G$ and $G^{\prime}$, define the new
shuffle graph $U$ to be their edge-union with $U$-components $\mathcal{C}(U)$.
The next lemma shows how to estimate $f_{G,G^{\prime}}$ based on the
intersection structure of $G$ and $G^{\prime}$. The proof is deferred to the
next subsection.

######  Lemma 3.1.

Suppose the $U$-components have vertex-sizes $(u_{1},\dots,u_{c})$. Then

$f_{G,G^{\prime}}\leq\prod_{\begin{subarray}{c}1\leq i\leq c,\\\ E(U_{i})\cap
E(G,G^{\prime})\neq\emptyset\end{subarray}}(u_{i}!).$ (3.4)

We now define the first condition that “typical” sequences in
$\mathcal{S}_{1}$ must satisfy. The objective is to ensure that the $u_{i}$ in
Lemma 3.1 are uniformly bounded by some constant
$L=L(\operatorname{\mathbf{p}},\varepsilon)$. Let us point out that it is not
enough to argue that $\max_{i}(u_{i})\leq L$ holds with high probability over
random pairs $(S,S^{\prime})$. Indeed, the truncation step (3.2) was used to
remove $\mathcal{S}_{0}$ before applying Cauchy–Schwarz to introduce
$S^{\prime}$. There is no analogous way to remove an arbitrary low-probability
subset of pairs $(S,S^{\prime})\in\mathcal{S}$. It is therefore important that
the definition of $L$-sparsity below implies $\max_{i}(u_{i})\leq L$ via
separate restrictions on $G$ and $G^{\prime}$.

######  Definition 3.2.

For $L\geq 10$ a positive integer, a shuffle graph $G$ is
$\boldsymbol{L}$-sparse if within any discrete interval
$\\{i,i+1,\dots,i+L-1\\}\subseteq[N]$ of $L$ consecutive vertices, at most
$L/3$ (of the possible $L-1$) edges are in $E(G)$.

######  Lemma 3.3.

Suppose $G$ and $G^{\prime}$ are $L$-sparse shuffle graphs. Then
$f_{G,G^{\prime}}\leq(L!)^{|E(G,G^{\prime})|}$.

###### Proof.

We claim that $\max_{i}(u_{i})\leq L$, i.e. each $U$-component contains at
most $L$ vertices. Indeed by $L$-sparsity, $U$ contains at most
$\frac{2L}{3}<L-1$ edges within each subinterval of $L$ vertices, hence no
such interval can be a connected subgraph of $U$. Therefore Lemma 3.1 implies
that

$f_{G,G^{\prime}}\leq\prod_{\begin{subarray}{c}1\leq i\leq c,\\\ E(U_{i})\cap
E(G,G^{\prime})\neq\emptyset\end{subarray}}(L!).$

By definition, $|E(G,G^{\prime})|$ is at least the number of components
$U_{i}$ satisfying $E(U_{i})\cap E(G,G^{\prime})\neq\emptyset$. This completes
the proof. ∎

Given Lemma 3.3, our main remaining task is to control the (truncated)
exponential moments of $|E(G,G^{\prime})|$. For technical reasons outlined at
the end of this subsection, we will cover $E(G,G^{\prime})$ by a union
$E(G,G^{\prime})=E_{\text{\tt{forward}}}(G,G^{\prime})\cup
E_{\text{\tt{backward}}}(G,G^{\prime})$ of two sets which omit
lexicographically late and early strings respectively. To ensure that
$E(G,G^{\prime})$ can be covered in this way for
$G,G^{\prime}\in\mathcal{S}_{1}$, we add a second restriction to the
definition of $\mathcal{S}_{1}$ called regularity. This amounts to requiring
that both prefixes $[00]$ and $[(k-1)(k-1)]$ appear with roughly the expected
frequency among the strings $(s_{1},\dots,s_{N})$ of $S$.

######  Definition 3.4.

The sequence $S=(s_{1},\dots,s_{N})\in\mathcal{S}$ of strings is regular if at
most $\left(p_{0}^{2}+\frac{p_{0}p_{k-1}}{2}\right)N$ strings $s_{i}$ begin
with $[00]$ (two consecutive $0$ digits) and at most
$\left(p_{k-1}^{2}+\frac{p_{0}p_{k-1}}{2}\right)N$ strings begin with
$[(k-1)(k-1)]$ (two consecutive $(k-1)$ digits).

######  Lemma 3.5.

For any $\operatorname{\mathbf{p}}$ and $\varepsilon>0$ there exist
$L=L(\operatorname{\mathbf{p}},\varepsilon)\in\mathbb{Z}^{+}$ and
$\delta=\delta(\operatorname{\mathbf{p}},\varepsilon)>0$ such that the
following holds. Consider a $\operatorname{\mathbf{p}}$-random sequence
$S=(s_{1},\dots,s_{N})$ of strings of length
$K\geq(\widetilde{C}_{\operatorname{\mathbf{p}}}+\varepsilon)\log(N)$. Then
with probability $1-O(N^{-\delta})$, $S$ is regular and $G(S)$ is $L$-sparse.

The proof is deferred to the next subsection. $\mathcal{S}_{1}$ can now be
defined: it consists of the regular sequences $S$ for which $G(S)$ is
$L$-sparse for $L=L(\operatorname{\mathbf{p}},\varepsilon)$ as in Lemma 3.5.
Then Lemma 3.5 exactly states that

$\mu_{\operatorname{\mathbf{p}}}(\mathcal{S}_{0})=O(N^{-\delta})$

for some small $\delta=\delta(\operatorname{\mathbf{p}},\varepsilon)$.

We remark that the convergence rate $O(N^{-\delta})$ eventually appears as the
upper bound for the total variation distance to uniformity (see (3.5) and the
next displayed equations in that proof). The rate $O(N^{-\delta})$ seems to be
tight in e.g. Proposition 4.1 via Lemma 4.15. As a result we use this rate in
the statement of Lemma 3.5 although it could be improved. In fact the
probability for $S$ to be regular is at least
$1-e^{-\Omega_{\operatorname{\mathbf{p}}}(N)}$. The probability for $G(S)$ to
be $L$-sparse can be made at most $e^{-CN}$ for any desired $C>0$, if
$L=L(C,\operatorname{\mathbf{p}},\varepsilon)$ is taken sufficiently large.

Next we show how to cover $E(G,G^{\prime})$ when $S$ and $S^{\prime}$ are
regular.

######  Definition 3.6.

Let $E_{\text{\tt{forward}}}(G)$ consist of all edges $(i,i+1)\in E(G)$ for
which the strings $s_{i}=s_{i+1}$ do not begin with prefix $[(k-1)(k-1)]$. Let
$E_{\text{\tt{forward}}}(G,G^{\prime})=E_{\text{\tt{forward}}}(G)\cap
E_{\text{\tt{forward}}}(G^{\prime})$. Define
$E_{\text{\tt{backward}}}(G,G^{\prime})$ in the same way but with
$[(k-1)(k-1)]$ replaced by $[00]$.

######  Lemma 3.7.

If $S,S^{\prime}\in\mathcal{S}$ are regular, then

$|E(G,G^{\prime})|\leq|E_{\text{\tt{forward}}}(G,G^{\prime})|+|E_{\text{\tt{backward}}}(G,G^{\prime})|.$

###### Proof.

Regularity implies that $E_{\text{\tt{forward}}}(G,G^{\prime})$ contains all
shared edges $(i,i+1)\in E(G,G^{\prime})$ with

$i\leq(1-p_{k-1}^{2}-(p_{0}p_{k-1}/2))N,$

and $E_{\text{\tt{backward}}}(G,G^{\prime})$ contains all shared edges
$(i,i+1)\in E(G,G^{\prime})$ with

$i\geq(p_{0}^{2}+(p_{0}p_{k-1}/2))N.$

Since

$p_{0}^{2}+p_{0}p_{k-1}+p_{k-1}^{2}<(p_{0}+p_{k-1})^{2}\leq 1$

we obtain

$(p_{0}^{2}+(p_{0}p_{k-1}/2))N\leq(1-p_{k-1}^{2}-(p_{0}p_{k-1}/2))N.$

Therefore

$E_{\text{\tt{forward}}}(G,G^{\prime})\cup
E_{\text{\tt{backward}}}(G,G^{\prime})=E(G,G^{\prime})$

which implies the result. ∎

Using symmetry to suppress the identical case of $E_{\text{\tt{backward}}}$,
to establish the mixing time upper bound in Theorem 1 it remains to verify the
following lemma.

######  Lemma 3.8.

For any $\operatorname{\mathbf{p}}$ and positive reals $\varepsilon$ and $t$,
there is $\delta=\delta(\operatorname{\mathbf{p}},\varepsilon,t)$ such that if
$K\geq(\overline{C}_{\operatorname{\mathbf{p}}}+\varepsilon)\log(N)$ then

$\mathbb{E}[e^{t\cdot|E_{\text{\tt{forward}}}(G,G^{\prime})|}]\leq
1+O(N^{-\delta}).$

Indeed, the mixing time upper bound (1.3) in Theorem 1 easily follows from the
results above as we show now.

###### Proof of (1.3).

Let $\delta>0$ be sufficiently small depending on
$(\operatorname{\mathbf{p}},\varepsilon,L,t)$, some of which are yet to be
chosen. By (3.2) and (3.3),

$\displaystyle d_{N}(K)$
$\displaystyle=\frac{1}{2}\cdot\mathbb{E}^{\sigma}\left|\mathbb{E}^{S}[f_{G(S),\sigma}]-1\right|$
$\displaystyle\leq\frac{1}{2}\cdot\sqrt{\mathbb{E}^{S,S^{\prime}}\left[(f_{G,G^{\prime}}-1)1_{S,S^{\prime}\in\mathcal{S}_{1}}\right]}+\mu_{\operatorname{\mathbf{p}}}(\mathcal{S}_{0}).$
(3.5)

(It follows from (3.3) that the expression inside the square-root is non-
negative.) Since
$\mu_{\operatorname{\mathbf{p}}}(\mathcal{S}_{0})=O(N^{-\delta})$ by Lemma
3.5, it remains to estimate
$\mathbb{E}^{S,S^{\prime}\in\mathcal{S}}\left[(f_{G,G^{\prime}}-1)1_{S,S^{\prime}\in\mathcal{S}_{1}}\right]$.
Using Lemma 3.3 in the first step, then Lemma 3.7 and finally Lemma 3.8 with
$t=2\log(L!)$, we obtain

$\WithArrows\mathbb{E}^{S,S^{\prime}\in\mathcal{S}}\left[(f_{G,G^{\prime}}-1)1_{S,S^{\prime}\in\mathcal{S}_{1}}\right]&\leq\mathbb{E}^{S,S^{\prime}}[\left((L!)^{|E(G,G^{\prime})|}-1\right)1_{S,S^{\prime}\in\mathcal{S}_{1}}]\Arrow{Lemma~{}\ref{lem:forplusback}}\\\
\leq\mathbb{E}[\left((L!)^{|E_{\text{\tt{forward}}}(G,G^{\prime})|+|E_{\text{\tt{backward}}}(G,G^{\prime})|}-1\right)1_{S,S^{\prime}\in\mathcal{S}_{1}}]\\\
\leq\mathbb{E}[(L!)^{|E_{\text{\tt{forward}}}(G,G^{\prime})|+|E_{\text{\tt{backward}}}(G,G^{\prime})|}-1]\\\
\leq\frac{\mathbb{E}[(L!)^{2|E_{\text{\tt{forward}}}(G,G^{\prime})|}]+\mathbb{E}[(L!)^{2|E_{\text{\tt{backward}}}(G,G^{\prime})|}]}{2}-1\Arrow{Lemma~{}\ref{lem:tails}}\\\
\leq O(N^{-\delta}).$

Combining the above, we conclude that $d_{N}(K)\leq O(N^{-\delta})$ when
$K\geq(\overline{C}_{\operatorname{\mathbf{p}}}+\varepsilon)\log(N)$. ∎

The above constitutes a complete proof for the upper bound, except that Lemmas
3.1, 3.5 and 3.8 are yet to be proved. The first two are not difficult and are
handled in the next subsection. Lemma 3.8 is more challenging and its proof
occupies Sections 4 and 5. We now outline our approach to Lemma 3.8, which
starts from the following basic fact. Suppose $X\in\mathbb{N}$ is a non-
negative integer-valued random variable satisfying the uniform hazard rate
bound

$\sup_{j\geq 0}\mathbb{P}[X\geq j+1|X\geq j]\leq O(N^{-\delta})$ (3.6)

for some $\delta>0$. Then $X$ is stochastically dominated by a geometric
random variable with mean $O(N^{-\delta})$, and therefore
$\mathbb{E}[e^{tX}]=1+O(e^{t}N^{-\delta})=1+o(1)$ for any constant $t$. To
prove Lemma 3.8, we will implement this idea with
$X=|E_{\text{\tt{forward}}}(G,G^{\prime})|$. We explore $G$ and $G^{\prime}$
by revealing their strings together in order, so that

$(s_{1},\dots,s_{i})\quad\text{ and
}\quad(s_{1}^{\prime},\dots,s_{i}^{\prime})$

have been revealed at time $i\in[N]$. We show that at _any_ time, the expected
number of unrevealed edges in $E_{\text{\tt{forward}}}(G,G^{\prime})$ is at
most $O(N^{-\delta})$. That is, almost surely,

$\mathbb{E}\left[\big{|}E_{\text{\tt{forward}}}(G,G^{\prime})|_{\\{i,i+1,\dots,N\\}}\big{|}~{}\Big{|}~{}(s_{1},\dots,s_{i},s_{1}^{\prime},\dots,s_{i}^{\prime})\right]\leq
O(N^{-\delta}).$ (3.7)

(Here we write $E_{\text{\tt{forward}}}(G,G^{\prime})|_{\\{i,i+1,\dots,N\\}}$
to indicate the set of edges $(j,j+1)\in
E_{\text{\tt{forward}}}(G,G^{\prime})$ with $j\geq i$.) The estimate (3.7)
readily implies Lemma 3.8 analogously to the above discussion on (3.6). See
Lemma 5.4 for a detailed proof.

As a first step towards establishing (3.7), in Section 4 we prove for
$K\geq(\overline{C}_{\operatorname{\mathbf{p}}}+\varepsilon)\log(N)$ the
weaker first moment bound

$\mathbb{E}\left[|E(G,G^{\prime})|\right]\leq O(N^{-\delta}).$ (3.8)

In Section 5 we use (3.8) to show (3.7). The idea is to group the set of
possible future strings

$\\{s\in[k]_{0}^{K}:s\geq_{\text{\tt{lex}}}s_{i}\\}$

into a small number of blocks. Here each block $B_{x}$ consists of all strings
beginning with some prefix $x\in[k]_{0}^{M}$ (where $M=M(x)$ depends on $x$).
Such a block $B_{x}$ is essentially equivalent to a copy of $[k]_{0}^{K-M}$.
The idea is to first estimate the left-hand side of (3.7) by a sum over blocks
(using Cauchy–Schwarz several times), and to then estimate the contribution of
each block using (3.8). The total number of blocks will always be $O(\log
N)\leq N^{o(1)}$. Therefore summing over blocks is no problem (up to adjusting
the value of $\delta$ slightly) as long as the hypothesis of (3.8) applies
“within” each block.

To illustrate the key reason for introducing $E_{\text{\tt{forward}}}$, let us
explain why (3.7) can be false if $E_{\text{\tt{forward}}}(G,G^{\prime})$ is
replaced by $E(G,G^{\prime})$. Suppose that $s_{i}=s_{i}^{\prime}=[(k-1)^{K}]$
holds for some $i\in[N]$. Then conditioning on $(s_{i},s_{i}^{\prime})$ forces
$s_{j}=s_{j}^{\prime}=[(k-1)^{K}]$ for all $j>i$. Hence $E(G,G^{\prime})$ must
contain all the edges $(i,i+1),(i+1,i+2),\dots,(N-1,N)$ and so

$\mathbb{E}\left[\big{|}E(G,G^{\prime})|_{\\{i,i+1,\dots,N\\}}\big{|}~{}\Big{|}~{}(s_{1},\dots,s_{i},s_{1}^{\prime},\dots,s_{i}^{\prime})\right]=N-i+1.$

However working with $E_{\text{\tt{forward}}}(G,G^{\prime})$ prevents such
situations by halting exploration once either $s_{i}$ or $s_{i}^{\prime}$
becomes too lexicographically late. This circumvents the above obstruction
because the left-hand side of (3.7) is trivially $0$ unless a lot of “space”
in $[k]_{0}^{K}$ remains available for future strings
$(s_{i+1},\dots,s_{N},s_{i+1}^{\prime},\dots,s_{N}^{\prime})$.

In fact, this guaranteed available space is also directly helpful in
implementing the block decomposition strategy outlined above. Namely for any
prefix $x\in[k]_{0}^{M}$, it ensures that the distribution for the number of
strings $(s_{i+1},\dots,s_{N})$ starting with $x$ cannot increase too much
from conditioning on $(s_{1},\dots,s_{i})$ (see Lemma 5.6 for a precise
statement). This is important because when applying (3.8) to the block of
strings starting with some prefix $x$, we replace $N$ by the number of strings
starting with $x$ (and also replace $K$ by $K-M$). In short, we must ensure
that the hypothesis of (3.8) holds within each block.

###  3.2 Proof of Lemmas 3.1 and 3.5

Here we prove Lemmas 3.1 and 3.5, thus reducing the proof of the mixing time
upper bound (1.3) to establishing Lemma 3.8.

###### Proof of Lemma 3.1.

Let $(v_{1},\dots,v_{a})$ be the vertex-sizes of the $G$-components and
$(w_{1},\dots,w_{b})$ be the vertex-sizes of the $G^{\prime}$-components.

We first claim that

$f_{G,G^{\prime}}=\frac{\big{(}\prod_{i=1}^{a}v_{i}!\big{)}\cdot\big{(}\prod_{j=1}^{b}w_{j}!\big{)}}{\prod_{\ell=1}^{c}u_{\ell}!}.$
(3.9)

Indeed this follows by writing

$\displaystyle f_{G,G^{\prime}}$
$\displaystyle=\mathbb{E}^{\sigma}[f_{G,\sigma}f_{G^{\prime},\sigma}]$
$\displaystyle=\mathbb{E}^{\sigma}\left[1_{\sigma^{G}=\sigma}\cdot
1_{\sigma^{G^{\prime}}=\sigma}\cdot\left(\prod_{i=1}^{a}v_{i}!\right)\cdot\left(\prod_{j=1}^{b}w_{j}!\right)\right]$
$\displaystyle=\mathbb{E}^{\sigma}\left[1_{\sigma^{U}=\sigma}\right]\cdot\left(\prod_{i=1}^{a}v_{i}!\right)\cdot\left(\prod_{j=1}^{b}w_{j}!\right)$
$\displaystyle=\frac{\big{(}\prod_{i=1}^{a}v_{i}!\big{)}\cdot\big{(}\prod_{j=1}^{b}w_{j}!\big{)}}{\prod_{{\ell}=1}^{c}u_{\ell}!}.$

Decomposing the product in (3.9) based on the components
$U_{i}\in\mathcal{C}(U)$ implies

$f_{G,G^{\prime}}=\prod_{\ell}f_{G,G^{\prime},U_{\ell}}$ (3.10)

where we define

$f_{G,G^{\prime},U_{\ell}}\equiv\frac{\left(\prod_{i:G_{i}\subseteq
U_{\ell}}v_{i}!\right)\cdot\left(\prod_{j:G^{\prime}_{j}\subseteq
U_{\ell}}w_{j}!\right)}{u_{\ell}!}.$

Observe that in general, for any positive integers $m_{1},\dots,m_{n},M$ with

$\sum_{i=1}^{n}(m_{i}-1)\leq M-1,$

one has $\prod_{i=1}^{n}m_{i}!\leq M!$. Indeed both sides can be written as a
product of at most $M-1$ integers at least $2$, and the $M-1$ numbers
appearing in the product for $M!$ are clearly larger. In particular, this
holds for $M=u_{\ell}$ whenever $m_{1},\dots,m_{n}$ are the vertex-sizes of
edge-disjoint subinterval graphs of $V(U_{\ell})$. It directly implies

$\displaystyle\prod_{i:G_{i}\subseteq U_{\ell}}v_{i}!$ $\displaystyle\leq
u_{\ell}!,$ $\displaystyle\prod_{j:G^{\prime}_{j}\subseteq U_{\ell}}w_{j}!$
$\displaystyle\leq u_{\ell}!$

from which it follows that $f_{G,G^{\prime},U_{\ell}}\leq u_{\ell}!$ holds.
Moreover if $U_{\ell}$ does not contain any edge in $E(G,G^{\prime})$ then the
$G$-components and $G^{\prime}$-components are collectively edge-disjoint.
Hence for such $U_{\ell}$,

$\left(\prod_{i:G_{i}\subseteq
U_{\ell}}v_{i}!\right)\cdot\left(\prod_{j:G^{\prime}_{j}\subseteq
U_{\ell}}w_{j}!\right)\leq u_{\ell}!$

which implies $f_{G,G^{\prime},U_{\ell}}\leq 1$. Substituting these estimates
into (3.10) implies (3.4). ∎

The next lemma is used to show Lemma 3.5.

######  Lemma 3.9.

For $K\geq(\widetilde{C}_{\operatorname{\mathbf{p}}}+\varepsilon)\log(N)$,
there is $\delta(\operatorname{\mathbf{p}},\varepsilon)>0$ so that the
following holds. Conditioned on any initial strings $s_{1},s_{2},\dots,s_{i}$,
none of which begin with $[(k-1)(k-1)]$, the conditional probability that
$s_{i}=s_{i+1}$ is at most $O(N^{-\delta})$.

###### Proof.

Recall the definitions (2.1), (2.2), (2.3) and the subsequent discussion. We
use the sampling model of $N$ i.i.d.-then-sorted uniform random variables,
letting

$0\leq a_{1}\leq a_{2}\leq\dots\leq a_{N}\leq 1$

be uniformly random before being sorted and then choosing $s_{j}$ such that
$a_{j}\in J_{s_{j}}$ for each $1\leq j\leq N$.

Recall that we condition on $s_{i}$. Let us now condition further on the value
$a_{i}\in J_{s_{i}}$. Then the remaining numbers $a_{j}$ for $j>i$ are, up to
sorting, conditionally i.i.d. in $[a_{i},1]$. The crucial observation is that
the interval $[a_{i},1]$ has length lower bounded by $1-a_{i}\geq
p_{k-1}^{2}\geq p_{\text{\tt{min}}}^{2}$. Indeed, $a_{i}<1-p_{k-1}^{2}$ is
equivalent to the assumption that $s_{i}$ does not begin with $[(k-1)(k-1)]$.
(For instance, note that $J_{[(k-1)(k-1)]}=[1-p_{k-1}^{2},1)$.) Meanwhile the
length of $J_{s_{i}}$ is $\lambda_{s_{i}}$.

Combining these observations, it follows that the conditional distribution for
the number of $j>i$ with $s_{j}=s_{i}$ is stochastically dominated by a
$\text{\tt{Bin}}(N,p_{\text{\tt{min}}}^{-2}\lambda_{s_{i}})$ random variable,
regardless of the value $a_{i}$. Averaging over the unknown $a_{i}$, the same
stochastic domination holds conditioned on just $(s_{1},\dots,s_{i})$. Since
$K\geq(\widetilde{C}_{\operatorname{\mathbf{p}}}+\varepsilon)\log(N)$ was
assumed,

$\lambda_{s_{i}}\leq(p_{\text{\tt{max}}})^{K}\leq N^{-1-\delta}.$

The result now follows. ∎

###### Proof of Lemma 3.5.

The regularity readily follows from Chernoff estimates so we focus only on the
$L$-sparsity. First, Lemma 3.9 implies that
$\mathbb{P}[s_{i+1}=s_{i}|(s_{1},\dots,s_{i})]\leq O(N^{-\delta})$ whenever
$s_{i}<_{\text{\tt{lex}}}[(k-1)(k-1)]$. A simple Markovian coupling now
implies that the set of edges formed by strings
$s_{i}<_{\text{\tt{lex}}}[(k-1)(k-1)]$ is stochastically dominated by instead
choosing each edge independently with probability $O(N^{-\delta})$. By
symmetry the same holds for edges formed by strings starting with
$[(k-1)(k-1)]$. Call these ordinary edges and final edges, respectively.

A simple Chernoff bound implies that for $L\geq 1000\delta^{-1}$, each
interval $\\{i,i+1,\dots,i+L-1\\}$ of $L$ consecutive vertices contains at
most $L/6$ ordinary edges and at most $L/6$ final edges with probability
$1-O_{L}\left(\frac{1}{N^{2}}\right)$. Since $L/6+L/6=L/3$, union bounding
over at most $N$ such length-$L$ intervals shows that $L$-sparsity holds with
probability at least $1-O(N^{-1})\geq 1-O(N^{-\delta})$. ∎

##  4 Upper Bounding the Expected Shared Edges

Define the constant

$\underline{C}_{\operatorname{\mathbf{p}}}\equiv\max\left(C_{\operatorname{\mathbf{p}}},\frac{1}{\log(1/p_{0})},\frac{1}{\log(1/p_{k-1})}\right)\leq\overline{C}_{\operatorname{\mathbf{p}}}.$

The purpose of this section is to prove the following crucial result.

######  Proposition 4.1.

For any $\varepsilon>0$, if
$K\geq\left(\underline{C}_{\operatorname{\mathbf{p}}}+\varepsilon\right)\log(N)$
holds then

$\mathbb{E}\left[|E(G,G^{\prime})|\right]\leq
O(N^{-\Omega_{\operatorname{\mathbf{p}}}(\varepsilon)}).$

We eventually need to control the (truncated) _exponential_ moments of
$E(G,G^{\prime})$. However Proposition 4.1 is the most involved part of upper-
bounding the mixing time, and the value
$C_{\operatorname{\mathbf{p}}}=\frac{3+\theta_{\operatorname{\mathbf{p}}}}{4\psi_{\operatorname{\mathbf{p}}}(2)}$
emerges naturally in its proof. We note that for our main goal of establishing
cutoff, proving Proposition 4.1 only for
$K\geq\left(\overline{C}_{\operatorname{\mathbf{p}}}+\varepsilon\right)\log(N)$
would suffice just as well. However there is no additional difficulty in
proving Proposition 4.1 as stated. Moreover the case
$\underline{C}_{\operatorname{\mathbf{p}}}\neq\overline{C}_{\operatorname{\mathbf{p}}}$
amounts to an interesting discrepancy between the first moment and exponential
moment behavior of $|E(G,G^{\prime})|$. See Remark 5.1 for more discussion of
this point.

Let us mention that after further preparation in Subsection 4.1, we provide in
Subsection 4.2 a proof outline for Proposition 4.1.

###  4.1 Preparation for the Upper Bound Proof

We now introduce several more technical definitions. As a convention,
$\operatorname{\mathbf{p}}$ and $\varepsilon$ will be treated as fixed, while
$\delta=\delta(\operatorname{\mathbf{p}},\varepsilon)$ will be taken
sufficiently small. As before $G$ and $G^{\prime}$ will always be independent
$\operatorname{\mathbf{p}}$-random shuffle graphs. Moreover $s$ will denote
strings of length $K$ while $x$ will denote strings of arbitrary length $M\leq
K$.

####  4.1.1 Lexicographic Subintervals and Blocks

Figure 4: The blocks $B_{00}$ and $B_{1}$ are shown for $k=2$ and $K=3$.

For a string $x$ of length $M$, define its _block_ $B_{x}\subseteq[k]_{0}^{K}$
to be the set of strings of length $K$ beginning with $x$. Hence $B_{x}$
consists of $k^{K-M}$ strings. Given a lexicographically sorted sequence
$(s_{1},\dots,s_{N})\in\mathcal{S}$ of strings, define the discrete interval
$\mathcal{I}(B_{x})\subseteq[N]$ by

$\mathcal{I}(B_{x})\equiv\\{i\in[N]:s_{i}\in
B_{x}\\}=\\{\iota(x),\iota(x)+1,\dots,\tau(x)\\}.$

In general, we define

$\iota(x)=|\\{i\in[N]:s_{i}<_{\text{\tt{lex}}}x\\}|+1,\quad\quad\tau(x)=|\\{i\in[N]:s_{i}<_{\text{\tt{lex}}}x\text{
or }s_{i}\in B_{x}\\}|.$

This ensures $|\mathcal{I}(B_{x})|=\tau(x)-\iota(x)+1$ even if
$\mathcal{I}(B_{x})$ is empty. Observe that for fixed $x$ (recall the
definitions (2.1) and (2.2)),

$\displaystyle|\mathcal{I}(B_{x})|$
$\displaystyle\sim\text{\tt{Bin}}(N,\lambda_{x}),$ (4.1)
$\displaystyle\iota(x)$ $\displaystyle\sim\text{\tt{Bin}}(N,t_{x})+1,$ (4.2)
$\displaystyle\tau(x)$
$\displaystyle\sim\text{\tt{Bin}}(N,t_{x}+\lambda_{x}).$ (4.3)

Finally define $G_{B_{x}}$ to be the induced subgraph of $G$ with vertex set
$\mathcal{I}(B_{x})$, which retains the edges $(i,i+1)\in E(G)$ such that
$s_{i}=s_{i+1}\in B_{x}$. Denote its edge set by $E(G_{B_{x}})$.

####  4.1.2 Entropy

We will require the entropy function. Given any $k$-tuple of non-negative real
numbers $(a_{0},\dots,a_{k-1})$ with sum $a_{\text{\tt{tot}}}$, let

$H(a_{0},\dots,a_{k-1})=\frac{\sum_{i=0}^{k-1}a_{i}\log\left(\frac{a_{\text{\tt{tot}}}}{a_{i}}\right)}{a_{\text{\tt{tot}}}}$

be the entropy of the discrete probability distribution with weights
$\left(a_{i}/a_{\text{\tt{tot}}}\right)_{i=0}^{k-1}.$ If
$a_{0}=\dots=a_{k-1}=0$ then set $H(a_{0},\dots,a_{k-1})=0$. The following
result allows approximation of multinomial coefficients using entropy. (The
values $a_{i}\log(N)$ correspond to the normalization in Definition 4.3 just
below.)

######  Proposition 4.2 ([CS04, Lemma 2.2]).

For fixed $A\geq 0$ and any non-negative real numbers
$a_{0},\dots,a_{k-1}\in[0,A]$ satisfying $a_{i}\log(N)\in\mathbb{Z}$,

$N^{a_{\text{\tt{tot}}}H(a_{0},\dots,a_{k-1})-o_{N}(1)}\leq\binom{a_{\text{\tt{tot}}}\log(N)}{a_{0}\log(N),\dots,a_{k-1}\log(N)}\leq
N^{a_{\text{\tt{tot}}}H(a_{0},\dots,a_{k-1})}.$

Here the term $o_{N}(1)$ tends to $0$ for any fixed $A$ as $N\to\infty$,
uniformly in the values $a_{0},\dots,a_{k-1}\in[0,A]$.

The following special definitions will also be convenient. For $t>0$, let
$\operatorname{\mathbf{p}}^{t}$ be the probability distribution on $[k]_{0}$
given by
$(\operatorname{\mathbf{p}}^{t})_{i}=\frac{p_{i}^{t}}{\phi_{\operatorname{\mathbf{p}}}(t)}$.
Define

$I(\operatorname{\mathbf{p}},\operatorname{\mathbf{p}}^{t})\equiv
D_{\text{\tt{KL}}}(\operatorname{\mathbf{p}}^{t}\mid\mid\operatorname{\mathbf{p}})+H(\operatorname{\mathbf{p}}^{t})=\sum_{i=0}^{k-1}(\operatorname{\mathbf{p}}^{t})_{i}\log(1/p_{i})=\sum_{i=0}^{k-1}\frac{p_{i}^{t}\log(1/p_{i})}{\phi_{\operatorname{\mathbf{p}}}(t)}>0.$
(4.4)

It is not difficult to verify the identity

$H(\operatorname{\mathbf{p}}^{t})=t\cdot
I(\operatorname{\mathbf{p}},\operatorname{\mathbf{p}}^{t})-\psi_{\operatorname{\mathbf{p}}}(t),\quad
t\in\mathbb{R}^{+}.$ (4.5)

####  4.1.3 Digit Profile

Here we define several notions based on the _digit profile_ of a string, which
tracks how many of each digit a string contains, as well as initial digits of
$0$ or $k-1$.

######  Definition 4.3.

For a string $x\in[k]_{0}^{M}$, the digit profile of $x$ is the $(k+2)$-tuple

$(b_{0}(x),b_{k-1}(x),c_{0}(x),\dots,c_{k-1}(x))\in\left(\mathbb{Z}/\log
N\right)^{k+2}$

of non-negative real numbers summing to
$b_{0}+b_{k-1}+\sum_{i=0}^{k-1}c_{i}=\frac{M}{\log(N)}$ defined as follows.
$b_{0}\log(N)$ is the number of initial $0$-digits in $x$ and $b_{k-1}\log(N)$
is the number of initial $(k-1)$-digits (so $\min(b_{0},b_{k-1})=0$). After
the first $(b_{0}+b_{k-1})\log(N)$ digits, $x$ contains $c_{i}\log(N)$ digits
of $i$ for each $i\in[k]_{0}$.

The normalization $\frac{1}{\log N}$ above is taken so that the total sum
$\frac{M}{\log N}$ is of constant order. We next define constants depending on
the digit profile of $x$. Let

$c_{\text{\tt{tot}}}(x)=\sum_{i=0}^{k-1}c_{i}(x)$

be the number of digits in $x$ after the initial $0$ or initial $(k-1)$
digits. Also define

$\displaystyle c_{L}(x)$ $\displaystyle\equiv
1-b_{0}\log\left(\frac{1}{p_{0}}\right)-b_{k-1}\log\left(\frac{1}{p_{k-1}}\right)-\sum_{i=0}^{k-1}c_{i}\log\left(\frac{1}{p_{i}}\right)=1+\log_{N}(\lambda_{x}),$
$\displaystyle c_{F}(x)$
$\displaystyle\equiv\frac{1-b_{0}\log\left(\frac{1}{p_{0}}\right)-b_{k-1}\log\left(\frac{1}{p_{k-1}}\right)}{2},$
$\displaystyle c_{D}(x)$ $\displaystyle\equiv
c_{L}(x)-c_{F}(x)=\frac{1-b_{0}\log\left(\frac{1}{p_{0}}\right)-b_{k-1}\log\left(\frac{1}{p_{k-1}}\right)}{2}-\sum_{i=0}^{k-1}c_{i}\log\left(\frac{1}{p_{i}}\right),$
$\displaystyle c_{E}(x)$ $\displaystyle\equiv\left(\frac{M-K}{\log
N}\right)\psi_{\operatorname{\mathbf{p}}}(2)=\left(b_{0}+b_{k-1}+c_{\text{\tt{tot}}}-\frac{K}{\log
N}\right)\psi_{\operatorname{\mathbf{p}}}(2)<0,$ $\displaystyle c_{X}(x)$
$\displaystyle\equiv
c_{\text{\tt{tot}}}H(c_{0},\dots,c_{k-1})+5c_{L}-2c_{F}+2c_{E}.$

Finally say $x$ is _$\delta$ -stable_ if

$c_{L}(x)-c_{F}(x)\in[\delta,2\delta].$ (4.6)

The typical size of $|\mathcal{I}(B_{x})|$ is $N^{c_{L}}$ while $N^{c_{F}}$ is
the order of fluctuations for $\iota(x)$ and $\tau(x)$. $c_{E}$ is related to
the typical number of $G$-edges coming from strings in $B_{x}$. $c_{X}$ is
related to the typical number of $G$-edges coming from strings of the same
digit profile as $x$. Note that when $b_{0}=b_{k-1}=0$ we have
$c_{F}=\frac{1}{2}$. As explained in the next subsection, this corresponds to
$\iota(x)$ and $\tau(x)$ having fluctuations of order $N^{1/2}$.

###  4.2 Proof Outline for Proposition 4.1

We now outline the proof of Proposition 4.1. Except for the end of this
outline we will only consider strings $x$ with $b_{0}(x)=b_{k-1}(x)=0$ so that
the interval $J_{x}\in[0,1]$ is a constant distance from the boundary points
$\\{0,1\\}$. We will take $\delta\ll\varepsilon$ to be a small constant, and
simply write $\delta$ when a constant multiple such as $4\delta$ would be
technically correct. Since we are targeting an upper bound
$O\left(N^{-\Omega_{\operatorname{\mathbf{p}}}(\varepsilon)}\right)$ in
Proposition 4.1, factors of $N^{O(\delta)}$ can usually be thought of as
small.

The first idea is to start from the empty block $B_{\emptyset}=[k]_{0}^{K}$
and recursively refine the partition of $[k]_{0}^{K}$ by decomposing a block
$B_{x}$ into $k$ smaller blocks via

$B_{x}=\bigcup_{i\in[k]_{0}}B_{xi}.$

For example when $k=2$ such a refinement might proceed as

$B_{\emptyset}\to B_{0}\cup B_{1}\to B_{00}\cup B_{01}\cup B_{1}=[2]_{0}^{K}.$

We recursively refine the partition $B_{\emptyset}$ in this way until each
block $B_{x}$ in the partition has size
$\mu_{\operatorname{\mathbf{p}}}(B_{x})\approx N^{-\frac{1}{2}+\delta}$; this
is formally carried out in Lemma 4.5. The set of strings $x$ used in the
resulting partition is denoted by $\mathcal{L}_{\text{\tt{stable}}}$, so that
we obtain

$[k]_{0}^{K}=\bigcup_{x\in\mathcal{L}_{\text{\tt{stable}}}}B_{x},\quad\text{
and
}\quad[N]=\bigcup_{x\in\mathcal{L}_{\text{\tt{stable}}}}\mathcal{I}(B_{x}).$
(4.7)

as in Lemma 4.6. The first and last indices $\iota(x)$ and $\tau(x)$ of
$\mathcal{I}(B_{x})$ are (non-independent) binomial random variables with $N$
trials, hence each fluctuate by at most $O(N^{1/2})$ with high probability.

The upshot of the above is that the random set $\mathcal{I}(B_{x})$ agrees
with a discrete deterministic interval of size $|NJ_{x}\cap\mathbb{Z}|\approx
N^{\frac{1}{2}+\delta}$ up to boundary fluctuations $|\iota(x)-Nt_{x}|$ and
$|\tau(x)-N(t_{x}+\lambda_{x})|$ which are smaller than
$N^{\frac{1}{2}+\delta}$ with high probability. Because the random interval
$\mathcal{I}(B_{x})$ has typical size of larger order than the fluctuations of
its left and right endpoints, we may think of $\mathcal{I}(B_{x})$ as being
nearly deterministic. In line with this intuition, we show in Lemma 4.10 that
given any $i\in[N]$ there exist adjacent
$x_{i,1},x_{i,2}\in\mathcal{L}_{\text{\tt{stable}}}$ such that
$i\in\mathcal{I}(B_{x_{i,1}})\cup\mathcal{I}(B_{x_{i,2}})$ holds with
extremely high probability. Combining this with AM-GM, we show in Lemma 4.11
that $\mathbb{E}[|E(G,G^{\prime})|]$ is upper bounded by the expected number
of shared edges from pairs $(G_{B_{x}},G^{\prime}_{B_{x}})$ of matching blocks
as follows.

$\displaystyle\mathbb{E}[|E(G,G^{\prime})|]$
$\displaystyle\lesssim\sum_{x\in\mathcal{L}_{\text{\tt{stable}}}}\mathbb{E}[E(G_{B_{x}},G^{\prime}_{B_{x}})]$
(4.8)
$\displaystyle=\sum_{x\in\mathcal{L}_{\text{\tt{stable}}}}\sum_{i=1}^{N-1}\mathbb{P}[(i,i+1)\in
E(G_{B_{x}})]^{2}.$

Here the informal notation $\lesssim$ hides a constant factor and a negligible
additive term.

Our next objective is to upper-bound for each $x$ the probability
$\mathbb{P}[(i,i+1)\in E(G_{B_{x}})]$ appearing in (4.8). We do this by
conditioning on the multiset $S_{x}$ of strings appearing in
$\mathcal{I}(B_{x})$ and averaging over the still-random external strings.
Although this conditioning determines the size and internal edge-structure of
$\mathcal{I}(B_{x})$, the _position_ of $\mathcal{I}(B_{x})$ is conditionally
random. Indeed the position of the interval $\mathcal{I}(B_{x})$ depends on
the number of external strings lexicographically smaller than $x$, which we
have not conditioned on. This shift is conditionally binomial with order
$N^{1/2}$ fluctuations. Crucially, these fluctuations “homogenize” the edge
locations within each block $B_{x}$. Indeed averaging over these external
shifts, it follows that

$\max_{i\in[N-1]}\mathbb{P}[(i,i+1)\in
E(G_{B_{x}})|S_{x}]\lesssim\frac{|E(G_{B_{x}})|}{N^{1/2}}.$ (4.9)

It is not difficult to control the typical size $|E(G_{B_{x}})|$. Moreover
since the location of $\mathcal{I}(B_{x})$ is almost deterministic, the above
probability is negligibly small for all but
$O(\mathbb{E}[|\mathcal{I}(B_{x})|])=O(N^{\frac{1}{2}+\delta})$ values of $i$.
Combining these considerations leads to an upper bound on

$\sum_{i=1}^{N-1}\mathbb{P}[(i,i+1)\in E(G_{B_{x}})]^{2}.$ (4.10)

The precise bound requires some care to state and is given in Lemma 4.14.

The preceding argument allowed us to estimate (4.10) for each $x$. In light of
(4.8), it remains to sum over $x\in\mathcal{L}_{\text{\tt{stable}}}$. The last
key point is that all $x\in\mathcal{L}_{\text{\tt{stable}}}$ with a given
digit profile contribute essentially identically. Moreover there are only
$\log(N)^{O(1)}\leq N^{o(1)}$ possible digit profiles. It therefore suffices
to count the number of $x\in\mathcal{L}_{\text{\tt{stable}}}$ with each digit
profile and then determine the maximum total contribution of any fixed digit
profile. This count is easily approximated using Proposition 4.2. The
resulting maximum turns out to be achieved when $x$ has digit frequencies
approximately given by
$\operatorname{\mathbf{p}}^{\theta_{\operatorname{\mathbf{p}}}}$, which leads
to the appearance of the constant $C_{\operatorname{\mathbf{p}}}$.

So far, this outline considered only blocks $B_{x}$ with
$b_{0}(x)=b_{k-1}(x)=0$. When $b_{0}(x)$ or $b_{k-1}(x)$ is large the
fluctuations of $\iota(x)$ and $\tau(x)$ shrink, simply because the variance
$Np(1-p)$ of a $\text{\tt{Bin}}(N,p)$ random variable shrinks when $p$ is
close to $0$ or $1$. To handle such prefixes $x$ requires a slightly revised
definition of $\mathcal{L}_{\text{\tt{stable}}}$. In general the fluctuations
of $\iota(x)$ and $\tau(x)$ should be slightly smaller than the typical size
of $\mathcal{I}(B_{x})$; this is precisely the definition of
$\delta$-stability in (4.6). It turns out that the resulting maximization
problem over digit profiles nearly reduces to considering those with
$b_{0}=b_{k-1}=0$. Indeed by an elementary linearity argument (see (4.18)),
the only other digit profiles that must be considered are the degenerate cases
with $c_{0}=c_{1}=\dots=c_{k-1}=0$ in which $x$ consists of all $0$ digits or
all $(k-1)$ digits. These cases are much simpler and lead to the requirement
that

$\underline{C}_{\operatorname{\mathbf{p}}}\geq\max\left(\frac{1}{\log(1/p_{0})},\frac{1}{\log(1/p_{k-1})}\right).$

During a first reading of the next subsection it may be easier to focus on the
main case $b_{0}=b_{k-1}=0$ so that the proofs match the outline above more
closely.

Finally, we remark that the estimates outlined after (4.8) lead to the
inequality

$\mathbb{E}[|E(G,G^{\prime})|]\lesssim
N^{O(\delta)}\sum_{x\in\mathcal{L}_{\text{\tt{stable}}}}\frac{\mathbb{E}[|E(G_{B_{x}})|]^{2}}{\mathbb{E}[|\mathcal{I}(B_{x})|]}.$

Hence for the purpose of counting edges in $E(G,G^{\prime})$, each block
$B_{x}$ behaves approximately like an i.i.d. point process of edges in
$\mathcal{I}(B_{x})$ with $x$-dependent edge probability
$\frac{\mathbb{E}[|E(G_{B_{x}})|]}{\mathbb{E}[|\mathcal{I}(B_{x})|]}$. In fact
(4.9) states that this holds more precisely at the level of individual edge
probabilities. These hold precisely because the boundary fluctuations of
$\mathcal{I}(B_{x})$ are only slightly smaller than
$\mathbb{E}[|\mathcal{I}(B_{x})|]$, so that the homogenizing effect of the
random shifts is near-total. Somewhat fancifully, one might then view the
partition (4.7) as analogous to an ergodic or pure state decomposition.

###  4.3 The Partition into Stable Blocks

We now turn to a tree-based partition of $[k]_{0}^{K}$ into blocks $B_{x}$.
Define the $k$-ary rooted tree $\mathcal{T}=\mathcal{T}_{k,K}$ of depth $K$
which consists of all $[k]_{0}$-strings of length $M$ at each level $0\leq
M\leq K$. Here the children of $s\in[k]_{0}^{M}$ are the concatenations
$s0,s1,\dots,s(k-1)\in[k]_{0}^{M+1}$. Hence the leaves of $\mathcal{T}$ are
given by $[k]_{0}^{K}$ while the root of $\mathcal{T}$ is the empty string
$\emptyset$. Recall from Subsection 4.1 the definition

$c_{D}(x)=c_{L}(x)-c_{F}(x)=\frac{1-b_{0}\log\left(\frac{1}{p_{0}}\right)-b_{k-1}\log\left(\frac{1}{p_{k-1}}\right)}{2}-\sum_{i=0}^{k-1}c_{i}\log\left(\frac{1}{p_{i}}\right).$

Moreover, as in Proposition 4.1, we assume throughout that
$K\geq(\underline{C}_{\operatorname{\mathbf{p}}}+\varepsilon)\log(N)$ holds
for some small, fixed $\varepsilon>0$.

######  Lemma 4.4.

Let $x$ be the parent of $y$ in $\mathcal{T}$. Then

$\displaystyle 0\leq c_{D}(x)-c_{D}(y)\leq O\left(\frac{1}{\log(N)}\right).$
(4.11)

Moreover $c_{D}$ takes value $c_{D}(\emptyset)=\frac{1}{2}$ at the root, while
$c_{D}(s)\leq-\Omega_{\operatorname{\mathbf{p}}}(\varepsilon)$ for any leaf
$s\in[k]_{0}^{K}$.

###### Proof.

The values $b_{0},b_{k-1},c_{0},\dots,c_{k-1}$ each change by
$O\left(1/\log(N)\right)$ between neighboring vertices in $\mathcal{T}$, which
shows that

$|c_{D}(x)-c_{D}(y)|\leq O\left(\frac{1}{\log(N)}\right).$

Moreover since $c_{D}$ is decreasing in each coordinate of the digit profile
it follows that $c_{D}(x)-c_{D}(y)\geq 0$. This concludes the proof of (4.11).

When $x=\emptyset$ is the root, $b_{0}=b_{k-1}=c_{0}=\dots=c_{k-1}=0$, and so
$c_{D}(\emptyset)=\frac{1}{2}$. Finally for any leaf $s\in[k]_{0}^{K}$ of
$\mathcal{T}$ we have

$b_{0}(s)+b_{k-1}(s)+\sum_{i=0}^{k-1}c_{i}(s)=K\geq\underline{C}_{\operatorname{\mathbf{p}}}+\varepsilon.$

Since $t\to\log(\frac{1}{t})$ is decreasing and positive for $t\in(0,1)$,

$\displaystyle c_{L}(s)-c_{F}(s)$
$\displaystyle=\frac{1}{2}-b_{0}\cdot\frac{\log\left(\frac{1}{p_{0}}\right)}{2}-b_{k-1}\cdot\frac{\log\left(\frac{1}{p_{k-1}}\right)}{2}-\sum_{i=0}^{k-1}c_{i}\log\left(\frac{1}{p_{i}}\right)$
$\displaystyle\leq\frac{1}{2}-\frac{(\underline{C}_{\operatorname{\mathbf{p}}}+\varepsilon)\min(\log(1/p_{0}),\log(1/p_{k-1}),2\log(1/p_{\text{\tt{max}}}))}{2}$

By definition $\underline{C}_{\operatorname{\mathbf{p}}}\log(1/p_{0})\geq 1$
and $\underline{C}_{\operatorname{\mathbf{p}}}\log(1/p_{k-1})\geq 1$. Moreover
Proposition 1.1 implies

$2\underline{C}_{\operatorname{\mathbf{p}}}\log(1/p_{\text{\tt{max}}})\geq\frac{2C_{\operatorname{\mathbf{p}}}}{\widetilde{C}_{\operatorname{\mathbf{p}}}}\geq
1.$

Combining yields

$\underline{C}_{\operatorname{\mathbf{p}}}\cdot\min(\log(1/p_{0}),\log(1/p_{k-1}),2\log(1/p_{\text{\tt{max}}}))\geq
1$

which implies the result. ∎

Define the subtree $\mathcal{T}_{\text{\tt{stable}}}\subseteq\mathcal{T}$ to
consist of all $x\in\mathcal{T}$ with $c_{D}(x)\geq 2\delta$, as well as all
children of such $x$. Let $\mathcal{L}_{\text{\tt{stable}}}$ denote the set of
leaves of $\mathcal{T}_{\text{\tt{stable}}}$. We say a finite rooted tree is a
_full $k$-ary tree_ if all of its vertices have either $0$ or $k$ children.

######  Lemma 4.5.

$\mathcal{T}_{\text{\tt{stable}}}$ is a full $k$-ary tree. Moreover
$\mathcal{L}_{\text{\tt{stable}}}$ consists entirely of $\delta$-stable
strings. Finally all $x\in\mathcal{L}_{\text{\tt{stable}}}$ are strings of
length in $[\Omega_{\operatorname{\mathbf{p}},\delta}(\log
N),K-\Omega_{\operatorname{\mathbf{p}},\delta}(\log N)]$ and satisfy

$c_{F}(x)\geq\delta\quad\text{ and }\quad c_{L}(x)\geq 2\delta.$

###### Proof.

First we explain why $\mathcal{T}_{\text{\tt{stable}}}$ is a full $k$-ary
tree. The point is that since $c_{D}(x)$ is decreasing down $\mathcal{T}$ by
Lemma 4.4, the set of strings $x$ with $c_{D}(x)\geq 2\delta$ forms a subtree,
and adding all children of such $x$ therefore yields a full $k$-ary subtree.

Next, Lemma 4.4 shows $c_{D}(\emptyset)=\frac{1}{2}$ while
$c_{D}(s)\leq-\Omega_{\operatorname{\mathbf{p}}}(\varepsilon)$ for any $s$ of
length $K$, and also shows $c_{D}$ has Lipschitz constant
$O\left(\frac{1}{\log(N)}\right)$ on $\mathcal{T}$. It follows that
$\mathcal{T}_{\text{\tt{stable}}}$ contains all of the first $\Omega(\log(N))$
levels of $\mathcal{T}$ but none of the last $\Omega(\log(N))$. As a result
all $x\in\mathcal{L}_{\text{\tt{stable}}}$ have length in

$[\Omega_{\operatorname{\mathbf{p}},\delta}(\log(N)),K-\Omega_{\operatorname{\mathbf{p}},\delta}(\log(N))].$

The fact that all leaves are $\delta$-stable holds because children were added
in the definition of $\mathcal{T}_{\text{\tt{stable}}}$. Indeed this
definition combined with (4.11) implies that

$c_{D}(x)\in[2\delta-O(1/\log N),2\delta]$

for all $x\in\mathcal{L}_{\text{\tt{stable}}}$. Moreover recalling the
definition (4.6), all $x\in\mathcal{L}_{\text{\tt{stable}}}$ satisfy

$c_{F}(x)+\delta\leq c_{L}(x).$

Finally the inequality $c_{L}(x)\leq 2c_{F}(x)$ holds for any string $x$.
Altogether, these inequalities imply $c_{F}(x)\geq\delta$ and therefore

$c_{L}(x)\geq c_{F}(x)+\delta\geq 2\delta.$

∎

######  Lemma 4.6.

The following partitions (i.e. disjoint unions) hold:

$[k]_{0}^{K}=\bigcup_{x\in\mathcal{L}_{\text{\tt{stable}}}}B_{x}\quad\text{
and
}\quad[N]=\bigcup_{x\in\mathcal{L}_{\text{\tt{stable}}}}\mathcal{I}(B_{x}).$
(4.12)

###### Proof.

The first partition clearly implies the second. The first partition holds
because $\mathcal{L}_{\text{\tt{stable}}}$ consists of the leaves of
$\mathcal{T}_{\text{\tt{stable}}}$ and
$\mathcal{T}_{\text{\tt{stable}}}\subseteq\mathcal{T}$ is a full $k$-ary
subtree. Indeed, it simply asserts that the subtrees of $\mathcal{T}$ rooted
at each $x\in\mathcal{L}_{\text{\tt{stable}}}$ partition the leaves of
$\mathcal{T}$. ∎

Figure 5: The first partition in Lemma 4.6 is shown in the case that
$\mathcal{L}_{\text{\tt{stable}}}=\\{B_{00},B_{01},B_{1}\\}$ with
$(k,K)=(2,3)$. It states that $[k]_{0}^{K}=[2]_{0}^{3}=B_{00}\cup B_{01}\cup
B_{1}$.

###  4.4 No Edge Intersections in Expectation

In this subsection we prove Proposition 4.1. As explained in the outline, the
idea is to estimate $\mathbb{E}[|E(G,G^{\prime})|]$ by a sum of individual
contributions from each $x\in\mathcal{L}_{\text{\tt{stable}}}$ and then
control the total contribution from each digit profile.

######  Lemma 4.7.

Let $X\sim\text{\tt{Bin}}(N,q)$ for some $q\in[0,1]$. Then for
$t\leq\sqrt{Nq(1-q)}$,

$\mathbb{P}\left[\big{|}X-\mathbb{E}[X]\big{|}\geq t\sqrt{Nq(1-q)}\right]\leq
e^{-\Omega(t^{2})}$

holds uniformly over $q$.

###### Proof.

This follows from Bernstein’s inequality; see for instance [BLM13, Inequality
(2.10)]. ∎

######  Lemma 4.8.

For any $x\in[k]_{0}^{M}$, either

$\min(t_{x},1-t_{x})=0$

or

$\min(t_{x},1-t_{x})\asymp_{\operatorname{\mathbf{p}}}N^{-1+2c_{F}(x)}$

holds. The same holds for $\min(t_{x}+\lambda_{x},1-t_{x}-\lambda_{x})$. Here
$\asymp_{\operatorname{\mathbf{p}}}$ denotes asymptotic equality for large $N$
up to $\operatorname{\mathbf{p}}$-dependent constant factors.

###### Proof.

We focus on $\min(t_{x},1-t_{x})$ (as the two statements are symmetric) and
assume $x$ has a digit $x[i]\neq 0$ so that $t_{x}\neq 0$. If $x[1]=0$ and
$i>1$ is minimal with $x[i]\neq 0$, then $b_{0}(x)\log(N)=i-1$ and so

$t_{x}\asymp_{\operatorname{\mathbf{p}}}p_{0}^{b_{0}(x)\log(N)}=N^{-1+2c_{F}}.$

Similarly if $x[1]>0$ and $i^{\prime}>1$ is minimal with
$x[i^{\prime}]\neq(k-1)$, then

$1-t_{x}-\lambda_{x}\asymp_{\operatorname{\mathbf{p}}}p_{k-1}^{b_{k-1}(x)\log(N)}=N^{-1+2c_{F}}.$

∎

######  Lemma 4.9.

Let $x\in\mathcal{L}_{\text{\tt{stable}}}$ have digit profile
$(b_{0},b_{k-1},c_{0},\dots,c_{k-1})$. Then

$\displaystyle\mathbb{P}\left[\bigg{|}|\mathcal{I}(B_{x})|-N^{c_{L}}\bigg{|}\geq
N^{\frac{c_{L}+\delta}{2}}\right]$ $\displaystyle\leq
e^{-\Omega(N^{\delta})},$ (4.13)
$\displaystyle\mathbb{P}\left[\big{|}\iota(x)-Nt_{x}]\big{|}\geq
N^{c_{F}+\frac{\delta}{2}}\right]$ $\displaystyle\leq e^{-\Omega(N^{\delta})}$
(4.14)
$\displaystyle\mathbb{P}\left[\big{|}\tau(x)-N(t_{x}+\lambda_{x})\big{|}\geq
N^{c_{F}+\frac{\delta}{2}}\right]$ $\displaystyle\leq
e^{-\Omega(N^{\delta})}.$ (4.15)

###### Proof.

First, inequality (4.13) follows immediately from (4.1), by applying Lemma 4.7
with $t=N^{\delta/2}$.

For inequality (4.14) we similarly recall the distribution of $\iota$ given by
(4.2). From Lemma 4.8 it follows that unless $t_{x}=0$ (in which case
$\iota(x)=1$ with probability $1$),

$\min(t_{x},1-t_{x})\asymp N^{-1+2c_{F}}.$

Then Lemma 4.7 with $t=N^{\delta/2}$ completes the proof of (4.14) as
$\frac{\delta}{2}<\min(\frac{c_{L}}{2},c_{F})$ by Lemma 4.5. Inequality (4.15)
is proved identically. ∎

The next lemma shows that for any $i\in[N]$, there are at most two blocks
$B_{x_{i,1}},B_{x_{i,2}}$ that $i$ could plausibly appear in.

######  Lemma 4.10.

For each index $i\in[N]$, there exist
$x_{i,1},x_{i,2}\in\mathcal{L}_{\text{\tt{stable}}}$ with

$\mathbb{P}[i\in\mathcal{I}(B_{x_{i,1}})\cup\mathcal{I}(B_{x_{i,2}})]\geq
1-e^{-\Omega(N^{\delta})}.$

###### Proof.

Choose $x_{i,1}\in\mathcal{L}_{\text{\tt{stable}}}$ so that $\frac{i}{N}\in
J_{x}=[t_{x_{i,1}},t_{x_{i,1}}+\lambda_{x_{i,1}})$, and without loss of
generality assume

$\frac{i}{N}\in\bigg{[}t_{x_{i,1}}+\frac{\lambda_{x_{i,1}}}{2},t_{x_{i,1}}+\lambda_{x_{i,1}}\bigg{)}.$

Then we obtain

$\displaystyle\iota(x_{i,1})$ $\displaystyle\leq
Nt_{x_{i,1}}+\left|\iota(x_{i,1})-Nt_{x_{i,1}}\right|$ $\displaystyle\leq
i-\frac{N\lambda_{x_{i,1}}}{2}+\left|\iota(x_{i,1})-Nt_{x_{i,1}}\right|.$

As

$N\lambda_{x_{i,1}}=N^{c_{L}(x_{i,1})}\geq N^{c_{F}(x_{i,1})+\delta},$

using inequality (4.14) implies that

$\mathbb{P}[\iota(x_{i,1})\leq i]\geq 1-e^{-\Omega(N^{\delta})}$

If $x_{i,1}$ is the lexicographically last element of
$\mathcal{L}_{\text{\tt{stable}}}$ then $\iota(x_{i,1})\leq i$ already implies
$i\in\mathcal{I}(B_{x_{i,1}})$. Otherwise using Lemma 4.6 we take
$x_{i,2}\in\mathcal{L}_{\text{\tt{stable}}}$ immediately lexicographically
following $x_{i,1}$, so that $t_{x_{i,1}}+\lambda_{x_{i,1}}=t_{x_{i,2}}.$
Reasoning identically to the above shows that

$\mathbb{P}[\tau(x_{i,2})\geq i]\geq 1-e^{-\Omega(N^{\delta})}.$

If $\iota(x_{i,1})\leq i\leq\tau(x_{i,2})$, then
$i\in\mathcal{I}(B_{x_{i,1}})\cup\mathcal{I}(B_{x_{i,2}})$ holds because
$x_{i,1}$ and $x_{i,2}$ are consecutive in $\mathcal{L}_{\text{\tt{stable}}}$.
The result follows. ∎

Based on the previous lemma, we now upper-bound
$\mathbb{E}[|E(G,G^{\prime})|]$ by a sum over the individual blocks $B_{x}$.
Recall that $E(G_{B_{x}})\subseteq E(G)$ is the set of edges $(i,i+1)\in E(G)$
coming from strings $s_{i}=s_{i+1}\in B_{x}$.

######  Lemma 4.11.

$\mathbb{E}[|E(G,G^{\prime})|]\leq
e^{-\Omega(N^{\delta})}+4\sum_{x\in\mathcal{L}_{\text{\tt{stable}}}}\sum_{i=1}^{N-1}\mathbb{P}[(i,i+1)\in
E(G_{B_{x}})]^{2}.$

###### Proof.

Lemma 4.10 and the AM-GM inequality imply

$\displaystyle\mathbb{E}[|E(G,G^{\prime})|]$
$\displaystyle\leq\sum_{i=1}^{N-1}\mathbb{P}[(i,i+1)\in E(G,G^{\prime})]$
$\displaystyle\leq
e^{-\Omega(N^{\delta})}+\sum_{i=1}^{N-1}\sum_{j_{1},j_{2}\in\\{1,2\\}}\mathbb{P}[(i,i+1)\in
E(G_{B_{x_{i,j_{1}}}},G_{B_{x_{i,j_{2}}}})]$ $\displaystyle\leq
e^{-\Omega(N^{\delta})}+2\sum_{i=1}^{N-1}\sum_{j\in\\{1,2\\}}\mathbb{P}[(i,i+1)\in
E(G_{B_{x_{i,j}}})]^{2}$ $\displaystyle\leq
e^{-\Omega(N^{\delta})}+4\sum_{x\in\mathcal{L}_{\text{\tt{stable}}}}\sum_{i=1}^{N-1}\mathbb{P}[(i,i+1)\in
E(G_{B_{x}})]^{2}.$

∎

The next lemma uses the quantity

$c_{E}(x)=\left(\frac{M(x)-K}{\log
N}\right)\psi_{\operatorname{\mathbf{p}}}(2)=\left(b_{0}(x)+b_{k-1}(x)+c_{\text{\tt{tot}}}(x)-\frac{K}{\log
N}\right)\psi_{\operatorname{\mathbf{p}}}(2)<0$

defined near the end of Subsubsection 4.1.3.

######  Lemma 4.12.

For any $x\in\mathcal{T}$,

$\mathbb{E}\left[|E(G_{B_{x}})|~{}\big{|}~{}|\mathcal{I}(B_{x})|\right]\leq|\mathcal{I}(B_{x})|^{2}N^{c_{E}(x)}.$

###### Proof.

The right-hand side upper-bounds the expected number of pairs $(i,j)$ with
$s_{i}=s_{j}$ and $i,j\in\mathcal{I}(B_{x})$, by summing over the
$|\mathcal{I}(B_{x})|^{2}$ pairs of pre-sorted strings in $B_{x}$. Indeed it
is easy to see that for independent $\mu_{\operatorname{\mathbf{p}},K}$-random
strings $s$ and $s^{\prime}$, and fixed $x\in[k]_{0}^{M}$,

$\mathbb{P}[s=s^{\prime}|s,s^{\prime}\in
B_{x}]=\phi_{\operatorname{\mathbf{p}}}(2)^{-(K-M)}=N^{c_{E}(x)}.$

∎

The following lemma upper-bounds the probability for an edge $(i,i+1)$ to
appear in $E(G_{B_{x}})$ as a function of $x$, uniformly over $i\in[N]$. The
idea is that even conditioned on the value $|\mathcal{I}(B_{x})|$ and the
internal structure of $\mathcal{I}(B_{x})$, the remaining randomness of the
value $\iota(x)$ has a “homogenizing” effect.

######  Lemma 4.13.

For any $x\in\mathcal{L}_{\text{\tt{stable}}}$ and index $i\in[N-1]$,

$\mathbb{P}[(i,i+1)\in E(G_{B_{x}})]\leq
4N^{2c_{L}(x)-c_{F}(x)+c_{E}(x)+2\delta}+e^{-\Omega(N^{\delta})}.$

###### Proof.

We condition on the multiset of strings $S_{x}\equiv[s_{j}|s_{j}\in B_{x}]$
appearing in $B_{x}$. We will show that if

$|\mathcal{I}(B_{x})|\leq 2N^{c_{L}}\leq N/2$ (4.16)

holds, then

$\mathbb{P}[(i,i+1)\in E(G_{B_{x}})|S_{x}]\leq
4N^{2c_{L}(x)-c_{F}(x)+c_{E}(x)+2\delta}.$

This implies the desired result since by inequality (4.13),

$\mathbb{P}[|\mathcal{I}(B_{x})|\leq 2N^{c_{L}}]\geq
1-e^{-\Omega(N^{\delta})}.$

Observe that the multiset $S_{x}$ determines the values $|E(G_{B_{x}})|$ and
$|\mathcal{I}(B_{x})|=|S_{x}|$, and in fact determines the entire set
$E(G_{B_{x}})$ up to shifts. Given $S_{x}$, it is easy to see that $\iota(x)$
has conditional law

$\iota(x)\sim\text{\tt{Bin}}\left(N-|\mathcal{I}(B_{x})|,\frac{t_{x}}{1-\lambda_{x}}\right)+1.$

From (4.16), we have $N-|\mathcal{I}(B_{x})|\geq N/2$. Because any
$x\in\mathcal{L}_{\text{\tt{stable}}}$ has length $\Omega(\log(N))$ by Lemma
4.5, it follows that $\lambda_{x}\leq\frac{1}{2}$ for all
$x\in\mathcal{L}_{\text{\tt{stable}}}$ when $N$ is large enough. Therefore
Lemma 4.8 gives $t_{x}=0$ or $t_{x}\geq\Omega(N^{-1+2c_{F}})$. Similarly

$1-\frac{t_{x}}{1-\lambda_{x}}=\frac{1-t_{x}-\lambda_{x}}{1-\lambda_{x}}\geq\Omega(N^{-1+2c_{F}})$

unless $1-t_{x}-\lambda_{x}=0$.

Let us now split into two cases, the first being that

$\min(t_{x},1-t_{x}-\lambda_{x})>0.$

In this case we conclude that $\iota(x)-1$ is binomial with number of trials
$N-|\mathcal{I}(B_{x})|\geq N/2$ and total variance $\Omega(N^{2c_{F}})$.
Recalling that $c_{F}(x)\geq\delta$ for
$x\in\mathcal{L}_{\text{\tt{stable}}}$, the Lindeberg condition implies that
conditionally on $S_{x}$, $\iota(x)$ satisfies a central limit theorem with
standard deviation $\Omega\left(N^{c_{F}(x)}\right)$. Since $\iota(x)-1$ is
binomial, this implies a pointwise bound on its probability mass function.
Explicitly, we may apply either [Pit97, Equation 25] or the combination of
[Pit97, Equation 24] and [Can80, Theorem B] to obtain

$\max_{j\in[N]}\mathbb{P}[\iota(x)=j|S_{x}]\leq N^{-c_{F}(x)+2\delta}.$ (4.17)

Next in the second case, assume that

$\min(t_{x},1-t_{x}-\lambda_{x})=0.$

This simply means that $x$ consists of all digits $0$ or all digits $(k-1)$.
Then $c_{\text{\tt{tot}}}(x)=0$ and so $c_{L}=2c_{F}\leq c_{F}+2\delta$
implies $c_{F}\leq 2\delta.$ Hence (4.17) holds in either case. As a result
for any $i\in[N-1]$,

$\displaystyle\mathbb{P}\left[(i,i+1)\in E(G_{B_{x}})\mid S_{x}\right]$
$\displaystyle\leq|E(G_{B_{x}})|\cdot\max_{j\in[N]}\mathbb{P}\left[\iota(x)=j|S_{x}\right]$
$\displaystyle\leq|E(G_{B_{x}})|\cdot N^{-c_{F}(x)+2\delta}.$

Applying Lemma 4.12 shows that when (4.16) holds,

$\mathbb{P}\left[(i,i+1)\in E(G_{B_{x}})\mid S_{x}\right]\leq
4N^{2c_{L}(x)-c_{F}(x)+c_{E}(x)+2\delta}.$

∎

Using Lemma 4.13, we can estimate each term appearing in Lemma 4.11.

######  Lemma 4.14.

For any $x\in\mathcal{L}_{\text{\tt{stable}}}$,

$\sum_{i=1}^{N-1}\mathbb{P}[(i,i+1)\in E(G_{B_{x}})]^{2}\leq
64N^{5c_{L}(x)-2c_{F}(x)+2c_{E}(x)+4\delta}+e^{-\Omega(N^{\delta})}.$

###### Proof.

For those $i\in[N]$ with

$i\in\left[Nt_{x}-N^{c_{F}+\frac{\delta}{2}},N(t_{x}+\lambda_{x})+N^{c_{F}+\frac{\delta}{2}}\right],$

Lemma 4.13 implies

$\mathbb{P}[(i,i+1)\in E(G_{B_{x}})]\leq
4N^{2c_{L}(x)-c_{F}(x)+c_{E}(x)+2\delta}+e^{-\Omega(N^{\delta})}.$

As $c_{F}+\frac{\delta}{2}\leq c_{L}-\frac{\delta}{2}$, the above applies to
at most $2N^{c_{L}}$ values of $i$. For all other $i\in[N-1]$, inequalities
(4.14) and (4.15) imply $\mathbb{P}[(i,i+1)\in E(G_{B_{x}})]\leq
e^{-\Omega(N^{\delta})}.$ Combining and using $(a+b)^{2}\leq 2a^{2}+2b^{2}$
yields

$\displaystyle\sum_{i=1}^{N-1}\mathbb{P}[(i,i+1)\in E(G_{B_{x}})]^{2}$
$\displaystyle\leq
2N^{c_{L}}\left(4N^{2c_{L}(x)-c_{F}(x)+c_{E}(x)+2\delta}+e^{-\Omega(N^{\delta})}\right)^{2}+Ne^{-\Omega(N^{\delta})}$
$\displaystyle\leq
64N^{5c_{L}(x)-2c_{F}(x)+2c_{E}(x)+4\delta}+e^{-\Omega(N^{\delta})}.$

∎

Having controlled the individual summands in Lemma 4.11 in terms of the digit
profile of $x$, it remains to sum over $x\in\mathcal{L}_{\text{\tt{stable}}}$.
This amounts to determining the number of
$x\in\mathcal{L}_{\text{\tt{stable}}}$ with each possible digit profile, and
then finding the maximum possible contribution of each digit profile.
Recalling the definition

$c_{X}=c_{\text{\tt{tot}}}H(c_{0},\dots,c_{k-1})+5c_{L}-2c_{F}+2c_{E},$

it follows from Lemma 4.14 and Proposition 4.2 that the contribution of a
given digit profile $x$ to the bound of Lemma 4.11 is roughly $N^{c_{X}(x)}$.
The next lemma shows that $c_{X}(x)$ is uniformly negative over
$x\in\mathcal{L}_{\text{\tt{stable}}}$ when
$K\geq(\underline{C}_{\operatorname{\mathbf{p}}}+\varepsilon)\log(N)$. Here we
give a concise proof which does not provide much intuition for the constants
$\theta_{\operatorname{\mathbf{p}}}$ and $C_{\operatorname{\mathbf{p}}}$. See
Subsection 4.5 for another argument which is longer and less formal but
probably more enlightening.

######  Lemma 4.15.

For $\delta=\delta(\operatorname{\mathbf{p}},\varepsilon)$ small enough, if
$K\geq(\underline{C}_{\operatorname{\mathbf{p}}}+\varepsilon)\log(N)$ then

$\max_{(b_{0},b_{k-1},c_{0},\dots,c_{k-1})\text{
}\delta\text{-stable}}c_{X}(b_{0},b_{k-1},c_{0},\dots,c_{k-1})\leq-\Omega_{\operatorname{\mathbf{p}}}(\varepsilon)<0.$

###### Proof.

Let us extend the definitions of $c_{\text{\tt{tot}}},c_{F},c_{L},c_{E},$ and
$c_{X}$ to be functions of arbitrary $(k+2)$-tuples
$(b_{0},b_{k-1},c_{0},\dots,c_{k-1})\in\left(\mathbb{R}^{+}\right)^{k+2}$
which are constrained to satisfy $\min(b_{0},b_{k-1})=0$. Having done this, we
observe that $c_{X}=c_{X}(b_{0},b_{k-1},c_{0},\dots,c_{k-1})$ is affine in $t$
along the paths

$t\in\mathbb{R}\to\left(\left(1-t\alpha_{\operatorname{\mathbf{p}}}\right)b_{0},\left(1-t\alpha_{\operatorname{\mathbf{p}}}\right)b_{k-1},(1+t)c_{0},\dots,(1+t)c_{k-1}\right)$
(4.18)

where $\alpha_{\operatorname{\mathbf{p}}}\geq 0$ is chosen so that
$c_{L}-c_{F}$ remains constant as $t$ varies.

Therefore to conclude we only need to show $c_{X}\leq-\Omega(\varepsilon)$ at
the endpoint cases, which take the forms $(b_{0},b_{k-1},0,\dots,0)$ and
$(0,0,c_{0},\dots,c_{k-1})$ and which continue to satisfy
$c_{L}-c_{F}\in[\delta,2\delta].$ As either $b_{0}=0$ or $b_{k-1}=0$, we
assume without loss of generality that $b_{k-1}=0$. In the case
$(b_{0},0,\dots,0)$, we get

$\displaystyle c_{X}(b_{0},0,\dots,0)$
$\displaystyle=5-5b_{0}\log\left(\frac{1}{p_{0}}\right)-1+b_{0}\log\left(\frac{1}{p_{0}}\right)+2\left(b_{0}-\frac{K}{\log(N)}\right)\psi_{\operatorname{\mathbf{p}}}(2)+2\delta$
$\displaystyle=4\left(1-b_{0}\log\left(\frac{1}{p_{0}}\right)\right)+2\left(b_{0}-\frac{K}{\log(N)}\right)\psi_{\operatorname{\mathbf{p}}}(2)+2\delta$

From $c_{L}-c_{F}\in[\delta,2\delta]$ we obtain

$c_{L}-c_{F}=\frac{1-b_{0}\log\left(\frac{1}{p_{0}}\right)}{2}\in[\delta,2\delta]$

and so

$b_{0}\log\left(\frac{1}{p_{0}}\right)\in[1-4\delta,1-2\delta].$

Using also that

$\frac{K}{\log
N}\geq\underline{C}_{\operatorname{\mathbf{p}}}+\varepsilon\geq\frac{1}{\log(1/p_{0})}+\varepsilon,$

we find

$\displaystyle c_{X}(b_{0},0,\dots,0)$ $\displaystyle\leq
8\delta+2\left(\frac{1-2\delta}{\log\left(\frac{1}{p_{0}}\right)}-\frac{1+\varepsilon}{\log\left(\frac{1}{p_{0}}\right)}\right)\psi_{\operatorname{\mathbf{p}}}(2)+2\delta$
$\displaystyle\leq-\Omega_{\operatorname{\mathbf{p}}}(\varepsilon)+10\delta$
$\displaystyle\leq-\Omega_{\operatorname{\mathbf{p}}}(\varepsilon).$

The last inequality above holds because
$\delta=\delta(\operatorname{\mathbf{p}},\varepsilon)$ is sufficiently small.
We now turn to the main task of estimating $c_{X}(0,0,c_{0},\dots,c_{k-1})$.
We use the following identities and inequalities.

  * •

$c_{L}-c_{F}\in[\delta,2\delta]$.

  * •

$c_{F}=\frac{1}{2}$.

  * •

$H(\operatorname{\mathbf{p}}^{\theta_{\operatorname{\mathbf{p}}}})=\theta_{\operatorname{\mathbf{p}}}I(\operatorname{\mathbf{p}},\operatorname{\mathbf{p}}^{\theta_{\operatorname{\mathbf{p}}}})-\psi_{\operatorname{\mathbf{p}}}(\theta_{\operatorname{\mathbf{p}}})$.

  * •

$\psi_{\operatorname{\mathbf{p}}}(\theta_{\operatorname{\mathbf{p}}})=2\psi_{\operatorname{\mathbf{p}}}(2)$.

To deal with the entropy term in $c_{X}$, we use the non-negativity of
Kullback-Leibler divergence. For any discrete probability distribution
$\mathbf{q}=(q_{0},\dots,q_{k-1})$ (with $\sum_{i=0}^{k-1}q_{i}=1$),

$\displaystyle H(q_{0},\dots,q_{k-1})$
$\displaystyle=\sum_{i=0}^{k-1}q_{i}\log\left(\frac{1}{(\operatorname{\mathbf{p}}^{\theta_{\operatorname{\mathbf{p}}}})_{i}}\right)-D_{\text{\tt{KL}}}(\mathbf{q},\operatorname{\mathbf{p}}^{\theta_{\operatorname{\mathbf{p}}}})$
$\displaystyle\leq\sum_{i=0}^{k-1}q_{i}\log\left(\frac{1}{(\operatorname{\mathbf{p}}^{\theta_{\operatorname{\mathbf{p}}}})_{i}}\right)$
$\displaystyle=-\psi_{\operatorname{\mathbf{p}}}(\theta_{\operatorname{\mathbf{p}}})+\theta_{\operatorname{\mathbf{p}}}\sum_{i=0}^{k-1}q_{i}\log\left(\frac{1}{p_{i}}\right).$

Using the above estimate with $q_{i}=\frac{c_{i}}{c_{\text{\tt{tot}}}}$, we
find

$\displaystyle c_{X}(0,0,c_{0},\dots,c_{k-1})$
$\displaystyle=c_{\text{\tt{tot}}}H(c_{0},\dots,c_{k-1})+5(c_{L}-c_{F})+\frac{3}{2}+2c_{E}+2\delta$
$\displaystyle\leq-
c_{\text{\tt{tot}}}\psi_{\operatorname{\mathbf{p}}}(\theta_{\operatorname{\mathbf{p}}})+\theta_{\operatorname{\mathbf{p}}}\sum_{i=0}^{k-1}c_{i}\log\left(\frac{1}{p_{i}}\right)+\frac{3}{2}+2c_{E}+12\delta$
(4.19)
$\displaystyle\leq\theta_{\operatorname{\mathbf{p}}}\sum_{i=0}^{k-1}c_{i}\log\left(\frac{1}{p_{i}}\right)+\frac{3}{2}-2(\underline{C}_{\operatorname{\mathbf{p}}}+\varepsilon)\psi_{\operatorname{\mathbf{p}}}(2)+12\delta$
$\displaystyle\leq\theta_{\operatorname{\mathbf{p}}}\sum_{i=0}^{k-1}c_{i}\log\left(\frac{1}{p_{i}}\right)+\frac{3}{2}-2\psi_{\operatorname{\mathbf{p}}}(2)\underline{C}_{\operatorname{\mathbf{p}}}-\Omega_{\operatorname{\mathbf{p}}}(\varepsilon).$
(4.20)

The last line again follows because $\delta$ is sufficiently small. Finally we
recall the following:

$\displaystyle\sum_{i=0}^{k-1}c_{i}\log\left(\frac{1}{p_{i}}\right)$
$\displaystyle=1-c_{L}=\frac{1}{2}+O(\delta),$ $\displaystyle
C_{\operatorname{\mathbf{p}}}$
$\displaystyle=\frac{3+\theta_{\operatorname{\mathbf{p}}}}{4\psi_{\operatorname{\mathbf{p}}}(2)}\leq\underline{C}_{\operatorname{\mathbf{p}}}=\max\left(C_{\operatorname{\mathbf{p}}},\frac{1}{\log(1/p_{0})},\frac{1}{\log(1/p_{k-1})}\right).$

Substituting into the estimate (4.20), we obtain

$c_{X}(0,0,c_{0},\dots,c_{k-1})\leq\frac{3+\theta_{\operatorname{\mathbf{p}}}+O(\delta)}{2}-2\psi_{\operatorname{\mathbf{p}}}(2)\underline{C}_{\operatorname{\mathbf{p}}}-\Omega_{\operatorname{\mathbf{p}}}(\varepsilon)\leq-\Omega_{\operatorname{\mathbf{p}}}(\varepsilon).$

This completes the proof. ∎

Proposition 4.1 readily follows by combining the ingredients just established.

###### Proof of Proposition 4.1.

We start from the upper bound in Lemma 4.11 and group the strings
$x\in\mathcal{L}_{\text{\tt{stable}}}$ by their digit profile. For each digit
profile $(b_{0},b_{k-1},c_{0},c_{1},\dots,c_{k-1})$, by Proposition 4.2 the
number of corresponding blocks $x\in\mathcal{L}_{\text{\tt{stable}}}$ is at
most

$\binom{c_{\text{\tt{tot}}}\log(N)}{c_{0}\log(N),\dots,c_{k-1}\log(N)}\leq
N^{c_{\text{\tt{tot}}}H(c_{0},\dots,c_{k-1})}.$

Lemmas 4.14 and 4.15 imply that for each fixed digit profile
$(b_{0},b_{k-1},c_{0},c_{1},\dots,c_{k-1})$,

$\displaystyle\sum_{\begin{subarray}{c}x\in\mathcal{L}_{\text{\tt{stable}}},\\\
\text{Digit
Profile}(x)=(b_{0},\dots,c_{k-1})\end{subarray}}\sum_{i=1}^{N-1}\mathbb{P}[(i,i+1)\in
E(G_{B_{x}})]^{2}$ $\displaystyle\leq
64N^{c_{\text{\tt{tot}}}H(c_{0},\dots,c_{k-1})+5c_{L}-2c_{F}+2c_{E}+2\delta}+e^{-\Omega(N^{\delta})}$
$\displaystyle=64N^{c_{X}+4\delta}+e^{-\Omega(N^{\delta})}$ $\displaystyle\leq
64N^{-\Omega_{\operatorname{\mathbf{p}}}(\varepsilon)}+e^{-\Omega(N^{\delta})}.$

Since there are at most $O(\log^{k+2}(N))\leq N^{o(1)}$ total digit profiles
$(b_{0},b_{k-1},\dots,c_{k-1})$, Lemma 4.11 therefore yields the desired
estimate

$\mathbb{E}[|E(G,G^{\prime})|]\leq
256N^{-\Omega_{\operatorname{\mathbf{p}}}(\varepsilon)}+e^{-\Omega(N^{\delta})}.$

∎

###  4.5 Informal Derivation of the Value $C_{\operatorname{\mathbf{p}}}$

We saw the constant

$\psi_{\operatorname{\mathbf{p}}}(2)=-\log\sum_{i=0}^{k-1}p_{i}^{2}$

arise naturally in Lemma 4.12, expressed via $c_{E}$. In this informal
subsection, we will explain why the constants
$\theta_{\operatorname{\mathbf{p}}}$ and $C_{\operatorname{\mathbf{p}}}$
appeared in the final stages of the proof above by determining
“straightforwardly” how large $\frac{K}{\log N}$ must be for Lemma 4.15 to
hold. We again view $c_{X}(c_{0},\dots,c_{k-1})$ as a continuous function and
restrict to the main case that $b_{0}=b_{k-1}=0$. Moreover we will set all
$O(\delta)$ terms to zero for simplicity. For
$x\in\mathcal{L}_{\text{\tt{stable}}}$ with $b_{0}(x)=b_{k-1}(x)=0$, we have
$c_{L}(x)=c_{F}(x)=1/2$ which yields the constraint equation

$\sum_{i=0}^{k-1}c_{i}\log(1/p_{i})=\frac{1}{2}.$ (4.21)

Setting $C=\frac{K}{\log N}$, we find from $c_{L}(x)=c_{F}(x)=1/2$ that

$c_{X}=\big{(}H(c_{0},\dots,c_{k-1})+2\psi_{\operatorname{\mathbf{p}}}(2)\big{)}\cdot
c_{\text{\tt{tot}}}+\frac{3}{2}-2C\psi_{\operatorname{\mathbf{p}}}(2).$

To maximize $c_{X}=c_{X}(c_{0},\dots,c_{k-1})$ given the constraint (4.21), we
set the gradient $\nabla c_{X}$ to be parallel to the constraint direction
$\big{(}\log(1/p_{0}),\log(1/p_{1}),\dots,\log(1/p_{k-1})\big{)}$. (Without
arguing too formally, one expects there are no issues of maxima occurring at
the boundary because the entropy function is concave and its inward-normal
derivative diverges when any coordinate approaches $0$.) By writing out the
definition of entropy one readily computes that the maximizer
$(c_{0}^{*},\dots,c_{k-1}^{*})$ satisfies

$\displaystyle\theta\log(1/p_{i})$ $\displaystyle=\frac{\partial~{}}{\partial
c_{i}}(c_{X}^{*})$
$\displaystyle=2\psi_{\operatorname{\mathbf{p}}}(2)+\log(c_{\text{\tt{tot}}}^{*}/c_{i}^{*})-1+\sum_{j\in[k]_{0}}\frac{c_{j}^{*}}{c_{\text{\tt{tot}}}^{*}}$
$\displaystyle=2\psi_{\operatorname{\mathbf{p}}}(2)+\log(c_{\text{\tt{tot}}}^{*}/c_{i}^{*})$

for some proportionality constant $\theta\in\mathbb{R}$. Recalling that
$\psi_{\operatorname{\mathbf{p}}}(t)=-\log\phi_{\operatorname{\mathbf{p}}}(t)$
for $\phi_{\operatorname{\mathbf{p}}}(t)=\sum_{i=0}^{k-1}p_{i}^{t}$, we obtain
by rearranging

$\displaystyle\frac{c_{i}^{*}}{c_{\text{\tt{tot}}}^{*}}$
$\displaystyle=e^{2\psi_{\operatorname{\mathbf{p}}}(2)}p_{i}^{\theta}$
$\displaystyle=\frac{p_{i}^{\theta}}{\phi_{\operatorname{\mathbf{p}}}(2)^{2}}.$

Since $\sum_{i=0}^{k-1}\frac{c_{i}^{*}}{c_{\text{\tt{tot}}}^{*}}=1$ it follows
that
$\phi_{\operatorname{\mathbf{p}}}(\theta)=\phi_{\operatorname{\mathbf{p}}}(2)^{2}$,
i.e. $\theta=\theta_{\operatorname{\mathbf{p}}}$. Moreover we find
$\left(\frac{c_{0}^{*}}{c_{\text{\tt{tot}}}^{*}},\dots,\frac{c_{k-1}^{*}}{c_{\text{\tt{tot}}}^{*}}\right)=\operatorname{\mathbf{p}}^{\theta_{\operatorname{\mathbf{p}}}}.$
Solving for $c_{\text{\tt{tot}}}^{*}$ using (4.21) above yields

$\frac{1}{c_{\text{\tt{tot}}}^{*}}=\frac{2}{\phi(\theta_{\operatorname{\mathbf{p}}})}\sum_{i=0}^{k-1}p_{i}^{\theta_{\operatorname{\mathbf{p}}}}\log(1/p_{i})=2I(\operatorname{\mathbf{p}},\operatorname{\mathbf{p}}^{\theta_{\operatorname{\mathbf{p}}}}).$

Finally plugging back into the definition of $c_{X}$ and recalling properties
of $I(\operatorname{\mathbf{p}},\operatorname{\mathbf{p}}^{t})$,

$\displaystyle c_{X}(c_{0}^{*},\dots,c_{k-1}^{*})$
$\displaystyle=\frac{H(\operatorname{\mathbf{p}}^{\theta_{\operatorname{\mathbf{p}}}})+2\psi_{\operatorname{\mathbf{p}}}(2)}{2I(\operatorname{\mathbf{p}},\operatorname{\mathbf{p}}^{\theta_{\operatorname{\mathbf{p}}}})}+\frac{3}{2}-2C\psi_{\operatorname{\mathbf{p}}}(2)$
$\displaystyle=\frac{H(\operatorname{\mathbf{p}}^{\theta_{\operatorname{\mathbf{p}}}})+\psi_{\operatorname{\mathbf{p}}}(\theta_{\operatorname{\mathbf{p}}})}{2I(\operatorname{\mathbf{p}},\operatorname{\mathbf{p}}^{\theta_{\operatorname{\mathbf{p}}}})}+\frac{3}{2}-2C\psi_{\theta_{\operatorname{\mathbf{p}}}}(2)$
$\displaystyle=\frac{3+\theta_{\operatorname{\mathbf{p}}}}{2}-2C\psi_{\operatorname{\mathbf{p}}}(2).$

Rearranging shows that $c_{X}^{*}<0$ is equivalent to

$C>C_{\operatorname{\mathbf{p}}}=\frac{3+\theta_{\operatorname{\mathbf{p}}}}{4\psi_{\operatorname{\mathbf{p}}}(2)}=\frac{3+\theta_{\operatorname{\mathbf{p}}}}{2\psi_{\operatorname{\mathbf{p}}}(\theta_{\operatorname{\mathbf{p}}})}.$

Therefore we have “straightforwardly” recovered the statement of Lemma 4.15.
Let us also point out that

$\displaystyle c_{\text{\tt{tot}}}$
$\displaystyle=\frac{1}{2I(\operatorname{\mathbf{p}},\operatorname{\mathbf{p}}^{\theta_{\operatorname{\mathbf{p}}}})}=\frac{\theta_{\operatorname{\mathbf{p}}}}{2(H(\operatorname{\mathbf{p}}^{\theta_{\operatorname{\mathbf{p}}}})+\psi_{\operatorname{\mathbf{p}}}(\theta_{\operatorname{\mathbf{p}}}))}$
$\displaystyle<\frac{\theta_{\operatorname{\mathbf{p}}}}{2\psi_{\operatorname{\mathbf{p}}}(\theta_{\operatorname{\mathbf{p}}})}<\frac{3+\theta_{\operatorname{\mathbf{p}}}}{2\psi_{\operatorname{\mathbf{p}}}(\theta_{\operatorname{\mathbf{p}}})}$
$\displaystyle=C_{\operatorname{\mathbf{p}}}\leq\underline{C}_{\operatorname{\mathbf{p}}}.$

Here we used (4.5) in the first line. Hence the maximizer we found corresponds
to “real” blocks $B_{x}$ with length $M\approx c_{\text{\tt{tot}}}\log N<K$.

Since this argument ignored $O(\delta)$ error terms and some details on
boundary issues, we verified Lemma 4.15 directly in the previous section
instead of making the informal argument rigorous. The main step of this
verification was to use non-negativity of the Kullback-Leibler divergence
$D_{\text{\tt{KL}}}(\mathbf{q},\operatorname{\mathbf{p}}^{\theta_{\operatorname{\mathbf{p}}}})$
with $q_{i}=\frac{c_{i}}{c_{\text{\tt{tot}}}}$ in inequality (4.19). Given the
argument above, this step becomes quite natural. Indeed $c_{X}$ is linear in
$(c_{0},\dots,c_{k-1})$ except for the entropy term, so (4.19) simply
linearizes this entropy term around the equality case
$\left(\frac{c_{0}^{*}}{c_{\text{\tt{tot}}}^{*}},\dots,\frac{c_{k-1}^{*}}{c_{\text{\tt{tot}}}^{*}}\right)\approx\operatorname{\mathbf{p}}^{\theta_{p}}$.

##  5 Proof of Lemma 3.8

In this section we prove Lemma 3.8, whose statement is recalled now.

See 3.8

It was shown in Section 3 how to upper-bound the total variation distance from
uniform after $K$ $\operatorname{\mathbf{p}}$-shuffles based on the
exponential moment estimate above. Therefore establishing Lemma 3.8 will
complete the proof of the mixing time upper bound (1.3).

###  5.1 Preparatory Lemmas

Define $F(a,b)$ to be the value $\mathbb{E}[|E(G,G^{\prime})|]$ for i.i.d.
$\operatorname{\mathbf{p}}$-random shuffle graphs $G$ and $G^{\prime}$ on
decks of $a$ cards with $b$ shuffles. Proposition 4.1 provides the main upper
bound on $F(a,b)$, stated as a bound on $F(N,K)$. The next lemma gives a much
easier estimate we will use for small values of $a$ and $b$.

######  Lemma 5.1.

For any non-negative integers $a$ and $b$,

$F(a,b)\leq\min\left(a,a^{2}\cdot\phi_{\operatorname{\mathbf{p}}}(2)^{b}\right).$

###### Proof.

The bound $F(a,b)\leq a$ is obvious. The other bound

$\mathbb{E}[|E(G,G^{\prime})|]\leq\mathbb{E}[|E(G)|]\leq
a^{2}\phi_{\operatorname{\mathbf{p}}}(2)^{b}$

follows by summing over all $\binom{a}{2}$ pairs of strings $s_{i},s_{j}$ as
in Lemma 4.12. ∎

The next two lemmas allow us to upper-bound relatively complicated expected
edge intersections based on simple expected edge intersections. They will be
used below to estimate the left-hand side of (5.2) as a sum over the blocks in
the decomposition (5.3).

######  Lemma 5.2.

Let $A$ and $B$ be independent random subsets of a finite set $\mathcal{A}$.
Let $A^{\prime}$ and $B^{\prime}$ respectively be independent copies of $A$
and $B$. Then

$\mathbb{E}[|A\cap B|]\leq\frac{\mathbb{E}[|A\cap
A^{\prime}|]+\mathbb{E}[|B\cap B^{\prime}|]}{2}.$

###### Proof.

For each $a\in\mathcal{A}$ let $A_{a}=\mathbb{P}[a\in A]$ and
$B_{a}=\mathbb{P}[a\in B]$. Then the statement reduces to showing
$\sum_{a}A_{a}B_{a}\leq\frac{\sum_{a}(A_{a}^{2}+B_{a}^{2})}{2}$ which holds by
AM-GM. ∎

######  Lemma 5.3.

Let $A$ be a random subset of a finite set $\mathcal{A}$ and let $\mathcal{F}$
be a $\sigma$-algebra. Let $A^{\prime}$ be an independent copy of $A$ and let
$A_{\mathcal{F}}$ and $A_{\mathcal{F}}^{\prime}$ be conditionally independent
copies of $A$ conditioned on $\mathcal{F}$. Then

$\mathbb{E}[|A\cap A^{\prime}|]\leq\mathbb{E}[|A_{\mathcal{F}}\cap
A^{\prime}_{\mathcal{F}}|].$ (5.1)

###### Proof.

For each element $a\in\mathcal{A}$, let $Q_{a}=\mathbb{P}[a\in
A|\mathcal{F}]$. Let $P_{a}=\mathbb{P}[a\in A]=\mathbb{E}[Q_{a}]$. Then (5.1)
amounts to showing

$\sum_{a\in\mathcal{A}}P_{a}^{2}\leq\sum_{a\in\mathcal{A}}\mathbb{E}[Q_{a}^{2}].$

Since $\mathbb{E}[Q_{a}^{2}]-P_{a}^{2}\geq 0$ is simply the variance of the
random variable $Q_{a}$ for each $a$, the result follows. ∎

###  5.2 The Edge-Exploration Process

We now define the exploration process mentioned at the end of Section 3, which
explores a pair
$(s_{1},\dots,s_{N}),(s_{1}^{\prime},\dots,s_{N}^{\prime})\in\mathcal{S}$ of
sorted string sequences in order starting from $s_{1},s_{1}^{\prime}$. At step
$i$, the currently revealed strings are

$(s_{1},\dots,s_{i})\quad\text{and}\quad(s_{1}^{\prime},\dots,s^{\prime}_{i})$

which results in revealed subgraphs

$G_{i}\subseteq G,\quad G_{i}^{\prime}\subseteq G^{\prime}$

that grow with $i$. Explicitly, $G_{i}$ and $G_{i}^{\prime}$ are simply the
induced subgraphs of $G$ and $G^{\prime}$ on the vertex set
$\\{1,2,\dots,i\\}$. When either $s_{i}$ or $s_{i}^{\prime}$ begins with the
prefix $[(k-1)(k-1)]$ we stop the process. Essentially by definition, this
process finds all edges in $E_{\text{\tt{forward}}}(G,G^{\prime})$. As alluded
to at the end of Section 3, the following lemma shows how to bound the
exponential moments of $E_{\text{\tt{forward}}}(G,G^{\prime})$ using this
exploration process.

######  Lemma 5.4.

Suppose $\gamma>0$ is such that the conditional expectation estimate

$\mathbb{E}[E_{\text{\tt{forward}}}(G,G^{\prime})-E(G_{i},G_{i}^{\prime})|\mathcal{F}_{i}]\leq\gamma$
(5.2)

holds almost surely with
$\mathcal{F}_{i}\equiv\sigma(s_{1},\dots,s_{i},s_{1}^{\prime},\dots,s_{i}^{\prime})$
for each $i\in[N]$. Then

$\mathbb{E}[e^{t\cdot E_{\text{\tt{forward}}}(G,G^{\prime})}]\leq
1+2e^{t}\gamma$

for any $t>0$ satisfying $e^{t}\gamma\leq\frac{1}{10}$.

###### Proof.

Define for simplicity the random variable
$X=E_{\text{\tt{forward}}}(G,G^{\prime})$. For each $j\geq 0$ let
$t_{j}=\inf\\{i:E(G_{i},G_{i}^{\prime})\geq j\\}$. Then $t_{j}$ is an stopping
time, and if $t_{j}<\infty$ then $|E(G_{t_{j}},G^{\prime}_{t_{j}})|=j$ holds
because $E(G_{i+1},G_{i+1}^{\prime})-E(G_{i},G_{i}^{\prime})\leq 1$ holds
almost surely for each $i$. Morever when $t_{j}<\infty$ we have

$\mathbb{P}[X>j|\mathcal{F}_{t_{j}}]\leq\gamma$

due to the assumption (5.2). Of course the inequality $X\geq j$ implies that
$t_{j}$ is finite. Hence by optional stopping, we may average the above
display to conclude that

$\mathbb{P}[X>j|X\geq j]\leq\gamma.$

This means $X$ has hazard rate at least that of a geometric random variable
$Y$ with

$\mathbb{P}[Y=j]=(1-\gamma)\gamma^{j},\quad j\geq 0.$

Therefore $X$ is stochastically dominated by $Y$. Using the assumption
$e^{t}\gamma\leq\frac{1}{10}$, we find

$\displaystyle\mathbb{E}[e^{tX}]$ $\displaystyle\leq\mathbb{E}[e^{tY}]$
$\displaystyle\leq(1-\gamma)\sum_{j\geq 0}(e^{t}\gamma)^{j}$
$\displaystyle\leq\frac{1}{1-e^{t}\gamma}$ $\displaystyle\leq 1+2e^{t}\gamma.$

∎

To analyze the exploration process we group the potential future strings which
are lexicographically larger than $s_{i}$. Supposing that
$s_{i}<_{\text{\tt{lex}}}[(k-1)(k-1)]$ does not begin with $[(k-1)(k-1)]$, set

$\text{\tt{Blocks}}(s_{i})=\text{\tt{Blocks}}(s_{i},[(k-1)(k-1)])$

in the notation of Lemma 5.5 just below. By construction,
$\text{\tt{Blocks}}(s_{i})$ consists of $O(\log N)$ blocks and

$\\{s\in[k]_{0}^{K}:s_{i}<_{\text{\tt{lex}}}s<_{\text{\tt{lex}}}[(k-1)(k-1)]\\}=\bigcup_{x\in\text{\tt{Blocks}}(s_{i})}B_{x}.$
(5.3)

The fact that $|\text{\tt{Blocks}}(s_{i})|\leq O(\log N)\leq N^{o(1)}$ will be
used in the proof of Lemma 3.8 in the next subsection. It allows us to
estimate a sum over $x\in\text{\tt{Blocks}}(s_{i})$ by its maximum term; see
just before the start of Case 1 therein.

Figure 6: The decomposition of (5.3), guaranteed by Lemma 5.5, is shown when
$s_{i}=010$ with $(k,K)=(2,3)$. It states that
$\\{s\in[2]_{0}^{3}:010<_{\text{\tt{lex}}}s<_{\text{\tt{lex}}}11\\}=B_{001}\cup
B_{10}$.

######  Lemma 5.5.

Let $s_{a}<_{\text{\tt{lex}}}s_{b}$ be strings each of length at most $K$.
Define the lexicographic interval

$I_{s_{a},s_{b}}\equiv\\{s\in[k]_{0}^{K}:s_{a}<_{\text{\tt{lex}}}s<_{\text{\tt{lex}}}s_{b}\\}.$

Then $I_{s_{a},s_{b}}$ can be written as a disjoint union of blocks

$I_{s_{a},s_{b}}=\bigcup_{x\in\text{\tt{Blocks}}(s_{a},s_{b})}B_{x}$

for some set $\text{\tt{Blocks}}(s_{a},s_{b})$ containing at most $2Kk\leq
O(\log N)$ strings, each of length at most $K$.

###### Proof.

For $0\leq M\leq K$, define

$\overline{\text{\tt{Blocks}}}^{M}(s_{a},s_{b})=\\{x\in[k]_{0}^{M}:B_{x}\cap
I_{s_{a},s_{b}}\neq\emptyset\\}$

to be the set of all length-$M$ strings $x$ such that $B_{x}$ has non-trivial
intersection with $I_{s_{a},s_{b}}$. Similarly define

$\underline{\text{\tt{Blocks}}}^{M}(s_{a},s_{b})=\\{x\in[k]_{0}^{M}:B_{x}\subseteq
I_{s_{a},s_{b}}\\}$

to be the set of all length-$M$ strings $x$ such that $B_{x}$ is contained
inside $I_{s_{a},s_{b}}$. Clearly
$\underline{\text{\tt{Blocks}}}^{M}(s_{a},s_{b})\subseteq\overline{\text{\tt{Blocks}}}^{M}(s_{a},s_{b})$.
Moreover the fact that $I_{s_{a},s_{b}}$ is a lexicographic interval means
these sets differ in at most $2$ elements, i.e.

$\big{|}\overline{\text{\tt{Blocks}}}^{M}(s_{a},s_{b})\backslash\underline{\text{\tt{Blocks}}}^{M}(s_{a},s_{b})\big{|}\leq
2.$ (5.4)

Define

$\displaystyle\overline{\text{\tt{Blocks}}}(s_{a},s_{b})$
$\displaystyle=\bigcup_{0\leq M\leq
K}\overline{\text{\tt{Blocks}}}^{M}(s_{a},s_{b}),$
$\displaystyle\underline{\text{\tt{Blocks}}}(s_{a},s_{b})$
$\displaystyle=\bigcup_{0\leq M\leq
K}\underline{\text{\tt{Blocks}}}^{M}(s_{a},s_{b}).$

Next, for any $s\in I_{s_{a},s_{b}}$, note that all ancestors (prefixes) of
$s$ are contained in $\overline{\text{\tt{Blocks}}}(s_{a},s_{b})$, while
$\emptyset\notin\underline{\text{\tt{Blocks}}}(s_{a},s_{b})$. Let $y_{s}$ be
the longest ancestor string of $s$ with

$y_{s}\notin\underline{\text{\tt{Blocks}}}(s_{a},s_{b}).$

By definition $y_{s}\neq s$, so $y_{s}$ has a child $x_{s}$ which is also an
ancestor of $s$ (possibly $x_{s}=s$). By definition of $y_{s}$,

$x_{s}\in\underline{\text{\tt{Blocks}}}(s_{a},s_{b})$

and so

$B_{x_{s}}\subseteq I_{s_{a},s_{b}}.$

We claim the blocks $B_{x_{s}}$ constructed in this way from $s\in
I_{s_{a},s_{b}}$ are pairwise equal or disjoint. Indeed if

$B_{x_{s}}\subsetneq B_{x_{s^{\prime}}}$

then $x_{s^{\prime}}$ is a prefix of $y_{s}$. However

$y_{s}\notin\underline{\text{\tt{Blocks}}}(s_{a},s_{b})$

and

$x_{s^{\prime}}\in\underline{\text{\tt{Blocks}}}(s_{a},s_{b})$

which contradicts the fact that $\underline{\text{\tt{Blocks}}}(s_{a},s_{b})$
is descendent-closed.

Above, we started from an arbitrary $s\in I_{s_{a},s_{b}}$ and found a block
$B_{x_{s}}$ containing $s$. It follows that the distinct blocks $B_{x_{s}}$
appearing in the above construction form a partition of $I_{s_{a},s_{b}}$.
Finally, note that by inequality (5.4), and the fact that $y_{s}$ has length
at most $K-1$, $y_{s}$ ranges over a set of size at most $2K$. Hence $x_{s}$
ranges over a set of size at most $2Kk$. This concludes the proof. ∎

The next lemma shows that conditioning on the exploration process for $G$ up
to $s_{i}$ with

$s_{i}<_{\text{\tt{lex}}}[(k-1)(k-1)]$

does not dramatically increase the typical size of $\mathcal{I}(B_{x})$ for
any $x\in\text{\tt{Blocks}}(s_{i})$. The fact that
$s_{i}<_{\text{\tt{lex}}}[(k-1)(k-1)]$ is crucial here, as was discussed at
the end of Subsection 3.1. Indeed conditioning on $s_{i}=[(k-1)^{K}]$ would
imply that

$s_{i}=s_{i+1}=\dots=s_{N}=[(k-1)^{K}]$

so that $E(G)$ contains all remaining potential edges
$(i,i+1),(i+1,i+2),\dots,(N-1,N)$. However when
$s_{i}<_{\text{\tt{lex}}}[(k-1)(k-1)]$, a constant fraction of the
$\mu_{\operatorname{\mathbf{p}},K}$-measure of $[k]_{0}^{K}$ remains not yet
occupied, which prevents such an example from occuring.

######  Lemma 5.6.

Conditioned on $(s_{1},\dots,s_{i})$ which satisfy
$s_{i}<_{\text{\tt{lex}}}[(k-1)(k-1)]$, for any
$x\in\text{\tt{Blocks}}(s_{i})$ the conditional distribution of
$|\mathcal{I}(B_{x})|$ is stochastically dominated by a
$\text{\tt{Bin}}(N,p_{\text{\tt{min}}}^{-2}\lambda_{x})$ random variable.

###### Proof.

Condition further on the largest value $j\in[N]$ with $s_{i}=s_{j}$. Then we
can generate all strings $(s_{j+1},\dots,s_{N})$ by sampling i.i.d. random
numbers $a^{\prime}_{j+1},\dots,a^{\prime}_{N}$ uniformly from
$[t_{s_{i}}+\lambda_{s_{i}},1]$, sorting them into increasing order
$a_{j+1}\leq a_{j+2}\leq\dots\leq a_{N}$, and choosing
$s_{\ell}\in[k]_{0}^{K}$ such that $a_{\ell}\in J_{s_{\ell}}$ for $\ell\geq
j+1$. There are $N-j\leq N$ such random numbers $a_{\ell}$, and
$1-(t_{s_{i}}+\lambda_{s_{i}})\geq p_{\text{\tt{min}}}^{2}$ because of the
assumption that $s_{i}<_{\text{\tt{lex}}}[(k-1)(k-1)]$. Therefore
conditionally on $j$, each $a^{\prime}_{i}$ has probability at most
$p_{\text{\tt{min}}}^{-2}\lambda_{x}$ to fall into the interval $J_{x}$, which
completes the proof. ∎

###  5.3 Proof of Lemma 3.8

We now complete the proof of Lemma 3.8. In light of Lemma 5.4 it remains to
show that the conditional expectation for the number of unrevealed edges in
$E_{\text{\tt{forward}}}(G,G^{\prime})$, given by

$\mathbb{E}[E_{\text{\tt{forward}}}(G,G^{\prime})-E(G_{i},G_{i}^{\prime})|\mathcal{F}_{i}],$

is almost surely bounded by $O(N^{-\delta})$. The idea is to use Lemmas 5.2
and 5.3 to upper-bound this quantity by a sum over the future blocks appearing
in (5.3), see Equation (5.6) in the proof below. Analyzing the summand
corresponding to a block $B_{x}$ for $x\in[k]_{0}^{M}$ amounts to a smaller
version of the problem considered in Proposition 4.1 since $B_{x}$ can be
viewed as a copy of $[k]_{0}^{K-M}$. As a result, the summand for $B_{x}$ has
value $F(|\mathcal{I}_{B_{x}}|,K-M)$. This term can be estimated by Lemma 5.1
when $\mathbb{E}[|\mathcal{I}_{B_{x}}|]\leq N^{\delta}$ is small (Cases $1$
and $2$ of the proof below) and by Proposition 4.1 when
$\mathbb{E}[|\mathcal{I}_{B_{x}}|]\geq N^{\delta}$ is reasonably large (Case
$3$ of the proof).

###### Proof of Lemma 3.8.

Take $\delta=\delta(\operatorname{\mathbf{p}},\varepsilon)$ sufficiently
small, $\eta=\eta(\operatorname{\mathbf{p}},\varepsilon,\delta)$ smaller and
$\zeta=\zeta(\operatorname{\mathbf{p}},\varepsilon,\delta,\eta)$ yet smaller.
Define the following $\sigma$-algebras.

$\displaystyle\mathcal{F}_{i}$
$\displaystyle=\sigma(s_{1},\dots,s_{i},s_{1}^{\prime},\dots,s_{i}^{\prime}),$
$\displaystyle\widetilde{\mathcal{F}}_{i}$
$\displaystyle=\sigma\left(s_{1},\dots,s_{i},s_{1}^{\prime},\dots,s_{i}^{\prime},\left(\mathcal{I}(B_{x})\right)_{x\in\text{\tt{Blocks}}(s_{i})}\right).$

(Note that the $\sigma$-algebras $\widetilde{\mathcal{F}}_{i}$ do not define a
filtration as $i$ varies.) Let

$G_{u,1}=E_{\text{\tt{forward}}}(G)\backslash E(G_{i})$

consist of all so-far-unrevealed edges which do not involve strings beginning
with $[(k-1)(k-1)]$. Let $G_{u,2}$ be a conditionally independent copy of
$G_{u,1}$ given $\widetilde{\mathcal{F}}_{i}$ \- equivalently this means
$G_{u,2}$ is obtained by resampling $G_{u,1}$ conditioned to have the same
sets $\mathcal{I}(B_{x})$ for each $x\in\text{\tt{Blocks}}(s_{i})$. Define
$G^{\prime}_{u,1},G^{\prime}_{u,2}$ the same way for $G^{\prime}$. Hence
$G_{u,1},G_{u,2},G^{\prime}_{u,1},G^{\prime}_{u,2}$ are shuffle graphs with
all edge-endpoints in $\\{i,i+1,\dots,N\\}$.

We will show that at any time $i$ in the exploration process, the expected
number of unrevealed edges in $E_{\text{\tt{forward}}}(G,G^{\prime})$ is
bounded by

$\mathbb{E}[|E(G_{u,1},G_{u,1}^{\prime})|\big{|}\mathcal{F}_{i}]\leq
O(N^{-\zeta}).$

By Lemma 5.4, this will complete the proof of Lemma 3.8 up to replacing
$\zeta$ with $\delta$. First, using Lemmas 5.2 and 5.3 conditionally on
$\mathcal{F}_{i}$, we estimate the expected number of unrevealed edges by

$\mathbb{E}[|E(G_{u,1},G_{u,1}^{\prime})|\big{|}\mathcal{F}_{i}]\leq\mathbb{E}\left[\frac{|E(G_{u,1},G_{u,2})|+|E(G^{\prime}_{u,1},G^{\prime}_{u,2})|}{2}\big{|}\mathcal{F}_{i}\right].$

Therefore by symmetry it suffices to show that

$\mathbb{E}\left[|E(G_{u,1},G_{u,2})|\big{|}\mathcal{F}_{i}\right]\leq
O(N^{-\zeta})$

holds almost surely. By definition, conditioning on
$\widetilde{\mathcal{F}}_{i}$ determines the interval $\mathcal{I}(B_{x})$ for
each such $x$. Moreover the remaining $K-M$ digits of each of the
$|\mathcal{I}(B_{x})|$ random strings in $B_{x}$ are still i.i.d.
$\operatorname{\mathbf{p}}$-random. As a consequence,

$\mathbb{E}[E(G_{u,1},G_{u,2})\big{|}\widetilde{\mathcal{F}}_{i}]=\left|\\{j>i:s_{j}=s_{i}\\}\right|+\sum_{x\in\text{\tt{Blocks}}(s_{i})}F(|\mathcal{I}(B_{x})|,K-M).$
(5.5)

Indeed recall from the start of Subsection 5.1 that $F(a,b)$ is the expected
size of $E(G,G^{\prime})$ when there are $a$ cards and $b$ shuffles. Thus
(5.5) essentially holds by definition.

Next, the law of total expectation yields

$\displaystyle\mathbb{E}[E(G_{u,1},G_{u,2})\big{|}\mathcal{F}_{i}]$
$\displaystyle=\mathbb{E}\left[\mathbb{E}[E(G_{u,1},G_{u,2})\big{|}\widetilde{\mathcal{F}}_{i}]\bigg{|}\mathcal{F}_{i}\right]$
$\displaystyle=\mathbb{E}\left[\left|\\{j>i:s_{j}=s_{i}\\}\right|\big{|}\mathcal{F}_{i}\right]+\sum_{x\in\text{\tt{Blocks}}(s_{i})}\mathbb{E}\big{[}F(|\mathcal{I}(B_{x})|,K-M)\big{|}\mathcal{F}_{i}\big{]}.$
(5.6)

The first term on the right-hand side of (5.6) is controlled by Lemma 3.9,
which implies

$\mathbb{E}[|\\{j>i:s_{j}=s_{i}\\}|\big{|}\mathcal{F}_{i}]\leq O(N^{-\zeta}).$

To estimate the other (main) term on the right-hand side of (5.6), we will
show for each $x\in\text{\tt{Blocks}}(s_{i})$ that

$\mathbb{E}\big{[}F(|\mathcal{I}(B_{x})|,K-M)\big{|}\mathcal{F}_{i}\big{]}\leq
O(N^{-\zeta}).$

As $|\text{\tt{Blocks}}(s_{i})|=O(\log N)\leq N^{o(1)}$ this suffices to
finish the proof. We now split into three cases depending on the size of
$\lambda_{x}$. In all cases below we let $M$ denote the length of $x$. Case
$3$ (the main one) is where Proposition 4.1 is essential.

Let us emphasize that $|I(B_{x})|$ is still random conditionally on
$\mathcal{F}_{i}$. While we do not have good almost sure bounds on
$|I(B_{x})|$ itself, its conditional distribution is uniformly stochastically
bounded by Lemma 5.6. Since we are estimating a conditional expectation given
$\mathcal{F}_{i}$ and not $\widetilde{\mathcal{F}}_{i}$, this suffices for an
almost sure bound.

Case 1: $\lambda_{x}\leq N^{-1-\delta}$.  In this case, Lemmas 5.1 and 5.6
imply

$\displaystyle\mathbb{E}\big{[}F(|\mathcal{I}(B_{x})|,K-M)|\mathcal{F}_{i}\big{]}$
$\displaystyle\leq\mathbb{E}[|\mathcal{I}(B_{x})|]$ $\displaystyle\leq
O(N^{-\zeta}).$

Case 2: $N^{-1-\delta}\leq\lambda_{x}\leq N^{-1+\delta}$.  In this case,
Lemmas 5.6 and 4.7 imply that $|\mathcal{I}(B_{x})|\leq N^{2\delta}$ holds
with probability $1-e^{-\Omega(N^{\delta})}$. The fact
$\lambda_{x}\leq(p_{\text{\tt{max}}})^{M}$ implies

$\displaystyle M$
$\displaystyle\leq\frac{\log(\lambda_{x}^{-1})}{\log(p_{\text{\tt{max}}}^{-1})}$
$\displaystyle\leq\frac{(1+\delta)\log N}{\log(p_{\text{\tt{max}}}^{-1})}$

In particular as $\delta\ll\varepsilon$ is sufficiently small this implies
$K-M\geq\Omega_{\operatorname{\mathbf{p}}}(\varepsilon)\log N$. Lemma 5.1 now
yields

$\displaystyle\mathbb{E}\big{[}F(|\mathcal{I}(B_{x})|,K-M)|\mathcal{F}_{i}\big{]}$
$\displaystyle\leq\mathbb{E}[|\mathcal{I}(B_{x})|^{2}]\phi_{\operatorname{\mathbf{p}}}(2)^{\Omega_{\operatorname{\mathbf{p}}}(\varepsilon)\log(N)}$
$\displaystyle\leq
O\left(N^{2\delta-\Omega_{\operatorname{\mathbf{p}}}(\varepsilon)}\right)$
$\displaystyle\leq O(N^{-\zeta}).$

Case 3: $\lambda_{x}\geq N^{-1+\delta}$.  Similarly to the previous case,
observe that

$\displaystyle M$
$\displaystyle\leq\frac{\log(\lambda_{x}^{-1})}{\log(p_{\text{\tt{max}}}^{-1})}$
(5.7)
$\displaystyle\leq\overline{C}_{\operatorname{\mathbf{p}}}\log(\lambda_{x}^{-1}).$
(5.8)

We break into subcases depending on $|\mathcal{I}(B_{x})|$. The first subcase
is that $|\mathcal{I}(B_{x})|\leq N^{\eta}$. Here the lower bound
$K-M\geq\Omega_{\operatorname{\mathbf{p}}}(\delta\log N)$ follows from
inequality (5.8), and applying Lemma 5.1 yields

$F(|\mathcal{I}(B_{x})|,K-M)\leq
N^{2\eta}\phi_{\operatorname{\mathbf{p}}}(2)^{K-M}\leq
N^{-\Omega_{\operatorname{\mathbf{p}}}(\delta)}.$

In the main subcase
$|\mathcal{I}(B_{x})|\in[N^{\eta},2p_{\text{\tt{min}}}^{-2}N\lambda_{x}]$ we
obtain:

$\displaystyle K-M$
$\displaystyle\geq(\overline{C}_{\operatorname{\mathbf{p}}}+\varepsilon)\log(N\lambda_{x})$
(5.9)
$\displaystyle\geq\left(\overline{C}_{\operatorname{\mathbf{p}}}+\frac{\varepsilon}{2}\right)\log(2p_{\text{\tt{min}}}^{-2}N\lambda_{x})$
$\displaystyle\geq\left(\overline{C}_{\operatorname{\mathbf{p}}}+\frac{\varepsilon}{2}\right)\log|\mathcal{I}(B_{x})|.$

Since $|\mathcal{I}(B_{x})|\geq N^{\eta}$ tends to infinity with $N$,
Proposition 4.1 implies

$F(|\mathcal{I}(B_{x})|,K-M)\leq
O\left(|\mathcal{I}(B_{x})|^{-\delta}\right)\leq O(N^{-\zeta}).$

Finally the subcase $|\mathcal{I}(B_{x})|\geq
2p_{\text{\tt{min}}}^{-2}N\lambda_{x}$ occurs with tiny probability
$e^{-\Omega(N^{\delta})}$ by Lemmas 5.6 and 4.7. In this subcase we use the
trivial bound $F(|\mathcal{I}(B_{x})|,K-M)\leq N$. Combining subcases, we have
established that whenever Case 3 holds,

$\mathbb{E}\big{[}F(|\mathcal{I}(B_{x})|,K-M)|\mathcal{F}_{i}\big{]}\leq
O(N^{-\zeta}).$

Combining cases (and substituting $\delta$ for $\zeta$ at the end) concludes
the proof of Lemma 3.8. ∎

######  Remark 5.1.

Recall that throughout Section 4, and in particular in Proposition 4.1, the
weaker inequality
$K\geq(\underline{C}_{\operatorname{\mathbf{p}}}+\varepsilon)\log N$ sufficed
where

$\underline{C}_{\operatorname{\mathbf{p}}}\equiv\max\left(C_{\operatorname{\mathbf{p}}},\frac{1}{\log(1/p_{0})},\frac{1}{\log(1/p_{k-1})}\right)\leq\overline{C}_{\operatorname{\mathbf{p}}}.$

This means that when $k>2$, for some parameter choices such as
$\operatorname{\mathbf{p}}=(0.01,0.98,0.01)$, the expectation
$\mathbb{E}[|E(G,G^{\prime})|]$ becomes small before mixing occurs, so the
exponential moments of $|E(G,G^{\prime})|$ are still large. This discrepancy
can be explained as follows. When $K$ satisfies

$\underline{C}_{\operatorname{\mathbf{p}}}+\varepsilon<\frac{K}{\log
N}<\overline{C}_{\operatorname{\mathbf{p}}}-\varepsilon,$

the graph $G$ typically contains $N^{\Omega(1)}$-size connected components
coming from strings with nearly all digits $i_{\text{\tt{max}}}$. In such
situations $\mathbb{E}[|E(G,G^{\prime})|]\leq o(1)$ is small by Proposition
4.1. However an easy pigeonhole argument on $N$ copies of $G$ shows that with
$\Omega(1/N^{2})$ probability, $E(G,G^{\prime})$ contains an
$N^{\Omega(1)}$-sized component formed by a large $G$-component and large
$G^{\prime}$-component overlapping. As a result $|E(G,G^{\prime})|$ has large
exponential moments. (Moreover this argument still applies if we initially
require $S,S^{\prime}\in\mathcal{S}_{1}$ to be “typical”.)

In upper-bounding the mixing time, the bound
$K\geq(\overline{C}_{\operatorname{\mathbf{p}}}+\varepsilon)\log N$, as
opposed to $K\geq(\underline{C}_{\operatorname{\mathbf{p}}}+\varepsilon)\log
N$, is necessary in two places. The first is in Lemma 3.9. The other occurs
above in (5.9) where we needed to ensure that Proposition 4.1 yields an upper
bound for $F(|\mathcal{I}(B_{x})|,K-M)$. In the worst case, all $M$ of $x$’s
digits might be $i_{\text{\tt{max}}}$. Then typically (at least when the
right-hand side below is positive),

$\log|\mathcal{I}(B_{x})|\approx\log(N)-M\log(1/p_{\text{\tt{max}}}).$

To apply Proposition 4.1, we thus need

$K-M\geq\underline{C}_{\operatorname{\mathbf{p}}}(\log
N-M\log(1/p_{\text{\tt{max}}}))$

to hold for any $M$ making both sides positive. In particular, if we
continuously increase $M$ the right side must reach $0$ before the left side,
which implies $K\geq\frac{\log N}{\log(1/p_{\text{\tt{max}}})}.$ On the other
hand, when $M=0$ we need $K\geq\underline{C}_{\operatorname{\mathbf{p}}}\log
N$ for Proposition 4.1 to apply. Hence at least in bounding the exponential
moments of $|E(G,G^{\prime})|$, the value
$\overline{C}_{\operatorname{\mathbf{p}}}=\max\left(\underline{C}_{\operatorname{\mathbf{p}}},\frac{1}{\log(1/p_{\text{\tt{max}}})}\right)$
arises from the need to apply Proposition 4.1 for all sizes of block $B_{x}$
appearing in the partition (5.3).

##  6 Proof of the Mixing Time Lower Bound

In this section we take
$K=\lfloor(C_{\operatorname{\mathbf{p}}}-\varepsilon)\log(N)\rfloor$ and show
that almost no total-variation mixing occurs after $K$ shuffles. First, when
$K\leq(\widetilde{C}_{\operatorname{\mathbf{p}}}-\varepsilon)\log(N)$ we
previously argued at the start of Subsection 2.1 that the total variation
distance from uniform is $1-o(1)$. Hence we may assume that
$\widetilde{C}_{\operatorname{\mathbf{p}}}<C_{\operatorname{\mathbf{p}}}$
holds, else there is nothing to prove. By taking $\varepsilon$ small enough,
we may further assume

$K\geq(\widetilde{C}_{\operatorname{\mathbf{p}}}+\varepsilon)\log N.$ (6.1)

For a set $H\subseteq\mathbb{Z}$, its boundary $\partial H\subseteq H$ is
defined by

$\partial H\equiv\\{h\in H:h-1\notin H\text{ or }h+1\notin H\\}.$

Its edge set $E(H)$ is the set of edges with both endpoints in $H$, i.e. we
identify $H$ with the corresponding induced subgraph of $G$. We will verify
the following criterion from [Lal00] for non-mixing. The idea of the proof is
to use the number of ascents of $\sigma\in\operatorname{\mathfrak{S}}_{N}$
within $H$ to distinguish the uniform distribution $\sigma=\pi$ from the
shuffled distribution $\sigma=\pi^{G}$.

######  Proposition 6.1 ([Lal00, Proposition 2]).

Let $(K_{N})_{N\geq 1}$ be a deterministic sequence of positive integers.
Suppose there exist deterministic subsets $H=H_{N}\subseteq[N]$ such that for
some $\delta=\delta(\operatorname{\mathbf{p}},\varepsilon)$ the following
properties hold as $N\to\infty$, where $G$ is the shuffle graph for a deck of
$N$ cards undergoing $K_{N}$ $\operatorname{\mathbf{p}}$-shuffles:

$\displaystyle|H|$ $\displaystyle\to\infty$ (6.2) $\displaystyle|\partial H|$
$\displaystyle=O(|H|^{1/2})$ (6.3) $\displaystyle\mathbb{P}\left[|E(G)\cap
E(H)|\geq|H|^{\frac{1}{2}+\delta}\right]$ $\displaystyle\to 1.$ (6.4)

Then asymptotically no total-variation mixing occurs after $K_{N}$ shuffles,
i.e.

$\lim_{N\to\infty}d_{N}(K_{N})=1.$

######  Remark 6.1.

By using AM-GM or Cauchy–Schwarz similarly to the proof of Lemma 5.3, the
conditions of Proposition 6.1 imply

$\displaystyle\mathbb{E}[|E(G,G^{\prime})|]$
$\displaystyle\geq\frac{\mathbb{E}[|E(G)\cap E(H)|]^{2}}{|E(H)|}\cdot(1-o(1))$
$\displaystyle\geq\Omega(|H|^{2\delta})$ $\displaystyle\gg 1.$

However it does not follow from what we show that
$K=(\underline{C}_{\operatorname{\mathbf{p}}}\pm o(1))\log N$ is always the
cutoff point where the expected number $\mathbb{E}[|E(G,G^{\prime})|]$ of
shared edges in $G$ and $G^{\prime}$ transitions from superconstant to
subconstant. This is because the analysis of this section assumes inequality
(6.1).

###  6.1 Preparation and Proof Idea

Define
$\alpha_{\text{\tt{tot}}}\log(N)=\left\lfloor\frac{1-\delta}{2I(\operatorname{\mathbf{p}},\operatorname{\mathbf{p}}^{\theta_{\operatorname{\mathbf{p}}}})}\log(N)\right\rfloor$,
where as usual $\delta=\delta(\operatorname{\mathbf{p}},\varepsilon)$ is
sufficiently small. Choose (via some rounding procedure) positive integers
$\alpha_{0}\log(N),\dots,\alpha_{k-1}\log(N)$ satisfying

$\sum_{i=0}^{k-1}\alpha_{i}=\alpha_{\text{\tt{tot}}}\quad\text{ and
}\quad\left|\alpha_{i}\log(N)-\frac{\alpha_{\text{\tt{tot}}}\log(N)p_{i}^{\theta_{\operatorname{\mathbf{p}}}}}{\phi_{\operatorname{\mathbf{p}}}(\theta_{\operatorname{\mathbf{p}}})}\right|\leq
1.$ (6.5)

Note that
$\alpha_{\text{\tt{tot}}}\leq\frac{3\underline{C}_{\operatorname{\mathbf{p}}}}{4}$;
indeed we showed in Proposition 1.1 that
$\theta_{\operatorname{\mathbf{p}}}\leq 4$, hence

$\displaystyle\alpha_{\text{\tt{tot}}}+O(\delta)$
$\displaystyle=\frac{1}{2I(\operatorname{\mathbf{p}},\operatorname{\mathbf{p}}^{\theta_{\operatorname{\mathbf{p}}}})}=\frac{\theta_{\operatorname{\mathbf{p}}}}{2(H(\operatorname{\mathbf{p}}^{\theta_{\operatorname{\mathbf{p}}}})+\psi_{\operatorname{\mathbf{p}}}(\theta_{\operatorname{\mathbf{p}}}))}$
$\displaystyle<\frac{\theta_{\operatorname{\mathbf{p}}}}{2\psi_{\operatorname{\mathbf{p}}}(\theta_{\operatorname{\mathbf{p}}})}<\frac{3+\theta_{\operatorname{\mathbf{p}}}}{3\psi_{\operatorname{\mathbf{p}}}(\theta_{\operatorname{\mathbf{p}}})}$
$\displaystyle=\frac{2C_{\operatorname{\mathbf{p}}}}{3}\leq\frac{2\underline{C}_{\operatorname{\mathbf{p}}}}{3}.$

We may therefore take
$\beta_{\text{\tt{tot}}}\log(N)=K-\alpha_{\text{\tt{tot}}}\log(N)\geq\Omega(\log
N)$ and choose positive integers $(\beta_{i}\log(N))_{i\in[k]_{0}}$ with

$\sum_{i=0}^{k-1}\beta_{i}=\beta_{\text{\tt{tot}}}\quad\text{ and
}\quad\left|\beta_{i}\log(N)-\frac{\beta_{\text{\tt{tot}}}\log(N)p_{i}^{2}}{\phi_{\operatorname{\mathbf{p}}}(2)}\right|\leq
1.$

The numbers just constructed satisfy