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.
Comments:


*

*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])$$

*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$.
 A: 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$.
