Imagine you sample $n$ numbers with replacement uniformly from the integers $1,\dots, n$ (we can assume $n$ is large). Let $X$ be the minimum of these samples. I am interested in $\mathbb{E}(X)$ but with a twist. All I know is that the samples are uniform and $k$-wise independent for some $k$.



> 
> What is the smallest $k$ so that there is a constant upper bound for $\mathbb{E}(X)$? 
> 
> 
> 


We know from the very nice answer of Will Sawin at [Expected value of the minimum with limited independence](https://mathoverflow.net/questions/199382/expected-value-of-the-minimum-with-limited-independence) that for pairwise independence, that is for $k=2$, $ \mathbb{E}(X)$ can be as large as approximately $\log {n}$. Obviously if $k=n$ then there is a constant upper bound on the expected minimum. What can we say for $k$ between $2$ and $n$?



Smallest $k$ so that $k$-wise independence guarantees a constant expected minimum
I can do $k\geq 4$. This is done using a method similar to the upper bound from last time. Let $N\_m$ be the number of samples that are at most $m$. Then we wish to upper bound the probability that $N\_m=0$. We can do this using the fourth moment method, because the first four moments are the same as for a totally independent and uniform distribution. 


$E(N\_m-m)^4=3m^2(n-m)^2(n-1)/n^3 + (m^3+(n-m)^3) m(n-m)/n^4= O(m^2)$


So the probability that $N\_m-m= -m$ is $O(1/m^2)$. Summing over all $m$ and adding $1$ to find the expectation of the minimum gives something $O(1)$. (Close to $1+ \pi^2/2$, I think.)


I'm not sure about $k=3$, but I'll think about it


