Polynomial Learning of Arbitrary Mallows Mixtures at Every Fixed Noise Level

We give a randomized algorithm for learning arbitrary finite mixtures of Kendall–Mallows distributions at every fixed known rational dispersion q in (0,1). For a mixture of at most k components on n items, with all positive component weights at least gamma, the algorithm recovers every central permutation exactly and estimates the weights to l1 error epsilon with probability at least 1-delta. Both sample complexity and worst-case bit complexity are polynomial in n, k, 1/gamma, 1/epsilon, and log(1/delta), with an exponent depending only on q. No separation between centers or prior knowledge of the support is required. The proof combines a uniformly bounded signed inverse for an arbitrary rank-cut shuffle with an exponentially accurate test based on spaced prefix sets. The inverse follows from an exact connected-interval expansion in the symmetric-group algebra; the test follows from independent local orders and insertion-length tail bounds. Together with the deterministic attenuated interpolation theorem of De, Saks, and Tang, these ingredients yield a weight oracle and a complete prefix-by-prefix support recovery algorithm. This extends the author's fixed-low-noise result (DOI: 10.5281/zenodo.23484943) to every fixed q<1. The theorem retains a known common dispersion and a supplied positive component-weight lower bound; its polynomial degree may depend on q.