Сравните времена смешивания цепи Маркова

Этот пример сравнивает предполагаемые времена смешивания нескольких Цепей Маркова с отличными структурами. Теоремы сходимости обычно требуют эргодического unichains. Поэтому прежде, чем сравнить смешивание временных оценок, этот пример гарантирует, что Цепи Маркова являются эргодическим unichains.

Быстро смешивающаяся цепочка

Создайте Цепь Маркова с 23 состояниями из случайной матрицы перехода, содержащей 250 неосуществимых переходов 529 общих переходов. Неосуществимый переход является переходом, чья вероятность появления является нулем. Постройте диграф Цепи Маркова и идентифицируйте классы при помощи цветов узла и маркеров.

rng(1); % For reproducibility
numStates = 23;
Zeros1 = 250;
mc1 = mcmix(numStates,'Zeros',Zeros1);

figure;
graphplot(mc1,'ColorNodes',true);

mc1 представляет unichain, потому что это - один, текущий, апериодический класс.

Определите, является ли Цепь Маркова эргодической.

tf1 = isergodic(mc1)

tf1 = logical
   1

tf1 = 1 указывает, что mc1 представляет эргодический unichain.

Постройте собственные значения Цепи Маркова на комплексной плоскости.

figure;
eigplot(mc1);

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

Оцените смесительное время цепочки.

[~,tMix1] = asymptotics(mc1)

tMix1 = 0.8357

В среднем это делает шаги 0.6121 для общего расстояния изменения, чтобы затухнуть фактором $e^{1}$ .

Медленно смешивающаяся цепочка

Создайте другую Цепь Маркова с 23 состояниями из случайной матрицы перехода, содержащей 475 неосуществимых переходов. С меньшим количеством выполнимых переходов эта цепочка должна занять больше времени, чтобы смешаться. Постройте диграф Цепи Маркова и идентифицируйте классы при помощи цветов узла и маркеров.

Zeros2 = 475;
mc2 = mcmix(numStates,'Zeros',Zeros2);

figure;
graphplot(mc2,'ColorNodes',true);

mc2 представляет unichain, потому что он имеет один, текущий, апериодический класс и несколько переходных классов.

Определите, является ли Цепь Маркова эргодической.

tf2 = isergodic(mc2)

tf2 = logical
   0

tf2 = 0 указывает, что mc2 не является эргодическим.

Извлеките текущую подцепь от mc2. Определите, является ли подцепь эргодической.

[bins,~,ClassRecurrence] = classify(mc2);
recurrentClass = find(ClassRecurrence,1);
recurrentState = find((bins == recurrentClass),1);
sc2 = subchain(mc2,recurrentState);
tf2 = isergodic(sc2)

tf2 = logical
   1

sc2 представляет эргодический unichain.

Постройте собственные значения подцепи на комплексной плоскости.

figure;
eigplot(sc2);

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

Оцените смесительное время подцепи.

[~,tMix2] = asymptotics(sc2)

tMix2 = 5.0201

В среднем это делает шаги 16.4417 для общего расстояния изменения, чтобы затухнуть фактором $e^{1}$ .

Цепочка гантели смешивание времени

Создайте Цепь Маркова "гантели", содержащую 10 состояний в каждом "весе" и три состояния в "панели".

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

w = 10;                             % Dumbbell weights
DBar = [0 1 0; 1 0 1; 0 1 0];       % Dumbbell bar
DB = blkdiag(rand(w),DBar,rand(w)); % Transition matrix

% Connect dumbbell weights and bar
DB(w,w+1) = 1;                       
DB(w+1,w) = 1; 
DB(w+3,w+4) = 1; 
DB(w+4,w+3) = 1;

mc3 = dtmc(DB);

Постройте ориентированного графа цепочки гантели и идентифицируйте классы при помощи цветов узла и маркеров. Подавите метки узла.

figure;
h = graphplot(mc3,'ColorNodes',true);
h.NodeLabel = {};

mc3 представляет unichain, потому что он имеет один, текущий, апериодический класс.

Определите, является ли Цепь Маркова эргодической.

tf3 = isergodic(mc3)

tf3 = logical
   1

tf3 = 1 указывает, что mc3 является эргодическим.

Постройте собственные значения гантели на комплексной плоскости.

figure;
eigplot(mc3);

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

Оцените смесительное время цепочки гантели.

[~,tMix3] = asymptotics(mc3)

tMix3 = 90.4334

В среднем это делает шаги 36.3541 для общего расстояния изменения, чтобы затухнуть фактором $e^{1}$ .

Документация