第二十一章：隨機漫步 — 動畫敘事
第二十一集 · Ch.21 隨機漫步
喝醉的數學
一個醉漢站在街上，每步隨機往左或往右。
他最終會離家多遠？會回到原點嗎？
隨機漫步是機率論最美的主題之一，
也是 PageRank、金融模型、物理擴散的基礎。
他最終會離家多遠？會回到原點嗎？
隨機漫步是機率論最美的主題之一，
也是 PageRank、金融模型、物理擴散的基礎。
一維隨機漫步
一維隨機漫步
從位置 0 出發，每步：
以機率 p 往右（+1），以機率 1-p 往左（-1）
對稱漫步（p=1/2）：
n 步後位置的期望值 = 0
n 步後位置的標準差 = √n
回到原點的機率：在對稱漫步中，幾乎必然會回到原點（機率為 1）！
以機率 p 往右（+1），以機率 1-p 往左（-1）
對稱漫步（p=1/2）：
n 步後位置的期望值 = 0
n 步後位置的標準差 = √n
回到原點的機率：在對稱漫步中，幾乎必然會回到原點（機率為 1）！
互動：隨機漫步模擬器
按模擬開始
賭徒破產問題
賭徒從 k 元開始，每局贏 1 元（機率 p）或輸 1 元（機率 1-p），到達 n 元或破產（0 元）為止。
破產機率是多少？
破產機率是多少？
賭徒破產定理
從 k 元出發，目標 n 元，破產機率：
若 p = 1/2：
若 p ≠ 1/2：
其中
推論：即使 p 稍大於 0.5，有足夠的錢才能有效對抗賭場。
若 p = 1/2：
Pr(破產) = 1 - k/n若 p ≠ 1/2：
Pr(破產) = (rⁿ - rᵏ)/(rⁿ - 1)其中
r = (1-p)/p推論：即使 p 稍大於 0.5，有足夠的錢才能有效對抗賭場。
互動：賭徒破產計算機
5
10
0.50
...
PageRank — 圖上的隨機漫步
Google 的 PageRank 把整個網頁圖想成一個隨機漫步：一個「隨機衝浪者」按超連結隨機跳轉。
停留在某頁面的長期比例，就是那個頁面的 PageRank 值。
停留在某頁面的長期比例，就是那個頁面的 PageRank 值。
平穩分布
隨機漫步長期停留在各節點的比例，收斂到平穩分布 π。
對無向圖：
對無向圖：
π(v) = deg(v) / 2|E|PageRank 公式
PR(u) = Σ PR(v)/出度(v)
（對所有指向 u 的頁面 v 求和）
反覆迭代直到收斂
（對所有指向 u 的頁面 v 求和）
反覆迭代直到收斂
應用
• 網頁搜尋排名
• 論文引用分析
• 社群網路影響力
• 蛋白質交互網路
• 論文引用分析
• 社群網路影響力
• 蛋白質交互網路
觀念測驗
對稱一維隨機漫步（p=1/2），n 步後距離原點的期望距離約是多少？
小結
隨機漫步
無處不在
無處不在
從醉漢到 PageRank，從股票價格到布朗運動，
隨機漫步是描述隨機動態系統的核心模型。
賭徒破產定理告訴我們：
即使有優勢，資金不足也終將失敗。
隨機漫步是描述隨機動態系統的核心模型。
賭徒破產定理告訴我們：
即使有優勢，資金不足也終將失敗。
下一集：遞迴關係——最後一章，也是最實用的一章
閱讀完整第二十一章互動教材 →
1 / 8
本頁為動畫敘事版。看完後可前往 完整第二十一章 進行互動練習。
教材來源：Mathematics for Computer Science (Lehman, Leighton, Meyer)