  Exponential histograms, with bins of the form $\left\{
\left(\rho^{k-1},\rho^{k}\right]\right\} _{k\in\mathbb{Z}}$, for $\rho>1$,
straightforwardly summarize the quantiles of streaming data sets (Masson et al.
2019). While they guarantee the relative accuracy of their estimates, they
appear to use only $\log n$ values to summarize $n$ inputs. We study four
aspects of exponential histograms -- size, accuracy, occupancy, and largest gap
size -- when inputs are i.i.d. $\mathrm{Exp}\left(\lambda\right)$ or i.i.d.
$\mathrm{Pareto}\left(\nu,\beta\right)$, taking
$\mathrm{Exp}\left(\lambda\right)$ (or,
$\mathrm{Pareto}\left(\nu,\beta\right)$) to represent all light- (or, heavy-)
tailed distributions. We show that, in these settings, size grows like $\log n$
and takes on a Gumbel distribution as $n$ grows large. We bound the missing
mass to the right of the histogram and the mass of its final bin and show that
occupancy grows apace with size. Finally, we approximate the size of the
largest number of consecutive, empty bins. Our study gives a deeper and broader
view of this low-memory approach to quantile estimation.
