A common source of randomness
A simulation often starts with a uniform number between zero and one, yet the desired outcome may have a skewed, discrete, or mixed distribution. How can one uniform source produce all of these? The answer is to read probability mass from left to right. A cumulative distribution function (CDF) tells us how much mass has been accumulated by each location; a quantile tells us where a given fraction of mass is first reached.
Let be a CDF. It is nondecreasing and right-continuous, with limits and . It may jump or be constant over intervals, so an ordinary inverse need not exist.
Definition 29.1.1
(Generalized quantile)
For , the generalized quantile of a CDF is
The set is nonempty and bounded below for each such , by the two limits of , so is a real number. The choice at or is irrelevant when the input is uniform on ; we need not assign finite values there.
Theorem 29.1.2
(The inverse-transform construction)
If is uniform on and is the generalized quantile of a CDF , then has CDF . In particular this holds whether is continuous, discrete, or mixed.
Proof
(An event identity for the quantile)
We show that for every real and ,
If , then belongs to the set defining , so its infimum satisfies . Conversely, the defining set is an interval unbounded to the right, because is nondecreasing. Take points of the set with (or if is already in the set). Then , and right-continuity gives . If , monotonicity now yields .
Since is uniform on , the identity gives, for every real ,
including the cases and . Thus has CDF .
Proof X-ray
Where right-continuity and the infimum enter
The whole proof is the event identity; after it, the uniform law converts into the number in one line. The identity has an easy half and a delicate half. The easy half, , uses only the definition of an infimum. The delicate half needs , that is, the infimum is attained, and this is the one place where right-continuity is used.
The choice of “” together with “” matters. With a left-continuous version of , the attained-infimum step could fail at an atom, and the identity would break exactly at the jumps that make discrete laws possible. Nothing in the argument assumes continuity or strict increase of ; this is why one construction covers discrete, continuous and mixed laws.
Three quantile computations
Worked example 29.1.3
(A discrete law)
Suppose , and . The CDF jumps at , so
The lengths of the three intervals are precisely . Thus has the required law. Changing the value assigned at either breakpoint does not alter that law for a continuous uniform input, but the displayed endpoint convention follows from the definition of .
Worked example 29.1.4
(An exponential law)
Let and for , with for . For , the inequality fails for and, for , is equivalent to , that is, . Hence
Solving the equation gives the same answer here, because is continuous and strictly increasing on . As a check, for .
Worked example 29.1.5
(A mixed law with an atom at the left end)
Let equal with probability and otherwise be uniform on , so for , for , and for . If , then while for , so . If , then exactly when , so .
The edge case is the atom. The whole interval of inputs is sent to the single value , giving , and on the map spreads the remaining mass uniformly over . Here the equation has no solution for , but is still defined.
Transforming in the other direction
Theorem 29.1.6
(Probability integral transform)
If is continuous on and has CDF , then is uniform on . Strict increase is not required.
Proof
(Use the right end of a level set)
Fix and put . The limits of make this set nonempty and bounded above, so is finite. Points of the set approach from the left, so continuity gives ; points to the right of have , so continuity gives . Hence . For one has , while implies . Therefore
Since takes values in and this holds for every , is uniform on .
Proof X-ray
Why flat pieces are harmless but jumps are not
The key move is to choose as the right end of the level set rather than to solve . If is flat on an interval at height , the equation has many solutions; taking the supremum picks one point for which , and the flat interval carries no probability anyway.
Continuity is used twice, to obtain both and . If jumped across at , then could hold while , and the computation would return instead of . No step uses strict increase, which is why the statement does not assume it.
The continuity assumption matters. If has an atom at , then equals with probability at least , whereas a uniform variable has no atoms. An ordinary application of cannot split an atom into a continuous interval of values.
Counterexample mode
A fair coin is not made uniform by its CDF
Let . Then takes the values and , each with probability . In particular , not . The inverse construction is valid for this same discontinuous CDF; the reverse assertion needs continuity.
Filling the jumps with independent randomness
There is a useful repair. Write for the left limit, so that is the jump at .
Theorem 29.1.7
(Randomized probability integral transform)
Let have CDF , and let be independent of and uniform on . Then
is uniform on , whatever the type of .
Proof
(Split according to the position of relative to a quantile)
Fix and put . The event identity gives , and every has , so . Split the event according to .
If , then , so this case contributes .
If , then . At a point with a positive jump, gives . At a point without a jump, forces , so lies in an interval to the right of on which is constant, and such an interval has probability zero. This case contributes .
If and the jump is positive, independence of gives
since the ratio lies in . If , then and , so the contribution is the same. Adding the three cases gives .
At an atom , the formula spreads its probability mass uniformly over the jump interval ; where there is no jump, .
Common mistakes
Common mistake
(Solving for a law with atoms)
For the discrete law with atoms at , the equation has no solution: jumps from to at . Inverse-transform sampling does not require a solution. The generalized quantile gives , the first point at which the accumulated mass reaches .
Common mistake
(Treating a quantile as the unique point with that mass)
For a fair coin on , every satisfies and , so every such is a median. The generalized quantile does not resolve this by finding the true median; it makes a definite choice, , the smallest point at which the CDF reaches .
Exercises
Quick check
(A variable has , and . Find its generalized quantile and use it to calculate .)
List the values of at the three atoms.
Solution · Answer
, and . Hence for , for , and for . The event is , with probability .
Quick check
(Let for , for , and for . Find and for uniform .)
On the CDF is continuous and strictly increasing.
Solution · Answer
For , with means , so . Hence , which agrees with .
Quick check
(For a Bernoulli variable with , where , find the distribution of . Explain why it is not uniform.)
Evaluate at the two possible values.
Solution · Answer
and . Therefore equals with probability and with probability . Its atoms preclude a continuous uniform law.
Quick check
(In the Bernoulli case, let be an independent uniform variable. Express the randomized transform separately on and , and check for .)
Find and first.
Solution · Answer
Since and : if , then ; if , then . For , only contributes, and . For , the probability is . The two conditional uniform intervals exactly fill .