Expectation of $\min(a \bmod p,2a\bmod p,....,ka \bmod p)$

Seems like a tough question in full generality, and I have no answer, but merely ideas in very special cases, when taking limits of the parameters in a precise order.

So, if you wish to fix $k$ and let $p$ goes to infinity, then you will have the following convergence in distribution. I let $M_p$ be the random variable to be studied.

$$ \frac{M_p}{p} \Rightarrow \min({ \{j U\}, j = 1 \ldots k }) $$

where $U$ is uniform on $(0,1)$ and $\{x\}$ is the fractional part of $x$

You may compute explicitly the density of the RHS random variable for $k$ small. And you also have convergence of the expectations (since it is bounded).

Then, we want to let $p\to \infty$ and a first and interesting question would be to establish that there is a constant $C$ such that :

$$E[\min({ \{j U\}, j = 1 \ldots k })] \sim C/k$$

which is not obvious because of the very rigid relation between the random variables $(\{jU\}, j = 1 \ldots k).$ To start things and understand this law for a small fixed $k$, I recommend to plot the functions $$ x \mapsto x, x \mapsto \{2x\}, \ldots , x \mapsto \{kx\} $$ on a same graph and look at the shape of their min.

If you look at the part of the graph :

• for $x$ between $[1-1/k, 1]$ then you find that for such $x=1-\epsilon$, $\epsilon \in [0,1/k)$

$$ \min( \{j(1-\epsilon)\}, j=1 \ldots k ) = 1-k \epsilon $$

• more generally, for $x$ between $[2^{-j}(1-1/k), 2^{-j}]$ then you find that for such $x=2^{-j}-\epsilon$, $\epsilon \in [0,2^{-j}/k]$

$$ \min( \{j (2^{-j}-\epsilon) \}, j=1 \ldots k ) \ge 2^{-j}- k \epsilon $$

thus

$$E[\min({ \{j U\}, j = 1 \ldots k })] \ge (\sum_{j\ge 0} \frac{1}{2^{2j+1}} ) \frac{1}{k} = \frac{\pi^2}{12} \frac{1}{k} $$

Notice the above constant satifies $1/2<\frac{\pi^2}{12} < 1$. (I'm also interested in the comparison with $1$ because this is the right order for n iid uniform on $(0,1)$).

--

There are papers on CLT for such "rotations on the circle", that have considered as achievements in the field, you should check them; notice the min functional is arguably more difficult to deal with than the normalized sum that appear in the CLT.