# What is the expected value of the submeasure of a random set?

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.

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

• 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). – Anthony Quas Oct 11 '18 at 8:11
• 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). – Anthony Quas Oct 11 '18 at 8:49

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