Introducción: El milagro más contraintuitivo de la probabilidad
En 2003, el científico de la computación danés Peter Bro Miltersen planteó el célebre problema de los 100 prisioneros:
- $100$ condenados a muerte están numerados del $1$ al $100$. En una sala hay $100$ cajas cerradas que contienen los números del $1$ al $100$ distribuidos al azar (una permutación $\sigma \in S_{100}$).
- Regla: Cada prisionero entra solo por turno y puede abrir hasta $50$ cajas buscando su propio número. Al salir, la sala queda exactamente igual y está prohibida toda comunicación una vez iniciado el proceso (aunque pueden acordar una estrategia antes de empezar).
- Condición de vida o muerte: Solo si los $100$ prisioneros encuentran su número se salvan todos; si uno solo falla, los $100$ son ejecutados.
Si cada prisionero abre $50$ cajas al azar (estrategia independiente), cada uno acierta con probabilidad $1/2$, pero la probabilidad de supervivencia conjunta es:
$$\mathbb{P}(\text{todos sobreviven})_{\text{indep.}} = \left(\frac{1}{2}\right)^{100} \approx 7.89 \times 10^{-31}$$Sin embargo, Sven Skyum descubrió la estrategia de seguimiento de punteros (Pointer-Following Strategy), ¡que eleva la supervivencia conjunta al $31.18\,\%$ sin transmitir un solo bit de información!
Capítulo 1: Seguimiento de punteros y descomposición en ciclos disjuntos
Para el prisionero número $k \in \{1, \dots, 100\}$, la estrategia de Skyum consiste en:
- Paso 1: Abrir primero la caja n.º $k$.
- Paso 2: Si el papel interior muestra $x_1 = k$, ha triunfado; si $x_1 \neq k$, abrir a continuación la caja n.º $x_1$.
- Paso 3: Leer el número $x_2$ y abrir la caja n.º $x_2$, siguiendo la cadena $k \mapsto \sigma(k) \mapsto \sigma^2(k) \mapsto \cdots$ hasta hallar $k$ o agotar los $50$ intentos.
flowchart TD
Start["El prisionero k entra en la sala (máx. 50 intentos)"]
Step1["Paso 1: Abrir la caja k, leer el número x = σ(k)"]
Check{"¿Papel x == k ?"}
Win["¡Número propio k encontrado!"]
Limit{"¿Cajas abiertas < 50 ?"}
Next["Seguir el puntero: Abrir la caja x (x ← σ(x))"]
Lose["No hallado en 50 pasos: Ejecución de todos"]
Start --> Step1 --> Check
Check -- "Sí" --> Win
Check -- "No" --> Limit
Limit -- "Sí" --> Next --> Check
Limit -- "No (longitud del ciclo ℓ > 50)" --> Lose
¿Por qué funciona? La asignación caja $\mapsto$ papel es una biyección $\sigma$ del grupo simétrico $S_{2n}$ ($2n=100$). Toda permutación finita se descompone de forma única en ciclos disjuntos:
$$\sigma = C_1 \circ C_2 \circ \cdots \circ C_m, \qquad \sum_{i=1}^m |C_i| = 2n = 100$$Al ser $\sigma$ biyectiva, partiendo de la caja $k$ el prisionero recorre el único ciclo cerrado que contiene a $k$ y termina en $\sigma^{-1}(k)$ (la caja que guarda el papel $k$). Por tanto:
- El prisionero $k$ triunfa en $\le 50$ pasos si y solo si su ciclo tiene longitud $\ell \le 50$.
- ¡Los $100$ prisioneros sobreviven todos si y solo si la permutación $\sigma \in S_{100}$ no contiene ningún ciclo de longitud $\ell > 50$!
Capítulo 2: Conteo de ciclos largos y números armónicos ($1 - \ln 2$)
Para $2n$ prisioneros ($n = 50$), una permutación $\sigma \in S_{2n}$ puede tener como máximo un único ciclo de longitud $\ell > n$, pues dos ciclos disjuntos de longitud $> n$ sumarían al menos $2n+2 > 2n$ elementos. Así, los sucesos $E_\ell := \{\sigma \text{ contiene un ciclo de longitud } \ell\}$ para $\ell = n+1, \dots, 2n$ son mutuamente excluyentes. El número de permutaciones en $E_\ell$ es:
- Elegir los $\ell$ elementos del ciclo largo: $\binom{2n}{\ell}$;
- Ordenarlos en un ciclo circular único: $(\ell - 1)!$;
- Permutar los $2n - \ell$ elementos restantes: $(2n - \ell)!$.
Multiplicando se cancelan los factoriales:
$$|E_\ell| = \binom{2n}{\ell} \cdot (\ell - 1)! \cdot (2n - \ell)! = \frac{(2n)!}{\ell! \, (2n - \ell)!} \cdot (\ell - 1)! \, (2n - \ell)! = \frac{(2n)!}{\ell}$$Dividiendo por $|S_{2n}| = (2n)!$ resulta $\mathbb{P}(E_\ell) = \frac{1}{\ell}$. Usando los números armónicos $H_N = \sum_{k=1}^N \frac{1}{k}$, la probabilidad exacta de supervivencia es:
$$\boxed{P_{\text{success}}(2n) = 1 - \sum_{\ell = n+1}^{2n} \frac{1}{\ell} = 1 - \left(H_{2n} - H_n\right) \xrightarrow{n \to \infty} 1 - \int_1^2 \frac{dx}{x} = 1 - \ln 2 \approx 30.685\,\%}$$Para $2n = 100$, obtenemos $P_{\text{success}}(100) = 1 - (H_{100} - H_{50}) \approx \mathbf{31.1828\,\%}$.
Capítulo 3: Acoplamiento de riesgos sin transmisión de información
flowchart TD
Pool["Riesgo total fijo: Esperanza de fallos E[fallos] = 50"]
Indep["Estrategia independiente: Fallos dispersos en casi todos los universos"]
Cycle["Seguimiento de ciclos: Destinos acoplados a la estructura cíclica de σ"]
ResI["Al menos 1 fallo en el 99.99...92 % de universos → Supervivencia ≈ 7.89×10⁻³¹"]
ResC["Fallos concentrados en el 68.82 % (ℓ>50) → ¡31.18 % de universos con 100 % de éxito!"]
Pool --> Indep --> ResI
Pool --> Cycle --> ResC
| Característica | 1. Estrategia independiente | 2. Estrategia de ciclos |
|---|---|---|
| Éxito individual $\mathbb{P}(A_k)$ | $50.00\,\%$ | $50.00\,\%$ (idéntico) |
| Esperanza de éxitos $\mathbb{E}[X]$ | $50$ prisioneros | $50$ prisioneros (idéntico) |
| Correlación | Nula (independiente) | Fuertemente acoplada vía $\sigma$ |
| Supervivencia de los $100$ | $(1/2)^{100} \approx 7.89 \times 10^{-31}$ | $1 - (H_{100} - H_{50}) \approx 31.18\,\%$ |
| Límite $n \to \infty$ | $0$ | $1 - \ln 2 \approx 30.685\,\%$ |
- Acoplamiento (Coupling): Como 1 fallo o 51 fallos producen la misma condena, la estrategia de ciclos concentra todos los fallos en el $68.82\,\%$ de permutaciones con un ciclo $\ell > 50$, ¡despejando un $31.18\,\%$ del espacio muestral con cero fallos!
- Defensa ante un alcaide malicioso: Acordando de antemano una biyección aleatoria secreta $\tau \in S_{100}$, la conjugación $\tau \sigma \tau^{-1}$ garantiza exactamente el $31.18\,\%$ de supervivencia.