# A central limit theorem for cycles of Mallows permutations

Jimmy He  Department of Mathematics, MIT, Cambridge, MA 02139<EMAIL_ADDRESS>
###### Abstract.

Fix $q\neq 1$, and sample $w\in S_{n}$ from the Mallows measure. We study the
distribution of $C_{i}(w)$, the number of $i$-cycles, as $n$ grows large. When
$q<1$, they are jointly Gaussian, and this more or less follows from known
ideas, but the regime $q>1$ behaves quite differently. In particular, we show
that the even cycles $C_{2i}(w)$ have a mean and variance of order $n$, and
jointly converge to Gaussian random variables, while the odd cycles
$C_{2i+1}(w)$ have a bounded mean and variance, and converge to
$C_{2i+1}(w^{even})$ or $C_{2i+1}(w^{odd})$ for some explicit random
permutations $w^{even}$ and $w^{odd}$, depending on whether $n$ is even or
odd. An extension to a larger class of functions is also given. The proof
utilizes a two-sided stationary regenerative process associated to Mallows
permutations constructed by Gnedin and Olshanski [11], extending the ideas of
Basu and Bhatnagar [4].

###### Key words and phrases:

Mallows permutations, regenerative processes, cycle structure

##  1\. Introduction

This paper studies the cycle structure for random permutations drawn from the
Mallows distribution with fixed parameter $q$. Let $C_{i}(w)$ denote the
number of cycles of length $i$ in $w$. For the uniform distribution, Goncharov
[12] showed that the $C_{i}(w)$ jointly converge to independent Poisson random
variables of mean $i^{-1}$. The macroscopic cycles are known to have Poisson-
Dirichlet statistics.

There has also been previous work on this problem for Mallows distributed
random permutations. Work of Gladkich and Peled [8] found the order of the
expected length of the cycle containing some given point when $q<1$. They also
showed that when $1>q\gg 1-\frac{1}{\sqrt{n}}$, the behaviour of the
macroscopic cycles is very similar to that of a uniform permutation,
exhibiting Poisson-Dirichlet statistics. There is also work of Mukherjee [18],
who studied the regime where $q\approx 1-\frac{\beta}{n}$, and showed that the
microscopic cycles converge to independent Poisson random variables, although
the means are different from the uniform distribution. In particular, his
result applies even if $q>1$, although it is still asymptotically very close
to $1$.

Our work complements these results by studying the case when $q$ is fixed.
Here, we expect to see behaviour very different from the uniform model, and
indeed our results show that the $C_{i}$ converge to normally distributed
random variables with a non-trivial covariance structure. We also study the
case when $q>1$, where more interesting behaviour occurs. Mallows permutations
with $q>1$ concentrate along the anti-diagonal, and so one expects almost no
cycles of odd length. Indeed, we show that the $C_{2i}(w)$ converge to
normally distributed random variables with a non-trivial correlation
structure, while the $C_{2i+1}(w)$ converge without normalization to limiting
random variables depending on whether $n$ is even or odd.

###  1.1. Main results

Fix some permutation $w\in S_{n}$. An _inversion_ of $w$ is a pair
$i,j\in\\{1,\dotsc,n\\}$, with $i<j$, such that $w(i)>w(j)$. The _length_ of
$w$, denoted $l(w)$, is the number of inversions in $w$. We let $C_{i}(w)$
denote the number of cycles of size $i$ in the cycle decomposition of $w$, and
let $C(w)$ denote the total number of cycles.

The _Mallows distribution_ $\mu_{q}$ is a one-parameter family of probability
measures on $S_{n}$, indexed by a real parameter $q\in(0,\infty)$. A random
permutation $w\in S_{n}$ is Mallows distributed if

$\operatorname{\mathbb{P}}(w=w_{0})=\frac{q^{l(w_{0})}}{Z_{n}(q)}$

where $Z_{n}(q)$ is a normalization constant, given explicitly as

$Z_{n}(q)=(1+q)(1+q+q^{2})\dotsm(1+q+\dotsc+q^{n-1}).$

When $q=1$, it reduces to the uniform distribution and when $q\to 0$ or
$q\to\infty$, it degenerates to a point mass at the identity or the
permutation sending $i$ to $n-i+1$ respectively.

Our first result gives the asymptotic means and covariances of the $C_{i}(w)$,
as well as their limiting distribution, when $q<1$.

######  Theorem 1.1.

Let $q\in(0,1)$, and let $w\in S_{n}$ be Mallows distributed with parameter
$q$. Let $C_{i}(w)$ denote the number of $i$-cycles in $w$, and let $C(w)$
denote the total number of cycles. Then there exist constants
$\alpha_{i},\beta_{ij}>0$, depending only on $q$, such that

$\operatorname{\mathbb{E}}(C_{i}(w))\sim\alpha_{i}n,\qquad\operatorname{Cov}(C_{i}(w),C_{j}(w))\sim\beta_{ij}n,$

and

$\left(\frac{C_{i}(w)-\alpha_{i}n}{\sqrt{n}}\right)_{i\geq
1}\xrightarrow{(d)}(Z_{i})_{i\geq 1},$

where the $Z_{i}$ are normal random variables of mean $0$ and covariance
structure $\beta_{ij}$.

In addition, if $\alpha=\sum\alpha_{i}$, there exists a constant $\beta>0$
such that

$\operatorname{\mathbb{E}}(C(w))\sim\alpha
n,\qquad\operatorname{Var}(C(w))\sim\beta n,$

and

$\frac{C(w)-\alpha n}{\sqrt{\beta n}}\xrightarrow{(d)}Z,$

where $Z\sim N(0,1)$.

The more interesting case is when $q>1$, which is covered by the next theorem.

######  Theorem 1.2.

Let $q\in(1,\infty)$, and let $w\in S_{n}$ be Mallows distributed with
parameter $q$. Let $C_{i}(w)$ denote the number of $i$-cycles in $w$, and let
$C(w)$ denote the total number of cycles. Then there exist constants
$\alpha^{\prime}_{i},\beta^{\prime}_{ij}>0$, depending only on $q$, such that

$E(C_{2i}(w))\sim\alpha^{\prime}_{i}n,\qquad\operatorname{Cov}(C_{2i}(w),C_{2j}(w))\sim\beta^{\prime}_{ij}n,$

and

$\left(\frac{C_{2i}(w)-\alpha^{\prime}_{i}n}{\sqrt{n}}\right)_{i\geq
1}\xrightarrow{(d)}(Z_{i})_{i\geq 1},$

where the $Z_{i}$ are normal random variables of mean $0$ and covariance
structure defined by $\beta_{ij}^{\prime}$.

There exist random permutations $w^{even}$ and $w^{odd}$ (of a random length)
such that the joint distribution of the odd cycles $(C_{2i+1}(w))_{i\geq 0}$
converges to $(C_{2i+1}(w^{even}))_{i\geq 0}$ or $(C_{2i+1}(w^{odd}))_{i\geq
0}$, depending on whether $n\to\infty$ is even or odd.

Finally, if $\alpha^{\prime}=\sum\alpha^{\prime}_{i}$, there exists a constant
$\beta^{\prime}>0$ such that

$\frac{C(w)-\alpha^{\prime}n}{\sqrt{\beta^{\prime}n}}\xrightarrow{(d)}Z,$

where $Z\sim N(0,1)$.

######  Remark 1.3.

The constants $\alpha_{i}$, $\beta_{ij}$, $\beta$, $\alpha_{i}^{\prime}$,
$\beta_{ij}^{\prime}$, and $\beta^{\prime}$ do not in general appear to have
nice formulas, but can be given implicitly as moments of the number of cycles
in a related random permutation, see Remark 5.1. For $q<1$, a characterization
was given in [22, Proposition 3.3].

However, $\alpha_{1}$ has the formula

$\alpha_{1}=\frac{1-q}{q}(q;q)_{\infty}\sum_{j=0}^{\infty}\frac{q^{(j+1)^{2}}}{(q;q)_{j}^{2}},$

where $(a;q)_{r}=\prod_{i=0}^{r-1}(1-aq^{i})$ denotes the $q$-Pochhammer
symbol. This series converges rapidly and allows reasonable asymptotic
estimates. This is stated as Proposition 5.3.

######  Remark 1.4.

In fact, Theorems 1.1 and 1.2 hold for a more general class of functions. We
make a few more comments on the details of this extension in Remark 5.2.

Let $w\in S_{n}$, and suppose that $w=w_{1}w_{2}$ where $w_{1}$ sends $[1,i]$
to itself and $[i+1,n]$ to itself. Say that a function
$f:\cup_{n}S_{n}\to\mathbf{R}^{d}$ is _additive_ if $f(w)=f(w_{1})+f(w_{2})$
for all $w=w_{1}w_{2}$ decomposing in this way, where $f(w)$ for $w$ a
permutation on an interval $[i,j]$ is defined by shifting down the permutation
to $[1,j-i+1]$. Then Theorem 1.1 holds for any (non-trivial) additive function
satisfying $|f(w)|\leq Cn^{k}$ for $w\in S_{n}$, where $C$ and $k$ are
constants.

Let $w\in S_{n}$, and suppose that $w=w_{1}w_{2}$, where $w_{1}$ sends
$[i,n-i]$ to itself and $w_{2}$ sends $[1,i]$ to $[n-i+1,n]$ and vice versa.
Say that $f:\cup_{n}S_{n}\to\mathbf{R}^{d}$ is _anti-additive_ if
$f(w)=f(w_{1})+f(w_{2})$ for all $w=w_{1}w_{2}$ decomposing in this way. Then
Theorem 1.2 holds for any (non-trivial) anti-additive function satisfying
$|f(w)|\leq Cn^{k}$ for $w\in S_{n}$, where $C$ and $k$ are constants.

Here, non-trivial means that $f$, when restricted to permutations of size $n$
for which no non-trivial decomposition of the form $w=w_{1}w_{2}$ exists, is
non-constant. This assumption is needed to ensure that the variances
$\beta_{ii}$ and $\beta_{ii}^{\prime}$ are non-zero. Almost any reasonable
function satisfies this, but note in particular that $f(w)=n$ the size of the
permutation does not satisfy this, and indeed Theorems 1.1 and 1.2 obviously
fail for this function.

Note that if $f(w)$ is either additive or anti-additive, then so is
$f(w^{-1})$. Thus, the theorems also apply to joint statistics for a Mallows
permutation and its inverse, giving another proof of Theorem 1.2 of [13].

The proof of Theorem 1.1 follows the ideas of Basu and Bhatnagar [4], who
studied the longest increasing subsequence for Mallows permutations. A strong
law of large numbers for the number of cycles was established by Pitman and
Tang [22], who studied a much more general class of examples. While this
result does not appear to have been written down in the literature, it follows
from known ideas. We give a proof of this theorem for completeness.

The proof of Theorem 1.2 is more involved and requires some new ideas. In
particular, while the Mallows distribution of parameter $q$ can be related to
the Mallows distribution of parameter $q^{-1}$ by reversing the permutation,
this significantly affects the cycle structure.

We use a two-sided stationary regenerative process constructed by Gnedin and
Olshanski [11], which we call the _stationary Mallows process_. We then study
a related regenerative process which we call the _symmetric process_ , where
the regeneration times are given as the times where both sides of the
stationary Mallows process simultaeneously regenerate. This corresponds to a
decomposition $w=v_{0}\dotsm v_{k}$, where $v_{0}$ sends some interval
$[s_{0}+1,n-s_{0}]$ to itself, and $v_{i}$ sends $[s_{i}+1,s_{i-1}]$ to
$[n-s_{i-1}+1,n-s_{i}]$ and vice versa. Moreover, the different $v_{i}$ will
be independent due to the regenerative structure of the stationary Mallows
process. Since the cycles are entirely restricted to some $v_{i}$, we can thus
obtain Theorem 1.2 using a central limit theorem for regenerative processes.

The biggest technical challenge in the proof is to obtain the necessary moment
estimates for the regeneration times in the symmetric process. This
corresponds to obtaining moment estimates for the simultaneous return times of
two independent copies of a Markov chain originally used in [4] to study the
regeneration times in the Mallows process.

######  Remark 1.5.

After the completion of this work, the author learned that Theorems 1.1 and
1.2 were also obtained independently by Müller and Verstraaten [19] using
similar methods.

###  1.2. Background

The works most closely related to ours is the recent development of a theory
of regenerative permutations and its application to the study of Mallows
permutations. Gnedin and Olshanski [10, 11] constructed infinite extensions of
Mallows measure to $\mathbf{N}$ and $\mathbf{Z}$. This was subsequently
generalized by Pitman and Tang [22], who also gave a very clear account of the
regenerative structure within these infinite permutations. This was in part
inspired by work of Basu and Bhatnagar [4], who applied these ideas to study
the longest increasing subsequence for Mallows permutations. Gladkich and
Peled [8] also used related ideas to study the cycle structure. These
applications all rely on taking $q<1$.

This work is in some sense a continuation of this body of work. We explain
what properties a permutation statistic needs to have to apply these methods
when $q<1$. We also extend the method to handle the case when $q>1$, although
the functions that this can be applied to are more limited, and we cannot for
example say anything about the longest increasing subsequence for Mallows
permutations when $q>1$.

The Mallows distribution was introduced by Mallows to study non-uniform ranked
data [15]. It is perhaps the most widely used non-uniform distribution on
permutations in applied statistics, see [17] or [24] for discussion of the
statistical uses for Mallows permutations. Thus, understanding the behaviour
of features of Mallows permutations is an important problem. They have also
seen applications to the study of one-dependent processes [14] and stable
matchings [3].

A growing body of work studies the behaviour of Mallows permutations as the
parameter $q$ varies. In general, it seems that for $q$ sufficiently close to
$1$, the model behaves very similarly to the uniform permutation, while for
$q$ far enough from $1$, different behaviour occurs. This has been observed
for the longest increasing subsequence [16, 5, 4].

One interesting feature of the Mallows model is that in many cases, there is
sharp phase transition between these two regimes. Specifically, this has been
observed for the expected length of cycles [8]. It would be interesting to see
if the fluctuations of the number of cycles also have a phase transition. Our
work suggests that this would be a transition from Poisson to Gaussian
fluctuations.

Finally, let us mention some other recent work on Mallows permutations. The
Mallows distribution appeared as the induced distribution on double cosets
coming from the uniform distribution on
$\operatorname{GL}_{n}(\mathbf{F}_{q})$ for the Bruhat decomposition [6].
Recent work of Pinsky [21, 20] studies pattern occurences in Mallows
permutations as well as the secretary problem when the arrivals are biased to
be a Mallows permutation. Finally, in [1], the height of trees constructed
from Mallows permutations was studied.

###  1.3. Organization

The paper is organized as follows. In Section 2, we recall some important
facts about regenerative and renewal processes. In Section 3, we introduce the
main tool, the Mallows process, which is an infinite regenerative process
closely related to Mallows permutations. In Section 4, we show that the
regeneration times of the symmetric process have finite moments, which allow
us to apply tools from renewal theory. In Section 5, we prove Theorems 1.1 and
1.2.

##  2\. Regenerative processes

In this section, we recall some key facts about regenerative processes,
including the renewal central limit theorem.

Recall that a (discrete time) regenerative process is a process
$X(t):\mathbf{N}\to X$ on $\mathbf{N}$ such that there exist (random) times
$T_{i}$ for $i\geq 1$ for which $\\{X(\sum_{i\leq j}T_{i}+t)\\}_{t\geq 0}$ is
equal in distribution to $\\{X(t)\\}_{t\geq 0}$ for any $j$, and independent
of the process before time $\sum_{i\leq j}T_{i}$. The times $\sum_{i\leq
j}T_{i}$ are called the regeneration times, and the process between
regeneration times, which we will denote $X_{i}$, are independent and
identically distributed (as random variables taking values in finite sequences
in $X$).

Actually, to handle the stationary Mallows process, we will need to consider a
slightly more general definition which allows the first regeneration time to
have a different distribution from the remaining ones. These are called
_delayed_ regenerative processes. In this case, we will let $T_{0}$ denote the
first $T_{i}$, and $X_{0}$ denote the first $X_{i}$, and the subsequent ones
we will labeled as usual. Thus, a non-delayed regenerative process simply
means that $T_{0}=0$ and $X_{0}$ is empty.

We let $N(t)$ be the largest $n$ such that $\sum_{i\leq n}T_{i}\leq t$. Let
$f:\cup X^{k}\to\mathbf{R}^{d}$, and consider the random sum
$\sum_{i=1}^{N(t)}f(X_{i})$. The following result of Smith establishes a
central limit theorem for this sum, given some mild moment assumptions
(actually the proof assumes $T_{0}=0$ but it is stated that the result holds
without this assumption, see [9] for example for the extension in the
univariate case).

######  Theorem 2.1 ([23, Theorem 10]).

Suppose that $\operatorname{\mathbb{E}}(T_{i})=\mu<\infty$ and
$\operatorname{\mathbb{E}}(T_{i}^{2})<\infty$, and that the vector $f(X_{i})$
has finite first and second moments for all $i$. Then

$\frac{\sum_{i=1}^{N(t)}f(X_{i})-\alpha
t}{(t/\mu)^{\frac{1}{2}}}\xrightarrow{(d)}Z,$

where $Z\sim N(0,\Sigma)$,
$\alpha_{i}=\operatorname{\mathbb{E}}(f(X_{1})_{i})/\mu$ and

$\Sigma_{ij}=\operatorname{Cov}\left(f(X_{1})_{i}-\frac{\operatorname{\mathbb{E}}(f(X_{1})_{i})T_{i}}{\mu},f(X_{1})_{j}-\frac{\operatorname{\mathbb{E}}(f(X_{1})_{j})T_{j}}{\mu}\right).$

######  Remark 2.2.

Theorem 2.1 was proved in much more generality in the original paper of Smith
[23], where the result was shown for continuous time. We restrict ourselves to
the case when the regeneration times are restricted to $\mathbf{N}$, and the
so-called cumulative process is a pure jump process with jumps only at the
regeneration times.

We also require the asymptotic convergence of the moments. This theorem seems
well-known, and in particular follows from Theorem 2.1 and the fact that the
mean and variances for each component converge [23, Theorem 8] (again, the
proof assumes $T_{0}=0$ but as long as $T_{0}$ has finite moments, this
assumption is not necessary).

######  Theorem 2.3 ([23]).

With the same setup as Theorem 2.1, we have

$\frac{1}{t}\operatorname{\mathbb{E}}\left(\sum_{i=1}^{N(t)}f(X_{i})\right)\to\alpha$

and

$\frac{1}{t}\operatorname{Cov}\left(\sum_{i=1}^{N(t)}f(X_{i})\right)\to\frac{1}{\mu}\Sigma$

as $t\to\infty$.

We will also need to ensure that no single $T_{i}$ can cause any issues. For
this, we require the following limit result for the length of the interval
containing $n$, which goes to the size-bias distribution, see for example [7,
Eq. 5.70].

######  Proposition 2.4.

Let $T^{(n)}$ be the length of the interval containing $n$. Then
$T^{(n)}\xrightarrow{(d)}T^{*}$ as $n\to\infty$, where $T^{*}$ has the size-
bias distribution with respect to the $T_{i}$. That is, $T^{*}$ has the unique
distribution such that
$\operatorname{\mathbb{E}}(f(T^{*}))=\operatorname{\mathbb{E}}(T_{1}f(T_{1}))$
for all $f$ where the expectations make sense.

##  3\. Mallows process

In this section, we recall the construction of the Mallows process on both
$\mathbf{N}$ and $\mathbf{Z}$, which is thus named because we want to view it
as a discrete time stochastic process. The analysis of Mallows permutations
when $q<1$ is fairly straightforward using the regenerative properties of this
process. The analysis when $q>1$ is more interesting, and requires the use of
the process on $\mathbf{Z}$, started at stationarity. We then study a related
regenerative process we call the symmetric process, and give some moment
estimates needed to apply the renewal theory arguments to obtain Theorem 1.2.

The Mallows process was defined by Gnedin and Olshanski [10], who later
extended the definition to a two-sided process [11]. A more general notion of
regenerative permutation on $\mathbf{N}$ or $\mathbf{Z}$ was introduced in
[22]. These ideas were first used by Basu and Bhatnagar [4] to study the
longest increasing subsequence for Mallows permutations (with related ideas
appearing in [8]), and then in [13] to study descents in $w$ and $w^{-1}$. The
basic properties of the Mallows process are reviewed here without proof. We
give references to places where more details can be found.

###  3.1. Mallows process

Figure 3.1. Mallows process $\widehat{w}$ on $\mathbf{N}$ is shown as black
dots. Red squares mark excursions. The $T_{i}$ are the lengths of the red
squares, and the $w_{i}$ are the permutations within each red square.

Fix $0<q<1$. The _Mallows process_ is a random permutation
$w:\mathbf{N}\to\mathbf{N}$ defined as follows. Set $\widehat{w}(1)=i$ with
probability $q^{i-1}(1-q)$ and given $\widehat{w}(1),\dotsc,\widehat{w}(i)$,
set
$\widehat{w}(i+1)=k\in\mathbf{N}\setminus\\{\widehat{w}(1),\dotsc,\widehat{w}(i)\\}$
with probability $q^{k^{\prime}-1}(1-q)$ where $k^{\prime}-1$ is the number of
elements in $\mathbf{N}\setminus\\{\widehat{w}(1),\dotsc,\widehat{w}(i)\\}$
less than $k$. This is almost surely a bijection.

Given any $n\in\mathbf{N}$, the relative order of
$\widehat{w}(1),\dotsc,\widehat{w}(n)$ as a random element in $S_{n}$ is
Mallows distributed, and more generally the same is true for the relative
order of $\widehat{w}(i)$ for $i\in[a,b]$. We will denote the permutation in
$S_{b-a+1}$ induced by this relative order $w^{a,b}$. Thus, it often suffices
to study the Mallows process, which has a regenerative structure that we now
describe.

Let $T_{1}$ be the first time $n$ that $\widehat{w}(i)\leq n$ for all $i\leq
n$. In other words, this is the first $n$ for which $w(1),\dotsc,w(n)$ defines
a permutation of $1,\dotsc,n$. Then the process
$(\widehat{w}(T_{1}+k)-T_{1})_{k\geq 1}$ is equal in distribution to
$(\widehat{w}(k))_{k\geq 1}$.

Similarly, let $T_{k}+\dots+T_{1}$ be the $k$th time that this occurs. Let
$w_{1}$ be the permutation induced by
$\widehat{w}(1),\dotsc,\widehat{w}(T_{1})$ and let $w_{k}$ be the permutation
induced by $\widehat{w}(T_{k-1}+1),\dotsc,\widehat{w}(T_{k})$ for $k\geq 1$.
Then it’s clear that the $T_{k}$ and the $w_{k}$ are independent and
identically distributed. Call the $w_{k}$ _excursions_ in the Mallows process
and $T_{k}$ their _sizes_. Moreover, the times $T_{k}$ are the renewal times
of a renewal process. See Figure 3.1 for an example of this process up until
$t=50$.

The cycles of $w$ must lie in the irreducible components. Thus we can study
$w^{1,n}$, which has the same distribution, and instead count cycles within
each $w_{i}$ contained in $[1,n]$. Standard renewal theory arguments will then
establish Theorem 1.1, as long as the moments of $T_{k}$ are finite. This is
the content of the next proposition.

######  Proposition 3.1 ([13, Proposition 3.4]).

We have $\operatorname{\mathbb{E}}(T_{i}^{k})<\infty$ for all $i>0$.

###  3.2. Stationary Mallows process

The stationary Mallows process should be thought of as the Mallows process
started from stationarity, in the sense that $\widehat{w}(i)-i$ is a
stationary process. It was first constructed in [11], although they did not
exploit the regenerative structure. Later, in [22], the fact that this process
can be viewed as the stationary version of the Mallows process was explained
and the usual renewal-theoretic consequences were given.

For example, stationary Mallows process can be obtained by running the Mallows
process for a long time, see [22, Lemma 3.1]. We do not give a formal
construction as it is quite a bit more involved than the Mallows process, but
merely take for granted the existence of a process $\widehat{w}$ with certain
desired properties. See [11] and [22, Section 3] for details and proofs.

Let $\widehat{w}$ denote the _stationary Mallows process_ , as defined in
[11]. This is a random bijection $\mathbf{Z}\to\mathbf{Z}$. This process again
has a regenerative structure. We let $T_{0}$ denote the length of $w_{0}$, the
irreducible permutation containing $0$, and we let $T_{i}$ for
$i\in\mathbf{Z}$ denote the lengths of the $i$th irreducible permutation
before or after $w_{0}$, denoted $w_{i}$. Then the $T_{i}$ and $w_{i}$ are
independent for different $i$, and for $i\neq 0$ they are identically
distributed according to the same distribution as for the Mallows process
described previously. We note that $T_{0}$ and $w_{0}$ do not have the same
distribution as the other $T_{i}$ and $w_{i}$. The size of the first excursion
$T_{0}$ has the size-biased distribution with respect to the distribution of
the other $T_{i}$, as is the case for any stationary renewal process. Thus,
Proposition 3.1 immediately extends to the stationary Mallows process.

######  Proposition 3.2.

Let the $T_{i}$ denote the sizes of the excursions in the stationary Mallows
process. Then $\operatorname{\mathbb{E}}(T_{i}^{k})<\infty$ for all
$i\in\mathbf{Z}$.

Again, $w^{a,b}\in S_{b-a+1}$ is Mallows distributed of parameter $q$. This
can be seen from the fact that this process is $q$-exchangeable (see comments
after Theorem 6.1 in [11] for example).

Finally, we remark that $-\widehat{w}(-i)$ has the same distribution as
$\widehat{w}$. Thus, the stationary Mallows process is also time-reversal
invariant.

###  3.3. The symmetric process

Figure 3.2. The reversed stationary Mallows process $\widehat{w}^{rev}$ is
shown as black dots. Here, we consider the odd case, which is centered at $0$,
marked by the dashed line. Red squares mark the excursions in the stationary
Mallows process $\widehat{w}$, with the green square denoting the excursion
containing $0$. The orange shaded square denotes the first regeneration in the
symmetric process, $S_{0}$ is the length of the orange shaded square, $v_{0}$
is the permutation contained in the orange shaded square. The blue shaded
squares, paired symmetrically, denote the subsequent regenerations in the
symmetric process, $S_{i}$ is the sum of the lengths of a symmetric pair of
blue shaded squares, and $v_{i}$ is the permutation contained in a symmetric
pair of blue shaded squares.

Note that all the processes we have defined are for $q<1$. In this section, we
define the symmetric process, which is essentially just a different
regenerative structure on $\widehat{w}$, which will be essential in studying
the cycle structure when $q>1$.

For a Mallows permutation $w$, the reversal permutation $w^{rev}(i)=w(n-i+1)$
is Mallows distributed with parameter $q^{-1}$. Thus, we would wish to study
the analogous Mallows process given by $\widehat{w}^{rev}=\widehat{w}(-i)$.
The relative order of $\widehat{w}^{rev}(i)$ for $a+1\leq i\leq b$ is Mallows
distributed in $S_{b-a}$ of parameter $q^{-1}$. However, it is no longer true
that $w_{i}$ is irreducible, and so it is no longer possible to study the
cycle structure using the same renewal structure. This is what motivates the
following construction. A related idea was proposed in [8].

We will need slightly different constructions depending on whether we wish to
study Mallows permutations for $n$ even or $n$ odd. We begin with $n$ odd. We
refer the reader to Figure 3.2 as a visual guide for the construction.

Let $T_{0}^{+}$ and $T_{0}^{-}$ be the length of $w_{0}$ to the right and left
of $0$ respectively, so $1+T_{0}^{+}+T_{0}^{-}=T_{0}$. In Figure 3.2, this is
the length of the green square to the left and right of $0$, so $T_{0}^{+}=3$
and $T_{0}^{-}=4$.

Let $k_{0}^{-}$ and $k_{0}^{+}$ be the first times that
$T_{0}^{+}+\sum_{i=1}^{k_{0}^{+}}T_{i}=T_{0}^{-}+\sum_{i=1}^{k_{0}^{-}}T_{-i}$.
In Figure 3.2, these are the number of red squares to the left and right of
the green square in the orange shaded square, so $k_{0}^{-}=2$ and
$k_{0}^{+}=1$.

Let $v_{0}$ be the permutation obtained by concatenating $w_{i}$ for
$-k_{0}^{-}\leq i\leq k_{0}^{+}$, and let $S_{0}$ denote its length. In Figure
3.2, $v_{0}$ is the permutation contained in the orange shaded square, and
$S_{0}$ is the length of the orange shaded square, so $S_{0}=15$. It can be
seen that $v_{0}$ is simply the first time that $\widehat{w}^{rev}$ sends
$[-i,i]$ to itself.

Now given $k_{i}^{-}$, $k_{i}^{+}$, inductively define $k_{i+1}^{-}$ and
$k_{i+1}^{+}$ as the smallest integers such that
$\sum_{i=k_{i}^{-}+1}^{k^{-}_{i+1}}T_{-i}=\sum_{i=k_{i}^{+}+1}^{k_{i+1}^{+}}T_{i}$,
and let $S_{i+1}=2\sum_{i=k_{i}^{-}+1}^{k^{-}_{i+1}}T_{-i}$. In other words,
we are waiting for the first time after $S_{i}$ that $\widehat{w}^{rev}$ sends
the interval $[S_{i}/2,S_{i+1}/2]$ to $-[S_{i}/2,S_{i+1}/2]$ and vice versa.
In Figure 3.2, note that the blue shaded squares are paired on the left and
right, each having the same size. The $k_{i}^{-}$ and $k_{i}^{+}$ are the
number of red squares in the left and right blue shaded squares, counting out
from the middle, so $k_{1}^{-}=1$, $k_{1}^{+}=2$, $k_{2}^{-}=5$, and
$k_{2}^{+}=2$. The $S_{i}$ are the sum of the lengths of the corresponding
blue shaded squares, so $S_{1}=12$ and $S_{2}=22$

Let $v_{i}$ denote the permutation of
$-[S_{i-1}/2,S_{i}/2]\cup[S_{i-1}/2,S_{i}/2]$ defined by restricting
$\widehat{w}^{rev}$ on this interval. For $i=1$, we instead use
$-[(S_{0}-1)/2,S_{1}/2]\cup[(S_{0}-1)/2,S_{1}/2]$ as $S_{0}$ is always odd. In
Figure 3.2, the $v_{i}$ correspond to the permutations contained in a
symmetric pair of blue shaded squares, counting out from the middle.

The utility of this construction is that the cycle structure of $v^{-n,n}$,
which we will use to denote the relative order of $\widehat{w}^{rev}(i)$ for
$i\in[-n,n]$, can be obtained from the cycle structures of the $v_{i}$,
exactly analogous to how for $q<1$ they could be obtained from the $w_{i}$.

The following proposition formalizes the fact that the $v_{i}$ and $S_{i}$
form a regenerative structure.

######  Proposition 3.3.

The process $(S_{i},v_{i})$ is regenerative in the following sense. The
$(S_{i},v_{i})$ are independent, and except for $i=0$, the $S_{i}$ are
identically distributed, and the $v_{i}$, relabeled so they form a permutation
of $\\{1,\dotsc,S_{i}\\}$, are also identically distributed.

###### Proof.

We proceed by induction, showing each $(S_{i},v_{i})$ is independent of all
previous $(S_{j},v_{j})$ for $j<i$. The base case is trivial. Given that the
$(S_{i},v_{i})$ are independent for $i\leq k$, we note that $S_{k+1}$ and
$v_{k+1}$ are functions of the renewed process, and so are independent of the
$(S_{i},v_{i})$ for $i\leq k$. Finally, since $S_{i}$ and $v_{i}$ are the same
functions applied to the renewed process, they have the same distribution. ∎

Figure 3.3. The reversed stationary Mallows process $\widehat{w}^{rev}$ is
shown as black dots. Here, we consider the even case, which is centered at
$1/2$, marked by the dashed line. Red squares mark the excursions in the
stationary Mallows process $\widehat{w}$, with the green square denoting the
(possibly empty) excursion containing $1/2$. The orange shaded square denotes
the first regeneration in the symmetric process, $S_{0}$ is the length of the
orange shaded square, $v_{0}$ is the permutation contained in the orange
shaded square. The blue shaded squares, paired symmetrically, denote the
subsequent regenerations in the symmetric process, $S_{i}$ is the sum of the
lengths of a symmetric pair of blue shaded squares, and $v_{i}$ is the
permutation contained in a symmetric pair of blue shaded squares.

When $n$ is even, we slightly modify the construction above. Figure 3.3 gives
a visual guide to the construction, which is almost identical except that the
line of symmetry is at $1/2$ rather than $0$. Since the construction is
extremely similar, we only explain the differences in detail.

We wait until the first time that $\widehat{w}^{rev}$ sends $[-n+1,n]$ to
itself, and we let $v_{0}$ be the permutation of this interval that this
induces. However, if $\widehat{w}^{rev}$ has a renewal at $1$ (in other words,
if $\widehat{w}$ had a renewal at $0$), we simply take $v_{0}$ to be the empty
permutation. Let $S_{0}$ denote the size of $v_{0}$. Essentially, the
difference is that we center the reversal around $1/2$ rather than $0$. See
Figure 3.3, where the dashed line is now at $1/2$ rather than at $0$.

We then define $S_{i}$ in exactly the same way, except we consider when
$\widehat{w}^{rev}$ sends the interval $[a,b]$ to $-[a-1,b-1]$ rather than
$-[a,b]$, again to account for the fact that everything is centered around
$1/2$. The following proposition states that this process also has a
regenerative structure, and has the same proof as Proposition 3.3. We will use
the same notation for both these constructions, since they are essentially the
same. In fact, the distributions of the $S_{i}$ and $v_{i}$ are identical,
except for when $i=0$, since they depend on the process after a renewal.

######  Proposition 3.4.

The process $(S_{i},v_{i})$ is regenerative in the following sense. The
$(S_{i},v_{i})$ are independent, and except for $i=0$, the $S_{i}$ are
identically distributed, and the $v_{i}$, relabeled so they form a permutation
of $\\{1,\dotsc,S_{i}\\}$, are also identically distributed.

##  4\. Moment estimates for the symmetric process

To apply the necessary renewal theory arguments, we need to obtain moment
estimates for the $S_{i}$. We first recall a Markovian representation of the
$T_{i}$ used in [4] to prove that they have finite first and second moments,
and we refer the reader there for proofs of any unproven claims in this
section.

The regeneration times $T_{i}$ can be viewed as the return times of a Markov
chain. Specifically, consider the process

$M_{n}=\max_{1\leq i\leq n}w(i)-n$

on $\mathbf{N}$. This is a positive recurrent Markov process with stationary
distribution

$\mu_{j}=\frac{1}{\prod_{k=1}^{\infty}(1-q^{k})}\frac{q^{j}}{\prod_{k=1}^{j}(1-q^{k})}.$

The Markov process can be described in terms of the geometric random variables
defining the Mallows process. Specifically, the walk can be described as
moving from $M_{n}$ to $M_{n+1}=\max(M_{n},Z_{n})-1$ where the $Z_{n}$ are
independent geometric random variables. Let $R_{i}$ denote the hitting time of
$i$ and let $R_{i}^{+}$ denote the return time at $i$. Then if the chain is
started from $0$, $R_{0}^{+}$ is distributed as the size of an excursion in
the Mallows process. This Markov chain was used in [4] to show that the
$T_{i}$ have finite first and second moments, and will also be essential to
show that the $S_{i}$ have finite moments. A related Markov chain was
considered in [8].

We now consider the regeneration times $S_{i}$. The regeneration times $S_{i}$
ask when two independent copies of the Markov chain starting from $(0,0)$
return to $(0,0)$ simultaneously, since both sides of the stationary Mallows
process behave like the one-sided Mallows process. When $n$ is odd, for
$S_{0}$, we can write it as $T_{0}+S_{0}^{\prime}$, where $T_{0}$ is the
length of the excursion containing $0$ and $S_{0}^{\prime}$ asks when two
independent copies of the Markov chain, started from a state depending on when
the excursion $w_{0}$ starts and ends, hits $(0,0)$, and similarly for $n$
even except we consider the excursion containing $1/2$ (meaning it either
contains both $0$ and $1$, or is defined to be empty if this isn’t possible).

More formally, consider the Markov chain $(M_{n},M_{n}^{\prime})$ consisting
of two independent copies of the above chain. We let $R_{(i,j)}$ denote the
hitting time of $(i,j)$ and $R_{(i,j)}^{+}$ denote the return time at $(i,j)$.
The next proposition shows that the $S_{i}$ are essentially given by these
return times.

######  Proposition 4.1.

For $i>0$, $S_{i}$ is equal to $2R_{(0,0)}^{+}$ in distribution, and $S_{0}$
is equal in distribution to $2R_{(0,0)}$ where the Markov chain is started at
some random location.

###### Proof.

First, suppose that $i>0$. Since $-\widehat{w}(-i)$ is equal in distribution
to $\widehat{w}(i)$, the stationary Mallows process to the left of a renewal
is equal in distribution to the usual one-sided Mallows process after a shift
and reflections across the $x$ and $y$ axes. Moreover, it’s independent of the
process to the right of a renewal that occurs after the first one. Thus,
$S_{i}$ simply asks for the first time that $\sum T_{i}=\sum T_{i}^{\prime}$,
where $T_{i}$ and $T_{i}^{\prime}$ are the regeneration times in two
independent copies of the one-sided Mallows process. This is exactly
$R_{(0,0)}$, except we multiply by a factor of $2$ due to the definition of
$S_{i}$.

Now take $i=0$, and first, suppose $n$ is odd. When $i=0$, we can write
$S_{0}=T_{0}+S_{0}^{\prime}$, where $T_{0}$ is the length of the excursion
$w_{0}$ containing $0$. But then $S_{0}^{\prime}$ is simply $2R_{(0,0)}$ for
the Markov chain started at a random point given by taking the shorter side of
the excursion $w_{0}$, and running the component corresponding to that side
until it reaches the same length.

When $n$ is even, the same proof applies, except that we consider $w_{0}$ the
excursion that contains both $0$ and $1$, or is empty if $0$ and $1$ are
contained in distinct excursions. ∎

We also define $B_{i}$ to be the set of points $(j,k)$ where $\max(j,k)=i$,
and we let $R_{B_{i}}$ denote the hitting time of $B_{i}$. The proof that
these times have finite moments then proceeds similarly to the analogous proof
for the $T_{i}$, given in [4, 13].

We will let $\operatorname{\mathbb{E}}_{x}$, $\operatorname{\mathbb{P}}_{x}$,
and $\operatorname{\mathbb{E}}_{\mu\times\mu}$,
$\operatorname{\mathbb{P}}_{\mu\times\mu}$ denote the expectation and
probability measure for the Markov chain started from $x\in\mathbf{N}^{2}$ and
from stationarity respectively.

######  Lemma 4.2.

For any point $x\in B_{i+1}$ and any point $y\in B_{i}$, we have
$\operatorname{\mathbb{E}}_{x}(R_{B_{i}}^{k})\leq\operatorname{\mathbb{E}}_{y}(R_{B_{i-1}}^{k})$.

###### Proof.

We couple two copies of the chain, started from $x$ and $y$, using the same
underlying geometric random variables. Recall that we sample a step of the
Markov chain by sampling geometric random variables $Z$ and $Z^{\prime}$, and
setting
$(M_{n+1},M_{n+1}^{\prime})=(\max(M_{n},Z)-1,\max(M_{n}^{\prime},Z^{\prime})-1)$.
Thus, each component can decrease by at most $1$ in a single step. The sets
$B_{i}$ are constructed such that the Markov chain, if it starts on $B_{k}$
for any $k>i$, must hit $B_{i}$ before $B_{i-1}$. Thus, if the two copies ever
collide before hitting $B_{i-1}$, they must both hit $B_{i}$ before $B_{i-1}$.

Consider the next step, generated by geometric random variables $Z$ and
$Z^{\prime}$. First, note that if both $Z\geq i+1$ and $Z^{\prime}\geq i+1$,
then both chains will couple, and so $B_{i}$ must be hit by both chains before
$B_{i-1}$ can be hit.

If $Z\geq i+1$ but $Z^{\prime}\leq i$, then the two copies of the chain couple
in the first coordinate, and the second coordinates are both at most $i$. Then
either in the subsequent steps, the $Z^{\prime}$ are all at most $i$, in which
case the two chains will eventually hit $B_{i}$ before $B_{i-1}$, or the
$Z^{\prime}$ will eventually be at least $i+1$, in which case both chains will
couple. The case when $Z\leq i$ and $Z^{\prime}\geq i+1$ is similar.

On the other hand, if both $Z\leq i$ and $Z^{\prime}\leq i$, then the two
chains will hit $B_{i}$ and $B_{i-1}$ respectively in the first step, and so
the hitting times are equal. But then we’ve shown that $R_{B_{i}}\leq
R_{B_{i-1}}$ under this coupling, and the result follows. ∎

######  Lemma 4.3.

For all $k$, $\operatorname{\mathbb{E}}_{(0,0)}((R_{(0,0)}^{+})^{k})<\infty$.

###### Proof.

We proceed by induction on $k$. The case $k=1$ follows from the existence of
the stationary distribution. We now assume that
$\operatorname{\mathbb{E}}_{(0,0)}((R_{(0,0)}^{+})^{k})<\infty$. We first show
that $\operatorname{\mathbb{E}}_{\mu\times\mu}(R_{(0,0)}^{k})<\infty$.

To see this, note that

$\operatorname{\mathbb{E}}_{\mu\times\mu}(R_{(0,0)}^{k})=\sum_{i,j}\mu_{i}\mu_{j}\left(\sum_{l=1}^{\max(i,j)}T_{l\to
l-1}\right)^{k}\leq\sum_{i,j}\mu_{i}\mu_{j}\max(i,j)^{k}\max_{x\in
B_{1}}\operatorname{\mathbb{E}}_{x}(R_{(0,0)}^{k})^{k},$

where $T_{l\to l-1}$ denotes the time it takes to reach $B_{l-1}$ starting
from the first time we hit $B_{l}$, and we expand into $\max(i,j)^{k}$ terms
and use Lemma 4.2 to replace $\operatorname{\mathbb{E}}(T_{l\to l-1}^{l})$
with $\max_{x\in B_{1}}\operatorname{\mathbb{E}}_{x}(R_{(0,0)}^{k})$, which
will dominate $T_{1\to 0}$ no matter the distribution of the initial state.
But since $\mu_{i}\mu_{j}\leq Aq^{i+j}$ for some $A>0$, and since
$\operatorname{\mathbb{E}}_{x}(R_{(0,0)}^{k})<\infty$ by the inductive
hypothesis (since we can always move from $(0,0)$ to $x$ in the first step),
we’ve shown $\operatorname{\mathbb{E}}_{\mu\times\mu}(R_{(0,0)}^{k})$ is
finite.

Then Lemma 2.23 of [2] states

$\operatorname{\mathbb{P}}_{\mu\times\mu}(R_{(0,0)}=t-1)=\mu_{0}^{2}\operatorname{\mathbb{P}}_{(0,0)}(R_{(0,0)}^{+}\geq
t)$

which gives

$\operatorname{\mathbb{E}}_{(0,0)}(P_{k+1}(R_{(0,0)}^{+}))=\frac{\operatorname{\mathbb{E}}_{\mu\times\mu}((R_{(0,0)}+1)^{k})}{\mu_{0}^{2}}$

after multiplying by $t^{k}$ and summing over $t$, where

$P_{k+1}(m)=\sum_{i=1}^{m}i^{k}$

are the Faulhaber polynomials of degree $k+1$. This implies that
$\operatorname{\mathbb{E}}_{(0,0)}((R_{(0,0)}^{+})^{k+1})<\infty$ since all
other expressions in the equation are finite by the inductive hypothesis. ∎

######  Proposition 4.4.

For both $n$ even and $n$ odd, we have
$\operatorname{\mathbb{E}}(S_{i}^{k})<\infty$ for all $i$ and $k$.

###### Proof.

When $i>0$, this is immediate by Lemma 4.3 since $S_{i}$ is equal in
distribution to $2R_{(0,0)}^{+}$ by Proposition 4.1.

For $i=0$, we note that $S_{0}$ is equal in distribution to $2R_{(0,0)}^{+}$,
but started from a random state given by running one component of the Markov
chain for a random time $T$ and conditioning on the second component being
$0$. We can bound the return time to $0$ starting from the random state given
by running the chain until time $T$ by $R_{1}+\dotsc+R_{T+1}$, where $R_{i}$
is $i$th return time to $0$. The $k$th moment of this is bounded by
$\operatorname{\mathbb{E}}((T+1)^{k})\operatorname{\mathbb{E}}(R_{1}^{k})^{k}$
which is finite since
$\operatorname{\mathbb{E}}(R_{1}^{k})\leq\operatorname{\mathbb{E}}((R_{(0,0)}^{+})^{k})$
and $T$ is bounded by the length of the excursion containing $0$, which has
the size-bias distribution of the excursion lengths and so has finite moments.
Finally, since the two components are independent, we can condition on the
second component being $0$, which has positive probability. ∎

##  5\. Proofs of main theorems

###  5.1. Proofs of Theorems 1.1 and 1.2

With the regenerative structure given by the Mallows process and the moment
estimates given by Proposition 3.1, Theorem 1.1 follows immediately from
Theorems 2.1 and 2.3.

###### Proof of Theorem 1.1.

We note that $C_{i}(w)$, the number of cycles, is additive in the sense that
$C_{i}(w)=C_{i}(w_{1})+C_{i}(w_{2})$ if $w=w_{1}w_{2}$ and $w_{1},w_{2}$ send
disjoint intervals to themselves. Thus, if we identify the random Mallows
permutation $w\in S_{n}$ with the relative order of $\widehat{w}(i)$ for
$i\leq n$, we obtain

$C_{i}(w)=\sum_{j=1}^{N(n)}C_{i}(w_{j})+C_{i}(w^{\prime}),$

where $w_{j}$ are the excursions in the Mallows process $\widehat{w}$ that end
before time $n$, and $w^{\prime}$ is the relative order of $\widehat{w}(j)$
for $j$ after the end of the last excursion.

Now we note that $\frac{C_{i}(w^{\prime})}{\sqrt{n}}\to 0$ almost surely, as
$C_{i}(w^{\prime})\leq T^{(n)}\xrightarrow{(d)}T^{*}$ by Proposition 2.4,
where $T^{(n)}$ is the size of the excursion containing $n$ and $T^{*}$ has
the size-bias distribution with respect to the $T_{i}$. Since
$C_{i}(w_{j})\leq T_{j}$, all moments exist for the $C_{i}(w_{j})$ by
Proposition 3.1. Thus, Theorem 2.1 gives the joint convergence in distribution
for any finite collection of the $C_{i}$, and thus also the convergence in
distribution for the entire vector.

The mean and covariance asymptotics follow from Theorem 2.3. We note that
$\beta_{ii}>0$ for all $i$, because we can condition on $T_{1}=k$ for some
large $k$ (which occurs with positive probability), and $C_{i}$ will not be
constant on the irreducible permutations in $S_{k}$. Finally, the statement
about $C(w)$ follows from the exact same argument, applied to $C$ rather than
$C_{i}$. ∎

The proof of Theorem 1.2 is similar to that of Theorem 1.1, except that we
work with the symmetric process rather than the Mallows process.

###### Proof of Theorem 1.2.

We note that $C_{i}(w)$, is anti-additive in the sense that
$C_{i}(w)=C_{i}(w_{1})+C_{i}(w_{2})$ if $w=w_{1}w_{2}$ and for some $k$,
$w_{1}$ sends $[k+1,n-k]$ to itself while $w_{2}$ sends $[1,k]$ to $[n-k+1,n]$
and vice versa.

We first consider the case when $n$ is odd. If we identify the random Mallows
permutation $w\in S_{n}$ with the relative order of $\widehat{w}^{rev}(k)$ for
$k\in[-(n-1)/2,(n-1)/2]$, we obtain

$C_{2i}(w)=\sum_{j=0}^{N(n)}C_{2i}(v_{j})+C_{2i}(v^{\prime}),$

where $N(n)$ is the largest $t$ for which $\sum_{j\leq t}S_{j}\leq n$, $v_{j}$
are the excursions in the symmetric process that end before time $n$, and
$v^{\prime}$ is the relative order of $\widehat{w}^{rev}(k)$ for
$|k|>\sum_{j=0}^{N(n)}S_{j}/2$. When $n$ is even, we do essentially the same
thing, except we will work on the interval $[-n/2+1,n/2]$ instead.

But now, we note that $\frac{C_{2i}(v^{\prime})}{\sqrt{n}}\to 0$ almost surely
as $C_{2i}(v^{\prime})\leq S^{(n)}\xrightarrow{(d)}S^{*}$ by Proposition 2.4
(where $S^{(n)}$ is the size of the $v_{i}$ containing $n/2$ or $(n-1)/2$, and
$S^{*}$ has the size-bias distribution with respect to the $S_{i}$), and
$C_{2i}(v_{j})\leq S_{j}$ so all moments exist for the $C_{2i}(v_{j})$ by
Proposition 4.4, and so Theorem 2.1 gives the joint convergence in
distribution for any finite collection of the $C_{2i}(w)$, and thus also the
convergence in distribution for the entire vector.

The mean and covariance asymptotics follow from Theorem 2.3. Again,
$\beta_{ii}>0$ because $C_{2i}$ will not be constant on the permutations in
$S_{2k}$ sending $[1,k]$ to $[k+1,2k]$ and vice versa for large enough $k$.
The statement on $C(w)$ follows from the exact same arguments applied to $C$
rather than $C_{2i}$.

Finally, since for all odd $i$, $C_{i}(v_{j})=0$ for all $j>0$ and
$C_{i}(v^{\prime})=0$, we have $C_{i}(w)=C_{i}(v_{0})$ as long as $v_{0}$ lies
in the interval $[-(n-1)/2,(n-1)/2]$ (or $[-n/2+1,n/2]$ if $n$ is even). But
the probability of this event goes to $1$ as $n\to\infty$, and so the
$C_{i}(w)$ will converge almost surely to $C_{i}(v_{0})$ for $i$ odd. Then
$w^{odd}$ and $w^{even}$ can be taken to be $v_{0}$ under the odd and even
constructions, which were used depending on whether $n$ was odd or even. ∎

######  Remark 5.1.

From the proof, it’s clear that the constants $\alpha_{i}$, $\beta_{ij}$, and
$\beta$, and similarly the $\alpha_{i}^{\prime}$, $\beta_{ij}^{\prime}$, and
$\beta^{\prime}$, are simply what is given by Theorem 2.3 applied to either
the Mallows process or the symmetric process. For convenience, we give the
explicit expressions. Let $\mu=\operatorname{\mathbb{E}}(T_{1})$ and
$\mu^{\prime}=\operatorname{\mathbb{E}}(S_{1})$. Then we have

$\displaystyle\alpha_{i}$
$\displaystyle=\frac{1}{\mu}\operatorname{\mathbb{E}}(C_{i}(w_{1})),$
$\displaystyle\beta_{ij}$
$\displaystyle=\frac{1}{\mu}\operatorname{Cov}\left(C_{i}(w_{1})-\frac{\operatorname{\mathbb{E}}(C_{i}(w_{1}))T_{1}}{\mu},C_{j}(w_{1})-\frac{\operatorname{\mathbb{E}}(C_{j}(w_{1}))T_{1}}{\mu}\right),$
$\displaystyle\beta$
$\displaystyle=\frac{1}{\mu}\operatorname{Var}\left(C(w_{1})-\frac{\operatorname{\mathbb{E}}(C(w_{1}))T_{1}}{\mu}\right),$

and

$\displaystyle\alpha_{i}^{\prime}$
$\displaystyle=\frac{1}{\mu^{\prime}}\operatorname{\mathbb{E}}(C_{2i}(v_{1})),$
$\displaystyle\beta_{ij}^{\prime}$
$\displaystyle=\frac{1}{\mu^{\prime}}\operatorname{Cov}\left(C_{2i}(v_{1})-\frac{\operatorname{\mathbb{E}}(C_{2i}(v_{1}))S_{1}}{\mu^{\prime}},C_{2j}(v_{1})-\frac{\operatorname{\mathbb{E}}(C_{2j}(v_{1}))S_{1}}{\mu^{\prime}}\right),$
$\displaystyle\beta^{\prime}$
$\displaystyle=\frac{1}{\mu^{\prime}}\operatorname{Var}\left(C(v_{1})-\frac{\operatorname{\mathbb{E}}(C(v_{1}))S_{1}}{\mu^{\prime}}\right).$

######  Remark 5.2.

Examining the proofs of Theorem 1.1, we see that the only properties of the
functions $C_{i}$ we use are that they are additive, in the sense that
$C_{i}(w)=\sum C_{i}(w_{j})+C_{i}(w^{\prime})$, that we can control the
moments of $C_{i}(w_{j})$, and that the variances
$\operatorname{Var}\left(C_{i}(w_{1})-\frac{\operatorname{\mathbb{E}}(C_{i}(w_{1}))T_{1}}{\mu}\right)$
are non-zero.

If $f$ is assumed to be additive, then the first property holds. If for $w\in
S_{n}$, $|f(w)|\leq Cn^{k}$ for constants $C$ and $k$, then $|f(w_{i})|\leq
CT_{i}^{k}$ and since all moments exist for the $T_{i}$, the second property
holds. To ensure that the variance is non-zero, it suffices to assume that
there exists some $k$ such that conditional on $T_{1}=k$, $f(w_{1})$ is non-
constant, and this is what we mean be a non-trivial function. Essentially,
there must be some $k$ for which $f$ is not constant on the irreducible
permutations in $S_{k}$. With these assumptions, an analogue of Theorem 1.1
then holds with the exact same proof.

A similar explanation explains why anti-additivity and the bound $|f(w)|\leq
Cn^{k}$ for $w\in S_{n}$ along with the assumption that there is some $k$ for
which $f(v_{1})$ conditional on $S_{1}=k$ is non-constant is enough to show an
analogue of Theorem 1.2.

###  5.2. Aymptotics for fixed points

We can compute the asymptotics for the number of fixed points when $q<1$ by
computing $\alpha_{1}$.

######  Proposition 5.3.

Let $q<1$ and let $w\in S_{n}$ be Mallows distributed. We have

$\alpha_{1}=\lim_{n\to\infty}n^{-1}\operatorname{\mathbb{E}}(C_{1}(w))=\frac{1-q}{q}(q;q)_{\infty}\sum_{j=0}^{\infty}\frac{q^{(j+1)^{2}}}{(q;q)_{j}^{2}}.$

###### Proof.

Since $w\in S_{n}$ and $w^{1,n}$ agree on all but the last excursion, which
has finite mean, we have that $\alpha_{1}$ can be computed as the probability
that $\widehat{w}(i)=i$ in the stationary Mallows process. The formula then
follows from a special case of Theorem 5.1 in [11], when in their notation,
$d=0$. ∎

######  Remark 5.4.

Proposition 5.3 can also be proven directly from the finite model, without
using the Mallows process. This involves computing
$\operatorname{\mathbb{P}}(w(i)=i)$ for all $i$, which has a messy but
explicit formula, and then computing
$n^{-1}\sum_{i}\operatorname{\mathbb{P}}(w(i)=i)$, which actually simplifies
the sums somewhat.

In fact, one can obtain formulas for all the $\alpha_{i}$, but the expressions
quickly become much more complicated, and do not appear useful for further
analysis. We thus do not attempt to write down formulas for the other
$\alpha_{i}$.

## Acknowledgment

The author wishes to thank Persi Diaconis for bringing this problem to his
attention.

## References

  * [1] L. Addario-Berry and B. Corsini.  The height of Mallows trees.  Ann. Probab., 49(5):2220–2271, 2021.
  * [2] D. Aldous and J. A. Fill.  Reversible Markov chains and random walks on graphs, 2002.  Unfinished monograph, recompiled 2014, available at http://www.stat.berkeley.edu/~aldous/RWG/book.html.
  * [3] O. Angel, A. E. Holroyd, T. Hutchcroft, and A. Levy.  Mallows permutations as stable matchings.  Canad. J. Math., page 1–25, 2020.
  * [4] R. Basu and N. Bhatnagar.  Limit theorems for longest monotone subsequences in random Mallows permutations.  Ann. Inst. Henri Poincaré Probab. Stat., 53(4):1934–1951, 2017\.
  * [5] N. Bhatnagar and R. Peled.  Lengths of monotone subsequences in a Mallows permutation.  Probab. Theory Related Fields, 161(3-4):719–780, 2015.
  * [6] P. Diaconis and M. Simper.  Statistical enumeration of groups by double cosets.  Journal of Algebra, 2021.
  * [7] R. G. Gallager.  Stochastic processes: Theory for applications.  Cambridge University Press, Cambridge, 2013.
  * [8] A. Gladkich and R. Peled.  On the cycle structure of Mallows permutations.  Ann. Probab., 46(2):1114–1169, 2018.
  * [9] P. W. Glynn and W. Whitt.  Necessary conditions in limit theorems for cumulative processes.  Stochastic Process. Appl., 98(2):199–209, 2002.
  * [10] A. Gnedin and G. Olshanski.  $q$-exchangeability via quasi-invariance.  Ann. Probab., 38(6):2103–2135, 2010.
  * [11] A. Gnedin and G. Olshanski.  The two-sided infinite extension of the Mallows model for random permutations.  Adv. in Appl. Math., 48(5):615–639, 2012.
  * [12] V. Gontcharoff.  Sur la distribution des cycles dans les permutations.  C. R. (Doklady) Acad. Sci. URSS (N.S.), 35:267–269, 1942.
  * [13] J. He.  A central limit theorem for descents of a Mallows permutation and its inverse, 2021, 2005.09802.
  * [14] A. E. Holroyd, T. Hutchcroft, and A. Levy.  Mallows permutations and finite dependence.  Ann. Probab., 48(1):343–379, 2020.
  * [15] C. L. Mallows.  Non-null ranking models. I.  Biometrika, 44:114–130, 1957.
  * [16] C. Mueller and S. Starr.  The length of the longest increasing subsequence of a random Mallows permutation.  J. Theoret. Probab., 26(2):514–540, 2013.
  * [17] S. Mukherjee.  Estimation in exponential families on permutations.  Ann. Statist., 44(2):853–875, 2016.
  * [18] S. Mukherjee.  Fixed points and cycle structure of random permutations.  Electron. J. Probab., 21:Paper No. 40, 18, 2016.
  * [19] T. Müller and T. Verstraaten.  Cycles in Mallows random permutations, 2022, 2201.11610.
  * [20] R. G. Pinsky.  Clustering of consecutive numbers in permutations under Mallows distributions and super-clustering under general $p$-shifted distributions, 2020, 2008.07215.
  * [21] R. G. Pinsky.  Permutations avoiding a pattern of length three under Mallows distributions.  Random Structures Algorithms, 58(4):676–690, 2021.
  * [22] J. Pitman and W. Tang.  Regenerative random permutations of integers.  Ann. Probab., 47(3):1378–1416, 2019.
  * [23] W. L. Smith.  Regenerative stochastic processes.  Proc. Roy. Soc. London Ser. A, 232:6–31, 1955.
  * [24] W. Tang.  Mallows ranking models: maximum likelihood estimate and regeneration.  In K. Chaudhuri and R. Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 6125–6134, Long Beach, California, USA, 09–15 Jun 2019. PMLR.


# COVID-19 Fake News Detection Using Bidirectional Encoder Representations
from Transformers Based Models

Yuxiang Wang, Yongheng Zhang111The first two authors have equal contribution.,
Xuebo Li, Xinyao Yu222The last two authors have equal contribution.
Whiting School of Engineering, Johns Hopkins Unversity
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Nowadays, the development of social media allows people to access the latest
news easily. During the COVID-19 pandemic, it is important for people to
access the news so that they can take corresponding protective measures.
However, the fake news is flooding and is a serious issue especially under the
global pandemic. The misleading fake news can cause significant loss in terms
of the individuals and the society. COVID-19 fake news detection has become a
novel and important task in the NLP field. However, fake news always contain
the correct portion and the incorrect portion. This fact increases the
difficulty of the classification task. In this paper, we fine tune the pre-
trained Bidirectional Encoder Representations from Transformers (BERT) model
as our base model. We add BiLSTM layers and CNN layers on the top of the
finetuned BERT model with frozen parameters or not frozen parameters methods
respectively. The model performance evaluation results showcase that our best
model (BERT finetuned model with frozen parameters plus BiLSTM layers)
achieves state-of-the-art results towards COVID-19 fake news detection task.
We also explore keywords evaluation methods using our best model and evaluate
the model performance after removing keywords.

#### Keywords:

COVID-19 Fake news, BERT, Finetune, BiLSTM, CNN

##  1 Introduction

###  1.1 Background

From the past year, the whole world has gone through the COVID-19 pandemic.
Twitter, Facebook, Instagram and many other social platforms update news on
pandemics every day. In this project, we will use and fine tune the pre-
trained Bidirectional Encoder Representations from Transformers (BERT) based
models to train social media news posts, which are already known for truth or
fake, for better recognizing those possible false news that may appear in the
future.

###  1.2 Related Work

Adhikari [1] presents the first application of BERT to document
classification. Aggarwal [2] demonstrates classification of fake news by fine-
tuning deep bidirectional transformers based language Model. Devlin [3]
introduces a new language representation model called BERT. Gundapu [4]
introduces an ensemble of three transformer models (BERT, ALBERT, and XLNET)
to detect fake news. Gupta [5] builds a model that makes use of an abusive
language detector coupled with features extracted via Hindi BERT and Hindi
FastText models and metadata. Kaliyar [6] proposes a BERT-based deep learning
approach by combining different parallel blocks of the single-layer deep
Convolutional Neural Network having different kernel sizes and filters with
the BERT. Kula[7] presents a hybrid architecture connecting BERT with RNN. Liu
[8] treats fake news detection as fine-grained multiple-classification task
and use two similar sub-models to identify different granularity labels
separately. Pham [9] explores encoding news title pairs and transforms into
new representation space. Pham-Hong [10] uses a stack of BERT and LSTM layers
to evaluate multilingual offensive language identification in social media.
Safaya [11] describes approach to utilize pre-trained BERT models with
Convolutional Neural Networks for sub-task of the Multilingual Offensive
Language Identification shared task. Sun [12] investigates different fine-
tuning methods of BERT on text classification task and provides a general
solution for BERT fine-tuning. Tang [13] mentions keyword extraction using
Attention-based Deep Learning models with BERT. Vijjali [14] leverages a novel
fact checking algorithm that retrieves the most relevant facts concerning user
claims about particular COVID-19 claims, and verifies the level of“truth” in
the claim by computing the textual entailment between the claim and the true
facts.

##  2 Methods

###  2.1 Dataset

The COVID-19 Fake News Detection Dataset comes from the Kaggle
website333https://www.kaggle.com/elvinagammed/covid19-fake-news-dataset-nlp.
We have the balanced training data, which contains 6,420 data entries with
variable id, tweet and label. We also have balanced testing data which
contains 2,140 data entries with variable id and tweet. There are three main
variables in our training dataset: ’id’ indicates the id number of the tweet;
’tweet’ means the actual context of the tweet/post; lastly, ’label’ describes
whether the news is real or fake. We combine those two datasets together and
randomly split data into training set (90%) and test set (10%) using the set
seed method.

###  2.2 Setup

Data pre-processing is essential for feeding the data into BERT. The pre-
processing steps can be summarized as the following steps: First, we load the
dataset. Second, we perform tokenization and Encoding. We use BertTokenizer
and our own tokenizer to tokenize the tweets. [SEP] and [CLS] tokens need to
be added at the end and beginning of every sentence. Then, we map tokens to
ids. Third, we apply pad and Truncation. BERT requires that all sentences must
have the same fixed length and the max length of 512 tokens per sentence. We
found out that only 10 out of 8560 rows has length that is over 512.
Therefore, we set up our max length to 512. Last, we use Attention Masks. The
purpose of adding the masks is to not incorporate the padded tokens into the
interpretation of the sentences.

###  2.3 Training and Evaluation

Our training and evaluation procedure can be summarized as the following
steps. First, we apply the BertForSequenceClassification model. Second, we
fine tune the BERT model. Third, we add additional layers after the fine-tuned
model, including CNN and Bidirectional LSTM, for both with and without
freezing the parameters in the fine-tuned model.Then, we perform training,
hyperparameter tuning, and testing. Last, we investigate key words that affect
the authenticity of the news. The procedure can be visualized in Figure 1.

Figure 1: Pipeline

##  3 Model

We build five different models to evaluate and compare the performance of fake
news classification.We define Model 1 as the BERT finetuned model. Next, we
define Model 2 as the BERT finetuned model with frozen parameters plus CNN
layer(s).Then, we define Model 3 as the BERT finetund model without frozen
parameters plus CNN layer(s). Besides, we define Model 4 as the BERT finetuned
model with frozen parameters plus BiLSTM layer(s). Lastly, we define Model 5
as the BERT finetuend model without frozen parameters plus BiLSTM layer(s).

Figure 2: BERT+CNN Model Architecture Figure 3: BERT+BiLSTM Model Architecture

###  3.1 Design Architecture

#### BERT finetune

For model 1, we use 2e-5 as the learning rate, and use 4 epochs to fine tune
the model.

#### BERT finetune + CNN

For model 2 and model 3, after the BERT model, we apply two convolutional
layers with kernel size (1,768) and (2,768) and ReLU activation function. Then
we follow a max pooling layer with the previous output size as the kernel size
and the previous height of the output as the stride. After this, we add a
dropout layer with the rate 0.1. Finally, we apply a linear layer with softmax
activation function. The softmax activation function can be expressed as

$\displaystyle\sigma({z})_{i}=\frac{e^{z_{i}}}{\sum_{j=1}^{K}e^{z_{j}}}$

Where K = 2 because we have two classes, fake and real news. ${z}$ indicates
input. The classification result is the class with the highest output of the
softmax activation function. Besides, the learning rate for those two models
are both 2e-5 and the epoch for those two models are both 4. The architecture
can be visualized in Figure 2.

#### BERT finetune + BiLSTM

For model 4 and model 5, after the BERT model, we apply 2 BiLSTM layers to
model 4 and 1 BiLSTM layers to model 5. After this, we apply a linear layer
with softmax activation function. Besides, the learning rate for model 4 and
model 5 are both 5e-5, and the epoch used for model 4 is 10 and for model 5 is
6. The architecture can be visualized in Figure 3.

##  4 Results

###  4.1 Evaluation Criteria

To test our classifiers’ prediction results on fake news dataset, we use the
following metrics. First, we use test accuracy as our primary metric. In our
task, the test accuracy is defined as (1).

$\displaystyle\frac{number\hskip 2.84526ptof\hskip 2.84526ptcorrectly\hskip
2.84526ptclassified\hskip 2.84526ptnews}{total\hskip 2.84526ptnumber\hskip
2.84526ptof\hskip 2.84526ptnews}$ (1)

The second matric we use is train loss. We use cross-entropy loss can be
defined as (2). The cross-entropy compares the model’s prediction with the
label which is the true probability distribution.

$\displaystyle L=-(y\log(p)+(1-y)\log(1-p))$ (2)

The third matric we use is ROC AUC score. The ROC AUC stands for the area
under the curve of ROC. The range of ROC AUC score is 0 to 1, and a large auc
value for a model indicates a good performance of the prediction. The last
matric we use is F1 score. It ranges from 0 to 1 and is calculated from the
precision and the recall of our test results. The precision is the number of
true positive results divided by the number of all positive results, and the
recall is the number of true positive results divided by the number of all
samples that should have been identified as positive. The higher the score,
the better performance it indicates. The formula of F1 score can be written as
(3).

$\displaystyle F1\hskip 2.84526ptscore=2\cdot\frac{precision\cdot
recall}{precision+recall}$ (3)

Table 1: Model Evaluation Model | Test acc | Train loss | ROC AUC | F1 score
---|---|---|---|---
Model 1 | 0.9579 | 0.0036 | 0.9586 | 0.9607
Model 2 | 0.9591 | 0.0200 | 0.9589 | 0.9622
Model 3 | 0.9439 | 0.0211 | 0.9449 | 0.9474
Model 4 | 0.9614 | 0.0197 | 0.9607 | 0.9646
Model 5 | 0.9346 | 0.0227 | 0.9351 | 0.9389

###  4.2 Performance Analysis

From the results, model 4 has the highest test accuracy, ROC AUC and F1 score.
The performance of model 2 is better than that of the BERT fine-tuned model as
well. It is in our expectation that model 4 performs the best since BiLSTM
considers the context before and after the target words.

Figure 4: Most Frequent Words in Our Prediction

###  4.3 Keywords in Fake News

#### Word count

We count and sort the words in sentences which are classified as fake news by
our best model to obtain keywords. For example, excluding some commonly used
prepositions, some of the keywords can be visualized in Figure 4.

#### Frequent words and model performance

We delete those top frequent words listed above in our inputs, and see if the
model performance changes after removing those words. As a result, the model
performance does not change. This indicates that top frequent words do not
usually sololy contribute to the overall performance.

##  5 Discussion

###  5.1 Dataset Limitation

In terms of the size of the dataset, we could collect more fake news data so
that the model can be better trained. We also could try different data set
split ways to find a more reasonable one.

###  5.2 Model Hyperparameters

In the future, there is still space for trying different values of
hyperparameters, such as learning rate and number of additional layers.

###  5.3 Model Structure

The combination of not pre-trained model with additional layers could possibly
improve the performance. Pre-trained model is representative for general tasks
but might not for this specific case. In addition, we could try different
additional layers other than BiLSTM and CNN. One example could be GRU.

###  5.4 Model Evaluation

We realize that the performance of models with frozen parameters in the fine-
tuned model improves, and the performance of models without frozen parameters
in the fine-tuned model does not improve. The reason could be that the size of
the dataset does not have enough support to learn those architectures without
frozen parameters. We also find out that adding additional layers will improve
the accuracy because the new model can capture more information on the
dataset. Overall, the performance of adding BiLSTM layer(s) is better than
that of adding CNN layers under the same condition. We believe that the result
is reasonable because BiLSTM consider the context of the sentence where CNN
does not. In addition, the performances among five models are relatively
similar. In order to achieve a stronger true conclusion, we need to consider
use other methods such as cross validation.

###  5.5 Keywords Evaluation

There are plenty of ways to find keywords that contribute to the fake news
detection. For example, we can find keywords by analyzing the Attention Layer
in BERT. Moreover, we can also find keywords by tracing the gradient value
during the backpropagation procedure.

## References

  * [1] Ashutosh Adhikari, Achyudh Ram, Raphael Tang, and Jimmy Lin.  Docbert: BERT for document classification.  CoRR, abs/1904.08398, 2019.
  * [2] Akshay Aggarwal, Aniruddha Chauhan, Deepika Kumar, Mamta Mittal, and Sharad Verma.  Classification of fake news by fine-tuning deep bidirectional transformers based language model.  EAI Endorsed Transactions on Scalable Information Systems, 7(27), 2020.
  * [3] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.  BERT: pre-training of deep bidirectional transformers for language understanding.  CoRR, abs/1810.04805, 2018.
  * [4] Sunil Gundapu and Radhika Mamidi.  Transformer based automatic COVID-19 fake news detection system.  CoRR, abs/2101.00180, 2021.
  * [5] Ayush Gupta, Rohan Sukumaran, Kevin John, and Sundeep Teki.  Hostility detection and covid-19 fake news detection in social media.  CoRR, abs/2101.05953, 2021.
  * [6] Rohit Kumar Kaliyar, Anurag Goswami, and Pratik Narang.  Fakebert: Fake news detection in social media with a bert-based deep learning approach.  Multimedia Tools and Applications, 80(8):11765–11788, 2021.
  * [7] Sebastian Kula, Michał Choraś, and Rafał Kozik.  Application of the bert-based architecture in fake news detection.  In Conference on Complex, Intelligent, and Software Intensive Systems, pages 239–249. Springer, 2020.
  * [8] Chao Liu, Xinghua Wu, Min Yu, Gang Li, Jianguo Jiang, Weiqing Huang, and Xiang Lu.  A two-stage model based on bert for short fake news detection.  In International Conference on Knowledge Science, Engineering and Management, pages 172–183. Springer, 2019.
  * [9] Lam Pham.  Transferring, transforming, ensembling: the novel formula of identifying fake news.  In Proceedings of the 12th ACM International Conference on Web Search and Data Mining, Melbourne, Australia, pages 11–15, 2019.
  * [10] Bao-Tran Pham-Hong and Setu Chokshi.  PGSG at SemEval-2020 task 12: BERT-LSTM with tweets’ pretrained model and noisy student training method.  In Proceedings of the Fourteenth Workshop on Semantic Evaluation, pages 2111–2116, Barcelona (online), December 2020. International Committee for Computational Linguistics.
  * [11] Ali Safaya, Moutasem Abdullatif, and Deniz Yuret.  KUISAIL at SemEval-2020 task 12: BERT-CNN for offensive speech identification in social media.  In Proceedings of the Fourteenth Workshop on Semantic Evaluation, pages 2054–2059, Barcelona (online), December 2020. International Committee for Computational Linguistics.
  * [12] Chi Sun, Xipeng Qiu, Yige Xu, and Xuanjing Huang.  How to fine-tune BERT for text classification?  CoRR, abs/1905.05583, 2019.
  * [13] Matthew Tang, Priyanka Gandhi, Md. Ahsanul Kabir, Christopher Zou, Jordyn Blakey, and Xiao Luo.  Progress notes classification and keyword extraction using attention-based deep learning models with BERT.  CoRR, abs/1910.05786, 2019.
  * [14] Rutvik Vijjali, Prathyush Potluri, Siddharth Kumar, and Sundeep Teki.  Two stage transformer model for covid-19 fake news detection and fact checking.  arXiv preprint arXiv:2011.13253, 2020.