Skip to main content
1 of 2
James Martin
  • 3.9k
  • 19
  • 30

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)1/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).

James Martin
  • 3.9k
  • 19
  • 30