用户:Kizzard99/沙盒

高斯随机游走

如果随机游走的步长根据正态分布变化，那么它可以用作真实世界时间序列数据的模型，诸如金融市场。用于建模期权价格的布莱克-舒尔斯公式就使用了高斯随机游走作为基础假设。

在这里，每一步的步长是累计正态分布的反函数$\Phi ^{-1}(z,\mu ,\sigma )$，0 ≤ z ≤ 1是一个均匀分布的随机数，μ和σ分别是正态分布的均值和标准差。如果μ非零，则随机游走将随线性趋势变化。如果v_s是随机游走的起始值，则n步之后的期望值将是v_s + nμ。对于μ等于零的特殊情况，在n步后，平移距离的概率分布为N(0, nσ²)，其中N() 是正态分布的符号，n是步数，σ同上。

证明：高斯随机游走可以被视为一系列独立同分布的随机变量X_i的总和，每一个变量来自累积正态分布的反函数，它的均值等于零，而σ和原始累积正态分布反函数的σ相同

Z = $\sum _{i=0}^{n}{X_{i}}$,

但两个独立的正态分布随机变量之和的分布，Z = X + Y，由下式给出

${\mathcal {N}}$(μ_X + μ_Y, σ²_X + σ²_Y) (see here).

在这个例子中，μ_X = μ_Y = 0 and σ²_X = σ²_Y = σ²给出

${\mathcal {N}}$(0, 2σ²)

通过归纳，在步数为n时

Z ~ ${\mathcal {N}}$(0, nσ²).

对均值为零，方差为有限数的任何分布，若随机游走的分布为这样的分布，那么n'步后的均方根平移距离为

${\sqrt {E|S_{n}^{2}|}}=\sigma {\sqrt {n}}.$

但对于高斯随机游走，这只是“n”步后平移距离分布的标准偏差。因此，在μ等于零的前提下，由于均方根平移距离是一个标准差的距离，所以n步后的均方根平移距离落在± σ${\sqrt {n}}$之间的概率为68.27％。同样，n步后的平移距离有50％的可能性落在± 0.6745σ${\sqrt {n}}$之间。

异常扩散

在诸如多孔介质和分形等无序系统中，$\sigma ^{2}$可能与$t$不成比例，而是与$t^{2/d_{w}}$成比例。 指数$d_{w}$称为异常扩散指数，它可能大于或小于2。。异常扩散也可以写为σ_r² ~ Dt^α，其中α是异常参数。 随机环境中的一些扩散甚至与时间的对数的幂成比例，参见西奈漫步（Sinai's walk）或布罗克斯扩散（Brox diffusion）。

不同站点的数量

在二维平面及三维空间上的点阵和分形上，对于单个随机游走者访问的不同站点的数量$S(t)$已经有了广氾的研究。该量可用于分析动力学陷阱和动力学反应的问题。它还与振动密度有关，扩散反应的过程， and spread of populations in ecology. 最近，对在d维欧几里得点阵上，$N$个随机游走者访问的不同站点的问题，已经有了扩展的研究。但N个步行者访问的不同站点的数量，不仅仅与每个步行者访问的不同站点的数量有关。

信息速率

对于一个高斯随机漫步，对应其平方差距离的信息速率，即其二次速率失真函数，由以下参数函数给出

$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 }$的条件下将其恢复。 另一方面，对于任何$\varepsilon >0$，存在一个足够大的$N\in \mathbb {N}$，以及一个元素数量不超过$2^{NR(D_{\theta })}$的二进制代码，使得从这段代码中恢复${\{Z_{n}\}_{n=1}^{N}}$时的预期均方误差最多为$D_{\theta }-\varepsilon$。

应用

伦敦的量子云雕像，由安东尼·戈姆利所塑，它的设计是由电脑用随机游走算法生成的。

如上所述，人们已经尝试将相当大范围的自然现象通过某种随机漫步来模拟，特别是在物理学，化学，以及材料科学，生物以及许多其他领域。以下是随机游走的一些具体的应用：

• 在金融经济学中，随机游走假设被用于模拟股票价格，等等。实证研究表明，这种理论模型与现实并不完全相符，特别是在短期和长期相关性方面。参看股价。
• 在群体遗传学中，随机游走描述了遗传漂变的统计特性。
• 在物理学中，随机游走是许多自然现象的简化模型，例如布朗运动，扩散作用，例如分子在液体和气体中的随机运动。参见扩散限制聚集。随机游走和一些自相互作用的行走也见于量子场理论。
• 在数学生态学中，随机游走用于模拟动物个体的运动，来从实践上支持生物扩散过程。它有时也用于模拟种群动态。
• 在高分子物理学中，随机游走描述了理想的链。这是研究聚合物模型最简单的一种。[32]
• 在其他数学领域，随机游走可对普拉斯方程求解，估算谐波测量，以及分析和组合学中的各种构造。
• 在计算机科学中，随机游走用于估计Web的大小。在2006年的万维网会议上，Bar-Yossef等人发表了他们的研究结果和算法。
• 在图像分割中，随机游走用于确定与每个像素相关联的标签（即“对象”或“背景”）。[33]该算法通常被称为随机游走分段算法。

• 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 the World Wide Web conference-2006, Bar-Yossef et al. published their findings and algorithms for the same.
• 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.

In all these cases , random walk is often substituted for Brownian motion .

• 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 or, for research of working conditions, a random worker in a given country.

• When this last approach is used in computer science it is known as Markov chain Monte Carlo or MCMC for short. Often, sampling from some complicated state space also allows one to get a probabilistic estimate of the space's size. The estimate of the permanent of a large matrix of zeros and ones was the first major problem tackled using this approach.

• Random walks have also been used to sample massive online graphs such as online social networks.
• In wireless networking, a random walk is used to model node movement.
• Motile bacteria engage in a biased random walk.
• Random walks are used to model gambling.
• In physics, random walks underlie the method of Fermi estimation.
• On the web, the Twitter website uses random walks to make suggestions of who to follow
• 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.

变种

许多随机过程都与单纯的随机漫步十分接近，只不过是在其结构上进行拓展。在这种单纯结构中，每一步都是独立同分布的随机变量。

On graphs

设G为有限或无限图。G上的随机漫步定义如下：一个从0开始，长度为k的随机过程，其随机变量为 $X_{1},X_{2},\dots ,X_{k}$ ，使得 $X_{1}=0$， ${X_{i+1}}$是随机选出的与$X_{i}$相邻的一个点，每一个相邻点有相同的概率被选中。 对任意随机游走，设$p_{v,w,k}(G)$为它长度为k，以v为起点，w为终点的可能性。 这样，若图G以顶点0为根，那么$p_{0,0,2k}$是$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. For example, if the lengths of all the blocks are between a and b (where a and b are any two finite positive numbers), then the person will, almost surely, reach his home. 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):

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.

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, 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 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.

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.

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.

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.

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.

The self-avoiding walk of length n on Z^d is the random n-step path which starts at the origin, makes transitions only between adjacent sites in 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.
• The reinforced random walk.
• The exploration process.
• The multiagent random walk.

Long-range correlated walks

Long-range correlated time series are found in many biological, climatological and economic systems.

• Heartbeat records
• Non-coding DNA sequences
• Volatility time series of stocks
• Temperature records around the globe

Biased random walks on graphs

主条目：Biased random walk on a graph

Maximal entropy random walk

主条目：Maximal entropy random walk

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

Correlated random walks

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