# 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
圖 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）
- **目標：** 修復模糊或損壞的影像，還原原始內容。
- **方式：** 使用鄰近像素的資訊來推測缺失部分。
Sign in with Wallet
Connect another wallet