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}


1 Answer 1


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

  • $\begingroup$ If the quadratic equation does not have real roots, we need to check the boundary right? Or is it obvious that on the boundary the inequality holds? $\endgroup$
    – Rui Zhang
    Aug 23, 2018 at 11:03
  • $\begingroup$ 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). $\endgroup$ Aug 23, 2018 at 12:18
  • $\begingroup$ You are right! Thank you so much for your time and effort for solving this problem! $\endgroup$
    – Rui Zhang
    Sep 2, 2018 at 12:38
  • $\begingroup$ By the way, do you think it will hold in the more general case: LHS are n samples from whole set, and product become all the k out of n combinations, while the RHS are k samples directly from whole set? $\endgroup$
    – Rui Zhang
    Sep 2, 2018 at 12:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.