# Private and Communication-Efficient Algorithms for Entropy
Estimation00footnotetext: Originally published at the 36th Conference on
Neural Information Processing Systems (NeurIPS 2022). This version corrects
some errors in the original version.

Gecia Bravo-Hermsdorff
Department of Statistics
University College London
<EMAIL_ADDRESS>
Róbert Busa-Fekete
Google Research
<EMAIL_ADDRESS>
Mohammad Ghavamzadeh
Google Research
<EMAIL_ADDRESS>
Andres Muñoz Medina
Google Research
<EMAIL_ADDRESS>
Umar Syed
Google Research
<EMAIL_ADDRESS>

###### Abstract

Modern statistical estimation is often performed in a distributed setting
where each sample belongs to a single user who shares their data with a
central server. Users are typically concerned with preserving the privacy of
their samples, and also with minimizing the amount of data they must transmit
to the server. We give improved private and communication-efficient algorithms
for estimating several popular measures of the entropy of a distribution. All
of our algorithms have constant communication cost and satisfy local
differential privacy. For a joint distribution over many variables whose
conditional independence is given by a tree, we describe algorithms for
estimating Shannon entropy that require a number of samples that is linear in
the number of variables, compared to the quadratic sample complexity of prior
work. We also describe an algorithm for estimating Gini entropy whose sample
complexity has no dependence on the support size of the distribution and can
be implemented using a single round of concurrent communication between the
users and the server. In contrast, the previously best-known algorithm has
high communication cost and requires the server to facilitate interaction
between the users. Finally, we describe an algorithm for estimating collision
entropy that generalizes the best known algorithm to the private and
communication-efficient setting.

##  1 Introduction

Statistical estimation has traditionally focused on minimizing the number of
samples needed to estimate properties of a distribution. In the ‘big data’
era, statisticians and computer scientists have also tried to minimize the
space complexity of estimation algorithms, particularly in the streaming
setting. More recently, the increasing prevalence of mobile computing has led
to a focus on the privacy and communication costs of statistical estimation.
In this paper, we consider the following setting: a set of users each draw one
sample from a distribution, and share information about their sample with a
central server. The central server then uses the collected data to estimate a
property of the distribution. Users are concerned with preserving the privacy
of their sample, and also with minimizing the amount of data that is
transmitted to the server.

For example, consider the problem of detecting fingerprinting on the web. Many
websites track users across the web without their consent by recording
(enough) information about their devices (e.g., installed fonts, operating
system, timezone, etc.), a practice known as “browser fingerprinting”. Entropy
is the standard metric used to quantify the identifiability of the collected
fingerprints. So a private and distributed method for estimating entropy can
be used by a browser to warn users that this covert tracking could occur,
without ever storing the fingerprints themselves.

The study of entropies has an extensive and rich history in mathematics and
sciences. Related quantities called “entropy” appear in many contexts
(thermodynamics, information theory, dynamical systems [36], category theory
[10], etc.). These may be broadly thought as measures of information of a
system or process obeying certain properties, which, in turn, lead to natural
measures of disorder, randomness, outcome diversity, information content,
uniformity, etc.

In this paper, we study private and communication-efficient algorithms for
estimating certain entropies of a distribution. Specifically, we give
algorithms for estimating the following entropies, which are widely-used in
many scientific fields to quantify the uncertainty, diversity and spread of a
discrete distribution:

  * •

Shannon entropy [34], a fundamental quantity in information theory.

  * •

Gini entropy (also known as Tsallis entropy [39] of order 2, or (one minus
the) second frequency moment). Some of its applications include measuring
ecological diversity [35, 29], market competition among firms [23], effective
size of political parties [28], and suitability of features to split on during
decision tree learning [32].

  * •

Collision entropy (also known as Rényi entropy [33] of order 2). Some of its
applications include measuring the quality of random number generators [37],
and determining the number of reads needed to reconstruct a DNA sequence [30].

Our algorithms are implemented in either the non-interactive model (for the
Gini and collision entropies), in which all users simultaneously exchange
information with the server during a single round of communication, or the
(stronger) sequentially interactive model (for the Shannon entropy), in which
the server queries users one at a time, possibly in an adaptive manner [24].
When analyzing the communication complexity of an algorithm, we prove bounds
on the number of bits that each user transmits to the server. However, the
server is allowed to broadcast an arbitrary amount of information to the users
(this is also called the blackboard model [18]), including shared random bits
(also known as the public coin model [1, 2, 25]). When analyzing the privacy
of our algorithms we use the framework of local differential privacy [19],
which ensures that the server learns very little about each user’s data.

###  1.1 Our contributions

  * •

A sequentially interactive $\alpha$-local differentially private algorithm for
estimating the Shannon entropy of a joint distribution on $d$ variables within
$\epsilon d$ error using $\tilde{O}(d/(\alpha^{2}\epsilon^{5}))$ samples and
$O(1)$ bits per sample. Our analysis assumes that each of the $d$ variables
has a constant support size and that their conditional independence graph is a
tree. We also describe algorithms that have better dependence on $1/\epsilon$
in certain special cases, such as when the tree has low diameter or is a
chain. Our algorithms achieve $O(1)$ communication complexity by observing
only two or three of the $d$ variables in any single sample; we call these
_pair_ and _triplet observations_. The only previously known algorithm for
estimating the Shannon entropy of a tree-structured distribution from _pair_
observations is a non-interactive algorithm due to Chow and Liu [13]. We prove
that any non-interactive algorithm requires $\Omega(d^{2})$ _pair_
observations to achieve $O(d)$ error. We also prove that, for any sequentially
interactive algorithm, $\Omega(d/\epsilon)$ pair observations are necessary to
achieve $O(\epsilon d)$ error.

  * •

A non-interactive $\alpha$-local differentially private algorithm for
estimating the Gini entropy of a distribution within $\epsilon$ error using
$O(1/(\alpha^{4}\epsilon^{2}))$ samples, $O(1)$ bits per sample, and
$\tilde{O}(1)$ space. The best previous algorithms [11] either have a sample
complexity that depends on the support size $k$ of the distribution, or are
sequentially interactive, and also require $\Omega(k)$ bits per sample and
$\Omega(k)$ space. Also our error bound holds with high probability instead of
only in expectation.

  * •

A non-interactive $\alpha$-local differentially private algorithm for
estimating the collision entropy of a distribution with support size $k$
within $\epsilon$ error using $\tilde{O}(k^{2}/(\alpha^{4}\epsilon^{2}))$
samples, $O(1)$ bits per sample, and $\tilde{O}(1)$ space. Our algorithm
generalizes the previously best known non-interactive algorithm [37] to the
private and communication-efficient setting.

##  2 Related Work

There is a very extensive literature on distributed statistical estimation
under communication constraints (see [41] for the paper that appears to have
started this thread). Variations on the problem include whether communication
is allowed between users, whether communication happens in one or multiple
rounds, whether there is a shared source of randomness among the users, and
whether communication is limited per-user or only cumulatively across all
users.

Many previous results in this area bound the sample and communication
complexity of estimating the parameters of a distribution $P_{\theta}$, where
$\theta\in\Theta$ (see e.g. [22]). This problem class includes discrete
distribution estimation, where the guarantees are usually stated as bounds on
the relative entropy or total variation distance between the estimated and
true distribution (see e.g. [5]). Other problems of interest are mean
estimation [38] and heavy hitter estimation [4].

There has also been significant interest in differentially private statistical
estimation, and of particular relevance is the work by [3], who gave private
algorithms for estimating certain functionals of a distribution, including the
Shannon entropy. However, they used the central model of differential privacy,
while in this paper we prove guarantees using the (stronger) local model.

##  3 Entropy Measures

The _Shannon_ , _Tsallis_ , and _Rényi_ entropy of a discrete random variable
$X$ are defined as

$\displaystyle\text{(Shannon)}\qquad\qquad H(X)$
$\displaystyle=-\sum_{x}\Pr[X=x]\log\Pr[X=x],$ (1)
$\displaystyle\text{(Tsallis)}\qquad\qquad T_{\gamma}(X)$
$\displaystyle=\frac{1}{\gamma-1}\big{(}1-\sum_{x}\Pr[X=x]^{\gamma}\big{)},$
(2) $\displaystyle\text{(R\'{e}nyi)}\qquad\qquad R_{\gamma}(X)$
$\displaystyle=\frac{1}{1-\gamma}\log\big{(}\sum_{x}(\Pr[X=x])^{\gamma}\big{)},$
(3)

where $\gamma$ in (2) and (3) is a free parameter satisfying $\gamma>0$ and
$\gamma\neq 1$. Both Tsallis and Rényi entropy are generalizations of Shannon
entropy in the sense that $\lim_{\gamma\rightarrow
1}T_{\gamma}(X)=\lim_{\gamma\rightarrow 1}R_{\gamma}(X)=H(X)$.

In this paper, we describe algorithms for estimating the Shannon entropy and
special cases of the Tsallis and the Rényi entropy that are widely used in
many scientific fields: $T_{2}(X)$, also known as the _Gini entropy_ , and
$R_{2}(X)$, also known as the _collision entropy_. Substituting $\gamma=2$
into the definitions above and using the abbreviations $G(X)\equiv T_{2}(X)$
and $C(X)\equiv R_{2}(X)$, we have:

$\displaystyle\text{(Gini)}\qquad\qquad G(X)$ $\displaystyle\equiv
T_{2}(X)=1-\sum_{x}\Pr[X=x]^{2},$ $\displaystyle\text{(Collision)}\qquad\qquad
C(X)$ $\displaystyle\equiv R_{2}(X)=-\log\big{(}\sum_{x}\Pr[X=x]^{2}\big{)}.$

Gini entropy is so-called because it is equivalent to the Gini diversity
index, a statistic proposed by Corrado Gini in 1912 to measure income and
wealth inequality [21]. Collision entropy takes its name from the observation
that if $X$ and $X^{\prime}$ are independent and identically distributed, then
$C(X)=-\log\Pr[X=X^{\prime}]$.

For the problem of estimating Shannon entropy, we specialize to a high-
dimensional setting, where we only observe a pair (or triplet) of the
dimensions at a time. That is, $X$ is a random-vector of $d$ discrete
variables, where $d$ is large, but each $X_{i}$ has a constant support size
(e.g., they are binary), and we only observe two (or three) dimensions per
sample. Without making any assumption about this joint distribution, the
problem is intractable. One of the most common assumptions, which we also
adopt in this work, is that the joint distribution is tree-structured. In this
case, the distribution can be estimated by the celebrated [13] (and optimal
[8]) Chow-Liu algorithm. While the Chow-Liu algorithm requires $\Omega(d^{2})$
pairs observations to estimate the Shannon entropy, our sequential algorithm
requires only $\mathcal{O}(d)$ pairs observations (see Section 5.2 for more
details).

The _joint Shannon entropy_ $H(X_{1},\ldots,X_{d})$ of a set of random
variables $X_{1},\ldots X_{d}$ is the Shannon entropy $H(X)$ of the random
variable $X=(X_{1},\ldots,X_{d})$. We write the abbreviated term _joint
entropy_ when the use of Shannon entropy is obvious from context.

The _mutual information_ between two random variables $X$ and $Y$ and their
_conditional mutual information_ given another random variable $Z$ are defined
as:

$\displaystyle I(X;Y)$ $\displaystyle=H(X)+H(Y)-H(X,Y),$ (4) $\displaystyle
I(X;Y~{}|~{}Z)$ $\displaystyle=H(X,Z)+H(Y,Z)-H(X,Y,Z)-H(Z).$ (5)

##  4 Estimation Algorithms and Evaluation Criteria

A set of $n$ users and a central server cooperate according to the following
protocol to estimate the entropy of a random variable $X$:

  1. 1.

Each user $i\in[n]$ draws an independent sample $x_{i}$ according to the
distribution of $X$.

  2. 2.

For $r$ rounds:

    1. (a)

The server sends information to a subset of the users.

    2. (b)

Those users send (partial) information about their sample back to the server.

  3. 3.

The server outputs an estimate of the Shannon entropy (Algorithms 1, 2, and 4)
or the Gini or collision (Algorithm 5) entropies of $X$.

An _estimation algorithm_ specifies the steps that each user and the server
perform to implement the above protocol. The algorithm is _non-interactive_ if
the protocol consists of a single round in which all users participate. In a
non-interactive algorithm the server cannot adapt its queries to users based
on responses from other users, since the server communicates with all the
users concurrently. An algorithm is _sequentially interactive_ if each round
consists of communication with a single user, who is never contacted again.
Sequential interactivity enables the server to query users adaptively [24].

We evaluate estimation algorithms according to the following criteria:

  * •

_Sample complexity_ : The number of users from whom the server requests data.

  * •

_Space complexity_ : The space used by the server when executing the
algorithm.

  * •

_Communication complexity_ : The maximum number of bits transmitted by any
single user to the server. Note that the amount of information sent by the
server to the users is not counted when determining communication complexity.

  * •

_Privacy_ : Let $x_{i}$ be the sample belonging to user $i$ and $o_{i}$ be the
data observed by the server from user $i$. We say that an algorithm satisfies
_$\alpha$ -local differential privacy_ if

$\Pr[o_{i}\in O~{}|~{}x_{i}=x]\leq e^{\alpha}\Pr[o_{i}\in
O~{}|~{}x_{i}=x^{\prime}]$

for any user $i$, measurable set $O$, and possible sample values
$x,x^{\prime}$.

  * •

_Error_ : The absolute difference between the true entropy of the distribution
and the estimate output by the server.

##  5 Estimating Shannon Entropy of Tree-structured Joint Distributions

In this section we assume that $X=(X_{1},\ldots,X_{d})$ is a vector of $d$
discrete variables, and that the support size of each variable $X_{i}$ is
constant (e.g., each variable is Boolean). We also assume that $X$ has a
_tree-structured_ distribution, which means that there exists a rooted tree
$T$ with $d$ nodes such that for any node $i\in[d]$ we have $\Pr[X_{i}\mid
X_{-i}]=\Pr[X_{i}\mid X_{\mathrm{pa}_{T}(i)}],$ where $X_{-i}=(X_{1},\ldots
X_{i-1},X_{i+1},\ldots,X_{d})$ and the node $\mathrm{pa}_{T}(i)$ is the parent
of node $i$ in tree $T$. If $i$ is the root node, then we define
$\Pr[X_{i}\mid X_{\mathrm{pa}_{T}(i)}]=\Pr[X_{i}]$. Equivalently, a tree-
structured distribution is a Markov random field with a tree as the underlying
undirected graph. Essentially, the tree-structured assumption implies that the
only correlations among the $X_{i}$’s are pairwise correlations. If $T$ is a
chain or a star we say that $X$ is chain-structured and star-structured,
respectively. We will treat these two special cases at the end of this section
(Algorithms 2 and 4, respectively).

###  5.1 Estimating Entropy of a Marginal Distribution When the Support Size
is Small

Before proceeding to describe algorithms for estimating the Shannon entropy of
tree-structured distributions, we use existing results for private
distribution estimation to devise a local differentially private estimator for
the Shannon entropy that is sample and communication efficient when the
support size of the distribution is small (as is the case for the individual
marginals). The server will repeatedly invoke this algorithm as a subroutine
in the sections below.

First we recall that the difference in Shannon entropy of two random variables
can be upper bounded according to Theorem 17.3.3 of [14] as

$|H(X_{\mathbf{p}})-H(X_{\mathbf{p}^{\prime}})|\leq\|\mathbf{p}-\mathbf{p}^{\prime}\|_{1}\log\frac{c}{\|\mathbf{p}-\mathbf{p}^{\prime}\|_{1}}$

where $X_{\mathbf{p}}$ and $X_{\mathbf{p}^{\prime}}$ are two discrete random
variables with support size $c$ and distributions $\mathbf{p}$ and
$\mathbf{p}^{\prime}$. Next, we apply a local differentially private learning
algorithm for discrete distribution due to [4] that learns the parameters of a
discrete distribution with small $L_{1}$ error. The following theorem combines
these two results by using the fact that $x/\log(1/x)\leq 1$ whenever $0<x\leq
1/2$.

######  Theorem 5.1.

For any discrete distribution $X$ with support size $c$ and for any
$1/2\geq\epsilon>0$, there exists an estimator satisfying $\alpha$-local
differential privacy that estimates $H(X)$ within $\epsilon$ error using
$n=O(c^{2}\log\frac{1}{\delta}/(\epsilon^{2}\alpha^{2}))$ samples with
probability $1-\delta$ when $\alpha\in(0,1)$.

This algorithm resulting from Theorem 5.1 can be used to privately estimate
the entropy $H(X_{i})$, mutual information $I(X_{i};X_{j})$, and conditional
mutual information $I(X_{i};X_{j}~{}|~{}X_{k})$ of any variables $X_{i},X_{j}$
and $X_{k}$. This can be done using
$O\left(\frac{\log\frac{1}{\delta}}{\alpha^{2}\epsilon^{2}}\right)$ samples
per estimate and $O(1)$ bits per sample, since each of these variables has
constant support size, and both mutual information and conditional mutual
information can be expressed in terms of entropies (Eqs. (4) and (5)). We call
such an estimate _$(\alpha,\epsilon,\delta)$ -good_.

###  5.2 Our Algorithm for Tree-structured Joint Distributions

Note that the support size of $X$ can be exponential in $d$. In the worst
case, estimating the entropy of a distribution with support size $k$ within
constant error requires $\tilde{\Theta}(k)$ samples [20]. However the tree-
structure of $X$ can be exploited to significantly reduce the sample
complexity. In their seminal paper, Chow and Liu [13] proved the identity

$\displaystyle
H(X)=\sum_{i=1}^{d}H(X_{i})-\max_{T}\sum_{i=1}^{d}I(X_{i};X_{\mathrm{pa}_{T}(i)}),$
(6)

for any tree-structured random variable $X$, where the maximization is taken
over all possible trees connecting the $d$ variables.

Eq. (6) suggests a communication-efficient algorithm for estimating the
entropy of $X$, which is known as the _Chow-Liu algorithm_ : First, estimate
each marginal entropy $H(X_{i})$ and each mutual information $I(X_{i};X_{j})$.
Next, compute a maximum spanning tree on the $d$ variables, where the weight
of each edge $(X_{i},X_{j})$ is the estimate of the mutual information
$I(X_{i};X_{j})$. Finally, plug these estimators into Eq. (6).

The Chow-Liu algorithm requires $\Omega(d^{2})$ samples, since it computes the
mutual information between every pair of variables in order to compute a
maximum spanning tree. However, estimating the right-hand side of Eq. (6) only
requires estimating the _weight_ of the maximum spanning tree, which is
significantly easier than finding the tree itself. Algorithm 1 adapts a
technique from [12] that estimates the weight of the maximum spanning tree of
a graph in time that is sublinear in the number of edges in the graph. The
basic idea is to select nodes of the graph at random and use breadth-first
search to determine the size of each of their connected components if we were
to drop edges that do not meet a weight threshold, short-circuiting the search
when the size becomes too large. These quantities are combined to estimate the
weight of the maximum spanning tree. In our case, an edge weight is a mutual
information between a pair of variables, which we estimate from pair
observations.

Algorithm 1 Shannon entropy estimation for tree-structured distribution

1:Let $M=\left\lceil\frac{2\log c}{\epsilon}\right\rceil$ and
$R=\left\lceil\frac{\log\frac{1}{\delta}}{\epsilon^{2}}\right\rceil$, where
$c$ is an upper bound on the support size of each $X_{i}$.

2:for $m=1,\ldots,M$ do

3: for $r=1,\ldots,R$ do

4: Choose positive integer $Z$ randomly according to $\Pr[Z\geq z]=1/z$.

5: Choose $i^{*}$ uniformly at random from $[d]$.

6: Initialize queue to contain $i^{*}$ and a set $V=\\{i^{*}\\}$.

7: while queue length is non-zero and shorter than
$\min\left\\{\frac{2}{\epsilon},Z\right\\}$ do $\triangleright$ Breadth-first
search

8: Remove $i$ from front of queue and $V=V\cup\\{i\\}$.

9: for $j=[d]\setminus V$ do

10: Server computes
$\left(\alpha,\frac{\epsilon}{2},\frac{\delta}{d^{2}}\right)$-good estimate
$\hat{I}_{ij}$ of $I(X_{i};X_{j})$.

11: (Only compute this estimate once per pair.)

12: if $\hat{I}_{ij}\geq\epsilon m$ then add $j$ to back of queue.

13: if queue length is zero then $\gamma_{mr}\leftarrow 1$ else
$\gamma_{mr}\leftarrow 0$.

14: $\;\hat{\eta}_{m}\leftarrow\frac{d}{R}\sum_{r=1}^{R}\gamma_{mr}$.

15:$\hat{W}\leftarrow\epsilon Md-\epsilon\sum_{m=1}^{M}\hat{\eta}_{m}$

16:Server computes $\left(\alpha,\epsilon,\frac{\delta}{d}\right)$-good
estimate of each marginal entropy $H(X_{i})$.

17:Let $\hat{S}$ be the sum of the marginal entropy estimates.

18:Return $\hat{H}=\hat{S}-\hat{W}$.

######  Theorem 5.2.

Algorithm 1 is $\alpha$-locally differentially private and has $O(1)$
communication complexity. Assume that each $X_{i}$ has constant support size.
The expected number of samples requested by the server is
$O\left(\frac{d\log\frac{d}{\delta}}{\alpha^{2}\epsilon^{5}}\right)$. Let
$\hat{H}$ be the entropy estimate output by the algorithm. If $X$ is tree-
structured, then $|\hat{H}-H(X)|\leq\epsilon d$ with probability $1-\delta$.

###  5.3 Our Algorithm for Chain-structured Joint Distributions

Verma and Pearl [40] observed that if $X$ is chain-structured with chain $T$
then for any triplet $(X_{i}$, $X_{j},X_{k})$, if $X_{k}$ is on the unique
path in $T$ between $X_{i}$ and $X_{j}$, then $I(X_{i};X_{j}|X_{k})=0$. Thus,
for any triplet $(X_{i},X_{j},X_{k})$ in $T$, at least one of
$I(X_{i};X_{j}|X_{k})$, $I(X_{i};X_{k}|X_{j})$, or $I(X_{j};X_{k}|X_{i})$ has
to be zero. This observation alone is not enough to recover the chain, since
the conditional mutual information $I(X_{i};X_{j}|X_{k})$ can also be zero for
$X_{i},X_{j}$ and $X_{k}$ when $X_{k}$ is not on the path between $X_{i}$ and
$X_{j}$ in the chain $T$. Nevertheless, under the mild assumption that the
mutual information $I(X_{i},X_{j})$ between every pair of variables is
distinct, we can recover the chain $T$ by estimating the conditional mutual
information of triplets of variables.

Our algorithm is similar to sorting algorithms such as _mergesort_ [26], which
require $O(d\log_{2}d)$ pairwise comparisons over $d$ items. While we cannot
compare pairs explicitly like in a sorting problem, for any triplet
$(X_{i},X_{j},X_{k})$, we can use their conditional mutual information
estimators to locally decide which “item” is between the other two: i.e.,
$X_{i}\leftrightarrow X_{j}\leftrightarrow X_{k}$, $X_{i}\leftrightarrow
X_{k}\leftrightarrow X_{j}$ or $X_{k}\leftrightarrow X_{i}\leftrightarrow
X_{j}$ in the chain $T$. This suggests our Algorithm 2, which inserts the
variables in a chain one by one in a sequential manner. Algorithm 2 calls
Algorithm 3 as a subroutine that seeks to find the position where to insert.

######  Theorem 5.3.

Algorithm 2 is $\alpha$-locally differentially private and has $O(1)$
communication complexity. The number of samples requested by the server is
$O\left(\frac{d\log\frac{d}{\delta}}{\alpha^{2}\epsilon^{2}}\right)$. Let
$\hat{H}$ be the entropy estimate output by the algorithm. If $X$ is chain-
structured and $|I(X_{i};X_{j})-I(X_{j};X_{k})|\geq\epsilon$, then
$|\hat{H}-H(X)|\leq\epsilon d$ with probability $1-\delta$.

###  5.4 Our Algorithm for Star-structured Joint Distributions

If $X$ is star-structured then recovering the star $T$ is a matter of
identifying its center, which can be done by computing the mutual information
between only $\tilde{\mathcal{O}}(d)$ pairs of variables. The algorithm picks
a random marginal $X_{i}$ and takes a “Prim’s step” [31], i.e., chooses the
neighboring node (say $X_{k}$) that has the largest mutual information with
$X_{i}$. Assuming that the mutual information $I(X_{i},X_{j})$ between every
pair of variables is distinct, the edge between $X_{i}$ and $X_{k}$ is in the
maximal spanning tree. Next, the algorithm estimates $\sum_{j\neq
i}I(X_{i},X_{j})$ and $\sum_{j\neq k}I(X_{k},X_{j})$ to decide whether $X_{i}$
or $X_{k}$ is the center node of the star. Algorithm 4 presents the procedure,
and Theorem 5.4 gives its sample complexity.

######  Theorem 5.4.

Algorithm 4 is $\alpha$-locally differentially private and has $O(1)$
communication complexity. The number of samples requested by the server is
$O\left(\frac{d\log\frac{d}{\delta}}{\alpha^{2}\epsilon^{2}}\right)$. Let
$\hat{H}$ be the entropy estimate output by the algorithm. If $X$ is star-
structured and $|I(X_{i};X_{j})-I(X_{j};X_{k})|\geq\epsilon$, then
$|\hat{H}-H(X)|\leq\epsilon d$ with probability $1-\delta$.

Algorithm 2 Shannon entropy estimation for chain-structured distribution

1:$S=[d]$, $C=\emptyset$, pick an arbitrary $i,j,k\in S$ and set
$S=S\setminus\\{i,j,k\\}$.

2:Server computes $(\alpha,\epsilon,\delta)$-good estimates
$\hat{I}(X_{i};X_{j}\,|\,X_{k})$, $\hat{I}(X_{i};X_{k}\,|\,X_{j})$ and
$\hat{I}(X_{k};X_{j}\,|\,X_{i})$.

3:if $\;\hat{I}(X_{i};X_{j}\,|\,X_{k})>\epsilon\;$ then
$\boldsymbol{x}_{1}=(i,k,j)$

4:else if $\;\hat{I}(X_{i};X_{k}\,|\,X_{j})>\epsilon\;$ then
$\boldsymbol{x}_{1}=(i,j,k)$

5:else if $\;\hat{I}(X_{k};X_{j}\,|\,X_{i})>\epsilon\;$ then
$\boldsymbol{x}_{1}=(j,i,k)$

6:for $i\in(1,\dots,d-3)$ do

7: Pick item $j$ from $S$ and set $S=S\setminus\\{j\\}$, $r=x_{i,1}$ and
$p=x_{i,i+2}$

8: Server computes $(\alpha,\epsilon,\delta)$-good estimates
$\hat{I}(X_{j};X_{p}\,|\,X_{o})$, $\hat{I}(X_{r};X_{j}\,|\,X_{p})$.

9: if $\;\hat{I}(X_{j};X_{p}\,|\,X_{r})>\epsilon\;$ then
$\boldsymbol{x}_{i+1}=(j,\boldsymbol{x}_{i})$ $\triangleright$ Attach $X_{j}$
to the head of the chain

10: else if $\;\hat{I}(X_{o};X_{j}\,|\,X_{p})>\epsilon\;$ then
$\boldsymbol{x}_{i+1}=(\boldsymbol{x}_{i},j)$ $\triangleright$ Attach $X_{j}$
to the tail of the chain

11: else$\triangleright$ Insert $X_{j}$ into the chain defined by
$\boldsymbol{x}_{i}$

12: $\ell=\textsc{TernarySearch}(\boldsymbol{x}_{i},1,i+2,j)$ $\triangleright$
Defined in Algorithm 3

13:
$\boldsymbol{x}_{i+1}=(\boldsymbol{x}_{i}[1,\dots,\ell],j,\boldsymbol{x}_{i}[\ell+1,\dots,i+2])$

14:Create chain $T$ according to the order defined by $\boldsymbol{x}_{d-2}$.

15:Server computes $(\alpha,\epsilon,\delta)$-good estimate of each term in
Eq. (6) using $T$ and returns $\hat{H}$.

Algorithm 3 $\textsc{TernarySearch}(\boldsymbol{x},\ell_{l},\ell_{h},j)$

1:if $\ell_{l}=\ell_{h}-1$ then return  $\ell_{l}$

2:Pick the median element $k=\lceil(\ell_{h}+\ell_{l})\rceil$, and set
$i=x_{\ell_{l}}$ and $o=x_{\ell_{h}}$

3:Server computes $(\alpha,\epsilon,\delta)$-good estimate
$\hat{I}(X_{i};X_{k}\,|\,X_{j})$.

4:if $\;\hat{I}(X_{i};X_{k}\,|\,X_{j})>\epsilon\;$ then return
$\textsc{TernarySearch}(\boldsymbol{x},i,k,j)$

5:else return  $\textsc{TernarySearch}(\boldsymbol{x},k,o,j)$

Algorithm 4 Shannon entropy estimation for star-structured distribution

1:Pick $i\in[d]$ uniformly at random.

2:Server computes $(\alpha,\epsilon,\delta)$-good estimate
$\hat{I}(X_{i},X_{j})$ for all $j\in[d]\setminus\\{i\\}$.

3:Find
$k=\operatorname*{\arg\max}_{j\in[d]\setminus\\{i\\}}\hat{I}(X_{i},X_{j})$

4:Server computes $(\alpha,\epsilon,\delta)$-good estimate
$\hat{I}(X_{k},X_{j})$.

5:if $\;\sum_{j}\hat{I}(X_{i},X_{j})>\sum_{j}\hat{I}(X_{k},X_{j})\;$ then let
$T$ be a star with $X_{i}$ as center

6:else  let $T$ be a star with $X_{k}$ as the center.

7:Server computes $(\alpha,\epsilon,\delta)$-good estimate of each term in Eq.
(6) using $T$ and returns $\hat{H}$.

###  5.5 Lower Bounds

We prove sample complexity lower bounds for estimating the Shannon entropy of
a tree-structured joint distribution from pair observations. Our first lower
bound focuses on the non-interactive case, when the algorithm must select all
the pairs in advance. The second claim is more general, and holds for all
sequentially interactive algorithms.

######  Theorem 5.5.

For any non-interactive algorithm that uses $o(d^{2})$ pair observations to
estimate Shannon entropy, there exists a tree-structured distribution over
$\\{0,1\\}^{d}$ such that the error of the algorithm is $\Omega(d)$ with
constant probability.

######  Theorem 5.6.

For any $\epsilon>0$ and for any sequentially interactive algorithm that uses
$o(d/\epsilon)$ pair observations to estimate Shannon entropy, there exists a
tree-structured distribution on $\\{0,1\\}^{d}$ such that the error of the
algorithm is $\Omega(\epsilon\cdot d)$ with constant probability.

The lower bound given in Theorem 5.5 is based on Turán’s theorem [9], which we
use to show that for any algorithm with sub-quadratic sample complexity and
for any constant $C\in(0,1)$, there is a graph with $d$ nodes containing a
$C\cdot d$-clique – when $d$ is large enough – such that the algorithm does
not observe any edge of that clique. This implies that the additive error of
the algorithm is linear in $d$. The lower bound for sequentially interactive
algorithms in Theorem 5.6 is based on a information theoretical approach.
Interestingly, our construction of problem instances for which we applied Le
Cam’s theorem is fairly simple, since it contains $d$ independent random
variables in every case. Nevertheless, this lower bound shows that Algorithm 1
is optimal in $d$.

###  5.6 Comparison to Prior Work

To the best of our knowledge, the Chow-Liu algorithm is the only published
method for estimating the entropy of a distribution that takes advantage of
its tree structure. Since the algorithm is non-interactive, the lower bound in
Theorem 5.5 shows that our algorithms have provably better sample complexity
when the number of variables $d$ is large (note that the dependence on $d$ in
each of Theorems 5.2, 5.3 and 5.4 is sub-quadratic). The Chow-Liu algorithm
can also be used to estimate the distribution itself, not just its entropy,
and it has recently been shown [8, 17] that the algorithm has optimal sample
complexity when given full observations (i.e., samples of the entire vector
$(X_{1},\ldots,X_{d})$ and not just pairs or triplets of the variables). Thus
the Chow-Liu algorithm is optimal for estimating a tree-structured
distribution, but suboptimal for estimating the _entropy_ of a tree-structured
distribution. The root cause of this difference appears to be the fact that it
is significantly easier to estimate the weight of the maximum spanning tree
than finding the tree itself.

##  6 Estimating Gini and Collision Entropies

In this section, we describe a non-iterative protocol (Algorithm 5) that
estimates both the Gini and collision entropies of a discrete random variable
$X$ while observing only $b$ bits per sample from its distribution, and does
not require any extra assumption on the distribution of $X$ (such as assuming
it is tree-structured). First, the server partitions all users into pairs
(assume for simplicity that the number of users is even). The server then
distributes a $b$-bit hash function to each user, along with a distinct salt
to each user pair. Each user then hashes their sample along with their salt,
and returns the hash value to the server. The server computes entropy
estimates based on the number of observed hash collisions across all pairs. In
Algorithm 5, we let $\left\langle x,y\right\rangle$ denote a binary string
that encodes $x$, followed by a delimiter, and by $y$.

Algorithm 5 Gini and collision entropy estimation

1:

2:Each user $i\in[n]$ draws a sample $x_{i}$ independently from the
distribution of $X$.

3:Server partitions the $n$ users into $\frac{n}{2}$ disjoint pairs.

4:Let $q_{i}\in\left[\frac{n}{2}\right]$ be the index of the pair containing
user $i$.

5:Server transmits $q_{i}$ and hash function
$h:\\{0,1\\}^{*}\mapsto\\{0,1\\}^{b}$ to each user $i$.

6:Each user $i$ generates a $b$-bit hash value $v_{i}=h(\langle
q_{i},x_{i}\rangle)$ for their sample $x_{i}$.

7:Each user $i$ lets $\hat{v}_{i}=v_{i}$ with probability
$\lambda=\frac{e^{\alpha}-1}{2^{b}+e^{\alpha}-1}$ and else draws $\hat{v}_{i}$
uniformly from $[2^{b}]$.

8:Server receives $\hat{v}_{i}$ from each user $i$.

9:If pair $q$ contains users $i$ and $j$ then let
$c_{q}=\mathbf{1}[\hat{v}_{i}=\hat{v}_{j}]$ indicate whether a hash collision
was observed for pair $q$.

10:Server computes $\bar{c}=\frac{2}{n}\sum_{q}c_{q}$.

11:Server outputs $\hat{G}=\frac{2^{b}\bar{c}-1}{\lambda^{2}(2^{b}-1)}$ and
$\hat{C}=-\log\left(1-\hat{G}\right)$.

Algorithm 5 is based on the observation that if $X$ and $X^{\prime}$ are
independent and identically distributed then the Gini entropy is equal to
$1-\Pr[X=X^{\prime}]$ and the collision entropy is equal to
$-\log\Pr[X=X^{\prime}]$. If the server observed each sample directly then it
could estimate $\Pr[X=X^{\prime}]$ using the collision frequency, i.e., the
fraction of sample pairs $(x_{i},x_{j})$ such that $x_{i}=x_{j}$. However, the
server only observes a $b$-bit hash of each sample. Among sample pairs in
which there is a true collision, all of them also produce a hash collision.
Among samples pairs in which there is not a true collision, about a
$\frac{1}{2^{b}}$ fraction of them produce a hash collision. Therefore the
true collision frequency can be estimated using an appropriately bias-
corrected hash collision frequency, and the server uses this estimate to
approximate the Gini and collision entropies.

The analysis of Algorithm 5 is given in Theorem 6.1 below. As is customary,
for the analysis we assume that the hash function $h$ is constructed by
assigning each element of its domain to a uniform random element of its range
[7]. See the Appendix G for the proof of the theorem.

######  Theorem 6.1.

Algorithm 5 is $\alpha$-locally differentially private, has $\tilde{O}(b)$
communication complexity and $\tilde{O}(b)$ space complexity. Let $\hat{G}$
and $\hat{C}$ be the outputs of the algorithm. Let
$\alpha,\epsilon,\delta\in(0,1)$. If
$n=\Omega\left(\frac{2^{4b}\max\\{1-G(X),2^{-b},\epsilon\\}\log\frac{1}{\delta}}{\alpha^{4}\epsilon^{2}}\right)$,
then $|\hat{G}-G(X)|\leq\epsilon$ with probability at least $1-\delta$. Also,
if $X$ has support size $k$ and
$n=\Omega\left(\frac{2^{4b}k^{2}\log\frac{1}{\delta}}{\alpha^{4}\epsilon^{2}}\right)$,
then $|\hat{C}-C(X)|\leq\epsilon$ with probability at least $1-\delta$.

###  6.1 Comparison to Prior Work

Recall that Gini entropy is proportional to the second frequency moment. Local
differentially private algorithms for estimating frequency moments were
recently studied in [11]. Letting $b=1$ in Algorithm 5 yields a sample
complexity of $\tilde{O}(1/(\alpha^{4}\epsilon^{2}))$, which is independent of
the distribution’s support size, unlike the sample complexity of the non-
interactive algorithm for estimating the second frequency moment from [11].
Also our algorithm only uses $1$ bit per sample and $\tilde{O}(1)$ space,
while the previous algorithm uses $\Omega(k)$ bits per sample and $\Omega(k)$
space, where $k$ is the support size of the distribution. The authors in [11]
asked whether there is a non-interactive algorithm for privately estimating
frequency moments with a sample complexity that is independent of the
distribution’s support size. Here we affirmatively answer this open question
for the second frequency moment.

The best known algorithm for estimating collision entropy using $\tilde{O}(1)$
space is due to [37]. The sample complexity of their algorithm is
$\tilde{O}\left(k/\epsilon^{2}\right)$ and its communication complexity is
$O(\log k)$ bits per user. Letting $b=1$ in Algorithm 5 generalizes the
previous algorithm to the private and communication-efficient setting. It was
shown in [15] that (conditioned on a plausible conjecture) any algorithm that
estimates collision entropy to within $O(1)$ error using $O(1)$ space requires
$\Omega(k)$ samples.

##  7 Experiments

In this section we present two sets of experiments to support our theoretical
findings. First, we demonstrate that Algorithm 1 is indeed able to estimate
the Shannon entropy of tree-structured distributions with linear sample
complexity in $d$. Thus it has a superior sample complexity compared to the
state-of-the-art non-interactive method [13, 8], which has a quadratic sample
complexity in $d$. The sample complexity is defined here in terms of number of
observations from pairs of marginals. In the second set of experiments, we use
our Algorithm 5 to estimate the collision entropy of discrete distributions,
and compare its performance to that of the best-known communication efficient,
non-private algorithm for this task, Skorski’s algorithm [37].

Estimating Shannon entropy: To estimate the Shannon entropy of a tree-
structured distribution as given by Eq. (6), the marginal entropies and the
mutual information between certain pairs of marginals has to be estimated. The
Chow-Liu algorithm estimates the mutual information between all pairs of
marginals which results in quadratic sample complexity, whereas Algorithm 1
estimates the mutual information only for a linear fraction of pairs. Both
algorithms estimate the marginal entropy values by sampling the marginals
independently from the mutual information estimations, and they both use the
same $\epsilon$ additive error and privacy budget $\alpha$ to estimate the
mutual information between pairs of marginals. Thus it is fair to compare
their performance in terms of number of pairs for which they estimate the
mutual information. For the Chow-Liu algorithm this is always $d^{2}$, whereas
our Algorithm 1 is randomized, thus we evaluate it over $100$ repetitions and
report the average.

We ran this experiment on random tree-structured joint distributions over
$\\{0,1\\}^{d}$. To create a random tree-structured distribution, we first
sample the structure of the distribution by taking the maximum spanning tree
of a complete graph with $d$ nodes and edge weights distributed according to a
standard normal. Next, we sample the parameters for each marginal uniformly at
random from $[0,1]$, and then we achieve the tree-structure by inducing
dependence between pairs of variables while preserving the marginals.
Specifically, for two marginals $X_{i}$ and $X_{j}$ with sampled parameters
$p_{i}$ and $p_{j}$, we set:
$P(X_{i}=0,X_{j}=0)=(1-p_{i})\cdot(1-p_{j})+r_{ij}$,
$P(X_{i}=1,X_{j}=1)=p_{i}\cdot p_{j}+r_{ij}$,
$P(X_{i}=0,X_{j}=1)=(1-p_{i})\cdot p_{j}-r_{ij}$, and
$P(X_{i}=1,X_{j}=0)=p_{i}\cdot(1-p_{j})-r_{ij}$, where $r_{ij}$ is sampled
uniformly at random from a range of values such that each probability stays
positive. The results are displayed in Figure 1(a). It is clear that the
sample size (_i.e._ , number of mutual information estimate) is close to
linear for our algorithm, whereas the Chow-Liu algorithm requires a larger
sample size.

(a) Sample complexity of estimating Shannon entropy of tree-structured
distributions (eq. (6)) for the Chow-Liu algorithm [13] and for our Algorithm
1.

(b) Absolute error in estimating the collision entropy of an exponential
distribution with domain size $k=1000$ for the Skorski’s algorithm [37] and
for our Algorithm 5.

Estimating collision entropy: In this set of experiments, we drew samples from
a discrete exponential distribution $p_{i}\propto e^{-i}$ with support size
$k=1000$ and estimated the collision entropy using algorithm [37] (the
previously best-known communication-efficient algorithm for this task) and our
Algorithm 5 (with and without local differential privacy). Algorithm [37]
requires $O(\log k)$ bits per sample and is not private, while our algorithm
only requires $1$ bit per sample and is differentially private. The results
are displayed in Figure 1(b). The previous algorithm has $5\%$ estimation
error after observing $10000$ bits, while our algorithm has less than $3.5\%$
estimation error. Thus our algorithm has lower error for the same
communication cost while also being local differentially private.

##  8 Conclusion and Future Work

Estimating entropy is of importance in many practical applications. In this
paper, we studied three widely used entropy measures: Shannon, Gini and
collision entropy. We described estimation algorithms for each entropy that
require minimal communication and satisfy local differential privacy. We also
validated our theoretical results with simulations.

Our sequentially interactive algorithm for estimating Shannon entropy of high-
dimensional tree-structured distributions observes only two of these
dimensions per sample and has a sample complexity $O(d/\epsilon^{5})$. Our
approach relies on the celebrated Chow-Liu approximation [13], providing a
substantial improvement on the $\Omega(d^{2})$ sample complexity of the
original non-interactive Chow-Liu algorithm. We also identified two special
cases (viz., when the underlying graphical model of the joint distribution is
either a chain or star graph) and provided algorithms with a sample complexity
of $\tilde{O}(d\log d/\epsilon^{2})$.

Our algorithm for Gini and collision entropy estimation also improved on the
state-of-the-art, either by improving the sample complexity and communication
complexity of previous work, or by generalizing the best known algorithm to
the private and communication-efficient setting.

A natural extension of our work on Shannon entropy estimation is to consider
higher-order correlations in the Chow-Liu decomposition [27]. In contrast to
the second-order case which reduces to a maximum spanning tree problem,
discovering the underlying structure of the joint distribution is already
computationally challenging. However, efficiently estimating the entropy of
the resulting distribution might still be possible.

## References

  * [1] Jayadev Acharya, Clement Canonne, Cody Freitag, and Himanshu Tyagi.  Test without trust: Optimal locally private distribution testing.  In Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, volume 89 of Proceedings of Machine Learning Research, pages 2067–2076. PMLR, 2019.
  * [2] Jayadev Acharya, Clément L Canonne, and Himanshu Tyagi.  Inference under information constraints: Lower bounds from chi-square contraction.  In Proceedings of the Thirty-Second Conference on Learning Theory, volume 99 of Proceedings of Machine Learning Research, pages 3–17. PMLR, 2019.
  * [3] Jayadev Acharya, Gautam Kamath, Ziteng Sun, and Huanyu Zhang.  Inspectre: Privately estimating the unseen.  In International Conference on Machine Learning, pages 30–39. PMLR, 2018.
  * [4] Jayadev Acharya and Ziteng Sun.  Communication complexity in locally private distribution estimation and heavy hitters.  In International Conference on Machine Learning, pages 51–60. PMLR, 2019.
  * [5] Jayadev Acharya, Ziteng Sun, and Huanyu Zhang.  Hadamard response: Estimating distributions privately, efficiently, and with little communication.  In The 22nd International Conference on Artificial Intelligence and Statistics, pages 1120–1129. PMLR, 2019.
  * [6] Vikas Bansal.  Sublinear-time algorithms for estimating the weight of minimum spanning trees.  Unpublished manuscript, 109, 2003.
  * [7] Mihir Bellare and Phillip Rogaway.  Random oracles are practical: A paradigm for designing efficient protocols.  In Proceedings of the 1st ACM Conference on Computer and Communications Security, pages 62–73, 1993.
  * [8] Arnab Bhattacharyya, Sutanu Gayen, Eric Price, and NV Vinodchandran.  Near-optimal learning of tree-structured distributions by Chow-Liu.  In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 147–160, 2021.
  * [9] Béla Bollobás.  Modern Graph Theory.  Graduate Texts in Mathematics 184. 1998.
  * [10] Tai-Danae Bradley.  Entropy as a topological operad derivation.  Entropy, 23(9), 2021.
  * [11] Cristina Butucea and Yann Issartel.  Locally differentially private estimation of functionals of discrete distributions.  In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 24753–24764. Curran Associates, Inc., 2021.
  * [12] Bernard Chazelle, Ronitt Rubinfeld, and Luca Trevisan.  Approximating the minimum spanning tree weight in sublinear time.  In International Colloquium on Automata, Languages, and Programming, pages 190–200. Springer, 2001.
  * [13] C. Chow and C. Liu.  Approximating discrete probability distributions with dependence trees.  IEEE Transactions on Information Theory, 14(3):462–467, 1968.
  * [14] Thomas M. Cover and Joy A. Thomas.  Elements of Information Theory (Wiley Series in Telecommunications and Signal Processing).  Wiley-Interscience, New York, NY, USA, 2006.
  * [15] Michael Crouch, Andrew McGregor, Gregory Valiant, and David P Woodruff.  Stochastic streams: Sample complexity vs. space complexity.  In 24th Annual European Symposium on Algorithms (ESA 2016). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2016.
  * [16] Artur Czumaj and Christian Sohler.  Estimating the weight of metric minimum spanning trees in sublinear-time.  In Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, pages 175–183, 2004.
  * [17] Constantinos Daskalakis and Qinxuan Pan.  Tree-structured Ising models can be learned efficiently.  arXiv e-prints, pages arXiv–2010, 2020.
  * [18] John Duchi and Ryan Rogers.  Lower bounds for locally private estimation via communication complexity.  In Conference on Learning Theory, pages 1161–1191. PMLR, 2019.
  * [19] Cynthia Dwork, Aaron Roth, et al.  The algorithmic foundations of differential privacy.  Found. Trends Theor. Comput. Sci., 9(3-4):211–407, 2014.
  * [20] Kazuto Fukuchi and Jun Sakuma.  Minimax optimal estimators for additive scalar functionals of discrete distributions.  In 2017 IEEE International Symposium on Information Theory (ISIT), pages 2103–2107. IEEE, 2017.
  * [21] C. Gini.  Variabilitá e Mutuabilitá. Contributo allo Studio delle Distribuzioni e delle Relazioni Statistiche.  Bologna: C. Cuppini., 1912.
  * [22] Yanjun Han, Ayfer Özgür, and Tsachy Weissman.  Geometric lower bounds for distributed parameter estimation under communication constraints.  In Conference On Learning Theory, pages 3163–3188. PMLR, 2018.
  * [23] Oc Herfindahl.  Concentration in the US steel industry.  1950\.
  * [24] Matthew Joseph, Jieming Mao, Seth Neel, and Aaron Roth.  The role of interactivity in local differential privacy.  In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 94–105. IEEE, 2019.
  * [25] Matthew Joseph, Jieming Mao, Seth Neel, and Aaron Roth.  The role of interactivity in local differential privacy.  In David Zuckerman, editor, 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019, pages 94–105. IEEE Computer Society, 2019.
  * [26] Jyrki Katajainen and Jesper Larsson Träff.  A meticulous analysis of mergesort programs.  In Italian Conference on Algorithms and Complexity, pages 217–228. Springer, 1997.
  * [27] Edith Kovács and Tamás Szántai.  On the Approximation of a Discrete Multivariate Probability Distribution Using the New Concept of t-Cherry Junction Tree, pages 39–56.  Springer Berlin Heidelberg, Berlin, Heidelberg, 2010.
  * [28] Markku Laakso and Rein Taagepera.  “Effective” number of parties: A measure with application to west europe.  Comparative Political Studies, 12(1):3–27, 1979.
  * [29] Tom Leinster.  Entropy and Diversity: The Axiomatic Approach.  Cambridge University Press, 2021.
  * [30] Abolfazl S Motahari, Guy Bresler, and NC David.  Information theory of DNA shotgun sequencing.  IEEE Transactions on Information Theory, 59(10):6273–6289, 2013\.
  * [31] Robert Clay Prim.  Shortest connection networks and some generalizations.  The Bell System Technical Journal, 36(6):1389–1401, 1957.
  * [32] Laura Elena Raileanu and Kilian Stoffel.  Theoretical comparison between the Gini index and information gain criteria.  Annals of Mathematics and Artificial Intelligence, 41(1):77–93, 2004.
  * [33] Alfréd Rényi.  On measures of information and entropy.  In Proceedings of the fourth Berkeley Symposium on Mathematics, Statistics and Probability, pages 547–561, 1960.
  * [34] C.E. Shannon.  A mathematical theory of communication.  Bell Syst. Tech. J., 27:379–423, 1948.
  * [35] Edward H Simpson.  Measurement of diversity.  nature, 163(4148):688–688, 1949.
  * [36] Yakov G. Sinai.  On the notion of entropy of a dynamical system.  2010\.
  * [37] Maciej Skorski.  Evaluating entropy for true random number generators: Efficient, robust and provably secure.  In International Conference on Information Security and Cryptology, pages 526–541, 03 2017.
  * [38] Ananda Theertha Suresh, X Yu Felix, Sanjiv Kumar, and H Brendan McMahan.  Distributed mean estimation with limited communication.  In International Conference on Machine Learning, pages 3329–3337. PMLR, 2017.
  * [39] Constantino Tsallis.  Introduction to Nonextensive Statistical Mechanics.  Springer New York, NY, Greece, 2009.
  * [40] Thomas Verma and Judea Pearl.  Equivalence and synthesis of causal models.  In Proceedings of the Sixth Annual Conference on Uncertainty in Artificial Intelligence, UAI ’90, page 255–270, USA, 1990. Elsevier Science Inc.
  * [41] Yuchen Zhang, John C Duchi, Michael I Jordan, and Martin J Wainwright.  Information-theoretic lower bounds for distributed statistical estimation with communication constraints.  In NIPS, pages 2328–2336. Citeseer, 2013.

##  Appendix A Proof of Theorem 5.1

###### Proof.

[4, 5] showed that any discrete distribution can be learnt in total variation
distance based on $O(c^{2}\log 1/\delta/(\epsilon^{2}\alpha^{2})$ when
$\alpha<1$. This result can be plug-in into Theorem 17.3.3 of [14]. ∎

##  Appendix B Proof of Theorem 5.2

Existing algorithms for estimating the weight of the maximum spanning tree in
sublinear time assume that each edge weight can be computed in $O(1)$ time.
Our main idea is to combine one of these algorithms with Theorem 5.1, which
gives the number of samples needed to privately estimate an edge weight (i.e.,
the mutual information between two variables).

The first sublinear algorithm for MST weight estimation is due to [12]. Our
algorithm and analysis follows the exposition in [6], which is itself based on
[16]. The main technical complication we must overcome is that the results
from [12] and [6] assume that the edge weights have a bounded ratio, while we
instead discretize the edge weights with resolution $\epsilon$.

Let $G$ be a graph on $d$ nodes such that the edge weight between nodes $i$
and $j$ is $I(X_{i};X_{j})$. Let $\tilde{G}$ be a graph on $d$ nodes with edge
weights belonging to the set

$\\{\epsilon,2\epsilon,\ldots,M\epsilon\\}$

and such that every edge weight in $\tilde{G}$ differs from the corresponding
edge weight in $G$ by at most $\epsilon$. Note that this is possible because
the edge weights in $G$ are guaranteed to be in the interval $[0,M\epsilon]$.
Let $w(G)$ be the weight of a maximum spanning tree of $G$. Clearly we have

$|w(G)-w(\tilde{G})|\leq\epsilon d.$ (7)

For each $m\in\\{1,\ldots,M\\}$ let $\tilde{G}_{m}$ be the subgraph of
$\tilde{G}$ containing the same nodes as $\tilde{G}$ and only those edges of
$\tilde{G}$ whose weight is at least $m\epsilon$. Thus
$\tilde{G}_{1}=\tilde{G}$.

Let $\mathcal{C}_{m}$ be the set of connected components in $\tilde{G}_{m}$.
Also let

$\displaystyle\mathcal{C}^{-}_{m}$
$\displaystyle=\left\\{C\in\mathcal{C}_{m}:|C|\leq\frac{2}{\epsilon}\right\\}$
$\displaystyle\mathcal{C}^{+}_{m}$
$\displaystyle=\left\\{C\in\mathcal{C}_{m}:|C|>\frac{2}{\epsilon}\right\\}$

be the sets of connected components in $\tilde{G}_{m}$ with size at most
$\frac{2}{\epsilon}$ and greater than $\frac{2}{\epsilon}$, respectively. Let
$\eta_{m}=|\mathcal{C}_{m}|$, $\eta^{-}_{m}=|\mathcal{C}^{-}_{m}|$ and
$\eta^{+}_{m}=|\mathcal{C}^{+}_{m}|$. Clearly

$\eta^{+}_{m}\leq\frac{\epsilon d}{2}$ (8)

since $\tilde{G}_{m}$ has $d$ nodes. Now consider the iteration of Algorithm 1
that sets the value of $\gamma_{mr}$. Let $i^{*}$ and $Z$ be the random
variables from this iteration. Recall that an
$\left(\alpha,\frac{\epsilon}{2},\frac{\delta}{d^{2}}\right)$-good estimate is
computed for the weight of each edge. Therefore, with probability $1-\delta$,
this iteration performs a breadth-first search on the graph $\tilde{G}_{m}$,
and sets $\gamma_{mr}=1$ if and only if the component in $\tilde{G}_{m}$
containing $i^{*}$ has size at most
$\min\left\\{\frac{1}{\epsilon},Z\right\\}$. Thus we have

$\displaystyle\operatorname{E}[\gamma_{mr}]$
$\displaystyle=\sum_{C\in\mathcal{C}_{m}}\Pr[i^{*}\in
C]\Pr\left[|C|\leq\min\left\\{\frac{2}{\epsilon},Z\right\\}\right]$
$\displaystyle=\sum_{C\in\mathcal{C}^{-}_{m}}\Pr[i^{*}\in C]\Pr\left[|C|\leq
Z\right]$
$\displaystyle=\sum_{C\in\mathcal{C}^{-}_{m}}\frac{|C|}{d}\frac{1}{|C|}$
$\displaystyle=\frac{\eta_{m}^{-}}{d}.$

Since $i^{*}$ and $Z$ are drawn independently in each iteration, we have by
Hoeffding’s inequality with probability $1-\delta$

$\left\lvert\hat{\eta}_{m}-\eta^{-}_{m}\right\rvert=\left\lvert\frac{d}{r}\sum_{r=1}^{R}\gamma_{mr}-\eta^{-}_{m}\right\rvert\leq\epsilon
d.$ (9)

Next, we will relate the weight of the maximum spanning tree of $\tilde{G}$ to
the number of connected components in various subgraphs of $\tilde{G}$. For
each $m\in\\{1,\ldots,M\\}$ let $\beta_{m}$ be the number of edges with weight
$m\epsilon$ in a maximum spanning tree of $\tilde{G}$. We have

$\sum_{m<\ell}\beta_{m}=\eta_{\ell}-1$

for any $\ell\in\\{1,\ldots,M\\}$, where the empty sum is defined to be zero.
This equality can be established by considering Kruskal’s greedy algorithm for
constructing a maximum spanning tree, which adds edges in decreasing order of
weight as long as they do not induce a cycle. Since $\tilde{G}_{\ell}$ has
$\eta_{\ell}$ connected components, and all the edges in $\tilde{G}_{\ell}$
are heavier than all the edges not in $\tilde{G}_{\ell}$, the greedy algorithm
must first connect the vertices within each component of $\tilde{G}_{\ell}$
and then use exactly $\eta_{\ell}-1$ edges not in $\tilde{G}_{\ell}$ to
connect the components to each other. Thus we have

$\displaystyle w(\tilde{G})$ $\displaystyle=\sum_{m=1}^{M}m\epsilon\beta_{m}$
$\displaystyle=\epsilon\left(\sum_{m\geq 1}\beta_{m}+\sum_{m\geq
2}\beta_{m}+\cdots+\sum_{m\geq M}\beta_{m}\right)$
$\displaystyle=\epsilon\left(d-1-\sum_{m<1}\beta_{m}+d-1-\sum_{m<2}\beta_{m}+\cdots+d-1-\sum_{m<M}\beta_{m}\right)$
$\displaystyle=\epsilon\left(M(d-1)-\sum_{m=1}^{M}(\eta_{m}-1)\right)$
$\displaystyle=\epsilon Md-\epsilon\sum_{m=1}^{M}\eta_{m}$ (10)

Putting everything together, and using the definition of $\hat{W}$ from
Algorithm 1, we have with probability $1-\delta$

$\displaystyle\left\lvert\hat{W}-w(G)\right\rvert$
$\displaystyle=\left\lvert\epsilon
Md-\epsilon\sum_{m=1}^{M}\hat{\eta}_{m}-w(G)\right\rvert$
$\displaystyle\leq\left\lvert\epsilon
Md-\epsilon\sum_{m=1}^{M}\eta_{m}-w(G)\right\rvert+\epsilon\sum_{m=1}^{M}\left\lvert\eta^{-}_{m}-\hat{\eta}_{m}\right\rvert+\epsilon\sum_{m=1}^{M}\left\lvert\eta^{-}_{m}-\eta_{m}\right\rvert$
$\displaystyle=\left\lvert\epsilon
Md-\epsilon\sum_{m=1}^{M}\eta_{m}-w(G)\right\rvert+\epsilon\sum_{m=1}^{M}\left\lvert\eta^{-}_{m}-\hat{\eta}_{m}\right\rvert+\epsilon\sum_{m=1}^{M}\left\lvert\eta^{+}_{m}\right\rvert$
$\displaystyle=\left\lvert
w(\tilde{G})-w(G)\right\rvert+\epsilon\sum_{m=1}^{M}\left\lvert\eta^{-}_{m}-\hat{\eta}_{m}\right\rvert+\epsilon\sum_{m=1}^{M}\left\lvert\eta^{+}_{m}\right\rvert$
$\displaystyle\because\textrm{Eq.~{}\eqref{eq:mst:four}}$
$\displaystyle\leq\left\lvert
w(\tilde{G})-w(G)\right\rvert+\epsilon^{2}Md+\epsilon\sum_{m=1}^{M}\left\lvert\eta^{+}_{m}\right\rvert$
$\displaystyle\because\textrm{Eq.~{}\eqref{eq:mst:three}}$
$\displaystyle\leq\left\lvert
w(\tilde{G})-w(G)\right\rvert+\epsilon^{2}Md+\frac{\epsilon^{2}Md}{2}$
$\displaystyle\because\textrm{Eq.~{}\eqref{eq:mst:two}}$
$\displaystyle\leq\epsilon d+\epsilon^{2}Md+\frac{\epsilon^{2}Md}{2}$
$\displaystyle\because\textrm{Eq.~{}\eqref{eq:mst:one}}$
$\displaystyle=O(\epsilon d).$

Finally, recall that an $\left(\alpha,\epsilon,\frac{\delta}{d}\right)$-good
estimate is computed for each marginal entropy. Therefore with probability
$1-\delta$ we have

$\left\lvert\hat{S}-\sum_{i}H(X_{i})\right\rvert\leq\epsilon d$

and thus by Eq. (6) we have

$|\hat{H}-H(X)|=\left\lvert\hat{S}-\hat{W}-\left(\sum_{i}H(X_{i})-w(G)\right)\right\rvert=O(\epsilon
d).$

Algorithm 1 has $\tilde{O}\left(\frac{1}{\epsilon^{3}}\right)$ iterations, in
each iteration estimates the weights of

$d\sum_{z\leq\frac{2}{\epsilon}}z\Pr[Z=z]=d\sum_{z\leq\frac{2}{\epsilon}}\Pr[Z\geq
z]=O\left(d\log\frac{1}{\epsilon}\right)$

edges on average, and uses
$\tilde{O}\left(\frac{1}{\alpha^{2}\epsilon^{2}}\right)$ samples to estimate
the weight of each edge.

##  Appendix C Proof of Theorem 5.3

###### Proof.

We start by recalling a lemma that applies to tree-structured distributions.

######  Lemma C.1.

[40] Let $\mathbf{X}=(X_{1},\dots,X_{d})$ be tree decomposable with tree $T$.
Then for any triplets $i$, $j$ and $k$, if $k$ is on the unique path in $T$
between $i$ and $j$, then

$I(X_{i};X_{j}|X_{k})=0\enspace.$

Next we show that the output Algorithm 2 is correct with high probability. We
make use of the Conditional Mutual Information Tester of [8]. This testing
algorithm consists of estimating the CMI using the plug-in estimator and then
applying a $\epsilon$ threshold on the estimate, i.e., if the estimate is
smaller than $\epsilon$ then accept, otherwise reject. The sample complexity
of Conditional Mutual Information Tester is
$O\left(\tfrac{|\Sigma|^{3}}{\epsilon}\log\frac{d|\Sigma|}{\delta}\log\frac{|\Sigma|\log
d/\delta}{\epsilon}\right)$ according to Theorem 1.3 of [8]. Thus if we apply
this tester with adjusted confidence parameter, i.e., $\delta/d\log_{3}d$,
then the union bound implies that the output of all tests is correct with
probability at least $1-\delta$.

Next, note that for any triplet $X_{i},X_{j},X_{k}$ such that $X_{i}$ is
between $X_{j}$ and $X_{k}$ in the chain, it holds that

$I(X_{j};X_{i})-I(X_{j};X_{k})=\underbrace{I(X_{j};X_{i}|X_{k})}_{>\epsilon}-\underbrace{I(X_{j};X_{k}|X_{i})}_{=0~{}\text{due
to Lemma ~{}\ref{lemma:condint_treedecomp_succ}}}$

as the edges are different with a margin of $\epsilon$. The same argument
implies that $I(X_{k};X_{i}|X_{j})>\epsilon$. Thus, Algorithm 2 divides the
nodes correctly in Line 4-10 which along with the testers’ correctness with
high probability implies the correctness of the algorithm.

Using the result from [8] that the sample complexity of Conditional Mutual
Information Tester is
$O\left(\tfrac{|\Sigma|^{3}}{\epsilon}\log\frac{d|\Sigma|}{\delta}\log\frac{|\Sigma|\log
d/\delta}{\epsilon}\right)$, we only need to upper bound the number of tests
for deciding whether $I(X_{i};X_{j}\,|\,X_{k})>\epsilon$ that is carried out
by Algorithm 2. It is indeed $3\sum_{i=3}^{d}\log_{3}i\in O(d\log_{3}d)$ which
concludes the proof. ∎

##  Appendix D Proof of Theorem 5.4

###### Proof.

First note that the Prim step in Line 3 of Algorithm 4 indeed finds an edge
that is in the maximum spanning tree due to the assumption
$|I(X_{i};X_{j})-I(X_{j};X_{k})|\geq\epsilon$. Say this edge is between
$X_{i}$ and $X_{k}$, what remains to be decided is whether $X_{i}$ or $X_{k}$
is the center of the graph. This can be done by comparing
$\sum_{j}\hat{I}(X_{i},X_{j})$ and $\sum_{j}\hat{I}(X_{k},X_{j})$.

So Algorithm 4 estimates $2d$ mutual information, which requires $4d$ marginal
and $2d$ pairwise marginal entropy estimation. Recall from Theorem 5.1 that
entropy can estimated $\alpha$-locally differential private with $\epsilon$
error using $O(c^{2}\log\frac{1}{\delta}/(\epsilon^{2}\alpha^{2}))$ samples.
Thus by the union bound the algorithm is correct if the confidence parameter
is set to $\delta/6d$, and accordingly has sample complexity
$O(\frac{6dc^{2}}{\epsilon^{2}\alpha^{2}}\log\frac{6d}{\delta})$. ∎

##  Appendix E Proof of Theorem 5.5

###### Proof.

Assume a deterministic algorithm $\mathcal{A}$ that takes sub-quadratic
samples from $\mathbf{X}$ and estimates $H(\mathbf{X})$. In addition, assume
that its sample complexity is $o(d^{2})$. Thus for any constant $C>0$, there
exists $d_{0}$ such that for any $d>d_{0}$, the sample complexity of the
algorithm is $<Cd^{2}$. This implies that, if $d$ is large enough, the
algorithm needs $\leq d^{2-\kappa}$. In addition, we can pick $d$ so as
$d^{-\kappa}<\kappa$ which implies $d^{2}-d^{2-\kappa}>(1-\kappa)d^{2}$. Thus
any deterministic algorithm which takes sub-quadratic sample size never
observes $(1-\kappa)d^{2}$ edges for $\forall\kappa$ when $d$ is large enough.

Let us recall that Turán’s theorem

######  Theorem E.1 ([9]).

Let $G(V,E)$ be a graph with $d$ vertices (i.e, $|V|=d$) that does not contain
a $(\ell+1)$-clique as a subgraph. Then $G$ has at most
$\frac{(\ell-1)d^{2}}{2\ell}$ edges.

In addition, recall that the Turán’s graph $G_{T}(d,\ell)$ [9] is defined as
the unique graph with $d$ nodes that does not contain a $(\ell+1)$-clique and
has the maximum possible number of edges which is
$\left\lfloor\frac{(\ell-1)d^{2}}{2\ell}\right\rfloor$. Let $t(d,\ell)$ denote
the number of edges in $G_{T}(d,\ell)$.

Thus for any $d>0$ there exists a graph $G=(V,E)$ such that $|V|=d$ and
$|E|>t(d,k)$ which contains a $(k+1)$-clique. This implies that if algorithm
$\mathcal{A}$ does not observes at least $t(d,k)$ edges of $G$, then $G$
contains a $k+1$-clique whose edges are never observed by algorithm
$\mathcal{A}$. Now we apply Turan’s result with $\ell=d/2$ which implies that

$t(d,d/2)=\left\lfloor(1/2-1/d)d^{2}\right\rfloor$

Thus for any $\kappa\in(0,1/2)$ and any algorithm with sample complexity
$o(d^{2})$, if $d$ is large enough, then there will be a $\Theta(d/2)$-clique
for which the algorithm does not observe any edge within this clique.

Finally it is easy to construct two $d/2$-dimensional problem instances,
denoted it $S$ and $S^{\prime}$, with joint entropy that differs by
$\Omega(d)$: take $d/2$ Bernoulli with parameter $1/2$ and take the copy of
the same Bernoulli $d/2$ times. The entropy for these two joint distributions
is $d/2$ and $1$, respectively. This also implies that for any deterministic
algorithm we can construct two problem instances which contains $S$ and
$S^{\prime}$ so as they are independent from the rest of the marginals and the
algorithm does not observe any sample from them, and hence it cannot achieve
$o(d)$ additive error. ∎

##  Appendix F Proof of Theorem 5.6

###### Proof.

Let $\hat{\theta}_{n}=\hat{\theta}(x_{1},\dots,x_{n})$ such that
$\hat{\theta}_{n}:(\Sigma^{d})^{n}\mapsto\mathbb{R}$ be an estimator using $n$
samples.

######  Theorem F.1.

[Le Cam’s theorem] Let $\mathcal{P}$ be a set of distributions. Then, for any
pair of distributions $P_{0},P_{1}\in\mathcal{P}$, we have

$\inf_{\hat{\theta}}\max_{P\in\mathcal{P}}\mathbb{E}_{P}\left[d(\hat{\theta}_{n}(P),\theta(P))\right]\geq\frac{d(\theta(P_{0}),\theta(P_{1}))}{8}e^{-nd_{\text{KL}}(P_{0},P_{1})},$

where $\theta(P)$ is a parameter taking values in a metric space with metric
$d$, and $\hat{\theta}_{n}$ is the estimator of $\theta$ based on $n$ samples.

Let us consider two Bernoulli distributions $P_{0}$ and $P_{1}$ with
parameters $p_{0}=1/2$ and $p_{1}=1/2-\epsilon$, where $\epsilon\in(0,1/2)$.
The entropy of random variables $X_{0}$ and $X_{1}$ distributed according to
$P_{0}$ and $P_{1}$ are $H(X_{0})=1$ and

$\displaystyle H(X_{1})$
$\displaystyle=-\left(\frac{1}{2}-\epsilon\right)\log_{2}\left(\frac{1}{2}-\epsilon\right)-\left(\frac{1}{2}+\epsilon\right)\log_{2}\left(\frac{1}{2}+\epsilon\right).$

Thus,

$\displaystyle|H(X_{0})-H(X_{1})|=H(X_{0})-H(X_{1})$
$\displaystyle=\left(\epsilon+\frac{1}{2}\right)\log_{2}(1+2\epsilon)-\left(\epsilon-\frac{1}{2}\right)\log_{2}(1-2\epsilon)$
$\displaystyle\geq\left(\epsilon+\frac{1}{2}\right)\frac{2\epsilon}{1+2\epsilon}-\left(\frac{1}{2}-\epsilon\right)2\epsilon$
$\displaystyle\geq 2\epsilon^{2}$

where we used that $\log(1-2\epsilon)\leq-\epsilon$ for $0<\epsilon<1$ and
$\frac{\epsilon}{1+\epsilon}\leq\log(1+\epsilon)$ for $\epsilon>-1$. The KL
divergence can be upper bounded as

$d_{\text{KL}}(P_{0},P_{1})=-\frac{1}{2}\log_{2}(1-4\epsilon^{2})\leq
2\epsilon^{2}.$

We can now apply the Le Cam’s theorem for the set of Bernoulli distributions
with metric $d$ being the $\ell_{1}$-norm as

$\inf_{\hat{\theta}}\max_{P\in\mathcal{P}}\mathbb{E}_{P}\left[|\hat{\theta}_{n}(P)-H(P)|\right]\geq\frac{d(\theta(P_{0}),\theta(P_{1}))}{8}e^{-nd_{\text{KL}}(P_{0},P_{1})}\geq\frac{\epsilon^{2}}{4}e^{-2n\epsilon^{2}}$

Using this result with $\epsilon^{\prime}=\sqrt{\epsilon}$, the following
sample complexity can be obtained for estimating Shannon entropy.

######  Corollary F.2.

For any $\hat{\theta}_{n}$ such that $n\in o(1/\epsilon)$, there exists a
Bernoulli distribution $P$ for which

$\mathbb{E}_{P}\left[|\hat{\theta}_{n}(P)-H(P)|\right]\geq C\cdot\epsilon,$

with $C>0$ that does not depend on $\epsilon$.

First, note that there is some bound on error $r(\delta)$, either lower or
upper, that holds with probability $1-\delta$. This translate into the bound
$r(\delta)+\delta$ on the expected error in a straightforward manner. Thus the
lower bound presented in Corollary F.2 also implies that there is no high
probability estimator for entropy with $o(1/\epsilon)$ sample complexity for
discrete distributions. This can be used to lower bound of the entropy
estimator for joint distribution as follows.

Let
$\mathcal{B}=\left\\{\mathbf{b}=(b_{1},\dots,b_{d}):b_{j}\in\\{0,1\\}\right\\}$
be the vertices of the $d$ dimensional hypercube, and define a set of
$d$-dimensional distribution $\mathcal{P}_{\mathbf{b}}$ indexed by the element
of $\mathcal{B}$. Each $P_{\mathbf{b}}\in\mathcal{P}$ contains
$X_{0}\sim\text{Bern}(1/2)$ if $b_{i}=0$ and
$X_{1}\sim\text{Bern}(1/2-\epsilon)$ if $b_{i}=1$, i.e.

$P_{\mathbf{b}}=X_{b_{1}}\oplus\cdots\oplus X_{b_{d}}$

and

$\mathcal{P}=\left\\{P_{\mathbf{b}}:\mathbf{b}\in\\{0,1\\}^{d}\right\\}\enspace.$

It is clear that $\mathcal{P}$ is a subset of the tree-structured
distributions and each distribution contains $d$ independent Bernoulli random
variables, thus

$H(P_{\mathbf{b}})=\sum_{i=1}^{d}H(X_{b_{i}})$

Therefore any estimator that achieves at most $\epsilon\cdot d$ additive error
for $H(P_{\mathbf{b}})$ has to estimate each individual Bernoulli distribution
with at most $\epsilon$ error. The sample complexity of any estimator of
$H(P_{\mathbf{b}})$ with an additive error $O(\epsilon d)$ is
$\Omega(d/\epsilon)$. ∎

##  Appendix G Proof of Theorem 6.1

###### Proof.

Algorithm 5 clearly has $\tilde{O}(b)$ communication complexity and
$\tilde{O}(b)$ space complexity, since it only has to maintain a counter of
collisions between $b$-bit hashes.

To prove that Algorithm 5 is $\alpha$-locally differentially private, note
that given $v_{i}$ the distribution of $\hat{v}_{i}$ is independent of every
other random variable. Also note that each $v_{i}$ is deterministic function
of $h$, $q_{i}$ and $x_{i}$. Therefore it suffices to show that for each user
$i$ and all $v,v^{\prime},\hat{v}\in\\{1,\ldots,2^{b}\\}$ we have

$\frac{\Pr[\hat{v}_{i}=\hat{v}~{}|~{}v_{i}=v]}{\Pr[\hat{v}_{i}=\hat{v}~{}|~{}v_{i}=v^{\prime}]}\leq
e^{\alpha}.$

Since user $i$ replaces $v_{i}$ with a hash value chosen uniformly at random
from $\\{1,\ldots,2^{b}\\}$ with probability $1-\lambda$, we have

$\frac{\Pr[\hat{v}_{i}=\hat{v}~{}|~{}v_{i}=v]}{\Pr[\hat{v}_{i}=\hat{v}~{}|~{}v_{i}=v^{\prime}]}\leq\frac{\lambda+(1-\lambda)/2^{b}}{(1-\lambda)/2^{b}}=1+\frac{\lambda
2^{b}}{1-\lambda}=e^{\alpha}$

where the last equality substitutes
$\lambda=\frac{e^{\alpha}-1}{2^{b}+e^{\alpha}-1}$.

To prove the sample complexity results, let

$\bar{G}(X)=1-G(X)=\sum_{x}\Pr[X=x]^{2}=\Pr[X=X^{\prime}]$

where $X^{\prime}$ is independent and identically distributed as $X$. We will
calculate the expected value of each $c_{q}$. Suppose pair $q$ contains
samples $x_{i}$ and $x_{j}$. Since $q_{i}=q_{j}$, we have that if
$x_{i}=x_{j}$ then $c_{q}=1$ with probability
$\lambda^{2}+\frac{1-\lambda^{2}}{2^{b}}$, and otherwise $c_{q}=1$ with
probability $\frac{1}{2^{b}}$. Thus

$\displaystyle\operatorname{E}[c_{q}]$
$\displaystyle=\Pr[c_{q}=1~{}|~{}x_{i}=x_{j}]\Pr[x_{i}=x_{j}]+\Pr[c_{q}=1~{}|~{}x_{i}\neq
x_{j}]\Pr[x_{i}\neq x_{j}]$
$\displaystyle=\left(\lambda^{2}+\frac{1-\lambda^{2}}{2^{b}}\right)\Pr[x_{i}=x_{j}]+\frac{1}{2^{b}}\Pr[x_{i}\neq
x_{j}]$
$\displaystyle=\left(\lambda^{2}+\frac{1-\lambda^{2}}{2^{b}}\right)\Pr[x_{i}=x_{j}]+\frac{1}{2^{b}}(1-\Pr[x_{i}=x_{j}])$
$\displaystyle=\lambda^{2}\left(1-\frac{1}{2^{b}}\right)\Pr[x_{i}=x_{j}]+\frac{1}{2^{b}}$
$\displaystyle=\lambda^{2}\left(1-\frac{1}{2^{b}}\right)\bar{G}(X)+\frac{1}{2^{b}}$
(11)

where the last line follows because $x_{i}$ and $x_{j}$ are independent
samples from the distribution of $X$.

Let $m=\frac{n}{2}$. Note that the $c_{q}$’s are independent random variables
because each $c_{q}$ is defined using a distinct pair of samples and distinct
pair index. Also, each $c_{q}\in\\{0,1\\}$. Therefore, by the Chernoff bound,
for all $\epsilon_{0}\geq 0$ the average $\bar{c}=\frac{1}{m}\sum_{q}c_{q}$
satisfies

$\Pr\left[\left\lvert\bar{c}-\operatorname{E}[\bar{c}]\right\rvert\geq\epsilon_{0}\operatorname{E}[\bar{c}]\right]\leq
2\exp\left(-\frac{\epsilon_{0}^{2}m}{2+\epsilon_{0}}\operatorname{E}[\bar{c}]\right).$

We proved in Eq. (11) that
$\operatorname{E}[\bar{c}]=\lambda^{2}\left(1-\frac{1}{2^{b}}\right)\bar{G}(X)+\frac{1}{2^{b}}$.
Therefore for all $\epsilon_{0}\geq 0$

$\displaystyle\Pr\left[\left\lvert\hat{G}-G(X)\right\rvert\geq\epsilon_{0}\left(\bar{G}(X)+\frac{1}{\lambda^{2}(2^{b}-1)}\right)\right]$
$\displaystyle=$
$\displaystyle\Pr\left[\left\lvert\frac{2^{b}\bar{c}-1}{\lambda^{2}(2^{b}-1)}-\bar{G}(X)\right\rvert\geq\epsilon_{0}\left(\bar{G}(X)+\frac{1}{\lambda^{2}(2^{b}-1)}\right)\right]$
$\displaystyle\because\bar{G}(X)=1-G(X)$ $\displaystyle=$
$\displaystyle\Pr\left[\left\lvert\bar{c}-\frac{1}{2^{b}}-\lambda^{2}\left(1-\frac{1}{2^{b}}\right)\bar{G}(X)\right\rvert\geq\epsilon_{0}\left(\lambda^{2}\left(1-\frac{1}{2^{b}}\right)\bar{G}(X)+\frac{1}{2^{b}}\right)\right]$
$\displaystyle\because\textrm{Multiply by }\frac{\lambda^{2}(2^{b}-1)}{2^{b}}$
$\displaystyle=$
$\displaystyle\Pr\left[\left\lvert\bar{c}-\operatorname{E}[\bar{c}]\right\rvert\geq\epsilon_{0}\operatorname{E}[\bar{c}]\right]$
$\displaystyle\because\textrm{Eq.~{}\eqref{eq:zero}}$ $\displaystyle\leq$
$\displaystyle
2\exp\left(-\frac{\epsilon_{0}^{2}m}{2+\epsilon_{0}}\operatorname{E}[\bar{c}]\right)$
$\displaystyle\because\textrm{Chernoff}$ $\displaystyle=$ $\displaystyle
2\exp\left(-\frac{\epsilon_{0}^{2}m}{2+\epsilon_{0}}\left(\lambda^{2}\left(1-\frac{1}{2^{b}}\right)\bar{G}(X)+\frac{1}{2^{b}}\right)\right)$
$\displaystyle\because\textrm{Eq.~{}\eqref{eq:zero}}$ $\displaystyle=$
$\displaystyle
2\exp\left(-\frac{\epsilon_{0}^{2}m}{(2+\epsilon_{0})2^{b}}\left(\lambda^{2}\left(2^{b}-1\right)\bar{G}(X)+1\right)\right)$

Recalling that $\rho=\frac{1}{\lambda^{2}(2^{b}-1)}$ and continuing from above
we have

$\Pr\left[\left|\hat{G}-G(X)\right|\geq\epsilon_{0}(\bar{G}(X)+\rho)\right]\leq
2\exp\left(-\frac{\epsilon_{0}^{2}m}{(2+\epsilon_{0})\rho
2^{b}}(\bar{G}(X)+\rho)\right)\leq
2\exp\left(-\frac{\lambda^{2}\epsilon_{0}^{2}m}{4+2\epsilon_{0}}(\bar{G}(X)+\rho)\right)$

where the last inequality follows from $\frac{2^{b}}{2^{b}-1}\leq 2$. Letting
$\epsilon=\epsilon_{0}(\bar{G}(X)+\rho)$ we have

$\displaystyle\Pr\left[\left|\hat{G}-G(X)\right|\geq\epsilon\right]$
$\displaystyle\leq
2\exp\left(-\frac{\lambda^{2}\epsilon^{2}m}{4\bar{G}(X)+4\rho+2\epsilon}\right).$

Substituting $m=\frac{n}{2}$ and $\bar{G}(X)=1-G(X)$, and then rearranging, we
have that for all $\epsilon\geq 0$ and all $\delta\in(0,1)$ if we want
$|\hat{G}-G(X)|\leq\epsilon$ to hold with probability at least $1-\delta$ then
it suffices that

$n=\Omega\left(\frac{(1-G(X)+\rho+\epsilon)\log\frac{1}{\delta}}{\lambda^{2}\epsilon^{2}}\right)$

and since $3\max\\{x,y,z\\}\geq x+y+z$ it is enough to have

$n=\Omega\left(\frac{\max\\{1-G(X),2^{-b},\epsilon\\}\log\frac{1}{\delta}}{\lambda^{4}\epsilon^{2}}\right)$

where we plugged in $\rho=\frac{1}{\lambda^{2}(2^{b}-1)}$. Note that if
$\alpha\leq 1$ then $\frac{1}{\lambda}=O\left(\frac{2^{b}}{\alpha}\right)$ and
therefore it suffices that

$n=\Omega\left(\frac{2^{4b}\max\\{1-G(X),2^{-b},\epsilon\\}\log\frac{1}{\delta}}{\alpha^{4}\epsilon^{2}}\right)$

which proves the first sample complexity bound.

As for the second sample complexity bound, since $C(X)=-\log(1-G(X))$ we have

$\displaystyle\left|C(X)-\hat{C}\right|$
$\displaystyle=\left|\log(1-\hat{G})-\log(1-G(X))\right|=\left|\log\frac{1-\hat{G}}{1-G(X)}\right|$
$\displaystyle=\left\lvert\log\frac{1-G(X)+G(X)-\hat{G}}{1-G(X)}\right\rvert\leq\log\left(1+\frac{\left|\hat{G}-G(X)\right|}{1-G(X)}\right)\leq\frac{\left|\hat{G}-G(X)\right|}{1-G(X)}.$
(12)

Observe that $G(X)\in[0,1-\frac{1}{k}]$ for any random variable $X$ with
support size $k$. Therefore by Eq. (12) we have

$|\hat{C}-C(X)|\leq\frac{\left|\hat{G}-G(X)\right|}{1-G(X)}\leq
k\left|\hat{G}-G(X)\right|\leq\epsilon.$

where the last inequality holds if

$n=\Omega\left(\frac{2^{4b}k^{2}\log\frac{1}{\delta}}{\alpha^{4}\epsilon^{2}}\right)$

by the first sample complexity bound, because
$\max\\{1-G(X),2^{-b},\epsilon\\}\leq 1$. ∎