Difference between revisions of "Bernoulli excursion"
(Importing text file) |
m (link) |
||
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|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: |
<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 20:50, 21 November 2014
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 (ordered) 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 |
Bernoulli excursion. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Bernoulli_excursion&oldid=34734