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

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

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

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

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

Если последовательность Икс₁, ..., Икс_п взят из i.i.d. распределение Икс определенный над конечным алфавитом ${\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)=-\sum _{y\in {\mathcal {X}}}p(y)\log _{2}p(y)}$

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

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

Для последовательности i.i.d, поскольку

${\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 .}$

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

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

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

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

1. Вероятность последовательности из Икс^(п) взяты из А_ε^(п) больше 1 -ε, т.е. ${\displaystyle Pr[x^{(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 H(X)<\log _{2}|{\mathcal {X}}|,}$ куда ${\displaystyle |{\mathcal {X}}|}$ это мощность из ${\displaystyle {\mathcal {X}}}$.

Для общего случайного процесса {Икс(т)} с помощью AEP (слабо) типичное множество может быть определено аналогично с помощью п(Икс₁, Икс₂, ..., Икс_п) заменен на п(Икс₀^τ) (т.е. вероятность того, что выборка будет ограничена временным интервалом [0,τ]), п будучи степень свободы процесса во временном интервале и ЧАС(Икс) будучи скорость энтропии. Если процесс является непрерывным, дифференциальная энтропия вместо этого используется.

Пример

Как ни странно, наиболее вероятная последовательность часто не входит в типичный набор. Например, предположим, что Икс это i.i.d Случайная величина Бернулли с п(0) = 0,1 и п(1) = 0,9. В п независимые судебные процессы, поскольку п(1)>п(0), наиболее вероятной последовательностью результата является последовательность всех единиц, (1,1, ..., 1). Здесь энтропия Икс является ЧАС(Икс) = 0,469, а

${\displaystyle -{\frac {1}{n}}\log _{2}p(x^{(n)}=(1,1,\ldots ,1))=-{\frac {1}{n}}\log _{2}(0.9^{n})=0.152}$

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

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

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

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

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

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

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

Если последовательность Икс₁, ..., Икс_п берется из некоторого заданного совместного распределения, определенного в конечном или бесконечном алфавите ${\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})}}$ - это количество вхождений определенного символа в последовательности.

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

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

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

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

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^{нН (Х)}, Только нН (Х) биты требуются для кодирования, в то же время гарантируя, что вероятность ошибки кодирования ограничена до ε. Асимптотически это, согласно AEP, без потерь и достигает минимальной скорости, равной скорости энтропии источника.

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

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

${\displaystyle {\hat {w}}=w\iff (\exists 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 A_{\varepsilon }^{n}(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})}$ - некоторое входное распределение, используемое для генерации кодовых слов в случайной кодовой книге.

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

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

Смотрите также: теория алгоритмической сложности

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

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

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

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