Muestreo por embalse: una muestra uniforme de un flujo de longitud desconocida

Objetivo

Seleccionar k elementos de forma uniformemente aleatoria de una secuencia cuya longitud se desconoce hasta que termina, en un único paso y con memoria independiente de la longitud: muestrear líneas de registro para inspección, elegir filas de una exportación grande, o escoger ejemplos para un informe sin cargarlo todo.

Requisitos previos

Un generador pseudoaleatorio con una función entera uniforme. El módulo random de Python, documentado como basado en el Mersenne Twister, es adecuado para el muestreo estadístico; la misma documentación advierte que no es apto para fines de seguridad, así que hay que usar secrets cuando un adversario no deba poder predecir la muestra. El flujo se lee una sola vez; los k elementos caben en memoria.

Pasos

1. Almacenar los primeros k elementos en una lista, el embalse.
2. Para cada elemento posterior, numerado i (contando desde 1), extraer un entero j de forma uniforme entre 1 e i. Si j es como mucho k, sobrescribir la posición j del embalse con el elemento; en caso contrario, descartar el elemento.
3. Cuando el flujo termina, el embalse es la muestra. El orden de sus posiciones no tiene significado; mezclarlo si el orden importa más adelante.
4. Convencerse de que es uniforme. El elemento i entra con probabilidad k/i. Un elemento del embalse sobrevive a la llegada del elemento t con probabilidad 1 − 1/t = (t−1)/t. Multiplicar la supervivencia para t desde i+1 hasta n se telescopa en i/n, y (k/i) × (i/n) = k/n, lo mismo para todos los elementos, incluidos los primeros k, que entran con probabilidad 1 y sobreviven con probabilidad k/n.
5. Caso especial k = 1: reemplazar la única posición con probabilidad 1/i.
6. Probar con un flujo pequeño, por ejemplo 10 elementos y k = 3, repitiendo el procedimiento muchas veces y comprobando que la frecuencia de inclusión de cada elemento se aproxima a 0,3; probar también que el código nunca pregunta por la longitud.
7. Sembrar el generador en las pruebas para reproducibilidad y registrar la semilla en producción, de modo que una muestra reportada se pueda regenerar.

Resultado esperado

Cada elemento está en la muestra con probabilidad exactamente k/n, con una extracción aleatoria por elemento, memoria proporcional a k, y sin necesitar nunca la longitud del flujo.

Límites y base de verificación

La muestra es uniforme sobre elementos, no sobre tiempo o bytes; un flujo a ráfagas se muestrea por recuento. Varios flujos en paralelo necesitan que sus embalses se combinen con pesos proporcionales a sus recuentos de elementos. Existen variantes ponderadas y variantes que saltan hacia delante para ahorrar extracciones aleatorias, pero no se tratan aquí. La corrección se sigue de la aritmética del paso 4; no se afirma ninguna medición.