Private Histograms

A histogram is one of the simplest ways to summarise a population: count how many people fall into each age group, salary bracket, or medical category, then plot the bars. The shape tells a real story — but behind every bar is a list of actual people.

Even a count can be a secret. If a hospital releases "3 patients aged 85–90 were treated for condition X," and you already know two of them, you have just learned something the third person never consented to share. The problem is not the chart — it is that a single person's presence or absence changes the numbers by a detectable amount.

Differential privacy, formalised by Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith in 2006, offers a precise solution: add carefully calibrated random noise to every count before releasing it. The result is a histogram that is statistically useful yet mathematically guarantees that no individual's data can be reliably inferred. Understanding why requires only the Laplace distribution and a single Greek letter — $\varepsilon$.

The demo below shows a synthetic dataset of 200 people grouped into eight age bins. The True bars are the raw counts; the Noisy bars have independent Laplace noise added to each bin. Use the $\varepsilon$ slider to control the privacy budget: smaller $\varepsilon$ means stronger privacy (more noise); larger $\varepsilon$ means less noise and a more accurate release.

<!-- {{c_intro}} -->
<div class="controls">
  <label for="eps-slider">{{label_epsilon}} <strong id="eps-val">1.0</strong></label>
  <input id="eps-slider" type="range" min="0.1" max="3" step="0.1" value="1.0" />
  <button id="resample" type="button">{{btn_resample}}</button>
</div>
<div class="legend">
  <span class="dot true-dot"></span> {{legend_true}}
  <span class="dot noisy-dot"></span> {{legend_noisy}}
</div>
<div id="chart" class="chart" aria-label="{{chart_aria}}"></div>
<p class="status" id="status">{{status_init}}</p>

/* {{c_layout}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; padding: .5rem; }
.controls { display: flex; align-items: center; gap: .7rem; flex-wrap: wrap; margin-bottom: .6rem; }
label { font-size: .9rem; color: #444; }
input[type=range] { width: 160px; cursor: pointer; }
button { font: 600 13px system-ui; padding: .35rem .8rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button:hover { background: #162a43; }
.legend { display: flex; align-items: center; gap: 1rem; font-size: .82rem; color: #555; margin-bottom: .5rem; }
.dot { width: 12px; height: 12px; display: inline-block; border-radius: 2px; }
.true-dot  { background: #457b9d; }
.noisy-dot { background: #e9c46a; }
/* {{c_chart}} */
.chart { display: flex; align-items: flex-end; gap: 4px; height: 200px; border-bottom: 2px solid #ccc;
         padding-bottom: 0; margin-bottom: .4rem; }
.bin-group { display: flex; flex-direction: column; align-items: center; flex: 1; }
.bars { display: flex; align-items: flex-end; gap: 2px; height: 100%; }
.bar { flex: 1; min-width: 10px; transition: height .3s ease; border-radius: 3px 3px 0 0; }
.bar.true-bar  { background: #457b9d; }
.bar.noisy-bar { background: #e9c46a; }
.bin-label { font-size: .65rem; color: #666; margin-top: .25rem; text-align: center; }
.status { font-size: .85rem; color: #555; margin: .4rem 0 0; min-height: 1.3em; }

// Code not found

Notice that even at strong privacy ($\varepsilon = 0.5$) the noisy histogram still roughly tracks the true shape — the tallest bars stay roughly tallest. That is the promise of differential privacy: the signal survives the noise at the population level, even though any individual bar can be off by dozens of counts.

The guarantee behind private histograms rests on three ideas.

Global sensitivity. For a single histogram bin, changing one person's data can alter the count by at most 1. That maximum change is called the global sensitivity $\Delta = 1$.

The Laplace mechanism. To release a count $c$, add a random variable drawn from a Laplace distribution with mean 0 and scale $b = \Delta / \varepsilon$:

$$\tilde{c} = c + \mathrm{Lap}\!\left(\frac{1}{\varepsilon}\right)$$

Each bin gets its own independent sample, so the noise on one bar tells you nothing about another.

The formal privacy guarantee. Let $D$ and $D'$ be any two datasets that differ in exactly one person. For any set $S$ of possible outputs, the mechanism satisfies:

$$\Pr[\mathcal{M}(D) \in S] \;\leq\; e^{\varepsilon} \cdot \Pr[\mathcal{M}(D') \in S]$$

This is $\varepsilon$-differential privacy. The ratio $e^{\varepsilon}$ bounds how much more likely any output is under one dataset versus the other — and with $\varepsilon = 1$, that factor is only about 2.7. Smaller $\varepsilon$ tightens the bound; larger $\varepsilon$ loosens it.

The accuracy–privacy trade-off is unavoidable: you cannot simultaneously achieve perfect accuracy and perfect privacy. But the Laplace mechanism hits the optimal trade-off for counting queries — no other mechanism with the same $\varepsilon$ guarantee can do better on average. This result, proved by Ghosh, Roughgarden, and Sundararajan (2012), shows the mechanism is not just sufficient but optimal.

Private histograms sit at the heart of several real systems you interact with every day:

• US Census 2020: the Census Bureau applied differential privacy to the entire population count, adding Laplace-style noise to protect individual households while still publishing accurate state-level totals.
• Apple and Google telemetry: both companies use local differential privacy — a variant where noise is added on-device before any data leaves your phone — to collect keyboard usage and emoji frequency histograms without seeing raw keystrokes.
• Medical research: hospitals can share age-stratified infection rates across institutions without any single patient's record being identifiable in the released table.
• Ad measurement: advertising platforms release histogram data about which demographics saw an ad without tying clicks back to individuals.

The same Laplace mechanism extends to randomised response, range queries, and machine learning with private gradient histograms. Every time a company claims "privacy-preserving statistics," it almost certainly relies on ideas that trace back to this simple noise-addition trick.

Private histograms are proof that privacy and utility are not opposites — they are a trade-off you can tune with a single number, $\varepsilon$. Add Laplace noise scaled to $1/\varepsilon$, and you transform an exact count into a release that is mathematically guaranteed to conceal any individual, while still letting the population-level shape shine through.

The next time an app says it "collects anonymous statistics," ask whether that anonymity comes with a proof or just a promise. Differential privacy with the Laplace mechanism is one of the few approaches that comes with both — a rigorous guarantee and a practical implementation simple enough to fit in a single formula.