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

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

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

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

mc1 представляет собой унихейн, потому что это единственный, повторяющийся, апериодический класс.

Определите, эргодична ли цепочка Маркова.

tf1 = isergodic(mc1)

tf1 = logical
   1

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

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

figure;
eigplot(mc1);

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

Оцените время смешивания цепи.

[~,tMix1] = asymptotics(mc1)

tMix1 = 0.8357

В среднем это занимает 0.8357 шаги для полного расстояния вариации для затухания на коэффициент $${}^{\mathrm{e1}}$$.

Ожидаемое время первого попадания для целевого состояния является другим способом просмотра скорости смешивания цепи Маркова. Вычисление времени удара не требует эргодической цепи Маркова.

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

hittime(mc1,1,'Graph',true);

Ожидаемое время первого удара для режима 1, начинающегося с режима 2, составляет приблизительно 16 временных шагов.

Цепочка медленного смешивания

Создайте еще одну цепочку Маркова с 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 представляет эргодический унихейн.

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

figure;
eigplot(sc2);

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

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

[~,tMix2] = asymptotics(sc2)

tMix2 = 5.0201

В среднем это занимает 5.0201 шаги для полного расстояния вариации для затухания на коэффициент $${}^{\mathrm{e1}}$$.

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

sc2.StateNames(1)

ans = 
"2"

hittime(sc2,1,'Graph',true);

Ожидаемое время первого удара для режима 2, начинающегося с режима 8, составляет около 30 временных шагов.

Время смешивания цепи гантелей

Создайте цепочку Маркова «гантели», содержащую 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 представляет собой унихейн, потому что он имеет один, повторяющийся, апериодический класс.

Определите, эргодична ли цепочка Маркова.

tf3 = isergodic(mc3)

tf3 = logical
   1

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

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

figure;
eigplot(mc3);

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

Оцените время смешивания цепи гантелей.

[~,tMix3] = asymptotics(mc3)

tMix3 = 90.4334

В среднем это занимает 90.4334 шаги для полного расстояния вариации для затухания на коэффициент $${}^{\mathrm{e1}}$$.

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

hittime(mc3,1,'Graph',true);

Ожидаемое время первого удара для режима 1, начинающегося с режима 15, составляет около 300 временных шагов.