Bernoulli excursion

Consider a set of sequences each consisting of elements such that elements are equal to , elements are equal to , and the sum of the first elements is greater than or equal to zero for every . The number of such sequences is given by the th Catalan number{}

The first few Catalan numbers are: , , , , , . A sequence is randomly chosen from the sequences, assuming that all possible sequences are equally probable. Denote by () the sum of the first elements in this chosen sequence and set . Then for and . The sequence describes a random walk, which is usually called a Bernoulli excursion (cf. also Bernoulli random walk). One can imagine that a particle performs a random walk on the -axis. It starts at and takes steps. At the th step the particle moves either a unit distance to the right or a unit distance to the left according to whether the th element in the random sequence is or . At the end of the th step the position of the particle is for .

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 the distribution of the maximal queue size during a busy period requires the determination of the distribution of the random variable . Another example is concerned with random trees. There are complete binary rooted plane trees with unlabelled vertices. Choose a tree at random, assuming that all the possible trees are equally probable. Then the height of the random tree has the same distribution as in the Bernoulli excursion. Explicitly:

for and . For other examples see [a1], [a2].

References

[a1]	L. Takács, "A Bernoulli excursion and its various applications" Adv. in Probability , 23 (1991) pp. 557–585
[a2]	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