Namespaces
Variants
Actions

Difference between revisions of "Bernoulli excursion"

From Encyclopedia of Mathematics
Jump to: navigation, search
(better, link to Binary tree)
(TeX done)
 
Line 1: Line 1:
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{}
+
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} \ .
 +
$$
  
<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: $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$.
  
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]] $\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 tree|binary]] [[rooted plane tree]]s 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 [[#References|[a1]]], [[#References|[a2]]].
  
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" /> complete [[Binary tree|binary]] [[rooted plane tree]]s 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:
+
====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>
  
<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>
+
{{TEX|done}}
 
 
<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>
 

Latest revision as of 17:54, 26 December 2017

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

[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
How to Cite This Entry:
Bernoulli excursion. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Bernoulli_excursion&oldid=42606
This article was adapted from an original article by L. Takács (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article