Markov Duality

markov_processes duality

Definition. Markov processes \(X\) and \(Y\) are dual with respect to function \(H\) if

\[ \expe_{X_0 = x} H(X_t, y) = \expe_{Y_0 = y} H(x, Y_t). \]

When \(X\) and \(Y\) have generator \(L^X\) and \(L^Y\), this is equivalent to

\[ L^X H(x, y) = L^Y H(x, y). \]

This equivalence can be seen by taking \(\partial_t|_{t = 0}\) and noting the initial condition is tautology (\(H(x, y) = H(x, y)\)).

We derive the duality between \(q\)-TASEP and \(q\)-TAZRP, and between ASEP occupation and location processes. These results can be found in e.g. [{borodin-corwin-sasamoto14}].

duality between \(q\)-TASEP and \(q\)-TAZRP

qTASEP qTAZRP duality

Let \(X\) be \(q\)-TASEP with \(N\) particles, and \(Y\) be \(q\)-TAZRP with \(N\) sites. More specifically, \(X_k\) is the location of \(k\)th particle of \(q\)-TASEP and \(Y_k\) is the number of particles at site \(k\). Let \(a_i\) be the rate of jumps by the \(i\)th particle in \(q\)-TASEP, and of from site \(i\) to site \(i - 1\) in \(q\)-TAZRP.

The generator of \(q\)-TASEP is

\[ L^X f(x) = \sum_i a_i (1 - q^{x_{i - 1} - x_i - 1}) (f(x + e_i) - f(x)) \]

and that of \(q\)-TAZRP is

\[ L^Y f(x) = \sum_i a_i (1 - q^{y_i}) (f(y - e_i + e_{i - 1}) - f(y)) \]

Let

\[ H(x, y) = \prod_{i = 1 : N} q^{(x_i + i) y_i}. \]

Claim. \(X\) and \(Y\) are dual w.r.t. \(H\).

Proof.

\[ L^X H(x, y) = \sum_i a_i (1 - q^{x_{i - 1} - x_i - 1}) (q^{y_i} - 1) H(x, y) = L^Y (x, y). \]

\(\square\).

duality between ASEP occupation and location processes

ASEP duality

Let \(\eta\) be the occupation process of ASEP with rate \(p\) to the right and \(q\) to the left:

\[ L^\eta f(\eta) = \sum_i p \eta_i (1 - \eta_{i + 1}) (f(\eta - e_i + e_{i + 1}) - f(\eta)) + q (1 - \eta_i) \eta_{i + 1} (f(\eta - e_{i + 1} + e_i) - f(\eta)). \]

and \(X\) be the location process of ASEP with rate \(p\) to the left and \(q\) to the right:

\[ L^X f(x) = \sum_{i \in l(x)} p (f(x - e_i) - f(x)) + \sum_{i \in r(x)} q (f(x + e_i) - f(x)), \]

where \(l(x) = \{i : x_{i - 1} + 1 < x_i\}\) and \(r(x) = \{i : x_i + 1 < x_{i + 1}\}\) are the left and right edges of clusters.

Let

\begin{align} \tau &= p / q\\ N_x (\eta) &= \sum_{i \le x} \eta_i\\ H(\eta, x) &= \prod_i \tau^{N_{x_i} (\eta)} \qquad (1) \\ G(\eta, x) &= \prod_i \tau^{N_{x_i - 1} (\eta)} \eta_{x_i} \end{align}

Claim 1. \(X\) and \(\eta\) are dual w.r.t. both \(H\) and \(G\).

Proof. Let us consider \(G\) first. We consider one \(x\)-cluster \(x_{l : r}\). Locally, there are 5 cases when at least one of the summands in \(L^\eta G\) or \(L^X G\) is nonzero. We use crosses on the horizontal axis to denote the \(x\)-particles, and lines to denote the profile of \(\eta\). That is, \(\eta = 0\) wherever the line touches the horizontal axis and \(\eta = 1\) wherever the line is above the horizontal axis. Here are the 5 cases.

In case 1 2 and 3 \(x_{l : r}\) is fully covered by \(\eta\). \(G(x, \eta)\) is locally nonzero, but when \(\eta\) is altered slightly, in case 2 and 3 \(G\) may be zero.

In case 4 (resp. 5) all but \(x_r\) (resp. \(x_l\)) is covered. \(G(x, \eta)\) is zero, but when \(\eta\) or \(x\) is altered slightly, \(G\) may become locally nonzero.

It suffices to consider one \(x\)-cluster \(x_{l : r}\).

In case 1:

\[ L^\eta G(\eta, x) = 0 \]

Consider \(L^X G(\eta, x)\).

Therefore

\[ L^X G(\eta, x) = (q - p) G(\eta, x) + (p - q) G(\eta, x) = 0. \]

In case 2:

\begin{align} L^\eta G(\eta, x) &= - q G(\eta, x)\\ L^X G(\eta, x) &= - p G(\eta, x) + (p - q) G(\eta, x) = - q G(\eta, x). \end{align}

Similarly in Case 3:

\begin{align} L^\eta G(\eta, x) &= - p G(\eta, x) = L^x G(\eta, x)\\ \end{align}

In case 4:

\[ L^\eta G(\eta, x) = q G(\eta - e_{x_r + 1} + e_{x_r}, x) = q G(\eta, x + e_r) = L^X G(\eta, x) \]

In case 5:

\[ L^\eta G(\eta, x) = p G(\eta - e_{x_l - 1} + e_{x_l}) = p G(\eta, x - e_l) = L^X G(\eta, x). \]

This concludes the proof that \(G\) is a duality function. Now let us turn to \(H\). In terms of \(L^\eta\) there are two cases where \(H(x, \eta)\) changes and has nonzero corresponding summands:

The summands are respectively

\begin{align} q (\tau - 1) H(x, \eta) &= (p - q) H(x, \eta) \\ p (\tau^{-1} - 1) H(x, \eta) &= (q - p) H(x, \eta) \end{align}

In terms of \(L^X\) there are also two cases, which are in a sense dual to the \(L^\eta\). We use circles to denote empty site in the \(X\)-process.

These two cases also correspond to

\begin{align} (p - q) H(x, \eta) \\ (q - p) H(x, \eta) \end{align}

respectively.

Now consider one \(X\)-cluster. We can pair the two cases \(E_1\) and \(E_2\) in \(L^\eta\) and removing the corresponding portions (since the contribution of \(E_1\) and \(E_2\) cancels each other) to reduce the configuration without \(\eta\)-"valleys" or -"hills".

For example here is such a pairing, and everything in the red frame can be removed, reducing the configuration to case 3 in the following.

we are left with verifying the duality in the following 4 cases wihtout "valleys" or "mountains":

All of them are easily verified:

\(\square\)

Remark. Note that duality does not hold in the ASEP case if, as in the \(q\)TASEP case we introduce the bond jump rate parameters \(a_i\). More specifically, duality does not hold for the following \(L^\eta\), \(L^X\), and \(G\) as in (1):

\begin{align} L^\eta f(\eta) &= \sum_i a_i p \eta_i (1 - \eta_{i + 1}) (f(\eta - e_i + e_{i + 1}) - f(\eta)) + a_i q (1 - \eta_i) \eta_{i + 1} (f(\eta - e_{i + 1} + e_i) - f(\eta))\\ L^X f(x) &= \sum_{i \in l(x)} a_{x_i - 1} p (f(x - e_i) - f(x)) + \sum_{i \in r(x)} a_{x_i} q (f(x + e_i) - f(x)) \end{align}

That is, for the \(x_i\) particle in the \(X\)-process, the rate of jumping to the left is \(a_{x_i - 1} p\) and to the right is \(a_{x_i} q\); and for the \(\eta\)-process at site \(x\), the rate of an unobstructed particle jumping to the left is \(a_{x - 1} q\) and to the right \(a_x p\). To see that \(G\) is not a duality function, for example consider Case 2 in the proof of \(G\) being the duality function in Claim 1.

\begin{align} L^\eta G(\eta, x) = - q a_{x_{l} - 1} G(\eta, x)\\ L^X G(\eta, x) = (- p a_{x_l - 1} + (p - q) a_{x_r}) G(\eta, x). \end{align}

They are not equal unless \(p = q\) or all the \(a_i\)s are equal. In fact if either of these conditions is satisfied, \(G\) is a duality function.

References

about. toywiki on Github. people. contact: me@ypei.me
Last updated on 2017-06-15. Licensed under CC BY-SA 4.0