Why Initial Randomness Matters in Parallel Markov Sampling

Parallel sampling aims to accelerate sequence generation by filling multiple positions per round. Yet even when every conditional distribution is known exactly, the choice of when to sample each position can limit the accuracy achievable within a fixed number of rounds. In our work, we show that randomizing the first set of sampled positions can achieve accuracy beyond every deterministic adaptive schedule for known stationary Markov targets, without increasing the round budget. Our samplers draw coordinate values independently within each batch from exact single-coordinate conditional distributions, never revise sampled values, and use at most $R$ rounds on every path. We establish this advantage for every reversible finite-state Markov chain with strictly positive transition probabilities and dependence between successive states. For each such chain, under a suitable scaling of sequence length and round budget, initial randomization yields vanishing total variation error, while the optimal deterministic adaptive error remains bounded away from zero. To quantify this advantage in forward KL divergence, we obtain matching bounds for positively correlated binary chains: over the full adaptive policy classes, randomization reduces the optimal divergence from the target to the output distribution by a factor of order $2^{R-1}$ in a fixed-kernel, bounded-error regime. To determine whether this randomness can be deferred, we specialize further to the symmetric binary chain in this regime and characterize how the entropy of the first-round position set controls optimal error. Attaining the optimal randomized error order requires at least $R-1-O(1)$ bits of this entropy, even with unrestricted later scheduling randomness and adaptation to sampled values: this initial randomness cannot be deferred.