JSD Bounds for the Shuffle Model: From Binary to k-ary Randomized Response

We establish exact asymptotic formulas for Jensen-Shannon divergence between neighboring datasets in the Shuffle Model of differential privacy. Part I (Binary): For Randomized Response with noise δ ∈ (0, 1/2) and n users:JSD = (1−2δ)² / [8nδ(1−δ)] + O(n⁻²)with exact remainder coefficient c(δ) = (3/64)·(1−2δ)⁴/[δ(1−δ)]². Part II (k-ary): For k-RR with keep probability p ∈ (1/k, 1):JSD = η_k(p) / (8n) + O(n⁻²)where η_k(p) = (q−p)²·(p(k−2)+1) / [(k−1)·p·q], q = (1−p)/(k−1). Key result: Exact relation to channel contraction theory:η_k(p) = η_JSD(W_δ^(k)) · s_k²·(k−1) / [p(1−p)] The leading coefficient equals the JSD contraction coefficient, revealing a fundamental connection between information-theoretic contraction and privacy amplification.