14
$\begingroup$

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 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$?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
9
+50
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thank you! I don't know if it is helpful but Douglas Zare gave a very nice $3$-wise independent process at mathoverflow.net/a/102214/48334 previously. It was interesting as it showed that in that case $4$-wise independence really was necessary. $\endgroup$
    – Simd
    Mar 23, 2015 at 10:53
  • $\begingroup$ @dorothy I think that one has a constant expected minimum. I think getting a nonconstant expected minimum, if possible, requires a distribution that does not treat $1$ to $n$ symmetrically. A related question: If $N_m$ is a random variable valued in $\mathbb N$ whose first three moments are the same as a Poisson variable with mean $m$, what is the largest possible value of $P(N_m=0)$? $\endgroup$
    – Will Sawin
    Mar 24, 2015 at 13:36
  • 2
    $\begingroup$ I think it's $1/m$, just like the answer for $2$ moments, because you can cancel the contribution of $N_m=0$ to the skewness by slightly adjusting the probability that $N_m$ is large, while not affecting the variance very much. The next question is whether you can choose dependencies of the $N_m$s such that the intermediate moments are OK. $\endgroup$
    – Will Sawin
    Mar 24, 2015 at 13:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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