Near-Optimal Estimation and Inference for Distribution Functions under Local Differential Privacy

We estimate population cumulative distribution functions under local differential privacy using independent cycles of dyadic optimized unary encoding reports. An exact grid-approximation modulus yields continuous uniform risk of order $\frac{(\log n{)}^{3/2}}{\tanh (ϵ/2)\sqrt{n}}$ under public Hölder regularity. An interactive lower bound establishes optimality up to logarithmic factors on a bounded-density class for $0<ϵ\le 1$. Total-mass-constrained least-squares reconstruction with a symmetric monotone envelope retains this rate. We further establish conditions for studentized pointwise Gaussian limits and construct ordered simultaneous bands with finite-sample or asymptotic coverage guarantees. Ordering band endpoints preserves coverage, whereas recentering pointwise intervals at a monotone estimate can fail. Across four simulated distributions at $ϵ=1$ and $n\approx 8.4\times 10^6$, the least-squares estimator reduces mean uniform error by 47–50% relative to one-bit current-status estimation based on Liu, Hu, and Kong (2024). Fixed-grid inference experiments show a 40–43% reduction in mean band width on identical reports.