马尔可夫链

标签：Xj Pij Xi 0.1 马尔可夫 ij 晴天

马尔可夫链的简单讲述

文章目录

一、概念
二、头疼部分（可以略过
- 2.1 条件概率和全概率公式
- 2.2 状态转移矩阵
三、例子部分（以天气预报为例子
四、Java代码实现
- 4.1 定义MarkovChain类
- 4.2 展示
五、马尔可夫的收敛性

一、概念

1.1 马尔可夫性质（Markov property

当一个随机过程在给定现在状态及所有过去状态情况下，其未来状态的条件概率分布仅依赖于当前状态

以后什么样，只取决于现在什么样，跟以前什么样没关系

1.2 马尔可夫模型

是一种具有马尔可夫性质的统计模型，广泛应用在语音识别、词性自动标注、音字转换、概率文法等各个自然语言处理等应用领域。

1.3 马尔科夫链（Markov Chain

具有马尔可夫性质（Markov property）且存在于离散的指数集（index set）和状态空间（state space）内的随机过程（stochastic process）

马尔可夫链是最简单的马尔可夫模型

二、头疼部分（可以略过

2.1 条件概率和全概率公式

条件概率：就是 B B B发生的情况下 A A A发生的概率
数学表达： P ( A ∣ B ) = P ( A B ) / P ( B ) P(A|B) = P(AB)/P(B) P(A∣B)=P(AB)/P(B)

全概率公式： A A A发生的概率等于所有 B i B_i Bi发生下A发生的概率和（要求 B i B_i Bi两两互斥
数学表达： P ( A ) = P ( A ∣ B 1 ) P ( B 1 ) + P ( A ∣ B 2 ) P ( B 2 ) + . . . + P ( A ∣ B n ) P ( B n ) P(A) = P(A|B_1)P(B_1) + P(A|B_2)P(B_2) + ... + P(A|B_n)P(B_n) P(A)=P(A∣B1)P(B1)+P(A∣B2)P(B2)+...+P(A∣Bn)P(Bn)

2.2 状态转移矩阵

马尔可夫图例

状态 1 状态 2 状态 3 状态 1 P i j ( X j = 1 ∣ X i = 1 ) P i j ( X j = 1 ∣ X i = 2 ) P i j ( X j = 1 ∣ X i = 3 ) 状态 2 P i j ( X j = 2 ∣ X i = 1 ) P i j ( X j = 2 ∣ X i = 2 ) P i j ( X j = 2 ∣ X i = 3 ) 状态 3 P i j ( X j = 3 ∣ X i = 1 ) P i j ( X j = 3 ∣ X i = 2 ) P i j ( X j = 3 ∣ X i = 3 ) \begin{matrix} & 状态1 & 状态2 &状态3 \\ 状态1 & P_{ij}(X_j=1|X_i=1) &P_{ij}(X_j=1|X_i=2) & P_{ij}(X_j=1|X_i=3)\\ 状态2 & P_{ij}(X_j=2|X_i=1) & P_{ij}(X_j=2|X_i=2) & P_{ij}(X_j=2|X_i=3)\\ 状态3 & P_{ij}(X_j=3|X_i=1) & P_{ij}(X_j=3|X_i=2) & P_{ij}(X_j=3|X_i=3)\end {matrix} 状态1状态2状态3状态1Pij(Xj=1∣Xi=1)Pij(Xj=2∣Xi=1)Pij(Xj=3∣Xi=1)状态2Pij(Xj=1∣Xi=2)Pij(Xj=2∣Xi=2)Pij(Xj=3∣Xi=2)状态3Pij(Xj=1∣Xi=3)Pij(Xj=2∣Xi=3)Pij(Xj=3∣Xi=3)

P i j 代表从第 i 次到 j = i + 1 次时的转移概率。 P_{ij}代表从第i次到j=i+1次时的转移概率。 Pij代表从第i次到j=i+1次时的转移概率。

记第 i 次的状态概率为 X i = ( P i ( X i = 1 ) , P i ( X i = 2 ) , P i ( X i = 3 ) ) T 记第i次的状态概率为X^i=(P_i(X_i=1),P_i(X_i=2),P_i(X_i=3))^T 记第i次的状态概率为Xi=(Pi(Xi=1),Pi(Xi=2),Pi(Xi=3))T

记状态转移矩阵 A 33 A_{33} A33:

A 33 = P i j ( X j = 1 ∣ X i = 1 ) P i j ( X j = 1 ∣ X i = 2 ) P i j ( X j = 1 ∣ X i = 3 ) P i j ( X j = 2 ∣ X i = 1 ) P i j ( X j = 2 ∣ X i = 2 ) P i j ( X j = 2 ∣ X i = 3 ) P i j ( X j = 3 ∣ X i = 1 ) P i j ( X j = 3 ∣ X i = 2 ) P i j ( X j = 3 ∣ X i = 3 ) A_{33}=\begin{matrix} P_{ij}(X_j=1|X_i=1) &P_{ij}(X_j=1|X_i=2) & P_{ij}(X_j=1|X_i=3)\\P_{ij}(X_j=2|X_i=1) & P_{ij}(X_j=2|X_i=2) & P_{ij}(X_j=2|X_i=3)\\ P_{ij}(X_j=3|X_i=1) & P_{ij}(X_j=3|X_i=2) & P_{ij}(X_j=3|X_i=3)\end {matrix} A33=Pij(Xj=1∣Xi=1)Pij(Xj=2∣Xi=1)Pij(Xj=3∣Xi=1)Pij(Xj=1∣Xi=2)Pij(Xj=2∣Xi=2)Pij(Xj=3∣Xi=2)Pij(Xj=1∣Xi=3)Pij(Xj=2∣Xi=3)Pij(Xj=3∣Xi=3)

根据全概率公式有： P j ( X j = 1 ) = P i j ( X j = 1 ∣ X i = 1 ) P ( X i = 1 ) + P i j ( X j = 1 ∣ X i = 2 ) P ( X i = 2 ) + P i j ( X j = 1 ∣ X i = 3 ) P ( X i = 3 ) 根据全概率公式有：\\P_j(X_j=1)=P_{ij}(X_j=1|X_i=1)P(X_i=1)+P_{ij}(X_j=1|X_i=2)P(X_i=2)+P_{ij}(X_j=1|X_i=3)P(X_i=3) 根据全概率公式有：Pj(Xj=1)=Pij(Xj=1∣Xi=1)P(Xi=1)+Pij(Xj=1∣Xi=2)P(Xi=2)+Pij(Xj=1∣Xi=3)P(Xi=3)

则第 j 次 X j = X i + 1 = A X i , 根据学过的知识，我们知道如果给定初始状态 X 的概率，那么经过 λ 次转移后的 X λ = A λ X 则第j次X^j=X^{i+1}=AX^i,根据学过的知识，我们知道如果给定初始状态X的概率，那么经过\lambda次转移后的X^{\lambda}=A^{\lambda}X 则第j次Xj=Xi+1=AXi,根据学过的知识，我们知道如果给定初始状态X的概率，那么经过λ次转移后的Xλ=AλX

三、例子部分（以天气预报为例子

3.1 例子描述

假设每一天有且只有三种天气：晴天、阴天和雨天

已知：今天是晴天那么：

1.明天是晴天的概率是0.6
2.明天是阴天的概率是0.3
3.明天是雨天的概率是0.1

已知：今天是阴天那么：

1.明天是晴天的概率是0.1
2.明天是阴天的概率是0.4
3.明天是雨天的概率是0.5

已知：今天是雨天那么：

1.明天是晴天的概率是0.7
2.明天是阴天的概率是0.2
3.明天是雨天的概率是0.1

请预测未来n天的天气

3.2 例子转化数学语言

天气预报例子

晴天阴天雨天晴天 P i j ( X j = 晴天 ∣ X i = 晴天 ) = 0.6 P i j ( X j = 晴天 ∣ X i = 阴天 ) = 0.1 P i j ( X j = 晴天 ∣ X i = 雨天 ) = 0.7 阴天 P i j ( X j = 阴天 ∣ X i = 晴天 ) = 0.3 P i j ( X j = 阴天 ∣ X i = 阴天 ) = 0.4 P i j ( X j = 阴天 ∣ X i = 雨天 ) = 0.2 雨天 P i j ( X j = 雨天 ∣ X i = 晴天 ) = 0.1 P i j ( X j = 雨天 ∣ X i = 阴天 ) = 0.5 P i j ( X j = 雨天 ∣ X i = 雨天 ) = 0.1 \begin{matrix} & 晴天 & 阴天 &雨天\\ 晴天 & P_{ij}(X_j=晴天 |X_i=晴天 )=0.6 &P_{ij}(X_j=晴天 |X_i=阴天 )=0.1 & P_{ij}(X_j=晴天 |X_i=雨天)=0.7\\ 阴天 & P_{ij}(X_j=阴天 |X_i=晴天 )=0.3 & P_{ij}(X_j=阴天 |X_i=阴天 )=0.4 & P_{ij}(X_j=阴天 |X_i=雨天)=0.2\\ 雨天& P_{ij}(X_j=雨天|X_i=晴天 )=0.1 & P_{ij}(X_j=雨天|X_i=阴天 )=0.5 & P_{ij}(X_j=雨天|X_i=雨天)=0.1\end {matrix} 晴天阴天雨天晴天Pij(Xj=晴天∣Xi=晴天)=0.6Pij(Xj=阴天∣Xi=晴天)=0.3Pij(Xj=雨天∣Xi=晴天)=0.1阴天Pij(Xj=晴天∣Xi=阴天)=0.1Pij(Xj=阴天∣Xi=阴天)=0.4Pij(Xj=雨天∣Xi=阴天)=0.5雨天Pij(Xj=晴天∣Xi=雨天)=0.7Pij(Xj=阴天∣Xi=雨天)=0.2Pij(Xj=雨天∣Xi=雨天)=0.1

3.3 状态转移矩阵

A 33 = 0.6 0.1 0.7 0.3 0.4 0.2 0.1 0.5 0.1 A_{33}=\begin{matrix} 0.6&0.1 & 0.7\\0.3 & 0.4 & 0.2\\0.1 & 0.5 & 0.1\end {matrix} A33=0.60.30.10.10.40.50.70.20.1

可以知道今天，也就是 X = ( 1 , 0 , 0 ) T ，即晴天。或者 X = ( 0 , 1 , 0 ) T ，即阴天。或者 X = ( 0 , 0 , 1 ) T ，即雨天。可以知道今天，也就是\\X=(1,0,0)^T，即晴天。或者\\X=(0,1,0)^T，即阴天。或者\\X=(0,0,1)^T，即雨天。可以知道今天，也就是X=(1,0,0)T，即晴天。或者X=(0,1,0)T，即阴天。或者X=(0,0,1)T，即雨天。

以今天是晴天 X = ( 1 , 0 , 0 ) T 为例，预测明天的天气情况（以明天晴天的概率为例）：根据全概率公式可以知道明天是晴天的概率为： P j ( X j = 晴 ) = P i j ( X j = 晴 ∣ X i = 晴 ) P i ( X i = 晴 ) + P i j ( X j = 晴 ∣ X i = 阴 ) P i ( X i = 阴 ) + P i j ( X j = 晴 ∣ X i = 雨 ) P i ( X i = 雨 ) 以今天是晴天X=(1,0,0)^T为例，预测明天的天气情况（以明天晴天的概率为例）： \\根据全概率公式可以知道明天是晴天的概率为： \\P_j(X_j=晴)=P_{ij}(X_j=晴|X_i=晴)P_i(X_i=晴)+P_{ij}(X_j=晴|X_i=阴)P_i(X_i=阴)+P_{ij}(X_j=晴|X_i=雨)P_i(X_i=雨) 以今天是晴天X=(1,0,0)T为例，预测明天的天气情况（以明天晴天的概率为例）：根据全概率公式可以知道明天是晴天的概率为：Pj(Xj=晴)=Pij(Xj=晴∣Xi=晴)Pi(Xi=晴)+Pij(Xj=晴∣Xi=阴)Pi(Xi=阴)+Pij(Xj=晴∣Xi=雨)Pi(Xi=雨)

计算明天是晴天、阴天、雨天的具体概率
P j ( X j = 晴 ) = 0.6 × 1 + 0.1 × 0 + 0.7 × 0 = 0.6 P_j(X_j=晴)=0.6×1+0.1×0+0.7×0=0.6 Pj(Xj=晴)=0.6×1+0.1×0+0.7×0=0.6
P j ( X j = 阴 ) = 0.3 × 1 + 0.4 × 0 + 0.2 × 0 = 0.3 P_j(X_j=阴)=0.3×1+0.4×0+0.2×0=0.3 Pj(Xj=阴)=0.3×1+0.4×0+0.2×0=0.3
P j ( X j = 雨 ) = 0.1 × 1 + 0.5 × 0 + 0.1 × 0 = 0.1 P_j(X_j=雨)=0.1×1+0.5×0+0.1×0=0.1 Pj(Xj=雨)=0.1×1+0.5×0+0.1×0=0.1
得到明天的状态概率： X 1 = ( 0.6 , 0.3 , 0.1 ) X^1=(0.6,0.3,0.1) X1=(0.6,0.3,0.1)
即今天是晴天的情况下，明天是晴天的概率为0.6，阴天的概率为0.3，雨天的概率为0.1
可以通过条件轻易知道我们的预测是正确的

再来预测下后天的再来预测下后天的再来预测下后天的
P j ( X j = 晴 ) = 0.6 × 0.6 + 0.1 × 0.3 + 0.7 × 0.1 = 0.46 P_j(X_j=晴)=0.6×0.6+0.1×0.3+0.7×0.1=0.46 Pj(Xj=晴)=0.6×0.6+0.1×0.3+0.7×0.1=0.46
P j ( X j = 阴 ) = 0.3 × 0.6 + 0.4 × 0.3 + 0.2 × 0.1 = 0.32 P_j(X_j=阴)=0.3×0.6+0.4×0.3+0.2×0.1=0.32 Pj(Xj=阴)=0.3×0.6+0.4×0.3+0.2×0.1=0.32
P j ( X j = 雨 ) = 0.1 × 0.6 + 0.5 × 0.3 + 0.1 × 0.1 = 0.22 P_j(X_j=雨)=0.1×0.6+0.5×0.3+0.1×0.1=0.22 Pj(Xj=雨)=0.1×0.6+0.5×0.3+0.1×0.1=0.22
后天的状态概率： X 2 = ( 0.46 , 0.32 , 0.22 ) X^2=(0.46,0.32,0.22) X2=(0.46,0.32,0.22)
即今天是晴天的情况下，明天是晴天的概率为0.46，阴天的概率为0.32，雨天的概率为0.22

四、Java代码实现

4.1 定义MarkovChain类

public class MarkovChain {
    private double[][] state;
    private final double[][] stateTransitionMatrix;
    MarkovChain(double[][] state,double[][] stateTransitionMatrix){
        this.state = state;
        this.stateTransitionMatrix = stateTransitionMatrix;
    }

    private static double[][] multiply(double[][] matrix1, double[][] matrix2) {
        if (matrix1[0].length != matrix2.length) {
            throw new IllegalArgumentException("第一个矩阵的列得等于第二个矩阵的行");
        }

        int rows1 = matrix1.length;
        int cols1 = matrix1[0].length;
        int cols2 = matrix2[0].length;
        double[][] result = new double[rows1][cols2];

        for (int i = 0; i < rows1; i++) {
            for (int j = 0; j < cols2; j++) {
                for (int k = 0; k < cols1; k++) {
                    result[i][j] += matrix1[i][k] * matrix2[k][j];
                }
            }
        }
        return result;
    }

    public double[][] markovChain(int n){
        if(n<0){
            throw new IllegalArgumentException("别搞事情，你让预知过去？");
        }

        if(n==0){
            return this.state;
        }else{
            return multiply(markovChain(n-1),this.stateTransitionMatrix);
        }
    }

    public double[][] getState() {
        return state;
    }

    public void setState(double[][] state) {
        this.state = state;
    }
}

4.2 展示

import java.util.Arrays;

public class Demo {
    public static void main(String[] args) {
        //三个（晴，阴，雨）的状态。
        //一个(晴晴，晴阴，晴雨）
        //   (阴晴，阴阴，阴雨）
        //   (雨晴，雨阴，雨雨）的状态转移矩阵
        double[][] state_01 = {{1,0,0}};
        double[][] state_02 = {{0,1,0}};
        double[][] state_03 = {{0,0,1}};
        double[][] stateTransitionMatrix = {{0.6,0.3,0.1},{0.1,0.4,0.5},{0.7,0.2,0.1}};
        //默认晴状态创建
        MarkovChain mc = new MarkovChain(state_01, stateTransitionMatrix);
        System.out.println(Arrays.deepToString(mc.markovChain(1)));
        System.out.println(Arrays.deepToString(mc.markovChain(2)));
        //确认状态输出100天后的预测结果
        System.out.println("-----分割线-----");
        System.out.println(Arrays.deepToString(mc.getState()));
        System.out.println(Arrays.deepToString(mc.markovChain(30)));
        System.out.println("-----分割线-----");
        System.out.println(Arrays.deepToString(mc.getState()));
        System.out.println(Arrays.deepToString(mc.markovChain(50)));
        System.out.println("-----分割线-----");
        System.out.println(Arrays.deepToString(mc.getState()));
        System.out.println(Arrays.deepToString(mc.markovChain(100)));
        //下一个状态
        System.out.println("-----分割线-----");
        mc.setState(state_02);
        System.out.println(Arrays.deepToString(mc.getState()));
        System.out.println(Arrays.deepToString(mc.markovChain(100)));
        //下一个状态
        System.out.println("-----分割线-----");
        mc.setState(state_03);
        System.out.println(Arrays.deepToString(mc.getState()));
        System.out.println(Arrays.deepToString(mc.markovChain(100)));
    }
}

五、马尔可夫的收敛性

上述代码尝试n=100,200,300发现后面结果相同了。这就是收敛性。

马尔可夫链的收敛性是其重要的性质之一。如果确定了马尔科夫链模型的状态转移矩阵P，以及一个初始状态，那么按照P转移n次后，马尔可夫链可能会收敛于一个特定的数或分布。这种收敛性在排名算法、概率计算等领域有广泛的应用。

东西很简单，但是我觉得思想很重要，状态和状态转移可以应用到很多地方上。

标签：Xj,Pij,Xi,0.1,马尔可夫,ij,晴天
From： https://blog.csdn.net/qq_52515420/article/details/136604585

文章目录

一、概念

1.1 马尔可夫性质（Markov property

1.2 马尔可夫模型

1.3 马尔科夫链（Markov Chain

二、头疼部分（可以略过

2.1 条件概率和全概率公式

2.2 状态转移矩阵

三、例子部分（以天气预报为例子

3.1 例子描述

3.2 例子转化数学语言

3.3 状态转移矩阵

四、Java代码实现

4.1 定义MarkovChain类

4.2 展示

五、马尔可夫的收敛性

相关文章

赞助商

阅读排行

马尔可夫链

文章目录

一、概念

1.1 马尔可夫性质（Markov property

1.2 马尔可夫模型

1.3 马尔科夫链（Markov Chain

二、头疼部分（可以略过

2.1 条件概率和全概率公式

2.2 状态转移矩阵

三、 例子部分（以天气预报为例子

3.1 例子描述

3.2 例子转化数学语言

3.3 状态转移矩阵

四、Java代码实现

4.1 定义MarkovChain类

4.2 展示

五、马尔可夫的收敛性

相关文章

赞助商

阅读排行

三、例子部分（以天气预报为例子