python - 从给定序列构建 N 阶马尔可夫转移矩阵

Question

我正在尝试创建一个函数，可以将给定的输入序列转换为请求顺序的转换矩阵。我找到了一阶马尔可夫转移矩阵的实现。

现在，我希望能够提出一个可以计算二阶和三阶转换矩阵的解决方案。

一阶矩阵实现示例:

import numpy as np

# sequence with 3 states -> 0, 1, 2

a = [0, 1, 0, 0, 0, 2, 2, 1, 1, 1, 0, 0, 0, 0, 0, 1, 2, 2, 2, 0, 0, 2]


def transition_matrix_first_order(seq):
    M = np.full((3, 3), fill_value = 1/3, dtype= np.float64)
    for (i,j) in zip(seq, seq[1:]):
        M[i, j] += 1

    M = M / M.sum(axis = 1, keepdims = True)

    return M

print(transition_matrix_first_order(a))

这给了我这个:

[[0.61111111 0.19444444 0.19444444]
 [0.38888889 0.38888889 0.22222222]
 [0.22222222 0.22222222 0.55555556]]

创建二阶矩阵时，它应该具有 unique_state_count ** order 行和 unique_state_count 列。在上面的示例中，我有 3 个独特的状态，因此矩阵将具有 9x3 结构。期望的功能示例:cal_tr_matrix(seq, unique_state_count, order)

Answer 1

我认为您对马尔可夫链及其转移矩阵有轻微的误解。

首先，不幸的是，您的函数生成的估计转移矩阵不正确。为什么？让我们刷新一下。

具有 N 个不同状态的离散时间的离散马尔可夫链具有大小为 N x N 的转移矩阵 P，其中 a (i , j) 元素为P(X_1=j|X_0=i)，即a中从状态i转移到状态j的概率单时间步长。

现在，n 阶的转换矩阵(表示为 P^{n})又是一个大小为 N x N 的矩阵，其中(i, j)元素为P(X_n=j|X_0=i)，即从状态i转换到状态j的概率在n个时间步内。

一个美妙的结果是:P^{n} = P^n，即采用单步转移矩阵的 n 次幂可以得到 n-步转移矩阵。

现在回顾一下，所需要的只是根据给定序列估计 P，然后估计 P^{n} 就可以使用已经估计的P 并取矩阵的 n 次方。那么如何估计矩阵P呢？好吧，如果我们将 N_{ij} 表示为从状态 i 转换到状态 j 的观察次数，并且 N_{i*} 处于状态 i 的观测值数量，则 P_{ij} = N_{ij}/N_{i*}。

Python 中的总体情况:

import numpy as np

def transition_matrix(arr, n=1):
    """"
    Computes the transition matrix from Markov chain sequence of order `n`.

    :param arr: Discrete Markov chain state sequence in discrete time with states in 0, ..., N
    :param n: Transition order
    """

    M = np.zeros(shape=(max(arr) + 1, max(arr) + 1))
    for (i, j) in zip(arr, arr[1:]):
        M[i, j] += 1

    T = (M.T / M.sum(axis=1)).T

    return np.linalg.matrix_power(T, n)

transition_matrix(arr=a, n=1)

>>> array([[0.63636364, 0.18181818, 0.18181818],
>>>       [0.4       , 0.4       , 0.2       ],
>>>       [0.2       , 0.2       , 0.6       ]])

transition_matrix(arr=a, n=2)

>>> array([[0.51404959, 0.22479339, 0.26115702],
>>>       [0.45454545, 0.27272727, 0.27272727],
>>>       [0.32727273, 0.23636364, 0.43636364]])

transition_matrix(arr=a, n=3)

>>> array([[0.46927122, 0.23561232, 0.29511645],
>>>       [0.45289256, 0.24628099, 0.30082645],
>>>       [0.39008264, 0.24132231, 0.36859504]])

有趣的是，当您将阶 n 设置为相当高的数字时，P 矩阵的越来越高的幂似乎会收敛到一些非常特定的值。这被称为马尔可夫链的平稳/不变分布，它很好地表明了该链在很长一段时间内/过渡期间的行为方式。另外:

P = transition_matrix(a, 1)
P111 = transition_matrix(a, 111)
print(P)
print(P111.dot(P))

编辑:现在根据您的评论调整解决方案，我建议使用更高维的矩阵来实现更高的阶数，而不是增加行数。一种方法是这样的:

def cal_tr_matrix(arr, order):

    _shape = (max(arr) + 1,) * (order + 1)
    M = np.zeros(_shape)

    for _ind in zip(*[arr[_x:] for _x in range(order + 1)]):
        M[_ind] += 1
    return M

res1 = cal_tr_matrix(a, 1)
res2 = cal_tr_matrix(a, 2)

现在元素 res1[i, j] 表示 i->j 发生了多少次转换，而元素 res2[i, j, k] 表示发生了多少次转换很多次 i->j->k 的转变发生了。