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.