Spatial Privacy & Anonymization Engineering

Implementing Randomized Response for Location Check-ins

Encode each check-in into a fixed H3 cell alphabet, keep the true cell with probability p=eε/(eε+d−1)p = e^{\varepsilon}/(e^{\varepsilon}+d-1) (otherwise report a random cell), and recover unbiased per-cell frequencies on the server with c^v=(c~v−nq)/(p−q)\hat{c}_v = (\tilde{c}_v - nq)/(p-q) — sizing the user count against the variance formula so your target error bound is actually met.

This is the concrete, single-mechanism recipe behind local differential privacy for mobile clients: the raw check-in coordinate never leaves the device, and the aggregator only ever sees randomized cells. A check-in is the ideal fit for randomized response because it is naturally discrete — a user is “at” one venue or map cell at a time, so the reporting domain is a finite alphabet of cells rather than a continuous coordinate. That discreteness is exactly what lets the server invert the randomization into an unbiased frequency estimate, which a continuous perturbation such as geo-indistinguishability cannot do directly. The whole design reduces to three numbers you must get right: the local budget ε\varepsilon, the alphabet size dd, and the user population nn.

Core Calculation permalink

Flip probabilities from epsilon permalink

Generalized randomized response over a dd-cell alphabet keeps the true cell with probability pp and otherwise reports one of the d−1d-1 other cells uniformly, each with probability qq:

p=eεeε+d−1,q=1eε+d−1=1−pd−1p = \frac{e^{\varepsilon}}{e^{\varepsilon} + d - 1}, \qquad q = \frac{1}{e^{\varepsilon} + d - 1} = \frac{1 - p}{d - 1}

Unbiased estimator permalink

The observed count c~v\tilde{c}_v of reports naming cell vv is inflated by lies from the other cells. Inverting the randomization gives an exactly unbiased count and frequency:

c^v=c~v−n qp−q,f^v=c^vn\hat{c}_v = \frac{\tilde{c}_v - n\,q}{p - q}, \qquad \hat{f}_v = \frac{\hat{c}_v}{n}

Variance and required n permalink

For a cell in the low-frequency regime, the estimator’s variance and standard error are:

Var⁡[f^v]≈d−2+eεn (eε−1)2,SE=Var⁡[f^v]\operatorname{Var}[\hat{f}_v] \approx \frac{d - 2 + e^{\varepsilon}}{n\,(e^{\varepsilon} - 1)^2}, \qquad \mathrm{SE} = \sqrt{\operatorname{Var}[\hat{f}_v]}

Solving for the population needed to hit a target standard error σ⋆\sigma^\star:

n≥d−2+eε(σ⋆)2 (eε−1)2n \geq \frac{d - 2 + e^{\varepsilon}}{(\sigma^\star)^2\,(e^{\varepsilon} - 1)^2}

Parameter reference permalink

Symbol Meaning Example value
ε\varepsilon Local privacy budget per report 2
dd Cell alphabet size 100
pp Truthful probability 0.0695
qq Per-other-cell lie probability 0.00942
nn Number of users / check-ins 10 000
σ⋆\sigma^\star Target standard error 0.01

Worked numeric example permalink

Take ε=2\varepsilon = 2, a d=100d = 100 cell alphabet, and n=10,000n = 10{,}000 check-ins. With e2≈7.389e^{2} \approx 7.389:

p=7.3897.389+99=7.389106.389≈0.0695p = \frac{7.389}{7.389 + 99} = \frac{7.389}{106.389} \approx 0.0695
q=1106.389≈0.00940q = \frac{1}{106.389} \approx 0.00940
Var⁡[f^v]≈100−2+7.38910,000×(7.389−1)2=105.38910,000×40.82≈2.58×10−4\operatorname{Var}[\hat{f}_v] \approx \frac{100 - 2 + 7.389}{10{,}000 \times (7.389 - 1)^2} = \frac{105.389}{10{,}000 \times 40.82} \approx 2.58 \times 10^{-4}
SE≈2.58×10−4≈0.0161\mathrm{SE} \approx \sqrt{2.58 \times 10^{-4}} \approx 0.0161

So at 10 000 users each cell frequency carries roughly a ±1.6\pm 1.6 percentage-point standard error. To tighten that to σ⋆=0.01\sigma^\star = 0.01:

n≥105.389(0.01)2×40.82=105.3890.004082≈25,820 usersn \geq \frac{105.389}{(0.01)^2 \times 40.82} = \frac{105.389}{0.004082} \approx 25{,}820 \text{ users}

Reaching a one-percentage-point error needs about 2.6× the 10 000-user pilot — a direct illustration of the 1/n1/\sqrt{n} scaling that governs every local-model deployment.

Two facts fall out of this example that are worth internalizing before you write any code. First, the keep probability p≈0.0695p \approx 0.0695 is tiny: at a 100-cell alphabet and ε=2\varepsilon = 2, an individual device tells the truth only about 7% of the time, and the remaining 93% is uniform noise. No single report is informative — utility comes entirely from aggregating tens of thousands of them. Second, the variance is dominated by the alphabet term dd far more than by eεe^{\varepsilon} in this regime: doubling the cell count from 100 to 200 nearly doubles the required nn, whereas raising ε\varepsilon from 2 to 3 (a meaningful privacy relaxation) barely moves it. The practical lesson is to keep the reporting alphabet as small as the analysis will tolerate, and to spend extra population budget on resolution only where the map genuinely needs it.

Python Implementation permalink

The block below runs the whole loop: encode a WGS84 check-in to an H3 cell, randomize on the device at the target ε\varepsilon, then aggregate and de-bias server-side. It uses numpy, pandas, and the h3 v4 API.

from __future__ import annotations
import h3          # h3 v4 API
import numpy as np
import pandas as pd
from typing import Sequence

H3_RESOLUTION: int = 8  # ~0.46 km^2 hexes; res sets the alphabet size d


def encode_checkin(lat: float, lon: float, alphabet: Sequence[str]) -> int:
    """Map a WGS84 (EPSG:4326) check-in to an index in the shared H3 alphabet.

    The raw coordinate is used only on the device. The final alphabet slot is
    an 'other' bucket so every real-world cell maps somewhere and the domain
    size d stays fixed -- a precondition for exact de-biasing.
    """
    cell = h3.latlng_to_cell(lat, lon, H3_RESOLUTION)
    return alphabet.index(cell) if cell in alphabet else len(alphabet) - 1


def randomize_checkin(true_index: int, epsilon: float, d: int,
                      rng: np.random.Generator) -> int:
    """Generalized randomized response over a d-cell alphabet.

    Keeps the true cell with p = e^eps / (e^eps + d - 1); otherwise reports a
    uniformly random *different* cell. The output alone satisfies epsilon-local
    differential privacy, so a single check-in is deniable and the raw location
    cannot be recovered from it.
    """
    p_keep = np.exp(epsilon) / (np.exp(epsilon) + d - 1)
    if rng.random() < p_keep:
        return true_index                      # truthful report
    other = int(rng.integers(0, d - 1))        # uniform over the d-1 others
    return other if other < true_index else other + 1


def debias_counts(reports: np.ndarray, epsilon: float, d: int) -> pd.DataFrame:
    """Recover unbiased per-cell frequencies from randomized check-ins.

    Applies c_hat = (observed - n*q) / (p - q), which is exactly unbiased for
    the true per-cell count. Negative de-biased frequencies (noise around empty
    cells) are clipped to zero -- valid post-processing that keeps the DP
    guarantee intact.
    """
    n = reports.size
    p = np.exp(epsilon) / (np.exp(epsilon) + d - 1)
    q = 1.0 / (np.exp(epsilon) + d - 1)

    observed = np.bincount(reports, minlength=d).astype(float)
    debiased = (observed - n * q) / (p - q)
    return pd.DataFrame({
        "cell_index": np.arange(d),
        "debiased_freq": np.clip(debiased / n, 0.0, None),
    })

Note that randomize_checkin runs on the handset; only its integer output is uploaded. The server calls debias_counts on the collected reports and never touches a raw coordinate. Three implementation details carry the privacy guarantee. The p_keep comparison against a single uniform draw is the entire mechanism — there is no seed shared with the server, so the operator cannot reverse a specific device’s coin flip. The other if other < true_index else other + 1 idiom draws uniformly from the d−1d-1 non-true cells without ever materializing the true index in the output when the lie branch is taken. And debias_counts subtracts exactly nqnq, the expected number of spurious reports each cell receives from the lie branch, which is what makes E[c^v]=cv\mathbb{E}[\hat{c}_v] = c_v hold precisely rather than approximately.

If you later move this to production, the client function is what ships inside the mobile app, ideally in a shared native library so the flip probabilities cannot drift, while debias_counts runs in the ingestion pipeline. The one invariant both sides must share is the ordered alphabet and its length dd; everything else is derived from ε\varepsilon and dd at call time.

Verification permalink

Simulate a known ground-truth distribution, push every user through the encode-randomize-debias loop, and confirm the recovered frequencies fall within the error predicted by the variance formula.

def verify(true_freq: np.ndarray, epsilon: float, n_users: int,
           seed: int = 0) -> dict:
    """Confirm unbiased recovery and that error tracks the theoretical SE."""
    rng = np.random.default_rng(seed)
    d = true_freq.size

    true_cells = rng.choice(d, size=n_users, p=true_freq)          # ground truth
    reports = np.fromiter(
        (randomize_checkin(int(c), epsilon, d, rng) for c in true_cells),
        dtype=np.int64, count=n_users,
    )
    est = debias_counts(reports, epsilon, d)["debiased_freq"].to_numpy()

    theo_se = np.sqrt((d - 2 + np.exp(epsilon)) /
                      (n_users * (np.exp(epsilon) - 1) ** 2))
    return {
        "mean_abs_error": float(np.mean(np.abs(est - true_freq))),
        "theoretical_se": float(theo_se),
    }


# Worked example: d=100, eps=2, n=10_000 -> theoretical SE ~ 0.0161
rng = np.random.default_rng(7)
tf = rng.dirichlet(np.ones(100))
print(verify(tf, epsilon=2.0, n_users=10_000))
# mean_abs_error should land within ~1x of theoretical_se (~0.016)

If mean_abs_error sits near theoretical_se, the estimator is unbiased and correctly calibrated. A much larger error means nn is too small for the alphabet or the client/server alphabets have drifted apart.

Edge Cases & Adjustments permalink

  • Small nn. Below a few thousand users the de-biased histogram is dominated by noise; the estimator stays unbiased but its variance swamps the signal. Suppress released cells whose de-biased count falls under a documented floor rather than publishing noisy near-zero cells, and re-check the required-nn formula before shipping.
  • Large cell alphabet. Variance grows with dd, so pushing H3 resolution up to sharpen the map inflates the standard error. When dd gets large (d≥3eε+2d \geq 3e^{\varepsilon}+2), switch from direct encoding to RAPPOR-style unary encoding, or report a coarse cell first and refine only well-populated regions.
  • Repeated daily reports (composition). One check-in is ε\varepsilon-LDP, but a user who checks in every day spends ε\varepsilon each time; 30 days at ε=2\varepsilon = 2 composes to ε=60\varepsilon = 60. Memoize a persistent randomized answer per stable location, or track cumulative spend with the privacy-budget accounting used for spatial queries.
  • CRS and H3 resolution. Encode from WGS84 (EPSG:4326) exactly as the device GPS emits it — H3 handles the spherical math, so no reprojection to a metric CRS is needed before indexing. Pin H3_RESOLUTION and the ordered alphabet in a versioned config; a resolution or ordering mismatch between client and server silently corrupts qq and biases every estimate.

FAQ permalink

What local epsilon should I use for location check-ins?

Values between 1 and 3 per report are typical for check-in histograms. Lower ε\varepsilon is more private but needs far more users to reach a usable error bound, as the required-nn formula makes explicit. Whatever you pick, pair it with a per-device composition budget, because repeated check-ins spend ε\varepsilon each time.

How many users do I need for a one-percentage-point error?

Use n≥(d−2+eε)/((σ⋆)2(eε−1)2)n \geq (d - 2 + e^{\varepsilon}) / ((\sigma^\star)^2 (e^{\varepsilon} - 1)^2). For a 100-cell alphabet at ε=2\varepsilon = 2 and σ⋆=0.01\sigma^\star = 0.01, that is about 25,800 users. Halving the target error quadruples the population, so budget users against the accuracy you actually need — see the broader accuracy vs. utility tradeoffs in geospatial DP.

Why can a de-biased cell count come out negative?

The estimator subtracts the expected noise floor nqnq, so genuinely empty cells fluctuate around zero and occasionally land slightly negative. Clipping to zero is valid post-processing that does not weaken the guarantee. Do not read a clipped-to-zero cell as a confirmed absence from a single release.

Does this leak the raw check-in coordinate?

No. Randomization happens on the device before upload, so the aggregator sees only a perturbed cell index. This is what lets the check-in flow support GDPR data-minimisation and de-identification obligations — there is no central store of true locations.

Related

← Back to Local Differential Privacy for Mobile Clients