Типичный набор

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

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

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

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

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

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

есть информационная энтропия  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 .}$

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

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

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

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

1. Вероятность того, что последовательность из X ⁽ⁿ⁾ будет извлечена из A _ε ^{( n )} , больше, чем 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}$

поскольку n становится очень большим, так как где мощность множества . ${\displaystyle H(X)<\log _{2}|{\mathcal {X}}|,}$ ${\displaystyle |{\mathcal {X}}|}$ ${\displaystyle {\mathcal {X}}}$

_Для общего стохастического процесса { X ( t )} с AEP (слабо) типичный набор может быть определен аналогично с заменой p ( x1 ,  x2 _, ...,  xn ₎ на p ( x0τ ) (т.е. вероятность выборки, ограниченной временным интервалом [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)^{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).}$

Для этого примера, если 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 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)}$

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

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 (\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})}$

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

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

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

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

Ссылки

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