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

By Neil O'Connell. 2002

90 citations recorded by the source corpus.

The author and Marc Yor recently introduced a path-transformation G((k)) with the property that, for X belonging to a certain class of random walks on Z(+)(k), the transformed walk G((k))( X) has the same law as the original walk conditioned never to exit the Weyl chamber {x : x(1) less than or equal to...less than or equal to x(k)}. In this paper, we show that G((k)) 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 of X and G((k))( 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-transformation G((k)) 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.

Subfields: Discrete Mathematics and Combinatorics, Mathematical Physics, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/794e4ab1beb9da5367d877ad2b4033803bccdc0b

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Discrete Mathematics and Combinatorics

In Mathematical Physics

In Statistics and Probability

Citations in the corpus

Directed polymers and the quantum Toda lattice (2009, background): “But we do not need these facts, and refer the reader to the papers [6, 40, 43] for details.”
Random matrices and determinantal processes (2005, background): “, the above argument gives us no clue what this law could be. For all we know it could be Gaussian. 5.4. Proof of theorem 5.1. Theprocedureisveryclosetothe Robinson-SchenstedKnuth correspondence. See [27] for a related analysis. We have to deﬁne the paths π 1,π 2,.... Set w(0)(i,j) = w(i,j). Assume ”
Combinatorial Stochastic Processes (2006, methodology): “This representation theorem is closely connected to random matrices, Young tableaux, the Robinson-Schensted-Knuth correspondence, and symmetric functions theory [329, 328].”
Conditioned random walks and the RSK correspondence (2003, unknown): “Fb Mathematics Subject Classification: 05E05, 60J45, 15A52”
Dyson's Brownian motions, intertwining and interlacing (2005, background): “A number of explicit formulae are given, including one for the distribution of a family of coalescing Brownian motions.”