The Markov Transition Kernel of FCS

From an FCS Sweep to a Transition Rule

A chained-equations algorithm repeatedly transforms one set of imputed values into another. To describe this process precisely, it helps to separate the fixed information from the values that change. Let \(y_{\mathrm{obs}}\) denote the observed data, including the fixed missingness pattern, and let \(z\) collect all currently imputed values. The completed data at state \(z\) can then be written \(D(z)\). A full sweep produces a new state \(z'\).

The transition from \(z\) to \(z'\) is generally random. Randomness can enter through parameter draws, residual variation, categorical draws, and any randomized update order. A transition kernel summarizes the probability law of the next state for each current state. It represents the algorithm’s one-sweep mechanics; by itself, it does not establish what distribution the chain approaches or whether it approaches one.

Definition: Let \((\mathcal{Z},\mathcal{A})\) be the measurable state space of the imputed values. A Markov transition kernel \(K\) assigns a probability distribution \(K(z,\cdot)\) on \((\mathcal{Z},\mathcal{A})\) to each current state \(z\). It satisfies: (1) \(K(z,A)\geq 0\) for every state \(z\) and measurable set \(A\); (2) \(K(z,\mathcal{Z})=1\); (3) \(A\mapsto K(z,A)\) is countably additive for each fixed \(z\); and (4) for each measurable set \(A\), the map \(z\mapsto K(z,A)\) is measurable. In an FCS chain, \(K(z,A)\) is the probability that one complete sweep, starting at \(z\), ends in \(A\), given the fixed observed data and algorithm.

The state usually contains the current imputations for every missing cell, not the observed values: observed values remain fixed during updates. The kernel may depend on \(y_{\mathrm{obs}}\), the chosen conditional models, the update order, and the rules for drawing model parameters and new values. These are held fixed when describing a particular FCS chain.

Composing the Conditional Updates

Suppose a sweep updates variables in the fixed order \(1,\ldots,p\). Write \(K_j(z,B)\) for the probability that update \(j\), when the current full state is \(z\), replaces the missing entries for variable \(j\) so that the resulting state lies in \(B\). The other entries—including observed values, which are not part of \(z\)—are treated according to the update rule and remain unchanged unless that rule updates them. After each update, later updates use the state produced so far.

For a measurable set \(A\), the full-sweep kernel is the composition of the update kernels. In the expression below, \(z_0=z\), and \(z_j\) is the state after update \(j\):

K(z,A) = \int_{\mathcal{Z}}\cdots\int_{\mathcal{Z}} K_1(z_0,dz_1)\, K_2(z_1,dz_2)\cdots K_p(z_{p-1},dz_p)\, \mathbf{1}_{A}(z_p).

Here \(\mathbf{1}_{A}(z_p)\) equals 1 when \(z_p\in A\) and 0 otherwise. Equivalently, the expression averages over every possible intermediate state generated during the sweep, counting only those final states in \(A\). Kernel composition preserves the probability and measurability requirements in the definition, so this construction gives a transition kernel when the component updates are themselves valid kernels.

Worked Example: A Two-Variable Binary Sweep

Consider a hypothetical state \(z=(x,y)\), where both missing values are binary. The sweep updates \(X\) first and \(Y\) second. Suppose the update rules are \(P(X'=1\mid Y=y)=a_y\), with \(a_0=0.20\) and \(a_1=0.80\), followed by \(P(Y'=1\mid X'=u)=b_u\), with \(b_0=0.30\) and \(b_1=0.70\). Assume each draw is made using the stated Bernoulli conditional law. The current \(x\) does not enter the first update, and the second update uses the new \(X'\), not the old \(X\).

For a current state with \(y=0\), the probability of ending at \((0,0)\) is the probability of drawing \(X'=0\) times the probability of then drawing \(Y'=0\) given \(X'=0\):

K((x,0),\{(0,0)\}) = (1-a_0)(1-b_0) = (1-0.20)(1-0.30) = 0.56.

The four possible next states have probabilities \(P(0,0)=0.56\), \(P(0,1)=0.24\), \(P(1,0)=0.06\), and \(P(1,1)=0.14\). For example, \(P(1,1)=0.20\times0.70=0.14\). These probabilities sum to \(1.00\). For a current state with \(y=1\), the corresponding probabilities in that same order are \(0.14, 0.06, 0.24, 0.56\), which also sum to \(1.00\). This illustrates that a transition row is a probability distribution over the possible states after the sweep, not a list of conditional-model coefficients.

What Randomness the Kernel Must Include

An update kernel must describe the joint law of all values produced by an update, including any shared randomness. If a parameter is drawn once and used for several imputations, integrating over that parameter can induce dependence among those imputations. Their marginal probabilities alone do not determine their joint transition probability.

Worked Example: A Shared Parameter Draw

For a hypothetical update, suppose a parameter \(\theta\) is first drawn from a \(\mathrm{Beta}(3,2)\) distribution. Conditional on this shared draw, two missing binary values \(W'_1\) and \(W'_2\) are drawn independently given \(\theta\), each from a Bernoulli distribution with success probability \(\theta\). This conditional independence assumption is part of the example’s update rule.

The marginal probability that either specified value equals 1 is the mean of the beta distribution:

P(W'_1=1)=E(\theta)=\frac{3}{3+2}=0.600.

For both values to equal 1, conditional independence gives \(P(W'_1=1,W'_2=1\mid\theta)=\theta^2\). Averaging over the shared draw,

P(W'_1=1,W'_2=1) = E(\theta^2) = \frac{3(3+1)}{(3+2)(3+2+1)} = \frac{12}{30} = 0.400.

If the two values were independent marginally, the joint probability would instead be \(0.600\times0.600=0.360\). In fact, their covariance is \(0.400-0.360=0.040\). Thus, the kernel for the pair cannot be specified by multiplying the marginal success probabilities. The conditional independence given \(\theta\), together with the distribution of the shared \(\theta\), determines the joint transition law. Sharing a parameter draw without specifying the conditional joint law would not, on its own, justify the calculation \(E(\theta^2)\).

In a standard sweep, a parameter draw for one variable’s update can be integrated into that update’s kernel, provided the update draws and their dependence are fully specified. If a random quantity is carried from one update to another and affects later draws, it must also be represented correctly: either the update kernels must retain that dependence, or the state must be enlarged to include the carried quantity. Otherwise, the proposed kernel can give the wrong transition probabilities.

Update Order Is Part of the Kernel

Composing the same update rules in a different order can produce a different full-sweep kernel. The reason is direct: the later update conditions on the values available when it runs, which may include a newly imputed value in one order and an old value in another. The next example compares two orders using the binary rules above.

Worked Example: Comparing Two Sweep Orders

Start at \(z=(0,0)\). In the \(X\)-then-\(Y\) order, the probability of ending at \((0,1)\) is \((1-a_0)b_0=0.80\times0.30=0.24\): first \(X'=0\), then \(Y'=1\) using \(b_0\). The four probabilities in the order \((0,0),(0,1),(1,0),(1,1)\) are \(0.56,0.24,0.06,0.14\).

Now reverse the order. Update \(Y\) first using the current \(X=0\), so \(P(Y'=1)=b_0=0.30\). Then update \(X\) using the new \(Y'\). The probability of ending at \((0,1)\) is the probability \(Y'=1\) multiplied by \(P(X'=0\mid Y'=1)=1-a_1\):

P((X',Y')=(0,1)\mid (X,Y)=(0,0),\ Y\text{-then-}X) = b_0(1-a_1) = 0.30(1-0.80) = 0.06.

For the reversed order, the probabilities in the same final-state order are \(0.56,0.06,0.14,0.24\), again summing to \(1.00\). The orders therefore define different transition distributions from the same starting state. The order is not merely a presentation choice; it is part of the specification of the full-sweep kernel.

When the Markov Description Is Valid

A process is Markov with respect to \(z\) if, given its current state, the distribution of its next state does not additionally depend on earlier states. For an FCS sweep, this description is appropriate when the observed data and missingness pattern are fixed; the conditional update rules are fixed; and all randomness used in the next sweep has a distribution determined by the current state and those fixed inputs. Under these conditions, for any measurable \(A\),

P(z^{(t+1)}\in A\mid z^{(t)},z^{(t-1)},\ldots,y_{\mathrm{obs}}) = K(z^{(t)},A).

A common failure is to call \(z\) the state while the algorithm actually carries additional history-dependent information. For example, if a parameter draw is held fixed across sweeps, or an adaptive rule changes the update based on previous iterations, the next-state law may depend on that extra information. In that case, \(z\) alone need not define a Markov chain. Including the persistent parameter or adaptation variables in an enlarged state can restore a Markov description, but then the resulting kernel is for the enlarged state.

Specify the state and fixed inputs.
List the imputed values in \(z\), and identify the observed data, missingness pattern, update models, and sweep order held fixed.

Describe each update’s complete random law.
Include parameter draws, residual or categorical draws, and dependencies among values produced together.

Compose the updates in order.
Integrate over intermediate states to obtain the probability distribution for the state after one full sweep.

Check the kernel and the Markov state.
Verify probabilities normalize, observed values stay fixed, and no omitted history affects the next sweep.

Diagnostics, Alternatives, and Limits

Several checks help detect an incorrectly specified transition. For a finite state space, calculate each row and verify that its entries are nonnegative and sum to one. For a continuous state space, check that the update laws are proper probability distributions and that their composition is measurable. In either setting, trace the values used by each conditional update: confusing old and newly updated values changes the kernel. Also check whether joint draws have been treated as independent without justification, and whether any supposedly fixed observed value is being inadvertently redrawn.

The full-sweep kernel is a useful alternative to describing a procedure only through its conditional models: it makes the whole one-step transformation explicit and allows different orders or randomization schemes to be compared. A single-update kernel gives a more local description, while the full-sweep kernel captures their ordered composition. In a genuine Gibbs sampler, the update rules are full conditionals of a joint distribution; FCS need not have that structure, as emphasized in the earlier material on why FCS is not always Gibbs sampling. The kernel representation still applies: it describes the algorithm whether or not its conditionals come from a common joint distribution.

The representation has limits. Writing down \(K\) does not prove that the chain has a stationary distribution, converges, or yields imputations with desirable statistical properties. Those are separate questions. Nor does a correct transition formula validate the chosen conditional models or guarantee that the imputation procedure is appropriate for a particular analysis. The kernel answers a narrower, precise question: given this current state and these fixed algorithmic rules, what is the probability law of the state after one complete sweep?

Common pitfall: Multiplying update probabilities as if all draws in a sweep were independent, or as if every update used the old state, can produce an incorrect kernel. Follow the actual order, condition later updates on the states they receive, and retain dependencies created by shared random draws.

Check Your Understanding

Answer each question, then compare with the solutions below.

In a two-step sweep, \(X\) is updated first and \(Y\) second. Why must the second update use the intermediate state when forming the full-sweep kernel?
Using the binary example, calculate the probability of ending at \((1,1)\) from a current state with \(y=1\) under the \(X\)-then-\(Y\) order.
Why are two marginal transition probabilities insufficient to determine the joint transition law of two imputed cells?
A procedure uses the previous sweep’s parameter draw again, but that draw is not included in \(z\). What may fail, and what is one possible remedy?
Does defining a valid full-sweep kernel establish that the FCS chain converges? Explain briefly.

Solutions. (1) The second update conditions on the state after the first update, so the composition must integrate over that intermediate state; using the old state would describe a different algorithm. (2) With \(y=1\), \(P(X'=1)=a_1=0.80\), and then \(P(Y'=1\mid X'=1)=b_1=0.70\). Thus the probability is \(0.80\times0.70=0.560\). (3) Marginals do not specify dependence. A shared parameter draw, for example, can make two values dependent even when they are conditionally independent given that parameter. (4) The next-state law may depend on history beyond \(z\), so \(z\) alone may not be Markov. Include the persistent parameter in an enlarged state, or otherwise formulate the transition to account for it. (5) No. A kernel describes one-step transition probabilities; convergence requires additional analysis.