Цепь Маркова

Материал из NLPub
(перенаправлено с «Марковская цепь»)
Перейти к: навигация, поиск

Цепь Маркова -- последовательность событий с конечным или счетным числом исходов. Характеризуется тем, что каждое следующее значение зависит только от k предыдущих. Названа в честь А. А. Маркова, который и описал это понятие.

Определение

Последовательность дискретных случайных величин называется цепью Маркова порядка k, если:

\mathbb{P}(X_{n+1} = i_{n+1} \mid X_n = i_n, X_{n-1} = i_{n-1},\ldots,  X_0 = i_0) = \mathbb{P}(X_{n+1} = i_{n+1} \mid X_n = i_n, \ldots , X_{n-k+1} = i_{n-k+1})

Другими словами, для каждого состояния важны только предыдущие k значений последовательности, а не все, как в общем случае для последовательностей случайных величин.

Марковская цепь нулевого порядка

Марковская цепь нулевого порядка -- марковская цепь, в котором каждое следующее состояние зависит только от предыдущего, поэтому формулу выше можно упростить таким образом:

\mathbb{P}(X_{n+1} = i_{n+1} \mid X_n = i_n, X_{n-1} = i_{n-1},\ldots,  X_0 = i_0) = \mathbb{P}(X_{n+1} = i_{n+1} \mid X_n = i_n)

Обычно применяют марковские цепи не выше второго порядка, поскольку на практике знание цепочки состояний длиной больше трех не дает почти никакого выигрыша.


Генерация марковских цепей

Чтобы сгенерировать марковскую цепь, как следует из определения, нужно знать вероятность каждого следующего шага в зависимости от k предыдущих.

Входные данные

Одним из удобных способов организовать входные данные является дерево следующего вида.

  1. Корень дерева -- вспомогательный символ, который должен связать все слова.
  2. Узел дерева состоит из значения, вероятности своего появления и массива ссылок на потомков.
  3. Глубина дерева -- k.

Алгоритм генерации

  1. Выбрать первые k объектов.
  2. Выбирать каждый следующий объект как лист дерева, причем предки листа -- предыдущие k объектов.
  3. Если необходимое количество объектов выбрано, закончить, иначе перейти к шагу 2.

Пример генератора

Примером генератора, построенного по данному алгоритму, является гем Love is ...