---
# System prepended metadata

title: Markov Chain

---

# Markov Chain
馬可夫鏈 (Markov Chain) 是一種數學模型，用來建立狀態轉換模型的數學工具。它被用於描述具有隨機變化的系統的動態行為，例如天氣、金融市場、語言等。

Markov Chain 是一種具有馬可夫性質（Markov Property）的隨機過程。所謂馬可夫性質，指的是==當前狀態的條件下，未來狀態的機率分佈只取決於當前狀態，而與過去狀態無關==。

# 1. 基本概念 (Basic Concepts)

### 1.1 狀態空間 (States Space)
系統中所有可能狀態的集合，分為以下兩類：

- ***有限空間 (Finite State Space)***  
 系統的狀態數量有限。
  EX：紅茶、綠茶、奶茶等有限的選項。

- ***無限空間 (Infinite State Space)***  
系統的狀態無限多或無法完全列舉。
  EX：隨機行走中的無限可能位置。

### 1.2 轉移矩陣 (Transition Matrix)

轉移矩陣為一個表示狀態之間轉移概率的矩陣。在 Markov Chain 中，==系統從一個狀態轉移到另一個狀態的機率由這個矩陣決定==。

- 定義系統從某個狀態 $i$ 在下一步轉移到狀態 $j$ 的機率 $P(i, j)$：

$P(i, j) = \Pr(X_{t+1} = j \mid X_t = i)$

- EX：
假設有三個飲料選擇：紅茶、綠茶、奶茶。
將這三個選擇變成轉移矩陣：

   | 狀態   | 紅茶 | 綠茶 | 奶茶 |
   |--------|------|------|------|
   | **紅茶** | 0.5  | 0.3  | 0.2  |
   | **綠茶** | 0.1  | 0.6  | 0.3  |
   | **奶茶** | 0.4  | 0.2  | 0.4  |
   
  在這個例子中，當前是紅茶，轉移到紅茶的機率是0.5，轉移到綠茶的機率是    0.3，轉移到奶茶的機率是 0.2。

- 特性：
 ==每一列的總和為 1==，因為每一列表示一個狀態轉移的所有可能結果。


#### 如何得到轉移矩陣？
- **觀察數據**：記錄系統從一個狀態轉移到另一個狀態的次數，並將這些數據轉換為機率。

### 1.3 無記憶性 (Memoryless Property)

Markov Chain 系統的**未來狀態僅取決於當前狀態**，與過去的歷史狀態無關。

- **數學表達**：
  $$
  P(X_{t+1} = j \mid X_t = i, X_{t-1}, \dots, X_0) = P(X_{t+1} = j \mid X_t = i)
  $$


# 2. 範例-商場購物行為
**商品區域** : 1、2、3
![](https://hackmd.io/_uploads/S1zT-2j11g.png)
圖 1：顧客在不同區域之間的轉移示意圖


- **轉移概率** : 
   - 若顧客在 1 區，80% 會留在 1 區，10% 會轉到 2 區，10% 會轉到 3 區。
   - 若顧客在 2 區，80% 會留在 2 區，10% 會轉到 1 區，10% 會轉到 3 區。
   - 若顧客在 3 區，80% 會留在 3 區，10% 會轉到 1 區，10% 會轉到 2 區。

- **轉移矩陣** :
\begin{aligned}
\text{P} = \begin{bmatrix}
0.8 & 0.1 & 0.1 \\
0.1 & 0.8 & 0.1 \\
0.1 & 0.1 & 0.8
\end{bmatrix}
\end{aligned}

- **初始狀態**：
  假設顧客 100% 從 1 區進去。
  \begin{aligned}
  \text{ $X_0$} = \begin{bmatrix}
  1 ,0, 0 
  \end{bmatrix}
  \end{aligned}
  
### 2.1 **單步轉移 (One-Step Transition)**

  - **計算公式**：
  $$X_1 = X_0 \cdot P$$

  - **步驟說明**：
   將初始狀態 $X_0$ 乘以轉移矩陣 $P$，即可計算，**下一步**各個狀態的機率。

  - **計算過程**：
  $$
  X_1 = \begin{bmatrix}
  1 & 0 & 0
  \end{bmatrix}
  \cdot
  \begin{bmatrix}
  0.8 & 0.1 & 0.1 \\
  0.1 & 0.8 & 0.1 \\
  0.1 & 0.1 & 0.8
  \end{bmatrix}
  =
  \begin{bmatrix}
  0.8 & 0.1 & 0.1
  \end{bmatrix}
  $$

  - **經過一步的結果**：
    -  80% 的機率去了 **1 區**。
    -  10% 的機率去了 **2 區**。
    -  10% 的機率去了 **3 區**。



#### **Python 程式範例**

```python
import numpy as np

# 定義轉移矩陣
P = np.array([[0.8, 0.1, 0.1],
              [0.1, 0.8, 0.1],
              [0.1, 0.1, 0.8]])

# 初始狀態向量 (100% 從 1 區開始)
X_0 = np.array([1, 0, 0])

# 計算一步後的狀態分佈
X_1 = np.dot(X_0, P)
print(f"一步之後的狀態分佈: {X_1}")
```


### 2.2 多步轉移 (Multiple Step Transition)
- **定義**：  
  多次轉移後的狀態變化。

  - **公式**：
  $$
  X_0 \cdot P^n = X_0 \cdot P \cdot P \cdot \dots \cdot P =X_n\quad 
  $$
  


 #### **Python 程式範例**：
 ```python
import numpy as np
import matplotlib.pyplot as plt

# 轉移矩陣
P = np.array([[0.8, 0.1, 0.1], 
              [0.1, 0.8, 0.1], 
              [0.1, 0.1, 0.8]])

# 初始狀態分佈
X_0 = np.array([0.1, 0.35, 0.55])

# 輸入要計算的步數
n_steps = int(input("請輸入要計算的步數："))


state_distributions = [X_0]  # 包含初始狀態分佈

for n in range(1, n_steps + 1):
    X_n = np.dot(state_distributions[-1], P)  # 計算下一步的狀態分佈
    state_distributions.append(X_n)


state_distributions = np.array(state_distributions)

plt.figure(figsize=(10, 6))
for i in range(P.shape[0]):  
    plt.plot(state_distributions[:, i], label=f" {i+1}")

plt.xlabel("step")
plt.ylabel("Probability")
plt.legend()
plt.grid(True)
plt.show()
```
###  2.3 穩態分佈 (Steady State Distribution)
- **定義**：  
  穩態分佈是一種長期平衡狀態，當經過無限多步後，==狀態的分佈不再隨時間改變==。

  - **公式**：
    $$
    \pi P = \pi \quad \text{且} \quad \sum_{i=1}^{n} \pi_i = 1
    $$
    其中 $\pi$ 是穩態分佈向量。

#### **Python 程式範例**：
```python
    # 計算穩態分佈
    eigvals, eigvecs = np.linalg.eig(P.T)
    steady_state = eigvecs[:, np.isclose(eigvals, 1)]
    steady_state = steady_state / np.sum(steady_state)
    print(f"穩態分佈: {steady_state.flatten()}")
```

---

# 3. 範例 - 隨機行走

- **定義**：
  隨機行走（Random Walk）是一種**無限狀態**的 Markov Chain，描述了系統或個體在每個時間步驟中，以隨機方式向左或向右移動一步的過程。
  
- **轉移概念**：
  - 在隨機行走中，每一步都有兩個可能的方向：
    - 以機率 $p$ 向右移動 $i + 1$。
    - 以機率 $1 - p$ 向左移動 $i - 1$。

- **轉移機率公式**：

  $$
  P(X_{t+1} = j \mid X_t = i) =
  \begin{cases}
  p & \text{若 } j = i + 1 \quad (\text{向右移動}) \\
  1 - p & \text{若 } j = i - 1 \quad (\text{向左移動})
  \end{cases}
  $$



#### **Python 程式碼範例**

```python
import matplotlib.pyplot as plt
import numpy as np

def random_walk(n_steps):
    steps = np.random.choice([-1, 1], size=n_steps)  
    position = np.cumsum(steps)  
    return position

n_steps = int(input("輸入行走的步數："))

position = random_walk(n_steps)

plt.plot(range(n_steps), position)
plt.title(f"1D Random Walk ({n_steps} steps)")
plt.xlabel("Steps")
plt.ylabel("Position")
plt.show()
```


# 4. Markov Chain的應用


### 應用概念
- **核心：**  
  當前像素的狀態只依賴於其「**鄰近像素**」的狀態，而與更遠的像素無關。
- **重點：**  
  分析像素之間的局部依賴關係，優化影像處理效果。



### 4.2 影像分割（Image Segmentation）

- **目標：** 將影像分為不同區域，如前景與背景。
- **方式：**  根據鄰近像素的顏色或紋理，透過轉移概率將像素標記為同一區域。


### 4.3 影像降噪（Image Denoising）
- **目標：** 去除影像中的噪點，保留重要細節。
- **方式：**  若像素與鄰居值差異過大，將其修正為鄰居的平均值。


### 4.4 影像恢復（Image Restoration）
- **目標：** 修復模糊或損壞的影像，還原原始內容。
- **方式：**  使用鄰近像素的資訊來推測缺失部分。

