I posted a related question also to math.SE.

Basically, I would like to know how to show the following, which is part of this paper:

\begin{align} &\frac{1}{m} \mathbb E_{X,X'}\left[\sum_{i=1}^m\sum_{j=1}^m\left(k(x_i, x_j) + k(x_i', x_j') -k(x_i,x_j') - k(x_i',x_j)\right)\right]^\frac{1}{2} \\ \leq & \frac{1}{m}\left[2m\mathbb E_xk(x,x) + 2m(m-1)\mathbb E_{x,x'}k(x,x')-2m^2\mathbb E_{x,x'}k(x,x')\right]^\frac{1}{2} \end{align}

As part of this, I am asking:

How to proof that for samples $X,X'$ of size $m$ and with distribution $p$ we have that

\begin{align} &\mathbb E_{X,X'} \left[\sum_{i=1}^m\sum_{j=1}^mk(x_i,x_j) \right]\\ = & 2m\mathbb E_{x\sim p} [k(x,x)] \end{align}

where $x_i \in X, x_i'\in X'$ for all $i=1,\dots,m$, and $\mathbb E_{X,X'}$ denotes the expectation over all possible i.i.d. samples $X,X'$.

$k(\cdot,\cdot)$ is a (real-valued) kernel function, i.e., it is symmetric in its arguments and zero if both arguments are the same.

Thanks in advance!


1 Answer 1


Ok, the question is ill-posed. In fact, to follow the proof, it suffices to reorder the terms in the sum as to arrive at the proper solution (handling the diagonal-elements separately).

  • 1
    $\begingroup$ Your answer could be improved with additional supporting information. Please edit to add further details, such as citations or documentation, so that others can confirm that your answer is correct. You can find more information on how to write good answers in the help center. $\endgroup$
    – Community Bot
    Dec 15, 2021 at 10:27

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.