Random Walks in Weyl Chambers and the Decomposition of Tensor Powers
David J. Grabiner
and Peter Magyar
DOI: 10.1023/A:1022499531492
Abstract
We consider a class of random walks on a lattice, introduced by Gessel and Zeilberger, for which the reflection principle can be used to count the number of k-step walks between two points which stay within a chamber of a Weyl group. We prove three independent results about such 
reflectable walks 
: first, a classification of all such walks; second, many determinant formulas for walk numbers and their generating functions; third, an equality between the walk numbers and the multiplicities of irreducibles in the kth tensor power of certain Lie group representations associated to the walk types. Our results apply to the defining representations of the classical groups, as well as some spin representations of the orthogonal groups.
reflectable walks : first, a classification of all such walks; second, many determinant formulas for walk numbers and their generating functions; third, an equality between the walk numbers and the multiplicities of irreducibles in the kth tensor power of certain Lie group representations associated to the walk types. Our results apply to the defining representations of the classical groups, as well as some spin representations of the orthogonal groups.Pages: 239–260
Keywords: random walk; representation of Lie group; tensor power; Weyl group; hyperbolic Bessel function
Full Text: PDF
References
1. J.F. Adams, Lectures on Lie Groups, University of Chicago Press, 1969.
2. N. Bourbaki, Groupes et Algebres de Lie, Chapters 4, 5, 6, Hermann, Paris, 1968.
3. W. Fulton and J. Harris, Representation Theory, Springer-Verlag, New York, 1991.
4. I.M. Gessel, "Symmetric functions and P-recursiveness," J. Combin. Th. A 53 (1990), 257-285.
5. I.M. Gessel and D. Zeilberger, "Random walk in a Weyl chamber," Proc. Amer. Math. Soc. 115 (1992), 27-31.
6. J.E. Humphreys, Introduction to Lie Algebras and Representation Theory, Springer-Verlag, New York, 1972.
7. R.C. King, "S-functions and characters of Lie algebras and superalgebras," Invariant Theory and Tableaux (Minneapolis, MN 1988), J.R. Stembridge, ed., Springer-Verlag, New York, 1990, 226-261.
8. K. Koike and L. Terada, "Young-diagrammatic methods for the restriction of representations of complex classical Lie groups to reductive subgroups of maximal rank," Advances in Math. 79 (1990), 104-135.
9. I.G. Macdonald, Symmetric Functions and Hall Polynomials, Oxford University Press, Oxford, 1979.
10. S. Okada, "A Robinson-Schensted algorithm for SO(2n,C)," preprint. 11, R.A. Proctor, "Reflection and algorithm proofs of some more Lie group dual pair identities",
7. Combin. Th. A, to appear. GRABINER AND MAGYAR
12. R.A. Proctor, "A generalized Berele-Schensted algorithm," Trans. Amer. Math. Soc. 324 (1991), 655-692.
13. J.R. Stembridge, "Rational tableaux and the tensor algebra of Bin." J. Combin. Th. A 46 (1987), 79-120.
14. S. Sundaram, "The Cauchy identity for Sp(2n)," J. Combin. Th. A 53 (1990), 209-238.
15. S. Sundaram, "Orthogonal tableaux and an insertion algorithm for SO(2n + 1)," J. Combin. Th. A S3 (1990), 239-256.
16. T. Watanabe and S.G. Mohanty, "On an inclusion-exclusion formula based on the reflection principle," Discrete Math. 64 (1987), 281-288.
17. E.T. Whittaker and G.N. Watson, A Course of Modem Analysis, Cambridge University Press, Cambridge, 1927.
18. D. Zeilberger, "Andre's reflection proof generalized to the many-candidate reflection problem," Discrete Math. 44 (1983) 325-326.
2. N. Bourbaki, Groupes et Algebres de Lie, Chapters 4, 5, 6, Hermann, Paris, 1968.
3. W. Fulton and J. Harris, Representation Theory, Springer-Verlag, New York, 1991.
4. I.M. Gessel, "Symmetric functions and P-recursiveness," J. Combin. Th. A 53 (1990), 257-285.
5. I.M. Gessel and D. Zeilberger, "Random walk in a Weyl chamber," Proc. Amer. Math. Soc. 115 (1992), 27-31.
6. J.E. Humphreys, Introduction to Lie Algebras and Representation Theory, Springer-Verlag, New York, 1972.
7. R.C. King, "S-functions and characters of Lie algebras and superalgebras," Invariant Theory and Tableaux (Minneapolis, MN 1988), J.R. Stembridge, ed., Springer-Verlag, New York, 1990, 226-261.
8. K. Koike and L. Terada, "Young-diagrammatic methods for the restriction of representations of complex classical Lie groups to reductive subgroups of maximal rank," Advances in Math. 79 (1990), 104-135.
9. I.G. Macdonald, Symmetric Functions and Hall Polynomials, Oxford University Press, Oxford, 1979.
10. S. Okada, "A Robinson-Schensted algorithm for SO(2n,C)," preprint. 11, R.A. Proctor, "Reflection and algorithm proofs of some more Lie group dual pair identities",
7. Combin. Th. A, to appear. GRABINER AND MAGYAR
12. R.A. Proctor, "A generalized Berele-Schensted algorithm," Trans. Amer. Math. Soc. 324 (1991), 655-692.
13. J.R. Stembridge, "Rational tableaux and the tensor algebra of Bin." J. Combin. Th. A 46 (1987), 79-120.
14. S. Sundaram, "The Cauchy identity for Sp(2n)," J. Combin. Th. A 53 (1990), 209-238.
15. S. Sundaram, "Orthogonal tableaux and an insertion algorithm for SO(2n + 1)," J. Combin. Th. A S3 (1990), 239-256.
16. T. Watanabe and S.G. Mohanty, "On an inclusion-exclusion formula based on the reflection principle," Discrete Math. 64 (1987), 281-288.
17. E.T. Whittaker and G.N. Watson, A Course of Modem Analysis, Cambridge University Press, Cambridge, 1927.
18. D. Zeilberger, "Andre's reflection proof generalized to the many-candidate reflection problem," Discrete Math. 44 (1983) 325-326.