一個輕裝上路的過程
你來到這一階段時，已經很熟悉隨機過程了——也就是一整族以時間為指標的隨機變數 X_0, X_1, X_2, ...——你也見過隨機漫步，其中每一步都和之前的每一步獨立。馬可夫鏈坐落在兩個極端之間。一個極端是完全獨立：下一個值忽略一切，連你現在身在何處都不管。另一個極端是完整記憶：下一個值可以取決於整段被記錄的歷史 X_0, X_1, ..., X_n。馬可夫鏈只保留一絲記憶——當前的位置——其餘全部丟棄。它輕裝上路。
具體一點，想像一隻青蛙待在五片荷葉上。每當時鐘滴答一聲，牠就依某組固定的賠率跳到相鄰的荷葉。要預測青蛙下一步往哪裡去，牠是怎麼來到當前這片荷葉的——是從左邊來的、還是已經繞了一個鐘頭——重要嗎？在馬可夫假設下，不重要。知道青蛙現在在第 3 片荷葉上，就等於掌握了過去所能告訴你的、關於牠下一跳的一切。歷史並沒有從世界上被刪除；只是一旦現在已知，它就變得無關緊要。
這個過程能身處的所有地點所成的集合——那五片荷葉、或全體整數、或一串天氣狀況——就是它的[[state-space|狀態空間]]。在這一階段，我們處理離散狀態空間（一份有限或可數的狀態清單）與離散時間（時鐘滴答 n = 0, 1, 2, ...）。這個組合恰恰就是[[discrete-time-markov-chain|離散時間馬可夫鏈]]，也是整個階段環繞著建立起來的主力工具。
把馬可夫性質說準確
「未來只取決於現在」這個直覺，值得一個精確的陳述，因為隨口的說法藏著一個陷阱。[[markov-property|馬可夫性質]]說：在給定整段過去之下，下一個狀態的條件分布，等於在僅給定當前狀態之下的條件分布。用符號寫，對任意狀態 i_0, ..., i_(n-1), i, j，P(X_(n+1) = j given X_n = i, X_(n-1) = i_(n-1), ..., X_0 = i_0) = P(X_(n+1) = j given X_n = i)。X_n = i 左邊的每一項都被丟掉了——不是因為它沒有價值，而是因為以現在為條件，已經把它吸收進去了。
這一階段的鏈裡，還烤進了第二個容易被忽略的假設：轉移的賠率不隨時間改變。無論 n 是 3 還是 3000，P(X_(n+1) = j given X_n = i) 都是同一個數。具有這個性質的鏈稱為時間齊次的，它讓我們能夠一勞永逸地為那個數命名：p_ij，也就是一步之內從狀態 i 走到狀態 j 的機率。齊次性是一個有著真實例外的真假設——一隻隨著日頭西斜而疲憊的青蛙就會違反它——所以值得大聲說出來，而不是偷偷夾帶進去。
把規則打包進一個矩陣
接下來這一步，正是讓馬可夫鏈如此好計算的關鍵。若狀態空間有 N 個狀態，就把每一個一步機率 p_ij 收集進一個 N×N 的方格陣。第 i 列列出你從狀態 i 出發可能往哪裡去；第 i 列、第 j 行的那一格就是 p_ij。這個方格陣就是[[transition-matrix|轉移矩陣]]，通常寫作 P。整條鏈的動力學定律——青蛙曾經可能做的每一跳——如今都住進了一個整潔的物件裡。
States: Sun Cloud Rain Row i must sum to 1
Sun Cloud Rain
Sun [ 0.7 0.2 0.1 ] <- from a Sunny day
Cloud[ 0.3 0.4 0.3 ] <- from a Cloudy day
Rain [ 0.2 0.5 0.3 ] <- from a Rainy day
row sums: 1.0 1.0 1.0 (every row is a distribution)關於 P 有兩件事不是可選的，而是被機率公理逼出來的。第一，每一格都介於 0 與 1 之間，因為每個 p_ij 都是機率。第二——而這正是大家會忘記的規則——每一列恰好加起來等於 1。第 i 列是「從 i 出發走一步之後你可能身處之處」的完整清單，而鏈總得落在某個地方，所以這些機率是周延的，加起來等於一。一個各元素非負、且每列加總為 1 的方陣，稱為隨機矩陣；轉移矩陣和隨機矩陣是同一回事。（各行通常不會加總為 1，期待它們也加總為 1 是初學者的經典失誤。）
從現在到未來：一個向量遇上矩陣
矩陣本身告訴你的是：一個狀態如何引向下一個。但要真正預測未來，你還需要一個起點——只是在機率裡，起點很少是某個確定的單一狀態。它是一個分布：[[initial-distribution|初始分布]]，一個列向量 mu_0 = (mu_0(1), mu_0(2), ..., mu_0(N))，給出鏈在每個狀態起始的機率。如果你確定它從狀態 2 開始，那麼 mu_0 = (0, 1, 0, ...)；如果它均勻隨機開始，那每一格都是 1/N。
現在是奇妙之處。下一步狀態的分布，由矩陣乘積 mu_1 = mu_0 P 得到（列向量乘以矩陣）。為什麼成立？它其實只是全機率公式的化身：明天身處狀態 j 的機率，等於對今天每一個可能狀態 i 求和，每一項是（今天在 i 的機率）乘以（i 跳到 j 的機率）。對 i 求和的 mu_0(i) p_ij，恰恰就是乘積 mu_0 P 的第 j 個元素。預測就此化為了矩陣乘法。
- 把今天的信念寫成一個列向量 mu（它的元素是機率，所以加總為 1）。
- 在右邊乘上轉移矩陣：mu_next = mu P。結果依然是一個合法的分布（它的元素仍然加總為 1）。
- 重複以在時間上向前推進：兩步是 mu P P = mu P^2，n 步是 mu P^n。
- 在每一階段都檢查向量的元素非負且加總為 1；若不然，多半是 P 的某一列沒有加總為 1。
用上面那個天氣矩陣做一個小小的演算。假設今天必定是晴天，所以 mu_0 = (1, 0, 0)。那麼 mu_1 = mu_0 P 就直接讀出第一列：(0.7, 0.2, 0.1)——明天有 70% 的機率放晴。再隔一天，mu_2 = mu_1 P。它的晴天那一格是 0.7(0.7) + 0.2(0.3) + 0.1(0.2) = 0.49 + 0.06 + 0.02 = 0.57。請注意，確定性已經開始模糊：從一個保證放晴的起點，兩天之後晴天的機率已從 1 鬆弛到 0.57，正朝著你會在第 4 篇研究的長期平衡漂移。
鏈捕捉到了什麼——以及要留意什麼
為什麼這一個假設值得用一整個階段來講？因為只要狀態選得好，數量驚人的真實系統其實是誠實地無記憶的：一枚桌遊棋子、一副每次只洗一次牌的撲克、一位網路衝浪者所點的連結（PageRank 背後的點子）、服務櫃檯的排隊長度、在等位基因之間漂移的基因，以及隱馬可夫模型試圖解碼的字母序列。在每一個例子裡，當前狀態就「預測未來」這個目的而言，都是過去的一份充分摘要。找到這樣的狀態是建模的藝術；一旦找到，矩陣機器就會包辦其餘。
帶著三條線索走進這一階段的其餘部分。矩陣 P 握有一步的定律；把它升冪到 P^n，就會給出 n 步的定律，並直接通向第 2 篇的查普曼–柯爾莫哥洛夫方程式。P 的結構——哪些狀態能到達哪些狀態——將讓我們在第 3 篇把狀態分類為常返或瞬態。而長期行為——mu P^n 不論從哪裡出發，都安定下來趨向一個固定的平穩分布（你已經在天氣的例子裡看到那份模糊化的開端）——則是第 4 篇的目的地。下游的一切，都是關於同一個隨機矩陣的問題。