Theorem E.5 — exact Markov sampling iff path-dyadic

For every nonempty finite Markov chain $M$ with arbitrary nonnegative real transition probabilities and normalized initial and transition laws, the family of complete trajectories $(X_0,\ldots,X_n)$ has exact randomized $\mathrm{AC}^0$ samplers of polynomial size in $n+1$ and depth uniformly bounded independently of $n$ if and only if every finite trajectory probability is dyadic. This includes $n=0$. All random seeds must encode valid trajectories. The condition concerns complete path probabilities, rather than entrywise dyadicity of the original transition matrix.