<p>The following lemma implies the inequality in question.</p>
<p><strong>Lemma 1.</strong> <span class="math-container">$E[f_{R\setminus \{a\}}(a)] \le E[f_{R\setminus\{a\}}(a) \,|\, a \in R]$</span></p>
<p><em>Proof.</em> Consider the following experiment:</p>
<ol>
<li><p>Let <span class="math-container">$R$</span> be distributed as in the question (uniformly at random from the size-<span class="math-container">$k$</span> subsets).</p>
</li>
<li><p>Obtain r.v.'s <span class="math-container">$R_1$</span> and <span class="math-container">$R_2$</span> from <span class="math-container">$R$</span> as follows: if <span class="math-container">$a\in R$</span>, let <span class="math-container">$R_1=R_2=R$</span>. Otherwise let <span class="math-container">$R_1 = R \cup\{a\}$</span> and let <span class="math-container">$R_2 = (R \setminus \{x\})\cup\{a\}$</span> where <span class="math-container">$x$</span> is a random element from <span class="math-container">$R$</span>.</p>
</li>
</ol>
<p>Note the following:</p>
<ol start="3">
<li><p>In any outcome
<span class="math-container">$f_{R_1\setminus \{a\}}(a) \le f_{R_2\setminus\{a\}}(a),$</span>
because <span class="math-container">$f$</span> is submodular and <span class="math-container">$R_2 \subseteq R_1$</span>.</p>
</li>
<li><p><span class="math-container">$R_2$</span> is distributed uniformly at random from the size-<span class="math-container">$k$</span> sets containing <span class="math-container">$a$</span>.  That is, the distribution of <span class="math-container">$R_2$</span> is the distribution of <span class="math-container">$R$</span> conditioned on <span class="math-container">$a\in R$</span>.</p>
</li>
</ol>
<p>Now we have</p>
<p><span class="math-container">$\begin{align*}
E[f_{R\setminus\{a\}}(a)]
&amp; = E[f_{R_1\setminus\{a\}}(a)]
&amp;&amp; (\text{because } R\setminus\{a\} = R_1\setminus\{a\})
\\
&amp; \le E[f_{R_2\setminus\{a\}}(a)]
&amp;&amp; (\text{by item 3 above})
\\
&amp; = E[f_{R\setminus\{a\}}(a)\,|\, a\in R]
&amp;&amp; (\text{by item 4 above})~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\Box
\end{align*}$</span></p>
<hr />

CC BY-SA 4.0
2022-11-11T03:53:18.447Z
2022-11-11T16:18:58.327Z
2022-11-11T16:18:58.327Z
Neal Young
<p>I am studying <strong>Lemma 1</strong> of this paper: <a href="https://dl.acm.org/doi/pdf/10.1145/3188745.3188752" rel="nofollow noreferrer">The Adaptive Complexity of Maximizing a Submodular Function</a>. The proof appears on page 11.</p>
<p>I got stuck on this inequality:</p>
<p><a href="https://i.sstatic.net/k8uBO.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/k8uBO.png" alt="" /></a></p>
<p>where <span class="math-container">$f$</span> is a monotone submodular set function, <span class="math-container">$S$</span> and <span class="math-container">$S^{-1}$</span> are two sets, <span class="math-container">$R$</span> is a random subset of <span class="math-container">$S$</span> (sampled from a uniform distribution over subsets of size <span class="math-container">$k$</span>, where <span class="math-container">$k$</span> is some given value.), and <span class="math-container">$f_{R \setminus \{a\}}(a)$</span> is the marginal gain by adding an element <span class="math-container">$a$</span> to the set <span class="math-container">$R \setminus \{a\}$</span>.</p>
<p>In particular, how does the second inequality follows from the submodularity of <span class="math-container">$f$</span>?</p>

CC BY-SA 4.0
2022-11-10T21:01:44.410Z
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
CC BY-SA 4.0
2022-11-10T22:32:35.760Z
@usul $R$ is a random subset of $S$, sampled from a uniform distribution over subsets of size $k$, where $k$ is some given value.
Null_Space
<co.combinatorics><optimization><pr.probability><submodularity>
A bound that follows from submodularity
Null_Space
# A bound that follows from submodularity

(Asked by: username_0 on 2022-11-10)

I am studying **Lemma 1** of this paper: [The Adaptive Complexity of Maximizing a Submodular Function](https://dl.acm.org/doi/pdf/10.1145/3188745.3188752). The proof appears on page 11.

I got stuck on this inequality:

[![](https://i.sstatic.net/k8uBO.png)](https://i.sstatic.net/k8uBO.png)

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

**Tags:** co.combinatorics, optimization, pr.probability, submodularity

> **Comments:**
> **username_1**: 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.  
> **username_0**: @username_1 $R$ is a random subset of $S$, sampled from a uniform distribution over subsets of size $k$, where $k$ is some given value.  

---

## 1 answers

### Answer by username_2 on 2022-11-11. Score: 3 | Accepted answer

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:

3. 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$.
4. $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\*}$

---


---

