A growth rule which received considerable attention in the literature is the following preferential attachment algorithm on permutations written as the product of cycles known as the Chinese restaurant process (CRP) [1, 5, 9, 12–14, 16, 20, 23]. For n ≥ 1, given a permutation of [ n − 1 ] : = 1 , 2 , … , n − 1 which has been constructed at step n − 1, element n is either appended to the permutation as a new singleton cycle with probability θ θ + n − 1 , or inserted into a random position within the existing permutation with probability equal to n − 1 θ + n − 1 . Let S n be the set of permutations on [ n ]. The permutation obtained at step n has the Ewens distribution, which is the uniform distribution on n ! permutations in the case θ = 1, and, in general, has probability distribution θ | π | / θ ( n ) , π ∈ S n , where θ ( n ) : = θ ( θ + 1 ) ⋯ ( θ + n − 1 ) and | π | is the number of cycles in π.

Let Π n be the random permutation of [ n ] at the nth step of the CRP. The distribution of Π n is invariant under relabelling. For different orders the permutations are consistent, in the sense that Π m , for m < n, can be derived from Π n by removing elements m + 1 , … , n from their cycles and deleting empty cycles if necessary.

The CRP expresses every permutation π of [ n ] uniquely as the product π = ( x 1 , 1 … x 1 , m 1 y 1 ) ( x 2 , 1 … x 2 , m 2 y 2 ) ⋯ ( x τ , 1 … x τ , m τ y τ ) , τ ≥ 1 , where the following two conditions are satisfied: 1.

y 1 < y 2 < ⋯ < y τ

The number of cycles in Π n , denoted by K n , has probability generating function (p.g.f.) E z K n = ( θ z ) n ( θ ) n , which corresponds to the distribution of the sum of n independent Bernoulli variables K n = ∑ i = 1 n I i , I i ∼ Bernoulli ( θ / ( i + θ − 1 ) ); see [1]. We have I i = 1 exactly when the element i starts a new cycle. As n → ∞, K n ∼ θ log n a . s . , K n − θ log n θ log n → d N ( 0 , 1 ) , where → d denotes convergence in distribution.

In this paper, a CRP will be defined for multiset permutations and derived using the methods in [23]. As motivation, we note that multiset permutations are of fundamental interest in combinatorics [22] and random multiset permutations have been studied previously [10].

There are at least two different ways of defining cycles of multiset permutations [19, 22]. Knuth’s way [19] will be used in this paper. In this section, we summarise the discussion and results on multiset permutation factorisation taken from Section 5.1.2 of [19] that is needed in this paper. In particular, we are going to use Theorem 1 below to factor multiset permutations. A multiset is like a set except that it can have repetitions of identical elements, for example M = { 1 , 1 , 1 , 2 , 2 , 3 , 4 , 4 , 4 , 4 } , where the set { 1 , 2 , 3 , 4 } is given the usual ordering. A permutation of a multiset is an arrangement of its elements in a row, for example 3 1 2 4 4 1 2 4 1 4 . We may write this in two-line notation as (1) 1 1 1 2 2 3 4 4 4 4 3 1 2 4 4 1 2 4 1 4 . The intercalation product π 1 ⊥ π 2 of two multiset permutations π 1 and π 2 is defined in [6, 11] and is obtained by 1.

Expressing π 1 and π 2 in the two-line notation.

Knuth [19] proves the following factorisation of multiset permutations into cycles.

Note that (2) is not in the form (3). The factorisation of (1) corresponding to Theorem 1 is ( 3 1 ) ⊤ ( 1 ) ⊤ ( 2 4 2 4 4 1 ) ⊤ ( 4 ) = 3 1 1 3 ⊤ 1 1 ⊤ 2 4 2 4 4 1 4 2 4 4 1 2 ⊤ 4 4 = 3 1 1 2 4 2 4 4 1 4 1 3 1 4 2 4 4 1 2 4 = 1 1 1 2 2 3 4 4 4 4 3 1 2 4 4 1 2 4 1 4 .

Given a fixed sequence of positive integers n i ≥ 1, i ≥ 1, we will construct a CRP process on permutations of multisets indexed by integers t ≥ 0. We define M ( n 1 , … , n t ) to be the multiset which contains n i copies of i for i ∈ [ t ], t ≥ 1, and ∅ for t = 0. We give the set of elements [ t ] of M ( n 1 , … , n t ) the usual ordering. The set of permutations of M ( n 1 , … , n t ) is denoted by S ( n 1 , … , n t ) and is of size | S ( n 1 , … , n t ) | = N t n 1 , … , n t , where N t = n 1 + ⋯ + n t . Note that S n = S ( 1 , 1 , … , 1 ︸ n times ). The random multiset permutation Π ˜ t of our process at the tth step is an element of S ( n 1 , … , n t ), represented in accordance with (3). At step t ≥ 1, there are n t copies of t either to be inserted in the existing permutation Π ˜ t − 1 or to be put into singleton cycles. (It is not possible to put more than one copy of t in a new cycle because of condition 2 of Theorem 1.) Suppose that k t ∈ { 0 } ∪ [ n t ] of the n t copies of t start k t new singleton cycles containing t, and the n t − k t other copies of t are inserted into the existing permutation. The n t − k t copies of t can be inserted to the left of any of the y i or x i j in (3). A ‘stars and bars’ argument shows that the number of ways of inserting n t − k t copies of t to the left of an element in the multiset S ( n 1 , … , n t − 1 ) formatted like (3) is (4) N t − 1 − 1 + n t − k t n t − k t , recalling that − 1 k = 1 if k = 0 ; 0 if k > 1 .

We now define the multiset CRP. Given θ > 0, define F t ( θ ) = ∑ k t = 0 n t N t − 1 − 1 + n t − k t n t − k t θ k t The special case (5) F t ( 1 ) = ∑ k t = 0 n t N t − 1 − 1 + n t − k t n t − k t = N t n t . results from the well known identity (6) ∑ ρ = 0 ν μ + ρ ρ = μ + ν + 1 ν , ν , μ ≥ 0 integers ; see page 161 of [15]. Note that (5) is the total number of ways of extending the permutation from time t − 1 to time t. At time t ≥ 1, k t new singleton cycles containing t are created and the other n t − k t copies are inserted into the existing permutation in a specified way with probability θ k t / F t ( θ ). If n t = 1 for all t, then F t ( θ ) = θ + t − 1 and we recover the usual CRP. An induction argument on t shows that all possible π ∈ S ( n 1 , … , n t ) can be constructed in this manner. This can also be seen from the identity N t n 1 , … , n t = ∏ s = 1 t N s n s

Next we will find the distribution of Π ˜ t .

For different steps the permutations are consistent, in the sense that Π ˜ s , for s < t, can be derived from Π ˜ t by removing elements s + 1 , … , t from their cycles and deleting empty cycles if necessary.

Let X t denote the number of new cycles added in moving from time t − 1 to time t, t ≥ 1, which is the choice of k t above. The X t are independent with distributions given by (10) IP ( X t = k t ) = θ k t F t ( θ ) N t − 1 − 1 + n t − k t n t − k t , k t ∈ { 0 } ∪ [ n t ] .

If θ = 1, then, by (5), we have (11) IP ( X t = k t ) = 1 N t n t N t − 1 − 1 + n t − k t n t − k t = n t k t N t k t N t − n t N t − k t This equals the probability that starting from an urn with n t balls representing failures and N t − n t balls representing successes, that the first k t balls pulled from the urn without replacement are failures, and the ( k t + 1 )th ball pulled from an urn is a success. This description shows that Y t = X t + 1 has a negative hypergeometric distribution, which we now describe. The negative hypergeometric distribution [17, 18, 21] with parameters N, M and r is like the negative binomial distribution, but without replacement. There are N balls in total, M balls representing success and N − M balls representing failures. The hypergeometric distribution gives the probability that the rth success happens on the κth draw, κ = r , r + 1 , … , N. A negative hypergeometric random variable Y with these parameters has probability mass function (12) P ( Y = κ ) = M r − 1 N − M κ − r N κ − 1 · M − r + 1 N − κ + 1 It is easily checked that (11) is (12) with N = N t , M = N t − n t = N t − 1 , r = 1 and κ = k + 1. The expectation of Y is E ( Y ) = r N + 1 M + 1 , the variance of Y is Var ( Y ) = r ( N − M ) ( N + 1 ) ( M + 1 − r ) ( M + 1 ) 2 ( M + 2 ) and the third centred moment (see [17, 18]) is E ( [ Y − E ( Y ) ] 3 ) = Var ( Y ) · ( 2 N − M + 1 ) ( M + 1 − 2 r ) ( M + 1 ) ( M + 3 ) . Therefore, (13) E ( X t ) = E ( Y t ) − 1 = N t + 1 N t − 1 + 1 − 1 = n t N t − 1 + 1 , (14) Var ( X t ) = Var ( Y t ) = n t ( N t + 1 ) N t − 1 ( N t − 1 + 1 ) 2 ( N t − 1 + 2 ) and (15) E ( [ X t − E ( X t ) ] 3 ) = E ( [ Y t − E ( Y t ) ] 3 ) = Var ( Y t ) · ( n t + N t + 1 ) ( N t − 1 − 1 ) ( N t − 1 + 1 ) ( N t − 1 + 3 ) . It follows that the number of cycles K t = ∑ s = 1 t X t has expectation E ( K t ) = ∑ s = 1 t n s N s − 1 + 1 and variance Var ( K t ) = ∑ s = 1 t n s ( N s + 1 ) N s − 1 ( N s − 1 + 1 ) 2 ( N s − 1 + 2 ) .

Given sequences a t and b t , we use the notation a t = O ( b t ) to mean a t ≤ C b t for a constant C > 0; a t ≍ b t to mean C 1 b t ≤ a t ≤ C 2 b t for constants C 1 > 0, C 2 > 0; and a t ∼ b t to mean lim t → ∞ a t / b t = 1. We also define a t = o ( b t ) to mean lim t → ∞ a t / b t = 0. We will put the bound the n t = O ( 1 ) to give a central limit theorem for K t for all θ.

By the following theorem a Central Limit Theorem can be obtained even when n t is unbounded, which is not the case in Theorem 3.

An example where Theorem 4 holds is obtained by setting θ = 1, n t = ⌈ C t α ⌉, for constants C > 0, α > 0, where ⌈ x ⌉ is the smallest integer greater or equal to x. Then, n t = C t α + O ( 1 ) and N t = C t α + 1 / ( α + 1 ) + O ( t α ) and the assumptions of Theorem 4 hold. The expectation and variance are asymptotically E ( K t ) ∼ ( α + 1 ) log t , Var ( K t ) ∼ ( α + 1 ) log t .

Another example for θ = 1 is obtained through regular variation [4]. A positive, measurable function ℓ ( x ), defined on [ η , ∞ ) for η real, is slowly varying if (21) lim x → ∞ ℓ ( λ x ) ℓ ( x ) = 1 , ∀ λ > 0 . The Uniform Convergence Theorem [4] provides that the convergence in (21) is uniform on compact λ-sets in ( 0 , ∞ ). A positive, measurable function defined on [ η , ∞ ), is regularly varying with real index α if lim x → ∞ f ( λ x ) f ( x ) = λ α , ∀ λ > 0 . A regularly varying function with index α can be written as f ( x ) = x α ℓ ( x ) , where ℓ ( x ) is a slowly varying function. Suppose that ℓ ( x ) is locally bounded in [ η , ∞ ), i.e. bounded on compact subsets of [ η , ∞ ), and α > − 1. Karamata’s theorem gives ∫ η t x α ℓ ( x ) d x ∼ t α + 1 ℓ ( t ) / ( α + 1 ) , t → ∞ . We further suppose that η ≤ 1, α ≥ 0, with lim x → ∞ ℓ ( x ) = ∞ in the case α = 0, and define n t = ⌈ ∫ t t + 1 x α ℓ ( x ) d x ⌉ , t ≥ 1 . The Uniform Convergence Theorem implies that sup t ≤ x ≤ t + 1 ℓ ( x ) ℓ ( t ) − 1 ≤ sup 1 ≤ λ ≤ 2 ℓ ( λ t ) ℓ ( t ) − 1 = o ( 1 ) , from which ∫ t t + 1 x α ℓ ( x ) d x = ( 1 + o ( 1 ) ) ℓ ( t ) ∫ t t + 1 x α d x = ( 1 + o ( 1 ) ) ℓ ( t ) ( t α + o ( t α ) ) and n t ∼ t α ℓ ( t ) . Moreover, Karamata’s theorem gives us N t − 1 ∼ t α + 1 ℓ ( t ) / ( α + 1 ) . Hence, the conditions of Theorem 4 hold.

We will now show that n t may be chosen in such a way that the conclusion of the central limit theorem does not hold for K t . Suppose that θ = 1 and the n t are chosen such that (22) N t − 1 = o ( n t ) . By (13) and (14), we have E ( X t ) ∼ n t N t − 1 , Var ( X t ) ∼ n t N t − 1 2 . We further choose the n t such that (23) ∑ s = 1 t − 1 Var ( X s ) = o Var ( X t ) ,

A particular example of such a sequence is n t = ⌈ e t 3 ⌉ = e t 3 + O ( 1 ) , from which N t = ∑ s = 1 t e s 3 + O ( t ) = e t 3 1 + ∑ s = 1 t − 1 e s 3 − t 3 + O ( t ) = e t 3 1 + O t e ( t − 1 ) 3 − t 3 + O ( t ) = e t 3 ( 1 + o ( 1 ) ) . Clearly, (22) holds and we also have ∑ s = 1 t − 1 Var ( X s ) = O ∑ s = 1 t − 1 e 2 s 3 − 2 ( s − 1 ) 3 = O ∑ s = 1 t − 1 e 6 s 2 − 6 s = O t e 6 ( t − 1 ) 2 − 6 ( t − 1 ) = o e 6 t 2 − 6 t and so (23) holds, as well, because Var ( X t ) ∼ e 6 t 2 − 6 t + 2 .

Assuming (22) and (23), we have (24) K t − E ( K t ) Var ( K t ) = X t − E ( X t ) Var ( X t ) ( 1 + o ( 1 ) ) + ∑ s = 1 t − 1 ( X s − E ( X s ) ) Var ( K t ) . Suppose that K t − E ( K t ) Var ( K t ) → d N ( 0 , 1 ) . By our assumptions, the variance of the last term of (24) is o ( 1 ) and so by Slutsky’s theorem [8] (25) lim t → ∞ P X t − E ( X t ) Var ( K t ) ≤ 0 = lim t → ∞ P K t − E ( K t ) Var ( X t ) ≤ 0 = 1 / 2 , We will show that (25) is impossible. The c.d.f. of X t is given by (26) P ( X t ≤ x t ) = ∑ k t = 0 x t P ( X t = k t ) = 1 N t n t ∑ k t = 0 x t N t − 1 − 1 + n t − k t n t − k t (27) = 1 N t n t ∑ j = 0 n t N t − 1 − 1 + j j − ∑ j = 0 n t − x t − 1 N t − 1 − 1 + j j = 1 N t n t N t n t − N t − x t − 1 n t − x t − 1 (28) = 1 − ( N t − x t − 1 ) ! / ( n t − x t − 1 ) ! N t ! / n t ! ≥ 1 − N t − x t − 1 N t N t − 1 , where we have used (11) at (26), (6) at (27), and ( N t − x t − 1 − i ) / ( N t − i ) ≤ ( N t − x t − 1 ) / N t for all 0 ≤ i ≤ N t − 1 − 1 at (28). We therefore have lim inf t → ∞ P ( X t ≤ E ( X t ) ) ≥ 1 − lim t → ∞ N t − E ( X t ) − 1 N t N t − 1 = 1 − lim t → ∞ N t − n t ( 1 + o ( 1 ) / N t − 1 − 1 N t N t − 1 = 1 − lim t → ∞ 1 − ( 1 + o ( 1 ) ) / N t − 1 N t − 1 = 1 − e − 1 > 1 / 2 , contradicting (25).

Potentially, improvements might be made on these results. The CRP we have defined places all n t elements labelled t at the same time. Placing them sequentially seems like a difficult problem. It would be interesting to get better estimates for E ( K t ) and Var ( K t ), especially when θ ≠ 1. Perhaps the hypotheses of Theorem 4 could be weakened.

In the case of random permutations, there is a Poisson approximation of K n . The total variation distance between the law L ( K n ) of K n and the Poisson ( E ( K n ) ) distribution is of order d TV ( L ( K n ) , Poisson ( E ( K n ) ) ) : = 1 2 ∑ k = 1 n P ( K n = k ) − exp − E ( K n ) E ( K n ) k k ! ≍ 1 log n ; see [2]. By considering the process of cycle counts ( C 1 ( n ) , C 2 ( n ) , … , C n ( n ) ), where C i ( n ) is the number of cycles of size i, we may write K n = ∑ i = 1 n C i ( n ). Moreover, [7] shows that B n ( · ) → d B ( · ), where B n ( t ) : = ∑ i = 1 ⌊ n t ⌋ C i ( n ) − t log n log n , 0 ≤ t ≤ 1 , and B ( t ) is standard Brownian motion. If suitable approximations could be made to the process of cycle counts for multiset permutations, then similar progress might be made for the results obtained in this paper when θ = 1.