Selezione efficiente di un sottoinsieme casuale di dimensione $m$ da un insieme di dimensione $n$

Question

Questo è un post incrociato della mia domanda Qui SU matematica.se.

Ho un elenco di $n$ elementi e vorrei selezionare casualmente un $m$ impostarlo in modo efficiente (in termini di complessità temporale).Inoltre, voglio che tutti i possibili sottoinsiemi vengano selezionati con la stessa probabilità.La soluzione ovvia è scegliere un numero intero casuale da $1$ A $n$ e scegli l'elemento corrispondente, quindi ripeti $m$ volte, senza contare l'evento in cui si sceglie e già scelto l'elemento.Ciò diventa sempre più inefficiente man mano che $m$ approcci $n$ così per $m>n/2$ avrebbe senso invece scegliere a $(nm)$-set e restituisce il suo complimento.

Per valori di $m$ vicino a $n/2$, penso che una soluzione migliore sarebbe quella di considerare ciascuno dei $n$ elementi e decidere se scegliere quell'elemento o scartarlo, aggiornando ogni volta la probabilità di scegliere o scartare a seconda del numero di elementi scelti rispetto a quelli scartati in precedenza.Nello specifico, l'algoritmo sarebbe il seguente (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

Tuttavia temo che ciò potrebbe non comportare la scelta di ciascun sottoinsieme con la stessa probabilità.

Ho due domande.Innanzitutto, questo algoritmo seleziona sottoinsiemi con uguale probabilità (in tal caso, vorrei una prova che lo fa e in caso contrario vorrei anche una prova che non lo fa).In secondo luogo, più in generale, mi piacerebbe sapere quali buone soluzioni esistono a questo problema.Chiaramente, se $m<<n$ allora il primo metodo è migliore del secondo, tuttavia ad un certo punto il secondo metodo (se funziona davvero) è migliore del primo.Inoltre, in generale, un approccio completamente diverso potrebbe essere il migliore.

Answer 1

La probabilità che l'elemento $1$ appartiene a un casuale $m$-sottoinsieme di un $n$-il set di elementi è $m/n$.Pertanto dovresti includere $1$ nel tuo sottoinsieme con probabilità $m/n$.

Se metti $1$ nel tuo sottoinsieme, ti rimane la scelta di an $(m-1)$-sottoinsieme di un $(n-1)$-insieme di elementi.

Se non hai messo $1$ nel tuo sottoinsieme, ti rimane la scelta di an $m$-sottoinsieme di un $(n-1)$-insieme di elementi.

Ciò significa che devi aggiornare leggermente il tuo algoritmo, sostituendo $m$ con $m-|L|$.

L'algoritmo risultante è in qualche modo simile a campionamento del serbatoio.

Un terzo approccio, con alcune somiglianze, sta generando una permutazione casuale di $1,\ldpunti,n$ e selezionando il primo $m$ inserimenti.

Lo svantaggio di tutti questi approcci è che funzionano nel tempo $ heta(n)$, mentre per $m \ll \sqrt{n}$, il tuo primo algoritmo viene eseguito nel tempo (previsto). $ ilde heta(m)$.

Possiamo migliorare il $ heta(n)$ tempo di esecuzione come segue.Genereremo un ordine casuale $m$-sottoinsieme dato $m$ indici $i_1,\ldots,i_m$, Dove $i_j \in \{1,\ldots,n-(j-1)\}$.IL $j$L'elemento nel sottoinsieme sarà il $i_j$il numero più piccolo in $\{1,\ldots,n\}$ tra i numeri non già scelti.

Per completare la descrizione dell’algoritmo dobbiamo risolvere il seguente problema:dato $S \subseteq \{1,\ldots,n\}$ E $i$, trovare il $i$l'elemento più piccolo in $\sopralinea{S}$.Possiamo presumerlo $S$ è memorizzato in una struttura (come un albero binario autobilanciante) che può rispondere in modo efficiente al seguente tipo di query:dato $x$, quanti elementi ci sono $S$ sono più piccoli di $x$.Possiamo quindi trovare il $i$il numero più piccolo in $\sopralinea{S}$ utilizzando la ricerca binaria.

Nel complesso, questo algoritmo funziona $ ilde heta(m)$ per tutti i valori di $m$, dove la tilde nasconde fattori logaritmici $n$.(Quando $m \ll \sqrt{n}$ possiamo utilizzare il tuo primo approccio, eliminando così questa dipendenza da $n$.)