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.
- Case 1:
- Case 2:
- Case 3:
- Case 4:
- Case 5:
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)\).
- The term corresponding to \(x_l\) jumping to the left is \(p G(\eta, x) (\tau^{-1} - 1) = (q - p) G(\eta, x)\). This will also appear in Case 3.
- The term corresponding to \(x_r\) jumping to the right is \(q G(\eta, x) (\tau - 1) = (p - q) G(\eta, x)\). This will also appear in Case 2.
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:
- E1. For some \(x_i\) in the \(X\)-process, \(\eta_{x_i} = 0\), \(\eta_{x_i + 1} = 1\). In other words, there is an \(X\)-particle just to the left of the left edge of an \(\eta\)-cluster. Then the \(\eta\)-particle jumps to the left.
- E2. For some \(x_i\) in the \(X\)-process, \(\eta_{x_i} = 1\), \(\eta_{x_i + 1} = 0\). In other words, there is an \(X\)-particle on the right edge of an \(\eta\)-cluster. Then the \(\eta\)-particle jumps to the right.
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.
- X1. For some site \(x\) in the \(\eta\)-process, \(\eta_x = 1\), there is an \(x_i = x - 1\) of the \(X\)-process, but no \(X\)-particle at \(x\). In other words, there is an \(\eta\)-particle just to the right of the right edge of an \(X\)-cluster. Then the \(x_i\) particle jumps to the right.
- X2. For some site \(x\) in the \(\eta\)-process, \(\eta_x = 1\), there is an \(x_i = x\) of the \(X\)-process, but no \(X\)-particle at \(x - 1\). In other words, there is an \(\eta\)-particle on the left edge of an \(X\)-cluster. Then the \(x_i\) particle jumps to the left.
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":
- case 1:
- case 2:
- case 3:
- case 4:
All of them are easily verified:
- In case 1 and 2, \(L^\eta H = L^x H = 0\).
- In case 3, \(L^\eta H = L^x H = (q - p) H\).
- In case 4, \(L^\eta H = L^x H = (p - q) H\).
\(\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
- [borodin-corwin-sasamoto14] From duality to determinants for q-TASEP and ASEP, , Ann. Probab., Vol. 42, No. 6, p.2314–2382, 11 2014. [ link ]