¿Cuál es la prueba de corrección del algoritmo de Robert Floyd para seleccionar una única combinación aleatoria de valores?

Question

Lo leí en una respuesta de SO:

¿Algoritmo para seleccionar una sola combinación aleatoria de valores?

inicializar el conjunto S como vacío
para J := N-M + 1 hasta N hacer
    T := RandInt(1, J)
    si T no está en S entonces
        insertar T en S
    else
        insertar J en S

¿Cuál es la prueba de corrección para esto? He invertido bastante tiempo en esto y puedo demostrarme a mí mismo que el valor $N^\text{th}$ y los valores $1^\text{st}$ - $(N-M+1)^\text{th}$ tienen $P$ (elegido) $= M/N$, pero no los que quedan.

por ejemplo.
Para elegir $N$ de $M$, cada elemento enumerado de $1$ a $N$, puedo demostrarme a mí mismo que usando este algoritmo, los elementos $1$, $2$, $\ldots$, $N-M$, $N-M+1$ y $N$ tienen una probabilidad de $M/N$ de ser elegidos. Sin embargo, no sé sobre los otros elementos restantes.

por ejemplo 2
Para elegir $8$ de $4$, cada elemento numerado de $1$ a $8$, puedo demostrarme a mí mismo que usando este algoritmo, los elementos $1$, $2$, $3$, $4$, $5$ y $8$ tienen una probabilidad de $4/8$ de ser elegidos.

Answer 1

Considere un número fijo $k \in [n]$ y denotar por $T_j$ $\, (n-m \leq j \leq n)$ el tiempo después de que el valor $j$ haya sido procesado; por lo tanto, $T_{n-m}$ es el tiempo de inicio. Argumentamos sobre la probabilidad $P_j$ de que $k$ aún no haya sido elegido en el tiempo $T_j.

Cuando $k \leq n-m$ entonces $P_{n-m} = 1$, y $$ P_j = \biggl(1 - {1 \over j} \biggr) P_{j-1} \qquad (n-m+1 \leq j \leq n) \ . $$ Sigue que $$ P_n = \prod_{j=n-m+1}^n \biggl( {j-1 \over j} \biggr) = {n-m \over n} \ , $$ como se requiere.

Cuando $k> n-m$ entonces $P_{k-1} = 1$, porque hasta el tiempo $T_{k-1}$ solo se han seleccionado números $\leq k-1$, de hecho exactamente $k-1-(n-m)$ de ellos. Por lo tanto, cuando se procesa el valor $j: = k$ hay $n-m$ números entre los $\leq k-1$ restantes, y si se elige uno de ellos en el paso $j: = k$, el número $k$ aún no está elegido en tiempo $T_k$. Esto implica que tenemos $$ P_k = {n-m \over k} P_{k-1} = {n-m \over k} \ . $$ Para los pasos restantes obtenemos como antes $$ P_n = {n-m \over k} \prod_{j=k+1}^n \biggl( {j-1 \over j} \biggr) = {n-m \over n} \ . $$

Answer 2

Esto se puede demostrar por inducción. Los casos base son aquellos con $M=1$, para los cuales el algoritmo obviamente funciona.

Como señalaste, $N$ tiene la probabilidad correcta $M/N$ de ser elegido. Todo lo que sucede antes del último paso en el que $N$ podría ser elegido sucedería de la misma manera para $N-1$. Por lo tanto, si $N$ es elegido, por la hipótesis de inducción el resto de la combinación es una elección aleatoria uniforme de $M-1$ entre $N-1$, mientras que si $N$ no es elegido, por la hipótesis de inducción el resto de la combinación es una elección aleatoria uniforme de $M-1$ entre $N-1$ con un elemento más aleatorio sin usar añadido, lo que la convierte en una elección aleatoria uniforme de $M$ entre $N-1$. Esto, junto con que $N$ tenga la probabilidad correcta de ser elegido, implica que la combinación total se elige de forma aleatoria uniforme.

Answer 3

Caso base

Para $_{N}C_{M}$ donde $M = 1$, T := RandInt(1, J) se ejecutará con $J = N-M+1 = N$, seleccionando aleatoriamente un elemento $I$ de los $N$ elementos, como se espera para $_{N}C_{1}$. En otras palabras, el caso trivial base es $P_{elegido}(I_{i\in1..N}|_NC_1) = {1 \over N}$, que denotaré usando

$P_{N,1}(I_i) = {1 \over N}

Supuesto inductivo

$P_{N,M}(I_i) = {M \over N}$ para elegir $M$ elementos de $N

Paso inductivo

El paso inductivo es resolver para

$P_{N',M'}(I_i)$ cuando $N'=N+1$ y $M'=M+1$

El paso inductivo se ejecuta en el algoritmo en cada iteración de bucle adicional.

Para elementos $I_{i\in1..N}$

$P_{N',M'}(I_{i\in1..N}) = P_{N,M}(I_i) + \neg P_{N,M}(I_i) * {1 \over N'}$

$P_{N', M'}(I_{i\in1..N}) = "Para elementos $I_i$ excepto $I_{N'}$ en la iteración adicional"

$P_{N,M}(I_i) = "La probabilidad de que $I_i$ ya haya sido elegido anteriormente"

$\neg P_{N,M}(I_i) = "La probabilidad de que $I_i$ aún no haya sido elegido anteriormente"

$1 \over N' = "La probabilidad de que $I_i$ sea elegido en la iteración adicional por RandInt()"

Sustituir en la hipótesis y simplificar:

$P_{N',M'}(I_{i\in1..N}) = {M \over N} + (1-{M \over N}) * {1 \over N+1}$

$P_{N',M'}(I_{i\in1..N}) = {M+1 \over N+1}

Para el último elemento $I_{N'}$ agregado en la iteración adicional

$P_{N',M'}(I_{i=N+1}) = {1 \over N'} + {M \over N'} = {M+1 \over N+1}

${M \over N'} = "La probabilidad de que uno de los $M$ elementos ya elegidos anteriormente sea elegido nuevamente en la iteración adicional"

Ahora sabemos que para todos los elementos $I_i$ en la iteración adicional

$P_{N',M'}(I_i) = {M+1 \over N+1} = {M' \over N'}

lo que completa el paso inductivo.

---

Esta demostración funciona porque para cualquier $N'$ y $M'$, el paso inductivo reduce el problema al subproblema, $N=N'-1$ y $M=M'-1$. Eventualmente, $M$ se reducirá a $1$, dándonos el caso base, $_NC_1$.

Dado que el algoritmo garantiza tanto

1. $P(I)={M \over N}$ para todos los elementos $I$

2. Exactamente $M$ de $N$ elementos serán seleccionados

Sabemos que el algoritmo selecciona correctamente una combinación aleatoria de $M$ elementos de un conjunto de $N$ elementos.