Цепь Маркова — последовательность случайных событий с конечным или счётным числом исходов, характеризующаяся тем, что при фиксированном настоящем будущее независимо от прошлого.
Процесс в каждый момент времени находится в одном из n состояний.
При этом, если он находится в состоянии с номером i, то он перейдет в состояние j с вероятностью pij.
Матрицу P = 2 вертикал полосы pij 2 вертикал полосы называют матрицей переходов.
Марковскую цепь можно представить в виде графа, в котором вершины — это состояния процесса, а ребра — переходы между состояниями, и на ребре из i в j написана вероятность перехода из i в j, то есть pij.
Марковскую цепь в любой момент времени t можно охарактеризовать вектором-строкой ct — распределением вероятностей по состояниям цепи (cti — вероятность цепи в момент времени t быть в состоянии i).
Если ci — текущее распределение вероятностей, то можно узнать распределение на следующем шаге, умножив вектор на матрицу перехода:
ci + 1 = ci x P
Из ассоциативности произведения матриц следует, что для того, чтобы узнать распределение вероятностей через t шагов, нужно умножить ci на матрицу перехода, возведённую в степень t:
ci + t = ci x P^t
Для марковской цепи иногда задают начальное распределение c0, хотя во многих классах марковских цепей распределение по прошествии большого периода времени от него не зависит (такое распределение называют предельным).
