Coherent random permutations with record statistics.

A two-parameter family of random permutations of [n] is introduced, with distribution conditionally uniform given the counts of upper and lower records. The family interpolates between two versions of Ewens' distribution. A distinguished role of the family is determined by the fact that every sequence of coherent permutations ([[pi].sub.n], n = 1, 2 ...) with the indicated kind of sufficiency is obtainable by randomisation of the parameters. Generating algorithms and asymptotic properties of the permutations follow from the representation via initial ranks.

Keywords: random permutations, records, sufficiency, Ewens' distribution

1 Introduction

Random permutations with non-uniform distribution appear in a variety of contexts such as combinatorial structures [1], shuffling and sorting algorithms [3, 18], dynamical systems [17] and statistics [11], just to mention a few. Generalisations of the uniform distribution can be designed by assuming some sort of sufficiency, that is requiring the distribution to be uniform conditionally given the value of some statistic of permutation.

One important instance of this kind is Ewens' distribution on the symmetric group [G.sub.n], The distribution assigns probability [[theta].sup.c-1]/[([theta] + 1).sub.n - 1], to every permutation [[pi].sub.n] [member of] [G.sub.n] with c cycles, where [theta] [greater than or equal to] 0 is a parameter, see [1, 21]. Ewens' distributions are coherent as n varies, hence can be viewed as a probability on the space [G.sup.[infinity]], a projective limit of [G.sub.n]'s. Moreover, every distribution for ([[pi].sub.n], n = 1, 2 ...) [member of] [G.sup.[infinity]] such that each [[pi].sub.n] is uniform given the number of cycles, can be obtained as a mixture over Ewens' family, that is by randomisation of [theta], see Gnedin and Pitman [8].

By the virtue of a fundamental bijection [G.sub.n] [right arrow] [G.sub.n] the number of cycles is translated into the number of upper records, hence Ewens' distribution may be also viewed as a distribution which assigns probability [[theta].sup.u-1]/[([theta] + 1).sub.n-1] to each permutation [[pi].sub.n] [member of] [G.sub.n] with a upper records, a viewpoint due to Kerov [14]. Gnedin and Olshanski [7] explored a similar setting with the number of descents as sufficient statistic; in this case the distinguished role is played by the dicrete-parameter family of a-shuffles (introduced in [3] and appearing in bucket sorting [18]) and their reversals.

This paper was largely motivated by the suggestion in [9, 10] to connect random record models with instances of Ewens' sampling formula. In this direction, we extend Ewens' family by introducing two-parameter distributions [[P.sup.([theta], [xi])] on [G.sup.[infinity]] under which every [[pi].sub.n] [member of] [G.sub.n] is uniform conditionally given (l, u), for l the number of lower and u the number of upper records of permutation. We show that every probability on [G.sup.[infinity]] having this kind of sufficiency is obtainable by randomising the parameters [theta] and [xi]. We also show that permutations under [P.sup.([theta], [xi]] can be generated by ranking a sequence of real-valued random variables ([X.sub.n]), whose record sequences follow a two-sided analogue of the GEM distribution for 'stick-breaking' partition of the unit interval.

2 Counting the records

Permutations [[pi].sub.n], [member of] [G.sub.n] of [n] := {1, ..., n} will be written in the one-row notation [[pi].sub.n] = ([[pi].sub.n1], ..., [[pi].sub.nn]). We call element [[pi].sub.nj] a lower record of [[pi].sub.n] if [[pi].sub.nj] = min([[pi].sub.n1], ..., [[pi].sub.nj]), and we call [[pi].sub.nj] an upper record if [[pi].sub.nj] = max([[pi].sub.n1], ..., [[pi].sub.nj]). When [[pi].sub.nj] is a record we say that [[pi].sub.nj] is a record value and that j is a record time (or a record position). The first entry [[pi].sub.n1] will be called center. We regard the center as improper lower and upper record, all other records being proper. We denote 

rec([[pi].sub.n]) = ([r.sub.-l], ..., [r.sub.-1], [r.sub.0], [r.sub.1], ..., [r.sub.u])

the two-sided increasing sequence of record values, with distinguished center [r.sub.0] = [[pi].sub.n1] proper lower records [r.sub.-l], ..., [r.sub.-1] and proper upper records [r.sub.1], ..., [r.sub.u]. In this notation l, u count the proper records; for instance, rec(3, 2, 7, 6, 1, 4, 8, 5) = (1, 2, 3, 7, 8), where the center is boldfaced and l = u = 2. Clearly, [r.sub.-l] = 1, [r.sub.u] = n, and the total number of records #rec([[pi].sub.n]) = l + u + 1 satisfies min(2, n) [less than or equal to] l + u + 1 [less than or equal] n. The record times of proper lower and upper records will be labelled [t.sub.1], ..., [t.sub.u] and [t.sub.-1], ..., [t.sub.-l], respectively, and we denote [t.sub.0] = 1 the record time associated with the improper record.

Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] be the number of permutations [[pi].sub.n] [member of] [G.sub.n] with l + 1 lower and u + 1 upper records. This array of combinatorial numbers is symmetric in l and u, and satisfies the recursion 

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (1)

Summing over one of the record counts, say u, yields a signless Stirling number of the first kind

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

equal to the number of permutations with l + 1 lower records. A more delicate connection to the Stirling numbers appears via the identity

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (2)

found in [[2], p. 179], where it was derived by manipulation with generating functions.

For our purposes it is important to introduce yet another encoding of permutation into the sequence of initial ranks

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

The correspondence [[pi].sub.n] [right arrow] ([t.sub.1], ..., [t.sub.n]) is a well-known bijection between [G.sub.n] and [1] x [2] x ... x [n]. Note that [[pi].sub.nj] is a lower record if [l.sub.j] = 1, and an upper record if [l.sub.j] = j.

In terms of the initial ranks abijective proof of (2) is easily acquired. To this end, consider the mapping which sends [[pi].sub.n] [member of] [G.sub.n] to [[pi]'.sub.n-1] [member of] [G.sub.n-1] so that the initial ranks are transformed as ([l.sub.i], ..., [l.sub.n]) [right arrow] ([l'.sub.i], ..., [l'.sub.n-1]) where [l'.sub.j-1] = [l.sub.j] 1([l.sub.j] < j) for 2 [less than or equal to] j [less than or equal to] n (and 1(...) will denote an indicator). Each proper record of [[pi].sub.n] is mapped bijectively to a lower record of [[pi]'.sub.n - 1], and the record counts satisfy l([[pi].sub.n]) + u([[pi].sub.n]) = l([[pi]'.sub.n] + 1. It is easily seen that [2.sup.r] permutations [[pi].sub.n] are mapped to the same [[pi]'.sub.n - 1], each time when l([[pi]'.sub.n - 1]) + 1 = r, and of these [[pi].sub.n] there are ([[sup.r].sub.l]) permutations with l proper lower records. Because [[pi]'.sub.n - 1] with r lower records can be chosen in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] ways, the identity (2) follows.

When a probability distribution [P.sub.n] is specified on [G.sub.n], we consider [[pi].sub.n] as a random variable. In particular, [[P.sup.(1, 1)].sub.n] ([[pi].sub.n]) [equivalent to] 1/n! is the uniform distribution (indices will be explained in the next section). The characteristic feature of the uniform distribution is that the initial ranks are independent, with each [l.sub.j] being uniformly distributed on [j]. Giving a probabilistic interpretation to (2) we have:

Lemma 1 Under the uniform distribution [[P.sup.(1, 1)].sub.n] for [[pi].sub.n], conditionally given the record counts (l, u) and given the positions occupied by l + u proper records, all [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] allocations of l lower records within these l + u positions are equally likely.

Recall that ranking associates with any sequence of distinct reals [x.sub.1], ..., [x.sub.n] a sequence of ranks [[pi].sub.nj] = #{i [less than or equal to] n : [x.sub.i] [less than or equal] [x.sub.j]}, also called the ranking permutation. A uniform permutation appears when [x.sub.1], ..., [x.sub.n] are sampled independently from the uniform distribution on [0, 1] (or from any other nonatomic distribution on reals).

3 The two-parameter family of random permutations

We introduce next a two-parameter deformation of the uniform distribution, for which (l, u) is a sufficient statistic, meaning that given the record counts the distribution of [[pi].sub.n] is uniform.

Proposition 2 For arbitrary positive [theta] and [xi] the formula

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (3)

defines a distribution on [G.sub.n], which assigns the same probability to every permutation with l + 1 lower and u + 1 upper records.

Proving this amounts to the fact that the probabilities in (3) add to unity, which is equivalent to the formula for the bivariate generating function

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (4)

known since at least [4]. Note that for [xi] = 1 this specialises as the well-known formula

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

for the generating function of Stirling numbers.

To generate [[pi].sub.n] under [[P.sup.([theta], [xi])].sub.n] one can exploit the representation via initial ranks, with [l.sub.1] = 1 and [l.sub.2], ..., [l.sub.n] to sampled independently from distributions

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

(w.p.=with probability). Multiplying these out it is seen that (3) is indeed the probability of any sequence ([i.sub.2], ..., [i.sub.n]) where [l.sub.j] = 1 occurs l times and [l.sub.j] = j occurs a times.

For the uniform distribution, each [l.sub.j] should be sampled from the uniform distribution on [j], which is a well-known method to generate uniform permutation. Thus, [[P.sup.([theta], [xi])].sub.n] deforms [[P.sup.(1, 1)].sub.n] by tilting the probabilities of extreme values of the initial ranks.

4 Construction for integer parameters

For integer [theta], [xi] the distribution [[P.sup.([theta], [xi])].sub.n] can be obtained as a projection of the uniform distribution [[P.sup.(1, 1)].sub.n + d] On [G.sub.n + d], where d = [theta] + [xi] - 2. To ease notation, for the rest of this section the elements of permutation are written with one index.

Fix ([w.sub.1], ..., [w.sub.n + d]) [member of] [G.sub. n + d]. A sequence ([[pi]'.sub.j], [member of] [n]) (which is a permutation of n integers {{[theta], ..., n + [theta] - 1}) is uniquely defined by the condition that {[[pi]'.sub.1], ..., [[pi]'.sub.j] [subset] {[w.sub.1], ..., [w.sub.d + j]} is the subset of integers whose ranks among {[w.sub.1], ..., [w.sub.d + j]} are neither among top [xi] - 1 ranks nor among bottom [theta] - 1 ranks. Here is the inductive definition. Let [s.sub.1], ..., [s.sub.n + d] be the initial ranks of [w.sub.1], ..., [w.sub.n + d]. At step 1 we define [[pi]'.sub.1] to be the element of rank [theta] among [w.sub.1], ..., [w.sub.d + 1], thus leaving [xi] - 1 elements ranked above and [theta] - 1 ranked below [[pi]'.sub.1]. At step j the element [w.sub.d + j] is added, if [theta] [less than or equal to] [s.sub.d + j] [less than or eqaul to] j + [theta] - 1 then [[pi]'.sub.j] = [w.sub.d + j], if 1 [less than or equal to] [s.sub.d + j] [less than or eqaul to] [theta] - 1 then [[pi]'.sub.j] is defined to be the element of rank [theta] among [w.sub.1], ..., [w.sub.d + j], and if j + [theta] [less than or equal to] [s.sub.d + j] [less than or eqaul to] j + d then [[pi]'.sub.j] is defined to be the element of rank j + [theta] -1 among [w.sub.1, ..., [w.sub.d + j] . standing the second arrow in ([w.sub.1], ..., [w.sub.n + d]) [right arrow] ([[pi]'.sub.1], ..., [[pi]'.sub.n]) [right arrow] ([[pi].sub.1], ..., [[pi].sub.n]) as the ranking operation, we have defined a projection [[f.sup. ([theta], [xi])].sub.n] from [G.sub.n + d] to [G.sub.n].

Proposition 3 For positive integers [theta], [xi] the mapping [ sends the uniform distribution on &n+d (where d = B + - 2) to [[P.sup.([theta], [xi])].sub.n].

Proof: In the above, the initial ranks for ([[pi].sub.1], ..., [[pi].sub.n]) and ([[pi]'.sub.1], ..., [[pi]'.sub.n]) are the same, and are given for j = 2, ...,n by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

For uniform permutation, [s.sub.j + d] is uniform on [j + d] and these are independent, hence the [r.sub.j]'s are independent with respective probabilities [theta]/ (n + d - 2), [xi]/ (n + d - 2) for extreme ranks and equal probabilities for other values of [l.sub.j]. [there does not exist]

For irrational [theta] or [xi] the distribution [[P.sup.([theta], [xi])].sub.n] cannot be obtained as a projection of a uniform distribution on some combinatorial object.

5 Coherent permutations

Our view of permutation is biased towards the interpretation as order, rather than mapping. Orders can be obviously restricted from larger sets to smaller. In this direction, we say that permutations [[pi].sub.n] and [[pi].sub.m], for m [less than or equal to] n, are coherent if they determine the same order on [m]. A sequence ([[pi].sub.n]) of coherent permutations [[pi].sub.n] [member of] [G.sub.n] defines a strict order [??] on the infinite set N: j [??] i iff [[pi].sub.nj] < [[pi].sub.ni] for all n [greater than or eqaul to] max(j, i).

Let [D.sub.nm] : [G.sub.n] [right arrow] [G.sub.m]. (n > m) be the projection which cuts the last n - m entries of [[pi].sub.n] and replaces the first m entries [[pi].sub.n1], ..., [[pi].sub.nm], by their ranking permutation. The projection [D.sub.nm] is the same as restricting orders from [n] to [m], hence the coherence means that [D.sub.nm], ([[pi].sub.n]) = [[pi].sub.m]. The space of all orders on N has the structure of the projective limit [G.sup.[infinity]] := [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Warning. The space [G.sup.[infinity]] should not be confused with the infinite symmetric group [G.sub.[infinity]] which is the inductive limit of finite symmetric groups with natural embedding. The elements of [G.sub.[infinity]] are bijections N [right arrow] N that displace only finitely many integers.

In terms of the initial ranks, Dnm : ([l.sub.1], ..., [l.sub.n]) [right arrow] ([l.sub.1], ..., [l.sub.m]) is just the projection on the first m coordinates. Every infinite sequence ([l.sub.n]) determines an order [??] on N, in which n is ranked [l.sub.n] th within the set [n]. Therefore [G.sup.[infinity]] can be identified with the infinite product space [1] x [2] x ... endowed with the discrete product topology (in which [G.sup.[infinity]] is a metrisable totally disconnected Borel space). When a probability measure is defined on [G.sup.[infinity]] we view ([[pi].sub.n]) [member of] [G.sup.[infinity]] as a random coherent sequence of permutations, or a random order on N. By the measure extension theorem, distributions [P.sub.n] on [G.sub.n], defined for every n, determine a unique distribution P on [G.sup.[infinity]] for a coherent sequence of permutations if and only if the [P.sub.n]'s are compatible with projections.

We denote [P.sup.([theta], [xi]) the measure on [G.sup.[infinity]] under which the initial ranks [l.sub.1], [l.sub.2], ... are independent, with distribution as in Section 3. The distributions [[P.sup.([theta], [xi])].sub.n] = 1, 2, ...) introduced in Proposition 3 are coherent projections of [P.sup.([theta], [xi])].

For an order [??] on N we shall say that an upper (or lower) record occurs at time n if [l.sub.n] = n (respectively, [l.sub.n] = 1). Reversing the order is an automorphism of [G.sup.[infinity]], which is written as either [[pi].sub.nj] [right arrow] n - [[pi].sub.nj] for j [member of] [n], n [member of] N, or, via the initial ranks, as [l.sub.n] [right arrow] n - [l.sub.n] for n [member of] N. Clearly, reversing the order swaps the types of records, hence maps [P.sup.([theta], [xi])] to [[P.sup.([xi]), [theta]].

Remark. Except [D.sub.n] := [D.sub.n, n - 1] there are two other useful n-to-1 projections [D'.sub.n], [D".sub.n] : [G.sub.n] [right arrow] [G.sub.n - 1], which appear in the context of descent statistics and cycle statistics, respectively [6, 16]. Projection [D'.sub.n] deletes n in the one-row notation of [[pi].sub.n], and [D".sub.n] deletes n in the cycle notation of [[pi].sub.n]. The projective limit [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] was introduced in the representation theory of [G.sub.[infinity]], as the space of virtual permutations [16], and [D'.sub.n] was used in [6]. The isomorphism of three kinds of projective limits is established by means of the commutative diagram 

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

where [[[pi].sup.-1].sub.n] denotes the inverse permutation, and [[pi].sub.n] denotes the fundamental bijection [G.sub.n] [right arrow] [G.sub.n] which translates the one-row notation of permutation into the cycle notation of another permutation by inserting parentheses ')(' before each proper lower record, e.g. (3, 2, 7, 6, 1, 4, 8, 5) = (3) (2, 7, 6) (1, 4, 8, 5) (Stanley [23, p. 17] gives a slightly different version of the mapping).

6 Specialisations

Some special values of the parameters [theta], [xi] and some limits are worth mentioning. We call distribution P on [G.sup.[infinity]] degenerate if [P.sub.n]([[pi].sub.n]) = 0 for some n and some [[pi].sub.n] [member of] [G.ub.n]. All distributions [P.sup.([theta], [xi])] for [theta], [xi] > 0 are nondegenerate.

The uniform distribution. The measure [P.sup.(1, 1)] may be called the uniform distribution on [G.sup.[infinity]], since every [[P.sup.(1, 1)].sub.n] is the uniform distribution on [G.sub.n], with [[P.sup.(1, 1)].sub.n] ([[pi].sub.n]) [equivalent to] 1/n! for every [[pi].sub.n] [member of] [G.sub.n]. The corresponding random order [??] on N has the characteristic property of exchangeability, that is the law of [??] is invariant under the action of [G.sub.[infinity]]. This order appears by ranking an iid sample ([X.sub.n]) from the uniform distribution on [0, 1] (or some other contunuous distribution on reals). For fixed n there are also other ways to link uniform [[pi].sub.n] to a sequence of n random reals [9].

Ewens' distributions [[P.sup.([theta], 1)].sub.n] and [[P.sup.(1, [xi])].sub.n]. Ewens' distribution on [G.sub.n] (also called [theta]-biased permutation, see [1]) is the one which assigns probability [[theta].sup.c - 1]/[([theta] + 1).sub.n - 1], to every permutation with c cycles. The partition of n comprised of cycle-sizes of [[pi].sub.n] follows then the Ewens sampling formula.

Suppose [xi] = 1, so the probabilities (3) become [[P.sup.([theta], 1)].sub.n] ([[pi].sub.n]) = [[theta].sup.l]/ [([theta] + 1).sub.n - 1] where l + 1 is the number of lower records of [[pi].sub.n]. When [[pi].sub.n] follows [[P.sup.([theta], 1)].sub.n] then also [[[pi].sup.-1].sub.n], because l([[pi].sub.n]) = l([[[pi].sup.-1].sub.n]). To see this, draw permutation in two dimensions as a point scatter {(j, [[pi].sub.nj]), j [member of] [n]}. Observe that the records are those points which do not have other points south-west of them. Flip the picture about the diagonal to see that the property is preserved. The inversion combined with the [??]-mapping in Section 5 transforms the distribution in its conventional 'cycle form'. Therefore we still call [[P.sup.([theta], 1)] and [[P.sup.(1, [xi])] Ewens' distributions (this viewpoint was suggested in [14, 15]).

By the same flipping argument, the sequence of lower record times [t.sub.-l], ..., [t.sub.-1], [t.sub.0] coincides with the decreasing sequence of lower record values of the inverse permutation [[[pi].sup.-1].sub.n], hence under [P.sup.([theta], 1)] we have further symmetry: ([t.sub.-l], ..., [t.sub.-1], [t.sub.0]) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] ([r.sub.o], ...,[r.sub.-1], [r.sub.-l]).

Distributions with equal parameters. For [theta] = [xi] there is a symmetry between lower and upper records. For distributions [[P.sup.([theta], [theta])].sub.n] ([[pi.sub.n]) = [[theta].sup.l + u]/[(2[theta]).sub.n + 1] the minimal sufficient statistic is the total number of records l + u + 1. Given the value of this statistic, [[pi].sub.n] is uniformly distributed.

Bernoulli pyramids [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (0 [less than or equal to] p [less than or equal to] 1, p + q = 1). If [theta], [xi] [right arrow] [infinity] but so that [theta]/([theta] + [xi]) [right arrow] p, then under the limiting law the probability of [[pi].sub.n] is [p.sup.l] [(1 - p).sup.u] provided l + u = n - 1, and the probability is zero otherwise. Such [[pi].sub.n] has each [[pi.sub.nj] (j > 1) an upper record with probability p and a lower record with probability 1-p. Only extreme initial ranks are possible, i.e [i.sub.j] [member of] {1, j}. Such distributions were exploited in optimal stopping [5, 12]. One way to generate such permutation is to split [n] by binomial variable at some intger v, then let [[pi].sub.1] = v] for the center and then riffle-shuffle v + 1, ..., n and v-1, ..., 1 to obtain [[pi].sub.2n], ..., [[pi.sub.nm]. In the cases p = 1 (respectively, p = 0) the distribution concentrates on the permutation (n, ..., 1) (respectively, (1, ..., n)).

Degenerate Ewens' permutations [P.sup.([theta], 0)], [P.sup.(0, [xi])]. In the limiting case [theta] [right arrow] 0 (but [xi] > 0), the permutation has the form [[pi].sub.n] = (1, [[pi]'.sub.n - 1]), where [[pi]'.sub.n - 1] is a permutation of {2, ..., n} which upon obvious identification has [[P.sup.(1, [xi])].sub.n - 1] distribution. In the limiting case [xi] [right arrow] (but [theta] > 0 ),the permutation has the form [[pi].sub.n] = (n, [[pi]'.sub.n - 1]), where [[pi]'.sub.n - 1] is a permutation of [n - 1] which has [[P.sup.([theta], 1)].sub.n - 1] distribution.

Permutations with only one proper record [[P.sup.(p, q)0] (0 [less than or equal to] p [less than or equal to] 1, p + q = 1). When both [theta], [xi] [right arrow] 0 but so that [theta]/([theta] + [xi]) [right arrow] p for some p [member of] [0, 1], then the limit law of [[pi].sub.n], is that of ([[pi].sub.n1], [[pi].sub.n2], [[pi]'.sub.n - 2]) where ([[pi].sub.n1], [[pi].sub.n2]) is either (1, n) or (n, 1) with probability p and 1 - p, respectively, while [[pi]'.sub.n - 2] is a uniform permutation of {2, ..., n - 1} independent of ([[pi].sub.n1], [[pi].sub.n2]).

Proposition 4 The weak closure of the ([theta], [xi])-family of distributions on [G.sub.[infinity]], is comprised of nondegenerate ditributions with [theta] > 0, [xi] > 0, and of the three degenerate types described above.

Proof: This follows by considering [[P.sup.([theta], [xi])].sub.2] and [[P.sup.([theta], [xi])].sub.3]. [there does not exist]

7 Characterisation of mixtures by sufficiency

We seek now for a two-parameter generalisation of [8], Theorem 12 (i)], that is we wish to characterise the distributions [P.sup.([theta], [xi])] as extreme points of a suitable family of probabilities on [G.sup.[infinity]] that are conditionally uniform on each [G.sub.n]. The following lemma is helpful.

Lemma 5 Let [Q.sub.1] be the law of are independent 0-1 sequence [B.sub.1], [B.sub.2], ... with [B.sub.n] Bernoulli (1/n). Assume Q is a distribution for [B.sub.1], [B.sub.2], ... with the property that, for each n, the conditional law of ([B.sub.1],..., [B.sub.n]) given [S.sub.n] := [B.sub.1] + ... + [B.sub.n] and given ([B.sub.m], m > n) under Q is the same as under [Q.sub.1]. Then Q is a unique mixture of distributions [Q.sub.[eta]], [eta], [member of] [0, [infinity]], under which [B.sub.1], [B.sub.2], ... are independent with [B.sub.[eta]] Bernoulli ([eta]/([eta] + r[eta] - 1)).

Proof: This can be concluded from either [[20], p. 269] or [[8], Lemma 9]. The key issue is that the convergence [S.sub.n]/ log n [right arrow] [eta] holds under [Q.sub.[eta]] almost surely. [there does not exist]

The first two assertions of the next proposition are equivalent to [[8], Theorem 12 (i)] and included here for completeness of exposition.

Proposition 6 For P a probability on [G.sup.[infinity]] suppose the distribution of [[pi].sub.n] for every n = 1, 2, ... is uniform conditionally given the value of a statistic stat. Then the following assertions are true:

(i) for stat = l distribution P is a unique mixture of [P.sup.([theta], 1)] ([theta] [member of] [0, [infinity][) and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.],

(ii) for stat = u distribution P is a unique mixture of [P.sup.(1, [xi])] ([xi] [member of] [0, [infinity][) and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.],

(iii) for stat = l + u distribution P is a unique mixture of [P.sup.([theta], [theta])] ([theta] [member of]0, [infinity][), [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.],

(iv) for stat = (l, u) distribution P is a unique mixture of nondegenerate distributions [P.sup.([theta], [xi])] ([theta], [xi] [member of] ]0, [infinity] [), degenerate distributions [P.sup.([theta], 0] and [P.sup.(0, [xi]] ([theta], [xi] [member of]]o, [infinity][), and further degenerate distributions [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.](p [member of] [0,1]). The degenerate distributions do not enter provided [P.sub.3] > 0.

Proof: We need to show that the described distributions and only they are extreme. Assuming P extreme in the setting of (iv), the tail algebra F of the process ((l([[pi].sub.n]), u ([[pi].sub.n])), n = 1, 2, ...) must be trivial. Let [B.sub.n] = 1([r.sub.n + 1] [member of] {1, n + 1}) be the indicator of some record at position n + 1. Under [P.sup.(1, 1)] the law of ([B.sub.1], [B.sub.2], ...) is [Q.sub.2], hence by Lemma 5 and because lim [S.sub.n]/ log n is F-measurable the law of ([B.sub.n]) under P is the same as under [Q.sub.[eta]] for some [eta]. This says that records occur by a Bernoulli process, without specifying the types of records. If [eta] = 0 the situation is clear: there is only one proper record (for n > 1) and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] are the sole possibilities. Suppose [eta] [not equal to] 0. A key to recognise how the records are classified in types is the exchangeability. Let [I.sub.k] be the indicator of the event that the record at (k + 1)st record time is a lower record. Conditionally given [I.sub.1] + ... + [I.sub.k] = l - 1 all values of the sequence ([I.sub.1], ..., [I.sub.k]) have the same probability 1/ ([MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]), because by Lemma 1 this is true under [P.sup.(1, 1)] by the virtue of a simple stopping times argument. By de Finetti's theorem, there exists a relative frequency of lower records, hence l([[pi].sub.n])/(l([[pi].sub.n] + u([[pi].sub.n])) must converge almost surely. But the limit of this ratio is F-measurable hence constant, say p. Appealing again to Lemma 1 we see that ([B.sub.n]) and ([I.sub.k]) are independent, hence the set of positions of lower records is the one obtained by independent thinning with probability p of the occurences of l's in ([B.sub.n). Thus P =[[P.sup.([theta], [xi])] with [theta] = p[eta], [xi] = (1 - p)[eta] (the instance [eta] = [infinity] is included). Part (iii) is shown similarly, with the special feature that p = 1/2. [there does not exist]

The result suggests a practical way to generate all possible coherent permutations with a suitable kind of sufficiency. For instance, if we wish to produce a nondegenerate sequence of permutations with every [[pi].sub.n] conditionally uniform given (l, u), then we need to first specify a distribution for positive ([theta], [xi]), to choose the parameters from this distribution and finally to construct permutation from the independent initial ranks whose distributions involve the chosen parameters. It should be noticed, however, that this de-Finetti-type procedure covers all possibilities only under the coherence condition. For each fixed n > 2 there exist conditionally uniform distributions on [G.sub.n] which are not mixtures of [[P.sup.([theta], [xi])].sub.n]'s.

Recall that de-Finetti's theorem can be stated as follows: if a 0-1-sequence ([B.sub.n]) is such that for every n the law of ([B.sub.1], ..., [B.sub.n]) is uniform conditionally given the number of l's then ([B.sub.n]) is a unique mixture of independent coin-tossing processes. In this spirit, Proposition 6(iv) says that if for ([I.sub.n]) (with the range of [I.sub.n] being [n]) the law of ([I.sub.1], ..., [I.sub.n]) for every n is uniform conditionally given [l.sub.n] := {1 < j [less than or equal to] n: [I.sub.j] = 1} and [u.sub.n] := {1 < j [less than or equal to] n : [I.sub.j] = j} then ([I.sub.n]) is a unique mixture of independent processes (5) (including the degenerate cases).

To put the characterisation result in the framework of arrays of combinatorial numbers [7, 8], denote [w.sub.n,](l, u) the probability for l lower and a upper proper records in [[pi].sub.n]. By the rule of addition of probabilities we have

[w.sub.n] (l, u) = [w.sub.n + 1](l + 1, u) + [w.sub.n + 1](l, u + 1) + (n - 1)[w.sub.n + 1](l, u), [w.sub.1] (0, 0) = 1, (6)

which is a recursion dual to (1). The set of nonnegative solutions to (6) is a convex compact set, and Proposition 6(iv) describes the set of extreme solutions to (6). Interestingly, the set of extremes is not closed: each distribution [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] with 0 < p < 1 appears as a limit of some nondegenerate [P.sup.([theta], [xi])]'s, but it is decomposable as a mixture [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.].

A familiar method of finding the extreme solutions of (6) is based on identifying the Martin boundary. To that end, one explores asymptotic regimes for l' = l'(n'), u' = u'(n') as n' [right arrow] [infinity], which guarantee for all n, f, a convergence of the ratios

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (7)

where the numerator is the number of permutations [[pi].sub.n'], of [n'] with record counts (f', u'), such that the restriction of [[pi].sub.n'], to [n] has record counts (l, u). Using a monotonicity argument like in [8], the things

can be reversed to show that the convergence l'/ log n' and u'/ log n' is necessary and sufficient for the convergence of the ratios (7) for all n, u, l (hence the Martin boundary coincides with the set of extreme solutions).

8 Related distributions and asymptotics

As in the case of the uniform distribution [19], asymptotic properties (as n [arrow roght] [infinity]) of record counts l = l([[pi].sub.n]), u = u([[pi].sub.n]) under [P.([theta]) follow straightforwardly from the representation via independent initial ranks. Thus, both mean and variance of l are asymptotic to [theta] log n, and that of u to ( log n. Jointly, (l, u) converge in distribution to independent Gaussian variables. The point processes of scaled record times {[t.sub.k]/n : 1 < 0}, {[t.sub.k]/n : 1 > 0} converge to independent Poisson processes with intensities [theta]dt/t, [zeta]dt/t (for t [member of] [0,1]), respectively.

The behaviour of each [[pi].sub.nj] under [P.sub.([theta][zeta]) as n varies is that of a process with exchangeable 0-1 increments, known as Polya's urn model. That is to say, each sequence ([[pi].sub.nj], n [greater than or equal to]j) is a nondecreasing inhomogeneous Markov chain on integers, which starts at some random initial rank [[pi].sub.jj] = [l.sub.j] at time j, and at time n either j umps from some rank [[pi].sub.nj] = v to v + 1 with probability (v -1 + [theta]) / (n - 2 + [theta] + [zeta] or otherwise remains at v.

The law of re c ([[pi].sub.n]) can be expressed in terms of Polya-Eggenberger distributions

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The distribution of the center [r.sub.0] = [[pi].sub.n1] is [PE.sup.([theta],[zeta].sub.n]. Conditionally given [r.sub.0], the lower and upper record sequences are independent. The sequence of lower records [r.sub.-1],..., [r.sub.-e] is a homogeneous decreasing Markov chain on integers which starts at [r.sub.0] and terminates at 1, each time descending from the generic r to r - d with probability [PE([theta],1]) (d). In a similar way, the sequence of upper records [r.sub.1], ..., [r.sub.u] is a homogeneous increasing Markov chain on integers which starts at [r.sub.0] and terminates at n, each time ascending from some r to r + d with probability [PE.sup.([zeta],1])sub.n-r +1(d).

Asymptotics of the record values follow from the well known properties of Polya urns. Recall that beta(a, b) distribution with parameters a > 0, b > 0 is the distribution on [0,1] with density [[x.sup.a]-1(1 - x]).sup.b-1/B(a, b), where B(a, b) = [GAMMA](a)[GAMMA](b)/[GAMMA](a + b).

Proposition 7 As n [right arow] [infinity], under [P.sup.([theta][zeta]]) the scaled record values of [[pi].sub.n] converge,

[MATHEMATECAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

The distribution of [p.sub.0] is beta([theta][zeta]). Given po the sequences ([P.sub.k], < 0) and (Pk,1 > 0) are independent and representable as

where [T.sub.k]'s are beta([theta]), [Z.sub.k]'s are beta(([zeta] 1) and the variables [p.sub.0], [T.sub.k] (k < 0) and [Z.sub.k] (k > 0) are all independent.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Let S be the space of two-sided nondecreasing sequences ([x.sub.k], 1 [member of] Z), [x.sub.k [member of] [0,1], endowed with the product topology of [[0, 1].sup.z]. Padding re c ([[pi].sub.n],) by infinitely many l's on the left and infinitely many n's on the right, and scaling by n makes [n.sup.-1] rec ([[pi].sub.n]) a random element of S

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Proposition 7 is a strong law of large numbers which says that [n.sup.-1]rec([[pi].sub.n]) converge in S almost surely to a limit (Pk).

Recall that GEM([beta]) distribution is the law of the sequence of gaps obtained by breaking [0,1] at atoms of the Poisson point process with intensity [theta]dx/x ([member of] [0,1]) [1, 21]. The decreasing sequence of atoms has the same distribution as the sequence of 'stick-breaking' products [D.sub.1], [D.sub.1], [D.sub.,..., with the [D.sub.j]'s being iid beta(theta],1). The two-sided sequence ([P.sub.k], k [member of] Z) is obtained in a similar way, by splitting [0,1] at [p.sub.0], and further partitioning the intervals [0, [p.sub.0] and [[p.sub.0], 1] by two independent beta stick-breakings with parameters [theta] and [zeta]. By analogy, the sequence of gaps [P.sub.k]+1 - [P.sub.k], k [member of] Z, may be regarded as a two-sided version of the GEM distribution.

Generalising the classical case of sampling from iid uniforms [22, Proposition 4.11.2], the distribution of the bivariate point process of upper record values and their durations follows from the spraying property of Poisson processes. (The latter also applies for lower records, of course.) Thus, given po the point processes {(p.sub.k], [t.sub.k]+1-[t.sub.k]), k [greater than or equal to] 0} and {p.sub.k]}, [t.sub.k] -1 -[t.sub.k]), 1 < 0}, are independent Poisson, with intensity measures [zeta][x.sup.j]-idx on [[p.sub.0], 1] x N and [theta][(1 - x).sup.j-i]dx on [0, [p.sub.0]] x N, respectively. In particular, by the projection property of Poisson processes, given [p.sub.0] the conditional distribution of the number of pairs of neighbouring lower records #{k [less than or equal to] 0 : [t.sub.k] 1 - [t.sub.k] = 1} is Poisson(Bpo) (an equivalent result is shown in [13, Corollary 3.1] by a computation of moments).

9 Generating permutations from continuous variates

Under P([theta][zeta]) not only the scaled record values converge (see Proposition 7), but also scaled permutations ([[pi.sub.nj]/n, j [member of] N) converge almost surely to some random sequence ([X.sub.j]) [member of] [0,1] [infinity]. In the case of uniform distribution [P.sup.(1,1)], the sequence ([X.sub.j]) is just iid uniform[0, 1], and ([[pi].sub.j]) can be generated by ranking ([X.sub.j]), as we already mentioned. Under any P([[theta][zeta]]), ([X.sub.j]) can be produced by a kind of shuffling of the sequences of record values ([P.sub.k], k [less than or equal to] 0), ([p.sub.k])k, 1 < 0) and another independent sequence of uniform variables. Here and henceforth, under shuffling of a few sequences we understand a sequence which is comprised of terms of all these sequences arranged in such a way that each of the sequences enters in its original order.

Construction 8 Let ([W.sub.n]) be iid uniform [0,1], independent of ([P.sub.k]). We define a new sequence ([X.sub.n]) where some [W.sub.n]'s are used, and some are replaced by [p.sub.k]'s which will appear as upper and lower record values. Start with [X.sub.1] = [p.sub.1]. Suppose before step n + 1 the values p-e,, [p.sub.u] have been included into [X.sub.1],..., [X.sub.n]; then [p.sub.1], = max([X.sub.1],,..., [X.sub.n]) and p-,, = min([X.sub.1],..., [X.sub.n]). At step n + 1 we let [X.sub.n]+1 = [p.sub.u]+1 if [[pi].sub.n]+1 > [p.sub.u] or [X.sub.n]+1 = P-e- t if [[pi].sub.n]+1 < p=f, or [X.sub.n]+1 = [[pi].sub.n]+1 otherwise. Define a coherent sequence of permutations ([pi].sub.n]) by ranking ([X.sub.n]).

It is obvious that, given ([P.sub.K], the sequence ([X.sub.n]) resulting from the construction has the same law as iid uniform[0,1] sequence conditioned on its two-sided sequence of record values (see [10] for the one-sided case of upper records). This works for any 0, ( because conditionally given (Pk) the distribution of (7ru) under any P([theta],[zeta]) is the same as under the uniform distribution [P(11)]

For every fixed n a similar procedure yields uniform permutation [[pi].sub.n] conditioned on rec([[pi].sub.n]). Start with setting [[pi].sub.n1] = [r.sub.0]. At each step j > 1 we will have [[pi].sub.n], ..., [[pi].sub.-1] already determined, with some maximum max([[pi].sub.n1], ..., [[pi].sub.n, j-1]) = [r.sub.u'] and some minimum min([[pi].sub.n1], ..., [[pi].sub.n,j-1]) = [r.sub.l']. At step j [member of] {2, ..., n} a value v is chosen uniformly at random from [n] \ {[[pi].sub.n1], ..., [[pi].sub.n,j-1]}. If v < [r.sub.-l] let [[pi].sub.nj] = [r.sub.-l-1], if v > [r.sub.u'] let [[pi].sub.nj] = and if [r.sub.-l'] < v < [r.sub.u'] let [[pi].sub.nj]= v. The sampled value v is replaced each time v breaks the last upper or lower record. In n steps the increasing sequences ([r.sub.-l], ..., [r.sub.-1]), ([r.sub.1], ..., [r.sub.u]) are shuffled with other elements of [n]. It is intiutively clear and not hard to show that, as ra becomes large, [n.sup.-1]rec([[pi].sub.n]) = [n.sup.-1](..., 1, [r.sub.-l'], ... [r.sub.-1], [r.sub.0], [r.sub.1], ..., [r.sub.u'] n, ...) will converge in S to ([[rho].sub.k]). This is just because sampling f[r.sub.0]m large finite sets will have nearly the same effect as independent uniform choices f[r.sub.0]m [0, 1].

Apparently, from the viewpoint of statistical theory of extremes the sequence ([X.sub.n]) is rather exotic, as it is chosen just to simulate desired behaviour of records. This differs general [P.sup.([theta], [zeta])] from the uniform distribution P(14), when 'injecting' some extrinsic (Pk) is not at all necessary since the uniform sample ([W.sub.n]) supplies automatically appropriate record values, so ([X.sub.n]) [??] ([W.sub.n]). Still, in the case of integer parameters there is a simpler way to produce app[r.sub.0]priate ([X.sub.n]) f[r.sub.0]m a sequence of uniforms, as parallels the construction of permutations in Proposition 3.

Construction for integer values of the parameters. The idea is to assume some 'prehistorical' sample of uniforms. Suppose [theta] [greater than or equal to] 1, [zeta] [greater than or equal to] 1 are integers. For d = [theta] + [zeta] - 2 let [V.sub.1], ...,[V.sub.d], [W.sub.1],[W.sub.2], ... be iid uniform [0,1]. At step 1 choose [X.sub.1] as the value of rank [theta] among [V.sub.1], ...,[V.sub.d],[W.sub.1]. At each step n we will have max([X.sub.1], ...,[X.sub.n]) equal to the (n - [theta] + 1)th order statistic in [V.sub.1], ...,[V.sub.d], [W.sub.1], ...,[W.sub.n], and min([X.sub.1], ...,[X.sub.n]) equal to the [theta]th order statistic in [X.sub.1]m ...,[X.sub.d],[W.sub.1], ...,[W.sub.n]. Now, if [W.sub.n+1] > max([X.sub.1], ...,[X.sub.n]) we set [X.sub.n+1] equal to the (n+[theta]-1)th order statistic in [V.sub.1], ...,[V.sub.d],[W.sub.1], ...,[W.sub.n],[W.sub.n+1], if [W.sub.n+1] < min([X.sub.1], ...,[X.sub.n]) we set [X.sub.n+1] equal to the [theta]th order statistic in the same sequence, and otherwise let [X.sub.n+1] = [X.sub.n+1]. This works, since there are always [theta] spacings below min ([x.sub.1], ...,[X.sub.n]) and [zeta] spacings above max([X.sub.1], ...,[X.sub.n]), thus the resulting ranking is as in the p[r.sub.0]of of P[r.sub.0]position 3.

The described process shows that, for integer [theta] > [greater than or equal to] 1, [zeta] [greater than or equal to] 1, P[r.sub.0]position 7 is a consequence of properties of the uniform order statistics. For all other values of [theta],[zeta] the result can be interpolated f[r.sub.0]m the integer case, because the law of each [[pi].sub.n] is a rational function of the parameters of beta laws for [T.sub.k],[Z.sub.k].

received 14 Feb 2006, revised 23rd January 2008, accepted 23rd January 2008.

References

[1] R. Arratia, A.D. Barbour and S. Tavare, Logarithmic combinatorial structures: a probabilistic approach, European Math. Soc. Publ. House, Zurich, 2003.

[2] F.N. David and D.E. Barton, Combinatorial chance, Griffin & Co, London, 1962.

[3] P. Diaconis, M. McGrath and J. Pitman, Riffle shuffles, cycles and descents, Combinatorlca, 15 (1995) 11-29.

[4] F.G. Foster and A. Stuart, Distribution-free tests in time-series based on the breaking of records, J. R. Stat. Soc. Ser. B 16 (1954) 1-22.

[5] A. Gnedin and U. Krengel, A stochastic game of optimal stopping and order selection, Ann. Appl. Prob. 5 (1995) 310-321.

[6] A. Gnedin and G. Olshanski, Coherent random permutations and the boundary problem for the graph of zigzag diagrams, Int. Math. Res. Notes Article m 51968 (2006) 39 pp.

[7] A. Gnedin and G. Olshanski, The boundary of the Eulerian number triangle, Moscow Math. J. 6 (2006) 461-475.

[8] A. Gnedin and J. Pitman, Exchangeable Gibbs partitions and Stirling triangles, Zapiski POMI (St. Petersburg Dept. Steklov Math. Inst.) 325 (2005) 82-105, also J. Math. Sci. 138 (2006) 5674-5685.

[9] C.M. Goldie, Records, permutations and greatest convex minorants, Math. Proc. [G.sub.n]b. Phil. Soc. 106 (1989) 169-177.

[10] C.M. Goldie and J. Bunge, Record sequences and their applications, in Handbook of Statistics vol. 19, (Stochastic Processes: Theory and Methods, Shanbhag, D.N. and Rao, C.R. eds), pp. 277-308, North Holland, Amsterdam, 1999.

[11] J. Hajek, Z. Sidak and P.K. Sen, Theory of rank tests, Academic Press, 1998.

[12] T.P. Hill and D.P. Kennedy, Sharp inequalities for optimal stopping with rewards based on ranks, Ann. Appl. Prob. 2 (1992) 503-517.

[13] L. Holst, On the number of consecutive successes in Bernoulli trials, (2006) preprint.

[14] S.V. Kerov, Subordinators and the permutation actions with quasi-invariant measure, J. Math. Sci. 87 (1997) 4094-4117.

[15] S.V. Kerov and N.V. Tsilevich, A random subdivision process generates virtual permutations with Ewens distribution, J. Math. Sci. 87 (1997) 4082-4093.

[16] S.V. Kerov, G. Olshanski and A.M. Vershik, Harmonic analysis on the infinite symmetric group, Comptes Rend. Acad. Sci. Paris, 316 (1993) 773-778.

[17] S. Lalley, Riffle shuffles and their associated dynamical systems, J. Theor Prob. 12 (1999) 903-932.

[18] H. Mahmoud, P. Flajolet, P. Jacquet and M. Regnier, Analytic variations on bucket selection and sorting. Acta. Inform. 36 (2000) 735-760.

[19] VB. Nevzorov, Records, Transl. Math. Monographs, Providence, AMS, 2001.

[20] J. Pitman, An extension of de Finetti's theorem, Adv. Appl. Prob. 10 (1978) 268-270.

[21] J. Pitman, Combinatorial stochastic processes, Lecture Notes Math. vol. 1875, Springer, NY, 2006.

[22] S. Resnick, Adventures in stochastic processes, Birkhduser, Boston, 1992.

[23] R. Stanley, Enumerative Combinatorics vol. 1, Wadsworth & Brooks/Cole, 1986.

Alexander Gnedin

Mathemtical Institute, Utrecht University, P.O. Box 80010, 3508 TA Utrecht, The Netherlands, [e-mail]