Типовой набор

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

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

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

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

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

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

где

$H(X)=-\sum _{x\in {\mathcal {X}}}p(x)\log _{2}p(x)$

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

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

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

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

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

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

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

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

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

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

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

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

поскольку n становится очень большим, поскольку $H(X)<\log _{2}|{\mathcal {X}}|,$ где $|{\mathcal {X}}|$ это мощность ​ ${\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, а

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

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

$-{\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 . Таким образом, мы имеем

$-{\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 взята из некоторого заданного совместного распределения, определенного в конечном или бесконечном алфавите ${\mathcal {X}}$, то сильно типичное множество A _ε,strong ^{( н )} $\in {\mathcal {X}}$ определяется как набор последовательностей, которые удовлетворяют

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

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

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

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

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

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

1. $P\left[(X^{n},Y^{n})\in A_{\varepsilon }^{n}(X,Y)\right]\geqslant 1-\epsilon$
2. $\left|A_{\varepsilon }^{n}(X,Y)\right|\leqslant 2^{n(H(X,Y)+\epsilon )}$
3. $\left|A_{\varepsilon }^{n}(X,Y)\right|\geqslant (1-\epsilon )2^{n(H(X,Y)-\epsilon )}$
4. $P\left[({\tilde {X}}^{n},{\tilde {Y}}^{n})\in A_{\varepsilon }^{n}(X,Y)\right]\leqslant 2^{-n(I(X;Y)-3\epsilon )}$
5. $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) , в то же время гарантируя, что вероятность ошибки кодирования ограничена ε. Асимптотически, согласно AEP, он не имеет потерь и достигает минимальной скорости, равной скорости энтропии источника.

Декодирование типичного набора

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

${\hat {w}}=w\iff (\exists w)((x_{1}^{n}(w),y_{1}^{n})\in A_{\varepsilon }^{n}(X,Y))$

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

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

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

См. также

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

Ссылки

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