User: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