Importance Sampling: A Detailed Tutorial

📌

For more content check out the Circuit of Knowledge.

Importance sampling is a powerful technique used in Monte Carlo simulations to efficiently estimate properties of rare events or difficult-to-sample distributions. It is particularly useful when the probability of the event of interest is very small, and direct sampling would require an enormous number of samples to obtain reliable estimates.

Theory Behind Importance Sampling:

Let's say we want to estimate the expectation of a function $f(x)$ over a probability distribution $p(x)$ . Mathematically, this can be expressed as:

$E_p[f(x)] = \int f(x) p(x) dx$

However, if the probability distribution $p(x)$ is difficult to sample from or the function $f(x)$ is zero for most values of $x$ , direct Monte Carlo sampling may be inefficient or even infeasible.

Importance sampling introduces a new probability distribution $q(x)$ , called the importance distribution or proposal distribution, which is easier to sample from and has a higher probability of generating samples in the regions where $f(x)$ is non-zero. The expectation can be rewritten as:

$E_p[f(x)] = \int f(x) \frac{p(x)}{q(x)} q(x) dx = E_q\left[f(x) \frac{p(x)}{q(x)}\right]$

The ratio $\frac{p(x)}{q(x)}$ is called the importance weight or likelihood ratio. It corrects for the bias introduced by sampling from the importance distribution $q(x)$ instead of the original distribution $p(x)$ .

The importance sampling estimator (sampling mean) for $E_p[f(x)]$ based on $N$ samples from $q(x)$ is given by:

$\hat{E}_p[f(x)] = \frac{1}{N} \sum_{i=1}^{N} f(x_i) \frac{p(x_i)}{q(x_i)}$

where $x_i$ are the samples drawn from $q(x)$ .

Python Script Explanation:

Now, let's go through the Python script step by step and see how it relates to the theory of importance sampling.

import numpy as np

def simulate_bit_error_rate(p_error, num_samples):
    # Importance distribution parameters
    q_error = 0.1  # Probability of error in the importance distribution

    # Generate samples from the importance distribution
    samples = np.random.choice([0, 1], size=num_samples, p=[1 - q_error, q_error])

    # Calculate the weights for each sample
    weights = np.where(samples == 1, p_error / q_error, (1 - p_error) / (1 - q_error))

    # Estimate the bit error rate using importance sampling
    estimate = np.sum(samples * weights) / num_samples

    return estimate

# Rare event probability (bit error rate)
p_error = 1e-7

# Number of samples for importance sampling
num_samples = 100000

# Simulate the bit error rate using importance sampling
estimated_error_rate = simulate_bit_error_rate(p_error, num_samples)

print(f"Estimated Bit Error Rate: {estimated_error_rate:.2e}")

Estimated Bit Error Rate: 1.00e-07

The simulate_bit_error_rate function takes the actual bit error rate (p_error) and the number of samples (num_samples) as input.
We define the importance distribution parameters. In this case, we set the probability of error in the importance distribution (q_error) to a higher value (e.g., 0.1) to increase the likelihood of sampling error events. This corresponds to choosing a suitable $q(x)$ that emphasizes the rare event of interest.
We generate samples from the importance distribution using np.random.choice. The samples are either 0 (no error) or 1 (error), and the probability of an error is determined by q_error. These samples represent $x_i$ drawn from $q(x)$ .
We calculate the weights for each sample using np.where. The weights are the likelihood ratios $\frac{p(x_i)}{q(x_i)}$ . For error events (samples equal to 1), the weight is $\frac{p_\text{error}}{q_\text{error}}$ , and for non-error events (samples equal to 0), the weight is $\frac{1 - p_\text{error}}{1 - q_\text{error}}$ . These weights correct for the bias introduced by sampling from the importance distribution.
We estimate the bit error rate using importance sampling by taking the sum of the product of the samples and their corresponding weights, divided by the total number of samples. This corresponds to the importance sampling estimator:

$\hat{E}p[f(x)] = \frac{1}{N} \sum_{i=1}^N f(x_i) \frac{p(x_i)}{q(x_i)}$

In this case, $f(x)$ is the identity function, as we are directly estimating the probability of error.

Finally, we call the simulate_bit_error_rate function with the desired bit error rate (p_error) and the number of samples (num_samples), and print the estimated bit error rate.

The key idea behind importance sampling is to sample from a distribution that increases the probability of the rare event occurring and then correct for the introduced bias using the importance weights. By doing so, we can obtain reliable estimates of rare event probabilities with a significantly smaller number of samples compared to direct Monte Carlo sampling.

It's important to note that the choice of the importance distribution $q(x)$ can greatly affect the efficiency and accuracy of the importance sampling estimator. Ideally, $q(x)$ should be chosen to minimize the variance of the estimator while being easy to sample from. In practice, finding the optimal importance distribution may be challenging, and various techniques, such as adaptive importance sampling or multiple importance sampling, can be employed to improve the performance of importance sampling.

In conclusion, importance sampling is a valuable technique for estimating properties of rare events or difficult-to-sample distributions. By leveraging the power of importance sampling, we can efficiently simulate and analyze systems with rare occurrences, such as bit error rates in communication systems or rare failure events in reliability analysis.

Another example of the effective utilization of importance sampling is to calculate tail probabilities of a distribution, e.g. Gaussian distribution, such as P(X > 5) where X is normally distributed, with considerably fewer samples compared to direct Monte Carlo sampling.

In the case of a Gaussian distribution, we can choose an importance distribution that shifts the mean of the original distribution towards the tail region of interest. This increases the likelihood of sampling points in the desired tail region, thereby reducing the number of samples needed to estimate the tail probability accurately.

Here's an example of how to use importance sampling to calculate the tail probability P(X > 5) for a standard normal distribution:

import numpy as np
from scipy.stats import norm

def gaussian_tail_probability(threshold, num_samples, shift):
    # Generate samples from the importance distribution (shifted Gaussian)
    samples = np.random.normal(loc=shift, scale=1, size=num_samples)

    # Calculate the weights for each sample
    weights = norm.pdf(samples) / norm.pdf(samples, loc=shift, scale=1)

    # Estimate the tail probability using importance sampling
    tail_prob = np.mean((samples > threshold) * weights)

    return tail_prob

# Parameters
threshold = 5.0  # Tail probability threshold
num_samples = 10000  # Number of samples for importance sampling
shift = 4.0  # Mean shift for the importance distribution

# Calculate the tail probability using importance sampling
estimated_tail_prob = gaussian_tail_probability(threshold, num_samples, shift)

# Calculate the true tail probability using the Gaussian CDF
true_tail_prob = 1 - norm.cdf(threshold)

print(f"Estimated Tail Probability: {estimated_tail_prob:.4e}")
print(f"True Tail Probability: {true_tail_prob:.4e}")

Estimated Tail Probability: 2.8493e-07
True Tail Probability: 2.8665e-07

Explanation:

We define the gaussian_tail_probability function that takes the tail probability threshold, the number of samples for importance sampling, and the mean shift for the importance distribution as parameters.
Inside the function, we generate samples from the importance distribution, which is a shifted Gaussian distribution with a mean of shift and a standard deviation of 1. The shift is chosen to move the mean closer to the tail region of interest.
We calculate the weights for each sample using the ratio of the probability density function (PDF) of the original Gaussian distribution to the PDF of the importance distribution evaluated at each sample point.
We estimate the tail probability using importance sampling by taking the mean of the product of the indicator function (samples greater than the threshold) and the corresponding weights.
We specify the tail probability threshold (threshold), the number of samples for importance sampling (num_samples), and the mean shift for the importance distribution (shift).
We calculate the estimated tail probability using the gaussian_tail_probability function with the specified parameters.
For comparison, we also calculate the true tail probability using the cumulative distribution function (CDF) of the standard normal distribution.
Finally, we print the estimated tail probability and the true tail probability.

Output:

Estimated Tail Probability: 2.8493e-07
True Tail Probability: 2.8665e-07

In this example, with just 10,000 samples and a mean shift of 4.0 for the importance distribution, we obtain an accurate estimate of the tail probability P(X > 5) for a standard normal distribution. The true tail probability is approximately 2.8665e-07, and the importance sampling estimate matches it closely.

By shifting the mean of the importance distribution towards the tail region, we increase the likelihood of sampling points in that region, thereby reducing the number of samples needed to estimate the tail probability accurately. The choice of the mean shift parameter depends on the specific problem and the desired trade-off between sample efficiency and estimation accuracy.

Using an exponential distribution as the importance distribution instead of a Gaussian distribution can have certain advantages, particularly when dealing with heavy-tailed or skewed distributions. Here are a few reasons why an exponential distribution might be preferable in some cases:

Tail behavior: The exponential distribution has a heavier tail compared to the Gaussian distribution. This means that it assigns higher probabilities to larger values, making it more likely to sample points in the tail region of interest. If the original distribution has a heavy tail, using an exponential importance distribution can be more effective in capturing the tail behavior.
Skewness: The exponential distribution is inherently skewed, with a longer right tail. If the original distribution is also skewed, using an exponential importance distribution can better match the shape of the distribution and provide a more efficient sampling scheme.
Non-negative support: The exponential distribution is defined only for non-negative values. If the quantity of interest is non-negative, using an exponential importance distribution can be a natural choice, as it automatically constrains the samples to the valid range.

Here's an example of how to use an exponential distribution as the importance distribution for calculating the tail probability P(X > 5) for a standard normal distribution:

import numpy as np
from scipy.stats import norm, expon

def gaussian_tail_probability_exponential(threshold, num_samples, shift, scale):
    # Generate samples from the importance distribution (shifted exponential)
    samples = shift + expon.rvs(scale=scale, size=num_samples)

    # Calculate the weights for each sample
    weights = norm.pdf(samples) / expon.pdf(samples - shift, scale=scale)

    # Estimate the tail probability using importance sampling
    tail_prob = np.mean((samples > threshold) * weights)

    return tail_prob

# Parameters
threshold = 5.0  # Tail probability threshold
num_samples = 10000  # Number of samples for importance sampling
shift = 4.0  # Location shift for the importance distribution
scale = 1.0  # Scale parameter for the exponential distribution

# Calculate the tail probability using importance sampling with exponential distribution
estimated_tail_prob = gaussian_tail_probability_exponential(threshold, num_samples, shift, scale)

# Calculate the true tail probability using the Gaussian CDF
true_tail_prob = 1 - norm.cdf(threshold)

print(f"Estimated Tail Probability (Exponential): {estimated_tail_prob:.4e}")
print(f"True Tail Probability: {true_tail_prob:.4e}")

Estimated Tail Probability (Exponential): 2.8942e-07
True Tail Probability: 2.8665e-07

Explanation:

We define the gaussian_tail_probability_exponential function that takes the tail probability threshold, the number of samples for importance sampling, the location shift, and the scale parameter for the exponential distribution as parameters.
Inside the function, we generate samples from the importance distribution, which is a shifted exponential distribution with a location shift of shift and a scale parameter of scale.
We calculate the weights for each sample using the ratio of the PDF of the original Gaussian distribution to the PDF of the shifted exponential distribution evaluated at each sample point.
We estimate the tail probability using importance sampling by taking the mean of the product of the indicator function (samples greater than the threshold) and the corresponding weights.
We specify the tail probability threshold (threshold), the number of samples for importance sampling (num_samples), the location shift (shift), and the scale parameter (scale) for the exponential distribution.
We calculate the estimated tail probability using the gaussian_tail_probability_exponential function with the specified parameters.
For comparison, we also calculate the true tail probability using the CDF of the standard normal distribution.
Finally, we print the estimated tail probability using the exponential importance distribution and the true tail probability.

Output:

Estimated Tail Probability (Exponential): 2.8942e-07
True Tail Probability: 2.8665e-07

In this example, the exponential importance distribution with a location shift of 4.0 and a scale parameter of 1.0 provides an accurate estimate of the tail probability P(X > 5) for a standard normal distribution, matching the true tail probability closely.

The choice between a Gaussian or an exponential importance distribution depends on the characteristics of the original distribution and the specific problem at hand. Experimenting with different importance distributions and comparing their performance can help determine the most suitable approach for a given scenario.