5. Эргодические и смешанные источники

Как указывалось выше, для наших целей можно считать, что дискретный источник представляется некоторым марковским процессом. Среди всевозможных дискретных марковских процессов имеется одна группа процессов с особо важными для теории связи свойствами. Этот специальный класс состоит из «эргодических» процессов, и мы будем называть соответствующие источники эргодическими источниками. Хотя строгое определение эргодического процесса несколько сложно, общая идея проста. В случае эргодического процесса каждая создаваемая процессом последовательность имеет одни и те же статистические свойства. Поэтому частоты букв, диграмм и т. полученные из частных последовательностей, будут стремиться с увеличением длин последовательностей к определенным пределам, не зависящим от этих частных последовательностей. В действительности это верно не для каждой последовательности, но множество последовательностей, для которых это не верно, имеет вероятность, равную нулю. Грубо говоря, свойство эргодичности означает статистическую однородность.

Все примеры искусственных языков, данные выше, являются эргодическими. Это свойство связано со структурой соответствующей схемы. Процесс будет эргодическим, если соответствующий граф обладает следующими двумя свойствами.

1. Соответствующая схема не распадается на две изолированные части А и В, такие, что от одной узловой точки в части А нельзя было бы перейти в направлении стрелок в точки части В, и наоборот.

2. Каждая замкнутая последовательность линий, стрелки которых ориентированы в одном направлении, называется «циклом». Под «длиной цикла» понимается число линий, из которых он состоит. Так, например, на рис. 5 последовательность есть цикл длины 5. Второе свойство состоит в том, чтобы наибольший общий делитель длин всех циклов равнялся единице.

Если первое условие удовлетворено, а второе нарушено тем, что общий делитель то последовательности имеют некоторого рода периодическую структуру. Различные последовательности распадаются на различных классов, которые в статистическом отношении одинаковы, за исключением сдвига начала (т. е. выбора того, какую букву последовательности назвать первой). С помощью смещения на величину от 0 до каждая последовательность может быть сделана статистически эквивалентной любой другой. При простым примером является следующий: имеются три возможные буквы с. За буквой а следует либо либо с с вероятностями и 2/3 соответственно. За и с всегда следует буква а. Тогда типичная последовательность имеет вид:

Процессы такого типа не будут иметь большого значения для нашей работы.

Если нарушено первое условие, то граф может быть разделен на некоторое число подграфов, каждый из которых удовлетворяет первому условию. Будем предполагать, что второе условие также выполняется для каждого подграфа. В этом случае имеет место то, что может быть названо «смешанным» источником, составленным из некоторого числа чистых компонент. Эти компоненты соответствуют различным подграфам. Если источники, соответствующие этим компонентам, то можно записать

где — вероятность компоненты

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

эргодическим). Априори неизвестно, какой источник будет использован, но если последовательность начинается с состояния, принадлежащего данной чистой компоненте то она продолжается бесконечно в соответствии со статистической структурой этой компоненты.

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

могла бы быть получена следующим образом: сначала выбирается или с вероятностями 0,2 и 0,8, а затем выбранный источник создает последовательность.

Если не оговорено противное, будем предполагать, что источник является эргодическим. Такое предположение позволяет отождествлять средние значения вдоль некоторой последовательности со средними значениями по ансамблю возможных последовательностей (причем вероятность расхождения равна нулю). Например, относительная частота буквы А в частной бесконечной последовательности будет с вероятностью единица равняться ее относительной частоте по ансамблю последовательностей.

Если — вероятность состояния — вероятность перехода в состояние то для того, чтобы процесс был стационарным, должны, очевидно, удовлетворять условиям равновесия:

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