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

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 $(\epsilon ,\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 <{\lambda }_{\min }$, the minimax value lies strictly between $(\Lambda +{\lambda }_{\min })/2$ and ${\lambda }_{\min }$, and a randomized-response construction with observed rare marks strictly improves on binary randomized response. We give a finite-sample certified example. Binary randomized response is strictly suboptimal at $\epsilon =0$ for every $0<\delta <1$, and this persists for sufficiently small positive $\epsilon$ at each fixed target. For every fixed positive $\epsilon$, strict suboptimality also occurs along a sequence of fixed privacy targets tending to zero. The variational characterization permits approximation by finite marked channels; it does not assert that a finite optimizer exists.

arXiv comment39 pages, 1 figure. v2: complete revision with a new title and scope; it replaces v1 entirely. The two-dominant hybrid argument of v1 is withdrawn (see the Introduction). Ancillary files contain the certificate scripts for Proposition 10.1