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

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

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

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

Определение

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

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

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

Источники идентификаторов дискретного времени

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

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

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

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

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

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

Сходимость в смысле L1 утверждает еще более сильное утверждение.

$$\mathbb {E} \left[\left|\lim _{n\to \infty }-{\frac {1}{n}}\log p(X_{1},X_{2},\ldots ,X_{n})-H(X)\right|\right]=0$$

конечнозначные, стационарные

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

Эскиз доказательства

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

Нестационарный источник дискретного времени,

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

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

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

где

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

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

Доказательство следует из простого применения неравенства Маркова (применительно ко второму моменту $\log(p(X_{i}))$.

$${\begin{aligned}\Pr \left[\left|-{\frac {1}{n}}\log p(X_{1},X_{2},\ldots ,X_{n})-{\overline {H}}(X)\right|>\varepsilon \right]&\leq {\frac {1}{n^{2}\varepsilon ^{2}}}\mathrm {Var} \left[\sum _{i=1}^{n}\left(\log(p(X_{i})\right)^{2}\right]\\&\leq {\frac {M}{n\varepsilon ^{2}}}\to 0{\text{ as }}n\to \infty \end{aligned}}$$

Очевидно, что доказательство справедливо, если в какой-либо момент $\mathrm {E} \left[|\log p(X_{i})|^{r}\right]$равномерно ограничено при r > 1 (опять же по неравенству Маркова, примененному к r -му моменту). КЭД

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

Приложения

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

Теоретико-мерная форма

${\textstyle T}$ представляет собой сохраняющее меру отображение вероятностного пространства ${\textstyle \Omega }$.

Если ${\textstyle P}$ является конечным или счетным разбиением ${\textstyle \Omega }$, то его энтропия равна $H(P):=-\sum _{p\in P}\mu (p)\ln \mu (p)$ с соглашением, что $0\ln 0=0$.

Мы рассматриваем только разбиения с конечной энтропией: ${\textstyle H(P)<\infty }$.

Если ${\textstyle P}$ является конечным или счетным разбиением ${\textstyle \Omega }$, затем строим последовательность разбиений путем итерации карты:

$$P^{(n)}:=P\vee T^{-1}P\vee \dots \vee T^{-(n-1)}P$$

где ${\textstyle P\vee Q}$ является разделом с наименьшей верхней границей, то есть наименее уточненным разделом, который уточняет оба ${\textstyle P}$ и ${\textstyle Q}$:

$$P\vee Q:=\{p\cap q:p\in P,q\in Q\}$$

Писать ${\textstyle P(x)}$ быть установленным в ${\textstyle P}$ где ${\textstyle x}$ впадает. Так, например, ${\textstyle P^{(n)}(x)}$ это ${\textstyle n}$ -буквенный начальный сегмент ${\textstyle (P,T)}$ -Имя ${\textstyle x}$.

Писать ${\textstyle I_{P}(x)}$ быть информацией (в единицах nats ) о ${\textstyle x}$ мы можем восстановить, если знаем, какой элемент в разделе ${\textstyle P}$ что ${\textstyle x}$ попадает:

$$I_{P}:=-\ln \mu (P(x))$$

Аналогично, условная информация раздела ${\textstyle P}$, при условии разделения ${\textstyle Q}$, о ${\textstyle x}$, является

$$I_{P|Q}(x):=-\ln {\frac {P\vee Q(x)}{Q(x)}}$$

${\textstyle h_{T}(P)}$ энтропия Колмогорова -Синая

$$h_{T}(P):=\lim _{n}{\frac {1}{n}}H(P^{(n)})=\lim _{n}E_{x\sim \mu }\left[{\frac {1}{n}}I_{P^{(n)}}(x)\right]$$

Другими словами, по определению мы имеем сходимость ожиданий. Теорема SMB утверждает, что когда ${\textstyle T}$ эргодична, то мы имеем сходимость в L1.

Теорема   (эргодический случай) — Если ${\textstyle T}$ эргодично, то

$$x\mapsto {\frac {1}{n}}I_{P^{(n)}}(x)$$

сходится в L1 к постоянной функции ${\textstyle x\mapsto h_{T}(P)}$.

Другими словами,

$$E_{x\sim \mu }\left[\left|\lim _{n}{\frac {1}{n}}I_{P^{(n)}}(x)-h_{T}(P)\right|\right]=0$$

В частности, поскольку сходимость L1 предполагает сходимость почти наверняка,

$$h_{T}(P)=\lim _{n}{\frac {1}{n}}I_{P^{(n)}}(x)$$

с вероятностью 1.

Следствие   (свойство равнораспределения энтропии) — ${\textstyle \forall \epsilon >0,\exists N,\forall n\geq N}$, мы можем разделить раздел ${\textstyle \vee _{k=0}^{n-1}T^{-k}P}$ на две части, «хорошую» часть ${\textstyle G}$ и «плохая» часть ${\textstyle B}$.

Плохая часть небольшая:

$$\sum _{b\in B}\mu (b)<\epsilon$$

Хорошая часть практически равномерно распределена по энтропии:

$$\forall g\in G,\quad -{\frac {1}{n}}\ln \mu (g)\in h_{T}(P)\pm \epsilon$$

Если ${\textstyle T}$ не обязательно эргодично, то базовое вероятностное пространство будет разделено на несколько подмножеств, каждое из которых инвариантно относительно ${\textstyle T}$. В этом случае мы все еще имеем сходимость L1 к некоторой функции, но эта функция уже не является постоянной функцией.

Теорема   (общий случай) — Пусть ${\textstyle {\mathcal {I}}}$ быть сигма-алгеброй, порожденной всеми ${\textstyle T}$ -инвариантные измеримые подмножества ${\textstyle \Omega }$, -

$$x\mapsto {\frac {1}{n}}I_{P^{(n)}}(x)$$

сходится в L1 к

$$x\mapsto E\left[\lim _{n}I_{P|\vee _{k=1}^{n}T^{-k}P}{\big |}\;{\mathcal {I}}\right]$$

Когда ${\textstyle T}$ является эргодическим, ${\textstyle {\mathcal {I}}}$ тривиально, поэтому функция

$$x\mapsto E\left[\lim _{n}I_{P|\vee _{k=1}^{n}T^{-k}P}{\big |}\;{\mathcal {I}}\right]$$

упрощается до постоянной функции ${\textstyle x\mapsto E\left[\lim _{n}I_{P|\vee _{k=1}^{n}T^{-k}P}\right]}$, что по определению равно ${\textstyle \lim _{n}H(P|\vee _{k=1}^{n}T^{-k}P)}$, что равно ${\textstyle h_{T}(P)}$ по предложению.

непрерывном времени

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

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

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

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

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

Теория категорий

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

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

$$|P-Q|_{\pi }=|P\setminus P'|+|Q\setminus Q'|,$$

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

Аналогично определите

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

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

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

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

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

Дана однородная пространственная последовательность H _N , асимптотически эквивалентная P ^Н , энтропию H ( P ) P можно принять как

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

См. также

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

Ссылки

Журнальные статьи

• Клод Э. Шеннон. « Математическая теория связи ». Технический журнал Bell System , июль/октябрь 1948 г.
• Серджио Верду и Те Сун Хан. «Роль свойства асимптотического равнораспределения в бесшумном исходном кодировании». Транзакции IEEE по теории информации , 43 (3): 847–857, 1997.

Учебники

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