Come testare la casualità (caso in questione: Shuffle)

Question

Prima di tutto, questa domanda è stata strappata via Questo domanda.L'ho fatto perché penso che questa parte sia più grande di una sottoparte di una domanda più lunga.Se ti offende, perdonami.

Supponiamo di avere un algoritmo che genera casualità.Ora come lo provi?O per essere più diretti: supponiamo di avere un algoritmo che mescola un mazzo di carte, come puoi verificare che si tratti di un algoritmo perfettamente casuale?

Per aggiungere un po 'di teoria al problema: un mazzo di carte può essere mescolato in 52!(52 fattoriale) modi diversi.Prendi un mazzo di carte, mescolalo a mano e scrivi l'ordine di tutte le carte.Qual è la probabilità che avresti ottenuto esattamente quella mescolata?Risposta:1/52!.

Qual è la probabilità che, dopo aver mescolato, otterrai A, K, Q, J...di ciascun seme in una sequenza?Risposta 1/52!

Quindi, mescolare semplicemente una volta e guardare il risultato non ti darà assolutamente alcuna informazione sulla casualità degli algoritmi di mescolamento.Due volte e avrai più informazioni, tre ancora di più...

Come testeresti la casualità di un algoritmo di mescolamento in una scatola nera?

Answer 1

Statistiche.Lo standard de facto per testare gli RNG è il Suite irriducibile (originariamente disponibile su http://stat.fsu.edu/pub/diehard).In alternativa, il Programma Ent fornisce test più semplici da interpretare ma meno completi.

Per quanto riguarda gli algoritmi di mescolamento, utilizzare un algoritmo noto come Fisher-Yates (alias "Knuth Shuffle").La mescolanza sarà uniformemente casuale finché l'RNG sottostante è uniformemente casuale.Se stai usando Java, questo algoritmo è disponibile nella libreria standard (vedi Collezioni.shuffle).

Probabilmente non ha importanza per la maggior parte delle applicazioni, ma tieni presente che la maggior parte degli RNG non fornisce sufficienti gradi di libertà per produrre ogni possibile permutazione di un mazzo da 52 carte (spiegato Qui).

Answer 2

Ecco un semplice controllo che puoi eseguire.Utilizza numeri casuali generati per stimare Pi.Non è una prova di casualità, ma gli RNG scadenti in genere non funzionano bene (restituiranno qualcosa come 2,5 o 3,8 piuttosto che ~ 3,14).

Idealmente questo sarebbe solo uno dei tanti test da eseguire per verificare la casualità.

Qualcos'altro che puoi controllare è the deviazione standard dell'uscita.La deviazione standard prevista per una popolazione di valori uniformemente distribuita nell'intervallo 0..n si avvicina a n/sqrt(12).

/**
 * This is a rudimentary check to ensure that the output of a given RNG
 * is approximately uniformly distributed.  If the RNG output is not
 * uniformly distributed, this method will return a poor estimate for the
 * value of pi.
 * @param rng The RNG to test.
 * @param iterations The number of random points to generate for use in the
 * calculation.  This value needs to be sufficiently large in order to
 * produce a reasonably accurate result (assuming the RNG is uniform).
 * Less than 10,000 is not particularly useful.  100,000 should be sufficient.
 * @return An approximation of pi generated using the provided RNG.
 */
public static double calculateMonteCarloValueForPi(Random rng,
                                                   int iterations)
{
    // Assumes a quadrant of a circle of radius 1, bounded by a box with
    // sides of length 1.  The area of the square is therefore 1 square unit
    // and the area of the quadrant is (pi * r^2) / 4.
    int totalInsideQuadrant = 0;
    // Generate the specified number of random points and count how many fall
    // within the quadrant and how many do not.  We expect the number of points
    // in the quadrant (expressed as a fraction of the total number of points)
    // to be pi/4.  Therefore pi = 4 * ratio.
    for (int i = 0; i < iterations; i++)
    {
        double x = rng.nextDouble();
        double y = rng.nextDouble();
        if (isInQuadrant(x, y))
        {
            ++totalInsideQuadrant;
        }
    }
    // From these figures we can deduce an approximate value for Pi.
    return 4 * ((double) totalInsideQuadrant / iterations);
}

/**
 * Uses Pythagoras' theorem to determine whether the specified coordinates
 * fall within the area of the quadrant of a circle of radius 1 that is
 * centered on the origin.
 * @param x The x-coordinate of the point (must be between 0 and 1).
 * @param y The y-coordinate of the point (must be between 0 and 1).
 * @return True if the point is within the quadrant, false otherwise.
 */
private static boolean isInQuadrant(double x, double y)
{
    double distance = Math.sqrt((x * x) + (y * y));
    return distance <= 1;
}

Answer 3

Innanzitutto, è impossibile sapere con certezza se un certo output finito è "veramente casuale" poiché, come fai notare, qualsiasi output è possibile.

Ciò che si può fare è prendere una sequenza di output e confrontare varie misurazioni di questa sequenza con ciò che è più probabile.Puoi ricavare una sorta di punteggio di confidenza che indica che l'algoritmo di generazione sta facendo un buon lavoro.

Ad esempio, potresti controllare l'output di 10 mescolamenti diversi.Assegna un numero da 0 a 51 a ciascuna carta e prendi la media della carta in posizione 6 durante i mescolamenti.La media convergente è 25,5, quindi rimarrai sorpreso nel vedere qui un valore pari a 1.Potresti utilizzare il teorema del limite centrale per ottenere una stima della probabilità di ciascuna media per una determinata posizione.

Ma non dobbiamo fermarci qui!Perché questo algoritmo potrebbe essere ingannato da un sistema che alterna solo due mescolamenti progettati per fornire la media esatta di 25,5 in ciascuna posizione.Come possiamo fare meglio?

Ci aspettiamo una distribuzione uniforme (uguale probabilità per ogni carta) in ogni posizione, attraverso diversi mescolamenti.Quindi tra i 10 shuffles, potremmo provare a verificare che le scelte "sembrino uniformi". Questa è fondamentalmente solo una versione ridotta del problema originale.Puoi verificare che la deviazione standard sia ragionevole, che il valore minimo sia ragionevole e anche il valore massimo.Potresti anche verificare che anche altri valori, come le due carte più vicine (in base ai numeri assegnati), abbiano senso.

Ma non possiamo nemmeno aggiungere varie misurazioni come questa all'infinito, poiché, date sufficienti statistiche, qualsiasi particolare mescolamento sembrerà altamente improbabile per qualche motivo (ad es.questo è uno dei pochissimi mescolamenti in cui le carte X,Y,Z appaiono in ordine).Quindi la grande domanda è:qual è il giusto insieme di misurazioni da effettuare?Qui devo ammettere che non conosco la risposta migliore.Tuttavia, se hai in mente una determinata applicazione, puoi scegliere un buon insieme di proprietà/misure da testare e lavorare con quelle: questo sembra essere il modo in cui i crittografi gestiscono le cose.

Answer 4

C'è molta teoria sui test della casualità.Per un test molto semplice su un algoritmo di mescolamento delle carte, potresti fare molti mescolamenti e poi eseguire un test del chi quadrato per verificare che la probabilità che ciascuna carta esca in qualsiasi posizione sia uniforme.Ma ciò non verifica che le carte consecutive non siano correlate, quindi dovresti fare dei test anche su questo.

Il volume 2 di Knuth's Art of Computer Programming fornisce una serie di test che potresti utilizzare nelle sezioni 3.3.2 (Test empirici) e 3.3.4 (Il test spettrale) e la teoria dietro di essi.

Answer 5

Mescola molto e poi registra i risultati (se sto leggendo correttamente).Ricordo di aver visto confronti tra "generatori di numeri casuali".Lo testano semplicemente più e più volte, quindi rappresentano graficamente i risultati.

Se è veramente casuale, il grafico sarà per lo più uniforme.

Answer 6

L'unico modo per verificare la casualità è scrivere un programma che tenti di costruire un modello predittivo per i dati da testare, quindi utilizzare quel modello per provare a prevedere i dati futuri e quindi mostrare che l'incertezza, o entropia, delle sue previsioni tendere al massimo (es.la distribuzione uniforme) nel tempo.Naturalmente, sarai sempre incerto se il tuo modello abbia catturato o meno tutto il contesto necessario;dato un modello, sarà sempre possibile costruire un secondo modello che generi dati non casuali che sembrano casuali rispetto al primo.Ma finché accetti che l'orbita di Plutone ha un'influenza insignificante sui risultati dell'algoritmo di mescolamento, allora dovresti essere in grado di accertarti che i suoi risultati siano accettabilmente casuali.

Naturalmente, se lo fai, potresti anche usare il tuo modello generativamente, per creare effettivamente i dati desiderati.E se lo fai, sei di nuovo al punto di partenza.

Answer 7

Non seguo pienamente la tua domanda.Tu dici

Supponiamo di avere un algoritmo che genera casualità.Ora come lo provi?

Cosa intendi?Se presumi di poter generare casualità, non è necessario testarlo.

Una volta che hai un buon generatore di numeri casuali, creare una permutazione casuale è facile (ad es.Chiama le tue carte 1-52.Genera 52 numeri casuali assegnandoli ciascuno a una carta in ordine, quindi ordinali in base ai tuoi 52 numeri casuali).Non distruggerai la casualità del tuo buon RNG generando la tua permutazione.

La domanda difficile è se puoi fidarti del tuo RNG. Ecco un collegamento di esempio a persone che discutono di tale questione in un contesto specifico.

Answer 8

Prova 52!possibilità è ovviamente impossibile.Prova invece a mescolare le carte su un numero più piccolo di carte, come 3, 5 e 10.Quindi puoi testare miliardi di mescolamenti e utilizzare un istogramma e il test statistico chi-quadrato per dimostrare che ogni permutazione si verifica un numero "pari" di volte.

Answer 9

Nessun codice finora, quindi copio e incollo una parte di test da la mia risposta alla domanda originale.

  // ...
  int main() {
    typedef std::map<std::pair<size_t, Deck::value_type>, size_t> Map;
    Map freqs;    
    Deck d;
    const size_t ntests = 100000;

    // compute frequencies of events: card at position
    for (size_t i = 0; i < ntests; ++i) {
      d.shuffle();
      size_t pos = 0;
      for(Deck::const_iterator j = d.begin(); j != d.end(); ++j, ++pos) 
        ++freqs[std::make_pair(pos, *j)]; 
    }

    // if Deck.shuffle() is correct then all frequencies must be similar
    for (Map::const_iterator j = freqs.begin(); j != freqs.end(); ++j)
      std::cout << "pos=" << j->first.first << " card=" << j->first.second 
                << " freq=" << j->second << std::endl;    
  }

Questo codice non verifica la casualità del generatore di numeri pseudocasuali sottostante.Testare la casualità del PRNG è un intero ramo della scienza.

Answer 10

Per un test veloce, puoi sempre provare a comprimerlo.Una volta che non si comprime, puoi passare ad altri test.

Ho provato irriducibile ma si rifiuta di funzionare per uno shuffle.Tutti i test falliscono.È anche davvero noioso, non ti consente di specificare l'intervallo di valori che desideri o qualcosa del genere.

Answer 11

Riflettendoci io stesso, quello che farei è qualcosa del tipo:

Impostazione (pseudo codice)

// A card has a Number 0-51 and a position 0-51
int[][] StatMatrix = new int[52][52]; // Assume all are set to 0 as starting values
ShuffleCards();
ForEach (card in Cards) {
   StatMatrix[Card.Position][Card.Number]++;
}

Questo ci dà una matrice 52x52 che indica quante volte una carta è finita in una certa posizione.Ripeti l'operazione un gran numero di volte (inizierei con 1000, ma persone più brave di me in statistica potrebbero fornire un numero migliore).

Analizzare la matrice

Se abbiamo una casualità perfetta ed eseguiamo il mescolamento un numero infinito di volte, allora per ogni carta e per ogni posizione il numero di volte in cui la carta è finita in quella posizione sarà lo stesso di qualsiasi altra carta.Dire la stessa cosa in modo diverso:

statMatrix[position][card] / numberOfShuffle = 1/52.

Quindi calcolerei quanto siamo lontani da quel numero.