SORTING WITH UNRELIABLE COMPARISONS: A PROBABILISTIC ANALYSIS

LAURENT ALONSO, PHILIPPE CHASSAING, FLORENT GILLET, SVANTE JANSON, EDWARD M. REINGOLD, AND RENÉ SCHOTT

Abstract. We provide a probabilistic analysis of the output of Quicksort when comparisons can err.

1. Introduction

Suppose that a sorting algorithm unknowingly uses element comparisons that can err; that is, considering sorting algorithms based solely on binary comparisons of the elements to be sorted (algorithms such as insertion sort, selection sort, quicksort, and so on), what problems do we face when those comparisons are unreliable? For example, [3] gives a clever O (ϵ^{−1} log n) algorithm to assure, with probability 1 − ϵ, that a putatively sorted sequence of length n is truly sorted. But knowing the structure of the ill-sorted output would likely make error checking easier. As a first step in order to understand this structure, we propose to analyze the number of inversions in the output of a sorting algorithm (we choose Quicksort [6]) subject to errors.

We assume throughout this paper that the elements of the sequence

x = (x_{1}, x_{2}, …, x_{n})

to be sorted are distinct. We assume further that the only comparisons subject to err are those made between elements being sorted; that is, comparisons among indices, and so on are always correct. Errors in element comparisons are random events, spontaneous and independent of each other, of position, and of value, with a common probability p, n being the length of the list to be sorted. The number of inversions in the output sequence y = (y_{1}, y_{2}, …, y_{n}) is denoted

I(y) = # {(i, j), 1 ≤ i < j ≤ n | y_{i} > y_{j} } .

We assume that the input list is sorted in random order, each of the n! random orders being equiprobable. Finally we denote by I(n, p) the random number of inversions in the output sequence of Quicksort subject to errors.

Our result is, roughly speaking,

I(n, p) = O (n^{2}p) ,

in the sense that \frac{I(n,p)}{n^{2}p} converges in distribution to some nondegenerate random variable X which is characterized by a functional equation. The ”surprise”, not so unexpected afterwards, is that there are phase changes in the limit law, depending on the asymptotic behaviour of p. Here and later we regard n and p as independent variables. In the limit results we always assume n → ∞ and p → c ∈ [0, 1], often with further conditions added.

Date: January 21, 2003.

The organization of this paper is as follows: The results are stated in Section 2. In Section 3, we establish a general functional equation for I(n, p). In the remaining sections, we prove convergence results for I(n, p) when:

• p → c, 0 < c ≤ 1,

• p vanishes slower than 1/n,

• p ≃ λ/n where λ is a positive constant. The case np → 0 is different and not treated in detail, see Remark 2.8. In Section 4, we establish a general result of convergence using contraction methods (cf. [10, 11]), and we use it in Section 5 , for the first two cases. These methods do not apply for Case 3, which requires poissonization (see Section 6, where we use an embedding of Quicksort in a Poisson point process).

2. Results

Set

X_{n,p} = \frac{I(n, p)}{n^{2}p}.

We will always let U denote a random variable that is uniformly distributed on [0, 1]. Also, ℕ^{∗} shall denote the set of positive integers, and ℕ the set of nonnegative integers.

Case 1: lim p = c > 0.

Theorem 2.1. If lim p = c, c ∈]0, 1], X_{n,p} converges in distribution to a random variable X_{c} whose distribution is characterized as the unique solution with finite mean of the equation

X_{c} =^{law} [(1 − 2c)U + c]^{2}X_{c} + [(2c − 1)U + 1 − c]^{2}X̃_{c} + T (c, U), (1)

in which X̃_{c} denotes an independent copy of X_{c}, both are independent of U, and

T (c, U) = \frac{1 − c}{2}(U^{2} + (1 − U)^{2}) + cU(1 − U).

Furthermore,

𝔼 [X_{c}] = \frac{2 − c}{2(1 + 2c − 2c^{2})},

and

Var (X_{c}) = \frac{(1 − c)^{2}(1 − 2c)^{2}}{4(1 + 2c − 2c^{2})^{2}(3 + 6c − 8c^{2} + 4c^{3} − 2c^{4})}.

As usual with laws related to Quicksort, see e.g. [10, 11], Un is approximately the position of the pivot of the first step of the algorithm. As in standard Quicksort recurrences, the coefficients of X_{c} and of its independent copy X̃_{c} are related to the sizes of the two sublists on the left and right of the pivot, sizes respectively asymptotic to ((1 − 2c)U + c) n and ((2c − 1)U + 1 − c) n. The toll function T (c, U) is approximately (n^{2}p)^{−1} ≈ (n^{2}c)^{−1} times the number of inversions created in the first step: c(1 − c)U^{2}n^{2}/2 is approximately the number of inversions of the cUn elements, smaller than the pivot but misplaced on the right of it, with the elements smaller than the pivot, that are placed, as they should be, on the left, and c^{2}U(1 − U)n^{2} is the number of inversions between misplaced elements from the two sides of the pivot. The toll function T (c, U) depends on only one of the two sources of randomness (the randomly sorted input list, and the places of the errors), viz. the first one, through U. The second source of randomness is killed by the law of large numbers: in the average, each of the cUn + o(n) misplaced numbers from the right of the pivot produces inversions with one half of the (1 − c)Un + o(n) elements smaller than the pivot, that are placed, as they should be, on the left. As opposed to the other values of c, the choices c = 0.5 and c = 1 lead to deterministic X_{c} = 1/2, without any surprise : for p = 0.5 the output sequence is a random uniform permutation, with a number of inversions concentrated around n^{2}/4 ; for p = 1 the output sequence is decreasing, and has n(n − 1)/2 inversions.

Case 2: p vanishes slower than \frac{1}{n}.

Theorem 2.2. If lim p = 0 and lim np = +∞, X_{n,p} converges in distribution to a random variable X whose distribution is characterized as the unique solution with finite mean of the equation

(2)  X =^{law} U^{2}X + (1 − U)^{2}X̃ + \frac{U^{2} + (1 − U)^{2}}{2} .

In (2), X̃ denotes an independent copy of X and both are independent of U. Furthermore,

𝔼 [X] = 1  and  Var (X) = \frac{1}{12}.

Note that equation (2) is just (1) specialized to c = 0. The phase transition between (1) and (2) is due to the fact that for p ≪ 1 the errors do not change anymore the sizes of buckets (and the runtime) in a significant way. The solution X equals half the sum of the squares of the widths of the random intervals [Y_{k,j}, Y_{k,j+1}] defined by (3) below. Also, 2X equals the area ∫_{0}^{1} Z(t) dt under the FIND limit process Z [4], see Remark 2.5.

Case 3: lim np = λ.

Assume that

• Π is a Poisson point process of intensity λ on ℕ^{∗} × [0, 1] (we regard a Poisson process as a random set of points, see [5] for details);

• {U_{k,j} : k ≥ 0, 1 ≤ i ≤ 2^{k}} is an array of independent uniform random variables on [0, 1], independent of Π;

• the random variables Y_{k,j} are defined recursively by

\begin{matrix}Y_{0,0} = 0,  Y_{0,1} = 1,  Y_{k+1,2j} = Y_{k,j}  for 0 ≤ j ≤ 2^{k}, \\ Y_{k+1,2j−1} = (1 − U_{k,j})Y_{k,j−1} + U_{k,j}Y_{k,j}  for 1 ≤ j ≤ 2^{k}; \end{matrix} (3)

• for x ∈ [0, 1], J_{k}(x) = 2j − 1 if Y_{k−1,j−1} ≤ x < Y_{k−1,j}, and define, for λ > 0, (the sum is a.s. finite by Lemma 6.4)

X(λ) = \frac{1}{λ} ∑_{(k,x)∈Π} |x − Y_{k,J_{k}(x)}|. (4)

The variables Y_{k,j} describe a fragmentation process (see also [4] for historical references): we start with [0, 1) and recursively break each interval into two at a random point (uniformly chosen). In the k-th generation we thus have a partition of [0, 1) into 2^{k} intervals I_{k,j}, 1 ≤ j ≤ 2^{k}, with I_{k,j} = [Y_{k,j−1}, Y_{k,j}). The interval of generation k − 1 that contains x is cut at step k at the point Y_{k,J_{k}(x)}. Hence |x − Y_{k,J_{k}(x)}| in (4) is the distance from x to this cut point.

Theorem 2.3. If lim p = 0 and lim np = λ > 0, then X_{n,p} converges in distribution to X(λ). The family {X(λ)}_{λ>0} of random variables satisfy the functional equation:

(5)  X(λ) =^{law} U^{2}X(λU) + (1 − U)^{2}X̃(λ(1 − U)) + Θ(λ, U),

in which, conditionally, given that U = u, X(λU), X̃(λ(1 − U)) and Θ(λ, U) are independent, X(λU) and X̃(λ(1 − U)) are distributed as X(λu) and X(λ(1 − u)), respectively, and

Θ(λ, u) =^{law} \frac{1}{λ} ∑_{i=1}^{N_{λ}} |u − V_{i}| ,

in which N_{λ} is a Poisson random variable with mean λ, the random variables V_{i} are uniformly distributed on [0, 1], and N_{λ}, and the V_{i}’s are independent.

Moreover, {X(λ)}_{λ>0} is (up to equivalence in laws) the only family of random variables satisfying (5) such that, X(λ) ≥ 0 a.s., 𝔼 [X(λ)^{n}] < ∞ for each n ≥ 0, and λ^{2n−1}𝔼 [X(λ)^{n}] → 0 as λ → 0 for each n ≥ 1.

Furthermore,

𝔼 [X(λ)] = 1, Var (X(λ)) = \frac{1}{12} + \frac{1}{3λ}. (6)

Remark 2.4. Note that the functional equations (1), (2) and (5) really are equations for distributions, but it is more convenient to state them for random variables as done here. For (5) to make sense, it is implicitly assumed that the distributions L(X(λ)) depend measurably on λ, i.e. that λ ↦ ℙ (X(λ) ∈ A) is measurable for every Borel set A. (For our X(λ), measurability, and indeed continuity, in λ follows from (8) below.) We do not know whether the extra assumptions in Theorem 2.3 for uniqueness of the solution of (5) are necessary.

Let us comment further on equation (4). Writing Π_{k} = {x : (k, x) ∈ Π} and Π_{k,j} = Π_{k} ∩ I_{k,j}, we can thus rewrite (4) as

(7)  X(λ) = \frac{1}{λ} ∑_{k=1}^{∞} ∑_{j=1}^{2^{k}} ∑_{x∈Π_{k,j}} |x − x_{k,j}|,

where x_{k,j} is either the left or right endpoint of I_{k,j} (depending on whether j is even or odd).

Note that, conditioned on the partitions {I_{k,j}}, i.e. on {Y_{k,j}}_{k,j}, each Π_{k,j} is a Poisson process on I_{k,j} with intensity λ, with the processes Π_{k,j} independent. Since only the distribution of X(λ) matters, we can by this conditioning and an obvious symmetry of the Poisson processes Π_{k,j} just as well let x_{k,j} in (7) be the left endpoint of I_{k,j} for every k and j.

Let Π′ be a Poisson process on (0, 1] × (0, ∞) with intensity 1, and let ξ(t) = ∑_{(x,y)∈Π′, y≤t} x, t ≥ 0. (This is a pure jump Lévy process with Lévy measure 1I_{(0,1]}dt.) Let ξ^{(k,j)}(t) be independent copies of this process, independent of {Y_{k,j}}.

A scaling argument shows that (7) can be written

(8)  X(λ) = \frac{1}{λ} ∑_{k=1}^{∞} ∑_{j=1}^{2^{k}} |I_{k,j}|ξ^{(k,j)}(λ|I_{k,j}|).

Remark 2.5. Let X = \frac{1}{2} ∑_{k=1}^{∞} ∑_{j=1}^{2^{k}} |I_{k,j}|^{2}. Then X satisfies (2), so this is the limit variable X in Theorem 2.2. (X is a.s. finite and has finite mean by Lemma 6.1.) Moreover, the FIND limit process Z in [4] is defined by Z(t) = ∑_{k=1}^{∞} ∑_{j=1}^{2^{k}} |I_{k,j}|1I_{t∈I_{k,j}}; hence ∫_{0}^{1} Z(t) dt = ∑_{k=1}^{∞} ∑_{j=1}^{2^{k}} |I_{k,j}|^{2} = 2X. This justifies the claims made after Theorem 2.2.

Moreover, by the law of large numbers, 𝔼|λ^{−1}ξ(λ) − 1/2| → 0 as λ → ∞. It follows from (8) (by dominated convergence using Lemma 6.1) that 𝔼|X(λ)−X| → 0 and hence X(λ) converges to X in distribution as λ → ∞.

In this third case, we have a system of equations involving an infinite family of laws, and we could not adapt the contraction method: we rather use a poissonization. The phase transition from (2) to (5) is explained easily: instead of a number of errors ≫ 1, we have now O (1) errors at each step, and the law of large numbers does not hold anymore for the number of inversions produced by step 1. Actually the number N_{λ} of errors at the first step is asymptotically Poisson distributed, and the N_{λ} errors are at positions nV_{i}, approximately uniformly distributed on [0, 1]. Thus, the number of inversions caused by this first step is approximately

n ∑_{i=1}^{N_{λ}} |U − V_{i}| ≈ n^{2}pΘ(λ, U).

Remark 2.6. Actually we prove a stronger theorem in each of the three cases, as we prove convergence of laws for the Wasserstein d_{1} metric [9]. It entails convergence of the first moment. The convergence of higher moments is an open problem.

Remark 2.7. As we shall see in Section 6, the distribution tail ℙ (X(λ) ≥ x) decreases exponentially fast (Theorem 6.5).

Remark 2.8. When np → 0 very slowly, that is (np)^{−1} ≪ log n, we conjecture that 2np log (I(n, p)/n) converges in distribution to log U, with the consequence that n^{1−ε} ≪ I(n, p) ≪ n, for any positive ε. Actually, the main contribution to I(n, p) comes from the ”first” error, in some sense. When (np)^{−1} ≃ log n, the probability that no error occurs has a positive limit, and conditionally, given the occurence of at least one error, the situation is similar to the previous case, that is, log (I(n, p)) / log n converges in distribution to a random variable with values in (0, 1). When (np)^{−1} ≫ log n, ℙ (I(n, p) = 0) → 1.

3. Functional equation for the number of inversions

At the first step Quicksort compares all elements of the input list with the first element of the list (usually called pivot). All items less (resp. larger) than the pivot are stored in a sublist on the left (resp. right) of the pivot. Comparisons are not reliable, therefore s_{ℓ} items that should belong to the left sublist are wrongly stored in the right sublist, and s_{r} items larger than the pivot are misplaced in the left sublist.

Since its items are chosen randomly, the input list is a random permutation and the rank of the pivot can be written ⌈nU⌉, where U is uniformly distributed on [0, 1] and ⌈x⌉ is the ceiling of x. Also, s_{ℓ} (resp. s_{r}) is a binomial random variable with parameters (⌈nU⌉ − 1, p) (resp. (n − ⌈nU⌉, p)). Quicksort is then independently applied on the left sublist ℓ and on the right sublist r and new errors occur, producing two new sublists ℓ̃ and r̃. Set

Z_{n,p} = ⌈Un⌉ − s_{ℓ} + s_{r},

so that Z_{n,p} − 1 (resp. n − Z_{n,p}) is the size of ℓ and ℓ̃ (resp. r and r̃).

In order to enumerate the inversions of the output list, we introduce a purely fictitious error-correcting algorithm that parallels the implementation of Quicksort: This fictitious error-correcting algorithm has two recursive steps,

• First, the error-correcting algorithm corrects the sublists ℓ̃(resp. r̃) at costs L = I(ℓ̃) (resp. R = I(r̃), producing two increasing sublists ℓ̂ and r̂. Note that L and R are conditionally independent, given Z_{n,p}. Furthermore, the two sublists ℓ and r obtained at the end of Step 1 are in uniform random order before the second step of Quicksort, so that, conditionally given Z_{n,p}, cost L (resp. R) is distributed as I(Z_{n,p} − 1, p) (resp. I(n − Z_{n,p}, p)).

• Then the error-correcting algorithm corrects the errors of Step 1, at a cost t(n, p) = I(ℓ̂− pivot − r̂). Here ℓ̂− pivot − r̂ stands for the list obtained when one puts ℓ̂, the pivot and r̂ side by side. The number of inversions t(n, p) in the list ℓ̂−pivot−r̂ is analyzed in detail at the end of this section.

These two steps lead to the following equation for I(n, p):

(9)  I(n, p) =^{law} I(Z_{n,p} − 1, p) + I′(n − Z_{n,p}, p) + t(n, p)

where Z_{n,p} = ⌈Un⌉ − s_{ℓ} + s_{r}. We shall obtain the asymptotic distribution of t(n, p), and as a consequence (9) will translate, after renormalisation, in a functional equation satisfied by the limit law of I(n, p)/n^{2}p. The limit law appears on both sides of the functional equation, as expected, due to the recursive structure of Quicksort, and is thus characterized as the fixed point of some transformation.

Description of t(n, p). At the end of the first step of the error-correcting algorithm, we obtain two subarrays ℓ̂ and r̂, left and right of the pivot (cf. Figure 3). They are sorted in increasing order but there are s_{r} (red) elements larger than the pivot just to its left and s_{ℓ} (green) elements smaller than the pivot element just to its right. Thus, the only misplaced elements that the proofreader must correct in step 2 are clustered around the pivot.

In order to sort the list, the red and green sublists must be exchanged. This requires s_{ℓ}s_{r} + s_{ℓ} + s_{r} inversions. We get therefore two unsorted lists ℓ⃗ and r⃗ each composed of two sorted sublists. All items of ℓ⃗ (resp. of r⃗ ) are now smaller (resp. larger) than the pivot, so that the length of ℓ⃗ (resp. of r⃗ ) is ⌈nU⌉ − 1 (resp. n − ⌈nU⌉). It remains to sort ℓ⃗ and r⃗, at respective costs Wℓ⃗ and Wr⃗ that are conditionally independent given U, leading to:

(10)  t(n, p) = s_{ℓ}s_{r} + s_{ℓ} + s_{r} + Wℓ⃗ + Wr⃗.

Figure 1. The error-correcting algorithm.

Figure 2. The two sublists ℓ̂ and r̂.

A model for (Wℓ⃗, Wr⃗). Let W_{m} be the number of inversions in a list of m elements sorted as follows: each element is painted black or white with probability p (resp. 1 − p). Then the black and white sublists are separately sorted in increasing order and the two sorted sublists are placed side by side, producing a new list h with m elements. We have

Proposition 3.1. Let Y_{1}, …, Y_{m} be m independent Bernoulli random variables with the same parameter p, and let S_{m} = Y_{1} + ⋯ + Y_{m}. Then

W_{m} =^{law} ( ∑_{i=1}^{m} iY_{i}) − \frac{S_{m}(S_{m} + 1)}{2}.

Proof. Let us abbreviate S_{m} to S. Among the Y_{i}’s, let Y_{i_{1}}, …, Y_{i_{S}} denote the S random variables equal to 1, Y_{i_{S+1}}, ⋯, Y_{i_{m}} those equal to 0, with i_{1} < ⋯ < i_{S} and i_{S+1} < ⋯ < i_{m}. Now W_{m} can be seen as the number of inversions of the list (i_{j})_{1≤j≤m}. In order to move the numbers i_{j} (j ≤ S) to the correct position, the proofreader corrects inversions with each of the i_{j} − j elements of {1, ⋯, m} that are smaller than i_{j} and do not belong to {i_{1}, ⋯, i_{S}}. Thus

(11)  W_{m} = ∑_{j=1}^{S}(i_{j} − j),

leading to the result. □

With the help of Proposition 3.1, we can give a useful description of the distribution of (s_{ℓ}, Wℓ⃗) and (s_{r}, Wr⃗):

Proposition 3.2. Conditionally, given that the length of ℓ⃗ is m − 1, (s_{ℓ}, Wℓ⃗) and (s_{r}, Wr⃗) are independent and distributed as (S_{m−1}, W_{m−1}) and (S_{n−m}, W_{n−m}), respectively.

To sum up the results of this section, renormalizing (9), one obtains a functional equation satisfied by X_{n,p}:

(12)  X_{n,p} =^{law} A_{n,p}X_{Z_{n,p}−1,p} + B_{n,p}X̃_{n−Z_{n,p},p} + T_{n,p}

in which

(13)  Z_{n,p} = ⌈Un⌉ − s_{ℓ} + s_{r},
(14)  A_{n,p} = (\frac{Z_{n,p} − 1}{n})^{2} ,

(15)  B_{n,p} = (\frac{n − Z_{n,p}}{n} )^{2} ,
(16)  t(n, p) = s_{ℓ}s_{r} + s_{ℓ} + s_{r} + Wℓ⃗ + Wr⃗,
(17)  T_{n,p} = \frac{t(n, p)}{n^{2}p},

and

• U is a uniform random variable on [0, 1], and ⌈nU⌉ is the position of the pivot,

• conditionally, given ⌈nU⌉ = m, (s_{ℓ}, Wℓ⃗) and (s_{r}, Wr⃗) are distributed as in Proposition 3.2,

• X = (X_{m})_{m≥0}, X̃ = \binom{}{X_{m}}_{m≥0} are two independent sequences with the

same unknown distribution, independent of (U, s_{ℓ}, Wℓ⃗, s_{r}, Wr⃗), or, equivalently, of (A_{n,p}, B_{n,p}, Z_{n,p}, T_{n,p}).

The errors having a balancing effect, Z_{n,p} = ⌈Un⌉ − s_{ℓ} + s_{r} has the same mean, (n + 1)/2, and a smaller variation than ⌈Un⌉; we prove this in the following form.

Lemma 3.3.

𝔼 [(Z_{n,p} − 1)^{2} + (n − Z_{n,p})^{2}] ≤ 𝔼 [(⌈Un⌉ − 1)^{2} + (n − ⌈Un⌉)^{2}] = \frac{(n − 1)(2n − 1)}{3}

≤ \frac{2}{3}n^{2}.

Proof. The left hand side is the expected number of pairs i and j that end up on the same side of the pivot. This happens if i and j originally are on the same side of the pivot and we either compare both correctly or make errors for both of them, or if they are on each side of the pivot and we make an error for exactly one of them. Hence

𝔼 [(Z_{n,p} − 1)^{2} + (n − Z_{n,p})^{2}] = (p^{2} + (1 − p)^{2})𝔼 [(⌈Un⌉ − 1)^{2} + (n − ⌈Un⌉)^{2}]

+ 2p(1 − p)2𝔼 [(⌈Un⌉ − 1)(n − ⌈Un⌉)]

= 𝔼 [(⌈Un⌉ − 1)^{2} + (n − ⌈Un⌉)^{2}] − 2p(1 − p)𝔼 [(⌈Un⌉ − 1 − (n − ⌈Un⌉))^{2}]

which proves the first inequality. The rest is a simple calculation. □

Let I^{(k)}(n, p) be the number of inversions created at step k. We shall need the following bound:

Lemma 3.4. For every k ≥ 1,

𝔼 [I^{(k)}(n, p)] ≤ \frac{1}{2} (\frac{2}{3})^{k} n^{2}p.

Proof. For k = 1, I^{(1)}(n, p) = t(n, p), and a simple calculation yields

𝔼 [t(n, p)] = p\frac{(n − 1)(n + 1)}{3} − p^{2} \frac{(n − 1)(n − 2)}{6} ≤ \frac{1}{3}n^{2}p.

For k > 1 we find by induction, conditioning on the partition in the first step,

𝔼 [I^{(k)}(n, p)] ≤ 𝔼 [\frac{1}{2} (\frac{2}{3})^{k−1} (Z_{n,p} − 1)^{2}p + \frac{1}{2} (\frac{2}{3})^{k−1} (n − Z_{n,p})^{2}p]

and the result follows by Lemma 3.3. □

Proposition 3.5. Set a_{n,p} = 𝔼 [X_{n,p}]. Then

a_{n,p} ≤ 1.

Proof. By Lemma 3.4, a_{n,p} ≤ ∑_{1}^{∞} \frac{1}{2} (\frac{2}{3})^{k}. □

4. Fixed point theorems

The proofs of the first two cases are examples of the contraction method [10, 11]: on one hand we have more or less explicitly defined random variables A_{n,p}^{(i)}, 1 ≤ i ≤ I, and T_{n,p}, and we know how to prove directly that they converge to A^{(i)}, T. On the other hand, we have a family X_{n,p} of random variables defined by induction:

(18)  X_{n,p} =^{law} ∑_{i=1}^{I} A_{n,p}^{(i)}X_{Z_{n,p}^{(i)},p}^{(i)} + T_{n,p},

and a random variable X implicitly defined by the following functional equation

(19)  X =^{law} ∑_{i=1}^{I} A^{(i)}X^{(i)} + T,

in which, in some sense, lim Z_{n,p}^{(i)} = +∞. Then, under additional technical conditions, the convergence of the ”coefficients” A_{n,p}^{(i)}, T_{n,p}, entails the convergence of the ”solution” X_{n,p}. One has to prove existence and unicity of the solutions, usually as fixed points of contracting transformations in a subspace of the space of probability measures, with a suitable metric. In the case we are interested in, (18) holds and:

• I is a fixed positive integer;

• C_{n,p} = (A_{n,p}^{(1)}, Z_{n,p}^{(1)}, …, A_{n,p}^{(I)}, Z_{n,p}^{(I)}, T_{n,p}) is a given random vector for each n, p;

• Z_{n,p}^{(i)} ∈ [0, …, n − 1];

• The families (X_{n,p}^{(i)})_{n,p}, i = 1, 2, …, I, are i.i.d. and independent of C_{n,p},

and and X_{n,p}^{(i)} =^{law} X_{n,p}.

Given such C_{n,p} we thus define, for any distributions G_{0,p}, …, G_{n−1,p},

Φ(G_{0,p}, …, G_{n−1,p}) = L (∑_{i=1}^{I} A_{n,p}^{(i)}X_{Z_{n,p}^{(i)},p}^{(i)} + T_{n,p}) ,

when, as above, the families (X_{k,p}^{(i)})_{k,p}, i = 1, 2, …, I, are i.i.d. and independent of

C_{n,p}, and further X_{k,p}^{(i)} has the distribution G_{k,p}. Thus (18) can be written

G_{n,p} = Φ(G_{0,p}, …, G_{n−1,p}).

For (19) we similarly assume • C = (A^{(1)}, …, A^{(I)}, T) is a given random vector;

• the variables X^{(i)}, i = 1, 2, …, I are i.i.d. and independent of C, and

X^{(i)} =^{law} X.

Given such C we define

Ψ(F) = L (∑_{i=1}^{I} A^{(i)}X^{(i)} + T ) ,

when the variables X^{(i)}, i = 1, 2, …, I are i.i.d. with distribution F and independent of C. Then (19) can be written

Ψ(F) = F.

Let D be the space of probability measures μ on ℝ, such that ∫_{ℝ} |x| dμ(x) < +∞. The space D is endowed with the Wasserstein metric

(20)  d_{1}(μ, ν) = inf_{{L(X)=μ \atop L(Y)=ν}} ∥X − Y ∥_{1}

= ∥F^{−1}(U) − G^{−1}(U)∥_{1} .

in which F and G denote the distribution functions of μ and ν, F^{−1} (resp. G^{−1}) denote the generalized inverses of F and G and, as in previous sections, U is a uniform random variable. Since F^{−1}(U) (resp. G^{−1}(U)) has distribution μ (resp. ν), the infimum is attained in relation (20).

The metric d_{1} makes D a complete metric space. Convergence of L(X_{n}) to L(X) in D is equivalent to convergence of X_{n} to X in distribution and

lim 𝔼 [|X_{n}|] = 𝔼 [|X|] ;

also, convergence in D entails

lim 𝔼 [X_{n}] = 𝔼 [X] .

We refer to [9] for an extensive treatment of Wasserstein metrics. In what follows, we shall improperly refer to the convergence of X_{n} to X in D, meaning the convergence of their distributions. Let us take care first of relation (19):

Theorem 4.1. If ∑_{i=1}^{I} 𝔼 [|A^{(i)}|] < 1, then Ψ is a strict contraction and (19) has a

unique solution in D.

Proof. Let (X, Y) be a couple of random variables, with laws μ and ν, respectively, such that

𝔼 [|X − Y |] = d_{1}(μ, ν).

Let ((X^{(i)}, Y^{(i)}))_{1≤i≤I} be I independent copies of (X, Y). Furthermore, assume that C and ((X^{(i)}, Y^{(i)}))_{1≤i≤I} are independent. Then the probability distribution of

∑_{i=1}^{I} A^{(i)}X^{(i)} + T, resp. ∑_{i=1}^{I} A^{(i)}Y^{(i)} + T

is Ψ(μ) (resp. Ψ(ν)) and

d_{1}(Ψ(μ), Ψ(ν)) ≤ ∑_{i=1}^{I} 𝔼 [|A^{(i)}| |X^{(i)} − Y^{(i)}|]

≤ d_{1}(μ, ν) ∑_{i=1}^{I} 𝔼 [|A^{(i)}|] .

Thus Ψ is a contraction with contraction constant smaller than 1. Since D is a complete metric space, this implies that Ψ has a unique fixed point in D, by Banach’s fixed point theorem. □

We prove now a theorem which is a variant of those used by the precited authors: the difference is not deep, but here we deal with family of laws, not sequences, as we have two parameters, n and p. As a consequence, to cover Theorems 2.1 and 2.2, it will be convenient in their proofs to consider convergence with respect to a filter F on ℕ × [0, 1]. The filter F_{1} corresponding to Theorem 2.1 has basis

V_{N,ε} = {n ≥ N} × [c − ε, c + ε] ,

while the filter F_{2} corresponding to Theorem 2.2 has basis

Ṽ_{N,ε} = {(n, p) | 0 < p ≤ ε, n ≥ N/p} .

Theorem 4.2. Suppose that (18) holds for n ≥ 1 and X_{0,p} = 0; i.e. G_{n,p} = Φ(G_{0,p}, …, G_{n−1,p}) for n ≥ 1 and G_{0,p} = δ_{0}, where G_{n,p} = L(X_{n,p}). If

i) (𝔼 [X_{n,p}])_{n,p} is bounded,

ii) ∑_{i=1}^{I} 𝔼 [|A^{(i)}|] < 1,

iii) T_{n,p} ⟶_{F}^{L^{1}} T, A_{n,p}^{(i)} ⟶_{F}^{L^{1}} A^{(i)},

iv) lim_{F} 𝔼 [|A_{n,p}^{(i)}| ; (Z_{n,p}^{(i)}, p) ∉ V ] = 0, ∀V ∈ F,

then

– Ψ is a contraction for d_{1} and the equation Ψ(F) = F has a unique solution F in D.

– X_{n,p} converges in distribution to F. More precisely, d_{1}(G_{n,p}, F) → 0 along F.

We need a lemma.

Lemma 4.3. Assume that three families of nonnegative numbers (a_{n,p}, b_{n,p})_{0≤n,0<p<1}, and (γ_{i,n,p})_{0≤n,0≤i≤n,0<p<1} satisfy the inequalities:

a_{n,p} ≤ b_{n,p} + ∑_{i=0}^{n−1} γ_{i,n,p}a_{i,p},

Let F be a filter. Under the following assumptions:

– a_{n,p} is nonnegative and bounded,

– for some Γ < 1 and some V_{0} ∈ F, ∀(n, p) ∈ V_{0}, ∑_{k=0}^{n−1} γ_{k,n,p} < Γ,

– lim_{F} b_{n,p} = 0,

– ∀V ∈ F, lim_{F} ∑_{k s.t. (k,p)∉V} γ_{k,n,p} = 0, we have

lim_{F} a_{n,p} = 0.

Proof of Lemma 4.3. The proof is also a variant of the proof of [10, Proposition 3.3]. Let M be a bound for a_{n,p}, and let

a = lim sup_{F} a_{n,p}.

For any ϵ > 0, let V_{ϵ} ∈ F be such that for (n, p) ∈ V_{ϵ},

a_{n,p} ≤ a + ϵ.

Then for (n, p) ∈ V_{ϵ} ∩ V_{0} we have

a_{n,p} ≤ ∑_{k s.t. (k,p)∉V_{ϵ}} γ_{k,n,p}a_{k,p} + ∑_{k s.t. (k,p)∈V_{ϵ}} γ_{k,n,p}a_{k,p} + b_{n,p}
≤ M ∑_{k s.t. (k,p)∉V_{ϵ}} γ_{k,n,p} + (a + ϵ)Γ + b_{n,p}.

Going to the limit, we obtain that for any ϵ > 0,

a ≤ (a + ϵ)Γ.
□

Proof of Theorem 4.2. We can choose X^{(i)} and the family (X_{k,p}^{(i)})_{k≥0} in such a way

that

𝔼 [|X_{k,p}^{(i)} − X^{(i)}|] = d_{1}(G_{k,p}, F),

and we can also choose the families (X^{(i)}, (X_{k,p}^{(i)})_{k≥0})_{0≤i≤I} to be i.i.d. Then

d_{1}(G_{n,p}, F) ≤ 𝔼 [| ∑_{i=1}^{I} A_{n,p}^{(i)}X_{Z_{n,p}^{(i)},p}^{(i)} + T_{n,p} − ∑_{i=1}^{I} A^{(i)}X^{(i)} − T |]

≤ ∑_{k=0}^{n−1} 𝔼 [∑_{i=1}^{I} |A_{n,p}^{(i)}1I_{Z_{n,p}^{(i)}=k}|] 𝔼 [|X_{k,p}^{(i)} − X^{(i)}|] + b_{n,p}

≤ ∑_{k=0}^{n−1} γ_{k,n,p} d_{1}(G_{k,p}, F) + b_{n,p}

with

b_{n,p} = ∑_{i=1}^{I} 𝔼 [|A_{n,p}^{(i)} − A^{(i)}|X^{(i)}] + 𝔼 [|T_{n,p} − T |] ,

γ_{k,n,p} = ∑_{i=1}^{I} 𝔼 [|A_{n,p}^{(i)}|1I_{Z_{n,p}^{(i)}=k}] .

Set

a_{n,p} = d_{1}(G_{n,p}, F),

and let us check the assumptions of Lemma 4.3:

0 ≤ a_{n,p} ≤ 𝔼 [X_{n,p}] + 𝔼 [X] ≤ 1 + 𝔼 [X] ;

for the second assumption,

lim sup_{F} ∑_{k=0}^{n−1} γ_{k,n,p} = lim sup_{F} ∑_{i=1}^{I} 𝔼 [|A_{n,p}^{(i)}|] = ∑_{i=1}^{I} 𝔼 [|A^{(i)}|] < 1 ;

lim_{F} b_{n,p} = 0 by assumption iii), as

∑_{i=1}^{I} 𝔼 [|A_{n,p}^{(i)} − A^{(i)}|X^{(i)}] = 𝔼 [X] ∑_{i=1}^{I} 𝔼 [|A_{n,p}^{(i)} − A^{(i)}|] ;

finally

∑_{k s.t. (k,p)∉V} γ_{k,n,p} = ∑_{i=1}^{I} 𝔼 [|A_{n,p}^{(i)}| ; (Z_{n,p}^{(i)}, p) ∉ V ] .

Therefore d_{1}(G_{n,p}, F) vanishes along F and the proof of the theorem is now complete. □

The following Theorem is folklore. It gives the means and variances in Theorems 2.1 and 2.2, after some computations.

Theorem 4.4. Suppose that (19) holds, where ∑_{i} 𝔼 [|A^{(i)}|] < 1 and 𝔼 [|X|] < ∞; in other words, L(X) = F, where F is the unique solution in D to Ψ(F) = F. Then

(21)  𝔼 [X] = \frac{𝔼 [T]}{1 − ∑_{i} 𝔼 [A^{(i)}]}.

Moreover, if further ∑_{i} 𝔼 [|A^{(i)}|^{2}] < 1 and 𝔼 [T^{2}] < ∞, then 𝔼 [X^{2}] < ∞ and

(22) Var (X) = \frac{𝔼 [T^{2}] + 2 𝔼 [X] 𝔼 [T ∑_{i} A^{(i)}] + 𝔼 [(∑_{i} A^{(i)})^{2} − 1] (𝔼 [X])^{2}}{1 − ∑_{i} 𝔼 [A^{(i) 2}]} .

Proof. Taking expectations in (19) we obtain 𝔼 [X] = ∑_{i} 𝔼 [A^{(i)}] 𝔼 [X] + 𝔼 [T], which yields (21).

For the second part, let D_{2} = {μ ∈ D : ∫ x dμ(x) = 𝔼 [X] , ∫ x^{2} dμ(x) < ∞}. It is easy to see that now Ψ is a strict contraction in D_{2} with the d_{2} metric; hence Ψ has a unique fixed point in D_{2}. Since D_{2} ⊂ D, this fixed point must be F, which shows that 𝔼 [X^{2}] < ∞. If we square (19) and take the expectation, we obtain

𝔼 [X^{2}] = 𝔼 [∑_{i=1}^{I} A^{(i) 2}] 𝔼 [X^{2}] + ∑_{i,j=1, i≠j}^{I} 𝔼 [A^{(i)}A^{(j)}] (𝔼 [X])^{2}

+ 2 ∑_{i=1}^{I} 𝔼 [A^{(i)}T ] 𝔼 [X] + 𝔼 [T^{2}] ,

which yields (22). □

5. Proofs of Theorems 2.1 and 2.2

We apply Theorem 4.2 to the functional equation (12), with I = 2,

(A_{n,p}^{(1)}, Z_{n,p}^{(1)}) = (A_{n,p}, Z_{n,p} − 1) ,
(A_{n,p}^{(2)}, Z_{n,p}^{(2)}) = (B_{n,p}, n − Z_{n,p}) .

Here the distribution of (A_{n,p}^{(i)}, Z_{n,p}^{(i)}) does not depend on i. We verify the assumptions i)–iv) of Theorem 4.2 for Theorems 2.1 and 2.2 together; for the second theorem take c = 0. The first assumption holds true by Proposition 3.5.

Verification of the second point. We have

A^{(1)} = A = [(1 − 2c)U + c]^{2},
A^{(2)} = B = [(2c − 1)U + 1 − c]^{2},

and c ∈ [0, 1]. Easy computations give

𝔼 [[(1 − 2c)U + c]^{2}] + 𝔼 [[(2c − 1)U + 1 − c]^{2}] = \frac{2}{3}(1 − c + c^{2}) ≤ \frac{2}{3}.

Verification of the third point. We must prove the convergence of A_{n,p}, B_{n,p} and T_{n,p} to A, B and T (c, U), in L^{1}. Recall (13)–(17).

Note first that, conditioned on U, s_{ℓ} ∼ Bi(⌈nU⌉ − 1, p) and thus

𝔼((s_{ℓ} − (⌈nU⌉ − 1)p)^{2} | U) = (⌈nU⌉ − 1)p(1 − p) ≤ np.

Hence, taking the expectation,

𝔼(s_{ℓ} − (⌈nU⌉ − 1)p)^{2} ≤ np

and thus

∥s_{ℓ} − nUp∥_{2} ≤ ∥s_{ℓ} − (⌈nU⌉ − 1)p∥_{2} + p ≤ (np)^{1/2} + p ≤ 2(np)^{1/2}.

Consequently,

(23)  ∥\frac{s_{ℓ}}{n} − Uc∥_{2} ≤ ∥\frac{s_{ℓ}}{n} − Up∥_{2} + |p − c| → 0,

and, similarly but sharper,

(24)  ∥\frac{s_{ℓ}}{n\sqrt{p}} − U\sqrt{c}∥_{2} ≤ \frac{2}{\sqrt{n}} + \frac{|p − c|}{\sqrt{p}} → 0.

Similarly,

(25)  ∥\frac{s_{r}}{n} − (1 − U)c∥_{2} → 0

and

(26)  ∥\frac{s_{r}}{n\sqrt{p}} − (1 − U)\sqrt{c}∥_{2} → 0.

From (13), (23) and (25) follows

(27)  ∥\frac{Z_{n,p} − 1}{n} − (U − Uc + (1 − U)c)∥_{2} → 0.

It follows easily from Hölder’s inequality that multiplication is a continuous bilinear map L^{2} × L^{2} → L^{1}. Hence (27) yields

∥A_{n,p} − A∥_{1} = ∥(\frac{Z_{n,p} − 1}{n})^{2} − (U − Uc + (1 − U)c)^{2}∥_{1} → 0,

verifying the first assertion. (27) similarly implies ∥B_{n,p} − B∥_{1} → 0 too. For T_{n,p} we first observe that, similarly, from (24) and (26),

∥\frac{s_{ℓ}s_{r}}{n^{2}p} − U(1 − U)c∥_{1} → 0.

Moreover, since np → ∞, (23) and (25) imply ∥s_{ℓ}/n^{2}p∥_{1} ≤ ∥s_{ℓ}/n^{2}p∥_{2} → 0 and ∥s_{r}/n^{2}p∥_{1} → 0.

For the terms Wℓ⃗ and Wr⃗ we use Proposition 3.1. We have ∥S_{m} − mp∥_{2} = \sqrt{mp(1 − p)} and thus, uniformly for 0 ≤ m ≤ n,

∥\frac{S_{m}}{n\sqrt{p}} − \frac{m}{n}\sqrt{c}∥_{2} ≤ \frac{1}{\sqrt{n}} + |\sqrt{p} − \sqrt{c}| → 0,

which, using Hölder again, yields

(28)  ∥\frac{S_{m}(S_{m} + 1)}{2n^{2}p} − \frac{c}{2} (\frac{m}{n})^{2}∥_{1} ≤ \frac{3}{\sqrt{n}} + \frac{1}{n\sqrt{p}} + 3|\sqrt{p} − \sqrt{c}| → 0.

Moreover, let W′_{m} = ∑_{i=1}^{m} iY_{i}. Then 𝔼W′_{m} = \frac{m(m+1)p}{2} and

∥W′_{m} − 𝔼W′_{m}∥_{2}^{2} = Var (W′_{m}) = ∑_{i=1}^{m} i^{2}p(1 − p) ≤ m^{3}p,

and thus

(29)  ∥\frac{W′_{m}}{n^{2}p} − \frac{1}{2} (\frac{m}{n})^{2}∥_{2} ≤ \frac{1}{\sqrt{np}} + \frac{1}{2n} → 0.

Proposition 3.1 now yields, by (28) and (29), uniformly for m ≤ n,

∥\frac{W_{m}}{n^{2}p} − \frac{1 − c}{2} (\frac{m}{n})^{2}∥_{1} → 0.

Consequently, using Proposition 3.2,

∥\frac{Wℓ⃗}{n^{2}p} − \frac{1 − c}{2}U^{2}∥_{1} → 0,
∥\frac{Wr⃗}{n^{2}p} − \frac{1 − c}{2}(1 − U)^{2}∥_{1} → 0.

Collecting the various terms above, we find ∥T_{n,p} − T ∥_{1} → 0.

Verification of the fourth point. We have to check that

lim_{F_{i}} 𝔼 [|A_{n,p}| ; (Z_{n,p}, p) ∉ V ] = 0, ∀V ∈ F_{i}.

But for (n, p) ∈ V_{N,ε} (resp. for (n, p) ∈ Ṽ_{N,ε}),

𝔼 [|A_{n,p}| ; (Z_{n,p}, p) ∉ V_{N,ε}] ≤ (\frac{N − 1}{n})^{2} ,

𝔼 [|A_{n,p}| ; (Z_{n,p}, p) ∉ Ṽ_{N,ε}] ≤ (\frac{N}{np})^{2} .

6. Proof of Theorem 2.3.

The proof of this theorem is done in three steps:

(i) We prove that X(λ) is almost surely finite, and has exponentially decreasing distribution tail. Thus it has moments of all orders.

(ii) With the help of a Poisson point process representation of Quicksort, we prove the convergence of certain copies of X_{n,p} to a copy of X(λ) for the norm ∥.∥_{1}. This entails the weak convergence.

(iii) We prove that X(λ) satisfies the functional equation (5), and that (5) has a unique solution under the extra assumptions in the theorem.

Some properties of X(λ). Recall that the increasing sequence (Y_{k,j})_{0≤j≤2^{k}}, defined by the recurrence relation (3), splits [0, 1] in 2^{k} intervals, obtained recursively by breaking each of the 2^{k−1} intervals of the previous step in two random pieces. For k ≥ 0 and 1 ≤ i ≤ 2^{k}, let

w_{k,i} = Y_{k,i} − Y_{k,i−1},
M_{k} = max {w_{k,i}; 1 ≤ i ≤ 2^{k}},
F_{k,α} = (\frac{1 + α}{2})^{k} ∑_{1≤i≤2^{k}} w_{k,i}^{α}
F_{k} = σ (Y_{i,j}, i ≤ k, 1 ≤ j ≤ 2^{i} − 1)
F = (F_{k})_{k≥0} .

We begin with a simple estimate (see also [4]):

Lemma 6.1. 𝔼 [w_{k,j}^{2}] = 3^{−k}.

Proof. The length w_{k,j} = |I_{k,j}| is the product of k independent random variables, each uniform on [0, 1]. Hence 𝔼 [w_{k,j}^{2}] = (𝔼 [U^{2}])^{k} = 3^{−k}. □

Lemma 6.2. For α > 0, (F_{k,α})_{k≥0} is a F-martingale, and 𝔼 [F_{k,α}] = 1.

Proof. Clearly 𝔼 [F_{0,α}] = 1. Also:

𝔼 [F_{k+1,α}|F_{k}] = (\frac{1 + α}{2})^{k+1} ∑_{i=1}^{2^{k}} 𝔼 [w_{k+1,2i−1}^{α} + w_{k+1,2i}^{α}|F_{k}]

= (\frac{1 + α}{2})^{k+1} ∑_{i=1}^{2^{k}} w_{k,i}^{α}𝔼 [V_{k,i−1}^{α} + (1 − V_{k,i−1})^{α}]

= (\frac{1 + α}{2})^{k} ∑_{i=1}^{2^{k}} w_{k,i}^{α}.

□

Let ρ = 0.792977 … denote the largest solution of the equation ρ = −2e ln ρ. Lemma 6.2 entails that

Lemma 6.3. 𝔼 [M_{k}] ≤ ρ^{k}.

Proof. Clearly,

M_{k}^{α} ≤ (\frac{2}{1 + α})^{k} F_{k,α},

thus, for α ≥ 1,

𝔼 [M_{k}] ≤ 𝔼 [M_{k}^{α}]^{1/α} ≤ (\frac{2}{1 + α})^{k/α} 𝔼 [F_{k,α}]^{1/α} = (\frac{2}{1 + α})^{k/α} .

The rate (\frac{2}{1+α})^{1/α} reaches its minimum for 1 + α = 4.311 …, a constant that is an old friend of Quicksort and binary search trees. This leads to the desired value for ρ. □

A weaker form of this inequality (for α = 2), actually sufficient for our purposes, is given in [4]. The sequence (F_{k,α})_{k≥0} is a specialization of martingales that are of a great use for the study of general branching random walks, see for instance [1], of which binary search trees are a special case [7, 8].

Lemma 6.4. 𝔼 [X(λ)] = 1.

Proof. Set F_{∞} = σ (Y_{k,j}, k ≥ 0, 1 ≤ j ≤ 2^{k} − 1). Inspecting (7), we see that

𝔼 [X(λ) | F_{∞}] = \frac{1}{2} ∑_{k≥1} (\frac{2}{3})^{k} F_{k,2},

because, conditionally given F_{∞}, the expected number of points of Π_{k,j} is λw_{k,j} and each of them has an expected contribution w_{k,j}/(2λ) to X(λ). □

As a consequence of Lemma 6.3, we have

Theorem 6.5. The distribution tail ℙ (X(λ) ≥ x) decreases exponentially fast.

Proof. Equivalently, we prove the first result for Ξ(λ) = λX(λ). Since

|x − Y_{k,J_{k}(x)}| ≤ M_{k},

we have

Ξ(λ) ≤ ∑_{(k,x)∈Π} M_{k} = ∑_{k≥1} N_{k}M_{k},

where N_{k} = |Π_{k}| is a Poisson random variable with mean λ. We split its tail as follows:

ℙ (Ξ(λ) ≥ x) ≤ ℙ (∑_{k≥1} N_{k}M_{k} ≥ x)
≤ p_{1} + p_{2},

in which

p_{1} = ℙ ( ∑_{1≤k≤n} N_{k}M_{k} ≥ x/2) ,

p_{2} = ℙ (∑_{k>n} N_{k}M_{k} ≥ x/2) .

We have, by the standard Chernoff bound for the Poisson distribution,

p_{1} ≤ ℙ ( ∑_{1≤k≤n} N_{k} ≥ x/2) ≤ exp (\frac{x}{2} (1 − ln(x/2nλ)) − nλ) ,

the last inequality holding only for n ≤ \frac{x}{2λ}. Also

p_{2} ≤ ℙ ( ∑_{0≤k≤n} N_{k}ρ^{k/2} ≥ x/2) + ℙ (∃k > n, M_{k} > ρ^{k/2})

≤ (1 + \frac{2λ}{x}) \frac{ρ^{(n+1)/2}}{1 − \sqrt{ρ}} ,

using a Markov first moment inequality to bound both terms. For any α in (0, 1), the choice n ≃ \frac{αx}{2λ} leads to an exponential decrease of the tail. □

Convergence of X_{n,p} to X(λ). We assume that the input list for Quicksort contains the integers {1, 2, …, n} in random order. We model our erratic Quicksort as follows using the variables U_{k,j} and Π in Section 2, but with the intensity λ of Π replaced by λ(n, p) = −n ln(1 − p):

In the first step, we use the pivot p_{1,1} = ⌈nU_{0,1}⌉ and let for each i (except the pivot) there be an error in the comparison of i and the pivot if Π_{1} ∩ (\frac{i−1}{n}, \frac{i}{n}] ≠ ∅. (Recall that Π_{k} = {x : (k, x) ∈ Π}.) Note that our choice of λ(n, p) yields the right error probability p.

Let p′_{1,1} be the position of the pivot after the first step. (This position was earlier denoted Z_{n,p}; it may differ from p_{1,1} because of errors.) The items of the left sublist will thus be placed on positions 1, …, p′_{1,1} − 1 and those in the right sublist on positions p′_{1,1} + 1, …, n. Let p′_{1,0} = 0 and p′_{1,2} = 1 + n.

When the k-th step begins, we have a set of 2^{k−1} sublists (ℓ_{k−1,j})_{j=1,...,2^{k−1}}, the elements of ℓ_{k−1,j} being on positions p′_{k−1,j−1} + 1, …, p′_{k−1,j} − 1, j = 1, …, 2^{k−1} (with the convention that the sublist is empty when p′_{k−1,j} − p′_{k−1,j−1} ≤ 1). In each nonempty such sublist we choose as pivot the item with rank ⌈U_{k−1,j}(p′_{k−1,j} − p′_{k−1,j−1} − 1)⌉, in this sublist, so that its position in the final output will be exactly

(30)  p_{k,2j−1} = p′_{k−1,j−1} + ⌈U_{k−1,j}(p′_{k−1,j} − p′_{k−1,j−1} − 1)⌉,

in case no errors occurs while proceeding the sublist. We assume an error is made when comparing the element at position i with the pivot p_{k,2j−1} if Π_{k} ∩ (\frac{i−1}{n}, \frac{i}{n}] ≠ ∅. Let p′_{k,2j} = p′_{k−1,j}. Let p′_{k,2j−1} be the position of the pivot p_{k,2j−1} after the comparisons (as in the first step, p′_{k,2j−1} may differ from p_{k,2j−1} because of errors); let p′_{k,2j−1} = p′_{k−1,j} if the sublist was empty. Set

y_{k,j} = p_{k,j}/n and y′_{k,j} = p′_{k,j}/n.

We expect y_{k,j} and y′_{k,j} to converge to Y_{k,j} as n → +∞.

This procedure (stopped when there are no more nonempty sublists) is an exact simulation of the erratic Quicksort, so we may assume that I(n, p) is the number of inversions created by it. As in Section 3, let I^{(k)}(n, p) be the number of inversions created at step k, so

I(n, p) = ∑_{k=1}^{∞} I^{(k)}(n, p).

We will prove that, using the notation of (7),

(31)  δ_{k} = ∥\frac{1}{n^{2}p}I^{(k)}(n, p) − \frac{1}{λ(n, p)} ∑_{j=1}^{2^{k}} ∑_{x∈Π_{k,j}} |x − x_{k,j}|∥_{1} → 0

for each k. Since also, by Lemmas 3.4 and 6.1,

δ_{k} ≤ \frac{1}{n^{2}p}𝔼 [I^{(k)}(n, p)] + \frac{1}{λ(n, p)}𝔼 [∑_{j=1}^{2^{k}} ∑_{x∈Π_{k,j}} |x − x_{k,j}|]

= \frac{1}{n^{2}p}𝔼 [I^{(k)}(n, p)] + 𝔼 [\frac{1}{2} ∑_{j=1}^{2^{k}} w_{k,j}^{2}] ≤ (\frac{2}{3})^{k} ,

it follows by dominated convergence that, using (7),

∥X_{n,p} − X(λ(n, p))∥_{1} ≤ ∑_{k=1}^{∞} δ_{k} → 0.

Moreover, λ(n, p) → λ, and it follows easily from (8) that ∥X(λ(n, p)) − X(λ)∥_{1} → 0. Hence we have 𝔼 |X_{n,p} − X(λ)| → 0, which proves the convergence.

It remains to verify (31). Set

X^{(k)} = ∑_{j=1}^{2^{k}} ∑_{x∈Π_{k,j}} |x − x_{k,j}|.

Relation (31) is equivalent to

(32)  𝔼 |\frac{1}{n}I^{(k)}(n, p) − X^{(k)}| → 0.

For simplicity, we write in the sequel λ instead of λ(n, p). We begin with a lemma.

Lemma 6.6. For each k and j,

max \{∥Y_{k,j} − y′_{k,j}∥_{1} , ∥Y_{k,j} − y_{k,j}∥_{1}\} ≤ \frac{k(1 + λ)}{n}.

Proof. Recall that p′_{k,j} = ny′_{k,j}, so (30) translates to

p_{k,2j−1} = ny′_{k−1,j−1} + ⌈U_{k−1,j}(ny′_{k−1,j} − ny′_{k−1,j−1} − 1)⌉,

We use induction on k. Comparing the definitions of Y_{k,j} and y′_{k,j}, we see that it suffices to consider an odd j = 2l − 1, and in that case there are three sources of a difference:

(i) The differences between y′_{k−1,l−1} and Y_{k−1,l−1} and between y′_{k−1,l} and Y_{k−1,l}. By the induction hypothesis, this contributes at most (k − 1)(1 + λ)/n.

(ii) The −1 inside (and the rounding by) the ceiling function. This contributes

at most 1/n. (iii) The shift of the pivot, from p_{k,2j−1} to p′_{k,2j−1}, caused by the erroneous comparisons. The shift is bounded by the total number of errors at step k, so its mean is less than λ, and the contribution is less than λ/n.

□

We return to (32). For k = 1, I^{(1)}(n, p) is just t(n, p) studied in Section 3, and (10) yields

I^{(1)}(n, p) = s_{ℓ}s_{r} + s_{ℓ} + s_{r} + Wℓ⃗ + Wr⃗.

Let E_{1} be the set of items i such that an error was made in the comparison with p_{1,1}. Relation (11) entails that

∑_{i∈E_{1}} |i − p_{1,1}| = Wℓ⃗ + Wr⃗ + \frac{1}{2}s_{ℓ}(s_{ℓ} + 1) + \frac{1}{2}s_{r}(s_{r} + 1).

We shall denote this last sum Ĩ^{(1)}(n, p). Thus, we have

|I^{(1)}(n, p) − Ĩ^{(1)}(n, p)| = |s_{ℓ}s_{r} + s_{ℓ} + s_{r} − \frac{1}{2}s_{ℓ}(s_{ℓ} + 1) − \frac{1}{2}s_{r}(s_{r} + 1)| ≤ s_{ℓ}^{2} + s_{r}^{2}.

Furthermore

(33)  𝔼 [s_{ℓ}^{2} | ⌈nU_{1,1} = k⌉] = (k − 1)p(1 − p) + ((k − 1)p)^{2} ≤ np + n^{2}p^{2}.

Hence,

∥I^{(1)}(n, p) − Ĩ^{(1)}(n, p)∥_{1} = O (1) .

Moreover, \frac{1}{n} Ĩ^{(1)}(n, p) = ∑_{i∈E_{1}} |\frac{i}{n} −y_{1,1}| differs from X^{(1)} = ∑_{j=1}^{2} ∑_{x∈Π_{1,j}} |x−x_{1,j}| in (32) in four ways only (recall that x_{1,1} = x_{1,2} = Y_{1,1}):

(i) i/n differs from x by at most 1/n. Since the expected number of terms is not larger than λ, this gives a contribution O (1/n).

(ii) |y_{1,1} − x_{1,j}| = |y_{1,1} − Y_{1,1}|, which by Lemma 6.6 has expectation O (1/n).

Thus this too gives a contribution O (1/n). (iii) If there are two or more points in Π_{1} ∩ (\frac{i−1}{n}, \frac{i}{n}] for some i, X^{(1)} contains more terms than \frac{1}{n} Ĩ^{(1)}(n, p). It is easily seen that the expected number of such extra points in each interval (\frac{i−1}{n}, \frac{i}{n}] is less than (λ/n)^{2}, and each point contributes for at most 1 to X^{(1)}.

(iv) Each point in Π_{1}∩(\frac{p_{1,1}−1}{n}, \frac{p_{1,1}}{n}] contributes for an extra term in X^{(1)} again. The expected number of such extra points is λ/n and each of these terms contributes for at most 1 to X^{(1)}.

This verifies (32) for k = 1.

For k ≥ 2 we argue similarly. We can approximate I^{(k)}(n, p) by the sum of the distances between the errors and the respective pivots,

Ĩ^{(k)}(n, p) = ∑_{j≤2^{k−1}} ∑_{i∈E_{k−1,j}} |i − p_{k,2j−1}|,

as follows: Let E_{k,j} be the set of items i ∈ ℓ_{k,j} subject to error when compared with p_{k+1,2j−1}, and let G_{k} be the σ-algebra generated by (U_{ℓ,j})_{ℓ≤k,j≤2^{ℓ}} and Π_{1} ∪ Π_{2} ∪ ⋯ ∪ Π_{k−1}. As for k = 1, using relation (11), we obtain the following bound:

𝔼 [|I^{(k)}(n, p) − Ĩ^{(k)}(n, p)| | G_{k}] ≤ ∑_{j≤2^{k−1}} (p^{2} (#ℓ_{k−1,j})^{2} + p#ℓ_{k−1,j})
≤ 2^{k−1}(n^{2}p^{2} + np) = O (1) ,

and as a consequence,

∥I^{(k)}(n, p) − Ĩ^{(k)}(n, p)∥_{1} = O (1) .

Now,

\frac{1}{n}Ĩ^{(k)}(n, p) = ∑_{j≤2^{k−1}} ∑_{i∈E_{k−1,j}} |\frac{i}{n} − y_{k,2j−1}|

differs from X^{(k)} = ∑_{j=1}^{2^{k}} ∑_{x∈Π_{k,j}} |x − x_{k,j}| in (32) in the same four ways as for k = 1, plus an extra fifth way:

(i) See the case k = 1.

(ii) |y_{k,2j−1}−x_{k,2j−1}| = |y_{k,2j−1}−x_{k,2j}| = |y_{k,2j−1}−Y_{k,2j−1}|, which by Lemma 6.6 has expectation O (1/n). Thus this too gives a contribution O (1/n).

(iii) Two or more points in Π_{k} ∩ (\frac{i−1}{n}, \frac{i}{n}] for some i, see the case k = 1.

(iv) Each point in Π_{k} ∩ (−1/n + y_{k,2j−1}, y_{k,2j−1}] contributes for an extra term in X^{(k)}. The expected number of such extra points is λ2^{k−1}/n and each of these terms contributes for at most 1 to X^{(k)}.

(v) There is a new source of error in this approximation, because some points x in Π_{k} and the corresponding positions i = ⌈nx⌉ belong to subintervals that do not correspond to each other, because the endpoints y′_{k−1,j} differ somewhat from Y_{k−1,j}. By Lemma 6.6, the expected number of such cases is O (1/n), so again we get a contribution of order O (1/n) only.

This verifies (32) and thus the convergence of X_{n,p} to X(λ).

The functional equation for X(λ). We first check that X(λ) satisfies the functional equation and our side conditions.

Proposition 6.7. (X(λ))_{λ>0} is a solution of (5). Moreover, 𝔼 [X(λ)^{n}] < ∞ and λ^{n}𝔼 [X(λ)^{n}] → 0 as λ → 0, for n ≥ 1.

Proof. All moments are finite by Theorem 6.5. Moreover, 𝔼 [(λX(λ))^{n}] → 0 as λ → 0 by (8) and dominated convergence.

For a < b, let Π(a, b) is a Poisson point process of intensity λ on ℕ^{∗} × [a, b], and let {U_{k,j} : k ≥ 0, 1 ≤ i ≤ 2^{k}} be independent uniform random variables as in Section 2, and further independent of Π(a, b). Define {Y_{k,j} : k ≥ 0, 1 ≤ i ≤ 2^{k}} and J_{k}(x) as in Section 2, with the slight modification

Y_{0,0} = a  and  Y_{0,1} = b

and set

X(λ, a, b) = \frac{1}{λ} ∑_{(k,x)∈Π(a,b)} |x − Y_{k,J_{k}(x)}|.

Note that X(λ, 0, 1) = X(λ). Shifting and rescaling Π(a, b), we obtain

X(λ, a, b) =^{law} X(λ, 0, b − a) =^{law} (b − a)^{2}X(λ(b − a)).

Let us split X(λ): we have

X(λ) = X_{0}(λ) + X_{1}(λ) + X_{2}(λ)
λX_{0}(λ) = ∑_{(x,1)∈Π(a,b)} |x − Y_{1,1}|
λX_{1}(λ) = ∑_{{(k,x)∈Π(a,b) \atop k≥2,x≤Y_{1,1}}} |x − Y_{k,J_{k}(x)}|,

λX_{2}(λ) = ∑_{{(k,x)∈Π(a,b) \atop k≥2,x≥Y_{1,1}}} |x − Y_{k,J_{k}(x)}|.

We see, using general properties of Poisson point processes and the recursive construction of {Y_{k,j} : k ≥ 0, 1 ≤ i ≤ 2^{k}}, that

(X_{0}(λ), X_{1}(λ), X_{2}(λ)) =^{law} (Θ(λ, Y_{1,1}), X(λ, 0, Y_{1,1}), X̃(λ, Y_{1,1}, 1))

=^{law} (Θ(λ, Y_{1,1}), Y_{1,1}^{2}X(λY_{1,1}), (1 − Y_{1,1})^{2}X̃(λ(1 − Y_{1,1}))),

in the sense that, conditionally given that Y_{1,1} = u, X_{0}(λ), X_{1}(λ) and X_{2}(λ) are independent and distributed as Θ(λ, u), u^{2}X(λu), (1−u)^{2}X(λ(1−u)), respectively. Also Y_{1,1} = U_{0,1} is uniformly distributed on [0, 1]. □

Uniqueness of solutions of (5). The idea of the proof is that (5) uniquely determines the moments of its solutions. However, using (5), computations of moments by induction are hardly tractable because all three terms on the right of (5) depend on U. To circumvent this problem, we consider a new functional equation

(34)  Y (λ) =^{law} ξ(λ) + UY (λU) + (1 − U)Ỹ(λ(1 − U)),

in which • ξ(λ) is as in Section 2; equivalently, ξ(λ) = ∑_{x∈Π_{1}} x;

• ξ(λ) and (U, Y (λU), Ỹ(λ(1 − U))) are independent;

• conditionally, given U = u, Y (λU) and Ỹ(λ(1 − U)) are independent and

distributed as Y (λu) and Y (λ(1 − u)), respectively. We say that a family of nonnegative random variables (Y (λ))_{λ>0} (with laws de-

pending measurably on λ) is an admissible solution of (34) if it satisfies furthermore, for any n ≥ 1,

(i) 𝔼 [Y (λ)^{n}] < ∞;

(ii) λ^{n−1}𝔼 [Y (λ)^{n}] → 0 as λ → 0.

Similarly, we say that a solution (Z(λ))_{λ>0} of (5) is admissible if it satifies the conditions 𝔼 [Z(λ)^{n}] < ∞ and λ^{2n−1}𝔼 [Z(λ)^{n}] → 0 as λ → 0 in Theorem 2.3.

To conclude the proof of the theorem, we prove the following two propositions.

Proposition 6.8. If (Z(λ))_{λ>0} is an admissible solution of (5), then the family (ξ(λ) + λZ(λ))_{λ>0}, in which ξ(λ) and Z(λ) are assumed independent, is an admissible solution of (34).

Proposition 6.9. All admissible solutions of (34) have the same moments f_{n}(λ), n ≥ 1.

Let (Z(λ))_{λ>0} be an admissible solution of (5). As the moments of ξ(λ)+λZ(λ) uniquely determine the moments of Z(λ), it follows from Propositions 6.7, 6.8 and 6.9 that X(λ) and Z(λ) have the same moments. Since X(λ) has an exponentially decreasing tail by Lemma 6.5 , its moments satisfy the Carleman condition [2, Chap. 7], and determine uniquely its distribution. Hence Z(λ) =^{law} X(λ), concluding the proof of uniqueness for admissible solutions of (5).

Before proving Propositions 6.8 and 6.9, we need a lemma.

Lemma 6.10. The n-th moment g_{n}(λ) = 𝔼 [ξ(λ)^{n}] is a polynomial of degree n with g_{n}(0) = 0.

Proof. Owing to Campbell’s Theorem [5, p.28], we have

𝔼 [e^{sξ(λ)}] = exp (λ (𝔼 [e^{sU}] − 1)) = exp (λ (\frac{s}{2!} + \frac{s^{2}}{3!} + …)) .

Expanding the last expression gives the lemma. □

Proof of Proposition 6.8. Lemma 6.10 shows that 𝔼 [ξ(λ)^{n}] is finite for every λ and converges to 0 as λ → 0. Hence, by Minkowski’s inequality for the norm ∥·∥_{n} = 𝔼 [| · |^{n}]^{1/n}, the conditions on the moments of Y (λ) = ξ(λ) + λZ(λ) follow from (and are equivalent to) the corresponding conditions on the moments of Z(λ).

To show (34), it is enough to show

λZ(λ) =^{law} UY (λU) + (1 − U)Ỹ(λ(1 − U))

= Uξ(λU) + λU^{2}Z(λU) + (1 − U)ξ̃(λ(1 − U)) + λ(1 − U)^{2}Z̃(λ(1 − U)),

where, as usual, conditioned on U = u, the terms on the right hand side are independent with the right distributions. This follows immediately from (5), since

λΘ(λ, u) =^{law} uξ(λu) + (1 − u)ξ̃(λ(1 − u)).

□

Proof of Proposition 6.9. Consider the sequence of integral equations

(35)  P_{0}(λ) = 1,  P_{n}(λ) = 2 ∫_{0}^{1} u^{n}P_{n}(λu)du + ψ_{n}(λ), n ≥ 1,

in which

(36)  ψ_{n}(λ) = ∑_{{r+k+ℓ=n \atop k<n,ℓ<n}} \binom{n}{r, k, ℓ}g_{r}(λ) ∫_{0}^{1} u^{k}(1 − u)^{ℓ}P_{k}(λu)P_{ℓ}(λ(1 − u)) du.

Proposition 6.9 is a consequence of the next lemma. □

Lemma 6.11. The induction formula (35) and the initial condition P_{1}(0) = 0 defines a unique sequence of polynomials, (P_{n}(λ))_{n≥0}. Furthermore, P_{n} has degree n, and vanishes at 0. If (Y (λ))_{λ} is an admissible solution of (34), then, for n ≥ 1, its n-th moment 𝔼 [Y (λ)^{n}] is equal to P_{n}(λ).

Proof. Consider n ≥ 1 and assume that the properties in the lemma hold for 1 ≤ m ≤ n − 1. Then, for k and ℓ smaller than n, and r + k + ℓ = n, the expression

g_{r}(λ) ∫_{0}^{1} u^{k}(1 − u)^{ℓ}P_{k}(λu)P_{ℓ}(λ(1 − u)) du

is a polynomial with degree n and, due to Lemma 6.10, vanishes at 0. Thus, in this case, ψ_{n}(λ) is a polynomial with degree n, vanishing at 0. It is now easy to check that a polynomial P_{n}(λ) satisfies (35) if and only if, for (n, k) ≠ (1, 0),

(37)  [λ^{k}] P_{n} = \frac{n + k + 1}{n + k − 1} [λ^{k}] ψ_{n}.

Also, by the induction assumptions,

𝔼 [Y (λ)^{n}] = 𝔼 [(ξ(λ) + UY (Uλ) + (1 − U)Ỹ((1 − U)λ))^{n}]

= ∑_{r+k+ℓ=n} \binom{n}{r, k, ℓ}g_{r}(λ)𝔼 [U^{k}(1 − U)^{ℓ}Y (Uλ)^{k}Ỹ((1 − U)λ)^{ℓ}]

= 2𝔼 [U^{n}Y (λU)^{n}] + ψ_{n}(λ).

Note that ψ_{n}(λ) ≥ 0 for λ ≥ 0. Since Y is admissible, λ → f_{n}(λ) = 𝔼 [Y (λ)^{n}] is nonnegative and measurable. Thus, for λ > 0, we can rewrite the previous equation:

f_{n}(λ) = 2 ∫_{0}^{1} u^{n}f_{n}(λu)du + ψ_{n}(λ)
= 2λ^{−n−1} ∫_{0}^{λ} v^{n}f_{n}(v)dv + ψ_{n}(λ).

Since f_{n}(λ) is assumed to be finite and ψ_{n}(λ) ≥ 0, the integral on the right hand side is convergent, and thus it is a continuous function of λ. As a consequence f_{n} belongs to C^{∞}(0, +∞), and is solution, on (0, +∞), of the following differential equation:

λf′_{n}(λ) + (n − 1)f_{n}(λ) = (n + 1)ψ_{n}(λ) + λψ′_{n}(λ).

As Y is admissible, λ^{n−1}f_{n}(λ) → 0 as λ → 0, but the general solution of the differential equation is P_{n}(λ) + C λ^{−n+1}. Thus f_{n} = P_{n} on (0, +∞). □

Computation of the first moments. The moments of Y (λ), and thus of X(λ), can be computed up to arbitrary order with the help of (35). For the first two moments, the calculations run as follows. Expanding

exp (λ (\frac{s}{2!} + \frac{s^{2}}{3!} + …)) ,

in the proof of Lemma 6.10 we obtain

Lemma 6.12.

g_{1}(λ) = 𝔼 [ξ(λ)] = \frac{1}{2}λ  and  g_{2}(λ) = 𝔼 [ξ(λ)^{2}] = \frac{1}{4}λ^{2} + \frac{1}{3}λ.

Proposition 6.13.

λ𝔼 [X(λ)] = 𝔼 [Ξ(λ)] = λ  and  λ^{2}Var (X(λ)) = Var (Ξ(λ)) = \frac{1}{3}λ + \frac{1}{12}λ^{2}.

Proof. Taking n = 1 in (36) and (37), we find, using Lemma 6.12,

ψ_{1}(λ) = g_{1}(λ) = \frac{1}{2}λ,
P_{1}(λ) = \frac{3}{1} · \frac{1}{2}λ = \frac{3}{2}λ.

Taking n = 2, we similarly find

ψ_{2}(λ) = g_{2}(λ) + 2 · 2g_{1}(λ) ∫_{0}^{1} uP_{1}(u) du + 2 ∫_{0}^{1} u(1 − u)P_{1}(λu)P_{1}(λ(1 − u)) du
= \frac{1}{3}λ + \frac{7}{5}λ^{2},
P_{2}(λ) = \frac{4}{2} · \frac{1}{3}λ + \frac{5}{3} · \frac{7}{5}λ^{2} = \frac{2}{3}λ + \frac{7}{3}λ^{2}.

Since Y (λ) = ξ(λ) + λX(λ), with independent summands,

P_{1}(λ) = 𝔼 [Y (λ)] = 𝔼 [ξ(λ)] + λ𝔼 [X(λ)] ,

which by Lemma 6.12 yields λ𝔼 [X(λ)] = λ. Similarly,

λ^{2}𝔼 [X(λ)^{2}] = P_{2}(λ) − 𝔼 [ξ(λ)^{2}] − 2𝔼 [ξ(λ)] 𝔼 [λX(λ)] = \frac{1}{3}λ + \frac{13}{12}λ^{2},

which yields the variance formula. □

The formulas for mean and variance of X(λ) can also be obtained directly from (8) and Lemma 6.12; we leave this as an exercise.

7. Concluding remarks

We have presented a probabilistic analysis of Quicksort when some comparisons can err. Analysing other sorting algorithms such as merge sort, insertion sort or selection is even more intricate. They do not fit into the model presented in this paper and further more involved probabilistic models/arguments are required. We conjecture that the same normalization holds for the number of inversions in the output of merge sort for n = 2^{m} → +∞, p = λ/n, and that the limit law Ŷ (λ) satisfies

𝔼 [Ŷ (λ)] = ∑_{k≥0} \frac{2^{k}}{(2^{k} + 2)(2^{k} + 3)} = 0.454674373 ⋯ < 𝔼 [X(λ)] .

References

Wiley & Sons, 1971.

[1] J.D. Biggins. Uniform convergence of martingales in the branching random walk, Ann.

Probab., 20(1):137–151, 1992.

[2] W. Feller. An introduction to probability theory and its applications, Vol. II, 2nd ed., John [3] F. Ergün, S. Kannan, S.R. Kummar, R. Rubinfeld & M. Vishanathan. Spot-Checkers, J.

Comput. Sys. Sci., 60(3):717–751, 2000.

[4] R. Grüber & U. Rösler. Asymptotic distribution theory for Hoare’s selection algorithm, Adv.

Appl. Prob., 28:252–269, 1996.

[5] J.F.C. Kingman. Poisson processes, Oxford University Press, New York, 1993.

[6] D.E. Knuth. The Art of Computer Programming. Vol. 3 : Sorting and Searching, 2nd ed.,

John Wiley & Sons, 1986.

[7] H.M. Mahmoud. Evolution of random search trees, John Wiley & Sons, 1992.

[8] B. Pittel. On growing random binary trees, J.Math.Anal.Appl., 103:461–480, 1984.

[9] S.T. Rachev. Probability Metrics and the Stability of Stochastic Models, Wiley, Chichester, U.K., 1991.

[10] U. Rösler. A limit theorem for ”Quicksort”, Theor. Inf. Appl., 25:85–100, 1991.

[11] U. Rösler & L. Rüschendorf. The contraction method for recursive algorithms, Algorithmica, 29:3-33, 2001.

INRIA-Lorraine and LORIA, Université Henri Poincaré-Nancy I, BP 239, 54506, Vandœuvre-lès-Nancy, France

E-mail address: Laurent.Alonso@loria.fr

Institut Élie Cartan, Université Henri Poincaré-Nancy I, BP 239, 54506, Vandœuvrelès-Nancy, France

E-mail address: Philippe.Chassaing@antares.iecn.u-nancy.fr
URL: http://www.iecn.u-nancy.fr/~chassain/

Institut Élie Cartan, Université Henri Poincaré-Nancy I, BP 239, 54506, Vandœuvrelès-Nancy, France

E-mail address: Florent.Gillet@antares.iecn.u-nancy.fr

Department of Mathematics, Uppsala University, PO Box 480, S-751 06 Uppsala, Sweden

E-mail address: svante.janson@math.uu.se
URL: http://www.math.uu.se/~svante/

Department of Computer Science, Illinois Institute of Technology, Stuart Building, 10 West 31st Street, Suite 236, Chicago, IL 60616-3729 U.S.A.

E-mail address: reingold@iit.edu

Institut Élie Cartan and LORIA, Université Henri Poincaré-Nancy I, BP 239, 54506, Vandœuvre-lès-Nancy, France

E-mail address: schott@loria.fr