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](https://brilliant.org/wiki/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$.



What is the expected value of the submeasure of a random set?
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$.


