A product formula for the TASEP on a ring
– extended abstract

Erik Aas* and Jonas Sjöstrand†

Dep. of Mathematics, Royal Institute of Technology, Stockholm, Sweden

**Abstract:** For a random permutation sampled from the stationary distribution of the TASEP on a ring, we show that, conditioned on the event that the first entries are strictly larger than the last entries, the *order* of the first entries is independent of the *order* of the last entries. The proof uses multi-line queues as defined by Ferrari and Martin, and the theorem has an enumerative combinatorial interpretation in that setting.

Finally, we present a conjecture for the case where the small and large entries are not separated.

**Resumé:** Pour une permutation randomisée tirée de la mesure stationnaire du TASEP, nous démontrons, conditionnée à l'événement que les prémières lettres sont plus grandes que les dernières lettres, que l'ordre des petites lettres est indépendant de l'ordre des grandes lettres. La preuve utilise les files d'attente multilignes de Ferrari et Martin, et le théorème a une interprétation combinatoire enumerative dans ce contexte.

Finalement, nous présentons une conjecture pour le cas où les petits et les grandes lettres ne sont pas séparées.

# 1 Introduction

Exclusion processes are Markov chains that can be defined for any graph; see [8] for an overview. The vertices of the graph are called *sites*, and a state in the process is a distribution of particles into the sites with *at most one particle* at each site—this is what the word “exclusion” refers to. The transitions in the Markov chain are defined by letting the particles jump or swap randomly according to some rules. The most studied case is probably the *totally asymmetric simple exclusion process (TASEP)* on $Z$, the set of integers thought of as an infinite row of sites. Each particle goes one step to the left with rate one, but only if that site is empty, otherwise nothing happens. The “totally asymmetric” part refers to particles going left but never right.

Recently, several authors ([5], [3], [4], [7]) have examined the TASEP on a ring $Z/nZ$, where furthermore particles have different *sizes* (or *classes*). This is sometimes called the *multi-type TASEP*. Lam [6] gave a nice connection between this TASEP and the limit shape of large random $n$-core partitions.

The TASEP on the ring $Z/nZ$ can be described as a continuous-time Markov chain defined on permutations of a finite multiset of positive integers. Given a permutation $w$ written as a word $w = w_1w_2\cdots w_n$, each entry $w_j$ carries an exponential clock that rings with rate $x_{w_j}$. When it rings, the entry trades place with its left neighbour (cyclically) if that entry is larger than $w_j$. Otherwise, nothing happens.

For a random permutation $w$ sampled from the stationary distribution, we show that, conditioned on the event that the first $k$ entries of $w$ are strictly larger than the last $n-k$ entries, the *order* of the first $k$ entries is independent of the *order* of the last $n-k$ entries. We also generalize this result to three or more groups of adjacent entries. The proof is based on a connection between the TASEP and multi-line queues which was found by Ferrari and Martin [5].

The paper is organized as follows. After introducing some notation and presenting our results, in Section 3 we describe the multi-line queues of Ferrari and Martin and their connection to TASEPs.

<footnote>*Email: eaas@kth.se.</footnote>

<footnote>†Email: jonass@kth.se. Supported by a grant from the Swedish Research Council (621-2009-6090).</footnote>
In the two succeding sections we prove two recurrence relations that will be the main ingredients in our proof. Section 5 contains the proof of our main result and in Section 6 we give some explicit formulas for the coefficients in the recurrence relations. Finally, in Section 7 we suggest some future research and offer a conjecture for the case where the small and large entries in the word are not separated.

## 2 Notation and results

Fix a positive integer $n$. We think of the $n$-ring $\mathbb{Z}/n\mathbb{Z}$ as a row of $n$ sites, indexed by $1, 2, \dots, n$ from the left, where the left and right edges of the row are glued together. The states in the Markov chain are identified with words $w$ in $\{1, 2, \dots, \infty\}^n$. Let $m_i$ be the number of times $i$ occurs in $w$. We will consider only words $w$ such that $m_1, \dots, m_r > 0$ for some $r$ and $m_i = 0$ for $r < i < \infty$. Such a sequence $m_1, \dots, m_r$ will be called a *type* and we say that $\mathbf{m} = (m_1, \dots, m_r)$ is the *type of* $w$. Note that the type determines $m_\infty$, as the length $n$ is fixed. The finite entries in $w$ should be interpreted as particles of the corresponding *size* and the infinite entries should be interpreted as *empty sites*. Let $\Omega_\mathbf{m}$ denote the set of words of type $\mathbf{m}$ (and length $n$ that is to be understood from the context).

**Definition 2.1** Let $\mathbf{m} = (m_1, \dots, m_r)$ be a type and let $t_1, \dots, t_r$ be positive real numbers. The totally asymmetric exclusion process, or TASEP, on $\Omega_\mathbf{m}$ with inverse rates $t_1, \dots, t_r$ is defined as follows.

*Each finite entry $i$ of $u \in \Omega_\mathbf{m}$ carries an exponential clock that rings with rate $1/t_i$. When the clock rings, the entry trades places with its left neighbour if that entry is larger.*

See Figure 1 for an example. For a generic choice of the $t_i$, this chain has a unique stationary distribution which we denote by $\pi$. We will for the most part think of the $t_i$'s as indeterminates and of the value $\pi(w)$ (for words $w$) as a rational function of these indeterminates. Sometimes it is useful to think of the $\pi(w)$ as actual probabilities.

Of course, we could also let the infinite entries carry clocks—their jumps would never be successful. Although this would be a more uniform definition, it has some drawbacks that make us opt for the definition above.

Finally, note that the stationary distribution is invariant with respect to cyclic shifts; for example, we have $\pi(123) = \pi(312) = \pi(231)$.

A word $w = w_1w_2\dots w_n$ is said to be *decomposable* if it can be written as a concatenation $w = uv$ of words $u = w_1w_2\dots w_k$ and $v = w_{k+1}w_{k+2}\dots w_n$ where all entries of $u$ are strictly larger than all entries of $v$. (Of course, an infinite entry $\infty$ is considered to be larger than any finite entry.)

We can now state our main theorem.

**Theorem 2.2** Let $uv$ be a decomposable word and let $v'$ be a word obtained from $v$ by permuting the entries. Then,

$$ \frac{\pi(uv)}{\pi(uv')} = \frac{\pi(\infty v)}{\pi(\infty v')} $$

as rational expressions in the $t_i$'s. (Here, $\infty$ denotes the word $\infty \cdots \infty$ of the same length as $u$.)

We postpone the proof until Section 5 and turn our interest to some corollaries for now.

Since the right hand side of the equation above is independent of $u$ (but dependent of the length of $u$), the following weaker but symmetric variant of our main result follows.

**Corollary 2.3** Let $uv$ be a decomposable word and let $u'$ and $v'$ be words obtained from $u$ and $v$, respectively, by permuting the entries. Then,

$$ \pi(uv)\pi(u'v') = \pi(u'v)\pi(uv') $$

as rational expressions in the $t_i$'s.

As a further corollary we obtain the result that we promised in the introduction.
<figure><img src="image_1.png" /><figcaption>**Fig. 1:** The TASEP on $\Omega_{(1,1,1)}$ with $n = 3$. Here $Z = 6t_1 + 3t_2$. The stationary distribution $\pi$ is indicated at each state. On each arrow is written the corresponding transition rate.</figcaption></figure>

**Corollary 2.4** Let $uv$ be a decomposable word of type $m$ and let $W$ be a random word sampled from the stationary distribution of the TASEP on $\Omega_m$, conditioned on the event that $W = UV$ is decomposable with $U$ and $V$ of the same length (and type) as $u$ and $v$, respectively. Then, $U$ and $V$ are independent, that is

$$P(U = u \text{ and } V = v) = P(U = u)P(V = v).$$

As an example, consider the TASEP on $\Omega_{(1,1,1,1)}$ with $n = 4$ and $t_1 = t_2 = t_3 = t_4 = 1$. Our result tells us that if we sample a word $w$ from the stationary distribution and it happens that the entries 3 and 4 come before 1 and 2, then the order of the 3 and 4 gives us no information about the order of the 1 and 2. This can be stated in equational form as $\pi(4321)/\pi(4312) = \pi(3421)/\pi(3412)$, which is true since $\pi(4321) = 1/96$, $\pi(4312) = \pi(3421) = 3/96$, and $\pi(3412) = 9/96$ (as a simple computation yields). At first glance our result may seem obvious, at least in the homogeneous case where all $t_i = 1$, since the “large” entries cannot tell the “small” entries apart and vice versa. However, this is an illusional simplicity and the condition that the large numbers are adjacent is essential for our main result. Indeed, if it happens that the entries 3 and 4 are at positions 2 and 4, then their order really tells us something about the order of the entries 1 and 2, since

$$3/5 = \pi(2413)/\pi(1423) \neq \pi(2314)/\pi(1324) = 5/3. \qquad (1)$$

## 3 Queues and multi-line queues

Ferrari and Martin [5] studied the *homogenous* case where $t_1 = \cdots = t_r$ and discovered that the TASEP on a ring is a projection of a richer process involving combinatorial structures called multi-line queues. Ayyer and Linusson [4] generalized the construction to the inhomogeneous case. Remarkably, this transfers questions about the stationary distribution of the TASEP to enumerative questions about multi-line queues and we state that result in Theorem 3.1. But first we must define queues and multi-line queues.
<figure><img src="image_2.png" /><figcaption>**Fig. 2:** A $2 \times n$ array representing a queue with input word $21\infty3\infty\infty112$ (converted to $214344112$) and output word $2\infty12341\infty1$. The circles on the bottom row corresponds to the terminal positions of the queue. The two non-circled 1's in the bottom row corresponds to non-terminal positions visited by 1. Thus the weight of this queue with respect to this input is $t_1^2$.</figcaption></figure>

## 3.1 Queues

A queue $q$ of capacity $c$ is an $n$-ring where $c$ sites are marked as terminal. It defines a map $q$ on words, defined as follows.

Given an input word $u$ of type $(m_1, \dots, m_r)$, first replace each letter $\infty$ (empty site) by $r+1$ (particle of a new maximal size). Next, put the queue immediately below $u$ to form a $2 \times n$-array of sites (see Figure 2), and perform the following queuing procedure.

We will associate a word $q(u)$ to $q$ whose empty sites are exactly at the non-terminal sites of $q$. At the start, all terminal positions of $q$ are unoccupied.

* We will let the $n$ input particles enter the queue one by one in any order such that smaller particles come before larger ones. (The order of particles of the same size does not matter.)

* According to such an ordering, each particle first enters the queue by moving one step down, and then it moves zero or more steps (cyclically) to the right until it reaches an unoccupied terminal site. If all terminal sites are occupied, the particle just continues around the ring forever and can be discarded. (However, it may have an impact on the weight of $q$ which is defined below.)

The resulting word is the output of the map.

Note that each non-terminal site in $q$ is visited by at least one particle. For $i = 1, 2, \dots, r$, let $\alpha_i$ be the number of non-terminal sites in the queue that are first visited by a particle of size $i$.

The monomial $t_1^{\alpha_1} \cdots t_r^{\alpha_r}$ is called the *weight of $q$ with respect to $u$*.

Note that neither the weight nor the resulting word depends on the order in which particles of the same size enter the queue.

## 3.2 Multi-line queues

A *multi-line queue* of type $\mathbf{m} = (m_1, \dots, m_r)$ is a sequence $\mathbf{q} = (q_1, \dots, q_r)$ of queues such that $q_i$ has capacity $m_1 + \dots + m_i$ for each $i$. We will think of the queues as being stacked vertically and view the multi-line queue as an $r \times n$-array of sites where exactly $m_1 + \dots + m_i$ of the sites in row $i$ are marked as terminal.

Let us feed the first queue $q_1$ with the “empty” word $\infty \dots \infty$ and then feed $q_2$ with the output from $q_1$ and $q_3$ with the output from $q_2$ and so on, see Figure 3. (We will denote an empty word simply by $\infty$, the length of the word usually being clear from the context.) The resulting word $w(\mathbf{q}) = (q_r \circ \dots \circ q_2 \circ q_1)(\infty)$ is called the *output word of $\mathbf{q}$ and has type $\mathbf{m}$*.

The *weight of $\mathbf{q}$*, denoted by $[\mathbf{q}]$, is a monomial in the variables $t_1, \dots, t_r$ defined as the product of the weights of $q_i$ with respect to $(q_{i-1} \circ \dots \circ q_2 \circ q_1)(\infty)$ for $1 \le i \le r$. Also, for any word $w$, define its *weight $[w]$* as the polynomial in $t_1, \dots, t_r$ obtained by adding the weights of all multi-line queues $\mathbf{q}$ with output $w(\mathbf{q}) = w$. Note that letting all $t_i = 1$ in the polynomial $[w]$ gives the number of such multi-line queues. Finally, let $Z_{\mathbf{m}} = Z_{\mathbf{m}}(t_1, \dots, t_r)$ denote the sum of the weights of all multi-line queues of type $\mathbf{m} = (m_1, \dots, m_r)$. (Recall that $n$ is fixed.)

The following theorem has appeared in increasingly stronger versions in [2], [5] and [4]. In [4] the strongest version (given below) is stated as a conjecture. The conjecture has recently been proved in at least two ways [3], [9].
<figure><img src="image_3.png" /><figcaption>Fig. 3: A multi-line queue. The circles correspond to terminal positions in the queues. The output of this multi-line queue is $3\infty1\infty1\infty2$. A number $i$ in a non-terminal position corresponds to a particle $i$ having visited that position first. Thus the weight of this multi-line queue is $t_1^9 t_2^3$.</figcaption></figure>

**Theorem 3.1** *The stationary distribution $\pi$ of the TASEP on $\Omega_m$ with inverse rates $t_1, \dots, t_r$ is given by $\pi(w) = [w]/Z_m$.*

## 4 Two lemmas

In this section we will, for each word $u$, express $[u]$ in terms of various $[v]$'s, where the $v$'s are simpler than $u$.

**Definition 4.1** A type $(m_1, \dots, m_s)$ is simpler than another type $(m'_1, \dots, m'_r)$ if $s < r$, or $s = r$ and $m_s > m'_r$. Let $u, v$ be two words of the same length. We say that $v$ is simpler than $u$ if either

* $v$ has simpler type than $u$, or

* $u$ and $v$ have the same type, and if $i, j$ are the smallest numbers such that $u_i = \infty$ and $v_j = \infty$, then $i > j$.

For any word $w$ of type $m = (m_1, \dots, m_r)$, let $w^-$ denote the word obtained from $w$ by removing all particles of maximal size (that is, replacing all occurrences of $r$ in $w$ by $\infty$). The type of $w^-$ is clearly $(m_1, \dots, m_{r-1})$, which we denote by $m^-$.

**Lemma 4.2** Suppose that $uv$ is a decomposable word of type $m$ and that all maximal particles precede all empty sites in $u$. Then

$$[uv] = \frac{Z_m}{Z_{m^{-}}} [u^{-}v] - \sum_{u'} [u'v],$$

summing over all $u' \neq u$ obtained from $u$ by permuting the particles of maximal size and empty sites. Furthermore, all the words occurring on the right hand side are decomposable and simpler than $uv$.

For example, if $u|v = 3434\infty3|21221$ (the delimiter is for emphasis only), we get the formula $[3434\infty3|21221] = \frac{Z_{2,3,3,2}}{Z_{2,3,3}} [3\infty3\infty\infty3|21221] - [343\infty43|21221] - [3\infty3443|21221]$, where each term on the right hand side is simpler than $uv$. (Using Lemma 6.3, we have $\frac{Z_{2,3,3,2}}{Z_{2,3,3}} = h_{11-(2+3+3+2)}(t_1, t_1, t_2, t_2, t_3, t_3, t_4, t_4, t_4) = t_1 + 3t_2 + 3t_3 + 3t_4$, though the explicit form of this factor is not important for the proof.)

Lemma 4.2 is not very useful by itself. It will, however, work in those (few) cases where Lemma 4.4 below fails.

Let us give some motivation for Lemma 4.4 by looking at an example. Consider the queue of length 10 with non-terminal sites 4 and 9. In Figure 4 we feed it with the word $w' = 21\infty2\infty\infty3\infty31$ and obtain the output word $v = 213\infty2434\infty1$. What would happen if the first site of the queue were non-terminal instead?

The 2-particle that settled at site 1 before will continue to the right until it reaches a non-occupied terminal site. That site could not be site 2 because it is already occupied by a 1-particle (since 1 is less than 2). But the 3-particle that will try to occupy site 3 has not yet arrived so the 2-particle will
<figure><img src="image_4.png" /><figcaption>Fig. 4: The last two lines of two multi-line queues that are identical except the for site 1 in the last row.</figcaption></figure>

stop there. Later, when the 3-particle arrives it finds that site 3 is already occupied so it continues to the right and stops at site 6. Later, when the 4-particle arrives at site 6 it finds it already occupied and continues to the right. Either of the two 4-particles will be unable to find an unoccupied terminal position and the process comes to an end. The output word will be $w = \infty 12 \infty 2334 \infty 1$ and can be obtained from $u$ by the operation $w = v^{1\to}$ defined as follows.

**Definition 4.3** Let $u$ be a word with at least two maximal particles and let $j_0$ be an index such that $u_{j_0} \neq \infty$. Define a sequence $j_1, \dots, j_s$ called the jumping sequence from $j_0$ recursively by letting $j_k$ be the first position cyclically to the right of $j_{k-1}$ such that $u_{j_k}$ is finite and strictly larger than $u_{j_{k-1}}$. If no such position exists, we define $s = k - 1$.

Now define a word $v = u^{j_0\to}$ by letting $v_{j_k} = u_{j_{k-1}}$ for $1 \le k \le s$ and $v_{j_0} = \infty$. The words $v$ and $u$ agree in all other positions.

For example, $155231\infty42^4\to = 145\infty21\infty32$ and $11^{1\to} = \infty 1$.

We stress the remarkable fact (for now just an observation in this particular example) that $w$ is determined by $v$ (and independent of $w'$). However it is not clear what the weight of $[q]$ is in terms of $[p]$; this requires knowing more about $w'$.

Let us turn this relation around and for a fixed $w$ as above ask which $v$ are possible? It happens that there are 18 such $v$'s so let us do this for a smaller example. Suppose instead that $w = \infty 3412 \infty 31$. Then there are two $v$'s satisfying $v^{1\to} = w$: $43412\infty 31$ and $34412\infty 31$. (In Lemma 6.5 we make explicit how to find these words though we will not need it for the proof of Theorem 2.2.) Furthermore, in this smaller example, we can actually determine the weight of $[q]$ in terms of $[p]$: If $v = 43412\infty 31$ then $[q] = t_4[p]$, and if $v = 34412\infty 31$ then $[q] = t_3[p]$ (independently of $w'$).

As we shall see later, the property of $w$ that allows us to read off $[p]$ in terms of $[q]$ is that the first maximal particle in $w$ to the right of the empty site 1 comes before any additional empty site.

Now, the weight of all multi-line queues with bottom row $v$ is counted by $[v]$ on one hand and by $t_4[43412\infty 31] + t_3[34412\infty 31]$ on the other hand, so

$$[\infty 3412 \infty 31] = t_4[43412 \infty 31] + t_3[34412 \infty 31].$$

(The number of multi-line queues representing $\infty 3412 \infty 31$, $43412 \infty 31$ and $34412 \infty 31$ are 624, 136 and 488; we have $624 = 136 + 488$ as predicted by the formula above when we let all $t_i$ equal 1.)

In the next lemma we give the general statement corresponding to the examples above.

**Lemma 4.4** Suppose $uv$ is decomposable, that site $j_0$ in $u$ is empty, and that there is a site $j > j_0$ in $u$ with a maximal particle such that there are no empty sites or maximal particles strictly between $j_0$ and $j$ in $u$.

Then

$$[uv] = \sum t_{u'_{j_0}}[u'v],$$

where the sum extends over all $u'$ such that $u'^{j_0\to} = u$. Moreover, the words $u'v$ occurring on the right hand side are decomposable and simpler than $uv$.
# 5 Finishing the proof

## Proof Proof of Theorem 2.2:

Fix $u_0, v_0, v'_0$ such that $u_0v_0$ is decomposable and $v'_0$ has the same type as $v_0$. By Theorem 3.1 we can work with brackets instead of probabilities, and we want to prove that $\frac{[u_0v_0]}{[u_0v'_0]} = \frac{[\infty v_0]}{[\infty v'_0]}$.

In the course of the proof we will consider decomposable words $uv$ such that $v$ has the same type as $v_0$ and $uv$ is simpler than $u_0v_0$.

Our main goal then will be to derive, for each such $uv$, an identity of the form

$$[uv] = f(u)[\infty v], \qquad (2)$$

where $f(u)$ is some polynomial in the $t_i$'s. The exact form of $f(u)$ is not important, only the fact that it depends only on $u$ and not on $v$. To see that this proves the theorem, note that $[u_0v'_0] = f(u_0)[\infty v'_0]$, which implies the desired conclusion $\frac{[u_0v_0]}{[\infty v_0]} = f(u_0) = \frac{[u_0v'_0]}{[\infty v'_0]}$, or $\frac{[u_0v_0]}{[u_0v'_0]} = \frac{[\infty v]}{[\infty v'_0]}$.

To prove (2), we will for each $uv$ prove an identity of the form

$$[uv] = c_1[u'_1v] + c_2[u'_2v] + \dots, \qquad (3)$$

where all the $u'_i$ are words simpler than $u$. The coefficients $c_i$ are polynomials in the $t_i$'s (actually, for the most they will be simply 1) and they are independent of $v$; recall that we only consider $v$ of same type as the fixed word $v_0$.

Note that there is a unique simplest word of the form $uv_0$ among those simpler than $u_0v_0$, namely $\infty v_0$. Hence, by applying (3) recursively we obtain an identity of the desired form (2).

So it remains to state and prove an identity of the form (3) for each $uv$. The identity will come in two forms, depending on the exact structure of $u$. They are given exactly by Lemmas 4.2 and 4.4; for a given $u$ exactly one of these apply!

□

## Example

Let $v$ be any word of the same type as 122. We give an example of the argument in the proof of the theorem for the decomposable word $534v$.

First we use Lemmas 4.2 and 4.4 to generate a set of identities where the words on the right hand side are simpler than the word on the left hand side. The identities with a term involving $Z_m/Z_{m-}$ are generated by Lemma 4.2, the others from Lemma 4.4. (Here we write $r + 1$ instead of $\infty$ for words of type $m = (m_1, \dots, m_r)$.)

$$[534v] = t_4[434v] + t_3[344v]$$

$$[434v] = t_3[334v]$$

$$[344v] = \frac{Z_{1,2,1}}{Z_{1,2}}[333v] - [434v] - [443v]$$

$$[334v] = \frac{Z_{1,2,2}}{Z_{1,2}}[333v] - [433v] - [343v]$$

$$[434v] = t_3[334v]$$

$$[443v] = t_3[433v] = t_3^2[333v]$$

$$[433v] = t_3[333v]$$

$$[343v] = t_3[333v]$$

Starting from the first equation and then repeatedly substituting to express $[534v]$ in yet simpler words we get $[534v] = (\frac{Z_{1,2,2}}{Z_{1,2}}(t_3t_4 - t_3^2) + \frac{Z_{1,2,1}}{Z_{1,2}}t_3 - 2t_3^2t_4 - t_3^2 - 2t_3^3)[333v]$. Since the parenthesized expression depends only on the type of $v$ we get for example that $[534212]/[333212] = [534221]/[333221]$.

# 6 Explicit formulas

In this section, we make the relations given in Lemmas 4.2 and 4.4 more explicit.
**Lemma 6.1** Let $u$ be any word of type $\mathbf{m} = (m_1, \dots, m_{i-1})$ and let $m_i$ be a positive integer. The sum of the weights with respect to $u$ of all queues of capacity $c = m_1 + \dots + m_i$ is given by

$$h_{n-c} \underbrace{(t_1, \dots, t_1)}_{m_1}, \underbrace{t_2, \dots, t_2)}_{m_2}, \dots, \underbrace{t_{i-1}, \dots, t_{i-1}}_{m_{i-1}}, \underbrace{t_i, \dots, t_i)}_{m_i+1}, \quad (4)$$

where $h_k$ denotes the complete homogeneous symmetric polynomial of degree $k$.

We can compute $Z_{\mathbf{m}}$, the sum of the weights of all multi-line queues of type $\mathbf{m}$, by applying Lemma 6.1 multiple times.

**Theorem 6.2** The sum of the weights of all multi-line queues of type $\mathbf{m} = (m_1, \dots, m_r)$ is given by

$$Z_{\mathbf{m}}(t_1, \dots, t_r) = \prod_{i=1}^{r} h_{n-m_1-m_2-\dots-m_i} \underbrace{(t_1, \dots, t_1)}_{m_1}, \underbrace{t_2, \dots, t_2)}_{m_2}, \dots, \underbrace{t_{i-1}, \dots, t_{i-1}}_{m_{i-1}}, \underbrace{t_i, \dots, t_i)}_{m_i+1}.$$

Theorem 6.2 appeared first in [1].

Now we can give an explicit formula for the quantity $Z_{\mathbf{m}}/Z_{\mathbf{m}^-}$ occurring in Lemma 4.2.

**Corollary 6.3** Let $\mathbf{m} = (m_1, \dots, m_r)$ be a type, and $e = n - m_1 - \dots - m_r$ be the number of empty sites. Then

$$\frac{Z_{\mathbf{m}}}{Z_{\mathbf{m}^{-}}} = h_e \underbrace{(t_1, \dots, t_1)}_{m_1}, \underbrace{t_2, \dots, t_2)}_{m_2}, \dots, \underbrace{t_{r-1}, \dots, t_{r-1}}_{m_{r-1}}, \underbrace{t_r, \dots, t_r)}_{m_r+1}.$$

Finally, we show how to invert the $\rightarrow$ operation, that is, for a fixed $u$ with $u_1 = \infty$, finding all $v$ such that $v^{1\rightarrow} = u$.

**Definition 6.4** Suppose $w$ is a word where site 1 is empty. For a subset of sites $J = \{j_1 < \dots < j_s\}$ with $w_j \neq \infty$ for all $j \in J$, define a word $v = w^{\leftarrow J}$ by letting $v_1 = w_{j_1}$, and $v_{j_k} = w_{j_{k+1}}$ for $0 \le k < s$. All other entries of $v$ and $w$ are the same.

Note that if $u = v^{1\rightarrow}$ then $v = u^{\leftarrow J}$ for some $J$ (namely the jump sequence considered as a set).

It is easy to characterize the possible $J$. Essentially, we just have to check how the inequalities of Definition 4.3 among the jumping entries of $v$ transform into inequalities among entries of $v^{1\rightarrow}$.

**Lemma 6.5** Let $u, v$ be two words and suppose $v_1 = \infty$. Then $u^{1\rightarrow} = v$ if and only if $u = v^{\leftarrow J}$ for some $J = \{j_1 < \dots < j_s\}$ satisfying the following properties

* $v_j \neq \infty$ for each $j \in J$,

* for $1 \le k \le s$, the entry $v_{j_k}$ is larger than or equal to each preceding finite entry, and

* $v_{j_1} < \dots < v_{j_s} < r$, where $r$ is the maximal particle size in $v$.

Another way of saying this is the following. Let $W$ be the set of positions of non-maximal entries in $v$ that are greater than or equal to all preceding finite entries. The sets $J$ described in Lemma 6.5 are precisely those subsets of $W$ such that all $v_j$, $j \in J$ are distinct. In particular, if the $a_i$ denotes the number of $k$ such that $v_{j_k} = i$, then the number of possible $J$ is $\prod_i (1 + a_i)$.

# 7 Open questions and a conjecture

Our independence result, Corollary 2.3, is a natural probabilistic statement; in fact, as we discussed earlier, one is easily mislead to believe that it is obvious. However, our proof is far less natural as it depends on the theory of multi-line queues and makes use of indirect recurrence relations. It would be desirable to have a more probabilistic proof not involving multi-line queues but focusing on the Markov process itself.
As we saw from the inequality (1), when the large and small entries are not separated, their orders are correlated. It would be interesting to quantify this correlation and bound it. In general, given the positions and the order of the small entries in a random word sampled from $\pi$, what can be said about the large ones? As a possible partial answer to that question, we offer the following conjecture.

**Conjecture 7.1** Let $\mathbf{m} = (1, 1, \dots, 1)$ be the type of the permutation word $12\cdots n$ and let $W$ be a random permutation sampled from the stationary distribution on $\Omega_{\mathbf{m}}$. Conditioned on the event that the $k$ smallest entries in $W$ are in some predefined positions in some predefined order, the most probable order among the $n-k$ largest entries is cyclically ascending and their least probable order is cyclically descending.

For instance, let us say that I draw a random permutation $W$, tells you that it happens to be of the form $W = *3*4**21$ (where the stars are placeholders for larger entries) and ask you what you think about the order of the entries 5 to 8. Your best guess would be to replace the stars with a cyclic shift of 5678, in fact the most probable among those guesses are 73845621. Your worst possible guess would be 63548721.

The conjecture has been checked in the homogeneous case ($t_1 = \cdots = t_r$) by a computer up to $n = 10$.

## References

[1] Erik Aas, Stationary probability of the identity for the TASEP on a ring, arXiv:1212.6366

[2] Omer Angel, The stationary measure of a 2-type totally asymmetric exclusion process, *J. Comb. Theory A* 113 (2006), 625–635.

[3] Chikashi Arita and Kirone Mallick: Matrix product solution to an inhomogenous multi-species TASEP. arXiv:1209.1913

[4] Arvind Ayyer and Svante Linusson, An inhomogenous multispecies TASEP on a ring. arXiv:1206.0316

[5] Pablo Ferrari and James Martin, Stationary distributions of multi-type totally asymmetric exclusion processes, *Ann. Prob.* 35 (2007) 807–832.

[6] Thomas Lam, The shape of a random affine Weyl group element, and random core partitions. arXiv:1102.4405

[7] Thomas Lam and Lauren Williams, A Markov chain on the symmetric group which is Schubert positive?, *Experimental Mathematics* 21 (2012), 189–192.

[8] Thomas Liggett, Interacting Particle Systems. Springer-Verlag (1985).

[9] Svante Linusson and James Martin, Stationary probabilities for an inhomogeneous multi-type TASEP, in preparation.