Come affrontare l'analisi dell'algoritmo randomizzato

Question

Supponiamo che abbiamo una sequenza di valori $ C (i) $ che rappresentano un po 'di contatore per un dato $ i $ per $ i in lbrace 1, CDOTS, n rbrace $. Supponiamo che una distribuzione uniforme $ U $ dove selezionare qualsiasi intero tra $1$ e $ n $ ha uguale probabilità. Un semplice processo che utilizza queste informazioni è loop per un numero fisso di iterazioni $ M $ Questo, per facilità, è un multiplo di $ n $, e fai quanto segue:

1. Ottenere casualmente un po 'di costante $ k leq n $ numero di numeri interi da $ U $ e mettili in un set $ V $
2. Per $ i^* = arg min v $, aggiorna $ C (i^*) leftarrow c (i^*) + 1 $

Alla fine, voglio essere in grado di indagare sulla quantità $ P left (| c (i) - frac {1} {n} sum_ {j = 1}^n c (j) | leq epsilon a destra) $ per ogni $ i $. La domanda che ho è se questo semplice algoritmo consente, in probabilità, per i valori di $ C (i) $ rimanere vicini ai loro valori medi indipendentemente da quante iterazioni facciamo. Questa probabilità è ovviamente di una forma in cui si potrebbe sfruttare la disuguaglianza di Hoeffding, ma non sono sicuro di come utilizzare la struttura dell'algoritmo per arrivare a quel punto.

Non sono molto esperto di algoritmi randomizzati e quindi qualsiasi intuizione su come affrontare l'analisi di un algoritmo così semplice sarebbe perspicace.