I was reading Robert Serfling's 1980 book "Approximation Theorems of Mathematical Statistics" and came across the following construction of the Dvoretzky–Kiefer–Wolfowitz inequality for arbitrary distributions $F$, which DKW prove for distributions on $[0,1]$.
Given independent $X_i$ with d.f. F and defined on a common probability space, one can construct independent uniform $[0,1]$ variates $Y_i$ such that $\mathbf{P}[X_i = F^{-1}(Y_i)] =1,\forall i$.
Why? Is this true for arbitrary distributions (including discontinuous ones)?
Secondly,
Let $G$ denote the uniform $[0,1]$ distribution and $G_n$ the sample distribution function of the $Y_i$s. Then $F(x)=G(F(x))$ and with probability $1$, $F_n(x) = G_n(F(x))$.
Why?
Now I don't understand quantile functions as well I would like, and so am having some trouble following these arguments.
Edit: All of this is on page 59 of the book.
whuber, thank you so much for your careful answer. It is appreciated. The answer to my question does indeed lie in the last paragraph of your reply – now if I could only wrap my head around it.
What is throwing me off is the following example which I have recreated from Galen Shorack's "Probability for Statisticians" (page 111). Here, the Lebesgue measure of the set $[X\neq F^{-1}Y]$ is not zero. Would you agree? I am referring to the points in the interval $(2,3)$ and in $(3,3.5)$ for which the inverse transformation does not bring any points back.
Thank you again for looking into this.
\documentclass[a4paper]{article}
% Graphics
\usepackage{graphics}
\usepackage{graphicx}
\usepackage{pstricks}
\usepackage{pst-plot}
\usepackage{pstricks-add}
\usepackage{epstopdf}
\begin{document}
% An arbitrary CDF
\begin{figure}[htbp]
\begin{center}
\begin{psgraph}[arrows=<->](0,0)(-1.5,-.3)(6,1.2){.5\textwidth}{2.5cm}
\psplot[algebraic, linecolor=black]{-1}{1}{.025*x^2+.1*x+.175} % {this goes from .1 --> .3}
\psplot[algebraic, linecolor=black]{1}{2}{-.1*x^2+.4*x+.1} % {this goes form .4 --> .5}
\psline[linecolor=black](2,.5)(3,.5) % this stays at .5
\psline[linecolor=black](3,.6)(3.5,.6) % this stays at .6
\psplot[algebraic, linecolor=black]{3.5}{5}{ -0.1333*(x-5)^2+.9} % this goes from .6 --> .9
\psdots[dotstyle=*](3,.6)(1,0.4)
\end{psgraph}
\end{center}
\caption{Arbitrary CDF with discontinuities and flat sections}
\label{fig:cdf}
\end{figure}
% The quantile function
\begin{figure}[htbp]
\begin{center}
\begin{psgraph}[arrows=<->](0,0)(-.3, -1.5)(1.2, 6){2cm}{5cm}
% inverses using the Matlab finverse symbolic toolbox function
\psplot[algebraic, linecolor=black]{.1}{.3}{20*(x/10 - 3/400)^(1/2) - 2}
\psline[linecolor=black](.3, 1)(.4, 1)
\psplot[algebraic, linecolor=black]{.4}{.5}{-((x-0.5)/(-0.1))^(0.5)+2}
\psline[linecolor=black](.5, 3)(.6, 3)
\psplot[algebraic, linecolor=black]{.6}{.9}{-((x-.9)/(-0.1333))^(0.5)+5}
\psdots[dotstyle=*](.6, 3)(.5, 2)
\end{psgraph}
\end{center}
\caption{Quantile function of CDF in figure (\protect \ref{fig:cdf})}
\label{fig:qf}
\end{figure}
\end{document}
PS. I could not use the comment box for the reply as I needed to use the environment.<code>
Best Answer
It’s much easier to simultaneously construct $X_i$ and $Y_i$ having the desired properties, by first letting $Y_i$ be i.i.d. Uniform$[0,1]$ and then taking $X_i = F^{-1}(Y_i)$. This is the basic method for generating random variables with arbitrary distributions. The other direction, where you are first given $X_i$ and then asked to construct $Y_i$, is more difficult, but is still possible for all distributions. You just have to be careful with how you define $Y_i$.
Attempting to define $Y_i$ as $Y_i = F(X_i)$ fails to produce uniformly distributed $Y_i$ when $F$ has jump discontinuities. You have to spread the point masses in the distribution of $X_i$ across the the gaps created by the jumps.
Let $$D = \{x : F(x) \neq \lim_{z \to x^-} F(z)\}$$ denote the set of jump discontinuities of $F$. ($\lim_{z\to x^-}$ denotes the limit from the left. All distributions functions are right continuous, so the main issue is left discontinuities.)
Let $U_i$ be i.i.d. Uniform$[0,1]$ random variables, and define $$Y_i = \begin{cases} F(X_i), & \text{if }X_i \notin D \\ U_i F(X_i) + (1-U_i) \lim_{z \to X_i^-} F(z), & \text{otherwise.} \end{cases} $$ The second part of the definition fills in the gaps uniformly.
The quantile function $F^{-1}$ is not a genuine inverse when $F$ is not 1-to-1. Note that if $X_i \in D$ then $F^{-1}(Y_i) = X_i$, because the pre-image of the gap is the corresponding point of discontinuity. For the continuous parts where $X_i \notin D$, the flat sections of $F$ correspond to intervals where $X_i$ has 0 probability so they don’t really matter when considering $F^{-1}(Y_i)$.
The second part of your question follows from similar reasoning after the first part which asserts that $X_i = F^{-1}(Y_i)$ with probability 1. The empirical CDFs are defined as
$$G_n(y) = \frac{1}{n} \sum_{i=1}^n 1_{\{Y_i \leq y\}}$$ $$F_n(x) = \frac{1}{n} \sum_{i=1}^n 1_{\{X_i \leq x\}}$$
so
$$ \begin{align} G_n(F(x)) &= \frac{1}{n} \sum_{i=1}^n 1_{\{Y_i \leq F(x) \}} = \frac{1}{n} \sum_{i=1}^n 1_{\{F^{-1}(Y_i) \leq x \}} = \frac{1}{n} \sum_{i=1}^n 1_{\{X_i \leq x \}} = F_n(x) \end{align} $$ with probability 1.
It should be easy to convince yourself that $Y_i$ has Uniform$[0,1]$ distribution by looking at pictures. Doing so rigorously is tedious, but can be done. We have to verify that $P(Y_i \leq u) = u$ for all $u \in (0,1)$. Fix such $u$ and let $x^* = \inf\{x : F(x) \geq u \}$ — this is just the value of quantile function at $u$. It’s defined this way to deal with flat sections. We’ll consider two separate cases.
First suppose that $F(x^*) = u$. Then $$ Y_i \leq u \iff Y_i \leq F(x^*) \iff F(X_i) \leq F(x^*). $$ Since $F$ is a non-decreasing function and $F(x^*) = u$, $$ F(X_i) \leq F(x^*) \iff X_i \leq x^* . $$ Thus, $$ P[Y_i \leq u] = P[X_i \leq x^*] = F(x^*) = u . $$
Now suppose that $F(x^*) \neq u$. Then necessarily $F(x^*) > u$, and $u$ falls inside one of the gaps. Moreover, $x^* \in D$, because otherwise $F(x^*) = u$ and we have a contradiction. Let $u^* = F(x^*)$ be the upper part of the gap. Then by the previous case, $$ \begin{align} P[Y_i \leq u] &= P[Y_i \leq u^*] - P[u < Y_i \leq u^*]\\ &= u^* - P[u < Y_i \leq u^*]. \end{align} $$ By the way $Y_i$ is defined, $P(Y_i = u^*) = 0$ and $$ \begin{align} P[u < Y_i \leq u^*] &= P[u < Y_i < u^*] \\ &= P[u < Y_i < u^* , X_i = x^*] \\ &= u^* - u . \end{align} $$ Thus, $P[Y_i \leq u] = u$.