Exercises 19 (Variance Reduction)

Variable Variance

The purpose of this quiz is to solidify your understanding of some elementary quantities, concepts, and terminology used in Monte Carlo rendering, to get a sense of how to code up basic Monte Carlo integration, to estimate variance (which can be useful for adaptive sampling...), and to empirically validate some of the claims made in lecture. Even though we "spoon feed" you tasks to implement in A4, a clear understanding of Monte Carlo is critical if you ever want to build a renderer (or more generally apply these concepts) beyond the scope of our class.

1. Discrete Data

Let's recall a few basic definitions by first considering a discrete random variable X. This variable can take three possible values, which will occur with three given probabilities P.

1. What is the expected value of X?
2. What is the variance of X?
3. What is the standard deviation of X?
4. Why might you use the standard deviation rather than the variance?

2. Continuing Continuously

Now let's consider the function f(x) = x^2 defined on the interval 0 <= x <= 1. We can use this function to define a random variable Y := f(X)?, where X? is a random variable uniformly distributed on the interval [0,1]?. For the next three questions, compute the exact answer by hand---not using Monte Carlo or other numerical integration techniques.

1. What is the expected value of Y?
2. What is the variance of Y?
3. What is the standard deviation of Y?

3. Estimating Expected Value

We will now numerically estimate statistics of the same continuous random variable Y from the previous problem?. Assume that each routine is given a number of samples N (which determines accuracy), and that you already have a subroutine unitRand() that returns independent uniformly distributed random values in the interval [0,1]. All routines should use Monte Carlo estimation (rather than other numerical quadrature). For each routine, the total number of calls to rand() should be linear in N. You should not use special knowledge of Y (such as the exact values computed earlier).

1. Implement a routine EY( N ) that estimates the expected value of Y.
2. Implement a routine VarY( N ) that numerically estimates the variance ?of Y. This estimator does not need to be unbiased, but it should at least be consistent.

4. Running the Estimators

Run your two routines EY(N) and VarY(N) with N = 4096 samples, and confirm that they produce values that are reasonably close to your closed-form values for the expected value and variance of Y.

5. Estimating Error in the Estimator

Write some code to estimate the variance in the estimates returned by EY(N) for N=2k samples, with k = 1,..., 12. In other words, as N increases what is the expected deviation of the estimate from the true expected value? calculated in question 2.1? For each value of N, confirm that the estimated variance is roughly equal to ?V[Y]/N, where ?V[Y] denotes the exact value of the variance calculated in question 2.2.

6. Plotting Error in the Estimator

Plot the estimated variance in our Monte Carlo estimator to check whether it agrees with the variance predicted for an N-sample Monte Carlo estimator. In particular, if F_N is an N-sample Monte Carlo estimator (for any quantity) the variance V[F_N] of the estimator should decrease like V[Y]/N, where V[Y] is the true (i.e., exact) variance of the random variable Y. Use a log-log plot in order to clearly indicate the convergence rate?.