Tag Archives: 馬可夫矩陣

Cesàro 矩陣序列

本文的閱讀等級:高級 給定一數列 ,Cesàro 數列定義為 ,其中 是 的前 項的平均數,如下: 。 Cesàro 數列因義大利數學家切薩羅 (Ernesto Cesàro) 而得名。若 ,我們說數列 是可累加的 (summable), 稱為 Cesàro 極限。若數列 收斂至 ,則對應的 Cesàro 數列 也收斂至 (證明見附註[1])。收斂性蘊含可累加性,但可累加性未必有收斂性。例如,震盪數列 不收斂,但對應的 Cesàro 數列收斂至 。Cesàro 數列可以推廣至矩陣序列。令 為一 階矩陣。若 存在,則稱 為可累加矩陣。(如果不取平均, 稱為 Neumann 無窮級數[2]。) 若 ,我們稱 … Continue reading

Posted in 線性代數專欄, 數值線性代數 | Tagged , , , , , , | Leave a comment

實對稱矩陣特徵值變化界定的典型問題

本文的閱讀等級:中級 線性代數所處理的最佳化問題可概分為兩大類:一是線性方程 的最小平方近似解問題,即求出 使得誤差平方 具有最小值。內積空間理論導出最佳解須滿足正規方程式 (normal equation) (見“ 從線性變換解釋最小平方近似”)。二是特徵分析推衍的二次型約束最佳化問題,即求單位向量 (unit vector) 使得 有最大值,其中 是實對稱矩陣。二次型 的極值產生條件是特徵方程式 ,極值大小則由 的特徵值決定 (見“二次型與正定矩陣”)。因為這個緣故,二次型約束最佳化也稱為實對稱矩陣的特徵值變化界定,下面我們討論兩個典型問題並說明完整的解法。   問題一 (取自 2012年台大資訊所碩士班入學試題):令 為實數,且 ,求 的最大值。

Posted in 線性代數專欄, 二次型 | Tagged , , , , , | Leave a comment

利用馬可夫鏈計算擲幣事件發生的機率

本文的閱讀等級:中級 美國康乃爾大學心理學教授季洛維奇 (Thomas Gilovich) 每年都會在他的統計學課堂中安排一個實驗[1]。他要求每位學生各自寫下一組心中模擬投擲一枚公正硬幣20次所產生的隨機序列,分別以 O 和 X 代表正面和反面。但是,其中一位學生則被指派實際投擲一枚硬幣20次,也寫下他的實驗結果。季洛維奇在實驗進行前走出教室,等他返回教室後,他將接受一項挑戰:檢視所有學生繳交的實驗記錄,然後判斷其中那一張紙記載了實際擲幣產生的序列。季洛維奇總是能令學生們驚訝不已,他無一次例外地揀選出真實的擲幣序列。究竟他是怎麼辦到的?季洛維奇既沒有暗藏機關也不具特異能力,他掌握的技能不過就是「資訊不對稱」。身為心理學教授,他知道絕大多數人──包括教室中的學生──總是低估了出現連續正面或反面的機率。真實的擲幣結果幾乎都是那張記錄著最長的連續正面或反面的序列,例如: OXXXXXOXOOXOOXOOXOOX, 而學生們想像出來的擲幣序列則經常如下: XXOXOOOXOOXOXXOOXXOO。 本文的主題即在破解季洛維奇的戲法:釐清投擲一枚公正硬幣 次,計算出現至少連續 次正面的機率。

Posted in 機率統計 | Tagged , , , , , , | 3 Comments

每週問題 October 17, 2011

這是關於隨機矩陣 (stationary matrix) 或稱馬可夫矩陣 (Markov matrix) 的特徵值問題。 Pow-Oct-17-11 參考解答: PowSol-Oct-17-11

Posted in pow 特徵分析, 每週問題 | Tagged | 2 Comments

馬可夫過程

本文的閱讀等級:中級 馬可夫過程 (Markov process) 是一種隨機過程,這裡我們討論的是具有離散狀態的過程,也稱為馬可夫鏈 (Markov chain)。馬可夫鏈不僅是一個應用廣泛的模型分析工具,也是線性代數裡一些數值演算法的基礎。馬可夫鏈常以矩陣形式的差分方程描述,通過分析此問題可以了解動態過程如何由矩陣的特徵值和特徵向量規範。

Posted in 機率統計 | Tagged , , , , , | 1 Comment

Google 搜尋引擎使用的矩陣運算

本文的閱讀等級:中級 Google 的技術總覽開宗明義說: Google 出類拔萃的地方在於專注開發「完美的搜尋引擎」,創辦人 Larry Page 將其定義為「能做到確實瞭解使用者想要的東西,並確實提供對應的資訊」…Google 使用 PageRankTM 檢查網路上的整個連結架構,藉此決定網頁的重要性。 接著會執行超文字符合分析,來判定哪些網頁與所執行的特定搜尋相關。結合所有的重要性和特定查詢的相關性後,Google 才會將最相關和最可靠的結果放在搜尋結果最前方。

Posted in 線性代數專欄, 圖論, 應用之道 | Tagged , , , , , , | 7 Comments