1.4. Источники образующих

Рассмотрим устройство, генерирующее образующие из Подобный источник может быть детерминированным или вероятностным.

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

Вероятностным источником является случайный процесс с дискретным временем, принимающий значения из Простейшим является

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

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

если этот интеграл сходится.

Подобные средние в вероятностных терминах описывают наличие у образующих определенных свойств. Полезно также

описать и характеристики самого в частности насколько оно сосредоточено или рассеяно.

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

Одной из таких мер является шенноновская мера информации:

Я является неотрицательной величиной и обращается в ноль только в тех случаях, когда вся масса вероятности сосредоточена на одной образующей. Большие значения Н означают, что рассредоточена и количество информации, получаемое при случайном выборе одной образующей, велико.

Две другие меры определяются выражением

где положительное число. При это выражение представляет собой критерий Юла и имеет вполне очевидную интерпретацию, заключающуюся в том, что вероятность равенства двух образующих, независимо воспроизведенных двумя простыми вероятностными источниками. Чем меньше тем больше рассредоточена Очевидно, что причем равенство соответствует тому случаю, когда вся масса вероятности сосредоточена на одной образующей. Случай интуитивно менее очевиден, однако мы увидим, что он показывает, как трудно разбить на подмножества, кластеры, таким образом, чтобы кластеры в среднем были малы (см. гл. 16 приложения). Наименьшее значение -единица. Это означает, что все распределение «сосредоточено» в одной точке. Из неравенства Шварца следует, что верхней гранью для критерия является где мощность При конечном верхняя грань достигается при что соответствует равномерному распределению.

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

Случай 1.4.2 (марковский вероятностный источник). Последовательность образует стационарную марковскую Цепь с заданными вероятностями перехода.

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