En teoría de la información , la propiedad de equipartición asintótica ( AEP ) es una propiedad general de las muestras de salida de una fuente estocástica . Es fundamental para el concepto de conjunto típico utilizado en las teorías de compresión de datos .
En términos generales, el teorema establece que aunque hay muchas series de resultados que pueden producirse mediante un proceso aleatorio, el que realmente se produce es muy probablemente a partir de un conjunto de resultados vagamente definidos que tienen aproximadamente la misma probabilidad de ser el que realmente se realizó. . (Esto es una consecuencia de la ley de los grandes números y la teoría ergódica .) Aunque hay resultados individuales que tienen una probabilidad más alta que cualquier resultado en este conjunto, el gran número de resultados en el conjunto casi garantiza que el resultado vendrá de la colocar. Una forma de comprender intuitivamente la propiedad es a través del teorema de la gran desviación de Cramér, que establece que la probabilidad de una gran desviación de la media disminuye exponencialmente con el número de muestras. Estos resultados se estudian en la teoría de las grandes desviaciones ; intuitivamente, son las grandes desviaciones las que violarían la equipartición, pero son poco probables.
En el campo de la generación de números pseudoaleatorios , un generador candidato de calidad indeterminada cuya secuencia de salida se encuentra demasiado lejos del conjunto típico según algunos criterios estadísticos se rechaza como insuficientemente aleatorio. Así, aunque el conjunto típico está vagamente definido, surgen nociones prácticas sobre suficiente tipicidad.
Definición
Dado un proceso estocástico ergódico estacionario en tiempo discreto en el espacio de probabilidad , la propiedad de equipartición asintótica es una afirmación de que
dónde o simplemente denota la tasa de entropía de, que debe existir para todos los procesos estacionarios de tiempo discreto , incluidos los ergódicos. La propiedad de equipartición asintótica se demuestra para valores finitos (es decir,) procesos estocásticos ergódicos estacionarios en el teorema de Shannon-McMillan-Breiman usando la teoría ergódica y para cualquier fuente iid usando directamente la ley de los grandes números tanto en el caso de valores discretos (dondees simplemente la entropía de un símbolo) y el caso de valores continuos (donde H es la entropía diferencial en su lugar). La definición de la propiedad de equipartición asintótica también se puede ampliar para ciertas clases de procesos estocásticos de tiempo continuo para los que existe un conjunto típico durante un tiempo de observación suficientemente largo. La convergencia está probada casi segura en todos los casos.
Fuentes de iid en tiempo discreto
Dado es una fuente iid que puede tomar valores en el alfabeto, su serie de tiempo es iid con entropía . La ley débil de los grandes números da la propiedad de equipartición asintótica con convergencia en probabilidad ,
ya que la entropía es igual a la expectativa de
La ley fuerte de los grandes números afirma la convergencia casi segura más fuerte,
Fuentes ergódicas estacionarias de valor finito de tiempo discreto
Considere un espacio muestral de valor finito , es decir , para el proceso ergódico estacionario de tiempo discreto definido en el espacio de probabilidad . La propiedad de equipartición asintótica para tal fuente estocástica se conoce como el teorema de Shannon-McMillan-Breiman , debido a Claude Shannon , Brockway McMillan y Leo Breiman .
Prueba (boceto) [2] - Sea x un conjunto medible para algunos
- Parametrice la probabilidad conjunta por n y x como
- Parametrice la probabilidad condicional por i , k y x como
- Tome el límite de la probabilidad condicional como k → ∞ y denótelo como
- Argumenta las dos nociones de tasa de entropía
- existir y son iguales para cualquier proceso estacionario incluyendo el proceso estacionario ergódico X . Denotemos como H .
- Argumenta que ambos
- donde i es el índice de tiempo, son procesos ergódicos estacionarios, cuyas medias muestrales convergen casi con seguridad a algunos valores denotados por y respectivamente.
- Definir la aproximación de Markov de k -ésimo orden a la probabilidad como
- Argumenta eso es finito a partir del supuesto de valor finito.
- Rápido en términos de la media muestral de y mostrar que converge casi con seguridad a H k
- Definir la medida de probabilidad
- Rápido en términos de la media muestral de y mostrar que converge casi con seguridad a H ∞ .
- Argumenta eso como k → ∞ utilizando la estacionariedad del proceso.
- Argumenta que H = H ∞ usando el teorema de convergencia de martingala de Lévy y el supuesto de valor finito.
- Muestra esa
- que es finito como se argumentó antes.
- Muestra esa
- condicionando el pasado infinito e iterando la expectativa.
- Muestra esa
- utilizando la desigualdad de Markov y la expectativa derivada previamente.
- De manera similar, demuestre que
- que es equivalente a
- Muestra ese limsup de
- son no positivos casi con seguridad estableciendo α = n β para cualquier β> 1 y aplicando el lema de Borel-Cantelli .
- Muestre que liminf y limsup de
- son inferiores y superiores delimitados casi con seguridad por H ∞ y H k respectivamente al romper los logaritmos del resultado anterior.
- Complete la demostración señalando que los límites superior e inferior se muestran previamente para aproximarse a H cuando k → ∞.
Fuente de tiempo discreto no estacionaria que produce símbolos independientes
Los supuestos de estacionariedad / ergodicidad / distribución idéntica de variables aleatorias no son esenciales para que se mantenga la propiedad de equipartición asintótica. De hecho, como es bastante claro intuitivamente, la propiedad de equipartición asintótica requiere que se cumpla sólo alguna forma de la ley de los grandes números, que es bastante general. Sin embargo, la expresión debe generalizarse adecuadamente y las condiciones deben formularse con precisión.
Suponemos que la fuente está produciendo símbolos independientes, posiblemente con diferentes estadísticas de salida en cada instante. Suponemos que las estadísticas del proceso se conocen por completo, es decir, se conoce la distribución marginal del proceso visto en cada instante de tiempo. La distribución conjunta es solo el producto de los marginales. Entonces, bajo la condición (que puede ser relajada) de quepara todo i , para algunos M > 0, se cumple lo siguiente (AEP):
dónde
Prueba La demostración se deriva de una aplicación simple de la desigualdad de Markov (aplicada al segundo momento de. Es obvio que la prueba se sostiene si en algún momento está uniformemente acotado para r > 1 (nuevamente por la desigualdad de Markov aplicada al r -ésimo momento).
Incluso esta condición no es necesaria, pero dado un proceso aleatorio no estacionario, no debería ser difícil probar si la propiedad de equipartición asintótica se cumple usando el método anterior.
Aplicaciones
La propiedad de equipartición asintótica para procesos independientes en tiempo discreto no estacionarios nos lleva (entre otros resultados) al teorema de codificación de fuente para fuente no estacionaria (con símbolos de salida independientes) y al teorema de codificación de canal ruidoso para canales sin memoria no estacionarios.
Fuentes ergódicas estacionarias de tiempo continuo
Las funciones de tiempo discreto se pueden interpolar en funciones de tiempo continuo. Si tal interpolación f es medible , podemos definir el proceso estacionario de tiempo continuo en consecuencia como. Si la propiedad de equipartición asintótica se cumple para el proceso de tiempo discreto, como en los casos iid o ergódicos estacionarios con valores finitos mostrados anteriormente, se cumple automáticamente para el proceso estacionario en tiempo continuo derivado de él mediante alguna interpolación mensurable. es decir
donde n corresponde al grado de libertad en el tiempo τ . nH ( X ) / τ y H ( X ) son la entropía por unidad de tiempo y por grado de libertad, respectivamente, definidos por Shannon .
Una clase importante de este proceso estacionario de tiempo continuo es el proceso ergódico estacionario limitado por banda, siendo el espacio muestral un subconjunto del proceso continuo. funciones. La propiedad de equipartición asintótica se mantiene si el proceso es blanco, en cuyo caso las muestras de tiempo son iid, o existe T > 1/2 W , donde W es el ancho de banda nominal , de modo que las muestras de tiempo T- espaciadas toman valores en un finito conjunto, en cuyo caso tenemos el proceso ergódico estacionario de valores finitos de tiempo discreto.
Cualquier operación invariante en el tiempo también conserva la propiedad de equipartición asintótica, la estacionariedad y la ergodicidad, y podemos convertir fácilmente un proceso estacionario en no estacionario sin perder la propiedad de equipartición asintótica anulando un número finito de muestras de tiempo en el proceso.
Teoría de categorías
Una teoría de la categoría definición de la propiedad de equipartición está dada por Gromov . [3] Dada una secuencia de poderes cartesianos de un espacio de medida P , esta secuencia admite una secuencia H N asintóticamente equivalente de espacios de medida homogéneos ( es decir, todos los conjuntos tienen la misma medida; todos los morfismos son invariantes bajo el grupo de automorfismos y, por lo tanto, se factorizan como un morfismo del objeto terminal ).
Lo anterior requiere una definición de equivalencia asintótica . Esto se da en términos de una función de distancia, dando cuánto difiere una correspondencia inyectiva de un isomorfismo . Una correspondencia inyectivaes un mapa parcialmente definido que es una biyección ; es decir, es una biyección entre un subconjunto y . Entonces define
donde | S | denota la medida de un conjunto S . En lo que sigue, la medida de P y Q se toma como 1, de modo que los espacios de medida son espacios de probabilidad. Esta distanciase conoce comúnmente como la distancia del movimiento de tierra o métrica de Wasserstein .
Del mismo modo, defina
con llevado a ser la medida de recuento en P . Por tanto, esta definición requiere que P sea un espacio de medida finito. Finalmente, deja
Una secuencia de correspondencias inyectivas son entonces asintóticamente equivalentes cuando
Dada una secuencia espacial homogénea H N que es asintóticamente equivalente a P N , la entropía H ( P ) de P puede tomarse como
Ver también
- Teorema de la gran desviación de Cramér
- Teorema de codificación de fuente
- Teorema de codificación de canal ruidoso
Notas
- ^ Portada y Thomas (1991) , p. 51.
- ^ Algoet y cubierta (1988) .
- ^ Misha Gromov, (2012) " En una búsqueda de una estructura, parte 1: sobre la entropía ". (Consulte la página 5, donde la propiedad de equipartición se denomina 'teorema de aproximación de Bernoulli').
Referencias
artículos periodísticos
- Claude E. Shannon. " Una teoría matemática de la comunicación ". Bell System Technical Journal , julio / octubre de 1948.
- Algoet, Paul H .; Portada, Thomas M. (1988). "Una prueba de sandwich del teorema de Shannon-McMillan-Breiman" (PDF) . Los anales de la probabilidad . 16 (2): 899–909.
- Sergio Verdu y Te Sun Han. "El papel de la propiedad de equipartición asintótica en la codificación de fuente silenciosa". Transacciones IEEE sobre teoría de la información , 43 (3): 847–857, 1997.
Libros de texto
- Portada, Thomas M .; Thomas, Joy A. (1991). Elementos de la teoría de la información (primera ed.). Hoboken, Nueva Jersey: Wiley. ISBN 978-0-471-24195-9.
- MacKay, David JC (2003). Teoría de la información, inferencia y algoritmos de aprendizaje . Prensa de la Universidad de Cambridge. ISBN 0-521-64298-1.