A caso è a malapena a caso a tutti?

StackOverflow https://stackoverflow.com/questions/2145510

  •  23-09-2019
  •  | 
  •  

Domanda

L'ho fatto per testare la casualità dei randint: 

>>> from random import randint
>>>
>>> uniques = []
>>> for i in range(4500):  # You can see I was optimistic.
...     x = randint(500, 5000)
...     if x in uniques:
...         raise Exception('We duped %d at iteration number %d' % (x, i))
...     uniques.append(x)
...
Traceback (most recent call last):
  File "<stdin>", line 4, in <module>
Exception: We duped 887 at iteration number 7

Ho provato a circa 10 volte di più e il miglior risultato ho ottenuto è stato di 121 iterazioni prima di un ripetitore. E 'questo il miglior tipo di risultato che si può ottenere dalla libreria standard?

È stato utile?

Soluzione

The Birthday Paradox, o perché PRNGs produrre duplicati più spesso di quanto si possa pensare.


Ci sono un paio di questioni in gioco nel problema del PO. Uno è il href="http://en.wikipedia.org/wiki/Birthday_problem" paradosso del compleanno come detto sopra, la seconda è la natura di ciò che si sta generando, che non intrinsecamente garantisce che un dato numero non verrà ripetuta.

Il compleanno Paradox applica quando determinato valore può verificarsi più di una volta durante il periodo del generatore - e quindi duplicati può avvenire in un campione di valori. L'effetto del compleanno paradosso è che la vera probabilità di ottenere tali duplicati è abbastanza significativo e il periodo medio tra loro è più piccolo di quanto si possa altrimenti potuto pensare. Questa dissonanza tra le probabilità percepiti e reali rende il compleanno Paradox un buon esempio di un cognitivo polarizzazione , dove una stima intuitiva ingenuo rischia di essere selvaggiamente sbagliato.

Un rapido primer su Generatori Pseudo di numeri casuali (PRNG)

La prima parte del problema è che si sta assumendo il valore esposto di un generatore di numeri casuali e convertirlo in un numero molto più piccolo, quindi lo spazio dei possibili valori è ridotta. Anche se alcuni numero pseudo-casuali generatori non si ripetono valori durante il loro periodo di questa trasformazione cambia il dominio uno molto più piccolo. Il dominio più piccolo invalida la condizione 'senza ripetizioni' così ci si può aspettare una significativa probabilità di ripetizioni.

Alcuni algoritmi, come ad esempio i href="http://en.wikipedia.org/wiki/Linear_congruential_generator" congruenziale PRNG (A'=AX|M) do garanzia di unicità per l'intero periodo. In un LCG valore generato contiene l'intero stato dell'accumulatore e nessuno stato supplementare è tenuto. Il generatore è deterministico e non può ripetere un numero entro il termine - un dato valore dell'accumulatore può implicare un solo possibile valore successivo. Pertanto, ciascun valore può avvenire solo una volta durante il periodo del generatore. Tuttavia, il periodo di tale PRNG è relativamente piccola - circa 2 ^ 30 per implementazioni tipiche dell'algoritmo LCG -. E non possono eventualmente essere maggiore del numero di valori distinti

Non tutti gli algoritmi PRNG condividono questa caratteristica; alcuni possono ripetere un dato valore entro il periodo. Nel problema del PO, il Mersenne Twister algoritmo (usato in di Python casuale modulo ) ha un periodo molto lungo - molto più grande di 2 ^ 32. A differenza di un lineare congruential PRNG, il risultato non è puramente una funzione del valore di uscita precedente come accumulatore contiene stato aggiuntivo. Con uscita intero a 32 bit ed un periodo di circa 2 ^ 19937, non può assolutamente fornire una garanzia tale.

Il Mersenne Twister è un algoritmo popolare per PRNGs perché ha buone proprietà statistiche e geometriche e un periodo molto lungo - caratteristiche desiderabili per un PRNG utilizzato su modelli di simulazione.

  • proprietà statistiche fanno sì che i numeri generati dall'algoritmo sono uniformemente distribuiti senza numeri avendo una probabilità significativamente più alta di apparire rispetto ad altri. Poveri proprietà statistiche potrebbero produrre skew indesiderati nei risultati.

  • properies geometriche significa che gruppi diN numeri non mentono su un iperpiano in spazio n-dimensionale. Scarse proprietà geometriche possono generare correlazioni spurie in un modello di simulazione e falsare i risultati.

  • Un lungo periodo significa che è possibile generare un sacco di numeri prima che la sequenza si avvolge intorno al punto di partenza. Se un modello ha bisogno di un gran numero di iterazioni o deve essere eseguito da numerosi semi allora i 2 ^ 30 o così numeri discreti disponibili da una tipica implementazione LCG potrebbe non essere sufficiente. L'algoritmo MT19337 ha un periodo molto lungo - 2 ^ 19.337-1, o circa il 10 ^ 5821. In confronto, il numero totale di atomi nell'universo è stimato in circa 10 ^ 80.

Il numero intero a 32 bit prodotta da un MT19337 PRNG non può assolutamente rappresentare valori discreti sufficienza per evitare di ripetere durante un periodo di grandi dimensioni tali. In questo caso, i valori duplicati sono suscettibili di verificarsi e inevitabile con un campione abbastanza grande.

The Birthday Paradox in poche parole

Il problema è originariamente definito come la probabilità di due persone nella stanza che condividono lo stesso compleanno. Il punto chiave è che ogni due persone nella stanza potrebbe condividere un compleanno. Le persone tendono a fraintendere ingenuamente il problema come la probabilità di qualcuno nella stanza condivisione di un compleanno con un individuo specifico, che è la fonte della pregiudizio cognitivo che spesso provoca la gente a sottovalutare la probabilità. Questo è il presupposto non corretto - non v'è alcun obbligo per la partita di essere a un individuo specifico e due individui poteva eguagliare.

Questo grafico mostra la probabilità di un compleanno condiviso come il numero di persone in camera aumenta. Per 23 persone la probabilità di due condividono un compleanno è poco più del 50%.

La probabilità di un incontro che si verificano tra due individui è molto più alta la probabilità di una partita ad un individuo specifico, come la partita non deve essere quello di una data specifica. Piuttosto, devi solo trovare due individui che condividono lo stesso compleanno. Da questo grafico (che si trova sulla pagina di Wikipedia sul tema), possiamo vedere che abbiamo solo bisogno di 23 persone nella stanza perché ci sia una probabilità del 50% di trovare due che corrispondono in questo modo.

voce di Wikipedia sul tema possiamo ottenere un bel riassunto problema del PO, abbiamo 4.500 possibili 'compleanni', piuttosto che 365. Per un dato numero di valori casuali generati (pari a 'gente') vogliamo sapere la probabilità di qualsiasi due valori identici che appaiono all'interno della sequenza.

Il calcolo del probabile effetto della Compleanno Paradox sul problema del PO

Per una sequenza di 100 numeri, abbiamo titolo (100 * 99) / 2 = 4950  coppie (vedi comprensione del problema ) che potrebbero corrispondere (cioè il primo potrebbe corrispondere con il secondo, terzo, ecc, il secondo potrebbe corrispondere al terzo, quarto ecc e così via), quindi il numero di combinazioni che potrebbe potenzialmente partita è piuttosto più di 100.

Da Calcolo della Probabilità otteniamo l'espressione di 1 -! (4500 / (4500 ** 100 * (4500 - 100)) . Il seguente frammento di codice Python sotto fa una valutazione naif della probabilità di una coppia corrispondente verificano. 

# === birthday.py ===========================================
#
from math import log10, factorial

PV=4500          # Number of possible values
SS=100           # Sample size

# These intermediate results are exceedingly large numbers;
# Python automatically starts using bignums behind the scenes.
#
numerator = factorial (PV)          
denominator = (PV ** SS) * factorial (PV - SS)

# Now we need to get from bignums to floats without intermediate
# values too large to cast into a double.  Taking the logs and 
# subtracting them is equivalent to division.
#  
log_prob_no_pair = log10 (numerator) - log10 (denominator)

# We've just calculated the log of the probability that *NO*
# two matching pairs occur in the sample.  The probability
# of at least one collision is 1.0 - the probability that no 
# matching pairs exist.
#
print 1.0 - (10 ** log_prob_no_pair)

Questo produce un risultato cercando sensibile della p = 0,669 per un match che si verificano entro 100 numeri campionati da una popolazione di 4500 possibili valori. (Forse qualcuno potrebbe verificare questo e pubblicare un commento se è sbagliato). Da questo possiamo vedere che le lunghezze di piste tra i numeri corrispondenti osservati dal PO sembrano essere abbastanza ragionevole.

Nota: usando mischiare per ottenere una sequenza unica di numeri pseudo-casuali

questa risposta qui sotto da S. Marco per un mezzo per ottenere un insieme unico garantito di numeri casuali. La tecnica del manifesto riferisce ad accetta un array di numeri (che si forniscono, in modo da poter rendere univoco) e le mescola in un ordine casuale. Disegnare i numeri in sequenza dalla matrice mischiato vi darà una sequenza di numeri pseudo-casuali che sono garantiti di non ripetere.

Nota: PRNGs crittografica sicura

L'algoritmo di MT non è crittograficamente sicuro in quanto è relativamente facile da dedurre lo stato interno del generatore osservando una sequenza di numeri. Altri algoritmi come Blum Blum Shub vengono utilizzati per applicazioni crittografiche ma può essere inadatto per la simulazione o generale applicazioni di numeri casuali. Crittograficamente PRNGs sicuri possono essere costosi (forse richiede calcoli bignum) o non può avere buone proprietà geometriche. Nel caso di questo tipo di algoritmo, il requisito principale è che dovrebbe essere computazionalmente impossibile dedurre lo stato interno del generatore osservando una sequenza di valori.

Altri suggerimenti

Prima di dare la colpa Python, si dovrebbe davvero rispolverare un po 'di teoria della probabilità e statistica. Iniziare con la lettura circa la paradosso del compleanno

A proposito, il modulo random in Python utilizza il Mersenne twister PRNG, che è considerato molto buono, ha un periodo di enormi ed è stato ampiamente testato. Così stare certi che siete in buone mani.

Se non si desidera un ripetitivo, generare serie sequenziale e utilizzare casuale. mescolare

Come risposta alla risposta di Nimbuz:

http://xkcd.com/221/

alt text

La vera casualità comprende sicuramente la ripetizione di valori prima che l'intero insieme dei possibili valori è esaurita. Non sarebbe casuale altrimenti, come si sarebbe in grado di prevedere per quanto tempo un valore non si sarebbe ripetuto.

Se mai dadi lanciati, è sicuramente ottenuto 3 sei in fila abbastanza spesso ...

implementazione casuale di Python è in realtà abbastanza stato dell'arte:

Non è un ripetitore. Un ripetitore è quando si ripete la stessa sequenza . Non solo un numero.

Si generazione di numeri casuali 4500 da un 500 <= x <= 5000 gamma. È quindi controllare per vedere per ogni numero se è stato generato in precedenza. Il ci dice ciò che la probabilità è per due di quei numeri per abbinare dato n sperimenta di una d gamma.

È anche possibile invertire la formula per calcolare quanti numeri è necessario generare fino a quando la possibilità di generare un duplicato è più che 50%. In questo caso si ha la possibilità >50% di trovare un numero duplicato dopo iterazioni 79.

È stato definito uno spazio casuale di 4501 valori (500-5000), e si sono iterazione 4500 volte. Si sono fondamentalmente garantiti per ottenere una collisione nel test che hai scritto.

Per pensare in un altro modo:

  • Quando l'array risultato è vuota P (dupe) = 0
  • 1 valore in Array P (dupe) = 1/4500
  • 2 valori nella matrice P (dupe) = 2/4500
  • ecc.

Quindi, per il momento si arriva a 45/4500, che inserto ha un 1% di possibilità di essere un duplicato, e che probabilità continua ad aumentare con ogni inserto successiva.

Per creare un test che mette alla prova realmente le capacità della funzione random, aumentare l'universo di possibili valori casuali (per esempio: 500-500000) Si può, o non può ottenere una vittima. Ma si otterrà molto di più iterazioni in media.

Per chiunque altro con questo problema, ho usato uuid.uuid4 () e funziona come un fascino.

C'è il paradosso del compleanno. Tenendo conto di ciò ci si rende conto che quello che stai dicendo è che trovare "764, 3875, 4290, 4378, 764", o qualcosa del genere non è molto casuale, perché un numero in che sequenza si ripete. Il vero modo per farlo è quello di confrontare le sequenze gli uni agli altri. Ho scritto uno script python per fare questo. 

from random import randint
y = 21533456
uniques = []
for i in range(y):  
    x1 = str(randint(500, 5000))
    x2 = str(randint(500, 5000))
    x3 = str(randint(500, 5000))
    x4 = str(randint(500, 5000))
    x = (x1 + ", " + x2 + ", " + x3 + ", " + x4)
if x in uniques:
    raise Exception('We duped the sequence %d at iteration number %d' % (x, i))
else:
    raise Exception('Couldn\'t find a repeating sequence in %d iterations' % (y))
uniques.append(x)
Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top