Some generalized juggling processes (extended abstract)

Arvind Ayyer, Jérémie Bouttier, Svante Linusson, François Nunzi

► To cite this version:

Arvind Ayyer, Jérémie Bouttier, Svante Linusson, François Nunzi. Some generalized juggling processes (extended abstract). 27th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2015), Jul 2015, Daejeon, South Korea. pp.925-936, 10.46298/dmtcs.2537 . hal-01337758

HAL Id: hal-01337758

https://hal.science/hal-01337758

Submitted on 27 Jun 2016

**HAL** is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Some generalized juggling processes
(extended abstract)

Arvind Ayyer<fnref n="1" />, Jérémie Bouttier<fnref n="2" />, Svante Linusson<fnref n="3" /> and François Nunzi<fnref n="4" />†

**Abstract.** We consider generalizations of juggling Markov chains introduced by Ayyer, Bouttier, Corteel and Nunzi. We first study multispecies generalizations of all the finite models therein, namely the MJMC, the add-drop and the annihilation models. We then consider the case of several jugglers exchanging balls. In all cases, we give explicit product formulas for the stationary probability and closed-form expressions for the normalization factor if known.

**Résumé.** On s’intéresse à des généralisations des chaînes de Markov de jonglage introduites par Ayyer, Bouttier, Corteel et Nunzi. On étudie d’abord des généralisations multiespèces de tous les modèles finis, à savoir le MJMC et les modèles d’add-drop et d’annihilation. On considère ensuite le cas de plusieurs jongleurs échangeant des balles entre eux. Dans chacun des cas, on donne une formule explicite sous forme de produit pour l’état stationnaire, ainsi qu’une forme réduite pour le facteur de normalisation dans les cas où l’on en connaît une.

**Keywords:** Markov chains, Combinatorics, Juggling

# 1 Introduction

Several combinatorial Markov chains are known to have, despite nontrivial dynamics, an explicit and sometimes remarkably simple stationary state. As famous examples related to physics, let us mention the 1D asymmetric exclusion process and the zero-range process, see for instance respectively [DEHP93] and [EH05]. In [AL14], the authors studied an inhomogeneous multispecies generalization of the totally asymmetric simple exclusion process on the ring introduced in [DJLS93] and solved completely in [FM07]. The purpose of this paper is to apply the same philosophy to the simpler juggling processes introduced in [War05] then extended in [ELV15] and [ABCN15], by providing multispecies generalizations of all the models.

Our proofs were mainly obtained by Warrington’s combinatorial approach which consists of introducing an enriched chain whose stationary distribution is simpler, and which yields the original chain by

<footnote n="1">¹Department of Mathematics, Indian Institute of Science, Bangalore - 560012, India</footnote>

<footnote n="2">²Institut de Physique Théorique, Université Paris-Saclay, CEA, CNRS, F-91191 Gif-sur-Yvette and
Département de Mathématiques et Applications, École normale supérieure, 45 rue d'Ulm, F-75231 Paris Cedex 05</footnote>

<footnote n="3">³Department of Mathematics, KTH-Royal Institute of Technology, SE-100 44, Stockholm, Sweden</footnote>

<footnote n="4">⁴LIAFA, CNRS et Université Paris Diderot, Case 7014, F-75205 Paris Cedex 13</footnote>

<footnote>†We are indebted to Sylvie Corteel for her participation in this project, see [ABC$^+$15]. Email of the corresponding author : fnunzi@liafa.univ-paris-diderot.fr.</footnote>
a projection or “lumping” procedure, see e.g. [LPW09, Section 2.3.1]. Let us summarize this strategy. Suppose we have a Markov chain on the state space S (which will be a finite set in all cases considered here), with transition matrix P (which is a matrix with rows and columns indexed by S, such that all rows sum up to 1), and for which we want to find the stationary distribution, namely the (usually unique) row vector π whose entries sum up to 1 and such that $πP = π$. The idea is to introduce another “enriched” Markov chain on a larger state space $\tilde{S}$ with transition matrix $\tilde{P}$, which has the two following properties: (i) its stationary distribution $\tilde{\pi}$ is “easy” to find (for instance we may guess and then check its general form because its entries are integers with nice factorizations, or monomials in some parameters of the chain) and (ii) it projects to the original Markov chain in the sense that there exists an equivalence relation $\sim$ over $\tilde{S}$ such that S can be identified with $\tilde{S}/\sim$ (i.e. the set of equivalence classes of $\sim$), and such that the lumping condition

$$ \sum_{y' \sim y} \tilde{P}_{x,y'} = P_{[x],[y]} \qquad (1) $$

is satisfied for all x, y in $\tilde{S}$, where $[x] \in S$ denotes the equivalence class of x. Then, it is straightforward to check that the stationary distribution $\pi$ of the original Markov chain is given by

$$ \pi_{[x]} = \sum_{x' \sim x} \tilde{\pi}_{x'}. \qquad (2) $$

In principle, there may be a large number of terms in the right-hand side of (2), making the resulting stationary distribution $\pi$ nontrivial.

The rest of the paper is organized as follows. In Section 2, we discuss in some detail the first model, the so-called Multispecies Juggling Markov Chain (MSJMC): Section 2.1 provides its definition and the expression for its stationary distribution, and Section 2.2 is devoted to the enriched chain. Other models with a fluctuating number of balls of each type (but with a finite state space) are considered in Section 3: we introduce the multispecies extension of the add-drop and the annihilation models studied in [ABCN15] in the respective Sections 3.1 and 3.2. Finally, in Section 4, we describe another possible extension of the juggling Markov chain of [War05], that involves several jugglers. Due to space restrictions, several proofs are omitted. These appear in a longer paper written with S. Corteel [ABC$^+$ 15].

# 2 Multispecies juggling

## 2.1 Definition and stationary distribution

The first model that we consider in this paper, and for which we give most details, is a “multispecies” generalization of the so-called Multivariate Juggling Markov Chain (MJMC) introduced in [ABCN15], which was itself a generalisation of a probabilistic juggling model [War05]. We first quickly remind the reader of the original model. Colloquially speaking, the juggler has a fixed number of balls n, which he can throw up to a maximum height h. At each time step, he either waits for any ball to land, or if a ball lands, he throws it uniformly randomly to a vacant height.

In our new model, the juggler has balls of different densities, and when a heavy ball collides with a light one, the light ball is bumped to a higher position, where it can itself bump a lighter ball, etc, until a ball arrives at the topmost position. More precisely, our *Multispecies Juggling Markov Chain (MSJMC)* is defined as follows.
Let $T$ be a fixed positive integer, and $n_1, \dots, n_T$ be a sequence of positive integers. The state space $\text{St}_{n_1, \dots, n_T}$ of the MSJMC is the set of words on the alphabet $\{1, \dots, T\}$ containing, for all $i = 1, \dots, T$, $n_i$ occurrences of the letter $i$ (the letter 1 represents the heaviest ball and $T$ the lightest one). Of course those words have length $n = n_1 + \dots + n_T$, and there are $\binom{n}{n_1, \dots, n_T}$ different states.

To understand the transitions, it is perhaps best to start with an example, by considering the word 132132 (i.e. $T = 3$, $n_1 = n_2 = n_3 = 2$). The first letter 1 corresponds to the ball received by the juggler: it can be thrown either directly to the topmost position, i.e. to the right of the word (resulting in the word 321321), or in the place of any lighter ball. Say we throw it in place of the first 2. This 2 can in turn be thrown either to the topmost position (resulting in the word 311322), or in the place of a lighter ball on its right: here it can only “bump” the second 3, which in turn has no choice but to go to the topmost position, resulting in the word 311223. This latter transition is represented on Figure 1.

<figure><img src="image_2.png" /><figcaption>Fig. 1: A possible transition from the state 132132, corresponding to the bumping sequence (1, 3, 5, 7).</figcaption></figure>

We now give a formal definition of the transitions. Let $w = w_1 \cdots w_n$ be a state in $\text{St}_{n_1, \dots, n_T}$, and set, by convention, $w_{n+1} = \infty$. A bumping sequence for $w$ is an increasing sequence of integers $(a(1), \dots, a(k))$ with length at most $T+1$ such that $a(1) = 1$, $a(k) = n+1$ and, for all $j$ between 1 and $k-1$, $w_{a(j)} < w_{a(j+1)}$ (that is to say, the ball at position $a(j)$ is heavier than that at position $a(j+1)$). We denote by $\mathcal{B}_w$ the set of bumping sequences for $w$. For $a \in \mathcal{B}_w$, we define the state $w^a$ resulting from $w$ via the bumping sequence $a$ by

$$w_i^a = \begin{cases} w_{a(\ell-1)} & \text{if } i = a(\ell) - 1 \text{ for some } \ell, \\ w_{i+1} & \text{otherwise,} \end{cases} \qquad (3)$$

which is easily seen to belong to $\text{St}_{n_1, \dots, n_T}$. Returning to the example in Figure 1 with $w = 132132$, the longest possible bumping sequence is $a = (1, 3, 5, 7)$ and indeed $w^a = 311223$.

We now turn to defining the transition probabilities, which means assigning a probability to each bumping sequence. As in the MJMC, these probabilities will depend on a sequence $z_1, z_2, \dots$ of nonnegative real parameters, whose interpretation is now the following. Suppose that we have constructed the $i-1$ first elements $(a(1), \dots, a(i-1))$ of a random bumping sequence, so that $a(i)$ has to be chosen in the set $\{\ell | a(i-1) < \ell \le n+1, w_\ell > w_{a(i-1)}\}$; $z_j$ is then proportional to the probability that we pick $a(i)$ as the $j$-th largest$^{(i)}$ element in that set. Upon normalizing, we find that the actual probability of picking a specific $a(i)$ can be written

$$Q_{w,a}(i) = \frac{z_{J_w(a(i), w_{a(i-1)})}}{y_{J_w(a(i-1)+1, w_{a(i-1)})}}, \qquad (4)$$

<footnote>$^{(i)}$ If we replace “largest” by “smallest” here, then the MSJMC does not seem to have a simple stationary distribution anymore.</footnote>
where we introduce the general useful notations

$$y_i = z_1 + \cdots + z_i, \qquad (5)$$

$$J_w(m, t) = \#\{\ell | m \le \ell \le n+1, w_\ell > t\}, \qquad (6)$$

for $m \in [1, n]$, $t \in [1, T]$ and $i \in [2, k]$ (throughout this paper, $\llbracket r, s \rrbracket$ denotes the set of integers between $r$ and $s$), and where we recall the convention $w_{n+1} = \infty$. All in all, the global probability assigned to the bumping sequence $a$ is $\prod_{i=2}^k Q_{w,a}(i)$. Noting that, for all states $w, w' \in St_{n_1, \dots, n_T}$, there is at most one $a \in \mathcal{B}_w$ such that $w' = w^a$, we define the transition probability from $w$ to $w'$ as

$$P_{w,w'} = \begin{cases} \prod_{i=2}^{k} Q_{w,a}(i) & \text{if } w' = w^a \text{ for some } a \in \mathcal{B}_w, \\ 0 & \text{otherwise.} \end{cases} \qquad (7)$$

For instance, the transition of Figure 1 has probability $z_4/y_5 \times z_2/y_2 \times z_1/y_1$.

**Remark 1** The MJMC studied in [ABCN15] is recovered by taking $T = 2$, upon identifying 1's with balls (●) and 2's with vacant positions (○).

<figure><img src="image_3.png" /><figcaption>Fig. 2: Transition graph of the MSJMC with $T = 3$ and $n_1 = n_2 = n_3 = 1$.</figcaption></figure>

**Example 2** Figure 2 illustrates the MSJMC on $St_{1,1,1}$, and the corresponding transition matrix in the basis $\{123, 132, 213, 231, 312, 321\}$ reads

$$\begin{pmatrix} \frac{z_3}{y_3} & \frac{z_2}{y_2} & \frac{z_3}{y_3} & \frac{z_1}{y_2} & \frac{z_2}{y_3} & \frac{z_1}{y_3} & 0 & 0 \\ \frac{z_3}{y_3} & 0 & 0 & 0 & 0 & \frac{z_2}{y_3} & \frac{z_1}{y_3} \\ \frac{z_2}{y_2} & \frac{z_1}{y_2} & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & \frac{z_2}{y_2} & 0 & \frac{z_1}{y_2} & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \end{pmatrix}. \qquad (8)$$
Observe that $(y_1y_2y_3, y_1^2y_3, y_1y_2^2, y_1^2y_2, y_1^2y_2, y_1^3)$ is a left eigenvector with eigenvalue 1, and thus is proportional to the stationary distribution.

It is not difficult to check that generically (i.e. when all $z_i$ are nonzero), the MSJMC is irreducible and aperiodic, and thus admits a unique stationary distribution $\pi$. Our main result for this section is an explicit expression for $\pi$.

**Theorem 3** The stationary probability of $w \in St_{n_1, \dots, n_T}$ is given by

$$ \pi(w) = \frac{1}{Z} \prod_{i=1}^{n} y_{J_w(i+1, w_i)}, \qquad (9) $$

where the normalization factor $Z$ reads

$$ Z = \prod_{i=1}^{T} h_{n_i}(y_1, \dots, y_{n-n_1-\dots-n_i+1}), \qquad (10) $$

with $h_\ell$ the complete homogeneous symmetric polynomial of degree $\ell$.

Returning again to the example $w = 132132$, we have $\pi(w) = y_1^3 y_2 y_3 y_5$. According to the general lumping strategy outlined in the introduction, Theorem 3 is proved by introducing a suitable enriched Markov chain as follows.

## 2.2 The enriched Markov chain

The first idea to define the enriched Markov chain comes from expanding the product on the right-hand side of (9) using the definition (5) of the $y_j$'s, resulting in a sum of monomials in the $z_j$'s which is naturally indexed by the set of sequences $v = v_1 \cdots v_n$ of positive integers such that $v_i \le J_w(i+1, w_i)$ for all $i \in [1, n]$. Let us call such $v$ an auxiliary word for $w$. This suggests that we can define an enriched state as a pair $(w, v)$ where $w \in St_{n_1, \dots, n_T}$ and $v$ is an auxiliary word for $w$. We denote by $S_{n_1, \dots, n_T}$ the set of enriched states.

The second idea, needed to define the transitions, is to use the auxiliary word to “record” some information about the past, in such a way that all transitions leading to a given enriched state have the same probability (this will be a key ingredient in the proof of Theorem 4 below). More precisely, given an enriched state $(w, v)$, we consider as before a bumping sequence $a \in B_w$, and we define the resulting enriched state $(w, v)^a = (w', v')$ by updating of course the basic state as before, i.e. we set $w' = w^a$ as in (3), while we update the auxiliary word as

$$ v'_{i} = \begin{cases} J_{w'}(i+1, w'_{i}) & \text{if } i = a(\ell) - 1 \text{ for some } \ell, \\ v_{i+1} & \text{otherwise.} \end{cases} \qquad (11) $$

For instance, in our running example $w = 132132$ and $a = (1, 3, 5, 7)$, for $v = 412211$ we have $v' = 142211$. We may think of the auxiliary word as “labels” carried by the balls, that are modified for the bumped balls and preserved otherwise. The transition probability from $(w, v)$ to $(w', v')$ is as before

$$ \tilde{P}_{(w,v),(w',v')} = \begin{cases} \prod_{i=2}^{k} Q_{w,a(i)} & \text{if } (w', v') = (w, v)^a \text{ for some } a \in B_w, \\ 0 & \text{otherwise.} \end{cases} \qquad (12) $$
It is clear that the enriched chain projects to the MSJMC. Indeed, we define an equivalence relation over $S_{n_1, \dots, n_T}$ by simply “forgetting” the auxiliary word, so that the equivalence classes may be identified with $St_{n_1, \dots, n_T}$ (note that $1^n$ is a valid auxiliary word for any element of $St_{n_1, \dots, n_T}$). The lumping condition (1) is trivially satisfied, since we have $\tilde{P}_{(w,v),(w,v)^a} = P_{w,w^a}$ for all $(w,v)$ in $S_{n_1, \dots, n_T}$ and $a$ in $B_w$, and $\tilde{P}_{(w,v),(w^a,v')} = 0$ whenever $(w^a, v') \neq (w, v)^a$.

**Theorem 4** The stationary distribution of $(w, v)$ in $S_{n_1, \dots, n_T}$ for the enriched chain is

$$ \tilde{\pi}(w, v) = \frac{1}{Z} \prod_{i=1}^{n} z_{v_i} \qquad (13) $$

where $Z$ is the normalization factor.

**Proof:** We have to check that, for all $(w', v') \in S_{n_1, \dots, n_T}$, we have

$$ \sum_{(w,v) \in S_{n_1, \dots, n_T}} \tilde{P}_{(w,v),(w',v')} \tilde{\pi}(w,v) = \tilde{\pi}(w',v'), \qquad (14) $$

which is done by characterizing the possible predecessors of $(w', v')$. Let $(w, v)$ be such that $(w', v') = (w, v)^a$ for some bumping sequence $a \in B_w$. We will show in particular that $a$ and $w$ are uniquely determined from the data of $(w', v')$ hence, as claimed above, all transitions to $(w', v')$ have the same probability.

We start by explaining how to recover the bumping sequence $a = (a(1), \dots, a(k))$ or, more precisely, its set of values $A = \{a(1), \dots, a(k)\}$. Recall that $1$ and $n+1$ belong to $A$ by definition. We claim that $j \in [2, n]$ belongs to $A$ if and only if the following two conditions hold:

(i) $v'_{j-1} = J_{w'}(j, w'_{j-1})$,

(ii) $w'_{j-1} < w'_{j'-1}$ where $j'$ is the smallest element of $A \cap [j+1, n+1]$.

Indeed, these two conditions are clearly necessary: (i) by (11), and (ii) by (3) and the requirement that $w_j < w_{j'}$ when $j < j'$ are both in the bumping sequence. Conversely, assume that $j \notin A$, so that $w_j = w'_{j-1}$ and $v_j = v'_{j-1}$. By the definition of the MSJMC transitions, the subword $w'_j \cdots w'_n$ is a permutation of $w_{j+1} \cdots w_n w'_{j'-1}$. Hence, recalling (6), $J_{w'}(j, w'_{j-1}) - J_w(j+1, w_j)$ is equal to $1$ if (ii) holds and to $0$ otherwise. If (i) holds, we have $J_{w'}(j, w'_{j-1}) = v'_{j-1} = v_j \le J_w(j+1, w_j)$, hence (ii) cannot hold. This completes the proof of our claim, which fully determines $A$ (hence $a$) by reverse induction.

Once we have recovered $a$, it is clear that $w$ is uniquely determined, while we have $v_j = v'_{j-1}$ for $j \notin A$. All predecessors of $(w', v')$ are then obtained by picking, for each $j \in A \setminus \{n+1\}$, $v_j$ an arbitrary integer between $1$ and $J_w(j+1, w_j)$. This shows that

$$ \sum_{v: (w', v') = (w, v)^a} \tilde{\pi}(w, v) = \frac{1}{Z} \prod_{j \notin A} z_{v'_{j-1}} \prod_{j \in A \setminus \{n+1\}} y_{J_w(j+1, w_j)}. \qquad (15) $$

The last observation we need is that $J_w(a(i), w_{a(i-1)}) = J_{w'}(a(i), w'_{a(i-1)}) = v'_{a(i-1)}$ for all $i \in [2, k]$, since $w'_{a(i)} \cdots w'_{n}$ is a permutation of $w_{a(i)} \cdots w_n$ and since $w_{a(i-1)} = w'_{a(i-1)}$. By (4) and (7)
we find that, for any predecessor $(w, v)$ of $(w', v')$,

$$ \tilde{P}_{(w,v),(w',v')} = \frac{\prod_{j \in A \setminus \{1\}} z_{v'_{j-1}}}{\prod_{j \in A \setminus \{n+1\}} y_{J_w(j+1,w_j)}}. \qquad (16) $$

Combined with (15), the desired stationarity condition (14) follows. □

**Proof of Theorem 3:** The expression (9) is immediately obtained by applying the general lumping expression (2) for the stationary state, Theorem 4 and the definition of enriched states. It remains to check the expression (10), which we do by induction on $T$. Let $\phi(w) = \prod_{i=1}^n y_{J_w(i+1,w_i)}$, so that $Z$ is the sum of $\phi(w)$ over all $w \in St_{n_1, \dots, n_T}$. The expression (10) holds for $T=0$, as $Z = \phi(\epsilon) = 1$ where $\epsilon$ is the empty word. For $T \ge 1$, let $w$ be a word in $St_{n_1, \dots, n_T}$, and let $\hat{w} \in St_{n_2, \dots, n_T}$ be the word obtained by removing all occurrences of 1 in $w$, and shifting all remaining letters down by 1. Denote by $i_1 > \dots > i_{n_1}$ the positions of 1's in $w$, and let $j_\ell = n+2-i_\ell-\ell$, so that $1 \le j_1 \le \dots \le j_{n_1} \le n-n_1+1$. The mapping $w \mapsto (\hat{w}, (j_1, \dots, j_{n_1}))$ is bijective, and it is not difficult to see from the definition (6) of $J_w(\cdot, \cdot)$ that

$$ \phi(w) = \phi(\hat{w}) \prod_{\ell=1}^{n_1} y_{j_{\ell}}. \qquad (17) $$

Summing the product on the right-hand side over all sequences $(j_1, \dots, j_{n_1})$ yields the complete homogeneous symmetric polynomial $h_{n_1}(y_1, \dots, y_{n-n_1+1})$, and (10) follows by induction. □

# 3 Multispecies juggling with fluctuating types

Our goal is here to introduce multispecies generalizations of the add-drop and annihilation models [War05, ABCN15]. Both models have the same state space and the same transition graph, but transition probabilities differ. The state space is $St_n^T$, the set of words of length $n$ on the alphabet $A = \{1, \dots, T\}$: the number of balls of each type is not fixed anymore and thus there are $T^n$ possible states. The transitions are similar to the ones in the MSJMC, except that the type of the ball the juggler throws is independent of the type of the ball he just caught. This ball then initiates a bumping sequence as defined before. More precisely, starting with a state $w = w_1 \cdots w_n \in St_n^T$, we let $w^- = w_2 \cdots w_n$: transitions consist in replacing the first letter of $w$ by an arbitrary $j \in A$, resulting in the intermediate state $jw^-$, then applying a bumping sequence $a \in B_{jw^-}$, resulting in the final state $(jw^-)^a$, where $(\cdot)^a$ is defined as in (3). Defining transitions probabilities requires specifying how we pick $j$ and $a$. The multispecies add-drop and annihilation models differ in the way that we pick the new ball of type $j$ and the position $a(2)$ where it is inserted, while the subsequent elements $a(3), \dots, a(k)$ of the bumping sequence are then chosen in the same way as for the MSJMC.

## 3.1 Add-drop model

In the add-drop model, choosing a ball of type $j$ and sending it to the $\ell$-th available position from the right is done with probability proportional to $c_j z_\ell$ where, in addition to the previous parameters $z_1, z_2, \dots$, we introduce new nonnegative real parameters $c_1, \dots, c_T$ that can be interpreted as “activities” for each type of ball. Because lighter balls can be inserted in fewer possible positions, the actual probability of choosing $j$ and $\ell$ has to be normalized, and reads $c_j z_\ell / (\sum_{t=1}^T c_t y_{J_w(2,t)})$ where $w$ is the initial state and where we
<figure><img src="image_4.png" /><figcaption>Fig. 3: The basic transition graph on $\mathcal{S}t_2^3$. Note that the first letter has no effect on which states can be reached.</figcaption></figure>

use the same notations (5) and (6) as before (note that $J_w(m, t) = J_{jw-}(m, t)$ for all $m > 1$). As the position where the new ball is inserted is $a(2) > 1$, saying that it is the $\ell$-th available position from the right means that $\ell = J_w(a(2), j)$. As said above, the subsequent elements $a(3), \dots, a(k)$ of the bumping sequence $a$ are chosen in the same way as for the MSJMC, so that the global probability of picking a new ball of type $j$ and a bumping sequence $a \in \mathcal{B}_{jw-}$ is

$$p_w(j, a) = \frac{c_j z J_w(a(2), j)}{\sum_{t=1}^{T} c_t y_{J_w(2, t)}} \prod_{i=3}^{k} Q_{w, a}(i) \quad (18)$$

where we recall the notation (4). The multispecies add-drop juggling Markov chain is then the Markov chain on the state space $\mathcal{S}t_n^T$ for which the transition probability from $w$ to $w'$ reads

$$P_{w,w'} = \begin{cases} p_w(j, a) & \text{if } w' = (jw^{-})^a \text{ for some } j \in \mathcal{A} \text{ and } a \in \mathcal{B}_{jw^{-}}, \\ 0 & \text{otherwise.} \end{cases} \quad (19)$$

Note that we recover the add-drop juggling model of [ABCN15] when we set $T = 2$.

**Example 5** The transition matrix of the multispecies add-drop Markov chain on the set space $\mathcal{S}t_2^3$ in the ordered basis $\{11, 21, 31, 12, 22, 32, 13, 23, 33\}$ reads

$$\begin{pmatrix}
\frac{c_1 z_1}{\lambda_1} & 0 & 0 & \frac{c_2 z_1}{\lambda_1} & 0 & 0 & \frac{c_3 z_1}{\lambda_1} & 0 & 0 \\
\frac{c_1 \bar{z}_1}{\lambda_1} & 0 & 0 & \frac{c_2 \bar{z}_1}{\lambda_1} & 0 & 0 & \frac{c_3 \bar{z}_1}{\lambda_1} & 0 & 0 \\
\frac{c_1 \bar{z}_1}{\lambda_1} & 0 & 0 & \frac{c_2 \bar{z}_1}{\lambda_1} & 0 & 0 & \frac{c_3 \bar{z}_1}{\lambda_1} & 0 & 0 \\
0 & \frac{c_1 z_1}{\lambda_2} & 0 & \frac{c_1 \bar{z}_2}{\lambda_2} & \frac{c_2 z_1}{\lambda_2} & 0 & 0 & \frac{c_3 z_1}{\lambda_2} & 0 & 0 \\
0 & \frac{c_1 \bar{z}_1}{\lambda_2} & 0 & \frac{c_1 \bar{z}_2}{\lambda_2} & \frac{c_2 \bar{z}_1}{\lambda_2} & 0 & 0 & \frac{c_3 \bar{z}_1}{\lambda_2} & 0 & 0 \\
0 & \frac{c_1 \bar{z}_1}{\lambda_2} & 0 & \frac{c_1 \bar{z}_2}{\lambda_2} & \frac{c_2 \bar{z}_1}{\lambda_2} & 0 & 0 & \frac{c_3 \bar{z}_1}{\lambda_2} & 0 & 0 \\
0 & 0 & \frac{c_1 z_1}{\lambda_3} & 0 & 0 & \frac{c_2 z_1}{\lambda_3} & \frac{c_1 z_2}{\lambda_3} & \frac{c_2 z_2}{\lambda_3} & \frac{c_3 z_1}{\lambda_3} & 0 \\
0 & 0 & \frac{c_1 \bar{z}_1}{\lambda_3} & 0 & 0 & \frac{c_2 \bar{z}_1}{\lambda_3} & \frac{c_1 \bar{z}_2}{\lambda_3} & \frac{c_2 \bar{z}_2}{\lambda_3} & \frac{c_3 \bar{z}_1}{\lambda_3} & 0 \\
0 & 0 & \frac{c_1 \bar{z}_1}{\lambda_3} & 0 & 0 & \frac{c_2 \bar{z}_1}{\lambda_3} & \frac{c_1 \bar{z}_2}{\lambda_3} & \frac{c_2 \bar{z}_2}{\lambda_3} & \frac{c_3 \bar{z}_1}{\lambda_3} & 0
\end{pmatrix} \quad (20)$$

with the notation $\lambda_1 = (c_1 + c_2 + c_3)y_1$, $\lambda_2 = c_1 y_2 + (c_2 + c_3)y_1$ and $\lambda_3 = (c_1 + c_2)y_2 + c_3 y_1$. One can check that $(c_1^2 y_1^2, c_1 c_2 y_1^2, c_1 c_3 y_1^2, c_1 c_2 y_1 y_2, c_2^2 y_1^2, c_2 c_3 y_1^2, c_1 c_3 y_1 y_2, c_2 c_3 y_1 y_2, c_3^2 y_1^2)$ is a left eigenvector for the eigenvalue 1.
**Theorem 6** The stationary probability of $w = w_1 \cdots w_n \in St_n^T$ for the add-drop model is given by

$$ \pi(w) = \frac{1}{Z} \prod_{i=1}^{n} c_{w_i} y_{J_w(i+1, w_i)}. \qquad (21) $$

where the normalization factor $Z$ reads

$$ Z = \sum_{n_1+\cdots+n_T=n} \left( c_1^{n_1} \cdots c_T^{n_T} \prod_{i=1}^{T} h_{n_i} (y_1, \ldots, y_{n-n_1-\cdots-n_i+1}) \right) \qquad (22) $$

with $h_\ell$ the complete homogeneous symmetric polynomial of degree $\ell$.

The proof is a straightforward adaptation of that of Theorem 3, and is omitted here.

## 3.2 Annihilation model

In this model, we consider that the juggler first tries to send a ball of type 1. He chooses $i \in [1, n+1]$ with probability $z_i$, and tries sending the ball at the $i$-th available position. Here we assume that $z_1 + \cdots + z_{n+1} = 1$. If $i$ is a valid position (that is, it is not larger than the number of available positions for the 1), there is a bumping sequence whose subsequent elements are drawn in the same way as for the MSJMC. Otherwise, he tries instead to send a 2 according to the same procedure, etc. In the end, if he did not manage to send any ball of type in $[1, T-1]$, he just sends a $T$ on the top (a $T$ never generates a bumping sequence). Note that failing to send a ball of type $\ell$ for an initial state $w$ is done with probability

$$ 1 - y_{J_w(2, \ell)}. \qquad (23) $$

Globally, the probability of picking a new ball of type $j$ and a bumping sequence $a \in B_{jw^-}$ reads

$$ p_w(j, a) = \begin{cases} z_{J_w(a_2, j)} \prod_{\ell=1}^{j-1} (1 - y_{J_w(2, \ell)}) \prod_{i=3}^{k} Q_{w, a}(i) & \text{if } j < T, \\ \prod_{\ell=1}^{T-1} (1 - y_{J_w(2, \ell)}) & \text{if } j = T, \end{cases} \qquad (24) $$

and the transition probabilities of the multispecies annihilation juggling Markov chain are obtained by superseding this new definition of $p_w(j, a)$ into (19). Note that we recover the annihilation juggling model of [ABCN15] when we set $T = 2$.

**Example 7** The transition matrix of the multispecies annihilation Markov chain on the set space $St_2^3$ in the ordered basis $\{11, 21, 31, 12, 22, 32, 13, 23, 33\}$ reads

$$ \begin{pmatrix} z_1 & 0 & 0 & z_1(z_2+z_3) & 0 & 0 & (z_2+z_3)^2 & 0 & 0 \\ z_1 & 0 & 0 & z_1(z_2+z_3) & 0 & 0 & (z_2+z_3)^2 & 0 & 0 \\ z_1 & 0 & 0 & z_1(z_2+z_3) & 0 & 0 & (z_2+z_3)^2 & 0 & 0 \\ 0 & z_1 & 0 & z_2 & z_1z_3 & 0 & 0 & z_3(z_2+z_3) & 0 \\ 0 & z_1 & 0 & z_2 & z_1z_3 & 0 & 0 & z_3(z_2+z_3) & 0 \\ 0 & z_1 & 0 & z_2 & z_1z_3 & 0 & 0 & z_3(z_2+z_3) & 0 \\ 0 & 0 & z_1 & 0 & 0 & z_1z_3 & z_2 & z_2z_3 & z_3^2 \\ 0 & 0 & z_1 & 0 & 0 & z_1z_3 & z_2 & z_2z_3 & z_3^2 \\ 0 & 0 & z_1 & 0 & 0 & z_1z_3 & z_2 & z_2z_3 & z_3^2 \end{pmatrix} \qquad (25) $$
Note that $(z_1^2, z_1^2(z_2 + z_3), z_1(z_2 + z_3)^2, z_1(z_1 + z_2)(z_2 + z_3), z_1^2z_3(z_2 + z_3), z_1z_3(z_2 + z_3)^2, (z_1 + z_2)(z_2 + z_3)^2, z_3(z_1 + z_2)(z_2 + z_3)^2, z_3^2(z_2 + z_3)^2)$ is a left eigenvector for the eigenvalue 1.

**Theorem 8** The stationary probability of $w = w_1 \cdots w_n \in St_n^T$ for the annihilation model is given by

$$ \pi(w) = \left( \prod_{i=1, w_i < T}^{n} y_{J_w(i+1, w_i)} \right) \left( \prod_{\ell=2}^{T} \prod_{j=1}^{\#\{i|w_i \ge \ell\}} (z_{j+1} + \cdots + z_{n+1}) \right). \quad (26) $$

Moreover, here no normalization factor is needed as

$$ \sum_{w \in St_n^T} \pi(w) = (z_1 + \cdots + z_{n+1})^{n(T-1)} = 1. \quad (27) $$

This theorem can be proved by enriching the chain as before. However, the stationary probabilities of enriched states are no longer monomials in the $z_i$'s, which suggest that a further enrichment is possible as already observed for the case $T = 2$ [ABCN15]. It also seems that there is an interesting pattern for the eigenvalues of the transition matrix, which we plan to investigate in the future.

## 4 Several jugglers

We now consider a completely different generalization of Warrington's model [War05]. Instead of a multivariate or multispecies generalization, we will now consider that there are several jugglers, and that each one of them can send the balls he catches to any other juggler. Let $r, c, \ell$ be nonnegative integers such that $\ell \le rc$, we denote by $S_{r \times c}$ the set of arrays with $r \times c$ cells, each cell being either empty or containing a ball, and by $S_{r \times c, \ell}$ the set of arrays in $S_{r \times c}$ containing exactly $\ell$ balls. Each column represents the balls that are sent to a specific juggler. Let $A$ and $B$ be two arrays in $S_{r \times c}$, we denote $A^-$ the array obtained by removing all the balls in the lowest row, and moving all the other balls down a row. We will also say that $A \subset B$ if all the balls in $A$ are also in $B$. For $i$ between 1 and $r$, we will note $A_i$ the number of balls in the $i$-th row (rows are numbered from top to bottom).

The several jugglers Markov chain is the Markov chain on the set space $S_{r \times c, \ell}$ whose transition probabilities read, for $A, B \in S_{r \times c}^\ell$,

$$ P_{A,B} = \begin{cases} 1/(\binom{A_r}{rc-\ell+A_r}) & \text{if } A^- \subset B \\ 0 & \text{otherwise.} \end{cases} \quad (28) $$

Here, $A_r$ is the number of balls in the lowest row of $A$, which is exactly the number of balls the jugglers will have to send back. These $A_r$ balls are reinjected uniformly in the $rc - \ell + A_r$ available positions, under the constraint that no two balls go to the same position.

**Example 9** The transition Matrix of the several jugglers Markov chain on the set space $S_{2 \times 2, 2}$ in the basis ordered $(1, 2, 3, 4, 5, 6)$ on Figure 4 reads

$$ \begin{pmatrix} \frac{1}{6} & \frac{1}{6} & \frac{1}{6} & \frac{1}{6} & \frac{1}{6} & \frac{1}{6} \\ \frac{1}{3} & \frac{1}{3} & 0 & \frac{1}{3} & 0 & 0 \\ \frac{1}{3} & \frac{1}{3} & 0 & \frac{1}{3} & 0 & 0 \\ \frac{1}{3} & 0 & \frac{1}{3} & 0 & \frac{1}{3} & 0 \\ \frac{1}{3} & 0 & \frac{1}{3} & 0 & \frac{1}{3} & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 \end{pmatrix} \quad (29) $$
<figure><img src="image_5.png" /><figcaption>Fig. 4: The several jugglers Markov chain on the set space $S_{2×2,2}$.</figcaption></figure>

Note that (6, 3, 3, 3, 3, 1) is a left eigenvector for the eigenvalue 1.

Again, we have an explicit expression for the stationary distribution of this Markov chain.

**Theorem 10** The stationary probability of $A \in S_{r×c,ℓ}$ for the several jugglers Markov chain reads

$$ \pi(A) = \frac{1}{Z_{r×c,ℓ}} \prod_{h=1}^{ℓ} (ci_h - h + 1) \qquad (30) $$

where $h$ counts the balls from top to bottom, and $i_h$ denotes the row in which the $h$-th ball is, upon numbering the balls from top to bottom (the order between columns is not relevant). $Z_{r×c,ℓ}$ is the normalization factor.

It can be obtained by introducing a suitable enriched chain, involving “arches”, whose stationary distribution is the uniform distribution. Details are given in [ABC$^{+}$15].

# 5 Conclusion

Several questions remain open in the multispecies juggling context. We have not found an expression for the normalization factor for the juggling chain with several jugglers. We have also not yet found a multiparameter version for the latter model, as the possibility of catching more than one ball at a time changes the behavior quite drastically.

A multispecies model with several jugglers is one possible extension of our model. From a probabilistic point of view, it would also be natural to look at the extension to infinite models, such as a Markov chain on the set space $St_{n_1,...,n_{T-1},∞}$. This would contain as special cases, the infinite and unbounded juggling models [ABCN15].
Acknowledgements

The authors acknowledge financial support from the Agence Nationale de la Recherche via the grants ANR-08-JCJC-0011 “IComb”, ANR 12-JS02-001-01 “Cartaplus” and ANR-14-CE25-0014 “GRAAL”, and by the “Combinatoire à Paris” project funded by the City of Paris. The first author (A.A.) would like to acknowledge the hospitality during his stay at LIAFA, where this work was initiated.

References

[ABC<sup>+</sup>15] Arvind Ayyer, Jérémie Bouttier, Sylvie Corteel, Svante Linusson, and François Nunzi. Some generalized juggling processes, 2015. arXiv:1504.02688 [math.CO].

[ABCN15] Arvind Ayyer, Jérémie Bouttier, Sylvie Corteel, and François Nunzi. Multivariate juggling probabilities. *Electron. J. Probab.*, 20:no. 5, 1–29, 2015. arXiv:1402.3752 [math.PR].

[AL14] Arvind Ayyer and Svante Linusson. An inhomogeneous multispecies TASEP on a ring. *Adv. in Appl. Math.*, 57:21–43, 2014. arXiv:1206.0316 [math.PR].

[DEHP93] B. Derrida, M. R. Evans, V. Hakim, and V. Pasquier. Exact solution of a 1D asymmetric exclusion model using a matrix formulation. *J. Phys. A*, 26(7):1493–1517, 1993.

[DJLS93] Bernard Derrida, Steven A Janowsky, Joel L Lebowitz, and Eugene R Speer. Exact solution of the totally asymmetric simple exclusion process: shock profiles. *Journal of Statistical Physics*, 73(5-6):813–842, 1993.

[EH05] M. R. Evans and T. Hanney. Nonequilibrium statistical mechanics of the zero-range process and related models. *J. Phys. A: Math. Gen.*, 38(19):R195, 2005. arXiv:cond-mat/0501338 [cond-mat.stat-mech].

[ELV15] Alexander Engström, Lasse Leskelä, and Harri Varpanen. Geometric juggling with q-analogues. *Discrete Mathematics*, 338(7):1067–1074, 2015. arXiv:1310.2725 [math.CO].

[FM07] Pablo A Ferrari and James B Martin. Stationary distributions of multi-type totally asymmetric exclusion processes. *The Annals of Probability*, pages 807–832, 2007. arXiv:math/0501291 [math.PR].

[LPW09] David A. Levin, Yuval Peres, and Elizabeth L. Wilmer. *Markov Chains and Mixing Times*. American Mathematical Society, Providence, RI, 2009. With a chapter by James G. Propp and David B. Wilson.

[War05] Gregory S. Warrington. Juggling probabilities. *The American Mathematical Monthly*, 112(2):pp. 105–118, 2005. arXiv:math/0501291 [math.PR].