CoreSource checked

Importance Sampling

Estimates quantities by sampling more often from important regions.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Randomness & Sampling
Difficulty: Advanced
Family: Weighted Sampling
Tier: Core
Status: Verified
Review: Source Checked
Sources: 1
Formulas: 1
Relationships: 8
Code example: Not ready
Visualization: Ready

Overview

Importance Sampling draws from a helpful proposal distribution and weights samples to correct for the changed sampling pattern.

Core Concepts

proposal distributionsample weightvariance reductionweighted estimaterandom drawsample selectionrandom samplingstate estimate

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(k)

Average

O(k)

Worst

O(k)

Space

O(1)

When to Use

Use Importance Sampling when you need to sample likely high-impact regions.
Use it for monte Carlo integration with inputs like target quantity.
Use it when randomization, representative samples, or controlled variation are needed.
Use it when the Weighted Sampling tradeoff is acceptable for the problem size.

When Not to Use

Avoid it when repeatability is required but seeds and random sources are not controlled.
Avoid it when reproducibility, distribution quality, or sample independence cannot be verified.
Avoid it when the required output is not weighted estimate.

What It Does

Samples likely high-impact regions
Weights samples to keep estimates unbiased

Use Cases

Monte Carlo integration
Rendering
Rare-event estimation

Inputs

Target quantity
Proposal distribution
Sample count

Outputs

Weighted estimate

Key Formulas (1)

Weighted estimate

estimate = mean(f(x) · target_prob(x) / proposal_prob(x))

estimate = mean(f(x) * target_prob(x) / proposal_prob(x))

Corrects samples from a proposal distribution with importance weights.

Pseudocode

1.Choose a proposal distribution
2.Draw samples from the proposal
3.Evaluate each sample's contribution
4.Weight each contribution by target over proposal probability
5.Average the weighted contributions

Canonical Example

Input: items = [A, B, C, D], seed = 7
Output: sampled or randomized result
Explanation: Importance Sampling: The algorithm uses controlled randomness to choose or generate values.

Implementation Notes

Keep the input contract explicit: Target quantity; Proposal distribution; Sample count.
Thread a seedable random source through the implementation for repeatable tests.
Separate the random number source from the algorithm so tests can use fixed seeds.
Separate the random source from the sampler so tests can use fixed seeds and distribution checks.

Common Pitfalls

A poor proposal distribution can create high-variance estimates.
Sampling from the wrong distribution can make the estimate look precise but biased.
Using biased random choices or forgetting to store the seed for reproducible runs.
Handle empty, invalid, and boundary inputs before trusting weighted estimate.

Interactive Mechanism Walkthrough

Iterative Convergence & State Trajectory

Show dense samples in important regions with weights correcting the estimate.

Step 1 of 5: Choose a proposal distribution

weighted-samples

Notes

Importance Sampling operates in O(k) time and O(1) space within the Weighted Sampling family. Key governing relation: estimate = mean(f(x) * target_prob(x) / proposal_prob(x)). Often compared with Rejection Sampling and Stratified Sampling.