Effizientes Auswählen einer zufälligen Teilmenge von Größe $ M $ aus einem Satz von Größe $ n $

Question

Dies ist ein Cross-Post meiner Frage hier auf math.se .

Ich habe eine Liste von $ N $ Elemente und möchte einen zufällig einer $ M $ auswählen effizient daraus eingestellt (in Bezug auf die Zeitkomplexität). Ich möchte auch alle möglichen Teilmengen mit gleichen Wahrscheinlichkeit ausgewählt werden. Die offensichtliche Lösung besteht darin, eine zufällige Ganzzahl aus $ 1 $ auf $ n $ und wählen Sie das entsprechende Element aus, Wiederholen Sie dann $ M $ mal, wobei das Ereignis nicht zählt, in dem man wählt, und bereits ausgewähltes Element. Dies wird zunehmend ineffizient wie $ M $ Ansätze $ N $ also für $ m> n / 2 $ Es ist sinnvoll, stattdessen einen $ (nm) $ -Set auszuwählen und sein Kompliment zurückzugeben.

für Werte von $ M $ In der Nähe von $ N / 2 $ , eine bessere Lösung, denke ich wäre es, jeden der $ n $ -Elements in Betracht zu ziehen, und entscheiden Sie sich entweder, um dieses Element auszuwählen, oder verwerfen Sie es, wobei jedes Mal die Wahrscheinlichkeitswahrscheinlichkeit, abhängig von der Anzahl von zu klicken oder zu verwerfen Elemente ausgewählte VS wurden vorher verworfen. Insbesondere würde der Algorithmus wie folgt (Python) gehen:

generasacodicetagpre.

Ich bin jedoch besorgt, dass dies nicht dazu führen kann, dass jede Teilmenge mit gleicher Wahrscheinlichkeit ausgewählt wird.

Ich habe zwei Fragen. Zunächst nimmt dieser Algorithmus-Subsets mit gleicher Wahrscheinlichkeit aus (wenn ja, möchte ich einen Beweis dafür, dass es tut, und wenn nicht, würde ich auch einen Beweis dafür, dass dies nicht der Fall ist). Zweitens, breiter, würde ich gerne wissen, welche guten Lösungen für dieses Problem vorhanden sind. Wenn $ M << N $ dann ist, ist das erste Verfahren besser als der zweite jedoch irgendwann das zweite Verfahren (wenn es tatsächlich funktioniert) besser ist als der zuerst. Darüber hinaus kann ein völlig unterschiedlicher Ansatz am besten im Allgemeinen sein.

Answer 1

die Wahrscheinlichkeit, dass das Element $ 1 $ zu einem zufälligen $ M $ -subset von einem < Span-Klasse="Math-Container"> $ N $ -element-Set ist $ M / N $ . Daher sollten Sie $ 1 $ in Ihrer Teilmenge mit der Wahrscheinlichkeit $ m / n $ .

Wenn Sie $ 1 $ in Ihrer Subset setzen, bleiben Sie mit der Wahl eines $ (M-1) $ -subset eines $ (n-1) $ -element-Set.

Wenn Sie nicht $ 1 $ in Ihrer Teilmenge eingesetzt haben, bleiben Sie mit der Auswahl eines $ M $ < / span> -subset eines $ (n-1) $ -element-Set.

Dies bedeutet, dass Sie Ihren Algorithmus leicht aktualisieren müssen, den $ M $ mit $ M- | L | $ .

Der resultierende Algorithmus ist etwas ähnlich zu Reservoir-Probenahme .

Ein dritter Ansatz mit einigen Ähnlichkeiten erzeugt eine zufällige Permutation von $ 1, \ ldots, n $ und wählt den ersten $ M $ Einträge.

Der Nachteil von all diesen Ansätzen besteht darin, dass sie in der Zeit $ \ theta (n) $ laufen, während für $ m \ ll \ sqrt {n} $ , Ihr erster Algorithmus läuft in (erwarteter) Zeit $ \ tilde \ theta (m) $ .

Wir können die $ \ theta (n) $ wie folgt verbessern. Wir erstellen einen zufälligen Bestellt $ M $ -subset gegeben $ M $ indizes $ i_1, \ ldots, i_m $ , wobei $ i_j \ in \ {1, \ ldots, n- (j-1) \} $ < / span>. Der $ J $ 'tiges Element in der Teilmenge ist der $ i_j $ ' Die kleinste Anzahl in < Span-Klasse="Math-Container"> $ \ {1, \ ldots, n \} $ Aus den nicht bereits ausgewählten Zahlen.

Um die Beschreibung des Algorithmus abzuschließen, müssen wir das folgende Problem lösen: Gegeben $ S \ Subseteq \ {1, \ ldots, n \} $ und $ i $ , Finden Sie den $ i $ 'ter kleines Element in $ \ Overline {S} $ . Wir können davon ausgehen, dass $ s $ in einer Struktur gespeichert ist (z. B. ein Burven-Binärbaum), der den folgenden Typ der Abfrage effizient beantworten kann: Angegebene $ x $ , wie viele Elemente in $ S $ kleiner als $ x $ . Wir können dann den $ I $ 'th kleinste Anzahl in $ \ Overline {S} $ mit binärem Suche.

Insgesamt läuft dieser Algorithmus in $ \ tilde \ theta (m) $ für alle Werte von $ M $ < / span>, wo der Tilde die Faktoren logarithmisch in $ n $ versteckt. (Wenn $ m \ ll \ sqrt {n} $ Wir können Ihren ersten Ansatz verwenden, wodurch diese Abhängigkeit von loswerden> $ n $ .)