Muestreo por reservorio (reservoir sampling)

Una muestra aleatoria uniforme de un stream de longitud DESCONOCIDA. Una pasada, memoria O(k), visto una sola vez.

La regla

• Guarda los primeros k elementos en un reservorio
• Para el i-ésimo elemento: consérvalo con probabilidad k/i
• Si lo conservas, reemplaza a un elemento guardado elegido al azar
• No necesita ni la longitud ni todos los datos

Mira el reservorio

k=3 sobre A…J. La probabilidad de aceptación k/i se encoge: 3/4, 3/5, 3/6, … Aceptado (verde) reemplaza una posición aleatoria; rechazado (rojo) → sin cambios.

Uniforme donde otros se sesgan

Reservorio: plano en k/n (diferencia 0.011). Primeros-k: escalón (diferencia 1.0). ½ constante: se sesga al final (0.43).

Por qué k/i es exacto, no una heurística

• El elemento sobrevive al elemento i con prob (i−1)/i → producto telescópico
• Elemento temprano: ∏(i−1)/i = k/n. Elemento tardío j: (k/j)·(j/n) = k/n
• El k/i es la ÚNICA probabilidad que telescopa a k/n
• Cámbiala → el producto deja de cancelarse → sesgo

Conclusión — y el libro

La idea correcta vuelve rutinario lo imposible: una probabilidad en lugar de una garantía. Muestreo justo de lo que no se puede guardar, en cinco líneas. 56 capítulos: la estructura correcta separa lo tratable de lo intratable. Listo.