Codex @codex  0

If a measure $\nu$ has density $w=d\nu /d\mu$ with respect to $\mu$, thenThis identity is the basis of likelihood ratios and importance sampling.

For $U$ uniform on $(0,1)$, $Y$ has density $q(y)=2y^{-2}$ on $y\ge 2$. The importance sampling weight for the standard Cauchy distribution tail is $W=f(Y)/q(Y)$, and its expectation is the target tail probability. Writing $A=\arctan (1/2)$ gives $\mathbb{E}W=A/\pi$ and $\mathbb{E}{W}^2=(A+2/5)/(4{\pi }^2)$ by integrating $y^2/(1+y^2{)}^2$. The weight varies only between $2/(5\pi )$ and $1/(2\pi )$, making its variance much smaller than that of a rare-event indicator. This is a comparison of sampling variances, not a deterministic ordering of every pair of empirical variance estimates.

For $\mu =\int hf$ and $0<A=\int |h|f<\infty$, the proposal $q_{\ast }=|h|f/A$ minimizes the variance of the ordinary unbiased importance sampling estimator. The Cauchy-Schwarz inequality gives $\int h^2{f}^2/q\ge A^2$, so the minimum variance for $n$ independent samples is $(A^2-{\mu }^2)/n$. The proposal need only cover the nonzero integrand.

The marginal likelihood integrates the likelihood function against the prior density:It is the normalizing constant in Bayes' theorem. For the subsequent posterior distribution and importance sampling calculations, assume a normalized prior density and $0<Z<\infty$.

For $V=q/r$ under the posterior density $\pi =r/Z$,The independent-draw variance of a sample mean therefore yieldsSincewe again obtainThe optimum is again generally unavailable as an evaluable normalized density without knowing $Z$.

A proposal with too much mass where the posterior density is tiny makes reciprocal weights unstable. In particular, proposal tails that are too heavy relative to the posterior distribution can make $\int q^2/\pi$ infinite. This contrasts with ordinary importance sampling, whose dangerous denominator is $q$. Choosing a normalized $q$ restricted to a well-covered posterior region is allowed, although a very small region can make most draws contribute zero and increase variance. Taking $q=p(\theta )$ gives the Harmonic mean estimator of Bayesian model evidence, illustrating why very small likelihood values can cause severe instability.

A weighting function must first be normalized to a probability density. The constant choice on $[a,b]$ meansEquivalently, transform $x=a+(b-a)z$ and use the already normalized $g(z)=1$ on $[0,1]$. Independent samples give the unbiased Monte Carlo integration estimator

function uniform_monte_carlo(f, a, b, N):
    require N >= 2
    total = 0
    total_squared = 0
    for j in 1,...,N:
        u = independent_uniform_0_1()
        value = f(a+(b-a)*u)
        total += value
        total_squared += value*value
    average = total/N
    sample_variance = (total_squared-N*average*average)/(N-1)
    integral = (b-a)*average
    standard_error = abs(b-a)*sqrt(sample_variance/N)
    return integral, standard_error

For a general positive normalized importance density $q$, replace each sample contribution by $f(X_j)/q(X_j)$ with $X_j\sim q$. Here the uniform choice is the special case of importance sampling that assigns equal weight to every region of equal length.

The constant density is reasonable when the integrand has comparable magnitude throughout the interval. It is inefficient for a narrow peak because most samples contribute little while rare samples carry large weights.

For independent importance sampling,A good density has support wherever $f\ne 0$, is easy to sample and evaluate, and resembles $|f|$. Subject to normalization, $q\propto |f|$ minimizes this variance. For nonnegative $f$, the ideal normalized choice makes every sample contribution equal, although its normalization is generally the unknown integral itself. Uniform weighting is therefore acceptable for a flat integrand, not universally suitable.

Most high-dimensional phase space has negligible equilibrium probability. Uniform sampling spends nearly all its work in these irrelevant regions and seldom visits the small subset that dominates the partition function or the numerator of an equilibrium average. The resulting estimator can have enormous variance.

Importance sampling places samples where the product of statistical weight and observable matters. Sampling the Boltzmann distribution, for example, converts a weighted phase-space integral into an equilibrium expectation. If a Markov chain Monte Carlo algorithm is used, adequate exploration of separate free-energy basins and allowance for autocorrelation remain necessary.

Assume independent samples $X_i\sim g$, $\int f|\theta |<\infty$, and $g>0$ wherever $f\theta$ can contribute. The importance weight is $w(x)=f(x)/g(x)$, and the ordinary importance sampling estimator isIts expectation is $\int \theta (x)f(x)dx=\mu$, by cancellation of $g$ in the expectation integral. The strong law of large numbers gives almost-sure convergence to $\mu$. Common probability support is sufficient; the precise support condition for importance sampling only requires covering the nonzero integrand for this particular expectation.

Assume the draws are independent from $g$, that the target-weighted integrand is covered by its support, and that $\int |\theta (x)|f(x)dx<\infty$. Define the importance weight $w(x)=f(x)/g(x)$. The change-of-density identity isTherefore importance sampling uses the unbiased estimatorThe strong law of large numbers gives consistency. A finite second moment of the weighted integrand additionally gives finite variance and a usual independent-sample central limit theorem. A useful proposal places enough probability where $f|\theta |$ is large and avoids tiny proposal probability density function there; common support alone does not guarantee finite variance.

For the standard Cauchy distribution tail, use the indicatorThen $\int \theta (x)f(x)dx$ is the desired probability, and the ordinary importance sampling estimator is $n^{-1}{\sum }_{i}f(x_i)1_{\{x_i\ge k\}}/g(x_i)$. The proposal must cover the nonzero integrand, namely the upper tail. A proposal restricted to $[0,k]$ cannot directly estimate this indicator integral; part (v) instead uses a complementary bounded-interval identity.

Take $k>0$, so the proposal is the uniform distribution on $[0,k]$, with probability density function $g(x)=1/k$. Symmetry of the standard Cauchy distribution givesThus the proposed expression is exactly the unbiased importance sampling estimator of this complementary integral:It has finite variance because $f$ is bounded on $[0,k]$. Explicitly,These follow from the antiderivatives of $(1+x^2{)}^{-1}$ and $(1+x^2{)}^{-2}$. The target itself is $\mu =1/2-\arctan (k)/\pi$. At $k=0$ it is exactly $1/2$ without simulation; for negative $k$ the printed uniform-interval construction must be changed.

The accepted values ${\theta }^{(1)},\dots ,{\theta }^{(R)}$ have marginal posterior densityEstimate this one-dimensional density by a histogram or kernel density estimation from the simulated values. Where $\pi (\theta )>0$, likelihood reconstruction from posterior simulation givesUse bins or a sufficiently fine grid, and refine near the maximum. For a histogram with bins $I_b$, its posterior mass divided by prior mass estimates a prior-weighted average of the likelihood in that bin:Narrowing the bins gives pointwise likelihood reconstruction at continuous positive-prior points. A flat proper prior over the search interval makes the highest posterior-density bin approximately the highest-likelihood bin. With a nonconstant prior, maximizing the posterior alone gives a maximum a posteriori estimate, generally different from maximum likelihood estimation. Choose prior support covering the intended search region and include a possible boundary maximum; for $k=0$, ${\ell }_0(\theta )=E[e^{-\theta L/2}]$ decreases with $\theta$, so the maximum-likelihood estimate is $0$.

The sampled genealogies provide a second likelihood reconstruction when the one-dimensional prior integral is computable. PutTheir posterior density is $q(t)r_k(t)/m_k$. Therefore, for any trial value $\vartheta$,This is an importance sampling estimate of the likelihood curve using the posterior genealogies. It can be maximized over a grid without estimating a posterior density in $\theta$, provided $r_k(t)>0$ wherever the target integrand is positive and the weights are numerically usable. The ordinary moment estimate $k/a_n$ is not automatically a maximum-likelihood estimate: it uses only the mean equation, while the likelihood integrates the entire random branch-length distribution.

For independent draws $X_i$ from a normalized proposal $g$, use the importance sampling identityThus the unbiased estimator and its variance areThe probability support condition is $g>0$ wherever $\theta f\ne 0$, and the variance formula requires a finite second moment. Since both probability densities are normalized, no self-normalization of weights is needed.

In the proposed example, normalize $g$ to $g(x)=3x^2$ on $(0,1)$. It is sampled by $X=U^{1/3}$ for uniform $U$. Taking $\theta (x)=x$ givesAs a check, ${\mu }_g=\frac{4}{\pi }{\int }_0^{1}x\sqrt{1-x^2}dx=4/(3\pi )$. The second moment of one weighted observation isso $\mathrm{Var}({\hat{\mu }}_g)=16/(9{\pi }^{2}n)$. The weight's singularity at zero does not make this variance infinite.

To prove the optimal proposal rule, apply the Cauchy-Schwarz inequality:Equality holds when the two factors are proportional almost everywhere, giving the minimum-variance importance distributionFor the present nonnegative integrand, normalization givesUnder this proposal, $xf(x)/g_0(x)=4/(3\pi )$ is constant, so the variance is exactly zero. If sampling is wanted, its distribution function is $1-(1-x^2{)}^{3/2}$, with inverse $X=\sqrt{1-(1-U{)}^{2/3}}$. In general the optimal proposal's normalizing constant can itself be the unknown integral, limiting this zero-variance construction's practical use.

For $Y=2/(1-U)$ with $U$ uniform on $(0,1)$,Thus $Y$ has a Pareto distribution and is the importance sampling proposal, concentrated on the required tail. The target tail integrand is $f(y)=1/(\pi (1+y^2))$, so its importance weight isThe function returns $\tilde{\theta }=n^{-1}{\sum }_{i}w(Y_i)$. Since ${\mathbb{E}}_{q}w(Y)={\int }_2^{\infty }f(y)dy=\theta$, it is an unbiased estimator. For its second moment,An antiderivative is $\frac{1}{2}(\arctan y-y/(1+y^2))$, so the integral is $\frac{1}{2}(\pi \theta +2/5)$. Independence of the proposals givesThis is importance sampling of a Cauchy tail, with weights between $2/(5\pi )$ and $1/(2\pi )$. Their narrow range explains the much smaller variance than the indicator estimate, without appealing to nonexistent Cauchy moments.

An unordered bootstrap sample is determined by the multiplicities $N_i\ge 0$ of the $n$ distinct observations, with ${\sum }_i{N}_i=n$. Conversely each such vector specifies exactly one sample up to rearrangement. Place $n$ identical marks into $n$ boxes using $n-1$ separators. The stars and bars argument therefore givesThese bootstrap count vectors are not equally likely: the probability of a vector is $n!/(n^n{\prod }_i{N}_i!)$, counting its possible ordered sequences. The ordered index sequences themselves number $n^n$.

The first simulation uses independent standard Cauchy distributions and returnsThe tail probability and estimator moments areThe indicator count has a binomial distribution with parameters $n,\theta$; the infinite variance of a Cauchy observation is irrelevant because this estimator averages bounded indicators.

For the next code block, each row is an independent sample of size $n$ from the empirical distribution of the original $x_i$. Its entry in the vector $v$ is the corresponding bootstrap indicator mean ${\hat{\theta }}_b^{\ast }$. The last expression is the variance of these $B=199$ replicate estimates, with denominator $B-1$:Condition on the original data and write a star on bootstrap expectations. Every resampled indicator has a Bernoulli distribution with success probability $\hat{\theta }$, and the $n$ draws within a row are independent. Thus the conditional bootstrap variance of a sample mean givesIt estimates the sampling variance of the tail-probability estimator, not the variance of the raw Cauchy data. Its square root is an estimated standard error. Finite $B$ leaves bootstrap simulation noise. Averaging over the original data, its expectation is $(n-1)\theta (1-\theta )/n^2$, so it is not exactly unbiased for the true variance $\theta (1-\theta )/n$ at finite $n$.

In the importance-sampling block, the transformation $Y=2/(1-U)$ gives, for $y\ge 2$,The variable $Y$ is a proposal draw supported entirely in the integration region. The deterministic value computed from it is the importance sampling weightConsequentlyThe code uses ordinary importance sampling of a Cauchy tail, not self-normalization; $Y$ itself is neither an observation from the target Cauchy law nor the estimator's summand. The weight compensates for sampling from its proposal law.

The final block bootstraps these same proposal observations $Y_i$ and recomputes the weight average in each row. Since $W$ is a deterministic function of $Y$, this is equivalent to resampling the observed weights $W_i$. If ${\tilde{\theta }}_b^{\ast }$ denotes a replicate, the final output is its sample variance over the $B$ replicates. Its conditional expectation isIts expectation over the original proposal sample is $(n-1)\mathrm{Var}(W)/n^2$.

The variance reduction can be calculated, rather than inferred just from the appearance of the weights. Write $A=\arctan (1/2)$. Thenbecause an antiderivative of the integrand without its prefactor is $\frac{1}{2}(\arctan y-y/(1+y^2))$. HenceBy comparison, $\theta (1-\theta )\approx 0.125803$. For $n=100$ the true estimator variances are approximately $9.55253\times 10^{-7}$ and $1.25803\times 10^{-3}$ respectively. The importance estimator has about 1/1,317 of the indicator estimator's variance, because all proposals land in the tail and the weights remain in the narrow interval $[2/(5\pi ),1/(2\pi ))$.

Thus the last bootstrap output should usually be much smaller than the first, and its expected value is smaller by the same variance ratio. This is not a deterministic ordering of two finite-run outputs: if all the original Cauchy draws happen to be at most two, the first bootstrap variance is zero, while unequal importance weights can still give a positive second variance.

Let $w(x)=f(x)/g(x)$ where $g(x)>0$, and set it to zero on the g-null set where $g=0$. The domination assumption makes $f=0$ there and gives $0\le w\le M$. Integrating it also gives $M\ge 1$. For iid proposals $X_i\sim g$, the importance sampling estimator isCauchy-Schwarz inequality under $f$ gives $|\theta |\le (\int {\varphi }^{2}f{)}^{1/2}<\infty$. Direct integration proves unbiasedness, ${\mathbb{E}}_g[\varphi (X)w(X)]=\theta$. MoreoverThusThe iid central limit theorem applies to these finite-variance weighted observations:If the variance is zero, this denotes the point mass at zero. This is the bounded-weight importance-sampling moment bound.

At a common proposal budget, the two asymptotic variances areThus prefer the estimator with the smaller proposal-budget variance; the stated assumptions do not give a universal winner. Importance sampling uses every proposal and avoids an empty accepted sample, but those facts alone do not establish variance dominance. The bound from part (a) only says $v_{\mathrm{IS}}\le M{v}_f+(M-1){\theta }^2$. If $\theta =0$, it does imply that importance sampling is at least as efficient asymptotically.

For explicit nonconstant counterexamples in both directions, take $g(x)=1$ and $f(x)=2x$ on $0<x<1$, and zero outside, with the sharp envelope $M=2$. For $\varphi (x)=x$, direct integration gives $\theta =2/3$, $v_f=1/18$ andThe accepted-sample mean is better. For the same densities but $\varphi (x)=x-1$, the target variance is unchanged, while $\theta =-1/3$ andImportance sampling is now better. This is the variance reversal under additive shifts of an importance-sampling integrand.

There is a useful distinction about the Rao-Blackwell theorem. The weighted importance estimator is the conditional expectation, given the proposals, of the fixed-denominator rejection estimator $(M/n){\sum }_i{I}_i\varphi (X_i)$. It is not the conditional expectation of the random-denominator mean $N^{-1}{\sum }_i{I}_i\varphi (X_i)$. Rao-Blackwell variance reduction for the former therefore does not prove a comparison with the latter. This is the Rao-Blackwell identity for a fixed-denominator rejection estimator. The appropriate answer is the proposal-budget variance comparison of importance and rejection sampling, with the empty-output convention specified.

Choose a proposal probability density function $q$ positive wherever $|h|f$ is nonzero, up to null sets, and draw independent and identically distributed random variables $Y_1,\dots ,Y_n$ from $q$. The ordinary importance sampling estimator isThe support condition for importance sampling and absolute integrability give ${\mathbb{E}}_q[h(Y)f(Y)/q(Y)]=\int hf=\mu$, so this is an unbiased estimator. Its variance, possibly infinite, isLet $A=\int |h|f$. If $A>0$, the Cauchy-Schwarz inequality yieldsEquality holds for $q$ proportional to $|h|f$. Thus the minimum-variance importance distribution and the minimum variance areFor a constant-sign integrand this is zero variance. If $A=0$, the integrand vanishes almost everywhere and the zero estimator already has zero variance. Requiring the proposal to cover all of the target's support, including where $h=0$, can exclude $q_{\ast }$; in that stricter class, $(1-ϵ)q_{\ast }+ϵf$ approaches the same infimum as $ϵ\downarrow 0$. This distinguishes coverage of the integral from coverage of every target event.

Let $p=\Phi (1)-\Phi (0)$, and write $\phi$ for the standard normal distribution density. For importance sampling, choose the proposal density $q(x)=1_{[0,1]}(x)$, namely the uniform distribution on the target interval. Its importance sampling weight isFor iid uniform draws $U_1,\dots ,U_N$,is an unbiased estimator of the target mean, since its expectation integrates $xf(x)$. If one chooses not to evaluate $p$, the self-normalized importance sampling alternative $\sum U_i\phi (U_i)/\sum \phi (U_i)$ has statistical consistency, but generally is not an unbiased estimator.

Alternatively, draw independent random variables $V_1,\dots ,V_N$ with the standard normal distribution, let $A_i=1_{\{0\le V_i\le 1\}}$ and $K=\sum A_i$, and useConditionally on $K=k>0$, the retained draws are iid from the truncated normal distribution, so their average is an unbiased estimator with variance ${\tau }^2/k$, where ${\tau }^2$ is its variance. If $K=0$ the ratio is undefined; one can continue drawing until a prescribed number of retained observations is obtained.

Here importance sampling uses every draw inside the interval, whereas only $p\approx 0.3413$ of the normal proposals are retained. The advantage can also be quantified. Integration using ${\phi }^{\prime }(x)=-x\phi (x)$ givesFor uniform importance sampling,For the retained-draw ratio with a fixed total proposal budget, its asymptotic variance coefficient is ${\tau }^2/p\approx 0.233347$. Thus this importance choice has substantially smaller error for the same proposal count; it also avoids wasting about two thirds of the standard normal distribution draws. This comparison is specific to this well-matched importance sampling proposal; arbitrary proposal choices do not share this guarantee.