Rejection Sampling in SMC-FCS

Why Adjust a Covariate Proposal?

In SMC-FCS, an imputation model supplies a proposal for an incomplete covariate, while the substantive model describes the outcome conditional on the covariates. A proposal drawn from the covariate model alone need not have the conditional distribution implied jointly by those two models. Rejection sampling provides a direct adjustment: propose a covariate value, then retain it with a probability determined by how well it accords with the observed outcome under the substantive model.

The adjustment is conditional on the other covariates and the current model parameters. It does not repair a misspecified substantive model, a poor covariate model, or an invalid missingness assumption. Its role is narrower: given the proposal distribution and substantive-model likelihood, it samples from the corresponding compatible conditional distribution.

Definition: For one individual, let $X_j$ be the covariate currently being imputed, $X_{-j}$ the other covariates held at their current values, and $Y$ the observed outcome. Let $q(x_j\mid x_{-j})$ be the proposal density or probability mass function for $X_j$, and let $L(x_j)=f(y\mid x_j,x_{-j})$ be the substantive-model likelihood contribution for the observed outcome. The SMC-FCS conditional target is $$ \pi(x_j\mid x_{-j},y) = \frac{q(x_j\mid x_{-j})L(x_j)} {\int q(u\mid x_{-j})L(u)\,du}, $$ with a sum replacing the integral for a discrete covariate. The expression is conditional on the other covariates and the model parameters used in that update.

The likelihood in this expression is the outcome likelihood as a function of the proposed covariate value. Factors that do not depend on $x_j$ cancel in the normalizing denominator and need not be included. For independent individuals, the update for one individual uses that individual's likelihood contribution, with the other individuals' values fixed.

The Rejection-Sampling Step

Suppose there is a finite constant $M$ such that $L(x_j)\leq M$ for every value that can be proposed. A single rejection-sampling attempt is:

Propose.
Draw $X_j^*$ from $q(x_j\mid x_{-j})$.

Evaluate the acceptance probability.
Set $a(X_j^*)=L(X_j^*)/M$, which lies between zero and one by the envelope condition.

Accept or reject.
Draw $U$ uniformly from zero to one. Accept $X_j^*$ if $U\leq a(X_j^*)$; otherwise return to Step 1 and propose again.

The envelope constant need not be the smallest possible bound, but it must be a valid bound over the proposal's entire support. A looser bound still gives the correct accepted distribution, but lowers the probability of acceptance. When the likelihood is already a probability, such as a Bernoulli likelihood, $M=1$ is a valid bound. For a continuous outcome, a density can exceed one, so simply using the likelihood as an acceptance probability may be invalid; a bound or a likelihood ratio to a valid bound is needed.

Why Accepted Draws Have the Required Distribution

The derivation follows by considering the probability density of a proposal that is accepted in a single attempt. A proposal has density $q(x_j\mid x_{-j})$, and it is accepted with probability $L(x_j)/M$. Thus the joint density of proposing $x_j$ and accepting it is proportional to their product:

q(x_j\mid x_{-j})\frac{L(x_j)}{M}.

To obtain the distribution conditional on acceptance, divide by the total acceptance probability, which is the integral of this expression over all possible proposals:

\begin{aligned} f(x_j\mid\text{accepted},x_{-j},y) &= \frac{q(x_j\mid x_{-j})L(x_j)/M} {\int q(u\mid x_{-j})L(u)/M\,du}\\ &= \frac{q(x_j\mid x_{-j})L(x_j)} {\int q(u\mid x_{-j})L(u)\,du}. \end{aligned}

The constant $M$ cancels, leaving exactly the SMC-FCS conditional target. Repeated attempts do not change this result: each attempt uses the same proposal and acceptance rule, so the first accepted value has the same distribution as a proposal conditional on acceptance. This argument requires a valid envelope, a well-defined target with a finite normalizing constant, and proposal support wherever the target has positive density.

Worked Example: A Binary Outcome and a Binary Covariate

Suppose a hypothetical individual has observed outcome $Y=1$, and the incomplete covariate $X$ is binary. At the current parameter values, the proposal gives $q(X=0)=q(X=1)=0.5$. The fitted substantive model gives $P(Y=1\mid X=0)=0.3226$ and $P(Y=1\mid X=1)=0.4980$. These are likelihoods for the observed outcome $Y=1$. Because they are probabilities, $M=1$ is valid.

A proposal of $X=0$ is accepted with probability $0.3226$, and a proposal of $X=1$ is accepted with probability $0.4980$. The unnormalized accepted weights are the proposal probabilities multiplied by these likelihoods:

w_0=0.5(0.3226)=0.1613,\qquad w_1=0.5(0.4980)=0.2490.

Consequently, the conditional probability that an accepted draw has $X=1$, using the displayed rounded weights, is

P(X=1\mid Y=1) = \frac{0.2490}{0.1613+0.2490} = \frac{0.2490}{0.4103} = 0.6069.

The average acceptance probability per proposal is $0.5(0.3226)+0.5(0.4980)=0.4103$. Thus proposals with $X=1$ are more likely to be retained, and about 60.69% of accepted proposals have $X=1$. This is a conditional distribution under the stated proposal and model, not a causal effect of $X$ on $Y$.

Continuous Outcomes and Likelihood Densities

For a continuous outcome, the likelihood is a density evaluated at the observed value. Its numerical value depends on the outcome's units and can exceed one; what matters for rejection sampling is a valid upper bound on the density across proposed covariate values.

Worked Example: A Normal Outcome Likelihood

Consider a hypothetical normal substantive model $Y\mid X\sim N(\beta_0+\beta_1X,\sigma^2)$, with $\sigma=2$. For the observed value $y=10$, suppose two possible proposals imply fitted means 9 and 12. The normal density is maximized when its mean equals the observation, so a valid bound over these proposals (and any other possible means) is $M=1/(\sqrt{2\pi}\,2)$.

For a candidate with mean 9, the residual is $10-9=1$. Its likelihood divided by the maximum density is

\frac{f(10\mid\mu=9,\sigma^2=4)}{M} = \exp\left(-\frac{(10-9)^2}{2(2^2)}\right) = \exp(-1/8) = 0.8825.

For a candidate with mean 12, the residual is $10-12=-2$, giving

\frac{f(10\mid\mu=12,\sigma^2=4)}{M} = \exp\left(-\frac{(10-12)^2}{2(2^2)}\right) = \exp(-1/2) = 0.6065.

The first candidate is therefore accepted more often because its fitted mean is closer to the observed outcome. The bound applies because the normal density with fixed $\sigma=2$ cannot exceed $1/(\sqrt{2\pi}\,2)$, regardless of the mean. If the proposal can produce other means, the same bound remains valid under this fixed-variance model.

Updating One of Several Incomplete Covariates

With multiple incomplete covariates, the rejection step is applied to the covariate currently being updated, conditional on the current values of all the others. A rejected proposal is not substituted into the data; the algorithm proposes again for that same covariate. Once an accepted value is obtained, the algorithm can move to the next covariate in its update sequence. The substantive likelihood is evaluated using the candidate together with the other current covariate values.

Worked Example: A Discrete Update With Other Covariates Held Fixed

Suppose a hypothetical update proposes $X_j\in\{0,1,2\}$, with probabilities $q=(0.20,0.50,0.30)$. The other covariates are held at their current values. For the observed binary outcome $Y=1$, suppose the substantive model gives likelihoods $L(0)=0.25$, $L(1)=0.80$, and $L(2)=0.40$. These are valid Bernoulli probabilities, so take $M=1$.

The acceptance probabilities for the three proposed values are $0.25$, $0.80$, and $0.40$, respectively. The unnormalized accepted weights are

(0.20)(0.25)=0.050,\qquad (0.50)(0.80)=0.400,\qquad (0.30)(0.40)=0.120.

Their sum is $0.050+0.400+0.120=0.570$, the probability of acceptance on a proposal attempt. The accepted conditional probabilities are therefore

P(X_j=0\mid\text{accepted})=\frac{0.050}{0.570}=0.08772,\quad P(X_j=1\mid\text{accepted})=\frac{0.400}{0.570}=0.7018,\quad P(X_j=2\mid\text{accepted})=\frac{0.120}{0.570}=0.2105.

These sum to 1. The most common proposal value, $X_j=1$, is also strongly favored by the likelihood in this example. The calculation is conditional on the other covariates' current values; changing those values can change the substantive likelihoods and hence the accepted distribution.

Assumptions, Diagnostics, and Failure Modes

The rejection step is exact for the stated target only under several conditions. The proposal model must give the intended covariate conditional distribution for the SMC-FCS construction, and the substantive likelihood must correctly represent the outcome model being preserved. The proposal must cover the target's support: if $q(x_j\mid x_{-j})=0$ where the intended target has positive density, no rejection rule can generate that value. The envelope must bound the likelihood everywhere the proposal can go. The missingness assumptions and model specification needed for the overall imputation analysis remain necessary; rejection sampling does not make missing-not-at-random data ignorable or correct a wrongly specified model.

Useful diagnostics include the acceptance fraction overall and across individuals or outcome patterns, and whether proposals and accepted values cover the covariate range expected under the model. Very low acceptance can mean that the likelihood is concentrated in a small part of the proposal distribution or that the envelope is unnecessarily loose. It is a computational warning, not by itself proof that the target model is wrong. An acceptance probability above one indicates an invalid envelope or an implementation error. A zero acceptance probability for a region means no proposal in that region can be retained under the specified likelihood.

A fixed envelope chosen from a theoretical bound is safer than a bound estimated from a few proposals: an estimated bound that falls below the true maximum can produce invalid draws. Likewise, clipping $L/M$ to one does not fix an invalid bound; it changes the acceptance rule and generally fails to produce the target distribution. Where likelihoods are extremely small, calculations on a log scale can help avoid numerical underflow, but the acceptance probability must still be computed from a valid likelihood ratio.

How Rejection Sampling Compares With Alternatives

Approach	What it does	Main consideration
Rejection sampling	Proposes from $q$ and retains a candidate with probability proportional to $L$.	Accepted draws are exact for the target when the support and envelope conditions hold; efficiency may be poor.
Direct sampling or enumeration	Computes and samples from the normalized target directly.	Useful when the conditional distribution is tractable or has few possible values; often unavailable for complex models.
Importance weighting	Retains proposals with weights proportional to $L$, rather than discarding rejected proposals.	Can use proposals more efficiently in some settings, but highly variable weights can make the effective information small.
Metropolis–Hastings	Uses a Markov chain with an acceptance rule designed to preserve the target.	Does not require a global likelihood envelope, but draws are dependent and require attention to chain behavior.

Ordinary chained-equation draws from the covariate proposal alone omit the substantive likelihood adjustment and therefore need not follow the SMC-FCS target. Rejection sampling is attractive when a useful envelope exists and the acceptance rate is adequate. Its limitations are computational: poor overlap between proposal and target can demand many attempts, and an unbounded likelihood without a usable envelope cannot be handled by the basic accept-with-$L/M$ rule.

Common Mistake

Key takeaway: A likelihood is not automatically an acceptance probability. Use $L(x_j)/M$, where $M$ is a valid upper bound over the full proposal support, and retain only candidates whose uniform draw is no larger than that ratio. The proposal multiplied by the likelihood determines the accepted distribution.

A common error is to say, “The likelihood is 1.4, so accept with probability 1.4,” or to cap that value at 1. In either case, the stipulated acceptance rule is not valid. For a continuous outcome, use a valid density bound or another valid envelope; for a probability likelihood bounded by 1, $M=1$ may be used. A related error is to forget the proposal probability when calculating the distribution of accepted values. Accepted weights are proportional to $q(x_j\mid x_{-j})L(x_j)$, not to $L(x_j)$ alone, unless the proposal is uniform over the relevant finite support.

Check Your Understanding

Answer each question, then compare your work with the solutions below.

A binary outcome likelihood is $0.30$ for one proposed value and $0.75$ for another. With $M=1$, what are their acceptance probabilities?
A discrete proposal assigns probabilities $0.40$ and $0.60$ to two values with likelihoods $0.50$ and $0.20$. What is the conditional probability of the first value among accepted proposals?
Why can a normal outcome density greater than one not be used directly as an acceptance probability?
What happens to the intended target if the proposal assigns zero probability to a covariate value with positive target density?

Solutions. (1) The acceptance probabilities are $0.30/1=0.30$ and $0.75/1=0.75$. (2) The accepted weights are $0.40(0.50)=0.20$ and $0.60(0.20)=0.12$, so the first value has conditional probability $0.20/(0.20+0.12)=0.625$. (3) Acceptance probabilities must be between zero and one. A density can exceed one, so divide by a valid upper bound; for a normal model with fixed variance, the maximum density can supply that bound. (4) Rejection sampling can never produce a value that is never proposed. The desired target cannot be recovered with that proposal, so the support condition fails.

Approach	What it does	Main consideration
Rejection sampling	Proposes from \(q\) and retains a candidate with probability proportional to \(L\).	Accepted draws are exact for the target when the support and envelope conditions hold; efficiency may be poor.
Direct sampling or enumeration	Computes and samples from the normalized target directly.	Useful when the conditional distribution is tractable or has few possible values; often unavailable for complex models.
Importance weighting	Retains proposals with weights proportional to \(L\), rather than discarding rejected proposals.	Can use proposals more efficiently in some settings, but highly variable weights can make the effective information small.
Metropolis–Hastings	Uses a Markov chain with an acceptance rule designed to preserve the target.	Does not require a global likelihood envelope, but draws are dependent and require attention to chain behavior.

What You'll Learn