Sylvie Corteel

Guy Louchard
email: louchard@ulb.ac.be

Robin Pemantle
email: pemantle@math.upenn.edu

Common Intervals in Permutations

Keywords: intervals in random permutations, gene teams, annealed mean

published or not. The documents may come

Introduction

Let [n] denote the set {1, 2, . . . , n}. We are interested in counting the common intervals of a pair of permutations. To be precise, if G A and G B are two permutations of [n], we are interested in counting the pairs of intervals (I, J) for which G A (I) = G B (J). It is equivalent to count intervals I for which G -1 B G A (I) is also an interval. Accordingly, we define Definition 1.1 The interval

I := [i, i + k -1] ⊆ [n] is called an interval of the permutation G if G -1 (I) is an interval, that is, if there is a j such that G[j, j + k -1] = [i, i + k -1] .
The proper intervals are those whose lengths are at least 2 and at most n -1.

Here and throughout, we use vector notation for permutations rather than cycle notation, so that (σ 1 , . . . , σ n ) denotes the permutation i → σ i rather than the permutation consisting of a single n-cycle. Example: Let G be the permutation [START_REF] Baryshnikov | Convolutions of inverse linear functions via multivariate residues[END_REF][START_REF] Arratia | Two moments suffice for Poisson approximation: the Chen-Stein method[END_REF][START_REF] Arratia | Poisson approximation and the Chen-Stein method[END_REF][START_REF] Bergeron | On the Similarity of Sets of Permutations and Its Applications to Genome Comparison[END_REF][START_REF] Bergeron | Common intervals and sorting by reversals: a marriage of necessity[END_REF]. Then the proper intervals of G are [START_REF] Arratia | Two moments suffice for Poisson approximation: the Chen-Stein method[END_REF][START_REF] Arratia | Poisson approximation and the Chen-Stein method[END_REF], [START_REF] Bergeron | On the Similarity of Sets of Permutations and Its Applications to Genome Comparison[END_REF][START_REF] Bergeron | Common intervals and sorting by reversals: a marriage of necessity[END_REF], [START_REF] Arratia | Two moments suffice for Poisson approximation: the Chen-Stein method[END_REF][START_REF] Baryshnikov | Convolutions of inverse linear functions via multivariate residues[END_REF] and [START_REF] Arratia | Two moments suffice for Poisson approximation: the Chen-Stein method[END_REF][START_REF] Bergeron | On the Similarity of Sets of Permutations and Its Applications to Genome Comparison[END_REF]. When G is a random variable, uniformly distributed over all permutations of [n], let X k denote the number of of intervals of length k of G and let X = k X k denote the number of intervals of G. We will show in Section 2 that as n → ∞, the distribution of X converges to a Poisson with mean 2.

The number of intervals, or runs of a permutation, was studied in the forties by Kaplansky [11] and Wolfowitz [START_REF] Wolfowitz | Additive partition functions and a class of statistical hypotheses[END_REF][START_REF] Wolfowitz | Note on runs of consecutive elements[END_REF] from a statistical point of view. See also [START_REF] Kolchin | Random Allocations[END_REF]. Recently several algorithms were designed to efficiently enumerate all common intervals of permutations [START_REF] Heber | Algorithms for Finding Gene Clusters[END_REF][START_REF] Uno | Fast Algorithms to Enumerate All Common Intervals of Two Permutations[END_REF] and their time complexity is O(n + K) where n is the size of the permutation and K the number of intervals. These algorithms were designed because common intervals have several applications. They relate to the consecutive arrangement problem [START_REF] Booth | Testing for the Consecutive Ones Property, Interval Graphs, and Graph Planarity Using PQ-Tree Algorithms[END_REF]. Genetic algorithms for sequencing problems are based on common intervals [START_REF] Kobayashi | An Efficient Genetic Algorithm for Job Shop Scheduling Problems[END_REF][START_REF] Mühlenbein | Evolution algorithms in combinatorial optimization[END_REF]. In bioinformatics [START_REF] Bergeron | On the Similarity of Sets of Permutations and Its Applications to Genome Comparison[END_REF][START_REF] Bergeron | Common intervals and sorting by reversals: a marriage of necessity[END_REF][START_REF] Didier | Common Intervals of Two Sequences[END_REF][START_REF] Heber | Algorithms for Finding Gene Clusters[END_REF][START_REF] Heber | Finding All Common Intervals of k Permutations[END_REF], genomes of prokaryotes can be modeled as a permutation of genes. A common interval is then a set of orthologous genes that appear consecutively, possibly in different orders, in two genomes. Therefore common intervals can be used to detect groups of genes that are functionally associated [START_REF] Heber | Algorithms for Finding Gene Clusters[END_REF][START_REF] Heber | Finding All Common Intervals of k Permutations[END_REF]. As the annotation of genomes is not perfect, the notion of consecutivity in intervals needs to be relaxed. A notion of gene teams was defined in [START_REF] Bergeron | The Algorithmic of Gene Teams[END_REF], where a gene team is a maximal set of orthologous genes, possibly occurring in different orders in the two species, but separated in each case by gaps that do not exceed a fixed threshold, δ. To study these, we consider a generalization of intervals, namely δ-intervals (the previous case corresponds to δ = 1).

Definition 1.2 The set I ⊆ [n] is called a δ-interval of [n] of length k if I is a set of integers {i 1 , . . . , i k } with 1 ≤ i r+1 -i r ≤ δ for each 1 ≤ r ≤ k -1.
We call I a δ-interval of length k of G if both I and G -1 (I) are δ-intervals. Proper δ-intervals are again those of cardinality at least 2 and at most n -1.

Example: G = (3, 1, 2, 4, 5) possesses the 2-intervals: {1, 2}, {1, 3}, {1, 2, 3}, {2, 3}, {1, 2, 3, 4}, {1, 3, 4}, {2, 3, 4}, {2, 4, 5}, {2, 4}, {2, 3, 5}, {2, 3, 4, 5}, {1, 3, 4, 5}, {1, 2, 4, 5}, {1, 2, 3, 5}

In [START_REF] Bergeron | The Algorithmic of Gene Teams[END_REF] a polynomial time enumeration algorithm for gene teams is presented. Our notion of δ-intervals removes the maximality constraint, whence the number of these may grow exponentially and it is natural to enumerate asymptotically rather than enumerating exactly.

The main purpose of this paper is to investigate the asymptotic properties of X (δ)

k , where this denotes the number of δ-intervals of length k of a uniformly chosen random permutation of [n], and of the total number X (δ) := k X (δ) k of δ-intervals of a random permutation. We are interested in all δ > 1 but in the present manuscript we examine only the case δ = 2. To reduce the number of superscripts, we let Y and Y k denote X (2) and X [START_REF] Arratia | Poisson approximation and the Chen-Stein method[END_REF] k respectively.

The number X (δ) of δ-intervals when δ > 1 behaves very differently from X. Whereas X is O(1) as n → ∞, with all the contributions coming from short intervals, there will typically be many δ-intervals. In fact for δ = 2, a thumbnail computation produces numbers α k in the unit interval (α 2 ≈ 0.57939) such that for k ∼ αn and α > α k , the random variable Y k will be typically exponentially large: the number of 2-intervals of [n] of size k grows exponentially, the probability of G -1 of one of these also being a 2-interval decays exponentially, and the growth overcomes the decay when α > α k .

Seeing that Y grows exponentially in n, it is natural to look at the rescaled quantity n -1 log Y . We compute the annealed mean, n -1 log EY . The term "annealed" means that we first take an expectation over the (uniform) measure on permutations. The more interesting quantities are the quenched quantities, which refer to the typical, rather than the mean behavior of Y . Often one has a so-called lottery effect, meaning that the mean of a quantity Y comes primarily from an exponentially small number of values that are exponentially larger than the median value, and that consequently, E log Y < log EY . For example, when there is a Gaussian limit law, n -1/2 (log Ynµ) → N (0, σ 2 ), then one will typically have a lottery effect. Perhaps surprisingly in light of the discussion in Section 7, there is no lottery effect. Our main result, Theorem 4.1 below, is that for δ = 2, we have EY 2 = O(EY ) 2 . This shows that as n → ∞, the sequence Y := Y /EY is tight on (0, ∞), meaning that when Y is rescaled by its mean, the probability of Y /EY < ǫ is uniformly bounded by some g(ǫ) going to zero as ǫ → 0.

The paper is organized as follows. In Section 2 we study the case δ = 1. We recall previous results and show that the distribution of X converges to a Poisson with mean 2. In Section 3 we compute the mean value of 2-intervals. We use basic counting arguments and then apply a saddle point argument. Section 4 states the main result which is that the quenched and annealed means are the same, that is EY 2 = O(EY ) 2 . Then we outline in Section 4 all the steps of the proof. The proof itself is presented in Sections 5, 6 and 7. In Section 5 we present a 4-variable generating function for pairs of 2-intervals of size k and k ′ which overlap on κ positions. Then in Section 6 we compute a rate function thanks to saddle point analysis which gives us the asymptotics of the number of pairs of 2-intervals of size k and k ′ which overlap on κ positions. This gives the exponential part of EY 2 . The full computation of the asymptotics of the non-exponential part of EY 2 seems daunting. We will show in Section 7 that EY 2 -(EY ) 2 = o(EY ) 2 , and that a Gaussian limit is not possible (Theorem 7.1). We are left to conjecture that Y converges in distribution to an unidentified positive real random variable, whose properties are discussed in Section 7.

A preliminary version of this paper was presented at the Third International Colloquium of Mathematics and Computer Science held at the Vienna University of Technology (Sep.2004).

Intervals

Recall that X k denotes the number of of intervals of length k of G and that X = k X k denotes the number of intervals of G. Uno et al [START_REF] Uno | Fast Algorithms to Enumerate All Common Intervals of Two Permutations[END_REF] computed

E(X 2 ) = 2(n -1) n ; E(X 3 ) = 6(n -2) n(n -1) ; E(X k ) ≤ 24 n 2 for k ≥ 4
Although this was not explicitly stated in [START_REF] Uno | Fast Algorithms to Enumerate All Common Intervals of Two Permutations[END_REF], it is not hard to show that in fact Proposition 2.1 As n → ∞, the distribution of X converges to a Poisson with mean 2.

Letting X ′ := n-1 k=3 X k , we see that EX ′ ≤ 6 n + (n -4) 24 n 2 ≤ 30 n so X ′ → 0 in probability as n → ∞.
Thus it suffices to show that X 2 converges to a Poisson of mean 2. Kaplansky proves this in [START_REF] Kaplansky | The asymptotic distributions of runs of consecutive elements[END_REF]. We give here an independent argument via a more modern approach, using the Poisson approximation machinery first developed by Chen and Stein, and put in an explicit and usable form in [START_REF] Arratia | Two moments suffice for Poisson approximation: the Chen-Stein method[END_REF].

Proof: Recall that G is a random permutation of [n]. Given k ∈ [n -1], let A k be the event that G -1 {k, k + 1} is an interval. Let B k = {k -1, k, k + 1} ∩ [n -1].
Write p k for P(A k ) and p k,l for P(A k ∩ A l ). Theorem 1 of [START_REF] Arratia | Poisson approximation and the Chen-Stein method[END_REF] concludes convergence to a Poisson with mean k p k provided the following three quantities go to zero. In fact the distance in total variation to the Poisson for any fixed n is bounded above by 2(b

1 (n) + b 2 (n) + b 3 (n))
, so the argument will show that the total variation distance is O(1/n).

b 1 := k j∈B k p j p k b 2 := k k =j∈B k p k,j b 3 := k E |E (1 A k -p k |σ(A j : j / ∈ B k ))| . Each p k = (n -1)/ n 2 = 2/n,
p k,j = (1/3) n-2 2 / n 4 = 4/(n 2 -n). Immediately we see that b 1 ≤ n[3(2/(n -2)) 2 ] = O(1/n) and that b 2 ≤ 3n4/(n 2 -n) = O(1/n).
It remains only to show that b

3 = O(1/n). Let σ denote σ(A j : j / ∈ B k ). A simple identity is |E (1 A k -p k |σ)| = 2 sup H∈σ [P(H ∩ A k ) -p k P(H)] = 2p k ||µ A k -µ|| T V ,
where || • || T V is the total variation distance, µ is the unconditional probability measure on σ and µ A k is the µ conditioned on A k . Now there is an easy way to generate a random permutation conditional on A k : pick G 0 uniformly at random, pick a pair of positions {j, j + 1} independently uniformly at random, switch the values of G -1 on k and G(j), and switch the values G -1 on k + 1 and G(j + 1).

With probability 1 -O(1/n), this does not change whether A j occurs for any j = k. It follows that ||µ A k -µ|| T V = O(1/n), which completes the proof. ✷ More generally, consider X k . There are T 1,k = nk + 1 possible k-tuples and each of them has a probability

Π 1,k = k! 1 n(n -1) . . . (n -k + 2)
of being made of k consecutive integers (again irrespective of their order, we denote this property by C k ). Hence

E(X k ) = k!(n -k + 1) n(n -1) . . . (n -k + 2) = k(n -k + 1) n k-1 . (1)
Set

X := n-1 k=2 X k .
We see that, as n → ∞, the dominant terms of E(X) are given by k = O(1) and k = n -O(1). Indeed, by Stirling, and setting k = αn + 1, we easily derive

E   n/2 k=εn X k   ∼ 1/2 ε α αn (1 -α) (1-α)n αn(1 -α)n 2πα(1 -α)n ndα ↓ 0, (2)
exponentially , n → ∞, for fixed ε.

We obtain

E(X) ∼ 2 + 8 n + 36 n 2 + 228 n 3 + . . .
As an example of X k behaviour, let us now turn to X 3 and compute E 2 3 := E X 2 3 . First we have T 1,3 = n -2 triplets contributing by E(X 3 ) to E 2 3 . Next we have T 2,3 = 2(n -3) couple of triplets with two common values and the probability of one of these couples contributing by 1 to E 2 3 is given by

Π 2,3 = 1 n(n -1)(n -2)(n -3) [2!T 2,3 ].
Next we have T 3,3 = 2(n -4) couples of triplets with one common value and the probability of one of these couples contributing by 1 to E 2 3 is given by

Π 3,3 = 1 n(n -1)(n -2)(n -3)(n -4) [(2!) 2 T 3,3 ].
Finally, there are T 4,3 = (n -4)(n -5) couples of disjoint triplets and the probability of one of these couples contributing by 1 to E 2 3 is given by

Π 4,3 = (3!) 2 T 4,3 5
0 (n -i) = (3!) 2 1 n(n -1)(n -2)(n -3)
.

Note again that

T i,3 = (n -2) + 2(n -3) + 2(n -4) + (n -4)(n -5) = (n -2) 2
as it should. This leads to

E 2 3 = E X 2 3 ∼ 6 n + 38 n 2 + . . . (3)
What is the asymptotic distribution of X 3 ? Let H i denote the event: the triplet [σ i , σ i+1 , σ i+2 ] is made of three consecutive integers (again irrespective of their order). We obtain, by inclusion-exclusion,

Pr[X 3 = 0] = Pr n-2 i=1 [I -H i ] = 1 -T 1,3 Π 1,3 + T 2,3 Π 2,3 /2 + T 3,3 Π 3,3 /2 + T 4,3 Π 4,3 /2 + . . . = 1 -(n -2) 3! n(n -1) + (n -3) 1 n(n -1)(n -2)(n -3) [4 + 4(n -4)] + (n -4)O 1 n 4 + (n -4)(n -5) 2 (3!) 2 1 n(n -1)(n -2)(n -3) + . . . Pr[X 3 = 1] = Pr   n-2 i=1 H i j =i [I -H j ]   = T 1,3 Π 1,3 -T 2,3 Π 2,3 -T 3,3 Π 3,3 -T 4,3 Π 4,3 + . . . = (n -2) 3! n(n -1) -2(n -3) 1 n(n -1)(n -2)(n -3) [4 + 4(n -4)] -2(n -4)O 1 n 4 -(n -4)(n -5)(3!) 2 1 n(n -1)(n -2)(n -3) + . . . Pr[X 3 = 2] = Pr   i j>i H i H j k =(i,j) [I -H k ]   = T 2,3 Π 2,3 /2 + T 3,3 Π 3,3 /2 + T 4,3 Π 4,3 /2 + . . . = (n -3) 1 n(n -1)(n -2)(n -3) [4 + 4(n -4)] + (n -4)O 1 n 4 + (n -4)(n -5) 2 (3!) 2 1 n(n -1)(n -2)(n -3) + . . .

This leads to

Pr[X 3 = 0] ∼ 1 - 6 n + 28 n 2 + . . . Pr[X 3 = 1] ∼ 6 n - 50 n 2 + . . . Pr[X 3 = 2] ∼ 22 n 2 + . . . . (4)
Note that this also leads to E(X 3 ) ∼ 6 n -6 n 2 + . . . and E(X 2 3 ) ∼ 6 n + 38 n 2 + . . . which is of course comptatible with (1) and [START_REF] Baryshnikov | Convolutions of inverse linear functions via multivariate residues[END_REF].

A simulation of X 3 based on M = 3000 trials with n = 40 is given in Figure 1 (asymptotic =line, observed =circle). The fit is reasonable.

The mean number of 2-intervals

Let N (k, n) denote the number of 2-intervals that are subsets of [n] and have cardinality k. We will take advantage of the uniformity of G. For each of the N (k, n) 2-intervals of cardinality k, its inverse image under G is uniformly distributed on k-subsets of [n]. Therefore, the probability is exactly N (k, n)/ n k for any given 2-interval of cardinality k, that its inverse image under G is again a 2-interval. Thus

EY k = N (k, n) 2 n k . ( 5
)
To evaluate N (k, n), note that there may be anywhere from 0 to m k := min{k -1, n -k} "holes" in a 2-interval, where a hole is an element not in the 2-interval but between its endpoints. Let T i,k denote the Fig. 1: Observed and limiting (4) X3 distribution number of 2-intervals of cardinality k with i holes. These may be enumerated by the following procedure. Pick a starting position r with 1 ≤ r ≤ n-k -i+1 and let r be the least element of the 2-interval. Choose any sequence with i occurrences of the word "skip" and k -1i occurrences of the word "no-skip". If the first word in the sequence is "no-skip" then r + 1 is the next element of the 2-interval; if the first word is "skip" then r + 2 is the next element. Continue in this manner until the sequence is used up. This method of enumeration makes it clear that

T i,k := (n -k + 1 -i) • k -1 i 0 ≤ i ≤ m k , and
EY k = m k i=0 (n + 1 -k -i) k-1 i 2 n k . (6)
When

k/n < 1/2 then N (k, n) = k-1 i=0 (n + 1 -k -i) k -1 i = n + 3 2 - 3 2 k 2 k-1 . (7)
When k/n > 1/2 the sum is better approximated than evaluated exactly. We find that

N (k, n) = n-k i=0 (n + 1 -k -i) k -1 i ,
which has its maximum term near the endpoint i = nk when k ≥ 2 3 n, and near k/2 when k ≤ 2 3 n. More categorical asymptotics than we need are available by using a normal approximation near k = 2n/3.

For n/2 < k < 2n/3) with (2n/3 -k)/ √ n → ∞, we have N (k, n) = n-k i=0 (n + 1 -k -i) k -1 i (8) ∼ k-1 i=0 (n + 1 -k -i) k -1 i = n + 3 2 - 3 2 k 2 k-1 .
which is asymptotically the same as when k < n/2. On the other hand, for (k

-2n/3)/ √ n → ∞, we have N (k, n) = n-k i=0 (n + 1 -k -i) k -1 i (9) ∼ k -1 n -k 2k -1 -n 3k -1 -2n 2 .
Finally, for

x := k -1/2 (k -2n/3) = O(1)
, the normal approximation yields directly

N (k, n) = 2 k-1 √ k 2 Ψ x , (10)
where Ψ x is the expected positive part of Z + x with Z a standard normal.

Via equation ( 6), these asymptotics for N (k, n) lead directly to asymptotics for EY k . To obtain asymptotics for EY , we then sum over k, using a saddle point approximation. The only significant terms are near k = α * n, where α * will be determined shortly but is evidently greater than 2/3. We therefore use [START_REF] Heber | Algorithms for Finding Gene Clusters[END_REF] with n → ∞ and α := k/n to obtain

N (k, n) 2 n k ∼ 2k -n k k n -k 2k -n 3k -2n 2 2 n k -1 ∼ A(α)n -1/2 exp [nF 1 (α)]
where

A(α) := (2α -1) 5 (3α -2) 4 1 2πα(1 -α) ; Fig. 2: F1(α) F 1 (α) := 3α ln α -(1 -α) ln(1 -α) -2(2α -1) ln(2α -1) .
When α < 2/3, we obtain, by a similar analysis,

F 1 (α) = α log(α) + (1 -α) log(1 -α) + 2 log(2)α. A plot of F 1 (α) is given in Figure 2. When α ≥ 2/3, the function F ′ 1 (α) vanishes when α solves 17α 4 -33α 3 + 24α 2 -8α + 1 = 0 . The unique root in [2/3, 1] is α * ≈ .7840013296 . . .. A saddle point approximation now gives us EY = n-1 k=2 EY k (11) ∼ n k=3n/4 A(k/n) exp [nF 1 (k/n)] n -1/2 ∼ A(α * ) exp(nF 1 (α * )) 2π -F ′′ 1 (α * ) = exp(nF 1 (α * )) (2α -1) 11 (3α -2) (3 -2α) 8 ≈ 2.4253 exp(0.40122467n) .
4

The second moment of the number of 2-intervals

In the next three sections, we show:

Theorem 4.1 EY 2 = O(EY ) 2 .
This section outlines, in three subsections, the argument for this. The subsequent section derives the crucial generating function and the following one uses the generating function to verify certain key computations.

Counting pairs of 2-intervals

Just as the mean of Y may be obtained from a saddle point analysis of EY k near k/n = α * , we expect the second moment of Y to be dominated by terms EY 2 k with k near some α * * . Because we have seen from numerical data that the quenched and annealed behavior are the same, we expect to find, and do find, that α * * = α * .

Again we will take advantage of symmetry. This time, if I and I ′ are 2-intervals, we will need to know the cardinality of their intersection before we can determine the probability that G -1 (I) and G -1 (I ′ ) are both 2-intervals. We therefore define N (k, k ′ , n, κ) to be the number of pairs of 2-intervals (I,

I ′ ) of [n] with |I| = k, |I ′ | = k ′ and |I ∩ I ′ | = κ.
For the computation of EY 2 k we will want to specialize to the case k = k ′ , so we denote N (k, n, κ) := N (k, k, n, κ). Our computations will now be analogous to the computation F 1 and its argmax, α * . Specifically, letting

α := k n β := k ′ n ρ := κ n
we will find a rate function r❛t❡(α, β, ρ) such that

N (k, k ′ , n, κ) ∼ A 0 (α, β, ρ)n -3/2 exp(nr❛t❡(α, β, ρ)) (12)
for all parameter values in a range containing the dominant contributions to the second moment of Y .

To obtain the analogue of ( 5) for second moments, we will need the rate function for total number of pairs of subsets A and

B of [n] with |A| = k, |B| = k ′ and |A ∩ B| = κ. The total number is given by n κ, k -κ, k ′ -κ, n -k -k ′ + κ = n! κ!(k -κ)!(k ′ -κ)!(n -k -k ′ + κ)! .
It follows that for any pair of sets of respective cardinalities k and k ′ whose intersection has cardinality κ ≤ k, the probability that their union is a specific pair of sets is

P (k, k ′ , n, κ) := n κ, k -κ, k ′ -κ, n -k -k ′ + κ -1
and that the rate function for this probability, lim n -1 log P , which we denote ❡♥t for entropy, is given by

❡♥t := ρ log ρ + (α -ρ) log(α -ρ) + (β -ρ) log(β -ρ) + (1 -α -β + ρ) log(1 -α -β + ρ) . (13)
Observe that the function ❡♥t satisfies the identity

❡♥t(α, β, α • β) = h(α) + h(β) (14)
where

h(x) = x log(x) + (1 -x) log(1 -x)
is the usual entropy function, and in particular that ρ = α • β is a maximum for the function -❡♥t for fixed α, β.

The rate function for the expected number of pairs of 2-intervals of respective sizes k and k ′ with overlap κ is given by

F 2 := 2 • r❛t❡ + ❡♥t , (15)
which we now analyze.

The exponential order of the second moment

Since EY 2 = k,l EY k Y l = k,l,κ N (k, l, n, κ) 2 P (k, l, n, κ)
is the sum of polynomially many summands, it follows that the exponential order of EY 2 is the same as the order of the largest summand, namely

n -1 log EY 2 → sup α,β,ρ F 2 (α, β, ρ) := λ * * . (16)
In order to compute λ * * we must find the location, (α * * , β * * , ρ * * ), of the maximum of F 2 . Without computing, we may narrow the search considerably. First, from the inequality EY k Y l ≤ 1 2 (EY 2 k + EY 2 l ), we see that the maximum of EY k Y l (for fixed n) can only occur when l = k, and therefore

λ * * = F 2 (α, α, ρ) (17)
for some α, ρ.

Next, consider how N (k, k ′ , n, κ) varies with κ for fixed (k, k ′ , n). In other words, enumerate pairs of 2-intervals of fixed sizes k and k ′ according to the size of their intersection, κ. Observe that κ N (k, k ′ , n, κ) counts all pairs of 2-intervals of sizes k and k ′ , so that

κ N (k, k ′ , n, κ) = N (k, n)N (k ′ , n) .
Since the number of summands is linear in n, we have at the exponential level that

sup ρ r❛t❡(α, β, ρ) = u(α) + u(β) (18)
where

u(α) = lim n -1 log N (k, n) as n → ∞ with k/n → α.
Later, we will show, for α and β in a range containing α * * , that this supremum occurs at ρ = α • β. Assume this for now. We have previously remarked that -❡♥t(α, β, •) has a maximum at α • β as well. Both functions are smooth, so the function F 2 = 2 • r❛t❡ + ❡♥t has a critical point there as well. With some work, using a four-variable generating function, we will show that this critical point is a maximum. It will then follow from ( 18) and ( 14) that

sup ρ F 2 (α, β, ρ) = F 2 (α, β, α • β) = 2 • r❛t❡(α, β, α • β) + ❡♥t(α, β, α • β) = 2u(α) + 2u(β) + h(α) + h(β) = F 1 (α) + F 1 (β) .
Taking the maximum over α and β then would give

λ * * = 2F 1 (α * ) . ( 19
)

End of the outline

More precise information about EY 2 is obtained by a saddle point summation. In particular, from the form of the generating function, it will follow that there is a n -3/2 correction term:

N (k, k ′ , n, κ) ∼ A 0 (k/n, k ′ /n, κ/n)n -3/2 exp(nr❛t❡(k/n, k ′ /n, κ/n))
in a neighborhood of the maximum. The product

N (k, k ′ , n, κ) 2 P (k, k ′ , n, κ) is then asymptotically A 1 (α, β, ρ)n -3/2 exp(nF 2 (α, β, ρ))
and the sum will be asymptotically C exp(nF 2 (α * , α * , α 2 * )) where

C = A 1 (α * , α * , α 2 * ) (2π) 3 H
and H is the Hessian of the rate function F 2 in appropriate coordinates. In particular the polynomial correction term is canceled by the summation, and the demonstration that EY 2 = O(EY ) 2 is completed.

To summarize, the foregoing outline proves Theorem 4.1 once we have verified several assertions:

(m1) that the supremum of r❛t❡(α, β, •) occurs at α • β;

(m2) that the critical point of F 2 at ρ = α • β is a maximum;

(m3) that exact asymptotics for EY k Y l have an n -3/2 correction term to the exponential and that the discrete saddle point summation exactly cancels this out.

We remark that this argument does not show that EY 2 -(EY ) 2 = Θ(EY ) 2 . In principle we could compute A(α * , α * , α 2 * ) and H and compare to the constant computed in [START_REF] Kaplansky | The asymptotic distributions of runs of consecutive elements[END_REF], but this computation seems daunting. Instead, a separate argument ruling out the possibility that E(Y 2 ) -(EY ) 2 = o(EY ) 2 is given in the last section.

Before turning to the generating function, we establish some helpful numerical bounds.

Lemma 4.2 If α < 12/17 or if α > 0.847 then

F 2 (α, α, ρ) < 2F 1 (α * ) .
Proof: Suppose first that α > 0.847. A crude upper bound for

F 2 (α, α, ρ) is lim n→∞ N (⌊αn⌋, n) 2 .
This latter quantity is equal to 2η where η := α log(α) [START_REF] Arratia | Two moments suffice for Poisson approximation: the Chen-Stein method[END_REF]. We may verify that when α > 0.847 then η < 0.4001, which is known to be less than F 1 (α * ). Verification: dη/dα is the log of an algebraic expression and vanishes exactly once on the interval [1, 2, 1] namely at α = (5 + √ 5)/10 ≈ 0.7236; in particular, η is decreasing on [0.73, 1] and η(0.847) < 0.4001 < F 1 (α * ). For the case when α < 12/17, the most straightforward method is to divide the α-δ plane into small squares. In each we may easily compute separate upper and lower bounds for 2 • r❛t❡ and ❡♥t, since these functions will have extremes at a vertex of the grid square. With the grid squares sufficiently small, one may then check that the sum of the bounds does not exceed 2F 1 (α * ). For details, see http://www.math.upenn.edu/˜pemantle/CLP04-grid1.mw ✷

-(1 -α) log(1 -α) -(2α -1) log(2α -

The Generating Function

Recall that N (k, k ′ , κ, n) denotes the number of pairs of 2-intervals (I,

I ′ ) of [n] with |I| = k, |I ′ | = k ′ and |I ∩ I ′ | = κ.
Define the generating function

F (u 1 , u 2 , t, z) := k,k ′ ,κ,n N (k, k ′ , κ, n)u k 1 u k ′ 2 t κ z n so that N (k, κ, n) = [u k 1 u k 2 t κ z n ]F .
As a warm-up, let us compute the generating function for N (k, n) and recover the asymptotic formulae ( 7) - [START_REF] Heber | Algorithms for Finding Gene Clusters[END_REF]. Recall from building the generic indicator function that a 2-interval consists of any number of unused locations, followed by a single used location, followed by any sequence of pairs (unused , used) and single used locations, followed by any number of unused locations. Each pair (unused , used) contributes a factor of uz 2 while each single used location gives a factor of uz. The generating function for an arbitrary sequence of pairs and singles is thus uz/(1 -(uz + uz 2 )) = uz/(1 -(1 + z)uz). Taking into account the initial and final strings of unused positions gives

F 3 (u, z) := N (k, n)u k z n = uz (1 -z) 2 (1 -(1 + z)uz) . ( 20
)
To recover the asymptotics in the different regimes, write

F 4 (z) = [u k ]F 3 (u, z) = (1 + z) k-1 z k (1 -z) 2
and

N (k, n) = [z n ]F 4 (z) = 1 2πi (1 + z) k-1 z k (1 -z) 2 z n+1 dz .
Writing F 5 := α log(1 + z) -(1α) log z and setting (k -1)/n := α we then have

N (k, n) = 1 2πi exp(nF 5 (z)) (1 -z) 2 dz .
There is a double pole at z = 1 and a saddle point at F ′ 5 (z) = 0, that is, at z * := (1α)/(2α -1). when α < 2/3 the double pole is the dominant singularity and leads by residues to

N (k, n) ∼ -n2 αn F ′ 5 (1) = n2 αn (1 -3α/2)
which is [START_REF] Booth | Testing for the Consecutive Ones Property, Interval Graphs, and Graph Planarity Using PQ-Tree Algorithms[END_REF]. When α > 2/3 the saddle point is dominant and leads to

N (k, n) ∼ 1 (1 -z * ) 2 -2πnF ′′ 5 (z * ) exp(nF 5 (z * ))
which agrees with [START_REF] Heber | Algorithms for Finding Gene Clusters[END_REF]. Now to derive F , we follow a similar route. A canonical way to build a pair of sets and keep track of the intersection is as follows.

1. An initial sequence of positions before the first common position; 2. A common position followed by zero or more segments of the form: a sequence of positions not common to either set, in such a way that no two positions in a row are absent from either set, followed by a common position;

3. A final sequence of positions after the last common position.

The crucial part of the generating function is the one that grows exponentially with κ, namely the second of the three parts. Nevertheless, in order to compute a valid leading order asymptotic, we must keep track of all three parts. To enumerate the second of the three parts, note that each segment between common positions can be one of six possible classes of configuration. We list these here, along with the factor contributed by such a step to the generating function. a Empty. f a = 1. b A single position, which can belong to either set or neither, but not both.

f b = z(1 + u 1 + u 2 ).
c A positive number of pairs (j, j +1) where j ∈ I \I ′ and j +1 ∈ I ′ \I.

f c = z 2 u 1 u 2 /(1-z 2 u 1 u 2 ).
c ′ A positive number of pairs (j, j + 1) where j ∈ I ′ \ I and j + 1

∈ I \ I ′ . f c ′ = f c .
d the same as (c) but there is a single position in I \ I ′ at the end. f d = zu 1 f c . d ′ the same as (c ′ ) but there is a single position in I ′ \ I at the end.

f d ′ = zu 2 f c ′ .
The generating function for an arbitrary sequence of these is

f = zu 1 u 2 t 1 -zu 1 u 2 t(f a + f b + (2 + z(u 1 + u 2 )f c ) (21) = zu 1 u 2 t(1 -z 2 u 1 u 2 ) (1 -z 2 u 1 u 2 )(1 -zu 1 u 2 t -z 2 u 1 u 2 t(1 + u 1 + u 2 )) -zu 1 u 2 t(2 + z(u 1 + u 2 ))z 2 u 1 u 2 .
Fig. 3: shaded squares in each row correspond to positions present in that set

For the first and last of the three parts, we first recall from (20) the generating function

F 6 (u, z) := uz 1 -(1 + z)uz
for that part of a 2-interval between its first and last point. By symmetry, parts 1 and 3 have the same generating function, which is equal to 1/(1z) times the generating function g for the segment to the right of the last common position but to the left of the last position in I ∪ I ′ . We may write g as the sum of several cases. e Empty. g e = 1.

f A position in neither set, followed by a non-empty string of positions, each of which is in neither set or I, with no two in a row not in I. g f = zF 6 (u 1 , z).

f ′ A position in neither set, followed by a non-empty string of positions, each of which is in neither set or I ′ , with no two in a row not in I ′ . g f ′ = zF 6 (u 2 , z).

g A string of pairs as in case (c) above, followed by a nonempty sequence as in case (f).

g g = F 6 (u 1 , z)/(1 -z 2 u 1 u 2 ).
g ′ A string of pairs as in case (c ′ ) above, followed by a nonempty sequence as in case (f ′ ).

g g ′ = F 6 (u 2 , z)/(1 -z 2 u 1 u 2 ).
h The same as (g) except with a position in I ′ \ I in the beginning.

g h = zu 2 F 6 (u 1 , z)/(1 -z 2 u 1 u 2 ).
h ′ The same as (g ′ ) except with a position in I \I ′ in the beginning.

g h ′ = zu 1 F 6 (u 2 , z)/(1-z 2 u 1 u 2 ).
Summing, we see that the factor from the first and last parts is

g = 1 1 -z 1 + zF 6 (u 1 , z) + zF 6 (u 2 , z) + F 6 (u 1 , z) + F 6 (u 2 , z) 1 -z 2 u 1 u 2 + u 2 zF 6 (u 1 , z) + u 1 zF 6 (u 2 , z) 1 -z 2 u 1 u 2 .
Finally,

F (u 1 , u 2 , t, z) = f g 2 . ( 22
)
6 The rate function

Let L denote the logarithmic gradient, that is, LQ is the vector whose j th coordinate is x j ∂Q/∂x j . Let h(x, y, z, τ ) = 1xyτ (1 + x + y + z + xyxyz) and let V o be the set of smooth points of the variety where h vanishes. Let (µ, ν, δ) denote (αρ, βρ, 1αβ + ρ). In the next subsection we will prove: Theorem 6.1 Let s 0 := (α * * , β * * , ρ * * ) be the argmax for F 2 as in [START_REF] Pemantle | Asymptotics of multivariate sequences, part II: multiple points of the singular variety[END_REF]. There is a neighborhood N of s 0 in RP d-1 and a continuous map x : N → V ∩ (R + ) 4 such for every s ∈ N there is a point x(s) satisfying:

1. h(x) = 0; 2. Lh(x) = s; 3. if α = s 1 + s 4 , β = s 2 + s 4 and ρ = s 4 with s normalized so that j s j = 1, then r❛t❡(α, β, ρ) = -µ log x 1 -ν log x 2 -δ log x 3 -ρ log x 4 (23) and N (k, k ′ , n, κ) ∼ A 0 (α, β, ρ)n -3/2 exp[nr❛t❡(α, β, ρ)] .
Readers not interested where this comes from may skip now to Section 6.1.

The general approach to extracting asymptotics from the generating function is taken from [START_REF] Baryshnikov | Convolutions of inverse linear functions via multivariate residues[END_REF]. Let F be a rational generating function in d variables, written as the quotient of polynomials P/Q with Q(0) = 0. The coefficients of F = r a r z r may be evaluated via Cauchy's integral formula

a r = 1 (2πi) d T z -r F (z) dz z .
The cycle of integration, T , is, initially, the product of small circles around the origin in each coordinate.

But, letting ❉♦♠ denote the domain of holomorphy of F (that is (C * ) d \ V where V is the variety on which Q vanishes), we may replace T by anything in the homology class

[T ] ∈ H d (❉♦♠).
It is shown in [START_REF] Baryshnikov | Convolutions of inverse linear functions via multivariate residues[END_REF] that H d (❉♦♠) is generated by cycles of the following sort. Fix a vector s ∈ (R d ) + , projecting to a direction also denoted s in RP d-1 . positive orthant of RP d-1 , for which one wishes to compute asymptotics of a r as r → s. Let {S β } be a Whitney decomposition of V into strata (e.g., if V is smooth, then one has simply {V }). For generic values of s, the function h s := -d j=1 s j log |z j | will be a Morse function on all strata of V and there will be a finite set of critical points {x β,j } of the restriction to stratum S β of h s . Then H d (❉♦♠) is generated by cycles C such that • C is the product of a cycle C 1 in some S β with an arbitrarily small cycle C 2 orthogonal to S β ;

• C 1 passes through some x β,j and h s is maximized on C 1 at x β,j .

The integral of ω := z -r F dz/z over C 2 will be computable as a residue, ω 1 . The integral of ω 1 over C 1 will be a saddle point integral, in the sense that it will be the integral of P 1 (z)z -r dz/z where for r → s, the dominant term in the integrand, z -r , has maximum modulus and stationary phase at x β,j . It is easy to evaluate C1 ω 1 as a stationary phase integral. Asymptotics of a r are then obtained by summing over critical points x β,j in the support of [T ] (when [T ] is written as a linear combination of these, which have positive coefficient). Among these, only those with the highest value of h s need be considered.

Carrying out this programme will require several steps: i Find the critical points (routine but messy exercise in computer algebra)

ii Determine which of these are in the support of [T ] (nontrivial topological problem with tidy answer in terms of local tangent cone)

iii Compute the functions r❛t❡ and A 0 (straightforward) iv Optimize F 2 in α, β and ρ (cajole the computer into performing the right simplifications)

v Sum in a neighborhood of the optimum (fairly routine discrete saddle point computation)

The first three of these are carried out in the next subsection, and the last two in the subsequent one.

Finding the dominating point

We now specialize to the generating function F = f g 2 . It will turn out to simplify the computations if we change variables to

τ := ztu 1 u 2 , u = zu 1 and v = zu 2 . The [k, k ′ , n, κ] coefficient of F now becomes the [k -κ, k ′ -κ, n -k -k ′ + κ, κ] coefficient of the function F (x, y, z, τ ). Thus 1 n log[nα, nβ, n, nρ]F = 1 n log[nµ, nν, nδ, nρ] F when α = µ + ρ, β = ν + ρ, ρ = α + β + δ -1
and F is F under the change of variables. In the new variables,

f = τ (1 -xy) 1 -xy -τ (1 + x + y + xy + zxy -z) .
The other divisors in V are factors in the denominator of g, namely, g 1 := 1z, g 2 := 1xy, g 3 := 1 -(1 + z)x and g 4 := 1 -(1 + z)y. The variety V e f where f vanishes is not smooth, since ∇ f vanishes on the curve γ := (-1, -1, 1/t, t). Thus V e f has the strata V o := V e f \ γ and γ. The other divisors of V are smooth.

Define the function D : V → CP 3 by D(x) = Lx for smooth points of V and otherwise by letting D(x) be the closure of the limit points of L(y) as y → x. The point x(s) "controls" the asymptotics in the direction s, as captured by the following result taken from [START_REF] Pemantle | Asymptotics of multivariate sequences, part I: smooth points of the singular variety[END_REF]. Proposition 6.2 For any s in the positive orthant of RP 3 , there is a point x(s) with the following properties.

1. x ∈ V 2. s ∈ D(x) 3. if x is a smooth point of V , and if α = s 1 + s 4 , β = s 2 + s 4 and ρ = s 4 with s normalized so that j s j = 1, then r❛t❡(α, β, ρ) = -µ log x 1 -ν log x 2 -δ log x 3 -ρ log x 4
Remark 6.3 The only difference between this proposition and Theorem 6.1 is that we would like x ∈ V o rather than just x ∈ V .

Proof: Let log D be the logarithmic domain of convergence of F , that is, the closure of the set of x ∈ R 4 such that a r exp(r • x) is finite. Since F has nonnegative coefficients, we may use the argument of [START_REF] Pemantle | Asymptotics of multivariate sequences, part I: smooth points of the singular variety[END_REF]Theorem 6.3] to see that there will be a minimal point x(s) for which conclusions ( 1) and ( 2) hold. Here a minimal point means a point x which is the only intersection of V with the polydisk {y : |y j | ≤ x j ∀j} in C 4 . The minimal point in question will be the exponential (e u1 , e u2 , e u3 , e u4 ) of the contact point u for the support hyperplane to log D in direction s. In other words, choosing u to maximize s • u on log D will yield a point x = exp(u) which is minimal in direction s. The third conclusion follows from [START_REF] Pemantle | Asymptotics of multivariate sequences, part I: smooth points of the singular variety[END_REF]Theorem 3.5]. ✷

Finding the asymptotics for n -1 log[nµ, nν, nδ, nρ] F is now a matter of locating the minimal point.

Lemma 6.4 Let s 0 be the maximizing direction (α * * , β * * , ρ * * ) for F . There is a neighborhood N of s 0 in RP 3 such that for any s ∈ N , the critical point x = (x 0 , y 0 , z 0 , τ 0 ) with maximum value of h s among those in the support of [T ] is in V o and the coordinates are positive and real.

Proof: Exponentiating log D, we obtain a set E in the positive orthant of R 4 that may be described as follows. First we compute the intersection with the plane τ = 0, or in other words, the positive minimal points of the divisors of g. Recall that these divisors are {z = 1}, {x(1 + z) = 1}, {y(1 + z) = 1} and {xy = 1}. Let E ′ denote the connected component of the complement of the coordinate hyperplanes and these four divisors that contains the origin in its closure. It is not hard to describe E ′ : it is the region below the graph of the function z = min{1, 1/x -1, 1/y -1}. A lower boundary is the square {z = 0, 0 ≤ x ≤ 1, 0 ≤ y ≤ 1}, an upper boundary is the square {z = 1, 0 ≤ x ≤ 1/2, 0 ≤ y ≤ 1/2} and there are sloping curved ruled surfaces for the remaining upper boundary defined by

S 1 := {z = 1/x -1, 0 ≤ y ≤ x ≤ 1} and S 2 := {z = 1/y -1, 0 ≤ x ≤ y ≤ 1}.
The divisor {xy = 1} intersects E ′ only at the point (1, 1, 0) and plays no role in bounding log D.

In R 4 , the set E will be a subset of the cylinder E ′′ := E ′ × [0, ∞). In particular, it will be bounded "below" (lowest τ ) by E ′ × {0} and "above" (highest τ ) by t = ψ(x, y, z) := (1xy)/(1 + x + y + z + xyxyz). There will be side boundaries at the graph of ψ restricted to the boundaries of E ′ . Now we rule out finding the minimal point at any place other than on the "upper" boundary, V f = V o ∪γ. As long as s is strictly positive, the support hyperplane to log D normal to s must contact log D either at a smooth point whose normal is strictly positive or at a non-smooth point whose normals together have positive values in each coordinate. Exponentiating, we see that the minimal point must be on the closure of the "upper" surface, namely the graph of ψ on E ′ . We must now rule out the following places for the minimal point to occur:

1. the graph E 1 of ψ on S 1 ; 2. the graph E 2 of ψ on S 2 ; 3. the graph E 3 of ψ on the upper square, [0, 1/2] × [0, 1/2] × {1}.
To rule out E 1 , we compute L(y) as y in the graph of ψ in the interior of E ′ converges to the graph on E 1 . Recalling that the direction corresponding to such a point on V ∩ E 1 is given by v := L f there, we compute the ratio of (v

1 + v 4 )/(v 1 + v 2 + v 3 + v 4 ): - -2 x 2 -4 x 2 y -x 2 y 2 -1 + x 3 y + xy + 2 x 3 y 2 3 x 2 + 6 x 2 y + x 2 y 2 -2 x 3 y + x 4 y 2 + 1 -2 x 3 y 2 . ( 24
)
Routine calculus shows this to attain a maximum value of 12/17 on V o ∩ S 1 , at (1/2, 1/2, 1, 1/4). The same is true of the ratio

(v 2 + v 4 )/(v 1 + v 2 + v 3 + v 4
). Thus points on the graph of ψ on E 1 control asymptotics of N (k, k ′ , n, κ) only when α, β ≤ 12/17. We see from Lemma 4.2 that EX k X k ′ is always exponentially less than (EX) 2 when α, β ≤ 12/17. This rules out E 1 , and an analogous argument rules out E 2 .

To rule out E 3 , we argue combinatorially. Without the factor of 1/(1z) 2 , we have a generating function F := (1z) 2 F ) that counts the number N (k, k ′ , κ, n) of pairs of 2-intervals in which the union of the two intervals contains 1 and n. Suppose, for a given (k, k ′ , κ, n) that

N (k, k ′ , λn, κ) ≥ N (k, k ′ , n, κ) (25)
for some λ ≤ 1 (this can happen, for example when µ = αρ is small). Then

N (k, k ′ , λn, κ) 2 P (k, k ′ , λn, κ) ≥ N (k, k ′ , n, κ) 2 P (k, k ′ , λn, κ) > N (k, k ′ , n, κ) 2 P (k, k ′ , n, κ)
by an exponential factor. But sup α,β,ρ F 2 (α, β, ρ) > 0, so if this supremum is achieved at α = k/n, β = k ′ /n, ρ = κ/n, then the inequality would be reversed. Thus, in a neighborhood of where the supremum is achieved, it is not possible for (25) to hold. Consequently, in this neighborhood the coefficients of F are, on the exponential scale, as large as those of F , whence the minimal point cannot occur on the divisor 1z. Finally, we must rule out x(s) ∈ γ. If x ∈ γ, and (µ, ν, δ, ρ) are the coordinates of s normalized to sum to 1, with α = µ + ρ and

β = ν + ρ, then r❛t❡(α, β, ρ) = µ log x 1 -ν log x 2 -δ log x 3 -ρ log x 4 .
The curve γ is parametrized by (1, 1, 1/t, t), so r❛t❡ = (ρδ) log x 3 . Recalling that the minimal point must lie in the region x 3 := z ≤ 1, and that ρ > δ for α, β ≥ 2/3, we see that we have r❛t❡ ≤ 0 anywhere controlled by a point on γ with α, β ≥ 2/3. It follows that for α, β ≥ 12/17 > 2/3, the minimal point cannot lie on γ. By Lemma 4.2, directions with α < 12/17 are not in a neighborhood of (α * * , α * * , ρ * * ), which completes the proof of the lemma. ✷

Proof of Theorem 6.1: By Proposition 6.2, the rate function r❛t❡ is controlled by a point x(α, β, ρ) with properties stated in the proposition. The foregoing lemma then shows that x ∈ V o ∩ (R + ) 4 , which proves Theorem 6.1. ✷ Let us interpret Theorem 6.1 and its proof. Values of (α, β, ρ) whose corresponding minimal points lie on V o correspond to values of (k, k ′ , n, κ) for which almost all the pairs of 2-intervals counted by N (k, k ′ , n, κ) nearly span the interval [n]. In other words, when the minimal point is on V o , the exponential rate for coefficients of F is the same as that for f , which enumerates pairs of 2-intervals both of which have 1 and n for their first and last element respectively (i) . We have interpreted f as generating a sequence of blocks between common values; it is well known that the statistics of these blocks are asymptotically independent. In particular, the intersection of two independent random 2-intervals, chosen uniformly from pairs of sizes (k, k ′ ), will be almost asymptotically of size N (k/n)N (k ′ /n) in probability. In other words, when the conclusion of Theorem 6.1 holds, the assertion (1) also holds.

Optimization and algebraic simplification

Everything now rests on verifying [START_REF] Arratia | Poisson approximation and the Chen-Stein method[END_REF], namely that the critical point for F 2 (α, β, •) at α • β is actually a maximum. This is mostly one long computer algebra computation. For replicability, we outline the trickier steps. Verification of the maximum can be (and later will have to be) restricted to the diagonal α = β. But in order also to verify (3) we will need a summation over all α and β, so we begin with all the variables.

To find the critical point x(α, β, ρ) = (u 0 , v 0 , z 0 , τ 0 ) ∈ V o for f , we tell Maple to compute the Groebner basis for the ideal generated by [h , (alpha+beta-1+delta) * vv [START_REF] Arratia | Two moments suffice for Poisson approximation: the Chen-Stein method[END_REF] -(1-alpha-delta) * vv [START_REF] Bergeron | On the Similarity of Sets of Permutations and Its Applications to Genome Comparison[END_REF] , vv [START_REF] Arratia | Poisson approximation and the Chen-Stein method[END_REF] * (1-alpha-delta) -vv [START_REF] Arratia | Two moments suffice for Poisson approximation: the Chen-Stein method[END_REF] * (1-beta-delta) , (1-alpha-delta) * vv [START_REF] Baryshnikov | Convolutions of inverse linear functions via multivariate residues[END_REF] -delta * vv [START_REF] Arratia | Two moments suffice for Poisson approximation: the Chen-Stein method[END_REF] ]; where

h := 1 -u * v -(1 + u * v + z -z * u * v + u + v) * t; vv := simplify([u * diff(h,u) , v * diff(h,v) , z * diff(h,z) , t * diff(h,t)]);
this is done using the Basis command of the Groebner package in Maple 10 (earlier versions use variants such as gbasis and name the package differently).

In order to get Maple to halt we had to first use the term ordering tdeg[z,t,alpha,beta,delta,u,v] and then compute a basis in the order plex[z,t,u,alpha,beta,delta,v] for the Groebner basis coming from the previous computation. The resulting Groebner basis has 27 generators, that first one of which (it will be the the last rather than the first in versions of Maple before Maple 10) is an elimination polynomial for v, that is, it contains v, α, β and δ but not z, u or t. Factoring out (v + 1) and the constant term (1αδ), we solve for v to obtain (i) As an aside: when the minimal point is on E 1 , the first 2-interval tends to span only (1 -Θ(1))n of the interval [n]; when it is on E 2 , the second 2-interval is similarly short; when it is on E 3 , the union of the two 2-intervals is short.

-2 + 36 α -4940 α 4 + 1472 α 3 -672 α 12 We may verify, by sign-change rules for polynomials, that twice this plus the second derivative 1/(α 2 (1α) 2 ) of the entropy function is negative for all α > 2/3. This shows ρ = α 2 to be a local maximum for all α > 2/3. [Our research assistant points out that if the derivatives are taken directly in ρ rather than in δ, then the second derivative comes out to be -(2α-1)/[α 2 (1-α) 2 (1-2α+2α 2 )]; doubling and adding the second derivative of the entropy function gives a quantity which is negative for α > ( √ 3-1)/2 ≈ 0.634.] There are several crude numeric ways to see it is a global maximum. For example one may compute an upper bound of -10 for the second derivative at δ = (1α) 2 for α > 12/17. One may then compute an upper bound for the third derivative of 1700 on the region α ≤ 0.847 and any δ. Taylor's Theorem then tells us that the region in which the local maximum is global extends at least 3/170 in the δ direction on either side of the curve δ = (1α) 2 . Away from this curve one may then divide the α-δ plane into grid squares sufficiently small so that when one bounds 2 • r❛t❡ and ❡♥t separately from above on the grid square, the sum of the bounds is less than 2F 1 (α * ). For details, see http://www.math.upenn.edu/˜pemantle/CLP04-grid2.mw

The final piece of the proof of Theorem 4.1 is the verification of (3). From Theorem 6.1 we know that equation ( 12) holds with r❛t❡ given by (23). Having maximized the smooth function F 2 , we see that for a fixed n,

E(k, k ′ , n, κ) := N (k, k ′ , n, κ) 2 P (k, k ′ , n, κ) has a global maximum at r := (r 1 , r 2 , r 3 , r 4 ) = (n + O(1))(α * , α * , 1, α 2 * ) . If |r ′ i -r i | ≤ n 1/2+ǫ for 1 ≤ i ≤ 4 and any ǫ < 1/6, then E(r ′ ) ∼ E(r) exp(-n -1 Q(r ′ -r))
where Q is the quadratic approximation to F 2 . Checking that Q is non-degenerate, we see that we may use a Gaussian approximation to sum the values of E(r ′ ) to yield

r ′ E(r ′ ) = n 3 (2π) 3 H E(r) = O(exp (2nF 1 (α * ))
with H denoting the determinant of the quadratic form Q. This proves Theorem 4. . This is a symmetrized definition, aimed at making some of the analysis easier without fundamentally changing the problem. We may reason heuristically that the least and greatest elements of a typical interval of G will be respectively O(1) and n -O(1), and that the strong intervals of G are a positive fraction of all intervals of G, so that in some sense, the number of strong δ-intervals of a random permutation should behave like the number of δ-intervals of a random permutation. Given a permutation G, let us look at the complement

I c := [n] \ I of a 2-interval I of G.
To say that I is a strong 2-interval of [n] is exactly to say that I c is an independent set of the cycle graph C with edges between each j and (j + 1) modn . To say that G -1 (I) is a strong 2-interval is equivalent to saying that I c is an independent set of the cycle graph G(C) with edges between G(j) and G((j + 1) modn ). Let H = H(G) denote graph with vertex set [n] whose edges are the union of the two n-cycles C and G(C). Then a strong 2-interval of G is exactly the complement of an independent set of H(G). There is a natural question, analogous to the question of how many 2-intervals there are in a typical permutation, namely, Problem: Determine the (quenched) behavior of the random number Z of independent sets of the graph C ∪ G(C).

This appears difficult, and the simplest heuristics misleading. One might expect that Z is asymptotically log-normal for the following reason. Adding or deleting an edge should change the number of independent sets by a factor of Θ(1). Changing an edge to a different edge should therefore also change by such a factor. The randomness in G is the result of Θ(n) random selections, thus there should be a variance of Θ(n) in log Z. We know this reasoning fails for 2-intervals, so it probably fails for strong 2-intervals as well.

Indeed, one may think that for graphs of high girth and average degree d, the log of the number of independent sets is very well approximated by the following mean field heuristic. If n is the number of vertices, then the number of vertex subsets of size k = αn is ∼ Cn -1/2 exp nα log 1 α + (1α) log 1 1α .

Such a set contains ∼ α 2 n 2 /2 pairs, each being an edge of the graph with probability ∼ d/n. A mean field heuristic would say that the probability of a k-set being independent is roughly exp(-α 2 dn/2).

Multiplying by the number of k-sets and taking the log gives

∼ α log 1 α + (1 -α) log 1 1 -α - α 2 d 2 .
For fixed d one may optimize in α. For d = 4, one finds that the optimal α is roughly 0.26064 . . . and that the number of independent sets would then be roughly exp(0.43786 . . . n). For the random graph H this surely fails, since the number of 2-intervals is exponentially lower than this. It appears that d-regularity is a stronger constraint than average degree d. Perhaps a large family of graphs, such as those of average degree d, tends to be subject to the lottery phenomenon, with the typical log number of independent sets falling below the mean of ≈ exp(.437n), while the more homogeneous family of d-regular graphs exhibits the quenched behavior even in the mean. Amid all this speculation, let us prove that the variance of Y must be at least of order (EY ) 2 , ruling out Gaussian behavior. We give a proof for Z instead of Y because the bookkeeping is simpler, with the proof for Y being entirely analogous. Theorem 7.1 There exists a positive number δ such that there is no number c for which Z ∈ [c, (1 + δ)c] with probability at least 1δ. It follows that Z/EZ, which has been shown to be tight, cannot converge to a constant in probability. Lemma 7.2 Let K be any finite graph with degrees bounded by d and let µ be the probability measure which is uniform on independent sets of K. Then for any non-adjacent vertices x, y of K, µ{I : x, y ∈ I} ≥ ǫ d := 2 -2d-2 .

Proof: Let K ′ be the subgraph of K induced on the vertices of K at distance at least 2 from both x and y. Each independent set I of K ′ has at most 2 2d+2 supersets that are subsets of the vertices of K, and at least one of these is an independent set containing both x and y. ✷ Remark 7.3 This is a bad bound, but on the other hand it is sharp (let K be the union of two stars). What is the right constant for d-regular graphs?

Proof of Theorem. Let G be a permutation for which {i, i + 1} and {i ′ , i ′ + 1} are both intervals, and both ascending, i.e., G -1 (i) = j, G -1 (i + 1) = j + 1, G -1 (i ′ ) = j ′ and G -1 (i ′ + 1) = j ′ + 1 for some i, j, i ′ , j ′ . Suppose further that i ′ ≥ i + 3 and that G has no other intervals of size 2. Let A denote the set of such permutations, G. Reasoning from Proposition 2.1, we know that P(A) = (1/4)(2e -2 + o(1)).

For G ∈ A, define φ(G) to be the permutation G ′ such that G ′ (j + 1) = i ′ + 1, G(j ′ + 1) = i + 1, and G ′ agrees with G except on j + 1 and j ′ + 1. The graph H(φ(G)) is the graph H(G) with two extra edges, namely {i, i ′ + 1} and {i ′ , i + 1}. The set of independent sets of φ(G) is therefore a subset of the set of independent sets of G, namely those not containing both endpoints of either new edge. Taking just one new edge into consideration and using Lemma 7.2, we see that the number of independent sets of φ(G) is most 1 -2 -10 times the number of independent sets of G. On the other hand, the measure of the collection {φ(G) : G ∈ A} is (1/2)e -4 + o(1) by reasoning similar to that used in the proof of Proposition 2.1. [The probability of no intervals of size 2 is e -2 and the probability of seeing (i, i ′ , j, j ′ ) as above is (1/4) • 2e -2 .] Choosing δ < 2 -10 completes the proof. ✷

Conclusion

We could also have dealt with a more general problem. We could have allowed gaps of bounded size δ -1 in the positions and gaps of bounded size γ -1 in the positions in the symbols. We call these δ, γ-intervals.

We conjecture that similar results hold for these δ, γ-intervals. Let X (δ,γ) be the number of δ, γ-intervals of G.

For example, the case δ = 2 and γ = 1 would follow using our previous analysis as,

EX (2,1) = k N (n, k)(n -k + 1)
n k and E(X (2,1) ) 2 = k,ℓ,κ N (k, ℓ, n, κ)(nkℓ + κ + 1)P (k, ℓ, n, κ).

  1365-8050 c 2006 Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France

  v0 := 1/2 * (alphaˆ2+4 * beta * alpha-4 * alpha+2 * alpha * delta-betaˆ2 -2 * beta * delta+1-(5-16 * alpha-8 * delta-16 * beta+18 * betaˆ2 -16 * betaˆ2 * delta-32 * alphaˆ2 * beta+40 * beta * alpha+20 * beta * delta +18 * alphaˆ2+20 * alpha * delta+4 * deltaˆ2+alphaˆ4+4 * alphaˆ3 * delta -8 * betaˆ3+8 * alpha * deltaˆ2 * beta+8 * betaˆ3 * alpha+4 * betaˆ3 * delta +14 * betaˆ2 * alphaˆ2-8 * alphaˆ3+4 * alphaˆ2 * deltaˆ2 +12 * beta * delta * alphaˆ2-16 * alphaˆ2 * delta+betaˆ4 -32 * alpha * beta * delta+4 * deltaˆ2 * betaˆ2-8 * deltaˆ2 * beta -8 * alpha * deltaˆ2-32 * betaˆ2 * alpha+12 * betaˆ2 * alpha * delta +8 * beta * alphaˆ3)ˆ(1/2))/(-delta+2 * betaˆ2+2 * beta * delta+1-3 * beta)

  since there are n 2 pairs of positions, and n -1 pairs of adjacent positions. Similarly there are n-2

	2	pairs of pairs of adjacent positions and n 4 quadruples of positions.
	It follows that for |k -j| ≥ 2,

  -296 α 2 + 18580 α 9 (27) -9424 α 10 + 3232 α 11 + 11816 α 5 -20728 α 6 + 27008 α 7 + 64 α 13 -26146 α 8 α 2 2 -12 α + 26 α 2 -24 α 3 + 8 α 4 2 -4 α + 2 + 2 α 2 2 1 -2 α + 2 α 2 (-1 + α)

	2

  1. ✷ 7 A lower variance bound and a related modelLet us call a subset of [n] a strong δ-interval if it intersects all of the intervals of size δ of [n], including cyclic ones, e.g., {n, 1, . . . , δ -1}. For δ = 2, this means a strong interval must be an interval and also must intersect {1, 2}, {1, n} and {n-1, n}. So, for example, the set {1, 3, 4, 6, 7, 8} is always a 2-interval of [n], n ≥ 8, but is only a strong 2-interval if n = 8 or 9. A strong δ-interval of the permutation G is a strong interval such that I and G -1 (I) are strong intervals of[n]

Acknowledgements

Thanks to Kate Davidson (undergraduate research assistant at The University of Pennsylvania) for help with the rigorous numerical bounds in Lemma 4.2 and the computation of the maximum in equation ( 27). We are also grateful to both referees, whose comments led to improvements in the presentation.

Luckily this can be simplified. First, we find the elimination polynomial for u in terms of v, α, β, δ, which is the 3 rd basis element, divided by (1 + v) 2 : upoly := -u * delta * v-u * beta * v+u * v+alpha+delta-u-1+2 * alpha * u; Solving for u and plugging in the value v 0 above yields

where

We then recover a simplified version of v 0 by symmetry, switching α and β:

Continuing with elimination polynomials, we find that

When we set β = α, things become a little simpler. We get

This is now manageable, meaning we can take two derivatives in δ. We get a mess, several pages long, but when we evaluate it at δ = (1α) 2 (i.e., ρ = α 2 ), the radical becomes a polynomial and we get -8 times the following rational function of α for the second derivative.


Arnold Knopfmacher

Helmut Prodinger

The first descent in samples of geometric random variables and permutations

Keywords: geometric random variables, generating function, limiting distribution, descents

For words of length n, generated by independent geometric random variables, we study the average initial and end heights of the first strict and weak descents in the word. Higher moments and limiting distributions are also derived. In addition we compute the average initial and end height of the first descent for a random permutation of n letters.

Introduction

Let X denote a geometrically distributed random variable, i. e. P{X = k} = pq k-1 for k ∈ N and q = 1 -p. The combinatorics of n geometrically distributed independent random variables X 1 , . . . , X n has attracted recent interest, especially because of applications in computer science. We mention just two areas, the skip list (1; 6; 12; 15) and probabilistic counting (2; 4; 5; 7).

• Skip lists are an alternative to tries and digital search trees. For each data, a geometric random variable defines the number of pointers that it contributes to the data structure. (The data structure is non-deterministic and is randomly constructed using a geometric random variable.) These pointers are then connected in a specific way that makes access to the data manageable. The analysis leads to parameters that are related to left-to-right maxima.

• Probabilistic counting uses hashing and the position of the first digit 1 when reading the binary representation of the hashed value from right to left. This is a geometric random variable with parameter p = q = 1 2 . Thus one has an urn model, with urns labelled 1, 2, . . ., and the relevant parameter here is the number of non-empty urns (starting with the first urn).

One of the first combinatorial questions investigated for words a 1 . . . a n , with the letters a i independently generated according to the geometric distribution, was the number of left-to-right maxima in [START_REF] Prodinger | Combinatorics of geometrically distributed random variables: Left-to-right maxima[END_REF]. In [START_REF] Knopfmacher | Combinatorics of geometrically distributed random variables: Value and position of the rth left-to-right maximum[END_REF] the study of left-to-right maxima was continued, but now the parameters studied were the mean value and mean position of the r-th maximum.

More recently the authors [START_REF] Knopfmacher | Descents in samples of geometric random variables[END_REF] studied the number of descents in a string of n geometrically distributed independent random letters. For example in w = 225114431 we have 2 strict and 6 weak descents (equality is included in the weak case). We continue the study of descents in this article by considering the initial and end heights and hence the size (magnitude of the first jump down) of the first descent in such a string. In our example word w the initial and end heights of the first descent are respectively 5 and 1 (strict case) and 2 and 2 (weak case). In this paper strict descents are considered in Section 2 and weak descents in Section 3. The limiting behaviour as q → 1 is investigated in Section 4.

Many permutation statistics can be deduced from the corresponding geometric random variable statistic by letting q → 1. However, this does not apply in the case of descent heights, so we consider separately the initial and end heights of the first descent for a random permutation of n letters in Section 5.

Strict descents

The end height of the first strict descent

For the end height of the first strict descent in a sample of geometrically distributed random variables we use the following decomposition. If a random word has at least one strict descent, then it begins with a weakly increasing sequence of values ending in some value h ≥ 2, which is followed by a letter smaller than h (the first descent). Thereafter the letters of the word can be an arbitrary sequence of geometrically distributed random variables. Alternatively, a random word has no strict descent at all, in which case it is a weakly increasing word. This gives the following decomposition for the set of all words: {all words}= h≥2 {weakly increasing word ending with h}{letter< h}{any word} ∪{weakly increasing word}.

We now consider a probability generating function F (z, u), where z labels the number of random variables, and u marks the end height of the first strict descent. Consider the case of words with at least one strict descent. Firstly, the generating function for weakly increasing words with values at most h is given by the product h j=1 1 1-pq j-1 z . Then the end letter h of this increasing word has generating function pq h-1 z. The subsequent value (first descent) is marked by u and has any value from 1 to h -1, with generating function h-1 i=1 pq i-1 u i z. The arbitrary word that follows the first descent then has generating function 1 1-z . Finally, words with no descent have generating function j≥1 1 1-pq j-1 z . This leads to

F (z, u) = h≥2 h j=1 1 1 -pq j-1 z pq h-1 z h-1 i=1 pq i-1 u i z 1 1 -z + j≥1 1 1 -pq j-1 z = 1 1 -z h≥2 h j=1 1 1 -pq j-1 z pq h-1 puz 2 (1 -q h-1 u h-1 ) 1 -qu + j≥1 1 1 -pq j-1 z . (2.1)
Remark. By definition F (z, 1) = 1 1-z , however, in order to deduce this from the above expression for F (z, u) we require the following proposition whose proof we relegate to the Appendix 6:

Proposition 1 h≥1 pzq 2h h j=1 1 1 -pq j z = 1 z j≥1 1 1 -pq j z -1 -q. (2.2)
We will also make use of Proposition 1 in order to simplify some of our expressions for the mean values of parameters.

For the mean end height of the first descent we must compute ∂ ∂u F (z, 1). Now

∂ ∂u F (z, 1) = z 2 1 -z h≥2 q h-1 1 -hq h-1 + (h -1)q h h j=1 1 1 -pq j-1 z . (2.3)
Since the dominant pole is at z = 1 we have by singularity analysis (3),

[z n ] ∂ ∂u F (z, 1) ∼ h≥1 q h-1 1 -(h + 1)q h + hq h+1 h j=1 1 1 -pq j = 1 pq h≥1 pq h -pq 2h + (q -1)hpq 2h h j=1 1 1 -pq j = 1 p + (q -1) h≥1 hq 2h-1 h j=1 1 1 -pq j ,
by using (2.2) and one of Euler's partition identities:

n≥0 x n (q) n = 1 (x) n . (2.4)
For notational convenience here and below, we make use of the q-series notation (x) n := (1 -x)(1xq) . . . (1 -xq n-1 ). Thus we have shown Theorem 1 The expected end height of the first strict descent is asymptotically as n → ∞,

1 p - h≥1 hpq 2h-1 1 (pq) h . (2.5)

Higher moments and limiting distributions

From (2.1), the r-th moment about the origin of the end height for r ≥ 1 is just

p 2 z 2 1 -z h≥2 k≥0 (k + 1) r q k -(k + h) r q k+h-1 h j=1 1 1 -pq j-1 z . (2.6)
Since the dominant pole is at z = 1, singularity analysis implies that this is asymptotic to the constant

ν s r (q) := p 2 h≥2 k≥0 (k + 1) r q k -(k + h) r q k+h-1 h j=1 1 1 -pq j-1 .
For the distribution, if F (z, u) = n≥0 p n (u)z n then again by singularity analysis around z = 1

p n (u) → p s E (u) := h≥2 h j=1 1 1 -pq j-1 pq h-1 pu(1 -q h-1 u h-1 ) 1 -qu . (2.7)
So the end descent height has a discrete limiting distribution.

The initial height and size of the first strict descent

We now consider a probability generating function F (z, u), where z labels the number of random variables, and u marks the initial height of the first strict descent.

Let us use the following decomposition again

{all words}= h≥2 {weakly increasing word ending with h}{letter< h}{any word} ∪{weakly increasing word}.

This leads to

F (z, u) = h≥2 h j=1 1 1 -pq j-1 z pu h q h-1 z h-1 i=1 pq i-1 z 1 1 -z + j≥1 1 1 -pq j-1 z = pz 2 1 -z h≥2 u h q h-1 (1 -q h-1 ) h j=1 1 1 -pq j-1 z + j≥1 1 1 -pq j-1 z . (2.8)
For the mean initial height of the first descent we must compute ∂ ∂u F (z, 1). Now

∂ ∂u F (z, 1) = pz 2 1 -z h≥2 hq h-1 (1 -q h-1 ) h j=1 1 1 -pq j-1 z . (2.9)
Since the dominant pole is at z = 1 we have by using (2.2) and Euler's partition identity (2.4). Therefore we have shown

[z n ] ∂ ∂u F (z, 1) ∼ p q h≥1 (h + 1)q h (1 -q h ) h j=1 1 1 -pq j = h≥1 hpq h-1 1 (pq) h - h≥1 hpq 2h-1 1 (pq) h + 1 q h≥1 pq h 1 (pq) h - 1 q h≥1 pq 2h 1 (pq) h = h≥1 hpq h-1 1 (pq) h - h≥1 hpq 2h-1 1 (pq) h + 1 (
Theorem 2
The expected initial height of the first strict descent is asymptotically as n → ∞,

h≥1 hpq h-1 1 (pq) h - h≥1 hpq 2h-1 1 (pq) h + 1. (2.10)
The mean size of the first descent is obtained by subtracting the mean end height from the mean initial height of the first descent. From Theorems 1 and 2 we obtain Theorem 3 The expected size of the first strict descent is asymptotically as n → ∞,

h≥1 hpq h-1 1 (pq) h - q p . (2.11)
Figure 1 illustrates the dependence on q of the mean initial height 1(a), end height 1(b) and size of the first strict descent 1(c). As q → 0, the initial height, end height and size tend, respectively to 2, 1 and 1. These parameters then grow as q increases. The growth as q → 1 will be quantified in Section 4.

Higher moments and limiting distributions

The r-th moment about the origin of the initial height is just

pz 2 1 -z h≥2 h r q h-1 (1 -q h-1 ) h j=1 1 1 -pq j-1 z . (2.12)
Since the dominant pole is at z = 1, singularity analysis implies that this is asymptotic to the constant

µ s r (q) := p q h≥1 (h + 1) r q h (1 -q h ) h j=1 1 1 -pq j .
For the distribution, if F (z, u) = n≥0 p n (u)z n then again by singularity analysis around z = 1

p n (u) → p s I (u) := h≥2 pu h q h-1 (1 -q h-1 ) h j=1 1 1 -pq j-1 .
(2.13)

So the initial descent height also has a discrete limiting distribution.

3 Weak descents

The end height of the first weak descent

We now consider a probability generating function F (z, u), where z labels the number of random variables, and u marks the end height of the first weak descent.

We use the following decomposition {all words}= h≥1 {strictly increasing word ending with h}{letter≤ h}{any word} ∪{strictly increasing word}.

This leads to

F (z, u) = h≥1 h-1 j=1 (1 + pq j-1 z)pq h-1 z h i=1 pq i-1 u i z 1 1 -z + j≥1 (1 + pq j-1 z) = 1 1 -z h≥1 h-1 j=1 (1 + pq j-1 z)pq h-1 puz 2 (1 -q h u h ) 1 -qu + j≥1 (1 + pq j-1 z). (3.1)
Once again to verify that F (z, u) gives 1 1-z when u = 1 requires an identity (also proved in the Appendix 6):

Proposition 2 h≥0 pzq 2h+1 h-1 j=0 (1 + pq j z) = 1 z j≥0 (1 + pq j z) -1 -1. (3.2)
For the mean end height of the first weak descent we must compute ∂ ∂u F (z, 1). Now

∂ ∂u F (z, 1) = z 2 1 -z h≥1 q h-1 1 -(h + 1)q h + hq h+1 h-1 j=1
(1 + pq j-1 z).

(3.3)

Since the dominant pole is at z = 1 we have

[z n ] ∂ ∂u F (z, 1) ∼ h≥1 q h-1 1 -(h + 1)q h + hq h+1 h-1 j=1 (1 + pq j-1 ) = h≥0 q h -q 2h+1 h-1 j=0
(1 + pq j ) + (q -1)

h≥1 hq 2h-1 h-2 j=0 (1 + pq j ) = 1 p + (q -1) h≥0 (h + 1)q 2h+1 h-1 j=0
(1 + pq j ), by using (3.2). Hence

Theorem 4

The expected end height of the first weak descent is asymptotically as n → ∞,

1 p - h≥0 (h + 1)pq 2h+1 (-p) h .
(3.4)

Higher moments and limiting distributions

The r-th moment about the origin of the weak end height for r ≥ 1 is

p 2 z 2 1 -z h≥1 k≥0 (k + 1) r q k -(k + h + 1) r q k+h h-1 j=1 (1 + pq j-1 z). (3.5)
Since the dominant pole is at z = 1, singularity analysis implies that this is asymptotic to the constant

ν w r (q) := p 2 h≥1 k≥0 (k + 1) r q k -(k + h + 1) r q k+h h-1 j=1
(1 + pq j-1 ).

For the distribution, if F (z, u) = n≥0 p n (u)z n then again by singularity analysis around z = 1

p n (u) → p w E (u) := h≥1 h-1 j=1 (1 + pq j-1 )pq h-1 pu(1 -q h u h ) 1 -qu . (3.6)
So the weak end descent height has a discrete limiting distribution.

The initial height and size of the first weak descent

We now consider a probability generating function F (z, u), where z labels the number of random variables, and u marks the initial height of the first weak descent.

We use again the decomposition {all words}= ∪ h≥1 {strictly increasing word ending with h}{letter≤ h}{any word} ∪{strictly increasing word}.

This leads to Since the dominant pole is at z = 1 we have

F (z, u) = h≥1 h-1 j=1 (1 + pq j-1 z)pq h-1 u h z h i=1 pq i-1 z 1 1 -z + j≥1 (1 + pq j-1 z) = z 2 1 -z h≥1 pq h-1 u h (1 -q h ) h-1 j=1 (1 + pq j-1 z) + j≥1 (1 + pq j-1 z). (3.7) Now ∂ ∂u F (z, 1) = z 2 1 -z h≥1 hpq h-1 (1 -q h ) h-1 j=1 (1 + pq j-1 z). (3.8)
[z n ] ∂ ∂u F (z, 1) ∼ h≥0 (h + 1)pq h (1 -q h+1 ) h-1 j=0 (1 + pq j ) = h≥0 (h + 1)pq h (-p) h - h≥0 (h + 1)pq 2h+1 (-p) h .

Hence

Theorem 5 The expected initial height of the first weak descent is asymptotically as n → ∞,

h≥0 (h + 1)pq h (-p) h - h≥0 (h + 1)pq 2h+1 (-p) h . (3.9)
From Theorems 4 and 5 we obtain

Theorem 6

The expected size of the first weak descent is asymptotically as n → ∞,

h≥0 (h + 1)pq h (-p) h - 1 p . (3.10)
Figure 2 illustrates the dependence on q of the mean initial height 2(a), end height 2(b) and size of the first weak descent 2(c).

Higher moments and limiting distributions

The r-th moment about the origin of the initial weak height is

pz 2 1 -z h≥1 h r q h-1 (1 -q h ) h-1 j=1 (1 + pq j-1 z) (3.11)
and singularity analysis implies that this is asymptotic to the constant

µ w r (q) := p q h≥1 h r q h (1 -q h ) h-1 j=1
(1 + pq j-1 ).

For the distribution, if F (z, u) = n≥0 p n (u)z n then again by singularity analysis around z = 1

p n (u) → p w I (u) := h≥1 pu h q h-1 (1 -q h ) h-1 j=1
(1 + pq j-1 ).

(3.12)

So once again the initial weak descent height has a discrete limiting distribution.

4 The behaviour for q → 1

The figures indicate that the quantities in Theorems 1, 2 and 3, as well as in Theorems 4, 5 and 6 tend to infinity as q → 1. We will quantify this observation in this section.

We will make use of Heine's formula

m≥0 (a) m (b) m t m (q) m (c) m = (b) ∞ (at) ∞ (c) ∞ (t) ∞ m≥0 (c/b) m (t) m (q) m (at) m (b) m . (4.1)
We start our study with a sum that arises in Theorems 2 and 3,

R 1 := h≥1 hpq h-1 1 (pq) h = p q d dz h≥0 (zq) h 1 (pq) h z=1 .
Now we apply Heine's formula (4.1), with t = zq, a = 0, b = q, and c = pq:

R 2 := h≥0 (zq) h 1 (pq) h = (q) ∞ (pq) ∞ (zq) ∞ m≥0 (p) m (zq) m (q) m q m .
A further application of Heine's formula, with t = q, a = zq, b = p, and c = 0 turns this into

R 2 = (q) ∞ (pq) ∞ (zq) ∞ (p) ∞ (zq 2 ) ∞ (q) ∞ m≥0 (q) m (q) m (zq 2 ) m p m = q 1 -zq m≥0 p m (zq 2 ) m = q p m≥1 p m (zq) m . Thus R 1 = d dz m≥1 p m (zq) m z=1 = m≥1 p m (q) m m i=1 q i 1 -q i .
At this stage, we can perform the limit for q → 1 and find

lim q→1 R 1 • (1 -q) = m≥1 1 m! m i=1 1 i = m≥1 H m m! = 2.165382215 . . . .
The next computation of a sum that arises in Theorems 1 and 2, is similar:

R 3 := h≥1 hpq 2h-1 1 (pq) h = p q d dz h≥0 (zq 2 ) h 1 (pq) h z=1 .
We apply Heine's formula, with t = zq 2 , a = 0, b = q, and c = pq:

R 4 := h≥0 (zq 2 ) h 1 (pq) h = (q) ∞ (pq) ∞ (zq 2 ) ∞ m≥0 (p) m (zq 2 ) m (q) m q m .
A further application of Heine's formula, with t = q, a = zq 2 , b = p, and c = 0 turns this into

R 4 = (q) ∞ (pq) ∞ (zq 2 ) ∞ (p) ∞ (zq 3 ) ∞ (q) ∞ m≥0 (q) m (q) m (zq 3 ) m p m = q 1 -zq 2 m≥0 p m (zq 3 ) m = q p m≥1 p m (zq 2 ) m . Thus R 3 = d dz m≥1 p m (zq 2 ) m z=1 = m≥1 p m (q 2 ) m m+1 i=2 q i 1 -q i .
We can perform the limit for q → 1 and find

lim q→1 R 3 • (1 -q) = m≥1 1 (m + 1)! m+1 i=2 1 i = m≥2 H m -1 m! = m≥1 H m m! -e + 1,
From this we infer e. g., that the quantity in Theorem 2 behaves for q → 1 as

h≥1 hpq h-1 1 (pq) h - h≥1 hpq 2h-1 1 (pq) h + 1 ∼ e -1 1 -q .
Next, we consider a sum arising in Theorems 5 and 6,

R 5 := h≥0 (h + 1)pq h (-p) h = d dz pz h≥0 (zq) h (-p) h z=1 .
We use Heine's formula; t = zq, a = -p, b = q, c = 0:

R 6 := h≥0 (zq) h (-p) h = (q) ∞ (-pqz) ∞ (zq) ∞ m≥0 (zq) m (q) m (-pqz) m q m .
We use Heine's formula again; t = q, a = zq, b = 0, c = -pqz. For this, (c/b) m b m has to be interpreted as

(b -c)(b -c) . . . (b -cq m-1
), after which b can be replaced by zero;

R 6 = (q) ∞ (-pqz) ∞ (zq) ∞ m≥0 (zq) m (q) m (-pqz) m q m = (q) ∞ (-pqz) ∞ (zq) ∞ (zq 2 ) ∞ (-pqz) ∞ (q) ∞ m≥0 (-1) m q ( m 2 ) (-pqz) m (q) m (q) m (zq 2 ) m = 1 1 -zq m≥0 q ( m 2 ) (pqz) m (zq 2 ) m = 1 pz m≥1 q ( m 2 ) (pz) m (zq) m .
Hence

R 5 = d dz m≥1 q ( m 2 ) (pz) m (zq) m z=1 = m≥1 q ( m 2 ) p m (q) m m + m i=1 q i 1 -q i . Thus lim q→1 R 5 • (1 -q) = m≥1 H m m! = 2.165382215.
Finally, a similar calculation for a sum found in Theorems 4 and 5:

R 7 := h≥0 (h + 1)pq 2h+1 (-p) h = d dz pqz h≥0 (zq 2 ) h (-p) h z=1 .
We use Heine's formula; t = zq 2 , a = -p, b = q, c = 0:

R 8 := h≥0 (zq 2 ) h (-p) h = (q) ∞ (-pqz 2 ) ∞ (zq 2 ) ∞ m≥0 (zq 2 ) m (q) m (-pqz 2 ) m q m .
We use Heine's formula again; t = q, a = zq 2 , b = 0, c = -pqz 2 :

R 8 = (q) ∞ (-pqz 2 ) ∞ (zq 2 ) ∞ (zq 3 ) ∞ (-pqz 2 ) ∞ (q) ∞ m≥0 (-1) m q ( m 2 ) (-pq 2 z) m (q) m (q) m (zq 3 ) m = 1 1 -zq 2 m≥0 q ( m 2 ) (pq 2 z) m (zq 3 ) m = 1 pqz m≥1 q ( m 2 ) (pqz) m (zq 2 ) m . Hence R 7 = d dz m≥1 q ( m 2 ) (pqz) m (zq 2 ) m z=1 = m≥1 q ( m 2 ) (pq) m (q 2 ) m m + m+1 i=2 q i 1 -q i . Thus lim q→1 R 7 • (1 -q) = m≥1 H m+1 -1 (m + 1)! = m≥1 H m m! -e + 1.
5 The height of the first descent in permutations

Initial height of first descent in permutations

Various permutation statistics, such as the number of descents ( 9) can be deduced from the corresponding geometic random variable statistic by letting q → 1. However, as q → 1, the values of the geometric sample do not correspond to those of the set {1, 2, . . . , n}, so one cannot deduce the initial height of the first descent in a permutation of the set {1, 2, . . . , n} from the corresponding geometic random variable statistic. We therefore consider this question separately. Suppose that this initial descent height is k. If this occurs in position j + 1 then we have k -1 choices for the element that follows k in the permutation and k-2 j choices for the elements that form the strictly increasing sequence of j -1 values that preceed k. There are (n -j -2)! arrangements of the remaining elements to complete the permutation. Hence the total number of permutations with initial descent height

k is k-2 j=0 (k -1) k -2 j (n -j -2)! . (5.1)
As all permutations of n-letters other than {1, 2, . . . , n} have a descent, if we sum (5.1) over k we obtain the identity

n k=2 (k -1) k-2 j=0 k -2 j (n -j -2)! = n! -1. (5.2)
A direct proof is as follows

A := n k=2 (k -1) k-2 j=0 k -2 j (n -j -2)! = n-2 j=0 (n -j -2)! j! n k=j+2 (k -1)! (k -2 -j)! = n-2 j=0 (n -j -2)!(j + 1) n k=j+2 k -1 j + 1 = n-2 j=0 (n -j -2)!(j + 1) n j + 2 = n! n-2 j=0 1 (j + 1)! - 1 (j + 2)! = n! -1.
The average initial height is then given by the expression

h(n) n! := 1 n! n k=2 k(k -1) k-2 j=0 k -2 j (n -j -2)! .
(5.3)

Theorem 7 We have h(n) n! = (n + 1) n-1 j=0 1 j! -2 + 2 (n + 1)! ∼ (e -2)(n + 1),
as n → ∞, where e -2 = 0.7182818284 . . . .

Proof:

We have

B := 1 n! n k=2 k(k -1) k-2 j=0 k -2 j (n -j -2)! = 1 n! n-2 j=0 (n -j -2)! j! n k=j+2 k! (k -2 -j)! = 1 n! n-2 j=0 (n -j -2)!(j + 1)(j + 2) n k=j+2 k j + 2 = 1 n! n-2 j=0 (n -j -2)!(j + 1)(j + 2) n + 1 j + 3 = (n + 1) n-2 j=0 (j + 1)(j + 2) (j + 3)! = (n + 1) n-2 j=0 1 (j + 1)! - 2 (j + 2)! + 2 (j + 3)! = (n + 1) n-1 j=0 1 j! -2 + 2 (n + 1)! ∼ (n + 1)(e -2).

✷

Remark. We note that h(n) satisfies the recurrence h(1) = 0, h(n) = (n + 1)h(n -1) + n(n -1) for n ≥ 2. In addition one easily sees that(n + 1)!(e -2) -h(n) = n + δ n , where 0 < δ n ≤ δ 1 < 1. This gives the formula h(n) = ⌊(e -2)(n + 1)! -n⌋ for n ≥ 1.

The h(n) sequence 0, 2, 14, 82, 512, 3614, 28954, 260642, 2606492, 28671502, 344058134, 4472755874, . . . is not in Sloane (16).

End height of first descent in permutations

As in the previous section, one cannot deduce the end height of the first descent in a permutation of the set {1, 2, . . . , n} from the corresponding geometic random variable statistic, as q → 1.

Suppose that this end descent height is m and the initial descent height is k > m. If k occurs in position j + 1 then we have n -m choices for the value of k and k-2 j choices for the elements that form the strictly increasing sequence of j -1 values that preceed k. There are (n -j -2)! arrangements of the remaining elements to complete the permutation. Hence the total number of permutations with end

descent height m is n k=m+1 k-2 j=0 k -2 j (n -j -2)! . (5.4)
As all permutations of n-letters other than {1, 2, . . . , n} have a descent, if we sum (5.4) over m we obtain the identity

n-1 m=1 n k=m+1 k-2 j=0 k -2 j (n -j -2)! = n! -1. (5.5)
A direct proof is

C := n-1 m=1 n k=m+1 k-2 j=0 k -2 j (n -j -2)! = n k=2 k-1 m=1 k-2 j=0 k -2 j (n -j -2)! = n k=2 (k -1) k-2 j=0 k -2 j (n -j -2)! = A.
The average end height is then given by the expression

g(n) n! := 1 n! n-1 m=1 m n k=m+1 k-2 j=0 k -2 j (n -j -2)! . ( 5

✷

From Theorems 7 and 8 the mean size of the first descent is also asymptotic to (e/2 -1)(n + 1) as n → ∞.

The g(n) sequence for n ≥ 1 is 0, [START_REF] Devroye | A limit theory for random skip lists[END_REF][START_REF] Kirschenhofer | Analysis of a splitting process arising in probabilistic counting and other related algorithms[END_REF]41,256,1807,14477,130321,1303246,14335751,172029067,2236377937, . . . is A080047 in Sloane [START_REF] Sloane | The encyclopaedia of integer sequences[END_REF]. It is described there as the operation count to create all permutations of n distinct elements using Algorithm L (lexicographic permutation generation) from Knuth (11, chapter 7.2.1.2). The term g(n -1) for n ≥ 2 gives the number of times l has to be repeatedly decreased in step L3. Knuth [START_REF] Knuth | The art of computer programming, volume 3: Sorting and Searching[END_REF] also studies the lengths of the runs in permutations.

Sloane also has the recurrence g(1) = 0, g(n) = (n + 1)g(n -1) + n(n -1)/2 for n ≥ 2 and the formula g(n) = ⌊(e/2 -1)(n + 1)! -n/2⌋ for n ≥ 1.

Appendix

Proof of Proposition 1:

We will make use of Heine's formula (4.1). We wish to evaluate

X := h≥1 pzq 2h h j=1 1 1 -pq j z = pz n≥0 q 2n 1 (pqz) n -1 .
Set ξ := n≥0 q 2n 1 (pqz) n and use Heine's formula with parameters t = q 2 , a = 0, b = q, c = pqz:

ξ = (q) ∞ (pqz) ∞ (q 2 ) ∞ m≥0 (pz) m (q 2 ) m (q) m q m = 1 (pqz) ∞ m≥0 (pz) m (q) m+1 (q) m q m = 1 (pqz) ∞ m≥0
(pz) m q mq (pqz) ∞ m≥0

(pz) m q 2m . (6.1)

Now compute the first sum, again with Heine's formula: t = q, a = q, b = pz, c = 0: (and then Euler's partition identity (2.4)) m≥0

(pz) m q m = (pz) ∞ (q 2 ) ∞ (q) ∞ m≥0 (q) m (q) m (q 2 ) m (pz

) m = (pz) ∞ pz m≥0 1 (q) m (pz) m -1 = (pz) ∞ pz 1 (pz) ∞ -1 = 1 pz - (pz) ∞ pz . (6.2)

Fig. 1 :

 1 Fig. 1: Mean initial height, end height and size of the first strict descent as a function of q.

( a )Fig. 2 :

 a2 Fig. 2: Mean initial height, end height and size of the first weak descent as a function of q.

7 )

 7 as n → ∞, where e/2 -1 = 0.3591409142 . . . .

† This material is based upon work supported by the National Research Foundation under grant number 2053740 ‡ This material is based upon work supported by the National Research Foundation under grant number 2053748 1365-8050 c 2006

Now compute the second sum, again with Heine's formula: t = q 2 , a = q, b = pz, c = 0: (and then (2.4)

Then using (6.1) together with (6.2) and (6.3),

Apply Heine's formula with t = q 2 , a = q, b = -pz, c = 0:

And finally

✷