Por qué una sola toma

La entropía de Shannon y su hermana cuántica, la de von Neumann, están entre las ideas más elegantes de la teoría de la información. También son, si uno mira la letra pequeña, afirmaciones sobre el límite de infinitas repeticiones. En cuanto una situación ocurre una única vez —una clave criptográfica que se genera y se usa una sola vez, un protocolo que se ejecuta con recursos finitos, un proceso físico irrepetible— esa maquinaria asintótica deja de contestar a la pregunta que importa. Este módulo construye las herramientas para ese régimen, el de una sola toma; antes conviene entender bien por qué las necesitamos.

La entropía mide una tasa, no una cuenta

El teorema de codificación de fuente de Shannon es el ejemplo de referencia. Afirma que una fuente que emite símbolos según una distribución $p$ puede comprimirse hasta $H(X)$ bits por símbolo, con una probabilidad de error que tiende a cero. La clave está en dos matices que suelen pasar inadvertidos: «por símbolo» y «tiende a cero». El teorema no promete nada sobre un símbolo aislado; promete un comportamiento medio que solo se materializa cuando el bloque de datos es enormemente largo.

El motor de esa promesa es la equipartición asintótica: al agrupar $n$ símbolos independientes, casi toda la probabilidad se concentra en un puñado de secuencias «típicas», y ese puñado tiene un tamaño de aproximadamente $2^{nH}$ . Comprimir se reduce entonces a numerar las secuencias típicas y descartar el resto, cuya probabilidad es despreciable… siempre que $n$ sea grande. Buena parte de la teoría clásica de la información se sostiene sobre esta misma idea: promediar sobre muchísimas repeticiones hasta que las fluctuaciones se desvanecen.

Pero muchas cosas ocurren una sola vez

El inconveniente es que «muchísimas repeticiones» es un lujo que no siempre está disponible. Una clave criptográfica se genera una vez y se usa una vez: no hay un conjunto de mil claves sobre el que promediar. Un experimento cuántico se ejecuta en un laboratorio con un número finito de rondas. La termodinámica de un único proceso microscópico no espera a que lo repitamos. En todos estos casos no existe el $n \to \infty$ que sostiene los teoremas asintóticos, y apoyarse en ellos conduce a respuestas que suenan bien pero son falsas.

El nudo del asunto es este: cuando algo sucede una sola vez, no puedes amortizar lo que sale mal. En el régimen asintótico, un suceso raro y desfavorable se diluye entre millones de sucesos favorables y apenas afecta al promedio. En una sola toma, ese mismo suceso raro puede ser, sin más, tu resultado. Por eso las garantías de una toma no pueden formularse sobre el promedio: tienen que valer en el peor caso.

Del promedio al peor caso

Ese giro —del promedio al peor caso— es precisamente lo que da lugar a cantidades nuevas. No se trata de reemplazar las entropías de siempre, sino de acompañarlas con sus versiones pesimistas:

Donde la divergencia KL mide la distinguibilidad media entre dos estados, la entropía max-relativa mide la distinguibilidad en el peor caso: cuánto sobresale $\rho$ por encima de $\sigma$ en la dirección más desfavorable.
Donde la entropía de von Neumann mide la incertidumbre media de un estado, la min-entropía mide la incertidumbre en el peor caso: la que percibe el adversario más listo, el que siempre apuesta por el resultado más probable.

Ambas son deliberadamente pesimistas, y esa es justamente la cualidad que las vuelve útiles: una garantía que se cumple en el peor caso no necesita apoyarse en el promedio de muchas rondas. Además, al final del camino espera una recompensa inesperada. La versión de la min-entropía con información lateral no es solo una fórmula, sino el valor óptimo de un programa semidefinido —el mismo objeto que montamos en el Módulo 01—. Cerraremos el círculo en el último artículo.

Ejemplos resueltos

Ejemplo resuelto 1 · La tasa no es la cuenta

Problema. Una fuente emite $0$ con probabilidad $0.9$ y $1$ con probabilidad $0.1$ . ¿Qué número da la entropía de Shannon y cuántos bits hacen falta realmente para un único símbolo sin error?

Solución. La entropía vale $H(X) = -0.9\log_2 0.9 - 0.1\log_2 0.1 \approx 0.469$ bits por símbolo. Ese número es una promesa asintótica: al transmitir mil símbolos independientes, puedes acercarte a unos $469$ bits en total.

Para un solo símbolo, en cambio, la aritmética se rompe. Solo hay dos valores posibles y distinguirlos sin error exige un bit entero: no existe manera de gastar $0.469$ bits en una única decisión binaria. La tasa media ( $0.469$ ) y la cuenta de una toma ( $1$ ) son magnitudes distintas, y confundirlas es precisamente el desliz que la teoría de una toma viene a corregir.

Ejemplo resuelto 2 · Cuánta aleatoriedad hay en una muestra

Problema. De esa misma fuente extraes una única muestra y quieres convertirla en aleatoriedad casi uniforme —por ejemplo, para una clave—. ¿Cuántos bits puedes esperar? Compara lo que sugiere Shannon con lo que dicta la min-entropía.

Solución. La tentación es contestar $H(X) \approx 0.469$ bits, pero es incorrecto. Lo que limita la aleatoriedad de una única muestra es la facilidad con que alguien adivina el resultado, y eso lo mide la min-entropía:

H_{\min}(X) = -\log_2 \max_i p_i = -\log_2 0.9 \approx 0.152 \text{ bits}.

La mejor apuesta —decir siempre $0$ — acierta el $90\%$ de las veces, así que la muestra es mucho menos impredecible de lo que sugiere su entropía media: apenas $0.152$ bits de aleatoriedad genuina, no $0.469$ . Por eso la criptografía de una toma se construye sobre $H_{\min}$ y no sobre $H$ .

El plan del módulo

El resto del módulo desarrolla estas dos cantidades con calma. En el artículo siguiente definimos con precisión la entropía max-relativa y veremos que basta una única desigualdad de operadores — $\rho \preceq \lambda\,\sigma$ — para capturar la idea de peor caso. Después llega la min-entropía y su lectura como probabilidad de acierto, y por último la reescribimos como una SDP, enlazando de vuelta con el Módulo 01.