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

Some return chances

dimension ${\displaystyle D}$	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 ${\displaystyle X^{D}}$ ${\displaystyle \mathbb {Z} ^{D}}$ ${\displaystyle D\in \mathbb {N} ^{+}}$

${\displaystyle P(X_{n+1}^{D}=x|X_{n}^{D}=y)={\begin{cases}{\frac {1}{2D}}&{\text{ falls }}|x-y|=1\\0&{\text{ sonst }}\end{cases}}}$

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 . ${\displaystyle x,y\in \mathbb {Z} ^{D}}$ ${\displaystyle D}$ ${\displaystyle 2D}$ ${\displaystyle D=1}$

Furthermore, be

${\displaystyle P(x):=P(\{{\text{ Es gibt ein }}n\geq 1\;{\text{ so dass }}X_{n}=x\}\;|\;X_{0}=x)}$

the return probability to the start for a given starting point . In fact, the return probabilities for all points are always the same. ${\displaystyle x}$

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. ${\displaystyle D=1}$ ${\displaystyle D=2}$ ${\displaystyle X^{D}}$ ${\displaystyle P(x)=1}$ ${\displaystyle x}$
• For is transient , so it is for everyone . Thus, the symmetrical simple random walk almost certainly only returns to its starting point finitely often. ${\displaystyle D\geq 3}$ ${\displaystyle X^{D}}$ ${\displaystyle P(x)<1}$ ${\displaystyle x}$

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

1. ^ Georgii: Stochastics. 2009, p. 176.
2. ↑ Eric W. Weisstein : Pólya's Random Walk Constants . In: MathWorld (English).