Типовой набор - Typical set

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

Это имеет большое значение в теории сжатия, поскольку предоставляет теоретические средства для сжатия данных, позволяя нам представить любую последовательность X ^n, используя в среднем nH ( X ) бит, и, следовательно, оправдывая использование энтропии в качестве меры информации из источник.

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

(Слабо) типичные последовательности (слабая типичность, энтропийная типичность)

Если последовательность x ₁ , ...,  x _n взята из распределения идентификаторов X, определенного в конечном алфавите , то типичный набор A _ε ^{( n ) ( n )} определяется как те последовательности, которые удовлетворяют: ${\ Displaystyle {\ mathcal {X}}}$${\ displaystyle \ in {\ mathcal {X}}}$

${\ displaystyle 2 ^ {- n (H (X) + \ varepsilon)} \ leqslant p (x_ {1}, x_ {2}, \ dots, x_ {n}) \ leqslant 2 ^ {- n (H ( X) - \ varepsilon)}}$

где

${\ Displaystyle H (X) = - \ сумма _ {y \ in {\ mathcal {X}}} p (y) \ log _ {2} p (y)}$

является информационная энтропия  X . Вероятность, указанная выше, должна быть только в пределах 2 ^{n ε} . Взяв логарифм со всех сторон и разделив на -n , это определение можно эквивалентно сформулировать как

${\ Displaystyle H (X) - \ varepsilon \ leq - {\ frac {1} {n}} \ log _ {2} p (x_ {1}, x_ {2}, \ ldots, x_ {n}) \ leq H (X) + \ varepsilon.}$

Для последовательности идентификаторов, поскольку

${\ displaystyle p (x_ {1}, x_ {2}, \ ldots, x_ {n}) = \ prod _ {i = 1} ^ {n} p (x_ {i}),}$

у нас также есть

${\ Displaystyle H (X) - \ varepsilon \ leq - {\ frac {1} {n}} \ sum _ {i = 1} ^ {n} \ log _ {2} p (x_ {i}) \ leq H (X) + \ varepsilon.}$

По закону больших чисел при достаточно большом n

${\ displaystyle - {\ frac {1} {n}} \ sum _ {i = 1} ^ {n} \ log _ {2} p (x_ {i}) \ rightarrow H (X).}$

Характеристики

Существенной характеристикой типичного набора является то, что если извлечь большое количество n независимых случайных выборок из распределения X , результирующая последовательность ( x ₁ ,  x ₂ , ...,  x _n ) с большой вероятностью будет членом типичного набора, хотя типичный набор включает лишь небольшую часть всех возможных последовательностей. Формально для любого можно выбрать n такое, что: ${\ displaystyle \ varepsilon> 0}$

1. Вероятность того, что последовательность из X ⁽ⁿ⁾ будет получена из A _ε ^{( n )} , больше 1 -  ε , т. Е. ${\ Displaystyle Pr [х ^ {(n)} \ in A _ {\ epsilon} ^ {(n)}] \ geq 1- \ varepsilon}$
2. ${\ displaystyle \ left | {A _ {\ varepsilon}} ^ {(n)} \ right | \ leqslant 2 ^ {n (H (X) + \ varepsilon)}}$
3. ${\ displaystyle \ left | {A _ {\ varepsilon}} ^ {(n)} \ right | \ geqslant (1- \ varepsilon) 2 ^ {n (H (X) - \ varepsilon)}}$
4. Если распределение по неравномерно, то доля типичных последовательностей равна ${\ Displaystyle {\ mathcal {X}}}$

${\ displaystyle {\ frac {| A _ {\ epsilon} ^ {(n)} |} {| {\ mathcal {X}} ^ {(n)} |}} \ Equiv {\ frac {2 ^ {nH ( X)}} {2 ^ {n \ log _ {2} | {\ mathcal {X}} |}}} = 2 ^ {- n (\ log _ {2} | {\ mathcal {X}} | - H (X))} \ rightarrow 0}$

а п становится очень большим, так как, когда это количество элементов из . ${\ Displaystyle Н (Х) <\ журнал _ {2} | {\ mathcal {X}} |,}$${\ displaystyle | {\ mathcal {X}} |}$${\ Displaystyle {\ mathcal {X}}}$

Для общего случайного процесса { X ( t )} с AEP (слабо) типичное множество может быть определено аналогично с заменой p ( x ₁ ,  x ₂ , ...,  x _n ) на p ( x ₀ ^τ ) (т. Е. вероятность того, что выборка будет ограничена временным интервалом [0,  τ ]), где n - степень свободы процесса во временном интервале, а H ( X ) - скорость энтропии . Если процесс является непрерывным, вместо него используется дифференциальная энтропия .

Пример

Как ни странно, наиболее вероятная последовательность часто не входит в типичный набор. Например, предположим, что X - это iid случайная величина Бернулли с p (0) = 0,1 и p (1) = 0,9. В n независимых испытаниях, поскольку p (1)> p (0), наиболее вероятной последовательностью результата является последовательность всех единиц, (1,1, ..., 1). Здесь энтропия X равна H ( X ) = 0,469, а

${\ displaystyle - {\ frac {1} {n}} \ log _ {2} p \ left (x ^ {(n)} = (1,1, \ ldots, 1) \ right) = - {\ frac {1} {n}} \ log _ {2} (0,9 ^ {n}) = 0,152}$

Таким образом, эта последовательность не входит в типичный набор, потому что ее средняя логарифмическая вероятность не может сколь угодно приближаться к энтропии случайной величины X, независимо от того, насколько большим мы принимаем значение n .

Для случайных величин Бернулли типичный набор состоит из последовательностей со средним числом нулей и единиц в n независимых испытаниях. Это легко продемонстрировать: если p (1) = p и p (0) = 1-p , то для n испытаний с m единицами имеем

${\ displaystyle - {\ frac {1} {n}} \ log _ {2} p (x ^ {(n)}) = - {\ frac {1} {n}} \ log _ {2} p ^ {m} (1-p) ^ {nm} = - {\ frac {m} {n}} \ log _ {2} p- \ left ({\ frac {nm} {n}} \ right) \ log _ {2} (1-п.).}$

Среднее количество единиц в последовательности испытаний Бернулли m = np . Таким образом, мы имеем

${\ displaystyle - {\ frac {1} {n}} \ log _ {2} p (x ^ {(n)}) = - p \ log _ {2} p- (1-p) \ log _ { 2} (1-p) = H (X).}$

В этом примере, если n = 10, то типичный набор состоит из всех последовательностей, которые имеют единственный 0 во всей последовательности. Если p (0) = p (1) = 0,5, то всевозможные двоичные последовательности принадлежат типичному набору.

Сильно типичные последовательности (сильная типичность, буквенная типичность)

Если последовательность x ₁ , ..., x _n взята из некоторого заданного совместного распределения, определенного в конечном или бесконечном алфавите , то строго типичное множество A _{ε, strong} ^{( n )} определяется как набор последовательностей, которые удовлетворяют ${\ Displaystyle {\ mathcal {X}}}$${\ displaystyle \ in {\ mathcal {X}}}$

${\ displaystyle \ left | {\ frac {N (x_ {i})} {n}} - p (x_ {i}) \ right | <{\ frac {\ varepsilon} {\ | {\ mathcal {X}) } \ |}}.}$

где - количество вхождений определенного символа в последовательности. ${\ displaystyle {N (x_ {i})}}$

Можно показать, что сильно типичные последовательности также являются слабо типичными (с другой постоянной ε), отсюда и название. Однако эти две формы не эквивалентны. С сильной типичностью часто легче работать при доказательстве теорем для каналов без памяти. Однако, как видно из определения, эта форма типичности определяется только для случайных величин, имеющих конечный носитель.

Совместно типичные последовательности

Две последовательности и вместе являются ε-типичными, если пара является ε-типичной по отношению к совместному распределению, и обе и являются ε-типичными по отношению к их маргинальным распределениям и . Множество всех таких пар последовательностей обозначается через . Аналогично определяются совместно ε-типичные последовательности из n наборов. ${\ Displaystyle х ^ {п}}$${\ Displaystyle у ^ {п}}$${\ Displaystyle (х ^ {п}, у ^ {п})}$${\ displaystyle p (x ^ {n}, y ^ {n}) = \ prod _ {i = 1} ^ {n} p (x_ {i}, y_ {i})}$${\ Displaystyle х ^ {п}}$${\ Displaystyle у ^ {п}}$${\ Displaystyle p (х ^ {п})}$${\ Displaystyle р (у ^ {п})}$${\ Displaystyle (х ^ {п}, у ^ {п})}$${\ Displaystyle А _ {\ varepsilon} ^ {п} (X, Y)}$

Позвольте и быть двумя независимыми последовательностями случайных величин с одинаковыми маргинальными распределениями и . Тогда для любого ε> 0 и достаточно большого n совокупно типичные последовательности удовлетворяют следующим свойствам: ${\ Displaystyle {\ тильда {X}} ^ {п}}$${\ Displaystyle {\ тильда {Y}} ^ {п}}$${\ Displaystyle p (х ^ {п})}$${\ Displaystyle р (у ^ {п})}$

1. ${\ displaystyle P \ left [(X ^ {n}, Y ^ {n}) \ in A _ {\ varepsilon} ^ {n} (X, Y) \ right] \ geqslant 1- \ epsilon}$
2. ${\ displaystyle \ left | A _ {\ varepsilon} ^ {n} (X, Y) \ right | \ leqslant 2 ^ {n (H (X, Y) + \ epsilon)}}$
3. ${\ displaystyle \ left | A _ {\ varepsilon} ^ {n} (X, Y) \ right | \ geqslant (1- \ epsilon) 2 ^ {n (H (X, Y) - \ epsilon)}}$
4. ${\ displaystyle P \ left [({\ tilde {X}} ^ {n}, {\ tilde {Y}} ^ {n}) \ in A _ {\ varepsilon} ^ {n} (X, Y) \ right ] \ leqslant 2 ^ {- n (I (X; Y) -3 \ epsilon)}}$
5. ${\ displaystyle P \ left [({\ tilde {X}} ^ {n}, {\ tilde {Y}} ^ {n}) \ in A _ {\ varepsilon} ^ {n} (X, Y) \ right ] \ geqslant (1- \ epsilon) 2 ^ {- n (I (X; Y) +3 \ epsilon)}}$

Приложения типичности

Типовая кодировка набора

В теории информации типичное кодирование набора кодирует только последовательности в типичном наборе стохастического источника с блочными кодами фиксированной длины. Поскольку размер типичного набора составляет около 2 ^{nH (X)} , для кодирования требуется только nH (X) битов, в то же время гарантируя, что вероятность ошибки кодирования ограничена значением ε. Асимптотически это, согласно AEP, без потерь и достигает минимальной скорости, равной скорости энтропии источника.

Типовой набор декодирования

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

${\ displaystyle {\ hat {w}} = w \ iff (\ существует w) ((x_ {1} ^ {n} (w), y_ {1} ^ {n}) \ in A _ {\ varepsilon} ^ {n} (X, Y))}$

где - оценка сообщения, кодовое слово сообщения и наблюдение соответственно. определяется относительно совместного распределения, где - вероятность перехода, которая характеризует статистику канала, и является некоторым входным распределением, используемым для генерации кодовых слов в случайной кодовой книге. ${\ displaystyle {\ hat {w}}, x_ {1} ^ {n} (w), y_ {1} ^ {n}}$${\ displaystyle w}$${\ Displaystyle А _ {\ varepsilon} ^ {п} (X, Y)}$${\ Displaystyle p (x_ {1} ^ {n}) p (y_ {1} ^ {n} | x_ {1} ^ {n})}$${\ displaystyle p (y_ {1} ^ {n} | x_ {1} ^ {n})}$${\ displaystyle p (x_ {1} ^ {n})}$

Универсальная проверка нулевой гипотезы

Универсальный код канала

Смотрите также

• Свойство асимптотического равнораспределения
• Теорема исходного кода
• Теорема кодирования с шумом

Рекомендации

• CE Shannon , " Математическая теория коммуникации ", Bell System Technical Journal , вып. 27, стр. 379–423, 623–656, июль, октябрь 1948 г.
• Обложка, Томас М. (2006). «Глава 3: Свойство асимптотической равнораспределенности, Глава 5: Сжатие данных, Глава 8: Пропускная способность канала». Элементы теории информации . Джон Вили и сыновья. ISBN   0-471-24195-4 .
• Дэвид Дж . К. Маккей . Теория информации, логический вывод и алгоритмы обучения Кембридж: Cambridge University Press, 2003. ISBN   0-521-64298-1