Conjunto típico

En la teoría de la información, el conjunto típico es un conjunto de secuencias cuya probabilidad es cercana a dos elevada a la potencia negativa de la entropía de su fuente de distribución. Que este conjunto tenga una probabilidad total cercana a uno es consecuencia de la propiedad de equipartición asintótica (AEP) que es una especie de ley de los grandes números. La noción de tipicidad solo se relaciona con la probabilidad de una secuencia y no con la secuencia real en sí.

Esto tiene un gran uso en la teoría de la compresión ya que proporciona un medio teórico para comprimir datos, permitiéndonos representar cualquier secuencia Xⁿ usando nH(X) bits en promedio y, por lo tanto, justifica el uso de la entropía como medida de información de una fuente.

El AEP también se puede probar para una gran clase de procesos ergódicos estacionarios, lo que permite definir el conjunto típico en casos más generales.

Secuencias típicas (débilmente) (tipicidad débil, tipicidad de entropía)

Si una secuencia x₁,...,x_n se extrae de una distribución i.i.d. X definido sobre un alfabeto finito X{displaystyle {fnMithcal}}, entonces el conjunto típico, A_ε⁽⁾ⁿ⁾▪ ▪ X{displaystyle in {fn}⁽⁾ⁿ⁾ se define como las secuencias que satisfacen:

2− − n()H()X)+ε ε )⩽ ⩽ p()x1,x2,...... ,xn)⩽ ⩽ 2− − n()H()X)− − ε ε ){displaystyle 2^{-n(H(X)+varepsilon)}leqslant p(x_{1},x_{2},dotsx_{n})leqslant 2^{-n(H(X)-varepsilon)}}}}}}}}

dónde

H()X)=− − .. x▪ ▪ Xp()x)log2⁡ ⁡ p()x){displaystyle H(X)=-sum _{xin {mathcal {X}}p(x)log _{2}p(x)}

es la entropía de la información de X. La probabilidad anterior solo necesita estar dentro de un factor de 2^{n ε}. Tomando el logaritmo en todos los lados y dividiendo por -n, esta definición se puede establecer de manera equivalente como

H()X)− − ε ε ≤ ≤ − − 1nlog2⁡ ⁡ p()x1,x2,...... ,xn)≤ ≤ H()X)+ε ε .{displaystyle H(X)-varepsilon leq -{frac {1}{n}log _{2}p(x_{1},x_{2},ldotsx_{n})leq H(X)+varepsilon.}

Para la secuencia i.i.d, ya que

p()x1,x2,...... ,xn)=∏ ∏ i=1np()xi),{displaystyle p(x_{1},x_{2},ldotsx_{n}=prod ¿Qué?

Además tenemos

H()X)− − ε ε ≤ ≤ − − 1n.. i=1nlog2⁡ ⁡ p()xi)≤ ≤ H()X)+ε ε .{displaystyle H(X)-varepsilon leq -{frac {1}{n}sum ¿Qué? ¿Por qué?

Por la ley de los grandes números, para n suficientemente grandes

− − 1n.. i=1nlog2⁡ ⁡ p()xi)→ → H()X).{displaystyle -{frac {1}{n}sum _{i=1} {n}log _{2}p(x_{i})rightarrow H(X).}

Propiedades

Una característica esencial del conjunto típico es que, si se dibuja un gran número n de muestras aleatorias independientes de la distribución X, la secuencia resultante (x₁,x₂,...,x_n) es muy probable que sea miembro del conjunto típico, aunque el conjunto típico comprende sólo una pequeña fracción de todas las secuencias posibles. Formalmente, dado cualquier 0}" xmlns="http://www.w3.org/1998/Math/MathML">ε ε ■0{displaystyle varepsilon }0" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e04ec3670b50384a3ce48aca42e7cc5131a06b12" style="vertical-align: -0.338ex; width:5.344ex; height:2.176ex;"/>, uno puede elegir n tal que:

1. La probabilidad de una secuencia desde Xⁿ⁾ ser extraído A_ε⁽⁾ⁿ⁾ es mayor que 1 -ε, es decir. Pr[x()n)▪ ▪ Aε ε ()n)]≥ ≥ 1− − ε ε {displaystyle Pr[x^{(n)}in A_{epsilon }gq 1-varepsilon }
2. SilencioAε ε ()n)Silencio⩽ ⩽ 2n()H()X)+ε ε ){displaystyle left WordPress{A_{varepsilon }{(n)}right sobre la vidaleqslant 2^{n(H(X)+varepsilon)}}
3. SilencioAε ε ()n)Silencio⩾ ⩾ ()1− − ε ε )2n()H()X)− − ε ε ){displaystyle left WordPress{A_{varepsilon }} {{(n)}right sometidageqslant (1-varepsilon)2^{n(H(X)-varepsilon)}}
4. Si la distribución sobre X{displaystyle {fnMithcal}} no es uniforme, entonces la fracción de secuencias que son típicas es

SilencioAε ε ()n)SilencioSilencioX()n)Silencio↑ ↑ 2nH()X)2nlog2⁡ ⁡ SilencioXSilencio=2− − n()log2⁡ ⁡ SilencioXSilencio− − H()X))→ → 0{displaystyle {frac {fnh00}{epsilon}{n)}{fn}{mthcal {X}} {n)}}equiv {frac {2^{nH(X)}}{2}{nlog}} {gngn}} {fn}}}}}}}} {equiv}}}equiv}equiv {equiv {equiv {fn} {fn}}}fn}}}}}}} {equiv}}}}}equiv}equiv} {equiv {f}}}}}}}}}equiv {equiv {equiv {fnH}} {fnhnhnhnhnh00}}} {fnhnhnhnhnhnhnhnhnhnhnhnhnhnhnhnhn _{2}Sobrevivir{mathcal {X}tuvo}=2^{-n(log) _{2}Sobrevivir{mathcal {X} sobreviviendo-H(X)}rightarrow 0}

como n se vuelve muy grande, ya que <math alttext="{displaystyle H(X)H()X).log2⁡ ⁡ SilencioXSilencio,{displaystyle H(X) _{2} sobrevivir {mathcal {X}<img alt="{displaystyle H(X) Donde SilencioXSilencio{displaystyle Silencio{mathcal {X}tuvo} es el cardenalismo X{displaystyle {fnMithcal}}.

Para un proceso estocástico general {X(t)} con AEP, el conjunto típico (débil) se puede definir de manera similar con p (x₁, x₂,..., x _n) reemplazado por p(x₀^τ) (es decir, la probabilidad de la muestra limitada al intervalo de tiempo [0, τ]), siendo n el grado de libertad del proceso en el intervalo de tiempo y H(X) siendo la tasa de entropía. Si el proceso es de valor continuo, se utiliza en su lugar la entropía diferencial.

Ejemplo

En contra de la intuición, la secuencia más probable a menudo no es un miembro del conjunto típico. Por ejemplo, suponga que X es una variable aleatoria i.i.d de Bernoulli con p(0)=0.1 y p(1)=0.9. En n ensayos independientes, dado que p(1)>p(0), la secuencia de resultados más probable es la secuencia de todos los 1& #39;s, (1,1,...,1). Aquí la entropía de X es H(X)=0.469, mientras que

− − 1nlog2⁡ ⁡ p()x()n)=()1,1,...... ,1))=− − 1nlog2⁡ ⁡ ()0.9n)=0.152{displaystyle -{frac {1}{n}}log _{2}pleft(x^{(n)}=(1,ldots1)right)=-{frac {1}log _{2}(0.9^{n})=0.152}

Entonces, esta secuencia no está en el conjunto típico porque su probabilidad logarítmica promedio no puede acercarse arbitrariamente a la entropía de la variable aleatoria X sin importar cuán grande tomemos el valor de n.

Para las variables aleatorias de Bernoulli, el conjunto típico consta de secuencias con números promedio de 0 y 1 en n pruebas independientes. Esto se demuestra fácilmente: si p(1) = p y p(0) = 1-p, entonces para n ensayos con m 1's, tenemos

− − 1nlog2⁡ ⁡ p()x()n))=− − 1nlog2⁡ ⁡ pm()1− − p)n− − m=− − mnlog2⁡ ⁡ p− − ()n− − mn)log2⁡ ⁡ ()1− − p).{displaystyle -{frac {1}{2}p(x^{(n)}=-{frac {1}{n}log} ¿Por qué? }

El número promedio de 1 en una secuencia de ensayos de Bernoulli es m = np. Así, tenemos

− − 1nlog2⁡ ⁡ p()x()n))=− − plog2⁡ ⁡ p− − ()1− − p)log2⁡ ⁡ ()1− − p)=H()X).{displaystyle -{frac {1}{n}}log _{2}p(x^{(n)})=-plog _{2}p-(1-p)log _{2}(1-p)=H(X). }

Para este ejemplo, si n=10, entonces el conjunto típico consta de todas las secuencias que tienen un solo 0 en toda la secuencia. En el caso p(0)=p(1)=0.5, entonces todas las secuencias binarias posibles pertenecen al conjunto típico.

Secuencias fuertemente típicas (tipicidad fuerte, tipicidad de letras)

Si una secuencia x₁,... x_n se extrae de alguna distribución conjunta especificada definida sobre un finito o un alfabeto infinito X{displaystyle {fnMithcal}}, entonces el conjunto muy típico, A_ε,strong⁽⁾ⁿ⁾▪ ▪ X{displaystyle in {fn} se define como el conjunto de secuencias que satisfacen

<math alttext="{displaystyle left|{frac {N(x_{i})}{n}}-p(x_{i})right|SilencioN()xi)n− − p()xi)Silencio.ε ε .. X.. .{displaystyle left WordPress{frac {N(x_{i}} {n}}-p(x_{i})right sometida{frac {varepsilon }{\mathcal {X}h}fnh}}}<img alt="left|{frac {N(x_{i})}{n}}-p(x_{i})right|

Donde N()xi){displaystyle {N(x_{i}}} es el número de ocurrencias de un símbolo específico en la secuencia.

Se puede demostrar que las secuencias fuertemente típicas también son débilmente típicas (con una constante ε diferente), y de ahí el nombre. Las dos formas, sin embargo, no son equivalentes. A menudo, es más fácil trabajar con una tipicidad fuerte para probar teoremas para canales sin memoria. Sin embargo, como se desprende de la definición, esta forma de tipicidad solo se define para variables aleatorias que tienen un soporte finito.

Secuencias típicas conjuntas

Dos secuencias xn{displaystyle x^{n} y Sí.n{displaystyle y^{n} son conjuntamente ε-typical si el par ()xn,Sí.n){displaystyle (x^{n},y^{n}} es ε-typical con respecto a la distribución conjunta p()xn,Sí.n)=∏ ∏ i=1np()xi,Sí.i){displaystyle p(x^{n},y^{n}=prod ¿Qué? } y ambos xn{displaystyle x^{n} y Sí.n{displaystyle y^{n} ε-typical with respect to their marginal distributions p()xn){displaystyle p(x^{n}} y p()Sí.n){displaystyle p(y^{n}}. El conjunto de todos estos pares de secuencias ()xn,Sí.n){displaystyle (x^{n},y^{n}} es denotado por Aε ε n()X,Y){displaystyle A_{varepsilon } {n}(X,Y)}. Jointly ε-typical n- secuencias de tropiezo se definen de forma similar.

Vamos X~ ~ n{displaystyle {fn} {fn}}} {fn}} y Y~ ~ n{displaystyle {fn} {fn}} {fn}} {fn}}} {fn}}} {fn}}} {fn} ser dos secuencias independientes de variables aleatorias con las mismas distribuciones marginales p()xn){displaystyle p(x^{n}} y p()Sí.n){displaystyle p(y^{n}}. Entonces para cualquier ε ratio0, para lo suficientemente grande n, secuencias típicas conjuntas satisfacen las siguientes propiedades:

1. P[()Xn,Yn)▪ ▪ Aε ε n()X,Y)]⩾ ⩾ 1− − ε ε {displaystyle Pleft[(X^{n},Y^{n}in A_{varepsilon }^{n}(X,Y)right]geqslant 1-epsilon }
2. SilencioAε ε n()X,Y)Silencio⩽ ⩽ 2n()H()X,Y)+ε ε ){displaystyle left WordPressA_{varepsilon }{n}(X,Y)right sobre la vidaleqslant 2^{n(H(X,Y)+epsilon)}
3. SilencioAε ε n()X,Y)Silencio⩾ ⩾ ()1− − ε ε )2n()H()X,Y)− − ε ε ){displaystyle left WordPressA_{varepsilon }{n}(X,Y)right sometidageqslant (1-epsilon)2^{n(H(X,Y)-epsilon)}}
4. P[()X~ ~ n,Y~ ~ n)▪ ▪ Aε ε n()X,Y)]⩽ ⩽ 2− − n()I()X;Y)− − 3ε ε ){displaystyle Pleft[{tilde {X} {fn} {fn} {fn} {fn}fn} {fn} {fn}fn} {fn}fn}fn}fn}fn}fnfn}fn}fnfn}fnfnH00fnfn}fn}fnfnfn}fn}fn}fn}fnfnfn}fnfnfn}fn}fnfn}cH00fn}cH00fn}fn}fn}fn}cH00cH00fn}fn}cH00cH00cH00cH00cH00cH00cH00cH00cH00cH00cH00cH00cH00}cH00cH En A_{varepsilon } [X,Y]right]leqslant 2^{-n(I(X;Y)-3epsilon]}
5. P[()X~ ~ n,Y~ ~ n)▪ ▪ Aε ε n()X,Y)]⩾ ⩾ ()1− − ε ε )2− − n()I()X;Y)+3ε ε ){displaystyle Pleft[{tilde {X} {fn} {fn} {fn} {fn}fn} {fn} {fn}fn} {fn}fn}fn}fn}fn}fnfn}fn}fnfn}fnfnH00fnfn}fn}fnfnfn}fn}fn}fn}fnfnfn}fnfnfn}fn}fnfn}cH00fn}cH00fn}fn}fn}fn}cH00cH00fn}fn}cH00cH00cH00cH00cH00cH00cH00cH00cH00cH00cH00cH00cH00}cH00cH En A_{varepsilon } {n}(X,Y)right]geqslant (1-epsilon)2^{-n(I(X;Y)+3epsilon)}

Aplicaciones de tipicidad

Codificación de conjunto típica

En la teoría de la información, la codificación de conjuntos típica codifica solo las secuencias en el conjunto típico de una fuente estocástica con códigos de bloque de longitud fija. Dado que el tamaño del conjunto típico es de aproximadamente 2^nH(X), solo se requieren nH(X) bits para la codificación, mientras que en al mismo tiempo, asegurando que las posibilidades de error de codificación se limiten a ε. Asintóticamente, según el AEP, no tiene pérdidas y alcanza la tasa mínima igual a la tasa de entropía de la fuente.

Descodificación típica de conjuntos

En la teoría de la información, la decodificación de conjuntos típicos se usa junto con la codificación aleatoria para estimar el mensaje transmitido como el que tiene una palabra clave que es ε-típica junto con la observación. es decir.

w^ ^ =w⟺ ⟺ ()∃ ∃ w)()()x1n()w),Sí.1n)▪ ▪ Aε ε n()X,Y)){displaystyle {hat {w}=wiff (exists w)(x_{1}{n}(w),y_{1}{n})in A_{varepsilon }{n}(X,Y)}

Donde w^ ^ ,x1n()w),Sí.1n{fnMicrosoft Sans Serif} son la estimación del mensaje, palabra clave del mensaje w{displaystyle w} y la observación respectivamente. Aε ε n()X,Y){displaystyle A_{varepsilon } {n}(X,Y)} se define con respecto a la distribución conjunta p()x1n)p()Sí.1nSilenciox1n){displaystyle p(x_{1}{n})p(y_{1}{n}tuvos_{1}{n}) } Donde p()Sí.1nSilenciox1n){displaystyle p(y_{1}{n}Principes_{1} {n}) } es la probabilidad de transición que caracteriza las estadísticas del canal, y p()x1n){displaystyle p(x_{1} {n}}} es una distribución de entrada utilizada para generar las palabras clave en el código aleatorio.

Prueba universal de hipótesis nula

Código de canal universal