Решенные билеты (1085496), страница 12

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 12)

Аналогичным образом определяема и дисперсия для общего количества раз пребывания в том или ином состоянии . Обозначим ее :

(11)

Эргодические цепи

Как указывалось выше под эргодической ДМЦ понимается цепь, не имеющая невозвратных состояний. Таким образом, в такой цепи возможны любые переходы между состояниями. Напомним, что эргодические цепи могут быть регулярными и циклическими. Ранее определение таких цепей было дано.

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

1. Степени при стремятся к стохастической матрице .

2. Каждая строка матрицы представляет один и тот же вероятностный вектор

(12)

все компоненты которого положительны.

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

(13)

которое в развернутом виде будет выглядеть так:

(13а)

К уравнениям (8.13а) можно дополнительно добавить условие нормировки:

(14)

Тогда любое из уравнений в (8.14) можно исключить.

Так же, как и в случае поглощения ДМЦ многие характеристики эргодических цепей определяются с помощью фундаментальной матрицы, которая в этом случае будет иметь вид:

(15)

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

(16)

где

- фундаментальная матрица (15);

- диагональная матрица, образованная из фундаментальной заменой всех элементов, кроме диагональных, нулями;

D - диагональная матрица с диагональными элементами, ;

Е - матрица, все элементы которой равны единице.

Матрица дисперсий времени первого достижения имеет несколько более сложный вид:

(17)

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

--------------------------------------------------ЧАСТЬ3-------------------------------------------------------

Вопрос 30.

Функции памяти и память автомата, их свойства, связь с установочными последовательностями.

Для любой функции : Y^bX^a+1Y; a,bN₀ определим автомат: M()=(X, Y^bX^a, Y, h, f), где h((y₁,…,y_b,x₁,…,x_a),x)=(y₁,…,y_b,( y₁,…,y_b,x₁,…,x_a,x),x₂,…,x_a,x);

f((y₁,…,y_b,x₁,…,x_a),x)=(y₁,…,y_b,x₁,…,x_a,x)

Этот автомат изображается следующим образом:

В частности, при b=0 M()=R₀()- проходная линия задержки длины a. При а=0 M()=R(), класс автоматов M и R пересекаются но не совпадают. Функция памяти А- всякая функция : sS, =x₁,…,x_tX^t, t1+max{a,b} выполняется равенство: A_s( )=y₁,…,y_t => y_t=(y_t-b,…,y_t-1,x_t-a,…,x_t) => память автомата А называется число m(A)= max{a,b}; Если  не сущуствует, то m(A)= иначе m(А)<; Если m(A)<, то А- автомат с конечной памятью и если при этом:  с а=0 => А- автомат с конечной памятью выхода;  c b=0 => А- автомат с конечной памятью входа. Если m(A) max{a,b}, тогда автомат имеет конечную память. В дальнейшем можно рассматривать случай: m=a=b, без ограничения общности, т.к. можно дополнить несущественными переменными.

Теорема1:A, : Y^mX^m+1Y и m 0 рассмотрим следующие свойства: а) - функция памяти А; б) y_m+1=(y₁,…,y_m,x₁,…,x_m+1) sS, x₁,…,x_m+1X^m+1, где А_s(x₁,…,x_m+1)=y₁,…,y_m+1; в) состояние h(s, ) автомата А эквивалентно состоянию (y₁,…,y_m,x₁,…,x_m) автомата M(), sS, X^m, где А_s( )=y₁,…,y_m; г) А- представляется автоматом M(); д) Существенный подавтомат А: A^[c] представляется автоматом M(). Тогда свойства а), б), в)- равносильны и выполняется импликация г) => а) => д). Доказательство: По определениям: [а), б), в)- равносильны и выполняется импликация [г) => а)]. Импликация [а) => д)] следует из равносильности свойств а) и в). Вывод: если у автомата А все состояния существенны, то свойства а) и г) равносильны.

Следствие: Для произвольного А следующие свойства равносильны: а) m(A)<; б) : Y^mX^m+1Y: A^[c] представляется автоматом M().

Доказательство: импликация [а) => б)] следует из импликации [а) => д)] теоремы1. Далее ] выполнено б) и S=n; определим : Y^n+m-1_X^n+mY равенством (y₁,…,y_n+m-1,x₁,…,x_n+m)=(y_n,…,y_n+m-1,x_n,…,x_n+m); т.е. добавим первые 2*n переменных, которые несущественны, тогда M()~M(); sS, A_s(x₁,…,x_n+m-1)=y₁,…,y_n+m-1 => h(s, x₁,…,x_n-1)- существенное состояние А, тогда h(s,x₁,…,x_n+m-1)[автомата М(П)]~(y_n,…,y_n+m-1,x_n,…,x_n+m-1)~(y₁,…,y_n+m-1,x₁,…,x_n+m-1)[автомата М(П')], т.е. выполняется в) теоремы1 для  => m(A)n+m-1<.

Теорема2 (‘Критерий существования функции памяти’): a,bN₀; m max{a,b} следующие свойства равносильны: а) : Y^bX^a+1Y- функция памяти А. б)  , X^m+1; s,sS, где =x₁,…,x_m+1; = x₁,…,x_m+1; A_s( )=y₁,…,y_m+1; A_s( )= y₁,…,y_m+1; Справедлива импликация: если x_m-a+1,…,x_m+1=x_m-a+1,…,x_m+1 и y_m-b+1,…,y_m+1=y_m-b+1,…,y_m+1, тогда y_m+1=y_m+1.

Доказательство: импликация [а) => б)] следует из определения. Обратно: ] выполнено б), тогда определим функцию : Y^bX^a+1Y следующим равенством: x_m-a+1,…,x_m+1X^a+1, y_m-b+1,…,y_mY^b: y_m+1=(y_m-b+1,…,y_m,x_m-a+1,…,x_m+1), где A_s(x₁,…,x_m+1)=y₁,…,y_m+1 для некоторых x₁,…,x_m-aX^m-a, sS, и определим - произвольно, если таких x и s не существует, тогда по теореме1-б): - функция памяти А.

Определение: Входная последовательность X^*- диагностическая для А, если s,sS справедлива импликация: A_s( )=A_s( ) => s~s и последовательность - установочная, если из A_a( )=A_s( ) => h(s, )~h(s, ).( s~s - начальное, h(s, )~h(s, ) - финальное с точностью до эквивалентности). Для любого автомата диагностическая последовательность является установочной, обратное верно только для подстановочного автомата.

Следствие: Для mN₀ следующие свойства равносильны: а) m(A)m; б)  входная последовательность X^m (длины m)- установочная; в) для x₁,…,x_m+1= X^m+1 и состояний s, sS справедлива импликация: из A_s(x₁,…,x_m)=A_s(x₁,…,x_m) => A_s( )=A_s( ). Доказательство: импликация [а) => б)] следует из равносильности свойств а) и в) теоремы1; [б) => в)] очевидны по определению; [а) => в)] следует из теоремы2 при a=b.

Вопрос 31

Критерий бесконечности памяти. Верхняя оценка конечной памяти.

Память - это есть минимальная длинна, для которой все входные последовательности установочные, если такого m- нет, то память = .

Следствие1(из теоремы "критерий существования функции памяти"): Для mN₀ cледующие свойства равносильны: а) m(A)m+1; б)  , S, и входная последовательность X^m+1: A ( )=y₁,…,y_m, ; i=1,2 ;  ;(без доказательства).

Теорема (‘Критерий бесконечности памяти’): Следующие утверждения равносильны: а) память автомата m(A)=; б)  s, sS, 1l( ), X^l: 1): s~s, 2): A_s( )=A_s( ), 3): {s, s}~{h(s, ),h(s, )}; в) m(A)( )+1.

Доказательство: Импликация [а) => в)]- очевидна; [в) => б)]: по следствию1 для m=( ),  пара состояний , , и ₀=x₁,…,x_m+1: выполняется условие б) следствия, тогда h^*( , ₀)= ,…, , т.к.  => ~ , t  1t₁<t₂m+1- номер тактов, в которых { , }~{ , }, тогда для s= и s= , = ,…, длины l=t₂-t₁m, выполняется утверждение б) теоремы. Импликация [ б) => a)]: Пусть tN, = *…* (t раз), тогда т.к. s~s, то  : A_s( )A_s( ), тогда A_s( )=A_s( ), A_s( )A_s( ), тогда по следствию1: m(A)t*l+1 => m(A)= (т.к. t=).

Следствие2: Если m(A)<, то m(A)( )- верхняя оценка памяти, если она <. Доказательство: Отрицанием утверждения в) теоремы.

Вопрос 32.

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

Утверждение (‘Нижняя оценка памяти’): Пусть Y<1, m(A)=m<, тогда: а) (А)m(A) - (степень различимости); б) log_{XY}(A^[c])m(A); в) А- подстановочный => log_Y(A) m(A).

Доказательство: а) Если s s, то т.к. если (A_s(x₁,…,x_m)=A_s(x₁,…,x_m) => A_s( )=A_s( ) - доказывалось ранее), тогда => s s, т.е. произошла стабилизация уже на m. б) следует из того, что существенный подавтомат А: A^[c] представляется автоматом M() - доказывалось ранее. в) ] А-подстановочный =>  установочная последовательность- диагностическая. Из условия , что  входная последовательность X^m (длины m)- установочная(доказывалось ранее) =>  входная последовательность длины m- диагностическая => число классов эквивалентных состояний  вообще выходных последовательностей автомата, т.е. (А)Y^m;

Определение: Длина единственности- l(A)- минимальное lN₀:  входная последовательность X^l- диагностическая для А. l(A)=, если таких l не существует. {по  паре (входные, выходные последовательности) длины l(A) однозначно определяется ключ} (A)m(A)l(A).

В силу определения: log_Y(A)l(A). Если А- подстановочный => m(A)=l(A); Если А- автономный, то понятия установочности и диагностичности также совпадают и сводятся к понятию: существует число l:  выходная последовательность длины l определяет однозначно с точностью до эквивалентности начальных состояний => если А- автономный => (A)=m(A)=l(A) => память всегда конечна (А)-1.

Характеристики

Список файлов ответов (шпаргалок)