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
    Commented 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
    Commented 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
    Commented Mar 24, 2015 at 13:39

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .