Random Walks in Weyl Chambers and the Decomposition of Tensor Powers.
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&semi; second, many determinant formulas for walk numbers and their generating functions&semi; 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.
Introduction
The ballot problem, a classical problem in random walks, asks how many
ways there are to walk from the origin to a point (-
unit-length steps in the positive coordinate directions while staying in the
region . The solution is known in terms of the hook-
length formula for Young tableaux; a combinatorial proof, using a reflection
argument, is given in [16, 18].
In [5], Gessel and Zeilberger consider a more general question, for which
some of the same techniques apply. For certain "reflectable" walk-types, we
want to count the number of k-step walks between two points of a lattice,
Supported by an NSF Graduate Fellowship.
staying within a chamber of a Weyl group. The steps must have certain
allowable lengths and directions.
In this paper, we show that this is equivalent to decomposing into irreducibles
the kth tensor power of certain representations of reductive Lie
groups. We classify the reflectable walk-types and their corresponding repre-
sentations. For many cases, we derive determinant formulas for the number
of walks, or equivalently, for the multiplicities of irreducibles in tensor powers.
In particular, our formulas apply to the defining representations of the classical
groups, as well as some spin representations of the orthogonal groups.
Our results are closely related to those obtained by Proctor [11].
Reflectable random walks
2.1 Definitions
A walk-type is defined by a lattice L, a set S of allowable steps between lattice
points, and a polygonal cone C to which the walks are confined. Without
affecting the walk problems, we may restrict L and C to the linear span
of S, so that L, S, and C have the same linear span. (We may weight the
steps with the relative probabilities of choosing each, but this will make little
difference in what follows.)
We will assume C is a Weyl chamber. That is, defined
by a system of simple roots \Delta ae R n as
the orthogonal reflections r ff : ~x 7! ~x \Gamma 2(ff;~x)
ff preserve L and S for all ff in
\Delta; and the r ff generate a finite group W of linear transformations, the Weyl
group.
Example. In the ballot problem,
defined by the simple roots
and W is the symmetric group S n permuting the n coordinates.
Definition. A walk-type (L; S; C) is reflectable if the following equivalent
conditions hold:
1. Any step s 2 S from any lattice point in the interior of C will not exit
C.
2. For each simple root ff i , there is a real number k i such that (ff
is an integer multiple of k i for
The reflectability condition guarantees that a walk cannot exit C without
landing on a wall of C at some step.
Example. The walk-type
0g is not reflectable. However, it becomes reflectable if we let C be a
coordinate quadrant, or if we restrict L to be the lattice points
2.2 The theorem of Gessel and Zeilberger
In a reflectable random walk problem, we want to compute b j-;k , the number
of walks from j to - of length k which stay in the interior of a Weyl chamber.
(The ballot problem can be converted to this form by starting at the point
instead of the origin, and requiring the coordinates to
remain strictly ordered.)
s2S ~u s , the generating function for the steps in the formal
monomials
n . (We call this - because it will later correspond
to a character, with weights equal to the permitted steps.) Let c fl;k
denote the number of random walks of length k, with steps in S, from the
origin to fl, but unconstrained by a chamber. Then we have
where
denotes the coefficient of ~u fl in the polynomial.
The fundamental result of Gessel and Zeilberger [5] is:
Theorem 1 If the walk from j to - is reflectable, then
Proof. Every walk from any w(j) to - which does touch at least one wall
has some last step j at which it touches a wall; let the wall be the hyperplane
perpendicular to ff i , choosing the largest i if there are several choices [11].
Reflect all steps of the walk up to step j across that hyperplane; the resulting
walk is a walk from w ff i
w(j) to - which also touches wall i at step j. This
clearly gives a pairing of walks, and since w ff i
has sign \Gamma1, these two walks
cancel out in (2). The only walks which do not cancel in these pairs are the
walks which stay within the Weyl chamber, and since w(j) is inside the Weyl
chamber only if w is the identity, this is the desired number of walks.
2.3 Generating functions
It is often natural to study these walks by studying their exponential generating
functions. If the generating function for unconstrained random walks
is h
k=0 c flk x k =k!, then we have
Let g j-
be the corresponding generating function for
random walks in the Weyl chamber. Then we have:
Corollary 1 With hypotheses as in Theorem 1,
As an illustration of the usefulness of exponential generating functions,
suppose the set S of steps can be partitioned into two subsets S 1 and S 2
orthogonal to each other, and acting only on S i
and fixing the steps of the other subset, 2. Then we can use the
corollary and the properties of the exponential to factor the exponential
generating function: g j-
(x) is the generating
function for the walk with steps S i and
with
In particular, if S
That is, adding the step 0 to the allowable steps for any random walk corresponds
to multiplying the exponential generating function by e x .
3 Decomposition of tensor powers
3.1 Characters
An important combinatorial problem in Lie theory is to determine the number
of times each irreducible representation of a group or algebra occurs in
the k-fold tensor power of a given finite-dimensional representation V . That
is, we wish to determine the positive integers a U;k for which
U a U;k U ,
where U runs over irreducible representations. We may let V be a virtual
representation (a formal difference of representations). We study the case of
a complex reductive group such as GL n (C ), a compact real Lie group such
as U(n) or O(n), or the Lie algebra of such a group. (See [1, 3, 6].)
For convenience, we will discuss g, a reductive Lie algebra over C , and a
finite dimensional virtual representation V . We recall some standard facts [6].
We know g possesses a maximal abelian subalgebra, its Cartan subalgebra h;
a root system, a certain finite set in h
(the linear functionals on h); and a
weight lattice   in h
. A Weyl group W defined by the root system acts on h
and h
. We choose a fundamental Weyl chamber of dominant weights in the
weight lattice.
We define an integrable character of h to be an element of C [h   ], the
formal C -linear combinations of symbols ~u - for - in the weight lattice.
Example. For is the set of all diagonal matrices; the
root system is gives the kth coordinate
of a diagonal matrix; and the weight lattice is Ze . W is the
symmetric group S n permuting the n diagonal entries.
A representation V of such a g is defined up to isomorphism by its character
Characters of g are invariant under the Weyl group, and span the space of
invariants In fact the irreducible representations of g are indexed by
dominant weights (or orbits of W on the weight lattice), and their characters
form a basis of C [ direct sum (or tensor product) of representations
corresponds to an ordinary sum (resp. ordinary product) of their characters.
Thus, our problem of decomposing
reduces to finding integers a -;k
such that
a
where - is the character of the irreducible representation of g with highest
weight -.
The case corresponds to the trivial representation, so a 0;k will be
the dimension of invariants in the kth tensor power of V .
3.2 Weyl's character formula
The character - is given by the Weyl Character Formula:
is the half-sum of the positive roots, and the Weyl denominator
Example. For
oe
Y
n\Thetan
a Vandermonde determinant. (We denote u - 1
n by ~u (- 1 ;:::;- n ) .)
Now, ffi- is essentially a monomial, i.e., there is only one dominant weight
- for which ~u - appears in this expression, and in fact
multiplying (4) by ffi, we get
a
where -j ~u - denotes the coefficient of ~u - in the element - 2 C [h   ]. Multiplying
out by the terms of ffi, we obtain
a
Forming an exponential generating function, we have
a -;k
3.3 Equivalence of tensor powers and random walks
The right-hand sides of these equations are the same sums of unconstrained
walks as in (2) and (3), with This gives us a correspondence
between random walks in a Weyl chamber and the decomposition of tensor
powers. In particular, equating the right sides of (8) and (2), and likewise
of (9) and (3), we have the following result.
Theorem 2 Let V be a finite-dimensional representation of a reductive complex
Lie algebra g. Let C be a Weyl chamber, S the set of weights of V , and
some lattice containing S and ae, the half-sum of the positive roots.
If (L; defines a reflectable walk-type, then the number b ae;ae+-;k of
random walks with k steps from ae to ae + - which stay strictly within the
principal Weyl chamber is equal to the multiplicity a -;k of the irreducible
with highest weight - in the kth tensor power of V ; and the corresponding
exponential generating functions g ae;ae+- and f - are equal.
The statement remains valid if we replace g by a connected Lie group
which is reductive or compact.
Specific cases of the theorem are implicitly known. With allowed steps
being the defining representation of
SL n or GL n ), the walks correspond to Young tableaux with at most n rows.
Likewise, the steps \Sigmae and the Weyl group B n (V a representation
of the symplectic group), correspond to up-down tableaux [14]. For relations
with orthogonal tableaux, see [10, 11, 12].
4 Classification
We outline a procedure to list all reflectable walks in a Weyl chamber, summarizing
our results in subsection 4.5.
4.1 Maximal lattices
Given a reflectable walk-type (L; S; C) in R n , with C defined by a system of
simple roots \Delta, we can embed L in a "maximal" lattice L S;C as follows. Let
- 0 be the orthogonal projection of R n onto \Delta ? , and let (ff
(This is maximal among all lattices L 0 for which (L 0 ; S; C) is a reflectable
walk-type and for which - 0 (L Counting the walks for (L; S; C) is
clearly a special case of the problem for L S;C , so we shall assume
choosing an arbitrary lattice for - 0 (L).
4.2 Classification of chambers
The simple roots \Delta defining C and W may be partitioned into minimal
subsets each orthogonal to the others:
k. We may then write
according to the classification
of Weyl groups [2, 6], the irreducible factors \Delta j ae R n j and the reflection
groups W j which they generate must be one of the classical types A
or the exceptional types indicating
the rank n j ).
4.3 Compatible steps
Given a Weyl group W and chamber C in R n , we will say that two steps
are compatible if: for each simple root ff i , (ff
have the same absolute value k i , or one of them is 0; and the projections
lattice. All the steps in S are compatible
with each other if and only if there is a lattice L such that (L;
is a reflectable walk.
be the orthogonal projection from R n to the irreducible component
reflectable if and only if all the projections
are reflectable. This is clear from the
compatibility characterization of reflectability and the discussion of maximal
lattices. Thus it suffices to classify pairs (S; C), where C is a chamber of
one of the irreducible Weyl groups listed above, and S is a W -invariant set
of mutually compatible steps. (Note that in the component R n 0 with trivial
Weyl group, any walk is reflectable.)
Example. The Weyl group A acts on Z n by permutations of
the coordinates. The roots of A n\Gamma1 span the hyperplane H of points whose
coordinates sum to 0, the orthogonal complement of which is R(e
Thus a walk will be reflectable if the projections of the steps onto H give
a reflectable walk and the sums of the coordinates of the steps generate a
discrete subgroup of R.
must be compatible with their images ws for w 2 W . (If
this holds, we say s is self-compatible.) This is the main constraint on the
possible S. To see this, we examine the W -images of an arbitrary step.
The most general form of the W -action is as follows. We fix the lengths
of ff i in one of the standard ways, and let f-! i g ae R n be the dual basis to
. Note that the reflection r i fixes
and the coefficients of r j (-! j ) are
Thus, the coefficients of r j (-! j ) are the jth column of the identity matrix
minus the Cartan matrix. That is, -
is transformed under r j by the rule
where c i;j is the number of links connecting the nodes i and j in the Dynkin
diagram of W , provided the arrow is pointed from i to j; and c
otherwise.
4.4 Classification of steps
We now find the self-compatible W -orbits of steps for each irreducible Weyl
group. The reflection law above gives some general restrictions. For instance:
for each W -orbit, consider the representative s dom which lies in the principal
Weyl chamber (i.e., all the -
Only one of the
coefficients can be nonzero, since otherwise we can easily find a chain of
reflections generating incompatible steps from s dom .
If s is any self-compatible step, then the coefficients of - ! i for i in any
parabolic subgroup of W must define a self-compatible step for that sub-
group. This allows some use of induction on the rank of W . Finally, if s is
any self-compatible step in the case of a Dynkin diagram with a node of order
3, the only i's such that (ff must lie in a parabolic subgroup
whose diagram is linear.
For the classical Weyl groups we supplement the general description of
the W -action by the usual description in terms of permutations and sign
changes in the e i basis.
Example. The symmetric group A n\Gamma1 acts on R
by permuting the n coordinate vectors e
-coefficients of the W -orbit of
are (ff . Since, for each i, these coefficients are
to stay within fk as oe varies, we conclude that at most two values
may appear among the x i . Assuming we find that
s must be a scalar multiple of one of the fundamental weights (or coweights)
We may check that these self-compatible W -orbits are compatible with each
other (provided they are scaled the same), so we have concluded the classification
in this case: up to a uniform dilation, S is any union of the W -orbits
of the fundamental weights.
For the exceptional Weyl groups, we use the -
basis and the general reflection
law to determine the self-compatible weights. The restrictions above
make the computations easy for G 2 and F 4 ; we used the program SimpLie to
exhaust the remaining possibilities for the E series.
4.5 Results of classification
A walk-type (L; S; C) in R n is reflectable if and only if its orthogonal projections
to the irreducible factors of C are reflectable.
The walk-types with irreducible Weyl chamber C and maximal lattice
are as follows. S must be the W -orbit of a dominant self-compatible
step, or a union of such W -orbits which are mutually compatible. We list
the dominant self-compatible steps in the -
(the dual of the simple
root basis), with step lengths normalized for the most mutual compatibility.
We use the Bourbaki numbering of the simple roots [2, 6], and for the Weyl
we compute in the B n root system.
The zero-step is always self-compatible dominant, and is compatible with
all other steps.
For the representation-theoretic problems corresponding to these reflect-
able walks, Theorem 2 requires the additional condition that ae lie in the
lattice. (We use the Killing form for which the square length of the long
roots is 2, so that the coweights equal the weights for simply-laced root sys-
tems.) Except for two cases, the above list gives the unique normalization of
steps for which this occurs.
One exceptional case is the weight -
1 of the root system B n . With an
additional step of 0 added, this corresponds to the defining representation
of SO 2n+1 . The steps are 0 and \Sigmae and the maximal lattice is
is not in this lattice. Thus we cannot solve
this representation-theoretic problem directly as a reflectable random walk:
instead, we must use the indirect technique given in subsection 5.5.
The other case is the weight -
n of the root system C n . The steps are the
and the maximal lattice is 2D
n , the sublattice
of Z n containing points whose coordinates are congruent modulo 2. But
is not in this lattice if n - 2. Our techniques do not
work for the resulting walks. In any case, for n - 3, the representation-
theoretic problem is not interesting; the nth fundamental representation of
2n has intermediate weights which violate the reflectability condition, and
the virtual representation with weights \Sigmae 1 \Sigma e 2 \Delta \Delta \Delta \Sigma e n is a complicated
sum of fundamental representations. For 2, the second fundamental
representation has the four weights \Sigmae 1 \Sigma e 2 and the weight 0, which gives
an interesting problem and a walk that could be handled by the technique of
subsection 5.5. However, this problem is equivalent to the problem for the
defining representation of SO 5 , using the isomorphism of the Lie algebras sp 4
and so 5 .
5 Computational techniques
The cases in which we can compute the number of random walks, or its exponential
generating function, are those cases in which the generating function
-(~u) for the steps is either a sum or a product of terms in only one variable,
and some closely related cases, such as SL n from the results for GL n .
In this section, we cover the techniques used to find the formulas. All
of the actual formulas, both for random walks and for decompositions, are
given in Section 6.
The formulas give generating functions which are determinants of Bessel
functions, or individual terms which are determinants of binomial coefficients.
Thus the generating functions are D-finite (that is, each function satisfies
a linear homogenous differential equation with polynomial coefficients), or,
equivalently, the coefficients are P-recursive [13], satisfying a relation
r
for some polynomials p i .
The Bessel function determinants of this section must clearly be related
to the formulas of Gessel [4].
5.1 The determinant technique
All cases use the same basic technique for converting the formulas in (2)
and (3) into a determinant, with the determinant coming from the sum over
the symmetric group S n ,which is either the whole Weyl group or a subgroup
of it.
The basic example is the case of the Weyl group A
allowed in both the positive and negative coordinate directions. In terms of
representation theory, this is the direct sum V \Phi V   of the defining representation
of GL n and its dual. The lattice is Z n .
Thus, using (3), with the generating function for the steps equal to
i ), the exponential generating function for the number of walks from j to
which stay within the Weyl chamber is
Y
This sum over oe can be written as a determinant, which gives
And, finally, we can simplify the terms in this determinant. We have
x 2k+m
I m is the hyperbolic Bessel function of the first kind of order m [17].
Thus the determinant above becomes
n\Thetan
For the representation-theoretic problem of Theorem 2, we have
is even, this is not in our lattice Z n , but we
can translate everything by subtracting 1from all the coordinates and get
an equivalent random walk.) For the representation with highest weight -,
we have which gives the decomposition formula
n\Thetan
This can also be used to give decomposition formulas for the adjoint
representation of GL n . We know that
is the direct sum of the adjoint
representation with one copy of the trivial. Also, we have
The weights of
representations
with
can appear in these factors. Thus, in particular,
the tensor powers of
appear only in the factor with and the
jth tensor power appears
times in the 2jth tensor power of V \Phi V   .
Thus, if we let b k be the multiplicity of the representation U , whose
highest weight has total weight 0, in the kth tensor power of
n\Thetan
We could rewrite this generating function as d - (x). However, it is not a
standard exponential generating function, because the denominator is (k!) 2
instead of k!. This prevents us from directly obtaining the decomposition
function for the adjoint representation from this generating function; if we
had the exponential generating function, we would just multiply by e \Gammax . We
can still calculate the function term by term, using (20) to calculate the first
k coefficients of d - .
We can also apply the determinant technique to (2). Consider the case
in which the steps are all the diagonals in the lattice; that is, the 2 n vectors
. The lattice is thus D
n , the weight lattice of D n , containing
points whose coordinates are all integers or all half-integers. The generating
function for the steps is
Y
Y
In the previous case, with steps in the coordinate directions, the generating
function for the steps was a sum of terms in the separate u i , and thus its
exponential was a product of such terms. Here, the function itself is a product
of terms in the separate u i , so there is no need to apply the exponential;
instead, we can compute the b j-;k explicitly.
We can get the formula for b j-;k from (2).
Y
Again, we write the sum over oe as a determinant. Since the coefficient of
\Delta , this gives us
The representation-theoretic problem is not as interesting here, because
the representation of GL n with weights
i is a complicated virtual rep-
resentation, not a natural one.
5.2 Projection from Z n onto A
The hook-length formulas (32) and (33) given in Section 6 for walks on
Z n , can also be used for the corresponding walks on the lattice A
1)g. The steps project to steps
with one coordinate
n and the others \Gamma 1
n , the weights of the defining
representation of SL n .
denote the total weight of the partition
t, then a walk of length
k with steps in the coordinate directions, starting at j, can end at - def
will be equal to the value given for b j -
-;k by (32).
Likewise, if the multiplicity of the representation with highest
weight - in the kth tensor power for SL n will be the multiplicity of the
representation with highest weight - in the kth tensor power
for GL n , as given by (33).
5.3 The multilinearity technique
In other cases, we get a determinant of a sum or difference of terms, because
the Weyl group is not just S n but a semidirect product of S n and some
coordinate changes.
The most natural example is the problem of random walks on Z n with
the Weyl group B steps in the positive or negative coordinate
directions; this corresponds to the decomposition of tensor powers of the
defining representation of Sp 2n .
Applying (3) for random walks, we get
Y
We now write the element w as a product of a oe in the symmetric group and
an ffl which negates some of the coordinates t i , thus converting u i to u
i . We
get
Y
Using the multilinearity of the products in the determinant, we can again
write the sum over oe as a determinant, with separate terms for ffl
in each entry, and these terms are again the hyperbolic Bessel
functions, so we have
In the decomposition for
as usual.
The same technique also applies, using (2) instead, for the diagonal walk
with Weyl group B this corresponds to the spin representation of
SO 2n+1 .
5.4 The splitting technique
The Weyl group D n does not lend itself directly to the multilinearity technique
which we used for B n . We need to use a trick, essentially turning the
problem into a sum over B n .
The random walk on the lattice D
n with steps in the coordinate directions
has two orbits, the points with all integer coordinates and the points with
all half-integer coordinates. The computations are valid if j and - are in
the same orbit; otherwise, the number of walks will obviously be 0. The
representation-theory problem is the decomposition of tensor powers of the
defining representation of SO 2n .
The formula for random walks is again (24), but when we
only those ffl with an even number of sign changes occur. We thus take the
sum over all ffl, but with an additional factor of (1
this factor is 1
when there are an even number of sign changes and 0 when there are an odd
number. We treat the 1=2 and the (
terms separately, which gives
Y
Y
The first term in this sum carries through just as in (25), using the determinant
technique. The second term, with no factor of ffl i , can be computed by
the same method; instead of the minus sign between the two terms in each
entry of the determinant (26), we get a plus sign.
A similar argument works for the diagonal walk on D
, corresponding to
the direct sum of the two spin representations of SO 2n .
5.5 The subgroup technique
Although D
n is the weight lattice of SO 2n+1 , the techniques we used for the
defining representations of Sp 2n and SO 2n cannot be applied directly to find
an equivalent random walk, because the ae is not in the maximal lattice Z n
for the reflectable walk. However, D n has index 2 in B n , B n is generated by
D n and the reflection in the last coordinate, and ae is now in the maximal
lattice D
n .
Thus the sum is equal to
w2Dn
ae 0 is obtained from ae by negating the last coordinate and then applying
w. This is a difference of two reflectable random walks; note that - V here
so the exponential generating functions f - (x) will be
e x times the corresponding functions for SO 2n with the same lattice. With
ae as usual, we have f -
We can thus compute the generating function for SO 2n+1 as a sum of
these two functions. However, this is a somewhat indirect argument; we
wind up computing a difference of two walks and then adding them together.
To actually compute the formulas, it is easier to work directly from (9), not
bothering to convert to reflectable random walks in Weyl chambers and then
back. We can just use the determinant and multilinearity techniques to get
the single determinant,
The subgroup technique may also be useful for other non-reflectable random
walks which become reflectable when we use a smaller Weyl group. For
example, the seven-dimensional representation of G 2 does not give a reflect-
able random walk with Weyl group G 2 , but it gives a difference of two such
walks with Weyl group A 2 . Our methods do not work to analyze the resulting
walks.
We could use the subgroup technique by considering A n\Gamma1 as a subgroup of
would give us 2 n simple determinants of the form (16), corresponding
to the 2 n choices of plus or minus signs in the n columns of (26). We could
get similar results for the diagonal walk, or the group D n .
5.6 The parity technique for the odd-dimensional orthogonal
group
The decomposition formulas for SO 2n+1 can be used to give decompositions
for O 2n+1 . Every irreducible representation U - of SO 2n+1 corresponds to two
representations U \Sigma
- of O 2n+1 , with U
- taking the transformation \Gamma1 to the
identity and U \Gamma
taking it to \Gamma1. Since the defining representation of O 2n+1
preserves the determinant, the representation U
- can occur only in even
tensor powers, and U \Gamma
- can occur only in odd tensor powers. Thus we have
The formula for f - (\Gammax) contains the determinant
det n\Thetan
I m (2x) is even if m is even and odd if m is odd, we can easily convert
this back to a determinant of I m (2x). If we replace \Gamma2x by 2x, this changes
the sign of the second term if - i +i+j is even, and of the first term if - i +i+j
is odd. In the resulting matrix, we can then negate column j if j is even,
and row i if getting
n\Thetan
From this, we can get the decomposition formula for O 2n+1 by adding this
to or subtracting it from (29).
The parity argument also works for the spin representations of O 2n+1 .
For the spin representation which preserves the determinant, we again have
that odd tensor powers presevre the determinant, while even tensor powers
do not. O 2n+1 also has another spin representation which takes \Gamma1 to the
all tensor powers of this representation take \Gamma1 to the identity.
We now present the formulas obtained by using the techniques of the previous
section, broken down by Weyl group. For each random walk, we list the
following information:
The Weyl group W , and corresponding Lie groups G.
The inequalities defining the Weyl chamber C in R n .
The set S of steps, in the usual basis e
The maximal lattice L S;C . The lattices occurring are Z n , A
The representation V of G whose tensor powers correspond to the random
walk.
Formulas for b j-;k , the number of k-step walks in C from j to -, and the
exponential generating function g j-
Formulas for a the multiplicity of the irreducible - in the kth
tensor power of the representation V of G corresponding whose weights are
the steps in S, and the exponential generating function f -
a -;k
The functions are usually given in terms of the hyperbolic Bessel functions
[17]
I m (2x) =X
x 2k+m
The techniques from Section 5 used to produce the formulas.
In some cases, there is another representation of a Lie group which does
not lead directly to a reflectable random walk problem but can be reduced to
one; such problems are listed as "Related representation". In each case,
we refer to the specific techniques, which are listed in the previous section
with examples.
6.1 Weyl group A
Lie groups GL n
Weyl chamber:
Steps:
Lattice: Z n .
Representation: Defining representation of GL n or U n .
Techniques used: Determinant, then use matrix techniques to get the
hook-length formulas [3, 9].
=number of standard skew tableaux of shape
The formula is
Y
Decomposition formula: a -;k =number of standard Young tableaux of
shape -, where
a
Y
is the hook of the square (i; j) in the Young diagram for -.
Steps:
Lattice: A n\Gamma1 .
Representation: Defining representation of SL n or SU n .
Techniques used: Project the lattice Z n onto A n\Gamma1 .
Random-walk formula: b j-;k as given by (32) for b ae+(t;t;:::;t);-;k where
Decomposition formula: a -+(t;t;:::;t);k as given by (33), where
Steps:
Lattice: Z n .
Representation: Direct sum of defining and dual representations for GL n
or U n .
Techniques used: Determinant.
Random-walk exponential generating function:
Decomposition exponential generating function:
n\Thetan
Related representation: Adjoint representation of GL n or U n .
Decomposition doubly-exponential generating function for direct sum of
the adjoint and trivial representations (see subsection 5.1):
det n\Thetan
Steps:
Lattice: D
n .
Techniques used: Determinant.
n\Thetan
The representation-theoretic problem is not interesting here.
6.2 Weyl group B
Lie groups
Weyl chamber:
Steps:
Lattice: Z n .
Representation: Defining representation for Sp 2n (see [14] for related re-
sults).
Techniques used: Determinant, multilinearity.
Random-walk exponential generating function:
n\Thetan
Decomposition exponential generating function:
n\Thetan
Steps:
Lattice: D
n .
Representations: Defining representations of SO 2n+1 and O 2n+1 .
Although the weights and Weyl group are the same in the case above,
we do not have ae in the lattice as required by Theorem 2. We can use the
Weyl group D n to get a reflectable walk, and thus the formula is given in
subsection 6.3.
Steps:
Lattice: D
n .
Techniques used: Determinant, multilinearity.
Representation: Spin representation of SO 2n+1 .
n\Thetan
Decomposition formula:
a
n\Thetan
Related representation: Spin representations of O 2n+1 .
Additional technique used: Parity.
Decomposition formula: For the spin representation which takes \Gamma1 to
the identity, the formula above is valid if the representation - takes \Gamma1 to
the identity. For the spin representation which takes \Gamma1 to itself, the above
formula is valid if the representation - takes \Gamma1 to itself for k odd, and to
the identity for k even. In the other cases, a
6.3 Weyl group D n
Lie group SO 2n
Defining representations of SO 2n+1 and O 2n+1
Weyl chamber:
Steps:
Lattice: D
n .
Techniques used: Determinant, multilinearity, splitting.
Representation: Defining representation of SO 2n (see [7, 8] for related
results).
Random-walk exponential generating function (for -
clearly 0 otherwise):
det n\Thetan
det
n\Thetan
Decomposition exponential generating function (for -
n\Thetan
(The first column of the other determinant is 0.)
Related representation: Defining representation of SO 2n+1 (see [7, 8, 10,
15] for related results). This requires that 0 be added to the list of steps,
since it is a weight of the representation.
Additional technique used: Subgroup (or work directly from (9), don't
use reflectable random walks, and use determinant and multilinearity tech-
niques).
Decomposition exponential generating function:
Related representation: Defining representation of O 2n+1 .
Additional technique used: Parity. (See subsection 5.6 for the f \Sigma
tion.)
Decomposition exponential generating function:
e x det
n\Thetan
Steps:
Lattice: D
n .
Techniques used: Determinant, multilinearity, splitting.
Representation: Sum of the two spin representations of SO 2n .
det n\Thetan
det
n\Thetan
Decomposition formula:
a -;k =2
det
n\Thetan
(The first column of the other determinant is 0.)

Acknowledgements

. We would like to thank our advisor, Nicholas
Katz, for introducing us to these problems. We would also like to thank Arun
Ram for several useful comments, including a suggestion which simplified
the calculation of the determinantal formulas from (9), and Richard Stanley,
Robert Proctor, and Persi Diaconis for several suggestions.



--R

Lectures on Lie Groups
groupes et Algebres de Lie
Representation Theory

"Random walk in a Weyl chamber,"
Introduction to Lie Algebras and Representation The- ory
"S-functions and characters of Lie algebras and superalge- bras,"
"Young-diagrammatic methods for the restriction of representations of complex classical Lie groups to reductive sub-groups of maximal rank,"
Oxford University Press
"A Robinson-Schensted algorithm for SO(2n; C ),"
"Reflection and algorithm proofs of some more Lie group dual pair identities"
"A generalized Berele-Schensted algorithm,"
"Rational tableaux and the tensor algebra of gl n ,"
"The Cauchy identity for Sp(2n),"
"Orthogonal tableaux and an insertion algorithm for SO(2n
"On an inclusion-exclusion formula based on the reflection principle,"
A Course of Modern Analysis
"Andre's reflection proof generalized to the many- candidate reflection problem,"
--TR

--CTR
David J. Grabiner, Random walk in an alcove of an affine Weyl group, and non-colliding random walks on an interval, Journal of Combinatorial Theory Series A, v.97 n.2, p.285-306, February 2002
weyl group;hyperbolic Bessel function;random walk;representation of Lie group;tensor power