Dimostrando che la probabilità che ogni possibile risultato sia uniforme alla fine di un algoritmo

Question

Ho memoria di $ k $ elementi che puoi immaginare di essere rappresentato da un array. Uno per uno, l'array riceve un valore corrispondente all'Indice del tempo, ad esempio a $ T= 1 $ Il valore sarà $ 1 $ . Ad un certo punto ( $ T= k + 1 $ ) L'array sarà pieno e dobbiamo scegliere un valore all'interno dell'array da sostituire con quello nuovo. L'obiettivo è trovare un algoritmo che emette un sottoinsieme uniforme di $ k $ elementi. Ad esempio, con $ k= 2 $ e $ t= 3 $ emetterà con la probabilità uniforme Di seguito: $ {1,2 \} $ , $ \ {1,3 \} $ o $ \ {2,3 \} $ . Un possibile algoritmo è il seguente:

.
1. Crea array di $ k $ elementi
2. per $ t= 1, \ ldots, t $ :
3. Se l'array non è completo inserire uno spazio vuoto
4. Ricevi un ingresso
5. Scarta l'ingresso con probabilità $ 1 - k / t $
6. Altrimenti inserisci l'ingresso in una posizione uniforme
7. fine per
8. Array di ritorno

È facile implementare un tale programma e convincere te stesso che questa è davvero una soluzione al problema, ma come lo dimostrando? Essenzialmente ho bisogno di dimostrare che ogni sottoinsieme ha probabilità $ 1 / \ binom tk $ per essere il risultato alla fine (questo perché $ \ binom tk $ è il numero di possibili sottoinsiemi di $ k $ elementi al momento $ T $ < / span>).

Answer 1

La prova è per induzione. Il caso base $ t= k $ è chiaro. Supponiamo che il reclamo sia vero in qualche momento $ T $ . Lo dimostraremo per il tempo $ t + 1 $ .

Lascia la prima classe $ T + 1 $ Elementi essere $ x_1, \ ldots, x_ {t + 1} $ . Dall'ipotesi di induzione, al momento $ T $ ciascuno dei $ \ binom {t} {k} $ Possibile $ k $ -subsets di $ x_1, \ ldots, x_t $ si trova nell'array con uguale probabilità. La probabilità che al passaggio $ T + 1 $ L'array rimane lo stesso è $ 1-k / (T + 1) $ , quindi ciascuna delle $ k $ -subsets di $ x_1, \ ldots, x_t $ appare al tempo $ T + 1 $ con probabilità $$ \ frac {t + 1-k} {t + 1} \ frac {1} {\ binom {t} {k}}=frac {1} {\ binom {t + 1} {k}}. $$ Considera ora alcuni $ k $ -subset $ s $ di $ x_1, \ Ldots, x_ {T + 1} $ che contiene $ x_ {t + 1} $ . Per questo set da appoggiare al momento $ t + 1 $ , i seguenti due eventi devono verificarsi: al momento $ t $ , l'array consisteva in $ s \ setminus \ {x_ {t + 1} \} $ insieme a una delle matematiche $ T- (k-1) $ elementi rimanenti; e al momento $ T + 1 $ , questo elemento è stato sostituito da $ x_ {t + 1} $ . In totale, la probabilità è $$ \ frac {k} {t + 1} \ clot \ frac {1} {k} \ clot \ frac {t-k + 1} {\ binom {t} {k}}=frac {1} {\ binom {T + 1} {K}}. $$