Minimax Binary Counting under Shuffle Privacy: Poisson Limits and Randomized-Response Optimality

arXiv:2603.10073v2 Announce Type: replace-cross Abstract: We study estimation of a deterministic binary count from the shuffled outputs of a common single-message local channel. Privacy is required for every neighboring composition at fixed global parameters $(\varepsilon,\delta)$, and estimators may be biased. We obtain uniform critical Poisson and Skellam approximations and characterize the limiting minimax risk as an infimum over finite observed-mark Poisson experiments. Let $\Lambda$ be the noise intensity required by the boundary Poisson-shift profile and let $\lambda_{\min}$ be the intensity required by the full composition-maximized randomized-response profile. Binary randomized response is asymptotically minimax optimal if and only if $\Lambda=\lambda_{\min}$. When $\Lambda