Bernoulli excursion

Consider a set of sequences each consisting of $2n$ elements such that $n$ elements are equal to $+1$, $n$ elements are equal to $-1$, and the sum of the first $i$ elements is greater than or equal to zero for every $i=1,\ldots,2n$. The number of such sequences is given by the $n$-th Catalan number $$ C_n = \frac{1}{n+1} \binom{2n}{n} \ . $$

The first few Catalan numbers are: $C_0=1$, $C_1 = 1$, $C_2 = 2$, $C_3 = 5$, $C_4 = 14$, $C_5 = 42$. A sequence is randomly chosen from the $C_n$ sequences, assuming that all possible sequences are equally probable. Denote by $\eta_i$ ($i=1,\ldots,2n$) the sum of the first $i$ elements in this chosen sequence and set $\eta_0 = 0$. Then $\eta_i \ge 0$ for $0 \le i \le 2n$ and $\eta_0 = \eta_{2n} = 0$. The sequence $(\eta_0,\ldots,\eta_{2n})$ 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 $x$-axis. It starts at $x=0$ and takes $2n$ steps. At the $i$-th step the particle moves either a unit distance to the right or a unit distance to the left according to whether the $i$-th element in the random sequence is $+1$ or $-1$. At the end of the $i$-th step the position of the particle is $x = \eta_i$ for $i=1,\ldots,2n$.

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 $\mathrm{M}{|}\mathrm{M}{|}1$ the distribution of the maximal queue size during a busy period requires the determination of the distribution of the random variable $\max(\eta_0,\ldots,\eta_{2n})$. Another example is concerned with random trees. There are $C_n$ complete binary rooted plane trees with $N+1$ unlabelled vertices. Choose a tree at random, assuming that all the $C_n$ possible trees are equally probable. Then the height of the random tree has the same distribution as $\max(\eta_0,\ldots,\eta_{2n})$ in the Bernoulli excursion. Explicitly: $$ C_n \cdot \mathbf{P}\{\max(\eta_0,\ldots,\eta_{2n}) \le k\} = \frac{2^{2n+1}}{k+1} \, \sum_{r=1}^{k+1}\left({\cos\frac{r\pi}{k+1}}\right)^{2n}\,\left({\sin\frac{r\pi}{k+1}}\right)^2 $$ for $k \ge 1$ and $n \ge 1$. For other examples see [a1], [a2].

References[edit]