Kolmogorov-Smirnov distance and expectation

Question

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

Answer 1

$\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}<x<\frac{2j+1}{2n}\Big)$$ 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$

Answer 2

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.