13.1 Background and Probability Review

We will start by defining some terms and reviewing basic ideas from probability. We assume that the reader is already familiar with basic probability concepts; readers needing a more complete introduction to this topic should consult a textbook such as Sheldon Ross’s Introduction to Probability Models (2002).

A random variable upper X is a value chosen by some random process. We will generally use capital letters to denote random variables, with exceptions made for a few Greek symbols that represent special random variables. Random variables are always drawn from some domain, which can be either discrete (e.g., a fixed, finite set of possibilities) or continuous (e.g., the real numbers bold upper R Superscript ). Applying a function  f to a random variable  upper X results in a new random variable upper Y equals f left-parenthesis upper X right-parenthesis .

For example, the result of a roll of a die is a discrete random variable sampled from the set of events upper X Subscript i Baseline element-of StartSet 1 comma 2 comma 3 comma 4 comma 5 comma 6 EndSet . Each event has a probability p Subscript i Baseline equals one-sixth , and the sum of probabilities sigma-summation p Subscript i is necessarily one. We can take a continuous, uniformly distributed random variable xi Subscript Baseline element-of left-bracket 0 comma 1 right-parenthesis and map it to a discrete random variable, choosing upper X Subscript i if

sigma-summation Underscript j equals 1 Overscript i minus 1 Endscripts p Subscript j Baseline less-than-or-equal-to xi Subscript Baseline less-than sigma-summation Underscript j equals 1 Overscript i Endscripts p Subscript j Baseline period

For lighting applications, we might want to define the probability of sampling illumination from each light in the scene based on the power normal upper Phi Subscript i from each source relative to the total power from all sources:

p Subscript i Baseline equals StartFraction normal upper Phi Subscript i Baseline Over sigma-summation Underscript j Endscripts normal upper Phi Subscript j Baseline EndFraction period

Notice that these p Subscript i also sum to 1.

The cumulative distribution function (CDF) upper P left-parenthesis x right-parenthesis of a random variable is the probability that a value from the variable’s distribution is less than or equal to some value x :

upper P left-parenthesis x right-parenthesis equals upper P r left-brace upper X less-than-or-equal-to x right-brace period

For the die example, upper P left-parenthesis 2 right-parenthesis equals one-third , since two of the six possibilities are less than or equal to 2.

13.1.1 Continuous Random Variables

In rendering, discrete random variables are less common than continuous random variables, which take on values over ranges of continuous domains (e.g., the real numbers, directions on the unit sphere, or the surfaces of shapes in the scene).

A particularly important random variable is the canonical uniform random variable, which we will write as  xi Subscript . This variable takes on all values in its domain left-bracket 0 comma 1 right-parenthesis with equal probability. This particular variable is important for two reasons. First, it is easy to generate a variable with this distribution in software—most run-time libraries have a pseudo-random number generator that does just that. Second, as we will show later, it is possible to generate samples from arbitrary distributions by first starting with canonical uniform random variables and applying an appropriate transformation. The technique described previously for mapping from xi Subscript to the six faces of a die gives a flavor of this technique in the discrete case.

Another example of a continuous random variable is one that ranges over the real numbers between 0 and 2, where the probability of its taking on any particular value x is proportional to the value 2 minus x : it is twice as likely for this random variable to take on a value around 0 as it is to take one around 1, and so forth. The probability density function (PDF) formalizes this idea: it describes the relative probability of a random variable taking on a particular value. The PDF p left-parenthesis x right-parenthesis is the derivative of the random variable’s CDF,

p left-parenthesis x right-parenthesis equals StartFraction normal d upper P left-parenthesis x right-parenthesis Over normal d x EndFraction period

For uniform random variables, p left-parenthesis x right-parenthesis is a constant; this is a direct consequence of uniformity. For xi Subscript we have

p left-parenthesis x right-parenthesis equals StartLayout Enlarged left-brace 1st Row 1st Column 1 2nd Column x element-of left-bracket 0 comma 1 right-parenthesis 2nd Row 1st Column 0 2nd Column otherwise period EndLayout

PDFs are necessarily nonnegative and always integrate to 1 over their domains. Given an arbitrary interval left-bracket a comma b right-bracket in the domain, integrating the PDF gives the probability that a random variable lies inside the interval:

upper P left-parenthesis x element-of left-bracket a comma b right-bracket right-parenthesis equals integral Subscript a Superscript b Baseline p left-parenthesis x right-parenthesis normal d x period

This follows directly from the first fundamental theorem of calculus and the definition of the PDF.

13.1.2 Expected Values and Variance

The expected value upper E Subscript p Baseline left-bracket f left-parenthesis x right-parenthesis right-bracket of a function f is defined as the average value of the function over some distribution of values p left-parenthesis x right-parenthesis over its domain. In the next section, we will see how Monte Carlo integration computes the expected values of arbitrary integrals. The expected value over a domain, upper D , is defined as

upper E Subscript p Baseline left-bracket f left-parenthesis x right-parenthesis right-bracket equals integral Underscript upper D Endscripts f left-parenthesis x right-parenthesis p left-parenthesis x right-parenthesis normal d x period
(13.1)

As an example, consider the problem of finding the expected value of the cosine function between 0 and pi , where p is uniform. Because the PDF p left-parenthesis x right-parenthesis must integrate to 1 over the domain, p left-parenthesis x right-parenthesis equals 1 slash pi , so

upper E left-bracket cosine x right-bracket equals integral Subscript 0 Superscript pi Baseline StartFraction cosine x Over pi EndFraction normal d x equals StartFraction 1 Over pi EndFraction left-parenthesis sine pi minus sine 0 right-parenthesis equals 0 comma

which is precisely the expected result. (Consider the graph of cosine x over left-bracket 0 comma pi right-bracket to see why this is so.)

The variance of a function is the expected squared deviation of the function from its expected value. Variance is a fundamental concept for quantifying the error in a value estimated by a Monte Carlo algorithm. It provides a precise way to quantify this error and measure how improvements to Monte Carlo algorithms reduce the error in the final result. The variance of a function  f is defined as

upper V left-bracket f left-parenthesis x right-parenthesis right-bracket equals upper E left-bracket left-parenthesis f left-parenthesis x right-parenthesis minus upper E left-bracket f left-parenthesis x right-parenthesis right-bracket right-parenthesis squared right-bracket period

The expected value and variance have a few important properties that follow immediately from their respective definitions:

StartLayout 1st Row 1st Column upper E left-bracket a f left-parenthesis x right-parenthesis right-bracket 2nd Column equals a upper E left-bracket f left-parenthesis x right-parenthesis right-bracket 2nd Row 1st Column upper E left-bracket sigma-summation Underscript i Endscripts f left-parenthesis upper X Subscript i Baseline right-parenthesis right-bracket 2nd Column equals sigma-summation Underscript i Endscripts upper E left-bracket f left-parenthesis upper X Subscript i Baseline right-parenthesis right-bracket 3rd Row 1st Column upper V left-bracket a f left-parenthesis x right-parenthesis right-bracket 2nd Column equals a squared upper V left-bracket f left-parenthesis x right-parenthesis right-bracket period EndLayout

These properties, and some simple algebraic manipulation, yield an alternative expanded expression for the variance:

upper V left-bracket f left-parenthesis x right-parenthesis right-bracket equals upper E left-bracket left-parenthesis f left-parenthesis x right-parenthesis right-parenthesis squared right-bracket minus upper E left-bracket f left-parenthesis x right-parenthesis right-bracket squared period
(13.2)

Thus, the variance is the expected value of the square minus the square of the expected value. Given random variables that are independent, variance also has the property that the sum of the variances is equal to the variance of their sum:

sigma-summation Underscript i Endscripts upper V left-bracket f left-parenthesis upper X Subscript i Baseline right-parenthesis right-bracket equals upper V left-bracket sigma-summation Underscript i Endscripts f left-parenthesis upper X Subscript i Baseline right-parenthesis right-bracket period