# 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(X_1, X_2) f(X_1, X_3) f(X_2, X_3) \le ( \mathbb E_{X_1, X_2} f^2(X_1, X_2) )^{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, this is equivalent to: $$\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$, this is: $$\left(f_{12} f_{13} f_{23}\right)^2 \le \left( \dfrac{ f_{12}^2 + f_{13}^2 + f_{23}^2}{3} \right)^3$$ which follows from the inequality between the geometric mean and the root-mean-square: $$\left(abc\right)^{1/3} \le \sqrt{\dfrac{a^2 + b^2 + c^2}{3}}$$

For $n=4$, this is: $$\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$$ which follows from https://artofproblemsolving.com/community/user/12908: \begin{align} \left(abd+ace+bcf+def\right)^2 &= \Big(a(bd+ce)+(bc+de)f\Big)^2 \\ &\le \left(a\sqrt{(b^2+c^2)(d^2+e^2)}+f\sqrt{(b^2+d^2)(c^2+e^2)}\right)^2 \\ &\le \left(\sqrt{(a^2+f^2)\big((b^2+c^2)(d^2+e^2)+(b^2+d^2)(c^2+e^2)\big)}\right)^2 \\ &= (a^2+f^2)(b^2+c^2)(d^2+e^2)+(a^2+f^2)(b^2+d^2)(c^2+e^2)\\ &\le \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 \end{align}

Let $\lambda_1,\dots,\lambda_n$ be eigenvalues of the symmetric matrix $(f_{ij})$, where $f_{ii}=0$ by definition. They are real, $\sum \lambda_i=0$ and the inequality rewrites as $$\left(\frac{\sum \lambda_i^3}{n(n-1)(n-2)}\right)^2\leqslant \left(\frac{\sum \lambda_i^2}{n(n-1)}\right)^3,$$ or $(\sum \lambda_i^3)^2\leqslant \frac{(n-2)^2}{n(n-1)}(\sum \lambda_i^2)^3$.
Now fix $\sum \lambda_i^2=S$ and $\sum \lambda_i=0$ and maximize $\sum \lambda_i^3$. When $\sum \lambda_i^3$ is maximal, the gradient vectors $(1,1,\dots,1),2(\lambda_1,\lambda_2,\dots,\lambda_n),3(\lambda_1^2,\lambda_2^2,\dots,\lambda_n^2)$ must be linearly dependent by Lagrange multipliers theorem. In other words, there should exist number $A,B,C$ not all equal to 0 such that $A+B\lambda_i+C\lambda_i^2=0$ for all $i$. Therefore $\lambda$'stake at most 2 different values. Without loss of generality $a+b=n$, $a$ $\lambda$'s are equal to $b$, $b$ $\lambda$'s are equal to $-a$ (for some $a\in \{1,2,\dots,n-1\}$), and the inequality rewrites as $(ab^3-ba^3)^2\leqslant \frac{(n-2)^2}{n(n-1)}(ab^2+ba^2)^3$, or $(b-a)^2\leqslant \frac{(n-2)^2}{n-1}ab$. This is clear from $|b-a|\leqslant n-2$, $ab\geqslant n-1$.
• What do you mean by a boundary? Geometrically your set is a sphere of codimension 2. The quadratic equation $A+Bx+Cx^2 =0$ necessarily has real roots (namely, $\lambda$'s). – Fedor Petrov Aug 23 '18 at 12:18