Chinese restaurant process and random permutations. The Hoppe model from Problem 6.5 can be slightly refined by taking the family structure of the clans into consideration.

The balls in Hoppe’s urn are labelled in the order in which they arrived in the urn. The state of the urn after the nth draw is written as a permutation in cycle notation as in Figure 6.8: For a new colour at time n we add .n/ as a new cycle and otherwise the label of the ball is written to the left of the label of the ‘mother ball’ in its respective cycle. Let Zn be the permutation created after n draws. The sequence .Zn/n0 was introduced by D. J. Aldous (1984) as the

‘Chinese restaurant process’; the labels are interpreted as the guests of a Chinese restaurant (in the order of their appearance), and each cycle as the seating order at a (round) table. Show the following:

(a) .Zn/n0 is a Markov chain. For which E and …?

(b) For each permutation  of ¹1; : : : ; nº with k cycles, P.Zn D / D #k=#.n/, where #.n/

is as in Problem 6.5a. So, Zn is uniformly distributed when # D 1.

(c) Deduce that the number of all permutations of ¹1; : : : ; nº that have, for each 1  i  n, xi cycles of length i is equal to nŠ=

Qn iD1.ixi xi Š/.