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

Asymptotic equipartition property

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

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

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

Определение

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

куда или просто обозначает скорость энтропии из , который должен существовать для всех дискретных стационарные процессы в том числе эргодические. Свойство асимптотической равнораспределенности доказано для конечнозначных (т.е. ) стационарные эргодические случайные процессы в Теорема Шеннона – Макмиллана – Бреймана. используя эргодическую теорию и для любых i.i.d. источников, непосредственно использующих закон больших чисел как в дискретнозначном случае (где это просто энтропия символа) и непрерывнозначный случай (где ЧАС - это дифференциальная энтропия). Определение свойства асимптотической равнораспределенности также может быть расширено для некоторых классов случайных процессов с непрерывным временем, для которых типичный набор существует в течение достаточно длительного времени наблюдения. Сходимость доказана почти уверен во всех случаях.

Дискретное время i.i.d. источники

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

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

[1]

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

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

Рассмотрим конечнозначное выборочное пространство , т.е. , для дискретного времени стационарный эргодический процесс определены на вероятностное пространство . Свойство асимптотического равнораспределения для такого стохастического источника известно как Теорема Шеннона – Макмиллана – Бреймана., из-за Клод Шеннон, Броквей Макмиллан, и Лео Брейман.


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

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

Мы предполагаем, что источник производит независимые символы, с возможной различной выходной статистикой в ​​каждый момент времени. Мы предполагаем, что статистика процесса известна полностью, то есть известно предельное распределение процесса, наблюдаемого в каждый момент времени. Совместное распределение - это всего лишь продукт маргиналов. Тогда при условии (которое можно ослабить), что для всех я, для некоторых M > 0 имеет место (AEP):

куда

Приложения

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

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

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

куда п соответствует степени свободы во времени τ. нГ(Икс)/τ и ЧАС(Икс) - энтропия в единицу времени и на степень свободы соответственно, определяемая Шеннон.

Важным классом таких стационарных процессов с непрерывным временем является стационарный эргодический процесс с ограниченной полосой пропускания, в котором пространство выборок является подмножеством непрерывных функции. Свойство асимптотического равнораспределения выполняется, если процесс белый, и в этом случае выборки времени i.i.d., или существует Т > 1/2W, куда W это номинальная полоса пропускания, так что Т-размерные временные выборки принимают значения в конечном наборе, и в этом случае мы имеем дискретный конечнозначный стационарный эргодический процесс.

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

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

А теоретико-категорийный определение свойства равнораспределения дается формулой Громов.[3] Учитывая последовательность Декартовы степени меры пространства п, эта последовательность допускает асимптотически эквивалентный последовательность ЧАСN однородных пространств с мерой (т.е. все наборы имеют одинаковую меру; все морфизмы инвариантны относительно группы автоморфизмов, и, таким образом, фактор как морфизм к конечный объект) .

Сказанное выше требует определения асимптотическая эквивалентность. Это дается в виде функции расстояния, которая дает инъективное соответствие отличается от изоморфизм. Инъективное соответствие это частично определенная карта это биекция; то есть это биекция между подмножеством и . Затем определите

где |S| обозначает меру множества S. В дальнейшем мера п и Q приняты равными 1, так что пространства мер являются вероятностными. Это расстояние широко известен как расстояние землекопа или же Метрика Вассерштейна.

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

с принято быть мерой подсчета п. Таким образом, это определение требует, чтобы п - пространство конечной меры. Наконец, пусть

Последовательность инъективных соответствий тогда асимптотически эквивалентный когда

Учитывая однородную пространственную последовательность ЧАСN что асимптотически эквивалентно пN, энтропия ЧАС(п) из п можно рассматривать как

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

Примечания

  1. ^ Обложка и Томас (1991), п. 51.
  2. ^ Алгоет и обложка (1988).
  3. ^ Миша Громов, (2012) »В поисках структуры, часть 1: об энтропии". (См. Стр. 5, где свойство равнораспределения называется «аппроксимационной теоремой Бернулли».)

Рекомендации

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

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

Учебники