動機
重複的獨立抽樣可能代價高昂,因為每抽取一個新的隨機頂點都需要大量隨機位元。隨機漫步則重用當前頂點:每一步從其鄰點中選取一個。這樣能否得到近似均勻的樣本,取決於圖本身。一個圖可以是連通的卻混合緩慢,而連通的二分圖則可能永遠在其兩側之間交替。特徵值為區分這些行為提供了定量的方法。本單元證明一個混合估計;若要把隨機漫步用於完整的節省隨機性的放大,還需要聯合事件的界,此處並不作這樣的斷言。
定義
定義 5.2.1
(轉移矩陣與第二大絕對特徵值)
設 是有限無向 -正則圖,有 個頂點且 。轉移矩陣為 ,其中 是鄰接矩陣。採用列概率向量:。因為 是對稱的且每一列之和為一,所以均勻分佈 是平穩分佈。實譜定理給出一組標準正交特徵基。把特徵值寫作 ,並為 選取歸一化的常值向量,再令 。
定義 5.2.2
(全變差距離)
對概率向量 ,它們的全變差距離為 。它等於在所有頂點集 上 的最大值。為說明這一點,令 為滿足 的頂點集;由於各座標之差的總和為零,正的部分之和恰為絕對值之和的一半,而其他任何集合給出的絕對差都不會更大。
定理
定理 5.2.3
(譜混合界)
對每個初始分佈 及每個整數 ,
特別地,從任意單個頂點出發,有 。若 ,則漫步從每個初始分佈出發都收斂到均勻分佈。
定理 5.2.4
(特徵值與週期性判據)
的每個特徵值都落在 內。若 連通,則特徵值 的重數為一。若 連通且非二分圖,則 不是特徵值。因此,對連通的非二分圖有 。
證明思路或證明
證明
(偏離均勻分佈的收縮)
向量 與常值向量正交,因為它的各座標之和為零。把它按標準正交特徵基展開為 。於是
由柯西–施瓦茨(Cauchy–Schwarz)不等式,。把它應用於 ,即證得第一個不等式。若 是點質量,則它到 的距離平方為 ,由此得到第二個不等式。
證明
(特徵值、連通性與二分性)
對於特徵值判據,設 是屬於特徵值 的實特徵向量,並選取使 最大的頂點 。由於 是鄰點座標的平均值,故 ,從而 。若 ,平均值中等號成立迫使 的每個鄰點的取值都等於 ;連通性把這一等式傳播到整個圖。因此每個 -特徵向量都是常值向量。
若 ,等號成立迫使 的每個鄰點的取值都等於 。在連通圖中傳播下去,沿每條路徑的取值都正負交替。奇圈會迫使一個非零值等於它的相反數,這是矛盾。因此連通的非二分圖沒有特徵值 。由於圖只有有限多個特徵值,且所有非常值特徵值都嚴格介乎 與 之間,它們的絕對值的最大值嚴格小於一。
證明透視
為甚麼偏差從第二個特徵向量開始
證明把 拆成平穩部分 與偏差 ,一切都建立在偏差與常值向量正交之上:它的各座標之和為零。正因如此,展開可以從 開始,因子 不會出現,衰減只由 控制。 的對稱性用來取得標準正交特徵基,所以平方範數就是 ,沒有交叉項。
中需要絕對值,因為 ,對 的衰減並不比 更快;接近 的特徵值會一邊交替變號,一邊使收縮停滯。最後一步 是 唯一出現之處:歐氏範數的收縮要付出這個因子,才變成全變差距離的界。
例題詳解
例題 5.2.5
(三角形上的漫步)
對三個頂點的無自環完全圖,。常值向量的特徵值為 ,而與之正交的每個向量的特徵值為 。因此 。從點質量出發,定理給出全變差距離至多為 。負特徵值帶來交替變號的修正項,但其模長按幾何級數衰減。
例題 5.2.6
(週期性的二分圖漫步)
在四圈上,若從二分劃分的某一側出發,則漫步在偶數時刻位於同一側,在奇數時刻位於另一側。均勻分佈給兩側各分配概率 ,而漫步在相應奇偶性的時刻把概率一全部分配給其中一側。因此全變差距離在每個時刻都至少為 。該圖是連通的,但 是特徵值,漫步並不收斂到均勻分佈。
例題 5.2.7
(足夠的步數)
若一個圖有 且 ,則從任意頂點出發, 步之後的全變差距離至多為 。當 時,它小於 。這只是充分性的界;實際距離可能更小。該估計使用的是假定的譜界,對所選定的圖,這個譜界必須另行證明。
常見錯誤
反例模式
平穩性並不蘊含收斂
即使對四圈,均勻分佈也是平穩的,但點質量並不收斂到它。平穩性說的是從均勻分佈出發的漫步始終保持均勻;收斂說的是其他初始分佈會趨近於均勻分佈。這是兩個不同的論斷。
常見錯誤
(正則圖不一定連通)
正則圖可以是不連通的;此時漫步無法離開其所在的連通分支,特徵值 還有額外的特徵向量。於是對適當選取的特徵基, 等於一。
常見錯誤
(近似均勻的邊緣分佈不等於獨立樣本)
對每個單一時刻分佈的界並不會使相繼的位置相互獨立。特別地,僅憑邊緣分佈近似均勻,並不能證明漫步以指數小的概率避開某個固定的壞集。
以等待消除週期性
一種標準的修改是懶惰漫步:每一步以概率 停留在當前頂點,否則執行原漫步的一步。它的矩陣為 。它是對稱的,並保持均勻分佈不變。若 ,則 ,所以它的特徵值由 的特徵值經這一變換得到。特徵值 變為零。在連通圖上, 的每個非常值特徵值都嚴格小於一,因此 的每個非常值特徵值都落在 內。於是同樣的譜證明給出:懶惰漫步在每個連通正則圖(包括二分圖)上都收斂。
這一修改改變了實驗本身。證明了懶惰漫步的界之後,不能悄悄地把它歸屬於原來的非懶惰漫步。懶惰的一步可以停留在同一頂點,而無自環圖上的原漫步不可能這樣。例如在四圈上,從某個頂點出發,懶惰的一步以概率 停在該頂點,並以概率 移到各個鄰點。這種重複消除了原漫步確定性的奇偶交替。
例題 5.2.8
(懶惰四圈)
非懶惰四圈的轉移矩陣特徵值為 。在 下,它們變為 。因此 。從任意頂點出發,經 個懶惰步之後,到均勻分佈的全變差距離至多為 。該界證明了收斂性,儘管它並不是每個時刻的精確距離。
從全變差距離到事件概率
若分佈 與均勻分佈的全變差距離不超過 ,則對每個頂點集 ,
這由定義中的事件刻畫得到。例如,若某個集合含有百分之十的頂點,且全變差距離至多為 ,則它在該時刻的概率介乎 與 之間。針對某個特定頂點的逐點論斷也是一個事件論斷,但 的全變差界可能遠大於均勻質量 ;對於一個非常稀少的頂點,它未必給出有用的相對估計。
概念視角組合
數長度為 t 的步行
設 為由 到 、長度為 的步行的條數。於是 ,所以均勻性表示:從 出發的 條等可能步行,其終點分佈得很均勻。由於 ,其算子範數為 ,所以每個元素都滿足
每一對頂點之間的步行條數,都幾乎恰好等於均勻分配的條數。
該陳述針對的是單個時刻。即使從平穩分佈出發的漫步,各個位置之間也是相依的:每一步的下一個頂點都必須是當前頂點的鄰點。對於無自環圖,在一步中停留在同一頂點的概率為零,而兩個獨立的均勻頂點重合的概率為 。因此,精確均勻的邊緣分佈並不蘊含獨立性。要證明許多次到訪全都落在某個壞集中,需要對相關性另加控制,而不僅僅是對每次到訪應用單一時刻的混合界。
若確實需要獨立的近似均勻樣本,一種直接的構造是:對每個樣本使用獨立的隨機位元分別運行漫步,每次都從固定頂點出發並走足夠多的步數。由於所得輸出依賴於互不相交的隨機種子,它們是相互獨立的。這種簡單做法無法獲得單條相關漫步所節省的隨機位元。後者可以藉助更強的擴展性或譜論證來分析,但這些界需要各自的證明與假設。
割與必要的瓶頸檢驗
對頂點集 ,記 為一端在 內、另一端在 外的無向邊之集。若初始頂點在非空集 上均勻分佈,則一步之內離開 的概率恰為
事實上, 個起始頂點等可能,每個頂點的 條關聯邊各以概率 被選中,而每條邊界邊恰從其位於 內的端點被計數一次。這個比值度量了該初始分佈所對應的瓶頸。如果它很小,則下一步時大部分概率仍留在 內,即使整個圖上的均勻分佈分配給 的質量要小得多。
更精確地說,若 ,則從 上的均勻分佈出發的一步分佈給 分配的概率為 ,而均勻分佈分配的是 。因此,只要這兩個概率之差為正,它們的全變差距離就至少等於這個差。邊界很小是不能快速一步混合的證據。這一初等觀察並不是一般的譜擴展定理的證明:要把每個割的比值與特徵值以及之後所有時刻聯繫起來,還需要額外的論證和適當的常數。
正則性使這裏的均勻分佈成為平穩分佈。對於非正則的無向圖,簡單隨機漫步的平穩分佈通常與度數成正比,而不是均勻的。對稱矩陣與範數的論證可以透過改變內積來適應,但上面給出的均勻分佈結論不能原樣照搬。類似地,有向圖未必有對稱的轉移矩陣,也未必有標準正交的實特徵基;上文所用的譜定理是該方法的一個實質性假設,而不是裝飾性的步驟。
譜估計的解讀
量 常被稱為絕對譜隙。該估計直接說明了它為何重要:當 接近一時,可能需要很多步才能使 變小。當 時,為使點質量的界至多為 ,只需
其中要求分子為正;否則對這個特定的界而言,零步就已滿足。將所得的數向上取整為整數。若 ,則譜表達式表明一步即精確到達均勻分佈。這些都是由該不等式導出的充分條件,未必是最優的混合時間。
如果當頂點數增長時存在公共的界 ,則稱這個圖族對快速混合是有用的。對固定的期望全變差誤差,所給估計只需要與頂點數的對數成正比的步數。但每一步的代價仍須考慮。如果每個頂點有 個可顯式定址的鄰點,且 是 的冪,則可用 個均勻隨機位元選定一步。對於其他度數,精確的均勻選取需要適當的抽樣方法;簡單地把均勻選取的位元串對 取模可能引入偏差。
譜定理給出的是對所有起始頂點一致的界,但對特定的起點或時刻它可能比較鬆。它把每個非常值特徵值的模長都替換為單一的最壞值 ,並應用了柯西–施瓦茨不等式。給定起始向量的某些係數可能為零,而一範數與二範數之間的不等式也未必取到等號。因此,計算得到的精確分佈可能比這一證書所預測的混合得更快,而這並不與它矛盾。
總結
對稱性使隨機漫步的轉移矩陣成為可正交對角化的算子。非常值特徵值控制著偏離均勻分佈的部分在歐氏範數下收縮的速度;柯西–施瓦茨不等式把這一點轉化為全變差保證。連通性消除了額外的平穩方向,非二分性則消除了交替的方向。
練習
快速檢查
(計算無自環完全圖 上漫步的非常值特徵值,並給出 。)
寫出 的 ,並利用 在常值向量的正交補上為零。
解答 · 答案
此時 。矩陣 在與常值向量正交的向量上為零,所以非常值特徵值為 ,且 。
快速檢查
(對 且 ,證明 足以使從點質量出發的界達到 。)
把 、、 代入點質量的界。
解答 · 答案
該界為 。
快速檢查
(為甚麼僅憑連通性不能保證收斂到均勻分佈?)
考慮連通的二分圖,例如四圈。
解答 · 答案
連通的二分圖會在其兩側之間交替。四圈的例子中,從某個頂點出發時,到均勻分佈的全變差距離始終至少為 。
快速檢查
(若 ,則在每個時刻到均勻分佈的全變差距離是多少?)
是平穩分佈嗎?
解答 · 答案
它為零,因為 ,因而對每個 都有 。