Growing Alphabets in Canonical Shuffle Experiments: Likelihood-Ratio Laws, Estimation Bounds, and Low-Budget Equivariant Design

We study canonical one-step neighboring shuffle experiments for finite-output epsilon_0-LDP d-ary channels along growing alphabets, with frequency estimation and mechanism design under a pairwise chi-squared budget. The pairwise likelihood-ratio law nu_{ab,d} (pushforward of the row ratio under the null row) is the governing invariant: the canonical shuffled histogram experiment is exactly equivalent to the quotient multinomial experiment generated by nu_{ab,d}. Alphabet growth improves canonical shuffled privacy iff the worst pairwise law collapses to delta_1. We prove a sharp pure-LDP endpoint principle for the pairwise chi-squared, construct full-support obstruction families saturating it, and establish a diluting/persistent dichotomy with explicit finite-n hockey-stick bounds. The worst-case pairwise budget chi_*(W) governs a two-regime Assouad lower bound for arbitrary estimators in the i.i.d. multinomial model. Symmetrization reduces the uniform-point Fisher criterion to permutation-equivariant channels. Calibrated GRR is not optimal; in the low-budget regime, augmented GRR is optimal among permutation-equivariant channels.

Paper

Similar papers

© 2026 NYSGPT2525 LLC