Моделирование динамики систем на основе цепи Маркова с дискретным временем

    Напомним, что i-е собственное число матрицы Р ʎ_i есть i-и корень алгебраического уравнения

    det(P- ʎI) = 0, 

    и собственный вектор u, соответствующий собственному числу ʎ_i , есть решения линейного уравнения

    Pu_i = ʎ_i u_j

    Преобразование  удобно тем, что при возведении в степень матрицы фактически возводится в степень только диагональная матрица

    P^k=(UɅU)^k=UɅ^kU^-1

    Причем Ʌ ^k

 

    Таким образом, динамику изменения матрицы Р^к легко оценить по поведению ʎ_i,   i = 1,...,п .

    Мы  уже упоминали, что матрица Р, определяющая однородную цепь Маркова, является стохастической матрицей. Особенностью этой матрицы является то, что ее максимальное собственное число равно 1, и ему соответствует собственный вектор, составленный из единиц: [l,l,...l].

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

    X_пред⁼ limX(t_k) k→∞.

    Напомним, что вектор состояния X{t_k) определяете» формулой:

    X(t_k)=X(t₀)P^k

    а к-я степень канонической стохастической матрицы имеет структуру: P^k=

 

    При большом числе шагов, как мы установили, матрица Q^k  -» 0, а матрицы W^k и R(k) стремятся к некоторым предельным W^k -» W_nред, R(k) -» R_пред. Таким образом, в предельном случае: Р_пред=limP^k , k→∞, = 

 

Матрицу Р_пред можно найти описанным выше способом,

    выполнив  спектральное разложение матрицы Р  и положив k→∞. Тогда

    X_пред= X(t₀)*P_пред

    Однако  существует более простой способ определении Х_пред. Он основан на том, что при большом числе шагов вектор X(t_k) сходится к Х_пред . Из соотношения

    X(t_k+1) = X{t_k)*P, при k→∞,, следует, что

    X(t_k) -»X{t_k+])-»X_пред

    и

    X_пред=X_пред*P

    Решая уравнение относительно неизвестных x1_пред, x2_пред,   …, xn_пред   при дополнительном условии

    Σx_{i пред}=1, при i→∞,. Получим вектор X_пред.  
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

     Практическая  часть  

     Матрица переходных вероятностей Р 

 
 

     Векторы вероятностей X(t) 

    Стартовым состоянием является состояние S1. Поэтому вектор вероятности для t0 выглядит следующим образом: 

X(t0)=[1 0 0 0 0 0 0] (График этого вектора не требуется, т.к. старт всегда из 1-ой вершины) 

    С помощью этого и матрицы переходных вероятностей найдены все остальные векторы вероятностей для 15 шагов и представлены графики вероятности нахождения системы на определенном шаге в каком-либо из состоянии: 

    Матрица X

 

            Оценка  результатов тестирования программы 1

          

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

    Векторы вероятностей (100 тестов):

    t0:  1  0  0  0  0  0  0 

    t1:  0  0,25  0,48  0  0,27  0  0 

    t2:  0,2  0  0,02  0,1  0,35  0,33  0 

    t3:  0  0,04  0,06  0,04  0,46  0,34  0,06 

    t4:  0,02  0  0,03  0,03  0,39  0,46  0,07 

    t5:  0  0  0,03  0,02  0,44  0,44  0,07 

    t6:  0,02  0  0,01  0,01  0,45  0,44  0,07 

    t7:  0  0,01  0  0,01  0,42  0,49  0,07 

    t8:  0  0  0,01  0,01  0,46  0,45  0,07 

    t9:  0,01  0  0  0  0,46  0,45  0,08 

    t10:  0  0,01  0  0  0,53  0,38  0,08 

    t11:  0  0  0  0  0,48  0,44  0,08 

    t12:  0  0  0  0  0,49  0,43  0,08 

    t13:  0  0  0  0  0,47  0,45  0,08 

    t14:  0  0  0  0  0,43  0,49  0,08 

    t15:  0  0  0  0  0,49  0,43  0,08   

    График, полученный программой за счёт вычисленных  данных. Здесь видно, что он имеет  расхождение с графиком, полученным из теоретических данных. 

 
 
 
 
 
 
 
 
 
 
 

    Векторы вероятностей (1000 тестов):

    t0:  1  0  0  0  0  0  0 

    t1:  0  0,336  0,362 0  0,302  0  0 

    t2:  0,143  0  0,115  0,086  0,422  0,234  0 

    t3:  0,045  0,052  0,066  0,052  0,387  0,377  0,021 

    t4:  0,026  0,011  0,056  0,04  0,431  0,405  0,031 

    t5:  0,022  0,006  0,024  0,022  0,438  0,444  0,044 

    t6:  0,007999  0,005  0,015  0,013  0,463  0,444  0,052 

    t7:  0,007  0,001999  0,005  0,01  0,415  0,503999  0,057 

    t8:  0,000999  0,003999  0,003999  0,006  0,45  0,475  0,06 

    t9:  0,001999  0,000999  0,006  0,001999  0,482  0,446  0,061 

    t10:  0,001999  0,001999  0,000999  0,001999  0,451  0,481  0,061 

    t11:  0,000999  0,000999  0,003  0,000999  0,501  0,432  0,061 

    t12:  0,000999  0  0,001999  0  0,477  0,458  0,062 

    t13:  0,001999  0  0  0  0,459  0,477  0,062 

    t14:  0  0  0,000999  0  0,452  0,485  0,062 

    t15:  0  0  0 0  0,466  0,472  0,062   

    При выполнении 1000 тестов график уже приближается к теоретическому, но все еще имеются  большие расхождения. 

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

    Векторы вероятностей (10000 тестов):

t0:  1  0  0  0  0  0  0 

t1:  0  0,3035  0,3961  0  0,3004  0  0 

t2:  0,1546  0  0,0904  0,0868  0,399  0,2692  0 

t3:  0,0331  0,0474  0,0795  0,044  0,4056  0,365  0,0254 

t4:  0,031  0,0096  0,0367  0,0378  0,4332  0,4127  0,039 

t5:  0,0145  0,0088  0,0203  0,0207  0,4411  0,4414  0,0532 

t6:  0,007999  0,0044  0,0125  0,0136  0,4537  0,4489  0,0589 

t7:  0,0048  0,0019  0,0082  0,0081  0,4565  0,4578  0,0627 

t8:  0,0032  0,0012  0,0047  0,0044  0,454  0,4676  0,0649 

t9:  0,0024  0,000999  0,0023  0,0024  0,4688  0,4571  0,066 

t10:  0,0011  0,000499  0,0018  0,0019  0,4624  0,4656  0,0667 

t11:  0,0008  0,0002  0,0009  0,0014  0,4629  0,4667  0,0671 

t12:  0,000499  0,0001  0,0006  0,0009  0,4647  0,4657  0,0675 

t13:  0,000499  0,0001  0,0002  0,0007  0,4699  0,4609  0,0677 

t14:  0,0002  0,0003  0,0003  0,000499  0,4691  0,4618  0,0678 

t15:  0,0003  0  0,0004  0,0002  0,4726  0,4585  0,068   

    График  при выполнении 10000 тестов можно  считать максимально приближенный к теоретическому графику.