- •Конспект лекций по дисциплине Теоретические основы информационных процессов
- •Глава 1 Основные понятия теории информационных систем
- •1.1. Основные понятия и определения
- •1.2. Вторичные понятия и определения теории систем
- •1.3. Классификация систем
- •Глава 2 Теорико-вероятностные методы теории информационных процессов
- •Глава 3 Модели и методы описания систем
- •3.1. Методы описания систем
- •3.3. Кибернетический подход к описанию систем
- •3.1. Теоретико-множественный подход к описанию систем
- •3.4. Агрегативное описание систем
- •3.5. Марковские цепи
- •Глава 4 Основы количественной теории информации
- •4.1. Основные понятия теории информации
- •4.2. Количество информации
- •4.3. Энтропия и ее свойства
- •Глава 5 Информационные процессы и сигналы
- •5.1. Общая схема передачи информации в линии связи
- •5.2. Модели сигналов
- •5.3. Передача информации по каналу связи без учета помех
- •5.4. Передача информации по каналу с помехами
- •Глава 6 Помехоустойчивое кодирование сообщений
- •6.1. Общие принципы помехоустойчивого кодирования.
- •6.2. Систематические коды
- •6.3. Циклические коды
3.5. Марковские цепи
Функционирование многих объектов представляет собой последовательность переходов их из одного состояния в другое (ЭВМ, каналы передачи информации…).
Система называется системой с дискретными состояниями, если множество ее состояний конечно, а переходы из одного состояния в другое осуществляются скачком.
Последовательность состояний такой системы называется цепью.
Простейшей характеристикой случайного процесса, являющегося цепью, служит набор вероятностей состояний p1(t), p2(t),…, pn(t), где pi(t) – вероятность того, что в момент t система находится в состоянии i. p1(t)+p2(t)+…+ pn(t)=1
Случайный процесс, протекающий в системе, называется марковским, если для любого момента времени t0 вероятность любого состояния системы в будущем (при t > t0) зависит только от ее состояния в настоящем (при t = t0) и не зависит от того, каким образом система пришла в это состояние.
Переход системы из одного состояния в другое является в общем случае случайным событием. Последовательность смены состояний является потоком событий.
Поток событий является ординарным, если события происходят поодиночке (нет двух одновременных событий). Поток называется стационарным, если его вероятностные характеристики не изменяются во времени. Чаще всего применяются пуассоновские потоки событий, то есть имеющие неизменную интенсивность (плотность) – среднее число событий в единицу времени постоянна. = const.
Эргодические и поглощающие марковские цепи
Динамику переходов системы из состояния в состояние с течением времени можно представить в виде графа. Нередко это иерархический граф, дерево.
Сообщающиеся состояния, находящиеся на последней ступени, называются эргодическим подмножеством состояний. В частном случае, эргодическое множество может состоять из одного элемента, который называется поглощающим. Если все эргодические подмножества цепи состоят только из одного поглощающего состояния, такая цепь называется поглощающей.
Поглощающие марковские цепи характеризуются тем, что эргодическое подмножество состоит из единственного элемента, который и является поглощающим.
В установившемся режиме, независимо от начального состояния, вероятность нахождения поглощающей марковской цепи в поглощающем состоянии близка к единице, а вероятности остальных состояний близки к нулю. Для примера на рисунке pС1= pС2 = pС3= 0, pС4=1. В связи с этим для исследования интересен только переходный режим.
Непрерывные марковские цепи
На практике часто встречаются ситуации, когда система имеет конечное число дискретных состояний, а переходы между состояниями происходят в произвольные моменты времени. Например, отказы аппаратуры могут произойти в любой случайный момент времени.
Случайный процесс с непрерывным временем называется непрерывной марковской цепью, если поведение системы после произвольного момента времени t зависит только от состояния в этот момент времени и не зависит от истории процесса, предшествующей моменту t (соблюдается принцип отсутствия последействия).