Burke property

burke_property robinson_schensted_knuth q-pochhammers

The Burke property is the simplest version of integrability of RSK-type dynamics of usual specialisation, whereas the more accepted Burke's theorem corresponds to the integrability of RSK-type dynamics of exponential specialisation (see [{oconnell-yor01}][{oconnell-yor02}]). The connection between the Burke properties and RSK algorithms is made possible via the DLPP and DP. In this entry we describe them without invoking RSK or DLPP or DP.

The Burke property is: Given two triplets $$U, V, X$$ and $$U', V', X'$$, where $$U, V, X$$ are independent with certain distributions, and $$U', V', X'$$ are derived from the first triplets by some relations, then $$(U', V', X')$$ have the same distribution as $$(U, V, X)$$.

More formally:

Theorem Template (Burke Property). Let $$f$$ and $$g$$ be a two-parameter and a one-parameter probability distributions respectively. Let $$U, V, X, U', V', X'$$ be random variables where $$U, V, X$$ are independent, and that the following conditions are satisfied:

\begin{align} U, V, X &\sim g_\alpha, g_\beta, g_{\alpha + \beta} \qquad (1)\\ U' - U &= V' - V = X - X' \qquad (2) \\ X' &\sim f_{U, V} \qquad (3). \end{align}

Then $$(U', V', X') \overset{d}{=} (U, V, X)$$.

Certainly the Theorem Template taking arbitrary $$f$$ and $$g$$ is not in general a theorem. Nevertheless for some special $$f$$-and-$$g$$'s the assertion is correct:

Theorem. The Burke property holds for the following $$(f, g)$$ pairs.

1. $$f_{u, v} = 1_{u \wedge v}$$ is an atom at $$u \wedge v$$, and $$g_\alpha =$$Geom$$(1 - e^{-\alpha})$$ is the geometric_distribution with parameter $$1 - e^{-\alpha}$$. This corresponds to the usual RSK algorithm.
2. $$f_{u, v} = 1_{u \wedge v}$$, $$g_\alpha=$$Exp$$(\alpha)$$ is the exponential distribution with parameter $$\alpha$$. This is the continuous analogue of the previous case.
3. $$f_{u, v} = 1_{- \log (e^{-u} + e^{-v})}$$, $$g_\alpha=-$$LogGamma$$(\alpha)$$, that is, the law of $$X$$ such that $$e^{-X}$$ has Gamma distribution of paramter $$\alpha$$. This corresponds to the geometric RSK algorithm.
4. $$f_{u, v} = q$$Hyp$$(u, \infty, v)$$, the q-hypergeometric distribution, and $$g_\alpha=q$$Geom$$(e^{-\alpha})$$, the q-geomtric distribution with paramter $$e^{-\alpha}$$. This corresponds to the $$q$$RSK algorithm.
5. $$f_{u, v}$$ has the following probability mass function (with suitable $$q, t$$ to ensure positivity, e.g. $$0 \le q \le t \le 1$$): \begin{align*} f_{u, v} (\ell) = \begin{cases} {h_t(\ell) \over h_t(u) h_t(v)} \sum_{k = 0 : v - \ell} h_{1 / t} (v - \ell - k) t^{v - \ell - k} h_t (k + u - v) h_t (k), \qquad \ell = 0 : v, & u \ge v \\ f_{v, u}(\ell) & u \le v \end{cases} \qquad (3.2) \end{align*} where $$h_t (n) = {(t)_n \over (q)_n}$$. $$g_\alpha=qt$$Geom$$(e^{-\alpha})$$ is the qt-geometric distribution with parameter $$e^{-\alpha}$$.

Remark.

1. Case 1 can be found in e.g. Lemma 2.3 of [{seppalainen09}], Case 2 in [{balazs-cator-seppalainen06}], Case 3 in [{seppalainen12}], Case 4 in [{pei16}] and Case 5 is a result due to Christian Krattenthaler.
2. Case 5 degenerates to Case 4 when $$t = 0$$, and to Case 1 when $$q = t$$. See Claim 2 below.

We focus on Case 5 for now. We first show a general result:

Claim. Let $$f_{m, n}$$ be a nonnegative function of the form

$f_{m, n} (\ell) = {h_t(\ell) \over h_t(m) h_t(n)} F(m - \ell, n - \ell) \qquad (3.5)$

for some $$F$$, and let $$g_\alpha = qt$$Geom$$(e^{-\alpha})$$. Then $$f_{m, n}$$ is a probability mass function if and only if the Burke property holds for $$f_{m, n}$$ and $$g$$.

Proof. $$f_{m, n}$$ is a pmf iff

$\sum_{\ell} h_t(\ell) F(m - \ell, n - \ell) = h_t(m) h_t(n). \qquad (4)$

On the other hand, by (1)(2)(3), Burke's property is equivalent to (note that we redefine $$(\alpha, \beta) := (e^{-\alpha}, e^{-\beta})$$)

\begin{align} \alpha^u \beta^v (\alpha\beta)^x h_t(x) h_t(u) h_t(v) &{(\alpha)_\infty (\beta)_\infty (\alpha \beta)_\infty \over (\alpha t)_\infty (\beta t)_\infty (\alpha \beta t)_\infty} = \prob(U' = u, V' = v, X' = x)\\ &= \sum_{y} \prob(U' = u, V' = v, X' = x, X = y) \\ &= \sum_y \prob(U = u + x - y, V = v + x - y, X = y, X' = x)\\ &= \sum_y {(\alpha)_\infty (\beta)_\infty (\alpha \beta)_\infty \over (\alpha t)_\infty (\beta t)_\infty (\alpha \beta t)_\infty} \alpha^{u + x - y} \beta^{v + x - y} (\alpha \beta)^y h_t(u + x - y) h_t(v + x - y) h_t(y) f_{u + x - y, v + x - y}(x) \\ &= {(\alpha)_\infty (\beta)_\infty (\alpha \beta)_\infty \over (\alpha t)_\infty (\beta t)_\infty (\alpha \beta t)_\infty} \alpha^u \beta^v (\alpha\beta)^x h_t(x) \sum_y h_t(y) F(u - y, v - y). \end{align}

which is in turn equivalent to (4). $$\square$$

It turns out formula (3.5) and (4) pins down $$F$$. The following claim is due to Christian Krattenthaler.

Claim 1. There exists a unique solution $$F$$ to (3.5) and (4), which is the one corresponding to (3.2):

$F(m, n) = \begin{cases} \sum_{k = 0}^n h_{1 / t} (n - k) t^{n - k} h_t(k + m - n) h_t(k) & m \ge n \\ F(n, m) & m < n \end{cases} \qquad (5)$

Proof. By replacing $$b := ta$$ and let $$a \to 0$$ in the main theorem in [{bressoud83}] (see also (1.3)(2) of [{krattenthaler96}]), we have:

Lemma.

$\sum_{\ell = 0 : n} h_t(n - \ell) A(\ell) = B(n)$

if and only if

$\sum_{k = 0 : \ell} h_{1 / t} (\ell - k) t^{\ell - k} B(k) = A(\ell).$

(End of Lemma)

Now we go back to the proof of Claim 1. Without loss of generality assume $$m \ge n$$ and let $$c := m - n$$. Rewrite (4) as

$\sum_{\ell} h_t(n - \ell) F(c + \ell, \ell) = h_t(n + c) h_t(n)$

Apply Lemma to $$A(\ell) := F(\ell + c, \ell)$$ we have

$F(\ell + c, \ell) = \sum_k h_{1 / t} (\ell - k) t^{\ell - k} h_t(k + c) h_t(k).$

Replacing $$\ell := n$$ and $$c := m - n$$ we arrive at the conclusion. $$\square$$

One can also verify (4) using (5) directly:

Proof of (4) given (5). Without loss of generality assume $$m \ge n$$.

\begin{align} \sum_{\ell = 0 : n} &h_t(n - \ell) \sum_{k = 0 : \ell} h_{1 / t} (\ell - k) t^{\ell - k} h_t (k + m - n) h_t(k) \\ &= \sum_{k = 0 : n} h_t(k + m - n) h_t(k) \sum_{\ell = k : n} h_t (n - \ell) h_{1 / t} (\ell - k) t^{\ell - k}\\ &= \sum_{k = 0 : n} h_t(k + m - n) h_t(k) \sum_{\ell = 0 : n - k} h_t (n - k - \ell) h_{1 / t} (\ell) t^\ell \\ &= \sum_{k = 0 : n} h_t(k + m - n) h_t(n - k) {}_2\phi_1(q^{- n + k}, t^{-1}; t^{-1} q^{1 - n + k}; q, q) \\ &= \sum_{k = 0 : n} h_t(k + m - n) h_t(n - k) 1_{n - k = 0} \\ &= h_t(m) h_t(n) \end{align}

where in step 1 we substitute $$\ell := n - \ell$$; in step 2 we exchange the two sums; in step 3 we substitute $$\ell := \ell - k$$; in step 4 we write the sum in standard form using

$(a)_{n - k} = {(a)_n \over (a^{-1} q^{1 - n})_k} (- q a^{-1})^k q^{ {k \choose 2} - n k}; \qquad (6)$

in step 5 we use

${}_2\phi_1(q^{-n}, b; c; q, q) = {(c / b)_n \over (c)_n} b^n. \qquad (7)$

$$\square$$

Claim 2. Case 5 of Theorem reduces to Case 4 when $$t = 0$$, and to Case 1 when $$q = t$$.

Proof. It suffices to show the reduction of $$f$$ and $$g$$. The reduction of $$g$$ is true because the $$qt$$-geometric distribution reduces to the $$q$$-geometric distribution when $$t = 0$$ and to the usual one when $$t = q$$ (see geometric_distribution), so we only need to show the reduction of $$f$$.

Without loss of generality assume $$m \ge n$$.

1. When $$t = q$$, $f_{m, n} (\ell) = \sum_{k = 0}^{n - \ell} {(1 / q)_{n - \ell - k} q^{n - \ell - k} \over (q)_{n - \ell - k}} = 1_{\ell = n},$ since for $$s \ge 0$$, ${(q^{-1})_s q^s \over (q)_s} = 1_{s = 0} - 1_{s = 1}.$
2. To show the reduction of $$t = 0$$, we first rewrite $$f_{m, n}$$. $f_{m, n} (\ell) = {h_t(\ell) \over h_t(m) h_t(n)} h_{1 / t} (n - \ell) t^{n - \ell} h_t (m - n) {}_3\phi_2(q^{- n + \ell}, t q^{m - n}, t; t q^{- n + \ell + 1}, q^{m - n + 1}; q; q).$ When $$t = 0$$, using (6)(7), \begin{align} f_{m, n} (\ell) &\to {(q)_n (q)_m \over (q)_\ell} (-1)^{n - \ell} q^{ {n - \ell \choose 2}} (q)_{n - \ell}^{-1} (q)_{m - n}^{-1} {}_2\phi_1 (q^{- n + \ell}, 0; q^{m - n + 1}; q, q) \\ &= {(q)_n (q)_m \over (q)_\ell} (-1)^{n - \ell} q^{ {n - \ell \choose 2}} (q)_{n - \ell}^{-1} (q)_{m - n}^{-1} \lim_{c \downarrow 0} {}_2\phi_1 (q^{- n + \ell}, c; q^{m - n + 1}; q, q) \\ &= {(q)_n (q)_m \over (q)_\ell} (-1)^{n - \ell} q^{ {n - \ell \choose 2}} (q)_{n - \ell}^{-1} (q)_{m - n}^{-1} (-1)^{n - \ell} q^{(m - n)(n - \ell) + {n - \ell + 1 \choose 2}} (q^{m - n + 1})_{n - \ell}^{-1} \\ &= q^{(m - \ell)(n - \ell)} {(q)_m (q)_n \over (q)_{\ell} (q)_{m - \ell} (q)_{n - \ell}} \end{align} which is the pmf of $$q$$Hyp$$(m, \infty, n)$$.

$$\square$$

Remark. For convenience, until a better name is found we call $$f_{u, v}$$ in (3.2) the qt-infhypergeometric distribution (with shorthand form $$qt$$IHyp$$(u, v)$$) since it reduces to $$q$$Hyp with an infinity parameter when $$t = 0$$.

References

• [balazs-cator-seppalainen06] Cube root fluctuations for the corner growth model associated to the exclusion process, , Electron. J. Probab, Vol. 11, No. 42, p.1094–1132 2006.
• [bressoud83] A matrix inverse, , Proceedings of the American Mathematical Society, Vol. 88, No. 3, p.446–448 1983.
• [krattenthaler96] A new matrix inverse, , Proceedings of the American Mathematical Society, Vol. 124, No. 1, p.47–59 1996.
• [oconnell-yor01] Brownian analogues of Burke's theorem, , Stochastic processes and their application, Vol. 96, p.285–304 2001.
• [oconnell-yor02] A Representation for Non-Colliding Random Walks, , Electronic Communications in Probability, Vol. 7, p.1–12 2002.
• [pei16] A $q$-Robinson-Schensted-Knuth Algorithm and a $q$-polymer, , 2016.
• [seppalainen09] Lecture notes on the corner growth model, , Unpublished notes 2009.
• [seppalainen12] Scaling for a one-dimensional directed polymer with boundary conditions, , Ann. Probab., Vol. 40, No. 1, p.19–73, 01 2012. [ link ]