Skip to main content
2 of 5
added 1457 characters in body

Expectation inequality for sampling without replacement

Is the following proposition correct?

$X_1, X_2, X_3$ are uniformly at random sampled from a finite set $\mathcal X$ without replacement. $f : \mathcal X^2 \rightarrow \mathbb R_{\ge0}$ is symmetric: $ f(x, y) = f(y, x) $, then:

$$ \mathbb E_{X_1, X_2, X_3} f^\frac{1}{2}(X_1, X_2) f^\frac{1}{2}(X_1, X_3) f^\frac{1}{2}(X_2, X_3) \le ( \mathbb E_{X_1, X_2} f(X_1, X_2) )^\frac{3}{2} $$

I tried to use Hoeffding's result $$ \mathbb E f\left( \sum_{i = 1}^n X_i \right) \le \mathbb E f\left( \sum_{i = 1}^n Y_i \right) $$ ($X_i$ are uniformly at random sampled without replacement, $Y_i$ are uniformly at random sampled with replacement, $f$ is convex and continuous) by combining two elements from set $\mathcal X$ to form a new set: $\{ ( X_i, X_j ) : i \ne j, X_i, X_j \in \mathcal X \}$. However, the sampling process for new set is no longer uniformly at random so I cannot use Hoeffding's result.

Since items are sampled uniformly, I can change it to this way: $$ \left( \dfrac{ \sum_{1 \le i < j < k \le n} f_{ij} f_{ik} f_{jk} }{\binom{n}{3}} \right)^2 \le \left( \dfrac{ \sum_{1 \le i < j \le n} f^2_{ij} } {\binom{n}{2}} \right)^3 $$

for $n = 3$, it is easy to see it is correct.

$$ \left( f_{12} f_{13} f_{23} \right)^2 \le \left( \dfrac{ f_{12}^2 + f_{13}^2 + f_{23}^2 }{3} \right)^3 $$

$$ f_{12} f_{13} f_{23} \le \left( \dfrac{ f_{12} + f_{13} + f_{23} }{3} \right)^3 $$

For $n=4$, it is proved by https://artofproblemsolving.com/community/user/12908 $$ \left(\frac{f_{12}f_{13}f_{23}+f_{12}f_{14}f_{24}+f_{13}f_{14}f_{34}+f_{23}f_{24}f_{34}}{4}\right)^2 \leq \left(\frac{f_{12}^2+f_{13}^2+f_{14}^2+f_{23}^2+f_{24}^2+f_{34}^2}{6}\right)^3 $$ or $$\left(\frac{abd+ace+bcf+def}{4}\right)^2\leq\left(\frac{a^2+b^2+c^2+d^2+e^2+f^2}{6}\right)^3$$

$$ \left(\frac{abd+ace+bcf+def}{4}\right)^2 $$ $$ = \left(\frac{a(bd+ce)+(bc+de)f}{4}\right)^2$$ $$ \le\left(\frac{a\sqrt{(b^2+c^2)(d^2+e^2)}+f\sqrt{(b^2+d^2)(c^2+e^2)}}{4}\right)^2 $$ $$ \le \left(\frac{\sqrt{(a^2+f^2)((b^2+c^2)(d^2+e^2)+(b^2+d^2)(c^2+e^2))}}{4}\right)^2 $$ $$ = \frac{(a^2+f^2)(b^2+c^2)(d^2+e^2)+(a^2+f^2)(b^2+d^2)(c^2+e^2)}{16} $$ $$ \le \frac{\left(\frac{a^2+f^2+b^2+c^2+d^2+e^2}{3}\right)^3+\left(\frac{a^2+f^2+b^2+d^2+c^2+e^2}{3}\right)^3}{16} $$ $$ = \left(\frac{a^2+b^2+c^2+d^2+e^2+f^2}{6}\right)^3 $$