Estimating the True Distribution of Data Collected with Randomized Response

Carlos Antonio Pinzón 1 , Ehab ElSalamouny 1,5 , Lucas Massot 3 , Alexis Miller 4 , Héber Hwang Arcolezi 2 , Catuscia Palamidessi 1 1 INRIA Saclay, France 2 INRIA Grenoble, France 3 École Polytechnique, France 4 Ecole Normale Supérieure de Lyon, France 5 Suez Canal University, Egypt · 2026

Read Estimating the True Distribution of Data Collected with Randomized Response by Carlos Antonio Pinzón 1 , Ehab ElSalamouny 1,5 , Lucas Massot 3 , Alexis Miller 4 , Héber Hwang Arcolezi 2 , Catuscia Palamidessi 1 1 INRIA Saclay, France 2 INRIA Grenoble, France 3 École Polytechnique, France 4 Ecole Normale Supérieure de Lyon, France 5 Suez Canal University, Egypt (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-08603.txt.

Introduction

Carlos Antonio Pinzon and co-authors estimate true data distributions collected under randomized response. Their 2026 arXiv paper studies a protocol for categorical data with local differential privacy guarantees. Randomized response lets people answer surveys while plausibly denying their true answer. Big technology companies have used it as a building block for collecting app and web user data. Recovering the true distribution from noisy responses is the statistical core. Better estimators mean firms can learn population trends without learning any person's answer.

Catalog record

CREATORCarlos Antonio Pinzón 1 , Ehab ElSalamouny 1,5 , Lucas Massot 3 , Alexis Miller 4 , Héber Hwang Arcolezi 2 , Catuscia Palamidessi 1 1 INRIA Saclay, France 2 INRIA Grenoble, France 3 École Polytechnique, France 4 Ecole Normale Supérieure de Lyon, France 5 Suez Canal University, Egypt
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE58 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-08603

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Estimating the True Distribution of Data Collected with Randomized Response Carlos Antonio Pinzón 1 , Ehab ElSalamouny 1,5 , Lucas Massot 3 , Alexis Miller 4 , Héber Hwang Arcolezi 2 , Catuscia Palamidessi 1 1 INRIA Saclay, France 2 INRIA Grenoble, France 3 École Polytechnique, France 4 Ecole Normale Supérieure de Lyon, France 5 Suez Canal University, Egypt Abstract Randomized Response (RR) is a protocol designed to collect and analyze categorical data with local differential privacy guarantees. It has been used as a building block of mechanisms deployed by Big tech companies to collect app or web users’ data. Each user reports an automatic random alteration of their true value to the analytics server, which then estimates the histogram of the true unseen values of all users using a debiasing rule to compensate for the added randomness. A known issue is that the standard debiasing rule can yield a vector with negative values (which can not be interpreted as a histogram), and there is no consensus on the best fix. An elegant but slow solution is the Iterative Bayesian Update algorithm (IBU), which converges to the Maximum Likelihood Estimate (MLE) as the number of iterations goes to infinity. This paper bypasses IBU by providing a simple formula for the exact MLE of RR and compares it with other estimation methods experimentally to help practitioners decide which one to use. 1 Introduction Local differential privacy (LDP) [ 9 ] is a framework for providing privacy guarantees when collecting data from a set of users. It removes the need for trust in the correct management of whoever collects the data and is typically used for automated telemetry. The essence of LDP is to introduce controlled uncertainty right before the users transmit their data to avoid the data collector from receiving the exact specific information of each user. The level of uncertainty or noise introduced by LDP is controlled by a parameter \epsilon>0 , varying from a high privacy regime with \epsilon\approx 0 (large uncertainty) to a low privacy regime with \epsilon\gg 1 (low uncertainty). The organization that collects and processes the data can not be certain about the specifics of any user in particular, but it can still derive statistical estimations. These estimations become more precise as \epsilon increases and as the size of the user group grows. One of the simplest and most fundamental LDP mechanisms is the Randomized Response [ 16 ] (also called K -ary RR, kRR, or simply RR), introduced firstly without any connection to LDP in [ 21 ] . In a nutshell, RR reports either the truth with some fixed probability or a random value, picked uniformly. Despite its simplicity, RR has been the subject of extensive research as it is the building block of more advanced mechanisms like Symmetric Unary Encoding and Local Hashing [ 20 ] as well as longitudinal protocols, e.g. RAPPOR [ 13 ] , d-bitFlipPM [ 7 ] , Longitudinal Local Hashing [ 3 ] . Moreover, RR is known to be optimal among all LDP mechanisms for small domains or large values of \epsilon . Namely, whenever the domain size K satisfies K<3e^{\epsilon}+2 [ 20 ] . Large values of \epsilon are particularly relevant in light of recent advances in Shuffle differential privacy [ 12 , 5 ] , where a shuffler is applied after local randomization to strip metadata and randomly permute the reports. This added layer of anonymity enables privacy amplification, meaning that stronger central-DP guarantees can be achieved from weaker local ones. The growing use of Shuffle DP in real-world scenarios heightens the importance of high \epsilon regimes, and therefore, of RR. Concerning statistical estimations, we focus on estimating the original data distribution, which is arguably the most fundamental statistic. To this purpose, typically the analytics server constructs a histogram of reported data, normalizes it to obtain a distribution, and uses a debiasing linear correction rule ( Inv ) to compensate for the added noise. The resulting vector is proven to be unbiased, but it may not be a valid distribution, as it may have some negative entries. Method Complexity Justification Debiasing Inv O(K) ✓ Unbiased, but invalid Neg. fix InvN O(K) Workaround: simple Proj. fix InvP O(K\log K) Workaround: close to Inv Bayesian IBU O(K\,{N_{\text{iters}}}) ✓ MLE when {N_{\text{iters}}}\to\infty Proposed MLE* O(K\log K) ✓ MLE in one step Table 1: Methods for estimating the original distribution from RR observations. {N_{\text{iters}}} represents the number of iterations, which depends on the desired precision. In order to obtain a distribution, two simple workarounds have been proposed. The first, InvN , sets to 0 all the negative entries of the vectors, and renormalizes it. The second, InvP , projects the vector on the closest point on the simplex in terms of Euclidean distance. A different approach, called iterative Bayesian update (IBU), was proposed by [ 1 ] . IBU produces an estimate of the original distribution using an iterative algorithm that converges to the maximum likelihood estimate (MLE) as the number of iterations grows [ 10 ] . In this sense, IBU is well justified mathematically. However, the asymptotic nature of the algorithm makes it less attractive. Another drawback is the missing theory about the number of iterations or the stop condition that guarantees a certain proximity to the MLE. Our first objective is to enhance the efficiency of MLE computation. To this aim, we propose MLE* , based on a mathematical formula that can be computed quickly, and which provides the exact MLE, thus bypassing the issue about the stop condition. The second objective is to compare these estimators. One may think that, since the MLE is the “most likely” estimate, it would also be the most precise. Furthermore, the MLE is known to minimize the Kullback-Leibler divergence between the empirical distribution (i.e., the normalized histogram output by RR) and the ideal distribution, obtained by multiplying the input distribution by the channel matrix that represents the RR noise. However, for practical purposes, the Kullback-Leibler divergence may not be the most important utility metric. Indeed, the precision of an estimation is typically measured in terms of mean square error (MSE). In this paper, we compare the MSE precision of the MLE, InvN and InvP . It turns out that, surprisingly, the precision of InvN and InvP “flip” depending on the distribution being more or less concentrated, while that of the MLE is always in between. Other important terms of comparisons we investigate in this paper are efficiency, consistency, and unbiasedness. The methods that we consider are summarized in Table 1 . In summary, the contributions of this paper are: 1. We provide a simple formulation for the MLE, prove its correctness formally, and validate it empirically. These formulas coincide with [ 16 ] , Supplementary Material, Section F. 2. We propose an algorithm that computes the MLE and is significantly more efficient than the state-of-the-art solution (IBU). In addition, our algorithm gives an exact solution, whereas IBU provides only an approximation because the number of iterations is necessarily finite. 3. We theoretically and experimentally compare MLE with other estimation methods to clarify their trade-offs, with the objective to help developers choose which one to use. 2 Preliminaries This section

Read the complete text