Imagina que te llegan entradas, sin saber cuándo terminan (cuántas seguirán a partir de ahora). Tienes que elegir una al azar y ser justo. No puedes guardar las entradas que pasaron pero puedes recordar cuántos pasó.
En este punto, si lo imaginas, parece imposible. En el momento de elegir, no se sabe cuál debe ser la posibilidad de ser elegido.
Pero quizás haya algún truco. Y si no, tendremos que demostrar que es imposible, lo que espero que sea parte de la respuesta negativa.
Existe un algoritmo estándar para ello:
(Repetir de forma similar hasta llegar a la última entrada; el $i$ La segunda entrada debe ser seleccionada con probabilidad $\frac1i$ , sustituyendo a lo que se había seleccionado anteriormente, y que, en caso contrario, debería descartarse. )
La entrada seleccionada es la que queda en $S$ una vez finalizado este procedimiento.
Pseudocódigo:
i := 0
while (another entry remains) do:
E := (read next entry)
i := i + 1
x := random (0,1)
if x < 1/i do:
S := E
end;
end;
(the selected entry is now in S)Una sencilla prueba de inducción establece que si hay $n$ entradas, entonces cada una es seleccionada con una probabilidad exacta $\frac1n $ . Porque si eso es cierto en el primer $n-1$ entradas, entonces cada una de ellas se selecciona con probabilidad $\frac1 {n-1}$ antes del paso final. Entonces se selecciona la entrada final con probabilidad $\frac1n $ si no se selecciona la última entrada, entonces la entrada anterior ya está en $S$ ha sido seleccionado con una probabilidad total $\frac1 {n-1}\frac {n-1}n$ .
Se trata de un algoritmo muy conocido entre los programadores informáticos; si se busca en Internet "seleccionar una línea al azar sin contar las líneas" se encontrarán muchas discusiones sobre el problema y su solución. )
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
