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

Теория информации
Энтропия Дифференциальная энтропия Условная энтропия Совместная энтропия Взаимная информация Условная взаимная информация Относительная энтропия Скорость энтропии Предельная плотность дискретных точек
Асимптотическое свойство равнораспределения Теория скорости – искажения
Теорема Шеннона о кодировании источника Емкость канала Теорема кодирования с шумом Теорема Шеннона – Хартли.
v т е

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

Грубо говоря, теорема утверждает, что, хотя существует множество серий результатов, которые могут быть получены случайным процессом, фактически полученный результат, скорее всего, является результатом слабо определенного набора результатов, которые имеют примерно одинаковые шансы на то, чтобы быть фактически реализованным. . (Это следствие закона больших чисел и эргодической теории .) Хотя есть отдельные исходы, которые имеют более высокую вероятность, чем любой исход в этом наборе, огромное количество исходов в наборе почти гарантирует, что исход будет исходить из набор. Один из способов интуитивного понимания свойства - использовать теорему Крамера о большом отклонении, который гласит, что вероятность большого отклонения от среднего экспоненциально спадает с количеством выборок. Такие результаты изучаются в теории больших уклонений ; интуитивно понятно, что именно большие отклонения нарушают равнораспределение, но это маловероятно.

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

Определение [ править ]

Для стационарного эргодического случайного процесса с дискретным временем на вероятностном пространстве свойство асимптотической равнораспределенности является утверждением, что${\ displaystyle X}$ ${\ displaystyle (\ Omega, B, p)}$

${\ displaystyle - {\ frac {1} {n}} \ log p (X_ {1}, X_ {2}, \ dots, X_ {n}) \ to H (X) \ quad {\ text {as} } \ quad n \ to \ infty}$

где либо просто обозначает энтропию скорость из , которая должна существовать для всех дискретных стационарных процессов , включая эргодические них. Свойство асимптотического равнораспределения доказывается для конечнозначных (т.е. ) стационарных эргодических случайных процессов в теореме Шеннона – Макмиллана – Бреймана с использованием эргодической теории и для любых источников iid непосредственно с использованием закона больших чисел как в дискретнозначном случае (где просто энтропия символа) и непрерывнозначный случай (где H${\ Displaystyle H (X)}$${\ displaystyle H}$${\ displaystyle X}$${\ displaystyle | \ Omega | <\ infty}$${\ displaystyle H}$- это дифференциальная энтропия). Определение свойства асимптотической равнораспределенности также может быть расширено для некоторых классов случайных процессов с непрерывным временем, для которых типичный набор существует в течение достаточно длительного времени наблюдения. Сходимость доказана почти во всех случаях.

Источники идентификаторов с дискретным временем [ править ]

Дан источник iid, который может принимать значения в алфавите , его временной ряд - iid с энтропией . Слабый закон больших чисел дает свойство асимптотической равнораспределенности со сходимостью по вероятности :${\ displaystyle X}$${\ Displaystyle {\ mathcal {X}}}$ ${\ Displaystyle X_ {1}, \ ldots, X_ {n}}$ ${\ Displaystyle H (X)}$

${\ displaystyle \ lim _ {n \ to \ infty} \ Pr \ left [\ left | - {\ frac {1} {n}} \ log p (X_ {1}, X_ {2}, \ ldots, X_ {n}) - H (X) \ right |> \ epsilon \ right] = 0 \ qquad \ forall \ epsilon> 0.}$

поскольку энтропия равна математическому ожиданию

${\ displaystyle - {\ frac {1} {n}} \ log p (X_ {1}, X_ {2}, \ ldots, X_ {n}).}$^[1]

Сильный закон больших чисел утверждает более сильную почти верную сходимость,

${\displaystyle \Pr \left[\lim _{n\to \infty }-{\frac {1}{n}}\log p(X_{1},X_{2},\ldots ,X_{n})=H(X)\right]=1.}$

Дискретное время конечнозначные стационарные эргодические источники [ править ]

Рассмотрим конечнозначное пространство выборок , т. Е. Для дискретного времени стационарного эргодического процесса, определенного на вероятностном пространстве . Свойство асимптотического равнораспределения для такого стохастического источника известно как теорема Шеннона – Макмиллана – Бреймана , принадлежащая Клоду Шеннону , Броквею Макмиллану и Лео Брейману .${\displaystyle \Omega }$${\displaystyle |\Omega |<\infty }$ ${\displaystyle X:=\{X_{n}\}}$ ${\displaystyle (\Omega ,B,p)}$

Доказательство (набросок) [2]

Обозначим через x некоторое измеримое множество для некоторого${\displaystyle x=X(A)}$${\displaystyle A\in B}$ Параметризуйте совместную вероятность n и x как ${\displaystyle j(n,x):=p\left(x_{0}^{n-1}\right).}$ Параметризуйте условную вероятность i , k и x как ${\displaystyle c(i,k,x):=p\left(x_{i}\mid x_{i-k}^{i-1}\right).}$ Возьмем предел условной вероятности при k → ∞ и обозначим его как ${\displaystyle c(i,x):=p\left(x_{i}\mid x_{-\infty }^{i-1}\right).}$ Спорить о двух понятиях скорости энтропии ${\displaystyle \lim _{n\to \infty }\mathrm {E} [-\log j(n,X)]\quad {\text{and}}\quad \lim _{n\to \infty }\mathrm {E} [-\log c(n,n,X)]}$ существует и равны для любого стационарного процесса , включая стационарную эргодическую процесса X . Обозначим его как H . Утверждают, что оба ${\displaystyle {\begin{aligned}c(i,k,X)&:=\left\{p\left(X_{i}\mid X_{i-k}^{i-1}\right)\right\}\\c(i,X)&:=\left\{p\left(X_{i}\mid X_{-\infty }^{i-1}\right)\right\}\end{aligned}}}$ где i - временной индекс, - стационарные эргодические процессы, выборочные средние которых почти наверняка сходятся к некоторым значениям, обозначенным и соответственно.${\displaystyle H^{k}}$${\displaystyle H^{\infty }}$ Определим марковское приближение k-го порядка для вероятности как${\displaystyle a(n,k,x)}$ ${\displaystyle a(n,k,x):=p\left(X_{0}^{k-1}\right)\prod _{i=k}^{n-1}p\left(X_{i}\mid X_{i-k}^{i-1}\right)=j(k,x)\prod _{i=k}^{n-1}c(i,k,x)}$ Утверждают, что это конечно из предположения конечности.${\displaystyle a(n,k,X(\Omega ))}$ Выразите через выборочное среднее значение и покажите, что оно почти наверняка сходится к H k${\displaystyle -{\frac {1}{n}}\log a(n,k,X)}$${\displaystyle c(i,k,X)}$ Определите вероятностную меру ${\displaystyle a(n,x):=p\left(x_{0}^{n-1}\mid x_{-\infty }^{-1}\right).}$ Выразите через выборочное среднее значение и покажите, что оно почти наверняка сходится к H ∞ .${\displaystyle -{\frac {1}{n}}\log a(n,X)}$${\displaystyle c(i,X)}$ Утверждают, что при k → ∞, используя стационарность процесса.${\displaystyle H^{k}\searrow H}$ Докажите, что H = H ∞, используя теорему Леви о сходимости мартингалов и предположение конечности. Покажи это ${\displaystyle \mathrm {E} \left[{\frac {a(n,k,X)}{j(n,X)}}\right]=a(n,k,X(\Omega ))}$ что конечно, как утверждалось ранее. Покажи это ${\displaystyle \mathrm {E} \left[{\frac {j(n,X)}{a(n,X)}}\right]=1}$ обусловливая бесконечное прошлое и повторяя ожидания.${\displaystyle X_{-\infty }^{-1}}$ Покажи это ${\displaystyle \forall \alpha \in \mathbb {R} \ :\ \Pr \left[{\frac {a(n,k,X)}{j(n,X)}}\geq \alpha \right]\leq {\frac {a(n,k,X(\Omega ))}{\alpha }}}$ используя неравенство Маркова и полученное ранее математическое ожидание. Аналогично покажем, что ${\displaystyle \forall \alpha \in \mathbb {R} \ :\ \Pr \left[{\frac {j(n,X)}{a(n,X)}}\geq \alpha \right]\leq {\frac {1}{\alpha }},}$ что эквивалентно ${\displaystyle \forall \alpha \in \mathbb {R} \ :\ \Pr \left[{\frac {1}{n}}\log {\frac {j(n,X)}{a(n,X)}}\geq {\frac {1}{n}}\log \alpha \right]\leq {\frac {1}{\alpha }}.}$ Покажи эту слабость ${\displaystyle {\frac {1}{n}}\log {\frac {a(n,k,X)}{j(n,X)}}\quad {\text{and}}\quad {\frac {1}{n}}\log {\frac {j(n,X)}{a(n,X)}}}$ неположительны почти наверное, если положить α = n β для любого β> 1 и применить лемму Бореля – Кантелли . Покажите, что liminf и limsup ${\displaystyle -{\frac {1}{n}}\log j(n,X)}$ ограничены снизу и сверху почти наверное величинами H ∞ и H k соответственно путем разбиения логарифмов в предыдущем результате. Завершите доказательство, указав, что ранее было показано, что верхняя и нижняя границы стремятся к H при k → ∞.

Нестационарный источник дискретного времени, создающий независимые символы [ править ]

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

Мы предполагаем, что источник создает независимые символы, с возможной различной выходной статистикой в ​​каждый момент времени. Мы предполагаем, что статистика процесса известна полностью, то есть известно маргинальное распределение процесса, наблюдаемого в каждый момент времени. Совместное распределение - это всего лишь продукт маргиналов. Тогда при условии (которое может быть ослаблено), что для всех i , для некоторого M > 0 выполняется следующее (AEP):${\displaystyle \mathrm {Var} [\log p(X_{i})]<M}$

${\displaystyle \lim _{n\to \infty }\Pr \left[\,\left|-{\frac {1}{n}}\log p(X_{1},X_{2},\ldots ,X_{n})-{\overline {H}}_{n}(X)\right|<\epsilon \right]=1\qquad \forall \epsilon >0}$

где

${\displaystyle {\overline {H}}_{n}(X)={\frac {1}{n}}H(X_{1},X_{2},\ldots ,X_{n})}$

Доказательство

Доказательство следует из простого применения неравенства Маркова (примененного ко второму моменту .${\displaystyle \log(p(X_{i}))}$ ${\displaystyle {\begin{aligned}\Pr \left[\left|-{\frac {1}{n}}\log p(X_{1},X_{2},\ldots ,X_{n})-{\overline {H}}(X)\right|>\epsilon \right]&\leq {\frac {1}{n^{2}\epsilon ^{2}}}\mathrm {Var} \left[\sum _{i=1}^{n}\left(\log(p(X_{i})\right)^{2}\right]\\&\leq {\frac {M}{n\epsilon ^{2}}}\to 0{\text{ as }}n\to \infty \end{aligned}}}$ Очевидно, что доказательство справедливо, если любой момент равномерно ограничен при r > 1 (снова в силу неравенства Маркова, примененного к r -ому моменту).${\displaystyle \mathrm {E} \left[|\log p(X_{i})|^{r}\right]}$${\displaystyle \Box {}}$ Даже это условие не является обязательным, но, учитывая нестационарный случайный процесс, нетрудно проверить, выполняется ли свойство асимптотической равнораспределенности, используя описанный выше метод.

Приложения [ править ]

Свойство асимптотического равнораспределения для нестационарного независимого от дискретного времени процесса приводит нас (среди других результатов) к теореме кодирования источника для нестационарного источника (с независимыми выходными символами) и теореме кодирования с шумом для нестационарных каналов без памяти.

Стационарные эргодические источники непрерывного времени [ править ]

Функции с дискретным временем могут быть интерполированы на функции с непрерывным временем. Если такая интерполяция F является измеримым , мы можем определить стационарный процесс непрерывного времени соответственно , как . Если свойство асимптотического равнораспределения выполняется для процесса с дискретным временем, как в iid или конечнозначных стационарных эргодических случаях, показанных выше, оно автоматически выполняется для стационарного процесса с непрерывным временем, полученного из него некоторой измеримой интерполяцией. т.е.${\displaystyle {\tilde {X}}:=f\circ X}$

${\displaystyle -{\frac {1}{n}}\log p({\tilde {X}}_{0}^{\tau })\to H(X)}$

где n соответствует степени свободы по времени τ . nH ( X ) / τ и H ( X ) - энтропия в единицу времени и на степень свободы соответственно, определенная Шенноном .

Важным классом таких стационарных процессов с непрерывным временем является стационарный эргодический процесс с ограниченной полосой пропускания, в котором пространство отсчетов является подмножеством непрерывных функций. Свойство асимптотического равнораспределения сохраняется, если процесс белый, и в этом случае временные отсчеты iid, или существует T > 1/2 W , где W - номинальная ширина полосы , так что временные отсчеты с интервалом T принимают значения в конечном множество, и в этом случае мы имеем конечнозначный стационарный эргодический процесс с дискретным временем.${\displaystyle {\mathcal {L}}_{2}}$

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

Теория категорий [ править ]

Категории теоретико определение свойства равнораспределении дается Громовым . ^[3] Для данной последовательности декартовых степеней пространства с мерой P эта последовательность допускает асимптотически эквивалентную последовательность H _N однородных пространств с мерой ( т. Е. Все множества имеют одну и ту же меру; все морфизмы инвариантны относительно группы автоморфизмов и, таким образом, разлагают на множители как морфизм к конечному объекту ).${\displaystyle P^{N}=P\times \cdots \times P}$

Сказанное выше требует определения асимптотической эквивалентности . Это дается в терминах функции расстояния, показывающей, насколько инъективное соответствие отличается от изоморфизма . Инъективное соответствие - это частично определенное отображение, которое является биекцией ; то есть это взаимно однозначное соответствие между подмножеством и . Затем определите${\displaystyle \pi :P\to Q}$${\displaystyle P'\subset P}$${\displaystyle Q'\subset Q}$

${\displaystyle |P-Q|_{\pi }=|P\smallsetminus P'|+|Q\smallsetminus Q'|}$

где | S | обозначает меру множества S . В дальнейшем мера P и Q принимается равной 1, так что пространства с мерой являются вероятностными. Это расстояние обычно называют расстоянием земного движителя или метрикой Вассерштейна .${\displaystyle |P-Q|_{\pi }}$

Аналогичным образом определим

${\displaystyle |\log P:Q|_{\pi }={\frac {\sup _{p\in P^{'}}|\log p-\log \pi (p)|}{\log \min \left(|\operatorname {set} (P')|,|\operatorname {set} (Q')|\right)}}}$

с берется подсчет мера на P . Таким образом, это определение требует, чтобы P было пространством с конечной мерой. Наконец, пусть${\displaystyle |\operatorname {set} (P)|}$

${\displaystyle {\text{dist}}_{\pi }(P,Q)=|P-Q|_{\pi }+|\log P:Q|_{\pi }}$

Последовательность инъективными соответствий затем асимптотически эквивалентны , когда${\displaystyle \pi _{N}:P_{N}\to Q_{N}}$

${\displaystyle {\text{dist}}_{\pi _{N}}(P_{N},Q_{N})\to 0\quad {\text{ as }}\quad N\to \infty }$

Учитывая однородную пространственную последовательность H _N, которая асимптотически эквивалентна P ^N , энтропия H ( P ) P может быть взята как

${\displaystyle H(P)=\lim _{N\to \infty }{\frac {1}{N}}|\operatorname {set} (H_{N})|}$

См. Также [ править ]

• Теорема Крамера о большом уклонении
• Теорема исходного кода
• Теорема кодирования с шумом

Заметки [ править ]

Ссылки [ править ]

Статьи журнала [ править ]

• Клод Э. Шеннон. « Математическая теория коммуникации ». Технический журнал Bell System , июль / октябрь 1948 г.
• Algoet, Paul H .; Обложка, Томас М. (1988). "Сэндвич-доказательство теоремы Шеннона-Макмиллана-Бреймана" (PDF) . Летопись вероятности . 16 (2): 899–909.
• Серхио Верду и Те Сун Хан. «Роль свойства асимптотической равнораспределенности в бесшумном исходном кодировании». IEEE Transactions по теории информации , 43 (3): 847–857, 1997.

Учебники [ править ]

• Обложка, Томас М .; Томас, Джой А. (1991). Элементы теории информации (первое изд.). Хобокен, Нью-Джерси: Wiley. ISBN 978-0-471-24195-9.
• Маккей, Дэвид JC (2003). Теория информации, выводы и алгоритмы обучения . Издательство Кембриджского университета. ISBN 0-521-64298-1.