Введение
В теории информации, типичное множество – это множество последовательностей, вероятность которых близка к двум в степени, равной минус энтропии их исходного распределения. Тот факт, что общая вероятность этого множества близка к единице, является следствием асимптотического свойства эквипартиции (AEP), которое представляет собой разновидность закона больших чисел. Понятие типичности связано только с вероятностью последовательности, а не с самой последовательностью. Это имеет большое значение в теории сжатия, поскольку предоставляет теоретическую возможность сжатия данных, позволяя представить любую последовательность Xn, используя в среднем nH(X) битов, и, следовательно, обосновывает использование энтропии в качестве меры информации, получаемой из источника. AEP также может быть доказано для широкого класса стационарных эргодических процессов, что позволяет определить типичное множество в более общих случаях.
Пример
Противореча интуиции, наиболее вероятная последовательность часто не является элементом типичного множества. Например, предположим, что X – независимая и одинаково распределенная (i.i.d.) случайная величина Бернулли с p(0) = 0,1 и p(1) = 0,9. В n независимых испытаниях, поскольку p(1) > p(0), наиболее вероятной последовательностью исходов является последовательность, состоящая только из 1, (1, 1, ..., 1). Здесь энтропия X равна H(X) = 0,469, в то время как эта последовательность не входит в типичное множество, потому что ее средняя логарифмическая вероятность не может произвольно близко приближаться к энтропии случайной величины X, вне зависимости от того, насколько большим мы выберем значение n.
So this sequence is not in the typical set because its average logarithmic probability cannot come arbitrarily close to the entropy of the random variable X no matter how large we take the value of n.
For Bernoulli random variables, the typical set consists of sequences with average numbers of 0s and 1s in n independent trials. This is easily demonstrated: If p(1) = p and p(0) = 1 p, then for n trials with m 1's, we have
The average number of 1's in a sequence of Bernoulli trials is m = np. Thus, we have
For this example, if n=10, then the typical set consist of all sequences that have a single 0 in the entire sequence. In case p(0)=p(1)=0.5, then every possible binary sequences belong to the typical set.
Для случайных величин Бернулли типичное множество состоит из последовательностей со средним количеством 0 и 1 в n независимых испытаниях. Это легко показать: если p(1) = p и p(0) = 1 – p, то для n испытаний с m единицами мы имеем:
So this sequence is not in the typical set because its average logarithmic probability cannot come arbitrarily close to the entropy of the random variable X no matter how large we take the value of n.
For Bernoulli random variables, the typical set consists of sequences with average numbers of 0s and 1s in n independent trials. This is easily demonstrated: If p(1) = p and p(0) = 1 p, then for n trials with m 1's, we have
The average number of 1's in a sequence of Bernoulli trials is m = np. Thus, we have
For this example, if n=10, then the typical set consist of all sequences that have a single 0 in the entire sequence. In case p(0)=p(1)=0.5, then every possible binary sequences belong to the typical set.
Среднее количество единиц в последовательности испытаний Бернулли равно m = np. Таким образом, для этого примера, если n = 10, то типичное множество состоит из всех последовательностей, содержащих ровно одну 0 во всей последовательности. В случае p(0) = p(1) = 0,5, то все возможные двоичные последовательности принадлежат типичному множеству.
So this sequence is not in the typical set because its average logarithmic probability cannot come arbitrarily close to the entropy of the random variable X no matter how large we take the value of n.
For Bernoulli random variables, the typical set consists of sequences with average numbers of 0s and 1s in n independent trials. This is easily demonstrated: If p(1) = p and p(0) = 1 p, then for n trials with m 1's, we have
The average number of 1's in a sequence of Bernoulli trials is m = np. Thus, we have
For this example, if n=10, then the typical set consist of all sequences that have a single 0 in the entire sequence. In case p(0)=p(1)=0.5, then every possible binary sequences belong to the typical set.
Сильно типичные последовательности (сильная типичность, типичность букв)
Если последовательность x1, …, xn извлекается из некоторого заданного совместного распределения, определенного на конечном или бесконечном алфавите, то сильно типичное множество Aε,strong(n) определяется как множество последовательностей, удовлетворяющих условию
где N(x, n) – число появлений конкретного символа x в последовательности. Можно показать, что сильно типичные последовательности также являются слабо типичными (с другой константой ε), что и объясняет название. Однако эти две формы не эквивалентны. С сильной типичностью часто проще работать при доказательстве теорем для каналов без памяти. Тем не менее, как следует из определения, эта форма типичности определена только для случайных величин с конечной областью значений.
Совместно типичные последовательности
Две последовательности x и y являются совместно ε-типичными, если пара (x, y) является ε-типичной относительно совместного распределения p(x, y), и обе последовательности x и y являются ε-типичными относительно своих предельных распределений p(x) и p(y) соответственно. Множество всех таких пар последовательностей обозначается как множество совместно ε-типичных последовательностей. Пусть x и y будут двумя независимыми последовательностями случайных величин с одинаковыми предельными распределениями p(x) и p(y). Тогда для любого ε > 0, при достаточно большом n, совместно типичные последовательности удовлетворяют следующим свойствам:
Типичное декодирование множества
В теории информации типичное декодирование множеств используется совместно со случайным кодированием для оценки переданного сообщения как сообщения, кодовое слово которого совместно ε-типично относительно наблюдения. То есть,
где – оценка сообщения, кодовое слово сообщения и наблюдение соответственно. определяется относительно совместного распределения , где – вероятность перехода, характеризующая статистику канала, а – некоторое входное распределение, используемое для генерации кодовых слов в случайном коде.