МАРКОВСКИЕ ЦЕПИ
Первым описал возможности применения Марковских цепей русский математик Андрей Андреевич Марков. Марковские цепи — это последовательности случайных величин, для которых вероятность появления того или иного значения на (k + 1)–м шагу зависит лишь от того, какое значение эта величина приняла на k–м шагу, и не зависит от значений величины на 1–м, 2–м, ..., (k — 1)–м шагах.
Цепью Маркова называют такую последовательность случайных событий, в которой вероятность каждого события зависит только от состояния, в котором процесс находится в текущий момент и не зависит от более ранних состояний. Конечная дискретная цепь определяется:
1. Множеством состояний S = {s1, …, sn}, событием является переход из одного состояния в другое в результате случайного испытания.
2. Вектором начальных вероятностей (начальным распределением) p(0) = {p(0)(1),…, p(0)(n)}, определяющим вероятности p(0)(i) того, что в начальный момент времени t = 0 процесс находился в состоянии si ;
3. Матрицей переходных вероятностей P = {pij}, характеризующей вероятность перехода процесса с текущим состоянием si в следующее состояние sj, при этом сумма вероятностей переходов из одного состояния равна 1:
∑j=1…n pij = 1 |
Использование Марковских цепей предполагает наличие матрицы переходных вероятностей, где каждая колонка позволяет определить вероятность наступления события исходя из того, какое событие было предыдущим.
![Пример матрицы переходных вероятностей](img/image256.jpg)
Пример матрицы переходных вероятностей
Марковская цепь может быть представлена графом, вершины которого соответствуют состояниям цепи, а дуги — ненулевым вероятностям переходов. На рисунке иже представлен граф Марковской цепи, имеющей 5 состояний и вектор начальных вероятностей {1;0;0;0;0}. Вероятности переходов показаны на дугах графа.
![пример представления Марковской цепи в виде графа](img/image258.png)
пример представления Марковской цепи в виде графа
Для генерации алгоритмических композиций также безусловно приемлемы и Марковские цепи более высоких порядков — например, второго. Цепью второго порядка называют такую цепь, в которой вероятность перехода в последующее состояние зависит как от двух предшествующих, так и от той последовательности, в которой эти состояния наступают (предшествующие состояния записаны в первом столбце).
![пример матрицы переходных вероятностей второго порядка для четырех нот](img/2015-07-06_151225.jpg)
пример матрицы переходных вероятностей второго порядка для четырех нот
Интерес представляет и так называемая Цепь Маркова со случайным блужданием (вероятностная матрица этой цепи имеет ненулевые значения на всех сторонах главной диагонали и нулевые на остальных):
![Цепь Маркова со случайным блужданием](img/2015-07-06_151256.jpg)
Цепь Маркова со случайным блужданием
Возможности Марковских цепей могут быть расширены за счет использования более сложных техник:
1) описание событием не какого–то одного значения, например, ноты, а нескольких параметров одновременно — продолжительности, динамики, силы и т.д.;
2) группировка под видом события наиболее успешных отрывков композиции, включая мелодии, аккорды, ритмические шаблоны. Упомянутая в одной из первых статей игра в музыкальные кости Моцарта является далеким предшественником такого метода;
Марковские цепи, безусловно, являются одним из самых старых, распространенных и успешно применяемых математических методов алгоритмической композиции.