Suppose $f$ is a submodular set function on a universe $U$ of size $n$.
For $k \in \{0,\ldots,n\}$, let $$ F(k) = \operatorname*{\mathbb{E}}_{X \in \binom{U}{k}} f(X), $$ where $\binom{U}{k}$ is the set of all subsets of $U$ of size $k$.
We are interested in proving the following inequality: $$ F(k) \geq \frac{k}{n} F(n) + \frac{n-k}{n} F(0). $$ One can prove this inequality by induction on $k$ (or even directly, if we're careful), but this doesn't explain why the inequality holds. Instead, we will use some form of term rewriting.
Submodularity directly implies the following inequality, for $k \in \{1,\ldots,n-1\}$: $$ F(k) \geq \frac{1}{2} F(k+1) + \frac{1}{2} F(k-1). $$ Imagine applying this inequality over and over again, in an arbitrary way. Here is an example for $n = 3$ and $k = 2$: $$ \begin{align*} F(2) &\geq \frac{1}{2} F(3) + \frac{1}{2} F(1) \\ &\geq \frac{1}{2} F(3) + \frac{1}{4} F(2) + \frac{1}{4} F(0) \\ &\geq \frac{5}{8} F(3) + \frac{1}{8} F(1) + \frac{1}{4} F(0) \\ &\geq \frac{5}{8} F(3) + \frac{1}{16} F(2) + \frac{5}{16} F(0) \\ &\geq \cdots \\ &\geq \frac{2}{3} F(3) + \frac{1}{3} F(0). \end{align*} $$ The dots hide infinitely many steps.
There is a way to make this argument completely rigorous. One can cook up some potential function that increases whenever one applies any instance of submodulary (for example, the expectation of squared cardinality). Taking the consequence of $F(k)$ maximizing this potential, it's easy to see that we get an inequality of the form $$ F(k) \geq \alpha F(n) + \beta F(0). $$ If $f$ is any modular function then there is equality. Taking $f = 1$ we find that $\alpha + \beta = 1$, and taking $f(X) = |X|$ we determine $\alpha = k/n$.
This argument extends to prove more interesting inequalities on submodular functions.
Does this sort of reasoning look familiar?
