Newsgroup: it.hobby.enigmi
Titolo: [MA] Estrazione lineare

Dispongo di n palline numerate da 1 a n, ma invece della classica urna da
cui "pescare" a caso una pallina voglio utilizzare un procedimento diverso
per effettuare l'estrazione. Il procedimento è questo: prendo la pallina 1 e
me la dispongo davanti, poi prendo la pallina 2 e, sulla base dell'esito di
un evento con probabilità a me nota, come ad esempio l'uscita di "testa"
lanciando una moneta o l'uscita di 1 lanciando un dado, decido se tenere la
pallina numero 2 e scartare la 1 o viceversa. Proseguo con la pallina 3,
scegliendo sempre in base al verificarsi di un certo evento con probabilità
a me nota, e decido se tenerla oppure scartarla tenendo la pallina rimasta
dalla scelta precedente. Alla fine rimango con una pallina e quella è il
risultato della mia estrazione.
Voglio ottenere un'estrazione con distribuzione uniforme.
Potrei ad esempio comportarmi così: ogni volta che seleziono una nuova
pallina, lancio una moneta; se viene testa la tengo, altrimenti la scarto.
Mi accorgo però ben presto che in questo modo l'ultima pallina ha
probabilità maggiore delle altre di venire "estratta".
Prima domanda: qual è la probabilità  per ognuna delle n palline di essere
estratta, utilizzando il suddetto procedimento?
Seconda domanda: ammesso di poter disporre di monete e dadi con qualsivoglia
numero di facce,
quale procedimento garantisce un'estrazione con distribuzione uniforme?
Ciao
Giorgio

 un'estrazione con distribuzione uniforme?
Un modo semplice per ottenere una distribuzione uniforme è quello di usare
un dado a due facce quando si sceglie fra le prime due palline, a tre qundo
entra in gioco la pallina numero tre, un i-dado per la pallina i, fino ad un
dado a n facce per la pallina n.
Dopo la prima prova (dado a una faccia !) la pallina uno ha probabilià uno
di continuare la gara, dopo la seconda prova le palline uno e due avranno la
stessa probabilità di sopravvivere e continuare a sperare. Supponiamo che
dopo i-1 prove cio' accada, e dimostriamo che è valido anche per la prova
successiva. Per ipotesi dopo i-1 prove si fronteggeranno la pallina i contro
una pallina che potrà essere con probabilità 1/(i-1) una qualsiasi delle i-1
palline precedenti. Se la prova ha esito positivo la pallina i sarà la
sopravvissuta (probabilità 1/i), con probabilità (i-1)/i la pallina sarà
quella sopravvissuta dai turni precedenti, quindi ancora una delle
precedenti con probabilità 1/(i-1)*(i-1)/i=1/i. Quindi l'induzione è
completa.
Altro modo di vedere la cosa. La pallina i vince se c'è un successo alla
i-esima prova e tutti insuccessi dopo. La probabilità che ciò accada vale:
1/i * i/(i+1) * (i+1)/(i+2) * .. * (n-1)/n = 1/n
Ciao, Silv:o)

 Un modo semplice per ottenere una distribuzione uniforme č quello ...
Credo anche che sia l'unico, visto che ad ogni lancio dobbiamo continuare a
mantenere la simmetria tra le palline sin lě utilizzate.
--
Ciao, Silv:o)

 --
Credo anch'io che sia l'unico e comunque è senz'altro il più semplice. E' il
metodo che uso nei programmi di gioco che devono scegliere tra una rosa di
mosse migliori, tutte di uguale valore, una a caso da giocare. Siccome le
mosse vengono prodotte in maniera sequenziale, invece di metterle in un
array per poi farne alla fine un'estrazione casuale (urna), le scarto o le
tengo di volta in volta sulla base della generazione di un numero casuale
compreso tra 1 e i (dado a i facce). Il bello del metodo è che non si basa
sul valore di n, che, almeno in questo caso delle mosse, non è inizialmente
noto.
Ciao e ... appuntamento a Bologna! :-)
Giorgio