Usuario:Lidia la cal/Taller

En Teoría de la información, el teorema de codificación de fuentes, primer teorema de Shannon o, menos utilizado, teorema de codificación sin ruido es un Teorema enunciado por Claude Shannon en 1948 que establece el límite teórico para la compresión de una fuente de datos​, así como el significado operacional de la entropía de Shannon.

El primer teorema de Shannon muestra que (En el limite en el que una cadena de Variables aleatorias independientes e idénticamente distribuidas de datos tiene a infinito) es imposible comprimir la información de forma que el ratio de codificación (número medio de bits por símbolo) es menor que la entropía de Shannon de la fuente, si se garantiza que no haya pérdida de información. Sin embargo, sí es posible conseguir un ratio de codificación arbitrariamente cerca del valor de la entropía de Shannon.

El primer teorema de Shannon establece una cota inferior y superior de la longitud mínima posible de bits de información como función de la entropía.

Enunciado

La codificación de una fuente es un mapeo de una secuencia de símbolos desde una fuente de información en una secuencia de símbolos de un alfabeto (generalmente bits) de forma que los símbolos de la fuente pueden ser recuperados posteriormente de forma exacta desde los bits binarios (codificación sin pérdidas) o recuperarla con alguna distorsión (codificación con pérdidas), pero aún entendibles. Éste es el concepto detrás de la compresión de datos.

Primer teorema de Shannon

En la Teoria de la Información, el primer teorema de Shannon (Shannon 1948)​ informally states that (MacKay 2003, pg. 81,​ Cover 2006, Chapter 5​):

N i.i.d. variables aleatorias cada una con una entropia H(X) puede ser comprimida en más de N H(X) bits con un riesgo despreciable de pérdida de información , segúnN → ∞; pero a la inversa, si son comprimidos en menos de N H(X) bits es prácticamente seguro que se produce pérdida de información.

Primer teorema de Shannon para códigos simbólicos

Sean Σ₁, Σ₂ dos alfabetos finitos y sean Σ∗
1 y Σ∗
2 los conjuntos finitos de palabras de esos alfabetos (respectivamente).

Suponga que X es una variable aleatoria tomando valores en Σ₁ y sea  f  un código singularmente decodificable desdeΣ∗
1 aΣ∗
2 donde|Σ₂| = a. SeaS la variable aleatoria dada por la longitud de la palabra clave f (X).

Si f  es óptimo en el sentido de que tiene la longitud de palabra clave mínima esperada para X, entonces(Shannon 1948):

${\frac {H(X)}{\log _{2}a}}\leq \mathbb {E} S<{\frac {H(X)}{\log _{2}a}}+1$

Demostración: Teorema de codificación de la fuente

Sea X una fuente de variables aleatorias i.i.d., su serie temporal X₁,…,X_n es también i.i.d. con entropía H(X) en el caso discreto y entropía diferencial en el caso continuo.

El teorema de codificación fuente establece que para cualquier ε>0 hay una cantidad suficientemente grande n y un codificador que toma n i.i.d repeticiones de la fuente, X^1:n, y lo lleva a $n{\bigl (}H{\bigl (}X{\bigr )}+\varepsilon {\bigr )}$bits binarios de tal manera que los símbolos fuente X^1:n son recuperables de los bits binarios con probabilidad de al menos 1-ε.

Demostración de su accesibilidad: Arregla algunos  y deja

$p{\bigl (}x_{1},...,x_{n}{\bigl )}=P_{r}[X_{1}=x_{1},...,X_{n}=x_{n}]$

El conjunto típico $A_{n}^{\varepsilon }$se define como:

$A_{n}^{\varepsilon }=\{(x_{1},...,x_{n}):\left\vert -{\frac {1}{n}}logp(x_{1},...,x_{n})-H_{n}(X)\right\vert <\varepsilon }\$

La propiedad de equipartición asintótica muestra que para cantidades suficientemente grandes de n, la probabilidad de que una secuencia generada por la fuente se encuentre en dicho conjunto se acerca a uno.

La definición de conjuntos típicos implica que aquellas secuencias que se encuentran en dicho conjunto satisfacen:

$2^{n(H(X)+\varepsilon }\leq p(x_{1},...,x_{n})\leq 2^{n(H(X)-\varepsilon }$

Nótese que:

• La probabilidad de que una secuencia  $(X_{1},...,X_{n})$ sea extraída de $A_{n}^{\varepsilon }$ es mayor que 1-ε .
• $|A_{n}^{\varepsilon }|\leq 2^{-n(H(X)+\varepsilon )}$
• $|A_{n}^{\varepsilon }|\leq (1-\varepsilon )2^{-n(H(X)-\varepsilon )}$   

Ya que $|A_{n}^{\varepsilon }|\leq 2^{-n(H(X)+\varepsilon )}$, $n(H(X)+\varepsilon )$ bits son suficientes para señalar cualquier cadena en este conjunto. La demostración inversa se realiza mostrando que cualquier conjunto menor que $A_{n}^{\varepsilon }$ (en el sentido de exponente), cubriría un conjunto de probabilidades limitadas desde 0.

Demostración: Teorema de codificación de fuentes para códigos de símbolos

Para $1\leq i\leq n$, $s_{i}$ representa la longitud de la palabra para cada $x_{i}$ posible. Se define $q_{i}=a^{-s_{i}}/C$ donde $C$ es una constante de normalización elegida de forma que $q_{i}+...+q_{n}=1$. Entonces:

$H(x)=-\sum _{i=1}^{n}p_{i}log_{2}p_{i}\leq -\sum _{i=1}^{n}p_{i}log_{2}q_{i}=-\sum _{i=1}^{n}p_{i}log_{2}a^{-s_{i}}+\sum _{i=1}^{n}p_{i}log_{2}C=-\sum _{i=1}^{n}p_{i}log_{2}a^{-s_{i}}+log_{2}C\leq -\sum _{i=1}^{n}-s_{i}p_{i}log_{2}a\leq \mathbb {E} Slog_{2}a$

Donde la segunda línea viene dada por la desigualdad de Gibbs y la quinta por la desigualdad de Kraft.

$C=\sum _{i=1}^{n}a^{-s_{i}}\leq 1$

Por lo que $log_{2}C\leq 0$.

Para la segunda desigualdad, se establece que:

$s_{i}=-log_{a}p_{i}$

por lo que:

$-log_{a}p_{i}\leq s_{i}\leq -log_{a}p_{i}+1$

por tanto:

$a^{-s_{i}}\leq p_{i}$

y por la desigualdad de Kraft, hay un código sin prefijo que tiene esa longitud de palabra. Esta S mínima satisface:

$\mathbb {E} S=\sum p_{i}s_{i}<\sum p_{i}(-log_{a}p_{i}+1)=\sum -p_{i}{\frac {log_{2}p_{i}}{log_{2}a}}+1={\frac {H(x)}{log_{2}a}}+1$

Extensión a fuentes independientes no estacionarias

En primer lugar definimos una base típica como $A_{n}^{\varepsilon }$

$A_{n}^{\varepsilon }=\{x_{n}:|-{\frac {1}{n}}log(p)(X_{1},....,X_{n})-H_{n}(X)-\varepsilon |\}$

Entonces, dada una δ >0 , con n suficientente grande $P_{r}(A_{n}^{\varepsilon })<1-\delta$ . Ahora solo hay que codificar las secuencias en la base típica, y los métodos más usuales de codificación muestran que la dimensión de esta base es menor que$2^{n(H(x)+\varepsilon )}$ . De esta forma, en promedio bits $H(X)+\varepsilon$ son suficientes para codificar con probabilidad mayor que 1- δ , donde $\varepsilon$ y δ pueden escogerse tan pequeños como se quiera, para un n muy grande.ç

Entropía de Tsallis

En física, la entropía de Tsallis es una generalización de la entropía estándar de Boltzmann. Es útil para estudiar los intercambios de información entre sistemas que no están en equilibrio.

Índice

• 1 Origen
• 2 Definición
• 3 Significado
• 4 Véase también

Origen

Edwin T. Jaynes formuló la mecánica estadística como un problema de maximización entrópica. Puso de manifiesto que cualquier problema en la mecánica estadística de los sistemas en equilibrio, la maximización de la entropía de Shannon se reduce a encontrar el conjunto de probabilidades math>p{i}</math> para las que la entropía de Shannon es máxima bajo un conjunto de ligaduras que especifican las condiciones macroscópicas, que pueden proceder de la teoría o de datos experimentales.

Si las ligaduras son la condición de normalización y la conservación de la energía (i.e. ), entonces sólo existe una única solución para la distribución de probabilidades en equilibrio térmico que es la distribución exponencial de Boltzmann (o Maxwell-Boltzmann-Gibbs): donde Z es un factor de normalización que a garantiza la conservación de probabilidad. La variable Z recibe el nombre de función de partición y su definición es tal que:

La distribución de Boltzmann describe el conjunto canónico, que se aplica a cualquier situación donde un sistema está en equilibrio térmico e intercambiando energía con su entorno.

Ahora bien, el principio de máxima entropía solo implica situaciones de equilibrio, que solamente comprenden un subconjunto pequeño de los problemas en Física

Para sistemas que no están en equilibrio, debemos adoptar una forma de actuar diferente. Para entender la mecánica estadística del no-equilibrio parece razonable pensar que hemos de explorar el uso de otras medidas de entropía diferente, más generales que la de Shannon.

Fundamentalmente, Jaynes mostró que la entropía de Shannon y la distribución exponencial asociada de estados se aplican solamente para sistemas de equilibrio. Cabe preguntarse entonces qué otro tipo de entropías permiten obtener variacionalmente la distribución de estados no-exponencial que presentan los sistemas fuera del equilibrio (ley de potencias, fractalidad, etc).

De hecho, existen otras funciones de entropía que satisfacen otros requisitos diferentes a los planteados por Shannon, como la Entropía de Rényi, la cual ha resultado ser muy útil para el Análisis multifractal.

Existen numerosos sistemas en la naturaleza y en el comportamiento humano para los que la distribución de estados asociada se aproxima por una ley de potencias.

Una ley de potencias es algo que se comporta para grandes como con . Las distribuciones de probabilidad de tipo potencia decrecen muchi más lentamente que las de tipo exponencial, por tanto tienen propiedades estadísticas muy diferentes. Además, no se comportan tan bien como las exponenciales, en particular, el momento de orden m-ésimo de una distribución de potencia no existe cuando .

Las distribuciones de tipo potencia se han observado en fenómenos tan diversos como la energía de los rayos cósmicos, la turbulencia de los fluidos, ls terremotos, fluctuaciones de precios, la expansión de las urbes, la frecuencia del uso de las palabras, entre otras muchas cosas.

Está claro que las leyes de potencia no pueden explicarse por la mecánica estadística de equilibrio, donde las distribuciones resultantes son siempre exponenciales. Una propiedad común de todos los sistemas que obedecen leyes de potencia es que siempre corresponden a sistemas de no-equilibrio.

La ubicuidad de las leyes de potencia sugiere que debe existir una mecánica estadística del no-equilibrio cuya distribución de probabilidad sea de este tipo, de forma análoga a la distribución exponencial dentro de los sistemas en equilibrio.

Dentro de simulaciones de sistemas caóticos se ha evidenciado que tales sistemas pueden estar de forma metaestable con distribuciones de tipo potencia durante periodos de tiempo muy largos antes de caer en el equilibrio.

Desde un punto de vista puramente estadístico se establecen entonces funciones de entropía permitidas para estos casos en que la distribución de estados asociada es de tipo potencia

La entropía que modela correctamente este tipo de sistemas es la entropía de Tsallis.

Definición

La entropía de Tsallis de la distribución de probabilidad discreta $p=\{p_{i}}\$ se define por

$T_{q}(p)={\frac {1}{q-1}}(1-\sum _{i}p_{i}^{q})$ donde $q\geq 0,q\neq 1$.

Para $q=1$ la entropía de Tsallis se reduce a la entropía de Gibbs estándar.

Usando el formalismo variacional de Jaynes para la mecánica estádistica, uno puede maximixar esta función entropía con las ligaduras adecuadas para obtener funciones de distribución que tienen un comportamiento de tipo ley de potencias para $q\neq 1$. Estas funciones se denominan q-exponenciales y se definen por

$e_{q}=[1+(1-q)x]^{\frac {1}{1-q}}$ cuando $1+(1-q)x>0$

$e_{q}=0$ cuando $1+(1-q)x<0$

La entropía de Tsallis tiene la propiedad de no aditividad

$T_{q}[p_{1}p_{2}]=T_{q}[p_{1}]+T_{q}[p_{2}]+(1-q)T_{q}[p_{1}]T_{q}[p_{2}]$

Por lo que se trata de una entropía no extensiva.

Significado

La entropía de Tsallis es una medida de falta de información. En particular, el conocimiento perfecto del estado microscópico de un sistema da lugar a que $T_{q}=0$, y la incertidumbre máxima produce entropía máxima $T_{q}=\ln _{q}W$.