Automatically generated from handwritten notes — Sampling.pdf

Efficient AI · Other topics

Sampling

Sampling turns hard expectations and hard-to-draw distributions into algorithms. These notes build from Monte Carlo averages to inverse transform sampling, importance sampling, and rejection sampling.

Roadmap
  1. Why sample?
  2. Inverse transform sampling
  3. Importance sampling
  4. Which proposal is best?
  5. Rejection sampling

Big picture: sometimes we want estimates, such as $\mathbb{E}[X]$ or $\mathbb{E}_f[w(X)]$; sometimes we want actual samples from a distribution. The algorithms below differ mainly in which of these goals they solve and what access they assume.

1. Why sample?

Sampling is a way to learn about a random variable: estimate expectations, distributional properties, and other functionals that are hard to compute in closed form. The simplest case is when we can run the random process itself many times.

Application: estimating an expectation

Suppose there is a randomized process with associated random variable $X$. How do we discover $\mathbb{E}[X]=\mu$?

Ans. Monte Carlo estimation. Sample and average: \[ \mathbb{E}[X] \approx \frac{1}{n}\sum_{i=1}^{n} X_i. \]

The law of large numbers is the reason this works: as $n$ grows, the sample average becomes a better estimate of the true expectation.

Q. How do we sample data from a distribution $f(x)$?

So the first algorithmic question becomes: if the computer gives us uniforms, how do we turn those uniforms into samples from some target distribution $f$?

2. Inverse transform sampling

Q. If I have access to $U(0,1)$, how do I create samples from $f(x)$?

The target density $f$ tells us where probability mass lives. For a continuous density, the probability of landing in a small bin around $x$ is the area under $f$ over that bin:

\[ \text{sample from }(x\pm\delta) \quad\text{with probability}\quad \int_{x-\delta}^{x+\delta} f(t)\,dt. \]

The cumulative distribution function (CDF) packages these areas into a monotone map $F$. This monotonicity is the key: a uniform number $r\in[0,1]$ can be interpreted as a target cumulative probability.

\[ F(x)=\Pr(X\le x)=\int_{-\infty}^{x} f(t)\,dt, \qquad \Pr(a < X < b)=F(b)-F(a). \]
r X F(x) 1 0

Draw $r\sim U[0,1]$, then read off $X=F^{-1}(r)$ from the CDF.

Inversion method
  1. Generate $r\sim U[0,1]$.
  2. Return $X=F^{-1}(r)$.

The returned value has the desired distribution. This method is exact whenever the inverse CDF is available and cheap enough to compute.

3. Importance sampling

Inverse transform gives actual samples from $f$, but it needs $F^{-1}$. Often that is not realistic. A different goal is easier: instead of sampling from $f$, estimate expectations under $f$ using a distribution we can sample from.

Setup. Suppose you want to estimate properties of a function $w(x)$ for $x\sim f(x)$. Assume $f(x)$ is known/evaluable, but there is no direct way to sample from $f$.

Why direct sampling may be hard.

Suppose instead we can sample from a proposal $g(x)$. Start from the target expectation:

\[ \mathbb{E}_f[w(x)] = \int w(x)\,f(x)\,dx \]

and rewrite it under $g$:

\[ \mathbb{E}_f[w(x)] = \int w(x)\cdot\frac{f(x)}{g(x)}\,g(x)\,dx = \mathbb{E}_g\!\left[\frac{f(x)\,w(x)}{g(x)}\right]. \]

Estimate the right-hand side by Monte Carlo with samples $x_i\sim g$:

\[ \mathbb{E}_f[w(x)] \approx \frac{1}{n}\sum_{i=1}^{n} \frac{f(x_i)\,w(x_i)}{g(x_i)}. \]

Thus we can estimate $\mathbb{E}_f[w(x)]$ using a proposal distribution $g$, without ever sampling from $f$. The price is that each sample gets reweighted by $f(x_i)/g(x_i)$.

Required conditions We still need to evaluate the ratio $f(x)/g(x)$ at sampled points, and $g$ must cover the important support: $g(x)>0$ wherever $f(x)w(x)\ne 0$. Otherwise the estimator is undefined or misses part of the expectation.
Q. Are all distributions $g$ good?
Q. What should we look at to know if $g$ is good?
A. How good is the estimate produced by the estimator that uses $g$ — typically its variance.

Write the importance-weighted random variable

\[ y=\frac{w(x)\,f(x)}{g(x)}, \qquad x\sim g(x). \]

Then $\mathbb{E}_g[y]=\mathbb{E}_f[w]=\mu$, but $\mathrm{Var}_g(y)$ depends strongly on the choice of $g$.

This is the central tradeoff in importance sampling: unbiasedness is easy to preserve, but a poor proposal can make the variance enormous.

Note Importance sampling does not let us sample from $f(x)$. It only lets us estimate $\mathbb{E}_f(\cdot)$ using samples from $g(x)$.
Even direct sampling can be inefficient Even if direct samples from $f$ were available, they may be inefficient for estimating a particular expectation. If there exist rare $x$ where $|w(x)|$ is very large but $f(x)$ is small, those rare regions can dominate the expectation and naive Monte Carlo from $f$ can have high variance.
Exercise Discuss when a softmax can be approximated via randomly uniform sampling of tokens.

4. Which proposal is best?

The previous section reduced proposal quality to estimator variance. Now ask what proposal would be ideal. We want a proposal that keeps the estimator unbiased while minimizing variance. With $y=f w / g$ and $x\sim g$,

\[ \mathbb{E}_g[y]=\mu, \qquad \mathrm{Var}_g(y) = \mathbb{E}_g[(y-\mu)^2] = \mathbb{E}_g[y^2]-\mu^2 = \int \frac{f(x)^2 w(x)^2}{g(x)}\,dx - \mu^2. \]

So the design question is:

\[ \min_g\ \mathrm{Var}_g(y) \quad\text{subject to}\quad g\ge 0,\ \int g=1,\ \text{and } g(x)>0\text{ when }f(x)w(x)\ne0. \]

Lower bound via Cauchy–Schwarz

\[ \Bigl(\int a(x)b(x)\,dx\Bigr)^2 \le \int a(x)^2\,dx\cdot\int b(x)^2\,dx. \]

Taking $a=f|w|/\sqrt{g}$ and $b=\sqrt{g}$ gives

\[ \Bigl(\int f|w|\,dx\Bigr)^2 \le \int\frac{f^2 w^2}{g}\,dx \cdot \underbrace{\int g\,dx}_{=1}, \] so \[ \int\frac{f^2 w^2}{g}\,dx \ge \bigl(\mathbb{E}_f[|w|]\bigr)^2. \]

When is the bound tight?

Equality holds when the two factors are proportional:

\[ \frac{f|w|}{\sqrt{g}} = C\sqrt{g} \quad\Rightarrow\quad g=\frac{1}{C}\,f|w|. \]
\[ g^\star \propto f\,|w|. \]

If $w(x)>0$ for all $x$, the absolute value disappears and $g\propto f\,w$.

The zero-variance fantasy

When $w>0$ and we take $g=f w / c$ with $c=\int f w\,dx=\mu$,

\[ \mathrm{Var} = \int\frac{f^2 w^2\cdot c}{f w}\,dx-\mu^2 = c\int f w\,dx-\mu^2 = c\mu-\mu^2 = 0. \]
Why this is not free Knowing this optimal $g$ already requires knowing $\mu$ — which is exactly what we wanted to estimate. So the zero-variance proposal is a characterization of the ideal, not a free algorithm.

Still, the message is practical: a good proposal should put mass where $|f w|$ is large. It does not have to be exactly optimal to help; it just needs to avoid wasting samples in unimportant regions.

good bad g(x)

A good proposal overlaps the important region of $|f w|$; a bad one wastes samples where the integrand is tiny.

Exercise

Let $S=x_1+\cdots+x_n$ with $x_i\in\mathbb{R}$. Estimate the sum by sampling indices $i$ instead of reading every term. If index $i$ is sampled with probability $p_i$, an unbiased one-sample estimator is $x_i/p_i$. What choice of $p_i$ minimizes the estimator variance?

What if instead $\vec S=\vec x_1+\cdots+\vec x_n$ with $\vec x_i\in\mathbb{R}^d$? What should the sampling probabilities depend on now?

5. Rejection sampling

Importance sampling estimates expectations under $f$, but its samples still come from $g$. Sometimes we really need accepted samples whose distribution is $f$ itself. Rejection sampling converts proposal samples into target samples by randomly accepting only some of them.

Suppose we can sample from a proposal $g$, and we know a constant $M$ such that $g$ covers the support of $f$ and

\[ M\,g(x)\ \ge\ f(x) \qquad\text{for all }x. \]
Rejection sampling
  1. Sample $x\sim g(x)$.
  2. Sample an independent $u\sim U[0,1]$.
  3. Accept $x$ if $u\le \dfrac{f(x)}{M g(x)}$; otherwise reject and resample.
x Mg(x) f(x)

The envelope $Mg$ must dominate $f$. Acceptance probability at $x$ is the vertical ratio $f(x)/(Mg(x))$.

Accepted samples follow the target density. Schematically,

\[ p(x) \propto g(x)\cdot\frac{f(x)}{M g(x)} \propto \frac{f(x)}{M}. \]

The constant $M$ affects efficiency, not the final accepted distribution: larger $M$ means lower acceptance probability.

How to choose a good $g$

Exercise

Sample a point uniformly from the unit disk in $d=2$ using only Uniform$(0,1)$ coordinates. First map two uniforms to a point in the square $[-1,1]^2$, then reject points outside the unit circle.

d=2

The rejection rate is \[ 1-\frac{\mathrm{Area(circle)}}{\mathrm{Area(square)}}. \] For $d=2$, the acceptance probability is $\pi/4$, so the rejection rate is $1-\pi/4$. What happens as $d$ grows? Can the same approach be used for a high-dimensional ball?

Sampling is the algorithmic side of the same concentration ideas that appear in the tail-bounds notes: once you can draw samples, Monte Carlo turns expectations into averages with explicit variance and concentration tradeoffs.