Skip to main content
MathOverflow

Return to Answer

added 32 characters in body
Source Link
Douglas Zare
Douglas Zare
  • 28k
  • 6
  • 90
  • 130

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 identitypermutations, 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.

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 identity. 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.

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.

Source Link
Douglas Zare
Douglas Zare
  • 28k
  • 6
  • 90
  • 130

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 identity. 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.