Selección eficiente de un subconjunto aleatorio de tamaño $ M $ de un conjunto de tamaño $ n $

Question

Este es un puesto cruzado de mi pregunta aquí en math.se .

Tengo una lista de $ n $ artículos y desea seleccionar aleatoriamente un $ m $ Establecer de ella eficientemente (en términos de complejidad de tiempo). Además, quiero que todos los subconjuntos posibles se seleccionen con igual probabilidad. La solución obvia es elegir un entero aleatorio de $ 1 $ a $ n $ y elija el elemento correspondiente, Luego repita $ m $ veces, sin contar el evento en el que uno elige y ya elegido el elemento. Esto se vuelve cada vez más ineficiente como $ m $ enfoques $ n $ para $ m> n / 2 $ tendría sentido para que elija un $ (nm) $ -et y devuelva su cumplido.

Para valores de $ m $ cerca de $ n / 2 $ , una mejor solución, creo sería considerar cada uno de los elementos $ n $ y decidir elegir ese elemento o desecharlo, cada vez que actualiza la probabilidad de recoger o descartar según el número de Elementos elegidos contra descartados antes. Específicamente, el algoritmo se destinaría a la siguiente (Python):

def randomSubset(n,m):
  L = []
  for i in range(n):
    if uniform(0,1)<m/(n-i): L,m = L+[i],m-1
  return L

Sin embargo, me preocupa que esto no pueda resultar en que cada subconjunto sea elegido con igual probabilidad.

Tengo dos preguntas. Primero, este algoritmo recoge subconjuntos con igual probabilidad (si es así, me gustaría una prueba de que lo hace y, si no, también me gustaría una prueba de que no lo hace). En segundo lugar, más ampliamente me gustaría saber qué buenas soluciones existen para este problema. Claramente, si $ m << n $ , el primer método es mejor que el segundo, sin embargo, sin embargo, en algún momento, el segundo método (si de hecho lo hace) es mejor que el primero. Además, un enfoque completamente diferente puede ser el mejor en general.

Answer 1

La probabilidad de que el elemento $ 1 $ pertenece a un aleatorio $ m $ -subset de un < Span Class="Math-contenedor"> $ n $ -element set is $ m / n $ . Por lo tanto, debe incluir $ 1 $ en su subconjunto con probabilidad $ m / n $ .

Si pone $ 1 $ en su subconjunto, luego se queda con elegir un $ (M-1) $ -subset de un $ (N-1) $ -element set.

Si no puso $ 1 $ en su subconjunto, luego se queda con elegir un $ m $ < / Span> -Subset de un $ (n-1) $ -element set.

Esto significa que tiene que actualizar ligeramente su algoritmo, reemplazar $ m $ con $ m- | l | $ .

El algoritmo resultante es algo similar a Muestreo de reservorio .

Un tercer enfoque, con algunas similitudes, está generando una permutación aleatoria de $ 1, \ ldots, n $ y seleccionando el primer $ m $ entradas.

El inconveniente de todos estos enfoques es que se ejecutan en el tiempo $ \ theTa (n) $ , mientras que para $ m \ ll \ sqrt {n} $ , su primer algoritmo se ejecuta en (esperado) tiempo $ \ tilde \ theta (m) $ .

Podemos mejorar en el $ \ theTa (n) $ Tiempo de ejecución de la siguiente manera. Generaremos un mensaje aleatorio ordenado $ m $ -subset dado $ m $ índices $ i_1, \ ldots, i_m $ , donde $ i_j \ in \ {1, \ ldots, n- (j-1) \} $ < / span>. El $ j $ 'El elemento en el subconjunto será el $ i_j $ ' th más pequeño en < Span Class="Math-contenedor"> $ \ {1, \ ldots, n \} $ fuera de los números que aún no se eligen.

Para completar la descripción del algoritmo, debemos resolver el siguiente problema: dado $ s \ subesteq \ {1, \ ldots, n \} $ y $ i $ , encuentre el $ i $ 'th más pequeño elemento en $ \ Overline {s} $ . Podemos asumir que $ s $ se almacena en una estructura (como un árbol binario de auto-equilibrio) que puede responder de manera eficiente el siguiente tipo de consulta: Dada $ x $ , cuántos elementos en $ s $ son más pequeños que $ x $ . Luego, podemos encontrar el $ i $ 'th más pequeño en $ \ overline {s} $ usando binario búsqueda.

En general, este algoritmo se ejecuta en $ \ tilde \ theta (m) $ para todos los valores de $ m $ < / SPAN>, donde el Tilde oculta los factores logarítmicos en $ n $ . (Cuando $ m \ ll \ sqrt {n} $ Podemos usar su primer enfoque, eliminando así esta dependencia de $ n $ .)