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 Xi with d.f. F and defined on a common probability space, one can construct independent uniform [0,1] variates Yi such that P[Xi=F−1(Yi)]=1,∀i.

Why? Is this true for arbitrary distributions (including discontinuous ones)?

Secondly,

Let G denote the uniform [0,1] distribution and Gn the sample distribution function of the Yis. Then F(x)=G(F(x)) and with probability 1, Fn(x)=Gn(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≠F−1Y] 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`

>

**Answer**

It’s much easier to simultaneously construct Xi and Yi having the desired properties,

by first letting Yi be i.i.d. Uniform[0,1] and then taking Xi=F−1(Yi). This is the basic method for generating random variables with arbitrary distributions.

The other direction, where you are first given Xi and then asked to construct Yi, is more difficult, but is still possible for all distributions. You just have to be careful with how you define Yi.

Attempting to define Yi as Yi=F(Xi) fails to produce uniformly distributed Yi when F has jump discontinuities. You have to spread the point masses in the distribution of Xi across the the gaps created by the jumps.

Let D={x:F(x)≠lim 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.

**Attribution***Source : Link , Question Author : blueberry , Answer Author : vqv*