Цепи Маркова

Коротко: Цепь Маркова — случайный процесс, в котором следующее состояние зависит только от текущего, а не от предыдущей истории.

Подробнее: Описывается вероятностями переходов между состояниями. Пример: погода, которая завтра с вероятностью 70 % остаётся такой же, как сегодня.

Подробности

• Марковское свойство: «отсутствие памяти». Будущее зависит только от настоящего.
• Матрица переходов: Матрица P, строка i которой содержит вероятности перехода из состояния i во все остальные. Каждая строка в сумме даёт 1.
• Стационарное распределение: В долгосрочной перспективе многие цепи устанавливаются на фиксированную долю для каждого состояния. На этом основан исходный метод PageRank (случайный сёрфер).
• Применение: Простая генерация текста (следующее слово из текущего), модели очередей, распознавание речи (скрытые марковские модели), MCMC-выборка.
• Предел: Если будущее зависит от более ранних шагов, нужны более крупные состояния или другие модели. Современные языковые модели идут далеко за эти рамки.

См. также: методы Монте-Карло