从给定序列构建 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转移矩阵，其中 (i, j) 元素为，即在单个时间步中从一个状态转移到另一个状态的概率。PN x NP(X_1=j|X_0=i)ij

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

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

现在回顾一下，所需要的就是P根据给定的序列进行估计，然后估计P^{n}可以只使用已经估计的值P并取n矩阵的 1 次方。那么如何估计矩阵P呢？那么，如果我们表示从状态转换到状态N_{ij}的观察数量以及处于状态 的观察数量，那么。ijN_{i*}iP_{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 发生了多少次转换。