# Kolmogorov-Smirnov distance and expectation

Let $$P$$ and $$Q$$ be two probability measures over $$R^n$$, with CDF denoted by $$F_P,F_Q$$, respectively (that is, $$F_P(x)=P(\{x'\in R^n:x'\leq x\})$$, where $$\leq$$ is taken componentwise. The Kolmogorov-Smirnov distance between $$P$$ and $$Q$$ is defined as $$d_{KS}(P,Q)=\sup_x |F_P(x)-F_Q(x)|$$.

Let $$f$$ be a nonnegative, bounded Borel measurable function defined on $$R^n$$, say $$0\leq f \leq M$$, and denote by $$E_P[f]$$ the expectation (integral) of $$f$$ taken according to $$P$$; similarly for $$E_Q[f]$$. Suppose $$d_{KS}(P,Q)\leq \epsilon$$. What can be said about $$|E_P[f]-E_Q[f]|$$? Ideally, I am looking for a bound of the form $$|E_P[f]-E_Q[f]|\leq \epsilon\cdot C$$, for some constant $$C$$ not depending on $$\epsilon$$.

$$\newcommand\ep\epsilon\newcommand\R{\mathbb R}$$No such bound exists.

Indeed, take any real $$\ep>0$$.

Take any natural $$n\ge1/(2\ep)$$. Let $$p(x):= \sum_{j=0}^{2n-1}1\Big(\frac{2j}{2n} for real $$x$$. Then $$p\ge0$$ and $$\int_\R p=1$$. So, $$p$$ is the density of some probability measure $$P$$ over $$\R$$.

Let $$q(x):=p(x-\frac1{2n})$$ for real $$x$$. Then $$q$$ is the density of some probability measure $$Q$$ over $$\R$$. Moreover, $$F_Q\le F_P\le F_Q+\frac1{2n}\le F_Q+\ep$$, so that $$d_{KS}(P,Q)\le\ep$$.

On the other hand, $$p^2=p$$ and $$qp=0$$. So, for $$f=p$$ we have $$0\le f\le1$$, $$E_P[f]=\int_\R p^2=\int_\R p=1$$, and $$E_Q[f]=\int_\R qp=\int_\R 0=0$$. So, $$E_P[f]-E_Q[f]=1\not\le C\ep$$ for any real $$C$$ if $$\ep$$ is small enough. $$\quad\Box$$

• Many thanks. In this particular counter-example, $f$ is not monotonic. Would a monotonicity assumption help to establish the wanted bound? I'm thinking of the formula (in the univariate case): $E_P[f]=\int_0^{\infty} (1-G(x)) dx$, where $G(x)$ is the CDF of $f$, that is $G(x)=P(\{x':f(x')\leq x\})$. If $f$ is nondecreasing, it seems to me that $G(x)=F_P(h(x))$, for some function $h$ depending only on $f$. Then $E_P[f]-E_Q[f]=\int_0^{M} F_Q(h(x))-F_P(h(x)) dx$... Sep 29 at 16:27
• @Michele : Yes, in one dimension the monotonicity of $f$ will be enough. In higher dimensions, a more complicated condition would be needed, something like $f$ being the joint cdf of a finite measure. However, these additional questions should be posted separately. For now, let us finalize the matter in hand. Sep 29 at 17:00
• Thanks, I have accepted your answer. I would be grateful for any additional help and/or references you could provide on the multivariate case. Sep 29 at 21:15

You probably can’t get the sort of bound you want, take any continuous cdf on R, and approximate it stepwise as closely as you like. The stepwise approximation puts mass only at the steps. Take a function that is 1 except in tiny intervals around the steps. The continuous cdf will hardly care and will integrate to almost 1, but the integral against the stepwise approximation is 0.

• Yet, in the case $n=1$, one could use the formula $E[f]=\int (1-G(x)) dx$, where $G(x)=P(\{x':f(x')\leq x\})$, and the fact that $f$ is bounded to some avail. Sep 29 at 11:41