Namespaces
Variants
Actions

Difference between revisions of "Andersen theorem"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (tex encoded by computer)
 
(One intermediate revision by one other user not shown)
Line 1: Line 1:
A result in the theory of fluctuations in random walks (cf. [[Random walk|Random walk]]). Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110590/a1105901.png" /> be independent random variables with the same distribution (cf. [[Random variable|Random variable]]), and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110590/a1105902.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110590/a1105903.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110590/a1105904.png" />. Define
+
<!--
 +
a1105901.png
 +
$#A+1 = 17 n = 0
 +
$#C+1 = 17 : ~/encyclopedia/old_files/data/A110/A.1100590 Andersen theorem
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
  
<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/a/a110/a110590/a1105905.png" /></td> </tr></table>
+
{{TEX|auto}}
 +
{{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/a/a110/a110590/a1105906.png" /></td> </tr></table>
+
A result in the theory of fluctuations in random walks (cf. [[Random walk|Random walk]]). Let  $  ( X _ {n} ) _ {1}  ^  \infty  $
 +
be independent random variables with the same distribution (cf. [[Random variable|Random variable]]), and let  $  S _ {0} = 0 $,
 +
$  S _ {k} = X _ {1} + \dots + X _ {k} $,
 +
$  k \in \mathbf N $.  
 +
Define
  
<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/a/a110/a110590/a1105907.png" /></td> </tr></table>
+
$$
 +
M _ {n} = \max  ( S _ {0} \dots S _ {n} ) ,  m _ {n} = { \mathop{\rm min} } ( S _ {0} \dots S _ {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/a/a110/a110590/a1105908.png" /></td> </tr></table>
+
$$
 +
L _ {n} = { \mathop{\rm min} } \left \{ k : {k = 0 \dots n,  S _ {k} = M _ {n} } \right \} ,
 +
$$
  
Then (equivalence principle) for each <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110590/a1105909.png" /> the pairs <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110590/a11059010.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110590/a11059011.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110590/a11059012.png" /> have the same distribution; in particular, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110590/a11059013.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110590/a11059014.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110590/a11059015.png" /> have the same distribution. As a consequence one has
+
$$
 +
L _ {n}  ^  \prime  = \max  \left \{ k : {k = 0 \dots n, S _ {k} = m _ {n} } \right \} ,
 +
$$
  
<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/a/a110/a110590/a11059016.png" /></td> </tr></table>
+
$$
 +
N _ {n} = \sum _ {k = 1 } ^ { n }  1 \{ S _ {k} > 0 \} .
 +
$$
  
<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/a/a110/a110590/a11059017.png" /></td> </tr></table>
+
Then (equivalence principle) for each  $  n \in \mathbf N $
 +
the pairs  $  ( N _ {n} ,S _ {n} ) $,
 +
$  ( L _ {n} ,S _ {n} ) $
 +
and  $  ( n - L _ {n}  ^  \prime  ,S _ {n} ) $
 +
have the same distribution; in particular,  $  N _ {n} $,
 +
$  L _ {n} $
 +
and  $  n - L _ {n}  ^  \prime  $
 +
have the same distribution. As a consequence one has
 +
 
 +
$$
 +
{\mathsf P} \{ N _ {n} = k \} = {\mathsf P} \{ N _ {k} = k \} {\mathsf P} \{ N _ {n - k }  = 0 \} ,
 +
$$
 +
 
 +
$$
 +
k = 1 \dots n .
 +
$$
  
 
These results were first proved by E. Sparre Andersen [[#References|[a1]]], [[#References|[a2]]], [[#References|[a3]]]. They connect the [[Arcsine law|arcsine law]] for random walks to the arcsine law in [[Renewal theory|renewal theory]].
 
These results were first proved by E. Sparre Andersen [[#References|[a1]]], [[#References|[a2]]], [[#References|[a3]]]. They connect the [[Arcsine law|arcsine law]] for random walks to the arcsine law in [[Renewal theory|renewal theory]].
Line 20: Line 55:
  
 
====References====
 
====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top"> E. Sparre Andersen,   "On the number of positive sums of random variables" ''Skand. Aktuarietikskr.'' , '''32''' (1949) pp. 27–36</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top"> E. Sparre Andersen,   "On sums of symmetrically dependent random variables" ''Skand. Aktuarietikskr.'' , '''36''' (1953) pp. 123–138</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top"> E. Sparre Andersen,   "On the fluctuations of sums of random variables" ''Math. Scand.'' , '''1''' (1953) pp. 263–285 (Also: 2 (1954), 195–223)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top"> N.H. Bingham,   C.M. Goldie,   J.L. Teugels,   "Regular variation" , ''Encycl. Math. Appl.'' , '''27''' , Cambridge Univ. Press (1989) (Edition: Second)</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top"> N.G. de Bruijn,   "Some algorithms for ordering a sequence of objects, with application to E. Sparre Andersen's principle of equivalence in mathematical statistics" ''Indagationes Mathematicae'' , '''34''' : 1 (1972) pp. 1–10</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top"> W. Feller,   "An introduction to probability theory and its applications" , '''2''' , Springer (1976) (Edition: Second)</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top"> A.W. Joseph,   "An elementary proof of the principle of equivalence" ''J. London Math. Soc. (2)'' , '''3''' (1971) pp. 101–102</TD></TR><TR><TD valign="top">[a8]</TD> <TD valign="top"> F. Spitzer,   "Principles of random walk" , Springer (1976) (Edition: Second)</TD></TR></table>
+
<table><TR><TD valign="top">[a1]</TD> <TD valign="top"> E. Sparre Andersen, "On the number of positive sums of random variables" ''Skand. Aktuarietikskr.'', '''32''' (1949) pp. 27–36</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top"> E. Sparre Andersen, "On sums of symmetrically dependent random variables" ''Skand. Aktuarietikskr.'', '''36''' (1953) pp. 123–138</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top"> E. Sparre Andersen, "On the fluctuations of sums of random variables" ''Math. Scand.'', '''1''' (1953) pp. 263–285 (Also: 2 (1954), 195–223)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top"> N.H. Bingham, C.M. Goldie, J.L. Teugels, "Regular variation", ''Encycl. Math. Appl.'', '''27''', Cambridge Univ. Press (1989) (Edition: Second)</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top"> N.G. de Bruijn, "Some algorithms for ordering a sequence of objects, with application to E. Sparre Andersen's principle of equivalence in mathematical statistics" ''Indagationes Mathematicae'', '''34''' : 1 (1972) pp. 1–10</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top"> W. Feller, [[Feller, "An introduction to probability theory and its  applications"|"An introduction to probability theory and its applications"]], '''2''', Springer (1976) (Edition: Second)</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top"> A.W. Joseph, "An elementary proof of the principle of equivalence" ''J. London Math. Soc. (2)'', '''3''' (1971) pp. 101–102</TD></TR><TR><TD valign="top">[a8]</TD> <TD valign="top"> F. Spitzer, "Principles of random walk", Springer (1976) (Edition: Second)</TD></TR></table>

Latest revision as of 18:47, 5 April 2020


A result in the theory of fluctuations in random walks (cf. Random walk). Let $ ( X _ {n} ) _ {1} ^ \infty $ be independent random variables with the same distribution (cf. Random variable), and let $ S _ {0} = 0 $, $ S _ {k} = X _ {1} + \dots + X _ {k} $, $ k \in \mathbf N $. Define

$$ M _ {n} = \max ( S _ {0} \dots S _ {n} ) , m _ {n} = { \mathop{\rm min} } ( S _ {0} \dots S _ {n} ) , $$

$$ L _ {n} = { \mathop{\rm min} } \left \{ k : {k = 0 \dots n, S _ {k} = M _ {n} } \right \} , $$

$$ L _ {n} ^ \prime = \max \left \{ k : {k = 0 \dots n, S _ {k} = m _ {n} } \right \} , $$

$$ N _ {n} = \sum _ {k = 1 } ^ { n } 1 \{ S _ {k} > 0 \} . $$

Then (equivalence principle) for each $ n \in \mathbf N $ the pairs $ ( N _ {n} ,S _ {n} ) $, $ ( L _ {n} ,S _ {n} ) $ and $ ( n - L _ {n} ^ \prime ,S _ {n} ) $ have the same distribution; in particular, $ N _ {n} $, $ L _ {n} $ and $ n - L _ {n} ^ \prime $ have the same distribution. As a consequence one has

$$ {\mathsf P} \{ N _ {n} = k \} = {\mathsf P} \{ N _ {k} = k \} {\mathsf P} \{ N _ {n - k } = 0 \} , $$

$$ k = 1 \dots n . $$

These results were first proved by E. Sparre Andersen [a1], [a2], [a3]. They connect the arcsine law for random walks to the arcsine law in renewal theory.

Nowadays there are brief proofs based on combinatorial properties of non-random sequences [a6], [a7]. The results can be generalized to random vectors with symmetric distributions [a2]. A comprehensive account for integer-valued random variables can be found in [a8]; a concise overview is given in [a4]. Related combinatorial results are discussed in [a5].

References

[a1] E. Sparre Andersen, "On the number of positive sums of random variables" Skand. Aktuarietikskr., 32 (1949) pp. 27–36
[a2] E. Sparre Andersen, "On sums of symmetrically dependent random variables" Skand. Aktuarietikskr., 36 (1953) pp. 123–138
[a3] E. Sparre Andersen, "On the fluctuations of sums of random variables" Math. Scand., 1 (1953) pp. 263–285 (Also: 2 (1954), 195–223)
[a4] N.H. Bingham, C.M. Goldie, J.L. Teugels, "Regular variation", Encycl. Math. Appl., 27, Cambridge Univ. Press (1989) (Edition: Second)
[a5] N.G. de Bruijn, "Some algorithms for ordering a sequence of objects, with application to E. Sparre Andersen's principle of equivalence in mathematical statistics" Indagationes Mathematicae, 34 : 1 (1972) pp. 1–10
[a6] W. Feller, "An introduction to probability theory and its applications", 2, Springer (1976) (Edition: Second)
[a7] A.W. Joseph, "An elementary proof of the principle of equivalence" J. London Math. Soc. (2), 3 (1971) pp. 101–102
[a8] F. Spitzer, "Principles of random walk", Springer (1976) (Edition: Second)
How to Cite This Entry:
Andersen theorem. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Andersen_theorem&oldid=14103
This article was adapted from an original article by F.W. Steutel (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article