View source for Bernoulli excursion

Consider a set of sequences each consisting of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110320/b1103201.png" /> elements such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110320/b1103202.png" /> elements are equal to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110320/b1103203.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110320/b1103204.png" /> elements are equal to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110320/b1103205.png" />, and the sum of the first <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110320/b1103206.png" /> elements is greater than or equal to zero for every <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110320/b1103207.png" />. The number of such sequences is given by the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110320/b1103208.png" />th Catalan number{}

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110320/b1103209.png" /></td> </tr></table>

The first few Catalan numbers are: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110320/b11032010.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110320/b11032011.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110320/b11032012.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110320/b11032013.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110320/b11032014.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110320/b11032015.png" />. A sequence is randomly chosen from the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110320/b11032016.png" /> sequences, assuming that all possible sequences are equally probable. Denote by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110320/b11032017.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110320/b11032018.png" />) the sum of the first <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110320/b11032019.png" /> elements in this chosen sequence and set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110320/b11032020.png" />. Then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110320/b11032021.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110320/b11032022.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110320/b11032023.png" />. The sequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110320/b11032024.png" /> describes a [[Random walk|random walk]], which is usually called a Bernoulli excursion (cf. also [[Bernoulli random walk|Bernoulli random walk]]). One can imagine that a particle performs a random walk on the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110320/b11032025.png" />-axis. It starts at <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110320/b11032026.png" /> and takes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110320/b11032027.png" /> steps. At the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110320/b11032028.png" />th step the particle moves either a unit distance to the right or a unit distance to the left according to whether the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110320/b11032029.png" />th element in the random sequence is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110320/b11032030.png" /> or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110320/b11032031.png" />. At the end of the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110320/b11032032.png" />th step the position of the particle is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110320/b11032033.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110320/b11032034.png" />.

In [[probability theory]], many problems require the determination of the distributions of various functionals of the Bernoulli excursion. For example, for a [[single-server queue]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110320/b11032036.png" /> the distribution of the maximal queue size during a busy period requires the determination of the distribution of the random variable <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110320/b11032037.png" />. Another example is concerned with random trees. There are <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110320/b11032038.png" /> [[rooted plane tree]]s (ordered) with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110320/b11032039.png" /> unlabelled vertices. Choose a tree at random, assuming that all the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110320/b11032040.png" /> possible trees are equally probable. Then the height of the random tree has the same distribution as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110320/b11032041.png" /> in the Bernoulli excursion. Explicitly:

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110320/b11032042.png" /></td> </tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110320/b11032043.png" /></td> </tr></table>

for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110320/b11032044.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110320/b11032045.png" />. For other examples see [[#References|[a1]]], [[#References|[a2]]].

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  L. Takács,   "A Bernoulli excursion and its various applications"  ''Adv. in Probability'' , '''23'''  (1991)  pp. 557–585</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  L. Takács,   "Queueing methods in the theory of random graphs"  J.H. Dshalalow (ed.) , ''Advances in Queueing Theory, Methods, and Open Problems'' , CRC  (1995)  pp. 45–78</TD></TR></table>