Learning Sparse Distributions through Arbitrary Local Markov Corruption

We give a proper learner for arbitrary sparse distributions on Boolean strings observed after a known continuous-time Markov process. Each supplied rational update reads and rewrites at most a fixed number of coordinates, and the total update rate incident to each coordinate is bounded. Updates may overlap, fail to commute, be state-dependent, or be irreversible. For every fixed known rational duration and fixed locality, the sample complexity and worst-case bit time are polynomial in ambient dimension and inverse accuracy, quasipolynomial in the support bound k, and polynomial in input encoding length and logarithmic confidence. No minimum atom weight, separation, stationary law, geometric structure, bounded unweighted degree, or lower bound on local transition probabilities is required. The output is a proper distribution on at most k complete n-bit strings with dyadic weights. A local-observable theorem applies to arbitrary initial laws, using exp(O(m)) times polynomial-in-accuracy observations for bounded m-coordinate functions. Its proof combines dimension-free local analytic estimates with stable repeated extrapolation and classical forward simulation from observed strings. Ridge whitening, sequential classical projection, and regularized coordinate leverage sampling give sparse reconstruction. Deterministic initial states admit optimal logarithmic-sample recovery. The generator and all final coordinates are supplied; unknown generators, unobserved outputs, growing duration/locality, and polynomial dependence on k are outside the claimed scope. The paper explains its relationship to the author's specialized joint-polynomial random-transposition and Mallows population-recovery results.