Цепи Маркова — это мощные математические модели, используемые для анализа систем, демонстрирующих случайное поведение. Одним из важных понятий цепей Маркова является среднее время первого прохождения (MFPT), которое измеряет ожидаемое время, необходимое системе для перехода из одного состояния в другое. В этой статье мы углубимся в различные методы расчета MFPT в цепях Маркова с использованием Python, а также приведем примеры кода.

Метод 1: Метод прямого решения
Метод прямого решения включает решение системы линейных уравнений для получения МФПТ. Вот пример фрагмента кода:

import numpy as np
def calculate_mfpt_direct(P, source_state, target_state):
    num_states = P.shape[0]
    I = np.eye(num_states)
    Q = P - I
    Q[:, target_state] = 0
    Q[source_state, :] = 0
    Q[source_state, source_state] = 1
    return np.linalg.solve(Q, np.ones(num_states))[source_state]
# Example usage
P = np.array([[0.2, 0.3, 0.5], [0.1, 0.4, 0.5], [0.3, 0.2, 0.5]])
source_state = 0
target_state = 2
mfpt = calculate_mfpt_direct(P, source_state, target_state)
print(f"MFPT from state {source_state} to state {target_state}: {mfpt}")

Метод 2: Метод моделирования случайного блуждания
Метод моделирования случайного блуждания включает в себя моделирование многочисленных случайных блужданий в цепи Маркова и усреднение времени, необходимого для достижения целевого состояния. Вот пример фрагмента кода:

import numpy as np
def calculate_mfpt_simulation(P, source_state, target_state, num_walks=10000, max_steps=1000):
    num_states = P.shape[0]
    mfpt_sum = 0
    for _ in range(num_walks):
        current_state = source_state
        steps = 0
        while current_state != target_state and steps < max_steps:
            current_state = np.random.choice(range(num_states), p=P[current_state])
            steps += 1
        if current_state == target_state:
            mfpt_sum += steps
    return mfpt_sum / num_walks
# Example usage
P = np.array([[0.2, 0.3, 0.5], [0.1, 0.4, 0.5], [0.3, 0.2, 0.5]])
source_state = 0
target_state = 2
mfpt = calculate_mfpt_simulation(P, source_state, target_state)
print(f"MFPT from state {source_state} to state {target_state}: {mfpt}")

Метод 3: Метод обращения матрицы
Метод обращения матрицы включает в себя вычисление фундаментальной матрицы цепи Маркова и выполнение обращения матрицы для получения MFPT. Вот пример фрагмента кода:

import numpy as np
def calculate_mfpt_matrix_inversion(P, source_state, target_state):
    num_states = P.shape[0]
    Q = P[:-1, :-1]
    I = np.eye(num_states - 1)
    F = np.linalg.inv(I - Q)
    return np.sum(F[source_state, :])
# Example usage
P = np.array([[0.2, 0.3, 0.5], [0.1, 0.4, 0.5], [0.3, 0.2, 0.5]])
source_state = 0
target_state = 2
mfpt = calculate_mfpt_matrix_inversion(P, source_state, target_state)
print(f"MFPT from state {source_state} to state {target_state}: {mfpt}")

В этой статье мы исследовали три различных метода расчета среднего времени первого прохождения в цепях Маркова: метод прямого решения, метод моделирования случайного блуждания и метод обращения матрицы. Каждый метод предлагает уникальный подход к вычислению MFPT, и выбор метода зависит от конкретной проблемы и характеристик рассматриваемой цепи Маркова. Используя Python, мы можем легко реализовать эти методы и получить ценную информацию о поведении сложных систем.