Dato un flusso di pacchetti {s1, s2, ...} che ci arrivano uno per volta, ed una memoria limitata in cui possiamo memorizzare al più k elementi, ad ogni istante t > k ci arriva il pacchetto t-esimo e dobbiamo decidere se memorizzarlo (e quindi sostituirlo con uno già presente in memoria) o meno.
Ho progettato un algoritmo probabilistico che all'istante t > k memorizza il t-esimo pacchetto con probabilità k/t.
Il mio dubbio ora è il seguente:
Sia X(t) la variabile aleatoria che indica l’insieme di pacchetti presenti in memoria all’istante t > k, per ogni sottoinsieme S ⊆ {s1,..., st} con |S| = k, qual è la probabilità dell’evento {X(t)= S} sapendo che ogni elemento ha probabilità k/t di essere in X(t) ?