nella macchina di Galton inseriamo dei pioli speciali che manderanno sempre a sinistra o a destra le palline
La macchina di Galton è un dispositivo che fornisce una dimostrazione pratica del teorema del limite centrale.
Vogliamo modificarla inserendo dei pioli speciali che manderanno sempre a sinistra o a destra le palline, per fare in modo che in tutti i contenitori finiscano lo stesso numero di palline.
Se il numero di contenitori è 1024, quale è il numero minimo di pioli speciali che bisogna inserire?
Nella macchina originale la distribuzione non è uniforme perché certi contenitori
sono ranggiungibili con molti cammini,
altri con pochi, e due con uno solo (gli estremi).
Devo quindi ostruire tutti cammini ridondanti,
in modo tale che ciascun contenitore sia raggiungibile con un solo cammino,
cioe' mi riduco ad albero binario, tipo Wimbledon alla rovescia.
Quindi, il primo piolo rimane com’è, dal secondo livello fino a metà blocco i pioli estremi.
Arrivato a metà, devo operare su due macchine indipendenti da 512 contenitori.
e così via, ricorsivamente.
Piu' in dettaglio, a metà lascio un livello libero,
poi blocco quattro pioli per ogni livello fino a 3/4, e mi ritrovo con
4 macchine indipendenti da 256 contenitori, etc etc.
Quindi, per n contenitori, quanti pioli devo bloccare ?
Quelli per le due semimacchine più quelli per arrivare a metà:
b(n) = 2 b(n/2) + n - 2
= n log2(n) - 2n + 2
= 0, 2, 10, 34, 98, ... 8194, ...
Comunque, tutto questo vale solo per n potenza di due
Vale solo per potenze di 2, e il numero di pioli da modificare per avere una distribuzione uniforme nei contenitori è
a(2^n) = 2 + 2^(n+1)*(n-1)
About Post Author
