Test di permutazione per sequenze di grandi dimensioni

0

Vorrei eseguire un test di permutazione su un set di dati particolarmente ampio, ovvero intorno a 4 milioni di voci. Fondamentalmente, ho bisogno di ottenere un certo numero di permutazioni casuali di questo set di dati. Il modo usuale per farlo è un rimescolamento di Fisher-Yates, ma è più o meno limitato per periodo di un PRNG . Cioè, per una sequenza non più lunga del 2080.

Esiste una soluzione per permutare casualmente sequenze molto più grandi?

EDIT: Qui è un'interessante discussione correlata su casuale algoritmi shuffle e quanto sono limitati da RNG.

    
posta Oreochromis 31.07.2014 - 17:40
fonte

2 risposte

1

Penso che qualcosa non sia chiaro nella domanda. Stai chiedendo:

1) Posso generare un gran numero di permutazioni casuali di 4000000 elementi usando un PRNG, dove un numero elevato è qualcosa come 100000000000 permutazioni casuali?

o

2) Posso generare OGNI permutazione casuale di 4000000 elementi usando un PRNG?

La risposta alla prima domanda è sì, e alla seconda domanda c'è no. Prendi Mersenne Twister come esempio. Per generare una permutazione casuale, è necessario generare 8.1e + 7 bit casuali, o circa 2 ^ 21 numeri casuali a 32 bit. Dal momento che il periodo di Mersenne Twister è 2 ^ 19997, puoi continuare e generare un enorme 2 ^ 19976 permutazioni casuali, molte di più di quelle di cui avrai mai bisogno.

Tuttavia, se si desidera generare OGNI eventuale permutazione casuale, è necessario generare almeno 2 ^ 8100000 permutazioni casuali, che è maggiore di 2 ^ 19976. Ma non c'è alcuna ragione pratica per generare ogni possibile permutazione.

Per quanto riguarda l'altra domanda nei commenti sul fatto che uno shuffle casuale possa campionare uniformemente da tutte le possibili permutazioni: la risposta è sì. Finché il tuo RNG può generare 80000000 bit consecutivi uniformemente casuali, che può essere Mersenne Twister, il tuo campionamento sarà uniforme.

    
risposta data 01.11.2014 - 09:13
fonte
0

Analizziamo il numero minimo di bit che devi usare per ottenere una permutazione casuale veramente (pseudo) uniforme.

Lascia che il numero di bit generato sia b . Vogliamo trovare b tale che 2^b = n! , quindi avrai bisogno di log_2(n!) bit almeno per generare una permutazione uniformemente distribuita che è ~ = 8.1 * 10 ^ 7

Il rimescolamento di Fisher-yates (supponendo numeri interi a 32 bit) dovrà generare 32 * n ~ = 32 * 4.000.000 ~ = 1.28 * 10 ^ 8 bit casuali

Anche se ci sono alcuni sprechi, non è così significativo come si potrebbe pensare (sono necessari 1.5 bit in più), e per ottenere una permutazione uniformemente distribuita, avrete bisogno di molto più di 2080 numeri interi casuali generati in entrambi i modi .

    
risposta data 31.07.2014 - 17:44
fonte

Leggi altre domande sui tag