# Auxiliary randomization and the generalized CDF inverse

I'm trying to solve Homework 4 from professor Ryan Tibshirani's class on "Advanced Topics in Statistical Learning" [pdf] at UC Berkeley. It deals with basic facts about CDFs and quantiles.

My question is regarding Exercise 1(f) where the author mentions an auxiliary randomization method which extends the well known result of random variable generation via the inverse CDF to cases where it might fail (I suppose non-continuous pdfs?)

I'll rewrite the method here below: Let $$X$$ be distributed according to $$F$$. Define, $$F^\star(x; v) = \lim_{y \to x^{-}} F(y) + v \cdot \Big(F(x) - \lim_{y \to x^{-}} F(y)\Big)$$ where $$y \to x^-$$ means that $$y$$ approaches $$x$$ from the left.

It is possible to show that for $$V \sim U(0, 1)$$, independent of $$X$$, and for any $$t$$, we have $$\mathbb{P}(F^\star(X; V) \leq t) = t$$

Question: Does anyone know of a reference (article? standard book?) where I can read more about this result? I admit that I'm having some trouble to understand the intuition and motivation for creating the auxiliary variable $$v$$ here. Any help would be greatly appreciated!

• The statement "$y \to x^+$ means that $y$ approaches $x$ from the left" is unconventional -- most of the time it means $y$ approaches $x$ from the right. Apr 30 at 20:13
• Thanks @Zhanxiong! I've corrected the statement. It seems to be a typo in the original homework that I cited in my question. Apr 30 at 21:53
• You should correct $x^+$ to $x^-$ instead of correcting "left" to "right", as your linked pdf document does. Apr 30 at 22:10

As I commented under you post, I will use "$$f(x-)$$" instead of "$$f(x+)$$" for the left limit of a function $$f$$ in the proof below.

#### Preparations

The key of the proof is a property of the quantile function of a random variable $$X$$. In general, if $$X$$ is a random variable with distribution function $$F$$, we can define its quantile function (see, e.g., Equation (14.5) in Probability and Measure by Patrick Billingsley) of $$X$$ as \begin{align} \varphi(u) = \inf[x: F(x) \geq u], \quad 0 < u < 1. \end{align} For fixed $$u \in (0, 1)$$, we will need the following property of $$\varphi$$ (the proof of it can also be found in the reference mentioned above):
\begin{align} & x \geq \varphi(u) \iff F(x) \geq u, \tag{1} \\ & x < \varphi(u) \iff F(x) < u. \tag{2} \end{align}

As a rigorous proof, some properties of measure-theoretic integral will also be used tacitly. If you have questions, please comment below the answer.

#### Proof

Denote $$F^\star(X; V) = F(X-) + V(F(X) - F(X-))$$ by $$U$$, to show $$U \sim U(0, 1)$$, it suffices to show for any $$u \in (0, 1)$$, it holds that $$P[U < u] = u$$.

To this end, let's denote the set of discontinuities of $$F$$ by $$J$$, it then follows by the independence between $$X$$ and $$V$$ and $$(2)$$ that \begin{align} & P[U < u] = P[U < u, X \in J] + P[U < u, X \in J^c] \\ =& P[F(X-) + V(F(X) - F(X-)) < u, X \in J] + P[F(X) < u, X \in J^c] \\ =& \int_J P\left[V < \frac{u - F(x-)}{F(x) - F(x-)}\right]dF(x) + P[X < \varphi(u), X \in J^c] \\ =& \int_J P\left[V < \frac{u - F(x-)}{F(x) - F(x-)}\right]dF(x) + \int_{J^c \cap (-\infty, \varphi(u))} dF(x). \tag{3} \end{align}

Let's analyze the integrand of the first term in the right-hand of $$(3)$$: If $$x \in (-\infty, \varphi(u)) \cap J$$, then $$F(x-) < F(x) < u$$ by the monotonicity of $$F$$ and $$(2)$$, whence $$\frac{u - F(x-)}{F(x) - F(x-)} > 1$$ and it then follows by $$V \sim U(0, 1)$$ that $$P\left[V < \frac{u - F(x-)}{F(x) - F(x-)}\right] = 1$$; if $$x \in (\varphi(u), +\infty) \cap J$$, then for every $$t \in (\varphi(u), x)$$, by $$(1)$$ we have $$F(t) \geq F(\varphi(u)) \geq u$$, hence $$F(x-) = \lim_{t \to x^-}F(t) \geq u$$, whence $$\frac{u - F(x-)}{F(x) - F(x-)} \leq 0$$ and it then follows by $$V \sim U(0, 1)$$ that $$P\left[V < \frac{u - F(x-)}{F(x) - F(x-)}\right] = 0$$. This implies that (decompose $$J$$ into $$J = [J \cap (-\infty, \varphi(u))] \cup [J \cap \{\varphi(u)\}] \cup [J \cap (\varphi(u), +\infty)]$$): \begin{align} & \int_J P\left[V < \frac{u - F(x-)}{F(x) - F(x-)}\right]dF(x) \\ =& \int_{J \cap (-\infty, \varphi(u))} dF(x) + \int_{J \cap \{\varphi(u)\}} P\left[V < \frac{u - F(x-)}{F(x) - F(x-)}\right]dF(x). \tag{4} \end{align}

$$(3)$$ and $$(4)$$ together then give \begin{align} P[U < u] = \int_{(-\infty, \varphi(u))} dF(x) + \int_{J \cap \{\varphi(u)\}} P\left[V < \frac{u - F(x-)}{F(x) - F(x-)}\right]dF(x). \tag{5} \end{align}

To simplify $$(5)$$, consider the following two cases:

Case 1: $$\varphi(u) \in J^c$$, i.e., $$F$$ is continuous at $$\varphi(u)$$. In this case the second term in the right-hand side of $$(5)$$ vanishes, and $$F(\varphi(u)) = F(\varphi(u)-)$$. $$(5)$$ thus reduces to \begin{align} P[U < u] = \int_{(-\infty, \varphi(u))} dF(x) = P[X < \varphi(u)] = F(\varphi(u)-) = F(\varphi(u)) = u. \end{align}

Case 2: $$\varphi(u) \in J$$, i.e., $$F$$ jumps at $$\varphi(u)$$. In this case the second term in the right-hand side of $$(5)$$ becomes \begin{align} & \int_{\{\varphi(u)\}}P\left[V < \frac{u - F(x-)}{F(x) - F(x-)}\right]dF(x) \\ =& P\left[V < \frac{u - F(\varphi(u)-)}{F(\varphi(u)) -F(\varphi(u)-)}\right] \times (F(\varphi(u)) -F(\varphi(u)-)) \\ =& u - F(\varphi(u)-). \end{align} Therefore $$(5)$$ reduces to \begin{align} P[U < u] = P[X < \varphi(u)] + u - F(\varphi(u)-) = F(\varphi(u)-) + u - F(\varphi(u)-) = u. \end{align}

This completes the proof.

• Thanks! I'm having trouble to see how you arrive at Equation (4). While I do understand the paragraph that precedes the equation, I don't see how you end up with that first integral on the RHS of (4). Also, is it correct to say that you split the space of X into three parts (x < phi(u), x = phi(u), and x > phi(u)) and that the integral on x > phi(u) is always zero? Finally, do we always have that F(x-) = F(x)? or is this something specially from the properties of the problem? May 1 at 8:39
• @PedroRodrigues For the first two questions, I elaborated the paragraph preceding Eq (4). For the last question, of course we do NOT always have $F(x-) = F(x)$ ($F(x) > F(x-)$ corresponds to the case $x \in J$ in the answer) -- this is actually the full point of this exercise, i.e., how to simulate random numbers from an $F$ that may have jump points. To gain a good understanding of it, I suggested you completing every sub-question in that pdf sequentially before jumping into this last bonus one. May 1 at 12:31