6 x 9 = 42

“Ho sempre detto che c’era qualcosa di fondamentalmente sbagliato nell’universo…” (Arthur Dent)

Giocando a Dadi

Posted by scardax su settembre 14, 2008

Il post di oggi é un altro esempio di come, da una domanda che si pensa semplice, possano risultare notevoli complicazioni. Ci chiediamo: come potremmo definire una sequenza numerica casuale? Il concetto di casualità é abbastanza radicato nel senso comune: qualcosa che, sostanzialmente, non é possibile prevedere con precisione. Applicare questo concetto ad una sequenza sembrerebbe un passaggio banale, eppure pensiamo a queste due serie:

(a) 1 2 1 2 1 2

(b) 5 1 4 2 3 2

Ad “occhio”, saremmo tentati di dire che la (a) non é casuale, in quanto riusciamo a riconoscere un qualche “motivo” (potremmo ipotizzare, ad esempio, che il prossimo numero sarebbe un ‘1’), mentre la (b) “sembrerebbe” esserlo. La matematica formalizza questa visione intuitiva dicendo che una sequenza casuale ha “una complessità equivalente alla sequenza stessa” ovvero, in termini terra terra, che non si puo’ descrivere più brevemente. Quindi possiamo dire che la (a) non é casuale in quanto possiamo definirla come la ripetizione alternata di 1 e 2, ma per quanto riguarda la (b)? Non possiamo escludere a priori la sua non casualità in quanto non abbiamo la possibilità di verificare ogni singola possibilità che potrebbe averla generata!

In effetti, l’intuito sbaglia: per ottenere la (b), é sufficiente prendere il primo decimale dei numeri che otteniamo con la formula Σ(-1)n+1 * (1/n+1), che puo’ sembrare complicata, ma vuol solo dire che (ad esempio) il terzo valore della serie é dato da (la prima cifra decimale di) 1 – 1/2 + 1/3.

Ed i problemi non finiscono qua: e se domani, giocando a dadi, ci uscisse una sequenza di sei 1 e 2 alternati fra loro? Penseremmo forse che il dado sia truccato? Oppure che é stata, semplicemente, una divertente coincidenza, visto che quella particolare sequenza aveva la stessa probabilità di uscire di qualunque altra? A quanto sembra, pur esistendo sequenze sicuramente generate da un qualche evento casuale, non siamo in grado, a posteriori, di poterle discernere con sicurezza. Per quanto possa sembrare strano, dov’é c’é bisogno di tali sequenze (cosa che, come abbiamo visto in altri posts, puo’ capitare spesso in informatica) si é costretti a ricorrere a metodi tremendamente prossimi a quello intuitivo con cui avevamo cominciato la discussione: secondo il criterio di Turing, ad esempio, una sequenza si puo’ dire casuale se é indistinguibile da una qualche estrazione meccanica non prevedibile.

Concretamente, ad esempio, possiamo dire che una data sequenza é casuale se le probabilità di ottenere ciascun numero sono all’incirca uguali (criterio di Von Neumann). Questo non ci aiuta a distinguere piccole sequenze (come la (a) e la (b)), ma é un criterio utilissimo quando dobbiamo progettare un qualche algoritmo che generi numeri casuali (o meglio, in questo caso, pseudocasuali) ed implementarlo su un computer: si prende un numero iniziale più o meno random (ad esempio legato all’orario in cui viene fatto partire il programma), e su quello vengono eseguite alcune operazioni matematiche che permettono di ottenere una sequenza indistinguibile (dall’esterno) da una casuale. Tanto per dare un esempio (e concludere il post), cito uno dei metodi più diffusi in questo senso, quello della Congruenza Lineare, che partendo da un numero k0 genera i successivi come:

kn+1 = (a * kn + b) mod c

Dove “mod” é semplicemente l’operatore di resto della divisione (ad esempio 5 mod 2 = 1), e ‘a’, ‘b’ e ‘c’ costanti fissate in anticipo. Quando si pensa che su una formuletta del genere si possono fondare interi giochi basati quasi esclusivamente sulla casualità, puo’ stupire per la sua semplicità, soprattutto visto che, il più delle volte, ‘b’ é addirittura nullo e la formula si riduce ad una moltiplicazione e ad una divisione!

Ma, si sa, la matematica é bella anche per questo! 🙂

Annunci

3 Risposte to “Giocando a Dadi”

  1. Ufo.rob said

    Un altro buon modo per avere cifre casuali è usare pi greco, l’hai detto anche tu in un altro post che è un numero normale.
    John von Neumann diceva “va da sé che chiunque cerchi di inventare un metodo aritmetico per produrre numeri a caso non andrà da nessuna parte” e Wittgenstein “datemi una sequenza qualsivoglia e vi troverò una regola di qualche tipo cui la sequenza obbedisce (Magari poi la regola sembra strana, ma è comunque una regola.)”
    http://www.columbia.edu/~av72/dialogues/2001_e.pdf
    Tra l’altro tra l’altro la sequeza 1011 è anche una specie di conteggio: un 1 poi lo zero come separatore e poi due 1…
    Un altro modo è considerare piccolissime variazioni di grandezze fisiche, avevo sentito di schede di espansione per computer che con questo sistema, basandosi sulla tensione dei componenti al loro interno, producono numeri “veramente casuali” ma non le ho mai viste di persona…
    Se non sbaglio la libreria standard del C usa la formula che hai indicato tu ma non ricordo se con l’operatore resto o no.

  2. Ufo.rob said

    Mi sono confuso, non è vero che pi greco è normale e neanche che tu l’hai detto, abbiamo detto entrambi che non si sa, però che le cifre di pi greco sono un buon modo per avere cifre casuali sono sicuro di averlo sentito.

  3. scardax said

    Hai tirato fuori una questione molto spigolosa! Teoricamente qualsiasi numero trascendente i cui decimali siano uniformemente distribuiti può essere usato come un generatore pseudocasuale (sottolineo: TEORICAMENTE). Questa proprietà è meno generale della normalità, nel caso di pi si è dimostrato che i primi milioni di cifre seguono una distribuzione simile: http://mathworld.wolfram.com/PiDigits.html. Quindi effettivamente pi viene usato in alcune applicazioni, ad esempio questo è un artista che genera musica “casuale” dalle cifre di pi: http://www.noiseaddicts.com/2008/09/algorithmic-house-music-number-pi-paul-slocum/.
    Detto questo, ci sono almeno due osservazioni contro l’utilizzo di pi: costo computazionale per il calcolo delle cifre e “riconoscibilità” della sequenza. Entrambe vengono discusse molto bene in questo post: http://symbo1ics.com/blog/?p=1465.
    Se vuoi approfondire c’è una discussione interessante su MathOverflow: http://mathoverflow.net/questions/26942/is-pi-a-good-random-number-generator.
    Quest’altro link (credo un po’ datato) approfondisce alcuni aspetti matematici della questione: http://www.pi314.net/eng/statistique.php.
    Infine quest’ultimo link è molto meno serio ma mi ha divertito molto (ed inoltre ha alcuni link interessanti alla fine): http://dorophone.blogspot.it/2008/04/on-randomness-of-pi.html.

Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...

 
%d blogger hanno fatto clic su Mi Piace per questo: