Abstract Abstract. We consider refined versions of Markov chains related to juggling introduced by Warrington. We further generalize the construction to juggling with arbitrary heights as well as infinitely many balls, which are expressed more succinctly in terms of Markov chains on integer partitions. In all cases, we give explicit product formulas for the stationary probabilities and closedform expressions for the normalization factor. We also refine and generalize enriched Markov chains on set partitions. Lastly, we prove that in one case, the stationary distribution is attained in finite time. Introduction Although juggling as a human endeavour has been around since time immemorial, it is fairly recently that mathematicians have taken an active interest in exploring the field. Combinatorialists became interested in juggling towards the end of the last century after an article in the Amer. Math. Monthly by Buhler, Eisenbud, Graham and Wright [BEGW94] , where they enumerate what they call juggling sequences and relate it to other known combinatorial structures. Since then, their results have been q-ified [ER96] and further refined in various ways [Sta97, Sta02, CG07, CG08, BG10] . Other connections between juggling and mathematics appear for instance in algebraic geometry [DM, KLS13] . A mathematical history of juggling is given in the fascinating book by Polster [Pol03] . Introduction Probabilists, on the other hand, are newer to this game, possibly because no one is able to perform totally random juggling. Coincidentally, it was another popular article in the Amer. Math. Monthly by Warrington [War05] on natural stochastic models inspired by juggling that got the attention of a few other members of the community. Exact combinatorial formulas for the stationary distribution of these models were found, and proved by a beautiful argument involving an auxiliary model defined on a larger state space whose elements may be viewed as set partitions, for which the stationary distribution is the uniform distribution. Introduction The simplest model considered by Warrington, where the number of balls is conserved, has been generalized by Leskelä and Varpanen as the so-called Juggler's Exclusion Process (JEP), where the balls can be thrown arbitrarily high so that the state space is infinite [LV12] . These authors showed that the JEP converges to a (unique) stationary distribution under very mild assumptions, could obtain an exact expression for this stationary distribution in the particular case of a "memoryless" (geometric) height distribution, and noted an intriguing phenomenon of "ultrafast convergence" in this case. More recently, a q-deformation of Warrington's original finite model was considered by Engström, Leskelä and Varpanen [ELV13] , who also obtained exact expressions for the stationary distribution via an enriched chain formulated in terms of rook placements (in bijection with some set partitions). Introduction In this paper, we provide multivariate deformations of all the models introduced in [War05] , namely juggling, add-drop juggling and annihilation juggling. Furthermore, in the case of the juggling model with a conserved number of balls, we investigate the limiting case where balls can be thrown arbitrarily high, which corresponds to the so-called infinite juggling model suggested by Warrington. We also consider the limiting case where the number of balls tends to infinity. In all these cases, we obtain an exact formula for the stationary distribution (in particular, in the case where balls can be thrown arbitrarily high, we find an "exactly solvable" instance of the general JEP of [LV12] with countably many parameters). Our proofs were obtained using two approaches. The direct approach involves guessing the general formulas (for instance by a computation for small system sizes) and then proving the results in a straightforward manner by considering the juggling process itself. The other approach is more combinatorial, and consists in introducing an enriched chain whose stationary distribution is simpler, and which yields the original chain by a projection or "lumping" procedure. Introduction The rest of the paper is organized as follows. In Section 2, we concentrate on the simplest version of our model, which we call the Multivariate Juggling Markov Chain (MJMC). The model is defined in Section 2.1, and we also discuss the uniqueness of the stationary distribution (a technicality deemed obvious in [War05] ). The expression for the stationary distribution of the Markov chain is stated in Section 2.2. For pedagogical purposes, we decide to provide two independent proofs by the direct and the combinatorial approaches. The direct proof is given in Section 2.3, via an interesting reformulation of the MJMC in terms of integer partitions restricted to lie within a rectangle. The combinatorial proof comes in Section 2.4 and involves set partitions with a prescribed number of elements and blocks. We then turn to extended models. Extensions to infinite state spaces are considered in Section 3: the case of a finite number of balls but unbounded heights (UMJMC) in discussed in Section 3.1, while the case of an infinite number of balls (IMJMC) is considered in Section 3.2. In both cases, we find the stationary measure by the direct approach. Extensions to a fluctuating number of balls (but with a finite state space) are considered in Section 4: we provide the multivariate extension of the add-drop and the annihilation models introduced in [War05] , in the respective Sections 4.1 and 4.2. These models have the same transition graph, only the transitions probabilities differ. In both cases we find the stationary distribution by the combinatorial approach. In the case of the annihilation model (precisely defined in Section 4.2.1), we further observe the interesting property that the stationary distribution is attained in finite time (Section 4.2.2), and we then discuss the remarkable algebraic structure of the model (Section 4.2.3). We end with some remarks and questions for future study in Section 5. Introduction The claims of this paper can be verified by downloading the Maple TM program RandomJuggling either from the arXiv source or the first author's (A.A.) homepage. Introduction 2. The finite Multiparameter Juggling Markov Chain 2.1. Definition. In this section, we introduce our juggling model in the simplest setting, i.e. a Markov chain on a finite state space. We start by explaining the model in colloquial terms, and refer to [War05] for further motivation. Consider a person, called Magnus with no loss of generality, who is juggling with a fixed finite number of balls. Time is discretized in, say, steps of one second and we assume that, at each second, Magnus is able to catch at most one ball, and then throws it back immediately. Besides this limitation Magnus juggles perfectly, i.e. in such a way that the ball will always return to him after some time (an imperfect juggler could drop a ball or throw it in a wrong direction, for instance). Magnus controls the velocity at which he sends the ball, which determines how long it will take for the ball to return to him. We suppose for now that the launch velocity is bounded or, in other words, that the number of seconds before the ball returns to Magnus is bounded by an integer h. Introduction Ignoring further spatial constraints, a simplified description of the state of the balls at a given time consists in associating to each ball the (integer) number of seconds remaining before it is caught by Magnus. This is now known as the siteswap notation. Of course, to be able to juggle for an indefinite amount of time, Magnus must choose the successive launch velocities in such a way that no two balls arrive to him at the same time. Thus the numbers associated to different balls shall be distinct and, treating the balls as indistinguishable, there are h possible ball states. It is convenient to think of a state as a configuration of non overlapping particles on a one-dimensional lattice with h sites, where the i-th site (read from the left) is occupied if and only if a ball is scheduled to arrive i seconds in the future. However, beware that sites do no correspond to actual spatial positions, but to the "remaining flight times" of the balls. We denote by k = h − the number of empty (unoccupied) sites. Introduction In this language, the time evolution of a state is easy to describe: at each time step, all particles are moved one site to the left. If there is no particle on the first site (i.e. Magnus catches no ball), then nothing else has to be done. Otherwise the particle on the first site, which would exit the lattice if moved to the left, is instead taken away and reinserted at one of the k + 1 available (empty) sites on the lattice (determined by the launch velocity chosen by Magnus). This defines the transition graph of our model, illustrated on Figure 1 for h = 4 and = k = 2 (ignoring edge labels for now). Introduction We now assume that Magnus juggles at random: each reinsertion is made randomly at one of the k + 1 available sites. In our model, we assume that the reinsertion is made at the i-th available site (read from the left) with probability x i−1 , independently of the past, so that our model is a Markov chain. Here, x 0 , . . . , x k are fixed nonnegative real numbers such that x 0 + · · · + x k = 1. This defines the Multivariate Juggling Markov Chain (MJMC), which generalizes the model considered in [War05] , obtained by taking x 0 = · · · = x k = 1/(k + 1), but is a particular case of the general "Juggling Exclusion Process" defined in [LV12] : beyond the extension to infinitely many empty sites which we will discuss in the next section, the main difference is that, in the model of Leskelä and Varpanen, the x i are allowed to depend on the current state. We now provide a more formal mathematical definition of the MJMC. Following Warrington's notation, let St h denote the set of words of length h on the alphabet {•, •}, and let St h,k ⊂ St h be the subset of words containing exactly k occurrences of •. For A ∈ St h,k+1 and i ∈ {0, . . . , k}, we let T i (A) ∈ St h,k be the word obtained by replacing the (i + 1)-th occurrence of • in A by •. Introduction Definition 2.1. Given h, k nonnegative integers such that h ≥ k, and x 0 , . . . , x k nonnegative real numbers such that x 0 + · · · + x k = 1, the Multivariate Juggling Markov Chain is the Markov chain on the state space St h,k for which the transition probability from A = a 1 a 2 · · · a h to B reads (2.1) Introduction Example 2.2. Figure 1 illustrates the Markov chain in the case h = 4, k = 2, and the transition matrix in the basis ( Introduction 2 ) is a left eigenvector with eigenvalue 1. Introduction Remark 2.3. To compare our model with that of [LV12] , note that St h,k may be canonically identified with the set of subsets of {1, . . . , h} with = h − k elements (corresponding to the positions of the occupied sites). For two such subsets S and S , the transition probability from S to S reads (2.3) Introduction where S − 1 is the set whose entries are those of S with 1 subtracted. Introduction Proposition 2.4. If x 0 > 0, then the MJMC has a unique closed communicating class, whose all states are aperiodic. If furthermore x k > 0, then the MJMC is irreducible. Introduction Proof. Assume that x 0 > 0 and let E = • • k be the "lowest" state. It is clear that, starting from any initial state, we may obtain E by a sequence of transitions of probabilities x 0 or 1, simply by doing any reinsertion at the first available site. Thus there is a unique closed communicating class, containing E. Since E jumps to itself with probability x 0 , all recurrent states are aperiodic. Introduction Assume now that x k > 0: to prove irreducibility we simply need to show that any state A = a 1 . . . a h ∈ St h,k may be obtained from E. For i ∈ {0, . . . , h}, we let Introduction . . a i where n i is the number of occurrences of • in a 1 . . . a i , so that A i ∈ St h,k , with A 0 = E and A h = A. For i < h, we have Introduction Thus A may be obtained from E by a sequence of possible transitions. Introduction Remark 2.5. When x 0 = 0, the chain may have several closed communicating classes. For example, see Figure 1 and let x 0 = x 1 = 0. Stationary distribution. From now on we assume x 0 > 0. By Proposition 2.4, the MJMC admits a unique stationary probability distribution. Our main result is an explicit form for it, given as follows. Stationary distribution. Theorem 2.6. The stationary distribution π of the MJMC is given by Stationary distribution. where B = b 1 · · · b h ∈ St h,k and E i (B) = #{j < i|b j = •}, and where Z h,k ≡ Z h,k (x 0 , . . . , x k ) is determined by the condition that π be a probability distribution. Stationary distribution. We will provide two proofs of this theorem, as they both lead to interesting generalizations to be studied later in Sections 3 and 4. The first proof, presented in Section 2.3, is a rather direct computational check that (2.5) indeed defines a stationary measure of the MJMC (but we find it clearer to first reformulate the chain in terms of integer partitions). The second proof, presented in Section 2.4, is more combinatorial and generalizes the approach of [War05] : it consists in defining an "enriched" Markov chain on a larger state space, where the stationary probability of a given state will be given by a monomial in x 0 , . . . , x k . The MJMC is then recovered by lumping together states of the enriched chain, which will explain the form of (2.5). Stationary distribution. Before proceeding to the proofs, let us discuss a few interesting particular cases, and properties of the normalization factor Z h,k . Stationary distribution. Example 2.7. If the reinsertion is made uniformly among all k + 1 available sites, i.e. if we take x 0 = . . . = x k = 1/(k + 1), then we recover [War05, Theorem 1] from Theorem 2.6 (see Corollary 2.12 below for a short rederivation of the normalization factor). Stationary distribution. Example 2.8. If the reinsertion site is chosen according to a geometric distribution of parameter q conditionned to be smaller than or equal to k + 1, i.e. if we take Stationary distribution. . , k, then we recover the so-called bounded geometric JEP considered in [ELV13] . It is simple exercise to check that we recover [ELV13, Theorem 2.1] from Theorem 2.6 (see also Corollary 2.12 below for the normalization factor). Stationary distribution. Example 2.9. A slight variant of the previous example consists in picking the reinsertion site according to a "truncated" geometric distribution of pararameter q, i.e. taking x i = (1 − q)q i for i = 0, . . . , k − 1 and x k = q k . In that case, the stationary probability of B ∈ St h,k reads (2.6) Stationary distribution. (see again Corollary 2.12 below for the normalization factor). Stationary distribution. Regarding Z h,k , observe first that the expression Stationary distribution. allows to define it for any x 0 , . . . , x k (not necessarily positive or subject to the condition x 0 + · · · + x k = 1) and h, k ≥ 0. It vanishes for h < k and is otherwise a homogeneous polynomial of degree = h − k. Stationary distribution. Proposition 2.10. We have Stationary distribution. with h the complete homogeneous symmetric polynomial of degree = h − k, and with the shorthand notation Stationary distribution. Again, there are several ways to establish this result. Perhaps the most combinatorial explanation comes from the integer partition approach of Section 2.3, see Remark 2.17 below. But, starting from the definition (2.7), we may easily check (2.8) by induction, using the following: Stationary distribution. Proof. Obtained immediately by distinguishing whether B ∈ St h,k starts with a • or a • (for h < k all terms vanish as wanted). Stationary distribution. We readily verify by induction and homogeneity some explicit specializations: Stationary distribution. Corollary 2.12. We have For completeness, we mention another recursion relation for Z h,k of a different nature, as we remove x k instead of x 0 . Proposition 2.13. For h, k ≥ 0, we have Stationary distribution. where, by convention, Stationary distribution. with y m = k−1 j=m x j , and use the identity (easily verified e.g. by induction on + k) 2.3. Reformulation of the MJMC in terms of integer partitions. There is a natural bijection between St h,k and Par k,h−k , where Par k, is the set of integer partitions whose Young diagram fits within a k × rectangle. In other words, an element of Par k, can be viewed as a nonincreasing sequence of nonnegative integers smaller than k. The bijection is given explicitly as follows: given a state in St h,k , we denote by s 1 < s 2 < · · · < s −1 < s the positions of •, then the corresponding integer partition is (s − , s −1 − ( − 1), . . . , s 2 − 2, s 1 − 1). Alternatively, an equivalent graphical construction is displayed on Figure 2 . Upon identifying St h,k and Par k,h−k via this bijection, we may reformulate the MJMC as follows. Stationary distribution. Proposition 2.14. For λ = (λ 1 , λ 2 , . . . , λ ) and µ two partitions in Par k, , the transition probability from λ to µ reads Stationary distribution. The proof of this proposition is left to the reader. The interest of the reformulation in terms of integer partitions is that the stationary distribution of the MJMC takes a particularly simple form: indeed, Theorem 2.6 is equivalent to Theorem 2.15. The stationary distribution π of the MJMC is given by Stationary distribution. where λ = (λ 1 , . . . , λ ) is an element of Par k, and where the y m are as in (2.9). Stationary distribution. Proof. Let w(λ) = i=1 y λi be the unnormalized weight of λ ∈ Par k, . We simply check that Stationary distribution. by considering the possible predecessors of λ: Stationary distribution. • If λ 1 = k then the only possible predecessor for λ is µ = (λ 2 , λ 3 , . . . , λ , 0), so that w(µ) = i=2 y λi (because y 0 = 1) and P µ,λ = x k = y k . Thus we have w(λ) = P µ,λ w(µ) as wanted. Stationary distribution. • We now assume that λ 1 < k. Let µ be a predecessor of λ, µ can -either be of the form µ = (λ 1 + 1, λ 2 + 1, . . . , λ + 1), in which case we have w(µ) = i=1 y λi+1 = i=1 (y λi − x λi ) and P µ,λ = 1; -or be of the form µ = (λ 1 + 1, λ 2 + 1, . . . , λ j−1 + 1, λ j+1 , λ i+2 . . . , λ , 0) Stationary distribution. for any 1 ≤ j ≤ , in which case we have w(µ) = Stationary distribution. where, to go from the first line to the second, we write x λj = y λj −(y λj −x λj ) so that the sum on the right hand side becomes telescopic. Stationary distribution. Example 2.16. We may now revisit Examples 2.7, 2.8 and 2.9 in the language of integer partitions. The corresponding stationary probabilities of λ ∈ Par k, read Stationary distribution. Remark 2.17. one can immediately recover Proposition 2.10 from Theorem 2.15, as Stationary distribution. where the m i correspond to the part multiplicities. A slight extension of this reasoning consists in restricting the sum to partitions λ such that, say, λ j = n (with 1 ≤ j ≤ and 0 ≤ n ≤ k), so as to obtain the probability that the j-th part in the stationary distribution π is n: Stationary distribution. More generally, the joint distribution for a fixed number of parts reads Stationary distribution. 2.4. Enriched Markov chain on set partitions. We now provide another, more combinatorial, proof of Theorem 2.6 whose rough idea goes as follows: consider the stationary probability (2.5) and expand the product in the right hand side as a sum of monomials in the x i . We will interpret each of these monomials as the stationary probability of an "enriched" state belonging to the larger state space of another Markov chain. The MJMC will then be obtained as a projection of this enriched chain (see e.g. [LPW09, Section 2.3.1] for a definition of this notion). Stationary distribution. 2.4.1. Definitions and basic properties. Our construction is a generalization of that of Warrington's. Rather than working with "landing/throwing-states", we prefer to work directly in the language of set partitions, see [War05, Lemma 2] . Recalling that h stands for the total number of sites and k for the number of empty sites in the particle picture of the MJMC, let us introduce the shorthand notations (2.26) Stationary distribution. An enriched state will then be a partition of the set {1, 2, . . . , H} into K subsets or blocks. We denote by S(H, K) the set of enriched states, and recall that Stationary distribution. | is a Stirling number of the second kind. To each enriched state σ, we associate a word ψ(σ) = a 1 . . . a h by setting, for all i between 1 and h, a i = • if i is a block maximum of σ (i.e. the largest element of its block in σ), and a i = • otherwise. Observe that ψ is a surjection from S(H, K) onto St h,k . Stationary distribution. We now define the enriched Markov chain on S(H, K), which requires some notations. For an enriched state σ, we denote by σ ↓ the partition of the set {1, . . . , h} obtained by removing 1 from σ (i.e. removing 1 from its block in σ, and removing this block from σ if it becomes empty), and shifting all the remaining elements of all blocks down by 1. Note that σ → σ ↓ is a mapping from S(H, K) to S(h, k)∪S(h, K) (which is surjective). For τ ∈ S(h, K) and i ∈ {0, . . . , k}, we denote by I i (τ ) the set partition of {1, . . . , H} obtained by inserting H into the (i + 1)-th block of τ , where the blocks are numbered by ascending order of their maxima (i.e. the first block has the smallest maximum among all blocks, etc. -this differs from the so-called standard form which consists in ordering blocks by ascending order of their minima). Note that I i (τ ) ∈ S(H, K) and that the mapping (τ, i) Stationary distribution. Definition 2.18. The enriched chain is the Markov chain on S(H, K) for which the transition probability from σ to τ is given by Stationary distribution. The condition x 0 + · · · + x k = 1 and the above remarks ensure thatP is indeed a (right) stochastic matrix. Stationary distribution. Example 2.19. For H = 8 and K = 3: Stationary distribution. • the enriched state 1 | 3 5 6 | 2 4 7 8 jumps with probability 1 to 2 4 5 | 1 3 6 7 | 8, Stationary distribution. • the enriched state σ = 3 5 | 2 6 7 | 1 4 8 reaches the intermediate state σ ↓ = 2 4 | 1 5 6 | 3 7 and jumps with probability: -x 0 to 1 5 6 | 3 7 | 2 4 8, -x 1 to 2 4 | 3 7 | 1 5 6 8, -x 2 to 2 4 | 1 5 6 | 3 7 8. (We use a hopefully self-explanatory compact notation for set partitions, with blocks written in ascending order of their maxima.) Stationary distribution. Example 2.20. For H = 4 and K = 2, the transition graph of the enriched chain is illustrated on Fig. 3 . Stationary distribution. The existence and uniqueness of the stationary distribution of the enriched chain results from: Proposition 2.21. For x 0 > 0, the enriched chain has a unique closed communicating class, whose all states are aperiodic. The chain is irreducible if and only if all x i s are nonzero. Stationary distribution. Proof. The first assertion is proved in the same way as that of Proposition 2.4, the "lowest" state being now the set partition (2.28)Ẽ = {{1, . . . , H} ∩ (j + KN)} j=1,...,K (precisely, starting from any initial state, we eventually obtainẼ by applying only transitions of probabilities x 0 and 1). Stationary distribution. For the second assertion, suppose that x i > 0 for all i: we want to prove that the transition graph is strongly connected. We first replace the transitions of probability 1 by K transitions of probabilities x 0 , . . . , x k , so that each state has K outgoing transitions, counting transitions to itself. It is then not difficult to check from the definition of the enriched chain that each state also has K incoming transitions. It follows that for any set of states, the number of incoming and outgoing transitions are the same, thus all communicating classes are closed. As there is a unique closed communicating class, irreducibility follows. Conversely, if x i = 0 for some i, then clearly some set partitions, e.g. Stationary distribution. 2.4.2. Projection, stationary distribution and second proof of Theorem 2.6. From the surjection ψ introduced above, we define a rectangular matrix Ψ with rows indexed by elements of S(H, K) and columns indexed by elements of St h,k in the obvious manner (namely a coefficient of Ψ is 1 if its column index is the image by ψ of its row index, and 0 otherwise). for H = 4 and K = 2 (h = 3 and k = 1). Enriched states (set partitions) are represented via "arches". Red, green and grey arrows represent transitions of respective probability x 0 , x 1 and 1. Arches covering 1 or 2 blocks are represented in green or red respectively. The reader may easily check that attaching a weight x 0 (resp. x 1 ) to each red (resp. green) arch yields the stationary measure of the enriched chain. Enriched states in a same column map to the same MJMC state (displayed below) via ψ. Stationary distribution. For clarity, the proofs of all lemmas in this section are postponed to Section 2.4.3. Note that, if we view the preimages by ψ of elements of St h,k as equivalences classes for an equivalence relation on S(H, K), then (2.29) shows that the MJMC is the projection of the enriched chain [LPW09, Lemma 2.5]. Noting that the sum of each row of Ψ is 1, we immediately deduce: Stationary distribution. Corollary 2.23. We have Stationary distribution. whereπ is the stationary probability distribution of the enriched chain (viewed as a row vector), and π is that of the MJMC. Stationary distribution. Our route to Theorem 2.6 is now clear. We want to find an explicit expression forπ, then computeπΨ. We first need to introduce some definitions and notations. Stationary distribution. Definition 2.24. Let σ be an enriched state and s, t two integers such that 1 ≤ s < t ≤ H. We say that the pair (s, t) is an arch of σ if s and t belong to the same block β of σ, while no integer strictly between s and t belongs to β. Stationary distribution. Note that σ ∈ S(H, K) has exactly = H − K arches. Notation 2.25. For 1 ≤ s < t ≤ H, we denote by C σ (s, t) the number of blocks containing at least one element in {s, s + 1, . . . , t − 1, t} (when (s, t) is an arch, then we say that these blocks are those covered by (s, t)). Stationary distribution. We are now ready to express the stationary distribution of the enriched chain, see again Figure 3 for an illustration in the case H = 4, K = 2. Stationary distribution. Lemma 2.26. For σ ∈ S(H, K), the monomial Stationary distribution. defines an unnormalized stationary measure of the enriched chain. Stationary distribution. Remark 2.27. It is here natural to introduce the notation z i = x K−i , i = 1, . . . , K, so that z i is simply the weight per arch covering i blocks. In the juggling language, z i is the probability of doing an insertion at the i-th available site starting from the right. This notation will be useful for the "add-drop" and "annihilation" generalizations of the MJMC, see Sections 4.1 and 4.2. However, the x i notation is more convenient to study the k → ∞ limit, as we do in Sections 3.1 and 3.2. Stationary distribution. Noting that, forẼ as in (2.28), we havew(Ẽ) = x 0 , we find that Stationary distribution. is positive whenever x 0 > 0, so thatπ =w/Z h,k is the stationary probability distribution of the enriched chain. For B ∈ St h,k , we set (2.33) Stationary distribution. that is w =wΨ. This implies that π = w/Z h,k is the stationary probability distribution of the MJMC by Corollary 2.23. Theorem 2.6 then follows immediately from: Stationary distribution. where Stationary distribution. Example 2.29. Returning again to the case H = 4, K = 2 (i.e. h = 3, k = 1) illustrated on Figure 3 , we find Stationary distribution. Remark 2.30. The unnormalized weightsw(σ) are well-defined for arbitrary x 0 , . . . , x k (not necessarily positive or subject to the condition x 0 + · · · + x k = 1). For x 0 = · · · = x k = 1, we recover Warrington's combinatorial proof of the identity (2.11). For Stationary distribution. The identity (2.12) shows that N (σ) is a so-called Mahonian statistic on set partitions, which seems different from the inversion number and the major index [Sag91] . Stationary distribution. (since inserting H into the (i + 1)-th block of σ ↓ transforms its maximum into a non-maximum, which means replacing the (i + 1)-th occurrence of . a 1 = •) , then, by the definition of the transition matrices and (2.37), (2.39) Stationary distribution. Otherwise, if {1} / ∈ σ (i.e. a 1 = •), we may write Stationary distribution. where we use (2.38) to go from the first to the second line. In both cases, we have the wanted relation. Stationary distribution. Proof of Lemma 2.26: We need to show that Stationary distribution. which is done by considering the possible predecessors of σ in the enriched chain. If {H} ∈ σ then σ has a unique precedessor τ such that σ = τ ↓ ∪ {H}. The arches of σ and τ are clearly in one-to-one correspondence, and their weights are unchanged, thusw(σ) =w(τ ) as wanted. Otherwise, there exists a unique pair (ρ, i) ∈ S(h, K) × {0, . . . , k} such that σ = I i (ρ) and it is easily seen thatw(σ) = x iw (ρ) (since inserting H in the (i + 1)-th block of ρ amounts to creating an arch covering K − i blocks, the other arch weights being unaffected). The predecessors of σ are the τ such that τ ↓ = ρ and {1} / ∈ τ , and we haveP τ,σ = x i regardless of τ . There are exactly K predecessors, whose weights are x jw (ρ) with j ∈ {0, . . . , k} (indeed all these predecessors are obtained by shifting all elements of all blocks of ρ up by one, which preserves the arch weights, then inserting 1 into one of the K blocks, which creates a new arch covering an arbitrary number of blocks between 1 and K). From the condition x 0 + . . . + x k = 1 we conclude that (2.41) holds as wanted. Stationary distribution. Proof of Lemma 2.28: We proceed by induction on = h − k = H − K. For = 0, the statement is true since B = • h has only one preimage, namely the set partition consisting of singletons {{1}, {2}, . . . , {H}} which has no arch, thus has a weight 1 consistent with (2.34). Let us now assume that > 0 and consider the smallest i such that Stationary distribution. be the word obtained by replacing the i-th letter of B by Stationary distribution. : it is easily seen from the definition of ψ that, for all j < i, the singleton {j} is necessarily a block of τ , but the block β containing i contains at least another (larger) element, thus τ has an arch of the form (i, i ) with weight w i,i = x n for some n ≥ E i (B). Stationary distribution. Splitting β in two blocks {i} and β \ {i}, we obtain a set partition τ ∈ S(H, K + 1), and a moment's thought shows that τ → (τ , n) is a bijection between ψ −1 (B) and ψ −1 (B ) × {E i (B), . . . , k} such thatw(τ ) = x nw (τ ). By induction hypothesis we have (2.42) Stationary distribution. and, multiplying this relation by x n and summing over n, the desired relation (2.34) follows. Extensions to infinite state spaces In this section, we discuss extensions of the Multivariate Juggling Markov Chain to an infinite setting. More precisely, we first let the number of available sites k tend to infinity, keeping the number of balls fixed. This is the Unbounded MJMC discussed in Section 3.1. Further, we consider the case where the number of balls tends to infinity (with k infinite or not), which corresponds to the Infinite MJMC discussed in Section 3.2. Extensions to infinite state spaces 3.1. Unbounded heights. As suggested in the conclusion of [War05] , a first natural extension is to allow Magnus to throw balls arbitrarily high, so that the ball flight times are unbounded. This corresponds to taking the limit h → ∞ of the MJMC, keeping the number of balls fixed. In the particle picture, the sites are now labelled by the set of positive integers, and exactly sites are occupied by a particle. The time evolution is essentially unchanged: at each time step, all particles are moved one site to the left, and if there was a particle on the first site, it is reinserted at an available site anywhere on the lattice. We keep the MJMC prescription of choosing the i-th available site with probability x i−1 , but since there are now infinitely many available sites, we have an infinite sequence (x i ) i≥0 of nonnegative real numbers such that Again, we might identify St ( ) with the set of -element subsets of N (corresponding to the positions of the occupied sites). For two such subsets S and S , the UMJMC transition probability from S to S is still given by (2.3). Our model is thus a particular case of the general model considered in [LV12] . The following proposition is an immediate extension of Proposition 2.4. Proposition 3.2. The UMJMC is irreducible and aperiodic whenever x 0 and infinitely many x i are nonzero. Extensions to infinite state spaces Note that, if k = sup{i : x i > 0} is finite, then no insertion is ever made at a position larger than k. Thus, the states with particles at positions larger than k are transient, and upon removing them we recover the finite MJMC on St +k,k . From now on, we assume that x 0 > 0 and sup{i : x i > 0} = +∞. We are again interested in the stationary distribution, but the fact that the state space is now countably infinite requires a bit of care. Still, we might extend Theorem 2.6 in the following form. Extensions to infinite state spaces Theorem 3.3. The unique invariant measure (up to constant of proportionality) of the UMJMC is given by Extensions to infinite state spaces where Extensions to infinite state spaces We prove this theorem by a straightforward extension of the discussion of Section 2.3 (it seems more tedious to extend that of Section 2.4). In the integer partition language, the extension simply consists in lifting the bound on part sizes. We denote by Par ∞, the set of integer partitions with at most parts and unbounded part sizes (which we can view as nonincreasing sequences of nonnegative integers). This set is naturally identified with St ( ) : given a state in St ( ) , we denote by s 1 < s 2 < . . . < s −1 < s the positions of •, so that the corresponding integer partition is (s − , s −1 − ( − 1), . . . , s 2 − 2, s 1 − 1). We let the reader verify that, in the integer partition language, the UMJMC transitions are still given by (2.18). Theorem 3.3 may then be reformulated as follows. Any predecessor µ of λ is either: -of the form µ = (λ 1 + 1, λ 2 + 1, . . . , λ + 1) in which case we have w(µ) = i=1 y λi+1 = i=1 (y λi − x λi ) and P µ,λ = 1 ; -of the form µ = (λ 1 + 1, λ 2 + 1, . . . , λ j−1 + 1, λ j+1 , λ j+2 . . . , λ , 0) for some j ∈ {1, . . . , } in which case we have w(µ) = j−1 i=1 (y λi − x λi ) i=j+1 y λi and P µ,λ = x λj . The verification of (3.4) is then done exactly as in (2.21). Extensions to infinite state spaces We have exhibited an invariant measure of the UMJMC which is clearly σ-finite. We might wonder whether it is actually finite, so that it may be normalized into a probability distribution. Proof. Let Z ( ) ∈ [0, ∞] be the total mass of w. Observe that (3.7) Extensions to infinite state spaces thus the first assertion is obviously true for = 1. It remains true for general as we have the inequalities Extensions to infinite state spaces since Par ∞, contains the set of partitions with at most one nonzero part (which has mass Z (1) by (3.3) and the fact that y 0 = 1), but may be viewed as a subset of N , for which we have λ∈N w(λ) = Z Extensions to infinite state spaces by (3.3). The identity (3.6) is obtained by letting k → ∞ in (2.23), since (Par k, ) k≥0 forms an increasing family of sets with union Par ∞, so that Z k+ ,k Z ( ) . Note that, when y m < ∞, the mapping f → f (y 0 , y 1 , y 2 , . . .) forms a well-defined real specialization of the ring of symmetric functions, as seen for instance by noting that the power sums are specialized to finite real numbers. By standard results from the theory of Markov chains, see e.g. [LG06, Chapter 13] or [LPW09, Chapter 21], we deduce: Corollary 3.6. The UMJMC is positive recurrent if and only if (3.5) holds. In that case, there is a unique stationary probability distribution, and the chain started from any initial state converges to it in total variation as time tends to infinity. By standard results from the theory of Markov chains, see e.g. [LG06, Chapter 13] or [LPW09, Chapter 21], we deduce: Example 3.7. Fix q ∈ (0, 1) and pick x i = (1 − q)q i . We recover the "JEP with memoryless height distribution" with parameter q considered in [LV12] . Clearly (3.5) holds and we recover from Theorem 3.3 Leskelä-Varpanen's expression for the stationary probability distribution. Interestingly, in the integer partition language, we find that w(λ) = q |λ| for λ ∈ Par ∞, , where |λ| stands for the size (sum of all parts) of λ. By standard results from the theory of Markov chains, see e.g. [LG06, Chapter 13] or [LPW09, Chapter 21], we deduce: Remark 3.8. It is interesting to note that (3.5) is a necessary and sufficient condition for the UMJMC to be uniformly integrable in the sense of [LV12] . When (3.5) does not hold, the chain may either be null recurrent or transient. For = 1, the state with the first site occupied is clearly recurrent, thus the chain is null recurrent. Figuring out the situation for > 1 is an intriguing question. By somewhat heuristic arguments inspired by Polyá's theorem on recurrence of random walks, we expect that, for a sequence x i decaying asymptotically as i −1−α with α ∈ (0, 1) (so that ix i = ∞), the IMJMC is null recurrent if (1−α) ≤ 1 and transient if (1−α) > 1. A formal proof of this statement is beyond the scope of this paper. By standard results from the theory of Markov chains, see e.g. [LG06, Chapter 13] or [LPW09, Chapter 21], we deduce: 3.2. Infinitely many balls. We now consider another limit in which Magnus juggles with infinitely many balls ( → ∞). Let us first heuristically discuss this limit in the particle picture: since the particles tend to accumulate on the left side of the lattice (i.e. balls tend to have low remaining flight times), we expect that, as becomes large, all sites at a finite distance from the first site will be occupied with high probability (in particular, Magnus receives a ball at every time step), and the first available site will then be typically at a position of order . It is convenient to relabel the sites by arbitrary (non necessarily positive) integers, so that the leftmost site has label − , and the lowest state corresponds to having particles on sites − , − + 1, . . . , −1. In the limit → ∞, the leftmost site is sent to −∞, and the lowest state corresponds to having all negative sites filled and all nonnegative sites empty. A general state is obtain by moving finitely many particles from occupied to empty sites, in other words it is a bi-infinite word B = (b i ) i∈Z ∈ {•, •} Z such that (3.9) {i ≥ 0 : By standard results from the theory of Markov chains, see e.g. [LG06, Chapter 13] or [LPW09, Chapter 21], we deduce: (such a word is sometimes called a "Maya diagram"). The time evolution is now easy to describe: at each time step, all particles are moved one site to the left and one particle is reinserted at an available site (so that the condition (3.9) is preserved). Again, we keep the MJMC prescription of picking the i-th available site from the left with probability x i−1 (this is well-defined since the set of available positions is bounded from below). Rather than writing down the transitions formally, we prefer to work directly in the language of integer partitions. It is well-known that bi-infinite words subject to (3.9) are in one-to-one correspondence with arbitrary integer partitions (i.e. nonincreasing sequences of integers that vanish eventually). We denote by Par the set of integer partitions and, for λ = (λ j ) j≥1 ∈ Par and i ≥ 0, we set (3.10) By standard results from the theory of Markov chains, see e.g. [LG06, Chapter 13] or [LPW09, Chapter 21], we deduce: with j the smallest index such that λ j ≤ i. This is the Par equivalent of the above time evolution with insertion at the (i + 1)-th available site. By standard results from the theory of Markov chains, see e.g. [LG06, Chapter 13] or [LPW09, Chapter 21], we deduce: Definition 3.9. Given a sequence (x i ) i≥0 of nonnegative real numbers such that ∞ i=0 x i = 1, the Infinite Multivariate Juggling Markov Chain (IMJMC) is the Markov chain on the state space Par for which the transition probability from λ to µ reads (3.11) By standard results from the theory of Markov chains, see e.g. [LG06, Chapter 13] or [LPW09, Chapter 21], we deduce: The existence and uniqueness (up to normalization) of an invariant measure of the IMJMC is ensured by the following: Proposition 3.10. If x 0 > 0, then the IMJMC has a unique closed communicating class, whose all states are aperiodic. They are precisely the integer partitions whose parts are smaller than or equal to sup{i : x i > 0}. In particular, if infinitely many x i are nonzero, then the IMJMC is irreducible. By standard results from the theory of Markov chains, see e.g. [LG06, Chapter 13] or [LPW09, Chapter 21], we deduce: Proof. It is easily seen that, applying repeatedly the transition x 0 , we end up with the empty partition starting from any initial state (which is a fixed point). This proves the first statement. For the second statement, let us prove that, for any k such that x k > 0, we may obtain any partition µ with µ 1 ≤ k from the empty partition using only the transitions x 0 and x k . We proceed by double induction on the number of parts p of µ and on k − µ 1 . If p = 0, then µ is already the empty partition. Otherwise, if k − µ 1 = 0, then µ is obtained from (µ 2 , µ 3 , . . .) (which has one less part) by the transition x k . Finally, if k − µ 1 > 0, then µ is obtained from µ = (µ 1 + 1, . . . , µ p + 1, 0, 0, . . .) (which still has p parts and k − µ 1 < k − µ 1 ) by the transition x 0 . By standard results from the theory of Markov chains, see e.g. [LG06, Chapter 13] or [LPW09, Chapter 21], we deduce: Theorem 3.11. An invariant measure of the IMJMC is given by Proof. Note that the r.h.s. of (3.12) is well-defined since y 0 = 1 and λ i vanishes eventually. By (3.10), any predecessor of λ ∈ Par is necessarily of the form µ = (λ 1 + 1, . . . , λ j−1 + 1, λ j+1 , λ j+2 , . . .) for some j, and λ = µ (λj ) . We then have By standard results from the theory of Markov chains, see e.g. [LG06, Chapter 13] or [LPW09, Chapter 21], we deduce: ∞ i=j+1 y λi and P µ,λ = x λj . Telescoping as in (2.21), we deduce By standard results from the theory of Markov chains, see e.g. [LG06, Chapter 13] or [LPW09, Chapter 21], we deduce: with y 1 < 1). This establishes the invariance of w. By standard results from the theory of Markov chains, see e.g. [LG06, Chapter 13] or [LPW09, Chapter 21], we deduce: The expression (3.13) follows from standard considerations on integer partitions, and is finite if and only if y m < ∞, i.e. if (3.5) holds. By standard results from the theory of Markov chains, see e.g. [LG06, Chapter 13] or [LPW09, Chapter 21], we deduce: Again, when (3.5) does not hold, the IMJMC is either null recurrent or transient, and it would be interesting to know which situation occurs. By standard results from the theory of Markov chains, see e.g. [LG06, Chapter 13] or [LPW09, Chapter
{'paper_id': '15436212', 'title': 'Multivariate Juggling Probabilities', 's2_url': 'https://api.semanticscholar.org/CorpusID:15436212', 'source': 'S2ORC'}