# How to show that $\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)]$?

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.