An Introduction to Permutation Processes (version 0.5)

An Introduction to Permutation Processes (version 0.5)

\frontmatter \preface \addcontentsline{toc}{chapter}{Preface}

This book is an introduction to the theory of stochastic processes whose randomness involves only a random permutation. Such randomnesses can occur either by design (e.g., through a simple sampling without replacement or a randomized controlled trial) or as a consequence of certain data analysis operations (e.g., through ranking).

The book pursues three objectives. First, it aims to provide an exposition on the theory of permutation statistics. The classical foundation of permutation statistics was summarized in the book by sidak1999theory. Permutation inequalities and central limit theorems were well-established as early as the 1970s. More recently, a deeper understanding of the connections between permutation statistics and Stein's methods has emerged, accompanied by the development of new tools and results, as partly outlined in works such as chen2010normal and chatterjee2005concentration. Part I of this book is dedicated to giving an exposition to this foundational theory.

The second objective is to construct a theory of permutation processes within the framework of the already established empirical process theory. In empirical process theory, randomness stems from independent sampling from a specific distribution, corresponding to a super-population perspective on the sampling paradigm. Conversely, in permutation processes, randomness is solely derived from a permutation, representing a finite-population view of sampling. The classical theory of finite-population sampling was summarized in hajek1981sampling and fuller2011sampling. Part II of this book presents alternative results that more closely align with the theory of stochastic processes, akin to the approaches adopted in, e.g., the works of vaart1996empirical and gine2021mathematical.

The third objective of this book is to apply the developed permutation process theory to various statistical applications, for now merely focusing on the theory of M- and Z-estimators and permutation tests. The inherent triangular array nature of permutation randomness, as observed by numerous researchers, calls for Lindeberg-Feller-type analyses of stochastic processes. They occasionally demand nuanced treatments compared to classical arguments. On the other hand, the exploration of finite-population statistical inference, as evidenced by the research endeavors of successive generations of statisticians, holds promise for offering alternative perspectives on a range of data analysis tasks, particularly those rooted in {\it design-based inference}, and can deliver more accurate and robust uncertainty quantification. Part III of this book represents the author's initial efforts, inspired by his colleagues, towards a more systematic treatment of permutation statistical inference. Subsequent enrichment of this section is anticipated in the coming years.

Underlying philosophy

The author's intent is to craft a {\it simple and short} book, featuring minimal notation and concise proofs. The inherent elegance of uniform permutation greatly facilitates this aim. As elucidated in Part II, by confining the support to a finite set, the typically intricate issue of measurability, which holds significant sway in empirical process analyses, can be elegantly resolved in a rigorous manner. Furthermore, the formidable results established by Bobkov bobkov2004concentration and Tolstikhin tolstikhin2017concentration endow Talagrand-type inequalities with remarkable utility within the permutation framework.

Simplicity also entails the author's deliberate selectivity regarding the inclusion of results. It is important to remark that this book exclusively focuses on permutation objects of {\it statistical relevance} and is confined to a narrow range of structures. Consequently, practitioners in fields like survey sampling or causal inference may find themselves grappling with the absence of the precise results they require, particularly those involving more intricate sampling methodologies. Conversely, researchers with a penchant for theoretical exploration may observe that this book barely touches upon modern combinatorial theories, such as those concerning graphs and other complex structures. However, despite these limitations, it is hoped that this book can still offer utility to researchers whose interests align with the book's scope.

Reading guide

This book is structured into three parts, each comprising several chapters. Part I comprises three chapters and is aimed at laying the groundwork for the subsequent discussions. Chapter (ref) provides a brief overview of the permutation objects under examination in this work, alongside establishing essential notation. Chapter (ref) equips the reader with foundational knowledge in mathematical analysis, probability theory, and statistics, essential for understanding the subsequent discussions. Additionally, it emphasizes the triangular array framework, accommodating scenarios where the data-generating distribution varies with the sample size. Chapter (ref) introduces Stein-type analyses of permutation statistics, giving an exploration of weak convergence theorems and moment inequalities.

Part II concerns stochastic processes stemmed from a permutation measure and indexed by a class of functions. It is structured to align with their empirical process counterparts. Chapter (ref) introduces elementary empirical process theory, covering Dudley's metric entropy bounds (Chapter (ref)), Glivenko-Cantelli theorems (Chapter (ref)), and Donsker theorems (Chapter (ref)). Chapter (ref) delves into the theory of permutation processes, corresponding to simple samplings without replacement from a finite population. Within this chapter, Chapter (ref) outlines the stochastic structure of such samplings, while Chapter (ref) presents maximal inequalities essential for stochastic process analyses. Chapters (ref), (ref), and (ref) are dedicated to the permutational Talagrand inequality, Glivenko-Cantelli bounds, and Donsker bounds, respectively, constituting the foundational components of this book. Lastly, Chapter (ref) focuses on a special stochastic process, the spectrum of a combinatorial random matrix, providing a specialized exploration within this domain.

Part III is currently a work in progress and comprises two chapters. Chapter (ref) concerns M- and Z-estimation theory in scenarios where data are sampled without replacement from a finite population. The triangular array setting introduces subtle differences from classical arguments, warranting careful consideration. In Chapter (ref), preliminary results on permutation tests within a finite-population setting are presented.

Why writing this book

The author's motivation to write this book is two-fold.

First, to his knowledge, in the literature {\it there has not been a book that relates probabilistic permutation theory, finite-population statistical inference, and empirical process theory}. It is believed that topics like Stein's method, combinatorial moment and Talagrand inequalities, permutation stochastic process theory, and the connections between them to mathematical statistics—particularly in the realm of hypothesis testing and confidence intervals for complex statistical inference problems—are not adequately covered in any book; their significance will only grow over time.

Second, the author wishes to give a more accessible introduction to the theory of empirical processes, which holds a foundational position in statistics, without sacrificing any mathematical rigor. The simplicity of permutation objects, for the first time, makes it possible.

Intended audience

This book has been used for a special topics course the author gave in the Department of Statistics at the University of Washington, Seattle, in Spring 2024. Accordingly, it is initially designed as a textbook for one-quarter or one-semester graduate-level study of finite-population statistical inference, or, if more ambitious, empirical process theory from a finite-population perspective. In this regard, it aims at {\it graduate students in regular statistics, biostatistics, or econometrics programs}.

This book could also be used for self-study and is suitable for {\it any researcher} with half a year of graduate-level measure/probability theory and a year of graduate-level mathematical statistics, who is {\it interested in learning statistical theory for inferring permutation objects}. In this regard, we hope that this book can clarify important concepts, provide useful theoretical justifications, and be beneficial to researchers in statistics, biostatistics, econometrics, and any other field whose research involves quantifying randomness stemming from permutations.

\chapter*{Notation} \addcontentsline{toc}{chapter}{Notation}

This section puts down the abbreviation and notation this book tries to keep coherently throughout.

Abbreviations

Symbols

Reserved symbols

Sets

Functions

Fonts

Probabilities and Distributions

\mainmatter

\chapter{Uniform Random Permutation}

Uniform random permutation

The primary focus of this book is on uniform random permutation and permutation statistics/processes as its functionals.

A uniform random permutation is a {\it random mapping}, \[ \pi (=\pi_N): [N] \to [N], \] such that \[ \mathrm{Pr}\Big(\pi(1)=i_1,\pi(2)=i_2,\ldots,\pi(N)=i_N\Big)=\frac{1}{N!} \] for any rearrangement $(i_1,\ldots,i_N)$ of $[N]:=\{1,2,\ldots,N\}$. Define $\mathcal{S}_N$ to be the permutation group over $[N]$. The random mapping $\pi$ is a uniform distribution over $\mathcal{S}_N$.

Some basic properties for $\pi$ are listed below.

Statistical permutation

Survey statisticians perceive random permutations as the tool to sample data {\it without replacement}. In the survey sampling literature, this is called {\it simple random sampling without replacement}, although in this book we shall simply call it the {\it permutation sampling}. The idea is simple: given a {\it finite population} \[ \Big\{z_1,z_2,\ldots,z_N\Big\}, \] we sample without replacement a subset of it based on whether, for each $i\in[N]$, whether $\pi(i)\leq n$. Here $n$ is a pre-determined size of the sample. Statistical inference for data collected from the permutation sampling paradigm belongs to the realm of {\it design-based inference}.

Permutation sampling is subtly different from {\it independence sampling}, with which statisticians are much more familiar. In the independence sampling paradigm, it is hypothesized that a researcher samples data points {\it independently} from a {\it superpopulation}, which follows a certain {\it unknown} distribution. Inference based on the independence sampling paradigm belongs to the realm of the {\it model-based inference}.

The two frameworks (design v.s. model) are intrinsically related. First, independence sampling can arise from a random permutation; this is characterized by the following proposition.

Conversely, a uniform random permutation can arise from an independence sampling through the concept of {\it rank-based statistics}. For any real sequence of random variables $X_1,\ldots,X_n$, define the rank of each entry $X_i$, $i\in[n]$, as \[ R_i=R_i(\{X_i;i\in[n]\})=\sum_{j=1}^n{\mathds 1}(X_j\leq X_i). \] It is obvious then that $\{R_i;i\in[n]\}$ is a subset of $[n]$. In particular, when $X_i$'s are distinct, the mapping, $i\to R_i$, is a permutation in $\mathcal{S}_n$.

The next proposition links ranking to permutation.

Permutation statistics

A permutation statistic is a functional of the random permutation. Early focus is on rank tests, e.g., measuring the disarray of two permutations, $\pi$ and $\sigma$, and the closeness of $\pi$ to a uniform permutation.

In statistics, resampling methods constitute to one of the most exciting and deep directions.

What plays the most important role in the scope of this book is the framework of finite-population/design-based statistical inference, where a size-$n$ sample of points is drawn uniformly without replacement from a finite population.

Recent surge in design-based causal inference brings up new application scenarios.

Notes

The results in Proposition (ref) can be found in standard survey sampling books; see, e.g., deming1966some, cochran1977sampling, levy2013sampling, and chaudhuri2014modern. scheaffer1990elementary, chaudhuri2005survey, fuller2011sampling cover more designs beyond simple random sampling. Proposition (ref) is a direct consequence of the entropy argument; cf. hajek1981sampling. \\

Proposition (ref) is well-known; e.g.,in commenting on a paper of Godambe and Thompson, Baranrd baranrd1971bayes mentioned that “a simple random sample of a simple random sample is itself a simple random sample”. Proposition (ref) is well-known as well.\\

Example (ref) mentions four notable rank correlations. A classical reference to rank correlations is Sir. Kendall's book kendall1948rank. We adopt the present version from diaconis1977spearman. Chatterjee's rank correlation is a recent breakthrough in rank correlation methods, proposed by Sourav Chatterjee chatterjee2021new; see, also, shi2022power, lin2023boosting, and lin2022limit. \\

Example (ref) mentions two popular two-sample rank tests. A classical reference is sidak1999theory; see, also, lehmann2006nonparametrics and nikitin1995asymptotic. The present version is adopted from zhao1997error.\\

Example (ref) is about permutation tests, for which good referencing books include good2005permutation, bonnini2014nonparametric, berry2018permutation; see, also, romano2005testing and van2000asymptotic, and chung2013exact. \\

Example (ref) concerns survey sampling, which we have given a brief review in the first paragraph. \\

Example (ref) concerns causal inference in a finite-population sampling without replacement framework. This track of study was initiated by Neyman in splawa1990application. For more discussions, we refer readers to a modern survey made by Li and Ding li2017general and Bai, Shaikh, and Tabord-Meehan bai2024primer.

\chapter{Technical Preparation}

Basic analysis

A {\it topological space} $(\Omega, \mathcal{O})$ contains a collection of subsets, $\mathcal{O}=\{O\subset \Omega\}$, such that

Elements in $\mathcal{O}$ are called {\it open sets}. A set of $B\subset\Omega$ is called {\it closed} if its complement, denoted by $B^c$, is open. The {\it closure} of a set $D\subset\Omega$, denoted by $\bar{D}$, is the intersection of all closed sets that cover $D$. The {\it interior} of $D$, denoted by $D^\circ$, is the union of all open subsets of $D$. A subset $A$ of $\Omega$ is said to be {\it dense} if $\bar A=\Omega$; in that case, $\Omega$ is called {\it separable}.

Any open set that contains $\omega\in\Omega$ is called a {\it neighborhood} of $\omega$. A sequence of points $\{\omega_n\}$ is said to converge to $\omega$ in $(\Omega,\mathcal{O})$, denoted as $\omega_n\to\omega$, if every neighborhood of $\omega$ contains all but finitely many $\omega_n$'s. If distinct points in $\Omega$ contain distinct neighborhoods, then $(\Omega,\mathcal{O})$ is said to be {\it Hausdorff}. A set $K\subset \Omega$ is said to be {\it compact} if for arbitrary open union that covers $K$, it contains a finite open union that still covers $K$. A compact set in a Hausdorff topological space is closed.

A mapping $f$ between two topological spaces is said to be {\it continuous} if the inverse of any open set is open. If $\omega_n\to\omega$ and $f$ is continuous, then $f(\omega_n)\to f(\omega)$.

A metric space $( T,d)$ contains a metric $d: T\times T\to [0,\infty)$ such that, for any $s,t,u\in T$,

A pseudo-metric space $( T,d)$ contains a pseudo-metric $d$ that satisfies (i) and (ii), but not (iii); it thus indues an equivalent class. A (pseudo-)metric space induces a topological space, where the open set is defined as arbitrary unions of the open $r$-balls, $B(t,r):=\{s\in T; d(s,t)<r\}$ for some $r\geq 0$. We can accordingly define topological notions in a (pseudo-)metric space.

A Cauchy sequence $\{t_n\}$ in $( T,d)$ is such that $d(t_n,t_m)\to 0$ as $n,m\to\infty$. The space $( T,d)$ is said to be complete if every Cauchy sequence converges to a limit in $ T$. A separable complete metric space is called a {\it Polish space}.

A set $K\subset T$ is said to be {\it totally bounded} if, for any $r>0$, $K$ can be covered by finitely many open $r$-balls. If $( T,d)$ is complete, then $K$ is compact if and only if $K$ is totally bounded and closed.

A {\it normed space} $( T,\|\cdot\|)$ contains a vector space $ T$ equipped with a norm $\|\cdot\|: T\to[0,\infty)$ such that, for any $s,t\in T$ and $\alpha\in\mathbb{R}$,

The space $( T,\|\cdot\|)$ is called a {\it pseudo-normed} space if it satisfies everything except for (iii) above. A normed space induces a metric space with $d(s,t)=\|s-t\|$ for any $s,t\in T$. A complete normed spaced is called a {\it Banach space}.

Any real space $\mathbb{R}^d$ equipped with the Euclidean norm $\|x\|_2=(\sum_{j=1}^dx_j^2)^{1/2}$ is a Banach space. Another Banach space that plays a special role in this book is the set of all bounded real functions $f: T\to\mathbb{R}$ equipped with the uniform norm $\|f\|_{ T}=\sup_{t\in T}|f(t)|$ (also written as $\|f\|_{\infty}$), denoted as $(\ell^{\infty}( T),\|\cdot\|_{ T})$. This space is not separable unless $ T$ is countable, and $(\ell^{\infty}( T),\|\cdot\|_{ T})$ is generally not Polish.

A subspace of $\ell^{\infty}( T)$, $UC( T,d)$, contains all bounded functions that are {\it uniformly $d$-continuous}, i.e., \[ \lim_{\delta\to0}\sup_{d(s,t)\leq \delta}|f(s)-f(t)|=0. \] The space $(UC( T,d), \|\cdot\|_{ T})$ is Polish.

Stochastic convergence

A collection of subsets of $\Omega$, denoted by $\mathcal{A}$, is a $\sigma$-algebra if

A space $(\Omega,\mathcal{A})$ is said to be {\it measurable} if $\mathcal{A}$ is a $\sigma$-algebra. If $(\Omega,\mathcal{A})$ is measurable and $(\Omega',\mathcal{O}')$ is topological, then $f:\Omega\to\Omega'$ is said to be a {\it measurable function} if the inverse of any element in $\mathcal{O}'$ belongs to $\mathcal{A}$.

For arbitrary collection of subsets of $\Omega$, denoted by $\mathcal{B}$, we define $\sigma(\mathcal{B})$ to be the smallest $\sigma$-algebra that contains $\mathcal{B}$; this is called the $\sigma$-algebra generated by $\mathcal{B}$. For a topological space $(\Omega,\mathcal{O})$, $\sigma(\mathcal{O})$ is called its {\it Borel $\sigma$-algebra}. A map $X$ between two topological spaces $(\Omega,\mathcal{O})$ and $(\Omega',\mathcal{O}')$ is said to be {\it Borel measurable} if $X^{-1}(\mathcal{O}')\subset \sigma(\mathcal{O})$.

For a measurable space $(\Omega,\mathcal{A})$, a map $\mu:\mathcal{A}\to[0,\infty]$ is said to be a {\it measure} if

We call such $(\Omega,\mathcal{A},\mu)$ a {\it measure space}. In particular, if $\mu(\Omega)=1$, the corresponding space is said to be a {\it probability space}, written as $(\Omega,\mathcal{A},\mathrm{Pr})$.

An $\mathcal{X}$-valued random variable $X:\Omega\to \mathcal{X}$ is a Borel measurable function mapping from a probability space $(\Omega,\mathcal{A},\mu)$ to a Polish space $(\mathcal{X},d)$, the latter of which can be infinite-dimensional. For any random variable $X\in\mathcal{X}$, its {\it law}, written as ${\mathrm P}_X$, is defined to be the {\it induced measure} such that ${\mathrm P}_X(A)=\mathrm{Pr}(X^{-1}(A))$ for any Borel measurable $A$ in $(\mathcal{X},d)$.

Consider a sequence of $\mathcal{X}$-valued random variables $\{X_n;n=1,2,\cdots\}$ defined over the same probability space $(\Omega,\mathcal{A},\mathrm{Pr})$.

The following proposition characterizes weak convergence; this is the famous Portmanteau lemma van2000asymptotic.

A probability measure, ${\mathrm Q}$, on a general metric space $(\mathcal{X},d_{\mathcal{X}})$ is said to be {\it tight} if for any $\epsilon>0$, there exists a compact set $K_{\epsilon}\subset \mathcal{X}$ such that ${\mathrm Q}(K_{\epsilon})\geq 1-\epsilon$. A random variable $X: \Omega\to \mathcal{X}$ is said to be tight if its law is tight. It is immediate that every Borel measurable $X$ in the Polish space is tight.

Specializing to the case when $(\mathcal{X},d)$ is $(\mathbb{R}^d,\|\cdot\|_2)$, a random variable $X$ is a measurable map between $(\Omega,\mathcal{A},\mathrm{Pr})$ and the topological space induced by the Euclidean norm $\|\cdot\|_2$. For any $X\in\mathbb{R}$, any probability measure ${\mathrm Q}$ over $(\mathbb{R}, \mathcal{B}(\mathbb{R}))$, and any $p\geq 1$, we define the $L^p({\mathrm Q})$ norm of $X$ as \[ \|X\|_{L^p({\mathrm Q})}=\Big(\int |x|^p{\mathrm d} {\mathrm Q}(x)\Big)^{1/p}. \] The subscript ${\mathrm Q}$ can be further suppressed when the law of $X$ is explicit from the context. In this case, \[ \|X\|_{L^p}=({\mathrm E}|X|^p)^{1/p}=\Big(\int |x|^p{\mathrm d} {\mathrm P}_X(x)\Big)^{1/p}. \] We further define \[ \|X\|_{L^{\infty}} = \inf\Big\{K\in[0,\infty]; \mathrm{Pr}(|X|\leq K)=1 \Big\}, \] which is the {\it essential supremum} of $X$.

The distribution of an $\mathbb{R}^d$-valued random vector ${\bm X}$ is uniquely determined by its characteristic function.

The last theorem connects, regarding weak convergence, the pointwise convergence to the uniform convergence.

Weak convergence of stochastic processes

Let $(\Omega,\mathcal{A},\mathrm{Pr})$ be a probability space and $( T,d)$ be a pseudo-metric space. A stochastic process $\{X(t);t\in T\}$ defined on $(\Omega,\mathcal{A},\mathrm{Pr})$ is a function \[ X: T\times\Omega \to \mathbb{R} \] such that $X(t,\omega)$ is an $\mathbb{R}$-valued random variable for any $t\in T$ and $\omega\in\Omega$. For any finite set $F\subset T$, $\omega\to\{X(t,\omega);t\in F\}$ is then measurable, and we call the distribution of it a {\it finite-dimensional distribution} of $X$. {\it Kolmogorov existence theorem} states then that a {\it consistent} family of finite distributions of $X$ defines a unique probability measure $\mu$ over the cylindrical $\sigma$-algebra $\mathcal{C}$ of $\mathbb{R}^ T$. Thusly, $X$ is a process mapping from $(\Omega,\mathcal{A})$ to $(\mathbb{R}^ T,\mathcal{C})$ and admits the law $\mu$.

In general, $\mu$ cannot be further extended to a tight Borel probability measure with regard to the topological space induced by $\|\cdot\|_T$. Accordingly, the classical theory of weak convergence of stochastic processes in Polish spaces has to be refined.

An important notion about $X$ that we will repeatedly use is {\it separable}.

By definition, if $X$ is separable, then for any $t\in T$, there exists a sequence $s_n\in S$ so that $s_n$ converges to $t$; this implies that $(T,d)$ has to be also separable. In addition, if $X$ is separable, then \[ \sup_{t\in T}|X(t)|=\sup_{t\in S}|X(t)|, a.s.. \] Accordingly, the supremum of a separable stochastic process is always measurable. We will appeal to this property in the following chapters.

A sample bounded $X$ can be embedded into $\ell^{\infty}(T)$ with the corresponding $\sigma$-algebra $\Sigma$ as the intersection between the cylindrical $\mathcal{C}$ and the Borel $\sigma$-algebra generated by the $\|\cdot\|_T$ norm. This metric space, $(\ell^{\infty}(T),\|\cdot\|_T)$, will play a pivotal role in the definition of weak convergence of stochastic processes.

Recall that $X$ is usually not Borel measurable in $(\ell^{\infty}(T),\|\cdot\|_T)$. However, when $X$ is indeed Borel measurable, the following proposition outlines the relation between tightness and sample continuity of $X$.

In reality, verifying the second condition of Definition (ref) is inessential, and the real deal is the following theorem. It connects weak convergence of bounded stochastic processes to another maximal inequality; this is the famous {\it stochastic equicontinuity.}

Theorem (ref) reduces proving weak convergence of stochastic processes to handling (a) weak convergence of any finite-dimensional realization, which is usually a consequence of multivariate central limit theorems, and (b) a new set of maximal inequalities in the form of (ref).

In statistics, weak convergence of stochastic processes is often used combined with the following generalized version of the continuous mapping theorem that extends Proposition (ref).

Elementary probability inequalities

Markov's inequality

Jensen's inequality

Letting $I$ be an interval in $\mathbb{R}$, a function $g:I\to \mathbb{R}$ is said to be convex if for any $x,y\in I$ and any $t\in[0,1]$, \[ g(tx+(1-t)y)\leq tg(x)+(1-t)g(y). \]

A quite useful consequence of Jensen's inequality is the monotonicity of the $L^p$ norms.

Maximal inequalities

A large fraction of this book concerns processes and their performance {\it at the worst case}. To this end, we usually have to bound the supremum of a set of random variables, i.e., to establish maximal inequalities. This point will be made much more clearly when we move on to the second part of this book.

Let us start with the introduction to the Orlicz norm.

Some quite powerful maximal inequalities can be derived based on the notion of Orlicz norm.

Most of the random variables we are going to handle in this book are those with either $\psi_2$- or $\psi_1$-Orlicz norm bounded. It is hence useful to discuss a little bit more about these two special norms.

Specializing to the Orlicz-$\psi_p$ norms, the following lemma gives an alterantive bound to Lemma (ref).

Invoking Proposition (ref), Lemma (ref) gives an (up to constants) equivalent bound to Lemma (ref): \[ {\mathrm E}\max_{i\in[m]}|X_i| \leq \frac{1}{\sqrt{\log 2}}\cdot \max_{i\in[m]}\Big\|X\Big\|_{\psi_p}\cdot\psi_p^{-1}(m). \]

Lastly, the following result connects random variables of a Bernstein tail to the Orlicz-$\psi_1$ norm.

Independence sampling

Statisticians are inevitably familiar with the independence sampling paradigm, which has produced fruitful results in both probability and mathematical statistics. Below we briefly review some of the most fundamental ideas when independence between observed points can be assumed.

Notably speaking, unless otherwise emphasized, in this book we always take a triangular array perspective towards sampling. In other words, for each positive integer $n$, what we observe is

Different $n$ may generate totally different ${\bm X}_{ni}$'s. It is also worthwhile pointing out that, for each fixed $n$, we do {\it not} require $\{{\bm X}_{ni}\}$'s to be identically distributed.

Needless to say, none of the results presented in this chapter can be directly applied to analyzing statistics whose randomness comes solely from a random permutation.

Law of large numbers

We start with the case that all $X_{i}=X_{ni}$'s are random scalars. Introduce \[ \mu_{ni}={\mathrm E}[X_{ni}], ~\sigma^2_{ni}={\rm Var}(X_{ni}), \text{ and } s_n^2=\sum_{i=1}^n{\rm Var}(X_{ni}). \] Let $\bar X_n=n^{-1}\sum_{i=1}^nX_{ni}$ be the sample mean.

Central limit theorems

Central limit theorems (CLTs), exemplified by the weak convergence of a sequence of statistics (random variables) to a continuous limit distribution, typically the Gaussian, not only play a pivotal role but also arguably serve as the cornerstone in the domain of statistical inference. They are crucial in uncertainty quantification, useful for hypothesis testing and building confidence intervals.

This section endeavors to offer a concise review of this pivotal topic, setting the stage for resonance in the subsequent chapters.

Lindeberg-Feller-Lyapunov CLT

Lindeberg-Feller CLT concerns the triangular array setting with independent but possible non-identically distributed random variables. In this regard, it is the most powerful result available to statisticians.

Next, consider multivariate ${\bm X}_{ni}\in\mathbb{R}^d$ with a fixed $d$. We can similarly define \[ {\bm \mu}_{ni}={\mathrm E}[{\bm X}_{ni}]~~~{\rm and}~~\mathbf{\Sigma}_n=\sum_{i=1}^n{\rm Cov}({\bm X}_{ni}). \]

Bounds on CLTs

Lindeberg-Feller CLTs and its variants establish convergence of one sequence of CDFs to its limit. However, in many applications it may also be of interest to learn {\it how fast} the convergence can be. This question is resolved in the next two theorems.

Let's prove a weaker version of Theorem (ref), which can be wrapped up in one page while also involving an important trick we will use later.

In this regard, we consider a simpler setting that \[ X_{n1},\ldots,X_{nn} \text{ are i.i.d.}. \] We further drop the subscript $n$ to save the notation. Without loss of generality then, let's assume they are mean-zero, of unit variance and finite third moment. Consider any smooth function $\phi$ such that the first three derivatives are bounded. One could then establish that, for \[ Z_n:=\frac{1}{\sqrt{n}}\sum_{i=1}^nX_n, \] there exists a universal constant $K>0$ such that \[ \Big|{\mathrm E}\phi(Z_n)-{\mathrm E}\phi(Y)\Big|\leq \|\phi'''\|_{\infty}\cdot \frac{K{\mathrm E}|X|^3}{\sqrt{n}}, \] where $Y\sim N(0,1)$.

Indeed, let $\{Y_i;i\in[n]\}$ be i.i.d. standard Gaussian random variable so that ${\mathrm E}\phi(Y)={\mathrm E}\phi(\sum_{i=1}^nY_i/\sqrt{n})$. Let's then implement an individual swapping trick and introduce \[ Z_{n,i}:=\frac{X_1+\ldots+X_i+Y_{i+1}+\ldots+Y_n}{\sqrt{n}}~~~\text{for }i=0,\ldots,n. \] Accordingly, we have

where in the second equality, for each $i$, we Taylor expand both $\phi(Z_{n,i+1})$ and $\phi(Z_{n,i})$ at $\tilde Z_{n,i}:=(X_1+\cdots+X_i+Y_{i+2}+\cdots+Y_n)/\sqrt{n}$, and the remainder terms satisify \[ R_{n,i}=O(|X_{i+1}|^{3}/n^{3/2})\|\phi'''\|_{\infty}~~~{\rm and}~~~\tilde R_{n,i}=O(|Y_{i+1}|^{3}/n^{3/2})\|\phi'''\|_{\infty}. \]

As a direct consequence, by smoothing the indicator function ${\mathds 1}(x\leq t)$, we obtain a smooth function $\phi$ that takes values 1 and 0 over $(-\infty, t)$ and $(t+\epsilon,\infty)$, respectively. This function has the third derivative upper bounded by $O(\epsilon^{-3})$. Optimizing over $\epsilon$, it yields

for some $K>0$.

This clever swapping idea is due to Lindeberg lindeberg1922neue, for which we call it {\it Lindeberg swapping method}.

Berry-Esseen bound can usually control the tail probabilities up to an order of logarithmic-$n$, which falls in the regime of {\it small deviations}. The next theorem, on the other hand, establishes tail probability bounds at an order of polynomial-$n$. This type of theorems can thus handle {\it moderate deviations}, the research of which was initiated by Khinchin khintchine1929neuen and Cram\'er cramer1994nouveau. The following gives such as a result that applies to triangular arrays.

Moment inequalities

Inequalities that bound the moments of a random variable can usually be translated to those that bound the tail probabilities; cf. Lemma (ref). In this regard, although many useful ones exist, this book is only interested in the following two, namely, Hoeffding's hoeffding1963probability and Bernstein's bernstein1924modification.

Here we give a proof of the Hoeffding's inequality with a slightly weaker bound that yields a worse constant. However, the derivation is easier to understand. Since the bound is location-invariant, we can always shift the random variable $X_{ni}-{\mathrm E} X_{ni}$ to be within $[-\frac{b_{ni}-a_{ni}}{2}, \frac{b_{ni}-a_{ni}}{2}]$ so that \[ \Big\|X_{ni}-{\mathrm E} X_{ni}\Big\|_{\psi_2}\leq \frac{b_{ni}-a_{ni}}{2}. \] Without loss of generality then, assume ${\mathrm E} X_{ni}=0$ for all $i\in[n]$. Using Lemma (ref), we have

The tail probability can then be obtained via Markov's inequality.

Notes

{\bf Chapter (ref).} The standard reference to basic analysis is rubin1987real and rubin1991real. We took most of materials in this chapter from Chapter 6.1 in kosorok2008introduction, which provides a concise summary.\\

{\bf Chapter (ref).} The standard reference to the topic of measure-theoretical probability theory is billingsley2008probability, along with the books of Chung chung2001course and Durret durret2019probability. van2000asymptotic gives a summary of stochastic convergence results, and the author learns the concept of weak convergence on metric spaces from Gallen Shorack shorack2017probability.\\

{\bf Chapter (ref).} billingsley1999convergence outlined the framework of weak convergence of stochastic processes. The present version of weak convergence for sample bounded stochastic processes was adapted from gine2021mathematical. Part I of vaart1996empirical and Chapter 7 of kosorok2008introduction contain further results.\\

{\bf Chapter (ref).} Results in this chapter were scattered in many useful textbooks. The author learnt Theorem (ref) from roch2024modern; see, also, the book by Baik, Deift, and Suidan baik2016combinatorics. More in-depth discussions on Orlicz norms and related properties can be found in, e.g., ledoux2013probability, vaart1996empirical, and vershynin2018high.\\

{\bf Chapter (ref).} The standard reference to the probability of sums of independent random variables is petrov1972independent; pena2009self gives a concise summary. Examples (ref) and (ref), on the number of circles in a permutation, are adapted from durret2019probability. Theorem (ref) is due to huber1973robust. The author learnt the Lindeberg swapping trick, used for proving Theorem (ref), from Terrence Tao tao2023topics. Lastly, a standard reference to moment and concentration inequalities under independence is boucheron2013concentration. Hanson-Wright inequality is due to hanson1971bound and the present form is developed in rudelson2013hanson; see, also, vershynin2018high.

\chapter{Combinatorial Probability}

Overview

In permutation statistics, a classical object of interest is a deterministic $N$ by $N$ real matrix $\mathbf{A}=\mathbf{A}_N\in\mathbb{R}^{N\times N}$, whose entries are written as $\{a_{i,j}=a^N_{i,j}; i,j\in[N]\}$. The matrix $\mathbf{A}=[a_{i,j}]$ changes with $N$. For reasons to be explained later, $\mathbf{A}$ is often coupled with its normalized version, \[ \mathbf{D}=[d_{i,j}], \text{ with } d_{i,j}=a_{i,j}-\frac1N\sum_{k=1}^Na_{k,j}-\frac1N\sum_{\ell=1}^Na_{i,\ell}+\frac{1}{N^2}\sum_{k,\ell=1}^Na_{k,\ell}. \] It is straightforward to verify that \[ \sum_{i=1}^N d_{i,j}=\sum_{j=1}^Nd_{i,j}=0~~\text{for any } i,j\in[N], \] which may help explain why we call $\mathbf{D}$ a normalized version of $\mathbf{A}$. Furthermore, let's define three features of $\mathbf{A}$ that we will repeatedly use in the subsequent sections: \[ \mu_A:=\frac{1}{N}\sum_{i,j=1}^Na_{i,j}, \quad \sigma_A^2:=\frac{1}{N-1}\sum_{i,j=1}^Nd_{i,j}^2, ~~~{\rm and}~~B_A:=\max\limits_{i,j\in[N]}\big|d_{i,j}\big|. \]

In permutation statistics, an analogy to the sample sum, $\sum_{i=1}^nX_i$, in the independence sampling paradigm (i.e., Section (ref)) is the following combinatorial sum, \[ Y:=\sum_{i=1}^N a_{i,\pi(i)}, \] where $\pi=\pi_N$ is uniformly distributed over $\mathcal{S}_N$.

Combinatorial law of large numbers

The mean and variance of a combinatorial sum, whose randomness only comes from the random permutation, was calculated in hoeffding1951combinatorial and we summarize the results below.

A direct consequence of Proposition (ref) is the following (weak) law of large numbers.

Combinatorial CLT

The following is the celebrated combinatorial central limit theorem that also gives a Berry-Esseen-type bound.

A direct consequence of Theorem (ref) is the following corollary, which gives an easier-to-check condition for asymptotic normality of $Y$.

Stein's method of exchangeable pairs

This section gives the proof of a weaker version of the combinatorial CLT. Compared to the proof of chen2010normal, the following one is easier to parse and thus fits more to the philosophy of this book. For {\it all} subsequence results this book is going to cover, this weaker result also suffices.

Let's first introduce Stein's identity that is due to stein1972bound.

The idea of characterizing the Gaussian by checking the averaged difference between $f'(Z)$ and $Zf(Z)$ is ingenious, and also proves to be extremely useful in bounding the distance between probability measures. It turns out to be directly related to a information-theoretical metric, the Wasserstein distance.

In detail, for any two $\mathbb{R}$-valued random variables $W$ and $Z$, the Wasserstein-1 distance between $W$ and $Z$ is defined as \[ d_W(W,Z):=\sup_{g\in\mathcal{L}(1)}\Big|{\mathrm E}[g(W)]-{\mathrm E}[g(Z)]\Big|, \] where the supremum is over $\mathcal{L}(1)$, the set of all 1-Lipschitz functions $g$, that is, functions satisfying $|g(w)-g(z)|\leq |w-z|$ for all $w,z\in\mathbb{R}$.

By Stein's identity, the following lemma then holds; its proof is a little bit technical and not quite related to the mainstream of this book, so we relegate it to the end of this chapter.

With Lemma (ref), the problem of quantifying the convergence rate of any sequence of $\mathbb{R}$-valued random variables $X_n$ to its limit $Z$, if Gaussian, reduces to bounding $|{\mathrm E}[f'(W)-Wf(W)]|$ over $\mathcal{L}'(1)$.

The following theorem connects the Wasserstein distance between any random variable $W$ and $Z\sim N(0,1)$ to, quite surprisingly, the structure of $(W,W')$. This is the celebrated {\it Stein's method of exchangeable pairs}.

Proof of a weaker version of the combinatorial CLT

Using Lemma (ref) yields the following weaker version of Theorem (ref).

A variant of the combinatorial CLT

To analyze Chatterjee's rank correlation in Example (ref), the classical combinatorial CLT is not helpful and we need a variant. To this end, let's define the oscillation sum as \[ W=\sum_{i=1}^{N}a_{\pi(i),\pi(i+1)}~~\text{with the convention that }\pi(N+1)=\pi(1). \]

Some calculations give the mean and variance of $W$.

Combinatorial moderate deviations

The proof of this result is based on a zero-biased coupling technique.

Get back to the proof of Theorem (ref). Let the random variable $X$ in Lemma (ref) take the value \[ \tilde Y=\sum_{i=1}^Nd_{i,\pi(i)}/\sigma_A. \]

Combinatorial moment inequalities

Chatterjee's method

This section aims to establish concentration inequalities for the combinatorial sums. It turns out that such inequalities can be derived through a novel use of Stein's exchangeable method. The idea first appeared in the Ph.D. thesis of Sourav Chatterjee, bearing the title “Concentration inequalities with exchangeable pairs” chatterjee2005concentration and later published in the Annals of Probability chatterjee2006stein.

To introduce Chatterjee's ingenious approach, let's consider a general setting with $X\in\mathcal{X}$ to be a generic random variable, and $f:\mathcal{X}\to\mathbb{R}$ to be the object of interest such that, without loss of generality, \[ {\mathrm E}[f(X)]=0. \] Introduce $X'$ so that $(X,X')$ form an exchangeable pair; see Definition (ref). Now, seek a couple of $f$, denoted by \[ F:\mathcal{X}^2\to \mathbb{R}, \] such that \[ F(X,X')=-F(X',X)~~~\text{ and }~~~{\mathrm E}[F(X,X') \mid X]=f(X). \] Define \[ v(x):=\frac12{\mathrm E}\Big[\Big|(f(X)-f(X'))F(X,X')\Big| \mid X=x\Big]. \] Lastly, assume

The following is Chatterjee's first lemma, which gives a Hoeffding type inequality for those $f(X)$ with $v(x)$ bounded almost surely.

Combinatorial moment inequalities

Next, let's apply Chatterjee's method to studying the combinatorial sums. To this end, we construct an exchangeable pair of $Y$. Like Theorem (ref), we introduce a couple of $\pi$ to be \[ \pi' :=\pi \circ (I,J) =

\] with $I,J$ uniformly and independently sampled from $[N]$. It is easy to check that $(\pi,\pi')$ is an exchangeable pair. Recall Lemma (ref) that \[ Y-{\mathrm E}[Y]=\sum_{i=1}^Nd_{i,\pi(i)}. \] Now take \[ f(\pi)=\sum_{i=1}^N d_{i,\pi(i)} ~~~{\rm and}~~~F(\pi_1,\pi_2)=\frac{N}{2} \Big(\sum_{i=1}^N d_{i,\pi_1(i)}-\sum_{i=1}^N d_{i, \pi_2(i)}\Big). \] The following lemma shows that the couple $(f,F)$ satisfies the conditions of Chatterjee's method.

Combinatorial multivariate CLT

Lastly, we extend the above results to multivariate ${\bm a}_{i,j}\in\mathbb{R}^p$. We could then similarly define \[ {\bm a}_{i,\bullet}=\frac{1}{N}\sum_{j=1}^N{\bm a}_{ij}, ~~~{\bm a}_{\bullet,j}=\frac1N\sum_{i=1}^N{\bm a}_{ij},~~~ {\bm a}_{\bullet,\bullet}=\frac{1}{N^2}\sum_{i,j=1}^N{\bm a}_{i,j}, \] and ${\bm d}_{i,j}={\bm a}_{i,j}-{\bm a}_{i,\bullet}-{\bm a}_{\bullet,j}+{\bm a}_{\bullet,\bullet}$. It is easy to verify that $\sum_{i=1}^N{\bm d}_{i,j}=\sum_{j=1}^N{\bm d}_{i,j}=\bm{0}~~\text{for any }i,j\in[N]$. Define \[ {\bm Y}:=\sum_{i=1}^N{\bm a}_{i,\pi(i)},~~~{\bm \mu}_A=\frac{1}{N}\sum_{i,j=1}^N{\bm a}_{i,j},~~~{\rm and}~~~\mathbf{\Sigma}_A=\frac{1}{N-1}\sum_{i,j\in[N]}{\bm d}_{i,j}{\bm d}_{i,j}^\top. \]

Hoeffding's convex ordering inequality

We end this chapter with a useful result that compares linear statistics of entries sampled without replacement to those with replacement. This inequality is due to Wassily Hoeffding's pathbreaking 1963 paper hoeffding1963probability that also proposed another, maybe more famous, inequality named after him (Theorem (ref)).

The observation that sampling without replacement would lead to more accurate estimates than sampling with replacement is intuitive. In the case of a linear statistics, the following argument of Debabrata Basu basu1958sampling is well-known.

Wassily Hoeffding extended the above argument to a more general framework that can potentially compare the stochastic ordering of vector-valued linear functionals arising from the two types of samplings. The following is his convex ordering inequality.

Notes

{\bf Chapters (ref)-(ref).} Study of combinatorial sums of the form $\sum_{i=1}^N{a_{i,\pi(i)}}$ originated from Wald and Wolfowitz wald1944statistical, who were focused on a more special case of $a_{i,j}=a_ib_j$; see, also, noether1949theorem, erdos1959central, and hajek1961some. The current form of the combinatorial sum was pinned down by Hoeffding hoeffding1951combinatorial; see, also, motoo1956hoeffding.\\

{\bf Chapters (ref)-(ref).} Wald and Wolfowitz wald1944statistical, Noether noether1949theorem, and Dwass dwass1955asymptotic proved CLTs for linear statistics of the form $\sum_{i=1}^Na_ib_{\pi(i)}$, for which H\'ajek hajek1961some gave a final say: a necessary and sufficient condition. Hoeffding introduced and proved the first CLT for the general permutation statistic $\sum_{i=1}^N{a_{i,\pi(i)}}$ in hoeffding1951combinatorial. A Lindeberg condition was later established in motoo1956hoeffding.

Von Bahr von1976remainder gave the first Berry-Esseen-type bound for quantifying the convergence of combinatorial CLTs. Ho and Chen ho1978l_p are the first to introduce Stein's method into analyzing the combinatorial sum. Using a more refined analysis based on Stein's method, Bolthausen bolthausen1984estimate gave the present theorem (Theorem (ref)).

Charles Stein introduced Stein's method in his famous 1972 paper stein1972bound. A standard reference to his method is the monograph written by Stein himself stein1986approximate. Another popular and also systematic introduction to his method is chen2010normal. See, also, ross2011fundamentals and chatterjee2014short for some concise surveys of the literature. In particular, the author learnt the arguments made in Chapter (ref) from ross2011fundamentals.

Chapter (ref) concerns an oscillation setting that was related to counting Eulerian number and the number of runs barton1965some,knuth1997art. A related setting concerns double- and multiply-indexed permutation statistics zhao1997error,shi2022distribution, which are U-statistics counterpart to the combinatorial sum studied in this chapter.

{\bf Chapters (ref)-(ref).} The idea of using Stein's method to derive sharp concentration bounds is due to Sourav Chatterjee in chatterjee2005concentration, which we followed closely in this chapter. Specializing to survey sample means, serfling1974probability introduced a set of concentration inequalities based on the martingale method; see, also, bardenet2015concentration and greene2016finite for surveys of related inequalities. We will give a relatively more detailed discussion on this literature in Chapter (ref).

shi2022berry gave a set of Berry-Esseen bounds for multivariate combinatorial CLT. See, also, fraser1956vector for an early attempt and bolthausen1993rate, chatterjee2007multivariate, and fang2015rates for some more recent progress.

Hoeffding's original convex ordering inequality, presented in hoeffding1963probability, only concerns real-valued random variables. The present theorem, instead, can handle general vector-valued random objects including, in particular, stochastic processes. This form was introduced in vaart1996empirical. The present proof is due to ben2018weighted, which only concerned real-valued random variables but whose proof idea can be easily generalized to analyzing vector-valued ones. This type of the generalization is of particular usefulness in stochastic process analysis.