Namespaces
Variants
Actions

Difference between revisions of "Bernoulli excursion"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (link)
m (links)
Line 5: Line 5:
 
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" />.
 
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|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 (ordered) trees 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:
+
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/b11032042.png" /></td> </tr></table>

Revision as of 17:07, 26 December 2017

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