Transforming arbitrary distributions to distributions on $[0,1]$

Question

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 <code> environment.

Answer 1

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

Answer 2

This is merely saying that $F(x) = \Pr[X \le x] = \Pr[F(X) \le F(x)]$ which is exactly what it means for $F(X)$ to have a uniform distribution.

OK, let's go a little slower.

For continuous distributions, forget for a moment that the CDF $F$ is a CDF and think of it as just a nonlinear way to re-express the values of $X$. In fact, to make the distinction clear, suppose that $G$ is any monotonically increasing way of re-expressing $X$. Let $Y$ be the name of its re-expressed value. $G^{-1}$, by definition, is the "back transform": it expresses $Y$ back in terms of the original $X$.

What is the distribution of $Y$? As always, we discover this by picking an arbitrary value that $Y$ might take on, say $y$, and ask for the chance that $Y$ is less than or equal to $y$. Back-transform this question in terms of the original way of expressing $X$: we are inquiring about the chance that $X$ is less than or equal to $x = G^{-1}(y)$. Now take $G$ to be $F$ and remember that $F$ is the CDF of $X$: by definition, the chance that $X$ is less than or equal to any $x$ is $F(x)$. In this case,

$$F(x) = F(G^{-1}(y)) = F(F^{-1}(y)) = y.$$

We have established that the CDF of $Y$ is $\Pr[Y \le y] = y$, the uniform distribution on $[0,1]$.

It can help to look at this graphically. Draw the graph of $F$. As $X$ ranges over the reals, $F$ ranges between $0$ and $1$. The function $F$ is constructed specifically so that the distribution of $F(x)$ is uniform. That is, if you want to pick a random value for $X$, pick a uniformly random value along the y-axis between $0$ and $1$ and find the value of $X$ where $F(X)$ equals that random height.

In the continuous case we have $X = F^{-1}(Y)$ so clearly $\Pr[X = F^{-1}(Y)] = 1$. In the discontinuous case there's no difficulty, either, provided we define $F^{-1}$ appropriately. But if there's a jump in $X$ from $x_0$ to $x_1 \gt x_0$, all we can say in general is that the event where $x_0 \le X \lt x_1$ has zero probability, not that it's impossible for $X$ to lie in this interval. For this reason we cannot assert that $X = F^{-1}(Y)$ everywhere, but we can assert that the event that this equality does not hold has probability zero, because it consists of at most a countable number of jumps.

(For a practical example of why this arcane technical distinction is important, consider a gambling problem. Suppose you will play Roulette repeatedly with a fixed bet until either you are broke or you double your money. Let $X$ be the random variable representing your net gain if you ever go broke or double your money. Otherwise, define $X$ to be any number you want. $X$ has a Bernoulli distribution because there is some chance $p$ you will go broke, the chance of doubling your money is $1-p$ (work it out!), and the chance of playing forever is zero. Nevertheless, playing forever is a possibility: it is part of the mathematical set of possible outcomes.)

As a simple exercise in learning to reason with the uniform probability transform, graph $F$ for a Bernoulli($p$) variable. The graph equals $0$ for all $x \lt 0$, jumps to $1-p$ at $0$, is horizontal again for $0 \lt x \lt 1$, then jumps to $1$ at $x=1$ and stays there for all greater $x$. A uniform variate on the interval $[0,1]$ on the y-axis will cover the initial jump with a probability $p$; $F^{-1}$ maps this down to $x = 0$. Otherwise, the variate covers the final jump with the remaining probability $1-p$ and $F^{-1}$ maps this down to $1$. We see, then, how a uniform distribution of $Y$ reproduces this simple discrete distribution function. Illustrations of CDFs of discrete and continuous/discrete distributions appear on this page I wrote for a stats course long ago.