Марковские процессы являются примерами стохастических процессов - процессов, генерирующих случайные последовательности результатов или состояний в соответствии с определёнными вероятностями. Марковские процессы отличаются беспамятством - их следующее состояние зависит только от их нынешнего состояния, а не от истории, которая привела их туда. Модели марковских процессов используются в самых разнообразных применениях, от суточных цен на акции до положений генов в хромосоме.
Марковской модели дается визуальное представление с диаграммой состояний, такой как приведенная ниже.
Диаграмма состояния для модели Маркова
Прямоугольники на диаграмме представляют возможные состояния моделируемого процесса, а стрелки - переходы между состояниями. Метка на каждой стрелке представляет вероятность этого перехода. На каждом этапе процесса модель может генерировать выходной сигнал или излучение в зависимости от того, в каком состоянии она находится, и затем осуществлять переход в другое состояние. Важной характеристикой марковских моделей является то, что следующее состояние зависит только от текущего состояния, а не от истории переходов, ведущих к текущему состоянию.
Например, для последовательности подбрасывания монет двумя состояниями являются головы и хвосты. Самый последний подброс монеты определяет текущее состояние модели, а каждый последующий подброс определяет переход в следующее состояние. Если монета справедливая, вероятности перехода равны 1/2. Выброс может быть просто текущим состоянием. В более сложных моделях случайные процессы в каждом состоянии будут генерировать выбросы. Можно, например, свернуть штамп, чтобы определить выброс на любом этапе.
Цепи Маркова - математические описания марковских моделей с дискретным набором состояний. Цепи Маркова характеризуются:
Набор состояний {1, 2,..., M}
Матрица Т перехода M-на-M, запись i, j которой является вероятностью перехода из состояния i в состояние j. Сумма записей в каждой строке T должна быть равна 1, поскольку это сумма вероятностей перехода из заданного состояния в каждое из других состояний.
Набор возможных выходов, или выбросов, {s1, s2,..., sN}. По умолчанию набор выбросов равен {1, 2,..., N}, где N - количество возможных выбросов, но можно выбрать другой набор чисел или символов.
Матрица E излучения M-by-N, запись i, k которой дает вероятность излучения символа sk при условии, что модель находится в состоянии i.
Цепи Маркова начинаются в начальном состоянии i0 на шаге 0. Затем цепь переходит в состояние i1 с вероятностью T1i1 и выдает выходной сигнал sk1 с вероятностью Ei1k1. Следовательно, вероятность наблюдения последовательности состояний i1i2... последовательности выбросов sk1sk2.. первых шагах r равна
1irEirk