马尔可夫链（Markov Chain）是一种描述状态转移的随机过程，其核心假设是”未来只依赖于现在，与过去无关”。本文以随机文本生成为切入点，深入讲解马尔可夫链的原理、矩阵运算，并给出完整的Java实现。
马尔可夫链的核心概念
什么是马尔可夫链
马尔可夫链是一个随机过程 ${X_n}$，满足马尔可夫性质：
$$P(X_{n+1} = s | X_n = s_n, X_{n-1} = s_{n-1}, …, X_0 = s_0) = P(X_{n+1} = s | X_n = s_n)$$
简单说：下一状态只取决于当前状态，与历史无关。
关键要素
- 状态空间 $S$：所有可能状态的集合
- 转移概率矩阵 $P$：$P_{ij}$ 表示从状态 $i$ 转移到状态 $j$ 的概率
- 初始分布 $\pi_0$：初始时刻各状态的概率分布
n步转移与稳态分布
- n步转移矩阵：$P^{(n)} = P^n$（矩阵的n次幂）
- 稳态分布 $\pi$：满足 $\pi = \pi P$，即经过足够长时间后状态分布不再变化
场景：基于马尔可夫链的随机文本生成
核心思路
将文本中的单词视为状态，通过统计语料库中单词间的转移频率，构建转移概率矩阵。生成新文本时，从当前单词出发，按照转移概率随机选择下一个单词。
Java实现
import java.util.*;
/**
* 基于马尔可夫链的随机文本生成器
* 支持一阶和二阶马尔可夫模型
*/
public class MarkovTextGenerator {
/**
* 一阶马尔可夫模型：下一个词只依赖当前词
*/
static class MarkovModel {
// 状态转移图：当前词 -> (下一个词 -> 出现次数)
Map<String, Map<String, Integer>> transitions = new HashMap<>();
Map<String, Integer> totalCounts = new HashMap<>(); // 每个状态的总转移次数
Set<String> vocabulary = new HashSet<>();
/**
* 从文本训练模型
*/
void train(String text) {
String[] words = tokenize(text);
if (words.length < 2) return;
for (int i = 0; i < words.length - 1; i++) {
String current = words[i];
String next = words[i + 1];
vocabulary.add(current);
vocabulary.add(next);
transitions.computeIfAbsent(current, k -> new HashMap<>())
.merge(next, 1, Integer::sum);
totalCounts.merge(current, 1, Integer::sum);
}
}
/**
* 从多个文档训练
*/
void train(List<String> documents) {
for (String doc : documents) {
train(doc);
}
}
/**
* 获取下一个词的概率分布
*/
Map<String, Double> getTransitionProbabilities(String word) {
Map<String, Double> probs = new HashMap<>();
Map<String, Integer> counts = transitions.get(word);
if (counts == null) return probs;
int total = totalCounts.getOrDefault(word, 0);
for (Map.Entry<String, Integer> entry : counts.entrySet()) {
probs.put(entry.getKey(), entry.getValue() / (double) total);
}
return probs;
}
/**
* 根据概率随机选择下一个词
*/
String predictNext(String word, Random random) {
Map<String, Integer> counts = transitions.get(word);
if (counts == null || counts.isEmpty()) {
// 随机返回一个词汇表中的词
List<String> vocabList = new ArrayList<>(vocabulary);
return vocabList.get(random.nextInt(vocabList.size()));
}
int total = totalCounts.get(word);
int threshold = random.nextInt(total);
int cumulative = 0;
for (Map.Entry<String, Integer> entry : counts.entrySet()) {
cumulative += entry.getValue();
if (cumulative > threshold) {
return entry.getKey();
}
}
return counts.keySet().iterator().next();
}
/**
* 生成文本
*/
String generate(String startWord, int length, Random random) {
StringBuilder sb = new StringBuilder(startWord);
String current = startWord;
for (int i = 0; i < length - 1; i++) {
current = predictNext(current, random);
sb.append(" ").append(current);
}
return sb.toString();
}
}
/**
* 二阶马尔可夫模型：下一个词依赖前两个词
* 生成的文本更连贯
*/
static class SecondOrderModel {
// (word_i, word_{i+1}) -> word_{i+2} 的转移计数
Map<String, Map<String, Integer>> transitions = new HashMap<>();
Map<String, Integer> totalCounts = new HashMap<>();
Set<String> starts = new HashSet<>(); // 可能的起始二元组
void train(String text) {
String[] words = tokenize(text);
if (words.length < 3) return;
for (int i = 0; i < words.length - 2; i++) {
String key = words[i] + " " + words[i + 1];
String next = words[i + 2];
transitions.computeIfAbsent(key, k -> new HashMap<>())
.merge(next, 1, Integer::sum);
totalCounts.merge(key, 1, Integer::sum);
if (i == 0) starts.add(key);
}
}
void train(List<String> documents) {
for (String doc : documents) {
train(doc);
}
}
String predictNext(String word1, String word2, Random random) {
String key = word1 + " " + word2;
Map<String, Integer> counts = transitions.get(key);
if (counts == null || counts.isEmpty()) {
return word2; // 回退到一阶
}
int total = totalCounts.get(key);
int threshold = random.nextInt(total);
int cumulative = 0;
for (Map.Entry<String, Integer> entry : counts.entrySet()) {
cumulative += entry.getValue();
if (cumulative > threshold) {
return entry.getKey();
}
}
return counts.keySet().iterator().next();
}
String generate(int length, Random random) {
// 随机选择起始二元组
List<String> startList = new ArrayList<>(starts);
String[] current = startList.get(random.nextInt(startList.size())).split(" ");
StringBuilder sb = new StringBuilder(current[0]).append(" ").append(current[1]);
for (int i = 0; i < length - 2; i++) {
String next = predictNext(current[0], current[1], random);
sb.append(" ").append(next);
current[0] = current[1];
current[1] = next;
}
return sb.toString();
}
}
/**
* 文本预处理：分词并规范化
*/
private static String[] tokenize(String text) {
// 转换为小写，保留字母和基本标点
text = text.toLowerCase()
.replaceAll("[^a-z\\s]", "")
.replaceAll("\\s+", " ")
.trim();
return text.split(" ");
}
// ==================== 马尔可夫链数学分析 ====================
/**
* 计算转移概率矩阵
*/
static class MarkovChainAnalyzer {
/**
* 计算矩阵的n次幂（用于n步转移概率）
* 使用快速幂算法，时间复杂度 O(k^3 log n)，k为状态数
*/
public static double[][] matrixPower(double[][] matrix, int n) {
int size = matrix.length;
double[][] result = identityMatrix(size);
double[][] base = copyMatrix(matrix);
while (n > 0) {
if ((n & 1) == 1) {
result = matrixMultiply(result, base);
}
base = matrixMultiply(base, base);
n >>= 1;
}
return result;
}
/**
* 矩阵乘法
*/
public static double[][] matrixMultiply(double[][] a, double[][] b) {
int n = a.length;
double[][] result = new double[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (int k = 0; k < n; k++) {
result[i][j] += a[i][k] * b[k][j];
}
}
}
return result;
}
/**
* 单位矩阵
*/
public static double[][] identityMatrix(int n) {
double[][] matrix = new double[n][n];
for (int i = 0; i < n; i++) {
matrix[i][i] = 1.0;
}
return matrix;
}
/**
* 复制矩阵
*/
public static double[][] copyMatrix(double[][] matrix) {
int n = matrix.length;
double[][] copy = new double[n][n];
for (int i = 0; i < n; i++) {
copy[i] = matrix[i].clone();
}
return copy;
}
/**
* 打印矩阵
*/
public static void printMatrix(double[][] matrix, String name) {
System.out.println("\\n" + name + ":");
for (double[] row : matrix) {
for (double val : row) {
System.out.printf("%.4f ", val);
}
System.out.println();
}
}
}
public static void main(String[] args) {
Random random = new Random(42); // 固定种子保证可复现
// 训练语料：简单的天气描述文本
List<String> corpus = Arrays.asList(
"the sun is shining and the sky is blue",
"the sun is bright and the weather is warm",
"the sky is blue and the sun is shining",
"the weather is warm and the sun is bright",
"the sun is shining and the day is beautiful",
"the sky is clear and the sun is warm",
"the day is beautiful and the weather is nice",
"the weather is nice and the sky is blue"
);
System.out.println("=== 一阶马尔可夫模型 ===");
MarkovModel model1 = new MarkovModel();
model1.train(corpus);
System.out.println("词汇表大小: " + model1.vocabulary.size());
System.out.println("转移状态数: " + model1.transitions.size());
System.out.println("\\n从 'the' 开始的转移概率:");
Map<String, Double> probs = model1.getTransitionProbabilities("the");
probs.entrySet().stream()
.sorted(Map.Entry.<String, Double>comparingByValue().reversed())
.forEach(e -> System.out.printf(" %s -> %.2f%%\n", e.getKey(), e.getValue() * 100));
System.out.println("\\n生成文本（一阶模型）:");
for (int i = 0; i < 5; i++) {
String generated = model1.generate("the", 10, random);
System.out.println(" " + generated);
}
System.out.println("\\n=== 二阶马尔可夫模型 ===");
SecondOrderModel model2 = new SecondOrderModel();
model2.train(corpus);
System.out.println("生成文本（二阶模型，更连贯）:");
for (int i = 0; i < 5; i++) {
String generated = model2.generate(10, random);
System.out.println(" " + generated);
}
// 马尔可夫链数学分析演示
System.out.println("\\n=== 马尔可夫链数学分析 ===");
System.out.println("以简化的三状态天气模型为例：");
System.out.println("状态 0: 晴天, 状态 1: 多云, 状态 2: 雨天");
// 转移概率矩阵
double[][] P = {
{0.7, 0.2, 0.1}, // 晴天 -> 晴天/多云/雨天
{0.3, 0.4, 0.3}, // 多云 -> 晴天/多云/雨天
{0.2, 0.3, 0.5} // 雨天 -> 晴天/多云/雨天
};
MarkovChainAnalyzer.printMatrix(P, "一步转移矩阵 P");
// 计算n步转移矩阵
double[][] P2 = MarkovChainAnalyzer.matrixPower(P, 2);
MarkovChainAnalyzer.printMatrix(P2, "两步转移矩阵 P²");
double[][] P10 = MarkovChainAnalyzer.matrixPower(P, 10);
MarkovChainAnalyzer.printMatrix(P10, "十步转移矩阵 P¹⁰（接近稳态）");
// 验证行和为1
System.out.println("\\n验证：P¹⁰ 每行和为1（合法概率分布）");
for (int i = 0; i < 3; i++) {
double sum = 0;
for (int j = 0; j < 3; j++) {
sum += P10[i][j];
}
System.out.printf(" 行 %d 和: %.6f\n", i, sum);
}
System.out.println("\\n稳态分布（从任意状态出发，长期概率趋于相同）:");
System.out.printf(" P(晴天) = %.4f\n", P10[0][0]);
System.out.printf(" P(多云) = %.4f\n", P10[0][1]);
System.out.printf(" P(雨天) = %.4f\n", P10[0][2]);
}
}
从文本生成到预测模型
状态转移概率的统计学习
马尔可夫链的强大之处在于从数据中学习转移规律：
- 最大似然估计：转移概率 $P_{ij} = \frac{\text{从状态}i\text{到状态}j\text{的观测次数}}{\text{状态}i\text{的总出现次数}}$
- 平滑处理：对于未观测到的转移，使用拉普拉斯平滑避免零概率
- 高阶模型：二阶、三阶模型可以捕捉更长距离的依赖关系
与隐马尔可夫模型（HMM）的关系
当状态不可直接观测，只能通过观测序列推断时，就进入了隐马尔可夫模型的领域。HMM在语音识别、自然语言处理中有广泛应用，而本文的一阶/二阶马尔可夫模型可视为HMM的简化形式。
应用场景
| 领域 | 应用 | 状态定义 |
|---|---|---|
| 自然语言处理 | 文本生成、输入法预测 | 单词或字符 |
| 天气预测 | 明天天气预测 | 天气类型 |
| 金融市场 | 股价趋势分析 | 涨跌状态 |
| 生物信息学 | DNA序列分析 | 碱基对 |
| 用户行为 | 网页点击流预测 | 访问的页面 |
| 游戏AI | NPC行为模式 | 行为状态 |
复杂度分析
| 操作 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 训练（一阶） | O(L) | O(V²) |
| 生成（一阶） | O(k) | O(1) |
| n步转移矩阵 | O(S³ log n) | O(S²) |
其中 L 为训练文本总长度，V 为词汇表大小，k 为生成长度，S 为状态数。
总结
马尔可夫链用极简的假设——无记忆性——构建了一个强大的概率模型。从随机文本生成到稳态分析，它展示了如何用矩阵运算和概率统计来理解和预测复杂系统的行为。掌握马尔可夫链，是进入随机过程与概率图论世界的重要一步。
