Let $f$ be a probability density function.

Let $r(n)$ be random number generator that picks a random real number between $0$ and $1$.

I'm wondering how to find (if it's possible) a function $g$ such that when $g(r(n))$ is sampled for some $n$ the probability that $g(r(n)) = x$ for some $x \in \mathbb{R}$ is $f(x)dx$?

  • $\begingroup$ You use the quantile function, which is essentially the inverse of the cumulative distribution function (but it still makes sense even if the CDF is not bijective). This process can be called the quantile transformation. It also has another name that I have forgotten. $\endgroup$ – Ian Sep 15 '16 at 17:45
  • $\begingroup$ I found this: en.wikipedia.org/wiki/Inverse_transform_sampling probably what you're referring to $\endgroup$ – saldukoo Sep 15 '16 at 17:50

Consider the probability space $(\Omega, \mathcal{F}, P)$ and let $X: \Omega \mapsto \mathbb{R}$ be a real random variable from the probability space into $(\mathbb{R}, \mathcal{B})$, where $\mathcal{B}$ is the Borel sigma-algebra on $\mathbb{R}$. Assume that $X$ has density $f$ wrt. the Lebesgue-measure. Let us for simplicity assume that $f$ is strictly positive on some interval $(a,b)$ where $a,b\in[-\infty,\infty]$, e.g. $\mathbb{R}_+$, and else zero.

Define the distribution function of $X$ called $F: (a,b) \mapsto (0,1)$ by

$F(x):=P(X\leq x)=\int_a^x f(x) \, \mathrm{d}x$.

Clearly $F$ is stricly increasing and continuous, thus there exists an inverse $F^{-1}:(0,1) \mapsto (a,b)$ which is also strictly increasing and continuous. For a proof of a similar statement see here: If f is continuous and strictly increasing, then the function $f^{-1}:f(I)\rightarrow I$ is continuous and strictly increasing.

Recall that $F(F^{-1}(x))=x$ for all $x\in(0,1)$.

$X$ is only almost surely in the interval $(a,b)$, but we can find a version* of $X$ denoted $X'$ which always takes values in the interval $(a,b)$. Note that $U:=F(X')$ then takes values in $(0,1)$, and for $u\in(0,1)$,

$P(U\leq u)=P(X' \leq F^{-1}(u))=F(F^{-1}(u))=u$,

such that $U$ is uniformly distributed on $(0,1)$ or "$U$ is a random number generator that picks a random real number between $0$ and $1$".

This shows, that there is a correspondence between the real random variable $X'$ and a uniform random variable $U$ through the distribution function $F$.

If we instead have given $U$ uniform on $(0,1)$ we can find a version of $U$ denoted $U'$ which always takes values in $(0,1)$. Then with $Y=F^{-1}(U')$, we have that $Y$ takes values in $(a,b)$, and for $y \in (a,b)$,

$P(Y\leq y) = P(U \leq F(y)) = F(y)$,

such that $X$ and $Y$ have the same distribution function.

All in all: We can sample from $X$ by sampling from $U$ and transforming the result with the quantile function of $X$, that is $F^{-1}$. Thus an algorithm is:

  1. Sample from $U$ uniform on $(0,1)$ and obtain $u\in(0,1)$.
  2. Set $x=F^{-1}(u)$.
  3. $x$ is now a sample from $X$.

A final comment: The approach is based on the evaluation of $F^{-1}(u)$ for $u\in(0,1)$. In practice there might not exists a closed expression for the quantile function $F^{-1}$, which complicates matters. That is for example the case for the normal distribution.

*If $Z'$ is a version of $Z$ they especially have the same distribution.


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.