Theorem E.5 — exact Markov criterion and linear seed bound

For every finite Markov chain $M$ with a nonempty state set, arbitrary nonnegative real initial and transition weights, and normalized probability laws, exact sampling of every complete trajectory law by polynomial-size constant-depth circuits supplied with finitely many fair bits is possible if and only if every finite path probability is dyadic. Length-zero paths are included, so initial probabilities are part of this condition.

Whenever this condition holds, there exist natural constants $D,C,k$ depending only on $M$, such that at every length $n\ge0$ an exact sampler has depth at most $D$, size at most $C(n+1)^k$ and at most $C(n+1)$ fair bits. Exactness requires every output to encode a trajectory and the probability of each full trajectory to match its Markov probability.

This statement groups the equivalence in Theorem E.5 together with its linear seed guarantee, stated in the motivation of Appendix E and established by its sufficiency construction. Both components are required for this milestone.