I am trying to understand the proof in Sec. A2 of [Gretton *et al.*](http://www.jmlr.org/papers/volume13/gretton12a/gretton12a.pdf). To make the question self-contained, I summarize below the key ingredients. At the end of the post, I state my question.


Given a Reproducing Kernel Hilbert Space $\mathcal{F}$, we know that any function $f\in\mathcal{F}$ can be evaluated in a point $a$ as $f(a) = \langle f, \phi(a)\rangle$, where the feature mapping $\phi(a)$ takes the usual canonical form $\phi(a) = k(a, \cdot)$. Here $k$ is kernel and $k(a,b) = \langle\phi(a),\phi(b)\rangle$. Moreover, we restrict ourselves to the case of a bounded kernel, specifically $0\leq k(a,b)\leq K$, for any $a$ and $b$.


Let MMD$(\mathcal{F},p,q)$ be the Maximum Mean Discrepancy between two distribution $p$ and $q$ defined in [Gretton *et al.*](http://www.jmlr.org/papers/volume13/gretton12a/gretton12a.pdf) as:
$$\text{MMD}(\mathcal{F},p,q) = \sup\_{f\in\mathcal{F}}({\bf E}\_x[f(x)]-{\bf E}\_y[f(y)]),$$
where $x\sim p$ and $y\sim q$. A biased empirical estimate can be obtained by replacing the population expectations with empirical expectations computed on the samples $X=\{x\_1, x\_2, \dots, x\_m\}$ and $Y=\{y\_1, y\_2, \dots, y\_n\}$, such that $x\_i\sim p$ and $y\_i\sim q$ for all $i$. Then:
$$\text{MMD}\_b(\mathcal{F},X,Y) = \sup\_{f\in\mathcal{F}}\left(\frac{1}{m}\sum\_{i=1}^mf(x\_i)-\frac{1}{n}\sum\_{i=1}^nf(y\_i)\right).$$


It is easy to see that the absolute difference $|\text{MMD}(\mathcal{F},p,q)-\text{MMD}\_b(\mathcal{F},X,Y)|$ is upper bounded by $\Delta(p,q,X,Y)$ defined as:
$$\Delta(p,q,X,Y) = \sup\_{f\in\mathcal{F}}\left|{\bf E}\_x[f(x)]-{\bf E}\_y[f(y)] - \frac{1}{m}\sum\_{i=1}^mf(x\_i)+\frac{1}{n}\sum\_{i=1}^nf(y\_i) \right|.$$


One step of the proof requires to compute McDiarmid's inequality where the function allowed to change is $\Delta(p,q,X,Y)$ with respect to all $x\_i$ and $y\_i$. In order to compute the bounding coefficients for McDiarmid's inequality, at the beginning of page 757 of the referenced paper the authors state that *changing either of $x\_i$ or $y\_i$ in $\Delta(p,q,X,Y)$ results in changes of at most $\frac{2}{m}\sqrt{K}$ or $\frac{2}{n}\sqrt{K}$, respectively*. Recall that $K$ is the bounding value for the kernel.


Now the question is simply: why the bounding values for the McDiarmid's inequality are $\frac{2}{m}\sqrt{K}$ and $\frac{2}{n}\sqrt{K}$ when changing $x\_i$ and $y\_i$, respectively?


Edit: the RKHS $\mathcal{F}$ is actually the unit ball.



How to compute bounding coefficients for McDiarmid's inequality?
The paper you refer to says (in line 1 of Sect. 2.2) that $\mathcal{F}$ is the **unit ball** of a reproducing kernel Hilbert space (not the entire RKHS). So, $|f(a)|=|\langle f, \phi(a)\rangle|\le\|f\| \|\phi(a)\|\le1\times\sqrt{\langle\phi(a),\phi(a)\rangle}=\sqrt{k(a,a)}\le\sqrt K$ for all $f\in\mathcal{F}$ and all points $a$. 
So, any change of the value of $x\_i$ incurs a change of $\Delta(p,q,X,Y)$ not exceeding $\frac1m\,\times2\times\sqrt K=\frac{2}{m}\sqrt{K}$ (in absolute value).


