15
$\begingroup$

Imagine you sample $n$ number 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 pairwise independent.

Assuming $n$ is large, what bounds can one get for $\mathbb{E}(X)$?

If we generalize this to $k$-wise independence, for $k \geq 2$, what can we say?

[Also asked at https://math.stackexchange.com/questions/1179943/expected-value-of-the-minimum-with-limited-independence previously. ]

$\endgroup$
9
+50
$\begingroup$

Let $u_k$ be the number of variables with value exactly $k$. If you pick a distribution of the $u_k$ such that $E[u_k]=1$, $E[u_k^2] = 2-1/n$, $E[u_ku_l] = 1-1/n$ for $k \neq l$ and $\sum_{k=1}^n u_k$ is always $1$, then by choosing a random $u_1, \dots ,u_n$ according to the distribution and then choosing a random ordering, you get a random set of variables with the desired independence property.

On the other hand if you do the same thing for $n+1$ pairwise independent random variables you get $E[u_k]=1+1/n$, $E[u_k^2] = 2+ 2/n$, $E[u_k u_l] = 1+1/n$. Here is a way to construct a distribution on $u_k$ that satisfies these conditions. To get a distribution for $n$ pairwise independent random variables, we just delete the last variable. The formula is:

With probability $(1+1/n) /k(k+1)$, we have $u_k=k+1$, $u_l =0$ for $l <k$, $u_l=1$ for $l>k$. To compute the three moments, we ignore a factor of $1+1/n$:

Mean:

$$ \frac{(k+1)}{k(k+1)} + \sum_{l < k} \frac{1}{l(l+1) } = \frac{1}{k} + 1- \frac{1}{k} = 1 $$

Mean of square:

$$ \frac{(k+1)^2}{k(k+1)} + \sum_{l < k} \frac{1}{l(l+1) } = \frac{k+1}{k} + 1- \frac{1}{k+1} = 2 $$

Mean of product is the same as mean, since if $l<k$ then $u_l=1$ whenever $u_k>0$.

Then put back in the factor of $(1+1/n)$ to get the right answer.

The expected value of the minimum of the $n+1$ variables at least $\sum_{k=1}^n (1+1/n) /(k+1) \approx \log n$. Removing a variable won't make the minimum any smaller.

$\endgroup$
  • 1
    $\begingroup$ Nice construction. Those should be $\frac{k+1}{k(k+1)}$ and $\frac{(k+1)^2}{k(k+1)}$ on the left hand sides. Also, in the middle, $\frac{1}{k+1}$ should be $\frac{1}{k}$. $\endgroup$ – Douglas Zare Mar 18 '15 at 7:24
  • $\begingroup$ This is very nice, thank you. I may post a follow up question about the generalization to $k$-wise independence. $\endgroup$ – dorothy Mar 18 '15 at 15:44
9
$\begingroup$

Here are two constructions, showing that the expectation of the min can get down to around $1+1/\sqrt{n}$, and on the other hand can get up to a value approaching $2$ as $n\to\infty$.

Maybe someone can do better!

Let the random variables be $X_1, X_2,\dots, X_n$.

(1) Aiming to make the expected minimum small; the idea is to let each value occur once, with a small perturbation to achieve the required probability that any two variables are the same.

Fix $p>0$ ($p$ will get small as $n$ gets large).

Let $\tilde{X}_1, \dots, \tilde{X}_n$ be a uniform permutation of $\{1,\dots, n\}$. Independently, let $Y$ be drawn uniformly from $\{1,\dots,n\}$. Finally (and independently of $(\tilde{X}_i)$ and $Y$), choose $B_1, B_2, \dots, B_n$ to be independent and each taking value $1$ with probability $p$, and $0$ with probability $1-p$.

Now define $X_i$ by setting \begin{equation*} X_i=\begin{cases}\tilde{X}_i& \text{ if } B_i=0\\ Y&\text{ if } B_i=1\end{cases}. \end{equation*}

If we choose $p$ such that $p^2 + 2p(1-p)/n = 1/n$, then it's easy to check that for each pair $i,j$, the variables $X_i$ and $X_j$ are equal with probability $1/n$. (Namely, $X_i=X_j$ whenever $B_i=B_j=1$, or $B_i=1, B_j=0$ with $Y=\tilde{X}_j$, or $B_i=0, B_j=1$ with $Y=\tilde{X}_i$.) From this it's easy to get (using symmetry) that all the pairwise distributions are as required.

The relevant $p$ is around $1/\sqrt{n}$. Then the probability that the minimum is 1 is approximately $1-p$, and more generally the distribution of the minimum is approximately geometric with parameter $1-p$, and so with mean $1/(1-p)$.

Overall we obtain that the expected minimum is $1+1/\sqrt{n}$ plus smaller order terms.

(2) Aiming to make the expected minimum large; the idea is to let each value occur either 0 or 2 times, again with a small perturbation to get the pairwise distributions precisely right.

For convenience let $n$ be even. Let $Y_1, Y_2, \dots, Y_{n/2}$ be $n/2$ distinct values chosen uniformly at random from $\{1,2,\dots,n\}$.

Now let $\tilde{X}_1, \dots, \tilde{X}_n$ be a uniform permutation of $Y_1, Y_1, Y_2, Y_2, Y_3, Y_3, \dots, Y_{n/2}, Y_{n/2}$.

So each value occurs either 0 or 2 times in the sequence $(\tilde{X}_i)$. The marginal distributions are correct, but the pairwise distributions are not quite correct; we have $\tilde{X}_i=\tilde{X}_j$ with probability $1/(n-1)$, while we want this probability to be $1/n$.

To correct this, let $Z_1, \dots, Z_n$ be a uniform permutation of $\{1,2,\dots, n\}$.

Now with probability $1/n$, let $X_i=Z_i$ for all $i$, and with probability $1-1/n$, let $X_i=\tilde{X}_i$ for all $i$.

Again it's not hard to check that the pairwise distributions are correct.

Now the probability that 1 appears in the sequence is approximately $1/2$; more generally, the distribution of the min of the sequence is approximately geometric with probability $1/2$ (since the numbers of occurrences of $1,2,3,\dots$ are approximately independent).

The expectation of the min is then $2+o(1)$ as $n\to\infty$.

Looking to improve this: note that to get the pairwise distributions right, the number of occurrences of any value $k$ should have mean approximately $1$ and variance approximately $1$ as $n\to\infty$. However, maybe we could improve on construction (2) by one in which the number of occurrences of $1,2,3,\dots$ are not asymptotically independent; again, to get the pairwise distributions right, they have to be asymptotically uncorrelated but this does not imply independence, so maybe by playing around one could get it so that, say, the number of occurrences of 1 and the number of occurrences of 2 tend to be 0 simultaneously (which will help to push up the expected minimum).

$\endgroup$
  • 2
    $\begingroup$ Can you show that there is a constant upper bound for $\mathbb{E}(X)$? $\endgroup$ – Anush Mar 8 '15 at 21:59
  • 1
    $\begingroup$ No. I can get a distributional upper bound. Let $N_k$ be the number of the variables with values in $\{1,2,\dots, k\}$. Then $N_k$ has mean $k$ and variance $k(1-k/n)$. So using the second moment method, $P(X\leq k)=P(N_k>0)\geq \frac{E(N)^2}{E(N)^2+\operatorname{Var}(N)}=\frac{k^2}{k^2+k(1-k/n)}\to \frac{k}{k+1} \text{ as } n\to\infty$. So in particular the distribution of the minimum is tight. However, this doesn't give a bound on the expectation. $\endgroup$ – James Martin Mar 9 '15 at 18:02
  • 1
    $\begingroup$ I should rather say: it doesn't give a constant bound on the expectation. It gives a bound of order $\log n$. $\endgroup$ – James Martin Mar 9 '15 at 22:13
  • $\begingroup$ Thank you. It's interesting in itself that the solution to this simple sounding question does not seem straightforward. $\endgroup$ – dorothy Mar 11 '15 at 14:02
4
$\begingroup$

I'll focus on how low the expected minimum can be under pairwise independence.

Lower bound on the lowest possible expected minimum:

Consider the number $N_1$ of samples equal to $1$ (after the comment by James Martin on his answer). The expected value of $N_1$ is $1$ since it only depends on the distribution of each sample. The variance of $N_1$ depends only on the pairwise joint distributions of the samples. Since the samples are pairwise independent, the variance of $N_1$ is $\frac{n-1}{n}$, just as for independent samples which would give a binomial distribution $\textrm{Bin}(n,\frac{1}{n})$.

Let $a_i = P(N_1 = i)$. Whenever $N_1=0$, the minimum sample is at least $2$, so $E[X] \ge 1+a_0$. Since $E(N_1) = 1, a_0 = \sum_{i=2}^{n} (i-1)a_i.$

$\textrm{Var}(N_1) = \frac{n-1}{n} = \sum_{i=0}^n a_i (i-1)^2 = a_0 + \sum_{i=2}^n a_i (i-1)^2.$

$$\begin{eqnarray}(n-1)a_0 = \sum_{i=2}^n a_i (n-1)(i-1) &\ge& \sum_{i=2}^n a_i(i-1)^2 = \frac{n-1}{n}-a_0. \newline n a_0 &\ge& \frac{n-1}{n} \newline a_0 &\ge & \frac{n-1}{n^2} \newline E[X] &\ge& 1 + \frac{n-1}{n^2} = 1+\frac{1}{n} - \frac{1}{n^2}.\end{eqnarray}$$

Upper bound on the lowest possible expected minimum:

There is a random partition determined by the samples: the sizes of the nonempty preimages. Let us suppose the distribution on functions from indices to sample values is symmetric on the left and right hand sides, under separate permutations of the domain and range. Then it is determined by the distribution on partitions, which we will write as linear combinations of partitions.

For any $1\lt k \le n$, let's consider distributions supported on the two partitions $\lambda_1 = 1+1+1...+1$ and $\lambda_k = k+1+1+...+1$. The first comes from the permutations, so every value is hit once. The second means we choose some random value, get that value on $k$ of the samples, and get $n-k$ distinct values on the other $n-k$ samples.

We would like to find some $p_k \in [0,1]$ so that the mixture of $(1-p_k)\lambda_1$ and $p_k \lambda_k$ is pairwise independent. By symmetry, all we need to do is make sure that the probability that the first two samples are equal is $1/n$. The only way this can happen is if we choose $\lambda_k$, and then both are among the $k$ sent to the special value, which happens with probability $p_k \frac{k}{n} \frac{k-1}{n-1}.$ For $\frac{1}{n} = p_k \frac{k}{n} \frac{k-1}{n-1},$ $p_k = \frac{n-1}{k(k-1)}.$ One requirement is that $k(k-1) \ge n-1$ or else this is not a probability.

What is the expected minimum for $(1- p_k)\lambda_1 + p_k \lambda_k$? If we draw $\lambda_1$, then every number is hit so the minimum is $1$. If we draw $\lambda_k$ then there are $n-k+1$ values out of $n$. If you arrange the values in order $0\lt X=x_1 \lt x_2 \lt ... \lt x_{n-k+1} \lt n+1$, then the average size of any gap is $E[x_{i+1}-x_i] =\frac{n+1}{n-k+2}$ (an exercise) so conditional on choosing $\lambda_k$, $E[X] = \frac{n+1}{n-k+2} = 1+\frac{k-1}{n-k+2}$. The unconditional expectation is thus

$$\begin{eqnarray}E[X] &=& (1-p_k)+ p_k \frac{n+1}{n-k+2} \newline &=& 1- \frac{n-1}{k(k-1)} + \frac{n-1}{k(k-1)}\left( 1 + \frac{k-1}{n-k+2}\right) \newline &=& 1 + \frac{(n-1)(k-1)}{k(k-1)(n-k+2)}.\end{eqnarray}$$

For $k \sim cn, E[X] \approx 1 + \frac{cn^2}{c^2(1-c)n^3} = 1 + \frac{1}{c(1-c)n}.$ This bound is best when $c=\frac{1}{2}.$ If we choose $k \sim \frac{n}{2}$ then we get $E[X] = 1 + \frac{4}{n} + o\left(\frac{1}{n}\right) .$

This construction is within a constant factor (away from $1$) of the lower bound on the expected minimum. It seems likely to be possible to get a better constant by modifying this construction so that there is not full symmetry between the values. We could try to ensure that whenever $1$ is omitted, $2$ is present, for example.

$\endgroup$
  • $\begingroup$ That's very nice. Thank you. Do you think there is a constant upper bound for the highest possible expected minimum too? $\endgroup$ – dorothy Mar 14 '15 at 7:27
  • 2
    $\begingroup$ @Dorothy: I don't know. The argument that James Martin gave in the comments on his answer can be restated as that $E[X] =1+\sum_{k=1}^n P(N_k = 0) \le 1 + \sum_{k=1}^n \frac{1}{k}-\frac{1}{n} = H_n \approx \log n + \gamma.$ The estimate $P(N_k =0 ) \le \frac{1}{k} - \frac{1}{n}$ can only be improved by a constant factor since if you define the partition $\mu_k = k+k+...+k$ then the distribution $\frac{k-2}{k-1} \mu_1 + \frac{1}{k-1} \mu_k$ is pairwise independent and has $P(N_k = 0) \sim \frac{1}{ek}.$ I haven't found a distribution so that for many different $k$, $P(N_k=0)$ is large. $\endgroup$ – Douglas Zare Mar 15 '15 at 1:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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