¿Cómo elegir eficazmente $n$ subconjunto de un conjunto de $m$ muchos números, de manera uniforme al azar?

Question

Problemas:

Es bastante simple: tenemos una lista de números de $x_1, x_2, \ldots,x_n,\ldots, x_m$. Nuestro objetivo es al azar y de manera uniforme elegir un subconjunto de a $n$ muchos números de estos.

Esto significa que, para cualquier $i \in \{1,2,\ldots,n,\ldots,m\}$, la probabilidad de elegir el valor de $x_i$ debe ser: $$ n\frac{1}{m} = \frac{n}{m} $$

Un algoritmo:

Una instrucción es $\text{swap}(x_{\text{left}},x_{\text{right}})$. Es simplemente cambia sus valores. I. e.

1. $t := x_{\text{left}}$
2. $x_{\text{left}} := x_{\text{right}}$
3. $x_{\text{right}} := t$

Una propuesta de algoritmo: para cada una de las $i \in \{1,2,\ldots,n\}$, de forma aleatoria y uniformemente elegir algunos $k_i \in \{1,2,\ldots,n, \ldots, m\}$, y, a continuación, ejecute $\text{swap}(x_i, x_{k_i})$. Luego regresar $x_1, x_2, \ldots, x_n$ como el conjunto de $n$-muchos de los números elegidos.

El reto:

Intuitivamente, que el algoritmo a mi me parece perfectamente bien. No veo absolutamente ningún problema en ello.

Pero cuando trato de mirar matemáticamente, no puedo probarlo. En lugar de eso, me parece realmente de demostrar que no es una solución correcta!

En primer lugar, echemos un vistazo a la probabilidad de elegir la primera de las $n$ números:

Para cualquier $i \in \{1,2,\ldots,n\}$, $x_i$ puede ser elegido si:

• $x_i$ existe en la mano derecha de $\text{swap}$. Hay exactamente $n$ de los casos, incluyendo el caso al $x_i$ existe en tanto, la izquierda y la mano derecha.
• $x_i$ existe en la mano izquierda, de tal manera que no existe $x_j$ en la mano derecha tal que $j \in \{1,2,\ldots,n\}$. Hay exactamente $n$ tales casos, uno de los cuales es el caso cuando se $i=j$ que hemos contado anteriormente. Por lo tanto, para evitar el recuento de los casos de $i=j$ dos veces, suponemos que no se $n-1$ de los casos.

No hay ningún otro caso en que $x_i$ es elegido. Por lo tanto, la probabilidad de elegir un número $x_i$, dado que el $i \in \{1,2,\ldots,n\}$ es: $$ \frac{n + (n-1)}{m^2} $$

Ahora, echemos un vistazo a la probabilidad de elegir el restablecimiento de los números hasta el $m$:

Para cualquier $i \in \{n+1,n+2,\ldots,m\}$, $x_i$ puede ser elegido si:

• $x_i$ existe en la mano derecha, de tal manera que no existe $x_j$ en la mano derecha tal que $j \in \{1,2,\ldots,n\}$. Hay exactamente $n$ de esos casos.

No hay ningún otro caso de tener $x_i$ elegido. Así que la probabilidad de elegir a $x_i$ es: $$ \frac{n}{m^2} $$

La comparación de las probabilidades:

Que dice que hay un sesgo. La probabilidad de elegir el 1 $n$ números es mayor que la probabilidad de elegir el restablecimiento de los números hasta el $m^{th}$

Mi pregunta:

¿De dónde me salen mal? Cómo abordar este problema?

Answer 1

La "propuesta de algoritmo" es incorrecta. Una forma de ver por qué esto es así es contar el número de equiprobables permutaciones realizadas por el algoritmo. A cada paso hay $m$ posibles valores de $k$, de donde después de $n$ hay $m^n$ resultados posibles. Aunque muchos de los resultados será duplicada, el punto es que la probabilidad de salida de cualquier permutación debe ser un múltiplo de $m^{-n}$. Sin embargo, la probabilidad correcta, $1/m!$, rara vez es un múltiple. Por ejemplo, con $m=3$ $n=2$ se producirá $3^2=9$ permutaciones posibles, cada uno con probabilidad de $1/9$, pero sólo hay $m!=6$ distintas permutaciones. Desde $1/6$ no es un múltiplo de a $1/9$, ninguna de las permutaciones será producido con una probabilidad de $1/6$.

Hay mejores maneras. Uno es el "Algoritmo P" de Knuth del Seminumerical Algoritmos, la sección 3.4.2:

for i := 1 to n do
    Swap(x[i], x[RandInt(i,m)])

La prueba de que esto funciona es por inducción sobre $m$.

1. Obviamente funciona en el caso base ($m=0$ o $m=1$, como usted prefiera).

2. En el primer paso, en cada $x_k$ tiene una posibilidad igual de ser trasladado a la primera posición. El algoritmo procede a trabajar de forma recursiva y de forma independiente en los elementos en las posiciones de $2$ a través de $n$, donde por la hipótesis inductiva cada uno de esos elementos tiene una igual e independiente probabilidad de aparecer en cualquier lugar entre la primera $n-1$ posiciones. En consecuencia, todos los $m$ de los elementos de $x$ condiciones de igualdad e independiente posibilidades de aparecer entre los primeros a $n$ posiciones cuando el algoritmo termina, QED.

El Algoritmo de Knuth S garantiza la salida será en el orden en que aparecieron originalmente en $x$:

Select := n
Remaining := m
for i := 1 to m do
    if RandReal(0,1) * Remaining < Select then
        output x[i]
        Select--
    Remaining--

Ejercicios (2), (3) y (4) en la sección pregunte el lector demostrar que este algoritmo funciona. Una vez más, la prueba es una inducción en $m$.

1. Cuando $m=n=1$, $x$ siempre es devuelto.

2. De lo contrario, $x_1$ será la salida con una probabilidad de $n/m$ en el primer paso, que es la probabilidad correcta, y el algoritmo funciona de forma recursiva a la salida de $n-1$ elementos de $x_{-1} = (x_2, x_3, \ldots, x_m)$ ordenados si $x_1$ estaba de salida y otra de salida será de $n$ elementos de $x_{-1}$ ordenados, QED.

---

Si te gustaría seguir a lo largo de, aquí es una versión ejecutable en R, junto con una rápida simulación para verificar que todos los elementos de a $x$ tienen iguales posibilidades de ser incluidos.

algorithm.S <- function(x, n=1) {
  m <- length(x)
  #
  # Check input.
  #
  if (n < 0 || n > m) stop("Subset size out of range.")
  #
  # Handle special cases that R has trouble with.
  #
  if (m <= 1) 
    if (n==0) return (x[c()]) else return(x)
  #
  # The algorithm.
  #
  y <- x[1:n]
  select <- n
  remaining <- m
  j <- 0
  for (i in 1:m) {
    if (runif(1) * remaining < select) {
      j <- j+1; y[j] <- i
      select <- select-1
    }
    remaining <- remaining-1
  }
  return(y)
}

x <- 1:10
sim <- replicate(1e4, algorithm.S(x, 4))
hist(sim, breaks=seq(min(x)-1/2, max(x)+1/2, by=1))

Answer 2

Empezar por el principio de la lista.

Elegir el elemento con probabilidad igual a $\frac{n}{m}$. Si es elegido set $n = n - 1$. Conjunto de $m = m - 1$ ahora pasar al elemento siguiente y repita hasta que sea $n$ $m$ es cero.

No probado en detalle, pero debería funcionar.

O utilizar las instalaciones de su software estadístico favorito.