Let us suppose we have a sequence of values $C(i)$ that represent some counter for a given $i$ for $i \in \lbrace 1, \cdots, n \rbrace$. Let us assume some uniform distribution $U$ where selecting any integer between $1$ and $n$ has equal probability. A simple process using this information is to loop for some fixed number of iterations $M$ that, for ease, is a multiple of $n$, and do the following:

  1. Randomly obtain some constant $k \leq n$ number of integers from $U$ and place them into a set $V$
  2. For $i^* = \arg \min V$, do update $C(i^*) \leftarrow C(i^*) + 1$

Ultimately, I want to be able to investigate the quantity $P\left( | C(i) - \frac{1}{n}\sum_{j=1}^n C(j) | \leq \epsilon \right)$ for any $i$. The question I have is if this simple algorithm allows, in probability, for the values of $C(i)$ to remain close to their average values regardless of how many iterations we do. This probability is obviously of a form where one could take advantage of say Hoeffding's inequality but I am not quite sure how to make use of the algorithm structure to get to that point.

I am not very well versed in randomized algorithms and so any insight into how to approach the analysis of such a simple algorithm would be insightful.


Let $P$ be the distribution of $i^*$, which you can calculate explicitly: $$ \begin{align*} p_i := \Pr[P=i] &= \left(1-\frac{i-1}{n}\right)^k - \left(1-\frac{i}{n}\right)^k. \end{align*} $$ This is the probability that all samples are at least $i$ minus the probability that they are all at least $i+1$.

The counter $C(i)$ has binomial distribution $\mathrm{Bin}(M,p_i)$, which will be concentrated around $Mp_i$. In contrast, $\frac{1}{n} \sum_{j=1}^n C(j) = \frac{M}{n}$. Therefore you can only expect $C(i)$ to be close to $\frac{1}{n} \sum_{j=1}^n C(j)$ if $p_i \approx \frac{1}{n}$. Even when $p_i \approx \frac{1}{n}$, the concentration of $C(i)$ is not so good – the standard deviation is $\sqrt{Mp_i(1-p_i)} \approx \sqrt{M/n}$, so the probability that $C(i)$ is very close to $M/n$ is probably quite small.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.