Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
81
Вот отрывок из этого последнего примера:
The head and in frontal attack on an english writer that the character of this point is therefore another method ...*)
Хотя этот пример является чистой тарабарщиной, он довольно похож на осмысленный текст. На самом деле мы не можем моделировать текст с помощью случайного процесса достаточно точно. Очевидно, что имеется существенная разница между текстом медицинского словаря и текстом первой детской книги для чтения. Из-за этой разницы теорема кодирования для источника не может быть применена к английскому тексту и нельзя точно определить его энтропию. Вместе с тем, используя некоторые статистические зависимости английского языка, можно более эффективно описывать текст в сравнении с описанием, которое не использует эти зависимости.
Приведем здесь без доказательств некоторые свойства конечных однородных цепей Маркова**'. Состояние s называется невозвратным, если существует некоторое состояние, которое может быть достигнуто из s за один или более переходов, но из которого невозможно никогда возвратиться в s. Например, на рис. 3.6.1 состояние 1 является невозвратным. Множество состояний называется неразложимым, если никакое состояние вне множества не может быть достигнуто ни из какого состояния, входящего в множество, и каждое состояние множества может быть достигнуто за один или более переходов. Так, например, состояния
2 и 3 образуют неразложимое множество, так же как и состояния 4 и 5.
Состояния любой конечной однородной цепи Маркова могут быть однозначно разбиты на одно или большее число неразложимых множеств состояний и множество (быть может пустое) невозвратных состояний. С вероятностью 1 цепь в конце концов оказывается в одном из неразложимых множеств и, конечно, остается в нем.
Число переходов, начиная из некоторого состояния s неразложимого множества, требующееся для первого возвращения в s, является случайной величиной, которая называется временем возвращения в s. Периодом неразложимого множества состояний называется наибольшее целое число т, такое, что все возможные времена возвращений для состояний этого множества являются кратными т. Например, период множества состояний 1 и 3 на рис. 3.6.1 равен 1, так как время возвращения для любого состояния может быть любым положительным целым числом. Период состояний 4 и 5 равен 2, так как время возвращения равно 2 для каждого состояния. Если неразложимое множество имеет период т ^ 2, то оно называется периодическим. Если т = 1, то множество называется эргодическим.
*) Русск. перев. «Голова и в фронтальной атаке на английского писателя, что характер этого места является, следовательно, другим методом....» (Прим. перев.).
**> Доказательства имеются, например, у Феллера (1950) или у Кокса и Миллера (1965).
82
Эргодическое множество состояний Е имеет ассоциированное с ним множество стационарных вероятностей q (/), задаваемых как решения уравнений
2 я (/)Qa = q(*'). i € Е, (3.6.5)
y.q(i) 1- (3.6.6)
J6?
Более того, для любых t и j из ?
lim Pr (sz = i | Sj /) q (i), (3.6.7)
1-+OQ
где сходимость к пределу экспоненциальна по /.
Можно заметить, что вероятности в (3.6.1)—(3.6.4) не описывают полностью источник. Необходимо еще указать, когда источник начинает работу и каково начальное распределение вероятностей для состояний. Если состояния источника принадлежат некоторому данному эргодическому множеству состояний, начиная со сколь угодно далекого прошлого, то
Pr (S; = г) = q (г) для всех I, (3.6.8)
и источник является стационарным и эргодическим согласно определениям этого параграфа. Вместе с тем, если источник начинает работу с заданного конечного момента времени из заданного состояния, то он не является стационарным и эргодическим, так как у него нет прошлого и так как имеется начальная неустойчивость в вероятности.
Проблема переходного режима много серьезнее для периодических множеств состояний, чем для эргодических множеств. Для периодического множества состояний с периодом т имеется т возможных фаз, соответствующих тому, что данное состояние может наступить только в моменты ..., ¦—т, 0, т, ... или в моменты ..., —т +1, 1, т + 1, ... или и т. д. вплоть до моментов ..., —т + (т—1), т—1, т-\-(т—1), ... Если источник начал свою работу в бесконечно удаленный момент прошлого в данной фазе, то результирующее случайное состояние последовательности является периодическим в смысле определения этого параграфа. Если источник начал свою работу в сколь угодно удаленном прошлом с равномерным распределением фаз,то результирующая последовательность случайных состояний удовлетворяет (3.5.13) и, следовательно, является эргодической.
