generazione in linea di campioni uniformi

Question

Una fonte fornisce un flusso di elementi $ x_1, x_2, \ dots $. Ad ogni passo $ n $ vogliamo salvare un campione casuale $ S_n \ subseteq \ {(x_i, i) | 1 \ le i \ le n \} $ di dimensione $ k $, vale a dire $ S_n $ dovrebbe essere una scelta uniforme campione da ogni $ \ tbinom {n} {k} $ possibili campioni composto da elementi visti. Così ad ogni passo $ n \ ge k $ dobbiamo decidere se aggiungere l'elemento successivo da $ S $ o meno. Se è così dobbiamo anche decidere quale delle voci attuali per rimuovere da $ S $.

Stato di un algoritmo per il problema. Dimostrare la sua correttezza.

Answer 1

A causa della natura dubbia della questione, ho solo fornire suggerimenti.

Hai provato l'ovvio? Con probabilità $ \ frac {1} {n} $, aggiungere il nuovo elemento al campione. Se si aggiunge, scegliere uno degli elementi già nel campione uniformemente a caso e rilasciarlo. Suoni circa giusto, non è vero?

Per una prova, si dovrà procedere induttivamente. Nella fase, si assume che $ S_ {n-1} $ è davvero un campione uniforme. Da questo e il modo in cui si sceglie se includere $ x_n $ e quale elemento a goccia, si deve ottenere che $ S_n $ è un campione omogeneo, anche.

Prova se si può dimostrare sopra un'idea corretta. Se non lo è, scoprire dove sia il problema e risolverlo. Vedere questa risposta a una domanda simile per un'applicazione dettagliata di questa tecnica.

Answer 2

Il miglior algoritmo per il vostro problema è algoritmo di campionamento Reservoir. Leggi questo