CMP.9:4 - Solution
Name the target law or quantity → choose obtainable random operations → derive the output law or correction → account for variation and dependence → choose effort and stopping → return and revise the qualified result.
CMP.9:4.1 - Separate the target, access and output
State whether the result is a random object, a subset, an expectation, an event probability, or another statistic. For sampling, specify the target probabilities, item identity, replacement rule and any order requirement. For estimation, define the quantity, such as μ=E_p[f(X)], before designing how X will be obtained.
Describe access: an indexed collection, a one-pass stream, evaluable weights, a generative operation, or neighbors of a current state. An evaluable probability density does not necessarily provide a cheap sampler. An unnormalized density does not supply its normalization constant.
If the inputs describe observations, MMP.7 supplies the relevant recording and inclusion law. Sampling uniformly from recorded rows remains different from sampling uniformly from the people, events or other objects those rows describe.
CMP.9:4.2 - Construct the random operation and its output law
Start with a random primitive whose assumptions are explicit, such as independent uniform bits or uniform integers in a bounded range. A finite generator supplies a particular implementation. Its period, correlations, state reuse or exposure to an adversary matter when the receiving claim depends on them.
For a finite categorical law with known probabilities, a cumulative-probability partition can transform a uniform draw. When generating a uniform integer from b bits for a range of size m, simply taking the remainder can bias the result unless m divides 2^b. One repair accepts only bit values below floor(2^b/m)*m, then takes their remainder; rejected draws are repeated. Choosing 2^b≥m makes this an effective rejection construction with acceptance greater than one half.
For a stream, maintain a distributional invariant that survives one new record; :5.1 derives such an update. For a proposal distribution q different from p, either correct the output distribution through an acceptance rule or correct the estimated contribution through weights. Derive which of those results the procedure actually returns.
When direct draws are unavailable, a transition rule can maintain a desired stationary law. Construct the transition probabilities and the condition that preserves that law. Reachability, convergence from the start and correlations remain additional algorithmic questions; :5.3 shows why an uncorrected neighbor walk can target the wrong distribution.
CMP.9:4.3 - Derive the estimator and its error sources
For independent draws from p, the mean of f(X_i) estimates E_p[f(X)]. Its expectation equals the target when the expectation exists. With finite variance σ², the mean’s variance is σ²/n.
For independent draws from q, use contributions Y_i=f(X_i)*p(X_i)/q(X_i) when the ratio is computable and q is positive wherever f*p contributes. Then E_q[Y_i]=E_p[f]. Inspect the second moment under q: a poor proposal can greatly increase variance. If an unknown normalizing constant leads to a self-normalized ratio of sums, its finite-sample bias and uncertainty require their own account.
For dependent draws, the variance of a mean includes covariance terms:
Var(mean Y_i)=(sum_i Var(Y_i)+2*sum_(i<j) Cov(Y_i,Y_j))/n².
This identity does not require stationarity. A chain’s approximate equilibrium, correlation and initial transient cannot be assessed just by counting iterations. Use an applicable mixing argument, a justified dependence-aware uncertainty method, or retain a weaker empirical conclusion.
Keep computational variation distinct from uncertainty in the target model. Sampling an assumed distribution accurately improves its computed consequences; it does not by itself validate that distribution for the subject.
CMP.9:4.4 - Choose sample effort and a compatible stopping rule
Select the error statement that changes the receiving decision. For independent identically distributed contributions bounded in [a,b], Hoeffding’s bound gives
P(|mean Y_i-μ|≥e)≤2*exp(-2*n*e²/(b-a)²)
at a fixed n chosen independently of their observed values. Thus n≥(b-a)²*log(2/δ)/(2*e²) suffices for error at most e with failure probability at most δ. The range and independence assumptions belong to this particular bound.
If results are inspected to choose the stopping time, use a compatible sequential bound. A simple conservative construction assigns δ_n=δ/(n*(n+1)) and applies a fixed-n bound at each n with that failure budget. Since the budgets sum to δ, all resulting intervals cover simultaneously with probability at least 1-δ. Stop when the current interval settles the question. More efficient confidence-sequence methods can replace this construction under their stated hypotheses.
Generating more draws is one possible improvement. A better proposal, stratification, fewer redundant transitions or an affordable deterministic calculation can improve the answer more per unit work. Include the cost of drawing, evaluating, weighting and retaining the results. Use C.11.DUA when deciding whether further computation is worthwhile; exploratory sampling need not acquire a formal interval unless the intended claim needs one.
CMP.9:4.5 - Return the useful result and identify what a change invalidates
Return the sample or estimate with the target and qualification its recipient needs. Distinguish samples without replacement, independent repeated draws, correlated states and weighted observations. A retained seed can support replay; uncertainty across repetitions needs genuinely distinct random streams under the assumed generator model.
Check a finite case by deriving or enumerating its output probabilities. A frequency experiment can expose an implementation error, but agreement on a small run does not establish a claimed law for every input.
A changed inclusion rule, target statistic, proposal, random source or stopping rule can invalidate a different part of the construction. Revise that part. Preserve already useful samples only with the correction and dependence account that their new use requires.