A bound that follows from submodularity

I am studying Lemma 1 of this paper: The Adaptive Complexity of Maximizing a Submodular Function. The proof appears on page 11.

I got stuck on this inequality:

where $$f$$ is a monotone submodular set function, $$S$$ and $$S^{-1}$$ are two sets, $$R$$ is a random subset of $$S$$ (sampled from a uniform distribution over subsets of size $$k$$, where $$k$$ is some given value.), and $$f_{R \setminus \{a\}}(a)$$ is the marginal gain by adding an element $$a$$ to the set $$R \setminus \{a\}$$.

In particular, how does the second inequality follows from the submodularity of $$f$$?

• Okay, submodularity is equivalent to a larger marginal gain if we add $a$ to a superset than the marginal gain to its subset. I can see an intuition that if we assume $a \in R$, then $R\setminus \{a\}$ is a smaller set. Whereas if $a \not\in R$, then $R \setminus \{a\} = R$ which is a large, so $a$ gives a larger marginal gain in the first place. But I don't immediately see that as compatible with conditional probability. It seems to rely on something you haven't told us about $R$, like each element is included with equal independent probability.
– usul
Commented Nov 10, 2022 at 21:01
• @usul $R$ is a random subset of $S$, sampled from a uniform distribution over subsets of size $k$, where $k$ is some given value. Commented Nov 10, 2022 at 22:32

The following lemma implies the inequality in question.

Lemma 1. $$E[f_{R\setminus \{a\}}(a)] \le E[f_{R\setminus\{a\}}(a) \,|\, a \in R]$$

Proof. Consider the following experiment:

1. Let $$R$$ be distributed as in the question (uniformly at random from the size-$$k$$ subsets).

2. Obtain r.v.'s $$R_1$$ and $$R_2$$ from $$R$$ as follows: if $$a\in R$$, let $$R_1=R_2=R$$. Otherwise let $$R_1 = R \cup\{a\}$$ and let $$R_2 = (R \setminus \{x\})\cup\{a\}$$ where $$x$$ is a random element from $$R$$.

Note the following:

1. In any outcome $$f_{R_1\setminus \{a\}}(a) \le f_{R_2\setminus\{a\}}(a),$$ because $$f$$ is submodular and $$R_2 \subseteq R_1$$.

2. $$R_2$$ is distributed uniformly at random from the size-$$k$$ sets containing $$a$$. That is, the distribution of $$R_2$$ is the distribution of $$R$$ conditioned on $$a\in R$$.

Now we have

\begin{align*} E[f_{R\setminus\{a\}}(a)] & = E[f_{R_1\setminus\{a\}}(a)] && (\text{because } R\setminus\{a\} = R_1\setminus\{a\}) \\ & \le E[f_{R_2\setminus\{a\}}(a)] && (\text{by item 3 above}) \\ & = E[f_{R\setminus\{a\}}(a)\,|\, a\in R] && (\text{by item 4 above})~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\Box \end{align*}