How to approach analysis of randomized algorithm
Let $P$ be the distribution of $i^*$, which you can calculate explicitly:
$$
\begin{align*}
p_i := \Pr[P=i] &amp;= \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.