更改

跳到导航 跳到搜索

随机游走 (查看源代码)

2022年7月4日 (一) 10:46的版本

添加111,412字节 、 2022年7月4日 (一) 10:46
Moved page from wikipedia:en:Random walk (history)
此词条暂由彩云小译翻译，翻译字数共5323，未经人工整理和审校，带来阅读不便，请见谅。

{{for|the novel|Random Walk}}
{{short description|Mathematical formalization of a path that consists of a succession of random steps}}
{{Use dmy dates|date=March 2020}}
{{Probability fundamentals}}

[[File:Eight-step random walks.png|thumb|Five eight-step random walks from a central point. Some paths appear shorter than eight steps where the route has doubled back on itself. ([[:File:Random_Walk_Simulator.gif|animated version]])]]

In [[mathematics]], a '''random walk''' is a [[random process]] that describes a path that consists of a succession of [[random]] steps on some [[Space (mathematics)|mathematical space]].

In mathematics, a random walk is a random process that describes a path that consists of a succession of random steps on some mathematical space.

在数学中，随机游走是一种随机过程，它描述了一条由一系列随机步骤组成的路径。

An elementary example of a random walk is the random walk on the integer number line <math>\mathbb Z</math> which starts at 0, and at each step moves +1 or −1 with equal [[probability]]. Other examples include the path traced by a [[molecule]] as it travels in a liquid or a gas (see [[Brownian motion]]), the search path of a [[foraging]] animal, or the price of a fluctuating [[random walk hypothesis|stock]] and the financial status of a [[gambler]]. Random walks have applications to [[engineering]] and many scientific fields including [[ecology]], [[psychology]], [[computer science]], [[physics]], [[chemistry]], [[biology]], [[economics]], and [[sociology]]. The term ''random walk'' was first introduced by [[Karl Pearson]] in 1905.<ref>{{cite journal| last=Pearson | first=Karl |title=The Problem of the Random Walk|journal=Nature|volume=72|issue=1865|pages=294 |doi=10.1038/072294b0| year=1905 | bibcode=1905Natur..72..294P|s2cid=4010776}}</ref>

An elementary example of a random walk is the random walk on the integer number line \mathbb Z which starts at 0, and at each step moves +1 or −1 with equal probability. Other examples include the path traced by a molecule as it travels in a liquid or a gas (see Brownian motion), the search path of a foraging animal, or the price of a fluctuating stock and the financial status of a gambler. Random walks have applications to engineering and many scientific fields including ecology, psychology, computer science, physics, chemistry, biology, economics, and sociology. The term random walk was first introduced by Karl Pearson in 1905.

随机游动的一个基本例子是整数行 mathbbZ 上的随机游动，它从0开始，在每一步移动 + 1或 -1的概率相等。其他的例子包括一个分子在液体或气体中旅行时所追踪的路径(参见布朗运动) ，一个觅食动物的搜索路径，或者波动的股票价格和一个赌徒的财务状况。随机游走在工程学和许多科学领域都有应用，包括生态学、心理学、计算机科学、物理学、化学、生物学、经济学和社会学。随机游走这个术语最早是由卡尔 · 皮尔森在1905年提出的。

==Lattice random walk==

==Lattice random walk==

= = 格子随机游走 = =

A popular random walk model is that of a random walk on a regular lattice, where at each step the location jumps to another site according to some probability distribution. In a ''simple random walk'', the location can only jump to neighboring sites of the lattice, forming a [[lattice path]]. In a ''simple symmetric random walk'' on a locally finite lattice, the probabilities of the location jumping to each one of its immediate neighbors are the same. The best-studied example is of random walk on the ''d''-dimensional integer lattice (sometimes called the hypercubic lattice) <math>\mathbb Z^d</math>.<ref>Pal, Révész (1990) ''Random walk in random and nonrandom environments'', World Scientific</ref>

A popular random walk model is that of a random walk on a regular lattice, where at each step the location jumps to another site according to some probability distribution. In a simple random walk, the location can only jump to neighboring sites of the lattice, forming a lattice path. In a simple symmetric random walk on a locally finite lattice, the probabilities of the location jumping to each one of its immediate neighbors are the same. The best-studied example is of random walk on the d-dimensional integer lattice (sometimes called the hypercubic lattice) \mathbb Z^d.Pal, Révész (1990) Random walk in random and nonrandom environments, World Scientific

一个流行的随机游走模型是在一个规则格子上的随机游走模型，在每一个步骤中，位置根据一些概率分布跳到另一个位置。在一个简单的随机游动中，位置只能跳到相邻的点阵位置，形成一条点阵路径。在局部有限格上的简单对称随机游动中，位置跳跃到其每一个近邻的概率是相同的。最好的研究例子是随机游走在 d 维整数格(有时称为超立方格) mathbb Z ^ d. Pal，Révész (1990)随机和非随机环境中的随机游走，世界科学

If the state space is limited to finite dimensions, the random walk model is called a ''simple bordered symmetric random walk'', and the transition probabilities depend on the location of the state because on margin and corner states the movement is limited.<ref>{{Cite document |arxiv = 1611.02861|bibcode = 2016arXiv161102861K|last1 = Kohls|first1 = Moritz|last2 = Hernandez|first2 = Tanja | title = Expected Coverage of Random Walk Mobility Algorithm|year = 2016}}</ref>

If the state space is limited to finite dimensions, the random walk model is called a simple bordered symmetric random walk, and the transition probabilities depend on the location of the state because on margin and corner states the movement is limited.

如果状态空间受有限维数的限制，随机游动模型称为简单的有边对称随机游动，由于边界和角点状态的运动受到限制，转移概率取决于状态的位置。

===One-dimensional random walk===
An elementary example of a random walk is the random walk on the [[integer]] number line, <math>\Z</math>, which starts at 0 and at each step moves +1 or −1 with equal probability.

An elementary example of a random walk is the random walk on the integer number line, \Z, which starts at 0 and at each step moves +1 or −1 with equal probability.

= = = = 一维随机游动 = = = = 一个随机游动的基本例子是整数行 Z 上的随机游动，它从0开始，每一步移动 + 1或 -1的概率相等。

This walk can be illustrated as follows. A marker is placed at zero on the number line, and a fair coin is flipped. If it lands on heads, the marker is moved one unit to the right. If it lands on tails, the marker is moved one unit to the left. After five flips, the marker could now be on -5, -3, -1, 1, 3, 5. With five flips, three heads and two tails, in any order, it will land on 1. There are 10 ways of landing on 1 (by flipping three heads and two tails), 10 ways of landing on −1 (by flipping three tails and two heads), 5 ways of landing on 3 (by flipping four heads and one tail), 5 ways of landing on −3 (by flipping four tails and one head), 1 way of landing on 5 (by flipping five heads), and 1 way of landing on −5 (by flipping five tails). See the figure below for an illustration of the possible outcomes of 5 flips.

This walk can be illustrated as follows. A marker is placed at zero on the number line, and a fair coin is flipped. If it lands on heads, the marker is moved one unit to the right. If it lands on tails, the marker is moved one unit to the left. After five flips, the marker could now be on -5, -3, -1, 1, 3, 5. With five flips, three heads and two tails, in any order, it will land on 1. There are 10 ways of landing on 1 (by flipping three heads and two tails), 10 ways of landing on −1 (by flipping three tails and two heads), 5 ways of landing on 3 (by flipping four heads and one tail), 5 ways of landing on −3 (by flipping four tails and one head), 1 way of landing on 5 (by flipping five heads), and 1 way of landing on −5 (by flipping five tails). See the figure below for an illustration of the possible outcomes of 5 flips.

此步行可以如下所示。在数字线上，一个记号笔被放置在零，一个公平的硬币被抛出。如果它落在头上，标记将向右移动一个单位。如果它落在尾部，则标记向左移动一个单位。五次翻转之后，标记可能出现在 -5，-3，-1,1,3,5。五次翻转，三个正面，两个反面，无论顺序如何，它都会落在1上。有10种降落在1上的方式(翻转三个头和两个尾巴) ，10种降落在 -1上的方式(翻转三个尾巴和两个头) ，5种降落在3上的方式(翻转四个头和一个尾巴) ，5种降落在 -3上的方式(翻转四个尾巴和一个头) ，1种降落在5上的方式(翻转五个头) ，和1种降落在 -5上的方式(翻转五个尾巴)。请参阅下面的图表来说明5次翻转的可能结果。

[[File:Flips.svg|thumb|800px|center|All possible random walk outcomes after 5 flips of a fair coin]]
[[File:random walk 2500.svg|right|thumb|280px|Random walk in two dimensions ([http://upload.wikimedia.org/wikipedia/commons/f/f3/Random_walk_2500_animated.svg animated version])]]
[[File:random walk 25000 not animated.svg|right|thumb|280px|Random walk in two dimensions with 25 thousand steps ([http://upload.wikimedia.org/wikipedia/commons/c/cb/Random_walk_25000.svg animated version])]]
[[File:Random walk 2000000.png|right|thumb|280px|Random walk in two dimensions with two million even smaller steps. This image was generated in such a way that points that are more frequently traversed are darker. In the limit, for very small steps, one obtains [[Brownian motion]].]]

thumb|800px|center|All possible random walk outcomes after 5 flips of a fair coin
right|thumb|280px|Random walk in two dimensions ([http://upload.wikimedia.org/wikipedia/commons/f/f3/Random_walk_2500_animated.svg animated version])
right|thumb|280px|Random walk in two dimensions with 25 thousand steps ([http://upload.wikimedia.org/wikipedia/commons/c/cb/Random_walk_25000.svg animated version])


拇指 | 800px | 中心 | 所有可能的随机游走结果在5次抛硬币之后右手 | 拇指 | 280px | 二维随机游走( http://upload.wikimedia.org/wikipedia/commons/f/f3/random_walk_2500_animated.svg 动画版本)右手 | 拇指 | 280px | 二维随机游走25000步( http://upload.wikimedia.org/wikipedia/commons/c/cb/random_walk_25000.svg 动画版本))

To define this walk formally, take independent random variables <math>Z_1, Z_2,\dots</math>, where each variable is either 1 or −1, with a 50% probability for either value, and set <math>S_0 = 0</math> and <math display="inline">S_n = \sum_{j=1}^n Z_j.</math> The [[Series (mathematics)|series]] <math>\{S_n\}</math> is called the ''simple random walk on <math>\Z</math>''. This series (the sum of the sequence of −1s and 1s) gives the net distance walked, if each part of the walk is of length one.
The [[expected value|expectation]] <math>E(S_n)</math> of <math>S_n</math> is zero. That is, the mean of all coin flips approaches zero as the number of flips increases. This follows by the finite additivity property of expectation:
<math display="block">E(S_n)=\sum_{j=1}^n E(Z_j)=0.</math>

To define this walk formally, take independent random variables Z_1, Z_2,\dots, where each variable is either 1 or −1, with a 50% probability for either value, and set S_0 = 0 and S_n = \sum_{j=1}^n Z_j. The series \{S_n\} is called the simple random walk on \Z. This series (the sum of the sequence of −1s and 1s) gives the net distance walked, if each part of the walk is of length one.
The expectation E(S_n) of S_n is zero. That is, the mean of all coin flips approaches zero as the number of flips increases. This follows by the finite additivity property of expectation:
E(S_n)=\sum_{j=1}^n E(Z_j)=0.

为了正式定义这个遍历，取独立的随机变量 Z _ 1，Z _ 2，点，其中每个变量是1或 -1，其中任一值的概率为50% ，并设置 S _ 0 = 0和 S _ n = sum _ { j = 1} ^ n Z _ j。级数{ S _ n }称为 Z 上的简单随机游动。这个级数(-1和1s 序列的和)给出了净步行距离，如果步行的每一部分都是长度为1的。S _ n 的期望值 E (S _ n)为零。也就是说，随着抛硬币次数的增加，所有抛硬币的平均值趋近于零。其次是期望的有限可加性: E (S _ n) = sum _ { j = 1} ^ n E (Z _ j) = 0。

A similar calculation, using the independence of the random variables and the fact that <math>E(Z_n^2)=1</math>, shows that:
<math display="block">E(S_n^2)=\sum_{i=1}^n E(Z_i^2)+2\sum_{1 \le i < j \le n}E(Z_i Z_j)=n.</math>

A similar calculation, using the independence of the random variables and the fact that E(Z_n^2)=1, shows that:
E(S_n^2)=\sum_{i=1}^n E(Z_i^2)+2\sum_{1 \le i < j \le n}E(Z_i Z_j)=n.

利用随机变量的独立性和 E (Z _ n ^ 2) = 1的事实进行了类似的计算，结果表明: E (S _ n ^ 2) = sum _ { i = 1} ^ n E (Z _ i ^ 2) + 2 sum _ {1 le i < j le n } E (Z _ i Z _ j) = n。

This hints that <math>E(|S_n|)\,\!</math>, the [[expected value|expected]] translation distance after ''n'' steps, should be [[Big O notation|of the order of]] <math>\sqrt n</math>. In fact,<ref>{{cite web|url=http://mathworld.wolfram.com/RandomWalk1-Dimensional.html |title=Random Walk-1-Dimensional – from Wolfram MathWorld |publisher=Mathworld.wolfram.com |date=2000-04-26 |access-date=2016-11-02}}</ref>
<math display="block">\lim_{n\to\infty} \frac{E(|S_n|)}{\sqrt n}= \sqrt{\frac {2}{\pi}}.</math>

This hints that E(|S_n|)\,\!, the expected translation distance after n steps, should be of the order of \sqrt n. In fact,
\lim_{n\to\infty} \frac{E(|S_n|)}{\sqrt n}= \sqrt{\frac {2}{\pi}}.

这暗示了 E (| S _ n |) ，！，n 步后的期望平移距离应该是 sqrn 的顺序。实际上，lim _ { n to infty } frac { E (| S _ n |)}{ sqrt n } = sqrt { frac {2}{ pi }}。

This result shows that diffusion is ineffective for mixing because of the way the square root behaves for large <math>N</math>.{{citation needed|date=April 2013}}

This result shows that diffusion is ineffective for mixing because of the way the square root behaves for large N.

这个结果表明，扩散对混合是无效的，因为方根的方式表现为大 N。

To answer the question of how many times will a random walk cross a boundary line if permitted to continue walking forever, a simple random walk on <math>\mathbb Z</math> will cross every point an infinite number of times. This result has many names: the ''level-crossing phenomenon'', ''recurrence'' or the ''[[gambler's ruin]]''. The reason for the last name is as follows: a gambler with a finite amount of money will eventually lose when playing ''a fair game'' against a bank with an infinite amount of money. The gambler's money will perform a random walk, and it will reach zero at some point, and the game will be over.

To answer the question of how many times will a random walk cross a boundary line if permitted to continue walking forever, a simple random walk on \mathbb Z will cross every point an infinite number of times. This result has many names: the level-crossing phenomenon, recurrence or the gambler's ruin. The reason for the last name is as follows: a gambler with a finite amount of money will eventually lose when playing a fair game against a bank with an infinite amount of money. The gambler's money will perform a random walk, and it will reach zero at some point, and the game will be over.

为了回答这个问题: 如果允许一个随机游走永远继续下去，它会越过边界线多少次? Mathbb Z 上的一个简单随机游走会无限次地越过每一个点。这个结果有许多名称: 越级现象，重复或赌徒的破产。姓氏的原因如下: 一个有限金钱的赌徒最终会在与一个有无限金钱的银行进行公平的游戏时输掉。赌徒的钱将执行一个随机游走，它将在某个点达到零，游戏将结束。

If ''a'' and ''b'' are positive integers, then the expected number of steps until a one-dimensional simple random walk starting at 0 first hits ''b'' or −''a'' is ''ab''. The probability that this walk will hit ''b'' before −''a'' is <math>a/(a+b)</math>, which can be derived from the fact that simple random walk is a [[martingale (probability theory)|martingale]]. And these expectations and hitting probabilities can be computed in <math> O(a+b) </math> in the general one-dimensional random walk Markov chain.
<!-- Maybe a reference to the iterated log law should come here? -->

If a and b are positive integers, then the expected number of steps until a one-dimensional simple random walk starting at 0 first hits b or −a is ab. The probability that this walk will hit b before −a is a/(a+b), which can be derived from the fact that simple random walk is a martingale. And these expectations and hitting probabilities can be computed in O(a+b) in the general one-dimensional random walk Markov chain.


如果 a 和 b 是正整数，那么直到从0开始的一维简单随机游动的预期步数首先命中 b 或-a 为 ab。这个随机游动在-a 之前击中 b 的概率是 a/(a + b) ，这可以从简单随机游动是鞅这一事实推导出来。在一般的一维随机游动马尔可夫链中，这些期望和命中概率可以在 O (a + b)中计算出来。

Some of the results mentioned above can be derived from properties of [[Pascal's triangle]]. The number of different walks of ''n'' steps where each step is +1 or −1 is 2<sup>''n''</sup>. For the simple random walk, each of these walks is equally likely.
In order for ''S<sub>n</sub>'' to be equal to a number ''k'' it is necessary and sufficient that the number of +1 in the walk exceeds those of −1 by ''k''. It follows +1 must appear (''n''&nbsp;+&nbsp;''k'')/2 times among ''n'' steps of a walk, hence the number of walks which satisfy <math>S_n=k</math> equals the number of ways of choosing (''n''&nbsp;+&nbsp;''k'')/2 elements from an ''n'' element set,<ref>Edward A. Codling et al, Random walk models in biology, Journal of the Royal Society Interface, 2008</ref> denoted <math display="inline">n \choose (n+k)/2</math>. For this to have meaning, it is necessary that ''n''&nbsp;+&nbsp;''k'' be an even number, which implies ''n'' and ''k'' are either both even or both odd. Therefore, the probability that <math>S_n=k</math> is equal to <math display="inline">2^{-n}{n\choose (n+k)/2}</math>. By representing entries of Pascal's triangle in terms of [[factorial]]s and using [[Stirling formula|Stirling's formula]], one can obtain good estimates for these probabilities for large values of <math>n</math>.

Some of the results mentioned above can be derived from properties of Pascal's triangle. The number of different walks of n steps where each step is +1 or −1 is 2n. For the simple random walk, each of these walks is equally likely.
In order for Sn to be equal to a number k it is necessary and sufficient that the number of +1 in the walk exceeds those of −1 by k. It follows +1 must appear (n + k)/2 times among n steps of a walk, hence the number of walks which satisfy S_n=k equals the number of ways of choosing (n + k)/2 elements from an n element set,Edward A. Codling et al, Random walk models in biology, Journal of the Royal Society Interface, 2008 denoted n \choose (n+k)/2. For this to have meaning, it is necessary that n + k be an even number, which implies n and k are either both even or both odd. Therefore, the probability that S_n=k is equal to 2^{-n}{n\choose (n+k)/2}. By representing entries of Pascal's triangle in terms of factorials and using Stirling's formula, one can obtain good estimates for these probabilities for large values of n.

上面提到的一些结果可以从帕斯卡三角形的性质推导出来。N 个步骤中每个步骤为 + 1或 -1的不同步数为2n。对于简单的随机行走，每一种行走的可能性是相等的。为了使 Sn 等于一个数 k，有必要并且充分地证明，在行走中 + 1的个数超过 -1的个数乘以 k。因此，满足 S _ n = k 的行走次数等于从 n 个元素集合中选择(n + k)/2个元素的次数，Edward A。 Coding 等，生物学中的随机行走模型，《皇家学会界面杂志》 ，2008年表示 n 选择(n + k)/2。为了使其具有意义，n + k 必须是偶数，这意味着 n 和 k 既是偶数也是奇数。因此，S _ n = k 等于2 ^ {-n }{ n 选择(n + k)/2}的概率。用阶乘表示帕斯卡三角形的条目，利用斯特林公式，可以得到对 n 的大值的这些概率的很好的估计。

If space is confined to <math>\mathbb Z</math>+ for brevity, the number of ways in which a random walk will land on any given number having five flips can be shown as {0,5,0,4,0,1}.

If space is confined to \mathbb Z+ for brevity, the number of ways in which a random walk will land on any given number having five flips can be shown as {0,5,0,4,0,1}.

如果为了简洁起见，空间被限制在 mathbb Z + 内，那么随机游动在任意给定的数字上有五次翻转的方式的数目可以显示为{0,5,0,4,0,1}。

This relation with Pascal's triangle is demonstrated for small values of ''n''. At zero turns, the only possibility will be to remain at zero. However, at one turn, there is one chance of landing on −1 or one chance of landing on 1. At two turns, a marker at 1 could move to 2 or back to zero. A marker at −1, could move to −2 or back to zero. Therefore, there is one chance of landing on −2, two chances of landing on zero, and one chance of landing on 2.

This relation with Pascal's triangle is demonstrated for small values of n. At zero turns, the only possibility will be to remain at zero. However, at one turn, there is one chance of landing on −1 or one chance of landing on 1. At two turns, a marker at 1 could move to 2 or back to zero. A marker at −1, could move to −2 or back to zero. Therefore, there is one chance of landing on −2, two chances of landing on zero, and one chance of landing on 2.

对于 n 的小值，证明了与帕斯卡三角形的这种关系。在零转弯时，唯一的可能性就是保持在零。然而，在一个回合，有一个机会降落在 -1或一个机会降落在1。在两个转弯处，1的标记可以移动到2或回到0。一个标记在 -1，可以移动到 -2或回到零。因此，有一个在 -2上着陆的机会，两个在零上着陆的机会，和一个在2上着陆的机会。

<!--[[File:PascalTriangleRandomWalk.JPG|thumb|center|600px|Pascal's triangle in a random walk]] Commenting out previous table from pic-->
{| class="wikitable" style="text-align:center"
|-
! k
! style="width:2em" | −5
! style="width:2em" | −4
! style="width:2em" | −3
! style="width:2em" | −2
! style="width:2em" | −1
! style="width:2em" | 0
! style="width:2em" | 1
! style="width:2em" | 2
! style="width:2em" | 3
! style="width:2em" | 4
! style="width:2em" | 5
|-
| <math>P[S_0=k]</math>
|
|
|
|
|
| 1
|
|
|
|
|
|-
| <math>2P[S_1=k]</math>
|
|
|
|
| 1
|
| 1
|
|
|
|
|-
| <math>2^2P[S_2=k]</math>
|
|
|
| 1
|
| 2
|
| 1
|
|
|
|-
| <math>2^3P[S_3=k]</math>
|
|
| 1
|
| 3
|
| 3
|
| 1
|
|
|-
| <math>2^4P[S_4=k]</math>
|
| 1
|
| 4
|
| 6
|
| 4
|
| 1
|
|-
| <math>2^5P[S_5=k]</math>
| 1
|
| 5
|
| 10
|
| 10
|
| 5
|
| 1
|}


{| class="wikitable" style="text-align:center"
|-
! k
! style="width:2em" | −5
! style="width:2em" | −4
! style="width:2em" | −3
! style="width:2em" | −2
! style="width:2em" | −1
! style="width:2em" | 0
! style="width:2em" | 1
! style="width:2em" | 2
! style="width:2em" | 3
! style="width:2em" | 4
! style="width:2em" | 5
|-
| P[S_0=k]
|
|
|
|
|
| 1
|
|
|
|
|
|-
| 2P[S_1=k]
|
|
|
|
| 1
|
| 1
|
|
|
|
|-
| 2^2P[S_2=k]
|
|
|
| 1
|
| 2
|
| 1
|
|
|
|-
| 2^3P[S_3=k]
|
|
| 1
|
| 3
|
| 3
|
| 1
|
|
|-
| 2^4P[S_4=k]
|
| 1
|
| 4
|
| 6
|
| 4
|
| 1
|
|-
| 2^5P[S_5=k]
| 1
|
| 5
|
| 10
|
| 10
|
| 5
|
| 1
|}


{| class="wikitable" style="text-align:center"
|-
!k
!style="width:2em" | −5
!style="width:2em" | −4
!style="width:2em" | −3
!style="width:2em" | −2
!style="width:2em" | −1
!style="width:2em" | 0
!style="width:2em" | 1
!style="width:2em" | 2
!style="width:2em" | 3
!style="width:2em" | 4
!style="width:2em" | 5
|-
| P[S_0=k]
|
|
|
|
|
| 1
|
|
|
|
|
|-
| 2P[S_1=k]
|
|
|
|
| 1
|
| 1
|
|
|
|
|-
| 2^2P[S_2=k]
|
|
|
| 1
|
| 2
|
| 1
|
|
|
|-
| 2^3P[S_3=k]
|
|
| 1
|
| 3
|
| 3
|
| 1
|
|
|-
| 2^4P[S_4=k]
|
| 1
|
| 4
|
| 6
|
| 4
|
| 1
|
|-
| 2^5P[S_5=k]
| 1
|
| 5
|
| 10
|
| 10
|
| 5
|
| 1
|}

The [[central limit theorem]] and the [[law of the iterated logarithm]] describe important aspects of the behavior of simple random walks on <math>\mathbb Z</math>. In particular, the former entails that as ''n'' increases, the probabilities (proportional to the numbers in each row) approach a [[normal distribution]].

The central limit theorem and the law of the iterated logarithm describe important aspects of the behavior of simple random walks on \mathbb Z. In particular, the former entails that as n increases, the probabilities (proportional to the numbers in each row) approach a normal distribution.

中心极限定理和重对数律描述了 mathbb Z 上简单随机游动行为的重要方面。特别地，前者要求随着 n 的增加，概率(与每行中的数字成比例)趋于正态分布。

As a direct generalization, one can consider random walks on crystal lattices (infinite-fold abelian covering graphs over finite graphs). Actually it is possible to establish the central limit theorem and large deviation theorem in this setting.<ref>{{cite journal |author= Kotani, M. and [[Toshikazu Sunada|Sunada, T.]] |year= 2003 |title= Spectral geometry of crystal lattices |journal= Contemporary. Math.|volume= 338 |pages= 271–305 |doi=10.1090/conm/338/06077|series= Contemporary Mathematics |isbn= 9780821833834 }}</ref><ref>{{cite journal |author= Kotani, M. and [[Toshikazu Sunada|Sunada, T.]] |year= 2006 |title= Large deviation and the tangent cone at infinity of a crystal lattice |journal= Math. Z. |volume= 254 |issue= 4 |pages= 837–870 |doi=10.1007/s00209-006-0951-9|s2cid= 122531716 }}</ref>

As a direct generalization, one can consider random walks on crystal lattices (infinite-fold abelian covering graphs over finite graphs). Actually it is possible to establish the central limit theorem and large deviation theorem in this setting.

作为直接推广，我们可以考虑晶格上的随机游动(有限图上的无限倍交换覆盖图)。实际上，在这种情况下建立中心极限定理和大偏差定理是可能的。

====As a Markov chain====
A one-dimensional ''random walk'' can also be looked at as a [[Markov chain]] whose state space is given by the integers <math>i=0,\pm 1,\pm 2,\dots .</math> For some number ''p'' satisfying <math>\,0 < p < 1</math>, the transition probabilities (the probability ''P<sub>i,j</sub>'' of moving from state ''i'' to state ''j'') are given by
<math display="block">\,P_{i,i+1}=p=1-P_{i,i-1}.</math>

A one-dimensional random walk can also be looked at as a Markov chain whose state space is given by the integers i=0,\pm 1,\pm 2,\dots . For some number p satisfying \,0 < p < 1, the transition probabilities (the probability Pi,j of moving from state i to state j) are given by
\,P_{i,i+1}=p=1-P_{i,i-1}.

一维随机游动也可以看作是一个马尔可夫链，其状态空间由整数 i = 0，pm1，pm2，点给出。对于满足0 < p < 1的数 p，转移概率(从状态 i 到状态 j 的概率 Pi，j)由 P _ { i，i + 1} = p = 1-P _ { i，i-1}给出。

==== Heterogeneous generalization ====
{{Main|Heterogeneous random walk in one dimension}}
{{Empty section|date=June 2021}}

===Higher dimensions===
[[File:Walk3d 0.png|right|thumb|280px|Three random walks in three dimensions]]
In higher dimensions, the set of randomly walked points has interesting geometric properties. In fact, one gets a discrete [[fractal]], that is, a set which exhibits stochastic [[self-similarity]] on large scales. On small scales, one can observe "jaggedness" resulting from the grid on which the walk is performed. The trajectory of a random walk is the collection of points visited, considered as a set with disregard to ''when'' the walk arrived at the point. In one dimension, the trajectory is simply all points between the minimum height and the maximum height the walk achieved (both are, on average, on the order of <math> \sqrt{n} </math>).

right|thumb|280px|Three random walks in three dimensions
In higher dimensions, the set of randomly walked points has interesting geometric properties. In fact, one gets a discrete fractal, that is, a set which exhibits stochastic self-similarity on large scales. On small scales, one can observe "jaggedness" resulting from the grid on which the walk is performed. The trajectory of a random walk is the collection of points visited, considered as a set with disregard to when the walk arrived at the point. In one dimension, the trajectory is simply all points between the minimum height and the maximum height the walk achieved (both are, on average, on the order of \sqrt{n} ).

= = 高维 = = 右拇指 | 280px | 三维随机游走在高维中，随机游走的点集具有有趣的几何性质。事实上，我们得到了一个离散的分形，即一个在大尺度上表现出随机自相似性的集合。在小尺度上，人们可以观察到“锯齿状”，这种锯齿状是由步行所在的网格引起的。随机行走的轨迹是所访问的点的集合，被认为是一组无视行走到达点的时间的集合。在一个维度中，轨迹仅仅是介于最小高度和最大高度之间的所有点(平均而言，两者都在 sqrt { n }的顺序上)。

To visualize the two-dimensional case, one can imagine a person walking randomly around a city. The city is effectively infinite and arranged in a square grid of sidewalks. At every intersection, the person randomly chooses one of the four possible routes (including the one originally travelled from). Formally, this is a random walk on the set of all points in the [[Plane (mathematics)|plane]] with [[integer]] [[Coordinate system|coordinates]].

To visualize the two-dimensional case, one can imagine a person walking randomly around a city. The city is effectively infinite and arranged in a square grid of sidewalks. At every intersection, the person randomly chooses one of the four possible routes (including the one originally travelled from). Formally, this is a random walk on the set of all points in the plane with integer coordinates.

为了使二维情况可视化，我们可以想象一个人在城市中随意走动。这座城市实际上是无边无际的，布置在一个方形的人行道网格中。在每个十字路口，人们随机选择四种可能的路线中的一种(包括最初走过的路线)。形式上，这是对整数坐标平面上所有点的集合进行随机游动。

To answer the question of the person ever getting back to the original starting point of the walk, this is the 2-dimensional equivalent of the level-crossing problem discussed above. In 1921 [[George Pólya]] proved that the person [[almost surely]] would in a 2-dimensional random walk, but for 3 dimensions or higher, the probability of returning to the origin decreases as the number of dimensions increases. In 3 dimensions, the probability decreases to roughly 34%.<ref>{{cite web| url=http://mathworld.wolfram.com/PolyasRandomWalkConstants.html |title=Pólya's Random Walk Constants | publisher=Mathworld.wolfram.com |access-date=2016-11-02}}</ref> The mathematician [[Shizuo Kakutani]] was known to refer to this result with the following quote: "A drunk man will find his way home, but a drunk bird may get lost forever".<ref>{{Cite book| last=Durrett|first=Rick|title=Probability: Theory and Examples|url=https://archive.org/details/probabilitytheor00rdur|url-access=limited |publisher=Cambridge University Press|year=2010|isbn=9781139491136|pages=[https://archive.org/details/probabilitytheor00rdur/page/n202 191]}}</ref>

To answer the question of the person ever getting back to the original starting point of the walk, this is the 2-dimensional equivalent of the level-crossing problem discussed above. In 1921 George Pólya proved that the person almost surely would in a 2-dimensional random walk, but for 3 dimensions or higher, the probability of returning to the origin decreases as the number of dimensions increases. In 3 dimensions, the probability decreases to roughly 34%. The mathematician Shizuo Kakutani was known to refer to this result with the following quote: "A drunk man will find his way home, but a drunk bird may get lost forever".

为了回答这个问题，人曾经回到原来的起点的步行，这是二维等价的水平交叉问题讨论了上面。1921年，George Pólya 证明，人几乎肯定会在二维随机游走，但对于三维或更高维度，返回原点的概率随着维度数量的增加而降低。在三个维度中，概率降低到大约34% 。众所周知，数学家角谷静雄(Shizuo Kakutani)引用了这个结果: “喝醉的人会找到回家的路，但喝醉的鸟可能会永远迷路。”。

Another variation of this question which was also asked by Pólya is: "if two people leave the same starting point, then will they ever meet again?"<ref>{{Cite book|last=Pólya|first=George|title=Probability; Combinatorics; Teaching and learning in mathematics|url=https://archive.org/details/collectedpapersp04plya|url-access=limited|date=1984|publisher=MIT Press|others=Rota, Gian-Carlo, 1932-1999., Reynolds, M. C., Shortt, Rae Michael.|isbn=0-262-16097-8|location=Cambridge, Mass.|pages=[https://archive.org/details/collectedpapersp04plya/page/n360 582]–585|oclc=10208449}}</ref> It can be shown that the difference between their locations (two independent random walks) is also a simple random walk, so they almost surely meet again in a 2-dimensional walk, but for 3 dimensions and higher the probability decreases with the number of the dimensions. [[Paul Erdős]] and Samuel James Taylor also showed in 1960 that for dimensions less or equal than 4, two independent random walks starting from any two given points have infinitely many intersections almost surely, but for dimensions higher than 5, they almost surely intersect only finitely often.<ref>{{Cite journal|last1=Erdős|first1=P.|last2=Taylor|first2=S. J.|date=1960|title=Some intersection properties of random walk paths|journal=Acta Mathematica Academiae Scientiarum Hungaricae|language=en|volume=11|issue=3–4|pages=231–248|doi=10.1007/BF02020942|s2cid=14143214|issn=0001-5954}}</ref>

Another variation of this question which was also asked by Pólya is: "if two people leave the same starting point, then will they ever meet again?" It can be shown that the difference between their locations (two independent random walks) is also a simple random walk, so they almost surely meet again in a 2-dimensional walk, but for 3 dimensions and higher the probability decreases with the number of the dimensions. Paul Erdős and Samuel James Taylor also showed in 1960 that for dimensions less or equal than 4, two independent random walks starting from any two given points have infinitely many intersections almost surely, but for dimensions higher than 5, they almost surely intersect only finitely often.

这个问题的另一个变体也被波利亚问到: “如果两个人离开同一个起点，那么他们还会再见面吗?”可以看出，它们位置之间的差异(两个独立的随机游动)也是一个简单的随机游动，所以它们几乎肯定会在二维游动中再次相遇，但对于三维和更高的维数，概率随着维数的减少而降低。Paul Erd 和 Samuel James Taylor 在1960年也指出，对于小于或等于4的维度，从任意两个给定点开始的两个独立随机游动几乎肯定有无限多个交点，但对于大于5的维度，它们几乎肯定只有有限次交点。

The asymptotic function for a two-dimensional random walk as the number of steps increases is given by a [[Rayleigh distribution]]. The probability distribution is a function of the radius from the origin and the step length is constant for each step.

The asymptotic function for a two-dimensional random walk as the number of steps increases is given by a Rayleigh distribution. The probability distribution is a function of the radius from the origin and the step length is constant for each step.

随着步数的增加，二维随机游动的渐近函数由一个瑞利分布给出。概率分布是原点半径的函数，每一步的步长是常数。

<math display="block">P(r) = \frac{2r}{N} e^{-r^2/N} </math>

P(r) = \frac{2r}{N} e^{-r^2/N}

P (r) = frac {2r }{ N } e ^ {-r ^ 2/N }

===Relation to Wiener process===

===Relation to Wiener process===

= = 与维纳过程的关系 = =

[[File:Brownian hierarchical.png|thumb|right|196px|Simulated steps approximating a Wiener process in two dimensions]]

thumb|right|196px|Simulated steps approximating a Wiener process in two dimensions

模拟二维维纳过程的步骤

A [[Wiener process]] is a stochastic process with similar behavior to [[Brownian motion]], the physical phenomenon of a minute particle diffusing in a fluid. (Sometimes the [[Wiener process]] is called "Brownian motion", although this is strictly speaking a confusion of a model with the phenomenon being modeled.)

A Wiener process is a stochastic process with similar behavior to Brownian motion, the physical phenomenon of a minute particle diffusing in a fluid. (Sometimes the Wiener process is called "Brownian motion", although this is strictly speaking a confusion of a model with the phenomenon being modeled.)

维纳过程是一个与布朗运动相似的随机过程过程，布朗运动是一种微小粒子在流体中扩散的物理现象。(有时，维纳过程被称为“布朗运动”，尽管这严格地说是模型与所模拟现象的混淆。)

A Wiener process is the [[scaling limit]] of random walk in dimension 1. This means that if there is a random walk with very small steps, there is an approximation to a Wiener process (and, less accurately, to Brownian motion). To be more precise, if the step size is ε, one needs to take a walk of length ''L''/ε<sup>2</sup> to approximate a Wiener length of ''L''. As the step size tends to 0 (and the number of steps increases proportionally), random walk converges to a Wiener process in an appropriate sense. Formally, if ''B'' is the space of all paths of length ''L'' with the maximum topology, and if ''M'' is the space of measure over ''B'' with the norm topology, then the convergence is in the space ''M''. Similarly, a Wiener process in several dimensions is the scaling limit of random walk in the same number of dimensions.

A Wiener process is the scaling limit of random walk in dimension 1. This means that if there is a random walk with very small steps, there is an approximation to a Wiener process (and, less accurately, to Brownian motion). To be more precise, if the step size is ε, one needs to take a walk of length L/ε2 to approximate a Wiener length of L. As the step size tends to 0 (and the number of steps increases proportionally), random walk converges to a Wiener process in an appropriate sense. Formally, if B is the space of all paths of length L with the maximum topology, and if M is the space of measure over B with the norm topology, then the convergence is in the space M. Similarly, a Wiener process in several dimensions is the scaling limit of random walk in the same number of dimensions.

维纳过程是维数为1的随机游动的标度极限。这意味着，如果有一个非常小的步长的随机游动，就有一个近似维纳过程(不太准确地说，是布朗运动)。更准确地说，如果步长是 ε，那么需要走一段 L/ε2的长度来近似 L 的 Wiener 长度。随着步长趋于0(步数成比例增加) ，随机游走在一定意义上收敛到 Wiener 过程。形式上，如果 B 是具有最大拓扑的 L 的所有路径的空间，而 M 是具有范拓扑的 B 上的测度空间，则收敛于空间 M。同样，多维维维纳过程是相同维数下随机游动的标度极限。

A random walk is a discrete fractal (a function with integer dimensions; 1, 2, ...), but a Wiener process trajectory is a true fractal, and there is a connection between the two. For example, take a random walk until it hits a circle of radius ''r'' times the step length. The average number of steps it performs is ''r''<sup>2</sup>.{{citation needed|date=April 2012}} This fact is the ''discrete version'' of the fact that a Wiener process walk is a fractal of [[Hausdorff dimension]]&nbsp;2.{{citation needed|date=April 2012}}

A random walk is a discrete fractal (a function with integer dimensions; 1, 2, ...), but a Wiener process trajectory is a true fractal, and there is a connection between the two. For example, take a random walk until it hits a circle of radius r times the step length. The average number of steps it performs is r2. This fact is the discrete version of the fact that a Wiener process walk is a fractal of Hausdorff dimension 2.

随机游走是一个离散的分形(一个具有整数维度的函数; 1,2，...) ，但是维纳过程轨迹是一个真正的分形，并且两者之间存在联系。例如，随机游走直到它到达一个半径为 r 乘以步长的圆。它执行的平均步数是 r2。这个事实是维纳过程行走是豪斯多夫维数2的分形的离散版本。

In two dimensions, the average number of points the same random walk has on the ''boundary'' of its trajectory is ''r''<sup>4/3</sup>. This corresponds to the fact that the boundary of the trajectory of a Wiener process is a fractal of dimension 4/3, a fact predicted by [[Benoît Mandelbrot|Mandelbrot]] using simulations but proved only in 2000
by [[Greg Lawler|Lawler]], [[Oded Schramm|Schramm]] and [[Wendelin Werner|Werner]].<ref>{{cite journal|year = 2000|doi = 10.1126/science.290.5498.1883|pmid = 17742050|title = MATHEMATICS: Taking the Measure of the Wildest Dance on Earth|journal = Science|volume = 290|issue = 5498|pages = 1883–4|last1 = MacKenzie|first1 = D.|s2cid = 12829171}} {{erratum|doi=10.1126/science.291.5504.597|checked=yes}}</ref>

In two dimensions, the average number of points the same random walk has on the boundary of its trajectory is r4/3. This corresponds to the fact that the boundary of the trajectory of a Wiener process is a fractal of dimension 4/3, a fact predicted by Mandelbrot using simulations but proved only in 2000
by Lawler, Schramm and Werner.

在二维情况下，同一随机游动在其轨道边界上的平均点数为 r4/3。这与维纳过程轨迹的边界是4/3维的分形这一事实相对应，Mandelbrot 使用模拟预测了这一事实，但直到2000年才得到 Lawler，Schramm 和 Werner 的证实。

A Wiener process enjoys many [[symmetry|symmetries]] a random walk does not. For example, a Wiener process walk is invariant to rotations, but the random walk is not, since the underlying grid is not (random walk is invariant to rotations by 90 degrees, but Wiener processes are invariant to rotations by, for example, 17 degrees too). This means that in many cases, problems on a random walk are easier to solve by translating them to a Wiener process, solving the problem there, and then translating back. On the other hand, some problems are easier to solve with random walks due to its discrete nature.

A Wiener process enjoys many symmetries a random walk does not. For example, a Wiener process walk is invariant to rotations, but the random walk is not, since the underlying grid is not (random walk is invariant to rotations by 90 degrees, but Wiener processes are invariant to rotations by, for example, 17 degrees too). This means that in many cases, problems on a random walk are easier to solve by translating them to a Wiener process, solving the problem there, and then translating back. On the other hand, some problems are easier to solve with random walks due to its discrete nature.

维纳过程具有许多对称性，而随机游走则不具有这些对称性。例如，Wiener 进程的行走对于旋转是不变的，但是随机行走不是，因为底层网格不是(随机行走对于旋转不变90度，但是 Wiener 进程对于旋转不变17度)。这意味着在许多情况下，随机游走中的问题更容易解决，方法是将它们转换成 Wiener 过程，在那里解决问题，然后再转换回来。另一方面，由于随机游动的离散性，有些问题比较容易解决。

Random walk and [[Wiener process]] can be [[Coupling (probability)|''coupled'']], namely manifested on the same probability space in a dependent way that forces them to be quite close. The simplest such coupling is the [[Skorokhod's embedding theorem|Skorokhod embedding]], but there exist more precise couplings, such as [[Komlós–Major–Tusnády approximation]] theorem.

Random walk and Wiener process can be coupled, namely manifested on the same probability space in a dependent way that forces them to be quite close. The simplest such coupling is the Skorokhod embedding, but there exist more precise couplings, such as Komlós–Major–Tusnády approximation theorem.

随机游走和维纳过程可以耦合，即在同一个概率空间上以一种依赖的方式表现出来，迫使它们非常接近。最简单的耦合是 Skorokhod 嵌入，但也存在更精确的耦合，如 Komlós-Major-Tusnády 近似定理。

The convergence of a random walk toward the Wiener process is controlled by the [[central limit theorem]], and by [[Donsker's theorem]]. For a particle in a known fixed position at ''t''&nbsp;=&nbsp;0, the central limit theorem tells us that after a large number of [[statistical independence|independent]] steps in the random walk, the walker's position is distributed according to a [[normal distribution]] of total [[variance]]:

The convergence of a random walk toward the Wiener process is controlled by the central limit theorem, and by Donsker's theorem. For a particle in a known fixed position at t = 0, the central limit theorem tells us that after a large number of independent steps in the random walk, the walker's position is distributed according to a normal distribution of total variance:

随机游走到维纳过程的收敛是由中心极限定理和 Donsker 定理控制的。对于一个在 t = 0处于已知固定位置的粒子，中心极限定理告诉我们，在随机游走中经过大量独立步骤之后，步行者的位置是按照总方差的正态分布来分布的:

<math display="block">\sigma^2 = \frac{t}{\delta t}\,\varepsilon^2,</math>

\sigma^2 = \frac{t}{\delta t}\,\varepsilon^2,

Sigma ^ 2 = frac { t }{ delta t } ，varepsilon ^ 2,

where ''t'' is the time elapsed since the start of the random walk, <math>\varepsilon</math> is the size of a step of the random walk, and <math>\delta t</math> is the time elapsed between two successive steps.

where t is the time elapsed since the start of the random walk, \varepsilon is the size of a step of the random walk, and \delta t is the time elapsed between two successive steps.

其中 t 是自随机游动开始以来所经过的时间 varepsilon 是随机游动的一个步长 delta t 是两个连续步长之间所经过的时间。

This corresponds to the [[Green's function]] of the [[diffusion equation]] that controls the Wiener process, which suggests that, after a large number of steps, the random walk converges toward a Wiener process.

This corresponds to the Green's function of the diffusion equation that controls the Wiener process, which suggests that, after a large number of steps, the random walk converges toward a Wiener process.

这与控制维纳过程的扩散方程的格林函数相对应，也就是说，经过大量的步骤之后，随机游走收敛到维纳过程。

In 3D, the variance corresponding to the [[Green's function]] of the diffusion equation is:
<math display="block">\sigma^2 = 6\,D\,t.</math>

In 3D, the variance corresponding to the Green's function of the diffusion equation is:
\sigma^2 = 6\,D\,t.

在3 d 中，与扩散方程的格林函数对应的方差是: sigma ^ 2 = 6，d，t。

By equalizing this quantity with the variance associated to the position of the random walker, one obtains the equivalent diffusion coefficient to be considered for the asymptotic Wiener process toward which the random walk converges after a large number of steps:
<math display="block">D = \frac{\varepsilon^2}{6 \delta t}</math> (valid only in 3D).

By equalizing this quantity with the variance associated to the position of the random walker, one obtains the equivalent diffusion coefficient to be considered for the asymptotic Wiener process toward which the random walk converges after a large number of steps:
D = \frac{\varepsilon^2}{6 \delta t} (valid only in 3D).

通过将这个量与随机步行者位置相关的方差相等化，得到了渐近 Wiener 过程的等效扩散系数: D = frac { varepsilon ^ 2}{6 delta t }(仅在3D 中有效)。

The two expressions of the variance above correspond to the distribution associated to the vector <math>\vec R</math> that links the two ends of the random walk, in 3D. The variance associated to each component <math>R_x</math>, <math>R_y</math> or <math>R_z</math> is only one third of this value (still in 3D).

The two expressions of the variance above correspond to the distribution associated to the vector \vec R that links the two ends of the random walk, in 3D. The variance associated to each component R_x, R_y or R_z is only one third of this value (still in 3D).

上面的两个方差表达式对应于3D 中连接随机游动两端的向量 vec R 的分布。与每个分量 R _ x、 R _ y 或 R _ z 相关联的方差只有这个值的三分之一(仍然是3D)。

For 2D:<ref>[http://engineering.dartmouth.edu/~d30345d/courses/engs43/Chapter2.pdf Chapter 2 DIFFUSION]. dartmouth.edu.</ref>

For 2D:Chapter 2 DIFFUSION. dartmouth.edu.

对于2D: 第2章扩散。Dartmouth Edu.

<math display="block">D = \frac{\varepsilon^2}{4 \delta t}.</math>

D = \frac{\varepsilon^2}{4 \delta t}.

D = frac { varepsilon ^ 2}{4 delta t }.

For 1D:<ref>[http://nebula.physics.uakron.edu/dept/faculty/jutta/modeling/diff_eqn.pdf Diffusion equation for the random walk]. physics.uakron.edu.</ref>

For 1D:Diffusion equation for the random walk. physics.uakron.edu.

1 d: 随机游走的扩散方程。Physics.uakron.edu.

<math display="block">D = \frac{\varepsilon^2}{2 \delta t}.</math>

D = \frac{\varepsilon^2}{2 \delta t}.

D = frac { varepsilon ^ 2}{2 delta t }.

==Gaussian random walk==
A random walk having a step size that varies according to a [[normal distribution]] is used as a model for real-world time series data such as financial markets. The [[Black–Scholes]] formula for modeling option prices, for example, uses a Gaussian random walk as an underlying assumption.

A random walk having a step size that varies according to a normal distribution is used as a model for real-world time series data such as financial markets. The Black–Scholes formula for modeling option prices, for example, uses a Gaussian random walk as an underlying assumption.

高斯随机游动 = = 步长随正态分布变化的随机游动被用作金融市场等现实世界时间序列数据的模型。例如，模拟期权价格的 Black-Scholes 公式使用高斯随机游走作为基本假设。

Here, the step size is the inverse cumulative normal distribution <math>\Phi^{-1}(z,\mu,\sigma)</math> where 0&nbsp;≤&nbsp;''z''&nbsp;≤&nbsp;1 is a uniformly distributed random number, and μ and σ are the mean and standard deviations of the normal distribution, respectively.

Here, the step size is the inverse cumulative normal distribution \Phi^{-1}(z,\mu,\sigma) where 0 ≤ z ≤ 1 is a uniformly distributed random number, and μ and σ are the mean and standard deviations of the normal distribution, respectively.

这里，步长是逆累积正态分布 Phi ^ {-1}(z，mu，σ) ，其中0≤ z ≤1是一个均匀分布的随机数，μ 和 σ 分别是正态分布的平均值和标准差。

If μ is nonzero, the random walk will vary about a linear trend. If v<sub>s</sub> is the starting value of the random walk, the expected value after ''n'' steps will be v<sub>s</sub> + ''n''μ.

If μ is nonzero, the random walk will vary about a linear trend. If vs is the starting value of the random walk, the expected value after n steps will be vs + nμ.

如果 μ 是非零的，随机游动将变化约一个线性趋势。如果 vs 是随机游动的起始值，那么 n 步之后的期望值将是 vs + nμ。

For the special case where μ is equal to zero, after ''n'' steps, the translation distance's probability distribution is given by ''N''(0, ''n''σ<sup>2</sup>), where ''N''() is the notation for the normal distribution, ''n'' is the number of steps, and σ is from the inverse cumulative normal distribution as given above.

For the special case where μ is equal to zero, after n steps, the translation distance's probability distribution is given by N(0, nσ2), where N() is the notation for the normal distribution, n is the number of steps, and σ is from the inverse cumulative normal distribution as given above.

对于 μ 等于零的特殊情况，n 步之后，平移距离的概率分布由 N (0，nσ2)给出，其中 N ()是正态分布的表示法，n 是步数，σ 来自上面给出的反累积正态分布。

Proof: The Gaussian random walk can be thought of as the sum of a sequence of independent and identically distributed random variables, X<sub>i</sub> from the inverse cumulative normal distribution with mean equal zero and σ of the original inverse cumulative normal distribution:
<math display="block">Z = \sum_{i=0}^n {X_i},</math>

Proof: The Gaussian random walk can be thought of as the sum of a sequence of independent and identically distributed random variables, Xi from the inverse cumulative normal distribution with mean equal zero and σ of the original inverse cumulative normal distribution:
Z = \sum_{i=0}^n {X_i},

证明: 高斯随机游动可以被看作是一系列独立同分布的和，来自平均等于零的反累积正态分布，以及原始的反累积正态分布的 σ: Z = sum _ { i = 0} ^ n { x _ i } ,

but we have the distribution for the sum of two independent normally distributed random variables, {{math|1=''Z'' = ''X'' + ''Y''}}, is given by
<math display="block">\mathcal{N}(\mu_X + \mu_Y, \sigma_X^2 + \sigma_Y^2)</math> [[Sum of normally distributed random variables|(see here)]].

but we have the distribution for the sum of two independent normally distributed random variables, , is given by
\mathcal{N}(\mu_X + \mu_Y, \sigma_X^2 + \sigma_Y^2) (see here).

但是我们有两个独立的正态分布随机变量之和的分布，由数学{ N }(mu _ X + mu _ Y，sigma _ X ^ 2 + sigma _ Y ^ 2)给出(见这里)。

In our case, {{math|1=μ<sub>X</sub> = μ<sub>Y</sub> = 0}} and {{math|1=σ<sup>2</sup><sub>X</sub> = σ<sup>2</sup><sub>Y</sub> = σ<sup>2</sup>}} yield
<math display="block">\mathcal{N}(0, 2\sigma^2)</math>
By induction, for ''n'' steps we have
<math>Z \sim \mathcal{N}(0, n \sigma^2).</math>
For steps distributed according to any distribution with zero mean and a finite variance (not necessarily just a normal distribution), the [[root mean square]] translation distance after ''n'' steps is
<math display="block">\sqrt{E|S_n^2|} = \sigma \sqrt{n}.</math>

In our case, and yield
\mathcal{N}(0, 2\sigma^2)
By induction, for n steps we have
Z \sim \mathcal{N}(0, n \sigma^2).
For steps distributed according to any distribution with zero mean and a finite variance (not necessarily just a normal distribution), the root mean square translation distance after n steps is
\sqrt{E|S_n^2|} = \sigma \sqrt{n}.

在我们的例子中，通过归纳得到数学{ N }(0,2 sigma ^ 2) ，对于 n 个步骤，我们得到 Z sim 数学{ N }(0，n sigma ^ 2)。对于按照任意均值为零且方差有限的分布(不一定是正态分布)分布的步长，n 步后的平方平均数平移距离为 sqrt { E | S _ n ^ 2 | } = sigma sqrt { n }。

But for the Gaussian random walk, this is just the standard deviation of the translation distance's distribution after ''n'' steps. Hence, if μ is equal to zero, and since the root mean square(RMS) translation distance is one standard deviation, there is 68.27% probability that the RMS translation distance after ''n'' steps will fall between <math>\pm \sigma \sqrt{n}</math>. Likewise, there is 50% probability that the translation distance after ''n'' steps will fall between <math>\pm 0.6745 \sigma \sqrt{n}</math>.

But for the Gaussian random walk, this is just the standard deviation of the translation distance's distribution after n steps. Hence, if μ is equal to zero, and since the root mean square(RMS) translation distance is one standard deviation, there is 68.27% probability that the RMS translation distance after n steps will fall between \pm \sigma \sqrt{n}. Likewise, there is 50% probability that the translation distance after n steps will fall between \pm 0.6745 \sigma \sqrt{n}.

但对于高斯随机游动，这只是 n 步后平移距离分布的标准差。因此，如果 μ 等于零，并且由于平方平均数平移距离是一个标准差，那么 n 步后的平移距离落在 pm sigma sqrt { n }之间的可能性为68.27% 。同样，n 步之后的平移距离有50% 的可能性落在下午0.6745 sigma sqrt { n }之间。

===Number of distinct sites===
The number of distinct sites visited by a single random walker <math>S(t)</math> has been studied extensively for square and cubic lattices and for fractals.<ref name="WeissRubin1982">{{cite book|last1=Weiss|first1=George H.|title=Advances in Chemical Physics|last2=Rubin|first2=Robert J.|chapter=Random Walks: Theory and Selected Applications|volume=52|year=1982| pages=363–505|doi=10.1002/9780470142769.ch5|isbn=9780470142769}}</ref><ref name="BlumenKlafter1986">{{cite book| last1=Blumen|first1=A. |title=Optical Spectroscopy of Glasses|last2=Klafter|first2=J.|last3=Zumofen|first3=G.|chapter=Models for Reaction Dynamics in Glasses|volume=1|year=1986|pages=199–265|doi=10.1007/978-94-009-4650-7_5|bibcode = 1986PCMLD...1..199B | series=Physic and Chemistry of Materials with Low-Dimensional Structures|isbn=978-94-010-8566-3}}</ref> This quantity is useful for the analysis of problems of trapping and kinetic reactions. It is also related to the vibrational density of states,<ref name="AlexanderOrbach1982">{{cite journal|last1=Alexander|first1=S.|last2=Orbach|first2=R.|title=Density of states on fractals : " fractons "|journal=Journal de Physique Lettres|volume=43|issue=17|year=1982| pages=625–631| doi=10.1051/jphyslet:019820043017062500 |s2cid=67757791|url=https://semanticscholar.org/paper/68d535511f6dcbf5776f1430e5816b99462ef989}}</ref><ref name="RammalToulouse1983">{{cite journal|last1=Rammal|first1=R.| last2=Toulouse|first2=G.|title=Random walks on fractal structures and percolation clusters|journal=Journal de Physique Lettres |volume=44|issue=1|year=1983|pages=13–22|doi=10.1051/jphyslet:0198300440101300|url=https://hal.archives-ouvertes.fr/jpa-00232136/document}}</ref> diffusion reactions processes<ref>{{cite journal|last=Smoluchowski|first=M.V.|journal=Z. Phys. Chem. | number=29| pages=129–168|year=1917|title=Versuch einer mathematischen Theorie der Koagulationskinetik kolloider Lösungen}},{{cite book|last=Rice|first=S.A.|title=Diffusion-Limited Reactions|url=https://books.google.com/books?id=sWiyspAjelsC&pg=PP2|access-date=13 August 2013|series=Comprehensive Chemical Kinetics|volume=25|date=1 March 1985|publisher=Elsevier | isbn=978-0-444-42354-2}}</ref>
and spread of populations in ecology.<ref name="Skellam1951">{{cite journal|last1=Skellam|first1=J. G.|title=Random Dispersal in Theoretical Populations|journal=Biometrika|volume=38|issue=1/2|year=1951|pages=196–218|doi=10.2307/2332328|jstor=2332328 | pmid=14848123}}</ref><ref>{{cite journal|last1=Skellam|first1=J. G.|title=Studies in Statistical Ecology: I. Spatial Pattern| journal=Biometrika|volume=39|issue=3/4|year=1952|pages=346–362|doi=10.2307/2334030|jstor=2334030}}</ref>

The number of distinct sites visited by a single random walker S(t) has been studied extensively for square and cubic lattices and for fractals. This quantity is useful for the analysis of problems of trapping and kinetic reactions. It is also related to the vibrational density of states, diffusion reactions processes,
and spread of populations in ecology.

单个随机行走者 S (t)访问的不同位置的数目已经被广泛地研究了正方形和立方形格子以及分形。这个量对于分析捕获和动力学反应问题是有用的。它还与振动状态密度、扩散反应过程以及生态学中种群的扩散有关。

===Information rate===
The [[information rate]] of a Gaussian random walk with respect to the squared error distance, i.e. its quadratic [[rate distortion function]], is given parametrically by<ref>{{Cite journal |doi = 10.1109/TIT.1970.1054423|title = Information rates of Wiener processes|year = 1970|last1 = Berger|first1 = T.|journal = IEEE Transactions on Information Theory|volume = 16|issue = 2|pages = 134–139}}</ref>
<math display="block"> R(D_\theta) = \frac{1}{2} \int_0^1 \max\{0, \log_2\left(S(\varphi)/\theta \right) \} \, d\varphi, </math>
<math display="block"> D_\theta = \int_0^1 \min\{S(\varphi),\theta\} \, d\varphi, </math>
where <math>S(\varphi) = \left(2 \sin (\pi \varphi/2) \right)^{-2}</math>. Therefore, it is impossible to encode <math>{\{Z_n\}_{n=1}^N}</math> using a [[binary code]] of less than <math>NR(D_\theta)</math> [[bit]]s and recover it with expected mean squared error less than <math>D_\theta</math>. On the other hand, for any <math>\varepsilon>0</math>, there exists an <math>N \in \mathbb N</math> large enough and a [[binary code]] of no more than <math>2^{N R(D_{\theta})}</math> distinct elements such that the expected mean squared error in recovering <math>{\{Z_n\}_{n=1}^N}</math> from this code is at most <math>D_\theta - \varepsilon</math>.

The information rate of a Gaussian random walk with respect to the squared error distance, i.e. its quadratic rate distortion function, is given parametrically by
R(D_\theta) = \frac{1}{2} \int_0^1 \max\{0, \log_2\left(S(\varphi)/\theta \right) \} \, d\varphi,
D_\theta = \int_0^1 \min\{S(\varphi),\theta\} \, d\varphi,
where S(\varphi) = \left(2 \sin (\pi \varphi/2) \right)^{-2}. Therefore, it is impossible to encode {\{Z_n\}_{n=1}^N} using a binary code of less than NR(D_\theta) bits and recover it with expected mean squared error less than D_\theta. On the other hand, for any \varepsilon>0, there exists an N \in \mathbb N large enough and a binary code of no more than 2^{N R(D_{\theta})} distinct elements such that the expected mean squared error in recovering {\{Z_n\}_{n=1}^N} from this code is at most D_\theta - \varepsilon.

信息率高斯随机游动相对于误差平方距离的信息率，即。它的二次速率失真函数，由 R (D _ theta) = frac {1}{2} int _ 0 ^ 1 max {0，log _ 2 left (S (varphi)/theta right)} ，d varphi，D _ theta = int _ 0 ^ 1 min { S (varphi) ，theta } ，d varphi 参数给出，其中 S (varphi) = left (2 sin (pi varphi/2) right) ^ {-2}。因此，使用小于 NR (D _ theta)比特的二进制码来编码{{ Z _ n } _ { n = 1} ^ N } ，并用小于 d _ theta 的期望均方差来恢复它是不可能的。另一方面，对于任何大于0的 varepsilon，在 mathbbN 中存在一个足够大的 n，并且存在一个不超过2 ^ { nR (dtheta })}的二进制代码，使得从这个代码中恢复{{ zn } _ { n = 1} ^ N }的期望均方差最多为 dtheta-varepsilon。

==Applications==
{{More citations needed section|date=February 2013}}
[[File:Antony Gormley Quantum Cloud 2000.jpg|thumb|[[Antony Gormley]]'s ''[[Quantum Cloud]]'' sculpture in London was designed by a computer using a random walk algorithm]]
As mentioned the range of natural phenomena which have been subject to attempts at description by some flavour of random walks is considerable, particularly in physics<ref name=[5]>Risken H. (1984) ''The Fokker–Planck Equation''. Springer, Berlin.</ref><ref name=[4c]>De Gennes P. G. (1979) ''Scaling Concepts in Polymer Physics''. Cornell University Press, Ithaca and London.</ref> and chemistry,<ref name=[1]>Van Kampen N. G. (1992) ''Stochastic Processes in Physics and Chemistry'', revised and enlarged edition. North-Holland, Amsterdam.</ref> [[materials science]],<ref name=[6]>{{cite book | last = Weiss | first = George H. | author-link = George Herbert Weiss | isbn = 978-0-444-81606-1 | mr = 1280031 | publisher = North-Holland Publishing Co., Amsterdam | series = Random Materials and Processes | title = Aspects and Applications of the Random Walk | year = 1994}}</ref><ref name=[4]>Doi M. and Edwards S. F. (1986) ''The Theory of Polymer Dynamics''. Clarendon Press, Oxford</ref> and biology.<ref name=[3]>Goel N. W. and [[Nira Dyn|Richter-Dyn N.]] (1974) ''Stochastic Models in Biology''. Academic Press, New York.</ref> <ref name=[2]>Redner S. (2001) ''A Guide to First-Passage Process''. Cambridge University Press, Cambridge, UK.</ref><ref name=[7]>Cox D. R. (1962) ''Renewal Theory''. Methuen, London.</ref> The following are some specific applications of random walks:
*In [[financial economics]], the [[random walk hypothesis]] is used to model shares prices and other factors.<ref>David A. Kodde and Hein Schreuder (1984), Forecasting Corporate Revenue and Profit: Time-Series Models versus Management and Analysts, Journal of Business Finance and Accounting, vol. 11, no 3, Autumn 1984</ref> Empirical studies found some deviations from this theoretical model, especially in short term and long term correlations. See [[share price]]s.
*In [[population genetics]], random walk describes the statistical properties of [[genetic drift]]
*In [[physics]], random walks are used as simplified models of physical Brownian motion and diffusion such as the [[random]] [[Motion (physics)|movement]] of [[molecules]] in liquids and gases. See for example diffusion-limited aggregation. Also in physics, random walks and some of the self interacting walks play a role in [[quantum field theory]].
*In [[theoretical biology|mathematical ecology]], random walks are used to describe individual animal movements, to empirically support processes of [[diffusion|biodiffusion]], and occasionally to model [[population dynamics]].
*In [[polymer physics]], random walk describes an [[ideal chain]]. It is the simplest model to study [[polymers]].<ref>{{cite book|last1=Jones|first1=R.A.L.|title=Soft condensed matter|url=https://archive.org/details/softcondensedmat00jone|url-access=limited|date=2004|publisher=Oxford Univ. Pr.|location=Oxford [u.a.]|isbn=978-0-19-850589-1|pages=[https://archive.org/details/softcondensedmat00jone/page/n89 77]–78|edition=Reprint.}}</ref>
*In other fields of mathematics, random walk is used to calculate solutions to [[Laplace's equation]], to estimate the [[harmonic measure]], and for various constructions in [[Mathematical analysis|analysis]] and [[combinatorics]].
* In [[computer science]], random walks are used to estimate the size of the [[www|Web]].<ref name="Bar-Yossef Gurevich 2008 pp. 1–74">{{cite journal | last1=Bar-Yossef | first1=Ziv | last2=Gurevich | first2=Maxim | title=Random sampling from a search engine's index | journal=Journal of the ACM | publisher=Association for Computing Machinery (ACM) | volume=55 | issue=5 | year=2008 | issn=0004-5411 | doi=10.1145/1411509.1411514 | pages=1–74}}</ref>
* In [[Segmentation (image processing)|image segmentation]], random walks are used to determine the labels (i.e., "object" or "background") to associate with each pixel.<ref>{{cite journal |pmid=17063682|url=http://cns-web.bu.edu/~lgrady/grady2006random.pdf|year=2006|last1=Grady|first1=L|title=Random walks for image segmentation|journal=IEEE Transactions on Pattern Analysis and Machine Intelligence|volume=28|issue=11|pages=1768–83|doi=10.1109/TPAMI.2006.233|citeseerx=10.1.1.375.3389|s2cid=489789}}</ref> This algorithm is typically referred to as the [[random walker (computer vision)|random walker]] segmentation algorithm.



As mentioned the range of natural phenomena which have been subject to attempts at description by some flavour of random walks is considerable, particularly in physicsRisken H. (1984) The Fokker–Planck Equation. Springer, Berlin.De Gennes P. G. (1979) Scaling Concepts in Polymer Physics. Cornell University Press, Ithaca and London. and chemistry,Van Kampen N. G. (1992) Stochastic Processes in Physics and Chemistry, revised and enlarged edition. North-Holland, Amsterdam. materials science,Doi M. and Edwards S. F. (1986) The Theory of Polymer Dynamics. Clarendon Press, Oxford and biology.Goel N. W. and Richter-Dyn N. (1974) Stochastic Models in Biology. Academic Press, New York. Redner S. (2001) A Guide to First-Passage Process. Cambridge University Press, Cambridge, UK.Cox D. R. (1962) Renewal Theory. Methuen, London. The following are some specific applications of random walks:
*In financial economics, the random walk hypothesis is used to model shares prices and other factors.David A. Kodde and Hein Schreuder (1984), Forecasting Corporate Revenue and Profit: Time-Series Models versus Management and Analysts, Journal of Business Finance and Accounting, vol. 11, no 3, Autumn 1984 Empirical studies found some deviations from this theoretical model, especially in short term and long term correlations. See share prices.
*In population genetics, random walk describes the statistical properties of genetic drift
*In physics, random walks are used as simplified models of physical Brownian motion and diffusion such as the random movement of molecules in liquids and gases. See for example diffusion-limited aggregation. Also in physics, random walks and some of the self interacting walks play a role in quantum field theory.
*In mathematical ecology, random walks are used to describe individual animal movements, to empirically support processes of biodiffusion, and occasionally to model population dynamics.
*In polymer physics, random walk describes an ideal chain. It is the simplest model to study polymers.
*In other fields of mathematics, random walk is used to calculate solutions to Laplace's equation, to estimate the harmonic measure, and for various constructions in analysis and combinatorics.
* In computer science, random walks are used to estimate the size of the Web.
* In image segmentation, random walks are used to determine the labels (i.e., "object" or "background") to associate with each pixel. This algorithm is typically referred to as the random walker segmentation algorithm.

= = 应用 = = 正如前面提到的，自然现象的范围相当广泛，人们试图用随机游走的某种味道来描述这些现象，特别是在物理学领域，Risken H。(1984)福克-普朗克方程。(1979)高分子物理中的标度概念。康乃尔大学出版社，绮色佳和伦敦。和化学，范坎本 N.G. (1992)物理和化学的随机过程，修订和扩大版。North-Holland.材料科学，Doi M 和 Edwards S。(1986)聚合物动力学理论。克拉伦登出版社，牛津大学与生物学。生物学随机模型。(1974)。学术出版社，纽约。雷德纳(2001)第一通道过程指南。剑桥大学出版社，剑桥，英国。考克斯 D。(1962)更新理论。梅休因。以下是随机游走的一些具体应用:
* 在金融经济学中，随机游走假说被用来模拟股票价格和其他因素。Kodde 和 Hein Schreuder (1984) ，《预测公司收入和利润: 时间序列模型与管理和分析师的比较》 ，《商业财务与会计杂志》 ，1984年第1期。1984年秋季实证研究发现，这一理论模型存在一些偏差，尤其是在短期和长期相关性方面。参见股票价格。
* 在群体遗传学中，随机游走描述了遗传漂移的统计特性
* 在物理学中，随机游走被用作物理布朗运动和扩散的简化模型，例如液体和气体中分子的随机运动。参见例子扩散受限的聚合。同样在物理学中，随机游动和一些自相互作用游动在量子场论中也起着重要作用。
* 在数学生态学中，随机游走被用来描述个别动物的运动，从经验上支持生物扩散过程，偶尔也用来模拟族群动态。
* 在高分子物理学中，随机游走描述了一个理想链。这是研究聚合物最简单的模型。
* 在其他数学领域，随机游走被用于计算拉普拉斯方程的解，估计调和测度，以及分析和组合学中的各种构造。在计算机科学中，随机游走被用来估计网络的大小。
* 在图像分割中，随机漫步用于确定与每个像素相关联的标签(即“对象”或“背景”)。这种算法通常被称为随机步行者分割算法。

*In [[human brain|brain research]], random walks and reinforced random walks are used to model cascades of neuron firing in the brain.
*In [[vision science]], ocular drift tends to behave like a random walk.<ref>{{cite journal |pmid=25698649|pmc=4385455|year=2015|last1=Rucci|first1=M|title=The unsteady eye: An information-processing stage, not a bug|journal=Trends in Neurosciences|volume=38|issue=4|pages=195–206|last2=Victor|first2=J. D.|doi=10.1016/j.tins.2015.01.005}}</ref> According to some authors, [[fixational eye movements]] in general are also well described by a random walk.<ref>{{cite journal |doi= 10.1073/pnas.1102730108|title= An integrated model of fixational eye movements and microsaccades|journal= Proceedings of the National Academy of Sciences|volume= 108|issue= 39|pages= E765-70|year= 2011|last1= Engbert|first1= R.|last2= Mergenthaler|first2= K.|last3= Sinn|first3= P.|last4= Pikovsky|first4= A.|pmid=21873243|pmc=3182695|bibcode= 2011PNAS..108E.765E|doi-access= free}}</ref>
*In [[psychology]], random walks explain accurately the relation between the time needed to make a decision and the probability that a certain decision will be made.<ref>{{cite journal|pmid=9127583 |url=http://oz.ss.uci.edu/237/readings/EBRW_nosofsky_1997.pdf |archive-url=https://web.archive.org/web/20041210231937/http://oz.ss.uci.edu/237/readings/EBRW_nosofsky_1997.pdf |url-status=dead |archive-date=2004-12-10 |year=1997 |last1=Nosofsky |first1=R. M. |title=An exemplar-based random walk model of speeded classification |journal=Psychological Review |volume=104 |issue=2 |pages=266–300 |last2=Palmeri |first2=T. J. |doi=10.1037/0033-295x.104.2.266 }}</ref>
*Random walks can be used to sample from a state space which is unknown or very large, for example to pick a random page off the internet.{{citation needed|date=April 2012}} In [[computer science]], this method is known as [[Markov chain Monte Carlo|Markov Chain Monte Carlo]] (MCMC).

*In brain research, random walks and reinforced random walks are used to model cascades of neuron firing in the brain.
*In vision science, ocular drift tends to behave like a random walk. According to some authors, fixational eye movements in general are also well described by a random walk.
*In psychology, random walks explain accurately the relation between the time needed to make a decision and the probability that a certain decision will be made.
*Random walks can be used to sample from a state space which is unknown or very large, for example to pick a random page off the internet. In computer science, this method is known as Markov Chain Monte Carlo (MCMC).


* 在大脑研究中，随机游走和强化随机游走被用来模拟大脑中的神经元级联放电。在视觉科学中，眼球漂移就像随机游走。根据一些作者的观点，一般来说，注视的眼球运动也可以用随机游走来描述。
* 在心理学中，随机游走准确地解释了做决定所需的时间和做出某个决定的可能性之间的关系。
* 随机游走可用于从未知或非常大的状态空间采样，例如从互联网上随机挑选一个页面。在计算机科学中，这种方法被称为马尔科夫蒙特卡洛(MCMC)。

*In [[wireless networking]], a random walk is used to model node movement.{{citation needed|date=April 2012}}
*[[bacterial motility|Motile bacteria]] engage in a [[biased random walk (biochemistry)|biased random walks]].<ref>{{cite journal|last1=Codling|first1=E. A|last2=Plank|first2=M. J|last3=Benhamou|first3=S.|title=Random walk models in biology|journal=Journal of the Royal Society Interface|date=6 August 2008|volume=5|issue=25|pages=813–834|doi=10.1098/rsif.2008.0014|pmid=18426776|pmc=2504494}}</ref>
*In physics, random walks underlie the method of [[Fermi estimation]].{{citation needed|date=April 2012}}
*On the web, the Twitter website uses random walks to make suggestions of whom to follow<ref name="twitterwtf">Gupta, Pankaj et al. [http://dl.acm.org/citation.cfm?id=2488433 WTF: The who-to-follow system at Twitter], Proceedings of the 22nd international conference on World Wide Web</ref>
*[[Dave Bayer]] and [[Persi Diaconis]] have proven that 7 [[shuffle|riffle shuffles]] are enough to mix a pack of cards (see more details under [[shuffle]]). This result translates to a statement about random walk on the [[symmetric group]] which is what they prove, with a crucial use of the group structure via Fourier analysis.

*In wireless networking, a random walk is used to model node movement.
*Motile bacteria engage in a biased random walks.
*In physics, random walks underlie the method of Fermi estimation.
*On the web, the Twitter website uses random walks to make suggestions of whom to followGupta, Pankaj et al. WTF: The who-to-follow system at Twitter, Proceedings of the 22nd international conference on World Wide Web
*Dave Bayer and Persi Diaconis have proven that 7 riffle shuffles are enough to mix a pack of cards (see more details under shuffle). This result translates to a statement about random walk on the symmetric group which is what they prove, with a crucial use of the group structure via Fourier analysis.


* 在无线网络中，使用随机游走来模拟节点的移动。
* 活动细菌会有偏见地随机游走。
* 在物理学中，随机游动是费米估计的基础。
* 在网络上，Twitter 网站使用随机漫步的方式来建议谁应该关注 Gupta、 Pankaj 等人。卧槽: Twitter 上的 who-follow 系统，第22届万维网国际会议的会议记录
* 戴夫 · 拜耳和佩西 · 迪亚科尼斯已经证明，7个 riffle shuffle 就足以混合一副扑克牌(更多细节见 shuffle)。这个结果转化为一个关于对称群上随机游走的陈述，这是他们所证明的，通过傅立叶变换家族中的关系对群结构进行了重要的应用。

==Variants==

==Variants==

= = 变体 = =

A number of types of [[stochastic process]]es have been considered that are similar to the pure random walks but where the simple structure is allowed to be more generalized. The ''pure'' structure can be characterized by the steps being defined by [[independent and identically distributed random variables]]. Random walks can take place on a variety of spaces, such as [[Graph (discrete mathematics)|graphs]], the integers, the real line, the plane or higher-dimensional vector spaces, on [[Surface (differential geometry)|curved surfaces]] or higher-dimensional [[Riemannian manifold]]s, and on [[group theory|groups]]. It is also possible to define random walks which take their steps at random times, and in that case, the position {{mvar|X{{su|b=t}}}} has to be defined for all times {{math|''t'' &isin; [0, +∞)}}. Specific cases or limits of random walks include the [[Lévy flight]] and [[diffusion]] models such as [[Brownian motion]].

A number of types of stochastic processes have been considered that are similar to the pure random walks but where the simple structure is allowed to be more generalized. The pure structure can be characterized by the steps being defined by independent and identically distributed random variables. Random walks can take place on a variety of spaces, such as graphs, the integers, the real line, the plane or higher-dimensional vector spaces, on curved surfaces or higher-dimensional Riemannian manifolds, and on groups. It is also possible to define random walks which take their steps at random times, and in that case, the position has to be defined for all times . Specific cases or limits of random walks include the Lévy flight and diffusion models such as Brownian motion.

我们考虑了许多类型的随机过程，这些过程类似于纯随机游动，但是允许简单结构更加广义化。纯结构可以拥有属性独立同分布定义的步骤。随机游走可以发生在各种空间上，如图、整数、实线、平面或高维向量空间、曲面或高维黎曼流形以及群上。也可以定义随机行走，这些行走在随机的时间采取他们的步骤，在这种情况下，位置必须定义为所有的时间。随机游动的特殊情况或极限包括 Lévy 飞行和扩散模型，如布朗运动。

===On graphs===

===On graphs===

= = 关于图表 = = =

A random walk of length ''k'' on a possibly infinite [[Graph (discrete mathematics)|graph]] ''G'' with a root ''0'' is a stochastic process with random variables <math>X_1,X_2,\dots,X_k</math> such that <math>X_1=0</math> and
<math> {X_{i+1}} </math> is a vertex chosen uniformly at random from the neighbors of <math>X_i</math>.
Then the number <math>p_{v,w,k}(G)</math> is the probability that a random walk of length ''k'' starting at ''v'' ends at ''w''.
In particular, if ''G'' is a graph with root ''0'', <math>p_{0,0,2k}</math> is the probability that a <math>2k</math>-step random walk returns to ''0''.

A random walk of length k on a possibly infinite graph G with a root 0 is a stochastic process with random variables X_1,X_2,\dots,X_k such that X_1=0 and
{X_{i+1}} is a vertex chosen uniformly at random from the neighbors of X_i.
Then the number p_{v,w,k}(G) is the probability that a random walk of length k starting at v ends at w.
In particular, if G is a graph with root 0, p_{0,0,2k} is the probability that a 2k-step random walk returns to 0.

可能无穷图 G 上的长度 k 的随机游动是一个具有随机变量 x _ 1，x _ 2，点，x _ k 的随机过程，使得 x _ 1 = 0和{ x _ { i + 1}}是从 x _ i 的邻居中随机选择的一个一致的顶点。那么 p _ { v，w，k }(G)是从 v 开始的长度 k 的随机游动在 w 结束的概率。特别地，如果 G 是根为0的图，p _ {0,0,2 k }是2k 步随机游动返回0的概率。

Building on the analogy from the earlier section on higher dimensions, assume now that our city is no longer a perfect square grid. When our person reaches a certain junction, he picks between the variously available roads with equal probability. Thus, if the junction has seven exits the person will go to each one with probability one-seventh. This is a random walk on a graph. Will our person reach his home? It turns out that under rather mild conditions, the answer is still yes,{{Refn|It is interesting to remark that in a general graph the meeting of two independent random walkers does not always reduces to the problem of a single random walk returning to its starting point.}} but depending on the graph, the answer to the variant question 'Will two persons meet again?' may not be that they meet infinitely often almost surely.<ref>{{Cite journal|last1=Krishnapur|first1=Manjunath|last2=Peres|first2=Yuval|date=2004|title=Recurrent Graphs where Two Independent Random Walks Collide Finitely Often|url=https://projecteuclid.org/euclid.ecp/1464286688|journal=Electronic Communications in Probability|language=en|volume=9|pages=72–81|doi=10.1214/ECP.v9-1111|arxiv=math/0406487|bibcode=2004math......6487K|s2cid=16584737|issn=1083-589X}}</ref>

Building on the analogy from the earlier section on higher dimensions, assume now that our city is no longer a perfect square grid. When our person reaches a certain junction, he picks between the variously available roads with equal probability. Thus, if the junction has seven exits the person will go to each one with probability one-seventh. This is a random walk on a graph. Will our person reach his home? It turns out that under rather mild conditions, the answer is still yes, but depending on the graph, the answer to the variant question 'Will two persons meet again?' may not be that they meet infinitely often almost surely.

基于前面关于更高维度的类比，假设现在我们的城市不再是一个完美的方形网格。当我们的人到达一个特定的路口，他选择各种可用的道路之间的概率相等。因此，如果这个路口有七个出口，那么这个人去每个出口的概率是七分之一。这是图上的随机游走。我们的人会到达他的家吗？结果表明，在相当温和的条件下，答案仍然是肯定的，但是根据图表，对于另一个问题“两个人会再次相遇吗?”的答案是肯定的？'也许并不是说它们经常无限地相遇，几乎是肯定的。

An example of a case where the person will reach his home almost surely is when the lengths of all the blocks are between ''a'' and ''b'' (where ''a'' and ''b'' are any two finite positive numbers). Notice that we do not assume that the graph is [[planar graph|planar]], i.e. the city may contain tunnels and bridges. One way to prove this result is using the connection to [[electrical networks]]. Take a map of the city and place a one [[Ohm (unit)|ohm]] [[electrical resistance|resistor]] on every block. Now measure the "resistance between a point and infinity". In other words, choose some number ''R'' and take all the points in the electrical network with distance bigger than ''R'' from our point and wire them together. This is now a finite electrical network, and we may measure the resistance from our point to the wired points. Take ''R'' to infinity. The limit is called the ''resistance between a point and infinity''. It turns out that the following is true (an elementary proof can be found in the book by Doyle and Snell):

An example of a case where the person will reach his home almost surely is when the lengths of all the blocks are between a and b (where a and b are any two finite positive numbers). Notice that we do not assume that the graph is planar, i.e. the city may contain tunnels and bridges. One way to prove this result is using the connection to electrical networks. Take a map of the city and place a one ohm resistor on every block. Now measure the "resistance between a point and infinity". In other words, choose some number R and take all the points in the electrical network with distance bigger than R from our point and wire them together. This is now a finite electrical network, and we may measure the resistance from our point to the wired points. Take R to infinity. The limit is called the resistance between a point and infinity. It turns out that the following is true (an elementary proof can be found in the book by Doyle and Snell):

举一个例子，当一个人几乎肯定会到家的时候，所有积木的长度都在 a 和 b 之间(其中 a 和 b 是任意两个有限正数)。注意，我们不假设图是平面的，即。城市里可能有隧道和桥梁。证明这一结果的一种方法是利用与电网的连接。拿一张城市地图，在每个街区放置一个欧姆电阻。现在测量“一个点和无穷大之间的电阻”。换句话说，选择一个数字 R，取电网中距离大于 R 的所有点，将它们连接在一起。现在这是一个有限的电子网络，我们可以测量从我们的点到有线点的电阻。带 R 到无穷大。这个极限称为点与无穷大之间的阻力。事实证明以下是正确的(Doyle 和 Snell 的书中提供了一个基本的证明) :

'''Theorem''': ''a graph is transient if and only if the resistance between a point and infinity is finite. It is not important which point is chosen if the graph is connected.''

Theorem: a graph is transient if and only if the resistance between a point and infinity is finite. It is not important which point is chosen if the graph is connected.

定理: 图是瞬态的当且仅当点与无穷大之间的阻力是有限的。如果图是连通的，选择哪个点并不重要。

In other words, in a transient system, one only needs to overcome a finite resistance to get to infinity from any point. In a recurrent system, the resistance from any point to infinity is infinite.

In other words, in a transient system, one only needs to overcome a finite resistance to get to infinity from any point. In a recurrent system, the resistance from any point to infinity is infinite.

换句话说，在一个暂态系统中，人们只需要克服有限的阻力，就可以从任意点到达无穷远处。在一个循环系统中，从任意点到无穷远处的电阻是无穷大的。

This characterization of [[Markov chain#Transience and recurrence|transience and recurrence]] is very useful, and specifically it allows us to analyze the case of a city drawn in the plane with the distances bounded.

This characterization of transience and recurrence is very useful, and specifically it allows us to analyze the case of a city drawn in the plane with the distances bounded.

这种短暂性和递归性的角色塑造是非常有用的，特别是它使我们能够分析一个城市在平面上被画出来的情况，而且距离是有限的。

A random walk on a graph is a very special case of a [[Markov chain]]. Unlike a general Markov chain, random walk on a graph enjoys a property called ''time symmetry'' or ''reversibility''. Roughly speaking, this property, also called the principle of [[detailed balance]], means that the probabilities to traverse a given path in one direction or the other have a very simple connection between them (if the graph is [[Regular graph|regular]], they are just equal). This property has important consequences.

A random walk on a graph is a very special case of a Markov chain. Unlike a general Markov chain, random walk on a graph enjoys a property called time symmetry or reversibility. Roughly speaking, this property, also called the principle of detailed balance, means that the probabilities to traverse a given path in one direction or the other have a very simple connection between them (if the graph is regular, they are just equal). This property has important consequences.

图上的随机游动是马尔可夫链的一个非常特殊的情形。与一般的马尔可夫链不同，图上的随机游动具有时间对称性或可逆性。粗略地说，这个性质，也被称为细节平衡原理，意味着在一个方向或另一个方向上穿越给定路径的概率之间有一个非常简单的联系(如果图是正则的，它们就是相等的)。这种财产具有重要的后果。

Starting in the 1980s, much research has gone into connecting properties of the graph to random walks. In addition to the electrical network connection described above, there are important connections to [[isoperimetry|isoperimetric inequalities]], see more [[Isoperimetric dimension#Consequences of isoperimetry|here]], functional inequalities such as [[Sobolev inequality|Sobolev]] and [[Poincaré inequality|Poincaré]] inequalities and properties of solutions of [[Laplace's equation]]. A significant portion of this research was focused on [[Cayley graph]]s of [[finitely generated group]]s. In many cases these discrete results carry over to, or are derived from [[manifold]]s and [[Lie group]]s.

Starting in the 1980s, much research has gone into connecting properties of the graph to random walks. In addition to the electrical network connection described above, there are important connections to isoperimetric inequalities, see more here, functional inequalities such as Sobolev and Poincaré inequalities and properties of solutions of Laplace's equation. A significant portion of this research was focused on Cayley graphs of finitely generated groups. In many cases these discrete results carry over to, or are derived from manifolds and Lie groups.

从20世纪80年代开始，许多研究都致力于将图的性质与随机游动联系起来。除了上面描述的电网连接之外，还有与等周不等式的重要联系，参见这里的函数不等式，例如 Sobolev 和庞加莱不等式以及拉普拉斯方程解的性质。这项研究的很大一部分集中在有限生成群的 Cayley 图上。在许多情况下，这些离散的结果传递到流形和李群，或者从流形和李群导出。

In the context of [[random graph]]s, particularly that of the [[Erdős–Rényi model]], analytical results to some properties of random walkers have been obtained. These include the distribution of first<ref>{{Cite journal |arxiv = 1606.01560|doi = 10.1088/1751-8121/aa5af3|bibcode = 2017JPhA...50k5001T|title = The distribution of first hitting times of randomwalks on Erdős–Rényi networks|year = 2017|last1 = Tishby|first1 = Ido|last2 = Biham|first2 = Ofer|last3 = Katzav|first3 = Eytan|journal = Journal of Physics A: Mathematical and Theoretical|volume = 50|issue = 11|pages = 115001|s2cid = 118850609}}</ref> and last hitting times<ref>{{cite journal|doi=10.1088/1751-8113/49/28/285002|arxiv=1603.06613|title=The distribution of path lengths of self avoiding walks on Erdős–Rényi networks|journal=Journal of Physics A: Mathematical and Theoretical|volume=49|issue=28|pages=285002|year=2016|last1=Tishby|first1=Ido|last2=Biham|first2=Ofer|last3=Katzav|first3=Eytan|bibcode=2016JPhA...49B5002T|s2cid=119182848}}
</ref> of the walker, where the first hitting time is given by the first time the walker steps into a previously visited site of the graph, and the last hitting time corresponds the first time the walker cannot perform an additional move without revisiting a previously visited site.

In the context of random graphs, particularly that of the Erdős–Rényi model, analytical results to some properties of random walkers have been obtained. These include the distribution of first and last hitting times
of the walker, where the first hitting time is given by the first time the walker steps into a previously visited site of the graph, and the last hitting time corresponds the first time the walker cannot perform an additional move without revisiting a previously visited site.

在随机图的情况下，特别是 Erd s-Rényi 模型的情况下，得到了随机游动的一些性质的解析结果。其中包括步行者的第一次和最后一次打击时间的分布，其中第一次打击时间是由步行者第一次步入图中先前访问过的站点时给出的，而最后一次打击时间对应于步行者第一次不能在不重新访问先前访问过的站点的情况下执行额外的动作。

A good reference for random walk on graphs is the online book by [https://www.stat.berkeley.edu/users/aldous/RWG/book.html Aldous and Fill]. For groups see the book of Woess.
If the transition kernel <math>p(x,y)</math> is itself random (based on an environment <math>\omega</math>) then the random walk is called a "random walk in random environment". When the law of the random walk includes the randomness of <math>\omega</math>, the law is called the annealed law; on the other hand, if <math>\omega</math> is seen as fixed, the law is called a quenched law. See the book of Hughes, the book of Revesz, or the lecture notes of Zeitouni.

A good reference for random walk on graphs is the online book by Aldous and Fill. For groups see the book of Woess.
If the transition kernel p(x,y) is itself random (based on an environment \omega) then the random walk is called a "random walk in random environment". When the law of the random walk includes the randomness of \omega, the law is called the annealed law; on the other hand, if \omega is seen as fixed, the law is called a quenched law. See the book of Hughes, the book of Revesz, or the lecture notes of Zeitouni.

图上随机游走的一个很好的参考是 Aldous 和 Fill 的在线书。有关团体，请参阅 Woess 之书。如果转换核 p (x，y)本身是随机的(基于一个欧米茄环境) ，那么随机游动被称为“随机环境中的随机游动”。当随机游动定律包含 ω 的随机性时，该定律称为退火定律; 另一方面，如果 ω 被认为是固定的，该定律称为淬灭定律。参见休斯的书，列维斯的书，或者蔡图尼的课堂讲稿。

We can think about choosing every possible edge with the same probability as maximizing uncertainty (entropy) locally. We could also do it globally – in maximal entropy random walk (MERW) we want all paths to be equally probable, or in other words: for every two vertexes, each path of given length is equally probable.<ref>{{Cite journal |arxiv = 0810.4113|doi = 10.1103/PhysRevLett.102.160602|pmid = 19518691|bibcode = 2009PhRvL.102p0602B|title = Localization of the Maximal Entropy Random Walk|year = 2009|last1 = Burda|first1 = Z.|last2 = Duda|first2 = J.|last3 = Luck|first3 = J. M.|last4 = Waclaw|first4 = B.|journal = Physical Review Letters|volume = 102|issue = 16|pages = 160602|s2cid = 32134048}}</ref> This random walk has much stronger localization properties.

We can think about choosing every possible edge with the same probability as maximizing uncertainty (entropy) locally. We could also do it globally – in maximal entropy random walk (MERW) we want all paths to be equally probable, or in other words: for every two vertexes, each path of given length is equally probable. This random walk has much stronger localization properties.

我们可以考虑选择与局部不确定性(熵)最大化概率相同的每一个可能的边。我们也可以在全局范围内这样做-在最大熵随机游走(MERW)中，我们希望所有的路径都是等概率的，或者换句话说: 对于每两个顶点，给定长度的每条路径都是等概率的。这种随机游动具有更强的局部化性质。

===Self-interacting random walks===
There are a number of interesting models of random paths in which each step depends on the past in a complicated manner. All are more complex for solving analytically than the usual random walk; still, the behavior of any model of a random walker is obtainable using computers. Examples include:
* The [[self-avoiding walk]].<ref>Madras, Neal and Slade, Gordon (1996) ''The Self-Avoiding Walk'', Birkhäuser Boston. {{isbn|0-8176-3891-1}}.</ref>
The self-avoiding walk of length ''n'' on <math>\mathbb{Z}^d</math> is the random ''n''-step path which starts at the origin, makes transitions only between adjacent sites in <math>\mathbb{Z}^d</math>, never revisit a site, and is chosen uniformly among all such paths. In two dimensions, due to self-trapping, a typical self-avoiding walk is very short,<ref>{{cite journal|author1=Hemmer, S. |author2=Hemmer, P. C. |title=An average self-avoiding random walk on the square lattice lasts 71 steps|journal=J. Chem. Phys.| volume=81|issue=1 | pages=584–585| year=1984| doi=10.1063/1.447349|bibcode = 1984JChPh..81..584H }}</ref> while in higher dimension it grows beyond all bounds.
This model has often been used in [[polymer physics]] (since the 1960s).
* The [[loop-erased random walk]].<ref>Lawler, Gregory (1996). ''Intersection of random walks'', Birkhäuser Boston. {{isbn|0-8176-3892-X}}.</ref><ref>Lawler, Gregory ''Conformally Invariant Processes in the Plane'', [http://www.math.cornell.edu/~lawler/book.ps book.ps].</ref>
* The [[reinforced random walk]].<ref>{{cite journal|author=Pemantle, Robin |year=2007|url=http://www.emis.de/journals/PS/images/getdoc9b04.pdf?id=432&article=94&mode=pdf |title=A survey of random processes with reinforcement|journal= Probability Surveys|volume =4 |pages=1–79|arxiv=math/0610076|doi=10.1214/07-PS094|s2cid=11964062}}</ref>
* The [[exploration process]].{{citation needed|date=April 2012}}
* The [[multiagent random walk]].<ref>Alamgir, M and von Luxburg, U (2010). [http://www.kyb.mpg.de/fileadmin/user_upload/files/publications/attachments/AlamgirLuxburg2010_%5b0%5d.pdf "Multi-agent random walks for local clustering on graphs"], ''IEEE 10th International Conference on Data Mining (ICDM)'', pp. 18–27.</ref>
<!-- All these deserve pages of their own. Currently I only feel competent to write the second (and maybe the last)-->

There are a number of interesting models of random paths in which each step depends on the past in a complicated manner. All are more complex for solving analytically than the usual random walk; still, the behavior of any model of a random walker is obtainable using computers. Examples include:
* The self-avoiding walk.Madras, Neal and Slade, Gordon (1996) The Self-Avoiding Walk, Birkhäuser Boston. .
The self-avoiding walk of length n on \mathbb{Z}^d is the random n-step path which starts at the origin, makes transitions only between adjacent sites in \mathbb{Z}^d, never revisit a site, and is chosen uniformly among all such paths. In two dimensions, due to self-trapping, a typical self-avoiding walk is very short, while in higher dimension it grows beyond all bounds.
This model has often been used in polymer physics (since the 1960s).
* The loop-erased random walk.Lawler, Gregory (1996). Intersection of random walks, Birkhäuser Boston. .Lawler, Gregory Conformally Invariant Processes in the Plane, book.ps.
* The reinforced random walk.
* The exploration process.
* The multiagent random walk.Alamgir, M and von Luxburg, U (2010). "Multi-agent random walks for local clustering on graphs", IEEE 10th International Conference on Data Mining (ICDM), pp. 18–27.


有许多有趣的随机路径模型，其中每一步都以一种复杂的方式依赖于过去。所有这些都比通常的随机游走的解析解要复杂得多; 尽管如此，任何随机游走模型的行为都可以用计算机获得。例子包括:
* 自我回避的步行，马德拉斯，尼尔和斯莱德，戈登(1996)自我回避的步行，波士顿伯克豪泽。.Mathbb { Z } ^ d 上的长度为 n 的自回避行走是从原点开始的随机 n 步路径，只在 mathbb { Z } ^ d 上的相邻点之间进行过渡，从不再访问一个点，并且在所有这样的路径中均匀地选择。在二维空间中，由于自陷效应，典型的自回避行走时间很短，而在高维空间中，自回避行走时间超越了所有界限。这个模型经常被用于聚合物物理学(自1960年代以来)。
* 循环擦除的随机游走，劳勒，格雷戈里(1996)。波士顿 Birkhäuser 的随机路口。。劳勒，格雷戈里共形不变过程在平面，book.ps。加强版的随机漫步
* 。探索的过程
* 。
* 多人随机游走。阿拉姆吉尔，M 和冯卢克斯堡，U (2010)。“用于图上局部聚类的多代理随机游动”，IEEE 第10届国际数据挖掘会议(ICDM) ，pp。18–27.

===Biased random walks on graphs===
{{main|Biased random walk on a graph}}

=== Maximal entropy random walk ===
{{main|Maximal entropy random walk}}
Random walk chosen to maximize [[entropy rate]], has much stronger localization properties.


Random walk chosen to maximize entropy rate, has much stronger localization properties.

最大熵随机游动 = = = 选择最大熵率的随机游动，具有更强的局部化特性。

===Correlated random walks===

===Correlated random walks===

= = 相关随机游走 = = =

Random walks where the direction of movement at one time is [[Correlation and dependence|correlated]] with the direction of movement at the next time. It is used to model animal movements.<ref>{{cite journal |year=1988 |title=Spatial analysis of animals' movements using a correlated random walk model |journal=Journal of Theoretical Biology |volume=131 |pages=419–433 |doi= 10.1016/S0022-5193(88)80038-9|issue=4 |last1=Bovet |first1=Pierre |last2=Benhamou |first2=Simon |bibcode=1988JThBi.131..419B }}</ref><ref>{{cite journal |year=1983 |title=Analyzing insect movement as a correlated random walk |journal=Oecologia |volume=56 |pages=234–238 |doi= 10.1007/BF00379695|pmid=28310199 |issue=2–3 |last1=Kareiva |first1=P.M. |last2=Shigesada |first2=N. |bibcode=1983Oecol..56..234K |s2cid=20329045 }}</ref>

Random walks where the direction of movement at one time is correlated with the direction of movement at the next time. It is used to model animal movements.

随机行走，一次的运动方向与下一次的运动方向相关。它被用来模拟动物的运动。

==See also==
* [[Branching random walk]]
* [[Brownian motion]]
* [[Law of the iterated logarithm]]
* [[Lévy flight]]
* [[Lévy flight foraging hypothesis]]
* [[Loop-erased random walk]]
* [[Maximal entropy random walk]]
* [[Self-avoiding walk]]
* [[Unit root#Unit root hypothesis|Unit root]]

* Branching random walk
* Brownian motion
* Law of the iterated logarithm
* Lévy flight
* Lévy flight foraging hypothesis
* Loop-erased random walk
* Maximal entropy random walk
* Self-avoiding walk
* Unit root

= = 参见同样 = =
* 分支随机行走
* 布朗运动
* 重对数律
* 雷维飞行
* 雷维飞行觅食假说
* 环擦除随机行走
* 最大熵随机行走
* 自我回避行走
* 单位根

== References ==
{{Reflist}}

== Bibliography ==

== Bibliography ==

= = 参考书目 = =

* {{cite book |last1=Aldous |first1=David |author-link1=David Aldous |last2=Fill |first2=James Allen |date=2002 |title=Reversible Markov Chains and Random Walks on Graphs |url=https://www.stat.berkeley.edu/~aldous/RWG/book.html |url-status=live |archive-url=https://web.archive.org/web/20190227224749/https://www.stat.berkeley.edu/~aldous/RWG/book.html |archive-date=27 February 2019}}
* {{Cite book |last1=Doyle |first1=Peter G. |last2=Snell |first2=J. Laurie |title=Random Walks and Electric Networks |arxiv=math.PR/0001057 |publisher=[[Mathematical Association of America]] |series=Carus Mathematical Monographs |isbn=978-0-88385-024-4 |mr=920811 |year=1984 |volume=22}}
* [[William Feller|Feller, William]] (1968), ''An Introduction to Probability Theory and its Applications'' (Volume 1). {{isbn|0-471-25708-7}}
* Hughes, Barry D. (1996), ''Random Walks and Random Environments'', Oxford University Press. {{isbn|0-19-853789-1}}
* Norris, James (1998), ''Markov Chains'', Cambridge University Press. {{isbn|0-521-63396-6}}
* <!---apparently broken---[http://www.springerlink.com/(brnqxc55mlvpxs452ufzp555)/app/home/contribution.asp?referrer=parent&backto=issue,13,13;journal,798,1099;linkingpublicationresults,1:100442,1 Springer]---> Pólya G.(1921), [http://gdz.sub.uni-goettingen.de/index.php?id=11&PPN=PPN235181684_0084&DMDID=DMDLOG_0016&L=1 "Über eine Aufgabe der Wahrscheinlichkeitsrechnung betreffend die Irrfahrt im Strassennetz"], ''[[Mathematische Annalen]]'', 84(1–2):149–160, March 1921.
* Révész, Pal (2013), ''Random Walk in Random and Non-random Environments (Third Edition)'', World Scientific Pub Co. {{isbn|978-981-4447-50-8}}
* {{cite book | last=Sunada | first=Toshikazu | author-link=Toshikazu Sunada | date=2012 | title=Topological Crystallography: With a View Towards Discrete Geometric Analysis | isbn=978-4-431-54177-6 | series=Surveys and Tutorials in the Applied Mathematical Sciences | volume=6 | publisher=Springer }}
* Weiss G. ''Aspects and Applications of the Random Walk'', North-Holland, 1994.
* Woess, Wolfgang (2000), ''Random Walks on Infinite Graphs and Groups'', Cambridge tracts in mathematics 138, Cambridge University Press. {{isbn|0-521-55292-3}}

*
*
* Feller, William (1968), An Introduction to Probability Theory and its Applications (Volume 1).
* Hughes, Barry D. (1996), Random Walks and Random Environments, Oxford University Press.
* Norris, James (1998), Markov Chains, Cambridge University Press.
* Pólya G.(1921), "Über eine Aufgabe der Wahrscheinlichkeitsrechnung betreffend die Irrfahrt im Strassennetz", Mathematische Annalen, 84(1–2):149–160, March 1921.
* Révész, Pal (2013), Random Walk in Random and Non-random Environments (Third Edition), World Scientific Pub Co.
*
* Weiss G. Aspects and Applications of the Random Walk, North-Holland, 1994.
* Woess, Wolfgang (2000), Random Walks on Infinite Graphs and Groups, Cambridge tracts in mathematics 138, Cambridge University Press.


*
*
* 费勒，威廉(1968) ，介绍概率论及其应用(卷1)。
* Hughes，Barry D. (1996) ，《随机游走与随机环境》 ，牛津大学出版社。
* 诺里斯，詹姆斯(1998) ，马尔科夫链，剑桥大学出版社。
* Pólya G.(1921), "Über eine Aufgabe der Wahrscheinlichkeitsrechnung betreffend die Irrfahrt im Strassennetz", Mathematische Annalen, 84(1–2):149–160, March 1921.
* Révész，Pal (2013) ，《随机和非随机环境中的随机漫步》(第三版) ，World Scientific Pub Co。
*
* 《随机游走的方面和应用》 ，北荷兰，1994年。
* Woess，Wolfgang (2000) ，《无穷图和群的随机游走》 ，剑桥数学丛书138，剑桥大学出版社。

==External links==
* [http://mathworld.wolfram.com/PolyasRandomWalkConstants.html Pólya's Random Walk Constants]
* [http://vlab.infotech.monash.edu.au/simulations/swarms/random-walk/ Random walk in Java Applet]
* [http://www.kisc.meiji.ac.jp/~tz14040/quantumwalk/english/ Quantum random walk]
* [http://fr.mathworks.com/matlabcentral/fileexchange/56869-random-walk-estimator Gaussian random walk estimator]
*[http://demonstrations.wolfram.com/ElectronConductanceModelsUsingMaximalEntropyRandomWalks/ Electron Conductance Models Using Maximal Entropy Random Walks] Wolfram Demonstrations Project

* Pólya's Random Walk Constants
* Random walk in Java Applet
* Quantum random walk
* Gaussian random walk estimator
*Electron Conductance Models Using Maximal Entropy Random Walks Wolfram Demonstrations Project

= = 外部链接 = =
* Pólya 的随机行走常数
* Java 小程序中的随机行走
* 量子随机行走
* 高斯随机行走估计
* 使用最大熵随机行走 Wolfram 演示项目的电子电导模型

{{Stochastic processes}}

{{Authority control}}

{{DEFAULTSORT:Random Walk}}
[[Category:Stochastic processes]]
[[Category:Variants of random walks]]


Category:Stochastic processes
Category:Variants of random walks

类别: 随机过程类别: 随机游动的变体

<noinclude>

<small>This page was moved from [[wikipedia:en:Random walk]]. Its edit history can be viewed at [[随机游走/edithistory]]</small></noinclude>

[[Category:待整理页面]]
Moonscar
1,564

个编辑

取自“https://wiki.swarma.org/index.php/特殊:移动版差异/32790”

导航菜单