圖上隨機遊走

本頁介紹圖上隨機遊走問題。主要從網格圖、稀疏圖、一般圖三個角度進行探究，介紹瞭解決這類問題的各種方法，並對比了它們在解決各種問題時的優缺點。

定義

給定一張有向簡單圖 \(G=(V, E)(V=\{v_1, v_2, \cdots, v_{|V|}\})\) 和起點 \(s \in V\)，終點 \(t \in V\)，每條邊 \(e=\left(x, y\right)\) 有正權值 \(w_e\)，滿足 \(\forall x \in V \backslash\left\{t\right\}\)，\(\sum_{\left(x, y\right) \in E} w_{\left(x, y\right)}=1\)，且對於任意點 \(x\) 都存在一條從 \(x\) 出發到達 \(t\) 的路徑。有一枚棋子從起點出發，每秒從當前所在點 \(x\) 以 \(w_{(x, y)}\) 的概率選擇出邊 \(\left(x, y\right)\) 並走向 \(y\)，到達終點則停止，求期望花費時間。

事實上，這個問題也可以寫成矩陣的形式。定義矩陣 \(P\)：

\[ P_{x, y}= \begin{cases} w_{(x, y)} & \text{if } (x, y) \in E \text{ and } x \neq t \\ 0 & \text{if } (x, y) \notin E \text{ or } x=t \\ \end{cases} \]

要求的答案即為：

\[ \sum_{k \geq 0} k \times\left(P^k\right)_{s, t} \]

其中 \(\left(P^k\right)_{s, t}\) 表示走了 \(k\) 步第一次到達終點的概率。當圖有限且所有點都能到達終點時，由 \(P\) 的定義可以證明其特徵值都小於 1，所以答案一定是收斂的。

為了方便描述，在本頁中如無特殊説明，均用 \(n\) 代指 \(|V|\)，\(m\) 代指 \(|E|\)。

另外，在本頁中，稀疏圖指邊數和點數同階的圖。

網格圖

例題 1 Circles of Waiting

有一枚棋子起始被放在平面直角座標系的 \((0,0)\) 點。每秒棋子會隨機移動。假設它當前在 \((x, y)\)，它下一秒有 \(p_1\) 的概率移動到 \((x-1, y)\)，\(p_2\) 的概率移動到 \((x, y-1)\)，\(p_3\) 的概率移動到 \((x+1, y)\)，\(p_4\) 的概率移動到 \((x, y+1)\)。保證 \(p_1+p_2+p_3+p_4=1\)。求期望經過多少時間它會移動到一個離原點的歐幾里得距離大於 \(R\) 的位置。\(0 \leq R \leq 50\)，\(p_1, p_2, p_3, p_4>0\)，答案對 \(10^9+7\) 取模。

樸素做法

記 \(f(i, j)\) 表示在棋子在 \((i, j)\) 時移動到一個離原點的歐幾里得距離大於 \(R\) 的位置的期望時間，轉移方程為：

\[ f(i, j)= \begin{cases} p_1 f(i-1, j) + p_2 f(i, j-1) + p_3 f(i+1, j) + p_4 f(i, j+1) + 1 & i^2 + j^2 \leq R \\ 0 & i^2 + j^2 > R \end{cases} \]

由於轉移並不存在拓撲序，需要使用高斯消元求解。時間複雜度 \(O\left(R^6\right)\)，無法通過本題。

直接消元法

注意到需要消元的方程的係數大多數都是 0，消元時只對值非 0 的位置進行計算就可以降低複雜度。

考慮消元的過程，將方程按照在座標系中從上到下，同一層中從左到右的順序進行消元，將已經消元過的方程染成黃色，與黃色點相鄰的點染成綠色，其餘點染成黑色，如下圖：

graph-random-walk-1

接下來要對下一個綠色格子對應的方程進行消元。在這個方程中，只有綠色格子和它下方的第一個黑色格子對應的變量係數可能不為 0 ; 而只有綠色格子和它下方的第一個黑色格子對應的方程中，當前格子對應的變量係數可能不為 0。

注意到綠色格子只有 \(O(R)\) 個，所以單個方程消元的時間複雜度為 \(O\left(R^2\right)\)。一共只有 \(O\left(R^2\right)\) 個方程，所以時間複雜度降低為 \(O\left(R^4\right)\)，可以通過本題。

主元法

方程和變量都有 \(O\left(R^2\right)\) 個，如果能將規模縮小至 \(O(R)\)，那麼樸素的高斯消元就能通過了。

將每行從左到右第一個格子對應的變量設為主元，共 \(2 R+1\) 個，設法將其他格子對應的變量用關於這些主元的線性函數表示。從左到右逐列考慮，對於當前列的每個格子 \((i, j)\)，注意到 \(f(i, j)， f(i-1, j)， f(i, j-1)， f(i, j+1)\) 都是已知的關於主元的線性函數，將轉移方程移項，有：

\[ f(i+1, j)=\frac{f(i, j)-p_1 f(i-1, j)-p_2 f(i, j-1)-p_4 f(i, j+1)-1}{p_3} \]

這樣我們就能得到 \(f(i+1, j)\) 關於主元的線性函數表示。如果 \((i+1, j)\) 已經離原點歐幾里得距離超過 \(R\) 了，則可以得到一個方程：\(f(i+1, j)=0\)。最終，會得到 \(2 R+1\) 個方程，對這些方程進行高斯消元即可。

在遞推關於主元的線性函數的階段，共有 \(O\left(R^2\right)\) 個變量，遞推單個變量需要花費 \(O(R)\) 的時間；之後，將問題的規模縮減到了 \(O(R)\)。兩部分的時間複雜度均為 \(O\left(R^3\right)\)，總的時間複雜度也為 \(O\left(R^3\right)\)，可以通過本題。

兩種做法的對比

下面從多種方面對比兩種做法：

從時間複雜度方面，主元法在網格圖上的最壞時間複雜度為 \(O(n \sqrt{n})\)（當網格圖長和寬都為 \(O(\sqrt{n})\) 級別時時間複雜度最高），直接消元法在網格圖上最壞時間複雜度為 \(O\left(n^2\right)\)，主元法較優。

從精度方面，對於一些需要進行實數計算而不是取模的題目，直接消元法的精度優於主元法。

從適用性方面，兩種做法適用於不同的方面。

當網格圖中存在障礙或者走某些邊的概率為 \(0\) 時，對於每個障礙或者概率為 \(0\) 的邊主元法需要增加一個主元，當障礙或者概率為 \(0\) 的邊的數量多於 \(O(R)\) 時，主元法的時間複雜度會增加，而直接消元法的時間複雜度仍然不變。

但主元法還可以做類似於網格圖的轉移方程的消元，例如 \(f(i, j)=p_1 f(i+1, j)+p_2 f(i, j+1)+p_3 f(\operatorname{pre}(i, j))+1\)，其中 \(\operatorname{pre}(i, j)=(x, y)(x \leq i, y \leq j)\) 是問題給定的值，而直接消元法的複雜度分析在這種模型中並不適用。

除此以外，網格圖鄰接矩陣行列式的計算，也不能使用主元法，只能用直接消元法來優化時間複雜度。

綜上，兩種做法各有所長，需要根據具體題目分析採用不同的做法。

稀疏圖

例題 2 Expected Value

給定一張簡單無向連通稀疏圖 \(G=(V, E)\)，有一枚棋子起始被放在 \(v_1\)，每秒棋子會從與當前點相連的邊中等概率選擇一條走到出邊指向的點，求到達 \(v_n\) 的期望時間。\(n \leq 2000\)，答案對 \(p\) 取模，\(p\) 是在區間 \(\left[10^9, 1.01 \times 10^9\right]\) 內隨機生成的一個質數。

基礎知識

定義 4.1. 所有滿足 \(p(A) = 0\) 的多項式 \(p(λ)\) 稱為矩陣 \(A\) 的零化多項式。

定義 4.2. 記 \(I_n\) 表示 \(n\) 階單位矩陣，定義一個 \(n × n\) 矩陣 \(A\) 的特徵多項式為 \(p(λ) = \det(λI_n - A)\)，其中 \(\det\) 表示一個矩陣的行列式。不難發現，一個 \(n\) 階矩陣 \(A\) 的特徵多項式的次數不超過 \(n\)。

定理 4.2.（Cayley–Hamilton 定理）任意矩陣的特徵多項式是它的零化多項式。

所以，一個 \(n\) 階矩陣的次數最小的零化多項式的次數也不超過 \(n\)。

求解原問題

注意到，期望走的時間 \(E(t)=\sum_{i\geq0}\Pr[t>i]\)，如果我們能求出走了 \(i\) 步還沒有結束的概率，對所有 \(i ≥ 0\) 求和即為答案。

記 \(f(i, j)\) 表示走了 \(i\) 步，當前停留在 \(j\)，且沒有走到過 \(n\) 的概率，那麼有：

\[ f(i,j)=\sum_{(k,j)\in E}\frac{f(i-1,k)}{\deg_k}(j\neq n) \]

其中 \(\deg_k\) 表示 \(k\) 的度數。

注意到 \(f\) 的轉移與 \(i\) 無關，可以認為一次轉移是乘上了一個矩陣，即 \(f{i+1}=f_iM\)。由於 \(M\) 的最小零化多項式次數不超過 \(n\)，所以 \(f\) 的最短遞推式長度也不超過 \(n\)，故 \(\Pr[t>i]=\sum_{j=1}^{n-1}f(i,j)\) 的最短遞推式長度也不超過 \(n\)。我們可以在 \(O(nm)\) 的時間求出 \(\Pr[t>0],\Pr[t>1],\cdots,\Pr[t>3n]\)，然後使用Berlekamp–Massey算法，在 \(O(n^2)\) 的時間內求解出 \(\Pr[t > i]\) 的最短遞推式。

考慮求一個 \(k\) 階線性遞推序列 \(a\) 的生成函數。不妨設 \(i ≥ i_0\) 時 \(a_i=\sum_{j=1}^kc_ja_{i-j}\)，記 \(a\) 和 \(c\) 的生成函數為 \(A(x)\) 和 \(C(x)\)，那麼 \(A(x)=A(x)C(x)+A_0(x)\)，其中 \(A_0(x)\) 是由 \(i < i_0\) 的項決定的。

回到原問題，由於我們能求出 \(\Pr[t > i]\) 的最短遞推式，則我們可以求出 \(C(x)\) 和 \(A_0(x)\)（定義與上一段相同），移項得 \(A(x)=\frac{A_0(x)}{1-C(x)}\)。我們要求的是 \(\sum_{i\geq0}[x^i]A(x)\)，不難發現這個值就等於 \(A(1)\)，將 \(x = 1\) 帶入原問題求解即可。由於模數是隨機質數，可以認為分母不會為 \(0\)。

這樣，我們就在 \(O(nm+n^2)\) 的時間複雜度內解決了本題。如果圖 \(G\) 的點數與邊數同階，本題中時間複雜度可以認為是 \(O(n^2)\)。

一般圖

例題 3 Frank

給定一張簡單強連通有向圖 \(G = (V, E)\)，對於所有 \(1 ≤ s ≤ n\)，\(1 ≤ t ≤ n\)，\(s ≠ t\)。回答下面的問題：有一枚棋子起始被放在 \(v_s\)，每秒棋子會從當前點的出邊中等概率選擇一條走到出邊指向的點，求到達 \(v_t\) 的期望時間。\(3 ≤ n ≤ 400\)。

分析和轉化

記 \(p_{i, j}\) 表示棋子在 \(i\) 時，選擇出邊 \((i, j)\) 走到 \(j\) 的概率，特別地，當出邊不存在時概率為 \(0\)。記 \(f_{i,j}\) 表示 \(i\) 隨機遊走到 \(j\) 的期望時間，特別地，\(f_{i,i} = 0\)。當 \(i ≠ j\) 時，轉移方程為：

\[ f_{i,j}=1+\sum_{1\leq k\leq n}p_{i,k}f_{k,j} \]

當 \(i = j\) 時，記 \(g_i\) 表示從 \(i\) 開始隨機遊走，第一次回到 \(i\) 的期望時間，那麼：

\[ f_{i,i}=1-g_i+\sum_{1\le k\le n}p_{i,k}f_{k,i} \]

為了方便觀察，我們將轉移方程寫成矩陣的形式。記 \(P\) 表示這個圖的轉移矩陣，\(F\) 表示答案矩陣，\(I\) 表示 \(n\) 階單位矩陣，\(J\) 表示 \(n\) 階全 \(1\) 矩陣，\(G\) 是一個 \(n\) 階矩陣，滿足 \(G_{i,i} = g_i\)，其他位置為 \(0\)，則：

\[ F=J-G+PF \]

如果我們能求出 \(G\)，那麼我們只需要解方程：

\[ (I − P)F = J − G \]

G 的求法

定義 5.1. 定義一個 \(n\) 階轉移矩陣 \(P\) 的穩態分佈為一個 \(n\) 維向量 \(π\)，滿足 \(\sum_{i=1}^{n}\pi_{i}=1\)，\(πP = π\)。其中，\(π\) 每一維的值都在區間 \([0,1]\) 內。

我們很容易找出穩態分佈的實際意義。如果某個時刻棋子有 \(π_i\) 的概率停留在 \(v_i\)，則在之後的任意時刻，棋子仍然滿足這個概率分佈。我們可以在 \(O(n^3)\) 的時間通過高斯消元解方程來求出 \(π\)，那麼 \(π\) 與 \(G\) 有什麼關係呢？

定理 5.1. 對於任意 \(1 ≤ i ≤ n\)，有 \(π_ig_i = 1\)。

證明

由 \(F = J - G + PF\)，移項得：

\[ G = PF + J − F \]

兩邊同時在左邊乘上 \(π\) 有：

\[ πG = πPF + πJ − πF \]

由 \(π\) 的定義有 \(πP = π\)，故：

\[ πG = πJ \]

所以：

\[ \pi_ig_i=\sum_{j=1}^n\pi_j=1 \]

原命題得證。

所以，通過引入穩態分佈，我們可以在 \(O(n^3)\) 的時間內求解 \(G\)。

求解原問題

在解方程的過程中，我們發現一個問題：\((I - P)\) 並不滿秩，不能通過乘逆矩陣的方法求解。

定義 5.2. 定義一個有向圖 \(G = (V,E)\) 的以 \(r\in V\) 為根的有向生成樹是 \(G\) 的一個子圖 \(T = (V,A)\)，滿足：

對於任意 \(i ≠ r\)，\(i\) 的出度為 \(1\)。
\(r\) 的出度為 \(0\)。
\(T\) 中不存在環。

引理 5.1.（有向圖上的矩陣樹定理）對於一個有向圖 \(G\)，記 \(D\) 表示其出度矩陣，即 \(D_{i,i} = d_i\)，\(D_{i,j} = 0(i ≠ j)\)，其中 \(d_i\) 表示 \(i\) 的出度，記 \(A\) 表示其鄰接矩陣，則其以 \(r\) 為根的有向生成樹個數為 \(D - A\) 去掉第 \(r\) 行第 \(r\) 列後的行列式。

定理 5.2. 對於一個強連通圖 \(G = (V,E)\) 的轉移矩陣 \(P\)，\((I - P)\) 的秩為 \(n - 1\)。

證明

因為對矩陣某一行乘上一個非零常數其秩不改變，所以我們將 \((I - P)\) 的第 \(i\) 行乘上 \(v_i\) 的出度，得到一個新的矩陣 \(L\)，只需證明 \(L\) 的秩為 \(n - 1\) 即可。
由於 \(L\) 每行的和均為 \(0\)，對 \(L\) 的所有列向量求和，會得到零向量，即這些向量線性相關，所以 \(L\) 的秩不為 \(n\)。
不難發現 \(L\) 等於圖 \(G\) 的出度矩陣減去其鄰接矩陣，由引理 5.1 得 \(L\) 去掉第 \(i\) 行第 \(i\) 列後行列式表示以 \(v_i\) 為根的有向生成樹個數。
由於 G 是強連通的，所以以任意點為根的有向生成樹個數均不為 \(0\)，即 \(L\) 去掉第 \(i\) 行第 \(i\) 列之後仍然滿秩。
因為加上一列秩不會變小，所以 \(L\) 去掉第 \(i\) 行後所有行向量線性無關。故 \(L\) 的秩為 \(n - 1\)。
回到原問題，考慮求解原問題中的方程。為了方便，我們將方程寫成 \(AX = B\) 的形式，其中 \(A\)，\(B\) 已知，需要求解 \(X\)。由於 \(A\) 不滿秩，解有無數個，我們首先求出一組特解。將 \(A\) 和 \(B\) 一起做高斯消元。把 \(A\) 的前 \(n - 1\) 行消成只有主對角線和第 \(n\) 列有值的形式，最後一行消成全 \(0\)，即下列形式：

\[ \begin{bmatrix} 1 & 0 & 0 & \cdots & 0 & a_1 \\0&1&0&\cdots&0&a_2\\0&0&1&\cdots&0&a_3\\ \vdots&\vdots&\vdots&\ddots&\vdots&\vdots \\0&0&0&\cdots&1&a_{n-1}\\0&0&0&\cdots&0&0 \end{bmatrix} X= \begin{bmatrix} b_{1,1}&b_{1,2}&b_{1,3}&\cdots&b_{1,n-1}&b_{1,n} \\b_{2,1}&b_{2,2}&b_{2,3}&\cdots&b_{2,n-1}&b_{2,n} \\b_{3,1}&b_{3,2}&b_{3,3}&\cdots&b_{3,n-1}&b_{3,n} \\\vdots&\vdots&\vdots&\ddots&\vdots&\vdots \\b_{n-1,1}&b_{n-1,2}&b_{n-1,3}&\cdots&b_{n-1,n-1}&b_{n-1,n} \\0&0&0&\cdots&0&0 \end{bmatrix} \]

令 \(X_{n,i} = 0\)，可以解出一組特解，記為 \(Y\)。接下來將特解調整為真正的解。
注意到 \(X_{n,i} = 0\)，考慮組合意義有 \(Y_{i,j} = 1 + Y_{j,j} + P_{i,k}X_{k,j}\)，不難解出 \(X_{i,j} = Y_{i,j} - Y_{j,j}\)。最終在 \(O(n^3)\) 的時間複雜度內解決了這個問題。

參考

淺談圖模型上的隨機遊走問題。IOI2019 中國國家候選隊論文集（pp. 17-26)

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用