Return to Question

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

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

Imagine you sample $n$ numbers with replacement uniformly from the integers $1,\dots, n$. 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$?

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

Imagine you sample $n$ numbers with replacement uniformly from the integers $1,\dots, n$. 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}$.

Imagine you sample $n$ numbers with replacement uniformly from the integers $1,\dots, n$. 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$?