Марковские цепи с доходами (платежами).

Случайным процессом называют функцию времени, принимающую случайные значения в каждый фиксированный момент времени.

Случайной последовательностью (цепью) называют случайный процесс с дискретными состояниями () и временем ().

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

МЦ называется однородной (стационарной), если переходные вероятности не изменяются во времени.

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

. (1)

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

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

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

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

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

К классу УМЦ относятся марковские цепи с платежами (МЦП). Их отличие от обычных МЦ в следующем:

1. На каждом (- ом) шаге процесса перед переходом на следующей (() - й) шаг можно принять одно из множества решений: .

2. Для каждого варианта решения () задана своя матрица условных вероятностей перехода за один шаг (МВП): . Здесь под условным имеется в виду следующее: «- это вероятность перехода в состояние на () – ом шаге при условии, что на - ом шаге процесс находился в состоянии , если было принято решение ».

3. Для каждого варианта решения () кроме МВП задана и матрица условных платежей за один шаг (МП): , где - платеж (или доход) за один шаг при переходе в состояние на () – ом шаге при условии, что на - ом шаге процесс находился в состояния и было принято решение .

Остальные элементы аналогичны обычным МЦ:

1. Множество состояний процесса .
2. Вектор вероятностей начальных состояний .

Пример. Приведенный выше типовой пример распределения рекламного бюджета на трех шагах можно представить следующими элементами:

▲

Таким образом, МЦП является моделью принятия решений, в которой:

· есть что выбирать - решения на каждом шаге;

· есть чем измерить качество выбираемого решения - платежами, накопленными за множество шагов или средние по всем шагам.

Существует два основных алгоритма поиска решений для МЦП:

· рекуррентный алгоритм, основанный на уравнении Р. Беллмана, где максимизируется накопленный выигрыш;

· итерационный алгоритм, где максимизируется средний выигрыш за один шаг.