ArticleslgStudy

mathematics

Inverse transform sampling

Inverse transform sampling is a mathematics topic covered in the lgStudy science library. This page brings together a partial reference excerpt, illustrations, worked examples, real-world applications and a short study plan, so you can understand Inverse transform sampling rather than just read about it. In short: Inverse transform sampling (also known as inversion sampling, the inverse probability integral transform, the inverse transformation method, or the Smirnov transform) is a basic method for pseudo-random number sampling, i.e., for generating sample numbers at random from any probability distribution given its cumulative distribution function. Inverse transformation sampling takes uniform samples of a number u {\displ…

Inverse transform sampling — main illustration
Inverse transform sampling — illustration

Key takeaways

  • Inverse transform sampling belongs to mathematics; place it in that map before memorising details.
  • Learn the definition first, then one example that makes the definition concrete.
  • Connect Inverse transform sampling to a quantity you can measure, compute or draw — that is where exam questions come from.
  • Reproduce the core statement of Inverse transform sampling from memory before moving on to harder problems.

Reference excerpt

Inverse transform sampling (also known as inversion sampling, the inverse probability integral transform, the inverse transformation method, or the Smirnov transform) is a basic method for pseudo-random number sampling, i.e., for generating sample numbers at random from any probability distribution given its cumulative distribution function. Inverse transformation sampling takes uniform samples of a number u {\displaystyle u} between 0 and 1, interpreted as a probability, and then returns the smallest number x ∈ R {\displaystyle x\in \mathbb {R} } such that F ( x ) ≥ u {\displaystyle F(x)\geq u} for the cumulative distribution function F {\displaystyle F} of a random variable. For example, imagine that F {\displaystyle F} is the standard normal distribution with mean zero and standard deviation one. The table below shows samples taken from the uniform distribution and their representation on the standard normal distribution.

We are randomly choosing a proportion of the area under the curve and returning the number in the domain such that exactly this proportion of the area occurs to the left of that number. Intuitively, we are unlikely to choose a number in the far end of tails because there is very little area in them which would require choosing a number very close to zero or one. Computationally, this method involves computing the quantile function of the distribution — in other words, computing the cumulative distribution function (CDF) of the distribution (which maps a number in the domain to a probability between 0 and 1) and then inverting that function. This is the source of the term "inverse" or "inversion" in most of the names for this method. Note that for a discrete distribution, computing the CDF is not in general too difficult: we simply add up the individual probabilities for the various points of the distribution. For a continuous distribution, however, we need to integrate the probability density function (PDF) of the distribution, which is impossible to do analytically for most distributions (including the normal distribution). As a result, this method may be computationally inefficient for many distributions and other methods are preferred; however, it is a useful method for building more generally applicable samplers such as those based on rejection sampling. For the normal distribution, the lack of an analytical expression for the corresponding quantile function means that other methods (e.g. the Box–Muller transform) may be preferred computationally. It is often the case that, even for simple distributions, the inverse transform sampling method can be improved on: see, for example, the ziggurat algorithm and rejection sampling. On the other hand, it is possible to approximate the quantile function of the normal distribution extremely accurately using moderate-degree polynomials, and in fact the method of doing this is fast enough that inversion sampling is now the default method for sampling from a normal distribution in the statistical package R.

Formal statement For any random variable X {\displaystyle X} on R {\displaystyle \mathbb {R} } , the random variable F X − 1 ( U ) {\displaystyle F_{X}^{-1}(U)} has the same distribution as X {\displaystyle X} , where F X − 1 {\displaystyle F_{X}^{-1}} is the generalized inverse of the cumulative distribution function F X {\displaystyle F_{X}} of X {\displaystyle X} and U {\displaystyle U} is uniform on [ 0 , 1 ] {\displaystyle [0,1]} . For continuous random variables, the inverse probability integral transform is indeed the inverse of the probability integral transform, which states that for a continuous random variable X {\displaystyle X} with cumulative distribution function F X {\displaystyle F_{X}} , the random variable U = F X ( X ) {\displaystyle U=F_{X}(X)} is uniform on [ 0 , 1 ] {\displaystyle [0,1]} .

Intuition From U ∼ U n i f [ 0 , 1 ] {\displaystyle U\sim \mathrm {Unif} [0,1]} , we want to generate X {\displaystyle X} with CDF F X ( x ) . {\displaystyle F_{X}(x).} We assume F X ( x ) {\displaystyle F_{X}(x)} to be a continuous, strictly increasing function, which provides good intuition. We want to see if we can find some strictly monotone transformation T : [ 0 , 1 ] ↦ R {\displaystyle T:[0,1]\mapsto \mathbb {R} } , such that T ( U ) = d X {\displaystyle T(U){\overset {d}{=}}X} . We will have

… excerpt ends here. Continue reading the full article.

Illustrations

Inverse transform sampling: Inverse transform sampling for normal distribution
Inverse transform sampling for normal distribution
Inverse transform sampling: Graph of the inversion technique from x {\displaystyle x} to F ( x ) {\displaystyle F(x)} . On the bottom right we see the regular function and in the top left its inversion.
Graph of the inversion technique from x {\displaystyle x} to F ( x ) {\displaystyle F(x)} . On the bottom right we see the regular function and in the top left its inversion.
Inverse transform sampling: Schematic of the inverse transform sampling. The inverse function of y = F X ( x ) {\displaystyle y=F_{X}(x)} can be defined by F X − 1 ( y ) = i n f { x | F X ( x ) ≥ y } {\displaystyle F_{X}^{-1}(y)=\mathrm {inf} \{x|F_{X}(x)\geq y\}} .
Schematic of the inverse transform sampling. The inverse function of y = F X ( x ) {\displaystyle y=F_{X}(x)} can be defined by F X − 1 ( y ) = i n f { x | F X ( x ) ≥ y } {\displaystyle F_{X}^{-1}(y)=\mathrm {inf} \{x|F_{X}(x)\geq y\}} .
Inverse transform sampling: An animation of how inverse transform sampling generates normally distributed random values from uniformly distributed random values
An animation of how inverse transform sampling generates normally distributed random values from uniformly distributed random values
Inverse transform sampling: Random numbers yi are generated from a uniform distribution between 0 and 1, i.e. Y ~ U(0, 1). They are sketched as colored points on the y-axis. Each of the points is mapped according to x=F−1(y), which is shown with gray arrows for two example points. In this example, we have used an exponential distribution. Hence, for x ≥ 0, the probability density is ϱ X ( x ) = λ e − λ x {\displaystyle \varrho _{X}(x)=\lambda e^{-\lambda \,x}} and the cumulative distribution function is F ( x ) = 1 − e − λ x {\displaystyle F(x)=1-e^{-\lambda \,x}} . Therefore, x = F − 1 ( y ) = − ln ⁡ ( 1 − y ) λ {\displaystyle x=F^{-1}(y)=-{\frac {\ln(1-y)}{\lambda }}} . We can see that using this method, many points end up close to 0 and only few points end up having high x-values - just as it is expected for an exponential distribution.
Random numbers yi are generated from a uniform distribution between 0 and 1, i.e. Y ~ U(0, 1). They are sketched as colored points on the y-axis. Each of the points is mapped according to x=F−1(y), which is shown with gray arrows for two example points. In this example, we have used an exponential distribution. Hence, for x ≥ 0, the probability density is ϱ X ( x ) = λ e − λ x {\displaystyle \varrho _{X}(x)=\lambda e^{-\lambda \,x}} and the cumulative distribution function is F ( x ) = 1 − e − λ x {\displaystyle F(x)=1-e^{-\lambda \,x}} . Therefore, x = F − 1 ( y ) = − ln ⁡ ( 1 − y ) λ {\displaystyle x=F^{-1}(y)=-{\frac {\ln(1-y)}{\lambda }}} . We can see that using this method, many points end up close to 0 and only few points end up having high x-values - just as it is expected for an exponential distribution.

Worked examples

Example 1 — a first encounter with Inverse transform sampling

Start with the simplest possible case. Write down what Inverse transform sampling claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In mathematics, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to Inverse transform sampling before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about Inverse transform sampling ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of Inverse transform sampling

In research
Inverse transform sampling appears in mathematics research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry
Engineering practice reuses Inverse transform sampling in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom
Inverse transform sampling is common in secondary-school and first-year university syllabi. It links to neighbouring topics Monte Carlo methods, Non-uniform random numbers, so understanding it makes those chapters shorter.
In everyday life
Look for Inverse transform sampling outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

Affiliate

Preply — study more efficiently by working with a personal tutor. 50% off.

How to study Inverse transform sampling in 20 minutes

  1. Read the reference excerpt below once, without taking notes.
  2. Close the page and write down what Inverse transform sampling means in your own words.
  3. Compare your version with the excerpt and mark what you missed.
  4. Work through the three examples above with pen and paper.
  5. Explain Inverse transform sampling out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is Inverse transform sampling in simple terms?

Inverse transform sampling (also known as inversion sampling, the inverse probability integral transform, the inverse transformation method, or the Smirnov transform) is a basic method for pseudo-random number sampling, i.e., for generating sample numbers at random from any probability distribution…

Why does Inverse transform sampling matter?

Because it connects several mathematics ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study Inverse transform sampling?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on Inverse transform sampling.

Tags

  • Monte Carlo methods
  • Non-uniform random numbers

Keep exploring