venerdì 21 ottobre 2011

Sulla legge dei grandi numeri e problemi affini

Volevo spiegare agli studenti il fatto che due infiniti dello stesso ordine possono avere rapporto finito ma non differenza finita, e volevo farlo in modo che il concetto rimanesse ben impresso nella memoria.

Allora ho fatto l'esempio del gioco del testa-o-croce: se lancio una moneta, la probabilità che esca testa è uguale a 1/2, ed è uguale alla probabilità che esca croce. Se io eseguo il lancio molte volte, mi aspetto che il rapporto tra numero di teste e numero di croci si avvicini sempre di più a 1 (se la moneta non è truccata, naturalmente). Questo è, in sostanza, quello che dice la legge dei grandi numeri (la quale ha una formulazione più sottile: la convergenza a 1 del rapporto è una convergenza in probabilità, cioè il rapporto converge al valore teorico con probabilità 1 (e probabilità 1 non significa che avverrà certamente, ma che avverrà quasi certamente (sì, i Veri Matematici hanno dato un significato rigoroso anche al quasi, roba da matti))).

Ora vediamo l'inghippo: analizziamo una serie di lanci e scopriamo che testa è uscita per 42000 volte. Cosa deduciamo? La prima risposta è questa: anche il numero di croci sarà molto vicino a 42000.

Bene, questo è sbagliato. Si può dimostrare che la differenza tra teste e croci non rimane costante, ma varia come la radice quadrata del numero di lanci. Se ho fatto quindi circa 100000 lanci, posso aspettarmi una differenza anche di circa 300. D'accordo, 300 è piccolo rispetto a 100000, ma non importa: il fatto è che questo valore cresce sempre, e tende ad infinito.

Insomma, se noi vediamo che ci sono 300 teste in più e deduciamo che le croci sono ritardatarie, e che certamente prima o poi ne usciranno molte, sbagliamo clamorosamente.

Ora si può anche fare l'esempio algebrico: le due successioni N+√N e N hanno rapporto che tende a 1 e differenza che tende a infinito.

Ho poi portato gli studenti in laboratorio, e ho fatto scrivere agli increduli un programmino che simulasse il lancio di una moneta, in modo da verificare la teoria. Il fatto è che alcuni sono invece riusciti a falsificarla.

Confortato dalla certezza che i teoremi matematici non sono falsificabili, sono andato a cercare l'errore, e dopo un po' di ricerche ho capito cosa era successo.

Per simulare il lancio di una moneta, alcuni avevano utilizzato la seguente istruzione C:

if (rand() % 2) == 1

che comporta le seguenti operazioni: crea un numero casuale con la funzione rand(), numero che è un intero compreso tra 0 e un valore massimo memorizzato all'interno della costante RAND_MAX, e guarda se è pari o dispari. Se è pari è uscita testa, se è dispari invece croce (o viceversa, non importa).

Bisogna ricordare che le funzioni che generano numeri casuali utilizzate dai vari linguaggi di programmazione non generano numeri davvero casuali: non c'è un omino, dentro al programma, che lancia un dado ogni volta che c'è bisogno. Ci sono invece delle funzioni matematiche che simulano la casualità, utilizzando tecniche diverse. Una delle più diffuse è quella che fa uso di un sistema che si chiama generatore lineare congruenziale, molto semplice da implementare, ma anche un po' scarsino. Sotto alcune condizioni, i bit meno significativi dei numeri pseudo-casuali generati con questo sistema hanno un periodo molto breve, e controllare se un numero è pari oppure dispari significa proprio utilizzare il bit meno significativo dell'intera sequenza. E quindi l'esperimento fallisce, perché le teste e le croci si presentano con preoccupante periodicità.

Come si fa allora a generare numeri casuali buoni?

In questo caso, l'istruzione che ho riportato qua sopra va sostituita da quest'altra:

if ((float) rand()/RAND_MAX)  < 0.5

che significa

  • genera un numero casuale intero compreso tra 0 e RAND_MAX,
  • trasformalo in un numero float (con la virgola, insomma),
  • dividilo per RAND_MAX, ottenendo così un numero compreso tra 0 e 1,
  • se è minore di 0.5 è uscita testa, altrimenti croce.

Così funziona bene.

Il compilatore usato a scuola è il Dev C++, che evidentemente usa, nella sua funzione rand(), questo sistema poco affidabile. Ho controllato quello che succede nel gcc, e ho trovato che la libreria C presente sul mio sistema non presenta questo problema. Il manuale, però, dice che non si può essere sicuri del fatto che rand() funzioni bene su ogni implementazione di questa funzione.

Per essere sicuri, invece, del fatto che anche i bit meno significativi siano sufficientemente casuali, occorre usare un'altra funzione, che si chiama random().

Ecco allora un programmino che lancia una moneta 50000 volte e salva su file i risultati:


#define NUM 50000

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<math.h>

/* viene usata la funzione random() al posto di rand() perche' usa
   un generatore di numeri casuali migliore. In vecche implementazioni
   di rand(), ad esempio, i bit meno significativi hanno un periodo
   molto breve, per cui non si puo' usare rand()%2 per estrarre un
   numero compreso tra 0 e 1
*/

int main(void)
{
    int i,t=0,c=0;
    FILE *f=fopen("grandinumeri.csv","wt");

    srandom((unsigned)time(NULL));

    for (i=0;i<NUM;i++) {
        if ((float) random()/RAND_MAX < 0.5) {
                t++;
        }
        else {
                c++;
        }

        if (c!=0) { // salto i primi calcoli fino a che non ho almeno una c
                fprintf(f,"%f, %d, %f, %f\n",(float)t/c,t-c,sqrt(i),-sqrt(i));
        }
    }

    fclose(f);
}

Il programma scrive su un file quattro colonne: nella prima c'è il rapporto teste/croci, nella seconda la differenza teste-croci, nelle ultime due i valori di più o meno la radice del numero dei lanci. Il tutto serve per produrre queso grafico:


La curva rossa è il rapporto teste/croci: si stabilizza rapidamente verso il valore 1 (tanto che sembra una retta orizzontale, ma non lo è). La curva blu, invece, è la differenza tra teste e croci: come si vede non si stabilizza per niente, anzi, oscilla molto e il suo andamento è compreso all'interno della parabola viola (non necessariamente all'interno: la variabilità della curva blu è dello stesso ordine di quella della parabola, cioè di più o meno radice del numero di lanci).

10 commenti:

Nico ha detto...

Scusa, ma la curva rossa non dovrebbe invece stabilizzarsi rapidamente verso il valore 1, e non 1/2, essendo il rapporto teste/croci?

zar ha detto...

Oops, ho sbagliato a scrivere, correggo. Grazie.

Juhan ha detto...

Post bellissimo, al solito. Ma volevo far notare che ho trovato, finalmente, chi usa le parentesi nidificate (nestificate?) anche nel testo. E forse mi batte -- 4.

zar ha detto...

Un post contenente del codice deve contenere almeno un paio di parentesi nidificate :-)

giovanna ha detto...

Bello! Che bravo sei, proof!:-)
O, lo so che non lo scopro ora ma: volevo dirlo :-)
g

zar ha detto...

:-)

Fed. ha detto...

Un programma in c che simula il lancio di una moneta? Mi ricorda qualcosa...

zar ha detto...

Lo spero bene... :-)

Fed. ha detto...

Ce l'ho sulla punta della lingua! :D

wo3 ha detto...

Good mathematics helps the student to get admission in higher technology related fields .