A path-transformation for random walks and the Robinson-Schensted correspondence

The author and Marc Yor recently introduced a path-transformationG(k)G⁽ᵏ⁾with the property that, forXXbelonging to a certain class of random walks onZ+kZ_+^k, the transformed walkG(k)(X)G⁽ᵏ⁾(X)has the same law as the original walk conditioned never to exit the Weyl chamber{x: x1≤⋯≤xk}\{x:\ x_1≤ ⋯ ≤ x_k\}. In this paper, we show thatG(k)G⁽ᵏ⁾is closely related to the Robinson-Schensted algorithm, and use this connection to give a new proof of the above representation theorem. The new proof is valid for a larger class of random walks and yields additional information about the joint law ofXXandG(k)(X)G⁽ᵏ⁾(X). The corresponding results for the Brownian model are recovered by Donsker’s theorem. These are connected with Hermitian Brownian motion and the Gaussian Unitary Ensemble of random matrix theory. The connection we make between the path-transformationG(k)G⁽ᵏ⁾and the Robinson-Schensted algorithm also provides a new formula and interpretation for the latter. This can be used to study properties of the Robinson-Schensted algorithm and, moreover, extends easily to a continuous setting.