Pattern Avoidance for Random Permutations
Using techniques from Poisson approximation, we prove explicit error bounds on the number of permutations that avoid any pattern. Most generally, we bound the total variation distance between the joint distribution of pattern occurrences and a corresponding joint distribution of independent Bernoulli random variables, which as a corollary yields a Poisson approximation for the distribution of the number of occurrences of any pattern. We also investigate occurrences of consecutive patterns in random Mallows permutations, of which uniform random permutations are a special case. These bounds allow us to estimate the probability that a pattern occurs any number of times and, in particular, the probability that a random permutation avoids a given pattern.
\mathop{\mbox{Part}}\nolimits{\mathop{\mbox{Part}}\nolimits}
\def\hbox{\bf.}{\hbox{\bf.}}
\def\mathop{\mathbf{MonSets}}\nolimits{\mathop{\mathbf{MonSets}}\nolimits}
\def\mathop{\mbox{Mon}}\nolimits{\mathop{\mbox{Mon}}\nolimits}
\def\mathop{\mathbf{Mon_{[n]}}}\nolimits{\mathop{\mathbf{Mon_{[n]}}}\nolimits}
\def\mathop{\mbox{im}}\nolimits{\mathop{\mbox{im}}\nolimits}
\def\mathop{\mbox{Set}}\nolimits{\mathop{\mbox{Set}}\nolimits}
\def\mathop{\mbox{Graph}}\nolimits{\mathop{\mbox{Graph}}\nolimits}
\def\mathop{[m]}\nolimits{\mathop{[m]}\nolimits}
\def\mathop{[mk]}\nolimits{\mathop{[mk]}\nolimits}
\def\mathop{[nk]}\nolimits{\mathop{[nk]}\nolimits}
\def\mathop{[m]^k}\nolimits{\mathop{[m]^k}\nolimits}
\def\mathop{[n]^k}\nolimits{\mathop{[n]^k}\nolimits}
\def\mathop{[l]}\nolimits{\mathop{[l]}\nolimits}
\def\mathop{=_{\mathcal{L}}}\nolimits{\mathop{=_{\mathcal{L}}}\nolimits}
\def\mathop{\mathbf{id}}\nolimits{\mathop{\mathbf{id}}\nolimits}
\def\mathop{\text{red}}\nolimits{\mathop{\text{red}}\nolimits}
\def\mathop{\text{flatten}}\nolimits{\mathop{\text{flatten}}\nolimits}

\def\mathbb{E}\,{\mathbb{E}\,}
\def\mathbb{R}\,{\mathbb{R}\,}
\def\mathbb{X}{\mathbb{X}}
\def\overline{\X}{\overline{\mathbb{X}}}
\def\mathbb{B}{\mathbb{B}}
\def\overline{\B}{\overline{\mathbb{B}}}
\def\mathcal{L}\left(\overline{\X}\right){\mathcal{L}\left(\overline{\mathbb{X}}\right)}
\def\mathcal{L}\left(\overline{\B}\right){\mathcal{L}\left(\overline{\mathbb{B}}\right)}

\newcommand{\ignore}[1]{ }



\newtheorem{thm}{Theorem}[section]
\newtheorem{lemma}[thm]{Lemma}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{defn}[thm]{Definition}
\newtheorem{example}[thm]{Example}
\newtheorem{conj}[thm]{Conjecture}
\newtheorem{rmk}[thm]{Remark}
\title{Pattern avoidance for random permutations}
\author{Harry Crane}
\address{Rutgers University, 110 Frelinghuysen Road, Piscataway, NJ, 08854}
\author{Stephen DeSalvo}
 \address{UCLA, 520 Portola Plaza, Los Angeles, CA, 90095}
\date{\today}

\subjclass{05A05; 05A15; 05A16; 60C05}
\keywords{pattern avoidance; Mallows distribution; random permutation; Poisson approximation}

\begin{document}
\maketitle
\begin{abstract}
We use techniques from Poisson approximation to prove explicit error bounds on the number of permutations that avoid any pattern.
Most generally, we bound the total variation distance between the joint distribution of pattern occurrences and a corresponding joint distribution of independent Bernoulli random variables, which as a corollary yields a Poisson approximation for the distribution of the number of occurrences. 
We also investigate occurrences of consecutive patterns in random Mallows permutations, of which uniform random permutations are a special case.
These bounds allow us to estimate the probability that a pattern occurs any number of times and, in particular, the probability that a random permutation avoids a given pattern.


\end{abstract}

\ignore{
Proposed Table of contents / organizational structure.
\begin{enumerate}
\item Intro
\item Pattern avoidance corollaries
	\begin{itemize}
	\item[2.1] Uniform Measure
	\item[2.2] Mallows measure
	\end{itemize}
\item Chen--Stein Poisson approximation
	\begin{itemize}
	\item[3.1] General coupling method
	\item[3.2] Fixed point example, $\sigma(i) \neq j$ generalization
	\item[3.3] Arratia--Goldstein Theorem
	\end{itemize}
\item Poisson convergence theorems
	\begin{itemize}
	\item[4.1] Uniform distribution
	\item[4.2] Mallows distribution
	\end{itemize}
\item Special cases, including asymptotic behavior for $n,q.$
\end{enumerate}
}

\setcounter{tocdepth}{1}
\tableofcontents

\ignore{
{\color{orange}
TODO:
\begin{enumerate}
\item
\item Add remark on difference between absolute error and relative error.
\item Add remark on total variation distance much stronger than convergence in distribution.
\item Make remark on the longest increasing sequence is log-concave conjecture of Sagan and others. 
\item Silverman paper 
\item QUANTITATIVE BOUNDS justifies Arratia Goldstein, as many other limit theorems could be applied.  
\end{enumerate}
}
}

\section{Introduction}\label{section:intro}

A {\em permutation} of $[n]=\{1,\ldots,n\}$ is a bijection $\sigma:[n]\rightarrow[n]$, $i\mapsto\sigma(i)=\sigma_i$, written $\sigma=\sigma_1\cdots\sigma_n$.
For each $n=1,2,\ldots$, we write $\mathop{\mathcal{S}_{n}}\nolimits$ to denote the set of permutations of $[n]$.
Given permutations $\sigma=\sigma_1\cdots\sigma_n$ and $\tau=\tau_1\cdots\tau_m$, we say that {\em $\sigma$ avoids $\tau$} if there does not exist a subsequence $1\leq i_1<\cdots <i_m\leq n$ such that $\sigma_{i_1}\cdots\sigma_{i_m}$ is order-isomorphic to $\tau$, and we say that {\em $\sigma$ avoids $\tau$ consecutively} if there is no $j=1,\ldots, n-m+1$ such that $\sigma_j\sigma_{j+1}\cdots\sigma_{j+m-1}$ is order-isomorphic to $\tau$.
Here we study pattern avoidance probabilities for a wide class of random permutations from the Mallows distribution, which is of particular interest in the fields of statistics and probability but special cases provide insights into questions in enumerative and extremal combinatorics.

An {\em inversion} in $\sigma=\sigma_1\cdots\sigma_n$ is a pair $(i,j)$, $i<j$, such that $\sigma_i>\sigma_j$.
For example, $\sigma=34125$ has four inversions, $(1,3), (1,4), (2,3), (2,4)$.
We write $\mathop{\text{inv}}\nolimits(\sigma)$ to denote the set of inversions of $\sigma$.
With $\Sigma_n$ denoting a random permutation of $[n]$, the {\em Mallows distribution with parameter $q\in(0,\infty)$} on $\mathop{\mathcal{S}_{n}}\nolimits$ assigns probability
\begin{equation}\label{eq:Mallows}
P\{\Sigma_n=\sigma\}=P_n^q(\sigma)=q^{|\mathop{\text{inv}}\nolimits(\sigma)|}/I_n(q),\quad\sigma\in\mathop{\mathcal{S}_{n}}\nolimits,\end{equation}
where $I_n(q)=\prod_{j=1}^n\sum_{i=0}^{j-1}q^i$ is the {\em inversion polynomial} and $|\mathop{\text{inv}}\nolimits(\sigma)|$ is the number of inversions in $\sigma$.
Note that $q=1$ corresponds to the uniform distribution on $\mathop{\mathcal{S}_{n}}\nolimits$, i.e., $P\{\Sigma_n=\sigma\}=1/n!$ for all $\sigma\in\mathop{\mathcal{S}_{n}}\nolimits$,  and is the critical point at which the Mallows family switches from penalizing inversions, $q<1$, to favoring them, $q>1$.
Results for pattern avoidance probabilities under the uniform distribution translate to enumerative results for the number of pattern avoiding permutations.
Combinatorial inequalities bounding the number of pattern avoiding permutations obtained from our techniques are contained in Equations~\eqref{bounds}~and~\eqref{bounds-consec}.  

The Mallows distribution \cite{Mallows1957} was introduced as a one-parameter model for rankings that occur in statistical analysis.
More recently, Mallows permutations have been studied in the context of the longest increasing subsequence problem \cite{Bhatnagar2014} and quasi-exchangeable random sequences \cite{GnedinOlshanski2009,GnedinOlshanski2010}. 
Our study of pattern avoidance for this class relates to recent work in the combinatorics literature, which considers the Wilf equivalence classes of the inversion polynomials for permutations that avoid certain sets of patterns \cite{cameronkilpatrick,sagan}.
For general values of $q>0$, we consider the problem of consecutive pattern avoidance for random Mallows permutations, but our main theorems go quite a bit further by establishing explicit error bounds on the entire distribution of the number of occurrences of patterns in a random permutation.
In the uniform setting ($q=1$), our method provides an estimate for the number of permutations with a prescribed number of occurrences as well as the number of permutations with a prescribed number of consecutive occurrences of a given pattern.
Our main theorems, therefore, complement prior work by Elizalde \& Noy \cite{elizaldenoy}, Perarnau \cite{perarnau}, and the more recent work by the current authors \& Elizalde ~\cite{crane2016probability} on consecutive pattern avoidance, as well as Nakamura \cite{Nakamura2014}, who used functional equations to enumerate sets with a prescribed number of occurrences of a given pattern. 
Other related works include~\cite{pratt1973computing} for patterns $\tau$ of length $n-1$, and~\cite{ray2003posets} for patterns $\tau$ of length $n-2$. 
And it is left as an open problem in~\cite{vatter376problems} to perform the same analysis for patterns $\tau$ of length $n-3$. 

Our approach also differs from previous work  in a few key respects. 
While most prior work seeks either exact or asymptotic enumeration of the sets that avoid a given pattern or collection of patterns, we use the Chen--Stein Poisson approximation method \cite{chen1975poisson}, in particular \cite{ArratiaGoldstein}, to bound the total variation distance between the collection of all \emph{dependent} indicator random variables indicating pattern occurrence at a prescribed set of indices, and a joint distribution of \emph{independent} Bernoulli random variables with the same marginal distributions.
From these bounds, we can approximate the probability that a random permutation avoids a given pattern, i.e., the pattern occurs zero times, or contains any number of occurrences of that pattern.

We summarize our main theorems in Section \ref{section:pattern}.





\section{Motivation}
Restricted permutations fall into two broad classes.  
The first, more tractable type is of the form $\sigma(a) \neq b$ for $a, b\in [n]$, whose study dates to the classical {\em probl\`emes des rencontres} in the early 1700s \cite{Montmort1708}; see also \cite[Chapter 4]{barbour1992poisson}.
A special case counts the number $D_n$ of {\em derangements} of $[n]$, i.e., permutations of $[n]$ without fixed points, yielding the asymptotic expression
\begin{equation}\label{eq:derangement}D_n=n!\sum_{i=0}^n\frac{(-1)^i}{i!}\sim n!/e\quad\text{as }n\rightarrow\infty.\end{equation}
Equation \eqref{eq:derangement} can be stated in probabilistic terms by letting $\Sigma_n$ be a uniform random permutation of $[n]$, i.e., $P\{\Sigma_n=\sigma\}=1/n!$ for each $\sigma\in\mathop{\mathcal{S}_{n}}\nolimits$, in which case
\begin{equation}\label{eq:derangement-prob}P\{\Sigma_n\text{ is a derangement}\}=D_n/n!\sim1/e\quad\text{as }n\rightarrow\infty.\end{equation}
See~\cite{ArratiaTavare,SheppLloyd} for more thorough treatments involving the cycle structure of random permutations.  

We can also derive the expression in \eqref{eq:derangement} by Poisson approximation. 
With $W$ denoting the number of fixed points in a random permutation of $[n]$, we demonstrate in Section~\ref{section:fixed}, see also \cite[Chapter 4]{barbour1992poisson}, that the distribution of $W$ converges in total variation distance to the distribution of an independent Poisson random variable with expected value $1$.  
In addition to the asymptotic value for the probability that a random permutation has no fixed points, this approach bounds the absolute error of probabilities that involve {any measurable function} of the number of fixed points in a random permutation.

The second type of restriction is {\em pattern avoidance}, which attracts increasing attention in the modern probability \cite{Bhatnagar2014,HoffmanRizzolo2016I,HoffmanRizzolo2016II} and modern combinatorics literature \cite{BonaBook}.
Any sequence of distinct positive integers $w=w_1\cdots w_k$ determines a permutation of $[k]$ by {\em reduction}: with $\{w_{(1)},\ldots,w_{(k)}\}_{<}$ denoting the set of elements listed in increasing order, we define the map $w_{(i)}\mapsto i$, under which $w$ maps to a permutation $\mathop{\text{red}}\nolimits(w)$ of $[k]$, called the {\em reduction} of $w$.
For example, $w=826315$ reduces to $\mathop{\text{red}}\nolimits(w)=625314$.
We call any fixed $\tau\in\mathop{\mathcal{S}_{m}}\nolimits$ a {\em pattern} and say that $\sigma\in\mathop{\mathcal{S}_{n}}\nolimits$ {\em contains} $\tau$ if there exists a subsequence $1\leq i_1<\cdots<i_m\leq m$ such that $\mathop{\text{red}}\nolimits(\sigma_{i_1}\cdots\sigma_{i_m})=\tau$.
We say $\sigma\in\mathop{\mathcal{S}_{n}}\nolimits$ {\em avoids} $\tau$ if it does not contain it.
We say that $\sigma$ {\em contains $\tau$ consecutively} if there exists an index $j\in[n-m+1]$ such that $\mathop{\text{red}}\nolimits(\sigma_{j}\sigma_{j+1}\cdots\sigma_{j+m-1})=\tau$; otherwise, we say $\sigma$ {\em avoids $\tau$ consecutively}.
For any pattern $\tau$, we define 
\begin{align}
\mathop{\mathcal{S}_{n}}\nolimits(\tau)&:=\{\sigma\in\mathop{\mathcal{S}_{n}}\nolimits:\,\text{$\sigma$ avoids $\tau$}\}\quad\text{and}\notag\\
\label{eq:consecutive-set}
\mathop{\overline{\mathcal{S}}_{n}}\nolimits(\tau)&:=\{\sigma\in\mathop{\mathcal{S}_{n}}\nolimits:\,\text{$\sigma$ avoids $\tau$ consecutively}\},
\end{align}
which we extend to any subset $A\subset\bigcup_{n\geq1}\mathop{\mathcal{S}_{n}}\nolimits$ by
\begin{align}
\label{eq:avoiding-set}\mathop{\mathcal{S}_{n}}\nolimits(A)&:=\{\sigma\in\mathop{\mathcal{S}_{n}}\nolimits:\,\sigma\text{ avoids all }\tau\in A\}\quad\text{and}\\
\mathop{\overline{\mathcal{S}}_{n}}\nolimits(A)&:=\{\sigma\in\mathop{\mathcal{S}_{n}}\nolimits:\,\sigma\text{ avoids all $\tau\in A$ consecutively}\}\notag.
\end{align}
Much effort has been devoted to exact enumeration of $\mathop{\mathcal{S}_{n}}\nolimits(A)$ for certain choices of $A$, see, e.g., \cite{TwoPatterns4,TwoPatterns1,TwoPatterns2,TwoPatterns3}.
For the most part, we are interested in sets $\mathop{\mathcal{S}_{n}}\nolimits(\tau)$ containing all permutations that avoid a given pattern $\tau$, though our approach extends in a straightforward manner for more general sets $A$.

Attempts to enumerate $\mathop{\mathcal{S}_{n}}\nolimits(\tau)$ are notoriously difficult for patterns of fixed length larger than 3.  
Knuth \cite{KnuthI} initiated interest in pattern avoidance in the study of algorithms by identifying the $231$-avoiding permutations as exactly those that can be sorted by a single run through a stack; see Bona \cite[Chapter 8]{BonaBook} for further discussion.
In fact, it is now well known that the avoidance sets $\mathop{\mathcal{S}_{n}}\nolimits(\tau)$ for every length-$3$ pattern $\tau$ are enumerated by the Catalan numbers \cite[A000108]{OEIS}:
\[|\mathop{\mathcal{S}_{n}}\nolimits(\tau)|={2n\choose n}/(n+1),\quad \tau\in\{123,132,213,231,312,321\}.\]

Just as in the derangement problem above, enumeration of $\mathop{\mathcal{S}_{n}}\nolimits(A)$ has an elementary probabilistic interpretation that motivates much of our paper.
With $\Sigma_n$ denoting a uniform random permutation of $[n]$ and $A$ a set of permutations, the probability that $\Sigma_n$ avoids $A$ is
\[P\{\Sigma_n\text{ avoids every }\tau\in A\}=|\mathop{\mathcal{S}_{n}}\nolimits(A)|/n!.\]
The Stanley--Wilf theorem \cite{MarcusTardos2004} states that $|\mathop{\mathcal{S}_{n}}\nolimits(\tau)|$ grows exponentially with $n$ for every {fixed} $\tau$.
For example, the Catalan numbers are known to grow asymptotically like $4^n / \sqrt{\pi\, n^3}$, yielding the asymptotic avoidance probability
\[P\{\Sigma_n\text{ avoids }231\}=\binom{2n}{n}/(n+1)!\sim \frac{1}{\pi\, n^2 \sqrt{2}}\left(\frac{4\, e}{n}\right)^n \quad\text{as }n\rightarrow\infty.\]
Such calculations quickly become intractable.
For example, the sets of $1324$-avoiding permutations have only been enumerated up to $n=31$ \cite{JohanssonNakamura2014}.
Even precise asymptotics for $|\mathop{\mathcal{S}_{n}}\nolimits(1324)|$ have not yet been established \cite{Bona2014b,Bona2014a,ClaessonJelinek2012}.



\section{Main Results}\label{section:pattern}

\subsection{Definitions}
\label{section:definitions}
Throughout the paper, we write $\mathcal{L}(X)$ to denote the {\em distribution}, or {\em law}, of a random variable $X$ and $\mathcal{L}(Y\mid X)$ to denote the {\em conditional distribution of $Y$ given $X$}.
For random variables $X$ and $Y$, we write $d_{TV}(\mathcal{L}(X),\mathcal{L}(Y))$ to denote the {\em total variation distance} between the distributions of $X$ and $Y$, which in the special case of non-negative integer-valued random variables can be computed as
\[d_{TV}(\mathcal{L}(X),\mathcal{L}(Y))=\frac{1}{2}\sum_{n=0}^{\infty}|P(X=n)-P(Y=n)|.\]

Define the set of all unordered, distinct $j$-tuples of elements from $[n]$ by
\[ \Gamma_j := \{\{i_1, \ldots, i_j\} : 1\leq i_1<\cdots<i_j\leq n\}, \qquad j\in [n]. \]
For each $\alpha \in \Gamma_j$, let $D_\alpha$ be the set of all $j$-element subsets of $[n]$ that overlap with $\alpha$ in at least one element, i.e., $D_{\alpha}:=\{\beta\in\Gamma_j:\,\beta\cap\alpha\neq\emptyset\}.$
  For example, if $\alpha = \{1, 5, 8\}$, then $D_{\alpha}^c = \{ \{j_1, j_2, j_3\} : j_i \notin\{1,5,8\}, i=1,2,3\}.$  

With $\Sigma_n$ denoting a uniform random permutation of $[n]$, $\alpha \in \Gamma_j$, and $\tau$ a fixed pattern of length $j$, we define $X_{\alpha}=X_{i_1, \ldots, i_m}$ as the indicator random variable for the event that the reduction of $\Sigma_n$ at positions $i_1, \ldots, i_m$ form the pattern $\tau$, i.e.,
\begin{equation}\label{eq:indicator}
X_{i_1,\ldots,i_m}:=\mathbb{I}( { \mathop{\text{red}}\nolimits(\Sigma_n(i_1)\cdots\Sigma_n(i_m))=\tau } ).\end{equation} 
Let $\mathbb{X} \equiv \mathbb{X}_j := (X_\alpha)_{\alpha\in\Gamma_j}$, and 
let $\mathbb{B} \equiv \mathbb{B}_j = (B_\alpha)_{\alpha\in \Gamma_j}$ denote a joint distribution of independent Bernoulli random variables with marginal distributions satisfying $\mathbb{E}\, B_\alpha = \mathbb{E}\, X_\alpha$ for all $\alpha \in \Gamma_j$.  
The random variable
\begin{equation}\label{eq:W}
 W = \sum_{1 \leq i_1 < \ldots < i_m \leq n} X_{i_1,\ldots, i_m}
 \end{equation}
counts the total number of occurrences of $\tau$ in $\Sigma_n$.



For any $\tau\in\mathop{\mathcal{S}_{m}}\nolimits$, for each $s=1,\ldots,m-1$ we define $L_s(\tau)$ as the {\em overlap of size $s$}, i.e., the number of permutations $\sigma\in\mathcal{S}_{2m-s}$ such that there are indices $1\leq i_1<\cdots<i_m\leq 2m-s$ and $1\leq j_1<\cdots<j_m\leq 2m-s$ such that $\{i_1,\ldots,i_m\}$ and $\{j_1,\ldots,j_m\}$ have exactly $s$ elements in common and 
\[\mathop{\text{red}}\nolimits(\sigma_{i_1}\cdots\sigma_{i_m})=\mathop{\text{red}}\nolimits(\sigma_{j_1}\cdots\sigma_{j_m})=\tau.\]



For consecutive pattern avoidance, we similarly define the set of all $j$-tuples of the form $\{i, i+1,\ldots, i+j-1\}$, $1 \leq i\leq n-j+1$, as
\[ \overline{\Gamma}_j := \{\{i, i+1, \ldots, i+j-1\} : 1\leq i \leq n-j+1\}, \qquad j\in [n-j+1]. \]
Let $\overline{\mathbb{X}} \equiv \overline{\mathbb{X}}_j := (X_\alpha)_{\alpha\in\overline{\Gamma}_j}$, and 
let $\overline{\mathbb{B}} \equiv \overline{\mathbb{B}}_j = (B_\alpha)_{\alpha\in \overline{\Gamma}_j}$ denote a joint distribution of independent Bernoulli random variables with marginal distributions which satisfy $\mathbb{E}\, B_\alpha = \mathbb{E}\, X_\alpha$ for all $\alpha \in \overline{\Gamma_j}$.  
Next, we define analogously the random variable
\begin{equation}\label{W'} \overline{W} := \sum_{1 \leq s \leq n-m+1} X_{s,s+1,\ldots,s+m-1},
\end{equation}
where $X_{s,s+1,\ldots,s+m-1}$ is defined as in \eqref{eq:indicator} for a fixed pattern $\tau\in\mathop{\mathcal{S}_{m}}\nolimits$ and a uniform random permutation $\Sigma_n$.
We also define $\overline{L}_s(\tau)$ as the {\em sequential overlap of size $s$}, i.e., the number of permutations $\sigma\in\mathcal{S}_{2m-s}$ such that 
\[\mathop{\text{red}}\nolimits(\sigma_{1}\cdots\sigma_{m})=\mathop{\text{red}}\nolimits(\sigma_{m-s+1}\cdots\sigma_{2m-s})=\tau.\]




\subsection{Main corollaries}\label{main:corollaries}
We begin with several limit theorems which follow from the quantitative bounds given in Section~\ref{poisson limits}. 

\begin{cor}\label{theorem:asymptotic-general}
Fix any $\eta\geq 0$, and let $j\equiv j(n)$ be some increasing, integer-valued function of $n$ such that $j \geq (e\, e^{1/e}+\eta)\sqrt{n}$.
For any sequence of patterns $\tau_n\in\mathop{\mathcal{S}_{j}}\nolimits$, and for any measurable function $h : \{0,1\}^{\binom{n}{j}} \to \mathbb{R}\,$ and Borel set $A \subseteq \mathbb{R}\,$, as $n$ tends to infinity we have
\[ \mathbb{P}( h(\mathbb{X}) \in A) = \mathbb{P}( h(\mathbb{B}) \in A) + o(1). \]
\end{cor}

\ignore{
\begin{rmk}
By the Stanley--Wilf theorem \cite{MarcusTardos2004}, the avoidance sets for every fixed pattern $\tau$ satisfy
\[ |S_n(\tau)| < \lambda^n \]
for some constant $\lambda>0$.  Note that Theorem~\ref{theorem:asymptotic-general} 
does not violate the Stanley--Wilf theorem since our patterns must also grow with $n$.
\end{rmk}
}


We also have an analogous theorem for consecutive patterns, but with a stronger result.


\begin{cor}\label{theorem:asymptotic-consecutive}
Fix any $t>0$, and define $M(t,n) := \left\lfloor \frac{\log(n/t)}{\log\log(n/t) - \log\log\log(n/t)} - \frac{1}{2}\right\rfloor$.  
Let $m \equiv m(n)$ be some increasing, integer-valued function of $n$ such that $m \geq M(t,n)$.
For any sequence of patterns $\tau_n\in\mathop{\mathcal{S}_{m}}\nolimits$, and for any measurable function $h : \{0,1\}^{n-m+1} \to \mathbb{R}\,$ and Borel set $A \subseteq \mathbb{R}\,$, as $n$ tends to infinity we have
\[ \mathbb{P}( h(\overline{\mathbb{X}}) \in A) = \mathbb{P}( h(\overline{\mathbb{B}}) \in A) + o(1). \]
In particular, denoting by $Y_t$ an independent Poisson random variable with parameter $t$, and taking $m(n) = M(t,n)$, we have 
\[ d_{TV}(\overline{W}, Y_t) = O\left(\frac{1}{m}\right); \]
whence, 
\begin{align*}
 |\mathop{\overline{\mathcal{S}}_{n}}\nolimits(\tau_n)| &\sim n!\, e^{-t}\quad\text{as }n\to\infty.
\end{align*}
\end{cor}

\ignore{
\begin{conj}\label{conjecture:asymptotic-consecutive}
Fix any $t>0$.  
Suppose $j \sim \Gamma^{(-1)}(n/t)$, and that $\tau_n$ is any sequence of patterns with size $j$.
Suppose $W'$ is defined as in Equation~\eqref{W'}.  
Then for $P$ an independent Poisson random variable with mean $\lambda = \mathbb{E}\, W$, as $n$ tends to infinity, we have
\begin{equation}
d_{TV}(\mathcal{L}(W'), \mathcal{L}(P)) \to 0,
\end{equation} 
whence,
\[ |\mathop{\overline{\mathcal{S}}_{n}}\nolimits(\tau_n)| \sim n!\, e^{-t}. \]
\end{conj}
}

Finally, we present an analogous result for permutations chosen according to the Mallows($q$) distribution.

\begin{cor}\label{cor:mallows}
Let $m\equiv m(n)$ be a non-decreasing integer-valued sequence, $\tau_n\in\mathop{\mathcal{S}_{m}}\nolimits$ be a sequence of patterns, and $q\equiv q(n)$ be a sequence of parameters.
For each $n\geq1$, let $\Sigma_n$ be a random permutation from the Mallows distribution \eqref{eq:Mallows} with parameter $q(n),$ with $\overline{\mathbb{X}}_q$ and $\overline{\mathbb{B}}_q$ defined analogously. 
For any measurable function $h : \{0,1\}^{n-m+1} \to \mathbb{R}\,$ and Borel set $A \subseteq \mathbb{R}\,$, we have
\[ \mathbb{P}( h(\overline{\mathbb{X}}_q) \in A) = \mathbb{P}( h(\overline{\mathbb{B}}_q) \in A) + o(1), \]
provided either
\begin{align*}
q(n)&\leq n^{-1/\mathop{\text{inv}}\nolimits(\tau_{m(n)})}\quad\text{for almost all }n\geq1,\\
q(n)&\geq n^{1/(\binom{m(n)}{2}-|\mathop{\text{inv}}\nolimits(\tau_{m(n)})|)}\quad\text{for almost all }n\geq1,\\
|\mathop{\text{inv}}\nolimits(\tau_{m(n)})|&\leq-\log(n)/\log(q(n))\quad\text{for almost all }n\geq1\text{ and }q<1\quad\text{or}\\
|\mathop{\text{inv}}\nolimits(\tau_{m(n)})|&\geq-\log(n)/\log(q(n))+m(n)^2/2\quad\text{for almost all }n\geq1\text{ and }q>1.
\end{align*}
\end{cor}






\subsection{Quantitative bounds for large patterns}\label{poisson limits}


Corollaries~\ref{theorem:asymptotic-general} and \ref{theorem:asymptotic-consecutive} provide an asymptotic analysis for sequences of patterns which also grow in size. 
It is too much to expect a general asymptotic formula for any fixed pattern---we have already noted the difficulty of nailing down the asymptotic growth of 1324-avoiding sets---but Poisson approximation, see Section \ref{section:poisson}, provides a general approach for obtaining \emph{quantitative} bounds on various quantities when all sizes are fixed.



\begin{thm}\label{theorem:main}
Assume $n \geq j \geq 3,$ and $\tau$ is any pattern of length $j$.  
Let $\mathbb{X} = (X_\alpha)_{\alpha\in\Gamma_j}$, and 
let $\mathbb{B} = (B_\alpha)_{\alpha\in \Gamma_j}$ denote an independent Bernoulli process with marginal distributions which satisfy $\mathbb{E}\, B_\alpha = \mathbb{E}\, X_\alpha$ for all $\alpha \in \Gamma_j$.  
We have
\begin{align}
\label{bounds-TV}
d_{TV}(\mathcal{L}(\mathbb{X}), \mathcal{L}(\mathbb{B})) &\leq 4D_{n,j} + \frac{2\lambda}{j!},
\end{align}
where $D_{n,j} = \min(1, \lambda^{-1})(d_1+d_2),$
\begin{align}
\notag \lambda & = \binom{n}{j}/j!,  \qquad  d_1  = \binom{n}{j} \left( \binom{n}{j} - \binom{n-j}{j} \right) \frac{1}{j!^2}, \\
\label{d2} d_2 & = \sum_{s=1}^{j-1} \binom{n}{2j-s}\frac{2\, L_s(\tau)}{(2j-s)!}.
\end{align}
Furthermore, for $Y$ a Poisson random variable with mean $\lambda = \mathbb{E}\, W$, we have
\[ d_{TV}(\mathcal{L}(W), \mathcal{L}(Y)) \leq 2D_{n,j}, \]
and also 
\begin{equation}\label{bounds}
n!\, e^{-\lambda}\left(1 - e^{\lambda} D_{n,j}\right) \leq |\mathop{\mathcal{S}_{n}}\nolimits(\tau)| \leq n!\, e^{-\lambda}\left(1 + e^\lambda D_{n,j}\right).
\end{equation}

\end{thm}


\begin{rmk}
There are several noteworthy aspects to Theorem \ref{theorem:main}.  

\begin{enumerate}
\item The expression for $\lambda$ is the same for all patterns of length $j$.  
\item The expression for $d_1$ cannot be improved by our approach.
\item
We are unaware of any efficient means to calculate the values $L_s(\tau)$ in general.  For a simple and explicit upper bound, applicable for all patterns $\tau$ of length $j$, we suggest
\begin{equation}\label{d2:crude}
 d_2 \leq \binom{n}{j} \sum_{s=1}^{j-1} \binom{n-j}{j-s} \binom{j}{s}\frac{s!}{j!^2}, 
 \end{equation}
but we suspect this bound can be improved. 
\item As Theorem \ref{theorem:asymptotic-general} suggests, these bounds are most useful when $D_{n,j} < 1$, i.e., when $j$ is large.  
\end{enumerate}
\end{rmk}


\begin{thm}\label{consecutive patterns}
Assume $n \geq m\geq 3$ and $\tau$ is any pattern of length $m$. 
We have 
\begin{align}
\label{uniform consecutive bounds}
d_{TV}\left(\mathcal{L}\left(\overline{\X}\right)), \mathcal{L}\left(\overline{\B}\right)\right) & \leq 4\overline{D}_{n,m} + \frac{2\overline{\lambda}}{m!},
\end{align}
where $\overline{D}_{n,m} = \min(1, 1/\overline{\lambda})(\overline{d}_1+\overline{d}_2),$
\begin{align*}
\overline{\lambda} & = \frac{n-m}{m!},  \qquad
\overline{d}_1  = \frac{n_1}{m!^2}, \qquad \overline{d}_2  =  \sum_{s=1}^{m-1} \frac{(n-2m+s)\, 2\, \overline{L}_s(\tau)}{(2m-s)!}, \qquad 
 n_1 & = 2mn - 3m^2 +m.
 \end{align*}
Let $\overline{Y}$ denote a Poisson random variable with parameter $\lambda = \mathbb{E}\, \overline{W}$.  We have
\[ d_{TV}\left(\mathcal{L}\left(\overline{W}\right), \mathcal{L}\left(\overline{Y}\right)\right) \leq 2\overline{D}_{n,m}, \]
and also 
\begin{align}
\label{bounds-consec}
n!\, e^{-\overline{\lambda}}\left(1 - e^{\overline{\lambda}}\, \overline{D}_{n,m}\right) \leq |\mathop{\overline{\mathcal{S}}_{n}}\nolimits(\tau)| &\leq n!\, e^{-\overline{\lambda}}\left(1 + e^{\overline{\lambda}}\, \overline{D}_{n,m}\right).
\end{align}
\end{thm}




\subsection{Limitations of Poisson Approximation}
It is tempting to conjecture that Corollary~\ref{theorem:asymptotic-general} holds even when $\lambda$ tends to some fixed positive constant, but we suspect this is not possible, which we now demonstrate. 
First, we note the following.

\begin{lemma}[\cite{McKayPersonal}]
\label{lemma:mckay}
Fix any $t>0$ and let $\lambda=\binom{n}{j}/j!$.
Then $\lambda\rightarrow t$ for 
\begin{equation}\label{j:asymptotic}
j \sim e \sqrt{n} - \frac{1}{4}\log(n) -\frac{1}{2}\log(2\pi t) - \frac{1}{4} e^2 - \frac{1}{2}\quad\text{as }n\rightarrow\infty.
\end{equation}
\end{lemma}

\begin{lemma}\label{lemma:d1bound}
Suppose $n$, $j$ and $n-j$ tend to infinity, then we have 
\[ d_1 \sim \lambda^2\left(1 - e^{-j^2/n}\right). \]
In particular, for $j \sim e\sqrt{n}-\frac{1}{4}\log(n)$, we have $d_1 \to c \in (0,\infty)$.  
\end{lemma}

Thus, a necessary condition for $d_1$ to tend to zero is
\begin{equation}
\label{possible:j}j \sim e \sqrt{n} - \left(\frac{1}{4}-\epsilon\right)\log(n).\
\end{equation}
It is also well known, see \cite{VershikKerov,LoganShepp}, that the typical size of the longest increasing subsequence is asymptotically of order $2 \sqrt{n},$ and so one cannot have a Poisson limit theorem which applies to the increasing pattern $12\ldots j$.  
It would be interesting to investigate the behavior in the gap, i.e., for $j \sim c \sqrt{n}$ with any $2 < c < e.$




\ignore{
The asymptotic result in Theorem \ref{theorem:asymptotic-general} cannot be strengthened due to the monotonic pattern $12\ldots j.$  It is well--known, see \cite{LoganShepp, VershikKerov}, that the typical size of the longest increasing subsequences is asymptotically of order $2 \sqrt{n}.$  
Thus, there cannot be a universal Poisson limit theorem applicable to all patterns of length 
based on Theorem \ref{theorem:main} and the following lemmas.
}


\ignore{
Using the bound for $d_2$ in Equation~\eqref{d2:crude}, we are able to prove the following asymptotic result.

\begin{thm}\label{theorem:asymptotic}
Let $j \equiv j(n)$ be some increasing, integer-valued function of $n$ such that for any $\epsilon>0$, $j > (e\sqrt{2}+\epsilon)\sqrt{n}$, and let $\tau_n \in \mathop{\mathcal{S}_{j}}\nolimits$ be a sequence of patterns.
Then
\[ |\mathop{\mathcal{S}_{n}}\nolimits(\tau_n)| \sim n!\, e^{-\binom{n}{j}/j!}\quad\text{as }n\to\infty. \]
\end{thm}
}

\ignore{
\begin{conj}\label{conjecture:asymptotic}
Fix any $t>0$.
Suppose $j = j(n) \sim e \sqrt{n} - \frac{1}{4}\log(n) -\frac{1}{2}\log(2\pi t) - \frac{1}{4} e^2 - \frac{1}{2}$ as $n\to\infty$, and let $\tau_n\in\mathop{\mathcal{S}_{j}}\nolimits$ be any sequence of patterns of size $j$.
Then the results of Theorem \ref{theorem:asymptotic-general} continue to hold with $\mu_n \to t$.
\end{conj}
}
 
\ignore{
\begin{conj}\label{conjecture:asymptotic}
Fix any $t>0$.  
Suppose $j \sim e \sqrt{n} - \frac{1}{4}\log(n) -\frac{1}{2}\log(2\pi t) - \frac{1}{4} e^2 - \frac{1}{2}$, and that $\tau_n$ is any sequence of patterns with size $j$.
Suppose $W$ is defined as in Equation~\eqref{eq:W}.  
Then for $P$ an independent Poisson random variable with mean $\lambda = \mathbb{E}\, W$, as $n$ tends to infinity, we have
\begin{equation}
d_{TV}(\mathcal{L}(W), \mathcal{L}(P)) \to 0,
\end{equation} 
whence,
\[ |\mathop{\mathcal{S}_{n}}\nolimits(\tau_n)| \sim n!\, e^{-t}. \]
\end{conj}
}





\ignore{
Computing $\tilde{L}_s(\tau),$ or at least a good upper bound, is the bottleneck to a more precise statement, and it is easy to show that
\[ d_2' \leq \frac{2\,(n-m)}{m!}(e-1) \]
for all length-$m$ patterns $\tau$.
In this case, however, we do conjecture that more is true, based on the following. 

\begin{lemma}\label{lemma:cantrell}
Suppose $t>0$ is some fixed constant and $m \sim \Gamma^{(-1)}(n/t)-1$.  Then as $n$ tends to infinity, 
\begin{align*}
\frac{n-m}{\Gamma(m+1)} \to t.
\end{align*}
\end{lemma}

\begin{rmk}
The purpose of Lemma~\ref{lemma:cantrell} is to establish the asymptotic boundary for Poisson approximation, and it is not needed for Theorem~\ref{theorem:main} or Theorem~\ref{consecutive patterns}. 
Our use of  for integer--valued $m$ requires qualification.  
As $n$ tends to infinity, we appeal to a sequence of integer--valued $m$, say $m = [\Gamma^{(-1)}(n/t)-1]$. 
\begin{align*}
 \lambda' & = \frac{n-m}{m!} \to t.
 \end{align*}
\end{rmk}

\begin{prop}[Increasing contiguous sequence]\label{longest:contiguous}
Let $\tau_m = 12\ldots m$ denote the monotonically increasing sequence of size $m$, $m \geq 1$. 
Suppose $t>0$ is some fixed constant and $m \sim \Gamma^{(-1)}(n/t).$ 
Then we have 
\begin{align*}
 |\mathop{\overline{\mathcal{S}}_{n}}\nolimits(\tau_m)| &\sim n!\, e^{-t}\quad\text{as }n\to\infty.
\end{align*}
Moreover,  with $\mu_n:=(n-m)/m!$, we have
\[\mathbb{P}(W'=k)\sim t^k e^{-t}/k!\quad\text{as }n\to\infty,\]
 for every $k=0,1,\ldots$.
\end{prop}




\begin{thm}\label{conjecture:asymptotic-consecutive}
Fix any $t>0$.  
Suppose $j \sim \Gamma^{(-1)}(n/t)$ and that $\tau_n$ is any sequence of patterns with size $j$. 
Then the results of Theorem \ref{theorem:asymptotic-consecutive} continue to hold with $\mu_n \to t$.
\end{thm}

}



\subsection{Consecutive pattern avoidance for Mallows permutations}

In Section \ref{section:Mallows}, we discuss several special properties of the Mallows distribution that are helpful for studying consecutive pattern avoidance.
Using these properties, we obtain analogous bounds to those in Theorems \ref{theorem:main} and \ref{consecutive patterns}.

Recall the definition of the {\em restriction} $\Sigma_{n|A}$ of $\Sigma_n$ to a subset $A\subseteq[n]$, and recall $\overline{\Gamma}_m$ denotes 
the set of subsets of size $m$ whose elements are consecutive in $\{1,2,\ldots, n\}$.  

\begin{thm}\label{main:mallows:theorem}
Fix $q>0$ and let $\Sigma_n\sim\text{Mallows}(q)$.
For any $m \geq 2$,
let $\tau_m$ be any pattern of size $m$. 
For any $\alpha \in \overline{\Gamma}_m$, let
\[ X_\alpha = \mathbb{I}(\mathop{\text{red}}\nolimits(\Sigma_{n|\alpha})=\tau_m). \]
Let $W = \sum_{\alpha \in \overline{\Gamma}_m} X_\alpha$ and let $Y$ be an independent Poisson random variable with expected value $\lambda = \mathbb{E}\, W$.  
Then
\[ d_{TV}(\mathcal{L}(W), \mathcal{L}(Y)) \leq 2(b_1+b_2), \]
where
\begin{align}
\notag \lambda&=(n-m)\frac{q^{|\mathop{\text{inv}}\nolimits(\tau_m)|}}{I_m(q)}, \qquad
 b_1 = \frac{n_1 q^{2 |\mathop{\text{inv}}\nolimits(\tau_m)|}}{I_m(q)^2}, \qquad 
 b_2 = \sum_{s=1}^{m-1} (n-2m+s) \sum_{\rho \in \overline{L}_s(\tau_m)} \frac{q^{|\mathop{\text{inv}}\nolimits(\rho)|}}{I_{2m-s}(q)}, \\

\notag n_1 &= 2 m n-3 m^2+m.
 \end{align}
 
 
\end{thm}

The key to obtaining asymptotic formulas and Poisson limit theorems for general Mallows permutations relies on the interplay  between the parameters $n$, $m$, $|\mathop{\text{inv}}\nolimits(\tau)|$, and $q$.
In particular, we need the expected number of occurrences to converge to a constant $\lambda\in(0,\infty)$.
In the case of consecutive pattern avoidance, the expected number of occurrences of a pattern $\tau\in\mathop{\mathcal{S}_{n}}\nolimits$ in $\Sigma_n\sim\text{Mallows}(q)$ is
\[\lambda=(n-m)q^{|\mathop{\text{inv}}\nolimits(\tau)|}/I_m(q),\]
which, for $m$ fixed, produces non-trivial limiting behavior as long as
\begin{align*}
q\sim n^{-1/|\mathop{\text{inv}}\nolimits(\tau)|}\quad&\text{or}\quad q\sim n^{1 / \left({m\choose2}-|\mathop{\text{inv}}\nolimits(\tau)|\right)}.
\end{align*}
We can also allow $m$ to vary and keep $q$ fixed so that
\begin{align*}
|\mathop{\text{inv}}\nolimits(\tau)|\sim-\log(n)/\log(q)\quad&\text{or}\quad|\mathop{\text{inv}}\nolimits(\tau)|\sim-\log(n)/\log(q)+m^2/2.
\end{align*}
Combined with Theorem \ref{main:mallows:theorem}, these observations yield Corollary~\ref{cor:mallows}.

In Section~\ref{section:3}, we demonstrate Theorem \ref{main:mallows:theorem} for all patterns of length 3.  
In Section~\ref{section:detailed}, we compute the bounds in Theorems \ref{theorem:main} and \ref{main:mallows:theorem} for the specific patterns 2341 and 23451 and we plot the estimated pattern avoidance probabilities in the appropriate asymptotic regime for $q$ from Corollary \ref{cor:mallows}.






\ignore{
\subsection{Improved bounds}\label{section:improved}

While asymptotic formulas in Section \ref{poisson limits} hold for all large patterns, the Poisson limit result is degenerate unless $\mu>0$, where $\mu$ is defined for general and consecutive pattern avoidance in  Theorems \ref{theorem:asymptotic-general} and \ref{theorem:asymptotic-consecutive}, respectively.
These limiting results are still useful for large finite $n$, but we are able to obtain non-degenerate Poisson limits for specially structured patterns.

As an illustration, consider consecutive pattern avoidance for {\em tent patterns}, which have the form
\[\tau = x_1\,x_2\,\ldots\, x_j\, y_{i-1}\, \ldots\, y_2\,y_1, \]
for $x_1 < x_2 < \cdots < x_j$ and $y_1 < y_2 <\cdots < y_{i-1} < x_j$,
i.e., a pattern of length $m = j+i-1$ of $j$ increasing elements followed by a pattern of $i-1$ decreasing elements.
The only sequential overlaps can occur on the first and last elements, so $\tilde{L}_s(\tau) = 0$ for $s \ge 2$.  
When $s=1$, i.e., one overlap at either end, we have
\[ \tilde{L}_1(\tau) = \binom{(m-x_1) + (m - y_1)}{m-x_1}\binom{x_1-1+y_1-1}{x_1-1},
\]
since there are $m-x_1$ elements larger than $x_1$, $m-y_1$ elements larger than $y_1$.
Also, for the $x_1 - 1$ elements smaller than $x_1$ and $y_1-1$ elements smaller than $y_1$, we have $\binom{x_1-1+y_1-1}{x_1-1} = 1$ possible orderings, since either $x_1 = 1$ or $y_1 = 1$.  
Thus, we have
\[ d_2'  =  2\, \frac{(n-2m+1)\, \binom{(m-x_1)+ (m - y_1)}{m-x_1}}{(2m-1)!}. \]
In this case, $d_2'$ attains a maximum when $\{x_1,y_1\} = \{1,2\}$ and 
\[ d_2' \leq n (2m) \binom{2m}{m} / (2m)! = \frac{2nm}{m!^2}. \]
By a slight generalization we arrive at the following non-degenerate Poisson limit theorem under the uniform distribution, of which the above example is a special case.
\begin{prop}\label{Poisson:theorem}
Let $\tau$ denote any pattern for which $\tilde{L}_s(\tau) = 0$ for $s \geq 2$. 
Suppose for some fixed $t>0$, we have $m \sim \Gamma^{(-1)}(n/t).$ 
Denote by $x$ and $y$ the first and last values of the pattern, respectively, i.e., $\tau = x\cdots y$. 
Then
\[ \tilde{L}_1(\tau) = \binom{2m-x-y}{m-x}\binom{x-1 + y-1}{x-1},
 \]
and the number of times the pattern $\tau$ occurs in a random permutation of $n$ is asymptotically Poisson distributed with expected value $t.$
In particular,
\[|\bar{\mathop{\mathcal{S}_{n}}\nolimits}(\tau)|\sim n!\, e^{-t}\quad\text{as }n\rightarrow\infty. \]
\end{prop}

\begin{prop}
The following types of sequences satisfy the conditions of Proposition~\ref{Poisson:theorem}.
\begin{enumerate}
\item Tent patterns, i.e., 
\[\tau = x_1\,x_2\,\ldots\, x_j\, y_{i-1}\, \ldots\, y_2\,y_1, \]
where $x_1 < x_2 < \cdots < x_j$ and $y_1 < y_2 <\cdots < y_{i-1} < x_j$,
i.e., a pattern of length $m = j+i-1$ of $j$ increasing elements followed by a pattern of $i-1$ decreasing elements.
\item Layered patterns, i.e., patterns which have strictly increasing (resp.\ decreasing) segments such that every element of preceding segments is larger (resp.\ smaller) than elements in later segments, e.g., 7 8 9 10 4 5 6 2 3 1 has segments (7 8 9 10) (4 5 6) (2 3) (1).


\end{enumerate}
\end{prop}

Note that the sequence $23\cdots k1$ is both a tent and a layered pattern; see~\cite{Nakamura2014} for other interesting aspects of this pattern.  
 
 }
 

\ignore{
In fact, we can improve the bound in Theorem~\ref{theorem:main} by taking specific structural information of $\tau$ into account.  
This additional information may also extend the range of patterns that provide non-trivial bounds.  
With $\sigma\in\mathop{\mathcal{S}_{n}}\nolimits$ understood, we define the $L_s(\tau)$ as the {\em overlap of size $s$}, i.e., the number of permutations $\sigma\in\mathcal{S}_{2m-s}$ such that there are indices $1\leq i_1<\cdots<i_m\leq 2m-s$ and $1\leq j_1<\cdots<j_m\leq 2m-s$ such that $\{i_1,\ldots,i_m\}$ and $\{j_1,\ldots,j_m\}$ have exactly $s$ elements in common and 
\[\mathop{\text{red}}\nolimits(\sigma_{i_1}\cdots\sigma_{i_m})=\mathop{\text{red}}\nolimits(\sigma_{j_1}\cdots\sigma_{j_m})=\tau.\]
Similarly, we define $\tilde{L}_s(\tau)$ as the {\em sequential overlap of size $s$}, i.e., the number of permutations $\sigma\in\mathcal{S}_{2m-s}$ such that 
\[\mathop{\text{red}}\nolimits(\sigma_{1}\cdots\sigma_{m})=\mathop{\text{red}}\nolimits(\sigma_{m-s+1}\cdots\sigma_{2m-s})=\tau.\]
We then define the {\em total overlap} and {\em total sequential overlap} of $\tau\in\mathop{\mathcal{S}_{m}}\nolimits$, respectively, by
\[\sum_{s=1}^{m-1}L_s(\tau)\quad\text{and}\quad\sum_{s=1}^{m-1}\tilde{L}_s(\tau).\]
}

\ignore{
For example, for $\tau = 12534$, the sequential overlap of size~$1$ is 5, corresponding to patterns 125346978, 126345978, 127345968, 128345967, and 129345867.  Similarly, the sequential overlap of size~$2$ is 4, corresponding to patterns 12534867, 12634857, 12734856, and 12834756.
There are a great many more cases to consider when finding the total overlap; in fact, we must look recursively at all patterns of length $s \leq j-1$ in $\tau.$
For example, to find the total overlap of size~$s$, we look at the number of patterns of size~$s$ \emph{in the pattern itself}, and then overlap with all patterns of size~$s$.  The pattern $\tau=12534$ contains $12$ in positions 12, 15, 25, 13, 14, 23, 24, and 34, so we should calculate all possible patterns for which overlap occurs in these cases.  For size~3, there is no overlap from patterns 123, however, the pattern 132 occurs several times, namely, 153, 154, 253, and 254.  The patterns 231, 213, 321, and 312 do not occur on overlapping indices.  Finally, no patterns of length 4 overlap.
}


\section{Poisson approximation}\label{section:poisson}

\subsection{Chen--Stein method}
Stein's method is an approach to proving the central limit theorem that was adapted by Chen to Poisson convergence \cite{chen1975poisson}.  The advantage of this method is that it provides guaranteed error bounds on the total variation distance between the distribution of a sum of possibly dependent random variables and the distribution of an independent Poisson random variable with the same mean. 

\begin{thm}[Chen \cite{chen1975poisson}]\label{ChenStein}
Suppose $X_1, X_2, \ldots, X_n$ are indicator random variables with expectations $p_1, p_2, \ldots, p_n$, respectively, and let $W = \sum_{i=1}^n X_i$.  Let $Y$ denote an independent Poisson random variable with expectation $\lambda = \sum_{i=1}^n p_i$.  Suppose, for each $i \geq 1$, a random variable $V_i$ can be constructed on the same probability space as $W$ such that
\[ \mathcal{L}(1+V_i) = \mathcal{L}(W \mid X_i=1).
\]
Then
\begin{equation}\label{dtv bound} 
d_{TV}(\mathcal{L}(W), \mathcal{L}(Y)) \leq \frac{1-e^{-\lambda}}{\lambda}\sum_{i=1}^n p_i \mathbb{E}\, |W - V_i|.
\end{equation}
\end{thm}
\ignore{\marginpar{
For the coupling below: suppose $\sigma=21543$ and $i=1$.  So $\sigma(i)=2$ and the coupling says ``swap elements $i$ and $j$'' to get $\sigma'=12543$.  Now the number of fixed points has gone from 1 in $\sigma$ to 3 in $\sigma'$ for a difference of 2.
It seems to me that the displayed equation below should have a difference of 2 whenever $i$ is in a 2-cycle.
}}
\subsection{Fixed Points Example}\label{section:fixed}
As a simple example, let $e(n)$ denote the number of fixed-point free permutations of $n$.  With $\Sigma_n$ a uniform permutation of $[n]$, we define indicator random variables  
\[X_i = \mathbb{I}(\text{ $i$ is a fixed point of $\Sigma_n$ }), \qquad i=1,\ldots,n.
\]
(Note that these random variables are \emph{not} independent.)  
We then define the sum
\[ W = \sum_{i=1}^n X_i \]
so that $P(W = 0) = e(n)/n!$ and $\lambda = \mathbb{E} W=\sum_{i=1}^n \frac{1}{n} = 1$, the expected number of fixed points.  
Even before we proceed with the bound, we obtain the heuristic estimate of $n!\, e^{-1}$ for $e(n)$, just as in \eqref{eq:derangement}.

To apply Theorem~\ref{ChenStein}, we need to construct $W$ and $1+V_i$ on the same probability space, and construct an explicit coupling.  This is done for more general restrictions in \cite{barbour1992poisson}, but we shall write out the full calculation on fixed points to demonstrate how one can construct such a coupling.


The random variable $1+V_i$ is the random sum $W$ conditioned on $X_i = 1$.  For a random permutation $\sigma$, suppose $\sigma(i) = j$, for some $j\in [n]$.  The coupling is: swap elements $i$ and $j$.  The resulting permutation has the same marginal distribution as a random permutation conditioned to have a fixed point at $i$.  In fact, $|W - V_i| \in \{0,1,2\}$ for each $i$ since we modify at most 2 elements, and the elements not involved in the swap cancel out (i.e., any fixed points occurring on indices other than these swapping positions remain unchanged).  Let us denote the random variables after the coupling by $X_1', X_2', \ldots, X_n'$; that is, $\mathcal{L}(X_j') = \mathcal{L}(X_j \mid X_i=1)$, so that $1+V_i = \sum_{j=1}^n X_j'$. 
We have 
\[
|W - V_i| = \left|X_i+\sum_{k\neq i} (X_k - X_k')\right| = |X_i + X_J\mathbb{I}(J = \sigma(i), J\neq i)| = \begin{cases} 0, & \sigma(i) \neq i, \text{$i$ not in a 2-cycle}, \\
				      1, & \sigma(i) = i, \\
				       2, & \text{$i$ in a 2-cycle}.
				       \end{cases}
				       \]
The probability that two given elements $i$ and $j$ are part of a 2-cycle is precisely $1/(n(n-1))$, and the probability that $i$ is part of a 1-cycle is $1/n$.  Thus, 
\[ \mathbb{E}\, |W - V_i| = \frac{1}{n}+\frac{2}{n} = \frac{3}{n}, \]
and Equation~\eqref{dtv bound} becomes
\[ 
d_{TV}(\mathcal{L}(W), \mathcal{L}(Y)) \leq (1 - e^{-1}) \sum_{i=1}^n \frac{1}{n} \frac{3}{n} = \frac{3(1-e^{-1})}{n}. 
\]
For all $n \geq 1$, we have
\[
|P(W=0) - P(Y=0)| = \left| \frac{e(n)}{n!} - e^{-1} \right| \leq \mathop{\rm sup}\nolimits_i | P(W=i) - P(Y=i)| \leq d_{TV}(W,Y) \leq \frac{3(1-e^{-1})}{n}.\]
Rearranging yields
\[n! e^{-1} - 3(n-1)! (1-e^{-1}) \leq e(n) \leq n! e^{-1} + 3(n-1)! (1-e^{-1}). \]
Note that this is a guaranteed error bound that holds for all $n\geq 1$, and as a corollary we get $e(n) = n! e^{-1}(1+o(n^{-1}))$.

The error bounds derived from the Chen--Stein method can be improved in special cases, e.g., $e(n)$ above can be obtained exactly by rounding $n!/e$ to the nearest integer for all $n \geq 1$, but the appeal of Poisson approximation is that it applies more generally. 
Our main theorems (Theorems \ref{theorem:asymptotic-general} and \ref{theorem:asymptotic-consecutive}) identify cases in which the bounds provide an asymptotically efficient estimate.

\subsection{The Arratia--Goldstein--Gordon Theorem}
Arratia, Goldstein, \& Gordon \cite{ArratiaGoldstein} provide another approach that is sometimes more practical for Poisson approximation.

\begin{thm}[Arratia, Goldstein, \& Gordon \cite{ArratiaGoldstein}]\label{Arratia}
Let $I$ be a countable set of indices and for each $\alpha \in I$ let $X_\alpha$ be an indicator random variable.
Let $\mathbb{X} = (X_\alpha)_{\alpha\in I}$ denote a collection of Bernoulli random variables, and 
let $\mathbb{B} = (B_\alpha)_{\alpha\in I}$ denote a collection of independent Bernoulli random variables with marginal distributions which satisfy $\mathbb{E}\, B_\alpha = \mathbb{E}\, X_\alpha$ for all $\alpha \in I$.  
Define $p_\alpha := \mathbb{E}\, X_\alpha = P(X_\alpha = 1) >0$ and $p_{\alpha\beta} := \mathbb{E}\, X_\alpha X_\beta$.  
Also define $W := \sum_{\alpha \in I} X_\alpha$ and $\lambda := \mathbb{E}\, W = \sum_{\alpha\in I} p_\alpha$.  For each $\alpha \in I$, define sets $D_\alpha \subset I$ (typically, this will be the set of all indices $\beta \in I$ for which $X_\alpha$ and $X_\beta$ are dependent, but this is not necessary) and  the quantities
\begin{align}
\notag 		 b_1 &:= \sum_{\alpha \in I} \sum_{\beta \in D_\alpha} p_\alpha p_\beta, \\
\label{eq:b2} 	 b_2 &:= \sum_{\alpha \in I} \sum_{\alpha \neq \beta\in D_\alpha} p_{\alpha \beta}, \quad\text{and}\\
\notag		 b_3 &:= \sum_{\alpha\in I} \mathbb{E}\, |\mathbb{E}\,\{X_\alpha - p_\alpha \mid \sigma(X_\beta: \beta \notin D_\alpha) \} |.
\end{align}
We have
\[ d_{TV}(\mathcal{L}(\mathbb{X}), \mathcal{L}(\mathbb{B})) \leq 2(2b_1 + 2b_2 + b_3) + 2 \sum_{\alpha \in I} p_\alpha^2. \]
Furthermore, let $Y$ denote a Poisson random variable with mean $\lambda = \mathbb{E}\, W$.  
We have 
\[ d_{TV}(\mathcal{L}(W), \mathcal{L}(Y)) \leq 2(b_1+b_2+b_3), \]
and also 
\[ |P(W = 0) - P(Y=0)| \leq \left(b_1+b_2+b_3\right) \frac{1-e^{-\lambda}}{\lambda}. \]
\end{thm}

In our applications, we are able to define sets $D_\alpha$, $\alpha\in I,$ so that $b_3 = 0$ always holds;
whence, the calculations of the bounds in our theorems require only calculations involving first and second (unconditioned) moments.  
For uniform random permutations this is straightforward, but that the analogous properties hold for consecutive patterns under random Mallows permutations is less obvious. 


\ignore{
\subsection{Example of application}

Perhaps an example using $X_i = \mathbb{I}(\sigma(i) = \sigma(i-1)^2)$, where we take $\sigma(0) \equiv \sigma(n)$.  That is, the number of times a pair of numbers appears of the form $(\ldots, k, k^2, \ldots)$ in a random permutation, where $k = 1,2,\ldots,\lfloor \sqrt{n} \rfloor.$  

For random permutations, the quantity $b_3$ is the most prohibitive to compute.  It is not impossible, but it certainly takes away from the elegance.  An example is given in \cite[Section 4.5]{ArratiaGoldstein}, for permutations with restrictions of a similar form to fixed points.  It should be possible to adapt the argument to more general forms, though at a possibly significant cost of analysis.
}

\ignore{
\subsection{Ideal Example}

The ideal example, for which I am a little less certain now how to fully work out the solution, is as follows:



How many permutations of $[n]$ are there are avoid the pattern $123...(n-1)n$ ?  How many that avoid the pattern $k_1,k_2, \ldots, k_j$?  We can provide an asymptotic enumeration with concrete error bounds for $j = n^a$, for $a>\frac{1}{2}$.  Of particular interest is when $j=3,4$, but  this lies very much outside of the region where a Poisson approximation would hold using our approach.
}



\ignore{
\subsection{Avoidance probabilities for Mallows permutations}
The Mallows distribution \cite{Mallows1957} was introduced as a one-parameter statistical model for rankings that occur in statistical analysis.
An {\em inversion} in $\sigma=\sigma_1\cdots\sigma_n$ is a pair $(i,j)$, $i<j$, such that $\sigma_i>\sigma_j$.
For example, $\sigma=34125$ has four inversions, $(1,3), (1,4), (2,3), (2,4)$.
We write $\mathop{\text{inv}}\nolimits(\sigma)$ to denote the set of inversions of $\sigma$.
For $0<q<\infty$, the {\em Mallows distribution with parameter $q$} on $\mathop{\mathcal{S}_{n}}\nolimits$ assigns probability
\begin{equation}\label{eq:Mallows}
P\{\Sigma_n=\sigma\}=P_n^q(\sigma)=q^{|\mathop{\text{inv}}\nolimits(\sigma)|}/I_n(q),\quad\sigma\in\mathop{\mathcal{S}_{n}}\nolimits,\end{equation}
where $I_n(q)=\prod_{j=1}^n\sum_{i=0}^{j-1}q^i$ and $I_1(q)=1$.
Note that $q=1$ corresponds to the uniform distribution as well as the critical point at which the Mallows family switches from penalizing inversions, $q<1$, to favoring them, $q>1$.
More recently, Mallows permutations have been studied in the context of the longest increasing subsequence problem \cite{AldousDiaconis1999,BaikDeiftJohansson1999,Bhatnagar2014,LoganShepp1977,VershikKerov1977} and {\em quasi}-exchangeable random sequences \cite{GnedinOlshanski2009,GnedinOlshanski2010}.

{\color{blue} Our first main theorem for Mallows permutations is as follows...}
}
\section{Consecutive pattern avoidance of Mallows permutations}\label{section:Mallows}


To fix notation, we write $\sigma=\sigma_1\cdots\sigma_n$ to denote a generic permutation, for which we define the {\em reversal} by $\sigma^r=\sigma_n\cdots\sigma_1$.
For any subset $A\subseteq[n]$, we write $\sigma_{|A}$ to denote the {\em restriction} of $\sigma$ to a permutation of $A$ obtained by removing those elements among $\sigma_1,\ldots,\sigma_n$ that are not in $A$.
For example, with $\sigma=867531924$ and $A=\{1,3,5,7,9\}$, we have $\sigma_{|A}=75319$.
We write $\Sigma_n$ to denote a random permutation of $[n]$.

From \eqref{eq:Mallows} it is apparent that $P_n^q(\sigma)=P_n^{1/q}(\sigma^r)$ for all $\sigma\in\mathop{\mathcal{S}_{n}}\nolimits$, and so we can focus on the case $0<q\leq 1$ in our analysis.


\subsection{Sequential construction}
The Mallows distribution \eqref{eq:Mallows} enjoys several nice properties that are amenable to the study of pattern avoidance.
These properties are readily observed by the following sequential constructions, both of which are well known and have been leveraged in previous studies of the Mallows distribution; see, for example, \cite{Bhatnagar2014,GnedinOlshanski2009}.
While the properties below are well known, we are not aware of their appearance in relation to pattern avoidance.
We provide proofs for completeness.


For $q>0$, we say that random variable $X$ has the {\em truncated Geometric($q$)} distribution on $[n],$ written as $X~\sim~\text{Geometric}(n,q)$ , when the point probabilities of $X$ are given by
\begin{equation}\label{eq:finite-geometric}
P^{n,q}(X=k)=q^{k-1}/(1+\cdots+q^{n-1}),\quad k=1,\ldots,n.
\end{equation}
A Mallows permutation can be generated from the truncated Geometric distribution in two ways, which we call the {\em ordering} and {\em bumping} constructions.

For the ordering construction, we generate $X_1,X_2,\ldots$ independently, with each $X_n$ distributed as $\text{Geometric}(n,1/q)$.
To initialize, we have $\Sigma_1=1$, the only permutation of $[1]$.
Given $\Sigma_n=\sigma_1\cdots\sigma_n$ and $X_{n+1}=k$, we define 
\[\Sigma_{n+1}=\sigma_1\cdots\sigma_{k-1}(n+1)\sigma_k\cdots\sigma_n.\]
For every $n=1,2,\ldots$, it  is apparent that $\Sigma_n$ is a Mallows$(q)$ permutation because the probability that element $n+1$ appears in position $k$ of $\Sigma_{n+1}$ is
\[P\{\Sigma_{n+1}(k)=n+1\}=P^{n+1,1/q}(X=k)=P^{n+1,q}(X=n+1-k)=q^{n+1-k}/(1+q+\cdots+q^n).\]
Since $X_1,\ldots,X_n$ are chosen independently and each event $\{\Sigma_n=\sigma\}$ corresponds to exactly one sequence $X_1,\ldots,X_n$, we observe
\[P\{\Sigma_n=\sigma\}=q^{|\mathop{\text{inv}}\nolimits(\sigma)|}/I_n(q),\quad \sigma\in\mathop{\mathcal{S}_{n}}\nolimits,\]
as in \eqref{eq:Mallows}.

\begin{defn}[Mallows process]\label{defn:Mallows process}
A collection $(\Sigma_n)_{n\geq1}$ generated by the ordering construction for fixed $q>0$ is called a {\em Mallows$(q)$ process}.
\end{defn}

For the bumping construction, we generate $X_1,X_2,\ldots$ independently with each $X_n$ distributed as $\text{Geometric}(n,1/q)$ as before, and again we initialize with $\Sigma_1=1$.
Given $\Sigma_n=\sigma_1\cdots\sigma_n$ and $X_{n+1}=k$, we obtain $\Sigma_{n+1}$ by appending $k$ to the end of $\Sigma_n$ and ``bumping'' all elements of $\Sigma_n$ that are greater or equal to $k$.
More formally, $(\Sigma_n,X_{n+1})\mapsto \Sigma'_1\cdots\Sigma'_nX_{n+1}$, where
\[\Sigma'_j=\left\{\begin{array}{cc} \Sigma_j+1,& \Sigma_j\geq X_{n+1},\\
\Sigma_j,& \text{otherwise.}
\end{array}\right.\]
For example, if $\Sigma_5=24135$ and $X_6=3$, then $\Sigma_{6}=251463$.
Again, the resulting distribution of $\Sigma_n$ is Mallows($q$) because $X_{n+1}=k$ introduces exactly $n+1-k$ new inversions in $\Sigma_{n+1}$ and $X_1,X_2,\ldots$ are generated independently.



\subsection{Properties of Mallows permutations}

Throughout this section, we let $(\Sigma_n)_{n\geq1}$ be a family of random permutations so that each $\Sigma_n$ is a permutation of $[n]$.
We say that $(\Sigma_n)_{n\geq1}$ is {\em consistent} if for all $1\leq m\leq n$
\begin{equation}\label{eq:consistent}
P\{\Sigma_{n|[m]}=\sigma\}=P\{\Sigma_m=\sigma\},\quad\sigma\in\mathop{\mathcal{S}_{m}}\nolimits.
\end{equation}
It is immediate from the ordering construction that the Mallows process $(\Sigma_n)_{n\geq1}$ is consistent for every $q>0$.

Recall the reduction map described in Section \ref{section:intro}.
We call $(\Sigma_n)_{n\geq1}$ {\em homogeneous} if for all $1\leq m\leq n$ and every subsequence $1\leq i_1<\cdots<i_m\leq n$
\begin{equation}\label{eq:homo}
P\{\mathop{\text{red}}\nolimits(\Sigma_{n}(i_1)\cdots\Sigma_{n}(i_m))=\sigma\}=P\{\Sigma_m=\sigma\},\quad\sigma\in\mathop{\mathcal{S}_{m}}\nolimits.
\end{equation}
We call $(\Sigma_n)_{n\geq1}$ {\em consecutively homogeneous} if \eqref{eq:homo} holds only for consecutive subsequences $i_1, i_1+1,\ldots,i_1+m-1$.

\begin{lemma}\label{lemma:homo}
The Mallows($q$) process is consecutively homogeneous for all $q>0$ and homogeneous for $q=1$.
\end{lemma}

\begin{proof}
The $q=1$ case corresponds to the uniform distribution, which is well known to be homogeneous.
For arbitrary $q>0$, consider the event $\{\mathop{\text{red}}\nolimits(\Sigma_{n}(j)\cdots\Sigma_{n}(j+m-1))=\sigma\}$ for some $\sigma\in\mathop{\mathcal{S}_{n}}\nolimits$.
By the ordering construction, we can first generate $\Sigma_m=\Sigma_{m}(1)\cdots\Sigma_{m}(m)$ from the Mallows($1/q$) distribution on $[m]$.
We then obtain $\Sigma_{m+j-1}$ from $\Sigma_m$ using the bumping construction for Mallows($1/q$) distribution.
Thus, we have $\Sigma_{m+j-1}\sim\text{Mallows}(1/q)$ and its reversal $\Sigma_{m+j-1}^r\sim\text{Mallows}(q)$ with $\mathop{\text{red}}\nolimits(\Sigma^r_{m+j-1}(j)\cdots\Sigma^r_{m+j-1}(m+j-1))=\Sigma_m(m)\cdots\Sigma_m(1)\sim\text{Mallows}(q)$.
Finally, we obtain $\Sigma_n$ by adding to $\Sigma_{m+j-1}^r$ according to the bumping construction, so that 
\[\mathop{\text{red}}\nolimits(\Sigma_{n}(j)\cdots\Sigma_{n}(m+j-1))=\mathop{\text{red}}\nolimits(\Sigma_{m+j-1}^r(j)\cdots\Sigma^r_{m+j-1}(m+j-1))=\Sigma_m(m)\cdots\Sigma_m(1)\sim\text{Mallows}(q).\]
This completes the proof.
\end{proof}

We say that $\Sigma_n$ is {\em dissociated} if $\Sigma_{n|A}$ and $\Sigma_{n|B}$ are independent for all non-overlapping subsets $A,B\subseteq[n]$.
If, instead, $\Sigma_{n|A}$ and $\Sigma_{n|B}$ are independent only when $A$ and $B$ are disjoint and each consists of consecutive indices, then we call $\Sigma_n$ {\em weakly dissociated}.

\begin{lemma}\label{lemma:dissociated}
For all $n\geq1$, the Mallows($q$) distribution on $\mathop{\mathcal{S}_{n}}\nolimits$ is weakly dissociated for all $q>0$ and dissociated for $q=1$.
\end{lemma}

\begin{proof}
For $i'>i\geq1$ and $m,m'\geq0$ satisfying $i+m-1<i'$ and $i'+m'-1\leq n$, let $A=\{i,i+1,\ldots,i+m-1\}$ and $B=\{i',i'+1,\ldots,i'+m'-1\}$.
For any $n\geq1$, we can construct a Mallows($q$) permutation of $[n]$ by first generating $\Sigma_{i+m-1}$, for which we know that $\mathop{\text{red}}\nolimits(\Sigma_{i+m-1}(i)\cdots\Sigma_{i+m-1}(i+m-1))\sim\text{Mallows}(q)$ by Lemma \ref{lemma:homo}.
We then construct $\Sigma_n$ from $\Sigma_{i+m-1}$ by the bumping construction.
Since bumping does not affect the reduction of any part of $\Sigma_{n}(1)\cdots\Sigma_{n}(i+m-1)$, we have
\begin{eqnarray*}
\lefteqn{P\{\mathop{\text{red}}\nolimits(\Sigma_{n}(i)\cdots\Sigma_{n}(i+m-1))=\sigma\mid\mathop{\text{red}}\nolimits(\Sigma_{n}(i')\cdots\Sigma_{n}(i'+m'-1))=\sigma'\}=}\\
&=&
P\{\mathop{\text{red}}\nolimits(\Sigma_{i+m-1}(i)\cdots\Sigma_{i+m-1}(i+m-1))=\sigma\mid\mathop{\text{red}}\nolimits(\Sigma_{n}(i')\cdots\Sigma_{n}(i'+m'-1))=\sigma'\}\\
&=&P\{\Sigma_{m}(1)\cdots\Sigma_{m}(m)=\sigma\},
\end{eqnarray*}
proving that $\Sigma_n$ is weakly dissociated.
Dissociation of the uniform distribution ($q=1$) is well known and so we omit its proof.
The proof is complete.
\end{proof}


Together, the above properties facilitate study of consecutive pattern avoidance for Mallows permutations with arbitrary $q>0$.
For example, the pattern $231$ has probability $q^2/(1+2q+2q^2+q^3)$ to occur in any stretch of three consecutive positions of a Mallows($q$) permutation.
Since there are $n-2$ consecutive patterns of length 3 in a permutation of $[n]$, the expected number of occurrences is $(n-2)q^2/(1+2q+2q^2+q^3)$.
For large $n$ and small $q$, this expected value behaves asymptotically as $nq^2$, so that taking $q\sim1/\sqrt{n}$ gives an expected number on the order of a constant.
 When $q$ is large, the expected number of occurrences behaves as $n q^{-1}$ for large $n$, and taking $q\sim n$ gives an expected number on the order of a constant.





\subsection{Poisson convergence theorems}

Theorem \ref{main:mallows:theorem} and its corollary follow by combining the above properties of Mallows permutations with Theorem~\ref{Arratia}.
The calculations and resulting bounds for the general Mallows measure follow the same program as the uniform case proven in Section \ref{section:proofs}, with the key distinction that we only consider {\em consecutive} patterns for the general Mallows distribution.  
Unlike the uniform setting, the bounds for the Mallows distribution depend non-trivially on the parameter $q$ and the structure of $\tau$.
It is more fruitful to illustrate this dependence with specific examples than to regurgitate the same proof for Mallows permutations.


\subsubsection{Monotonic patterns under Mallows distribution}\label{section:monotonic}
 
Consider the set of permutations that avoid the pattern 123.  There are no inversions, and the size of the pattern is $3$; thus, the probability of seeing this pattern in any given set of three consecutive indices of a Mallows($q$) permutation is $1/I_3(q)$.  
We also need to consider second moments, i.e., the probability of seeing two 123 patterns.  
By Lemma~\ref{lemma:dissociated} we need only consider overlapping sets of indices.
There are two cases, either two indices overlap or one does. 
If two indices overlap and the first three and last three both reduce to pattern 123, then the segment must reduce to 1234.
Similarly, if one index overlaps, then the segment must reduce to 12345.

The results below extend this notion to monotonic patterns. 

\begin{lemma}
Fix $q>0$ and let $\Sigma_n\sim\text{Mallows}(q)$.
For each $m \geq 1$, let $\tau_m$ denote the pattern $12\cdots m$.  
For each $\alpha \in J_m$, define
\[ X_\alpha = \mathbb{I}(\mathop{\text{red}}\nolimits(\Sigma_{n|\alpha})=\tau_m). \]
For a random permutation generated using the Mallows measure, we have
\[ \mathbb{E}\, X_\alpha = \frac{1}{I_m(q)},  \qquad \alpha \in J_m, \]
and for $\alpha, \beta \in J_m$, $\alpha \neq \beta$, we have
\[ \mathbb{E}\, X_\alpha X_\beta = 
\begin{cases} 
	\frac{1}{I_m(q)^2} & \text{$\alpha, \beta$ have no overlapping elements} \\
	\frac{1}{I_{2m-s}(q)} & \text{$\alpha, \beta$ have exactly $s$ overlapping elements, $s = 1, 2, \ldots, m-1$.}
\end{cases}
\]
\end{lemma}

\begin{proof}
The expression when $\alpha$ and $\beta$ do not overlap is a consequence of the weak dissociation property of Mallows permutations (Lemma \ref{lemma:dissociated}), whereby
\[\mathbb{E}\, X_{\alpha}X_{\beta}=\mathbb{E}\, X_{\alpha} \mathbb{E}\, X_{\beta} = P\{\mathop{\text{red}}\nolimits(\Sigma_{n|\alpha})=\tau_m\}^2=(1/I_m(q))^2.\]
When $\alpha$ and $\beta$ overlap in $s$ elements, the event $\{X_{\alpha}=X_{\beta}=1\}$ requires that both $\Sigma_{n|\alpha}$ and $\Sigma_{n|\beta}$ reduce to the increasing permutation, which can occur only if $\Sigma_{n|\alpha\cup\beta}$ reduces to the increasing permutation of $2m-s$.
\end{proof}

\begin{prop}\label{prop:increasing}
Fix $q>0$ and let $\Sigma_n\sim\text{Mallows}(q)$.
For any $m \geq 2$,
let $\tau_m$ be the increasing pattern $12\cdots m$.  
For any $\alpha \in J_m$, let
\[ X_\alpha = \mathbb{I}(\mathop{\text{red}}\nolimits(\Sigma_{n|\alpha})=\tau_m). \]
Let $W = \sum_{\alpha \in J_m} X_\alpha$ and let $Y$ be an independent Poisson random variable with expected value $\lambda = \mathbb{E}\, W$.  
Then
\[ d_{TV}(\mathcal{L}(W), \mathcal{L}(Y)) \leq 2(b_1+b_2), \]
where
\begin{align}
\notag \lambda&=\frac{n-m}{I_m(q)}, \qquad 
 b_1 = \frac{n_1}{I_m(q)^2}, \qquad 
 b_2  =n_2 \sum_{s=1}^{m-1}\frac{1}{I_{2m-s}(q)},
\end{align}
 and $n_1$ and $n_2$ are given by
 \begin{align}
\notag n_1 &= 2 m n- 3 m^2+m, \quad\text{and}\\
\label{mono n2} n_2 &= 3 m - 3 m^2 - 2 n + 2 m n.
 \end{align}
\end{prop}
\begin{proof}
When $2m-1 \leq n$, we have $n_1 = 2\sum_{s=1}^m (n-2m+s) = 2 m n- 3 m^2+m$, and similarly $n_2 = 2\sum_{s=1}^{m-1}(n-2m+s) = 3 m - 3 m^2 - 2 n + 2 m n.$  The factor of $2$ is from exchanging the role of $\alpha, \beta$.
When $2m-1 > n$, the stated expressions for $n_1$ and $n_2$ are still valid upper bounds, but they can be slightly improved.
\ignore{
The justification for the formula for $n_2$ is as follows. 
The $m$-tuples $\{i, i+1, \ldots, i+m-1\}$, $i=1,\ldots, m-1$, can have $m-1$ overlapping indices to the right and $i-1$ overlapping indices on the left.  Hence, summing over all $i=1,\ldots, m-1$, the number of overlapping pairs of indices for these first $m-1$ elements is
\[ (m-1+0) + (m-1+1) + \ldots + (m-1 + m-2). \]
By symmetry, the same is true for the last $m-1$ elements.  When $n\geq 2(m-1)$, there are $n-2(m-1)-m$ elements in between, each with $2(m-1)$ possible overlapping pairs on either side (i.e., no restrictions due to the boundary); whence, the total number of possible pairs of overlapping $m$-tuples is given by
\[ 2\left( (m-1)(m-1) + \frac{(m-1)(m-2)}{2}\right) + 2(m-1)(n-2(m-1)-m), \]
which simplifies to the expression in~\eqref{mono n2}.
 In case $n < 2(m-1)$, $b_2$ is still an upper bound, and one can simply work out the more efficient enumeration to obtain a slightly better bound.  

The justification for the formula for $n_1$
is similar, except we are allowed to have all $m$-tuples overlap.  Thus, the number of overlapping pairs of indices for the first $m-1$ elements is
\[ (m-1+1) + (m-1+2) + \ldots + (m-1 + m-1), \]
and similarly for the last $m-1$ elements.  
There are $n-2(m-1)-m$ elements in between, each with $m-1 + m$ possible overlapping pairs on either side (including one where the overlap is over all $m$ elements).
}
\end{proof}

In addition, it is easy to state the complementary result about the decreasing pattern $m\cdots 21$.

\begin{prop}\label{prop:decreasing}
Fix $q>0$ and let $\Sigma_n\sim\text{Mallows}(q)$.
For any $m \geq 2$,
let $\eta_m$ be the decreasing pattern $m\cdots 21$.
For any $\alpha \in J_m$, let
\[ X_\alpha = \mathbb{I}(\mathop{\text{red}}\nolimits(\Sigma_{n|\alpha})=\eta_m). \]
Let $W = \sum_{\alpha \in J_m} X_\alpha$ and let $Y$ denote an independent Poisson random variable with expected value $\lambda = \mathbb{E}\, W$.  
Then
\[ d_{TV}(\mathcal{L}(W), \mathcal{L}(Y)) \leq 2(b_1+b_2), \]
where
\begin{align*}
\lambda&= (n-m)\frac{q^{{m\choose2}}}{I_m(q)}, \qquad 
 b_1 = \frac{n_1\ q^{\binom{m}{2}}}{I_m(q)^2}, \qquad
 b_2 = n_2\ \sum_{s=1}^{m-1} \frac{q^{\binom{2m-s}{2}}}{I_{2m-s}(q)}, 
\end{align*}
 and $n_1$ and $n_2$ are given by
 \begin{align*}
\notag n_1 &= 2 m n- 3 m^2+m, \quad\text{and}\\
\label{mono n2} n_2 &= 3 m - 3 m^2 - 2 n + 2 m n.
 \end{align*}
\end{prop}

\ignore{The approach in Propositions \ref{prop:increasing} and \ref{prop:decreasing} generalizes to arbitrary patterns $\tau\in\mathop{\mathcal{S}_{m}}\nolimits$, except that we cannot compute a useful bound $b_2$ that applies to all patterns; we must take the structure of $\tau$ into account.
We discuss this aspect further in Section \ref{section:improved}.
We note that the bounds for non-monotonic patterns $\tau\in\mathop{\mathcal{S}_{m}}\nolimits$ are most useful when we allow $q\equiv q(n)$ to depend on $n$ so that either $q\sim n^{-1/|\mathop{\text{inv}}\nolimits(\tau)|}$ or $q\sim n^{1/({m\choose2}-|\mathop{\text{inv}}\nolimits(\tau)|)}$ as $n\rightarrow\infty$.
}

\ignore{
Alternatively, we can choose $m(n)\equiv m$ to be an increasing function of $n$ so that the number of inversions in the sequence $\tau_m\in\mathop{\mathcal{S}_{m}}\nolimits$ grows as

\[\begin{tabular}{lll}
$|\mathop{\text{inv}}\nolimits(\tau_m)|$& $\sim -\log(n)/\log(q)$& \quad\text{for $q<1$ and}\\
$|\mathop{\text{inv}}\nolimits(\tau_m)|$& $\sim -\log(n)/\log(q)+m^2/2$& \quad \text{for $q>1$}.
\end{tabular}\]

We demonstrate these regimes further in Section \ref{section:cases}.
}

\subsubsection{Other patterns of length 3}\label{section:3}
We now demonstrate the dependence of the total variation bound on $q$ for the small patterns 132, 213, 231, and 312.
 In this section, we again recall that $\overline{\Gamma}_m$ denotes the set of all $m$-tuples with consecutive elements in $\{1,2,\ldots, n\}$, and for a given $\alpha \in \overline{\Gamma}_3$, $X_\alpha$  denotes the indicator random variable defined in \eqref{eq:indicator}.

For $\tau=132$, we have $\mathbb{E}\, X_\alpha = {q}/{I_3(q)}$, and there can be no consecutive occurrences of $\tau$ that overlap with two indices.  The only possible ways in which we can have one overlapping index are the patterns 13254, 15243, and 14253.  In these cases, we have
\[ \lambda  = \frac{(n-3)\, q}{I_3(q)}\quad\text{and} \]
\[ 
\mathbb{E}\, X_\alpha X_\beta = \frac{1}{I_5(q)}\times \begin{cases}
q^2, & 13254, \\
q^3, & 14253, \\
q^4, & 15243.
\end{cases}
\]
Letting $W = \sum_{\alpha \in \overline{\Gamma}_3} \mathbb{E}\, X_\alpha$  and defining $Y$ as an independent Poisson random variable with expectation $\lambda = \mathbb{E}\, W = {(n-3)\, q}/{I_3(q)}$, the total variation distance bound is given by
\[ d_{TV}(\mathcal{L}(W), \mathcal{L}(Y)) \leq 2\left( (3n-13)\, \frac{q^2}{I_3(q)^2} + 2(n-5)\, \frac{q^2+q^3+q^4}{I_5(q)}\right). 
\]
The $2(n-5)$ term comes from the 2 sets of triplets $\{1,2,3\}$ and $\{2,3,4\}$ for which the overlapping pair can only occur to the right of the elements, and similarly from the 2 sets of triplets $\{n-2, n-1, n\}$ and $\{n-3, n-2, n-1\}$ for which the overlapping pair can only occur to the left of the elements, and finally the $(n-4-3)$ triplets in between for which the overlapping pairs are both to the left and the right; hence $2+2(n-7)+2 = 2(n-5)$. 
Similarly, the $3n-13$ comes from $2\cdot2 + 3(n-7) + 2\cdot 2$.  
Let $t>0$ be fixed.  If $q \sim t\, n^{-1}$ or $q \sim t\, n^{1/2}$, we have $\lambda \to t$, and $d_{TV}(\mathcal{L}(W), \mathcal{L}(Y)) = O(n^{-1}).$  


For $\tau=213$, we similarly have 
\begin{align*}
\lambda & = \frac{(n-3)\, q}{I_3(q)}, \\
\mathbb{E}\, X_\alpha X_\beta & =
\frac{1}{I_5(q)}\times \begin{cases}
{q^2}, & 21435, \\
{q^3}, & 31425, \\
{q^4}, & 32415,
\end{cases}\quad \text{and} \\
d_{TV}(\mathcal{L}(W), \mathcal{L}(Y)) & \leq 2\left( (3n-13)\, \frac{q^2}{I_3(q)^2} + 2(n-5)\, \frac{q^2+q^3+q^4}{I_5(q)}\right),
\end{align*}
and $q \sim t\,n^{-1}$ or $q \sim t\,n^{1/2}$ implies $\lambda \to t$ and $d_{TV}(\mathcal{L}(W), \mathcal{L}(Y)) = O(n^{-1}).$  

For $\tau= 231$:
\begin{align*}
\lambda & = \frac{(n-3)\, q^2}{I_3(q)}, \\
\mathbb{E}\, X_\alpha X_\beta & = \frac{1}{I_5(q)}\times\begin{cases}
{q^6}, & 34251, \\
{q^7}, & 35241, \\
{q^8}, & 45231,
\end{cases} \quad\text{and}\\
d_{TV}(\mathcal{L}(W), \mathcal{L}(Y)) & \leq 2\left( (3n-13)\, \frac{q^4}{I_3(q)^2} + 2(n-5)\, \frac{q^6+q^7+q^8}{I_5(q)}\right), 
\end{align*}
and $q \sim t^{1/2} n^{-1/2}$ or $q \sim n\, t^{1/2}$ implies $\lambda \to t$ and $d_{TV}(\mathcal{L}(W), \mathcal{L}(Y)) = O(n^{-1}).$  

And finally for $\tau= 312$:
\begin{align*}
\lambda & = \frac{(n-3)\, q^2}{I_3(q)}, \\
\mathbb{E}\, X_\alpha X_\beta & = \frac{1}{I_5(q)}\times\begin{cases}
{q^6}, & 51423, \\
{q^7}, & 52413, \\
{q^8}, & 53412,
\end{cases}\quad\text{and} \\
d_{TV}(\mathcal{L}(W), \mathcal{L}(Y)) & \leq 2\left( (3n-13)\, \frac{q^4}{I_3(q)^2} + 2(n-5)\, \frac{q^6+q^7+q^8}{I_5(q)}\right), 
\end{align*}
and $q \sim t^{1/2}\, n^{-1/2}$ or $q \sim n\,t^{1/2}$ implies $\lambda \to t$ and $d_{TV}(\mathcal{L}(W), \mathcal{L}(Y)) = O(n^{-1}).$  


\section{Numerical examples}\label{section:cases}

\subsection{Numerical values}


Using Theorem~\ref{theorem:main}, we can estimate $|\mathop{\mathcal{S}_{n}}\nolimits(\tau)|$ for various sizes of patterns $\tau$.  Table~\ref{table:bounds} shows the lower bound thresholds for various values of $n$ and patterns of size $j$.  
Similarly, using Theorem~\ref{consecutive patterns}, we estimate $|\mathop{\overline{\mathcal{S}}_{n}}\nolimits(\tau)|$ in Table~\ref{table:consecutive:bounds}.
In the case of $n = 1000$ and $j = 133$, we have more specifically $3.4433\times 10^{2567} \leq |\mathop{\mathcal{S}_{n}}\nolimits(\tau)| \leq 4.0239\times 10^{2567}$.

\begin{table}[t]
\begin{tabular}{llll}
$n$ & $j$ & lower & $n!$ \\\hline
 100 & 36 & $6.85456\times 10^{157}$ & $9.3326\times 10^{157}$ \\
 1000 & 133 & $3.4433\times 10^{2567}$ & $4.6045\times 10^{2567}$ \\
 10000 & 442 & $8.3847\times 10^{35658}$ & $2.8463\times 10^{35659}$ \\
 100000 & 14353 & $9.9451\times 10^{65657058}$ & $1.2024\times 10^{65657059}$
\end{tabular}
\caption{Bounds on $|\mathop{\mathcal{S}_{n}}\nolimits(\tau)|$ for $\tau \in \mathop{\mathcal{S}_{j}}\nolimits$, for various values of $n$ and $j$.}
\label{table:bounds}
\end{table}

\begin{table}[t]
\begin{tabular}{llll}
$n$ & $j$ & lower & $n!$ \\\hline
100      & 6  & $3.98735\times 10^{157}$ & $9.33262\times 10^{157}$ \\
1000    & 7  & $5.77948\times 10^{2566}$ & $4.02387\times 10^{2567}$ \\
10000  & 9  & $2.49966\times 10^{35659}$ & $2.84626\times 10^{35659}$ \\
100000 & 10 & $2.48004\times 10^{456573}$ &$2.82423\times 10^{456573}$ \\
1000000 &11 & $7.34802\times 10^{5565708}$ &$8.26393\times 10^{5565708}$
\end{tabular}
\caption{ Bounds on $|\mathop{\overline{\mathcal{S}}_{n}}\nolimits(\tau)|$ for $\tau \in \mathop{\mathcal{S}_{j}}\nolimits$, for various values of $n$ and $j$.}
\label{table:consecutive:bounds}
\end{table}

\ignore{
\begin{table}[t]
\begin{tabular}{lllll}
$n$ & $j$ & lower & upper & $n!$ \\\hline
 100 & 36 & $6.85456\times 10^{157}$ & $1.18107\times 10^{158}$ & $9.3326\times 10^{157}$ \\
 1000 & 133 & $3.4433\times 10^{2567}$ & $4.0239\times 10^{2567}$ & $4.6045\times 10^{2567}$ \\
 10000 & 442 & $8.3847\times 10^{35658}$ & $4.8540\times 10^{35659}$ & $2.8463\times 10^{35659}$ \\
 100000 & 14353 & $9.9451\times 10^{65657058}$ & $1.4103\times 10^{65657059}$ & $1.2024\times 10^{65657059}$
\end{tabular}
\caption{Bounds on $|\mathop{\mathcal{S}_{n}}\nolimits(\tau)|$ for $\tau \in \mathop{\mathcal{S}_{j}}\nolimits$, for various values of $n$ and $j$.}
\label{table:bounds}
\end{table}

\begin{table}[t]
\begin{tabular}{lllll}
$n$ & $j$ & lower & upper & $n!$ \\\hline
100      & 6  & $3.98735\times 10^{157}$ & $1.23934\times 10^{158}$ & $9.33262\times 10^{157}$ \\
1000    & 7  & $5.77948\times 10^{2566}$ & $6.03063\times 10^{2567}$ & $4.02387\times 10^{2567}$ \\
10000  & 9  & $2.49966\times 10^{35659}$ & $3.03827\times 10^{35659}$ & $2.84626\times 10^{35659}$ \\
100000 & 10 & $2.48004\times 10^{456573}$& $3.01491\times 10^{456573}$ &$2.82423\times 10^{456573}$ \\
1000000 &11 & $7.34802\times 10^{5565708}$ & $8.77094\times 10^{5565708}$ &$8.26393\times 10^{5565708}$
\end{tabular}
\caption{ Bounds on $|\mathop{\overline{\mathcal{S}}_{n}}\nolimits(\tau)|$ for $\tau \in \mathop{\mathcal{S}_{j}}\nolimits$, for various values of $n$ and $j$.}
\label{table:consecutive:bounds}
\end{table}



\begin{figure}
\[
\left(
\begin{array}{lllll}
n & j & lower & upper & n! \\
 100 & 36 & 6.85456\times 10^{157} & 1.18107\times 10^{158} & 9.3326\times 10^{157} \\
 1000 & 133 & 3.4433\times 10^{2567} & 4.0239\times 10^{2567} & 4.6045\times 10^{2567} \\
 10000 & 442 & 8.3847\times 10^{35658} & 4.8540\times 10^{35659} & 2.8463\times 10^{35659} \\
 100000 & 14353 & 9.9451\times 10^{65657058} & 1.4103\times 10^{65657059} & 1.2024\times 10^{65657059}
\end{array}
\right)
\]
\caption{Bounds on $|\mathop{\mathcal{S}_{n}}\nolimits(\tau)|$ for $\tau \in \mathop{\mathcal{S}_{j}}\nolimits$, for various values of $n$ and $j$. 
}
\label{table:bounds}
\end{figure}

\begin{figure}
\[
\left(
\begin{array}{lllll}
n & j & lower & upper & n! \\
100      & 6  & 3.98735\times 10^{157} & 1.23934\times 10^{158} & 9.33262\times 10^{157} \\
1000    & 7  & 5.77948\times 10^{2566} & 6.03063\times 10^{2567} & 4.02387\times 10^{2567} \\
10000  & 9  & 2.49966\times 10^{35659} & 3.03827\times 10^{35659} & 2.84626\times 10^{35659} \\
100000 & 10 & 2.48004\times 10^{456573}&3.01491\times 10^{456573}&2.82423\times 10^{456573} \\
1000000 &11 & 7.34802\times 10^{5565708}&8.77094\times 10^{5565708}&8.26393\times 10^{5565708}
\end{array}
\right)
\]
\caption{ Bounds on $|\mathop{\overline{\mathcal{S}}_{n}}\nolimits(\tau)|$ for $\tau \in \mathop{\mathcal{S}_{j}}\nolimits$, for various values of $n$ and $j$. 
}
\label{table:consecutive:bounds}
\end{figure}
}








\subsection{Detailed illustration for the patterns 2341 and 23451}\label{section:detailed}

Propositions \ref{prop:increasing} and \ref{prop:decreasing} give an expression for the total variation bound between the number of occurrences of the increasing and decreasing patterns and an independent Poisson random variable.
In principle, these bounds can be computed exactly for any pattern by way of the Arratia--Goldstein--Gordon theorem (Theorem \ref{Arratia}); we need only compute the quantities $b_1$, $b_2$, and $b_3$ as in Theorem \ref{Arratia}.

By Lemma \ref{lemma:dissociated}, all Mallows($q$) permutations are weakly dissociated and, therefore, $b_3\equiv0$ for all patterns in the case of consecutive pattern avoidance.
For any pattern $\tau$, homogeneity of the Mallows measure implies $p_{\alpha}=q^{|\mathop{\text{inv}}\nolimits(\tau)|}/I_m(q)$ for all $\alpha,$ and so $b_1$ is easy to compute.
The only complication involves the consideration of overlapping patterns in the calculation of $b_2$.
We cannot provide anything more general than Arratia--Goldstein--Gordon for arbitrary patterns; instead, we compute these bounds in the special cases of $\tau=2341$ and $\tau=23451$.
Figure \ref{figure:plots} shows the performance of these bounds at the critical values $q\sim n^{-1/3}$ and $q\sim n^{1/3}$ for $\tau=2341,$ and $q\sim n^{-1/4}$ and $q\sim n^{1/6}$ for $\tau=23451$.

\begin{figure}[t]
	\centering
		\includegraphics[width=0.8\textwidth]{plot-2341-23451-largesmall.pdf}
	\caption{ Plot of pattern avoidance probabilities of Mallows($q$) distribution for: (top left)  pattern $\tau=2341$ with $q=n^{-1/3}$; (top right) pattern $\tau=23451$ with $q=n^{-1/4}$; (bottom left) pattern $\tau=2341$ with $q=n^{1/3}$; and (bottom right) pattern $\tau=23451$ with $q=n^{1/6}$.
The dashed lines represent the upper and lower error bounds from the Arratia--Goldstein--Gordon theorem, and the solid line represent their average, i.e., the heuristic approximation.
In all panels, the horizontal axis is on the logarithmic scale with base 10.}
	\label{figure:plots}
\end{figure}

\begin{figure}[t]
\includegraphics[width=0.4\textwidth]{plot-2341-unif.pdf}
\includegraphics[width=0.4\textwidth]{plot-23451-unif.pdf}
\caption{ Plot of lower and upper bounds on pattern avoidance probabilities of uniform distribution ($q=1$) for: (left)  pattern $\tau=2341$; (right) pattern $\tau=23451$.}
	\label{figure:plots2}
\end{figure}

\subsubsection{The pattern $2341$}


\begin{table}[t]
\begin{tabular}{c|c||c|c}
permutation & no.\ inversions & permutation & no.\ inversions \\\hline
3452671 & 9 & 3462571 & 10 \\
3472561 & 11 & 3562471 & 11 \\
3572461 & 12 & 4562371 & 12\\
4572361 & 13 & 3672451 & 13\\
4672351 & 14 & 5672341 & 15
\end{tabular}
\caption{List of all permutations that have pattern 2341 in overlapping positions along with the number of inversions.}\label{2341}
\end{table}
For $\tau=2341$, we have $p_{\alpha}=q^{3}/I_4(q)$ and $b_1=(n-4)q^3/I_4(q)$.
The structure of $\tau$ only permits overlap with the first or last position.
Table \ref{2341} lists all permutations that have pattern 2341 in the first 4 and last 4 positions.  These are the only permutations that contribute to $b_2$ in the bound of Theorem \ref{Arratia}.
We assume $n\geq7$.
For positions $5,\ldots,n-5$, each of these overlapping patterns can occur twice; otherwise, the patterns occur only once for a total of $2(n-8)+8 = 2n-8$ possibilities.
There are $6(n-8)+2(5+4+3)=6n-24$ overlapping patterns $\alpha$ and $\beta$ that contribute to $b_1$.
Thus,
\begin{align*}
\lambda&=(n-4)q^3/I_4(q),\\
b_1&=(6n-24)q^{6}/I_4(q)^2,\quad\text{and}\\
b_2&=(2n-8)q^{9}(1+q+2q^{2}+2q^{3}+2q^{4}+q^{5}+q^{6})/I_7(q),
\end{align*}
producing the bounds
\[e^{-\lambda}-(b_1+b_2)\frac{1-e^{-\lambda}}{\lambda}\leq P(W=0)\leq e^{-\lambda} + (b_1+b_2)\frac{1-e^{-\lambda}}{\lambda}.\]




\subsubsection{The pattern $23451$}

\begin{table}[t]
\begin{tabular}{c|c||c|c||c|c}
permutation & no.\ inversions & permutation & no.\ inversions & permutation & no.\ inversions\\\hline
345627891 & 12 & 347825691 & 16 & 456923781 & 18\\
345726891 & 13 & 347925681 & 17 & 467823591 & 19 \\
345826791 & 14 & 348925671 & 18 & 467923581 & 20 \\
345926781 & 15 & 357824691 & 17 &468923571 & 21 \\
346725891 & 14 & 357924681 & 18 & 567823491 & 20\\
346825791 & 15 & 358924671 & 19 & 567923481 & 21\\
346924781 & 16 & 367824591 & 18 & 568923471 & 22 \\
356724891 & 15 & 367924581 & 19 & 378924561 & 21 \\
356824781 & 16 & 368924571 & 20 &  478923561 & 22\\
356924781 & 17 & 457823691 & 18 & 578923461 & 23 \\
456723891 & 16 & 457923681 & 19 & 678923451 & 24\\
456823791 & 17 & 458923671 & 20 &  &\\
\end{tabular}
\caption{List of all permutations that have pattern 23451 in overlapping positions along with the number of inversions.}
\label{23451}
\end{table}

For $\tau=23451$, we have $p_{\alpha}=q^{4}/I_5(q)$ and $b_1=(n-5)q^4/I_5(q)$.
The structure of $\tau$ only permits overlap with the first or last position.
Table \ref{23451} lists all permutations that have pattern 23451 in the first 5 and last 5 positions.  These are the only permutations that contribute to $b_2$ in the bound of Theorem \ref{Arratia}.
We assume $n\geq9$.
For positions $5,\ldots,n-5$, each of these overlapping patterns can occur twice; otherwise, the patterns occur only once for a total of $2(n-10)+10 = 2n-10$ possibilities.
There are $8(n-10)+2(7+6+5+4)=8n-36$ overlapping patterns $\alpha$ and $\beta$ that contribute to $b_1$.
Thus,
\begin{align*}
\lambda&=(n-5)q^4/I_5(q),\\
b_1&=(8n-36)q^{8}/I_5(q)^2,\quad\text{and}\\
b_2&=(2n-10)q^{12}(1+q+2q^{2}+3q^{3}+4q^{4}+4q^{5}+5q^{6}+4q^{7}+4q^{8}+3q^{9}+2q^{10}+q^{11}+q^{12})/I_9(q),
\end{align*}
producing the bounds
\[e^{-\lambda}-(b_1+b_2)\frac{1-e^{-\lambda}}{\lambda}\leq P(W=0)\leq e^{-\lambda} + (b_1+b_2)\frac{1-e^{-\lambda}}{\lambda}.\]











\section{Proofs}\label{section:proofs}

\subsection{Bounds on $p_\alpha$ and $p_{\alpha\beta}$}
We first prove several lemmas, from which the theorems follow.
By the homogeneity property of uniform permutations  we have
\[p_\alpha = \mathbb{E}\, X_\alpha = {1}/{j!}\quad\text{for all }\alpha\in\Gamma_j.\] 
To calculate the Poisson rate $\lambda$, we use linearity of expectation:
there are $\binom{n}{j}$ possible $j$-tuples of elements in $[n]$, and so the expected number of subsets of $j$ elements that reduce to the pattern $k_1k_2\cdots k_j$ is
\[ \lambda = |\Gamma_j|\, p_\alpha = \binom{n}{j}/j!.\]

\ignore{
\begin{prop}
If we assume that $j \sim n^a$ for some $\frac{1}{2} < a \leq 1$, then $\lambda \to 0$ as $n\to\infty$.  Furthermore, if $j \sim \sqrt{n} - \log(\sqrt{n}) + C$, $C>0$, then $\lambda \to \frac{1}{2\pi} e^C$.  
\end{prop}
\begin{proof}
The proof is a trivial calculation by Stirling's asymptotic formula for the factorial, since both $n$ and $j$ tend to infinity.
\end{proof}
}

Next, we consider the joint expectation $p_{\alpha\beta} = \mathbb{E}\, X_\alpha X_\beta.$
\begin{lemma}\label{lemma:pab}
Fix $\alpha,\beta\in\Gamma_j$ and let $s=1,\ldots, j-1$ denote the number of elements that $\alpha, \beta$ have in common.
 For any such pair $\alpha, \beta$, we have
\begin{equation}\label{pab}
 p_{\alpha\beta} \le \frac{s!}{j!^2}.
\end{equation}
\end{lemma}
\begin{proof}
First we condition on $X_\alpha$, which contributes a factor of $1/j!$.  
By conditioning on $X_{\alpha}$, we assume that the $s$ common elements are in their proper order with respect to $X_\beta$.  It may so happen that, conditional on $X_\alpha$, no such event can occur, which justifies the inequality. 

Consider first $s = j-1$, i.e., condition on $j-1$ of the entries being in their proper order.  
Assuming that it is possible to realize both events simultaneously, the remaining element has probability $1/j$ of appearing in its correct order. 

Consider, for general $s$, conditional on $s$ entries being in their proper order, the probability that the remaining $j-s$ elements appear in their proper order is then $((s+1) (s+2)\cdots j)^{-1}$.  
\end{proof}





\ignore{
For each $\alpha \in \Gamma_j$, let $D_\alpha$ be the set of all $j$-element subsets of $[n]$ that overlap with $\alpha$ in at least one but not all elements, i.e.,
\[D_{\alpha}:=\{\beta\in\Gamma_j:\,\beta\cap\alpha\neq\emptyset\}\setminus\{\alpha\}.\]
  For example, if $\alpha = \{1, 5, 8\}$, then $D_{\alpha}^c = \{ \{j_1, j_2, j_3\} : j_i \notin\{1,5,8\}, i=1,2,3\}\cup\{\{1,5,8\}\}.$  
}





\subsection{Proof of Theorem~\ref{theorem:main}}
We have the following lemma.

\begin{lemma}
For $D_{\alpha}$ defined as in Section~\ref{section:definitions} and $b_3$ as in Theorem~\ref{Arratia}, we have $ b_3 = 0$ for all patterns $\tau$.
\end{lemma}

\begin{proof}
This follows from the dissociated property of uniform permutations (Lemma \ref{lemma:dissociated}).
We interpret the conditioning on $\sigma(X_\beta : \beta \notin D_\alpha)$ as the $\sigma$-algebra containing all possible information about just the order of a particular set of three elements.  Since these three elements do not overlap any of the elements in $\alpha$, knowing only their order does not affect $X_\alpha$ because uniform permutations are dissociated.
\end{proof}

\begin{rmk}
Note that the conditioning in the expression for $b_3$ is not the $\sigma$-algebra containing all information about the elements indexed by each tuple.  If it were, then knowing their particular location would have an impact.  However, simply knowing their order does not reveal any more information about $X_\alpha$.
\end{rmk}

Next we obtain the size of $D_\alpha$, which is the same for all $\alpha \in \Gamma_j$.  

\begin{lemma}\label{count:D}
For each $\alpha \in \Gamma_j$, 
\[ |D_\alpha| = \binom{n}{j} - \binom{n-j}{j}. \]
\end{lemma}
\begin{proof} 
Fix any $\alpha,\beta\in\Gamma_j$ and let $s=1,\ldots,j$ denote the number of elements that $\alpha, \beta$ have in common.
 (This includes the case $\alpha = \beta$.)  
For each $s = 1,2,\ldots,j$, we select any $s$ elements out of the $j$ for the two sets of indices $\alpha, \beta$ to have in common, then we select the remaining $j-s$ elements from the $n-j$ remaining elements that are not in $\alpha$.  That is, 
\[ |D_\alpha| = \sum_{s=1}^{j} \binom{n-j}{j-s} \binom{j}{s} = \binom{n}{j} - \binom{n-j}{j}, \qquad \mbox{for all $\alpha\in\Gamma_j$}. \qedhere\]
\end{proof}

\begin{lemma} 
We have 
\[d_1 = \binom{n}{j}\left(\binom{n}{j} - \binom{n-j}{j}\right) / j!^2. \]
\end{lemma}
\begin{proof}
Follows immediately from Lemma~\ref{count:D} and Lemma~\ref{lemma:pab}. 
\end{proof}

The expression given for $d_2$ in Equation \eqref{d2} in the statement of Theorem \ref{theorem:main} is straightforward, although it
contains the overlap quantities $L_s(\tau),$ which can vary wildly for different patterns $\tau$, and for which we are unaware of any general explicit or asymptotic expression.
We calculate explicit upper bounds for $d_2$ in Lemma~\ref{better:d2:bounds}. 

\subsection{Proof of Theorem~\ref{consecutive patterns} and Theorem~\ref{main:mallows:theorem}}

Theorem~\ref{consecutive patterns} follows from Theorem~\ref{main:mallows:theorem} using $q = 1$ and the fact that $I_n(1) = n!$. 
Theorem~\ref{main:mallows:theorem} is a straightforward generalization of Proposition~\ref{prop:increasing}.  

\subsection{Proof of corollaries}


\label{asymptotic:proof}
For the proof of Corollary~\ref{theorem:asymptotic-general} it is sufficient that the bounds for $d_1$ and $d_2$ in Theorem \ref{theorem:main} converge to 0 as $n\to\infty$.

\begin{lemma}\label{lemma:d1}
Suppose $j \geq (e+\epsilon) \sqrt{n}$.  
Then for $d_1$ as in Theorem \ref{theorem:main}, we have $d_1 \to 0.$
\end{lemma}
\begin{proof}
The proof is an elementary application of Stirling's formula.  
\end{proof}

For $d_2$, the asymptotic analysis is not so straightforward, which is why we 
instead
use the inequality in Equation~\eqref{pab}.
\begin{lemma}\label{better:d2:bounds}
We have 
\[ d_2 \leq \frac{\binom{n}{j}}{j!^2} \sum_{s=1}^{j-1} \binom{n-j}{j-s}\binom{j}{s} \ s! \leq \frac{e^{2\left(\frac{1}{12} - \frac{3}{13}\right)}}{(2\pi)^2} \left(\frac{e^2(n-j)}{j^2}\right)^j \frac{1}{j} \ e^{2\sqrt{n-j}} \log(j) . \]
Whence, for any $\eta \geq 0$, taking $j \geq (e\, e^{1/e}+\eta) \sqrt{n}$, we have $d_2 \to 0$.  
\end{lemma}
\begin{proof}
We count the number of pairs $(\alpha, \beta)$, $\alpha \in \Gamma_j$ and $\beta \in D_\alpha$ with exactly $s$ shared elements.  
We may first choose any $2j-s$ locations among the $n$ possible choices for the patterns to occur on. 
Of those $2j-s$ locations, we can choose any $j$ of them for the elements of $\alpha$.
Then, of those $j$ locations, any $s$ can also be shared with $\beta$.
Thus, for a given $s \in \{1,2,\ldots, j-1\}$, there are
\[\binom{n}{2j-s}\binom{2j-s}{j} \binom{j}{s} = \binom{n}{j} \binom{n-j}{j-s}\binom{j}{s}\]
 terms in the sum. 
Using Equation~\eqref{pab}, we have 
\[ d_2 \leq \frac{\binom{n}{j}}{j!^2} \sum_{s=1}^{j-1} \binom{n-j}{j-s}\binom{j}{s} \ s! = \frac{\binom{n}{j}}{j!} \sum_{s=1}^{j-1} \frac{\binom{n-j}{j-s}}{(j-s)!}. \]
In order to handle the sum, first we recall the quantitative bounds of Robbins~\cite{Robbins}, i.e.,
\[ e^{\frac{1}{12n+1}} < \frac{n!}{(n/e)^n \sqrt{2\pi n}} < e^{\frac{1}{12n}}, \qquad \mbox{\emph{for all $n\geq 1$}}. \]
Again we emphasize that this inequality holds for all $n \geq 1$, which allows us to provide the simpler bound of
\[ d_2 \leq \lambda \exp\left( \left(\frac{1}{12}-\frac{3}{13}\right)\right) \sum_{s=1}^{j-1} \left(\frac{e^2(n-j)}{(j-s)^2}\right)^{j-s} \frac{e^{-\frac{(j-s)^2}{n-j}}}{2\pi (j-s)}. \]
The term $\left(\frac{e^2(n-j)}{(j-s)^2}\right)^{j-s}$ is maximized when $j-s = \sqrt{n-j}$, whence
\[ d_2 \leq \frac{\lambda}{2\pi}\exp\left( \left(\frac{1}{12}-\frac{3}{13}\right)\right)  \left(e^2\right)^{\sqrt{n-j}} \sum_{s=1}^{j-1} \frac{e^{-s^2/(n-j)}}{s} \leq \frac{\lambda}{2\pi} \exp\left( \left(\frac{1}{12}-\frac{3}{13}\right)\right)  e^{2\sqrt{n-j}} \log(j). \]
Note next that
\[ \lambda \leq  \left(\frac{e^2\, n}{j^2}\right)^{j} \frac{e^{-\frac{j^2}{n}}}{2\pi\, j}, \]
so that for $j \sim (e + \epsilon) \sqrt{n}$, we have
\[ \lambda \leq \left(1 + \frac{\epsilon}{e}\right)^{2j} \frac{e^{-(e+\epsilon)^2}}{2\pi\, j}, \]
and so
\[ d_2 \leq \left( \left(1+\frac{\epsilon}{e}\right)\left(e^{\frac{1}{e+\epsilon}}\right)\right)^{2j} \frac{\log j}{2\pi j} \leq \left(\frac{e^{1/e}}{1+\frac{\epsilon}{e}}\right)^{2j} \frac{\log j}{2\pi j}. \]
Letting $\epsilon = e(e^{1/e}-1) +\eta$ for any $\eta \geq 0$, we conclude that taking $j \geq (e\, e^{1/e}+\eta)\sqrt{n}$ implies $d_2 \to 0$. 
\end{proof}


We now compute an upper bound on $\overline{d}_2$ which is explicit and establishes Corollary~\ref{theorem:asymptotic-consecutive}.
\begin{lemma}
\[ \overline{d}_2 \leq  \sum_{s=1}^{m-1} (n-2m+s)\frac{s!}{(m)!^2} \sim \frac{n}{m!} \frac{1}{m}. \]
Taking $m \geq \Gamma^{(-1)}(n/t)-1$ and $m \sim \Gamma^{(-1)}(n/t)-1$, we have $\overline{d}_2 \leq \frac{t}{m} \to 0$ as $n$ tends to infinity. 
\end{lemma}
\begin{proof}
It is easy to see that
\[ \sum_{s=1}^{m-1} \frac{1}{(m+s-1)!} = \frac{1}{m!}\left(1 + O(m^{-1})\right), \]
and also
\[ \sum_{s=1}^{m-1} \frac{s}{(m+s-1)!} = \frac{1}{m!}\left(1 + O(m^{-1})\right). \]
Using Equation~\eqref{pab}, the result immediately follows. 
\end{proof}

For a more explicit form of the growth of $m$, we 
 define  $\psi(x) = \Gamma'(x) / \Gamma(x)$, the digamma function, as the logarithmic derivative of the gamma function, and denote by $k_0$ the smallest positive root of $\psi(x)$, i.e., $k_0 = 1.46163\ldots$. 
Also, let $c = e^{-1}\sqrt{2\pi} - \Gamma(k_0) = 0.036534\ldots,$ and denote by $W(x)$ the Lambert W function, i.e., the solution to $x = W(x) e^{W(x)}$.  
Finally, let $L(x) := \log((x+c) / 2\pi)$.

\begin{lemma}[\cite{Cantrell}
As $x$ tends to infinity, we have
\[\Gamma^{(-1)}(x) \sim \frac{L(x)}{W( L(x) / e)} + \frac{1}{2} \sim \frac{\log(x)}{\log\log(x) - \log\log\log(x)}. \]
\end{lemma}


\begin{lemma}\label{lemma:cantrell}
Suppose $t>0$ is some fixed constant and $m = \lceil\Gamma^{(-1)}(n/t)-1\rceil$.  Then
\begin{align*}
\overline{\lambda} & = \frac{n-m}{m!} \to t.
 \end{align*}
\end{lemma}

\begin{rmk}
We must be slightly careful when specifying the length of the pattern $m$ in Lemma~\ref{lemma:cantrell}, since in general $\Gamma^{(-1)}(n/t)-1$ will not be an integer.  However, as long as $m$ always exceeds this value, which we have ensured by setting it equal to the smallest integer exceeding it, then the asymptotic expressions still hold.
\end{rmk}





\ignore{ 


\begin{lemma}\label{lemma:d2}
For $d_2$ as in Theorem \ref{theorem:main},
\[ d_2\leq \binom{n}{j} \sum_{s=1}^{j-1} \binom{j}{s} \binom{n-j}{j-s}\frac{1}{j!(j-s)!} \leq \lambda^2\, 2^j; \]
whence, for $j > (e\sqrt{2}+\epsilon)\, n^{1/2}$, we have $d_2 \to 0$ as $n\to\infty$.
\end{lemma}
\begin{proof}
With $\lambda=\binom{n}{j}/j!$, we see
\ignore{
\begin{align*}
d_2 & \leq \frac{\binom{n}{j}}{j!} \sum_{s=1}^{j-1} \binom{j}{s} \frac{\binom{n-j}{j-s}}{(j-s)!} \leq \lambda^2 \sum_{s=1}^{j-1} \binom{j}{s} \leq \lambda^2 2^j. 
\end{align*}}
\begin{eqnarray*}
\binom{n}{j} \sum_{s=1}^{j-1} \binom{j}{s} \binom{n-j}{j-s}\frac{1}{j!(j-s)!}&=&\frac{\binom{n}{j}^2}{j!^2}\sum_{s=1}^{j-1}\binom{j}{s}^2\binom{n-j}{j-s}\binom{n}{j}^{-1}\\
&\leq&\frac{\binom{n}{j}^2}{j!^2}\sum_{s=1}^{j-1}\binom{j}{s}\\
&=&\lambda^2\sum_{s=1}^{j-1}\binom{j}{s},
\end{eqnarray*}
where the final inequality follows from 
\[\binom{n-j}{j-s}\binom{j}{s}\leq\binom{n}{j}\quad\text{ for all }s=0,1,\ldots,j.\]
Using
Stirling's formula for $\lambda=\binom{n}{j}/j!$, we have
\[ \lambda^2\sum_{s=1}^{j-1}\binom{j}{s}\leq\lambda^2 2^j \sim \left(\frac{2\, e^2\, n}{j^2}\right)^j \frac{1}{ \sqrt{2\pi\, j}}. \]
\end{proof}

\begin{proof}[Proof of Theorem \ref{theorem:asymptotic-general}]
Follows immediately from Theorem \ref{theorem:main} and Lemmas \ref{lemma:d1} and \ref{lemma:d2}.
\end{proof}
}


\ignore{
 Define  $\psi(x) = \Gamma'(x) / \Gamma(x)$, the digamma function, as the logarithmic derivative of the gamma function, and denote by $k_0$ the smallest positive root of $\psi(x)$, i.e., $k_0 = 1.46163\ldots$. 
Also, let $c = e^{-1}\sqrt{2\pi} - \Gamma(k) = 0.036534\ldots,$ and denote by $W(x)$ the Lambert W function, i.e., the solution to $x = W(x) e^{W(x)}$.  
Finally, let $L(x) := \log((x+c) / 2\pi)$.

\begin{lemma}[\cite{Cantrell}
As $x$ tends to infinity, we have
\[\Gamma^{(-1)}(x) \sim \frac{L(x)}{W( L(x) / e)} + \frac{1}{2} \sim \frac{\log(x)}{\log\log(x) - \log\log\log(x)}. \]
\end{lemma}


\begin{lemma}\label{lemma:cantrell}
Suppose $t>0$ is some fixed constant and $m \sim \Gamma^{(-1)}(n/t)-1$.  Then
\begin{align*}
 \lambda' & = \frac{n-m}{m!} \to t.
 \end{align*}
\end{lemma}

When $m\geq(1+\epsilon)\Gamma^{(-1)}(n/t)$, then $\lambda'\to0$ in Lemma \ref{lemma:cantrell} and
\begin{align*}
d_1'  &= {n_1}/{m!^2} \to 0\quad\text{and}\\
d_2' & \leq 2 (e-1)(n-m)/m!\to0.
\end{align*}

\begin{proof}[Proof of Theorem \ref{theorem:asymptotic-consecutive}]
Follows from Theorem \ref{consecutive patterns} and Lemma \ref{lemma:cantrell}.
\end{proof}

\begin{proof}[Proof of Propoisition~\ref{longest:contiguous}]
Note that for the increasing pattern $\tau_m = 12\ldots m$, we have $L_s(\tau_m) = 1$, i.e., one (increasing) pattern $12\ldots 2m-s.$ 
Then for $m \sim \Gamma^{(-1)}(n/t)$, we have
\begin{align*}
d_1' & = {n_1}/{m!^2} \to 0 \quad\text{and}\\
d_2' & = 2\sum_{s=1}^{m-1}\frac{(n-2m+s)}{(2m-s)!} \\
 & \leq 2 \frac{(n-m)}{m!} \sum_{s=1}^{m-1}\frac{m!}{(2m-s)!} \to 0.
 \end{align*}
\end{proof}


\ignore{We have $\lambda' = \frac{n-m}{m!},$ and we would like to find a suitable sequence $m\equiv m(n,t)$ such that $\lambda' \to t,$ for some fixed, positive constant $t$ chosen in advance.

\begin{lemma}
Suppose $t>0$ is some fixed constant.  Let $m = g^{-1}(n/t)$.  Then
\begin{align*}
 \lambda' & = \frac{n-m}{m!} \to t, \\
 d_1' & = \frac{n_1}{m!^2} \to 0, \\
 d_2' & \leq 2\lambda (e-1) \to 2t(e-1).
 \end{align*}
\end{lemma}
}
}




\section{Acknowledgements}
The authors would like to acknowledge helpful comments from Brendan McKay, Dan Romik, Igor Rivin, Jim Pitman, Richard Arratia, Igor Pak, Michael Albert, and Doron Zeilberger.




\bibliographystyle{acm}

2017-03-21T01:09:17.000
1509
1509.07941
en
https://arxiv.org/abs/1509.07941
Using techniques from Poisson approximation, we prove explicit error bounds on the number of permutations that avoid any pattern. Most generally, we bound the total variation distance between the joint distribution of pattern occurrences and a corresponding joint distribution of independent Bernoulli random variables, which as a corollary yields a Poisson approximation for the distribution of the number of occurrences of any pattern. We also investigate occurrences of consecutive patterns in random Mallows permutations, of which uniform random permutations are a special case. These bounds allow us to estimate the probability that a pattern occurs any number of times and, in particular, the probability that a random permutation avoids a given pattern.
Combinatorics (math.CO); Probability (math.PR)
Pattern Avoidance for Random Permutations
Qwen/Qwen-72B
1. YES
2. YES