Sélectionnant efficacement un sous-ensemble aléatoire de taille $ M $ à partir d'un ensemble de taille $ N $

Question

Ceci est une croix de ma question ici sur math.se .

J'ai une liste de N $ N $ Éléments et souhaitez sélectionner aléatoirement une $ M $ Ensemble de cela efficacement (en termes de complexité du temps). De plus, je veux que tous les sous-ensembles possibles soient sélectionnés avec une probabilité égale. La solution évidente consiste à choisir un entier aléatoire de 1 $ $ à $ n $ et choisissez l'élément correspondant, Ensuite, répétez $ M $ fois, sans compter l'événement dans lequel on choisit et déjà choisi. Cela devient de plus en plus inefficace comme APPROCHES $ N $ pour $ M> n / 2 $ il serait logique de choisir un $ (nm) $ -set et renvoie son compliment.

pour les valeurs de $ m $ proche de $ N / 2 $ , une meilleure solution que je pense serait de considérer chacun des éléments N $ N $ et décidez de choisir cet élément ou de la jeter à la mise à jour de la probabilité de cueillir ou de jeter en fonction du nombre de éléments choisis vs rejetés avant. Plus précisément, l'algorithme irait comme suit (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

Cependant, je suis préoccupé par le fait que cela ne résulte peut-être pas que chaque sous-ensemble soit choisi avec une probabilité égale.

J'ai deux questions. Premièrement, cet algorithme choisit-t-il des sous-ensembles avec une probabilité égale (si oui, j'aimerais une preuve qu'elle le fait et, sinon, j'aimerais aussi une preuve qu'elle ne le fait pas). Deuxièmement, plus largement, j'aimerais savoir quelles sont les bonnes solutions pour ce problème. Clairement si $ m << n $ alors la première méthode est meilleure que la seconde, à un moment donné, la deuxième méthode (si elle fonctionne en fait) est meilleure que la premier. De plus, une approche entièrement différente peut être la meilleure en général.

Answer 1

La probabilité que l'élément 1 $ appartient à une $ M $ -Subset d'un < span class="math-conteneur"> $ n $ set -Element est $ m / n $ . Par conséquent, vous devez inclure 1 $ dans votre sous-ensemble avec une probabilité $ m / n $ .

.

Si vous mettez $ 1 $ dans votre sous-ensemble, alors il ne vous reste le choix d'une $ (m-1) $ -Subset d'une $ (n-1) $ -Element ensemble.

Si vous n'avez pas mis 1 $ $ Dans votre sous-ensemble, vous êtes laissé avec le choix d'une $ m $ < / SPAN> -SUBSET D'UNE $ (N-1) $ -Element.

Cela signifie que vous devez mettre à jour légèrement votre algorithme, remplacer $ m $ avec $ m- | .

L'algorithme résultant est quelque peu semblable à réservoir échantillonnage .

Une troisième approche, avec quelques similitudes, génère une permutation aléatoire de 1 $, \ ldots, n $ et en sélectionnant la première $ \ theta (n) $ , alors que pour $ m \ ll \ sqrt {n} $ , votre premier algorithme fonctionne dans (attendu) temps $ \ \ \ theta (m) $ .

Nous pouvons améliorer la $ \ theta (n) $ durée comme suit. Nous allons générer un échantillon aléatoire ordonné $ m $ -subset donné $ m $ indices i_1 $, \ ldots, i_m $ , où i_j $ \ in \ {1, \ ldots, n- (j-1) \} $ < / span>. Le $ J $ 'TH ELEMENT DANS LE SOUSET sera la $ I_J $ "TH le plus petit numéro dans < span class="math-conteneur"> $ \ {1, \ ldots, n \} $ sur les numéros ne sont pas déjà choisi.

Pour compléter la description de l'algorithme, nous devons résoudre le problème suivant: étant donné $ S \ subseteq \ {1, \ ldots, n \} $ et $ i $ , trouver la $ i $ 'e plus petit élément $ \ overline {S} $ . Nous pouvons supposer que $ s $ est stocké dans une structure (telle qu'une arborescence binaire auto-équilibrante) qui peut répondre efficacement au type de requête suivant: donnée $ x $ , combien d'éléments dans $ s $ sont plus petits que $ x $ . On peut alors trouver la $ i $ 'e plus petit nombre de $ \ overline {S} $ à l'aide binaire recherche.

Globalement, cet algorithme fonctionne dans $ \ \ Tilde \ theta (m) $ pour toutes les valeurs de $ m $ < / SPAN>, où la tilde cache des facteurs logarithmiques dans $ n $ . (Quand $ m \ ll \ sqrt {n} $ Nous pouvons utiliser votre première approche, éliminez ainsi cette dépendance sur $ n $ ).