%begin macros
\parskip=8pt
\magnification=\magstephalf
\parindent=0pt
\overfullrule=0in
%end macros
\rm
\bf 
RANDOM WALK IN A WEYL CHAMBER
\footnote{$^1$}{
AMS Subject Classification. Primary: 05A15, 60J15.
}
\rm 

\it 
Ira M. Gessel
\footnote{$^2$}{
Department of Mathematics, Brandeis University, Waltham, MA 02254-9110.
Supported in part by NSF grant DMS-8902666.
}
and Doron Zeilberger\rm 
\footnote{$^3$}{
Department of Mathematics, Temple University,
Philadelphia, PA 19122. Supported in part by NSF grant DMS-8800663.
}

{\bf Appeared in:} Proc. Amer. Math. Soc. {\bf 115} (1992), 27-31.

{\bf Abstract:} The classical Ballot problem that counts  the number of
ways of walking from the origin and  staying within the wedge 
$x_1 \geq x_2 \geq ... \geq x_n$ (which is a Weyl chamber for the
symmetric group), using positive unit steps, is generalized to general
Weyl groups and general sets of steps.

{\bf 0. Introduction}

To any simple and natural proof, one can ask the question:
How far can it be generalized? We will 
attempt to give one possible answer to this question
for Andre\*''s[A] celebrated solution of the two-candidate ballot
problem. Andre's proof uses a reflection argument, and we
will show that it can be naturally generalized to the context
of Coxeter-Weyl ([Co], [H], [H1], [BG]) general finite reflection groups.

Random and lattice walks form a venerable part of probability
theory and combinatorics. In a typical problem, a walker
is allowed to perform a certain number of {\it given} fundamental
steps, and must remain in a certain region of the lattice. It is
then required to find the number of ways, or probability, of
getting from an initial point to a final point. The oldest
such problem is the celebrated {\it ballot problem} 
in which it is required to find the number of ways of walking
from the origin to a typical point 
$( m_1 , ... , m_n )$ , performing positive unit steps,
such that the walk remains in the region
$x_1 \geq ... \geq x_n$.  More recently Fisher [Fis] and
Huse and Fisher [HF] used reflection arguments to
consider other such problems.

A beautiful combinatorial proof of the 2-dimensional ballot problem
was given by Andre\*' [A], using reflection. Andre\*''s elegant argument
is extended to $3$ dimensions in [G], to
$n$ dimensions in [Z] and [WM], and it was $q$-analogized
by Krattenthaler [K]
and Krattenthaler and Mohanty[KM],
who gave many far-reaching applications.

In this paper we will show that Andre\*''s
idea extends naturally to the wider context of root systems and
Weyl groups. After the first version of this paper was written,
Proctor[P] used our method to give new proofs of Cauchy-type
symmetric functions identities. We would like to thank Bob Proctor
and the referee for many helpful suggestions.

{\bf 1. Root Systems and their Weyl groups}

A {\it root system} ([H], [B], [Ca])
is a finite set of vectors in Euclidean n-space
such that the reflection of any root with respect to any hyperplane
that is perpendicular to a root is yet another root, and such that
the difference between any such root and its mirror image
with respect to any such hyperplane is an {\it integer} multiple
of the root corresponding to the hyperplane. If we allow affine
hyperplanes and affine vectors, we get {\it affine root systems}
([M1]). A root system is called {\it reduced} if for any root
$\alpha$, $k \alpha$ can't be a root unless $k= \pm 1$.
The set of linear (affine-linear) transformations 
generated by all the reflections with respect to the hyperplanes
perpendicular to the roots is called the {\it Weyl group}.

Both finite and affine root systems have been completely characterized
([B] and [M1] respectively). Every root system is a direct
sum of {\it irreducible} root systems. There are five infinite
families of irreducible finite root systems, four of which are
reduced ($A_n$, $B_n$, $C_n$, $D_n $), and
one of which is not ($BC_n$), and five exceptional
cases ($G_2$, $F_4$, $E_6$, $E_7$, $E_8$) all
of which are reduced ([B]). The irreducible, reduced, affine
root systems fall into
seven  infinite families ($A_n$, $B_n$, ${B_n}^v$,
$C_n$, ${C_n}^v$, $D_n$, $BC_n$), and
seven exceptional cases ($G_2$, 
${G_2}^v$, $F_4$,
${F_4 }^v$, $E_6$, $E_7$, $E_8 $ ([M1]).)
We refer the reader to the comprehensive {\it planches} of
[B] and the appendix of [M1] for a description of these
root systems. For example the finite root system $A_n$
consists of the $n(n-1)$ vectors 
{$ e_i - e_j , \, 1 \leq i \neq  j \leq n $}, 
where $e_i$ is the unit vector with all zeroes except
the $i^{th}$ component which is $1$, and its Weyl
group is the symmetric group acting by permuting the coordinates.

The Weyl group of a finite root system is a finite group,
and that of an affine root system is a discrete group acting
locally finitely. The complement of the union of all the hyperplanes
is an open set, and its connected components are called
{\it Weyl chambers}. It is easy to see that any Weyl chamber
is a fundamental region for the action of the Weyl group. 

{\bf  2. The Fundamental Formula}

We will use the notation of [H] and [M1].
Let $R$ be a finite or affine root system, let $W$ be its
Weyl group, and let $\Delta$ be any of its bases.
The length of an element $w$ of the Weyl group, $l(w)$, is
the least number of terms possible
to express $w$ as a product of fundamental reflections 
$\sigma_{\alpha}$, $\alpha \epsilon \Delta$.
We will consider 
random walk in a lattice $L$ embedded in the euclidean space
in which $R$ resides, with inner
product inherited from it, and which is invariant under the 
action of the Weyl group: $ g L = L$ for every $g$ in $W$.
We fix a set of allowable steps $S$, that is a finite subset of
$L$ which is also invariant under the Weyl group:$WS=S$.
We will also assume that for any
$\alpha$ in $\Delta$, the non-zero values of $( \alpha , s )$, as
$s$ ranges over $S$, are $\pm k( \alpha )$, where $k ( \alpha )$
is a fixed number that depends only on
$\alpha$. Now, for any positive integer $m$, and any two lattice points
$a$ and $b$, let

$$
  WALK_m ( a \rightarrow b ) 
$$

be the number of walks from $a$ to
$b$, using exactly $m$ steps
drawn from the set $S$.

Let $a$ and $b$ be two lattice points that belong to
the fundamental Weyl chamber 

$$
  C:= \, \{ x \epsilon L  \,: \, (x , \alpha ) > 0  \,for \,every \,alpha \} 
$$

and such that for every $\alpha$ in $ \Delta$,
$(a, \alpha )$ and  $(b, \alpha )$ are integral multiples
of  $k ( \alpha )$.
We are interested in 

$$
  WALK_m^G( a \rightarrow b ) \,, 
$$

the number of walks from $a$ to $b$ that always stay strictly within
the Weyl chamber $C$. The fundamental result of our
paper is the following theorem.

{\bf Theorem 1:} With the above notation and assumptions, we have

$$
 WALK_m^G(a \rightarrow b )  \,= \, \sum_{ w \epsilon W } (-1)^{l(w)} WALK_m (w(a) \rightarrow b ) \,. 
\eqno(1)
$$         

{\bf Proof}: The proof is modeled after [Z], (where as
Krattenthaler [K] observed, "first" should be replaced
by  "last").
Totally order the roots of $\Delta$ by some arbitrary but fixed
order.
Let $WALK_m^B(a \rightarrow b ) $ be the number of
{\it bad} walks from $a$ to $b$, i.e., walks that
bump into at least one of the walls of $C$, 
{ $x \,: \,(x, \alpha )=0$ } for some $\alpha$ in $\Delta$.
The assumption on
$S$, that the absolute value of $( \alpha , s )$ is either
zero or a constant that only depends on $\alpha$, guarantees that
every walk that crosses a wall must touch it, i.e., it
is not possible to get from inside $C$ to outside $C$ and vice
versa, without pausing on some wall.
Thus

$$
 WALK_m^G(a \rightarrow b )  \,= \, WALK_m  (a \rightarrow b )  \,- \, WALK_m^B(a \rightarrow b ) . 
\eqno(2)
$$         

We now claim that

$$
 \sum_{ w \epsilon W } (-1)^{l(w)} WALK_m^B(w(a) \rightarrow b ) \,= \,0. 
\eqno(3)
$$          

Indeed, let $walk:=( s_1 , ... , s_n )$ be a typical bad walk
from, say, $w(a)$ to $b$. This means that the walker bumps into
at least one wall $(x, \alpha ) =0$, $\alpha \epsilon \Delta$. Let
$\alpha$ be the fundamental root corresponding to the
last visit to a wall. In case of a "tie", in which that last visit
takes place on more than one wall, let $\alpha$ be the "largest" such
root in the above mentioned total order.
We pair to this walk the walk
from $w_{\alpha} w (a)$ to $b$ obtained by reflecting,
with respect to $(x, \alpha )=0$, that portion
of the walk until the last visit to the wall $( x, \alpha )=0$.
In symbols, if the last visit to a wall was at the $r^{th}$
step, and the walk from $w(a)$ to $b$ was 
$( s_1 , ... , s_m )$, then
the paired walk, from $w_{\alpha} w (a)$ to $b$ is
$ ( w_{\alpha} ( s_1 ) , ... , w_{\alpha} ( s_r )  ,$
$s_{r+1} , ... , s_m )$. This pairing of walks is clearly
an involution, since $w_{\alpha}$ is an involution. It is sign
reversing, since the length of $w$ and $w_{\alpha} w$ have opposite
parity. It follows that all the terms in (3) can be arranged in
mutually canceling pairs, and thus the sum total is zero.

Now, if $w$ is not the identity, $w(a)$ is outside $C$,
since $C$ is a fundamental region, and so every walk
from $w(a)$ to $b$ must cross a wall, and hence is bad,
so 

$$
 WALK_m^B( w(a) \rightarrow b ) \,= \, WALK_m  ( w(a) \rightarrow b ), \, \,  w \neq  identity  \,. 
\eqno(4)
$$         

Combining (2), (3),  and (4) yields (1). QED

In the affine case, the Weyl group is infinite, but since it is
discrete, the sum in (1) is always finite. It is readily seen
that for the affine root system $S( A_n )$, (1) reduces to
Filaseta's theorem ([Fil], p. 103), since the Weyl group of 
$S( A_n )$ is the semi-direct product of the symmetric group
and the group of translations on the lattice $M$, described in
[M1], p. 92.

{\bf 3. Constant Term and Integral Representation Formulas}

We will now derive some constant term and integral representation
formulas for $WALK_m (a \rightarrow b)$ and $WALK_m^G( a \rightarrow b)$, for
finite root-systems. First we will deal with the simple case
of unrestricted walks. If the walk takes place in $Z^n$, then
let $x_1$, ..., $x_n$ be indeterminates. For any vector
of integers $a= ( a_1 , ... , a_n )$, let

$$
  x^a := x_1^{a_1} ... x_i^{a_i} ... x_n^{a_n}, \, \, \, 
$$

otherwise, we think of $x^a$ as "formal exponetial".
For our set of steps $S$, let

$$
  \Phi (x) :=   \sum_{ s \epsilon S } x^{s \,}. 
$$

Recall that a {\it Laurent polynomial} is a linear combination of
exponents $x^a$. The {\it constant term} of a Laurent polynomial
$f$, denoted by $CT f$, is the coefficient of $x^0$.
The following theorem is almost trivial:

{\bf Theorem 2}: 

$$
 WALK_m (a \rightarrow b) = CT  \, \Phi (x)^m / x^{b-a}  \,. 
\eqno(5)
$$          

{\bf Proof:} Obviously
$WALK_m (a \rightarrow b) = WALK_m (0 \rightarrow b-a)$, so without loss of 
generality,
we can assume that $a=0$, since every step is independent of the
others.  When we multiply out $\Phi (x)^m$, every term, before
simplification, corresponds to a walk with $m$ steps, and those
terms that evaluate to $x^b$ correspond to walks that end at $b$,
so the coefficient of $x^b$ gives exactly  
$WALK_m (0 \rightarrow b)$.  QED

Combining Theorems 1 and 2, we have 

{\bf Theorem 3:} 

$$
 WALK_m^G(a \rightarrow b ) = CT  \,[ \, \Phi (x)^m x^{-b}   \sum_{w \epsilon W} (-1)^{l(w)} x^{w(a) \,]}  \,. 
\eqno(6)
$$         

For special values of $a$, the sum on the right side of (6) 
factorizes nicely,
thanks to the celebrated {\it Weyl denominator formula} ([H], p. 138;
[Ca], p. 149), which we now recall. Let $\delta$ be one half of the sum
of all the positive roots:

$$
   \delta := (1/2) \sum_{\alpha \epsilon R^+ } \alpha  \,. 
$$

Then we have

{\bf The Weyl Denominator Formula}

$$
  \sum_{ w \epsilon W } (-1)^{l(w)} x^{ w( \delta ) } =  x^{- \delta} \prod_{ \alpha \epsilon R^+ }   ( x^{\alpha} -1 ) \,. 
$$

Plugging this into Theorem 3 we have:

{\bf Theorem 4:} For any scalar $c$ such that $c \delta $ 
is a lattice point,
and for any lattice vector $\lambda$ that is invariant under the
Weyl group (i.e., $w( \lambda ) = \lambda$ for every $w$ in $W$), and 
such that $( \lambda + c \delta , \alpha )$ is an integral multiple
of $k( \alpha )$ for every $\alpha$ in $\Delta$, we have

$$
 WALK_m^G(  \, \lambda + c \delta   \,\rightarrow  \, b ) = CT \, [ \Phi (x)^m   x^{-b+ \lambda - c \delta } \prod_{ \alpha \epsilon R^+ }   ( x^{c \alpha} -1 ) \,] \,. 
\eqno(7)
$$        

If we replace each $x_j$ with $e^{i \theta_j}$, 
$j= 1, ... ,  n$,  and replace the operator "constant term" with that of
integration over the torus
$[0, \, 2 \pi ]^n$, Theorems 3 and 4 become
integral representation formulas, from which it is possible, in
many cases, to obtain asymptotic formulas, generalizing the formulas
on p. 676 of Fisher [Fis]. 
Let us mention that the constant $A_p$ appearing
in formulas (4.9) and (4.10) of [Fis] can be evaluated explicitly
by Mehta's [M2] integral, and its analogs for the other root-systems
follow from the Macdonald-Mehta conjectures, proved for the infinite
families by Regev and Beckner (see [M2]), for $F_4$ by Garvan [Ga],
and for all root systems by Opdam[O].

{\it REFERENCES}

[A] Andr\'e, D., \it 
Solution directe du probl\`eme r\'esolu
par M. Bertrand\rm 
, C. R. Acad. Sci. Paris {\bf 105} (1887),
436-437.

[BG] Benson, C. T., and Grove, L. C., "{\it Finite Reflection Groups}",
Bogden \& Quigley, Terrytown-on-Hudson, NY, 1971.

[B] Bourbaki. N., "{\it Groupes et alg\`ebres de Lie}", chaps. 4, 5, 
and 6, Hermann, Paris, 1968.

[Ca] Carter, R. W., "{\it Simple Groups of Lie Type}", John Wiley,
London, 1972.

[Co] Coxeter, H. S. M., {\it Discrete groups generated by reflections},
Ann. Math. {\bf 35} (1934), 588-621.

[Fil] Filaseta, M., \it 
A new method for solving a class of ballot
problems\rm 
, J. Combin. Theory Ser. A {\bf 39} (1985), 102-111.

[Fis] Fisher, M. E., {\it Walks, walls, wetting, and melting},
J. Stat. Phys. {\bf 34} (1984), 667-729.

[Ga] Garvan, F., \it 
Some Macdonald-Mehta integrals by brute
force\rm 
, in "{\it q-Series and Partitions}", D. Stanton, editor,
IMA Volumes in Mathematics and its Applications, Springer, New York,
1989.

[Gr] Grossman, H. D., {\it Fun with lattice points}, Scripta Math.
{\bf 16} (1950), 206-212.

[H] Humphreys, J. E., \it 
"Introduction to Lie Algebras and
Representation Theory"\rm 
, Springer, New York, 1972.

[H1] Humphreys, J. E., {\it "Reflection Groups and Coxeter Groups"},
Cambridge University Press, Cambridge, 1990.

[HF] Huse, D., and Fisher, M. E., \it 
Commensurate melting,
domain walls, and dislocations\rm 
, Physical Review B {\bf 29}
(1984), 239-270.

[K] Krattenthaler, C., \it 
Enumeration of lattice paths and
generating functions for skew plane partitions\rm 
, Manuscripta
Math. {\bf 63} (1989), 129-155.

[KM] Krattenthaler, C., and Mohanty, S. G., \it 
q-Generalizations of
a ballot problem\rm 
, preprint.

[M1] Macdonald, I. G., \it 
Affine root systems and Dedekind's 
$eta$-function\rm 
, Inv. Math. {\bf 15} (1972), 91-143.

[M2] Macdonald, I. G., \it 
Some conjectures for root systems and
finite reflection groups\rm 
, SIAM J. Math. Anal., {\bf 13} (1982),
988-1007.

[O] Opdam, E., \it 
Some applications of hypergeometric shift
operators\rm 
, Inv. Math. {\bf 98} (1989), 1-18.

[P] Proctor, R. A., \it 
Reflection and algorithm proofs of some more
Lie group dual pair identities\rm 
, preprint.

[WM] Watanabe, T., and Mohanty, S. G., \it 
On an inclusion-exclusion
formula based on the reflection principle\rm 
, Discrete Math. {\bf 64}
(1987), 281-288.

[Z] Zeilberger, D., \it 
Andr\'e's reflection proof generalized to
the many-candidate ballot problem\rm 
, 
Discrete Math. {\bf 44} (1983), 325-326.
\end




