El teorema de equipartición

Con la intuición de la concentración en la mano, el teorema se lee casi solo. Al promediar la entropía max-relativa suavizada sobre muchas copias, el peor caso se disuelve y emerge el promedio: la entropía relativa. Es la culminación del arco que empezó, hace tres módulos, con una cantidad de una sola toma.

El teorema

La propiedad de equipartición propiedad de equipartición para la max-relativa suavizada afirma que, para cualquier error fijo $\varepsilon \in (0, 1)$ ,

\lim_{n \to \infty} \frac{1}{n}\, D_{\max}^{\varepsilon}\big(\rho^{\otimes n} \,\big\|\, \sigma^{\otimes n}\big) = D(\rho\,\|\,\sigma).

Tres cosas merecen subrayarse. La primera: el límite es la divergencia KL entropía relativa, la cantidad asintótica «de siempre». La segunda: no depende de $\varepsilon$ — el presupuesto de error, tan importante en una toma, es irrelevante en el límite. La tercera: contrasta con el crudo, cuya regularización se quedaba clavada en $D_{\max}$ . El suavizado es justo lo que abre el hueco entre ambos y deja caer la tasa desde $D_{\max}$ hasta $D$ .

La curva de convergencia lo dice todo: arranca cerca del peor caso y desciende hacia el promedio a medida que $n$ crece. Muévela y comprueba que el destino no cambia con $\varepsilon$ :

Regularizar la lleva a la entropía relativa

Con n = 50: ≈ 0.000 bits, ya cerca de D(p‖q) = 0.000 y lejos de D_max = 0.000.

La curva parte del peor caso (D_max) y desciende hacia el promedio (D) al crecer n: eso es la equipartición.

p(0) 0.50

q(0) 0.20

ε 0.10

Por qué es cierto

La demostración formaliza la imagen del artículo anterior. La razón de verosimilitud $\mathrm{LLR}_n$ se concentra en torno a $n\,D(\rho\|\sigma)$ , con una anchura de solo $\sim\sqrt{n}$ . La entropía max-relativa suavizada equivale, en esencia, a un cuantil de esa razón: el suavizado nos deja recortar la cola superior de peso $\varepsilon$ —las secuencias atípicas de razón enorme— y quedarnos con el borde del bloque típico. Ese borde está a distancia $O(\sqrt{n})$ de la media, de modo que, al dividir por $n$ , la corrección se desvanece y solo sobrevive $D(\rho\|\sigma)$ .

El vínculo con el lema de Stein

Este teorema tiene una cara operacional célebre. Imagina que debes decidir si tienes $n$ copias de $\rho$ o de $\sigma$ —un problema de contraste de hipótesis—. El lema de Stein cuántico lema de Stein cuántico dice que, si mantienes controlado el error de un tipo, el error del otro tipo decae exponencialmente con exponente óptimo exactamente $D(\rho\|\sigma)$ :

\text{error de tipo II} \;\approx\; 2^{-n\,D(\rho\,\|\,\sigma)}.

No es casualidad que aparezca la misma cantidad: la entropía max-relativa suavizada es la herramienta natural para probar Stein, y su regularización es el exponente de Stein. La distinguibilidad de una toma, promediada sobre muchas copias, se convierte en la velocidad a la que puedes separar dos hipótesis.

Ejemplos resueltos

Ejemplo resuelto 1 · Leer el límite

Problema. Con $p = (0.5,\ 0.5)$ y $q = (0.25,\ 0.75)$ , ¿hacia qué valor tiende $\tfrac1n D_{\max}^{\varepsilon}(p^{\otimes n}\|q^{\otimes n})$ , y desde dónde parte?

Solución. Parte del peor caso $D_{\max}(p\|q) = 1$ bit (el valor para $n$ pequeño) y desciende hasta el límite

\lim_{n\to\infty} \tfrac1n D_{\max}^{\varepsilon}(p^{\otimes n}\|q^{\otimes n}) = D(p\|q) \approx 0.207 \text{ bits}.

La aproximación al límite es del orden de $1/\sqrt{n}$ , por lo que para $n$ moderado la tasa aún queda algo por encima de $0.207$ — como muestra la curva de arriba. Cambiar $\varepsilon$ mueve la curva un poco, pero no su destino.

Ejemplo resuelto 2 · El exponente de Stein, en números

Problema. Para las mismas distribuciones, estima el error de tipo II al distinguir $p^{\otimes n}$ de $q^{\otimes n}$ con $n = 100$ copias.

Solución. Con exponente $D(p\|q) \approx 0.207$ bits por copia, el error de tipo II decae como

2^{-nD(p\|q)} = 2^{-100 \cdot 0.207} = 2^{-20.7} \approx 6 \times 10^{-7}.

Cien muestras bastan para separar las dos hipótesis con un error inferior a una en un millón. Y ese ritmo —el exponente— es precisamente lo que la regularización de la entropía suavizada calcula.

Ejercicios

Ejercicio 1

Argumenta por qué el límite $D(\rho\|\sigma)$ nunca puede superar a $D_{\max}(\rho\|\sigma)$ , coherente con que la curva de convergencia desciende y no asciende.

Solución

Para cada $n$ , suavizar solo baja el valor: $D_{\max}^{\varepsilon} \le D_{\max}$ ; y el crudo, regularizado, vale $D_{\max}$ exacto. Por tanto $\tfrac1n D_{\max}^{\varepsilon}(\rho^{\otimes n}\|\sigma^{\otimes n}) \le D_{\max}(\rho\|\sigma)$ para todo $n$ , y el límite hereda la cota: $D(\rho\|\sigma) \le D_{\max}(\rho\|\sigma)$ . La entropía relativa es siempre la más pequeña de la escalera.

Ejercicio 2

Para $p = (0.9,\ 0.1)$ y $q = (0.5,\ 0.5)$ , calcula el valor límite de la tasa regularizada.

Solución

El límite es $D(p\|q) = 0.9\log_2\tfrac{0.9}{0.5} + 0.1\log_2\tfrac{0.1}{0.5}$ . Numéricamente, $0.9\cdot 0.848 + 0.1\cdot(-2.322) \approx 0.763 - 0.232 = 0.531$ bits. (El peor caso de partida era $D_{\max} = \log_2\tfrac{0.9}{0.5} \approx 0.848$ , así que la regularización lo rebaja de $0.848$ a $0.531$ .)