On the Asymptotic Statistics of the Number of Occurrences of Multiple Permutation Patterns

Svante Janson^{1}, Brian Nakamura^{2}, and Doron Zeilberger^{3}

Abstract

To come...

1 Introduction

The primary area of interest in this article is the study of patterns in permutations. We will denote the set of length n permutations by S_{n}. Let a_{1}a_{2} … a_{k} be a sequence of k distinct real numbers. The reduction of this sequence, which is denoted by red(a_{1} … a_{k}), is the length k permutation π_{1} … π_{k} ∈ S_{n} such that order-relations are preserved (i.e., π_{i} < π_{j} if and only if a_{i} < a_{j} for every i and j). Given a (permutation) pattern τ ∈ S_{k}, we say that a permutation π = π_{1} … π_{n} ∈ S_{n} contains the pattern τ if there exists 1 ≤ i_{1} < i_{2} < … < i_{k} ≤ n such that red(π_{i_{1}}π_{i_{2}} … π_{i_{k}}) = τ. Each such subsequence in π will be called an occurrence of the pattern τ. If π contains no such subsequence, it is said to avoid the pattern τ. Additionally, we will denote the number of occurrences of the pattern τ in permutation π by N_{τ} (π) (e.g., π avoids the pattern τ if and only if N_{τ} (π) = 0).

For any pattern τ and integer n ≥ 0, we define the set

S_{n}(τ) := {π ∈ S_{n} : π avoids the pattern τ}  (1)

and also define s_{n}(τ) := |S_{n}(τ)|. The patterns σ and τ are said to be Wilf-equivalent if s_{n}(σ) = s_{n}(τ) for all n ≥ 0. We may also consider the more general set

S_{n}(τ, r) := {π ∈ S_{n} : π contains exactly r occurrences of τ}.  (2)

We will analogously define s_{n}(τ, r) := |S_{n}(τ, r)|.

A classical problem in this area is to find an enumeration for these sets or at the least, to study properties of the generating function encoding the enumerating sequence (for example, is it rational/algebraic/holonomic?). However, it is not even known if these generating functions are always holonomic. In general, the enumeration problem gets very difficult very quickly. Patterns up to length 3 are well-understood, but there are basic unresolved questions even for length 4 patterns. For example, it is known that there are three Wilf-equivalence classes for length 4 patterns: 1234, 1324, and 1342. While the enumeration problems have been solved for 1234 and 1342, no exact enumeration (or even asymptotics) is known for 1324.

1Department of Mathematics, Uppsala University, Uppsala, Sweden. [svante.janson@math.uu.se]

2CCICADA, Rutgers University-New Brunswick, Piscataway, NJ, USA. [brian.nakamura@rutgers.edu]

3Mathematics Department, Rutgers University-New Brunswick, Piscataway, NJ, USA. [zeilberg@math.rutgers.edu]

A (probabilistic) variation of this problem was posed by Joshua Cooper [ADD REF]: Given two (permutation) patterns σ and τ, what is the expected number of copies of σ in a permutation chosen uniformly at random from S_{n}(τ)? We note that if the enumeration of S_{n}(τ) is known, this question is equivalent to counting the total number of occurrences of σ in permutations from S_{n}(τ), or put more precisely, to compute

T_{n}(σ, τ) := ∑_{π∈S_{n}(τ)} N_{σ}(π).  (3)

Bóna first addressed the question for τ = 132 when σ is either the increasing or decreasing permutation in [ADD REF]. He shows how to derive the generating functions for T_{n}(12 … k, 132) and T_{n}(k … 21, 132), the total number of occurrences of 12 … k in S_{n}(τ) and occurrences of k … 21 in S_{n}(τ), respectively. In [ADD REF], Bóna also shows that T_{n}(213, 132) = T_{n}(231, 132) = T_{n}(312, 132) for all n and provides an explicit formula for them. Rudolph [ADD REF] also proves some conditions on when two patterns, say p and q, occur equally frequently in S_{n}(132) (i.e., T_{n}(p, 132) = T_{n}(q, 132) for all n).

In [ADD REF], Homberger answers the analogous question when τ = 123 and shows that there are three non-trivial cases to consider: T_{n}(132, 123), T_{n}(231, 123), and T_{n}(321, 123). He finds generating functions and explicit formulas for each one.

2 Enumerating with functional equations

For various patterns τ, functional equations were derived for enumerating permutations with r occurrences of τ in [ADD REFS]. These functional equations were then used to derive enumeration algorithms. We briefly review the relevant results here. The curious reader can see [ADD REFS] for more details.

2.1 Functional equations for single patterns

Given a (fixed) pattern τ and non-negative integer n, we define the polynomial:

f_{n}(τ; t) := ∑_{π∈S_{n}} t^{N_{τ} (π)}.  (4)

Recall that the coefficient of t^{r} is exactly s_{n}(τ, r). For certain patterns τ, a multi-variate polynomial P_{n}(τ; t; x_{1}, …, x_{n}) was defined so that P_{n}(τ; t; 1, …, 1) = f_{n}(τ; t) and that functional equations could be derived for the P_{n} polynomial.

The pattern τ = 123 was considered in [ADD REFS], and the polynomial P_{n} was defined to be:

P_{n}(123; t; x_{1}, …, x_{n}) := ∑_{π∈S_{n}} (t^{N_{123}(π)} ∏_{i=1}^{n} x_{i}^{|{(a,b) : π_{a}=i<π_{b}, 1≤a<b≤n}|}).  (5)

It was shown that this P_{n} satisfies the functional equation:

Theorem 1. For the pattern τ = 123,

P_{n}(123; t; x_{1}, …, x_{n}) = ∑_{i=1}^{n} x_{i}^{n−i} · P_{n−1}(123; t; x_{1}, …, x_{i−1}, tx_{i+1}, …, tx_{n}).  (FE123)

Since P_{1}(123; t; x_{1}) = 1, the functional equation can be used to recursively compute our desired quantity P_{n}(123; t; 1, …, 1) = f_{n}(123; t).

Similarly, in [ADD REFS], the polynomial P_{n} was defined for the pattern τ = 132 so that it satisfied the functional equation:

Theorem 2. For the pattern τ = 132,

P_{n}(132; t; x_{1}, …, x_{n}) = ∑_{i=1}^{n} x_{1}x_{2} … x_{i−1} · P_{n−1}(132; t; x_{1}, …, x_{i−1}, tx_{i+1}, …, tx_{n}). (FE132)

Again P_{1}(132; t; x_{1}) = 1, so the functional equation can be used to recursively compute our desired quantity P_{n}(132; t; 1, …, 1) = f_{n}(132; t).

The same was also done for the pattern τ = 231 in [ADD REF]. Although f_{n}(231; t) = f_{n}(132; t), redeveloping the approach directly for the pattern 231 allows us to consider the patterns 132 and 231 simultaneously. For 231, the polynomial P_{n} was defined so that it satisfies the functional equation:

Theorem 3. For the pattern τ = 231,

P_{n}(231; t; x_{1}, …, x_{n}) = ∑_{i=1}^{n} x_{1}^{0}x_{2}^{1} … x_{i}^{i−1} · P_{n−1}(231; t; x_{1}, …, x_{i−1}, tx_{i}x_{i+1}, x_{i+2}, …, x_{n}).

(FE231)

We again have that P_{1}(231; t; x_{1}) = 1, so the functional equation can be used to recursively compute our desired quantity P_{n}(231; t; 1, …, 1) = f_{n}(231; t).

The approach for the pattern 123 was also extended to the pattern τ = 1234 in [ADD REFS]. The polynomial P_{n}(1234; t; x_{1}, …, x_{n}; y_{1}, …, y_{n}) was defined so that P_{n}(1234; t; 1 [n times]; 1 [n times]) = f_{n}(1234; t) and in such a way that it satisfies the functional equation:

Theorem 4. For the pattern τ = 1234,

P_{n}(1234; t; x_{1}, …, x_{n}; y_{1}, …, y_{n}) =
∑_{i=1}^{n} y_{i}^{n−i} · P_{n−1}(1234; t; x_{1}, …, x_{i−1}, tx_{i+1}, …, tx_{n}; y_{1}, …, y_{i−1}, x_{i}y_{i+1}, …, x_{i}y_{n}). (FE1234)

Since P_{1}(1234; t; x_{1}; y_{1}) = 1, the functional equation can be used to recursively compute our desired quantity P_{n}(1234; t; 1 [n times]; 1 [n times]) = f_{n}(1234; t).

2.2 Merging functional equations for multiple patterns

It is also straight-forward to consider multiple patterns simultaneously if their corresponding functional equations are known, as shown in [ADD REF]. For example, suppose that we want to consider the two patterns σ = 123 and τ = 132 simultaneously. We can extend the f_{n} polynomial in the natural way to:

f_{n}(σ, τ; s, t) := ∑_{π∈S_{n}} s^{N_{σ}(π)}t^{N_{τ} (π)}.  (6)

In [ADD REF], the polynomial P_{n}(123, 132; s, t; x_{1}, …, x_{n}; y_{1}, …, y_{n}) was defined so that P_{n}(123, 132; s, t; 1 [n times]; 1 [n times]) = f_{n}(123, 132; s, t). The following functional equation was then derived:

Theorem 5. For the patterns σ = 123 and τ = 132,

P_{n}(123, 132; s, t; x_{1}, …, x_{n}; y_{1}, …, y_{n}) =

∑_{i=1}^{n} x_{i}^{n−i} · y_{1}y_{2} … y_{i−1} · P_{n−1}(123, 132; s, t; x_{1}, …, x_{i−1}, sx_{i+1}, …, sx_{n}; y_{1}, …, y_{i−1}, ty_{i+1}, …, ty_{n}).

Observe that we combined the functional equations for the individual patterns 123 and 132 by re-labeling the x_{i} variables for 132 to y_{i}, merging the reductions in the P_{n−1} in the natural way, and multiplying the coefficient terms for the P_{n−1} within the summands. We again have that P_{1}(123, 132; s, t; x_{1}; y_{1}) = 1, so the functional equation can be used to recursively compute our desired quantity P_{n}(123, 132; s, t; 1 [n times]; 1 [n times]) = f_{n}(123, 132; s, t).

More generally, we can similarly extend f_{n}(τ; t) to k different patterns τ_{1}, τ_{2}, …, τ_{k} and the corresponding variables t_{1}, t_{2}, …, t_{k} as:

f_{n}(τ_{1}, τ_{2}, …, τ_{k}; t_{1}, t_{2}, …, t_{k}) := ∑_{π∈S_{n}} t_{1}^{N_{τ_{1}} (π)}t_{2}^{N_{τ_{2}} (π)} … t_{k}^{N_{τ_{k}} (π)}.  (7)

The generalized polynomials P_{n} can be similarly defined and analogous functional equations can be derived.

For example, suppose that we want to consider all length three patterns simultaneously. We will consider the patterns in lexicographical order (i.e., τ_{1} = 123, τ_{2} = 132, …, τ_{6} = 321). Our f_{n} polynomial now becomes:

f_{n}(123, 132, …, 321; t_{1}, t_{2}, …, t_{6}) := ∑_{π∈S_{n}} t_{1}^{N_{123}(π)}t_{2}^{N_{132}(π)} … t_{6}^{N_{321}(π)}.  (8)

For notational convenience, the polynomial f_{n}(123, 132, …, 321; t_{1}, t_{2}, …, t_{6}) will be denoted by f_{n}(S_{3}; t_{1}, …, t_{6}). In [ADD REF], we discuss how to extend this to the generalized polynomial P_{n} and derive analogous functional equations.

The previous polynomial could also be refined further to consider all length three patterns and the pattern 1234 simultaneously. We will again consider the length three patterns in lexicographical order. Our f_{n} polynomial now becomes:

f_{n}(1234, S_{3}; s, t_{1}, t_{2}, …, t_{6}) := ∑_{π∈S_{n}} s^{N_{1234}(π)}t_{1}^{N_{123}(π)}t_{2}^{N_{132}(π)} … t_{6}^{N_{321}(π)}.  (9)

Just like the previous case, this polynomial can be extended to the analogous generalized polynomial P_{n} and similar functional equations can be derived.

2.3 Adapting multi-pattern functional equations

The previously described f_{n} polynomials (and their corresponding generalized P_{n} polynomials and functional equations) can be easily specialized to consider a variety of scenarios. This allows us to quickly extract functional equations (and fast enumeration algorithms) in a number of cases.

The polynomial f_{n}(S_{3}; t_{1}, …, t_{6}) (in Eq. 8) can be specialized to consider any subset of S_{3} by setting some t_{i} variables to 1. For example, f_{n}(S_{3}; t_{1}, t_{2}, 1, 1, 1, 1) would give us the polynomial tracking 123 and 132 simultaneously. Setting t_{i} = 1 for 3 ≤ i ≤ 6 in the generalized polynomial P_{n} and its functional equation would reproduce Theorem 5. This approach actually allows us to quickly compute the bi-variate polynomial

f_{n}(σ, τ; s, t) = ∑_{π∈S_{n}} s^{N_{σ}(π)}t^{N_{τ} (π)}  (10)

for any patterns σ, τ ∈ S_{3} (with σ ≠ τ).

The polynomial f_{n}(S_{3}; t_{1}, …, t_{6}) can actually be specialized in other ways. Suppose that we wanted to compute the bi-variate polynomial

∑_{π∈S_{n}(132)} s^{N_{123}(π)}t^{N_{321}(π)}.  (11)

Observe that this is exactly f_{n}(S_{3}; s, 0, 1, 1, 1, t). In other words, we may find the coefficient of t_{2}^{0} in f_{n}(S_{3}; t_{1}, …, t_{6}) and then set t_{3} = t_{4} = t_{5} = 1 and t_{1} = s, t_{6} = t. The same approach can be used to compute the polynomial

∑_{π∈S_{n}(132)} s^{N_{σ}(π)}t^{N_{τ} (π)}.  (12)

for any patterns σ, τ ∈ S_{3}\{132} (with σ ≠ τ).

The analogous specialization can be done to quickly compute

∑_{π∈S_{n}(123)} s^{N_{σ}(π)}t^{N_{τ} (π)}.  (13)

for any patterns σ, τ ∈ S_{3}\{123} (with σ ≠ τ). In general, for any p ∈ S_{3}, we can quickly compute

∑_{π∈S_{n}(p)} s^{N_{σ}(π)}t^{N_{τ} (π)}.  (14)

for any patterns σ, τ ∈ S_{3}\{p} (with σ ≠ τ).

We can also adapt the polynomial f_{n}(1234, S_{3}; s, t_{1}, t_{2}, …, t_{6}) (from Eq. 9) similarly. In particular, we can quickly compute the polynomial

∑_{π∈S_{n}(1234)} s^{N_{σ}(π)}t^{N_{τ} (π)}.  (15)

for any patterns σ, τ ∈ S_{3} (with σ ≠ τ) by setting s = 0 (i.e. extracting the coefficient of s^{0}) and setting the appropriate t_{i}’s to 1 in f_{n}(1234, S_{3}; s, t_{1}, t_{2}, …, t_{6}).

The previously discussed functional equation approaches have been implemented in the Maple

packages PDSn, PDAV132, PDAV123, and PDAV1234.

3 Computing moments for random permutations

3.1 Moments for random permutations from S_{n}

The previously discussed functional equations approach allows us to compute both rigorous and empirical statistical properties on permutations.

For some fixed n and fixed pattern σ ∈ S_{k}, suppose that a permutation π ∈ S_{n} is chosen uniformly at random. Let the random variable X_{σ}(π) be the number of occurrences of the pattern σ in π. It is not hard to compute the expected value (i.e., the first moment of the random variable X): 𝔼[X] = \binom{n}{k}/k!. More generally, it was shown in [ADD REF: SMP1] that the higher moments of X is a polynomial in n. In particular, the r-th moment about the mean of X, which is 𝔼[(X − 𝔼[X])^{r}], is a polynomial of degree (k − 1)r + 1.

For the patterns σ that were discussed in the previous section, the functional equations approach allows us to quickly compute f_{n}(σ; t) for any desired n. Observe that f_{n}(σ; t)/n! gives us the polynomial where the coefficient of t^{i} is the probability that a randomly chosen π ∈ S_{n} will have exactly i copies of σ. The important point is that we can (rigorously) find a closed-form expression (in n) for the higher order moments of X by computing sufficiently many terms to fit the polynomial.

For example, it was shown in [ADD REF: SMP1] that the exact expression for the second moment (about the mean) of the random variable X_{123} (over S_{n}) is:

[ADD EXAMPLE]

and that the third moment (about the mean) of the random variable X_{123} (over S_{n}) is:

[ADD EXAMPLE]

We may also consider mixed moments for two patterns σ and τ. Suppose that a permutation π is chosen uniformly at random from S_{n}, and again let the random variable X_{σ}(π) be the number of occurrences of pattern σ in π (and equivalently for X_{τ} (π)). It was also shown in [ADD REF: SMP1] that the mixed moments of the random variables X_{σ} and X_{τ} (about their respective means) are also polynomials in n. This allows us to rigorously find closed-form expressions (in n) for the higher order mixed moments by computing enough terms to find the polynomial.

For example, the covariance of the two random variables X_{123} and X_{132} is:

[ADD EXAMPLE]

while the covariance of the two random variables X_{123} and X_{321} is:

[ADD EXAMPLE]

The covariance of every two random variables X_{σ} and X_{τ} (with σ, τ ∈ S_{3}) can be found in the table [ADD REF: TABLE1].

[ADD TABLE]

3.2 Moments for random permutations from S_{n}(τ)

There has been a flurry of recent activity studying occurrences of patterns in the set of permutations avoiding specific patterns. Many of the recent articles focus on counting the total number of occurrences of a pattern in S_{n}(132) or in S_{n}(123). For example, [ADD REFS]... It is important to note that finding the total number of occurrences of pattern σ in the set S_{n}(τ) is equivalent to picking a permutation uniformly at random from S_{n}(τ) and finding the expected value 𝔼[X_{σ}] (assuming that the enumeration of S_{n}(τ) is known).

In the previous section, we were able to rigorously derive closed-form expressions for moments of the random variable X_{σ}(π) when the permutation π was randomly chosen from S_{n}. While we currently cannot derive similar rigorous results for random permutations from S_{n}(τ), we can still compute numerical moments for a variety of cases.

3.2.1 Permutations from S_{132}

Suppose a permutation is chosen uniformly at random from S_{n}(132). Using the Maple packages that accompany this article, we can compute many empirical moments. The expected values of the random variables X_{123}, X_{312}, and X_{321} for 1 ≤ n ≤ 10 can be found in the table [ADD REF:TABLE]:

[ADD TABLE]

The second moments (about the mean) of the random variables X_{123}, X_{312}, and X_{321} for 1 ≤ n ≤ 10 can be found in the table [ADD REF:TABLE]:

[ADD TABLE]

Data for the higher moments can be found on the authors websites. Additionally, mixed (i, j) moments of the random variables X_{123} and X_{321} for 1 ≤ n ≤ 10 can be found in the table [ADD REF:TABLE]:

[ADD TABLE]

Analogous outputs for other patterns can be found on the authors websites.

3.2.2 Permutations from S_{123}

Suppose a permutation is chosen uniformly at random from S_{n}(123). Using the Maple packages that accompany this article, we can compute many empirical moments. The expected values of the random variables X_{132}, X_{312}, and X_{321} for 1 ≤ n ≤ 10 can be found in the table [ADD REF:TABLE]:

[ADD TABLE]

The second moments (about the mean) of the random variables X_{132}, X_{312}, and X_{321} for 1 ≤ n ≤ 10 can be found in the table [ADD REF:TABLE]:

[ADD TABLE]

Data for the higher moments can be found on the authors websites. Additionally, mixed (i, j) moments of the random variables X_{132} and X_{312} for 1 ≤ n ≤ 10 can be found in the table [ADD REF:TABLE]:

[ADD TABLE]

Analogous outputs for other patterns can be found on the authors websites.

3.2.3 Permutations from S_{1234}

Suppose a permutation is chosen uniformly at random from S_{n}(1234). Using the Maple packages that accompany this article, we can compute many empirical moments. The expected values of the random variables X_{123}, X_{312}, and X_{321} for 1 ≤ n ≤ 10 can be found in the table [ADD REF:TABLE]:

[ADD TABLE]

The second moments (about the mean) of the random variables X_{123}, X_{312}, and X_{321} for 1 ≤ n ≤ 10 can be found in the table [ADD REF:TABLE]:

[ADD TABLE]

Data for the higher moments can be found on the authors websites. Additionally, mixed (i, j) moments of the random variables X_{123} and X_{321} for 1 ≤ n ≤ 10 can be found in the table [ADD REF:TABLE]:

[ADD TABLE]

Analogous outputs for other patterns can be found on the authors websites.

4 Svante’s part

In this section we let π be a permutation chosen uniformly at random from S_{n} (without any condition) and we study the joint distribution of the random variables X_{σ,n} := X_{σ}(π), the number of copies of σ in π, for different patterns σ ∈ S_{∗} := ⋃_{k=1}^{∞} S_{k} . We consider asymptotics as n → ∞ for (one or several) fixed σ.

Each X_{σ,n} has an asymptotic normal distribution, as was shown by Bona [1] (see also [2]). We give another (perhaps simpler) proof of this; moreover, we extend the result to joint asymptotic normality for several patterns σ.

The asymptotic variances and covariances depend on the patterns in a slightly complicated way, so we begin with some definitions. For k ≥ 1 and 1 ≤ i ≤ k, define

g_{k,i}(x) := \binom{k − 1}{i − 1}x^{i−1}(1 − x)^{k−i}.  (16)

For a permutation σ ∈ S_{k}, define

G_{σ}(x, y) := \frac{1}{(k − 1)!^{2}} (∑_{i=1}^{k} g_{k,i}(x)g_{k,σ(i)}(y) − \frac{1}{k} ) .  (17)

Let Z_{σ}, σ ∈ S_{∗}, be jointly normal random variables with 𝔼 Z_{σ} = 0 and (co)variances

Cov(Z_{σ}, Z_{τ}) = Σ_{σ,τ} := ⟨G_{σ}, G_{τ} ⟩_{L^{2}([0,1]^{2})} := ∫_{0}^{1} ∫_{0}^{1} G_{σ}(x, y)G_{τ} (x, y) dx dy.  (18)

(Such normal random variables exist since the matrix (Σ_{σ,τ})_{σ,τ} is non-negative definite. As is well known, the joint distribution is uniquely defined by the means and covariances.)

We denote the length of a permutation σ by |σ|, and let ⟶^{d} denote convergence in distribution of random variables.

Theorem 4.1. For every pattern σ ∈ S_{∗}, as n → ∞,

\frac{X_{σ,n} − 𝔼 X_{σ,n}}{n^{|σ|−1/2}} = \frac{X_{σ,n} − \frac{1}{|σ|!} \binom{n}{|σ|}}{n^{|σ|−1/2}} ⟶^{d} Z_{σ}.  (19)

Moreover, this holds jointly for any finite family of patterns σ. Furthermore, all (joint) moments converge; in particular, for any permutations σ, τ

\frac{Cov(X_{σ,n}, X_{τ,n})}{n^{|σ|+|τ|−1}} → Σ_{σ,τ} .  (20)

Before giving the proof we give some comments. First, as noted above, if σ has length |σ| = k,

𝔼 X_{σ,n} = \binom{n}{k}\frac{1}{k!} ∼ \frac{1}{k!^{2}} n^{k},  as n → ∞.  (21)

The asymptotic covariances Σ_{σ,τ} can be computed explicitly. By a beta integral,

∫_{0}^{1} g_{k,i}(x) dx = \binom{k − 1}{i − 1}\frac{Γ(i)Γ(k − i + 1)}{Γ(k + 1)} = \frac{1}{k} ,  (22)

and similarly, for any k, ℓ ≥ 1 and 1 ≤ i ≤ k, 1 ≤ j ≤ ℓ,

\begin{aligned}∫_{0}^{1} g_{k,i}(x)g_{ℓ,j}(x) dx & = \binom{k − 1}{i − 1}\binom{ℓ − 1}{j − 1}\frac{Γ(i + j − 1)Γ(k + ℓ − i − j + 1)}{Γ(k + ℓ)} \\ & = \frac{(k − 1)! (ℓ − 1)!}{(k + ℓ − 1)!}\binom{i + j − 2}{i − 1}\binom{k + ℓ − i − j}{k − i}. \end{aligned}  (23)

It follows from (22) that, if |σ| = k,

∫_{0}^{1} ∫_{0}^{1} ∑_{i=1}^{k} g_{k,i}(x)g_{k,σ(i)}(y) dx dy = \frac{k}{k^{2}} = \frac{1}{k}  (24)

which implies, using (23) twice, if further |τ| = ℓ,

∫_{0}^{1} ∫_{0}^{1} (∑_{i=1}^{k} g_{k,i}(x)g_{k,σ(i)}(y) − \frac{1}{k} ) (∑_{j=1}^{ℓ} g_{ℓ,j}(x)g_{ℓ,τ(j)}(y) − \frac{1}{ℓ}) dx dy

= ∫_{0}^{1} ∫_{0}^{1} ∑_{i=1}^{k} g_{k,i}(x)g_{k,σ(i)}(y) ∑_{j=1}^{ℓ} g_{ℓ,j}(x)g_{ℓ,τ(j)}(y) dx dy − \frac{1}{kℓ}

= ∑_{i=1}^{k} ∑_{j=1}^{ℓ} ∫_{0}^{1} g_{k,i}(x)g_{ℓ,j}(x) dx ∫_{0}^{1} g_{k,σ(i)}(y)g_{ℓ,τ(j)}(y) dy − \frac{1}{kℓ}

= ∑_{i=1}^{k} ∑_{j=1}^{ℓ} \frac{(k − 1)!^{2} (ℓ − 1)!^{2}}{(k + ℓ − 1)!^{2}} \binom{i + j − 2}{i − 1}\binom{k + ℓ − i − j}{k − i}\binom{σ(i) + τ(j) − 2}{σ(i) − 1}\binom{k + ℓ − σ(i) − τ(j)}{k − σ(i)}

− \frac{1}{kℓ}.

Consequently, by (18) and (17), if |σ| = k and |τ| = ℓ, then

Σ_{σ,τ} = \frac{1}{(k + ℓ − 1)!^{2}} ∑_{i=1}^{k} ∑_{j=1}^{ℓ} \binom{i + j − 2}{i − 1}\binom{k + ℓ − i − j}{k − i}\binom{σ(i) + τ(j) − 2}{σ(i) − 1}\binom{k + ℓ − σ(i) − τ(j)}{k − σ(i)}

− \frac{1}{(k − 1)! k! (ℓ − 1)! ℓ!}. (25)

Proof of Theorem 4.1. Let U_{1}, …, U_{n} be independent and identically distributed (i.i.d.) random variables with a uniform distribution on [0, 1]. It is a standard trick that (by symmetry) the reduction red(U_{1}, …, U_{n}) is a uniformly random permutation in S_{n} (note that U_{1}, …, U_{n} almost surely are distinct), so we can take this as our random π and obtain the representation, with k = |σ|,

X_{σ,n} = X_{σ}(π) = ∑_{i_{1}<···<i_{k}} 1 [red(U_{i_{1}}, …, U_{i_{k}}) = σ] .  (26)

This is an example of an asymmetric U-statistic, and (a rather simple instance of) the general theory in [6, Section 11.2] can be used to show the theorem. However, the details are a bit technical, in particular to calculate the asymptotic covariances, so we will instead use another, more symmetric representation. (See [6, Remark 11.21].)

Let V_{1}, …, V_{n} be another sequence of i.i.d. random variables, uniformly distributed on [0,1] and independent of U_{1}, …, U_{n}. Let π′ be the permutation that sorts these numbers such that V_{π′(1)} < ⋯ < V_{π′(n)} and let π be the reduction of U_{π′(1)}, …, U_{π′(n)}. Then π is still uniformly random, and it is easy to see that

\begin{aligned}X_{σ,n} = X_{σ}(π) & := ∑_{i_{1}<···<i_{k}} 1 [red(U_{π′(i_{1})}, …, U_{π′(i_{k})}) = σ] \\ & = \begin{matrix}∑ & * \\ j_{1},...,j_{k} \end{matrix} 1 [red(U_{j_{1}}, …, U_{j_{k}}) = σ] · 1 [V_{j_{1}} < ⋯ < V_{j_{k}}] , \end{aligned}  (27)

where ^{∑*} denotes summation over all distinct indices j_{1}, …, j_{k}. This representation, while in some ways more complicated that (26), has the great advantage that we sum over all ordered n-tuples of distinct indices; this is thus an example of a U-statistic, and we can apply the basic central limit theorem by Hoeffding [5, Theorem 7.1], see also [7] and [6, Section 11.1]. In order to compute the (co)variances, we follow the path of Hoeffding’s proof.

The main idea of Hoeffding’s proof of his central limit theorem is to use a projection. In our case we let W_{j} := (U_{j}, V_{j}) ∈ [0, 1]^{2} and write (27) as

X_{σ,n} = \begin{matrix}∑ & * \\ j_{1},...,j_{k} \end{matrix} f_{σ}(W_{j_{1}}, …, W_{j_{k}}),  (28)

for a certain (indicator) function f_{σ}. We then take the conditional expectation of f_{σ}(W_{1}, …, W_{k}) given one of the variables W_{i}:

f_{σ;i}(x, y) := 𝔼(f_{σ}(W_{1}, …, W_{k}) | W_{i} = (x, y));  (29)

we also take the expectation

μ := 𝔼 f_{σ}(W_{1}, …, W_{k}) = 𝔼 f_{σ;i}(W_{i}).  (30)

Hoeffding then shows that if we replace f_{σ} by f′_{σ}(W_{1}, …, W_{k}) := μ + ∑_{i=1}^{k}(f_{σ,i}(W_{i}) − μ), then the resulting error for the sum in (28) will have variance O(n^{2k−2}), which is negligible with the normalization used in Theorem 4.1. Thus we can approximate X_{σ,n} − 𝔼 X_{σ,n} by

\begin{matrix}∑ & * \\ j_{1},...,j_{n} \end{matrix} ∑_{i=1}^{k}(f_{σ;i}(W_{j_{i}}) − μ) = ∑_{i=1}^{k}(n − 1)\underline{k−1} ∑_{j=1}^{n}(f_{σ;i}(W_{j}) − μ) = (n − 1)\underline{k−1} ∑_{j=1}^{n} F_{σ}(W_{j}), (31)

where (n − 1)\underline{k−1} = (n − 1) ⋯ (n − k + 1) and

F_{σ}(x, y) := ∑_{i=1}^{k}(f_{σ;i}(x, y) − μ).  (32)

The asymptotic normality of X_{σ,n} now follows by the standard central limit theorem for the i.i.d. random variables F_{σ}(W_{j}), which yields (X_{σ,n} − 𝔼 X_{σ,n})/n^{k−1/2} ⟶^{d} N(0, Σ_{σ,σ}) where

Σ_{σ,σ} := 𝔼(F_{σ}(W_{1})^{2}) = ∫_{0}^{1} ∫_{0}^{1} F_{σ}(x, y)^{2} dx dy.  (33)

Joint normality for several patterns σ (possibly of different lengths) follows in the same way, with the asymptotic covariances

Σ_{σ,τ} := 𝔼(F_{σ}(W_{1})F_{τ} (W_{1})) = ∫_{0}^{1} ∫_{0}^{1} F_{σ}(x, y)F_{τ} (x, y) dx dy.  (34)

It remains to compute the functions F_{σ} defined in (32) In order to do this, we see that from (29) and the definition of f_{σ} as an indicator function, cf. (27)–(28),

f_{σ;i}(x, y) = ℙ(red(U_{1}, …, U_{k}) = σ | U_{i} = x) ℙ(V_{1} < ⋯ < V_{k} | V_{i} = y).  (35)

For the second probability in (35) we require that V_{1}, …, V_{i−1} < y and V_{i+1}, …, V_{k} > y, and furthermore that these two sets of variables are increasing; since the variables are independent and uniformly distributed, the probability is, recalling the notation (16),

\frac{y^{i−1}}{(i − 1)!} \frac{(1 − y)^{k−i}}{(k − i)!} = \frac{1}{(k − 1)!}g_{k,i}(y).  (36)

Similarly, for the first probability in (35) we require that the σ(i):th smallest of U_{1}, …, U_{k} is x, and that the others come in the order specified by σ, and the probability of this is (k − 1)!^{−1}g_{k,σ(i)}(x). Consequently,

f_{σ;i}(x, y) = \frac{1}{(k − 1)!^{2}} g_{k,σ(i)}(x)g_{k,i}(y).  (37)

Furthermore,

μ := 𝔼 f_{σ}(W_{1}, …, W_{k}) = ℙ(red(U_{1}, …, U_{k}) = σ) ℙ(V_{1} < ⋯ < V_{k}) = \frac{1}{k!^{2}} .  (38)

It follows from (32), (37), (38) and (17) that F_{σ}(x, y) = G_{σ}(y, x). Hence (33)–(34) agree with (18), and Hoeffding’s theorem yields (19).

Hoeffding’s theorem (and its proof sketched above) yields also the convergence (20) of the covariances. To see that moment convergence holds also for higher moments, let m be a positive integer. By (28),

𝔼(X_{σ,n} − 𝔼 X_{σ,n})^{m} = \begin{matrix}∑ & * \\ j_{11},...,j_{k1} \end{matrix} ⋯ \begin{matrix}∑ & * \\ j_{1m},...,j_{km} \end{matrix} 𝔼 ∏_{i=1}^{m}(f_{σ}(W_{j_{1i}}, …, W_{j_{ki}}) − μ)  (39)

where the expectation on the right-hand side vanishes unless each index set {j_{1i}, …, j_{mi}} contains at least one index shared by another such set. In this case, however, there are at most mk − m/2 distinct indices, and it follows that the moment (39) is a polynomial in n of degree at most mk − m/2. In particular, the normalized central moment 𝔼((X_{σ,n} − 𝔼 X_{σ,n})/n^{k−1/2})^{m} = O(1). If m is an even integer, this implies, by standard results on uniform integrability, that all moments of lower order converge to the corresponding moments of the limit Z_{σ}, and the same holds for joint moments. Since m is arbitrary, this shows convergence of all moments.

Example 4.2. The case k = 1 is trivial, with X_{1,n} = n deterministic. Indeed, (16)–(17) yield g_{1,1}(x) = 1 and G_{1,1}(x, y) = 0.

Example 4.3. The simplest non-trivial example is k = 2, where X_{21}(π) is the number of inversions in π. The distribution of this random variable, for π uniformly at random in S_{n}, is called the Mahonian distribution, and it is well-known that it is asymptotically normal, see e.g. [4, Section X.6]. (See [3] for the case of permutations of multi-sets; it would be interesting to obtain similar results for other patterns in multi-set permutations.) A simple calculation using (16)–(17) yields

G_{21,21}(x, y) = −2(x − \frac{1}{2})(y − \frac{1}{2})  (40)

and (18) or (25) yields Σ_{21,21} = 1/36. Hence Theorem 4.1 in this case yields the well-known

\frac{X_{21,n} − \frac{1}{2} \binom{n}{2}}{n^{3/2}} ⟶^{d} N(0, 1/36).  (41)

Example 4.2 is the only case when the limit Z_{σ} in Theorem 4.1 vanishes, as we show next.

Theorem 4.4. If k > 1, then Σ_{σ,σ} > 0 and thus Z_{σ} is non-degenerate, for every σ ∈ S_{k}.

Proof. By (16),

∑_{i=1}^{k} g_{k,i}(x) = 1.  (42)

Hence (17) may be written, using Kronecker’s delta δ_{i,j},

G_{σ}(x, y) := \frac{1}{(k − 1)!^{2}} ∑_{i=1}^{k} ∑_{j=1}^{k}(δ_{j,σ(i)} − \frac{1}{k} )g_{k,i}(x)g_{k,j}(y).  (43)

For a fixed k, the polynomials g_{k,i}, 1 ≤ i ≤ k, are linearly independent (and form basis in the k-dimensional vector space of polynomials of degree ≤ k − 1). Hence the k^{2} tensor products g_{k,i}(x)g_{k,j}(y) are linearly independent in L^{2}([0, 1]^{2}), and it follows from (43) and (18) that if k ≥ 2, then G_{σ} is not identically 0 and thus Σ_{σ,σ} = ∫∫ G_{σ}(x, y)^{2} > 0.

For a given k we have k! patterns σ ∈ S_{k} and thus k! limit variables Z_{σ}. We have just seen that (if k > 1) these are all non-degenerate; however, they are not linearly independent. For example, the sum ∑_{σ∈S_{k}} X_{σ}(π) = \binom{n}{k} for every π, so the sum is deterministic and it follows that ∑_{σ∈S_{k}} Z_{σ} = 0. Many non-trivial linear combinations vanish too, as is seen by the following theorem.

Theorem 4.5. Let k ≥ 1. The k! limit random variables Z_{σ}, σ ∈ S_{k}, span a linear space of dimension (k − 1)^{2}.

Proof. By the definition (18), this linear space, V say, is isomorphic (and isometric for the appropriate L^{2}-norms) to the linear space V_{1} spanned by the functions G_{σ} on [0, 1]^{2}. Furthermore, by (43) and the comments after it, V_{1} is isomorphic to the linear space V_{2} of k × k matrices spanned by the matrices A_{σ} := (δ_{j,σ(i)} − \frac{1}{k} )_{ij=1}^{k}. Let V_{3} be the space of all k × k matrices with all row sums and column sums 0. Then each matrix A_{σ} ∈ V_{3} and thus V_{2} ⊆ V_{3}. Conversely, it is easily seen that each matrix in V_{3} is a linear combination of matrices A_{σ}, for example using the well-known fact that every doubly stochastic matrix is a convex combination of permutation matrices. Hence V_{2} = V_{3}. Finally, dim(V_{3}) = (k − 1)^{2} since a matrix in V_{3} is uniquely determined by its upper left corner (k − 1) × (k − 1) submatrix obtained by deleting the last row and column, and conversely this submatrix may be chosen arbitrarily.

Example 4.6. There are 6 patterns of length k = 3. Taking them in lexicographic order 123, 132, 213, 231, 312, 321, and using Maple to calculate the covariance matrix of the limit variables Z_{σ} by (16)–(18), we find

(Cov(Z_{σ}, Z_{τ}))_{σ,τ∈S_{3}} = (Σ_{σ,τ} )_{σ,τ∈S_{3}} = \frac{1}{5!^{2}} (\begin{matrix}26 & 12 & 12 & −13 & −13 & −24 \\ 12 & 14 & −1 & −6 & −6 & −13 \\ 12 & −1 & 14 & −6 & −6 & −13 \\ −13 & −6 & −6 & 14 & −1 & 12 \\ −13 & −6 & −6 & −1 & 14 & 12 \\ −24 & −13 & −13 & 12 & 12 & 26 \end{matrix}) .  (44)

We note that the asymptotic variances differ between different patterns; they are 13/7200 (for 123 and 321) or 7/7200 (for the other patterns).

The eigenvalues of the covariance matrix (44) are

\frac{3}{5!^{2}} (25, 5, 5, 1, 0, 0),  (45)

verifying that this matrix has rank 4 as given by Theorem 4.5. A choice of pairwise orthogonal eigenvectors (in the corresponding order) is

(\begin{matrix}2 \\ 1 \\ 1 \\ −1 \\ −1 \\ −2 \end{matrix}) , (\begin{matrix}0 \\ 1 \\ −1 \\ 0 \\ 0 \\ 0 \end{matrix}) , (\begin{matrix}0 \\ 0 \\ 0 \\ 1 \\ −1 \\ 0 \end{matrix}) , (\begin{matrix}2 \\ −1 \\ −1 \\ −1 \\ −1 \\ 2 \end{matrix}) , (\begin{matrix}1 \\ −1 \\ −1 \\ 1 \\ 1 \\ −1 \end{matrix}) , (\begin{matrix}1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \end{matrix}) .  (46)

Remark 4.7. The last eigenvector in (46) corresponds to the trivial fact mentioned above that the sum of all Z_{σ} vanishes. The fifth eigenvector, also with eigenvalue 0, says that

Z_{123} + Z_{231} + Z_{312} − Z_{132} − Z_{213} − Z_{321} = 0.  (47)

Let Y (π) be the corresponding number

Y (π) := X_{123}(π) + X_{231}(π) + X_{312}(π) − X_{132}(π) − X_{213}(π) − X_{321}(π),  (48)

and let Y_{n} := Y (π) with π chosen uniformly at random in S_{n}. (Note that Y (π) is the sum of the signs of the \binom{n}{3} permutations red(π_{i_{1}}π_{i_{2}}π_{i_{3}}).) Theorem 4.1 and (47) thus say that, as n → ∞,

n^{−5/2}Y_{n} ⟶^{d} 0. However, in this case, the random variable Y_{n} does not vanish identically. (Take π as the identity permutation.) In fact, it can be shown that Var(Y_{n}) is a polynomial in n of degree 4, with leading term \frac{1}{18}n^{4}, i.e. of order n^{2k−2} instead of n^{2k−1} as in the cases when Theorem 4.1 yields a non-degenerate limit. In such cases, one can use a more advanced version of Hoeffding’s argument above and show that there is an asymptotic distribution that can be represented as an (infinite) polynomial of degree 2 in normal random variables; this polynomial can further be diagonalized as a linear combination of squares of independent normal variables, see e.g. [7] and [6, Section 11.1]. In the present case this leads to

n^{−2}Y_{n} ⟶^{d} Y^{∗} = ∑_{\begin{matrix}ℓ,m=−∞ \\ ℓ,m≠0 \end{matrix}}^{∞} \frac{1}{2π^{2}ℓm}(ξ_{ℓ,m}^{2} − 1),  (49)

where ξ_{ℓ,m} are i.i.d. standard normal random variables. (We omit the details but note that the bilinear form in [6, Corollary 11.5(iii)] in this case after some calculation turns out to correspond to the convolution operator on L^{2}(𝕋^{2}) given by convolution with H(x, y) = \frac{1}{6}(2x − 1)(2y − 1) (where we identify the group 𝕋 with [0, 1)); hence its eigenvalues are the Fourier coefficients Ĥ(ℓ, m) = −1/(6π^{2}ℓm), which yields the coefficients in (49).) Note that, since Var(ξ_{ℓ,m}^{2}) = 2,

Var Y^{∗} = ∑_{\begin{matrix}ℓ,m=−∞ \\ ℓ,m≠0 \end{matrix}}^{∞} \frac{2}{4π^{4}ℓ^{2}m^{2}} = \frac{1}{18},  (50)

in accordance with the asymptotic formula Var(Y_{n}) ∼ n^{4}/18. Furthermore, the representation (49) of the limit Y yields its moment generating function as

𝔼 e^{tY^{∗}} = ∏_{\begin{matrix}ℓ,m=−∞ \\ ℓ,m≠0 \end{matrix}}^{∞}(1 − \frac{2t}{2π^{2}ℓm})^{−1/2} = ∏_{ℓ,m=1}^{∞}(1 − \frac{t^{2}}{π^{4}ℓ^{2}m^{2}} )^{−1} = ∏_{m=1}^{∞} \frac{t/mπ}{sin(t/mπ)}, |ℜt| < π^{2}.

(51)

This type of limit is typical of the degenerate cases that can occur for certain linear combinations of pattern counts. It is presumably also possible to obtain higher degeneracies in special cases, with variance of still lower order and a limit that is a polynomial of higher degree in normal variables, but we have no explicit example of this.

Example 4.8. There are 24 patterns of length k = 4. A calculation as in Example 4.6 of the covariance matrix yields a 24 × 24 matrix of rank (4 − 1)^{2} = 9. The 9 non-zero eigenvalues are

\frac{8}{7!^{2}} (441, 147, 147, 49, 21, 21, 7, 7, 1).  (52)

Similarly, for k = 5 the covariance matrix is a 120 × 120 matrix with the 4^{2} = 16 non-zero eigenvalues

\frac{30}{9!^{2}} (7056, 3024, 3024, 1296, 756, 756, 324, 324, 84, 84, 81, 36, 36, 9, 9, 1).  (53)

The fact that the eigenvalues in (45), (52) and (53) all are simple rational numbers suggests that there is a general structure (valid for all k) for these eigenvalues, and presumably also for the corresponding eigenvectors; it would be interesting to know more about this.

5 Conclusion

To come...

References

[1] Miklós Bóna, The copies of any permutation pattern are asymptotically normal.

   arXiv:0712.2792.

[2] Miklós Bóna, On three different notions of monotone subsequences. Permutation Patterns, 89–114, London Math. Soc. Lecture Note Ser., 376, Cambridge Univ. Press, Cambridge, 2010.

[3] E. Rodney Canfield, Svante Janson and Doron Zeilberger, The Mahonian probability distribution on words is asymptotically normal. Adv. Appl. Math. 46 (2011), no. 1–4, 109–124. Corrigendum: ibid 49 (2012), no. 1, 77.

[4] William Feller, An Introduction to Probability Theory and Its Application, volume I, third edition, Wiley, New York, 1968.

[5] Wassily Hoeffding, A class of statistics with asymptotically normal distribution. Ann. Math. Statistics 19, (1948). 293–325.

[6] Svante Janson, Gaussian Hilbert Spaces. Cambridge Univ. Press, Cambridge, UK, 1997.

[7] H. Rubin and R. A. Vitale, Asymptotic distribution of symmetric statistics. Ann. Statist. 8 (1980), no. 1, 165–170.