Forum libero

Supponiamo di avere un array

a(i) = p

dove p è la probabilità dell'elemento i-esimo.

È possibile scrivere un algoritmo che esegua l'estrazione a caso di un elemento, in modo che la probabilità di essere estratti corrisponda a p?

Cioè se

a(0) = 1/2
a(1) = 1/4
a(2) = 1/4
a(3) = 0

eseguendo estrazioni multiple si osserverà che a(3) non viene mai estratto, e a(0) viene estratto il doppio delle volte di ciascuno degli altri due.

Gatto estrattore