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

редактировать

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

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

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

Содержание

1 Определение
2 Дискретное время i.i.d. источники
3 конечнозначные стационарные эргодические источники с дискретным временем
4 Нестационарный источник с дискретным временем, генерирующий независимые символы
- 4.1 Приложения
5 Стационарные эргодические источники с непрерывным временем
6 Теория категорий
7 См. Также
8 Примечания
9 Ссылки
- 9.1 Журнальные статьи
- 9.2 Учебники

Определение

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

- 1 n log ⁡ p (X 1, X 2,…, X n) → H (X) при n → ∞ {\ displaystyle - {\ frac {1} {n} } \ log p (X_ {1}, X_ {2}, \ dots, X_ {n}) \ to H (X) \ quad {\ text {as}} \ quad n \ to \ infty}

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

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

Дискретный i.i.d. sources

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

lim n → ∞ Pr [| - 1 n log ⁡ p (X 1, X 2,…, X n) - H (X) |>ϵ] = 0 ∀ ϵ>0. {\ 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.}

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

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

- 1 n log ⁡ p (X 1, X 2,…, X n). {\ displaystyle - {\ frac {1} {n}} \ log p (X_ {1}, X_ {2}, \ ldots, X_ {n}).}

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

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

Pr [lim n → ∞ - 1 n log ⁡ p (X 1, Икс 2,…, Икс 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 \ Pr \ left [\ lim _ {n \ to \ infty} - {\ frac {1} {n}} \ log p (X_ { 1}, X_ {2}, \ ldots, X_ {n}) = H (X) \ right] = 1.}

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

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

Доказательство (набросок)
Пусть x обозначает некоторое измеримое множество $x = X (A) {\ displaystyle x = X (A)}$ ${\ displaystyle x = X (A)}$ для некоторого $A ∈ B {\ displaystyle A \ in B}$ $A \ in B$ Параметризуйте совместную вероятность с помощью n и x как $j (n, x): = p (x 0 n - 1). {\ displaystyle j (n, x): = p \ left (x_ {0} ^ {n-1} \ right).}$ $j (n, x): = p \ left (x_ {0} ^ {{n-1}} \ right).$ Параметризуйте условную вероятность с помощью i, k и x как $c (i, k, x): = p (xi ∣ xi - ki - 1). {\ displaystyle c (i, k, x): = p \ left (x_ {i} \ mid x_ {ik} ^ {i-1} \ right).}$ $c (i, k, x): = p \ left (x_ {i} \ mid x _ {{ik}} ^ {{i-1}} \ right).$ Возьмите предел условной вероятности как k → ∞ и обозначим его как $c (i, x): = p (xi ∣ x - ∞ i - 1). {\ displaystyle c (i, x): = p \ left (x_ {i} \ mid x _ {- \ infty} ^ {i-1} \ right).}$ $c (i, x): = p \ left (x_ {i} \ mid x _ {{- \ infty}} ^ {{i-1}} \ right).$ Спорить о двух понятиях скорости энтропии $lim n → ∞ E [- журнал ⁡ J (n, X)] и lim n → ∞ E [- журнал ⁡ c (n, n, X)] {\ 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)]}$ $\ 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. Утверждают, что оба $c (i, k, X): = {p ( Икс я ∣ Икс я - ки - 1)} с (я, Икс): знак равно {п (Икс я ∣ Икс - ∞ я - 1)} {\ Displaystyle {\ begin {выровнено} с (я, к, X) : = \ left \ {p \ left (X_ {i} \ mid X_ {ik} ^ {i-1} \ right) \ right \} \\ c (i, X) : = \ left \ {p \ left (X_ {i} \ mid X _ {- \ infty} ^ {i-1} \ right) \ right \} \ end {align}}}$ ${\ begin {align} c (i, k, X) : = \ left \ {p \ left (X_ {i} \ mid X _ {{ik}} ^ {{i-1}} \ right) \ right \} \\ c (i, X) : = \ left \ {p \ left (X_ {i} \ mid X _ {{- \ infty}} ^ {{i-1}} \ right) \ right \} \ end {align}}$ где i - временной индекс, - стационарные эргодические процессы, чья выборка означает сходиться почти наверняка к некоторым значениям, обозначенным $H k {\ displaystyle H ^ {k}}$ $H ^ {k}$ и $H ∞ {\ displaystyle H ^ {\ infty}}$ ${\ displaystyle H ^ {\ infty}}$ соответственно. Определите kt Марковская аппроксимация вероятности h порядка $a (n, k, x) {\ displaystyle a (n, k, x)}$ $a (n, k, x)$ as $a (n, k, x): = p (X 0 k - 1) ∏ я знак равно кн - 1 п (Икс я ∣ Икс я - ки - 1) знак равно J (к, х) ∏ я = кн - 1 с (я, к, х) {\ Displaystyle а (п, к, х): = p \ left (X_ {0} ^ {k-1} \ right) \ prod _ {i = k} ^ {n-1} p \ left (X_ {i} \ mid X_ {ik} ^ { i-1} \ right) = j (k, x) \ prod _ {i = k} ^ {n-1} c (i, k, x)}$ $a (n, k, x): = p \ left (X_ {0} ^ {{k-1}} \ right) \ prod _ {{i = k}} ^ {{n-1}} p \ left (X_ {i} \ mid X _ {{ik}} ^ {{i-1}}} \ right) = j (k, x) \ prod _ {{i = k}} ^ {{n-1}} c (i, k, x)$ Утверждают, что $a (n, k, X (Ω)) {\ displaystyle a (n, k, X (\ Omega))}$ $a (n, k, X (\ Omega))$ конечно из предположения конечного значения. Express $- 1 n log ⁡ a (n, k, X) {\ displaystyle - {\ frac {1} {n}} \ log a (n, k, X)}$ $- { \ frac 1n} \ log a (n, k, X)$ в терминах выборочного среднего $c (i, k, X) {\ displaystyle c (i, k, X)}$ $c(i,k,X)$ и показать, что он почти наверняка сходится к H Определите вероятностную меру $a (n, x): = p (x 0 n - 1 ∣ x - ∞ - 1). {\ displaystyle a (n, x): = p \ left (x_ {0} ^ {n-1} \ mid x _ {- \ infty} ^ {- 1} \ right).}$ $a (n, x): = p \ left (x_ {0} ^ { {n-1}} \ mid x _ {{- \ infty}} ^ {{- 1}} \ right).$ Express $- 1 n log ⁡ a (n, X) {\ displaystyle - {\ frac {1} {n}} \ log a (n, X)}$ $- {\ frac 1n} \ log a (n, X)$ в терминах выборочного среднего $c (i, X) {\ displaystyle c (i, X)}$ $c (i, X)$ и показать, что он почти наверняка сходится к H. Утверждают, что $H k ↘ H {\ displaystyle H ^ {k} \ Searrow H}$ $H ^ {k} \ Searrow H$ при k → ∞ с использованием стационарности процесса. Докажите, что H = H, используя теорему о сходимости мартингалов Леви и предположение конечного значения. Покажите, что $E [a (n, k, X) j (n, X)] = a (n, k, X (Ω)) {\ displaystyle \ mathrm {E} \ left [{\ frac {a (n, k, X)} {j (n, X)}} \ right] = a (n, k, X (\ Omega))}$ ${\ mathrm {E}} \ left [{\ frac {a (n, k, X)} {j (n, X) }} \ right] = a (n, k, X (\ Omega))$ который конечно, как утверждалось ранее. Покажите, что $E [j (n, X) a (n, X)] = 1 {\ displaystyle \ mathrm {E} \ left [{\ frac {j (n, X)} {a (n, X)}} \ right] = 1}$ ${\ mathrm {E}} \ left [{\ frac {j (n, X)} {a (n, X)}} \ right] = 1$ путем обусловливания бесконечного прошлого $X - ∞ - 1 {\ displaystyle X _ {- \ infty} ^ {- 1}}$ $X _ {{- \ infty}} ^ {{- 1}}$ и повторение ожидания. Покажите, что $∀ α ∈ R: Pr [a (n, k, X) j (n, X) ≥ α] ≤ a (n, k, X (Ω)) α {\ 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}}}$ $\ 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 }}$ используя неравенство Маркова и математическое ожидание, полученное ранее. Аналогичным образом покажите, что $∀ α ∈ R: Pr [J (N, Икс) a (N, X) ≥ α] ≤ 1 α, {\ displaystyle \ 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 {j (n, X)} {a (n, X)}} \ geq \ alpha \ right] \ leq {\ frac {1} {\ alpha}},$ , что эквивалентно $∀ α ∈ R: Pr [1 n журнал j (n, X) a (n, X) ≥ 1 n журнал α] ≤ 1 α. {\ 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}}.}$ $\ forall \ alpha \ in {\ mathbb {R}} \: \ \ Pr \ left [{\ frac 1n} \ log {\ frac {j (n, X)} {a (n, X)}} \ geq {\ frac {1} {n}} \ log \ alpha \ right] \ leq {\ frac {1} {\ alpha}}.$ Покажите это limsup $1 n журнал ⁡ a (N, K, X) J (N, X) и 1 N журнал ⁡ J (N, X) a (N, X) {\ 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)}}}$ ${\ frac 1n} \ 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 of $- 1 n log ⁡ j (n, X) {\ displaystyle - {\ frac {1} {n}} \ log j (n, X)}$ $- {\ frac {1} {n}} \ log j (n, X)$ снизу и сверху ограничены почти наверняка H и H соответственно путем разбиения логарифмов в предыдущем результате. Завершите доказательство, указав, что верхняя и нижняя границы показаны ранее для приближения к H при k → ∞.

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

Пусть x обозначает некоторое измеримое множество $x = X (A) {\ displaystyle x = X (A)}$ ${\ displaystyle x = X (A)}$ для некоторого $A ∈ B {\ displaystyle A \ in B}$ $A \ in B$
Параметризуйте совместную вероятность с помощью n и x как

j (n, x): = p (x 0 n - 1). {\ displaystyle j (n, x): = p \ left (x_ {0} ^ {n-1} \ right).}

j (n, x): = p \ left (x_ {0} ^ {{n-1}} \ right).

Параметризуйте условную вероятность с помощью i, k и x как

c (i, k, x): = p (xi ∣ xi - ki - 1). {\ displaystyle c (i, k, x): = p \ left (x_ {i} \ mid x_ {ik} ^ {i-1} \ right).}

c (i, k, x): = p \ left (x_ {i} \ mid x _ {{ik}} ^ {{i-1}} \ right).

Возьмите предел условной вероятности как k → ∞ и обозначим его как

c (i, x): = p (xi ∣ x - ∞ i - 1). {\ displaystyle c (i, x): = p \ left (x_ {i} \ mid x _ {- \ infty} ^ {i-1} \ right).}

c (i, x): = p \ left (x_ {i} \ mid x _ {{- \ infty}} ^ {{i-1}} \ right).

Спорить о двух понятиях скорости энтропии

lim n → ∞ E [- журнал ⁡ J (n, X)] и lim n → ∞ E [- журнал ⁡ c (n, n, X)] {\ 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)]}

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

Утверждают, что оба

c (i, k, X): = {p ( Икс я ∣ Икс я - ки - 1)} с (я, Икс): знак равно {п (Икс я ∣ Икс - ∞ я - 1)} {\ Displaystyle {\ begin {выровнено} с (я, к, X) : = \ left \ {p \ left (X_ {i} \ mid X_ {ik} ^ {i-1} \ right) \ right \} \\ c (i, X) : = \ left \ {p \ left (X_ {i} \ mid X _ {- \ infty} ^ {i-1} \ right) \ right \} \ end {align}}}

{\ begin {align} c (i, k, X) : = \ left \ {p \ left (X_ {i} \ mid X _ {{ik}} ^ {{i-1}} \ right) \ right \} \\ c (i, X) : = \ left \ {p \ left (X_ {i} \ mid X _ {{- \ infty}} ^ {{i-1}} \ right) \ right \} \ end {align}}

где i - временной индекс, - стационарные эргодические процессы, чья выборка означает сходиться почти наверняка к некоторым значениям, обозначенным

H k {\ displaystyle H ^ {k}}

H ^ {k}

H ∞ {\ displaystyle H ^ {\ infty}}

{\ displaystyle H ^ {\ infty}}

соответственно.

Определите kt Марковская аппроксимация вероятности h порядка $a (n, k, x) {\ displaystyle a (n, k, x)}$ $a (n, k, x)$ as

a (n, k, x): = p (X 0 k - 1) ∏ я знак равно кн - 1 п (Икс я ∣ Икс я - ки - 1) знак равно J (к, х) ∏ я = кн - 1 с (я, к, х) {\ Displaystyle а (п, к, х): = p \ left (X_ {0} ^ {k-1} \ right) \ prod _ {i = k} ^ {n-1} p \ left (X_ {i} \ mid X_ {ik} ^ { i-1} \ right) = j (k, x) \ prod _ {i = k} ^ {n-1} c (i, k, x)}

a (n, k, x): = p \ left (X_ {0} ^ {{k-1}} \ right) \ prod _ {{i = k}} ^ {{n-1}} p \ left (X_ {i} \ mid X _ {{ik}} ^ {{i-1}}} \ right) = j (k, x) \ prod _ {{i = k}} ^ {{n-1}} c (i, k, x)

Утверждают, что $a (n, k, X (Ω)) {\ displaystyle a (n, k, X (\ Omega))}$ $a (n, k, X (\ Omega))$ конечно из предположения конечного значения.
Express $- 1 n log ⁡ a (n, k, X) {\ displaystyle - {\ frac {1} {n}} \ log a (n, k, X)}$ $- { \ frac 1n} \ log a (n, k, X)$ в терминах выборочного среднего $c (i, k, X) {\ displaystyle c (i, k, X)}$ $c(i,k,X)$ и показать, что он почти наверняка сходится к H
Определите вероятностную меру

a (n, x): = p (x 0 n - 1 ∣ x - ∞ - 1). {\ displaystyle a (n, x): = p \ left (x_ {0} ^ {n-1} \ mid x _ {- \ infty} ^ {- 1} \ right).}

a (n, x): = p \ left (x_ {0} ^ { {n-1}} \ mid x _ {{- \ infty}} ^ {{- 1}} \ right).

Express $- 1 n log ⁡ a (n, X) {\ displaystyle - {\ frac {1} {n}} \ log a (n, X)}$ $- {\ frac 1n} \ log a (n, X)$ в терминах выборочного среднего $c (i, X) {\ displaystyle c (i, X)}$ $c (i, X)$ и показать, что он почти наверняка сходится к H.
Утверждают, что $H k ↘ H {\ displaystyle H ^ {k} \ Searrow H}$ $H ^ {k} \ Searrow H$ при k → ∞ с использованием стационарности процесса.
Докажите, что H = H, используя теорему о сходимости мартингалов Леви и предположение конечного значения.
Покажите, что

E [a (n, k, X) j (n, X)] = a (n, k, X (Ω)) {\ displaystyle \ mathrm {E} \ left [{\ frac {a (n, k, X)} {j (n, X)}} \ right] = a (n, k, X (\ Omega))}

{\ mathrm {E}} \ left [{\ frac {a (n, k, X)} {j (n, X) }} \ right] = a (n, k, X (\ Omega))

который конечно, как утверждалось ранее.

Покажите, что

E [j (n, X) a (n, X)] = 1 {\ displaystyle \ mathrm {E} \ left [{\ frac {j (n, X)} {a (n, X)}} \ right] = 1}

{\ mathrm {E}} \ left [{\ frac {j (n, X)} {a (n, X)}} \ right] = 1

путем обусловливания бесконечного прошлого

X - ∞ - 1 {\ displaystyle X _ {- \ infty} ^ {- 1}}

X _ {{- \ infty}} ^ {{- 1}}

и повторение ожидания.

Покажите, что

∀ α ∈ R: Pr [a (n, k, X) j (n, X) ≥ α] ≤ a (n, k, X (Ω)) α {\ 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}}}

\ 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 }}

используя неравенство Маркова и математическое ожидание, полученное ранее.

Аналогичным образом покажите, что

∀ α ∈ R: Pr [J (N, Икс) a (N, X) ≥ α] ≤ 1 α, {\ displaystyle \ 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 {j (n, X)} {a (n, X)}} \ geq \ alpha \ right] \ leq {\ frac {1} {\ alpha}},

, что эквивалентно

∀ α ∈ R: Pr [1 n журнал j (n, X) a (n, X) ≥ 1 n журнал α] ≤ 1 α. {\ 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}}.}

\ forall \ alpha \ in {\ mathbb {R}} \: \ \ Pr \ left [{\ frac 1n} \ log {\ frac {j (n, X)} {a (n, X)}} \ geq {\ frac {1} {n}} \ log \ alpha \ right] \ leq {\ frac {1} {\ alpha}}.

Покажите это limsup

1 n журнал ⁡ a (N, K, X) J (N, X) и 1 N журнал ⁡ J (N, X) a (N, X) {\ 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)}}}

{\ frac 1n} \ 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 of

- 1 n log ⁡ j (n, X) {\ displaystyle - {\ frac {1} {n}} \ log j (n, X)}

- {\ frac {1} {n}} \ log j (n, X)

снизу и сверху ограничены почти наверняка H и H соответственно путем разбиения логарифмов в предыдущем результате.

Завершите доказательство, указав, что верхняя и нижняя границы показаны ранее для приближения к H при k → ∞.

Нестационарный источник с дискретным временем создание независимых символов

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

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

lim n → ∞ Pr [| - 1 n log ⁡ p (X 1, X 2,…, X n) - H ¯ n (X) | < ϵ ] = 1 ∀ ϵ>0 {\ 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}

\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

где

H ¯ n (X) = 1 n H (X 1, Икс 2,…, Икс n) {\ displaystyle {\ overline {H}} _ {n} (X) = {\ frac {1} {n}} H (X_ {1}, X_ {2}, \ ldots, X_ {n})}

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

Доказательство
Доказательство следует из простого применения неравенства Маркова (примененного ко второму моменту $log ⁡ (p (X i)) {\ displaystyle \ log (p (X_ {i}))}$ $\ log (p (X_ {i}))$ . $Pr [\| - 1 n журнал ⁡ p (X 1, X 2,…, X n) - H ¯ (X) \|>ϵ] ≤ 1 N 2 ϵ 2 В ар [∑ я = 1 N (журнал ⁡ (p (X i)) 2] ≤ M n ϵ 2 → 0 при n → ∞ {\ displaystyle {\ begin {align} \ 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} \ влево (\ log (p (X_ {i}) \ right) ^ {2} \ right] \\ \ leq {\ frac {M} {n \ epsilon ^ {2}}} \ to 0 {\ text {as}} n \ to \ infty \ end {align}} }$ ${\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}}} \ в 0 {\ text {as}} n \ to \ infty \ end {align}}$ Очевидно, что доказательство справедливо, если в любой момент $E [\| журнал ⁡ p (X i) \| r] {\ displaystyle \ mathrm {E} \ left [\| \ log p (X_ {i}) \| ^ {r} \ right]}$ ${\ displaystyle \ mathrm {E} \ left [\| \ log p (X_ {i}) \| ^ {r} \ right]}$ равномерно ограничен для r>1 (снова Неравенство Маркова применимо к r-му моменту). $◻ {\ displaystyle \ Box {}}$ $\ Box {}$ Даже это условие не является обязательным, но, учитывая нестационарный случайный процесс, нетрудно проверить, выполняется ли свойство асимптотического равнораспределения, используя описанный выше метод.

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

Доказательство следует из простого применения неравенства Маркова (примененного ко второму моменту

log ⁡ (p (X i)) {\ displaystyle \ log (p (X_ {i}))}

\ log (p (X_ {i}))

Pr [| - 1 n журнал ⁡ p (X 1, X 2,…, X n) - H ¯ (X) |>ϵ] ≤ 1 N 2 ϵ 2 В ар [∑ я = 1 N (журнал ⁡ (p (X i)) 2] ≤ M n ϵ 2 → 0 при n → ∞ {\ displaystyle {\ begin {align} \ 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} \ влево (\ log (p (X_ {i}) \ right) ^ {2} \ right] \\ \ leq {\ frac {M} {n \ epsilon ^ {2}}} \ to 0 {\ text {as}} n \ to \ infty \ end {align}} }

{\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}}} \ в 0 {\ text {as}} n \ to \ infty \ end {align}}

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

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

Приложения

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

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

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

- 1 n журнал п (Икс ~ 0 τ) → H (X) {\ displaystyle - {\ frac {1} {n}} \ log p ({\ tilde {X}} _ {0} ^ {\ tau}) \ to H (X)}

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

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

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

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

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

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

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

| P - Q | π = | P ∖ P ′ | + | Q ∖ Q ′ | {\ displaystyle | P-Q | _ {\ pi} = | P \ smallsetminus P '| + | Q \ smallsetminus Q' |}

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

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

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

| журнал ⁡ P: Q | π = sup p ∈ P ′ | журнал ⁡ p - журнал ⁡ π (p) | журнал ⁡ мин (| набор ⁡ (P ') |, | набор ⁡ (Q') |) {\ 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)}}}

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

dist π (P, Q) = | P - Q | π + | журнал ⁡ P: Q | π {\ displaystyle {\ text {dist}} _ {\ pi} (P, Q) = | PQ | _ {\ pi} + | \ log P: Q | _ {\ pi}}

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

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

dist π N (PN, QN) → 0 как N → ∞ {\ displaystyle {\ text {dist}} _ {\ pi _ {N}} (P_ {N}, Q_ {N}) \ to 0 \ quad {\ text {as}} \ quad N \ to \ infty}

{\ 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 → ∞ 1 N | множество ⁡ (H N) | {\ displaystyle H (P) = \ lim _ {N \ to \ infty} {\ frac {1} {N}} | \ operatorname {set} (H_ {N}) |}

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

См. также

Примечания

Ссылки

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

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

Учебники

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