2010-06-23 37 views
6

Data una sequenza binaria pseudocasuale (ad esempio 00101010010101) di valori finiti, prevedere come continuerà la sequenza. Qualcuno può dirmi il modo più semplice per farlo? O nel caso sia troppo difficile per qualcuno che riesce a malapena a giocare al solitario sul suo computer, qualcuno può dirmi dove muovere i miei primi passi ... PS: questa tecnica può essere utilizzata per prevedere il colore del prossimo numero della roulette elettronica (es. : assegnazione di 1 e 0 a rosso e nero rispettivamente)?Previsione sequenza binaria pseudo-casuale

risposta

1

Per rispondere prima al PS: No, perché gli spin della roulette sono eventi indipendenti quindi non c'è nulla di predittivo nella sequenza storica dei risultati.

La domanda generale è difficile e interessante. Questo sito può dedurre un numero sorprendente di sequenze dai loro valori iniziali:

http://www.research.att.com/~njas/sequences/

Nota che è per le sequenze intero arbitrario.

Ho provato su modelli semplici come {0,0,1,1,0,0,1,1, ...} e dice la cosa giusta.

1

Beh, per pseudo-casuali sequenze, l'unica possibilità è quella di tenere il conto quanti di ogni possibilità è venuto prima. Se gli 1 superano gli 0, è più probabile che il prossimo sia 0. Quanto più probabile dipende dalle occorrenze relative di ciascuno.

Si noti che questo non funziona per una vera casualità in quanto gli eventi sono indipendenti, nonostante quello che gli statistici ti dicono :-)

Troverete che fuori (dolorosamente) la prima volta che si ottiene una serie di 13 rossi sul tavolo quando si utilizza il metodo a doppia perdita di giocare alla roulette. In ogni caso, la casa trae il suo vantaggio da 0 (e da un doppio 0 su alcuni tavoli) che non sono né rossi né neri.

+0

Le mie intuizioni non mi lasceranno cadere il falso di Montecarlo. Il fatto che il nero e il rosso stiano fuori nel tempo sembra che a un certo punto ti serva una corsa di rosso per contrastare quella corsa di nero. Ovviamente intellettualmente so che questo è un errore, ma è maledettamente furbo. –

+0

Hai ragione se ritieni che gli eventi siano indipendenti. Ma se così non fosse, potrebbe esserci uno schema evidente che l'approccio statistico che proporrà fallirà completamente. Ad esempio, l'approccio statistico suggerirà 0 come il prossimo numero in {1,0,0,1,0,0,1,0,0,1,0,0, ...}. Passa all'enciclopedia online delle sequenze intere (vedi la mia risposta) e inferirà correttamente che il numero successivo è 1. (Naturalmente se sai che gli eventi sono davvero indipendenti, allora il modello apparente è una coincidenza e dovresti davvero dirlo 0!) – dreeves

+0

È difficile lasciarlo andare, @Grafhain. Ma "da tanto tempo" nella mia mente significa trilioni e trilioni di eventi, non qualcosa che puoi fare in una notte al casinò :-) Un'altra cosa che devi guardare è che gli eventi, anche se indipendenti l'uno dall'altro, non sono necessariamente indipendente dall'influenza. Ho visto croupiers che possono posizionare la palla in un quadrante specifico in modo affidabile (e anche se si tratta di voci, sono informato che alcuni possono arrivare a un ottavo). Questo è il ragazzo che vuoi dalla tua parte piuttosto che dalle case (almeno finché non viene scoperto nelle analisi statistiche che la casa fa sempre). – paxdiablo

1

Questa è una domanda decente, ma penso che se "si riesce a malapena a giocare al solitario" potrebbe essere fuori dalla tua portata in questo momento.

Si dovrebbe prendere in esame una lingua di base, e la maggior parte sta per dire PHP, ma io sono cauto di raccomandarlo ad un principiante (è piuttosto facile da lavorare però, vedi: XAMPP). Java è probabilmente un linguaggio "easy to get-running-and-work-with" ma sono sicuro che ci sono discussioni migliori su quale lingua iniziare (Python o qualcosa vince probabilmente perché i programmatori esperti lo adorano).

A proposito, il tuo inglese va bene (non ho notato che eri un madrelingua inglese non nativo).

Ora, come per la tua domanda, se stai osservando il vero abbinamento di modelli. Sarei propenso a trasformare questa idea in codice:

"CURRENTPOINT" is end of first letter. 
LOOP: Pick letter(s) from Start to "CURRENTPOINT" 
Break the rest of your binary string into blocks of the same size. 
See if these blocks all equal your picked letters. 
If not, move "CURRENTPOINT" along and repeat the LOOP until you run out of letters. 
If so, you have your "repeating section." 

Se sei solo indovinare che il generatore di numeri casuali è temporaneamente di parte, e che questa distorsione si ri-stabilire una linea di base (0s bilanciati e 1) in A ragione, a breve termine, è possibile confrontare il conteggio di ciascuno 0 e 1 e dire che l'altro è più probabile in base alla deviazione dalla linea di base. Tuttavia, fai attenzione a Monte Carlo fallacy.

+0

"La maggior parte direbbe PHP"? Veramente? : P –

+0

Sì ogni volta che vedo un "cosa dovrebbe imparare un noob" PHP viene suggerito ed è difficile perché sicuro è facile per loro implementare e così molti programmatori mancano i fondamentali del web ma allo stesso tempo PHP ti punisce per la codifica correttamente e dà hai terribili errori come novizio. –

3

I generatori di numeri pseudocasuali crittograficamente sicuri sono concepiti specificamente per rendere impossibile ciò che si vuole fare.In particolare, soddisfano il "prossimo bit test": dato k bit del loro output, non si può indovinare il bit k+1 con probabilità maggiore di 1/2.

I semplici generatori di numeri pseudocasuali che non soddisfano il prossimo bit test possono essere attaccati e in effetti sono state scoperte vulnerabilità di sicurezza in sistemi reali a causa della scelta di PRNG. In particolare, i generatori congruenziali lineari sono noti per essere in qualche modo (o completamente) prevedibili, e alcune versioni di Unix random possono usare questo algoritmo. Questo metodo è abbastanza matematico però. Se si vuole percorrere questo percorso, la ricerca di "previsione del generatore lineare congruenziale" è un punto di partenza.

Un altro attacco se si è a conoscenza dell'implementazione PRNG è di provare a determinare il seme utilizzato per generare la sequenza che si sta analizzando. Il seme è a volte basato su informazioni ipotetiche come ora del giorno, ID del processo, ecc.

0

Ho notato che nessuno ti ha parlato di periodicità.

La sequenza pseudo-casuale funziona sempre con operazioni matematiche. (fino al computer quantico ^^)

Un modo normale di generarne uno è dividere due numeri primi (non è sicuro che sia la parola giusta ma qualunque).

per esempio

1/3=1.333333..... 
9/7=1,2857142857142857142857142857143 

Quelli sono abbastanza piccolo numero e che cosa notiamo? Periodicità.

1/3=1.3 3 3 3 3 3..... 
9/7=1,2857 142857 142857 142857 142857 143 

Quanto più grande è il numero primo più la sequenza in quel caso: 3 e 142.857 saranno grandi

Quindi, se si guarda a una sequenza pseudo-casuale per un lungo periodo è possibile trovare una periodicità ed essere in grado di "indovinare" il prossimo numero. Ma potrebbe volerci un po '.

PS: mi dispiace per il mio inglese, io sono un po 'arrugginito ^^

+0

Benvenuti in Stack Overflow! Per favore fornisci risposte complete: in questo caso dovresti fornire del codice o almeno un algoritmo come prova del tuo concetto. Anche il collegamento a fonti esterne è benvenuto. –

+0

Inoltre, si noti che l'alfabeto inglese non usa "àccéntéd léttérs";) –

0

Quello che dovete pensare è la proprietà di casualità, studiare quelli. Ad esempio, "Randomness viene eseguito in mazzi". Confronta una sequenza casuale con una sequenza prevedibile: normalmente non troverai mazzi nella prevedibile. Per sfruttare i mazzi, aspetta il mazzo. E con un po 'di fortuna vincerai.