A \(q\)-analog of the hook walk algorithm and random Young tableaux (Q1324671)

In the papers [\textit{C. Greene}, \textit{A. Nijenhuis} and \textit{H. S. Wilf}, Adv. Math. 31, 104-109 (1979; Zbl 0398.05008) and J. Comb. Theory, Ser. A 37, 127-135 (1984; Zbl 0561.05004)] a remarkable probabilistic algorithm, the hook walk, was introduced. It was used there for two purposes: to give a new probabilistic proof of the hook formula and to generate random Young tableaux distributed according to the Plancherel measure. In the present paper we suggest new applications of the original Greene- Nijenhuis-Wilf algorithm and define a \(q\)-analog of this algorithm. Two applications of the generalized version of the algorithm are presented. The first application deals with an interesting family of probability distributions on the space of (infinite) Young tableaux. This family can be considered as a \(q\)-deformation of the Plancherel measure, and its distributions are in one-to-one correspondence with Markov traces on Hecke algebras (these traces arise in the algebraic construction of link and knot invariants defined by Jones). The new algorithm provides an efficient generation procedure for random Young tableaux with these distributions. The second application is related to a new interpretation of the well- known \(q\)-analog of the hook formula. We show that one can associate multiplicities (depending on \(q\) rationally) with the edges of a Young graph in such a way that the \(q\)-dimension of a Young diagram, defined recurrently, is given by the \(q\)-hook formula. In the particular case \(q=1\) all the edges are simple and the proof yields the classical formula.