hittime

Вычислите времена удара Цепи Маркова

Описание

пример

ht = hittime(mc,target) возвращает ожидаемое первое время удара ht для заданного подмножества состояний target, начало от каждого состояния в Цепи Маркова mc. Если target формирует текущий класс, элементы ht expected absorption times.

пример

ht = hittime(mc,target,'Graph',true) строит ориентированного графа mc с цветами узла, представляющими ожидаемые первые времена удара. Цветная полоса обобщает расцветку.

[ht,h] = hittime(mc,target,'Graph',true) также возвращает указатель графика. Используйте h изменить свойства графика после того, как вы создаете его.

[ht,h] = hittime(ax,mc,target,'Graph',true) графики на осях заданы ax вместо текущей системы координат (gca).

Примеры

свернуть все

Рассмотрите эту теоретическую, правильно-стохастическую матрицу перехода стохастического процесса.

P=[10001/201/200001001/21/2].

Создайте Цепь Маркова, которая характеризуется матрицей P перехода.

P = [1 0 0 0; 1/2 0 1/2 0; 0 0 0 1; 0 0 1/2 1/2];
mc = dtmc(P);

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

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

Вычислите ожидаемое первое время удара для состояния 3, начинающегося с каждого состояния в Цепи Маркова.

ht = hittime(mc,3)
ht = 4×1

   Inf
   Inf
     0
     2

Поскольку состояние 3 недостижимо от состояния 1, состояние 1 является удаленным состоянием относительно состояния 3 с ожидаемым первым временем удара Inf.

Состояние 3 достижимо от состояния 2, но состояние 2 имеет положительную вероятность перехода, чтобы утвердить 1, который является абсорбирующим состоянием. Поэтому состояние 2 является удаленно-достижимым состоянием относительно состояния 3 с ожидаемым первым временем удара Inf.

Поскольку состояние 3 является целью, ее ожидаемым первым временем удара для себя является 0.

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

Рассмотрите эту теоретическую, правильно-стохастическую матрицу перехода стохастического процесса.

P=[01/201/22/301/3001/201/21/302/30].

Создайте Цепь Маркова, которая характеризуется матрицей P перехода.

P = [0   1/2 0   1/2 
     2/3 0   1/3 0   
     0   1/2 0   1/2 
     1/3 0   2/3 0  ];
mc = dtmc(P);

Постройте диграф Цепи Маркова mc. Отобразите вероятности перехода.

graphplot(mc,'ColorEdges',true)

Вычислите ожидаемое первое время удара для состояния 1, начиная с каждого состояния в Цепи Маркова.

ht = hittime(mc,1)
ht = 4×1

         0
    2.3333
    4.0000
    3.6667

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

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

Постройте другой диграф. Включайте состояние 4 как целевое состояние.

hittime(mc,[1 4],'Graph',true);

Создайте Цепь Маркова, охарактеризованную этой матрицей перехода:

P=[1/201/2000001/302/30001/403/4000002/301/30001/41/81/81/81/41/801/61/61/61/61/61/601/2000001/2].

P = [1/2 0   1/2 0   0   0   0
     0   1/3 0   2/3 0   0   0
     1/4 0   3/4 0   0   0   0
     0   2/3 0   1/3 0   0   0
     1/4 1/8 1/8 1/8 1/4 1/8 0
     1/6 1/6 1/6 1/6 1/6 1/6 0
     1/2 0   0   0   0   0   1/2];
mc = dtmc(P);

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

ht = hittime(mc,1,'Graph',true)

ht = 7×1

     0
   Inf
     4
   Inf
   Inf
   Inf
     2

Состояния 2 и 4 формируют абсорбирующий класс. Поэтому состояние 1 недостижимо от этих состояний. Абсорбирующий класс является удаленным относительно состояния 1 с ожидаемым первым временем удара Inf.

Состояние 1 достижимо от состояний 5 и 6, но вероятность перехода в абсорбирующий класс от состояний 5 и 6 является ненулевой. Поэтому состояния 5 и 6 удаленно-достижимы относительно состояния 1 с ожидаемым первым временем удара Inf.

Ожидаемое первое время удара для состояния 1 начало от состояния 7 является 2 временными шагами. Ожидаемое первое время удара для состояния 1 начало от состояния 3 является 4 временными шагами.

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

numStates = 8;
Zeros = 50;
stateNames = strcat(repmat("Regime ",1,8),string(1:8));
rng(1617676169) % For reproducibility
mc = mcmix(8,'Zeros',Zeros,'StateNames',stateNames);

Постройте диграф Цепи Маркова mc. Задайте цвета узла, которые идентифицируют переходные и текущие состояния и связывающиеся классы.

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

Найдите текущий класс в Цепи Маркова mc путем выполнения этой процедуры:

  1. Классифицируйте состояния путем передачи mc к classify. Возвратите массив членств в классе ClassStates и логический вектор, задающий, является ли классами текущий ClassRecurrence.

  2. Извлеките текущие классы из массива классов путем индексации в массив с помощью логического вектора.

[~,ClassStates,IsClassRecurrent] = classify(mc);
recurrent = ClassStates{IsClassRecurrent}
recurrent = 1x4 string
    "Regime 2"    "Regime 3"    "Regime 6"    "Regime 8"

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

ht = hittime(mc,recurrent);

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

istransient = ~ismember(mc.StateNames,recurrent);
absorbtime = ht(istransient);
table(absorbtime,'RowNames',mc.StateNames(istransient))
ans=4×1 table
                absorbtime
                __________

    Regime 1      5.8929  
    Regime 4           1  
    Regime 5      1.7777  
    Regime 7      4.8929  

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

rng(1) % For reproducibility
mc = mcmix(50,'Zeros',2400);

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

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

Визуализируйте смесительное время Цепи Маркова для состояния 5.

hittime(mc,5,'Graph',true);

Ожидаемое время поездки на работу от состояния i утверждать j ожидаемое время, требуемое для Цепи Маркова к переходу от состояния i утверждать j (ожидаемое первое время удара ht(i,j)), затем обратно чтобы утвердить i (ht(j,i)). Официально, ожидаемое время поездки на работу

C(i,j)=ht(i,j)+ht(j,i).

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

  • Задайте случайные вероятности перехода между состояниями в каждом весе.

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

  • Задайте универсальные переходы между состояниями в панели.

rng(1); % For reproducibility
w = 5;                              % 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;

mc = dtmc(DB);

Постройте диграф Цепи Маркова mc. Подавите метки узла.

figure;
graphplot(mc);

Полагайте, что вычисление ожидаемого времени поездки на работу от состояния 1 утверждает 10.

Вычислите ht(1,10), ожидаемое первое время удара для состояния 10 начала от состояния 1.

ht = hittime(mc,10);
ht1to10 = ht(1);

Вычислите ht(10,1), ожидаемое первое время удара для состояния 1 начало от состояния 10.

ht = hittime(mc,1);
ht10to1 = ht(10);

Вычислите ожидаемое время поездки на работу из состояния 1, чтобы утвердить 10.

C1to10 = ht1to10 + ht10to1
C1to10 = 236.6165

Ожидаемое время поездки на работу от состояния 1, чтобы утвердить 10 и назад является 236,62 временными шагами.

Входные параметры

свернуть все

Дискретная цепь Маркова с NumStates состояния и матрица перехода PВ виде dtmc объект. P должен быть полностью задан (никакой NaN записи).

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

  • Для числового вектора, элементов target соответствуйте строкам матрицы перехода mc.P.

  • Для вектора строки или вектора ячейки из векторов символов, элементов target должны быть имена состояния в mc.StateNames.

Пример: ["Regime 1" "Regime 2"]

Типы данных: double | string | cell

Оси, на которых можно построить в виде Axes объект.

По умолчанию, hittime графики к текущей системе координат (gca).

Выходные аргументы

свернуть все

Ожидаемый сначала совершающие нападки времена, возвращенные как числовой вектор из длины mc.NumStates. ht (j) ожидаемое первое время удара заданного подмножества цели, утверждает target от начального состояния j.

Если ht (j) = Inf, j состояния удаленное или удаленно-достижимое состояние состояния для цели, утверждает target.

Обработайте к графику графика, возвращенному как графический объект когда 'Graph' аргументом пары "имя-значение" является trueH уникальный идентификатор, который можно использовать, чтобы запросить или изменить свойства графика.

Больше о

свернуть все

Удаленное состояние

Remote states является теми состояниями, от которых целевые состояния недостижимы. Удаленное состояние имеет совершающую нападки вероятность 0 и ожидаемое первое время удара Inf. Для получения дополнительной информации о совершающих нападки вероятностях смотрите hitprob.

Удаленно-достижимое состояние

Remote-reachable states является теми состояниями, от которых целевые состояния достижимы и которые имеют положительную вероятность достижения абсорбирующего класса. Удаленно-достижимое состояние имеет ожидаемое первое время удара Inf для целевых состояний.

Алгоритмы

hittime использование linprog найти минимальную норму неотрицательным решением системы:

{kiA=0,iAkiA=1+jAPijkjA,iA,

где

  • kiA = ht (i), ожидаемое первое время удара для подмножества состояний A, начинающийся с i состояния.

  • A является набором индексов состояний в target.

  • P = mc.P.

  • N = mc.NumStates [1].

Ссылки

[1] Норрис, J. R. Цепи Маркова. Кембридж, Великобритания: Издательство Кембриджского университета, 1997.

Введенный в R2019b
Для просмотра документации необходимо авторизоваться на сайте