A.S.: Sì, apparentemente il singolare di ‘dadi’ è ‘die’. 😉
Una complicata attività di programmazione sta girando su Internet che, come avrete capito dal mio tentativo di titolo pragmatico, può essere formalizzata come segue:
Data una funzione che restituisce un numero uniformemente casuale tra 1 e 5 (incluso), progettare una funzione che restituisca un numero uniformemente casuale tra 1 e 7 (incluso).
Se l’intersezione di algoritmi e statistiche sono il tuo genere di cose, sentiti libero di provarci! Una sfida extra è quella di rendere il vostro algoritmo limitato nel tempo. L’ho trovato un esercizio divertente, solo per rendermi conto che ci sono limitazioni fondamentali in gioco qui.
Ovviamente, un dado qui significa un generatore casuale perfettamente uniforme che esiste solo in teoria. I dadi del mondo reale sono governati da leggi naturali e imperfezioni ambientali in modo tale che sono solo un’approssimazione (anche se buona) di questo modello astratto.
Una soluzione senza limiti
Guardiamo una famiglia di algoritmi senza limiti. Per creare un generatore casuale che abbia almeno 7 risultati, abbiamo bisogno di lanciare il dado a 5 facce almeno due volte. Lanciandolo due volte si creano 5^2=25 possibili risultati, e mentre questo non è un fattore di 7, possiamo assegnare i primi 21 risultati a 7 gruppi di uguale dimensione 3. Se però finiamo in uno dei 4 risultati rimanenti, allora la procedura deve ricominciare. Non possiamo semplicemente assegnare uno qualsiasi di questi 4 stati finali sfortunati a un’uscita, perché questo incasinerebbe la proprietà di casualità uniforme.
Nel grafico sopra, i cerchi rappresentano gli ‘stati’ del nostro programma, e il testo all’interno è il valore più recente del dado lanciato. Le caselle verdi rappresentano poi l’output che assegniamo a seconda dello stato finale (= dopo aver lanciato il dado due volte). L’84% delle volte, otteniamo un output dopo due lanci e l’algoritmo finisce. Come potete vedere, un ciclo è presente e rende l’algoritmo senza limiti. Questo significa che per ogni numero intero, non importa quanto grande, c’è una piccola ma non nulla probabilità che il numero totale di lanci superi quella quantità per calcolare un valore di uscita. Applicazioni in tempo reale con rigidi requisiti di tempo sono quindi fuori questione, a meno che non siate disposti a scendere a compromessi sull’accuratezza statistica dell’algoritmo.
Una variante di questa soluzione lancia inizialmente fino a tre dadi prima di ripartire: questo crea 5^3=125 stati finali, e possiamo assegnarne al massimo 119 a 7 gruppi di uguali dimensioni 17. Ora, c’è una probabilità del 95,2% di finire dopo un massimo di tre lanci. Si noti che dobbiamo tirare meno volte in media di prima (280/119 ≈ 2,35 contro 50/21 ≈ 2,38), perché la maggior parte delle volte possiamo già prendere una scorciatoia dopo i primi due lanci, e mappare direttamente questi stati intermedi a un’uscita. Questa quantità media di lanci continua a diminuire man mano che continuiamo la tendenza.
Se avete familiarità con la teoria dell’informazione, allora considerate il fatto che un lancio di un dado a 5 facce (= rand5) genera log2(5) ≈ 2,32 bit di informazione, e un lancio di un dado a 7 facce (= rand7) genera log2(7) ≈ 2,81 bit di informazione. Si scopre che nel caso limite, abbiamo bisogno solo di log(7)/log(5) ≈ 1,21 chiamate di rand5 per ogni valore di rand7 che vogliamo ottenere. L’implementazione esatta che funziona arbitrariamente vicino a questo limite è piuttosto complicata e fuori dallo scopo di questo articolo. Avremmo bisogno di memorizzare informazioni di stato tra più chiamate di rand7, e l’algoritmo che ho in mente non solo è ancora senza limiti di tempo, ma anche di memoria. Vi invito volentieri ad informarmi di un metodo che risolva quest’ultimo problema!
Una soluzione vincolata
Non esiste un algoritmo vincolato che calcoli un valore casuale perfettamente uniforme tra 1 e 7, dato un generatore casuale tra 1 e 5 soltanto. Consideriamo la famiglia di soluzioni non vincolate di cui sopra. Come ho accennato, in ogni punto ci sarà sempre una quantità di stati ‘left-over’ (che vanno ovunque da 1 a 6) che causano il riavvio dell’algoritmo. Questo perché 5 e 7 sono numeri primi, e nessuna potenza di 5 può mai essere un multiplo di 7. Per quanto allettante possa essere usare il piccolo teorema di Fermat, tali tentativi risulteranno in errori off-by-one, poiché la teoria dei numeri di base rende impossibile una soluzione delimitata in questa famiglia.
Si potrebbe giustamente far notare che il numero di stati finali non è sempre una potenza di 5, per esempio nel caso di ‘fino a tre rulli’ dove possiamo prendere scorciatoie già dopo due rulli. Forse potremmo organizzare il diagramma di stato in modo da creare un algoritmo vincolato con percorsi di lunghezza variabile e 7n stati finali? Tuttavia, considerate quanto segue:
- Questi stati finali non saranno ugualmente probabili perché non tutti i percorsi hanno la stessa lunghezza (= quantità di chiamate rand5).
- Possiamo molto facilmente espandere l’albero per rendere ogni percorso ugualmente lungo, chiamando inutilmente rand5 una quantità appropriata di volte ogni volta che ci troviamo in uno stato finale prematuro. Ora la quantità di stati finali diventa di nuovo una potenza di 5, e tutti gli stati finali sono ugualmente probabili.
Ovviamente, questa non è una prova formale, ma spero di avervi dato qualche intuizione sul problema. Come vediamo, a volte un problema può sembrare molto realistico, solo per inciampare in fatti matematici come questi. Dopo questa analisi, puoi capire se è possibile simulare un dado a 8 facce partendo da un dado a 4 facce?