Markov-Doob integrability on triangular arrays

---

markov_function_theorem doob_transform intertwining_relation

We use the notation in Markov-Doob integrability. When \(S^\ell\) is a triangular array \((\lambda^k_j)_{1 \le j \le k \le \ell}\) and \(T^\ell\) the space of the bottom row of the arrays \((\lambda^\ell_j)_{1 \le j \le \ell}\), equation (0) in Markov-Doob integrability can be further reduced to an equation between neighbouring rows.

In the following we write superscript to indicate the level of the triangular array. For example \(P^k\) is the transition kernel of \(\lambda^{1 : k}\).

One key assumption is Pieri rule for \(h\)

\[ h^k(\lambda^k) = \sum_{\lambda^{k - 1}} B(\lambda^{k - 1}, \lambda^k) h^{k - 1} (\lambda^{k - 1}) \]

which is equivalent to

\[ w^k(\lambda^{1 : k}) = w^{k - 1} (\lambda^{1 : k - 1}) B(\lambda^{k - 1}, \lambda^k). \qquad (-1) \]

There are three types of results, the usual-spec, the exp-spec and the dual-spec, corresponding to the usual, exponential and dual specialisations of the symmetric functions. In terms of the RS(K) algorithms, they correspond to the usual RSK algorithm, the RS algorithm and the dual RSK algorithm.

One way to look at RSK dynamics is to look at its effect on two adjacent levels on the GT pattern, namely to see how it changes \(\lambda^j(n - 1)\) to \(\lambda^j(n)\) given \(\lambda^{j - 1}(n - 1)\) and \(\lambda^{j - 1}(n)\) and matrix element \(w_{n, j}\).

To write everything in a more symmetric manner, we write \(\lambda^{n, k} := \lambda^k(n)\).

In general (not just the RSK dynamics) in the usual specialisation (with discrete space), we have

• A matrix \(W = (w_{n, k})\), where \(w_{n, k} \sim p_{n, k}\) are independent random variables with some law \(p_{n, k}\).
• A dynamics with stochastic kernel \(R_{v}((\lambda^{n - 1, k - 1}, \lambda^{n - 1, k}, \lambda^{n, k - 1}), \lambda^{n, k})\), which is the law of obtaining \(\lambda^{n, k}\) after inserting \(v\) to \(\lambda^{n - 1, k}\) given \(\lambda^{n - 1, k - 1}\) and \(\lambda^{n, k - 1}\).

We write

\[ L(\lambda^{n - 1, k - 1}, \lambda^{n - 1, k}, \lambda^{n, k - 1}, \lambda^{n, k}) = \sum_{w} \prob(w_{n, k} = w) R_{w_{n, k}}((\lambda^{n - 1, k - 1}, \lambda^{n - 1, k}, \lambda^{n, k - 1}), \lambda^{n, k}) \]

to be the kernel of coupling of random variable \(w_{n, k}\) with the usual-spec dynamics.

Then we have

\[ P^k(\lambda^{n - 1, 1 : k}, \lambda^{n, 1 : k}) = P^{k - 1} (\lambda^{n - 1, 1 : k - 1}, \lambda^{n, 1 : k - 1}) L(\lambda^{n - 1, k - 1}, \lambda^{n - 1, k}, \lambda^{n, k - 1}, \lambda^{n, k}). \qquad (0) \]

Proposition. The equation

\begin{align} A(\lambda^{n - 1, k}, \lambda^{n, k}) B(\lambda^{n, k - 1}, \lambda^{n, k}) = \sum_{\lambda^{n - 1, k - 1}} A(\lambda^{n - 1, k - 1}, \lambda^{n, k - 1}) B(\lambda^{n - 1, k - 1}, \lambda^{n - 1, k}) \notag \\ \times L( \lambda^{n - 1, k - 1}, \lambda^{n - 1, k}, \lambda^{n, k - 1}, \lambda^{n, k}). \qquad (1) \end{align}

implies (0) in Markov-Doob integrability.

Proof. Using induction.

\begin{align} \sum_{\lambda^{n - 1, 1 : k - 1}} &w^k (\lambda^{n - 1, 1 : k}) P^k(\lambda^{n - 1, 1 : k}, \lambda^{n, 1 : k})\\ &= \sum_{\lambda^{n - 1, k - 1}} \sum_{\lambda^{n - 1, 1 : k - 2}} w^{k - 1} (\lambda^{n - 1, 1 : k - 1}) B(\lambda^{n - 1, k - 1}, \lambda^{n - 1, k}) P^{k - 1} (\lambda^{n - 1, 1 : k - 1}, \lambda^{n, 1 : k - 1}) \\ &\qquad\qquad\qquad\qquad\qquad\times L(\lambda^{n - 1, k - 1}, \lambda^{n - 1, k}, \lambda^{n, k - 1}, \lambda^{n, k})\\ &= \sum_{\lambda^{k - 1}} A(\lambda^{n - 1, k - 1}, \lambda^{n, k - 1}) w^{k - 1}(\lambda^{n, 1 : k - 1}) B(\lambda^{n - 1, k - 1}, \lambda^{n - 1, k}) \\ &\qquad\qquad\qquad\qquad\qquad\times L(\lambda^{n - 1, k - 1}, \lambda^{n - 1, k}, \lambda^{n, k - 1}, \lambda^{n, k})\\ &= w^{k - 1}(\lambda^{n, 1 : k - 1}) A(\lambda^{n - 1, k}, \lambda^{n, k}) B(\lambda^{n, k - 1}, \lambda^{n, k})\\ &= A(\lambda^{n - 1, k}, \lambda^{n, k}) w^k(\lambda^{n, 1 : k}). \end{align}

where in the first step we use (-1)(0), in the second step we use the induction assumption, in the third step we use (1), and in the last step we use (-1) again. \(\square\)

Using the Lemma in Markov-Doob integrability we have:

Corollary. Recall \(K\) defined in (-1) of Markov-Doob integrability, which in our case is

\[ K(\lambda^{1 : k}, \mu) = {w^k (\lambda^{1 : k}) \over h(\mu)} 1_{\lambda^k = \mu}. \]

Given \(p_{n, k}\) and \(R\) satisfying (1). Recall the \(n\) in \(\lambda^{n, k}\) is the time parameter and we can view \(\lambda^k\) as a stochastic process whose value at time \(n\) is \(\lambda^{n, k}\). We have

1. \((\lambda^k|_{\lambda^{0, 1 : k} \sim K(\lambda^{0, k}, \cdot)}\) is a Markov process with transition kernel \[ Q(\lambda, \mu) = h(\lambda)^{-1} A(\lambda, \mu) h(\mu), \] which is the Doob \(h\)-transform of \(A\).
2. \(\prob(\lambda^{n, 1 : k} = \mu^{1 : k} | \lambda^{n, k} = \mu^k, \lambda^{1 : n - 1, k}) = {w^k(\mu^{1 : k}) \over h(\mu^k)}.\)

For exp-spec algorithms, the inputs are words (discrete space) or paths (continuous space) instead of matrices. Consider the discrete space case. The integrability is similar, except that (0) is replaced by

\[ P^k(\lambda^{n - 1, 1 : k}, \lambda^{n, 1 : k}) = (I + P^{k - 1}) (\lambda^{n - 1, 1 : k - 1}, \lambda^{n, 1 : k - 1}) L(\lambda^{n - 1, k - 1}, \lambda^{n - 1, k}, \lambda^{n, k - 1}, \lambda^{n, k}). \qquad (1) \]

where \(I\) is the identity matrix.

Remark. Equations (0)(1) have been used extensively in the literature to obtain integrability results. See for example the classification of the some the dynamics for references.