5
$\begingroup$

Let $N \in \mathbb N$ and suppose that $\phi$ is a submeasure on $[1,N] = \{1,2,\dots,N\}$, by which I mean that $\phi$ is a function $\mathcal P ([1,N]) \rightarrow \mathbb R$ such that

i. $A \subseteq B$ implies $\phi(A) \leq \phi(B)$,

ii. $\phi(A \cup B) \leq \phi(A) + \phi(B)$ for any $A, B \subseteq [1,N]$, and

iii. $\phi(\emptyset) = 0$.

Suppose we choose a subset $X$ of $[1,N]$ at random. We do not know anything about the probability distribution used to select $X$, except that for every $i \in [1,N]$ the probability $P(i \in X)$ that $i$ is in the random set $X$ is at least $\varepsilon > 0$.

I would like to have a lower bound for the expected value of $\phi(X)$ in terms of $\varepsilon$ and $\phi([1,N])$. I conjecture that

$$E(\phi(X)) \,\geq\, \frac{1}{2} \cdot \varepsilon \cdot \phi([1,N])$$

but cannot seem to prove it. I would be happy if there is any constant $c > 0$ (independent of $N$, but possibly dependent on $\varepsilon$) such that

$$E(\phi(X)) \,\geq\, c \cdot \varepsilon \cdot \phi([1,N]).$$

(So my conjecture is that taking $c = \frac{1}{2}$ will do, but if you have a proof for some smaller value of $c$ then I would still love to see it.) My question is simply whether either of these bounds is true.

Comments:

  1. If $\phi$ is a measure instead of a submeasure, then it follows from the linearity of expectation that $E(\phi(X)) \geq \varepsilon \cdot \phi([1,N])$ (an even better lower bound than the conjectured one above). Indeed, if $\phi$ is a measure then $$E(\phi(X)) = E\left( \sum_{i \in X}\phi(\{i\}) \right) = E\left( \sum_{i \in [1,N]}\phi(\{i\} \cap X) \right) = \sum_{i \in [1,N]}E(\phi(\{i\} \cap X)) = \sum_{i \in [1,N]}P(i \in X)\phi(\{i\}) \geq \varepsilon \sum_{i \in [1,N]}\phi(\{i\}) = \varepsilon \cdot \phi([1,N])$$

  2. Despite the previous comment, the factor of $\frac{1}{2}$ in my conjecture is necessary. For example, $\phi$ could be a submeasure on $[1,N]$ that assigns $\phi(\emptyset) = 0$, $\phi([1,n]) = 2$, and $\phi(A) = 1$ for all other $A \subseteq [1,N]$. If $X$ is selected uniformly at random from among the $N$ sets of the form $[1,N] \setminus \{i\}$, then we have $E(\phi(X)) = 1$ but $\varepsilon \cdot \phi([1,N]) = 2 - \frac{2}{N} \approx 2$.

$\endgroup$
2
  • 1
    $\begingroup$ I'm pretty sure the answer is no, but I'm trying to nail down the details. I think it boils down to efficiency of coverings. Consider $S=\{a,b,c\}^n$ and let $P$ be the collection of all $3^n$ subsets of the form $A_1\times A_2\times\ldots\times A_n$, where each $A_i$ has cardinality 2. Define $\phi(A)$ to be the size of its smallest covering by members of $P$. Let $X$ be a random variable taking uniform values in $P$. Then $\epsilon=(2/3)^n$ and $E(\phi(X))=1$, so we need to show that $\phi(S)\gg (3/2)^n$ (that is that $P$ doesn't cover $S$ efficiently). $\endgroup$ – Anthony Quas Oct 11 '18 at 8:11
  • 1
    $\begingroup$ There is an old result of Coxeter, Few and Rogers (Covering space with equal spheres. Mathematika 6 1959 147–157, mathscinet.ams.org/mathscinet-getitem?mr=124821), proving that in coverings of $n$-dimensional space by balls, the "inefficiency" (that is the average number of times a point is covered) is at least $Kn$. By discretizing, this should lead to a counterexample of the type that I'm suggesting. (Hopefully something cleaner will also work). $\endgroup$ – Anthony Quas Oct 11 '18 at 8:49
5
$\begingroup$

Let $n$ be chosen arbitrarily and let $S_k=\{1,2,\ldots,n\}^k$ and let $\mathcal P$ be the collection of all Cartesian products of the form $A_1\times\ldots\times A_k$ where $|A_i|=n-1$. For $Z\subset S_k$, define $\phi(Z)=\min\{j\colon \exists P_1,\ldots,P_j\in \mathcal P:P_1\cup\ldots\cup P_k\supset Z\}$.

I claim that $\phi(S_k)>k$. The proof is by induction. In the case $k=1$, $\phi(S_1)=2$. Now suppose the result holds for $k$ and suppose we have a covering of $S_{k+1}$. Let the first element be $P_1$, which we may suppose by re-labelling is $\{2,\ldots,n\}^{k+1}$. Now the remaining elements are required to cover $\{1,\ldots,n\}^{k}\times \{1\}$. In particular, projecting them onto the first $k$ coordinates, they are required to cover $\{1,\ldots,n\}^k$. By the inductive hypothesis, the number of additional elements in the cover exceeds $k$, so that $\phi(S_{k+1})>k+1$ as required.

In particular, we have $\phi(S_n)>n$. Now if $X$ is a random variable taking values in $\mathcal P$, all with equal probability, then we see that for each element of $S_n$, the probability that it is contained in $X$ is $\epsilon=(\frac{n-1}n)^n\approx e^{-1}$.

So for any $c>0$, we have $\mathbb E\phi(X)=1\le c\epsilon \phi(S_n)$ for all sufficiently large $n$.

$\endgroup$

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.