概念

马尔可夫链（Markov Chain）是一种随机过程，它描述了一个系统在给定当前状态下，未来状态的概率分布仅依赖于当前状态，而与过去的状态无关。

原理

马尔可夫链的原理基于马尔可夫性质，即系统的下一个状态只与当前状态有关，与之前的状态无关。这一性质可以用转移概率矩阵来表示。

步骤

1. 定义状态空间。
2. 构建转移概率矩阵。
3. 选择一个初始状态。
4. 根据转移概率矩阵计算下一个状态。
5. 重复步骤4，直到达到所需的迭代次数或稳态。

分类

1. 离散时间马尔可夫链（DTMC）：状态转移发生在离散的时间点上。
2. 连续时间马尔可夫链（CTMC）：状态转移可以发生在任何时间点。

用途

• 预测天气变化
• 经济模型分析
• 股票市场预测
• 机器学习中的隐马尔可夫模型（HMM）

C语言代码实现

#include <stdio.h>
#include <stdlib.h>
#define STATES 3 // 状态数量
// 转移概率矩阵
double transitionMatrix[STATES][STATES] = {
    {0.5, 0.2, 0.3},
    {0.3, 0.5, 0.2},
    {0.2, 0.3, 0.5}
};
// 计算下一个状态
int getNextState(double probabilities[], int currentState) {
    double cumulativeProbability = 0.0;
    double randomValue = (double)rand() / RAND_MAX; // 生成[0,1]之间的随机数
    for (int i = 0; i < STATES; ++i) {
        cumulativeProbability += probabilities[i];
        if (randomValue <= cumulativeProbability) {
            return i;
        }
    }
    return currentState; // 如果出现误差，返回当前状态
}
// 马尔可夫链的模拟
void simulateMarkovChain(int steps) {
    int currentState = 0; // 初始状态
    printf("状态序列: %d", currentState);
    for (int i = 0; i < steps; ++i) {
        currentState = getNextState(transitionMatrix[currentState], currentState);
        printf(" -> %d", currentState);
    }
    printf("\n");
}
int main() {
    int steps = 10; // 模拟的步数
    simulateMarkovChain(steps);
    return 0;
}

时间复杂度和空间复杂度分析

• 时间复杂度：模拟马尔可夫链的时间复杂度主要取决于模拟的步数steps。每一步需要计算下一个状态，其时间复杂度为O(S)，其中S是状态的数量。因此，总的时间复杂度为O(S * steps)。
• 空间复杂度：空间复杂度主要取决于存储转移概率矩阵所需的内存，即O(S^{2)。此外，还需要O(S)的额外空间来存储每个状态的转移概率，所以总的空间复杂度仍然是O(S}2)。