Comment aborder l'analyse de l'algorithme randomisé

Question

Supposons que nous ayons une séquence de valeurs $ C (i) $ qui représentent un compteur pour une donnée $ i $ pour $ i in lbrace 1, cdots, n rbrace $. Assuons-nous une distribution uniforme $ U $ où sélectionner n'importe quel entier entre $1$ et $ n $ a une probabilité égale. Un processus simple utilisant ces informations consiste à faire boucle pour un nombre fixe d'itérations $ M $ C'est, pour la facilité, est un multiple de $ n $, et faites ce qui suit:

1. Obtenir au hasard une certaine constante $ k leq n $ nombre d'entiers de $ U $ et les placer dans un ensemble $ V $
2. Pour $ i ^ * = arg min v $, faire la mise à jour $ C (i ^ *) Leftarrow C (i ^ *) + 1 $

En fin de compte, je veux pouvoir étudier la quantité $ P Left (| c (i) - frac {1} {n} sum_ {j = 1} ^ n c (j) | leq epsilon droite) $ pour toute $ i $. La question que j'ai est de savoir si cet algorithme simple permet, en probabilité, pour les valeurs de $ C (i) $ rester proche de leurs valeurs moyennes, quel que soit le nombre d'itérations que nous faisons. Cette probabilité est évidemment d'une forme où l'on pourrait profiter de l'inégalité de Say Hoffding, mais je ne sais pas trop comment utiliser la structure de l'algorithme pour arriver à ce point.

Je ne connais pas très bien les algorithmes randomisés et donc tout aperçu de la façon d'approcher l'analyse d'un algorithme aussi simple serait perspicace.