Some Examples of Dynamics for Gelfand Tsetlin Patterns

Introduction

In , the authors Baik, Deift and Johansson show that suitably rescaled, the law of the longest increasing subsequence of a uniformly chosen random permutation of $\{1,2,\ldots,n\}$ converges, as $n$ tends to infinity, to that of the Tracy-Widom distribution. The latter, first identified in , describes the typical fluctuations of the largest eigenvalue of a large random Hermitian matrix from the Gaussian unitary ensemble (see for a definition). This somewhat surprising discovery has been followed by much research which has shown that the Tracy-Widom distribution also occurs as a limiting law in various other models such as last passage percolation , exclusion processes , random tilings and polynuclear growth . See also the survey .

Eigenvalues of random matrices are closely related to multi-dimensional random walks whose components are conditioned not to collide. In particular, both fall into a class of processes with determinantal correlation structure and exhibit pairwise repulsion at a distance. On the other hand, models such as the exclusion process are defined by local “hard edged” interactions rather than particles repelling each other remotely. This paper is concerned with showing how it is possible to connect these two types of model by coupling processes of one class with processes from the other.

In common with previous works in this area, we realise these couplings via the construction of a stochastic process in the Gelfand-Tsetlin cone

Description of dynamics and results

Fix a vector of rates $q\in(0,\infty)^{n}$ and identify each particle with its corresponding component in $\mathfrak{X}$. The particle $\mathfrak{X}_{1}^{1}$ jumps rightwards at rate $q_{1}>0$, i.e. after an exponentially distributed waiting time of mean $q_{1}^{-1}$. The two particles, $\mathfrak{X}^{2}_{1},\mathfrak{X}^{2}_{2}$ corresponding to the second row of the pattern each jump rightwards at rate $q_{2}$ independently of $\mathfrak{X}^{1}_{1}$ and each other unless either

$\mathfrak{X}_{1}^{2}(t)=\mathfrak{X}_{1}^{1}(t)$, in which case any rightward jump of $\mathfrak{X}^{2}_{1}$ is suppressed (blocked), or

$\mathfrak{X}_{2}^{2}(t)=\mathfrak{X}_{1}^{1}(t)$, in which case $\mathfrak{X}_{2}^{2}$ will be forced to jump (pushed) if $\mathfrak{X}^{1}_{1}$ jumps.

is harmonic for $Z$ killed at the first instant it leaves $\mathcal{W}^{n}$ (see for example). Hence, $h$ may be used to define a new process, $Z^{\dagger}$, with conservative $Q$-matrix on $\mathcal{W}^{n}$ defined by

where $e_{i}$ is the standard basis vector, and the other off diagonal rates in $Q$ are zero.

This Doob $h$-transform, $Z^{\dagger}$, may be interpretted as a version of $Z$ conditioned not to leave $\mathcal{W}^{n}$ and is closely related to the Charlier orthogonal polynomial ensemble (again see ).

In section 3 we prove the following result, obtained independently by Borodin and Ferrari by another method in .

If $(\mathfrak{X}(t);\;t\geq 0)$ has initial distribution $M_{z}(\cdot)$ for some $z\in\mathcal{W}^{n}$ then $(\mathfrak{X}^{n}(t);\;t\geq 0)$ is distributed as an $n$ dimensional Markov process with conservative $Q$-matrix

and all other off diagonal entries set to zero, started from $z$.

Note that from structure of the initial distribution and the construction of $\mathfrak{X}$, this theorem implies that in fact every row of the pattern is distributed as a conditioned Markov process of appropriate dimension and rates.

Theorem 2.1 readily yields a coupling of the type discussed in the introduction – the (shifted) left hand edge $(\mathfrak{X}^{1}_{1}(t),\mathfrak{X}^{2}_{1}(t)-1,\ldots,\mathfrak{X}^{n}_{1}(t)-n+1;t\geq 0)$ of $\mathfrak{X}$ has the same “hard edged” interactions as an asymmetric exclusion process (the particle with position $\mathfrak{X}^{k}_{1}(t)-k+1$, $1\leq k\leq n$ takes unit jumps rightwards at rate $q_{k}$ but is barred from occupying the same site as any particle to its right). However, Theorem 2.1 implies that $(\mathfrak{X}^{n}_{1}(t);t\geq 0)$ has the same law as $(Z^{\dagger}_{1}(t);t\geq 0)$, the first component of the random walk $Z$ conditioned to stay in $\mathcal{W}^{n}$, when started from $Z^{\dagger}(0)=z$. Further we observe that when $z=(0,\ldots,0)$, $M_{z}$ is concentrated on the origin and a version of the left hand edge can be constructed from the paths of $Z$ via $\mathfrak{X}^{1}_{1}(t)=Z_{1}(t)$ and

Iterating this expression and appealing to Theorem 2.1,

This identity was previously derived by O’Connell and Yor in using a construction based on the Robinson-Schensted-Knuth correspondence.

2 Geometric jumps

Let $q$ be a fixed vector in $(0,1)^{n}$ and update the pattern at time $t$ beginning with the top particle by setting $\mathfrak{X}^{1}_{1}(t+1)=\mathfrak{X}^{1}_{1}(t)+\xi$, where $\xi$ is a geometric random variable with mean $(1-q_{1})/q_{1}$. That is, the top most particle always takes geometrically distributed jumps rightwards without experiencing pushing or blocking.

The Markov process with transition kernel $p$ can be described by a Doob $h$-transform - suppose $Z$ is now a discrete time random walk beginning at $z\in\mathcal{W}^{n}$ in which the $k^{th}$ component makes a geometric($q_{k}$) rightward jump at each time step, independently of the other components. Then the function $h$ defined in (2.3) is harmonic for $Z$ killed at the instant that the interlacing condition $Z(t)\prec Z(t+1)$ fails to hold (see ). The corresponding $h$-transform $Z^{\dagger}$ is the discrete analogue of a process that arises from eigenvalues of Wishart matrices .

As a consequence, Theorem 2.2 provides a new proof that such last passage percolation times have the same distribution as the rightmost particle in the conditioned process $Z^{\dagger}$ (the distribution of which, at a fixed time, is given by the Meixner ensemble – see Johansson or ). This is a key step in obtaining the Tracy-Widom distribution in this setting.

Note that the dynamics discussed above are different to those exhibited in for geometric jumps. In particular, the particles in the process we described above are blocked by the position of the particle immediately above and to the right of them at the previous time step.

3 With wall at the origin

The final example of the paper uses the ideas introduced above to construct a continuous time process $(\mathfrak{X}(t);\;t\geq 0)$ on a symplectic Gelfand-Tsetlin cone. The latter are so termed because they are in direct correspondence with the symplectic tableau arising from the representations of the symplectic group .

$x^{2i-1}\prec x^{2i}$ for $1\leq i\leq\lfloor\frac{n}{2}\rfloor$,

$x^{2i}\preceq x^{2i+1}$ for $1\leq i\leq\lfloor\frac{n-1}{2}\rfloor$.

So the all the points in a symplectic pattern lie to the right of an impenetrable wall at the origin, represented diagrammatically below.

Fix $q\in(0,1)^{n}$. The top particle $\mathfrak{X}^{1}_{1}$ jumps right at rate $q_{1}$ and left at rate $q^{-1}_{1}$, apart from at origin where its left jumps are suppressed. The second row also only has one particle, $\mathfrak{X}^{1}_{2}$, which jumps rightwards at rate $q_{1}^{-1}$ and leftwards at rate $q_{1}$ (notice rates are reversed), except at instances when $\mathfrak{X}^{1}_{1}(t)=\mathfrak{X}^{2}_{1}(t)$. In the latter case, it is pushed rightwards if $\mathfrak{X}^{1}_{1}$ jumps to the right and any leftward jumps are suppressed.

The remaining particles evolve in a similar fashion – on row $2k-1$, particles take steps to the right at rate $q_{k}$ and left at rate $q^{-1}_{k}$ when they are not subject to the blocking or pushing required to keep the process in the state space, in particular $\mathfrak{X}^{2k-1}_{1}$ has any leftward jump from the origin suppressed. On row $2k$, the rates are reversed but the same blocking and pushing mantra applies.

We will deduce that for appropriate initial conditions, the marginal distribution of each row $(\mathfrak{X}^{k}(t);t\geq 0)$ is a Markov process. The $Q$-matrices for the marginal processes can be written in terms of symplectic Schur functions, the definition of which is similar to that of the classic Schur function (2.1) – they are sums over geometrically weighted symplectic Gelfand-Tsetlin patterns.

using the convention that $|x^{0}|=0$ and empty products are equal to 1 (so $w_{1}^{(q_{1})}(x)=q_{1}^{|x^{1}|}$).

For even $n$, $Sp^{n}$ gives the characters of irreducible representations of the symplectic group $Sp(n)$ . For odd $n$, $Sp^{n}$ was introduced by Proctor and can interpretted as the character of the irreducible representations of a group that interpolates between the classical groups $Sp(n)$ and $Sp(n+1)$ .

All other off diagonal entries vanish and the diagonals are given by

A corollary of the intertwinings we prove in sections 5.1 and 5.2 is that $Q_{n}$ is conservative.

Suppose $\mathfrak{X}$ has initial distribution given by $M^{n}_{z}(\cdot)$, then $(\mathfrak{X}^{n}(t);t\geq 0)$ is distributed as a Markov process with $Q$-matrix $Q_{n}$, started from $z$.

The relevance of this theorem to the discussion in the introduction may again be seen by examining the evolution of the right hand edge of $\mathfrak{X}$. Suppose we have a system of $n$ particles with positions $(\mathfrak{X}^{1}_{1}(t),\mathfrak{X}^{2}_{1}(t)+1,\mathfrak{X}^{3}_{2}(t)+2,\ldots,\mathfrak{X}_{\lfloor(n+1)/2\rfloor}^{n}(t)+n-1;t\geq 0)$.

Particle $i>1$ attempts to jump rightwards at rate $\gamma_{i}=q_{(i+1)/2}$ if $i$ is odd or $\gamma_{i}=q^{-1}_{i/2}$ if $i$ is even and leftwards at rate $\gamma^{-1}_{i}$. An attempted left jump succeeds only if the destination site is vacant, otherwise it is suppressed. A rightward jump always succeeds, and, any particle occupying the destination site is pushed rightwards. A particle being pushed rightwards also pushes any particle standing in its way, so a rightward jump by a particle could cause many particles to be pushed. So far we have essentially described the dynamics of the “PushASEP” process introduced in . Our process differs by the presence of a wall: the leftmost particle (identified with $\mathfrak{X}^{1}_{1}$) is modified so that any leftward jump at the origin suppressed. Also, the particle rates are restricted in that for odd $i$, the jump rates of particle $i$ and $i+1$ are inverses of each other (which is not the case in ).

As in the previous examples, the bottom row $(\mathfrak{X}^{n}(t);t\geq 0)$ may be realised as a Doob $h$-transform and we deduce identities analogous to (2.4) and (2.5). For simplicity, we shall only consider the case that $n=2k$. The case of odd $n$ can be treated with similar arguments but it is complicated slightly due to the non-standard behaviour of $\mathfrak{X}_{1}^{n}$ at the wall.

Let $Z$ be a $k$-dimensional random walk in which the $i^{th}$ component jumps rightwards at rate $q^{-1}_{i}$ and leftwards at rate $q_{i}$. It is readily seen that $Q_{2k}$ is the $Q$-matrix of $Z^{\dagger}$, the $h$-transform of $Z$ killed on leaving $\mathcal{W}_{0}^{k}$ under harmonic functions

Theorem 2.3 shows that $\left(Z^{\dagger}_{k}(t);t\geq 0\right)$ has the same law as $\left(\mathfrak{X}^{2k}_{k}(t);t\geq 0\right)$ when $\mathfrak{X}$ is initially distributed according to $M^{2k}_{z}$ and $Z(0)=z\in\mathcal{W}_{0}^{k}$.

The Brownian analogue of this result will be considered in .

Proof of Theorem 2.1

To this end, we assume for induction that the conclusion of 2.1 holds. Then, when $\mathfrak{X}(0)$ is distributed according to $M_{z}(\cdot)$, the bottom layer $(\mathfrak{X}^{n}(t);t\geq 0)$ is Markovian and evolves according to the conservative $Q$-matrix $Q_{X}$ defined via

and all other off diagonal entries set to zero.

for some $q_{n+1}>0$, and all other off diagonal entries vanish. The diagonal entries are given by

Appropriate dynamics for $(X,Y)$ are specified by the conservative $Q$-matrix $\mathcal{A}$ with off diagonal entries given by

for $(x,y),(x^{\prime},y^{\prime})\in\mathcal{W}^{n,n+1}$ and $1\leq i\leq n$, $1\leq j\leq n+1$. The diagonal entry $-\mathcal{A}((x^{\prime},y^{\prime}),(x^{\prime},y^{\prime}))$ is given by

Now, as an immediate consequence of the definition of the Schur function in (2.1), we have

So the marginal distribution of the penultimate row of particles under the initial distribution defined in (2.2) is given by $m(\cdot,y)$ where $y\in\mathcal{W}^{n+1}$ is fixed and $m:\mathcal{W}^{n,n+1}\to$ is defined by

defines a Markov kernel from $\mathcal{W}^{n+1}$ to $\mathcal{W}^{n,n+1}$. That is, for each $y\in\mathcal{W}^{n+1}$, $\Lambda(y,\cdot)$ defines a probability distribution on $\mathcal{W}^{n,n+1}$.

The heart of our proof is showing that the conservative $Q_{Y}$ is intertwined with $\mathcal{A}$ via $\Lambda$,

From here, lemma A.1 shows that $\Lambda$ intertwines the corresponding transition kernels. That is, if $(p_{t};t\geq 0)$ are the transition kernels corresponding to $Q_{Y}$ and $(q_{t};t\geq 0)$ those to $\mathcal{A}$, then for $y\in\mathcal{W}^{n+1}$, $(x^{\prime},y^{\prime})\in\mathcal{W}^{n,n+1}$ and $t\geq 0$,

This is essentially the argument of Rogers and Pitman and establishes

Suppose $(X(t),Y(t);t\geq 0)$ is a Markov process with $Q$-matrix $\mathcal{A}$ and initial distribution $\Lambda(y,\cdot)$, for some $y\in\mathcal{W}^{n+1}$. Then $Q_{Y}$ and $\mathcal{A}$ are interwined via $\Lambda$ and as a consequence, $(Y(t);t\geq 0)$ is distributed as a Markov process with $Q$-matrix $Q_{Y}$, started from $y$.

where the summation is over the points $x$ in $\mathcal{W}^{n}$ that interlace with $y$. As the particles can only make unit jumps rightwards, both sides of the expression vanish unless either $y^{\prime}=y$ or $y^{\prime}=y+e_{j}$, for some $1\leq j\leq n+1$.

We first consider the case when $y=y^{\prime}$, corresponding to the diagonal entries of $Q_{Y}$. The right hand side of the expression is

Using the definition of $m$, this becomes

Now, $\mathcal{A}((x,y^{\prime}),(x^{\prime},y^{\prime}))$ is non zero for $x\preceq y^{\prime}$ only if $x=x^{\prime}$ or $x=x^{\prime}-e_{i}$ for some $1\leq i\leq n$. When $x=x^{\prime}$, $-\mathcal{A}((x,y^{\prime}),(x^{\prime},y^{\prime}))$ is the rate of leaving at $(x^{\prime},y^{\prime})$, given in (3.1). On the other hand if $x=x^{\prime}-e_{i}$, $\mathcal{A}((x,y^{\prime}),(x^{\prime},y^{\prime}))$ is the rate at which the $i^{th}$ $X$ particle jumps rightwards (without pushing a $Y$ particle). But, such values of $x$ are included in the summation only if $x=x^{\prime}-e_{i}\preceq y=y^{\prime}$, i.e. $x_{i}^{\prime}>y_{i}^{\prime}$.

Combining this with (3.5) and (3.1) and the fact that $q_{n+1}^{|x^{\prime}|-|x^{\prime}-e_{i}|}=q_{n+1}$, we see that if $y=y^{\prime}$ the right hand side of (3.4) is

so the first and last summations above disappear and we are left with $-\sum_{i=1}^{n+1}q_{i}$, which is exactly $Q_{Y}(y^{\prime},y^{\prime})$.

If $y\neq y^{\prime}$, the only other possibility is that $y^{\prime}=y+e_{i}$ for some $1\leq i\leq n+1$. Let us first deal with the simplest case, where $i=1$, that is, $y^{\prime}=y+e_{1}$. The only value of $x$ for which $\mathcal{A}((x,y^{\prime}-e_{1}),(x^{\prime},y^{\prime}))$ is non zero is $x=x^{\prime}$ as the first $Y$ particle is never pushed by an $X$ particle. Furthermore, $y^{\prime}_{1}-1<y^{\prime}_{1}\leq x^{\prime}_{1}$ and so the jump of $Y_{1}$ is certainly not blocked. Hence,

For $i>1$, consider the dichotomy $x^{\prime}_{i-1}<y^{\prime}_{i}$ or $x^{\prime}_{i-1}=y^{\prime}_{i}$. Suppose we are in the former case, i.e. $y^{\prime}=y+e_{i}$ and $x^{\prime}_{i-1}<y^{\prime}_{i}$. It is not possible that the movement in the $i^{th}$ component of $Y$ could have been instigated due to pushing by the $(i-1)^{th}$ $X$ particle (a push could only have occurred if $x^{\prime}_{i-1}-1=y^{\prime}_{i}-1$). Thus, as in the $i=1$ case above, $\mathcal{A}((x,y^{\prime}-e_{i}),(x^{\prime},y^{\prime}))$ is non zero only for $x=x^{\prime}$ and almost identical calculations verify (3.4).

The second $i>1$ subcase is that $x^{\prime}_{i-1}=y^{\prime}_{i}$ and $y=y^{\prime}-e_{i}$. Here the only possibility is that the $i^{th}$ $Y$ particle “did not jump but was pushed”, which one may confirm by noting that $x^{\prime}$ does not interlace with $y^{\prime}-e_{i}$ when $x^{\prime}_{i-1}=y^{\prime}_{i}$. So, the right hand side of (3.4) is given by

Using the definitions of $m$ and $\mathcal{A}$, this becomes

a quantity which is easily seen to equal $Q_{Y}(y^{\prime}-e_{i},y^{\prime})$.

This concludes the proof that $Q_{Y}$ and $\mathcal{A}$ are intertwined via $\Lambda$.

Proof of Theorem 2.2

It is again sufficient to consider any pair of consecutive rows $(X,Y)$ and construct the process iteratively.

The recursion encodes the blocking and pushing mechanism, maintaining the initial interlacing relationship, so $X(t)\prec Y(t)$ for each $t$.

We will prove that if $\Lambda$ is as defined in (3.2) then

If $(X,Y)$ is initially distributed according to $\Lambda(y,\cdot)$, $y\in\mathcal{W}^{n+1}$, and then evolves according to the recursion above, the marginal process $(Y(t);t\geq 0)$ is distributed as an $n+1$ dimensional Markov process with transition kernel

Our strategy, again, is to prove that $\Lambda$ interwines the corresponding transition probabilities. Suppose $(x,y),(x^{\prime},y^{\prime})\in\mathcal{W}^{n,n+1}$, $x\prec x^{\prime}$ and $y\prec y^{\prime}$. Let us write down $q((x,y),(x^{\prime},y^{\prime}))$, the one step transition probabilities for $(X,Y)$. Firstly note that

Then $r(y^{\prime},x^{\prime},x,y)$ is equal to

To prove the theorem we will need the following “integrating out” lemma.

The lemma may be understood more readily by imagining that we are considering the $n=1$ case, so that there is one “$X$” particle nestled between two “$Y$” particles. We may fix the initial and final positions of the “$Y$” particles ($v$ and $v^{\prime}$ in the lemma above) and also the final position of the “$X$” particle ($u$ in the lemma) – it is the starting location of the $X$ particle that we are integrating out. The summation is over the possible values that the $X$ particle may have started from. It must be at least equal to the final position of the left most $Y$ particle $v_{1}^{\prime}$, as this particle cannot overtake the $X$ particle (see recursion equations above). Also, it cannot exceed either the initial position of the second $Y$ particle $v_{2}$ (due to the interlacing constraint) or the final position of the $X$ particle $u^{\prime}$ (as the particles may only jump rightwards).

After using the definitions of $b$ and $c$, the sum becomes

Now expand the brackets in the summand and sum the terms individually. We find

Summing the above expressions gives the result. ∎

The interesting thing about this scheme, as we will see in a moment, is that we may apply it successively from left to right when there are $n$ particles so that the leftmost particles get heavier and heavier until we have reduced the problem to the $n=1$ case.

When the initial distribution is $\Lambda(y,\cdot)$, the joint distribution after one time step is given by

Expanding the sum and incorporating the conditions $y_{i}^{\prime}\leq x_{i}$ and $x\prec x^{\prime}$ into the summation indices yields

for $x\preceq y,x^{\prime}\preceq y^{\prime},x\prec x^{\prime},y\prec y^{\prime}$ and vanishes elsewhere.

Now, one notices that we may use lemma 4.2 to iteratively evaluate the summation over $x_{1},x_{2},\ldots,x_{n}$ (in that order). More concretely, first apply the lemma with $u^{\prime}=x_{1}^{\prime},v=(y_{1},y_{2}),v^{\prime}=(y_{1}^{\prime},y_{2}^{\prime})$ to reveal that the sum $\sum_{x_{1}=y_{1}^{\prime}}^{y_{2}\wedge x_{1}^{\prime}}m(x,y)Q((x,y),(x^{\prime},y^{\prime}))$ is equal to

This expression is again in a suitable form to apply lemma 4.2, but this time with $u^{\prime}=x_{2}^{\prime},v=(y_{2},y_{3}),v^{\prime}=(y_{2}^{\prime},y_{3}^{\prime})$ and summing over $x_{2}$. Continuing in this fashion shows that (4.2) is equal to

and Theorem 4.1 follows from the argument of discussed in the previous section.

Proof of Theorem 2.3

As in the previous two examples, we give a row by row construction. This time the asymmetry between odd rows and even rows means we have to specify how to iterate from even rows to odd rows and odd rows to even rows separately (presented below in 5.1 and 5.2 respectively).

En route to proving Theorem 2.3, we need to conclude that $Q_{n}$ is a conservative $Q$-matrix for each $n$.

This will be achieved by an inductive argument. Let H($n$) denote the hypothesis that $Q_{n}$ is a conservative $Q$-matrix. It is easy to establish H(1), that $Q_{1}$ is conservative – recall that for $x_{1}\geq 0$, $Sp^{1}_{(x_{1})}=q_{1}^{x_{1}}$ so

a quantity equal to zero, and the off diagonal entries are clearly positive.

Under the assumption that H($2n-1$) holds we will define a conservative $Q$-matrix $\mathcal{A}_{0}$ on $\mathcal{W}^{n,n}_{0}=\{(x,y)\in\mathcal{W}^{n}_{0}\times\mathcal{W}^{n}_{0}:x\prec y\}$ in terms of $Q_{2n-1}$ and prove the intertwining relationship

where $\Lambda$ is a Markov kernel. Expanding the intertwining and summing both sides shows that $\sum_{x^{\prime}}Q_{2n}(x,x^{\prime})=0$, so we conclude that H($2n$) holds as well. The step from H($2n$) to H($2n+1$) follows a similar argument.

Suppose H($2n-1$) holds and identify $Q_{X}\equiv Q_{2n-1}$. Introduce a $Q$-matrix $\mathcal{A}_{0}$ on $\mathcal{W}^{n,n}_{0}$ with off diagonal entries defined by

for $(x,y),(x^{\prime},y^{\prime})\in\mathcal{W}^{n,n}_{0}$, $1\leq i<n$, $1\leq j\leq n$. The diagonal entry $-\mathcal{A}_{0}((x,y),(x,y))$ is given by

so under the assumption that $Q_{X}$ is conservative, $\mathcal{A}_{0}$ is also conservative.

Note that the geometric factor is now $q_{n}^{|x|-|y|}$ instead of the usual $q_{n}^{|y|-|x|}$. By definition (2.6),

Hence, $m$ gives a Markov kernel $\Lambda$ from $\mathcal{W}^{n}_{0}$ to $\mathcal{W}^{n,n}_{0}$ defined by

Assume $Q_{2n-1}$ is a conservative $Q$-matrix and $(X(t),Y(t);t\geq 0)$ is a Markov process with $Q$-matrix $\mathcal{A}_{0}$ and initial distribution $\Lambda(y,\cdot)$ for some $y\in\mathcal{W}^{n}_{0}$. Then $Q_{2n}$ is a conservative $Q$-matrix and $(Y(t);t\geq 0)$ is distributed as a Markov process with $Q$-matrix $Q_{2n}$, started from $y$.

Suppose $Q_{Y}\equiv Q_{2n}$, then as usual we prove an intertwining relationship

where the sum is over $x\in\mathcal{W}^{n}_{0}$ such that $(x,y)\in\mathcal{W}^{n,n}_{0}$.

Particles may take unit steps in either direction so we need to check the equality (5.2) holds for $y=y^{\prime}$, $y=y^{\prime}+e_{j}$ and $y=y^{\prime}-e_{j}$ for some $1\leq j\leq n$.

Let us first consider the case $y=y^{\prime}$. When $x=x^{\prime}$, $-\mathcal{A}_{0}((x,y),(x^{\prime},y^{\prime}))$ is the rate of leaving $(x^{\prime},y^{\prime})$ and is given by (5.1). The only other possible values of $x$ in the summation for which the summand is non-zero are $x=x^{\prime}\pm e_{i}$, $1\leq i\leq n$. For such values (i.e. if $(x^{\prime}\pm e_{i},y)\in\mathcal{W}^{n,n}_{0}$), the summand is

which is a rather fancy way of writing $q_{n}^{\pm 1}$. But, for $(x^{\prime},y^{\prime})\in\mathcal{W}^{n,n}_{0}$,

$(x^{\prime}+e_{i},y^{\prime})\in\mathcal{W}^{n,n}_{0}$ only if $x^{\prime}_{i}<y^{\prime}_{i}$

$(x^{\prime}-e_{i},y^{\prime})\in\mathcal{W}^{n,n}_{0}$, $i>1$ only if $x^{\prime}_{i}>y^{\prime}_{i-1}$

$(x^{\prime}-e_{1},y^{\prime})\in\mathcal{W}^{n,n}_{0}$, only if $x^{\prime}_{1}>0$.

On subtracting the rate of leaving $-\mathcal{A}_{0}((x^{\prime},y^{\prime}),(x^{\prime},y^{\prime}))$ defined in (5.1) we find that the indicator functions all cancel and the right hand side of (5.2) is

Next we consider the case that $y^{\prime}=y-e_{i}\in\mathcal{W}^{n}_{0}$. If $i=n$, the only possibility is that the $Y$ particle jumped by itself. When $i<n$, the only possibilities are that the $i^{th}$ component of $Y$ was pushed by the $(i+1)^{th}$ component of $X$ (i.e. $x=x^{\prime}+e_{i+1}$) or it jumped by its own volition (i.e. $x=x^{\prime}$). The former only occurs if $y^{\prime}_{i}=x^{\prime}_{i+1}$, while the latter can only occur if $y^{\prime}_{i}<x^{\prime}_{i+1}$, inducing a natural partition on the values we have to check the intertwining on. When $y^{\prime}=y-e_{i}$, $y^{\prime}_{i}<x^{\prime}_{i+1}$, $i<n$, or $i=n$, the right hand side of (5.2) is

When $y^{\prime}=y-e_{i}$, $x^{\prime}_{i+1}=y^{\prime}_{i}$, $i<n$, the sum on the right hand side of the intertwining involves a single term,

Using the definitions of $m$ and $Q_{X}$ shows this summand is

Both of these quantities are equal to $Q_{Y}(y^{\prime}+e_{i},y)$.

Finally we consider the case $y^{\prime}=y+e_{i}$, $1\leq i\leq n$. As in the previous case, the dichotomy $x^{\prime}_{i}=y^{\prime}_{i}$ and $x^{\prime}_{i}<y^{\prime}_{i}$ divides the possible values of $x$ in the summation into two cases, each of which having only one term contributing to the sum. When $x^{\prime}_{i}=y^{\prime}_{i}$, the $i^{th}$ $Y$ particle must have been pushed, and

Simplifying the expression on the right hand side by cancelling common factors in the numerator and denominator reveal it to be simply $Q_{Y}(y^{\prime}-e_{i},y)$.

On the other hand, when $x^{\prime}_{i}<y^{\prime}_{i}$ the $i^{th}$ $Y$ particle cannot have been pushed so the right hand side of the intertwining (5.2) is

The proof of the intertwining relationship is concluded by noting that this is $Q_{Y}(y^{\prime}-e_{i},y)$ as required.

Now, summing both sides of the intertwining

over all pairs in $(x^{\prime},y^{\prime})$ in $\mathcal{W}^{n,n}_{0}$ shows that $Q_{Y}$ is conservative as $\sum_{x^{\prime}}m(x^{\prime},y^{\prime})=1$ and $\sum_{(x^{\prime},y^{\prime})}\mathcal{A}_{0}((x,y),(x^{\prime},y^{\prime}))=0$.

We then apply lemma A.1 to recover the rest of the theorem.

2 Part II: Iterating from an even row to an odd

Suppose $Q_{X}\equiv Q_{2n}$, $Q_{Y}\equiv Q_{2n+1}$ and $\mathcal{A}_{0}$ is a conservative $Q$-matrix $\mathcal{A}_{0}$ on $\mathcal{W}^{n,n+1}_{0}=\{(x,y)\in\mathcal{W}^{n}_{0}\times\mathcal{W}^{n+1}_{0}:x\preceq y\}$ with off diagonal entries given by

for $(x,y),(x^{\prime},y^{\prime})\in\mathcal{W}^{n,n+1}_{0}$, $1\leq i\leq n$, $1\leq j\leq n+1$. The diagonal $-\mathcal{A}_{0}((x,y),(x,y))$ is given by

Hence $\mathcal{A}_{0}$ is conservative if $Q_{X}$ is.

So the function $m:\mathcal{W}^{n,n+1}_{0}\to$ given by

induces a Markov kernel from $\mathcal{W}^{n+1}_{0}$ to $\mathcal{W}^{n,n+1}_{0}$,

Assume $Q_{2n}$ is a conservative $Q$-matrix and suppose $(X(t),Y(t);t\geq 0)$ is a Markov process with $Q$-matrix $\mathcal{A}_{0}$ and initial distribution $\Lambda(y,\cdot)$ for some $y\in\mathcal{W}^{n+1}_{0}$. Then $Q_{2n+1}$ is a conservative $Q$-matrix and $(Y(t);t\geq 0)$ is distributed as a Markov process with $Q$-matrix $Q_{2n+1}$, started from $y$.

The intertwining via $\Lambda$ is equivalent to

where we sum over $x$ such that $(x,y)\in\mathcal{W}^{n,n+1}_{0}$.

We only need to check (5.4) holds for $y$ of the form $y=y^{\prime}$, $y=y^{\prime}\pm e_{j}$ for $1\leq j\leq n+1$ as both sides vanish otherwise.

Again we start with the case $y^{\prime}=y$. When $x=x^{\prime}$, the rate of leaving $-\mathcal{A}_{0}((x^{\prime},y^{\prime}),(x^{\prime},y^{\prime}))$ is given by (5.3). The only other possible values of $x$ for which the summand is non-zero are $x=x^{\prime}\pm e_{i}$ for $1\leq i\leq n$. For such $x$ values satisfying $(x,y)\in\mathcal{W}^{n,n+1}_{0}$, the definitions of $m$ and $Q_{X}$ give

which is equal to $q_{n+1}^{\mp 1}$. But, for $(x^{\prime},y^{\prime})\in\mathcal{W}^{n,n+1}_{0}$,

$(x^{\prime}+e_{i},y^{\prime})\in\mathcal{W}^{n,n+1}_{0}$ only if $x^{\prime}_{i}<y^{\prime}_{i+1}$ and

$(x^{\prime}-e_{i},y^{\prime})\in\mathcal{W}^{n,n+1}_{0}$ only if $x^{\prime}_{i}>y^{\prime}_{i}$.

If we now subtract the rate of leaving (5.3) we find that at $y=y^{\prime}$ the right hand side of (5.4) is equal to

which is equal to $Q_{Y}(y^{\prime},y^{\prime})$.

The remaining cases are $y=y^{\prime}\pm e_{i}$ for some $1\leq i\leq n+1$. Let us deal with $y^{\prime}=y-e_{i}$. If $i=n+1$, this case corresponds to a leftward jump in the rightmost $Y$ particle, a situation that cannot arise through pushing by an $X$ particle. If $i<n+1$, then the jump arose by pushing if $x^{\prime}_{i}=y^{\prime}_{i}$, while if $x^{\prime}_{i}>y^{\prime}_{i}$ then the $Y$ particle jumped by its own volition. In the case of pushing ($i<n+1$, $x^{\prime}_{i}=y^{\prime}_{i}$), familiar calculations show

In the case of no pushing, i.e. $i<n+1$ and $x^{\prime}_{i}>y^{\prime}_{i}$ or $i=n+1$, the summand is

Finally we consider the case $y^{\prime}=y+e_{i}$, $1\leq i\leq n+1$ corresponding to a rightward jump in the $i^{th}$ $Y$ particle. For $i>1$, consider the dichotomy $x^{\prime}_{i-1}=y^{\prime}_{i}$ or $x^{\prime}_{i-1}<y^{\prime}_{i}$, corresponding to the $i^{th}$ $Y$ particle being pushed upwards by the $(i-1)^{th}$ $X$ particle and a free jump respectively. The case $i=1$ corresponds to the leftmost $Y$ particle jumping rightwards, an event that cannot arise as a result of pushing. In the case of pushing, i.e. $i>1$ and $x^{\prime}_{i-1}=y^{\prime}_{i}$, the summand is equal to

Using the definitions of $\mathcal{A}_{0}$ and $m$, this is

If $y_{i}^{\prime}>x^{\prime}_{i-1}$ ($i>1$) or $i=1$, then the $i^{th}$ $Y$ particle jumped of its own accord and the only term in the summation is

This concludes the verification of the intertwining relationship and the theorem follows.

Appendix A A lemma on intertwinings of Q𝑄Q-matrices

Suppose that $L$ and $L^{\prime}$ are uniformly bounded conservative $Q$-matrices on discrete spaces $U$ and $V$ that are intertwined by a Markov kernel $\Lambda:U\times V\to$ from $U$ to $V$, i.e.

Then the transition kernels for the Markov processes with $Q$-matrices $L$ and $L^{\prime}$ are also intertwined.

The intertwining relationship $L\Lambda=\Lambda L^{\prime}$ may be written

Let $(p_{t};t\geq 0)$ denote the transition kernels for the Markov process corresponding to $Q$-matrix $L$ and fix $u_{0}\in U$. Multiplying both sides of the expanded intertwining relationship above by $p_{t}(u_{0},u)$ and summing over $u\in U$ gives

so the double sum on the left hand side is absolutely convergent. Also,

and the same conclusion holds for the double sum on the right hand side. So, we may exchange the order of the sums on both sides to give

Now, as $(p_{t};t\geq 0)$ is the transition kernel corresponding to the Markov process with $Q$ matrix $L$, it satisfies the Kolmogorov forward equation

We may differentiate the summation term by term in $t$ using Fubini’s theorem and the absolute bounds on the summands discussed above. Hence, the right hand side of (A.1) is simply $\frac{d}{dt}q_{t}(v)$.

Then, using the definition of $q_{t}$ in the left hand side of (A.1), we see that

Now let $(p^{\prime}_{t};t\geq 0)$ denote the transition kernels of the Markov process with $Q$-matrix $L^{\prime}$, and

Then $p^{\prime}_{0}(v)=q_{0}(v)$ for all $v\in V$ and $p^{\prime}_{t}$ also satisfies the forward equation (A.2) in $L^{\prime}$.

But when the rates are uniformly bounded there is exactly one solution to the forward differential equation with the same boundary conditions as $q_{t}$ so $q_{t}(v)=p^{\prime}_{t}(v)$ for all $t\geq 0$ and $v\in V$.

By definition of $q_{t}(v)$, we then have

and since the argument holds for arbitrary $u_{0}\in U$ we’re done.

References