\documentclass[12pt]{amsart}

\usepackage{amsmath,amsfonts}

\textwidth137mm
\textheight200mm

\newtheorem{theorem}{Theorem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Input-Datei zum Erzeugen von Gitterpunktwegen.%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%LaTeX-Version%
%%%%%%%%%%%%%%%
%entering a path: 
%  \Pfad(x-coordinate of starting point,y-coordinate of starting point),path
%  as 1-2-3-4-5-6-7-8-word\endPfad
%(1=step in x-direction, 2=step in y-direction, 3=upward diagonal step, 4=downward diagonal step)
%(5=step in negative x-direction, 6=step in negative y-direction, 7=downward left diagonal step, 8=upward left diagonal step)
%
%entering a dotted path: 
%  \SPfad(x-coordinate of starting point,y-coordinate of starting point),path
%  as 1-2-3-4-5-6-7-8-word\endSPfad
%(1=step in x-direction, 2=step in y-direction, 3=upward diagonal step, 4=downward diagonal step)
%(5=step in negative x-direction, 6=step in negative y-direction, 7=downward left diagonal step, 8=upward left diagonal step)
%
%coordinate-axes:
%  \Koordinatenachsen(length of positive x-axes, length of positive y-axes)(length of negative x-axes, length of negative y-axes)
%The length of negative axes are entered as negative numbers.
%
%lattice:
%  \Gitter(number of points in positive x-direction, number of points in positive y-direction)(number of points in negative x-direction, number of points in negative y-direction)
%
%diagonal lines:
%  \Diagonale(x-coordinate of SW-most point,y-coordinate of SW-most point)length of the projection on the x-axes
%
%antidiagonal lines:
%  \AntiDiagonale(x-coordinate of NW-most point,y-coordinate of NW-most point)length of the projection on the x-axes
%
%labelling of points:
%  \Label[location?]{[label]}(x-coordinate,y-coordinate)
%where:
%  [location?]=\l,\lo,\lu,\r,\ro,\ru,\o,\u
%and l=left, r=right, u=bottom, o=top.
%In addition, if by \Einheit?cm the basic unit is changed, there exist
%\llo,\loo,\llu,\luu,\rro,\roo,\rru,\ruu.
%
%The basic unit can be changed by entering
%  \Einheit=?cm
%The default is \Einheit=0.5cm.
%
%The thickness of the paths can be changed by entering
%     \PfadDicke{?cm}
%The default is \PfadDicke=1pt.
%
%The following point sizes are available:
%\DuennPunkt, \NormalPunkt, \DickPunkt. Syntax:
%  \DickPunkt(x-coordinate,y-coordinate), etc.
%
%Besides, a circle is available by \Kreis. Syntax:
%  \Kreis(x-coordinate,y-coordinate)
%
\catcode`\@=11
\font\tenln    = line10
\font\tenlnw   = linew10

\thinlines
\newskip\Einheit \Einheit=0.6cm
\newcount\xcoord \newcount\ycoord
\newdimen\xdim \newdimen\ydim \newdimen\PfadD@cke \newdimen\Pfadd@cke
\PfadD@cke1pt \Pfadd@cke0.5pt
\def\PfadDicke#1{\PfadD@cke#1 \divide\PfadD@cke by2 \Pfadd@cke\PfadD@cke \multiply\PfadD@cke by2}
\long\def\LOOP#1\REPEAT{\def\BODY{#1}\ITERATE}
\def\ITERATE{\BODY \let\next\ITERATE \else\let\next\relax\fi \next}
\let\REPEAT=\fi
\def\Punkt{\hbox{\raise-2pt\hbox to0pt{\hss\scriptsize$\bullet$\hss}}}
\def\DuennPunkt(#1,#2){\unskip
  \raise#2 \Einheit\hbox to0pt{\hskip#1 \Einheit
          \raise-2.5pt\hbox to0pt{\hss\normalsize$\bullet$\hss}\hss}}
\def\NormalPunkt(#1,#2){\unskip
  \raise#2 \Einheit\hbox to0pt{\hskip#1 \Einheit
          \raise-3pt\hbox to0pt{\hss\large$\bullet$\hss}\hss}}
\def\DickPunkt(#1,#2){\unskip
  \raise#2 \Einheit\hbox to0pt{\hskip#1 \Einheit
          \raise-4pt\hbox to0pt{\hss\Large$\bullet$\hss}\hss}}
\def\Kreis(#1,#2){\unskip
  \raise#2 \Einheit\hbox to0pt{\hskip#1 \Einheit
          \raise-4pt\hbox to0pt{\hss\Large$\circ$\hss}\hss}}
\def\Diagonale(#1,#2)#3{\unskip\leavevmode
  \xcoord#1\relax \ycoord#2\relax
      \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit
         \unitlength\Einheit
         \line(1,1){#3}\hss}}
\def\AntiDiagonale(#1,#2)#3{\unskip\leavevmode
  \xcoord#1\relax \ycoord#2\relax \advance\xcoord by -0.05\relax
      \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit
         \unitlength\Einheit
         \line(1,-1){#3}\hss}}
\def\Pfad(#1,#2),#3\endPfad{\unskip\leavevmode
  \xcoord#1 \ycoord#2 \thicklines\ZeichnePfad#3\endPfad\thinlines}
\def\ZeichnePfad#1{\ifx#1\endPfad\let\next\relax
  \else\let\next\ZeichnePfad
    \ifnum#1=1
      \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit
         \vrule height\Pfadd@cke width1 \Einheit depth\Pfadd@cke\hss}%
      \advance\xcoord by 1
    \else\ifnum#1=2
      \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit
        \hbox{\hskip-\PfadD@cke\vrule height1 \Einheit width\PfadD@cke depth0pt}\hss}%
      \advance\ycoord by 1
    \else\ifnum#1=3
      \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit
         \unitlength\Einheit
         \line(1,1){1}\hss}
      \advance\xcoord by 1
      \advance\ycoord by 1
    \else\ifnum#1=4
      \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit
         \unitlength\Einheit
         \line(1,-1){1}\hss}
      \advance\xcoord by 1
      \advance\ycoord by -1
    \else\ifnum#1=5
      \advance\xcoord by -1
      \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit
         \vrule height\Pfadd@cke width1 \Einheit depth\Pfadd@cke\hss}%
    \else\ifnum#1=6
      \advance\ycoord by -1
      \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit
        \hbox{\hskip-\PfadD@cke\vrule height1 \Einheit width\PfadD@cke depth0pt}\hss}%
    \else\ifnum#1=7
      \advance\xcoord by -1
      \advance\ycoord by -1
      \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit
         \unitlength\Einheit
         \line(1,1){1}\hss}
    \else\ifnum#1=8
      \advance\xcoord by -1
      \advance\ycoord by +1
      \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit
         \unitlength\Einheit
         \line(1,-1){1}\hss}
    \fi\fi\fi\fi
    \fi\fi\fi\fi
  \fi\next}
\def\hSSchritt{\leavevmode\raise-.4pt\hbox to0pt{\hss.\hss}\hskip.2\Einheit
  \raise-.4pt\hbox to0pt{\hss.\hss}\hskip.2\Einheit
  \raise-.4pt\hbox to0pt{\hss.\hss}\hskip.2\Einheit
  \raise-.4pt\hbox to0pt{\hss.\hss}\hskip.2\Einheit
  \raise-.4pt\hbox to0pt{\hss.\hss}\hskip.2\Einheit}
\def\vSSchritt{\vbox{\baselineskip.2\Einheit\lineskiplimit0pt
\hbox{.}\hbox{.}\hbox{.}\hbox{.}\hbox{.}}}
\def\DSSchritt{\leavevmode\raise-.4pt\hbox to0pt{%
  \hbox to0pt{\hss.\hss}\hskip.2\Einheit
  \raise.2\Einheit\hbox to0pt{\hss.\hss}\hskip.2\Einheit
  \raise.4\Einheit\hbox to0pt{\hss.\hss}\hskip.2\Einheit
  \raise.6\Einheit\hbox to0pt{\hss.\hss}\hskip.2\Einheit
  \raise.8\Einheit\hbox to0pt{\hss.\hss}\hss}}
\def\dSSchritt{\leavevmode\raise-.4pt\hbox to0pt{%
  \hbox to0pt{\hss.\hss}\hskip.2\Einheit
  \raise-.2\Einheit\hbox to0pt{\hss.\hss}\hskip.2\Einheit
  \raise-.4\Einheit\hbox to0pt{\hss.\hss}\hskip.2\Einheit
  \raise-.6\Einheit\hbox to0pt{\hss.\hss}\hskip.2\Einheit
  \raise-.8\Einheit\hbox to0pt{\hss.\hss}\hss}}
\def\SPfad(#1,#2),#3\endSPfad{\unskip\leavevmode
  \xcoord#1 \ycoord#2 \ZeichneSPfad#3\endSPfad}
\def\ZeichneSPfad#1{\ifx#1\endSPfad\let\next\relax
  \else\let\next\ZeichneSPfad
    \ifnum#1=1
      \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit
         \hSSchritt\hss}%
      \advance\xcoord by 1
    \else\ifnum#1=2
      \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit
        \hbox{\hskip-2pt \vSSchritt}\hss}%
      \advance\ycoord by 1
    \else\ifnum#1=3
      \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit
         \DSSchritt\hss}
      \advance\xcoord by 1
      \advance\ycoord by 1
    \else\ifnum#1=4
      \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit
         \dSSchritt\hss}
      \advance\xcoord by 1
      \advance\ycoord by -1
    \else\ifnum#1=5
      \advance\xcoord by -1
      \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit
         \hSSchritt\hss}%
    \else\ifnum#1=6
      \advance\ycoord by -1
      \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit
        \hbox{\hskip-2pt \vSSchritt}\hss}%
    \else\ifnum#1=7
      \advance\xcoord by -1
      \advance\ycoord by -1
      \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit
         \DSSchritt\hss}
    \else\ifnum#1=8
      \advance\xcoord by -1
      \advance\ycoord by 1
      \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit
         \dSSchritt\hss}
    \fi\fi\fi\fi
    \fi\fi\fi\fi
  \fi\next}
\def\Koordinatenachsen(#1,#2){\unskip
 \hbox to0pt{\hskip-.5pt\vrule height#2 \Einheit width.5pt depth1 \Einheit}%
 \hbox to0pt{\hskip-1 \Einheit \xcoord#1 \advance\xcoord by1
    \vrule height0.25pt width\xcoord \Einheit depth0.25pt\hss}}
\def\Koordinatenachsen(#1,#2)(#3,#4){\unskip
 \hbox to0pt{\hskip-.5pt \ycoord-#4 \advance\ycoord by1
    \vrule height#2 \Einheit width.5pt depth\ycoord \Einheit}%
 \hbox to0pt{\hskip-1 \Einheit \hskip#3\Einheit 
    \xcoord#1 \advance\xcoord by1 \advance\xcoord by-#3 
    \vrule height0.25pt width\xcoord \Einheit depth0.25pt\hss}}
\def\Gitter(#1,#2){\unskip \xcoord0 \ycoord0 \leavevmode
  \LOOP\ifnum\ycoord<#2
    \loop\ifnum\xcoord<#1
      \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit\Punkt\hss}%
      \advance\xcoord by1
    \repeat
    \xcoord0
    \advance\ycoord by1
  \REPEAT}
\def\Gitter(#1,#2)(#3,#4){\unskip \xcoord#3 \ycoord#4 \leavevmode
  \LOOP\ifnum\ycoord<#2
    \loop\ifnum\xcoord<#1
      \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit\Punkt\hss}%
      \advance\xcoord by1
    \repeat
    \xcoord#3
    \advance\ycoord by1
  \REPEAT}
\def\Label#1#2(#3,#4){\unskip \xdim#3 \Einheit \ydim#4 \Einheit
  \def\lo{\advance\xdim by-.5 \Einheit \advance\ydim by.5 \Einheit}%
  \def\llo{\advance\xdim by-.25cm \advance\ydim by.5 \Einheit}%
  \def\loo{\advance\xdim by-.5 \Einheit \advance\ydim by.25cm}%
  \def\o{\advance\ydim by.25cm}%
  \def\ro{\advance\xdim by.5 \Einheit \advance\ydim by.5 \Einheit}%
  \def\rro{\advance\xdim by.25cm \advance\ydim by.5 \Einheit}%
  \def\roo{\advance\xdim by.5 \Einheit \advance\ydim by.25cm}%
  \def\l{\advance\xdim by-.30cm}%
  \def\r{\advance\xdim by.30cm}%
  \def\lu{\advance\xdim by-.5 \Einheit \advance\ydim by-.6 \Einheit}%
  \def\llu{\advance\xdim by-.25cm \advance\ydim by-.6 \Einheit}%
  \def\luu{\advance\xdim by-.5 \Einheit \advance\ydim by-.30cm}%
  \def\u{\advance\ydim by-.30cm}%
  \def\ru{\advance\xdim by.5 \Einheit \advance\ydim by-.6 \Einheit}%
  \def\rru{\advance\xdim by.25cm \advance\ydim by-.6 \Einheit}%
  \def\ruu{\advance\xdim by.5 \Einheit \advance\ydim by-.30cm}%
  #1\raise\ydim\hbox to0pt{\hskip\xdim
     \vbox to0pt{\vss\hbox to0pt{\hss$#2$\hss}\vss}\hss}%
}
\catcode`\@=12



\begin{document}

\title[]{Lattice path combinatorics --- applications
to probability and statistics}
\author[]{C. Krattenthaler and S. G. Mohanty}

\maketitle

A {\it lattice path} $P$ in $\mathbb Z^d$ is a path in the $d$-dimensional
integer lattice $\mathbb Z^d$ which uses only points of the lattice,
that is, it is a sequence $(P_0,P_1,\dots,P_l)$, where $P_i\in \mathbb
Z^d$ for all $i$. The vectors
$\overrightarrow {P_0P_1},\overrightarrow {P_1P_2}, \dots, \overrightarrow
{P_{l-1}P_{l}}$ are called the {\em steps} of $P$. The number of
steps, $l$, is called the {\em length} 
of $P$, and denoted by $\ell(P)$. Figure~\ref{fig1} shows a lattice path
in $\mathbb Z^2$ of length $11$. (The horizontal line labelled 
$y=R-2$ should be
ignored at the moment.)

\newbox\figbox
\setbox\figbox\hbox{\small 
A lattice path}

\begin{figure}[h]
$$
\Gitter(12,5)(-1,0)
\Koordinatenachsen(12,5)(-1,0)
\Pfad(0,1),13141133444\endPfad
\DickPunkt(0,1)
\DickPunkt(11,0)
\PfadDicke{.5pt}
\Pfad(-2,4),11111111111111\endPfad
\Label\l{y=R-2}(-3,4)
\hbox{\hskip6.5cm}
$$
\caption{\unhbox\figbox}
\label{fig1}
\end{figure}

The interest in the combinatorial study of lattice paths in a
statistical context arises primarily 
from three different sources: {\it random walks},
{\it rank order statistics} for {\it non-parametric testing}, and
{\it queueing processes}. In
most cases one is concerned with 2-dimensional lattice paths, i.e., 
with the case $d=2$.

The prototypical example of a random walk problem is the {\it
gambler's ruin problem} (see also \cite[Ch.~XIV]{FellAA}): 
two players $A$ and $B$ have initially $a$
and $R-a$ dollar, respectively. They play several rounds, in each of
which the probability that player $A$ wins is $p_A$, the probability
that player $B$ wins is $p_B$, and that there is a tie is $p_T=1-p_A-p_B$.
If one player wins,
(s)he takes a dollar from the other.
If there is a tie, nothing happens. The play stops when one of the
players is bankrupt. What is the probability that
player $A$, say, goes bankrupt after $N$ rounds ? 

By disregarding the last round (which is necessarily a round in which
$B$ wins),
this problem can be represented by a lattice path starting at 
$(0,a-1)$, ending at $(N-1,0)$, 
with steps $(1,1)$
(corresponding to player $A$ to win a round), $(1,-1)$
(corresponding to player $B$ to win a round), and
$(1,0)$ (corresponding to a tie), which does not pass below the
$x$-axis, and which does not pass above the
horizontal line $y=R-2$. For example, the lattice path in Figure~\ref{fig1}
corresponds to the play, where player~A starts with 2~dollar, player~B
starts with 4~dollar, the
outcome of the rounds is in turn TATBTTAABBBB (the letter $A$ symbolizing
a round where $A$ won, with an analogous meaning of the letter $B$,
and the letter $T$ symbolizing a tie), so that $A$ goes bankrupt
after $N=12$ rounds (while $B$ did not). 

If we assign the {\it
weight\/} $p_A$ to an up-step $(1,1)$, $p_B$ to a down-step $(1,-1)$,
and $p_T$ to a level-step $(1,0)$, then the probability of this play
is the product of the weights of all the steps of the path $P$
times $p_B$
(corresponding to the last round where $B$ wins and $A$ goes bankrupt;
in our example, it is $p_Tp_Ap_Tp_Bp_Tp_Tp_Ap_Ap_Bp_Bp_Bp_B$). If we
write $p(P)$ for the product of the weights of the steps of $P$, 
then, in order to solve 
the problem, we need to compute the sum $\sum _{P} ^{}p_Bp(P)$, where
the sum is over all the above described paths from $(0,a-1)$ to $(N-1,0)$.

This problem is solved, in terms of generating functions, by the
general theorem below, which shows that the solution is provided
by {\it orthogonal polynomials}. For the statement of the theorem, we
slightly modify and generalize the lattice path problem. We consider
three-step 
lattice paths as above\footnote{In the combinatorial literature,
the term {\it Motzkin path\/} is often used for the special 
three-step lattice paths
that start at the origin, return to the $x$-axis, and do not pass below
the $x$-axis. Furthermore, the term {\it Dyck path} is used
for Motzkin paths without any level-step.} 
(i.e., consisting of up-steps $(1,1)$, down-steps
$(1,-1)$, and level-steps $(1,0)$), 
starting at $(0,r)$ and ending at $(\ell,s)$, which do
not pass below the $x$-axis and do not pass above the horizontal line
$y=K$. Furthermore, we assign the weight 1 to an
up-step, the
weight $b_h$ to a level-step at height $h$, and the weight $\lambda_h$
to a down-step from height $h$ to $h-1$. The weight $w(P)$
of a path $P$ is defined as the product of the weights of all its
steps.\footnote{Clearly, these three-step paths can also be
interpreted as a discrete-time birth-death process with stay, where
the number of individuals in the process does not exceed $K$ (see
\cite{BoKMAA}). There is as well a Markov chain interpretation, see
\cite[Ch.~XVI]{FellAA}.}
The gambler's ruin problem that we considered above
corresponds to the choices $K=R-2$, $r=a-1$, $s=0$, $b_h=p_T$, and
$\lambda_h=p_Ap_B$ in the more general problem. (This is because, for any
three-step path from $(0,a-1)$ to $(\ell,0)$, the difference of the numbers
of down- and up-steps is $a-1$, and, thus, the described weighting differs
from the weight which results by weighting an up-step by $p_A$, a down-step
by $p_B$, and a level-step by $p_t$ always by a factor of $p_A^{a-1}$,
regardless of $\ell$.)

\begin{theorem}\leavevmode\hbox{\hskip-5pt}\footnote{For 
self-contained derivations see e.g.\ \cite[Appendix]{KratBP}
or \cite[Eqs.~(4)/(5)]{MohaAZ}.} \label{A2}
Define the sequence $(p_n(x))_{n\ge0}$ of polynomials
by
\begin{equation} \label{A.2} 
xp_{n}(x)=p_{n+1}(x)+b_np_n(x)+\lambda_{n}p_{n-1}(x),\quad \quad 
\text{ for } n\geq 1,
\end{equation}
with initial conditions $p_0(x)=1$ and $p_1(x)=x-b_0$.
Furthermore, define\break $(Sp_n(x))_{n\ge0}$ to be the sequence of
polynomials which arises from the sequence $(p_n(x))$ by replacing $\lambda_i$ by
$\lambda_{i+1}$ and $b_i$ by $b_{i+1}$, $i=0,1,2,\dots$, everywhere in
the three-term recurrence \eqref{A.2} and in the initial
conditions. Finally, given a polynomial $p(x)$ of degree $n$, we
denote the corresponding reciprocal polynomial
$x^np(1/x)$ by $p^*(x)$.

With the weight $w$ defined as before, the generating function $\sum
_{P} ^{}w(P)x^{\ell(P)}$, where the sum is over all
three-step paths which start at $(0,r)$, terminate at height $s$,
do not pass below the $x$-axis,
and do not pass above the line $y=K$, is given by
\begin{equation} \label{eq:gf} 
\begin{cases} \dfrac {x^{s-r}p^*_r(x)S^{s+1}p_{K-s}^*(x)} {p_{K+1}^*(x)}
&r\le s,\\
\lambda_r\cdots\lambda_{s+1}\dfrac {x^{r-s}p^*_s(x)S^{r+1}p_{K-r}^*(x)}
{p_{K+1}^*(x)}
&r\ge s.
\end{cases}
\end{equation}
\end{theorem}

We remark that in the case that $r=s=0$ there is also an elegant
expression for the generating function due to Flajolet \cite{FlajAA}
in terms of a continued fraction.

In order to solve our problem, we just have to extract the coefficient
of $x^\ell$ in \eqref{eq:gf}. By a partial fraction expansion, 
a formula of the type
\begin{equation} \label{eq:part} 
\sum _{m} ^{}c_m\xi_m^\ell,
\end{equation}
results, where the $\xi_m$'s are the zeroes of $p_{K+1}(x)$, and the
$c_m$'s are some coefficients, only a finite number of them being non-zero.
In particular, the asymptotic behaviour of \eqref{eq:part} 
is typically governed by the
$\xi_m$'s of largest absolute value, i.e., it is of the form
\begin{equation} \label{eq:asy} 
\sum _{m:\vert \xi_m\vert=M} ^{}c_m\xi_m^\ell,
\end{equation}
where $M$ denotes $\max_m\vert\xi_m\vert$.
A difficulty would occur when this expression vanishes.
However, under ``normal" circumstances, this event rarely occurs.
For, by Favard's theorem (see \cite[Th\'eor\`eme~9 on
p.~I-4]{VienAE} or \cite[Theorem 50.1]{WallCF}), 
the sequence of polynomials $(p_n(x))_{n\ge0}$
is in fact a sequence of {\it orthogonal polynomials}.
It is then known by general facts about orthogonal polynomials 
(see e.g.\ \cite[Theorem~3.3.1]{SzegOP}) that if
all $b_n$'s are real and $\lambda_n>0$ for all $n$, 
all the zeroes of $p_{n}(x)$ are in fact real and simple.

It should be noted that, because of the many available parameters (the
$b_n$'s and $\lambda_n$'s), by appropriate specializations one can also
obtain numerous results about enumerating three-step paths according
to various statistics, such as the number of touchings on the bounding
lines, etc. (See also \cite{KaPaAC}; see \cite[Theorem~3.1]{BoKMAA}
for alternative combinatorial formulas.)

There are two important special cases, in which a completely explicit
solution in terms of elementary functions can be given. 

The first case occurs for $b_i=0$ and $\lambda_i=1$ for all $i$,
which (up to some multiplicative constant) 
corresponds to the game where each of the players $A$ and $B$
win a round with probability 1/2.
In this case, the polynomials
$p_n(x)$ defined by the three-term recurrence \eqref{A.2} are Chebyshev
polynomials of the second kind,\footnote{The Chebyshev polynomial of
the second kind $U_n(x)$ is defined by $U_n(\cos t)=\sin((n+1)t)/\sin
t$ (see \cite{KoSwAA} for almost exhaustive 
information on these polynomials and,
more generally, on hypergeometric orthogonal polynomials).}
$p_n(x)=U_n(x/2)$. The result which is then obtained from Theorem~\ref{A2}
(clearly, the zeroes of
$U_n(x)$ are $x=\cos(2k\pi/(n+1))$, $k=1,2,\dots,n$, and therefore the
partial fraction expansion of \eqref{eq:gf} is easily determined)
is that the number of lattice paths from $(0,r)$ to $(\ell,s)$ with
only up- and down-steps, which always stay between the $x$-axis and the
line $y=K$, is given by (see also \cite[Ch.~XIV, Eq.~(5.7)]{FellAA})
\begin{equation} \label{sincos1}
\frac {2} {K+2}\sum _{k=1} ^{K+1}
\left(2\cos \frac {\pi k} {K+2}\right)^\ell\cdot
\sin\frac {\pi k(r+1)} {K+2}\cdot \sin\frac
{\pi k(s+1)} {K+2},
\end{equation}
a formula which goes back to Lagrange.
(An alternative expression is given in \eqref{eq:ref2} with the 
replacements $s\to -r$, $t\to K-r$, $n\to \frac {1} {2}(\ell-s+r)$,
$m\to \frac {1} {2}(\ell+s-r)$. It shows
more clearly the integrality of the number. On the other hand, the advantage
of the expression \eqref{sincos1} is that it immediately allows to extract
the asymptotic behaviour as the length $\ell$ of the paths tends to $\infty$.)

The second case occurs for $b_i=1$ and $\lambda_i=1$ for all $i$,
which (up to some multiplicative constant) 
corresponds to the game where each of the three 
possibilities (player $A$ wins,
player $B$ wins, a tie occurs) has equal probability 1/3. 
In this case, the polynomials
$p_n(x)$ defined by the three-term recurrence \eqref{A.2} are again Chebyshev
polynomials of the second kind,
$p_n(x)=U_n((x-1)/2)$. The result which is then obtained from Theorem~\ref{A2}
is that the number of three-step lattice paths from $(0,r)$ to $(\ell,s)$,
which always stay between the $x$-axis and the
line $y=K$, is given by
\begin{equation} \label{sincos2}
\frac {2} {K+2}\sum _{k=1} ^{K+1}
\left(2\cos \frac {\pi k} {K+2}+1\right)^\ell\cdot
\sin\frac {\pi k(r+1)} {K+2}\cdot \sin\frac
{\pi k(s+1)} {K+2}. 
\end{equation}


\medskip
We now turn to the second statistical motivation to study lattice
paths: {\it rank order statistics} for {\it non-parametric testing}.
There, we are given two sets of independent and identically
distributed random variables
$\mathcal X=\{X_1,X_2,\break\ldots,X_m\}$ of size $m$ and 
$\mathcal Y=\{Y_1,Y_2,\ldots,Y_n\}$ of size $n$. 
These are then put together and ordered into
$\mathcal Z=(Z_1,Z_2,\ldots,Z_{m+n})$ according to size. 
To such an ordered sample one associates a lattice path in
$\mathbb Z^2$ starting at the origin, in which the $i$-th step
is a unit vertical step $(0,1)$ if $Z_i$ belongs to $\mathcal X$,
while it is a unit horizontal step $(1,0)$ if $Z_i$ belongs to $\mathcal Y$.
Thus, if $m=n=5$, an example is $\mathcal Z=
(X_1,Y_1,Y_2,Y_3,X_2,X_3,Y_4,X_4,X_5,$ $Y_5)$, which would be
represented as shown in Figure~\ref{fig2}. (The diagonal lines should
be ignored at the moment.) From now on, unless otherwise stated, the
term ``path" will always mean a lattice path in $\mathbb Z^2$ with
unit horizontal and vertical steps in the positive direction.

\begin{figure}[h]
$$\Koordinatenachsen(7,7)(-2,-1)
\Gitter(7,7)(-2,-1)
\Pfad(0,0),2111221221\endPfad
\DickPunkt(0,0)
\DickPunkt(5,5)
\Label\ro{P_3}(1,1)
\Label\lo{y=x+2\kern-6pt}(3,6)
\Label\ru{\kern-6pt y=x-2}(7,4)
\Diagonale(-2,0)8
\Diagonale(0,-2)7
\hskip2cm
$$
\caption{}
\label{fig2}
\end{figure}

To test whether the underlying distribution functions for $\mathcal X$
and $\mathcal Y$ are equal or not, one introduces several statistics,
all of which translate into lattice path statistics. 
For the purpose of testing, the distributions of these statistics are
needed under the {\it null hypothesis} of equal distribution functions.
In light of the preceding remark, this involves counting of certain paths.

The {\it one-sided Kolmogorov-Smirnov statistic}
$D_{m,n}^+$ is defined by
$$D^+_{m,n}= \max_i\Big\{\frac {a_i}m-\frac {b_i}n\Big\},$$
where $a_i$ is the number of occurrences of $X_j$'s in the initial segment 
$Z_1,Z_2,\ldots,\break Z_i$ of $\mathcal Z$,
while $b_i$ is the number of occurrences of $Y_j$'s in this initial
segment. The {\it two-sided Kolmogorov-Smirnov statistic}
$D_{m,n}$ is defined by
$$D_{m,n}=\max_i\Big\{\Big\vert\frac {a_i}m-\frac {b_i}n\Big\vert\Big\}.$$
Thus we have $D^+_{5,5}=1/5$ and $D_{5,5}=2/5$
in our sample represented in Figure~\ref{fig2}.
The {\it run
statistic} counts the number of maximal consecutive subsequences in
$\mathcal Z$ the members of which belong to just one of the sets $\mathcal X$
or $\mathcal Y$. The number of runs
in our example sample is 6. Other statistics that are considered are 
the {\it Galton statistic} (in the lattice path picture: the number
of steps on the ``positive" side of the main diagonal $y=x$), the {\it
median statistic}, and the {\it rank sum statistic}, to mention a few,
see \cite[Ch.~4]{MohaAE}.

In the lattice path picture, the one-sided Kolmogorov-Smirnov statistic is
basically the maximal deviation from the main diagonal in direction
$(-1,1)$. The two-sided Kolmogorov-Smirnov statistic is
basically the maximal deviation from the main diagonal, in either
direction. So in Figure~\ref{fig2}, paths which stay in the region between the
indicated lines $y=x+2$ and $y=x-2$ correspond to sequences $\mathcal Z$
with two-sided Kolmogorov-Smirnov statistic $D_{n,n}\le 2/5$.
The run statistic obviously translates into
the number of maximal straight pieces (horizontal or vertical) in the
corresponding path. 

Clearly, the number of all (unrestricted) paths from the origin to
$(n,m)$ is the binomial coefficient $\binom {n+m}n$. By the {\it
reflection principle}, which is commonly attributed to D.~Andr\'e
(see e.g.\ \cite[p.~22]{ComtAA}), it
follows that the number of paths from the origin to $(n,m)$ which do
not pass above the line $y=x+t$, where $m\le n+t$, is given 
by\footnote{Roughly, the reflection principle
sets up a bijection between the paths from the origin to $(n,m)$
which {\it do pass above} the line $y=x+t$ and {\it all\/} paths from
$(-t-1,t+1)$ to $(n,m)$, by reflecting the path portion between the
origin and the last touching point on $y=x+t+1$ in this latter
line. Thus, the result of the enumeration problem is the number of
{\it all\/} paths from $(0,0)$ to $(n,m)$, which is given by the
binomial coefficient $\binom {n+m}n$, minus the number of {\it all\/}
paths from $(-t-1,t+1)$ to $(n,m)$, which is given by the binomial
coefficient $\binom {n+m}{n+t+1}$, whence the formula \eqref{eq:ref1}.}
\begin{equation} \label{eq:ref1}
\binom {n+m} {n} -
\binom {n+m}{n+t+1}. 
\end{equation}
In the case that $n=m$, this translates easily into an expression for
the probability of encountering $D_{n,n}^+\le t/n$ under the null
hypothesis. If $n\ne m$, we need to count paths that do not pass 
above the line
$my=nx+t$, for which there is no compact formula known (and is
unlikely to exist). Sato \cite{SatoAA,SatoAB} has dealt with this
problem (and its higher dimensional generalization) extensively. 
However, the most
conceptual way to approach this problem seems to be through the
so-called {\it kernel method} (see \cite{BaFlAA}), which, in
combination with the saddle point method, allows one also to obtain
strong asymptotic results.
There is one special instance, however, which has a ``nice"
formula. The number of all lattice paths from the origin to
$(n,m)$ which never pass above $x=\mu y$, where $\mu$ is a positive
integer, is given by
\begin{equation} \label{e1.8}
\frac {n-\mu m+1} {n+m+1}\binom
{n+m+1} {m}  .
\end{equation}
The most elegant way to prove this formula is by means of the {\it
cycle lemma} of Dvoretzky and Motzkin \cite{DvMoAA} (see
\cite[p.~9]{MohaAE}, where the cycle lemma occurs under the name of
``penetrating analysis"). 

Expression \eqref{eq:ref1} with $t=1$ and \eqref{e1.8} provide solutions
to the so-called {\it classical ballot problem}. Its generalization to the
urn problem due to Tak\'acs (see \cite[p.~2--4]{TakaAJ}), which has
applications in queueing theory, has its solution through the form
of a cycle lemma. Its most general form is
due to Spitzer \cite{SpitAA}, and is known as ``Spitzer's lemma," which
has also many applications in random walk theory.

Iteration of the reflection principle shows that the 
number of paths from the origin to $(n,m)$ which stay
between the lines $y=x+t$ and $y=x+s$ (being allowed to touch them), 
where $t\ge 0\ge s$ and $n+t\ge m\ge n+s$, is given by the finite (!) sum
\begin{equation} \label{eq:ref2}
\sum _{k\in\mathbb Z} ^{}\left(\binom
{n+m} {n-k(t-s+2)}-\binom {n+m}{n-k(t-s+2)+t+1}\right).
\end{equation}
(See e.g.\ \cite[p.~6]{MohaAE}.
Clearly, an alternative expression is provided by \eqref{sincos1},
under the substitutions $s\to m-n-s$, $r\to -s$, $K\to t-s$, $\ell\to
n+m$. While the above expression shows clearly the
integrality of the numbers, the expression \eqref{sincos1} allows to
extract the asymptotic behaviour as the length of the paths tends to
$\infty$.)
If $n=m$ and $t=s$, this translates in an obvious assertion about
the probability of encountering $D_{n,n}\le t/n$ under the assumption
that the distribution functions of $\mathcal X$ and $\mathcal Y$ are
the same. Again, if $n\ne m$, there is no compact formula. 
Sato \cite{SatoAA,SatoAB} has given formulas
in terms of generating functions, but it seems difficult to work with
them, except in a few special cases.

\medskip
The enumeration of lattice paths restricted to regions bounded by hyperplanes
has also been considered for other regions, such as quadrants, octants, 
and rectangles, as well as in higher dimensions. The papers
\cite{BianAD,GeZeAA} (see also \cite{GrabAD}) contain a general result
on the number of lattice 
paths in a chamber (alcove) of an (affine) reflection group that shows
how far one can go when one uses the reflection principle. In particular,
this result covers \eqref{eq:ref1} and \eqref{eq:ref2}, the
enumeration of lattice paths in quadrants, octants, rectangles, and many other
results that have appeared (before and after) in the literature.
We present a particularly elegant (and frequently occurring) special
case. (In the language of \cite{BianAD,GeZeAA}, it corresponds to the
reflection group of ``type $A_{n-1}$". See \cite{HumpAC} for
terminology and information on reflection groups.)

\begin{theorem} \label{thm:2}
Let $A=(a_1,a_2,\dots,a_d)$ and $E=(e_1,e_2,\dots,e_d)$ be points in
$\mathbb Z^d$ with $a_1\ge a_2\ge\dots\ge a_d$ and $e_1\ge e_2\ge\dots\ge
e_d$. The number of all paths from $A$ to $E$ in the integer lattice
$\mathbb Z^d$, which consist of
positive unit steps and which stay in the region
$x_1\ge x_2\ge\dots\ge x_d$, equals
\begin{equation} \label{e7.2} 
\Big(\sum _{i=1}
^{d}(e_i-a_i)\Big)! 
\det_{1\le i,j\le d}\left(\frac {1} {(e_i-a_j-i+j)!}\right).
\end{equation}
\end{theorem}

The counting problem of the theorem is equivalent to numerous other counting
problems. It has been originally formulated as an $n$-candidate 
ballot problem (see
e.g.\ \cite{BaMaAA}), but it is as well equivalent to counting the
number of standard Young tableaux of a given shape (see e.g.\
\cite{BaMaAA,ZeilAD}). In the case that all $a_j$'s are equal, the
determinant does in fact evaluate into a closed form product.
In Young tableaux theory a particular way to write the result is known as the 
{\it hook-length formula} (see e.g.\ \cite[Sec.~3.10]{SagaAQ} or
\cite[Cor.~7.21.6]{StanBI}).

\medskip
We return to lattice paths in the plane, mentioning 
some more closely related results. The first is a
result of Mohanty \cite{MohaAB}, which
expresses the number of all lattice paths from the origin to $(n,m)$
which touch the line $y=x+t$ {\it exactly} $r$ times, never
crossing it, as the difference
\begin{equation} \label{eq:touch}
\binom {n+m-r}{n+t-1}-\binom {n+m-r}{n+t},\quad \quad r\ge1. 
\end{equation}

Not forbidding that the paths cross the bounding line, we arrive at
the problem of counting the lattice paths from the origin to $(n,m)$, which
cross the main diagonal $y=x$ exactly $r$ times, the answer being
\cite{KanwAA}
\begin{equation} \label{} 
\begin{cases} %\displaystyle
\frac {m-n+2r+1} {m+n+1}\binom {m+n+1}{n-r}&\text{if }m>n,\\
%\displaystyle
\frac {2r+2} {n}\binom {2n}{n-r-1}&\text{if }m=n.
\end{cases}
\end{equation}
Next, we give the number of lattice paths from the
origin to $(n,n)$ which have $2r$ steps on one side of the line $y=x$, as
\begin{equation} \label{} 
\binom {2r}r\binom {2n-2r}{n-r},
\end{equation}
a result due to Sparre Andersen \cite{AndSAC}.
We refer the reader to \cite[Ch.~3]{MohaAE} for further results in
this direction.

\medskip
Enumerating lattice paths with a fixed number of maximal straight
pieces (which correspond to runs), 
is intimately connected to another basic enumeration problem
concerning lattice paths: the enumeration of lattice paths having 
a fixed number
of {\it turns}. An effective way to attack the latter problem is by
means of {\it two-rowed arrays}, see the survey article \cite{KratBL},
where in particular analogues of the reflection principle for
two-rowed arrays are developed. These imply formulas for the number
of lattice paths with fixed starting and end points and a fixed 
number of {\it north-east} (respectively {\it east-north}) {\it
turns}\footnote{A north-east turn in a lattice path is a point where
the direction changes from ``north" to ``east." An east-north turn is
defined analogously.}, for unrestricted paths, as well as for paths
bounded by lines. In particular, analogues of \eqref{eq:ref1}--\eqref{eq:ref2} 
are known when the number of north-east (respectively
east-north) turns is fixed.\footnote{These formulas imply directly formulas
for the probability of the {\it correlated random walk} 
(see \cite[Sec.~5.2]{MohaAE}), which is a
random walk with horizontal and vertical steps in which the
probability of a step is not independent of the previous step made,
subject to various restrictions.}

These formulas imply for example (see again \cite[Sec.~3.5]{KratBL}) that the
number of lattice paths from the origin to $(n,n)$ which never pass
above the line $y=x+t$ and have exactly $2r$ maximal straight pieces
is given by
\begin{equation} \label{eq:D+R}
2{\binom{n-1}{r-1}}^2-
{\binom {n+t-1}{r-2}}{\binom{n-t-1}{r}} -
{ \binom{n+t-1}{r-1}}{\binom{n-t-1}{r-1}},
\end{equation}
with a similar result for the case of $2r+1$ maximal straight 
pieces.\footnote{If $t=0$, the numbers in \eqref{eq:D+R} become
$\frac {1} {n}\binom nr\binom n{r-1}$, and they are known as the 
{\it Narayana numbers}.}
Furthermore, they imply that the
number of lattice paths from the origin to $(n,n)$ which never pass
above the line $y=x+t$ and never below the line $y=x-t$ and have 
exactly $2r$ maximal straight pieces is given by
\begin{multline} \label{eq:DR}
\sum _{k=-\infty}^{\infty}
\Bigg\{2{\binom{n-2kt-1}{r+k-1}}{\binom{n+2kt-1}{r-k-1}}\\-
{\binom {n-2kt+t-1}{r+k-2}}{\binom{n+2kt-t-1}{r-k}}\\
 \qquad -
{ \binom{n-2kt+t-1}{r+k-1}}{\binom{n+2kt-t-1}{r-k-1}}\Bigg\},
\end{multline}
with a similar result for the case of $2r+1$ maximal straight pieces. 
Both, Eqs.~\eqref{eq:D+R} and \eqref{eq:DR}, are results originally
obtained by Vellore \cite{VellAA}. They translate into obvious
assertions about the joint probability of encountering a fixed number
of runs {\it and\/} $D^+_{n,n}\le t/n$, respectively $D_{n,n}\le t/n$,
under the assumption
that the distribution functions of $\mathcal X$ and $\mathcal Y$ are
the same.

\medskip
The most general boundary for lattice paths that one can
imagine is the restriction that it stays between two given (fixed)
paths. Let us assume that the horizontal steps of the upper (fixed) path
are at heights $a_1\le a_2\le \dots\le a_n$, whereas the 
horizontal steps of the lower (fixed) path are at heights 
$b_1\le b_2\le \dots\le b_n$, $a_i\ge b_i$, $i=1,2,\dots,n$.
Then the number of all
paths from $(0,b_1)$ to $(n,a_n)$ satisfying the property that 
for all $i=1,2,\dots,n$ the height of the $i$-th horizontal step is
between $b_i$ and $a_i$ is given by the determinant
\begin{equation} \label{e1.30}
\det_{1\le i,j\le n}\left(\binom {a_i-b_j+1}{j-i+1}\right). 
\end{equation}
In the statistical literature, this formula is often known as 
``Steck's formula" \cite{StecAC}, but it is actually a special case of a
much more general theorem due to Kreweras \cite{KrewAB}.
A generalization of \eqref{e1.30} to higher dimensional paths was
given by Handa and Mohanty \cite{HaMoAB}. For a continuous analogue
of \eqref{e1.30}, and its applications see \cite[Sec.~4.5]{MohaAE}.

\medskip
Several of the formulas presented have also applications in queueing theory
(see \cite{TakaAJ} and \cite[Sec.~5.3]{MohaAE} for more extensive
treatments of this aspect of lattice paths). Consider an $M/M/1$ queueing
system in which the customers arrive individually 
at a counter in accordance with a
Poisson process of density $\lambda_1$ and are served individually by a
single server. The service times are i.i.d.\ random variables with
distribution function 
$$F(x)=\begin{cases} 1-e^{-\lambda_0x}&\text{if }x\ge0,\\
0&\text{otherwise,}\end{cases}$$
and are independent of the arrival times. 
In the combined process, every event independent of
others is either an arrival with
probability $p=\lambda_1/(\lambda_0+\lambda_1)$ or a departure
with probability $q=1-p$. 
If we represent a departure 
by a vertical unit and an arrival by a horizontal unit, then a busy
period, initiated by $j$ customers and consisting of 
$n+j$ services (departures) corresponds to the
set of lattice paths from $(0,0)$ to $(n,n+j)$ that do not touch the
line $y=x+j$ except at the end. Thus, the probability for a busy
period initiated by $j$ customers in which $n+j$ customers are served,
is $p^nq^{n+j}$ times the number of these lattice
paths. The latter number results from \eqref{eq:ref1} by setting
$m=n+j-1$ and $t=j-1$.
Using some probabilistic reasoning, it is then possible to derive an
explicit integral formula for the probability that such a busy period has
length $\le t$. More refined queueing problems (allowing for
arrivals/departures in batches, for bounds on the number of waiting
customers, etc.) can also be treated by this lattice path method.
We refer the reader again to \cite{TakaAJ} and \cite[Sec.~5.3]{MohaAE}.

\medskip
We remark that another area of application of lattice path enumeration
has been in Discrete Distributions, see \cite[Ch.~5]{MohaAE}.

\medskip
Another vast topic is the enumeration of {\it several\/} paths 
which do not have any common points.\footnote{In the combinatorial
literature, such families of paths are, slightly confusingly, called
``{\it non-intersecting}" paths. In this text we use the term ``{\it
non-touching}" paths.} This problem has been introduced
and was first
studied by Karlin and McGregor \cite{KaMGAB,KaMGAC} (in the continuous case). 
If the starting and end points of the paths are fixed, the number of
such families of non-touching paths is given (under mild restrictions on the
starting and end points) by a determinant, where the
$(i,j)$-entry of the determinant counts the number of paths from the
$j$-th starting to the $i$-th end point. The most
general form of this theorem has been obtained by 
Lindstr\"om \cite{LindAA} and has been rediscovered by Gessel and
Viennot \cite{GeViAA}.\footnote{Other occurrences of non-touching
paths are in statistical physics under the name of {\it ``vicious
walkers"} as introduced by Fisher \cite{FishAA}, and in combinatorial
chemistry in the enumeration of perfect matchings of hexagonal graphs,
see \cite{GrJSAA,JoSaAB}.} It covers numerous determinant formulas in the
literature, including \eqref{e1.30} and its higher dimensional
generalization due to Handa and Mohanty (as shown by Sulanke
\cite{SulaAC}). The most widely used case of the theorem is the following.

\begin{theorem} \label{thm:3}
Let $G$ be an acyclic directed graph.
Let $(A_1,A_2,\dots,A_n)$ and $(E_1,E_2,\dots,E_n)$ be sequences
of vertices in $G$ such 
that for $i<j$ and $k<l$ any path from $A_i$ to $E_l$ and any path
from $A_j$ to $E_k$ have at least one point in common.
Then the number of all
families $(P_1,P_2,\dots,P_n)$ of non-touching
paths, where $P_i$ is a path running from
$A_i$ to $E_i$, $i=1,2,\dots,n$, is given by 
\begin{equation} \label{e2.4a}
\det_{1\le i,j\le n}\big(P(A_j\to E_i)\big),
\end{equation}
where $P(A_j\to E_i)$ is the number of paths from $A_j$ to $E_i$.
\end{theorem}

The most general theorem includes weighted counting as well, and it
drops the condition involving $i,j,k,l$. The standard application
of the above ``weak" form of the theorem is
to the enumeration of families of non-touching paths in the integer
lattice.

\begin{theorem} \label{thm:4}
Let $(A_1,A_2,\dots,A_n)$ and $(E_1,E_2,\dots,E_n)$ be sequences
of lattice points in $\mathbb Z^2$ such 
that for $i<j$ and $k<l$ any path from $A_i$ to $E_l$ and any path
from $A_j$ to $E_k$ have at least one point in common.
Then the number of all
families $(P_1,P_2,\dots,P_n)$ of non-touching
paths, where $P_i$ consists of horizontal and vertical steps in the
positive direction and runs from
$A_i$ to $E_i$, $i=1,2,\dots,n$, is given by 
\begin{equation} \label{e2.4}
\det_{1\le i,j\le n}\big(P(A_j\to E_i)\big),
\end{equation}
where $P(A\to E)$ is the binomial coefficient $\binom
{e_1+e_2-a_1-a_2}{e_1-a_1}$, given that $A=(a_1,a_2)$ and $E=(e_1,e_2)$.
\end{theorem}


If the starting points or/and the end points
are not fixed, then the corresponding number is given by a Pfaffian, a
result obtained by Okada \cite{OkadAA} and Stembridge \cite{StemAE}.
Refinements when the number of turns is fixed have been obtained by
Krattenthaler, see \cite{KratBL}.

\medskip
For further reading, and many more references, we refer the reader to
the textbooks \cite{MohaAE} and \cite{NaraAB}.

\footnotesize

\begin{thebibliography}{10}

\bibitem{BaFlAA} C.    Banderier and P. Flajolet,
{\it Basic analytic combinatorics of directed lattice paths},
Theoret.\ Computer Science {\bf 281} (2002), 37--80.

\bibitem{BaMaAA} D. E. Barton and C. L. Mallows, {\it Some
aspects of the random sequences}, Amer.\ Math.\ Statist.\
{\bf 36} (1965), 236--260.

\bibitem{BianAD} P.    Biane,
{\it Minuscule weights and random
walks on lattices}, in: Quantum probability \& related topics,
L.~Accardi, ed., World Sci.\ Publ., River Edge, NJ, 1992, pp.~51--65.

\bibitem{BoKMAA}  W. B\"ohm, A. Krinik and S. G. Mohanty,
{\it The combinatorics of birth-death processes and applications to queues},
Queueing Systems {\bf 26} (1997), 255--267.

\bibitem{ComtAA}
L.~Comtet, {\em Advanced {C}ombinatorics}, D.~Reidel, Dordrecht, Holland, 1974.

\bibitem{DvMoAA} A.    Dvoretzky and T. Motzkin,
{\it A problem of arrangements}, Duke Math.\ J. {\bf 14} (1947), 305--313.

\bibitem{FellAA} W.    Feller, {\it An introduction to
probability theory and its applications}, vol.~1, 2nd ed., Wiley,
New York,  1957.

\bibitem{FishAA}
M. E. Fisher, {\it Walks, walls, wetting, 
and melting}, J. Statist.\ Phys.\ {\bf 34} (1984), 667--729.

\bibitem{FlajAA} P.    Flajolet, {\it Combinatorial
aspects of continued fractions}, Discrete Math.\ {\bf 32} (1980),
125--161.

\bibitem{GeViAA}
I. M. Gessel and X. Viennot,
{\em Binomial determinants, paths, and hook length formulae},
Adv.\ in Math.\ {\bf 58} (1985), 300--321.

\bibitem{GeZeAA} I. M. Gessel and D. Zeilberger,
{\it Random walk in a Weyl chamber}, Proc.\ Amer.\ Math.\ Soc.\
{\bf 115} (1992), 27--31.

\bibitem{GrabAD} D. J. Grabiner,
{\em Random walk in an alcove of an affine Weyl group, and non-colliding
random walks on an interval}, J. Combin.\ Theory Ser.~A {\bf 97} 
(2002), 285--306.

\bibitem{GrJSAA}
H.-D. O. F. Gronau, W. Just, W. Schade, 
P. Scheffler and J. Wojciechowski,
{\it Path systems in acyclic directed graphs},
Zastos.\ Mat.\ {\bf 19} (1988), 399--411.

\bibitem{HaMoAB} B. R. Handa and S. G. Mohanty,
{\it Enumeration of higher-dimensional paths under restrictions},
Discrete Math.\ {\bf 26} (1979), 119--128.

\bibitem{HumpAC}
J. E. Humphreys, {\it Reflection groups
and Coxeter groups}, Cambridge University Press,
Cambridge, 1990.

\bibitem{JoSaAB}
P. John and H. Sachs, {\it Wegesysteme und
Linearfaktoren in hexagonalen und quadratischen Systemen},
Graphs in research and teaching (Kiel, 1985), Franzbecker,
Bad Salzdetfurth, 1985, pp.~85--101.

\bibitem{KanwAA}  Kanwar Sen, {\it On some
combinatorial relations concerning the symmetric random walk},
Publ.\ Math.\ Inst.\ Hungar.\ Acad.\ Sci.\ {\bf 9} (1965), 335--357.

\bibitem{KaMGAB} S.    Karlin and J. L. McGregor,
{\it Coincidence properties of birth-and-death processes},
Pacific J. Math.\ {\bf 9} (1959), 1109--1140.

\bibitem{KaMGAC} S.    Karlin and J. L. McGregor,
{\it Coincidence probabilities}, Pacific J. Math.\ {\bf 9} (1959),
1141--1164.

\bibitem{KaPaAC} 
W.    Katzenbeisser and W. Panny,
{\it Simple random walk statistics I: discrete time results},
J. Appl.\ Probab.\ {\bf 33} (1996), 311--330.

\bibitem{KoSwAA}
R.    Koekoek and R. F. Swarttouw,
{\em The Askey--scheme of hypergeometric orthogonal polynomials and 
its $q$-analogue}, TU Delft, The Netherlands, 1998; on the WWW:
\newline 
{\tt ftp://ftp.twi.tudelft.nl/TWI/publications/tech-reports/1998/DUT-TWI-98-17.ps.gz}.

\bibitem{KratBL} C.    Krattenthaler,
{\it The enumeration
of lattice paths with respect to their number of turns},
in: Advances
in Combinatorial Methods and Applications to Probability and
Statistics, N.~Balakrishnan, ed., Birkh\"auser, Boston,
29--58.

\bibitem{KratBP} C.    Krattenthaler,
{\it Permutations
with restricted patterns and Dyck paths}, Adv.\ Appl.\ Math.\
{\bf 27} (2001), 510--530.

\bibitem{KrewAB} G.    Kreweras,
{\it Sur une classe de
probl\`emes de d\'enombrement li\'es au treillis des partitions des
entiers}, Cahiers du B.U.R.O. Univ.\ de Rech.\ Op\'er.\ {\bf 6} (1965),
5--105.

\bibitem{LindAA} B.    Lindstr\"om,
{\it On the vector representations of induced matroids},
Bull.\ London Math.\ Soc.\ {\bf 5} (1973), 85--90.

\bibitem{MohaAB} S. G. Mohanty,
{\it On some generalization 
of a restricted random walk}, Stud.\ Sci.\ Math.\ 
Hungarica {\bf 3} (1968), 225--241.

\bibitem{MohaAE} S. G. Mohanty,
{\it Lattice Path Counting and Applications},  Academic
Press, New York, 1979.

\bibitem{MohaAZ} S. G. Mohanty,
{\it On the transient behaviour of a finite discrete time birth-death 
process}, Assam Statist.\ Rev.\ {\bf 5} (1991), 1--7.

\bibitem{NaraAB} T. V. Narayana, {\it Lattice path
combinatorics with statistical applications}, Math.\ Expositions,
no.~23, Univ.\ of Toronto Press, Toronto, 1979.

\bibitem{OkadAA}
S.    Okada, {\em On the generating functions for certain classes of 
plane partitions}, J. Combin.\ Theory A {\bf 51} (1989), 1--23.

\bibitem{SagaAQ}
B. E. Sagan, {\it The symmetric
group}, 2nd edition, Springer--Verlag, New
York, 2001.

\bibitem{SatoAA} M.    Sato,
{\it Generating functions for
the number of lattice paths between two parallel lines with a rational
incline}, Math.\ Japonica {\bf 34} (1989), 123--137.

\bibitem{SatoAB} M.    Sato,
{\it Generating functions for
the number of lattice paths restricted by two parallel
hyperplanes}, J. Statist.\ Plann.\ Inference {\bf 34} (1993),
251--258.

\bibitem{AndSAC} E. Sparre Andersen,
{\it On the number of
positive sums of random variables}, Scand.\ Actuarietidskr.\ {\bf
32} (1949), 27--36.

\bibitem{SpitAA} F.    Spitzer,
{\it A combinatorial lemma
and its application to probability theory},
Trans.\ Amer.\ Math.\ Soc.\ {\bf 82} (1956), 323--339.

\bibitem{StanBI} 
R. P. Stanley, {\it Enumerative
Combinatorics}, Vol.~2, Cambridge University Press, Cambridge, 1999.

\bibitem{StecAC} G. P. Steck,
{\it The Smirnov two-sample
tests as rank tests}, Ann.\ Math.\ Statist.\ {\bf 40} (1969),
1449--1466.

\bibitem{StemAE}
J.~R.~Stembridge, {\em Nonintersecting paths, pfaffians and plane partitions\/}, 
Adv.\ in Math.\ {\bf 83} (1990),
96--131.

\bibitem{SulaAC} R. A. Sulanke,
{\it A determinant for
$q$-counting lattice paths}, Discrete Math.\ {\bf 81} (1990),
91--96.

\bibitem{SzegOP}
G.~Szeg\H o,
{\em Orthogonal polynomials\/},
American Mathematical Society Colloquium Publications Vol.~XXIII, 
New York, 1959.

\bibitem{TakaAJ}
L.    Tak\'acs, {\it Combinatorial methods 
in the theory of stochastic processes}, Wiley, New York, 1967.

\bibitem{VellAA} S.    Vellore,
{\it Joint distributions of Kolmogorov--Smirnov statistics and runs},
Studia Scientiarum Math.\ Hungarica {\bf 7} (1972), 155--165.

\bibitem{VienAE}
X.~Viennot,
{\em  Une th\'eorie combinatoire des polyn\^omes orthogonaux g\'en\'eraux},
UQAM, Montr\'eal, Qu\'ebec, 1983.

\bibitem{WallCF}
H.~S.~Wall,
{\em Analytic Theory of Continued Fractions},
Van Nostrand, New York, 1948.

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

\end{thebibliography}

\end{document}
