Pitman's transform of type A

pitman_transform robinson_schensted robinson_schensted_knuth

Recall the \(\otimes\) and \(\odot\) in RS as Pitman's transform and RSK as Pitman's transform. They are defined in similar but slightly different ways, and the corresponding path transformations define the RS and the RSK algorithms.

When treating the input as paths, they may be one of the four possibilities in \(\{\text{constinuous}, \text{discrete}\} \times \{\text{time}, \text{space}\}\)

For example, for the discrete-time discrete-space RS algorithm, namely the RS algorithm with words input, the paths are defined in (1.3) in rs_pitman_type_a#Rank-any; and for the RSK algorithm with discrete or continuous space, the paths are defined in (1) in rsk_path_transformation. They are both discrete-time-discrete-space version.

For RSK it is straightforward to extend the transform to continuous space - just allow the input matrix to be real rather than integer.

For RS it is also straightforward to extend the transform to continuous time - just Poissonise the RS algorithm.

This leaves only one unresolved case: the continuous-time-continuous-space case, which we simply call the Pitman's transform of type A. It can be found in [{oconnell03b}] and [{biane-bougerol-oconnell05}].

Here is a table summarising the known cases:

	discrete-time	continuous-time
discrete-space	RS, RSK	RS (e.g. with Poisson input)
continuous-space	RSK (e.g. DLPP with exponential weight)	Pitman's transform of type A

Even though the RS and RSK algorithms have different dynamics, as one can see in the difference of definitions of \(\odot\) and \(\otimes\) in rs_pitman_type_a vs rsk_path_transformation, in the continuous-time continuous-space case, they are unified by the Pitman's transform of type A. This is because the consideration at one time-point is negligible when time is continuous.

Let us move to the definition of the Pitman's transform, which is rather trivial if one already knows the discrete cases.

Let \(S_1, S_2, ..., S_\ell\) be the input paths.

Redefine the two operators:

\begin{align} (f \odot g)(t) = \sup_{0 \le s \le t} \{f(s) + g(t) - g(s)\}\\ (f \otimes g)(t) = \inf_{0 \le s \le t} \{f(s) + g(t) - g(s)\} \end{align}

Then we may define the Pitman's transform of type A, which is the same as the discrete cases in terms of \(\odot\) and \(\otimes\):

Column insertion: \begin{align} \mu^k_k &= S_k\\ \lambda^k_1 &= \mu^k_1 \\ (\lambda^k_j, \mu^k_{j - 1}) &= (\lambda^{k - 1}_{j - 1} \otimes \mu^k_j, \mu^k_j \odot \lambda^{k - 1}_{j - 1}), \qquad j > 1. \end{align} so \begin{align} \lambda^1_1 &= S_1 \\ \lambda^k_1 &= S_k \odot \lambda^{k - 1}_{k - 1} \odot \lambda^{k - 1}_{k - 2} \odot ... \odot \lambda^{k - 1}_1, \qquad k > 1 \\ \lambda^k_j &= \lambda^{k - 1}_{j - 1} \otimes (S_k \odot \lambda^{k - 1}_{k - 1} \odot \lambda^{k - 1}_{k - 2} \odot ... \odot \lambda^{k - 1}_j), \qquad j > 1 \end{align}
Row insertion: \begin{align} \mu^k_1 &= S_k\\ \lambda^k_k &= \mu^k_k\\ (\lambda^k_j, \mu^k_{j + 1}) &= (\lambda^{k - 1}_j \odot \mu^k_j, \mu^k_j \otimes \lambda^{k - 1}_j), \qquad j < k. \end{align} so \begin{align} \lambda^1_1 &= S_1 \\ \lambda^k_k &= S_k \otimes \lambda^{k - 1}_1 \otimes \lambda^{k - 1}_2 ... \otimes \lambda^{k - 1}_{k - 1}, \qquad k > 1 \\ \lambda^k_j &= \lambda^{k - 1}_j \odot (S_k \otimes \lambda^{k - 1}_1 \otimes \lambda^{k - 1}_2 \otimes ... \otimes \lambda^{k - 1}_{j - 1}), \qquad j < k \end{align}

Remark. The symmetry between the column and the row insertion has finally become transparent: one may use an involution

\begin{align} \lambda^k_j &\mapsto - \lambda^k_{k - j + 1} \\ S_k &\mapsto - S_k \end{align}

and the fact

\begin{align} (-f) \otimes (-g) = - (f \odot g), \qquad (-f) \odot (-g) = - (f \otimes g) \end{align}

to transform the row (resp. column) insertion equation to the column (resp. row) insertion equation. Such striking "duality" between the row and column insertion could not be easily observed when one looks at the conventional definition of the discrete-time-discrete-space version of the RS algorithms.

References

[biane-bougerol-oconnell05] Littelmann paths and Brownian paths, P. Biane, P. Bougerol, N. O'Connell, Duke Mathematical Journal, Vol. 130, No. 1, p.127–167 2005.
[oconnell03b] A path-transformation for random walks and the Robinson-Schensted correspondence, Neil O'Connell, Transactions of American Mathematical Society, Vol. 355, No. 9, p.3669–3697 2003.