隨機遊走檢視原始碼討論檢視歷史

隨機遊走（random walk）也稱隨機漫步，隨機行走等是指基於過去的表現，無法預測將來的發展步驟和方向。核心概念是指任何無規則行走者所帶的守恆量都各自對應着一個擴散運輸定律，接近於布朗運動，是布朗運動理想的數學狀態，現階段主要應用於互聯網鏈接分析及金融股票市場中。

隨機遊走圖片來源百度網原圖鏈接

中文名:隨機遊走

外文名:random walk

別 名:隨機行走

核 心:一個擴散運輸定律

定 義:即隨機遊走，

概念接近於布朗運動

應 用:計算機、金融

釋義

英文：random walk

定義：隨機遊走，概念接近於布朗運動，是布朗運動的理想數學狀態。

核心概念：任何無規則行走者所帶的守恆量都各自對應着一個擴散運輸定律。

定律介紹

無規則行走

無規則行走在任意尺度上都具有相似結構。例如一個在二維（d=2）格子上遊動，每一定時間以相同概率移動到其相鄰位置，其軌跡即二維隨機軌跡，同樣可以擴展到三維。舉個例子，你取2個硬幣一個1分，一個5分。你每五秒，將2個硬幣擲一次，1分硬幣用於左右移動標記，5分硬幣用於前後移動標記，繪出路徑就是你的二維無規則行走。假如你走了1000步那麼你回到起點的方式M0有多少種？那麼麼必須正反面各500次。即，對一個特定投幣序列將投出正面的序號列出清單，清單包括500個不同的整數這個量為：1000！/500！，而任意兩張清單只在元素存在換序的差異，則實際上並無區別所以必須除以可能的置換數500!,M0=1000！/（500×500！），「！」表示階乘。回到原點的概率P0=M0/M，這個概率滿足二項分布。

對於所有M種可能可以用斯特林公式進行計算，通過計算我們知道回到起點的概率很低。

隨機遊走圖片來源百度網原圖鏈接

要想找出第1000步後你走了多遠，你可以列出1000次投幣的結果序列然後對所有（x1000）的2次方求平均，得到1000步後的均方位置；這顯然太複雜，好在還有另外的方法。我們可以將所有2的N次方種可能行走一一配對，每一配對由相同的x（N-1）；{（N-1）為x的下腳標}的兩個可能性相等的行走組成，只是最後一步不同。N步隨機性走的均方位移比N-1步大a的2次方，後者又比N-2步大a的2次方，均方位移=Na的2次方。a為格子間隔，每一個格子點上遊動的可能方向有2d個（d是格子維數）單位時間內遊動的方差為D=a2/（2d）t，D為擴散係數（一些參考書中也用字母K表示，

===a後面的2為次方，後面凡數字在字母後面都表示指數)===。 對於一維無規則行走的均方位移隨時間線性增加2Kt，擴散常數D=a2/（2Δt）。這個邏輯可以推廣到二維和三維。

也許行走若干個步後他會回到出發點，但這樣的概率非常小。他離開酒吧的距離滿足擴散定律。

（a）二維無規則行走；

隨機遊走圖片來源百度網原圖鏈接

（b）當步驟更多，步幅更低時二維無規則行走；

（c）三維無規則行走。

擴散定律

擴散以一個初始分布釋放大量的無規則行走，觀察他們的密度，就會得到分布函數。

1855年法國生理學家Fick提出了描述擴散規律的基本公式—菲克定律，在一維（如x方向擴散的）粒子流密度（即單位時間內在單位截面上擴散的粒子流）JN與粒子數密度梯度dc/dx成正比。擴散通量J=-D×（dc/dx），稱為菲克定律又稱擴散第一定律。進一步消掉J，找出濃度隨時間的變化關係dc/dt=D（d2c/dx2），稱為菲克第二定律；在高等教材中可以寫成偏導的形式d換成ә。

任何單次步驟不會遵從擴散定律，但只要等待足夠長的時間和步驟，便可精確預測無規則行走。布朗運動就是無規則行走這一現象的宏觀觀察。通過擴散定律我們將布朗運動的微觀參數（步長a和間隔時間Δt）與宏觀實驗可觀測量（擴散常數D）建立了聯繫。然而一個方程無法解出兩個未知量，測量K不足以得到a和Δt。這意味着還需要其他能夠說明摩擦與擴散定量聯繫的公式。

擴散定律是跨學科的普適定律

對無規則行走的數學處理使用了過於簡化的假設，擴散定律是普適的，只要給定獨立隨機行走的某種分布，它就不依賴於具體的模型。漲落是隨機的、混沌的，無規則行走的結果就是擴散，這包括物質擴散、動量擴散、熱量擴散等。這也意味着結晶學、天文學、生物學、氣象學、流體力學、經濟學都將用到擴散定律。擴散定律是普適的，在這裡我們作為一個結論而接受下來，具體的一系列數學證明過程給予捨棄。感興趣的朋友可以參見任何一本物理化學教材或分形教材。

擴散定律與守恆量

擴散是一個隨機漲落的過程，在本科一年級的物理課程已經提及一個落體最終會達到取決於摩擦的「末速度」。以懸浮顆粒來考慮摩擦，顆粒雖然受隨機碰撞，仍獲得了一個淨漂移速度。v=f/ζ，ζ=2m/Δt，其中ζ是黏性摩擦係數，與擴散係數一樣可以實驗測量。摩擦源於物理實體與周圍熱致擾動的流體隨機碰撞。每一種顆粒當置於不同的溶劑中時都會有相應特徵D（擴散係數）和ζ。球體的黏性摩擦係數與尺寸間存在簡單關係，ζ=6πηR斯托克斯（stokes）公式；R是顆粒半徑，η是常數稱為流體黏度（水的黏度為10-3kg/ms）。

由於有效步長a和Δt無法觀察，要想證實擴散與粘滯僅僅是熱運動的兩個方面，我們還需要第三個關係。愛因斯坦注意到a和Δt的關係，按照推導理想氣體定律的思路：（a/Δt）2=kBT/m，聯合起來就構成愛因斯坦第一擴散公式：ζD=kBT。越小的顆粒受到摩擦阻力越小，但擴散係數會更大，更容易擴散。ζD的乘積提供了一個可證偽的預言來檢驗「熱即分子的無規則運動」；這個預言提出不久就立刻被佩蘭（Jeans Perrin）和其他人的實驗所證實。任何無規則行走攜帶的守恆量都各自對應一個擴散定律。

理想狀態

無規則行走只是布朗運動的理想狀態。

在很多系統都存在不同類型的無規則行走，他們都具有相似結構。單個的隨機事件我們不可預測，但隨機大量的群體行為，卻是精確可知的，這就是概率世界的魅力，在偶然中隱含着必然。隨機性造成了低尺度下的差異性，但在高尺度下又表現為共同的特徵的相似性。按照概率的觀點「宇宙即是所有隨機事件概率的總和」。

相關研究

橢球體布朗運動相關研究

雖然無規則行走導致的擴散滿足以上的方程並有普適性，但假如這樣的「無規則行走」某個方向，並不是完全隨機呢？以前面提到的投硬幣為例子，一個1分，一個5分，其中1分硬幣破損使得正反面概率不相等，並且隨機若干步後，將1分和5分硬幣所代表的方向對調；那麼二維的無規則行走路徑必然發生改變。

當年愛因斯坦的論文是探討球形顆粒的布朗運動，我們知道球形顆粒的旋轉並不影響他的平移，旋轉的非球形例子卻會影響它的平移。實際中，大量布朗運動的顆粒都是非球形的，所以更多的模型不得不考慮隨機轉動問題。其實即使對球形顆粒在黏性流體中，也要考慮隨機轉動產生的轉動摩擦係數對擴散的影響。

隨機遊走圖片來源百度網原圖鏈接

賓夕法尼亞大學的網站報道，研究人員用數字視屏顯微鏡觀察水中懸浮橢球體的隨機旋轉和移動。球形顆粒擴散分布將隨時間逐漸變寬，為高斯型濃度分布；而橢球顆粒不滿足高斯分布。隨着布朗運動的深入研究，越來越多的實驗表明布朗運動顆粒的行為與愛因斯坦一個世紀前的假設不同。

2005年10月的物理評論快報，提到現在實驗室可以跟蹤布朗運動顆粒的測量精度達到微秒和納米的尺度。科學家們也發現活細胞的許多基本過程由布朗運動所驅動。試驗結果描述布朗運動的方程式偏離標準理論的，實際的布朗運動要比理想化的無規則行走要複雜。

標準的無規則行走，色彩標記顯示出橢球的耦合方向和位移，並清楚的表明橢球的擴散其長軸比其短軸擴散更快。 觀點的缺憾

布朗運動是分形的典型例子，理想狀態下的布朗運動是高斯正態分布，當然更多的布朗運動研究細節我們不做探討。任何事物都不是孤立的，都是相互作用、相互聯繫的。用還原論觀點將系統一個個隔離是對事物的理想化，是在一定程度上精確定量描述系統，當然這也是認識事物必經的步驟，但是有缺陷的。

哥德爾不完備定理，以及認識主體對客體的反映永遠存在這不完備性。我觀贊同哥本哈根學派的主張「自然科學不是自然界本身，而是人和自然界間關係的一部分，因而依賴人」。無論用還原論還是整體論都是用抽象去闡明物質的特性，這些抽象在任何時候僅僅是近似地、有條件的把握了物質的本質，不是世界的全部。布朗運動研究的歷史，具有典型性，有點像整個科學研究史的縮影。人對事物的認識總是漸進的，不斷深入的，隨着認識深入會發現各種模型都是理想化的條件。這種認識永遠無法走向事物的絕對認識，因為孤立的事物是不存在的，所有的系統都是宇宙整體的一部分。

其他類型

與P2P

許多系統都有類似無規則行走的例子。例如：P2P（Peer-to-Peer，對等計算，簡稱P2P）搜索中Random Walk搜索方法在隨機漫步中，請求者發出K個查詢請求給隨機挑選的K個相鄰節點。然後每個查詢信息在以後的漫步過程中直接與請求者保持聯繫，詢問是否還要繼續下一步。如果請求者同意繼續漫步，則又開始隨機選擇下一步漫步的節點，否則中止搜索又開始隨機選擇下一步漫步的節點，否則中止搜索又開始隨機選擇下一步漫步的節點，否則中止搜索。

與高分子

高分子的形狀類似於無規則行走，把高分子想象成由N個單元排成的長串。每個單元都由一個完全柔軟的鉸鏈與下一個單元相連，就像一串回形針。熱平衡時，這些鉸鏈全部處於隨機選取的角度，高分子每一時刻的形狀都會不同，每一時刻都是一個無規則行走。如果合成的高分子由不同數量的單元組成，線團尺寸的增加正比於其摩爾質量的平方根。 如果單元間存在着強烈的相互吸引力，高分子將不再採取無規則行走構象而是密堆成一個球體，例如血清球蛋白。可以通過比較高分子的體積和假設所有密堆占的最小體積，將高分子分為「緊密型」和「舒展型」。即使高分子不坍縮為團，單體也並非真正處於任何位置，兩個單體不可能占據空間同一點，這是自迴避現象。這樣標度指數（線團尺寸的增加正比於其摩爾質量的指數）就由0.5變為其他值，所以這個值往往略大一點。不管精確值是什麼，高分子運動的複雜性可湧現出簡單的標度關係。

梅爾（B.Maier）和雷德勒爾（J.Radler）首先構建了一個帶正電的表面並讓他吸附帶負電荷的單鏈DNA然後對被吸附的DNA分子不斷變化的構象進行連續快照（DNA帶有熒光染色）。DNA分子可以是自交叉的但每次出現這種情況都是一個消耗結合能的過程，在交叉點處那條帶負電的鏈並不與帶正電的表面接觸，而是被強迫與另一條帶負電的鏈接觸。因此我們可以認為線團尺寸遵從二維無規自迴避行走標度律，標度指數為0.75。一旦結合在平面上，DNA鏈就開始各種蜿蜒構象間的變化，梅爾和雷德勒爾計算出了高分子鏈的迴轉半徑與首末端距離的均方有關，標度指數0.79接近於理論的0.75。

與金融市場

股票市場由無數的亞單元即投資者構成。每個投資者為個人經驗、感情和不完全信息所左右，其決策立足於其他投資的的決策以及匯總的信息中的隨機事件，在經濟學上研究這樣的決策叫做博弈論（game theory）。當然單個投資者的行為不可預測，但長期來看，股票價格作某種帶漂移的無規則行走。驅動這個行走的包括投資者的突發奇想、自然災難、公司倒閉、以及其他不可預知的新聞事件。

為什麼行走會是隨機？假如一個分析員發現12月末股價會上揚，到1月初在下跌，一旦這種規律被市場參與者得知自然人們會選擇這段時間內拋出股票，這一行為導致了股票下跌，消除了這種效應的可能。股票的公平原則即要求公開信息資源，使得一個投資者沒有更多戰勝其他投資者的有用信息。在信息完全公開的情況下長時間的股票曲線應該近似於一維無規則行走。

任何無規則行走者所帶的守恆量都各自對應着一個擴散運輸定律。比如粒子數守恆對應物質擴散，能量守恆對應熱傳導定律，熱傳導定律可以看成另一條菲克型定律。

模型

互聯網用戶在上網時，往往有類似的網絡行為：輸入網址，瀏覽頁面，然後順着頁面的鏈接不斷打開新的網頁。隨機遊走模型就是針對瀏覽網頁的用戶行為建立的抽象概念模型。之所以要建立這個抽象概念模型，是因為包括PageRank算法在內的很多鏈接分析算法都是建立在隨機遊走模型基礎上的。

在最初階段，用戶打開瀏覽器瀏覽第1個網頁，假設我們有一個虛擬時鐘用來計時，此時可以設定時間為1，用戶在看完網頁後，對網頁內某個鏈接指向的頁面感興趣，於是點擊該鏈接，進入第2個頁面，此時虛擬時鐘再次計時，時鐘走向字2，如果網頁包含了k個出鏈，則用戶從當前頁面跳轉到任意一個鏈接所指向頁面的概率是相等的。

用戶不斷重複以上過程，在相互有鏈接指向的頁面之間跳轉。如果對於某個頁面所包含的所有鏈接，用戶都沒有興趣繼續瀏覽，則可能會在瀏覽器中輸入另外一個網址，直接到達該網頁，這個行為稱為遠程跳轉（Teleporting）。假設互聯網中共有m個頁面，則用戶遠程跳轉到任意一個頁面的概率也是相等的，即為1/m。隨機遊走模型就是一個對直接跳轉和遠程跳轉兩種用戶瀏覽行為進行抽象的概念模型。