Sampling da multiset in spazio limitato
Inviato: 29 set 2007, 13:15
La signorina A va in giro per il suo paese alla ricerca di un fidanzato ed incontra una serie di m pretendenti che rappresentiamo con una sequenza $ s = s_1 s_2 \ldots s_m $, dove $ s_i $ è il codice fiscale dell'i-esimo tizio. Attenzione perchè nella sua visita può incontrare più volte la stessa persona, quindi $ s $ può contenere ripetizioni.
Nonostante ciò A vuole scegliere il suo boyfriend in maniera equiprobaile nell'insieme dei pretendenti distinti che ha incontrato (l'amore è cieco in questo caso). Purtroppo è davvero smemorata, può ricordarsi al massimo di $ O(\log m) $ bits, in compenso ha un potente generatore di interi pseudocasuali che associa ad ogni codice fiscale un intero tra 1 ed $ m^3 $ preso uniformemente a caso. Sotto tali vincoli A riesce nel suo intento con probabilità $ \geq 1 - 1/m $, molto elevata in pratica, quale algoritmo può usare?
Nonostante ciò A vuole scegliere il suo boyfriend in maniera equiprobaile nell'insieme dei pretendenti distinti che ha incontrato (l'amore è cieco in questo caso). Purtroppo è davvero smemorata, può ricordarsi al massimo di $ O(\log m) $ bits, in compenso ha un potente generatore di interi pseudocasuali che associa ad ogni codice fiscale un intero tra 1 ed $ m^3 $ preso uniformemente a caso. Sotto tali vincoli A riesce nel suo intento con probabilità $ \geq 1 - 1/m $, molto elevata in pratica, quale algoritmo può usare?
.