# Support Size Estimation: The Power of Conditioning

Diptarka Chakraborty111National University of Singapore, Singapore. Supported
in part by NUS ODPRT Grant, WBS No. R-252-000-A94-133. Email:
<EMAIL_ADDRESS>Gunjan Kumar 222National University of Singapore,
Singapore. Email<EMAIL_ADDRESS>Kuldeep S. Meel333National University of
Singapore, Singapore. Supported in part by National Research Foundation
Singapore under its NRF Fellowship Programme[NRF-NRFFAI1-2019-0004 ] ,
Ministry of Education Singapore Tier 2 grant MOE-T2EP20121-0011, and Ministry
of Education Singapore Tier 1 Grant [R-252-000-B59-114 ]. Email:
<EMAIL_ADDRESS>
###### Abstract

We consider the problem of estimating the support size of a distribution $D$.
Our investigations are pursued through the lens of distribution testing and
seek to understand the power of conditional sampling (denoted as COND),
wherein one is allowed to query the given distribution conditioned on an
arbitrary subset $S$. The primary contribution of this work is to introduce a
new approach to lower bounds for the COND model that relies on using powerful
tools from information theory and communication complexity.

Our approach allows us to obtain surprisingly strong lower bounds for the COND
model and its extensions.

  * •

We bridges the longstanding gap between the upper ($O(\log\log
n+\frac{1}{\epsilon^{2}})$) and the lower bound $\Omega(\sqrt{\log\log n})$
for COND model by providing a nearly matching lower bound. Surprisingly, we
show that even if we get to know the actual probabilities along with COND
samples, still $\Omega(\log\log n+\frac{1}{\epsilon^{2}\log(1/\epsilon)})$
queries are necessary.

  * •

We obtain the first non-trivial lower bound for COND equipped with an
additional oracle that reveals the conditional probabilities of the samples
(to the best of our knowledge, this subsumes all of the models previously
studied): in particular, we demonstrate that $\Omega(\log\log\log
n+\frac{1}{\epsilon^{2}\log(1/\epsilon)})$ queries are necessary.

##  1 Introduction

We consider the problem of estimating the support size of a distribution $D$
over a domain $\Omega$ (of size $n$), which is defined as follows:

$\displaystyle\textsc{supp}(D):=\\{x\mid D(x)>0\\}.$

We are interested in $(\epsilon,\delta)$-approximation444We want to estimate
$|\textsc{supp}(D)|$ by $\hat{s}$ such that
$\frac{|\textsc{supp}(D)|}{(1+\epsilon)}\leq\hat{s}\leq(1+\epsilon)|\textsc{supp}(D)|$
with the success probability at least $1-\delta$. This version is also
referred to as $(1+\epsilon)$-multiplicative factor estimation. Another
interesting version to consider is the additive $\epsilon n$-estimation (where
$n$ denotes the size of the domain) which asks to output a $\hat{s}$ such that
$|\textsc{supp}(D)|-\epsilon n\leq\hat{s}\leq|\textsc{supp}(D)|+\epsilon n$
with the success probability at least $1-\delta$. Unless otherwise stated
explicitly, we consider the multiplicative variant. of the size of
$\textsc{supp}(D)$ (i.e., $|\textsc{supp}(D)|$). For simplicity in exposition,
throughout this paper, we consider $\delta$ to be a small constant (more
specifically, 1/3, which can be reduced to any arbitrary small constant.). The
support size estimation is a fundamental problem in data science and finds a
myriad of applications ranging from database management, biology, ecology,
genetics, linguistics, neuroscience, and physics (see [VV11] and the
references therein). Naturally, the distribution is not specified explicitly,
and therefore, the complexity of the problem depends on the queries that one
is allowed to the distribution. As such, the primary objective is to minimize
the number of queries (aka _query complexity_).

Along with support size estimation, several other properties of distributions
have attracted investigations over the past three decades (see [Can20]). As
such, several query models have been considered by the research community. The
simplest model SAMP only allows drawing independent and identically
distributed samples from $D$. Valiant and Valiant [VV11] showed that to get an
estimation up to an additive factor of $\epsilon n$ (for any $\epsilon>0$),
$O(n/\epsilon^{2}\log n)$ samples suffice, which was subsequently improved to
$O(\frac{n}{\log n}\log^{2}(1/\epsilon))$ by Wu and Yang [WY19]. Further, Wu
and Yang proved that $\Omega(\frac{n}{\log n}\log^{2}(1/\epsilon))$ samples
are also necessary to get an estimate up to an additive error of $\epsilon n$.
A natural extension to SAMP is called _probability-revealing sample_ or PR-
SAMP, due to Onak and Sun [OS18], wherein instead of just returning an
independent sample $x$ from $D$ (as in SAMP), the oracle provides a pair
$(x,D(x))$ (i.e., a sample along with the probability assigned on it by $D$).
Onak and Sun showed that to estimate the support size up to an additive error
of $\epsilon n$, $\Theta(1/\epsilon^{2})$ samples are necessary and sufficient
in the PR-SAMP model. The same upper bound for the PR-SAMP model was also
implicit in the work by Canonne and Rubinfeld [CR14].

As we seek to explore more powerful models than PR-SAMP, a model of interest
is DUAL [BDKR05, GMV09, CR14] wherein we have access to two oracles: One is
SAMP that provides a sample from $D$, and another is EVAL that given any
$x\in\Omega$, outputs the value of $D(x)$. In the DUAL model, for any
$\epsilon_{1},\epsilon_{2}\in(0,1]$, distinguishing between whether the
support size of $D$ is at most $\epsilon_{1}n$ or at least $\epsilon_{2}n$
requires $\Theta(1/(\epsilon_{2}-\epsilon_{1})^{2})$ queries [CR14]. An
extension of EVAL is CEVAL wherein for totally ordered domains, given $x$,
CEVAL outputs $\sum_{y\preccurlyeq x}D(x)$. Similarly, CDUAL is an extension
of DUAL where we have access to oracles SAMP and CEVAL. Caferov et al.
[CKOS15] showed that $\Omega(\frac{1}{\epsilon^{2}})$ queries are needed in
the CDUAL model to estimate the support size up to an additive factor of
$\epsilon n$. However, to the best of our knowledge, no non-trivial result is
known for the support size estimation problem with $(1+\epsilon)$
multiplicative error in the above models.

While SAMP, PR-SAMP, and DUAL are natural models, they are limiting in theory
and practice as they fail to capture several scenarios wherein one is allowed
more powerful access to the distribution under consideration. Accordingly,
Chakraborty _et al._ [CFGM16] and Canonne _et al._ [CRS15] initiated the study
of a more general sampling model COND, where we are allowed to draw samples
conditioning on any arbitrary subsets of the domain $\Omega$. More
specifically, the sampling oracle takes a subset $S\subseteq\Omega$ chosen by
the algorithm and returns an element $x\in S$ with probability $D(x)/D(S)$ if
$D(S)>0$. The models proposed by Chakraborty et al. and Canonne et al. differ
in their behavior for the case when $D(S)=0$. The model proposed by
Chakraborty _et al._ [CFGM16] allows the oracle to return a uniformly random
element from $S$ when $D(S)=0$. On the other hand, the COND model defined in
Canonne _et al._ [CRS15] assumes that the oracle (and hence the algorithm)
returns “failure” and terminates if $D(S)=0$555 Note that analyzing each step
of the algorithm makes it possible to determine the set, conditioning on which
caused the algorithm to output “failure” and terminate. The rest of the
algorithm can then execute with the information that $D(S)=0$ for the above
set $S$. Therefore, for the simplicity of exposition, we will assume that the
COND model defined in Canonne _et al._ returns “failure” when $D(S)=0$ but the
algorithm does not terminate.. Note that the COND model of Canonne _et al._ is
more powerful than that of Chakraborty _et al._ since, when $D(S)=0$, in the
former case, we get to know that $D(S)=0$ whereas in the latter case, we get a
uniformly random element of $S$.

The relative power of the COND model of Canonne et al. over that of
Chakraborty et al. is also exhibited in the context of support size
estimation. Acharya, Canonne, and Kamath [ACK15] designed an algorithm with
query complexity $\tilde{O}(\log\log n/\epsilon^{3})$ in the COND model of
Chakraborty _et al._ to estimate the support size up to $(1+\epsilon)$
multiplicative factor under the assumption that the probability of each
element is at least $\Omega(1/n)$. They also note that the assumption of a
lower bound on the probability of each element is required for their
techniques to work. Surprisingly, a result of Falahatgar et al. [FJO+16]
implies that $O(\log\log n+\frac{1}{\epsilon^{2}})$ queries are sufficient for
COND model of Canonne _et al._ for any arbitrary probability distribution,
i.e., there is no requirement for the assumption of lower bound on the
probability of each element666They considered oracle access in which, given
any $S\subseteq\Omega$, it can be determined if
$S\cap\textsc{supp}(D)=\emptyset$ or not. Clearly, the COND model of Canonne
_et al._ generalizes this model. It is worth noting that in the SAMP model, to
get any meaningful upper bound, we need the assumption that each element has a
probability at least $1/n$; however, such an assumption is not needed in the
COND model or its extensions.. On the lower bound side, we only know that at
least $\Omega(\sqrt{\log\log n})$ COND queries are necessary [CFGM16].

The two models were introduced in the context of uniformity testing, wherein
the choice of how to handle the case of $D(S)=0$ did not make any significant
differences. We would like to emphasize that Canonne et al.’s model is more
powerful than that of Chakraborty et al., and thus any lower bound shown in
the first one also provides the same in the latter one. Moreover, the model of
Canonne et al. closely approximates the behavior of modern probabilistic
programming systems [GHNR14]. Therefore, throughout this paper, we consider
the COND model of Canonne et al.

Since its introduction, the COND model has attained significant attention both
in theory and practice. From a theoretical perspective, various other
distribution testing problems have been studied under the COND model [FJO+15,
KT19, Nar21] and its variant like _subcube conditioning model_ [BC18, CCK+21,
CJLW21]. Apart from that, the COND model and its variants find real-world
applications in the areas like formal methods and machine learning (e.g.,
[CM19, MPC20, GJM22]). Also, the modern probabilistic programming systems
extend classical programs with the addition of sampling and _observe_ , where
the semantics of the observe match that of Canonne et al.’s COND model
[GHNR14].

It is worth remarking that the COND model is incomparable with PR-SAMP.
Therefore, it is quite natural, both from a theory and practical perspective,
to consider a sampling model that inherits power from both COND and PR-SAMP.
We consider a model where we are allowed to condition on any arbitrary subset
$S\subseteq\Omega$, and if $D(S)>0$, we receive a sample $x\in S$ with
probability $D(x)/D(S)$ (as in COND) along with the probability assigned on it
by $D$ (i.e., $D(x)$); “failure” otherwise. We refer to this model as
_probability-revealing conditional sample_ 777The name is motivated from the
PR-SAMP model [OS18]. or in short COND-PR. To the best of our knowledge,
Golia, Juba, and Meel [GJM22] were the first ones to initiate the study of the
COND-PR model. Their work focused on the multiplicative estimation of entropy
on the COND-PR model. Golia et al. were primarily motivated to investigate the
COND-PR model upon the observation that the usage of the model counter and a
sampler can simulate the COND-PR model wherein a circuit specifies the
distribution. Also, implicit in their study is that the availability of model
counter and samplers [DM22] allows one to simulate generalization of COND-PR
model wherein for a given input $D$ and $S$ in addition to $D(x)$ for a
sampled item $x\in S$, the oracle also returns the value of $D(x)/D(S)$ (the
conditional probability of $x$ given $S$). We refer to this model as
conditional sampling evaluation model888The name is motivated from the
standard _evaluation_ model EVAL [RS09] where given any $x\in\Omega$, we get
the value of the probability density function of $D$ at $x$., or in short
COND-EVAL. To the best of our knowledge, the COND-EVAL subsumes all the
previously studied variants of the COND model (see Figure 1, and Section 5
where we provide a few examples showcasing the power of COND-EVAL).

SAMPPR-SAMPEVALDUALCONDCEVALCDUALCOND-PRCOND-EVAL Figure 1: Relative power of
different models: An edge $u\to v$ means the model $v$ is more powerful than
the model $u$.

To summarize, there has been a long line of research that has relied on the
usage of the COND model and its variants, resulting in significant
improvements in the query complexity for several problems in distribution
testing. While there has been a multitude of techniques for obtaining upper
bounds for the COND model and its variants, such has not been the case for
lower bounds. In particular, the prior techniques developed in the context of
support size estimation for COND model have primarily relied on the
observation that an algorithm $\mathcal{A}$ that makes $q$ COND queries can be
simulated by a decision tree of $O(q2^{q^{2}})$ nodes. Accordingly, the
foregoing observation allows one to obtain $\Omega(\sqrt{\log\log n})$ lower
bound for COND, which leaves open a major gap with respect to the upper bound
of $O(\log\log n+\frac{1}{\epsilon^{2}})$. The situation is even more dire
when considering models that augment COND with powerful oracles such as EVAL
since the approach based on decision tree fails due to additional information
supplied by oracles such as EVAL, and accordingly, no non-trivial lower bounds
are known for models such as CDUAL, COND-EVAL, and the like. Therefore, there
is a desperate need for new lower bound techniques to fully understand the
power of COND model and its natural extensions.

###  1.1 Our Contribution

One of our primary contributions is to provide a seemingly new approach to
proving lower bounds in the COND model and its more powerful variants. Our
approach is based on information theory and reductions to problems in
communication complexity. We note that the communication complexity-based
approaches to lower bounds have been explored in prior work; such approaches
are only limited to weaker models such as SAMP and PAIRCOND models [BCG19,
BBM12]. While we demonstrate the application of our approach in the context of
support size estimation for different variants of COND, we believe our
approach is of general interest and can be applied to other distribution
testing problems.

For ease of exposition, here we situate the discussion in the context of the
most general model, COND-EVAL. One of the inherent difficulties in proving any
non-trivial lower bound for the COND-EVAL model arises from the fact that the
different sets for conditioning can overlap in an arbitrary manner (and unlike
in PAIRCOND model, these sets are of arbitrary size) and further be chosen in
an adaptive way. The adaptivity and arbitrary size of sets make it extremely
difficult to upper bound the conditional entropy at any step of the algorithm.
Furthermore, the power of revealing the probability mass (on any set) by a
COND-EVAL query risks licking “a lot of” information which makes it even more
challenging. The key departure from earlier work is the choice of an infinite
family of distributions, so the range of outcomes of an algorithm is
continuous and so cannot be encoded with any finite (or even infinite) length
message. To this end, we rely on Fano’s inequality, a fundamental tool in
information theory, to show lower bounds for statistical estimation. In order
to apply Fano’s inequality, we need to upper bound the information gain at
every step of the algorithm. Our approach proceeds by relying on a restricted
model of conditioning where the queried sets are laminar, i.e., either they do
not intersect or are subsets/supersets of each other. Accordingly, we first
obtain lower bounds for the restricted model and lift to the lower bounds for
the COND-EVAL model.

Our approach is compelling enough to provide non-trivial lower bounds in the
most potent COND-EVAL model, for which no lower bound was known before.
However, before providing the usefulness of the general framework, let us
demonstrate how a special instantiation of our approach can be applied to
obtain strong lower bounds in the context of support size estimation for the
COND model and its (simpler) variants. Our first result bridges the long-
standing gap between the upper bound of $O(\log\log n+\frac{1}{\epsilon^{2}})$
and the lower bound of $\Omega(\sqrt{\log\log n})$ in case of COND model. In
particular, we obtain an $\Omega(\log\log
n+\frac{1}{\epsilon^{2}\log(1/\epsilon)})$ lower bound on the query complexity
in the COND-PR model, which in turn provides the same lower bound for the PR-
SAMP, DUAL, and COND model.

######  Theorem 1.1.

Every algorithm that, given COND-PR access to a distribution $D$ on $[n]$ and
$\epsilon\in(0,1]$, estimates the support size $|\textsc{supp}(D)|$ within a
multiplicative $(1+\epsilon)$-factor with probability at least $\frac{2}{3}$,
must make $\Omega(\log\log n+\frac{1}{\epsilon^{2}\log(1/\epsilon)})$ queries
to the COND-PR oracle.

Recall the best-known upper bound for the support size estimation in COND is
$O(\log\log n+\frac{1}{\varepsilon^{2}})$ and therefore, the above theorem
achieves a near-matching lower bound in the context of COND and COND-PR. It is
rather surprising that the combination of PR-SAMP and COND does not yield
power in the context of the support size estimation. It is worth mentioning
that we already know of a lower bound of $\Omega(1/\epsilon^{2})$ for the PR-
SAMP and DUAL model due to [CR14]. Hence, our result along with [CR14]
provides a lower bound of $\Omega(\log\log n+\frac{1}{\epsilon^{2}})$ for
these two models (i.e., we can get rid of the annoying $\log(1/\epsilon)$
factor from the lower bound term of Theorem 1.1).

Our primary result is to establish the first non-trivial lower bound in the
context of COND-EVAL, which in turn provides the first-known lower bound for
many other previously studied models, such as CDUAL.

######  Theorem 1.2.

Any algorithm that, given COND-EVAL access to a distribution $D$ on $[n]$
approximates the support size $|\textsc{supp}(D)|$ within a multiplicative
$(1+\epsilon)$-factor with probability at least $2/3$, must make
$\Omega(\log\log\log n+\frac{1}{\epsilon^{2}\log(1/\epsilon)})$ queries.

Since COND-EVAL subsumes COND-PR, we have the upper bound of $O(\log\log
n+\frac{1}{\epsilon^{2}})$, and the ensuing gap leaves open an interesting
question. It is worth remarking that it is not hard to see (by extending the
proof of Theorem 1.1) that the upper bound is nearly tight if one were to
replace COND-EVAL with approximate-COND-EVAL wherein, for a given $D$ and $S$,
the oracle essentially provides an estimate of $D(S)$ up to a small
multiplicative error (see the discussion at the end of Section 4.2). We
conjecture that the upper bound is tight for COND-EVAL.

######  Conjecture 1.

Any algorithm that, given COND-EVAL access to a distribution $D$ on $[n]$
approximates the support size $|\textsc{supp}(D)|$ within a multiplicative
$(1+\epsilon)$-factor with probability at least $2/3$, must make
$\Omega(\log\log n+\frac{1}{\epsilon^{2}\log(1/\epsilon)})$ queries.

The validity of the above conjecture would establish the significant power of
the COND model in the context of support size estimation as COND-EVAL and
COND-PR, despite being augmented with powerful oracles in addition to
conditioning, do not yield better algorithms.

###  1.2 Technical Overview

#### Lower bound for COND-PR.

We start with deriving the lower bound of Theorem 1.1. It consists of two
parts – an $\Omega(\log\log n)$ lower bound for a multiplicative $4/3$-factor
estimation algorithm and an
$\Omega(\frac{1}{\epsilon^{2}\log\frac{1}{\epsilon}})$ lower bound for an
additive $\epsilon n$-factor algorithm. We first show an $\Omega(\log\log n)$
lower bound for a multiplicative $4/3$-factor algorithm (3.1). For that
purpose, we consider an _integer-guessing_ game between Alice and Bob, where
Alice uniformly at random chooses an integer $x\in[\log n]$. Then sends a
message (binary string) to Bob. Upon receiving the message, Bob’s task is to
guess $x$ correctly (with high probability). Since the entropy of the chosen
integer is $\log\log n$, by Shannon’s source coding theorem, the length of the
message, on average, must be $\Omega(\log\log n)$. We show that if there
exists an algorithm $T$ that makes $t$ COND-PR queries then it suffices for
Alice to send a message of length $O(t)$, and hence $t=\Omega(\log\log n)$.

To show the same, for each $x\in[\log n]$, Alice considers a distribution
$D_{x}$ with support $[2^{x}]$. The probability $D_{x}(j)$ of an element
$j\in[2^{x}]$ in $D_{x}$ decreases exponentially as $j$ increases. Alice runs
the algorithm $T$ on the distribution $D_{x}$ and would like to send an
encoding of the run (i.e., the sampled element along with its probability for
each step). Using a trivial encoding, even to send a sampled element, requires
$\Theta(\log n)$ bits, which is already more than the Shannon entropy and thus
would not give any lower bound. So Alice needs to use a slightly clever
encoding. Roughly speaking, since the probabilities are exponentially
decreasing, the conditional sampling from any set $S\subseteq[n]$ returns an
element from the first “few” smallest elements of $S$ (with high probability).
Thus even though $|S|$ can be large, the sampled element (at each step) can be
specified by only constantly many bits. Alice sends this encoding of the
sampled element (along with its probability value which can again be encoded
with constantly many bits due to the construction of $D_{x}$’s) at each of $t$
steps to Bob. Hence Bob knows the complete run and thus can determine the
index $x$ using the algorithm $T$. We provide the detailed proof in Section 3.

Next, we turn our attention to showing the dependency of $\epsilon$ in the
lower bound. We show an
$\Omega\Big{(}\frac{1}{\epsilon^{2}\log\frac{1}{\epsilon}}\Big{)}$ lower bound
for an additive $\epsilon n$-factor algorithm (4.24). Since a multiplicative
$(1+\epsilon)$-factor algorithm also provides an additive $\epsilon n$-factor
estimation, the above lower bound also works for $(1+\epsilon)$-factor
algorithms. We prove this bound by showing a reduction from a well-studied
communication complexity problem, namely the _Gap-Hamming distance_ problem
(see Section 4.3), and then applying the known lower bound for the Gap-Hamming
distance [CR12]. The proof argument (and the dependence on $\epsilon$) also
holds true for COND-EVAL model, and therefore, the detailed proof is presented
in Section 4.3.

#### Lower bound for COND-EVAL.

The approach used to get an $\Omega(\log\log n)$ lower bound in the COND-PR
model cannot be used to show the same for the COND-EVAL model. One of the
powers of COND-EVAL model (over the COND-PR) comes from its ability to compute
$D(S):=\sum_{j\in S}D(j)$ for any set $S\subseteq[n]$.

Recall the hard instance $D_{x}$’s used in the $\Omega(\log\log n)$ lower
bound proof for the COND-PR model. Let $X^{*}:=\\{2^{x}\mid x\in[\log n]\\}$.
It is easy to verify that $D_{x}(X^{*})\neq D_{x^{\prime}}(X^{*})$ for any
$x\neq x^{\prime}\in[\log n]$. So, the value of $x$ (and hence the support of
$D_{x}$) can be determined using only one COND-EVAL query with the set
$X^{*}$. Thus our lower bound argument fails in this model. For the sake of
intuition about how we overcome the above issue, we want to point out that the
above argument does not fail if we have an approximate COND-EVAL query instead
of COND-EVAL query, i.e., if the oracle gives the estimate of $D(S)$ up to a
small additive error say $\frac{3}{2^{n^{0.1}}}$. This is because for
$x,x^{\prime}\in[\frac{\log n}{10},\log n]$, we have
$|D_{x}(X^{*})-D_{x^{\prime}}(X^{*})|\leq\frac{2}{2^{n^{0.1}}}$. Hence, given
that $x,x^{\prime}\in[\frac{\log n}{10},\log n]$, we can not distinguish
between $x$ and $x^{\prime}$ as the estimate could be the same for both $x$
and $x^{\prime}$.

To mitigate the above issue (for COND-EVAL), we construct a new set of hard
distributions. Our objective is that for any set $X^{*}$, if the value of
$D_{x}(X^{*})$ is in $(0,1)$, then value of $D_{x}(X^{*})$ should not give
information about $x$. One plausible approach could be to replace each
distribution $D_{x}$ with a finite set of distributions such that for any set
$S\subseteq[n]$, there are many distributions in the instance with the same
value of $D(S)$. Unfortunately, we do not know how to get such a set of
distributions preserving other useful properties needed for our proof. Our key
high-level idea is to replace the distribution $D_{x}$ (for each $x\in[\log
n]$) with a distribution over an infinite number of distributions. This way,
the value of $D_{x}(X^{*})$ cannot be used to determine the value of chosen
$x$ (as there can be infinite values of $x$ having the same value $D(X^{*})$).
However, one immediate issue that arises is if our instance has an infinite
domain (here distributions), then how do we even get a distribution over an
infinite space? Further, like before, we still want the probabilities to
exponentially decrease so that the sampled element is always among the first
few smallest elements of the conditioning set $S$. Fortunately, in statistics
and compositional data analysis, there has been a study of probability
distributions on the set of all (infinite) distributions. Based on
requirements, our choice is the well-studied Dirichlet distribution that
satisfies a strong independence property (4.6) which is necessary for our
analysis.

A Dirichlet distribution on support $[K]$ with parameters
$\alpha_{1},\cdots,\alpha_{K}>0$ has a probability density function given by
$f(p_{1},\dots,p_{K})=\frac{\prod_{i\in[K]}p_{i}^{\alpha_{i}-1}}{B(\alpha_{1},\cdots,\alpha_{K})}$
where $\\{p_{i}\\}_{i\in K}$ belongs to the standard $K-1$ simplex, i.e.,
$\sum_{i\in[K]}p_{i}=1$ and $p_{i}\geq 0$ for all $i\in[K]$ and
$B(\alpha_{1},\cdots,\alpha_{K})$ is a normalizing constant. When
$\alpha_{1}=\cdots=\alpha_{K}=1$, the Dirichlet distribution is just the
uniform distribution on $K-1$ simplex. The higher the value of parameter
$\alpha_{i}$, the higher the (expected) value of $p_{i}$. Since we want the
probability value to be exponentially decreasing, we set the values of
$\alpha_{1},\cdots,\alpha_{n}$ exponentially decreasing. Then for each index
$x$ chosen uniformly at random from $[\log n]$, we sample a distribution
$D_{x}$ with support $[2^{x}]$ from the Dirichlet distribution with parameters
$\alpha_{1},\cdots,\alpha_{2^{i}}$. By the standard Yao’s principle, it
suffices to show high error probability of any deterministic algorithm that
correctly estimates the support size (and hence determines the index $x$) of
the distribution sampled as above. Note that the entropy of the index is still
$\log\log n$, but the previous communication framework (between Alice and Bob)
will not be useful here. This is because the range of the outcomes of the
algorithm (the actual and the conditional probabilities) is continuous and so
cannot be encoded with any finite (or even infinite) length message. Instead,
we apply Fano’s inequality, a tool from information theory.

Roughly speaking, we show that the information gain (about the index) by the
query’s outcome at every step is $O(1)$. Since the initial entropy of the
index is $\log\log n$, at least $\log\log n$ steps of the algorithm are
needed. The main technical challenge is to upper bound the information gain at
every step. It is particularly challenging as it requires calculating the
explicit density function (for the outcome) corresponding to each index. These
density functions are conditioned on the previous outcomes and thus change at
every step. Further, the set queried by the algorithms can be adaptive, which
makes our task even more difficult. To ease our analysis, we first assume that
the queried sets by the algorithm are _laminar_ , i.e., either they do not
intersect or are subsets/supersets of each other. Our $\Omega(\log\log n)$
lower bound holds for COND-EVAL model for all the algorithms satisfying this
laminar condition. It is not hard to observe that any algorithm that makes $t$
general queries can be simulated by an algorithm that queries the laminar
family of sets and makes at most $2^{t}$ queries. This observation gives us
$\Omega(\log\log\log n)$ lower bound for the general case. We believe that
$\Omega(\log\log n)$ is the correct lower bound for the general case, but
(perhaps it is an artifact of our analysis that) the laminar structure is
necessary for applying the independence properties of Dirichlet distribution
which leads to only an $\Omega(\log\log\log n)$ lower bound. For the sake of
simplicity, we first prove the lower bound for a weaker model called, SET-
EVAL, (in Section 4.1), and then extend to the general COND-EVAL model (in
Section 4.2). We refer to the oracle that, given any $S\subseteq[n]$, just
outputs the value of $D(S)$, as SET-EVAL oracle. Since using a COND-EVAL query
we can simulate a SET-EVAL query, the COND-EVAL model is at least as powerful
as SET-EVAL. We now describe the proof of the lower bound for the SET-EVAL
model in more detail.

For an index $x$ chosen uniformly at random from $[\log n]$, we sample a
distribution $D_{x}$ with support $[2^{x}]$ from the Dirichlet distribution
with parameters $\alpha_{1},\cdots,\alpha_{2^{x}}$
($\alpha_{j}=\frac{1}{2^{j}}$ for all $j\in[x]$). By the standard Yao’s
principle, it suffices for us to show a high error probability of any
deterministic algorithm that correctly estimates the support size (and hence
determines the index $x$) of the distribution sampled as above. Let $T$ be any
such deterministic algorithm that queries a laminar family of sets. We need to
show that $T$ must make $\Omega(\log\log n)$ queries. The main technical
ingredient in the proof is to show that the information gain (about the index
$x$) by the outcome of any query of the algorithm is $O(1)$ (4.7). This
implies that the total information gain is $O(t)$, where $t$ is the number of
queries (4.7). Then Fano’s inequality immediately implies that
$t\geq\Omega(\log\log n)$. Let the $i$-th query ($i\in[t]$) be denoted by set
$A_{i}$ and the outcome of the $i$-th query (sum of probabilities of elements
in the set $A_{i}$) be denoted by $Z_{i}$. The information gain (about the
index $x$) by the $i$-th query (for any $i\in[t]$) is the conditional mutual
information $I(X;Z_{i}|Z^{i-1})$ where $Z_{i}$ is the random variable denoting
the outcome of $i$-th query, $Z^{i-1}=(Z_{1},\dots,Z_{i-1})$ is the random
variable denoting the vector of previous outcomes and $X$ is the random
variable denoting the uniformly chosen index $x$ from $[\log n]$. By
definition, the conditional mutual information $I(A;B|C)$ for random variables
$A,B,C$ is equal to the expectation (over $C$) of the KL divergence between
the joint distribution $Q_{(A,B)|C}$ and the product distribution
$Q_{A|C}\times Q_{B|C}$. The technical difficulty is to upper bound the
conditional mutual information $I(X;Z_{i}|Z^{i-1})$ by $O(1)$. This is
particularly challenging since the joint and the product distributions are not
explicitly given, and queries are adaptive. To overcome this difficulty, at
any step $i\in[t]$ (after $(i-1)$-th query), we first partition the $[\log n]$
into four groups denoted by $L^{i}_{0},L^{i}_{1},L^{i}_{2},L^{i}_{3}$ such
that for the first three groups, the outcome of the algorithm (i.e., $Z_{i}$)
is (deterministically) determined by the previous outcomes of the algorithm
(i.e., $Z^{i-1}=(Z_{1},\dots,Z^{i-1}))$ whereas for any $x$ in the fourth
group $L^{i}_{3}$, the outcome is not fixed (given previous outcomes) but
comes from a distribution (which we show to be also Dirichlet). Let this
distribution be denoted by $Q_{x}$ for $x\in L^{i}_{3}$. The information gain
by the $i$-th query (4.11) is $\log 3$ (because there are three groups for
which outcome is deterministically determined) plus the information gain
corresponding to the last group $L^{i}_{3}$. This term can be upper bounded by
the maximum KL divergence between distributions $Q_{x}$ and $Q_{x^{\prime}}$
for any $x,x^{\prime}\in L^{i}_{3}$. Thus our goal is to show that KL
divergence between $Q_{x}$ and $Q_{x^{\prime}}$ for any $x,x^{\prime}\in
L^{i}_{3}$ is $O(1)$. Using the independence property of Dirichlet
distributions (4.6) and the laminar structure of query sets, we show that the
KL divergence between the distributions $Q_{x}$ and $Q_{x^{\prime}}$ is equal
to the KL divergence between two beta distributions with different parameters
(beta distributions are a special case of Dirichlet distributions). The
explicit formula for KL divergence between two beta distributions is well-
known (e.g., see [JKB95]), and we use this formula to upper bound the KL
divergence by $O(1)$.

######  Remark 1.1.

Technically, the above lower bound for SET-EVAL (and COND-EVAL) does not hold
if it is promised that the probabilities in the given distribution are
rational numbers. This is because, in the lower bound instances above, the
probability of an element can be any arbitrary real number in $(0,1)$.
However, we can use the following standard fact to show that the lower bound
holds even with the rational probabilities.

A Polya urn is an urn containing $\alpha_{i}$ balls of color $i$, for each
$i\in[K]$. The urn evolves at each discrete time step – a ball is sampled
uniformly at random. The ball’s color is observed, and two balls of the
observed color are returned to the urn. Let $X_{i,m}$ be the number of balls
of color $i$ (for each $i\in[K]$) added after $m$ time steps. Clearly
$D_{m}=(\frac{X_{1,m}}{m},\cdots,\frac{X_{K,m}}{m})$ is a probability
distribution over $[K]$. It can be shown that the distributions
$D_{1},\cdots,D_{m}$ converges to a Dirichlet distribution with parameters
$\alpha_{1},\dots,\alpha_{K}$ when $m$ tends to $\infty$ [BM73].

Instead of using Dirichlet distribution in our lower bound proof, we can use
the distribution $D_{m}$ for sufficiently large $m$. Since for any $m$, the
probabilities in $D_{m}$ are rational numbers, we can get the lower bound even
when the probabilities are rationals.

#### The power of COND-EVAL.

We further demonstrate the power of the COND-EVAL model by showing an
algorithm with constant query complexity for a number of distribution testing
problems for which there are strong lower bounds known for the COND-PR and
COND model. Our first example is the well-studied _Equivalence testing_
problem. Here, given two distributions $D$ and $D^{\prime}$, the goal is to
accept if $D=D^{\prime}$ and reject if their _total variation distance_
$||D-D^{\prime}||_{TV}=\sum_{i\in[n]}|D(i)-D^{\prime}(i)|>\epsilon$ (both with
high probability). It is known that $\Omega(\sqrt{\log\log n})$ queries are
necessary in the COND model [ACK15]. On the other hand, $\Omega(1/\epsilon)$
queries are required in the COND-PR model. (Consider a uniform distribution
$U$ on $[n]$. Now randomly choose $i,j\in[n]$. We modify $U$ to construct
another distribution $U^{\prime}$ by setting $U^{\prime}(i)=2/n$,
$U^{\prime}(j)=0$, and no changes in the probability mass of other elements.
Note that $\epsilon=||U-U^{\prime}||_{TV}=2/n$. It is easy to see that
$\Omega(n)=\Omega(\frac{1}{\epsilon})$ queries are required to distinguish $U$
and $U^{\prime}$ in the COND-PR model.) We show that Equivalence testing can
be done in just two COND-EVAL queries. The above upper bound result extends to
another unrelated problem for the COND-EVAL model – the problem of testing if
the given distribution is _$m$ -grained_, i.e., the probability of each
element is an integer multiple of $1/m$. Finally, we show that the
multiplicative $(1+\epsilon)$-approximation of square of the $L_{2}$ norm
$(\sum_{j\in[n]}D(j)^{2})$ of a distribution $D$ can be computed using
$O(\frac{1}{\epsilon^{2}})$ queries of COND-EVAL. To the best of our
knowledge, this problem has been studied previously only in the SAMP model
[GR11], wherein it was shown that $\Omega(\frac{\sqrt{n}}{\epsilon^{2}})$
queries are required. We refer the readers to Section 5 for the details of the
above upper bound results.

#### The power of bounded-set conditioning.

We further study the support size estimation problem when we allow SAMP oracle
access and conditioning on sets of size at most $k$ (see Section 6). We show a
lower bound of $\Omega(n/k)$ (Theorem 6.2) and an upper bound of
$O(\frac{n\log\log n}{k})$ (Theorem 6.1) for constant factor approximation in
this model. The upper bound holds for the COND oracle model, while our lower
bound holds for the stronger COND-EVAL oracle model.

Both the upper and lower bounds are not difficult to establish. Falahatgar et
al. [FJO+16] showed that $O(\log\log n)$ queries are sufficient (with no
restriction on the size of the set for conditioning) to get a constant
approximation for oracle access which, given any $S\subseteq[n]$, returns
whether $S\cap\textsc{supp}(D)=\emptyset$ or not. Oracle access to a set of
size $s$ can be simulated by $s/k$ oracle access when conditioning on at most
$k$-sized sets is allowed. This gives an upper bound of $O(\frac{n\log\log
n}{k})$. Interestingly, the hard instance for the bounded-set conditioning to
estimate the support size is when the support size is constant. We formally
prove our lower bound in Section 6.

###  1.3 Conclusion

We investigate the power of conditioning for estimating the support size up to
a multiplicative $(1+\epsilon)$-factor. Till date, there is a gap between the
upper bound of $O(\log\log n+1/\epsilon^{2})$ and the lower bound of
$\Omega(\sqrt{\log\log n})$ in the standard COND model. In this paper, we
close this gap by providing a lower bound of $\Omega(\log\log
n+\frac{1}{\epsilon^{2}\log\frac{1}{\epsilon}})$. We actually show the lower
bound in even a more powerful model, namely COND-PR, where in addition to the
conditioning, one is also allowed to get the actual probability of the sampled
elements (i.e., a combination of COND and PR-SAMP). In the dependency of
$\epsilon$, there is a small gap of $\log(1/\epsilon)$ factor, and we want to
leave the problem of removing this factor from the lower bound term as an open
problem.

It is quite surprising that the combination of COND and PR-SAMP does not yield
more power compared to only the COND model in the context of the support size
estimation. We thus continue our investigation by appending the algorithms
with an even more powerful oracle that could also get the conditional
probabilities of the sampled elements (not just the actual probabilities). We
call this model COND-EVAL. This model turns out to be more powerful in the
context of several other important distribution testing problems, as
demonstrated in Section 5. For the support size estimation, we show a lower
bound of $\Omega(\log\log\log n+\frac{1}{\epsilon^{2}\log\frac{1}{\epsilon}})$
in this COND-EVAL model. On the technical side, this paper introduces many new
ideas, such as using continuous distribution (Dirichlet distribution) for
constructing hard instances and applying information theory and communication
complexity tools to conditional sampling models. We hope that such techniques
could be useful for showing non-trivial lower bounds for other distribution
testing problems as well.

For the support size estimation problem in the COND-EVAL model, currently, we
only know of an $O(\log\log n)$ upper bound, whereas we could only show a
lower bound of $\Omega(\log\log\log n)$. We would like to pose the problem of
closing this gap as an interesting open problem.

##  2 Preliminaries

#### Notations.

We use the notation $[n]$ to denote the set of integers $\\{1,2,\cdots,n\\}$.
For any probability distribution $D$ defined over $[n]$, for any $i\in[n]$,
let $D(i)$ denote the probability of choosing $i$ when sampling according to
$D$. For any subset $S\subseteq[n]$, we use $D(S)$ to denote the probability
mass assigned on $S$ by the distribution $D$, i.e., $D(S):=\sum_{i\in S}D(i)$.

#### Different access models.

Let $D$ be a distribution over $[n]$. Below we formally define the query
models that we consider in this paper.

######  Definition 2.1 (COND Query Model).

A _conditional_ (in short, COND) oracle for $D$ takes as input a set
$S\subseteq[n]$, and if $D(S)>0$, returns an element $j\in S$ with probability
$D(j)/D(S)$. If $D(S)=0$, then the oracle returns “failure”.

######  Definition 2.2 (COND-PR Query Model).

A _probability-revealing conditional sampling_ (in short, COND-PR) oracle for
$D$ takes as input a set $S\subseteq[n]$, and if $D(S)>0$, returns a pair
$(j,D(j))$ (where $j\in S$) with probability $D(j)/D(S)$. If $D(S)=0$, then
the oracle returns “failure”.

######  Definition 2.3 (COND-EVAL Query Model).

A _conditional evaluation_ (in short, COND-EVAL) oracle for $D$ takes as input
a set $S\subseteq[n]$, and if $D(S)>0$, returns a tuple $(j,D(j),D(j)/D(S))$
(where $j\in S$) with probability $D(j)/D(S)$. If $D(S)=0$, then the oracle
returns “failure”.

######  Definition 2.4 (SET-EVAL Query Model).

A _set evaluation_ (in short, SET-EVAL) oracle for $D$ takes as input a set
$S\subseteq[n]$, and returns the value $D(S)$.

It is straightforward to observe that the COND-EVAL is at least as powerful as
the COND-PR oracle which in turn is at least as powerful as the COND oracle.
Further, the COND-EVAL oracle is at least as powerful as the SET-EVAL
oracle.999Since on input $S$, the COND-EVAL oracle returns a tuple
$(j,D(j),D(j)/D(S))$ where $j\in S$, one can compute the value of $D(S)$
whenever $D(S)>0$; otherwise (when $D(S)=0$) the COND-EVAL oracle returns
“failure”, from which one can infer that $D(S)=0$.

#### Shannon entropy and source coding theorem.

The _entropy_ of a discrete random variable $X$ taking values in $\mathcal{X}$
is defined as $H(X):=\sum_{x\in\mathcal{X}}p(x)\log\frac{1}{p(x)}$ where
$p(x)=\Pr[X=x]$.

The seminal work of Shannon [Sha48] establishes a connection between the
entropy and the expected length of an optimal code that encodes a random
variable.

######  Theorem 2.1 (Shannon’s Source Coding Theorem [Sha48]).

Let $X$ be a discrete random variable over domain ${\cal X}$. Then for every
uniquely decodable code $C:{\cal X}\to\\{0,1\\}^{*}$, $\mathbb{E}(|C(X)|)\geq
H(X)$. Moreover, there exists a uniquely decodable code $C:{\cal
X}\to\\{0,1\\}^{*}$ such that $\mathbb{E}(|C(X)|)\leq H(X)+1$.

##  3 Lower Bound in COND-PR Model

In this section, we show a lower bound of $\Omega(\log\log
n+\frac{1}{\epsilon^{2}\log\frac{1}{\epsilon}})$ COND-PR queries, for any
algorithm that estimates the support size within a multiplicative
$(1+\epsilon)$-factor with high probability. Since COND-PR is more powerful
than COND, our lower bound holds for COND as well. Till date, a lower bound of
only $\Omega(\sqrt{\log\log n})$ is known for COND queries [CFGM16]. We want
to emphasize that the lower bound construction in [CFGM16] is quite
complicated and their framework cannot give better than $\Omega(\sqrt{\log\log
n})$ lower bound. This is because their lower bound is derived from the fact
that the number of leaves of a decision tree representing a $q$-query tester
is $O(2^{q^{2}})$ (note, this bound is tight), which must be at least
$\Omega(\log n)$, implying the $\Omega(\sqrt{\log\log n})$ lower bound.

See 1.1

We prove the above theorem by first showing that $\Omega(\log\log n)$ queries
are necessary to estimate the support size up to a multiplicative
$4/3$-factor. Next, we show that to achieve an additive $\epsilon
n$-approximation, $\Omega(\frac{1}{\epsilon^{2}\log(1/\epsilon)})$ queries are
required. Since multiplicative $(1+\epsilon)$-approximation of the support
size also implies an $\epsilon n$-additive approximation of the same, we get a
lower bound of $\Omega(\frac{1}{\epsilon^{2}\log(1/\epsilon)})$ on
multiplicative $(1+\epsilon)$-approximation algorithms as well. It turns out
$\Omega(\frac{1}{\epsilon^{2}\log(1/\epsilon)})$ bound holds for the stronger
model of COND-EVAL query model (and thus also for the COND-PR model).
Therefore, we defer the proof of lower bound for $\epsilon$-dependence to
Section 4.3 for the sake of clarity of exposition.

######  Lemma 3.1.

Any algorithm that, given COND-PR access to a distribution $D$ on $[n]$,
estimates $|Supp(D)|$ within a multiplicative $\frac{4}{3}$-factor with
probability at least $\frac{9}{10}$, must make $\Omega(\log\log n)$ queries to
the COND-PR oracle.

We devote the rest of this section in proving the above lemma. First, consider
the following simple _integer-guessing game_ between Alice and Bob: Alice
chooses an integer $x\in[\log n]$ uniformly at random. Bob’s task is to guess
the integer $x$.

Let us consider the randomized one-way communication complexity of the above
problem. More specifically, only Alice can send a message to Bob (but Bob
cannot send anything to Alice). Alice and Bob also have access to public
randomness. Then the question is how many bits Alice needs to send to solve
the above problem with probability at least $2/3$. The one-way communication
complexity is defined to be the minimum number of bits that is communicated in
any (randomized) protocol that solves the integer-guessing game.

By a simple application of Shannon’s source coding theorem (Theorem 2.1), we
show the following.

######  Claim 3.2.

The randomized one-way communication complexity of the above integer-guessing
game is $\Omega(\log\log n)$.

###### Proof.

Consider a one-way randomized protocol $P$ for the above integer-guessing
game, where with probability at least $2/3$, Alice sends at most $t$ bits to
Bob and Bob succeeds in guessing Alice’s chosen integer. Let $X$ be the random
variable denoting the integer chosen by Alice. Let the random variable $R$
denote the public randomness shared between Alice and Bob, to be used by the
randomized communication protocol $P$.

Now define the following encoding function $Enc$ to encode $X$ given $R$: If
using $R$ the protocol $P$ succeeds (i.e., Bob outputs Alice’s chosen integer
correctly), then encode the $t$ bits sent by Alice (according to the protocol
$P$); else encode $X$ using a trivial encoding (using at most $\log\log n+1$
bits). Then $\mathbb{E}[|Enc(X)|]\leq t+1/3\cdot(\log\log n+1)$ (since the
protocol $P$ succeeds with probability at least $2/3$ while Alice sending at
most $t$ bits to Bob). Since $X$ and $R$ are independent, the entropy of
$X\mid R$ is $H(X\mid R)=H(X)=\log\log n$. Now it follows from Shannon’s
source coding theorem (Theorem 2.1),

$\displaystyle\mathbb{E}[|Enc(X)|]\geq H(X\mid R)$ $\displaystyle\Rightarrow$
$\displaystyle t+1/3\cdot(\log\log n+1)\geq\log\log n$

which in turn implies $t\geq\Omega(\log\log n)$. ∎

Next, we provide a reduction from the above integer-guessing game to the
problem of estimating the support size up to $4/3$-multiplicative factor. We
start with constructing a hard distribution for the support size estimation.

For each $i\in[\log n]$, we construct a distribution $D_{i}$ on $[n]$ with
support size $2^{i}$ as follows: Set

$\displaystyle D_{i}(j)=\begin{cases}1/2^{j}&\text{ if }j\in[2^{i}-1]\\\
1/2^{2^{i}-1}&\text{ if }j=2^{i}\\\ 0&\text{ otherwise}.\end{cases}$

$2^{i}+1$$n$$2^{i}$$2^{i}-1$$1$$2$$3$$\frac{1}{2}$$\frac{1}{4}$$\frac{1}{8}$$\frac{1}{2^{2^{i}-1}}$
Figure 2: The distribution $D_{i}$

Given $S\subseteq[n]$ and $j\in S$, if $j$ is the $k$-th largest element in
$S$ then we define rank of $j$ in $S$, denoted by $\textsc{rank}_{S}(j)$, to
be $k$. E.g., let $s_{1}<s_{2}<\cdots<s_{c}$ be the elements in $S$. Then the
rank of $s_{r}$ (for $r\in[c]$) in $S$ is $\textsc{rank}_{S}(s_{r})=r$.

For the sake of contradiction, we assume that there is a randomized algorithm
$T$ that, with probability at least $9/10$, estimates the support size of any
distribution on $[n]$ within a multiplicative $4/3$-factor by making at most
$t=t(n)$ COND-PR queries. Next, we describe a one-way communication protocol
between Alice and Bob to solve the integer-guessing game defined previously.
First recall, by the construction,
$|\textsc{supp}(D_{i+1})|=2|\textsc{supp}(D_{i})|$, for any $i\in[\log n-1]$.
Now, since $T$ estimates the support size of any distribution within
$4/3$-factor, from the output of the algorithm $T$, it is straightforward to
retrieve $i$ if the input distribution is $D_{i}$ (for any $i\in[\log n]$)
with probability at least $9/10$. Let us now describe a strategy used by Alice
and Bob to solve the integer-guessing game using one-way communication.

Alice and Bob share a public random string $R$ (to be used by the randomized
algorithm $T$). Recall, in the first step of the integer guessing game, Alice
chooses $x\in[\log n]$ uniformly at random. Then Alice wants to construct a
message on receiving which Bob can guess $x$ correctly with high probability.
To construct the message, Alice considers the distribution $D_{x}$ (as defined
earlier). Then she runs the algorithm $T$ (using the random string $R$) with
COND-PR oracle queries to $D_{x}$. Given $R$, the algorithm $T$ can be viewed
as a decision tree $\mathcal{T}_{R}$ in a straightforward way. Note, each leaf
node of this decision tree is labelled by some $i\in[\log n]$. Since $T$
places exactly $t$ queries, the height of the decision tree $\mathcal{T}_{R}$
is also $t$. At any step $\ell$, let $A_{\ell}$ denote the set to condition
on, and $(z_{\ell},p_{\ell})$ denote the output of COND-PR oracle after
placing a query to $D_{x}$ condition on the set $A_{\ell}$. Thus $z_{\ell}\in
A_{\ell}$ and $p_{\ell}=D_{x}(z_{\ell})$. Note, at any step $\ell$, the
decision tree $\mathcal{T}_{R}$ chooses the set $A_{\ell}$ based on
$(A_{1},z_{1},p_{1}),\cdots,(A_{\ell-1},z_{\ell-1},p_{\ell-1})$. The root to
leaf path in $\mathcal{T}_{R}$ is specified by the sequence
$(A_{1},z_{1},p_{1}),\cdots,(A_{t},z_{t},p_{t})$. Then Alice constructs a
“short” message so that Bob can retrieve the above sequence from her message.

For an $\ell\in[t]$, let $X_{\ell}$ denote
$\textsc{rank}_{A_{\ell}}(z_{\ell})$. Instead of directly encoding $z_{\ell}$,
Alice encodes $X_{\ell}$. Observe, by the construction of the distributions
$D_{i}$’s, for any $\ell\in[t]$, the value of $p_{\ell}$ can be either
$1/2^{z_{\ell}}$, or $1/2^{z_{\ell}-1}$, or $0$. Alice uses two bits to encode
these three values – say $00$ for the value $0$, $01$ for the value
$1/2^{z_{\ell}}$, and $10$ for the value $1/2^{z_{\ell}-1}$. Formally, each
pair $(z_{\ell},p_{\ell})$, Alice uses the encoding $\textsc{blk}(\ell)$ as
follows: First, encode $X_{\ell}$ using $\lceil\log X_{\ell}\rceil$ bits. Then
append that with two bits to encode the value of $p_{\ell}$ (as mentioned
above). We refer to each $\textsc{blk}(\ell)$ as _block_. Note,
$|\textsc{blk}(\ell)|=\lceil\log X_{\ell}\rceil+2$ .

Ideally, Alice would like to send the string
$\textsc{blk}(1)\circ\textsc{blk}(2)\circ\cdots\textsc{blk}(\ell)$ (let
$\circ$ denote the concatenation operation). However, note, the length of
$\textsc{blk}(\ell)$ is different for different $\ell$’s. To make sure Bob can
decode each encoding block correctly, Alice only uses every alternate bits of
her message to encode $\textsc{blk}(\ell)$’s and sets remaining bits as 1 or 0
depending on whether it is the end of an encoding block or not. More
specifically, suppose $\textsc{blk}(\ell)=b^{\ell}_{1}\dots
b^{\ell}_{|\textsc{blk}(\ell)|}$. Then Alice sends the following message

$M_{R}(x)=b^{1}_{1}\thinspace 0\thinspace b^{1}_{2}\thinspace 0\thinspace\dots
0\thinspace b^{1}_{|\textsc{blk}(1)|}\thinspace 1\thinspace
b^{2}_{1}\thinspace 0\thinspace b^{2}_{2}\thinspace 0\dots 0\thinspace
b^{2}_{|\textsc{blk}(2)|}1\cdots\thinspace b^{t}_{1}\thinspace 0\thinspace
b^{t}_{2}\thinspace 0\dots 0\thinspace b^{t}_{|\textsc{blk}(t)|}\thinspace 1$

to Bob. Note, an even digit is $0$ unless it marks the end of
$\textsc{blk}(\ell)$ for some $\ell\in[t]$. Total number of bits sent by Alice
is

$|M_{R}(x)|=2\sum_{\ell\in[t]}|\textsc{blk}(\ell)|=2\sum_{\ell\in[t]}(\lceil\log
X_{j}\rceil+2)\leq 6t+2\log(X_{1}\cdots X_{t}).$ (1)

Let us now describe how Bob uses the message $M_{R}(x)$ to decode back the
sequence $(A_{1},z_{1},p_{1}),\cdots,(A_{t},z_{t},p_{t})$. Recall, the random
string $R$ is shared between both Alice and Bob. Thus Bob knows the decision
tree $\mathcal{T}_{R}$ and so the set $A_{1}$. Now, Bob starts traversing the
decision tree using the message $M_{R}(x)$. He finds the first even bit set to
1 and then discards all the even bits up to that part of the message
$M_{R}(x)$ to retrieve $\textsc{blk}(1)$. By the construction of
$\textsc{blk}(1)$, the last two bits denotes whether $p_{1}$ is $0$, or
$1/2^{z_{1}}$, or $1/2^{z_{1}-1}$. The remaining bits represent
$\textsc{rank}_{A_{1}}(z_{1})$. Once Bob gets the rank of $z_{1}$ in $A_{1}$,
he retrieves $z_{1}$ (since he knows the set $A_{1}$), and then he retrieves
the value of $p_{1}$. Using $(z_{1},p_{1})$, he traverses the decision tree
and reaches the next internal node and gets to know the set $A_{2}$. Then he
extracts $\textsc{blk}(2)$ from the message $M_{R}(x)$ as before and proceeds.
At the end, he decodes back the whole sequence
$(A_{1},z_{1},p_{1}),\cdots,(A_{t},z_{t},p_{t})$, and thus reaches the desired
leaf node in the decision tree $\mathcal{T}_{R}$. This completes the
description of the strategy used by Alice and Bob.

Now, if the algorithm $T$ using the random string $R$ outputs an estimate of
$|\textsc{supp}(D_{x})|$ up to $4/3$-factor, Bob also gets to know that
estimated value by following the above described one-way protocol. Observe,
since by the construction, $|\textsc{supp}(D_{i+1})|=2|\textsc{supp}(D_{i})|$,
for any $i\in[\log n-1]$, from the estimated value Bob can easily compute $x$
correctly. Hence, the above one-way communication protocol solves the integer-
guessing game with probability at least $9/10$.

It only remains to argue about the communication cost (the message length sent
by Alice) of the above one-way protocol. For that purpose, we claim the
following.

######  Claim 3.3.

With probability at least $5/6$, $X_{1}X_{2}\cdots X_{t}\leq 23^{t}$.

We defer the proof of the above claim to the end. Let us now provide an upper
bound on the message length by assuming the above claim. It implies from
Equation 1 that with probability at least $5/6$, $|M_{R}(x)|\leq 16t$. Hence,
with probability at least $5/6\cdot 9/10=3/4$, using the above one-way
communication protocol Alice needs to send at most $16t$ bits and Bob outputs
Alice’s chosen integer $x$ correctly. It now follows from 3.2,
$t\geq\Omega(\log\log n)$ which concludes the proof of 3.1.

Now it only remains to prove 3.3.

###### Proof of 3.3.

Recall, for each $\ell\in[t]$, $X_{\ell}$ is a random variable denoting
$\textsc{rank}_{A_{\ell}}(z_{\ell})$. We now bound its expectation and
variance. Further recall, $z_{\ell}$ was sampled from the distribution $D_{x}$
condition on the set $A_{\ell}\subseteq[n]$. Suppose $|A_{\ell}|=m$. Let
$a_{1}<a_{2}<\cdots a_{m}$ be the elements of $A_{\ell}$ in the order. Let
$q_{j}$ denote the conditional probability of $a_{j}$. Let us first provide an
upper bound on $q_{j}$ for any $3\leq j\leq m$. Observe, by the construction,
$D_{x}(a_{j})\geq 2D_{x}(a_{j+1})$ for all $j\in[m-2]$, and
$D_{x}(a_{m-1})\geq D_{x}(a_{m})$. Thus, we have
$D_{x}(a_{j})\leq\frac{D_{x}(a_{1})}{2^{j-2}}$ for all $3\leq j\leq m$. So we
get
$q_{j}=\frac{D_{x}(a_{j})}{D_{x}(A_{\ell})}=\frac{D_{x}(a_{j})}{\sum_{k\in[m]}D_{x}(a_{k})}\leq\frac{1}{2^{j-2}}$,
for any $3\leq j\leq m$.

Now, we have $\mathbb{E}[X_{\ell}]=\sum_{j\in[m]}j\cdot q_{j}\leq
q_{1}+q_{2}+\sum_{j\geq 3}j\cdot\frac{1}{2^{j-2}}<6$. Also
$\mathbb{E}[X_{\ell}^{2}]=\sum_{j\in[m]}j^{2}\cdot q_{j}\leq
1+4q_{2}+\sum_{j\geq 3}\frac{j^{2}}{2^{j-2}}\leq 23$.

Consider the random variable $Z:=X_{1}X_{2}\cdots X_{t}$. Since
$X_{1},\cdots,X_{t}$ are independent, we have
$\mathbb{E}[Z]=\mathbb{E}[X_{1}]\cdots\mathbb{E}[X_{t}]\leq 6^{t}$ and
$Var(Z)=\mathbb{E}[X_{1}^{2}]\cdots\mathbb{E}[X_{t}^{2}]-(\mathbb{E}[X_{1}])^{2}\cdots(\mathbb{E}[X_{t}])^{2}\leq
23^{t}$. By Chebyshev inequality, for any $r$, we have
$\Pr[Z\leq\mathbb{E}[Z]+r]\geq 1-Var(Z)/r^{2}\geq 1-23^{t}/r^{2}$. Set
$r=\sqrt{6\cdot 23^{t}}$. Then we get $Z\leq 6^{t}+\sqrt{6\cdot
23^{t}}<23^{t}$ with probability at least $5/6$. ∎

##  4 Lower bound for COND-EVAL

In this section, we provide a lower bound on the query complexity of the
support size estimation problem in the COND-EVAL query model. Recall, for a
given distribution $D$, a COND-EVAL query with a set $S\subseteq[n]$ outputs
an element $j\in S$ sampled as per its conditional probability $D(j)/D(S)$
(like COND), its actual probability $D(j)$ (like COND-PR) and its conditional
probability $D(j)/D(S)$. It is easy to see that the COND-EVAL query model can
simulate the SET-EVAL model as $D(S)=\sum_{i\in S}D(i)$ can be determined from
the values $D(j)/D(S)$ and $D(j)$, for any $S\subseteq[n]$.

We now illustrate the power of the SET-EVAL queries in our case of support
size estimation. Recall, in the proof of 3.1, we construct, for each
$x\in[\log n]$, a distribution $D_{x}$ on $[n]$ with support size $2^{x}$.
Suppose $x$ is uniformly chosen at random from $[\log n]$. Then we prove any
deterministic algorithm that, given COND-PR access to $D_{x}$ and estimates
the support size of $D_{x}$ within multiplicative $4/3$-factor with high
probability, must make $\Omega(\log\log n)$ queries. We now argue that if the
algorithm is given SET-EVAL access to $D_{x}$ then just one query is
sufficient to estimate the support size with high probability. Let
$X^{*}:=\\{2^{x}|x\in[\log n]\\}$. It is easy to verify that $D_{x}(X^{*})\neq
D_{x^{\prime}}(X^{*})$ for any $x\neq x^{\prime}\in[\log n]$. Hence, the value
of $x$ (and hence the support of $D_{x})$ can be determined via a SET-EVAL
query with the set $X^{*}$.

To mitigate the above issue, we need to construct a new set of hard
distributions to show the lower bound. Our idea to construct hard distribution
over distributions, for this model, is to replace the distribution $D_{x}$
(for each $x\in[\log n]$) with a distribution over an infinite number of
distributions. This way, the value of $\sum_{j\in X^{*}}D_{x}(j)$ cannot be
used to determine the value of Alice’s chosen $x$. We will give a formal
description of our hard distribution later. In this section, we first prove
the following theorem.

######  Theorem 4.1.

Any algorithm that, given COND-EVAL access to a distribution $D$ on $[n]$
approximates the support size $|\textsc{supp}(D)|$ within multiplicative
$4/3$-factor with probability at least $2/3$, must make $\Omega(\log\log\log
n)$ queries.

Later, we will show in 4.24 that
$\Omega(\frac{1}{\log(1/\epsilon)\epsilon^{2}})$ queries in the COND-EVAL
model are needed to approximate the support size within an additive $\epsilon
n$-factor. Together, we get the following lower bound.

See 1.2

We first prove a lower bound of $\Omega(\log\log\log n)$ for the weaker SET-
EVAL model, which illustrates the main idea. Later in Section 4.2 we will
generalize this proof idea to the COND-EVAL model.

###  4.1 Warm-up with Lower bound for SET-EVAL

######  Theorem 4.2.

Any algorithm that, given SET-EVAL access to a distribution $D$ on $[n]$
approximates the support size $|\textsc{supp}(D)|$ within multiplicative
$4/3$-factor with probability at least $2/3$, must make $\Omega(\log\log\log
n)$ queries.

To prove the above theorem, we first assume that the queried sets by the
algorithm are laminar, i.e., for any two queried sets $A_{i},A_{j}$ either
$A_{i}\cap A_{j}=\emptyset$ or $A_{i}\subset A_{j}$ or $A_{j}\subset A_{i}$.
We argue that an algorithm that makes $t$ SET-EVAL queries can be simulated by
an algorithm that makes at most $2^{t}$ SET-EVAL queries such that the queried
sets form a laminar family. Next, we show a lower bound of $\Omega(\log\log
n)$ on the number of queries with the laminar family assumption. As a
consequence, we deduce $\Omega(\log\log\log n)$ query lower bound for
algorithms with arbitrary (i.e., with no assumption of queried sets forming a
laminar family) SET-EVAL queries.

######  Lemma 4.3.

Any algorithm that makes $t$ SET-EVAL queries to a given distribution $D$, can
be simulated by an algorithm that makes at most $2^{t}$ SET-EVAL queries with
the property that the queried sets are laminar.

###### Proof.

Let algorithm $\mathcal{A}$ makes $t$ queries of SET-EVAL. We give an
algorithm $\mathcal{B}$ that can simulate $\mathcal{A}$ such that the queried
sets by $\mathcal{B}$ are laminar. Let the queries of $\mathcal{A}$, in order,
be denoted by $A_{1},\dots,A_{t}$. Then the first set queried by $\mathcal{B}$
is also $A_{1}$. On receiving the value $D(A_{1})$, the algorithm
$\mathcal{B}$ (using $\mathcal{A}$) determines the set $A_{2}$. Then the
algorithm $\mathcal{B}$, instead of $A_{2}$, queries the sets $A_{2}\cap
A_{1}$ and $A_{2}\cap A^{c}_{1}$ (where $A^{c}_{2}=[n]\setminus A_{2}$), and
receives the values $D(A_{2}\cap A_{1})$ and $D(A_{2}\cap A^{c}_{1})$. Note,
$D(A_{2})=D(A_{2}\cap A_{1})+D(A_{2}\cap A^{c}_{1})$. Thus $\mathcal{B}$ can
then determine the set $A_{3}$ (again using $\mathcal{A}$).

In general, instead of $A_{i}$, the algorithm $\mathcal{B}$ queries all the
sets in

$\mathcal{C}:=\\{A_{i}\cap C_{1}\cap C_{2}\cdots\cap C_{i-1}\mid
C_{j}\in\\{A_{j},A^{c}_{j}\\},\;\forall j\in[i-1]\\}.$

where $A^{c}_{j}=[n]\setminus A^{j}$. Note that $|\mathcal{C}|=2^{i-1}$ and
$D(A_{i})=\sum_{C\in\mathcal{C}}D(C)$. From the value of $D(A_{i})$, the
algorithm $\mathcal{B}$, using $\mathcal{A}$, determines $A_{i+1}$, and
proceeds.

It is easy to see that the sets queried by $\mathcal{B}$ form a laminar family
and total number of queries is at most $\leq\sum_{j\in[t]}2^{j-1}\leq 2^{t}$.

∎

So now to prove Theorem 4.2 it suffices to show the following.

######  Lemma 4.4.

Any algorithm that queries laminar family of sets and given SET-EVAL access to
a distribution $D$ on $[n]$, approximates the support size
$|\textsc{supp}(D)|$ within multiplicative $4/3$-factor with probability at
least $2/3$, must make $\Omega(\log\log n)$ queries.

To establish our result we need to introduce a few definitions and known
results.

#### Basics of information theory.

The _Kullback–Leibler divergence_ or simply _KL divergence_ (also called
relative entropy) between two discrete probability distributions $P$ and $Q$
defined on same probability space $\mathcal{X}$ is given by :

$KL(P||Q):=\sum_{x\in\mathcal{X}}p(x)\log\frac{p(x)}{q(x)}$

where $p$ and $q$ are probability mass functions of $P$ and $Q$ respectively.
If $P$ and $Q$ are continuous distributions then the summation is replaced by
integration: $KL(P||Q)=\int_{x\in\mathcal{X}}p(x)\log\frac{p(x)}{q(x)}\,dx$.

Let $X$ and $Y$ be two random variables over the space
$\mathcal{X}\times\mathcal{Y}$. If their joint distribution is $Q_{X,Y}$ and
marginal distributions $Q_{X}$ and $Q_{Y}$ respectively, then the mutual
information $I(X;Y)$ is defined as:

$I(X;Y):=KL(Q_{X,Y}||Q_{X}\times Q_{Y}).$

For three random variables $X,Y,Z$, the _conditional mutual information_
$I(X;Y|Z)$ is defined as

$\displaystyle I(X;Y|Z):=\mathbb{E}_{Z}[KL(Q_{(X,Y)|Z}||Q_{X|Z}\times
Q_{Y|Z})].$

If $Z$ is a discrete random variable taking values in $\mathcal{Z}$ then we
have

$\displaystyle\mathbb{E}_{Z}[KL(Q_{(X,Y)|Z}||Q_{X|Z}\times
Q_{Y|Z})]=\sum_{z\in\mathcal{Z}}Q_{Z}(z)\cdot
KL(Q_{(X,Y)|Z=z}||Q_{X|Z=z}\times Q_{Y|Z=z})$
$\displaystyle=\sum_{z\in\mathcal{Z}}Q_{Z}(z)\cdot I(X;Y|Z=z).$

If $Z$ is a continuous random variable with density function $p$ then

$\displaystyle\mathbb{E}_{Z}[KL(Q_{(X,Y)|Z}||Q_{X|Z}\times
P_{Y|Z})]=\int_{z\in\mathcal{Z}}Q_{Z}(z)\cdot
KL(P_{(X,Y)|Z=z}||P_{X|Z=z}\times P_{Y|Z=z})\,dz.$
$\displaystyle=\int_{z\in\mathcal{Z}}Q_{Z}(z)\cdot I(X,Y|Z=z)\,dz.$

For any three random variables $X,Y,Z$, the _chain rule_ for mutual
information says that

$I(X;(Y,Z))=I(X;Y)+I(X;Z|Y).$

######  Theorem 4.5 (Fano’s inequality).

Consider discrete random variables $X$ and $\hat{X}$ both taking values in
$\mathcal{V}$. Then

$\Pr[\hat{X}\neq X]\geq 1-\frac{I(X;\hat{X})+\log 2}{\log|\mathcal{V}|}.$

Consider the random variables $X,Z,\hat{X}$. If the random variable $\hat{X}$
depends only on $Z$ and is conditionally independent on $X$, then we have
$I(X;\hat{X})\leq I(X;Z)$. This inequality is known as the _data processing
inequality_. For further exposition, readers may refer to any standard
textbook on information theory (e.g., [CT06]).

#### Dirichlet Distribution.

Now, we describe Dirichlet distribution, which is one of the main building
blocks of our hard distribution. For any $K\in\mathbb{N}$, a random variable
$P=(P_{1},\dots,P_{K})$ is said to have a _Dirichlet distribution_ with
parameters $\alpha_{1},\dots,\alpha_{K}>0$ (denoted by
$Dir(\alpha_{1},\dots,\alpha_{K}))$ if it has a probability density function
$f(p_{1},\dots,p_{K})$ given by:

$\displaystyle
f(p_{1},\dots,p_{K})=\begin{cases}\frac{\prod_{i\in[K]}p_{i}^{\alpha_{i}-1}}{B(\alpha_{1},\dots,\alpha_{K})}&\text{
if }\sum_{i\in[K]}p_{i}=1,p_{i}\in(0,1]\\\ 0&\text{ otherwise}.\end{cases}$

The denominator $B(\alpha_{1},\dots,\alpha_{K})$ is a normalization constant
to ensure total probability is $1$. When $\alpha_{1}=\dots=\alpha_{K}=1$, the
Dirichlet distribution is just a uniform distribution on the set of all
probability distributions on $[K]$, i.e., on
$\\{(p_{1},\dots,p_{K})|\sum_{i=1}^{K}p_{i}=1,\;\forall_{i\in[K]}p_{i}\geq
0\\}$. It is known that
$\mathbb{E}[P_{i}]=\frac{\alpha_{i}}{\sum_{i\in[K]}\alpha_{i}}$. Thus higher
the value of $\alpha_{i}$, the higher is the expected value of $P_{i}$. For
the special case when $K=2$, the Dirichlet distribution is known as beta
distribution denoted as $Beta(\alpha_{1},\alpha_{2})$.

Independence property of Dirichlet distribution: Our proof will crucially rely
on the independence property of Dirichlet distribution stated below.

######  Proposition 4.6.

Fix $A\subseteq[K]$, $B\subset A$ and $d\in(0,1)$. Suppose
$(P_{1},\dots,P_{K})\sim Dir(\alpha_{1},\dots,\alpha_{K})$. Then conditioned
on $\sum_{i\in A}P_{i}=d$, we have $\frac{\sum_{i\in B}P_{i}}{d}\sim
Beta(\sum_{i\in B}\alpha_{i},\sum_{i\in A\setminus B}\alpha_{i})$.

######  Remark 4.1.

If $A\cap B\neq\emptyset$ and neither $A\subset B$ nor $B\subset A$, then
there is no explicit distribution of $\frac{\sum_{i\in B}P_{i}}{d}$ given
$\sum_{i\in A}P_{i}=d$. This is why, to prove our lower bound, we assume that
the sets queried by the algorithm form a laminar family.

#### Yao’s Principle.

Yao’s principle [Yao77] is a standard tool to show lower bounds for randomized
algorithms. It relates two kinds of randomness – the randomness over inputs
and the randomness used by the randomized algorithm.

Consider a problem over inputs $\mathcal{X}$ (the set $\mathcal{X}$ can be
infinite). Let $\gamma$ be a probability distribution over $\mathcal{X}$ and
$X\in\mathcal{X}$ be an input chosen as per $\gamma$. Let $\mathcal{T}$ be the
set of all deterministic algorithms with complexity $t$ (for us, it is query
complexity). For $x\in\mathcal{X}$ and $T\in\mathcal{T}$, let the cost
$c(x,T)$ take the value $1$ if $T$ gives the wrong answer on input $x$ and $0$
otherwise. Therefore, $\Pr[T\thinspace\text{gives wrong answer on}\thinspace
x]=\mathbb{E}[c(x,T)]$.

Note that a randomized algorithm $R$ is just a probability distribution over
the set of deterministic algorithms $\mathcal{T}$. Let $r$ be any probability
distribution over $\mathcal{T}$ and $R$ be a random algorithm chosen as per
$r$.

From Yao’s principle, we have

$\displaystyle\max_{x\in\mathcal{X}}\Pr[R\thinspace\text{gives wrong answer
on}\thinspace x]=\max_{x\in\mathcal{X}}\mathbb{E}[c(x,R)]$
$\displaystyle\geq\min_{T\in\mathcal{T}}\mathbb{E}[c(X,T)]=\min_{T\in\mathcal{T}}\Pr[T\thinspace\text{gives
wrong answer on}\thinspace X].$

#### Proof of 4.4.

From Yao’s principle, it suffices to consider a distribution $\gamma$ over a
set of inputs $\mathcal{X}$ (note, in our case, an input is a distribution)
and prove the statement of 4.4 for any deterministic algorithm with the
distribution $D$ being sampled from $\gamma$. Now we define a set of
distributions $\mathcal{X}$ on $[n]$ and a distribution $\gamma$ over it.

For any $x\in[\log n]$, $\mathcal{X}_{x}$ is a set of all probability
distributions on $[n]$ with the support $[2^{x}]$, i.e.,

$\mathcal{X}_{x}:=\\{(p_{1},\dots,p_{n})|\sum_{i=1}^{2^{x}}p_{i}=1,\text{ and
}\forall_{i\in[n]},p_{i}\geq 0,\text{ and }\forall_{i\in[2^{x}]},p_{i}>0\\}.$

Let $\mathcal{X}:=\cup_{x\in[\log n]}\mathcal{X}_{x}$. Now we define the
distribution $\gamma$.

Let $\alpha_{j}=\frac{1}{2^{j}}$ for all $j\in[n]$. The distribution $\gamma$
first picks $X\in[\log n]$ uniformly at random. Then it samples
$(P_{1},\dots,P_{2^{X}})\sim Dir(\alpha_{1},\dots,\alpha_{2^{X}})$ and returns
the distribution $(P_{1},\dots,P_{2^{X}},0,\dots,0)$. We use $D_{X}$ to denote
the distribution $(P_{1},\dots,P_{2^{X}},0,\dots,0)$.

Let $T$ be any deterministic algorithm that estimates the support size (up to
$4/3$-factor) of the distribution $D_{X}$ sampled from $\gamma$ with
probability at least $2/3$ (where the probability is over the random choice of
input distributions). Let us denote the output of $T$ by $N$. Let
$\hat{X}\in[\log n]$ be such that $2^{\hat{X}}\in[\frac{3}{4}N,\frac{4}{3}N]$.
Since $|\textsc{supp}(D_{x+1})|=2|\textsc{supp}(D_{x})|$, for every $x\in[\log
n]$) and $N$ is within a $4/3$-multiplicative factor of the support size,
$\hat{X}=X$. Therefore,

$\Pr[X=\hat{X}]\geq\Pr\Big{[}\frac{3}{4}|\textsc{supp}(D_{X})|\leq
N\leq\frac{4}{3}|\textsc{supp}(D_{X})|\Big{]}\geq 2/3.$ (2)

For simplicity, from now on, we consider $\hat{X}$ as the output of the
algorithm.

Note that both $X$ and $\hat{X}$ are random variables taking values in $[\log
n]$. By Fano’s inequality ( Theorem 4.5), we have

$\Pr[X=\hat{X}]\leq\frac{I(X;\hat{X})+\log 2}{\log\log n}.$ (3)

Let $t$ be the number of the queries made by $T$ (as mentioned in statement of
4.4, $T$ has access to SET-EVAL oracle and queries laminar family of sets). We
will show $I(X;\hat{X})=O(t)$. Hence, for $\Pr[\hat{X}=X]$ to be at least
$2/3$, the number of queries $t$ must be $\Omega(\log\log n)$.

Let the $i$th query ($1\leq i\leq t$) of $T$ be denoted by $A_{i}$. Note that
the set $A_{1}$ is fixed as $T$ is deterministic (whereas $A_{2},\dots,A_{t}$
are random variables). For any set $A\subseteq[n]$, $D_{X}(A)=\sum_{i\in
A}D_{X}(i)$ is the total probability mass of set $A$ in the (randomly chosen
distribution) $D_{X}$. Let $Z_{r}$ ($r\in[t]$) be the random variable equal to
$D_{X}(A_{r})$. At any step, the algorithm determines the set $A_{i}$ based on
the previous outcomes $Z_{1},\dots,Z_{i-1}$.

######  Claim 4.7.

If for all $i\in[t]$, $I(X;Z_{i}|Z_{1},\dots,Z_{i-1})=O(1)$, then
$I(X;\hat{X})=O(t)$.

###### Proof.

The output $\hat{X}$ is determined by the values of $Z_{1},\dots,Z_{t}$. Thus,

$\displaystyle I(X;\hat{X})$ $\displaystyle\leq I(X;Z_{1},\dots,Z_{t})$ (by
the data processing inequality)
$\displaystyle=\sum_{i\in[t]}I(X;Z_{i}|Z_{1},\dots,Z_{i-1})$
$\displaystyle\text{(by the chain rule of mutual information)}.$

Hence, if for all $i\in[t]$, $I(X;Z_{i}|Z_{1},\dots,Z_{i-1})=O(1)$, then
$I(X;\hat{X})=O(t)$. ∎

Next, we claim the following.

######  Lemma 4.8.

For all $i\in[t]$, $I(X;Z_{i}|Z_{1},\dots,Z_{i-1})=O(1)$.

Before proving the above, let us argue that the above implies 4.4. It follows
from Equation 3 along with 4.7, that

$\Pr[\hat{X}=X]\leq O(\frac{t}{\log\log n}).$

Then by Equation 2, $t\geq\Omega(\log\log n)$. This completes the proof of
4.4.

So it only remains to prove 4.8.

#### Proof of 4.8.

We use $Z^{i-1}$ to denote the tuple $(Z_{1},\cdots,Z_{i-1})$. For any random
variable $Y$, we use $Q_{Y}$ to denote the corresponding probability
distribution. When clear from the context, we will drop $Y$ from the
subscript. From the definition of conditional mutual information, we have

$\displaystyle I(X;Z_{i}|Z_{1},\dots,Z_{i-1})$
$\displaystyle=\int_{z^{i-1}}Q_{Z^{i-1}}(z^{i-1})I(X;Z_{i}|Z^{i-1}=z^{i-1})\,dz^{i-1}$
(4)

The following claim is now immediate from Equation 4.

######  Claim 4.9.

If for every $i\in[t]$ and $z^{i-1}$, $I(X;Z_{i}|Z^{i-1}=z^{i-1})=O(1)$, then
$I(X;Z_{i}|Z_{1},\dots,Z_{i-1})=O(1)$.

######  Lemma 4.10 ([SC19]).

Consider two random variables $X$ and $Z$, where $X$ is discrete. Suppose
there exists $N$ distributions $R_{1}(z),\dots,R_{N}(z)$ such that for all
$x\in X$ and for some $m>0$, it holds that

$\displaystyle\min_{j\in[N]}KL(Q_{Z|X}(\cdot|x)||R_{j})\leq m.$

Then we have

$\displaystyle I(X;Z)\leq\log N+m.$

The above lemma is informally called mutual information bound via covering.
Suppose we can partition $X$ into $N$ sets $L_{1},\dots,L_{N}$ such that for
all $x\in L_{j}$, the distributions $\\{Q_{Z|X=x}(\cdot|x)\\}_{x\in L_{j}}$
are close (note $Q_{Z|X=x_{1}}(\cdot|x_{1})$ and $Q_{Z|X=x_{2}}(\cdot|x_{2})$
can be different if $x_{1},x_{2}$ are not in same $L_{j})$ then maximum
information that $Z$ can give about $X$ is $\log N$. The above lemma
formalizes this intuition.

Consider any $i\in[t]$. We now fix $z^{i-1}=(z_{1},\cdots,z_{i-1})$. We will
now partition $X$ into $L^{i}_{-1},L^{i}_{0},L^{i}_{1},L^{i}_{2},L^{i}_{3}$
such that the distributions $\\{Q_{Z|X=x}(\cdot|x)\\}_{x\in L^{i}_{j}}$ will
be close.

Let $L^{i}$ be the set of all $x\in[\log n]$ such that there exists a
distribution $D\in\mathcal{X}_{x}$ consistent with the values $z^{i-1}$, i.e.,
$\sum_{j\in A_{k}}D(j)=z_{k}$ for all $k\in[i-1]$. So, for any $x\not\in
L^{i}$, we have $Q_{X|Z^{i-1}=z^{i-1}}(x|z^{i-1})=0$. We have
$L^{i}_{-1}:=[\log n]\setminus L^{i}$.

We will show a partition of the set $L^{i}$ into the subsets
$L^{i}_{0},L^{i}_{1},L^{i}_{2}$ and $L^{i}_{3}$ such that

  * •

For each $x\in L^{i}_{0}$, the value of $z_{i}$ will always be equal to $0$
(to apply Lemma 4.10, we will set $R^{i}_{0}$ as a distribution that takes
value $0$ with probability $1$).

  * •

For each $x\in L^{i}_{1}$, the value of $z_{i}$ will always be equal to $1$
(set $R^{i}_{1}$ as a distribution that takes value $1$ with probability $1$).

  * •

For each $x\in L^{i}_{2}$, the value of $z_{i}$ will (be $\neq 0,1$ and)
always be completely determined by the value of $z^{i-1}$ (i.e., a fixed
number depending on $z^{i-1}$) (set $R^{i}_{2}$ as a distribution that takes
this fixed value with probability $1$).

  * •

$L^{i}_{3}:=L^{i}\setminus(L^{i}_{0}\cup L^{i}_{1}\cup L^{i}_{2})$ (set
$R^{i}_{3}$ as the distribution $Q_{Z|X=x}(\cdot|x)$ for any $x\in
L^{i}_{3}$).

This partition directly implies the following lemma.

######  Lemma 4.11.

For every $i\in[t]$, $z^{i-1}$, and $x\in[\log n]$,

$I(X;Z_{i}|Z^{i-1}=z^{i-1})\leq\log 4+\max_{x,x^{\prime}\in
L^{i}_{3}}KL(Q_{Z_{i}|X=x,Z^{i-1}=z^{i-1}}||Q_{Z_{i}|X=x^{\prime},Z^{i-1}=z^{i-1}}).$

###### Proof.

Conditioned on $Z^{i-1}=z^{i-1}$, we apply Lemma 4.10 by substituting $Z_{i}$
for $Z$, distributions $R^{i}_{0},R^{i}_{1},R^{i}_{2},R^{i}_{3}$ for
$R^{1},R^{2},R^{3},R^{4}$ respectively and $N=4$. ∎

Let us now define the partition of $L^{i}$. Consider the $i$-th set $A_{i}$
queried (on the SET-EVAL oracle) by the algorithm.

#### Partition $L^{i}_{0}$:

Let $L^{i}_{0}=\\{x\in L^{i}:[2^{x}]\cap A_{i}=\emptyset\\}$. So $z_{i}$ must
be $0$ for all $x\in L^{i}_{0}$.

#### Partition $L^{i}_{1}$:

Let $L^{i}_{1}=\\{x\in L^{i}:[2^{x}]\subseteq A_{i}\\}$. So $z_{i}$ must be
$1$ for all $x\in L^{i}_{1}$.

#### Partition $L^{i}_{2}$:

For any $1\leq j\leq i$, let $\chi^{x}(A_{j})\in\\{0,1\\}^{2^{x}}$ be the
characteristic vector of $A_{j}$ restricted to $[2^{x}]$.

Let $x_{\ell}$ be the largest $x\in L^{i}$ such that
$\chi^{x}(A_{i})=\sum_{j\in[i-1]}\beta_{j}\cdot\chi^{x}(A_{j})$ for some reals
$\beta_{1},\dots,\beta_{i-1}$. Since
$\chi^{x_{\ell}}(A_{i})=\sum_{j\in[i-1]}\beta_{j}\cdot\chi^{x_{\ell}}(A_{j})$,
we have that for all $x\in L^{i}$ such that $x\leq x_{\ell}$, the following
holds

$\chi^{x}(A_{i})=\sum_{j\in[i-1]}\beta_{j}\cdot\chi^{x}(A_{j}).$

Observe, $\chi^{x}(A_{i})=\sum_{j\in[i-1]}\beta_{j}\cdot\chi^{x}(A_{j})$
implies $z_{i}=\sum_{j\in[i-1]}\beta_{j}\cdot z_{j}$ for all $x\in L^{i}$ such
that $x\leq x_{\ell}$.

Next, define $L^{i}_{2}:=\\{x\in L^{i}\mid x\leq
x_{\ell}\\}\setminus(L^{i}_{0}\cup L^{i}_{1})$.

#### Partition $L^{i}_{3}$:

$L^{i}_{3}:=L^{i}\setminus(L^{i}_{0}\cup L^{i}_{1}\cup L^{i}_{2})$.

We will now give expression for the distribution
$Q_{Z_{i}|X=x,Z^{i-1}=z^{i-1}}$ for $x\in L^{i}_{3}$. We will provide the
explicit expression for
$KL(Q_{Z_{i}|X=x,Z^{i-1}=z^{i-1}}||Q_{Z_{i}|X=x^{\prime},Z^{i-1}=z^{i-1}})$
later (subsection 4.1). Recall, ultimately, we want to show

$\max_{x,x^{\prime}\in
L^{i}_{3}}KL(Q_{Z_{i}|X=x,Z^{i-1}=z^{i-1}}||Q_{Z_{i}|X=x^{\prime},Z^{i-1}=z^{i-1}})=O(1).$

For any $x\in L^{i}_{3}$, let $A^{x}_{j}:=A_{j}\cap[2^{x}]$ ($1\leq j\leq i)$
be the restriction of $A_{j}$ to $[2^{x}]$. Recall, we assume $A_{i}$’s are
laminar. Thus it is straightforward to make the following observation.

######  Observation 4.12.

For any $u,v\in[t]$, if $A_{u}\subseteq A_{v}$ then $A^{s}_{u}\subseteq
A^{s}_{v}$.

However, it is possible that $A_{u}\subset A_{v}$, but $A^{s}_{u}=A^{s}_{v}$.
Let $x_{m}$ be the maximum value of $x\in L^{i}_{3}$.

######  Claim 4.13.

For any $1\leq u,v\leq i$ and $x^{\prime}\in L^{i}_{3}$, $A^{x_{m}}_{u}\subset
A^{x_{m}}_{v}$ if and only if $A^{x^{\prime}}_{u}\subset A^{x^{\prime}}_{v}$ .

###### Proof.

Consider any $x^{\prime}\in\bar{L}$. Clearly, if $A^{x^{\prime}}_{u}\subset
A^{x^{\prime}}_{v}$, then $A^{x_{m}}_{u}\subset A^{x_{m}}_{v}$. So it only
remains to show the converse.

Consider any $1\leq u,v<i$ and let $A^{x_{m}}_{u}\subset A^{x_{m}}_{v}$. Then
if $A^{x^{\prime}}_{u}$ is not a strict subset of $A^{x^{\prime}}_{v}$. then
we must have $A^{x^{\prime}}_{u}=A^{x^{\prime}}_{v}$. Since
$x_{m},x^{\prime}\in L^{i}_{3}\subseteq L^{i}$, by the definition, there must
exist some distributions $D_{x^{\prime}}\in\mathcal{X}_{x^{\prime}}$ and
$D_{x_{m}}\in\mathcal{X}_{x_{m}}$ consistent with the values
$z_{1},\dots,z_{i-1}$. Note, in $D_{X=x^{\prime}}$, we have

$z_{u}=\sum_{j\in A^{x^{\prime}}_{u}}D_{X=x^{\prime}}(j)=\sum_{j\in
A^{x^{\prime}}_{v}}D_{X=x^{\prime}}(j)=z_{v}.$

On the other hand, in $D_{X=x_{m}}$, we have

$z_{u}=\sum_{j\in A^{x_{m}}_{u}}D_{X=x_{m}}(j)<\sum_{j\in
A^{x_{m}}_{v}}D_{X=x_{m}}(j)=z_{v}.$

This contradicts the fact that $x_{m},x^{\prime}\in L^{i}$. Thus
$A^{x^{\prime}}_{u}\subset A^{x^{\prime}}_{v}$ when both $u,v<i$.

It is easy to see that for any $x\in\\{x^{\prime},x_{m}\\}$, $A^{x}_{i}\neq
A^{x}_{u}$ for all $1\leq u<i$ because both $x^{\prime},x^{m}\in L^{i}_{3}$.
Hence, $A^{x_{m}}_{u}\subset A^{x_{m}}_{v}$ implies $A^{x^{\prime}}_{u}\subset
A^{x^{\prime}}_{v}$ for the case when one of $u,v$ is equal to $i$. ∎

Let $1\leq u,v\leq i$. We say $A^{x}_{u}$ is a child of $A^{x}_{v}$
(alternately, $A^{x}_{v}$ is a parent of $A^{x}_{u}$) if $A^{x}_{u}\subset
A^{x}_{v}$, and there is no $w\in[i]$ such that $A^{x}_{u}\subset
A^{x}_{w}\subset A^{x}_{v}$. Let $1\leq
p,c_{1},\dots,c_{r},b_{1},\dots,b_{k}<i$. Let $A^{x}_{p}$ be a parent of
$A^{x}_{i}$, and let $A^{x}_{c_{1}},\cdots,A^{x}_{c_{r}}$ be the children of
$A^{x}_{i}$. Further, let $A^{x}_{b_{1}},\cdots,A^{x}_{b_{k}}$ be the children
(apart from $A^{x}_{i}$) of $A^{x}_{p}$. (In other words,
$A^{x}_{b_{1}},\cdots,A^{x}_{b_{k}}$ are siblings of $A^{x}_{i}$.) Next,
define

$\displaystyle
B^{x}:=A^{x}_{p}\setminus\Big{(}\cup_{j\in[r]}A^{x}_{c_{j}}\bigcup\cup_{j\in[k]}A^{x}_{b_{j}}\Big{)},\text{
and}$ $\displaystyle C^{x}:=A^{x}_{i}\setminus(\cup_{j\in[r]}A^{x}_{c_{j}}).$

Now by 4.13, for any $x,x^{\prime}\in L^{i}_{3}$, $A^{x}_{u}$ is a child (or
parent) of $A^{x}_{v}$ if and only if $A^{x^{\prime}}_{u}$ is a child (or
parent) of $A^{x^{\prime}}_{v}$. Therefore, for all $x\in L^{i}_{3}$,

  * •

$C^{x},B^{x}\neq\emptyset$, and

  * •

$D_{X}(B^{x})=z_{p}-z_{c_{1}}-\cdots-z_{c_{r}}-z_{b_{1}}-\cdots-z_{b_{k}}>0$.

Let $h:=z_{p}-z_{c_{1}}-\cdots-z_{c_{r}}-z_{b_{1}}-\cdots-z_{b_{k}}$. Note,

$\displaystyle Z_{i}|(X=x,Z^{i-1}=z^{i-1})$ $\displaystyle=D_{X}(A^{x}_{i})$
$\displaystyle=D_{X}(A^{x}_{c_{1}})+\cdots+D_{X}(A^{x}_{c_{r}})+D_{X}(C^{x})$
$\displaystyle=z_{c_{1}}+\cdots+z_{c_{r}}+D_{X}(C^{x}).$

Then we get

$\displaystyle
KL(Q_{Z_{i}|X=x,Z^{i-1}=z^{i-1}}||Q_{Z_{i}|X=x^{\prime},Z^{i-1}=z^{i-1}})$
$\displaystyle=KL(Q_{D_{X}(A^{x}_{i})}||Q_{D_{X}(A^{x^{\prime}}_{i})})$
$\displaystyle=KL(Q_{D_{X}(C^{x})}||Q_{D_{X}(C^{x^{\prime}})})$
$\displaystyle=KL\Big{(}Q_{\frac{D_{X}(C^{x})}{h}}||Q_{\frac{D_{X}(C^{x^{\prime}})}{h}}\Big{)}$
(5)

where the last two equalities follow since $z_{c_{1}}+\cdots+z_{c_{r}}$ and
$h$ depend only on $z^{i-1}$ (not on $x$).

Let us now recall the independence property of Dirichlet distribution (4.6).
Suppose $(P_{1},\dots,P_{K})\sim Dir(\alpha_{1},\dots,\alpha_{K})$. Given
$E\subset F\subseteq[K]$ and $d\in(0,1)$, the random variable
$\frac{\sum_{i\in E}P_{i}}{d}$ conditioned on $\sum_{i\in F}P_{i}=d$ is
distributed a per the beta distribution with parameter $(\sum_{i\in
E}\alpha_{i},\sum_{i\in F\setminus E}\alpha_{i})$.

For our purpose, we set $d=h$, $F=B^{x}$ and $E=C^{x}$ in 4.6. Therefore,

$\displaystyle\frac{D_{X}(C^{x})}{h}\sim Beta(\sum_{i\in
C^{x}}\alpha_{i},\sum_{i\in B^{x}\setminus C^{x}}\alpha_{i}),\text{ and}$
$\displaystyle\frac{D_{X}(C^{x^{\prime}})}{h}\sim Beta(\sum_{i\in
C^{x^{\prime}}}\alpha_{i},\sum_{i\in B^{x^{\prime}}\setminus
C^{x^{\prime}}}\alpha_{i}).$

Let for any $x\in L^{i}_{3}$, $U^{x}=B^{x}\setminus C^{x}$,
$\alpha(U^{x})=\sum_{i\in U^{x}}\alpha_{i}$ and $\alpha(C^{x})=\sum_{i\in
C^{x}}\alpha_{i}$. Therefore,

$\displaystyle\frac{D_{X}(C^{x})}{h}\sim
Beta(\alpha(C^{x}),\alpha(U^{x})),\text{ and}$
$\displaystyle\frac{D_{X}(C^{x^{\prime}})}{h}\sim
Beta(\alpha(C^{x^{\prime}}),\alpha(U^{x^{\prime}})).$

The KL divergence between two beta distributions with different parameters is
well known (e.g., see [JKB95]) and as follows.

######  Lemma 4.14.

$\displaystyle
KL(Beta(\alpha(C^{x}),\alpha(U^{x}))||Beta(\alpha(C^{x^{\prime}}),\alpha(U^{x^{\prime}}))$
$\displaystyle=\ln(\frac{B(\alpha(C^{x^{\prime}}),\alpha(U^{x^{\prime}}))}{B(\alpha(C^{x}),\alpha(U^{x}))})$
$\displaystyle+(\alpha(C^{x})-\alpha(C^{x^{\prime}}))\psi(\alpha(C^{x}))+(\alpha(U^{x})-\alpha(U^{x^{\prime}}))\psi(\alpha(U^{x}))$
$\displaystyle+(\alpha(C^{x^{\prime}})-\alpha(C^{x})+\alpha(U^{x^{\prime}})-\alpha(D^{x}))\psi(\alpha(C^{x})+\alpha(U^{x}))$

where $B(w,y)=\frac{\Gamma(w)\Gamma(y)}{\Gamma(w+y)}$ and $\Gamma()$ is a
gamma function, and $\psi$ is the digamma function defined as the logarithmic
derivative of the gamma function:
$\psi(\alpha)=\frac{d}{d\alpha}\ln\Gamma(\alpha)$.

Next, we derive a simple claim about the digamma function.

######  Lemma 4.15.

For $0<w\leq 1$, we have $|w\psi(w)|\leq 3$.

###### Proof.

It is well known and follows from the definition of digamma function (e.g.,
see [Ber76]) that

$\psi(w)=\psi(w+1)+\frac{1}{w}.$

So $|w\psi(w)|\leq 1+w|\psi(w+1)|$. It is also known that
$|\psi(w+1)|\leq\frac{1}{1+w}+\ln(1+w)$. So, we get that

$\displaystyle|w\psi(w)|$ $\displaystyle\leq 1+w|\psi(w+1)|$
$\displaystyle\leq 1+\frac{w}{1+w}+w\ln(1+w)<3.$

∎

######  Lemma 4.16.

For all $x,x^{\prime}\in L^{i}_{3}$,
$KL(Q_{Z_{i}|X=x,Z^{i-1}=z^{i-1}}||Q_{Z_{i}|X=x^{\prime},Z^{i-1}=z^{i-1}})=O(1)$
.

###### Proof.

W.l.o.g. assume, $x<x^{\prime}\in L^{i}_{3}$. We have $C^{x}\subset
C^{x^{\prime}}$ and $U^{x}\subset U^{x^{\prime}}$. So we have

$\displaystyle|\alpha(C^{x})-\alpha(C^{x^{\prime}})|$
$\displaystyle\leq\sum_{j\geq 2^{x}+1}\alpha_{j}$
$\displaystyle\leq\alpha_{2^{x}}\leq\alpha(C^{x})$

where the second last inequality follows since $\alpha_{j}=\frac{1}{2^{j}}$
for all $j$. Similarly,

$|\alpha(U^{x^{\prime}})-\alpha(D^{x})|\leq\alpha(U^{x})$

From 4.15, we have

  1. 1.

$|(\alpha(C^{x})-\alpha(C^{x^{\prime}}))|\cdot|\psi(\alpha(C^{x}))|\leq\alpha(C^{x})|\psi(\alpha(C^{x}))|<3$,

  2. 2.

$|(\alpha(U^{x})-\alpha(U^{x^{\prime}}))|\cdot|\psi(\alpha(U^{x}))|\leq\alpha(U^{x})|\psi(\alpha(U^{x}))|<3$,
and

  3. 3.

$|(\alpha(C^{x^{\prime}})-\alpha(C^{x})+\alpha(U^{x^{\prime}})-\alpha(D^{x}))|\cdot|\psi(\alpha(C^{x})+\alpha(U^{x}))|\leq(\alpha(C^{x})+\alpha(U^{x}))|\psi(\alpha(C^{x})+\alpha(U^{x}))|<3$.

So it follows from subsection 4.1 and 4.14, we have

$KL(Q_{Z_{i}|X=x,Z^{i-1}=z^{i-1}}||Q_{Z_{i}|X=x^{\prime},Z^{i-1}=z^{i-1}})=O(1)+\ln(\frac{B(\alpha(C^{x^{\prime}}),\alpha(U^{x^{\prime}}))}{B(\alpha(C^{x}),\alpha(U^{x}))}).$

It is well known and follows from the definition (e.g., see [Dav59]) that

$\displaystyle B(w,y)=\frac{\Gamma(w)\Gamma(y)}{\Gamma(w+y)},\text{ and}$
$\displaystyle\Gamma(w)=\frac{\Gamma(w+1)}{w}.$

Therefore,

$\displaystyle\ln(\frac{B(\alpha(C^{x^{\prime}}),\alpha(U^{x^{\prime}}))}{B(\alpha(C^{x}),\alpha(U^{x}))})$
$\displaystyle=\ln\frac{\alpha(C^{x})\alpha(U^{x})(\alpha(C^{x^{\prime}})+\alpha(U^{x^{\prime}}))}{\alpha(C^{x^{\prime}})\alpha(U^{x^{\prime}})(\alpha(C^{x})+\alpha(U^{x}))}$
$\displaystyle+\ln\frac{\Gamma(1+\alpha(C^{x^{\prime}}))\Gamma(1+\alpha(U^{x^{\prime}}))\Gamma(1+\alpha(C^{x})+\alpha(U^{x}))}{\Gamma(1+\alpha(C^{x}))\Gamma(1+\alpha(U^{x}))\Gamma(1+\alpha(C^{x^{\prime}})+\alpha(U^{x^{\prime}}))}.$

Note,
$\frac{\alpha(C^{x^{\prime}})}{\alpha(C^{x})},\frac{\alpha(U^{x^{\prime}})}{\alpha(D^{x})},\frac{\alpha(C^{x^{\prime}})+\alpha(U^{x^{\prime}})}{\alpha(C^{x}+\alpha(D^{x})}\in[1,2]$.
So we have

$\Big{|}\ln\frac{\alpha(C^{x})\alpha(U^{x})(\alpha(C^{x^{\prime}})+\alpha(U^{x^{\prime}}))}{\alpha(C^{x^{\prime}})\alpha(U^{x^{\prime}})(\alpha(C^{x})+\alpha(U^{x}))}\Big{|}\leq
3\ln 2.$

For any $0\leq w\leq 1$, it is known that $\Gamma(1+w)\in[0.6,2]$. Therefore,

$\Big{|}\ln\frac{\Gamma(1+\alpha(C^{x^{\prime}}))\Gamma(1+\alpha(U^{x^{\prime}}))\Gamma(1+\alpha(C^{x})+\alpha(U^{x}))}{\Gamma(1+\alpha(C^{x}))\Gamma(1+\alpha(U^{x}))\Gamma(1+\alpha(C^{x^{\prime}})+\alpha(U^{x^{\prime}}))}\Big{|}=O(1).$

Thus we have
$\ln(\frac{B(\alpha(C^{x^{\prime}}),\alpha(U^{x^{\prime}}))}{B(\alpha(C^{x}),\alpha(U^{x}))})=O(1)$,
and hence
$KL(Q_{Z_{i}|X=x,Z^{i-1}=z^{i-1}}||Q_{Z_{i}|X=x^{\prime},Z^{i-1}=z^{i-1}})=O(1)$.
∎

Now, it directly follows from 4.11 and 4.16 that for every $i\in[t]$,
$z^{i-1}$, and $x\in[\log n]$, $I(X;Z_{i}|Z^{i-1}=z^{i-1})=O(1)$ which along
with 4.9 completes the proof of 4.8.

###  4.2 Extending $\Omega(\log\log\log n)$ bound to COND-EVAL model

We now extend the $\Omega(\log\log\log n)$ bound to the COND-EVAL model. The
extra difficulty (compared to the SET-EVAL) comes from the fact that now at
any step, there are three outcomes - (i) the sum $Z_{i}=D_{X}(A_{i})$, (ii)
the sampled element $E_{i}\in A_{i}$ (if $D_{X}(A_{i})>0$), and (iii) the
actual probability $D_{X}(E_{i})$ of $E_{i}$ (in actual definition, the
outcomes are $(E_{i},D_{X}(E_{i}),\frac{D_{X}(E_{i})}{D_{X}(A_{i})})$.
Obviously it is equivalent to $(E_{i},D_{X}(E_{i}),D_{X}(A_{i}))$). If
$D_{X}(A_{i})=0$ then we set $E_{i}$ to be $\emptyset$. We need to show now
that the information gain about $X$ from all of these outcomes is small.
Formally, we need to upper bound $I(X;(Z_{i},E_{i},D_{X}(E_{i})))$ (compared
to earlier $I(X;Z_{i})$). Further, (as before), the upper bound
$I(X;(Z_{i},E_{i},D_{X}(E_{i})))$ needs to be shown conditioned on the
previous outcomes.

The set of inputs $\mathcal{X}$ and distribution $\gamma$ is the same as
before except that we set the Dirichlet parameters
$\alpha_{1},\dots,\alpha_{n}$ as follows:

$\alpha_{j}=\frac{1}{c^{j}}\text{ for all }1\leq j\leq n\text{, where
}c=4(2^{2^{n}})^{2}2^{2^{n}}.$

As before, we will require that the queried sets are laminar.

######  Lemma 4.17.

Any algorithm that makes $t$ queries of COND-EVAL can be simulated by an
algorithm that makes at most $2^{t}$ COND-EVAL queries with the property that
(i)the queried sets are laminar, and (ii) a set queried later is not a strict
superset of a set queried as well as sampled elements earlier (i.e., of those
sets $S\subseteq[n]$, whose $D_{X}(S)$ is known so far).

###### Proof.

Let algorithm $\mathcal{A}$ makes $t$ queries of COND-EVAL. Let the queried
sets by $\mathcal{A}$, in order, be denoted by $A_{1},\dots,A_{t}$. We give an
algorithm $\mathcal{B}$ that can simulate $A$ such that the queried sets
satisfy the property as mentioned in the lemma. Like before, we use $D_{X}(A)$
for $\sum_{j\in A}D_{X}(j)$ for all $A\subseteq[n]$. The first set queried by
$\mathcal{B}$ is also $A_{1}$. The algorithm $\mathcal{B}$ receives the tuple
$(D_{X}(A_{1}),E(A_{1}),D_{X}(E(A_{1}))$ (where $E(A_{1})\in A_{1}$ is the
sampled element) and via $\mathcal{A}$ determines the next set $A_{2}$ queried
by $\mathcal{A}$.

Let $\mathcal{E}_{i-1}$ be the set of all sampled elements of $\mathcal{B}$
till step $i-1$, i.e., till $\mathcal{B}$ has determined the set $A_{i}$ by
simulating the sets $A_{1},\dots,A_{i-1}$. Let
$\mathcal{E}_{A_{i}}=A_{i}\cap\mathcal{E}_{i-1}$ be the set of sampled
elements so far in $A_{i}$. In place of set $A_{i}$, the algorithm
$\mathcal{B}$ queries all sets in

$\mathcal{C}_{i}=\\{A_{i}\cap C_{1}\cap C_{2}\dots
C_{i-1}\cap(\cap_{E\in\mathcal{E}_{A_{i}}}E^{c})|C_{j}\in\\{A_{j},A^{c}_{j}\\},\forall
j\in[i-1]\\}$

($A^{c}_{j}=[n]\setminus A_{j}$ and $E^{c}=[n]\setminus E$). For each set
$C\in\mathcal{C}_{i}$, the algorithm $\mathcal{B}$ receives the tuple
$(D_{X}(C),E(C),D_{X}(E(C)))$, where $E(C)\in C$ is the sampled element with
probability $\frac{D_{X}(E(C))}{D_{X}(C)}$. Note that $\mathcal{B}$ can
determine $D_{X}(A_{i})$ since

$D_{X}(A_{i})=\sum_{C\in\mathcal{C}_{i}}D_{X}(C)+\sum_{E\in\mathcal{E}_{A_{i}}}D_{X}(E).$

Now $\mathcal{B}$ needs to sample an element $E_{i}\in A_{i}$ with probability
$\frac{D_{X}(E_{i})}{D_{X}(A_{i})}$. For the same, the algorithm $\mathcal{B}$
samples a set $U\in\mathcal{C}_{i}\cup\mathcal{E}_{A_{i}}$ with probability
$\frac{D_{X}(U)}{D_{X}(A_{i})}$ (note that $D_{X}(U)$ is known to
$\mathcal{B}$ for all $U\in\mathcal{C}_{i}\cup\mathcal{E}_{A_{i}}$) and then
to determine the next set $A_{i+1}$, uses the tuple
$(D_{X}(A_{i}),E(U),D_{X}(E(U)))$ or $(D_{X}(A_{i}),U,D_{X}(U))$ as an outcome
of $\mathcal{A}$ for $A_{i}$, depending on $U\in\mathcal{C}_{i}$ or
$U\in\mathcal{E}_{A_{i}}$ respectively.

Observe, $|\mathcal{C}_{i}|=2^{i-1}$, and hence the total number of queries is
bounded by $\sum_{i\in[t]}2^{i-1}\leq 2^{t}.$ Also, it is easy to see that the
queried sets satisfy the conditions of the lemma.

∎

Let $m_{i}\in A_{i}$ be the minimum element of $A_{i}$. We will need the
following lemma later to show that for any $A_{i}$ ($1\leq i\leq t$), if
$D_{X}(A_{i})>0$, the sampled element $E_{i}$ will be $m_{i}$ with probability
at least $1-\frac{1}{2^{2^{n}}}$.

######  Lemma 4.18.

Consider a random variable $Y\sim Beta(\alpha,\beta)$ where
$\beta\leq\frac{\alpha}{c}$ and $c\geq 4(2^{2^{n}})^{2}2^{2^{n}}$. We have
$\Pr[Y\leq 1-\frac{1}{2^{2^{n}}}]\leq\frac{1}{2^{2^{n}}}.$

###### Proof.

Let $d=4(2^{2^{n}})^{2}2^{2^{n}}$. It is immediate from the property of beta
distributions, that

$\displaystyle\mathbb{E}[Y]=\frac{\alpha}{\alpha+\beta}\geq
1-\frac{1}{d+1}\text{ and}$ $\displaystyle
Var[Y]=\frac{\alpha\beta}{(\alpha+\beta)^{2}(\alpha+\beta+1)}\leq\frac{1}{d}.$

Therefore, we derive that

$\displaystyle\Pr[Y\leq 1-\frac{1}{2^{2^{n}}}]$
$\displaystyle\leq\Pr[|Y-\mathbb{E}[Y]|>\frac{1}{2\cdot 2^{2^{n}}}]$
$\displaystyle<4(2^{2^{n}})^{2}Var[Y]$ (by Chebyshev inequality)
$\displaystyle\leq\frac{4(2^{2^{n}})^{2}}{4(2^{2^{n}})^{2}2^{2^{n}}}=\frac{1}{2^{2^{n}}}.$

∎

We will use $H^{i-1}$ to denote the history
$(Z_{i-1},E_{i-1},D_{X}(E_{i-1}),\dots,Z_{1},E_{1},D_{X}(E_{1})).$ Then
observe,

$\displaystyle I(X;(Z_{i},E_{i},D_{X}(E_{i}))|H^{i-1})$
$\displaystyle=I(X;Z_{i}|H^{i-1})+I(X;E_{i}|Z_{i},H^{i-1})+I(X;D_{X}(E_{i}))|E_{i},Z_{i},H^{i-1}).$
(6)

######  Lemma 4.19.

$I(X;Z_{i}|H^{i-1})=O(1)$.

###### Proof.

The distribution of $Z_{i}$ will depend on $Z_{1},\dots,Z_{i-1}$ and on
$D_{X}(E_{1}),\dots,D_{X}(E_{i-1})$, but not on the fact that element $E_{j}$
was sampled from set $A_{j}$ for $j\leq i-1$. So the proof of the current
lemma is the same as that of 4.8, except that now the Dirichlet parameters are
set to $\alpha_{j}=\frac{1}{c^{j}}$ for all $1\leq j\leq n$. However, all the
previous calculations (as in the proof of 4.8) will also work here.

∎

######  Lemma 4.20.

$I(X;E_{i}|Z_{i},H^{i-1})=O(1)$.

###### Proof.

To show $I(X;E_{i}|Z_{i},H^{i-1})=O(1)$, as previously, it suffices to show,
for given any $z_{i},h^{i-1}$,

$I(X;E_{i}|Z_{i}=z_{i},H^{i-1}=h^{i-1})=O(1)$

where

$I(X;E_{i}|Z_{i}=z_{i},H^{i-1}=h^{i-1})=\sum_{x\in
L^{c}}\sum_{e_{i}}Q_{X,E_{i}|Z_{i},H^{i-1}}(x,e_{i}|z_{i},h^{i-1})\log\frac{Q_{X,E_{i}|Z_{i},H^{i-1}}(x,e_{i}|z_{i},h^{i-1})}{Q_{X|Z_{i},H^{i-1}}(x|z_{i},h^{i-1})Q_{E_{i}|Z_{i},H^{i-1}}(e_{i}|z_{i},h^{i-1})}$

From now, we will omit the $z_{i},h^{i-1}$ in the density functions (as it is
understood). Further, for brevity, we will omit the subscript when the context
is understood. For example, we will use $q(x,e_{i})$ for
$Q_{X,E_{i}|Z_{i},H^{i-1}}(x,e_{i}|z_{i},h^{i-1})$. Now for any $x\in
L^{i}_{0},$ we have $e_{i}=\emptyset$ with probability one. Therefore,

$\sum_{x\in
L^{i}_{0}}\sum_{e_{i}}q(x,e_{i})\log\frac{q(x,e_{i})}{q(s)q(e_{i})}=\Big{(}\sum_{x\in
L^{i}_{0}}g_{x}\Big{)}\log\frac{1}{\sum_{x\in L^{i}_{0}}g_{x}}.$

Since the set $A_{i}$ does not contain any of the earlier sets
$A_{1},\dots,A_{i-1}$ as well as the sampled elements $E_{1},\dots,E_{i-1}$,
we have

$\frac{D_{X}(m_{i})}{z_{i}}\sim Beta(\alpha(m_{i}),\alpha(A_{i}\setminus
m_{i})).$

Therefore, by 4.18, for $x\not\in L^{i}_{0}$, we have $\Pr[E_{i}\neq
m_{i}]\leq\frac{1}{2^{2^{n}}}$. Therefore,

$\sum_{x\not\in
L^{i}_{0}}\sum_{e_{i}}q(x,e_{i})\log\frac{q(x,e_{i})}{q(x)q(e_{i})}\leq\sum_{x\not\in
L^{i}_{0}}q(x,m_{i})\log\frac{q(x,m_{i})}{q(x)q(m_{i})}+(n\log
n)|q(x,e)\log\frac{q(x,e)}{q(x)q(e)}|$

where $e$ is an any element in $A_{i}\setminus m_{i}$. Now,

$\displaystyle|q(x,e)\log\frac{q(x,e)}{q(x)q(e)}|$
$\displaystyle\leq|q(x,e)\log q(x,e)|+|q(x,e)\log q(x)|+|q(x,e)\log q(e)|$
$\displaystyle\leq 3|q(x,e)\log q(x,e)|.$

As $q(x,e)=g_{x}q_{x}(e)\leq\frac{1}{2^{2^{n}}}$, we have $|q(x,e)\log
q(x,e)|\leq\frac{2^{n}}{2^{2^{n}}}.$ Therefore,

$\displaystyle\sum_{x\not\in
L^{i}_{0}}\sum_{e_{i}}q(x,e_{i})\log\frac{q(x,e_{i})}{q(x)q(e_{i})}$
$\displaystyle\leq\sum_{x\not\in
L^{i}_{0}}q(x,m_{i})\log\frac{q(x,m_{i})}{q(s)q(m_{i})}+(3n\log
n)\frac{2^{n}}{2^{2^{n}}}$ $\displaystyle=\sum_{x\not\in
L^{i}_{0}}g_{x}q_{x}(m_{i})\log\frac{q_{x}(m_{i})}{\sum_{x\not\in
L^{i}_{0}}g_{x}q_{x}(m_{i})}+(3n\log n)\frac{2^{n}}{2^{2^{n}}}$
$\displaystyle\leq\sum_{x\not\in L^{i}_{0}}g_{x}\log\frac{1}{\sum_{x\not\in
L^{i}_{0}}g_{x}(1-\frac{1}{2^{2^{n}}})}+\sum_{x\not\in
L^{i}_{0}}g_{x}|\log\frac{1-\frac{1}{2^{2^{n}}}}{\sum_{x\not\in
L^{i}_{0}}g_{x}}|+(3n\log n)\frac{2^{n}}{2^{2^{n}}}$
$\displaystyle=\sum_{x\not\in L^{i}_{0}}g_{x}\log\frac{1}{\sum_{x\not\in
L^{i}_{0}}g_{x}}+o(1).$

Also,

$\sum_{x\in
L^{i}_{0}}\sum_{e_{i}}q(x,e_{i})\log\frac{q(x,e_{i})}{q(s)q(e_{i})}=\sum_{x\in
L^{i}_{0}}g_{x}\log\frac{1}{\sum_{x\in L^{i}_{0}}g_{x}}.$

Hence, we have

$\displaystyle I(X;E_{i}|z_{i},h^{i-1})$ $\displaystyle=\sum_{x\not\in
L^{i}_{0}}\sum_{e_{i}}q(x,e_{i})\log\frac{q(x,e_{i})}{q(x)q(e_{i})}+\sum_{x\in
L^{i}_{0}}\sum_{e_{i}}q(x,e_{i})\log\frac{q(x,e_{i})}{q(s)q(e_{i})}$
$\displaystyle\leq\log 2+o(1)=O(1)$

which completes the proof. ∎

######  Lemma 4.21.

If for any value of $z_{i}$ and $h^{i-1}$, we have
$I(X;D_{X}(E_{i})|E_{i}=m_{i},Z_{i}=z_{i},H^{i-1}=h^{i-1})=O(1)$ then
$I(X;D_{X}(E_{i})|E_{i},Z_{i},H^{i-1})=O(1)$.

###### Proof.

We have

$\displaystyle I(X;D_{X}(E_{i})|E_{i},Z_{i},H^{i-1})$
$\displaystyle=\sum_{e_{i}}\int_{(z_{i},h^{i-1})}q(e_{i},z_{i},h^{i-1})I(X;D_{X}(E_{i})|E_{i}=e_{i},Z_{i}=z_{i},H^{i-1}=h^{i-1})\,d(z_{i},h^{i-1})$
$\displaystyle=\int_{(z_{i},h^{i-1})}q(\emptyset,z_{i},h^{i-1})I(X;D_{X}(E_{i})|E_{i}=\emptyset,Z_{i}=z_{i},H^{i-1}=h^{i-1})\,d(z_{i},h^{i-1})$
$\displaystyle+\int_{(z_{i},h^{i-1})}q(m_{i},z_{i},h^{i-1})I(X;P_{i}|E_{i}=0,Z_{i}=z_{i},H^{i-1}=h^{i-1})\,d(z_{i},h^{i-1})$
$\displaystyle+\sum_{e_{i}\not\in\\{0,m_{i}\\}}\int_{(z_{i},h^{i-1})}q(e_{i},z_{i},h^{i-1})I(X;D_{X}(E_{i})|E_{i}=e_{i},Z_{i}=z_{i},H^{i-1}=h^{i-1})\,d(z_{i},h^{i-1}).$

Note that

$\displaystyle I(X;D_{X}(E_{i})\mid
E_{i}=\emptyset,Z_{i}=z_{i},H^{i-1}=h^{i-1})$ $\displaystyle=\Big{(}\sum_{x\in
L^{i}_{0}}g_{x}\Big{)}\log\frac{1}{\sum_{x\in L^{i}_{0}}g_{x}}$
$\displaystyle=O(1).$

Then, by the assumption of the lemma,
$I(X;P_{i}|E_{i}=m_{i},Z_{i}=z_{i},H^{i-1}=h^{i-1})=O(1)$. Therefore,

$\displaystyle I(X;P_{i}|E_{i},Z_{i},H^{i-1})$ $\displaystyle\leq
O(1)+\sum_{e_{i}\not\in\\{0,m_{i}\\}}\int_{(z_{i},h^{i-1})}q(e_{i},z_{i},h^{i-1})I(X;D_{X}(E_{i})|E_{i}=e_{i},Z_{i}=z_{i},H^{i-1}=h^{i-1})\,d(z_{i},h^{i-1})$
$\displaystyle\leq
O(1)+\sum_{e_{i}\not\in\\{0,m_{i}\\}}\int_{(z_{i},h^{i-1})}q(e_{i}|z_{i},h^{i-1})q(z_{i},h^{i-1})I(X;D_{X}(E_{i})|E_{i}=e_{i},Z_{i}=z_{i},H^{i-1}=h^{i-1})\,d(z_{i},h^{i-1})$
$\displaystyle\leq
O(1)+\sum_{e_{i}\not\in\\{0,m_{i}\\}}\int_{(z_{i},h^{i-1})}\frac{1}{2^{2^{n}}}q(z_{i},h^{i-1})I(X;D_{X}(E_{i})|E_{i}=e_{i},Z_{i}=z_{i},H^{i-1}=h^{i-1})\,d(z_{i},h^{i-1})$
$\displaystyle\leq
O(1)+\frac{n}{2^{2^{n}}}\int_{(z_{i},h^{i-1})}q(z_{i},h^{i-1})I(X;D_{X}(E_{i})|E_{i}=e_{i},Z_{i}=z_{i},H^{i-1}=h^{i-1})\,d(z_{i},h^{i-1}).$

Note,

$\displaystyle I(X;D_{X}(E_{i})|E_{i}=e_{i},Z_{i}=z_{i},H^{i-1}=h^{i-1})$
$\displaystyle=\sum_{x}\int_{p_{i}}q(x,p(e_{i})|e_{i},z_{i},h^{i-1})\log\frac{q(x,p(e_{i})|e_{i},z_{i},h^{i-1})}{q(x|e_{i},z_{i},h^{i-1})q(p(e_{i})|e_{i},z_{i},h^{i-1})}\,d(q_{i})$
$\displaystyle\leq 3\log n.$

Hence, $I(X;D_{X}(E_{i})|E_{i},Z_{i},H^{i-1})\leq O(1)+\frac{3n\log
n}{2^{2^{n}}}=O(1)$. ∎

It remains to argue that $I(S;D_{X}(m_{i})|E_{i}=m_{i},Z_{i},H^{i-1})=O(1)$.
Unfortunately, $I(S;D_{X}(m_{i})|E_{i}=m_{i},Z_{i},H^{i-1})\neq
I(S;D_{X}(m_{i})|Z_{i},H^{i-1})$, and thus 4.8 cannot be used directly.
However, the following well-known property of Dirichlet distribution will help
us to remove the condition $E_{i}=m_{i}$.

######  Proposition 4.22.

Suppose $(P_{1},\dots,P_{K})\sim Dir(\alpha_{1},\dots,\alpha_{K})$. Let
$e\in[K]$. Let $E$ be the event that $e$ is the element sampled from the
distribution $(P_{1},\dots,P_{K})$. Let for $1\leq i\leq K$, $G_{i}$ takes the
value $1$ if $i=e$, and $0$ otherwise. Then $(P_{1},\dots,P_{K}|E)\sim
Dir(\alpha_{1}+G_{1},\dots,\alpha_{K}+G_{K})$.

Now, we are ready to conclude the following.

######  Lemma 4.23.

$I(X;D_{X}(m_{i})|E_{i}=m_{i},Z_{i}=z_{i},H^{i-1}=h^{i-1})=O(1).$

###### Proof.

It suffices to show that for any $x<x^{\prime}\in\bar{L}$, we have

$\displaystyle
KL(q_{x}(p(m_{i})|m_{i},z_{i},h^{i-1})||q_{x^{\prime}}(p(m_{i})|m_{i},z_{i},h^{i-1}))$
$\displaystyle=KL(q_{x}(\frac{p(m_{i})}{z_{i}}|m_{i},z_{i},h^{i-1})||q_{x^{\prime}}(\frac{p(m_{i})}{z_{i}}|m_{i},z_{i},h^{i-1}))$
$\displaystyle=O(1).$

In our case, $C^{x}=C^{x^{\prime}}=m_{i}$, and $D^{x}$, $D^{x^{\prime}}$ are
subsets of $A^{x}_{i}\setminus m_{i}$ and $A^{x^{\prime}}_{i}\setminus m_{i}$
respectively. Recall that

$\Big{(}\frac{D_{X}(m_{i})}{z_{i}}|x,Z_{i}=z_{i},H^{i-1}=h^{i-1}\Big{)}\sim
Beta(\alpha(m_{i}),\alpha(D^{x}))$

for any $x\in\bar{L}$. From 4.22, we have

$\Big{(}\frac{D_{X}(m_{i})}{z_{i}}|x,E_{i}=m_{i},Z_{i}=z_{i},H^{i-1}=h^{i-1}\Big{)}\sim
Beta(1+\alpha(m_{i}),\alpha(D^{x})).$

All we now need to show that the calculations in 4.16 will work for the
current values of Dirichlet parameters —
$\alpha_{m_{i}}=1+\frac{1}{c^{m_{i}}}$ and $\alpha_{j}=\frac{1}{c^{j}}$ for
$j\geq m_{i}+1$ (note, $\alpha_{1},\dots,\alpha_{m_{i}-1}$ do not appear in
the calculations).

The inequalities used in 4.16 are

  1. (i)

$|\alpha(C^{x})-\alpha(C^{x^{\prime}})|\leq\sum_{j\geq
2^{x}+1}\alpha_{j}\leq\alpha_{2^{x}}\leq\alpha(C^{x})$ (this now holds
trivially since $\alpha(C^{x})=\alpha(C^{x^{\prime}}$),

  2. (ii)

$|\alpha(D^{x^{\prime}})-\alpha(D^{x})|\leq\sum_{j\geq
2^{x}+1}\alpha_{j}\leq\alpha_{2^{x}}\leq\alpha(D^{x})$ (since $m_{i}$ is
neither in $D^{x}$ nor in $D^{x^{\prime}}$, this also holds now),

  3. (iii)

$\frac{\alpha(C^{x^{\prime}})}{\alpha(C^{x})},\frac{\alpha(D^{x^{\prime}})}{\alpha(D^{x})},\frac{\alpha(C^{x^{\prime}})+\alpha(D^{x^{\prime}})}{\alpha(C^{x}+\alpha(D^{x})}\in[1,2]$
(easy to see all of them holds now), and

  4. (iv)

$|\ln\frac{\Gamma(1+\alpha(C^{x^{\prime}}))\Gamma(1+\alpha(D^{x^{\prime}}))\Gamma(1+\alpha(C^{x})+\alpha(D^{x}))}{\Gamma(1+\alpha(C^{x}))\Gamma(1+\alpha(D^{x}))\Gamma(1+\alpha(C^{x^{\prime}})+\alpha(D^{x^{\prime}}))}|=O(1)$
(which also holds now as for $0\leq w\leq 2$, $\Gamma(1+w)\in[0.6,2]$).

The lemma now follows by following the calculations in 4.16. ∎

From Equation 6, and 4.19, 4.20 and 4.23, we have
$I(X;(Z_{i},E_{i},D_{X}(E_{i}))|H^{i-1})=O(1)$. Hence, as in Section 4, by
chain rule, we get

$I(X;(Z_{1},E_{1},D_{X}(E_{1}),\dots,(Z_{t},E_{t},D_{X}(E_{t})))\leq O(t).$

Hence, by Fano’s inequality (Theorem 4.5), we have the error probability at
least $1-\frac{O(t)}{\log\log n}$. Hence, $t=\Omega(\log\log n)$. Recall that
this lower bound is for the tester that queries only the laminar family of
sets. Finally, as in Section 4, using 4.17, we get a lower bound of
$\Omega(\log\log\log n)$ for general testers. So we conclude the following.

See 4.1

#### Discussion on stronger lower bound with approximate COND-EVAL queries.

Now, we discuss how we get an $\Omega(\log\log n)$ query lower bound when we
have access to a COND-PR oracle and an approximate SET-EVAL oracle. We refer
to the oracle that, given a subset $S\subseteq[n]$, returns the value of
$D(S)$ up to a 2-multiplicative factor as the approximate SET-EVAL oracle.
Here, we would like to highlight how, by slightly modifying the proof of 3.1,
we get an $\Omega(\log\log n)$ lower bound for this extended model. The proof
of 3.1 will remain the same, except now we need to modify the encoding
argument slightly. More specifically, for any $A_{i}\subseteq[n]$, let
$m_{i}\in A_{i}$ be the minimum element (minimum is well-defined since we
consider the ordered domain is $[n]$) in $A_{i}$. Note that for any $x\in[\log
n]$, we have $D_{x}(m_{i})\geq D_{x}(A_{i})/2$ (for the choice of hard
distribution $D_{x}$ in the proof of 3.1). Thus, Bob can determine the
approximate value of $D_{x}(A_{i})$ without any extra bit sent by Alice. In
general, for $(1+\delta)$-multiplicative approximation of the SET-EVAL query,
Alice needs to send only $O(1/\delta)$ extra bits to Bob to specify the
estimate. Hence, for any constant $\delta$, we get the same lower bound of
$\Omega(\log\log n)$ as in 3.1. This lower bound result is interesting on its
own. Apart from that, it also provides a piece of evidence that
$\Omega(\log\log n)$ might be the correct lower bound even for (exact) COND-
EVAL (which is a combination of COND-PR and exact SET-EVAL) queries.
Therefore, we believe that our Conjecture 1 is true, i.e., $\Omega(\log\log
n)$ lower bound holds even for the COND-EVAL model.

###  4.3 An $\Omega(\frac{1}{\epsilon^{2}\log(1/\epsilon)})$ lower bound

Now we prove a lower bound of $\Omega(\frac{1}{\epsilon^{2}\log(1/\epsilon)})$
for additive $\epsilon n$-approximation of support size (4.27).

######  Lemma 4.24.

Any algorithm that, given COND-EVAL access to a distribution $D$ on $[n]$ and
any $\epsilon=\epsilon(n)\in(0,1]$ where $\epsilon(n)\geq\Omega(n^{-1/2})$,
estimates the support size $|\textsc{supp}(D)|$ to an additive $\epsilon
n$-factor with probability at least $\frac{2}{3}$, must make
$\Omega(\frac{1}{\epsilon^{2}\log n})$ queries to the COND-EVAL oracle.

The proof is based on a reduction from a well-studied communication complexity
problem, namely the _Gap-Hamming distance_ problem, to the support size
estimation problem.

For any two strings $x,y\in\\{0,1\\}^{n}$, their Hamming distance, denoted by
$d_{H}(x,y)$, is the number of coordinates where the bit-values of $x,y$
differ, i.e., $d_{H}(x,y):=|\\{i\in[n]\mid x[i]\neq y[i]\\}|$. In the _Gap-
Hamming distance_ problem $\textsc{Gap-Hamming}_{n,n/2,g}$, Alice and Bob are
given strings $x,y\in\\{0,1\\}^{n}$ respectively (neither of them knows the
input of the other party). Their task is to decide between the following two
cases:

  * •

Yes: $d_{H}(x,y)\geq n/2+g$;

  * •

No: $d_{H}(x,y)<n/2-g$.

In this subsection, we consider the randomized two-way communication
complexity of the above problem. In a randomized two-way communication
protocol, both Alice and Bob are given access to a shared random string
(public randomness) and are allowed to communicate with each other (unlike
one-way protocol as considered in Section 3, where only Alice was allowed to
send a message). Then the question is how many bits need to be sent to solve
the above problem with a probability at least $2/3$. The two-way randomized
communication complexity is defined to be the minimum number of bits that is
communicated in any protocol that solves $\textsc{Gap-Hamming}_{n,n/2,g}$.

######  Theorem 4.25 ([CR12]).

The two-way randomized communication complexity of $\textsc{Gap-
Hamming}_{n,n/2,\sqrt{2n}}$ is $\Omega(n)$.

By using a standard padding argument as in [BCR+10, BBM12], the above theorem
can be generalized as follows.

######  Theorem 4.26 ([CR12, BCR+10, BBM12]).

For any $g\geq\Omega(\sqrt{n})$, the two-way randomized communication
complexity of $\textsc{Gap-Hamming}_{n,n/2,g}$ is $\Omega((n/g)^{2})$.

Now we use the above theorem to prove 4.24.

###### Proof of 4.24.

Suppose there is a randomized algorithm $T$ that, given any $\epsilon>0$ and a
distribution on $[n]$, approximates the support size to an additive $\epsilon
n$-factor with probability at least $2/3$ by making at most $t=t(n)$ COND-EVAL
queries. Now consider an instance of $\textsc{Gap-Hamming}_{n,n/2,g}$, for any
$g\geq\Omega(\sqrt{n})$. Alice and Bob are given $x,y\in\\{0,1\\}^{n}$,
respectively. From $x$, construct the set $I_{x}\subseteq[n]$ by including
each $i\in[n]$ such that $i$-th bit of $x$ is set to 1. So
$I_{x}=\\{i\in[n]\mid x[i]=1\\}$. Similarly, construct $I_{y}\subseteq[n]$
from $y$.

Next, consider the following distribution $D$ over $[n]$

$\displaystyle D(j)=\begin{cases}\frac{2}{|I_{x}|+|I_{y}|}&\text{ if }j\in
I_{x}\cap I_{y}\\\ \frac{1}{(|I_{x}|+|I_{y}|)}&\text{ if }j\in I_{x}\triangle
I_{y}\\\ 0&\text{ otherwise}\end{cases}$

where $\triangle$ denotes the symmetric difference between two sets.

Clearly, $|\textsc{supp}(D)|=|I_{x}\cup
I_{y}|=\frac{1}{2}(|I_{x}|+|I_{y}|+|I_{x}\triangle I_{y}|)$. By the
construction of $I_{x},I_{y}$, $|I_{x}\triangle I_{y}|=d_{H}(x,y)$. So

$|\textsc{supp}(D)|=|I_{x}\cup
I_{y}|=\frac{1}{2}(|I_{x}|+|I_{y}|+d_{H}(x,y)).$ (7)

Next, we argue that Alice and Bob can simulate the algorithm $T$ by setting
$\epsilon=\frac{g}{3n}$, using their shared public random string, say $r$, to
estimate $|\textsc{supp}(D)|$, which in turn help them in deciding whether
$d_{H}(x,y)\geq n/2+g$ or $d_{H}(x,y)<n/2-g$. Note, since $I_{x},I_{y}$ are
known only by Alice and Bob, respectively, none of them know the distribution
$D$.

Let us first argue that given any $S\subseteq[n]$ (known to both Alice and
Bob), a COND-EVAL query to $D$ condition on $S$ can be simulated by Alice and
Bob using only $O(\log n)$ bits of communication. Recall performing a COND-
EVAL query means they need to sample from $D$ condition on $S$ and determine
the actual and conditional probability of the sampled element. This can be
done as follows. Alice first picks an element (say $a$) uniformly at random
from $S\cap I_{x}$ and sends $a$ and the value of $|S\cap I_{x}|$ to Bob. Bob
also selects an element (say $b$) uniformly at random from $S\cap I_{y}$. Bob
then picks $a$ with probability $\frac{|S\cap I_{x}|}{|S\cap I_{x}|+|S\cap
I_{y}|}$ and $b$ with probability $\frac{|S\cap I_{y}|}{|S\cap I_{x}|+|S\cap
I_{y}|}$. Bob then sends this chosen element $c\in\\{a,b\\}$ to Alice. It is
easy to see that $c$ is picked with a probability equal to $D(c)/D(S)$ (i.e.,
the conditional probability of picking $c$ from $D$ conditioned on $S$).
Further, if $c=a$, then Bob tells Alice whether $a\in I_{y}$ or not using
$O(1)$ bits. If $c=b$, then Alice can by herself check whether $c\in I_{x}$ or
not. In any case, Alice knows if $c\in I_{x}\cap I_{y}$ or not. Recall, the
actual probability of any element $j$ in the support of $D$ takes only two
values – $\frac{2}{|I_{x}|+|I_{y}|}$ if $j\in I_{x}\cap I_{y}$, and
$\frac{1}{(|I_{x}|+|I_{y}|)}$ otherwise. Thus Alice can determine the actual
probability of sampled element $c$ as she knows whether $c\in X\cap Y$ or not.
Note,

$D(S)=\sum_{j\in S}D(j)=\frac{|S\cap I_{x}|+|S\cap I_{y}|}{|I_{x}|+|I_{y}|}.$

Both Alice and Bob can know the values of $|I_{x}|,|I_{y}|,|S\cap
I_{x}|,|S\cap I_{y}|$ and thus $D(S)$, by communicating only $O(\log n)$ bits.
Hence, they can determine the conditional probability of the sampled element
as well.

Consider $\epsilon=\frac{g}{3n}$. Let us now describe how Alice and Bob
simulate $T$ using their shared random string $r$. Given $r$, the first set
$A_{1}$ on which $T$ conditions (i.e., places COND-EVAL query), is fixed. Then
Alice and Bob simulate this query by communicating $O(\log n)$ bits using the
protocol described above. Using the outcome of the first COND-EVAL query, $T$
decides the second set $A_{2}$ to condition. In general, at any step $\ell$,
$T$ decides the set $A_{\ell}$ to condition on $D$ based on the outcomes of
COND-EVAL queries so far and the random string $r$. Since $T$ places at most
$t$ queries, Alice and Bob need to communicate $O(t\log n)$ bits to simulate
$T$. At the end of the simulation, with probability at least $2/3$, Alice and
Bob get an estimate $\hat{s}$ of $|\textsc{supp}(D)|$ up to an $\epsilon n$
additive factor. So, $|\textsc{supp}(D)|-\epsilon
n\leq\hat{s}\leq|\textsc{supp}(D)|+\epsilon n$.

For a Yes instance (i.e., $d_{H}(x,y)\geq n/2+g$), by Equation 7,
$|\textsc{supp}(D)|\geq\frac{1}{2}(|I_{x}|+|I_{y}|+n/2+g)$. Thus the estimated
value $\hat{s}\geq\frac{1}{2}(|I_{x}|+|I_{y}|+n/2+g)-\epsilon n$. On the other
hand, for a No instance (i.e., $d_{H}(x,y)<n/2-g$), by Equation 7,
$|\textsc{supp}(D)|<\frac{1}{2}(|I_{x}|+|I_{y}|+n/2-g)$. Thus the estimated
value $\hat{s}<\frac{1}{2}(|I_{x}|+|I_{y}|+n/2-g)+\epsilon n$. It is now
straightforward to verify that for $\epsilon=\frac{g}{3n}$,

$\frac{1}{2}(|I_{x}|+|I_{y}|+n/2-g)+\epsilon
n<\frac{1}{2}(|I_{x}|+|I_{y}|+n/2+g)-\epsilon n.$

Note both Alice and Bob can know the values of $|I_{x}|,|I_{y}|$ by
communicating only $O(\log n)$ bits at the beginning. Hence, Alice and Bob can
decide whether the given instance of $\textsc{Gap-Hamming}_{n,n/2,g}$ is a Yes
instance or No instance with probability at least $2/3$ and the total number
of bits communicated is at most $O(t\log n)$. Recall, $\epsilon=\frac{g}{3n}$.
Then by Theorem 4.26,

$t\geq\Omega\Big{(}\frac{n^{2}}{g^{2}\log
n}\Big{)}=\Omega\Big{(}\frac{1}{\epsilon^{2}\log n}\Big{)}.$

∎

Now, as a direct corollary of 4.24, we get the following.

######  Corollary 4.27.

Consider any $\alpha\in(0,1/2)$. Any algorithm that, given COND-EVAL access to
a distribution $D$ on $[n]$ and any $\epsilon=n^{-\alpha}$, estimates the
support size $|\textsc{supp}(D)|$ to an additive $\epsilon n$-factor with
probability at least $\frac{2}{3}$, must make
$\Omega(\frac{1}{\epsilon^{2}\log(1/\epsilon)})$ queries to the COND-EVAL
oracle.

##  5 Power of COND-EVAL model

In this section, we formally illustrate the power of COND-EVAL model. We
actually focus on an even weaker model, namely SET-EVAL. Recall, a SET-EVAL
oracle for a distribution $D$ on $[n]$, on input a subset $S\subseteq[n]$,
returns the value of $D(S)$. Since using a COND-EVAL query we can simulate a
SET-EVAL query (see Section 2), any upper bound (on the number of queries) in
the SET-EVAL model also provides the same upper bound on the COND-EVAL model.

### Equivalence Testing

As the first example, we consider the standard _equivalence testing_ problem.
Given access to two (unknown) distributions $D,D^{\prime}$, this problem asks
whether $D=D^{\prime}$ or they are “far” from each other. More specifically,
the goal is to accept if $D=D^{\prime}$ and reject if their _total variation
distance_ $||D-D^{\prime}||_{TV}=\sum_{i\in[n]}|D(i)-D^{\prime}(i)|>\epsilon$
(both with high probability). It is known that $\Omega(\sqrt{\log\log n})$
queries are necessary in the COND model [ACK15]. On the other hand, it is easy
to see that $\Omega(1/\epsilon)$ queries must be needed in the COND-PR model.
Below we show that for this problem, it suffices to place only two SET-EVAL
queries to both $D$ and $D^{\prime}$. In particular, we prove the following.

######  Theorem 5.1.

There is an algorithm that given SET-EVAL access to distributions $D$ and
$D^{\prime}$ on $[n]$, makes at most two queries to both $D,D^{\prime}$, and
if $D=D^{\prime}$, always accepts; otherwise, rejects with probability at
least $3/4$.

###### Proof.

Our algorithm generates two sets $S_{1},S_{2}\subseteq[n]$, both of them by
including each element $i\in[n]$ independently with probability $1/2$. The
algorithm accepts if and only if $D(S_{1})=D^{\prime}(S_{1})$ and
$D(S_{2})=D^{\prime}(S_{2})$. Clearly if $D=D^{\prime}$ then the algorithm
always accepts. Next, we show that with probability at least $3/4$, either
$D(S_{1})\neq D^{\prime}(S_{1})$ or $D(S_{2})\neq D^{\prime}(S_{2})$.

To prove the above, let us consider a random subset $S\subseteq[n]$
constructed by including each element $i\in[n]$ independently with probability
$1/2$. Observe, it suffices to show that if $D\neq D^{\prime}$, we have
$D(S)=D^{\prime}(S)$ with probability at most $1/2$.

Let $U=\\{i\in[n]\mid D(i)\neq D^{\prime}(i)\\}$ and $N=\\{T\subseteq U\mid
D(T)\neq D^{\prime}(T)\\}$. We claim that $|N|\geq\frac{2^{|U|}}{2}$. Note, if
for any $A\subseteq U$, $D(A)=D^{\prime}(A)$ then for any $j\in U\setminus A$,
we have $D(A\cup\\{j\\})\neq D^{\prime}(A\cup\\{j\\})$. Consider an undirected
graph with $2^{U}:=\\{V\mid V\subseteq U\\}$ as the set of vertices and
$\\{\\{V_{1},V_{2}\\}\mid V_{1}\subseteq
V_{2},|V_{2}|=|V_{1}|+1,V_{1},V_{2}\subseteq U\\}$ as the set of edges. Thus
$2^{U}\setminus N$ is an independent set (there is no edge between any two
vertices in $2^{U}\setminus N$) in the above graph. Therefore, we have
$|N|\geq\frac{2^{|U|}}{2}$. Recall, $S\subseteq[n]$ is a random subset
constructed by including each element $i\in[n]$ independently with probability
$1/2$. Let $S_{U}=S\cap U$ and $S_{E}=S\cap([n]\setminus U)$. Since
$|N|\geq\frac{2^{|U|}}{2},$ we have $D(S_{U})\neq D^{\prime}(S_{U})$ with
probability at least $1/2$. Also note that $D(S_{E})=D^{\prime}(S_{E})$ and
hence we have $D(S)=D(S_{E})+D(S_{U})\neq
D^{\prime}(S_{E})+D^{\prime}(S_{U})=D^{\prime}(S)$ with probability at least
$1/2$. ∎

### Testing Grained Distributions

A distribution is called $m$-grained if the probability of each element is an
integer multiple of $\frac{1}{m}$. Goldreich and Ron [GR21] show that testing
if a distribution on $[n]$ elements is $m$-grained, where $m=\Theta(n)$
requires $\Omega(n^{c})$ SAMP queries for any constant $c<1$. Grained
distributions appear in several prior works, either implicitly (e.g.,
[RRSS09]) or as in [Gol20, GR21].

Surprisingly, we show that just two SET-EVAL queries are sufficient to test
grained distributions. The algorithm and proof is similar to as that of
Equivalence testing.

######  Theorem 5.2.

There is an algorithm that given SET-EVAL access to distributions $D$ on
$[n]$, makes at most two queries, and if $D$ is $m$-grained, always accepts;
otherwise, rejects with probability at least $3/4$.

###### Proof.

Our algorithm generates two sets $S_{1},S_{2}\subseteq[n]$, both of them by
including each element $i\in[n]$ independently with probability $1/2$. The
algorithm accepts if and only if both $D(S_{1})$ and $D(S_{2})$ are an integer
multiple of $\frac{1}{m}$. Clearly if $D$ is $m$-grained then the algorithm
always accepts. Below we claim that if $D$ is not $m$-grained, with
probability at least $3/4$, either $D(S_{1})$ or $D(S_{2})$ is not an integer
multiple of $\frac{1}{m}$.

Let $S\subseteq[n]$ be a random set constructed by including each element
$i\in[n]$ independently with probability $1/2$. Observe, it suffices to show
that if $D$ is not $m$-grained then with probability at least $1/2$, $D(S)$ is
not an integer multiple of $\frac{1}{m}$, the proof of which is similar to
that in Theorem 5.1. Let $U=\\{i\in[n]\mid D(i)\thinspace\text{is not an
integer multiple of}\thinspace\frac{1}{m}\\}$ and $N=\\{T\subseteq U\mid
P(T)\thinspace\text{is not an integer multiple of}\thinspace\frac{1}{m}\\}$.
We claim that $|N|\geq\frac{2^{|U|}}{2}$. If for any $A\subseteq U$, $D(A)$ is
an integer multiple of $\frac{1}{m}$ then for any $j\in U\setminus A$,
$D(A\cup\\{j\\})$ is not an integer multiple of $\frac{1}{m}$. As argued in
Theorem 5.1, we have $|N|\geq\frac{2^{|U|}}{2}$. Recall, $S\subseteq[n]$ is a
random subset constructed by including each element $i\in[n]$ independently
with probability $1/2$. Let $S_{U}=S\cap U$ and $S_{E}=S\cap([n]\setminus U)$.
Since $|N|\geq\frac{2^{|U|}}{2}$, $D(S_{U})$ is not an integer multiple of
$1/m$ with probability at least $1/2$. Also note that $D(S_{E})$ is an integer
multiple of $1/m$ and hence $D(S)=D(S_{E})+D(S_{U})$ is not an integer
multiple of $1/m$ with probability at least $1/2$. ∎

### Estimating $L_{2}$ norm

The third example we consider is the classical (squared) $L_{2}$ norm
estimation problem for a distribution. The $L_{2}$ norm of a distribution $D$
over $[n]$, denoted by $\ell_{2}(D)$, is defined as
$\ell_{2}(D):=(\sum_{j\in[n]}D(j)^{2})^{1/2}$. In this problem, given oracle
access to a distribution $D$ on $[n]$, we are asked to estimate
$\ell_{2}^{2}(D)$ up to a multiplicative $(1+\epsilon)$-factor. To the best of
our knowledge, this problem has been studied previously only in the SAMP model
[GR11], wherein it was shown that $\Omega(\frac{\sqrt{n}}{\epsilon^{2}})$
queries are required.

Surprisingly, we show that $\Omega(\sqrt{n})$ queries are also required in
COND and COND-PR models. Further, we show that in the SET-EVAL model (hence
COND-EVAL model too), only $O(1/\epsilon^{2})$ queries are sufficient. Our
algorithm (and also the analysis) resembles that of estimating $L_{2}$ norm in
the streaming model [AMS99]. We also show an almost tight lower bound of
$\Omega(\frac{1}{\epsilon^{2}\log\frac{1}{\epsilon}})$ for the COND-EVAL
model.

######  Theorem 5.3.

There is an algorithm that given SET-EVAL access to distributions $D$ on $[n]$
and $\epsilon>0$, estimates $\ell_{2}^{2}(D)$ within a multiplicative
$(1+\epsilon)$-factor with probability at least $3/4$, by making at most
$O(\frac{1}{\epsilon^{2}})$ queries.

###### Proof.

Consider a $4$-wise independent hash function $h:[n]\rightarrow\\{-1,1\\}$.
Let $S^{+}=\\{j\in[n]\mid h(j)=1\\}$ and $S^{-}=\\{j\in[n]\mid h(j)=-1\\}$.
Then we compute $X=(D(S_{+})-D(S_{-}))^{2}$. We repeat the above procedure
independently for $t=4/\epsilon^{2}$ times and output the mean $\bar{X}$ of
the values of the random variable $X$ in each iteration. (Let $X_{i}$ denote
the value of $X$ at the $i$-th iteration. Then we compute
$\bar{X}=\frac{\sum_{i=1}^{t}X_{i}}{t}$.) Note, the total number of SET-EVAL
queries is $8/\epsilon^{2}$.

We will show that at any iteration, $\mathbb{E}[X]=\sum_{j\in[n]}D^{2}(j)$ and
$Var[X]\leq(\mathbb{E}[X])^{2}$. Then clearly we have
$\mathbb{E}[\bar{X}]=\mathbb{E}[X]$ and $Var[\bar{X}]=\frac{Var[X]}{t}$.
Hence, by Chebyshev inequality, we have

$\Pr[|\bar{X}-\sum_{j\in[n]}D(j)^{2}|>\epsilon\sum_{j\in[n]}D(j)^{2}]\leq\frac{Var[\bar{X}]}{\epsilon^{2}(\mathbb{E}[\bar{X}])^{2}}\leq\frac{1}{4}.$

So, it only remains to prove that $\mathbb{E}[X]=\sum_{j\in[n]}D^{2}(j)$ and
$Var[X]\leq(\mathbb{E}[X])^{2}$. Note that
$X=(D(S_{+})-D(S_{-}))^{2}=(\sum_{j\in[n]}h(j)D(j))^{2}=\sum_{j\in[n]}D^{2}(j)+2\sum_{i<j}h(i)h(j)D(i)D(j)$
(since $h^{2}(j)=1$ for all $j\in[n]$). Therefore,
$\mathbb{E}[X]=\sum_{j\in[n]}D^{2}(j)+2\sum_{i<j}\mathbb{E}[h(i)h(j)D(i)D(j)]$.
Since $h$ is $4$-wise independent, $\mathbb{E}[h(j)]=0$ for any $j\in[n]$ and
also $\mathbb{E}[h(i)h(j)]=\mathbb{E}[h(i)]\cdot\mathbb{E}[h(j)]$ = 0 for any
$i\neq j$. Hence, $\mathbb{E}[X]=\sum_{j\in[n]}D^{2}(j)$. The variance
$Var[X]$ can similarly be bounded as follows. Note that since $h$ is $4$-wise
independent,
$\mathbb{E}[h(i)h(j)h(k)h(l)]=\mathbb{E}[h(i)]\mathbb{E}[h(j)]\mathbb{E}[h(k)]\mathbb{E}[h(l)]=0$
if any of $i,j,k,l\in[n]$ appears once or thrice.

$\displaystyle Var[X]=\mathbb{E}[X^{2}]-(\mathbb{E}[X])^{2}$
$\displaystyle=\mathbb{E}[(\sum_{j\in[n]}h(j)D(j))^{4}]-(\sum_{j\in[n]}D^{2}(j))^{2}$
$\displaystyle=\sum_{i,j,k,l\in[n]^{4}}D(i)D(j)D(k)D(l)\mathbb{E}[h(i)h(j)h(k)h(l)]-(\sum_{j\in[n]}D^{2}(j))^{2}$
$\displaystyle=\sum_{j\in[n]}D^{4}(j)+\frac{1}{2}\binom{4}{2}\sum_{i\neq
j}D^{2}(i)D^{2}(j)-(\sum_{j\in[n]}D^{2}(j))^{2}$ $\displaystyle=\sum_{i\neq
j}D^{2}(i)D^{2}(j)\leq(\mathbb{E}[X])^{2}.$

∎

Next, we show that the above upper bound result for the squared $\ell_{2}$
norm estimation is almost tight.

######  Theorem 5.4.

Consider any $\alpha\in(0,1/2)$. Any algorithm that, given COND-EVAL access to
a distribution $D$ on $[n]$ and any $\epsilon=n^{-\alpha}$, estimates
$\ell_{2}^{2}(D)$ within a multiplicative $(1+\epsilon)$-factor with
probability at least $2/3$, must make
$\Omega(\frac{1}{\epsilon^{2}\log(1/\epsilon)})$ queries to the COND-EVAL
oracle.

###### Proof.

The proof is based on the observation that, in the proof of the Lemma 4.24, we
have
$\ell_{2}^{2}(D)=\sum_{j}D(j)^{2}=\frac{2(|I_{x}|+|I_{y}|)-d_{H}(x,y)}{(|I_{x}|+|I_{y}|)^{2}}$.
The ratio of $\ell_{2}^{2}(D)$ for Yes and No instances is

$\frac{2(|I_{x}|+|I_{y}|)-(n/2-g)}{2(|I_{x}|+|I_{y}|)-(n/2+g)}\geq 1+\epsilon$

for the same values of parameters $\epsilon$ and $g$. Thus the lower bound
also applies to estimates $\ell_{2}^{2}(D)$ within a multiplicative
$(1+\epsilon)$-factor. ∎

######  Theorem 5.5.

Any algorithm that, given COND-PR (COND) access to a distribution $D$ on $[n]$
estimates $\ell_{2}^{2}(D)$ within a multiplicative $5/4$-factor with
probability at least $2/3$, must make $\tilde{\Omega}(\sqrt{n})$ queries to
the COND-PR (COND) oracle.

###### Proof.

Let $D_{1}$ be a uniform distribution on $[n]$, i.e, $D_{1}(j)=1/n$ for all
$j\in[n]$. Clearly, $\ell_{2}^{2}(D_{1})=1/n$. For any $k\in[n]$ and any
$G\subseteq[n]\setminus\\{k\\}$ such that $|G|=n-\sqrt{n}$, consider a
distribution $D_{k,G}$ on $[n]$, defined as follows.

$\displaystyle D_{k,G}(j)=\begin{cases}\frac{1}{\sqrt{n}}&\text{ if }j=k\\\
\frac{1}{n}&\text{ if }j\in G\\\ 0&\text{ otherwise}.\end{cases}$

Let $\mathcal{D}_{2}=\bigcup_{k,G}D_{k,G}$ be the set of distributions over
all possible values of $k$ and $G$. Note that for any
$D_{2}\in\mathcal{D}_{2}$, we have
$\ell_{2}^{2}(D_{2})=1/n+(n-\sqrt{n})\cdot\frac{1}{n^{2}}\geq\frac{5}{4n}$.

Consider a distribution $D$ randomly selected from distributions in
$D_{1}\cup\bigcup_{k,G}D_{k,G}$ as follows. We pick $D_{1}$ with probability
$1/2$ and any distribution $D_{k,G}\in\mathcal{D}_{2}$ with probability
$\frac{1}{2|\mathcal{D}_{2}|}$. As before, from Yao’s theorem, it suffices to
show $\tilde{\Omega}(\sqrt{n})$ lower bound on the number of queries for any
deterministic tester $T$ that correctly answers whether $D=D_{1}$ or
$D\in\mathcal{D}_{2}$ with probability $2/3$, for randomly chosen distribution
$D$ as described above.

For any fixed $S\subseteq[n]$, let $N^{g}_{S}$ be the random variable denoting
the cardinality of the set $|\\{j\in S:D(j)=1/n\\}|$ and $N^{b}_{S}$ be the
random variable denoting the cardinality of the set $|\\{j\in
S:D(j)\in\\{0,1/\sqrt{n}\\}\\}|$. We want to show that
$\frac{N^{b}_{S}}{N^{b}_{S}+N^{g}_{S}}>\frac{(\log n)^{2}}{\sqrt{n}}$ holds
with probability at most $1/n^{2}$. This is trivially true when $D=D_{1}$.
Given that $D\in\mathcal{D}_{2}$, we have
$\mu^{g}_{S}=\mathbb{E}[N^{g}_{S}]=|S|(1-1/\sqrt{n})$ and
$\mu^{b}_{S}=\mathbb{E}[N^{b}_{S}]=|S|/\sqrt{n}.$ Further,

  1. 1.

Suppose $|S|\geq\frac{\sqrt{n}}{(\log n)^{2}}$. By Chernoff’s bound, we have
$\Pr[N^{b}_{S}\geq(\log n)^{2}\mu^{b}_{S}]\leq exp(-\frac{1}{3}(\log
n)^{4}\mu^{b}_{S})\leq exp(-\frac{1}{3}(\log n)^{2})<1/n^{2}$ and
$\Pr[N^{g}_{S}\leq\mu^{g}_{S}/2]\leq exp(-\frac{\sqrt{n}}{10(\log
n)^{2}})<1/n^{2}$. Hence we have,
$\frac{N^{b}_{S}}{N^{b}_{S}+N^{g}_{S}}>\frac{(\log n)^{2}}{\sqrt{n}}$ with
probability at most $1/n^{2}$.

  2. 2.

If $|S|\leq\frac{\sqrt{n}}{(\log n)^{2}}$ then again by Chernoff bound, we
have $\Pr[N^{b}_{S}\geq 1]\leq exp(-(1/\mu^{b}_{S}-1)^{2}\mu^{b}_{S})\leq
exp(-(\log n)^{2}/4)<1/n^{2}$. Hence , we have
$\frac{N^{b}_{S}}{N^{b}_{S}+N^{g}_{S}}>\frac{(\log n)^{2}}{\sqrt{n}}$ with
probability at most $1/n^{2}$.

If $T$ makes $q<\frac{\sqrt{n}}{(\log n)^{2}}$ queries then probability that
for all $q$ query sets $S$, we have
$\frac{N^{b}_{S}}{N^{b}_{S}+N^{g}_{S}}\leq\frac{(\log n)^{2}}{\sqrt{n}}$ is at
least $1-q/n^{2}\geq 1-1/n$. Further, probability that any of the $q$ COND-PR
(or COND) queries returns an element with probability value $1/\sqrt{n}$ is at
most $q\cdot\frac{(\log n)^{2}}{\sqrt{n}}<1/3$ for $q<\frac{\sqrt{n}}{3(\log
n)^{2}}$. Hence, with probability at least $2/3$, the tester $T$ can not
distinguish between $D=D_{1}$ or $D\in\mathcal{D}_{2}$ if
$q<\frac{\sqrt{n}}{3(\log n)^{2}}$ (as the outcomes at every step will be an
element with probability $1/n$ for both distributions).

∎

##  6 Bounded-Set Conditioning

In this section, we discuss the power of conditioning when the conditioned set
is of bounded size, in light of the support size estimation problem. A _$k$
-bounded conditional_, in short ${\textsc{COND}}_{k}$, oracle (similarly
${\textsc{COND-PR}}_{k}$ and ${\textsc{COND-EVAL}}_{k}$) allow the input set
$S\subseteq[n]$ to be of size at most $k$. Additionally, we also allow
algorithms to access SAMP oracle (to make sure that it is at least as powerful
as the SAMP model). Note, this is indeed the case in the literature while
allowing _pair-conditioning_ (PAIRCOND), i.e., when $k=2$ (e.g. [CFGM16,
CRS15, CR14]).

In this bounded conditioning model, we show that to get an estimation of the
support size up to a constant factor, we need at least $\Omega(n/k)$ queries,
which is in contrast with the $O(\log\log n)$ upper bounded in the standard
(unbounded) conditioning model.

######  Theorem 6.1.

Any algorithm that, given SAMP access and ${\textsc{COND-EVAL}}_{k}$ access to
a distribution $D$ on $[n]$, approximates the support size
$|\textsc{supp}(D)|$ within a multiplicative $6/5$-factor with probability at
least $2/3$, must make at least $\Omega(\frac{n}{k})$ queries.

###### Proof.

Let us consider the following two sets of distributions. Let
$\mathcal{D}_{1}=\bigcup_{2\leq i\leq n}\\{D_{i}\\}$, where $D_{i}$ is defined
as follows.

$\displaystyle D_{i}(j)=\begin{cases}1-\frac{2}{n}&\text{ if }j=1\\\
\frac{2}{n}&\text{ if }j=i\\\ 0&\text{ otherwise}.\end{cases}$

Let $\mathcal{D}_{2}=\bigcup_{2\leq i<i^{\prime}\leq
n}\\{D_{i,i^{\prime}}\\}$, where $D_{i,i^{\prime}}$ is defined as follows.

$\displaystyle D_{i,i^{\prime}}(j)=\begin{cases}1-\frac{2}{n}&\text{ if
}j=1\\\ \frac{1}{n}&\text{ if }j\in\\{i,i^{\prime}\\}\\\ 0&\text{
otherwise}.\end{cases}$

Note that the support size of any distribution in $\mathcal{D}_{1}$ is $2$,
whereas that of any distribution in $\mathcal{D}_{2}$ is $3$. Consider a
distribution $\gamma$ that picks $r\in\\{1,2\\}$ uniformly at random. Then it