Pólya's theorem (random walks)
The set of Pólya is a mathematical theorem from probability theory , specifically the theory of stochastic processes . He is concerned with the question of how the return probability of a symmetrical random walk to the starting point changes when the dimension of the space in which the random walk takes place increases.
Pólya's theorem is one of the classic results in the theory of random walks and was shown in 1921 by George Pólya .
preparation
dimension | Return probability to the start |
---|---|
1 | 1 |
2 | 1 |
3 | 0.340537 |
4th | 0.193206 |
5 | 0.135178 |
6th | 0.104715 |
7th | 0.0858449 |
8th | 0.0729126 |
Pólya's theorem deals with the symmetrical simple random walk in for dimensions . Such a random walk is a Markov chain and through the transition probabilities
defined, where are. Note that there can be a step forwards or backwards in each of the dimensions, which leads to possibilities overall , and each of these possibilities is by definition equally likely. For is the symmetrical simple random walk .
Furthermore, be
the return probability to the start for a given starting point . In fact, the return probabilities for all points are always the same.
statement
Pólya's theorem now reads:
- For and is recurrent , so it is for everyone . The symmetrical simple odyssey almost certainly returns to its starting point and does so infinitely often.
- For is transient , so it is for everyone . Thus, the symmetrical simple random walk almost certainly only returns to its starting point finitely often.
Web links
- AA Borovkov: Random Walk . In: Michiel Hazewinkel (Ed.): Encyclopaedia of Mathematics . Springer-Verlag , Berlin 2002, ISBN 978-1-55608-010-4 (English, online ).
literature
- Achim Klenke: Probability Theory . 3. Edition. Springer-Verlag, Berlin Heidelberg 2013, ISBN 978-3-642-36017-6 , doi : 10.1007 / 978-3-642-36018-3 .
- Hans-Otto Georgii: Stochastics . Introduction to probability theory and statistics. 4th edition. Walter de Gruyter, Berlin 2009, ISBN 978-3-11-021526-7 , doi : 10.1515 / 9783110215274 .
- Polya: About a task regarding the random walk in the road network, Mathematische Annalen, Volume 84, 1921, pp. 149-160, SUB Göttingen
Individual evidence
- ^ Georgii: Stochastics. 2009, p. 176.
- ↑ Eric W. Weisstein : Pólya's Random Walk Constants . In: MathWorld (English).