МАРКОВСКИЕ ЦЕПИ

Первым описал возможности применения Марковских цепей русский математик Андрей Андреевич Марков. Марковские цепи — это последовательности случайных величин, для которых вероятность появления того или иного значения на (k + 1)–м шагу зависит лишь от того, какое значение эта величина приняла на k–м шагу, и не зависит от значений величины на 1–м, 2–м, ..., (k — 1)–м шагах.

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

1. Множеством состояний S = {s₁, …, s_n}, событием является переход из одного состояния в другое в результате случайного испытания.

2. Вектором начальных вероятностей (начальным распределением) p⁽⁰⁾ = {p⁽⁰⁾(1),…, p⁽⁰⁾(n)}, определяющим вероятности p⁽⁰⁾(i) того, что в начальный момент времени t = 0 процесс находился в состоянии s_i ;

3. Матрицей переходных вероятностей P = {p_ij}, характеризующей вероятность перехода процесса с текущим состоянием s_i в следующее состояние s_j, при этом сумма вероятностей переходов из одного состояния равна 1:

∑j=1…n pij = 1

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

Марковская цепь может быть представлена графом, вершины которого соответствуют состояниям цепи, а дуги — ненулевым вероятностям переходов. На рисунке иже представлен граф Марковской цепи, имеющей 5 состояний и вектор начальных вероятностей {1;0;0;0;0}. Вероятности переходов показаны на дугах графа.

Для генерации алгоритмических композиций также безусловно приемлемы и Марковские цепи более высоких порядков — например, второго. Цепью второго порядка называют такую цепь, в которой вероятность перехода в последующее состояние зависит как от двух предшествующих, так и от той последовательности, в которой эти состояния наступают (предшествующие состояния записаны в первом столбце).

Интерес представляет и так называемая Цепь Маркова со случайным блужданием (вероятностная матрица этой цепи имеет ненулевые значения на всех сторонах главной диагонали и нулевые на остальных):

Возможности Марковских цепей могут быть расширены за счет использования более сложных техник:

1) описание событием не какого–то одного значения, например, ноты, а нескольких параметров одновременно — продолжительности, динамики, силы и т.д.;

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

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