Monte Carlo

Cumulative Distribution Function

Suppose that

X

is a random variable. The cumulative distribution function of

X

is the function

F_{X} : ℝ \to [0,1]

defined by

F_{X} (x) : = P (X \leq x) .

Joint Density Function

Suppose that

X

and

Y

are real-valued random variables. A function

p : ℝ^{2} \to [0, \infty)

is a joint density function for

(X, Y)

if, for every suitable set

A \subseteq ℝ^{2}

P ((X, Y) \in A) = \int_{A} p (x, y) d x d y .

Marginal Density Function

Suppose that

p (x, y)

is a joint density function. The marginal density function of

X

p_{X} (x) : = \int_{- \infty}^{\infty} p (x, y) d y .

Conditional Density Function

Suppose that

p (x, y)

is a joint density function and

p_{X} (x) > 0

. The conditional density function of

Y

given

X = x

p_{Y | X} (y | x) : = \frac{p (x, y)}{p_{X} (x)} .

Joint Density Factors as Marginal Times Conditional Density

Suppose that

p (x, y)

is a joint density. Then

p (x, y) = p_{X} (x) p_{Y | X} (y | x)

whenever

p_{X} (x) > 0

Estimator

Suppose that

Q

is a quantity to be estimated. An estimator for

Q

is a random variable

\hat{Q}

whose values are used as approximations to

Q

Unbiased Estimator

Suppose that

\hat{Q}

is an estimator for

Q

. The estimator

\hat{Q}

is unbiased if

E (\hat{Q}) = Q .

Biased Estimator

Suppose that

\hat{Q}

is an estimator for

Q

. The bias of

\hat{Q}

E (\hat{Q}) - Q .

The estimator is biased if its bias is not

0

Monte Carlo Estimator

Suppose that

D \subseteq ℝ^{n}

f : D \to ℝ

, and

p

is a density function on

D

such that

p (x) > 0

whenever

f (x) \neq 0

. If

X_{1}, \dots, X_{N}

are independent samples with density

p

, the Monte Carlo estimator for

Q : = \int_{D} f (x) d x

F_{N} : = \frac{1}{N} \sum_{i = 1}^{N} \frac{f (X_{i})}{p (X_{i})} .

Monte Carlo Estimator is Unbiased

Under the hypotheses of the Monte Carlo estimator,

E (F_{N}) = \int_{D} f (x) d x .

Variance of an Average of Independent Identically Distributed Random Variables

Suppose that

X_{1}, \dots, X_{N}

are independent identically distributed random variables with finite variance. Then

Var (\frac{1}{N} \sum_{i = 1}^{N} X_{i}) = \frac{Var (X_{1})}{N} .

Sample Variance

Suppose that

x_{1}, \dots, x_{N} \in ℝ

, with

N \geq 2

, and let

x : = \frac{1}{N} \sum_{i = 1}^{N} x_{i} .

The sample variance of

x_{1}, \dots, x_{N}

s^{2} : = \frac{1}{N - 1} \sum_{i = 1}^{N} {(x_{i} - x)}^{2} .

Inversion Method

Suppose that

F

is a cumulative distribution function that has an inverse

F^{- 1}

, and suppose that

U \sim unif [0,1]

. The inversion method samples from

F

by setting

X : = F^{- 1} (U) .

Inversion Method Samples from the Target Distribution

Suppose that

F

is an invertible cumulative distribution function,

U \sim unif [0,1]

, and

X = F^{- 1} (U)

. Then

X

has cumulative distribution function

F

Change of Variables for Density Functions

Suppose that

X

is an

n

-dimensional random variable with density

p_{X}

, and suppose that

T : ℝ^{n} \to ℝ^{n}

is a differentiable bijection whose Jacobian determinant is nonzero. If

Y = T (X)

, then the density of

Y

p_{Y} (y) = \frac{p_{X} (T^{- 1} (y))}{| \det D T (T^{- 1} (y)) |} .

Stratified Sampling

Suppose that a domain

D

is partitioned into disjoint measurable sets

D_{1}, \dots, D_{m}

. Stratified sampling is the practice of estimating an integral over

D

by taking samples separately within each stratum

D_{i}

and combining the resulting estimates.

Stratified Sampling Does Not Increase Variance

For an integral estimator with a fixed total number of samples, stratifying the domain and sampling each stratum proportionally to its measure does not increase variance compared with unstratified sampling from the whole domain.

Importance Sampling

Importance sampling estimates an integral

\int_{D} f (x) d x

by drawing samples from a density

p

and using the weighted terms

\frac{f (X)}{p (X)} .

The density

p

should be positive wherever

f

is nonzero.

Multiple Importance Sampling

Multiple importance sampling estimates an integral by combining samples drawn from several densities

p_{1}, \dots, p_{m}

. If

w_{i}

is a weight function for density

p_{i}

, then a typical weighted term has the form

w_{i} (X) \frac{f (X)}{p_{i} (X)} .

Balance Heuristic

Suppose that

p_{1}, \dots, p_{m}

are sampling densities and

n_{i}

samples are drawn from

p_{i}

. The balance heuristic assigns the weight

w_{i} (x) : = \frac{n_{i} p_{i} (x)}{\sum_{j} n_{j} p_{j} (x)} .

Power Heuristic

Suppose that

p_{1}, \dots, p_{m}

are sampling densities,

n_{i}

samples are drawn from

p_{i}

, and

β \in ℝ^{+}

. The power heuristic assigns the weight

w_{i} (x) : = \frac{{(n_{i} p_{i} (x))}^{β}}{\sum_{j} {(n_{j} p_{j} (x))}^{β}} .

Russian Roulette Estimator

Suppose that

X

is an unbiased estimator for

Q

, and let

B

be a Bernoulli random variable with

P (B = 1) = q > 0

, independent of

X

. The Russian roulette estimator is

Y : = {\begin{matrix} X / q & a m p; B = 1, \\ 0 & a m p; B = 0. \end{matrix}

Russian Roulette Estimator is Unbiased

The Russian roulette estimator is unbiased:

E (Y) = Q .