隨機矩陣（ stochastic matrix）
- 坏嘻嘻原創
- 2018-09-14 10:53:133627瀏覽
本文實例敘述了隨機矩陣。分享給大家供大家參考，如下：
隨機矩陣（stochastic matrix）
最近一個月來一直在看Google排序的核心演算法---PageRank排序演算法[1][2]，在多篇論文中涉及圖論、馬可夫鏈的相關性質說明與應用[3][4][5] ，而最為關鍵，一直讓我迷惑的一句話是"A stochastic matrix has principal/primary eigenvalue 1"[3][4][5][6][7][8]。可能對於系統學過矩陣理論的人，它很平淡，不值得單獨拿出來討論或說明。而我在此不得不承認自己的無知。儘管在高等代數中學習過關於矩陣性質的一些討論，但從來沒有接觸過所謂的隨機矩陣(Stochastic Matrix)，更不要說其性質了。於是，我從網路上努力的尋找相關文獻，但結果不是特別理想，也沒有關於隨機矩陣的詳細介紹以及相關性質的證明。我想也許一方面是我搜尋技術還不成熟，或是搜尋的關鍵字不準確，亦或是網路上關於它的資料本就很缺乏。在這裡我想將最近蒐集的相關資料拿出來整理一下思路，以備將來之用，也是對自己學習的一個真實記錄和督促。
隨機矩陣其實是非負矩陣(Nonnegative matrix)的一類，而非負矩陣是指矩陣元素都是非負(Nonnegative)的，當然非負要與正矩陣（Positive matrix）進行細微的區分。非負矩陣在計算數學、圖論、線性規劃、自動控制等領域有著廣泛的應用，對其特徵值，尤其是最大特徵值（注意這裡的最大是從模的角度或者說是絕對值概念上的最大）特徵值，也就是矩陣的主特徵值（principal/primary eigenvalue）的估計有很重要的意義[9]。
隨機矩陣說來如此之重要，那麼到底是什麼樣的矩陣才是隨機矩陣呢？假如隨便給你一個非負矩陣，該如何判定它是否屬於隨機矩陣呢？
隨機矩陣實際上要分成行隨機矩陣（Row stochastic matrix）和列隨機矩陣（Column stochastic matrix）。行隨機矩陣是指方陣的行和等於1；而列隨機矩陣就是其列和等於1的非負矩陣。那麼同時滿足行和列和都是1的非負矩陣就是雙隨機矩陣（Double stochastic matrix），單位矩陣就是一種雙隨機矩陣。從研究的角度，其實只要研究行矩陣的性質即可，畢竟列隨機矩陣只是行隨機矩陣的轉置矩陣。因此以下的討論完全從行隨機矩陣出發。
既然隨機矩陣A行和為1，那麼假設e=（1,1,...,1），則e的轉置向量e'，即是矩陣的一個特徵向量，對應於A的特徵值1。這樣對於證明隨機矩陣的主特徵值是1還有一定的距離。假設A的n個特徵值為λ(i)，其中i=1,2,...,n；若要證明性質成立，則必須證明|λ(i)|
於是我又查找了相關資料，並在「數學博士論壇」發文請教，得到的回復是要證明它，粗略地講利用圓盤定理即可，若要精細的證明還要利用Perron-Frobenius Theorm[9][10][11][12]。一個個新的概念和方法出現在眼前，看來需要係統的學習數值方法、數值計算理論。查找到的資料[10]顯示任何矩陣的譜半徑都不大於該矩陣任意誘導矩陣範數，而隨機矩陣的L1-Norm值是1，那麼譜半徑（是主特徵值的等價說法）不大於1，而由於1是A的一個特徵值，那麼就不可能出現絕對值大於1的特徵值了：1確實是隨機矩陣A的主特徵值。
那麼上述性質的證明就等價於證明資料[10]的結論了。
其實，「任意複數域上的矩陣的譜半徑不大於其任一種誘導範數」只是矩陣的一個基本的性質。其特定證明見下圖：
# 根據上述的證明結果可知，對任意的行隨機矩陣，其頻譜半徑為1，即最大特徵值是1得證。
由此可知，其實矩陣的一個小小的性質對於沒有系統學過矩陣理論的人有時確實是一個難題。要入行，就當懂行規，要入門，就當精通門路。
隨機矩陣的主特徵值以及second largest eigenvalue的比值是冪法收斂速度的一個基本的衡量標準。 PageRank的計算有多種方式，而對此的研究也是不計其數，當然最傳統的還是利用冪法來確定抓取入庫的各網頁的PageRank值。由於web網頁的數量龐大，針對冪法收斂速度的考量就不是多餘無用的分析。而兩個特徵值的「譜隙」（Eigengap）主要用來衡量利用冪法求解得到的PR值的穩定性的。由此看來，特徵值分析對於理解PageRank演算法扮演關鍵角色。
相關推薦：
以上是隨機矩陣（ stochastic matrix）的詳細內容。更多資訊請關注PHP中文網其他相關文章！