7
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Re the edit: The Lebesgue measure of this set is irrelevant. You need to be looking at the probability that the CDF of a uniform distribution on Y does not agree with the CDF of X. This probability is still zero. Take a closer look at the Web page I referenced and think harder about the Bernoulli case: once you understand this (the simplest possible situation) all should be clear. (This comment was originally posted Dec 19 '10.) $\endgroup$ – whuber Oct 5 '13 at 15:09
6
$\begingroup$

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

$\endgroup$
  • $\begingroup$ "For the continuous parts where Xi∉D, the flat sections of F correspond to intervals where Xi has 0 probability so they don’t really matter when considering F−1(Yi)." That is it! That was a beautiful answer. Thank you. $\endgroup$ – blueberry Dec 17 '10 at 20:41
  • 1
    $\begingroup$ +1 for the rigor and for addressing the second question about the EDFs. $\endgroup$ – whuber Dec 19 '10 at 17:16
13
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.