使用者: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