Return to Question

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, 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} \frac{1}{16}\left(abd+ace+bcf+def\right)^2 & = \frac{1}{16}\Big(a(bd+ce)+(bc+de)f\Big)^2 \\ &\le\frac{1}{16}\left(a\sqrt{(b^2+c^2)(d^2+e^2)}+f\sqrt{(b^2+d^2)(c^2+e^2)}\right)^2 \\ & \le \frac{1}{16}\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 \\ & =\frac{1}{16} \Big((a^2+f^2)(b^2+c^2)(d^2+e^2)+(a^2+f^2)(b^2+d^2)(c^2+e^2)\Big)\\ & \le \frac{1}{16}\left(\frac{a^2+f^2+b^2+c^2+d^2+e^2}{3}\right)^3+\frac{1}{16}\left(\frac{a^2+f^2+b^2+d^2+c^2+e^2}{3}\right)^3 \\ & = \left(\frac{a^2+b^2+c^2+d^2+e^2+f^2}{6}\right)^3 \end{align}

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}

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, 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$, 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 $$ which follows from \begin{align} \frac{1}{16}\left(abd+ace+bcf+def\right)^2 & = \frac{1}{16}\Big(a(bd+ce)+(bc+de)f\Big)^2 \\ &\le\frac{1}{16}\left(a\sqrt{(b^2+c^2)(d^2+e^2)}+f\sqrt{(b^2+d^2)(c^2+e^2)}\right)^2 \\ & \le \frac{1}{16}\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 \\ & =\frac{1}{16} \Big((a^2+f^2)(b^2+c^2)(d^2+e^2)+(a^2+f^2)(b^2+d^2)(c^2+e^2)\Big)\\ & \le \frac{1}{16}\left(\frac{a^2+f^2+b^2+c^2+d^2+e^2}{3}\right)^3+\frac{1}{16}\left(\frac{a^2+f^2+b^2+d^2+c^2+e^2}{3}\right)^3 \\ & = \left(\frac{a^2+b^2+c^2+d^2+e^2+f^2}{6}\right)^3 \end{align}

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, 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} \frac{1}{16}\left(abd+ace+bcf+def\right)^2 & = \frac{1}{16}\Big(a(bd+ce)+(bc+de)f\Big)^2 \\ &\le\frac{1}{16}\left(a\sqrt{(b^2+c^2)(d^2+e^2)}+f\sqrt{(b^2+d^2)(c^2+e^2)}\right)^2 \\ & \le \frac{1}{16}\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 \\ & =\frac{1}{16} \Big((a^2+f^2)(b^2+c^2)(d^2+e^2)+(a^2+f^2)(b^2+d^2)(c^2+e^2)\Big)\\ & \le \frac{1}{16}\left(\frac{a^2+f^2+b^2+c^2+d^2+e^2}{3}\right)^3+\frac{1}{16}\left(\frac{a^2+f^2+b^2+d^2+c^2+e^2}{3}\right)^3 \\ & = \left(\frac{a^2+b^2+c^2+d^2+e^2+f^2}{6}\right)^3 \end{align}

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

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, 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$, 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 $$ which follows from \begin{align} \frac{1}{16}\left(abd+ace+bcf+def\right)^2 & = \frac{1}{16}\Big(a(bd+ce)+(bc+de)f\Big)^2 \\ &\le\frac{1}{16}\left(a\sqrt{(b^2+c^2)(d^2+e^2)}+f\sqrt{(b^2+d^2)(c^2+e^2)}\right)^2 \\ & \le \frac{1}{16}\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 \\ & =\frac{1}{16} \Big((a^2+f^2)(b^2+c^2)(d^2+e^2)+(a^2+f^2)(b^2+d^2)(c^2+e^2)\Big)\\ & \le \frac{1}{16}\left(\frac{a^2+f^2+b^2+c^2+d^2+e^2}{3}\right)^3+\frac{1}{16}\left(\frac{a^2+f^2+b^2+d^2+c^2+e^2}{3}\right)^3 \\ & = \left(\frac{a^2+b^2+c^2+d^2+e^2+f^2}{6}\right)^3 \end{align}