[inst1]organization=Department of Electrical Engineering,addressline=IIT
Bombay, country=India

# Fixed confidence community mode estimation

Meera Pai  Nikhil Karamchandani  Jayakrishnan Nair

###### Abstract

Our aim is to estimate the largest community (a.k.a., mode) in a population
composed of multiple disjoint communities. This estimation is performed in a
fixed confidence setting via sequential sampling of individuals with
replacement. We consider two sampling models: (i) an identityless model,
wherein only the community of each sampled individual is revealed, and (ii) an
identity-based model, wherein the learner is able to discern whether or not
each sampled individual has been sampled before, in addition to the community
of that individual. The former model corresponds to the classical problem of
identifying the mode of a discrete distribution, whereas the latter seeks to
capture the utility of identity information in mode estimation. For each of
these models, we establish information theoretic lower bounds on the expected
number of samples needed to meet the prescribed confidence level, and propose
sound algorithms with a sample complexity that is provably asymptotically
optimal. Our analysis highlights that identity information can indeed be
utilized to improve the efficiency of community mode estimation.

###### keywords:

mode estimation; identity-based sampling; PAC algorithms; generalized
likelihood ratio (GLR) statistics

111Nikhil Karamchandani and Jayakrishnan Nair acknowledge support from SERB
via grant CRG/2021/002923 and two MATRICS grants.

##  1 Introduction

There are several interesting applications which are based on sequentially
sampling individuals from an underlying population. Examples include online
cardinality estimation [14, 7, 5, 22] where the goal is to approximate the
total size of the population and algorithms are typically based on the
counting of ‘collisions’, i.e., instances where the sampled individual was
‘seen’ before; community exploration [9, 21, 6] where the goal is to discover
as many distinct entities of interest as possible; and community detection /
clustering [30, 10, 24] where the underlying population is naturally divided
into communities / clusters and the goal is to estimate the true clustering
using samples from the population.

In this work, we study a variant of the above problems where the learning
agent can sequentially sample individuals uniformly at random from a
population and the goal is to identify the largest community, a.k.a. the
community mode. Some applications which motivate our formulation are (i)
election polling where the community of an individual is the candidate / party
it supports and estimating the community mode corresponds to predicting the
winning candidate / party; (ii) identifying the dominant strain of a virus in
an infected population where the communities refer to different strains; and
(iii) market research surveys where the goal is to identify the most prevalent
opinion in a population on some topic of interest.

We consider two sampling models in our formulation, which differ in the
information revealed to the agent about each sample: (i) identityless sampling
where only the community that the sampled individual belongs to is provided to
the learning agent; and (ii) identity-based sampling where in addition to the
community information, the agent is also able to infer if the sampled
individual was seen before during the sampling process.

Since at each time, an individual is sampled uniformly at random from the
population, the probability that it belongs to a certain community is
proportional to the community size. Thus, under the identityless sampling
model, where the observation at each time is just the community label,
identifying the largest community becomes equivalent to identifying the mode
of an underlying discrete distribution from independent and identically
distributed (i.i.d.) samples. Given a target error probability, the goal is to
define a stopping rule which minimizes the number of samples needed to
estimate the mode reliably. This problem was recently studied in [26] where an
instance-dependent (i.e., it is a function of the underlying probability
distribution) lower bound on the optimal sample complexity was derived and an
algorithm based on the idea of data-driven confidence intervals [23] was
proposed, for which the sample complexity was shown to be within a constant
factor of the optimal. More recently, [19] proposed an alternate stopping rule
based on prior-posterior-ratio (PPR) martingale confidence sequences (see
[28]) and showed that its sample complexity is in fact asymptotically optimal
as the target error probability goes to zero. For this problem, we consider an
alternate Chernoff-style stopping rule based on a novel Generalized Likelihood
Ratio (GLR) statistic [11] and prove its asymptotic optimality.
(Interestingly, we discover a connection between our GLR based algorithms and
PPR based algorithms; see Remark 3.8).

In contrast to the identityless sampling model, the identity-based sampling
model allows the learning agent to also know whether the sampled individual at
each time was seen before or not. A key focus of this work is to study the
impact of this additional ‘identity’ information on the sample complexity of
community mode estimation. The main challenge in designing and analyzing a
sample-efficient stopping rule for this setting is that the observations are
no longer i.i.d. across time; in fact the process has a Markovian structure.
While a direct application of our GLR statistic for the identityless setting
is computationally intractable in the identity-based setting, we devise a
computationally tractable relaxation of this statistic that preserves both
soundness as well as asymptotic optimality. We clearly demonstrate, via both
theoretical results as well as numerical simulations, that there can be a
significant gap between the optimal sample complexity for community mode
estimation under the identityless and the identity-based sampling models.

The GLR based test has found application in several other online learning
settings, including change point detection [27] and best arm identification in
multi armed bandits [15]. As mentioned before, one of the key technical
challenges for our setting is that the observations are non i.i.d.; in fact
the number of distinct individuals seen from each community evolves as an
absorbing Markov chain in the community mode estimation problem.

The mode estimation problem has been studied classically in the batch or non-
sequential setting since many decades, see for example [25, 12], with focus
mainly on proving statistical properties such as consistency for various
estimators. Another related problem with a long and rich history is property
estimation from samples generated from an underlying distribution. Recent work
has characterized the optimal sample complexity for various properties of
interest such as entropy [8, 4], support size and coverage [16, 29], amongst
others. Finally, the problem of community mode estimation has been recently
studied in [18] under the fixed budget setting, i.e., the number of samples is
fixed and the goal is to design decision rules which minimize the probability
of error. In contrast, our work focuses on the fixed confidence setting where
a target error probability is specified but the number of samples is not fixed
apriori and the goal is to design stopping rules with small sample complexity.

In this paper, we considered the learning task of online community mode
estimation in a fixed confidence setting, focusing on the role of identity
information. Our analysis relies heavily on the existing GLR-based machinery
for establishing correctness and asymptotic optimality of PAC algorithms (most
notably, the methodology developed in [15, 20]). Our key novelty is:
(i) From a modeling standpoint, we highlight the value of _identity_
information in mode estimation.
(ii) We modify the GLR statistic proposed in [20] to design a tractable
algorithm for the identityless sampling model. A superior ‘1v1’ variant of
this algorithm is also designed, which turns out to be identical to the state
of the art algorithm for (identityless) mode estimation–PPR-1v1 (see [19]),
which was designed using a different design recipe.
(ii) We design a sound stopping condition under a _Markovian_ observation
sequence (arising under identity-based sampling), and further design a
computationally tractable relaxation of the stopping statistic that preserves
both soundness and asymptotic optimality (Lemma 4.3 is crucial to this
relaxation); indeed, that the discrete likelihood optimization over
$\mathbb{N}^{K}$ in (14) can be tractably relaxed is far from trivial.

##  2 Problem formulation

We consider a population of $N$ individuals. This population is partitioned
into $K$ communities, the set of communities being denoted by
$\mathcal{K}=\\{1,2,\ldots,K\\}.$ In particular, community $j$ has $d_{j}$
individuals, so that $\sum_{j\in\mathcal{K}}d_{j}=N.$ Our goal is to identify
the largest community (a.k.a., the community mode) in this population, via
sequential (random) sampling of individuals _with replacement_ , in a fixed
confidence setting. At each sampling epoch, an individual, selected uniformly
at random from the population, is ‘seen’ by the learning agent. We make the
assumption that the number of communities $K$ is known to the learning agent.
However, _the total population size $N$ is assumed to be a priori unknown to
the learning agent_. We consider two different sampling models in this work,
which differ in the information that the learning agent obtains in each
sampling epoch.

  1. 1.

Identityless sampling:
Under this sampling model, at each time (a.k.a., sampling epoch) $t$, only the
community associated with the sampled individual is revealed to the learning
agent. In particular, let $x_{t}$ denote the community of the individual
sampled at time $t$. Then the vector
$\boldsymbol{x}^{t}=(x_{1},x_{2},\ldots,x_{t})$ represents the observations
recorded by the learning agent till time $t$.

Under the identityless sampling model, the agent is essentially recording
i.i.d. samples from a distribution with support $\mathcal{K},$ with a
probability mass $p_{j}=d_{j}/N$ on community $j.$ Thus, community mode
estimation boils down to identifying the mode of this distribution using
i.i.d. samples; this estimation has been analysed recently (also in the fixed
confidence setting) in [26, 19]. In particular, [19] proposed a stopping rule
based on prior-posterior-ratio (PPR) martingale confidence sequences [28] and
showed that its sample complexity is asymptotically optimal as the target
error probability goes to zero. We prove an analogous result for an alternate
Chernoff-style stopping rule based on a Generalized Likelihood Ratio (GLR)
statistic [11]. More importantly, this result for the identityless sampling
model provides a benchmark for the identity-based sampling model described
next and will help us quantify the impact of identity information in community
mode estimation.

  2. 2.

Identity-based sampling:
Under this sampling model, we assume that along with the community of the
sampled individual, the learning agent is also able to _identify_ her, such
that it knows whether or not this individual has been seen before.

It is important to note that under identity-based sampling, the learning agent
does not need to observe or record a unique identifier (say a ‘social security
number’) associated with the sampled individual. It may simply assign a
pseudo-identity to each individiual when she is seen for the first time; all
that is assumed here is the agent’s ability to compare the sampled individual
with those sampled before. For example, in the context of wildlife
conservation, samples might correspond to animal sightings collected by camera
traps, with image processing tools used to identify distinct
sightings.222https://www.nytimes.com/1996/07/30/science/snapshots-to-improve-
the-tallies-of-tigers.html

Let $\sigma_{t}$ be an indicator of whether the individual sampled at time $t$
is new or repeated; formally,

$\sigma_{t}=\begin{cases}0&\text{if sample at time~{}$t$ was seen before,}\\\
1&\text{if sample at time~{}$t$ was observed for the first time}.\end{cases}$

Under the identity-based sampling model, the observation recorded at time $t$
is $(x_{t},\sigma_{t})$, and the observations made till time $t$ are captured
by $(\boldsymbol{x}^{t},\boldsymbol{\sigma}^{t}),$ where
$\boldsymbol{\sigma}^{t}=(\sigma_{1},\sigma_{2},\ldots,\sigma_{t}).$

Unlike the identityless sampling model, observations under the identity-based
sampling model are not i.i.d. across time; rather, the observation process is
_Markovian_. This complicates the design and analysis of sound stopping rules
for the identity-based sampling model (see Section 4).333The identity-based
sampling model has been also used before in the context of cardinality
estimation [14, 7] and community exploration [9].

As noted before, our goal is to estimate the community mode in a fixed
confidence setting under the above sampling models. Without loss of
generality, we assume that the community 1 is the largest, and that the
community sizes satisfy $d_{1}>d_{2}\geq\cdots d_{K-1}\geq d_{K}.$ Given a
prescribed error threshold $\delta\in(0,1),$ we seek to design $\delta$-PC
algorithms (PC stands for _Probably Correct_), i.e., algorithms that terminate
at a stopping time, say $\tau_{\delta},$ and output a mode estimate
$\hat{a}_{\tau_{\delta}},$ such that the probability of error is bounded by
$\delta,$ i.e., ${\mathbb{P}}(\tau_{\delta}<\infty,\hat{a}_{\tau_{\delta}}\neq
1)\leq\delta.$

##  3 Mode estimation with identityless sampling

In this section, we study the sequential mode estimation problem under the
identityless sampling model. Specifically, we propose an algorithm that stops
sampling based on a novel generalized likelihood ratio (GLR) statistic
inspired by [20] (which uses a related statistic in the context of detecting
an odd Markov arm). This algorithm is proved to be sound (i.e., $\delta$-PC),
and also asymptotically optimal as $\delta\downarrow 0.$ We also propose a
‘one-versus-one’ variant of the same algorithm, which makes only pairwise
comparisons between communities (disregarding observations pertaining to other
communities when considering any pair of communities) and show that this ‘1v1’
variant outperforms the original algorithm. The algorithms proposed in this
section serve as a benchmark for the algorithms we design under the identity-
based sampling model in Section 4.

We begin by stating an information theoretic lower bound on the expected
stopping time of any $\delta$-PC mode estimation algorithm under identityless
sampling.

######  Lemma 3.1 (Theorem 3 in [26]).

Under the identityless sampling model, given $\delta\in(0,1)$, the expected
stopping time ${\mathbb{E}}[\tau_{\delta}]$ of any $\delta$-PC algorithm
satisfies

${\mathbb{E}}[\tau_{\delta}]\geq\frac{\log\left(\frac{1}{2.4\delta}\right)}{(p_{1}+p_{2})\
kl\left(\frac{p_{1}}{p_{1}+p_{2}},\frac{1}{2}\right)},$

where
$kl(x,y):=x\log\left(\frac{x}{y}\right)+(1-x)\log\left(\frac{1-x}{1-y}\right)$
denotes the binary relative entropy function.444Throughout the paper, all
logarithms are to the base $e.$

Next, we describe our main algorithm, which seeks to match the above lower
bound as $\delta\downarrow 0.$

###  3.1 The NI-ME algorithm

At time $t\in{\mathbb{N}}$ (specifically, after sampling epoch $t$), let
$N_{i}(t)$ denote the number of observations from community $i,$ and let
$\hat{p}_{i}(t):=N_{i}(t)/t$ denote the empirical frequency of samples from
community $i.$ Let
$\hat{a}_{t}:=\operatorname*{arg\,max}_{i\in\mathcal{K}}\hat{p}_{i}(t)$ and
$\hat{b}_{t}:=\operatorname*{arg\,max}_{i\in\mathcal{K}\setminus\\{\hat{a}_{t}\\}}\hat{p}_{i}(t)$
denote the communities associated with the largest and second largest
empirical frequency respectively. (In case either maximizer is not unique,
$\hat{a}_{t}$ and $\hat{b}_{t}$ may be chosen arbitrarily from the
corresponding sets of maximizers.)

We employ the following stopping statistic:

$\displaystyle Z(t)$
$\displaystyle:=\log\frac{B(N_{1}(t)+1,N_{2}(t)+1,\ldots,N_{K}(t)+1)}{B(1,1,\ldots,1)}-\sum_{i\in\mathcal{K}\setminus\\{\hat{a}_{t},\hat{b}_{t}\\}}N_{i}(t)\log(\hat{p}_{i}(t))$
$\displaystyle\qquad-(N_{\hat{a}_{t}}(t)+N_{\hat{b}_{t}}(t))\log\left(\frac{\hat{p}_{\hat{a}_{t}}(t)+\hat{p}_{\hat{b}_{t}}(t)}{2}\right)$
(1)

Here $B:\mathbb{R}_{+}^{K}\rightarrow\mathbb{R}_{+}$ denotes the multinomial
beta function.555For
$\boldsymbol{\psi}=(\psi_{1},\psi_{2},\ldots,\psi_{K})\in\mathbb{R}_{+}^{K},$
$\displaystyle
B(\boldsymbol{\psi})=\frac{\prod_{i=1}^{K}\Gamma(\psi_{i})}{\Gamma(\sum_{i=1}^{K}\psi_{i})},$
where $\Gamma(.)$ denotes the gamma function. The proposed algorithm, which we
refer to as the _No Identity Mode Estimation_ (NI-ME) algorithm, stops
sampling if

$\begin{array}[]{l}Z(t)>\beta(t,\delta):=\log\left(\frac{K-1}{\delta}\right),\end{array}$
(2)

and outputs the mode estimate $\hat{a}_{t}$. This is stated formally as
Algorithm 1.

Algorithm 1 No Identity Mode Estimation (NI-ME) algorithm

$t\leftarrow 1$

loop

Obtain $x_{t}$

$\hat{a}_{t}\leftarrow\arg\max_{i\in\mathcal{K}}\hat{p}_{i}(t)$,
$\hat{b}_{t}\leftarrow\arg\max_{i\in\mathcal{K}\setminus\\{\hat{a}_{t}\\}}\hat{p}_{i}(t)$

$Z(t)\leftarrow\log\frac{B(N_{1}(t)+1,N_{2}(t)+1,\ldots,N_{K}(t)+1)}{B(1,1,\ldots,1)}-\sum_{i\in\mathcal{K}\setminus\\{\hat{a}_{t},\hat{b}_{t}\\}}N_{i}(t)\log(\hat{p}_{i}(t))$

$\hskip
85.35826pt-(N_{\hat{a}_{t}}(t)+N_{\hat{b}_{t}}(t))\log\left(\frac{\hat{p}_{\hat{a}_{t}}(t)+\hat{p}_{\hat{b}_{t}}(t)}{2}\right)$

$\beta(t,\delta)\leftarrow\log\left(\frac{K-1}{\delta}\right)$

if $Z(t)>\beta(t,\delta)$ then

stopping time $\tau_{\delta}=t$ and mode $\hat{a}_{\tau_{\delta}}=\hat{a}_{t}$

Exit loop

else

$t\leftarrow t+1$

end if

end loop

###  3.2 Stopping rule interpretation

From (2), the stopping time of the NI-ME algorithm is given by

$\tau_{\delta}=\inf\\{t\in{\mathbb{N}}\colon Z(t)>\beta(t,\delta)\\}.$ (3)

In what follows, we interpret $Z(t),$ defined in (1) as a certain GLR
statistic.

At time $t\in{\mathbb{N}},$ the observations made by the learning agent thus
far are represented by $\boldsymbol{x}^{t}=(x_{1},x_{2},\ldots,x_{t}).$ Recall
that $x_{j}$ denotes the community associated with the sampled individual at
time $j$ and $p_{i}=d_{i}/N$ denotes the probability of drawing a sample from
community $i$ at any given time. Thus, the likelihood associated with the
observations till time $t$ is given by

$\mathcal{L}_{\boldsymbol{p}}(x_{1},x_{2},\ldots,x_{t})=\prod_{i=1}^{K}p_{i}^{N_{i}(t)},$

where $\boldsymbol{p}=(p_{1},p_{2},\ldots p_{K}).$ Let $\mathcal{S}$ denote
the $K$-dimensional probability simplex, i.e. the set of all $K$-dimensional
probability mass functions, and let $\mathcal{P}$ denote the Dirichlet
distribution over $\mathcal{S},$ with all concentration parameters equal to
one.666The probability density function associated with $\mathcal{P}$ is
constant and equal to $\frac{1}{B(1,1,\ldots,1)}=\frac{1}{\Gamma(K)}$ over
$\mathcal{S}.$ For communities $a,b\in\mathcal{K},$ define the statistic

$\displaystyle
Z_{a,b}(t):=\log\frac{{\mathbb{E}}_{\boldsymbol{p}^{\prime}\sim\mathcal{P}}[\mathcal{L}_{\boldsymbol{p}^{\prime}}(\boldsymbol{x}^{t})]}{\max_{\boldsymbol{p}^{\prime}\in\mathcal{S}\colon
p^{\prime}_{a}\leq
p^{\prime}_{b}}\mathcal{L}_{\boldsymbol{p}^{\prime}}(\boldsymbol{x}^{t})}.$
(4)

We now show that $Z_{a,b}(t)$ admits a simpler representation in terms of the
empirical frequencies of communities.

######  Lemma 3.2.

At any time $t\in{\mathbb{N}}$, if $\hat{p}_{a}(t)\geq\hat{p}_{b}(t),$ then

$\displaystyle Z_{a,b}(t)$
$\displaystyle=\log\frac{B(N_{1}(t)+1,N_{2}(t)+1,\ldots,N_{K}(t)+1)}{B(1,1,\ldots,1)}-\sum_{i\in\mathcal{K}\setminus\\{a,b\\}}N_{i}(t)\log(\hat{p}_{i}(t))$
$\displaystyle\hskip
85.35826pt-(N_{a}(t)+N_{b}(t))\log\left(\frac{\hat{p}_{a}(t)+\hat{p}_{b}(t)}{2}\right),$
$\displaystyle Z_{b,a}(t)$
$\displaystyle=\log\frac{B(N_{1}(t)+1,N_{2}(t)+1,\ldots,N_{K}(t)+1)}{B(1,1,\ldots,1)}-\sum_{i=1}^{K}N_{i}(t)\log(\hat{p}_{i}(t))\leq
Z_{a,b}(t).$

Finally, the following lemma establishes the connection between the statistics
$\\{Z_{a,b}(t)\\}$ and our stopping condition (2).

######  Lemma 3.3.

At any time $t\in{\mathbb{N}}$,

$Z(t)=\max_{a\in\mathcal{K}}\min_{b\in\mathcal{K}\setminus\\{a\\}}Z_{a,b}(t)=Z_{\hat{a}_{t},\hat{b}_{t}}(t).$

######  Remark 3.4.

The statistic $Z_{a,b}(t),$ whose relation to the stopping condition of the
NI-ME algorithm is established in Lemma 3.3, is a modification of the
statistic defined in [20] (in the context of a different learning
task–detecting an ‘odd’ Markov arm). Specifically, [20] used a _conditional_
average likelihood (conditioned on hypothesis $a$ dominating hypothesis $b$)
in place of the _unconditional_ average likelihood we use (see (4)). While
this modification does not affect the soundness of the stopping criterion (as
we establish in Theorem 3.6 below), it enables a closed form, numerically
tractable characterization of $Z_{a,b}(t)$ (see Lemma 3.2).

######  Remark 3.5.

It is also instructive to connect the statistic $Z_{a,b}(t)$ to the one used
in the celebrated Track & Stop algorithm (see [15]) for the MAB problem. The
corresponding statistic in [15] is the logarithm of the ratio of the maximum
likelihood over instances where hypothesis $a$ dominates hypothesis $b$, to
the maximum likelihood over instances where hypothesis $b$ dominates
hypothesis $a.$ In effect, we replace the former maximum likelihood with an
_average_ likelihood over a suitably chosen ‘fake’ prior on the space of
instances (note that we are _not_ considering a Bayesian setting where the
instance is assumed to be drawn from this prior). This modification obviates
the need for a certain Krichevsky-Trofimov (KT) bound in the soundness
argument (see the proof of Theorem 10 in [15]), resulting in a tighter
stopping threshold $\beta.$

###  3.3 Correctness and asymptotic optimality of NI-ME

We now present performance guarantees on the NI-ME algorithm. First, we
establish that the algorithm is sound.

######  Theorem 3.6.

Let $\delta\in(0,1).$ Under the identityless sampling model, the NI-ME
algorithm (see Algorithm 1) is $\delta$-PC.

The proof of Theorem 3.6, which uses arguments similar to those in [15, 20],
is presented in A. Next, we establish that the NI-ME algorithm is
asymptotically optimal as $\delta\downarrow 0.$

######  Theorem 3.7.

Given $\delta\in(0,1),$ under the identityless sampling model, the stopping
time $\tau_{\delta}$ (see (3)) for the NI-ME algorithm (see Algorithm 1)
satisfies ${\mathbb{P}}(\tau_{\delta}<\infty)=1.$ Moreover,

$\displaystyle{\mathbb{P}}\left(\limsup_{\delta\to
0}\frac{\tau_{\delta}}{\log(1/\delta)}\leq(g^{*}(\boldsymbol{p}))^{-1}\right)=1,$
(5)

and

$\displaystyle\lim\sup_{\delta\to
0}\frac{{\mathbb{E}}_{[}\tau_{\delta}]}{\log(\frac{1}{\delta})}\leq(g^{*}(\boldsymbol{p}))^{-1}.$
(6)

where
$g^{*}(\boldsymbol{p})=(p_{1}+p_{2})kl\left(\frac{p_{1}}{p_{1}+p_{2}},\frac{1}{2}\right)$.

In light of Lemma 3.1, Theorem 3.7 establishes that NI-ME has an expected
stopping that (multiplicatively) matches the information theoretic lower bound
as $\delta\downarrow 0.$ Moreover, the same scaling is also established in an
almost sure sense. These results are structurally analogous to the best
optimality guarantees that are available in the MAB setting. The proof of
Theorem 3.7, which also uses arguments similar to those in [15, 20], is
presented in A.

###  3.4 A one-versus-one variant of NI-ME

While the NI-ME algorithm is asymptotically optimal as $\delta\downarrow 0,$
we now present a variant of this algorithm that performs even better for
moderate choices of $\delta.$ Specifically, this variant employs pairwise
comparisons between communities (each such pairwise comparison being based
only on the samples generated from those communities).

Formally, define the ‘pairwise’ statistic

$\tilde{Z}_{a,b}(t):=\log(B(N_{a}(t)+1,N_{b}(t)+1))-(N_{a}(t)+N_{b}(t))\log\left(\frac{1}{2}\right).$

Note that $\tilde{Z}_{a,b}(t)$ is simply what $Z_{a,b}(t)$ (as defined in (4))
would be in a hypothetical instance consisting of only the two communities $a$
and $b$ (with observations from other communities being disregarded).

The proposed variant of NI-ME, which we refer to as NI-ME-1v1, stops sampling
when

$\displaystyle\tilde{Z}(t):=\tilde{Z}_{\hat{a}_{t},\hat{b}_{t}}(t)>\beta(t,\delta),$
(7)

declaring $\hat{a}_{t}$ as the mode. It is easy to see that
$\tilde{Z}_{\hat{a}_{t},\hat{b}_{t}}(t)\leq\tilde{Z}_{\hat{a}_{t},b}(t)$ for
all $b\neq\hat{a}_{t},$ meaning the stopping criterion (7) is equivalent to
$\tilde{Z}_{\hat{a}_{t},b}(t)>\beta(t,\delta)$ for all $b\neq\hat{a}_{t}.$

######  Remark 3.8.

Remarkably, NI-ME-1v1 as defined above is identical to the PPR-1v1 algorithm
proposed in [19]. The latter algorithm is designed on the basis of very
distinct machinery–confidence intervals obtained via prior-posterior-ratios
(PPRs). This suggests an interesting connection between certain types of GLR
based stopping criteria and confidence intervals; formalizing and exploiting
this connection in the context of PAC learning is a promising avenue for
future work.

We now establish performance guarantees for NI-ME-1v1. The soundness of the
algorithm follows directly from the soundness of NI-ME.

######  Lemma 3.9.

Let $\delta\in(0,1).$ Under the identityless sampling model, the NI-ME-1v1
algorithm is $\delta$-PC.

###### Proof.

Let $t_{a,b}(k)$ denote the subsequence of observations pertaining only to
communities $a$ and $b.$ The key property we exploit here is that under our
sampling model, this subsequence can be treated as being generated by a
2-community instance consisting only of $d_{a}$ individuals from community $a$
and $d_{b}$ individuals from community $b.$ The fact that the NI-ME algorithm
is $\delta$-PC over such 2-community instances implies the soundness of NI-
ME-1v1 in the original $K$-community instance.

Let $\hat{a}$ denote the estimated mode by NI-ME-1v1.

$\displaystyle{\mathbb{P}}(\hat{a}\neq 1)$
$\displaystyle\leq{\mathbb{P}}(\exists b\in\mathcal{K}\setminus\\{1\\},\exists
t\in{\mathbb{N}},\forall
a\in\mathcal{K}\setminus\\{b\\}:\tilde{Z}_{b,a}(t)>\beta(t,\delta))$
$\displaystyle=\sum_{b\in\mathcal{K}\setminus\\{1\\}}{\mathbb{P}}\left(\exists
k\in{\mathbb{N}},\forall
a\in\mathcal{K}\setminus\\{b\\}:\tilde{Z}_{b,a}(t_{a,b}(k))>\log\left(\frac{K-1}{\delta}\right)\right)$
$\displaystyle\overset{(a)}{=}\sum_{b\in\mathcal{K}\setminus\\{1\\}}{\mathbb{P}}\left(\exists
k\in{\mathbb{N}},\forall
a\in\mathcal{K}\setminus\\{b\\}:Z^{(2)}_{b,a}(k)>\log\left(\frac{K-1}{\delta}\right)\right)$
$\displaystyle\overset{(b)}{\leq}\sum_{b\in\mathcal{K}\setminus\\{1\\}}\frac{\delta}{K-1}=\delta.$

In $(a),$ $Z^{(2)}_{a,b}(k)$ denotes the $Z_{a,b}(\cdot)$ statistic, computed
after $k$ observations, in a hypothetical 2-community instance consisting only
of $d_{a}$ individuals from community $a$ and $d_{b}$ individuals from
community $b.$ The inequality $(b)$ follows the soundness of NI-ME over such
two-community instances. (Note that the error threshold that is imposed on
these 2-community instances is $\nicefrac{{\delta}}{{K-1}}.$) ∎

Having established soundness, we now compare the stopping times under NI-ME
and NI-ME-1v1.

######  Lemma 3.10.

For all $t,$ $\tilde{Z}(t)\geq Z(t).$ As a consequence, on any sample path,
NI-ME-1v1 terminates no later than NI-ME.

###### Proof.

That $\tilde{Z}(t)\geq Z(t)$ follows, via a logarithmic transformation, from
the analysis in Appendix C.3.2 of [19]. ∎

In practice, we find that NI-ME-1v1 often terminates significantly faster than
NI-ME for moderate choices of $\delta;$ see Section 5. Lemma 3.10 also implies
that NI-ME-1v1 is asymptotically optimal, in light of the corresponding
guarantee for NI-ME.

######  Corollary 3.11.

The stopping time under the NI-ME-1v1 algorithm satisfies the asymptotic
optimality guarantees of Theorem 3.7.

##  4 Mode estimation with identity-based sampling

In this section, we turn our attention to the identity-based sampling model,
which is the main focus of this paper. Under this sampling model, the
observation process is Markovian (not i.i.d.), which makes the design of a
sound stopping criterion both methodologically and computationally
challenging. Via a novel relaxation of a GLR statistic analogous to that used
under the the identityless sampling model, we derive a stopping statistic
which provides a trade-off between sampling efficiency and computational
efficiency. The corresponding family of algorithms is proved to be $\delta$-PC
and also asymptotically optimal as $\delta\downarrow 0.$

We begin by establishing the following information theoretic lower bound on
the expected stopping time of any $\delta$-PC algorithm under the identity-
based sampling model.

######  Lemma 4.1.

Under the identity-based sampling model, given $\delta\in(0,1)$, the expected
stopping time ${\mathbb{E}}[\tau_{\delta}]$ of any $\delta$-PC algorithm
satisfies

${\mathbb{E}}[\tau_{\delta}]\geq\frac{\log\left(\frac{1}{2.4\delta}\right)}{\log\left(\frac{N-d_{2}+d_{1}+1}{N}\right)}.$

It is instructive to compare the above lower bound to the one for identityless
sampling in Lemma 3.1.

######  Lemma 4.2.

It holds that

$\log\left(\frac{N-d_{2}+d_{1}+1}{N}\right)>\log\left(\frac{N-d_{2}+d_{1}}{N}\right)>(p_{1}+p_{2})\
kl\left(\frac{p_{1}}{p_{1}+p_{2}},\frac{1}{2}\right).$

Consequently, for $\delta$-PC algorithms, the lower bound on the expected
stopping time under the identityless sampling model (see Lemma 3.1) is greater
than that under the identity-based sampling model (see Lemma 4.1). Moreover,
the ratio of former to the latter can be arbitrarily large, as the following
inequality shows:

$\displaystyle\frac{\log\left(\frac{N-d_{2}+d_{1}+1}{N}\right)}{(p_{1}+p_{2})\
kl\left(\frac{p_{1}}{p_{1}+p_{2}},\frac{1}{2}\right)}>\frac{\log\left(\frac{N-d_{2}+d_{1}}{N}\right)}{(p_{1}+p_{2})\
kl\left(\frac{p_{1}}{p_{1}+p_{2}},\frac{1}{2}\right)}>\frac{(p_{1}+p_{2})\log(2)}{(p_{1}-p_{2})}$
(8)

The above lemma highlights that _identity information can significantly
enhance the sampling efficiency of community mode estimation_. From (8), it is
easy to check that if $p_{2}$ is close to $p_{1}$, i.e., the second largest
community is only slightly smaller than the largest community, the lower bound
on the expected stopping time in the identity-based case is much smaller
(multiplicatively) than the lower bound in the identityless case. In other
words, for _challenging_ instances, identity information can significantly
speed up the task of community mode estimation. Some intuition for the above
comes from the analysis of the fixed budget variant of the community mode
estimation problem (see [18]). In particular, for any fixed $t,$ it was shown
in [18] that

$\displaystyle\mathbb{P}\left(\hat{a}_{t}\neq 1\right)$ $\displaystyle\leq
c_{1}\
\mathrm{exp}\left(-t\log\left(\frac{1}{1-(\sqrt{p_{1}}-\sqrt{p_{2}})^{2}}\right)\right),$
$\displaystyle\mathbb{P}\left(\tilde{a}_{t}\neq 1\right)$ $\displaystyle\leq
c_{2}\ \mathrm{exp}\left(-t\log\left(\frac{1}{1-(p_{1}-p_{2})}\right)\right).$

Here, $c_{1}$ and $c_{2}$ are instance dependent constants. Recall that
$\hat{a}_{t}$ is the empirical mode under the identityless setting (the
community with the greatest number of samples). Finally, $\tilde{a}_{t}$
denotes the the community with the greatest number of _distinct_ samples; it
may be interpreted as the empirical mode under the identity-based setting.
(Lower bounds that match the above decay rates are also established in [18].)
It is easy to see that the exponential decay rates above satisfy

$\log\left(\frac{1}{1-(\sqrt{p_{1}}-\sqrt{p_{2}})^{2}}\right)<\log\left(\frac{1}{1-(p_{1}-p_{2})}\right).$

This means that for large $t,$ it is more likely that the empirical mode
disagress with the true mode under the identityless setting as compared to the
identity-based setting. This provides intuition for why identity information
is useful in the first place. Moreover, under challenging instances, denoting
$p_{1}-p_{2}=\epsilon$ for small $\epsilon>0,$ the decay rate in the identity
based setting is approximately $\log(1+\epsilon)\approx\epsilon$ whereas the
decay rate in the identityless setting is $o(\epsilon).$ This suggests that
the time required to make the probability of error $\leq\delta$ is
approximately $\frac{\log(1/\delta)}{\epsilon}$ in the identity-based setting,
and approximately $\frac{\log(1/\delta)}{o(\epsilon)}$ in the identityless
setting; this in turn suggests that the boost provided by identity information
is particularly strong under challenging instances.

While Lemma 4.2 compares lower bounds on the expected sample complexity, note
that Theorems 3.7 and 4.6 also demonstrate their asymptotic achievability as
$\delta\to 0$. The proofs of Lemmas 4.1 and 4.2 are given in B. In the
remainder of this section, we develop and analyse a family of algorithms that
seek to match the lower bound in Lemma 4.1 as $\delta\downarrow 0.$

###  4.1 Algorithms

Recall that under the identity-based sampling model, the observation recorded
at time $t$ is $(x_{t},\sigma_{t}),$ where $x_{t}$ denotes the community label
of the sampled individual, and $\sigma_{t}$ is an indicator of whether this
individual is being seen for the first time. Let $S_{j}(t)$ denote the number
of distinct individuals from community $j$ sampled till time $t$. Note that
the vector $S(t)=(S_{1}(t),S_{2}(t),\ldots,S_{K}(t))$ is a function of the
observations $(\boldsymbol{x}^{t},\boldsymbol{\sigma}^{t})$ recorded until
time $t.$

Definition of the stopping statistic: The family of proposed stopping rules is
parameterized by a probability distribution $\mathcal{D}$ over
$\mathbb{N}^{K},$ which is defined as follows. Let $\theta(\cdot)$ denote a
probability mass function supported on $\mathbb{N},$ i.e., it satisfies
$\theta(i)>0\ \forall\ i\in\mathbb{N}$ and $\sum_{i\in\mathbb{N}}\theta(i)=1.$
Then for $\boldsymbol{d}^{\prime}\in\mathbb{N}^{K},$ let

${\mathbb{P}}_{\mathcal{D}}\left(\boldsymbol{d}^{\prime}\right):=\prod_{i=1}^{K}\theta(d^{\prime}_{j})$
(9)

denote a prior distribution on the community sizes. Let $\mathcal{K}^{(t)}$
denote the set of communities that have been observed until time $t$, i.e.,
$\mathcal{K}^{(t)}:=\\{j\in\mathcal{K}\colon S_{j}(t)>0\\},$ and let
$K^{(t)}:=|\mathcal{K}^{(t)}|.$ Finally, for $\alpha\in\mathbb{N},$ let

$\mathcal{S}_{\alpha}(t):=\\{\boldsymbol{d}^{\prime}\in\mathbb{N}^{K}\colon
S_{j}(t)\leq d^{\prime}_{j}\leq\alpha S_{j}(t)\ \forall\ j\\}.$

Let $\tilde{a}_{t}:=\operatorname*{arg\,max}_{j\in\mathcal{K}}S_{j}(t)$ denote
the community that has produced the largest number of distinct individuals and
let
$\tilde{b}_{t}:=\operatorname*{arg\,max}_{j\in\mathcal{K}\setminus\\{\tilde{a}_{t}\\}}S_{j}(t)$
denote the community with the second largest number of distinct individuals.
The identity-based stopping statistic is defined once
$t>\sum_{j\in\mathcal{K}}S_{j}(t)+K^{(t)}$; this means that the number of
‘collisions’ (i.e., instances where the sampled individual had been seen
before) exceeds the number of communities observed. Under this condition, we
define the statistic

$\displaystyle Y(t):=$
$\displaystyle\log\left(\sum_{\boldsymbol{d}^{\prime}\in\mathcal{S}_{\alpha}(t)}\frac{\prod_{j=1}^{K}\prod_{l=0}^{S_{j}(t)-1}(d^{\prime}_{j}-l){\mathbb{P}}_{\boldsymbol{d}^{\prime}\sim\mathcal{D}}(\boldsymbol{d}^{\prime})}{(\sum_{i=1}^{K}d^{\prime}_{i})^{t}}\right)$
$\displaystyle\qquad\qquad\qquad\qquad\quad-\sum_{j\in\mathcal{K}^{(t)}}\int_{-1}^{S_{j}(t)}\log(d^{\tilde{a}_{t},\tilde{b}_{t}}_{j}(\gamma_{0})-v)dv+t\log\left(\sum_{i=1}^{K}d^{\tilde{a}_{t},\tilde{b}_{t}}_{i}(\gamma_{0})\right),$
(10)

where

$\displaystyle
d^{\tilde{a}_{t},\tilde{b}_{t}}_{\tilde{a}_{t}}(\gamma_{0}):=d^{\tilde{a}_{t},\tilde{b}_{t}}_{\tilde{b}_{t}}(\gamma_{0})=\frac{S_{\tilde{a}_{t}}(t)+S_{\tilde{b}_{t}}(t)+2\gamma_{0}^{2}+r(\gamma_{0})}{2(1-\gamma_{0}^{2})},\quad
d^{\tilde{a}_{t},\tilde{b}_{t}}_{j}(\gamma_{0}):=\frac{S_{j}(t)+\gamma_{0}}{1-\gamma_{0}}\text{
for }j\neq\tilde{a}_{t},\tilde{b}_{t}.$

Here, $\gamma_{0}$ is the unique zero in $(0,1)$ of

$\displaystyle g(\gamma)$ $\displaystyle:=g_{1}(\gamma)-t,$ (11)

$\displaystyle\text{ where
}g_{1}(\gamma):=\log\left(\frac{1}{\gamma}\right)\Bigg{(}\frac{\sum_{j\in\mathcal{K}^{(t)}\setminus\\{\tilde{a}_{t},\tilde{b}_{t}\\}}S_{j}(t)+\gamma(K^{(t)}-2)}{1-\gamma}+\frac{S_{\tilde{a}_{t}}(t)+S_{\tilde{b}_{t}}(t)+2\gamma^{2}+r(\gamma)}{(1-\gamma^{2})}\Bigg{)}$

and
$r(\gamma):=\sqrt{(S_{\tilde{a}_{t}}(t)-S_{\tilde{b}_{t}}(t))^{2}+4\gamma^{2}(1+S_{\tilde{a}_{t}}(t)+S_{\tilde{b}_{t}}(t)+S_{\tilde{a}_{t}}(t)S_{\tilde{b}_{t}}(t))}.$

Stopping rule: The family of algorithms we propose is parameterized by the
choice of $\alpha$ and the distribution $\theta$ on $\mathbb{N}.$ An instance
of this family, referred to as the _Identity-based Community Mode Estimation_
algorithm, or IB-CME$(\alpha,\theta),$ operates as follows.

  * 1.

At time $t,$ if the stopping condition of NI-ME holds for $\beta(t,\delta/2)$,
then IB-CME$(\alpha,\theta)$ also stops sampling and reports the output of NI-
ME as the mode estimate.777The stopping condition of NI-ME can be replaced by
that of NI-ME-1v1, or indeed, by that of any algorithm that is $\delta$-PC in
the identityless model. This choice does not influence the performance
guarantees of IB-CME$(\alpha,\theta)$.

  * 2.

If $t>\sum_{j\in\mathcal{K}}S_{j}(t)+K^{(t)},$ compute $Y(t)$. IB-
CME$(\alpha,\theta)$ stops sampling if

$Y(t)>\beta(t,\delta/2)=\log\left(\frac{2(K-1)}{\delta}\right),$ (12)

reporting $\tilde{a}_{t}$ as the estimated mode.

This procedure is formalized as Algorithm 2.

Algorithm 2 Community mode estimation with identity-based sampling (IB-CME)

$t\leftarrow 1$

loop

Obtain $x_{t}$, $\sigma_{t}$

$\hat{a}_{t}\leftarrow\arg\max_{i\in\mathcal{K}}\hat{p}_{i}(t)$,
$\hat{b}_{t}\leftarrow\arg\max_{i\in\mathcal{K}\setminus\\{\hat{a}_{t}\\}}\hat{p}_{i}(t)$

$Z(t)\leftarrow\log\frac{B(N_{1}(t)+1,N_{2}(t)+1,\ldots,N_{K}(t)+1)}{B(1,1,\ldots,1)}$

$\hskip
31.2982pt-\sum_{i\in\mathcal{K}\setminus\\{\hat{a}_{t},\hat{b}_{t}\\}}N_{i}(t)\log(\hat{p}_{i}(t))$

$\hskip
36.98866pt-(N_{\hat{a}_{t}}(t)+N_{\hat{b}_{t}}(t))\log\left(\frac{\hat{p}_{\hat{a}_{t}}(t)+\hat{p}_{\hat{b}_{t}}(t)}{2}\right)$

$\beta(t,\delta/2)\leftarrow\log\left(\frac{2(K-1)}{\delta}\right)$

if $Z(t)>\beta(t,\delta/2)$ then

stopping time $\tau_{\delta}=t$ and mode $\hat{a}_{\tau_{\delta}}=\hat{a}_{t}$

Exit loop

else

if $t>\sum_{j\in\mathcal{K}}S_{j}(t)+K^{(t)}$ then

$\tilde{a}_{t}\leftarrow\operatorname*{arg\,max}_{j\in\mathcal{K}}S_{j}(t)$

$\tilde{b}_{t}\leftarrow\arg\max_{j\in\mathcal{K}\setminus\\{\tilde{a}_{t}\\}}S_{j}(t)$

$Y(t)\leftarrow\log\left(\sum_{\boldsymbol{d}^{\prime}\in\mathcal{S}_{\alpha}(t)}\frac{\prod_{j=1}^{K}\prod_{l=0}^{S_{j}(t)-1}(d^{\prime}_{j}-l){\mathbb{P}}_{\boldsymbol{d}^{\prime}\sim\mathcal{D}}(\boldsymbol{d}^{\prime})}{(\sum_{i=1}^{K}d^{\prime}_{i})^{t}}\right)$

$\qquad\qquad\qquad-\sum_{j\in\mathcal{K}^{(t)}}\int_{-1}^{S_{j}(t)}\log(d^{\tilde{a}_{t},\tilde{b}_{t}}_{j}(\gamma_{0})-v)dv+t\log\left(\sum_{i=1}^{K}d^{\tilde{a}_{t},\tilde{b}_{t}}_{i}(\gamma_{0})\right)$

if $Y(t)>\beta(t,\delta/2)$ then

stopping time $\tau_{\delta}=t$ and mode
$\hat{a}_{\tau_{\delta}}=\tilde{a}_{t}$

Exit loop

else

$t\leftarrow t+1$

end if

else

$t\leftarrow t+1$

end if

end if

end loop

###  4.2 Stopping rule interpretation

We now provide an interpretation for the stopping condition (12). We begin by
characterizing the likelihood function under the identity-based sampling
model. At time $t+1$, given the observations recorded till time $t$, the
probability of picking a new sample from community $j\in\mathcal{K}$ is

$\displaystyle{\mathbb{P}}(x_{t+1}=j,\sigma_{t+1}=1|\boldsymbol{x}^{t},\boldsymbol{\sigma}^{t})=\frac{d_{j}-S_{j}(t)}{\sum_{i=1}^{K}d_{i}}\quad\text{and}\quad{\mathbb{P}}(x_{t+1}=j,\sigma_{t+1}=0|\boldsymbol{x}^{t},\boldsymbol{\sigma}^{t})=\frac{S_{j}(t)}{\sum_{i=1}^{K}d_{i}}$

is the probability of picking a sample already seen before. Thus, the
likelihood of the observations till time $t$ is given by

$\displaystyle\mathcal{L}_{\boldsymbol{d}}(\boldsymbol{x}^{t},\boldsymbol{\sigma}^{t})$
$\displaystyle=\underbrace{\prod_{j=1}^{K}\prod_{l=0}^{S_{j}(t)-1}\frac{d_{j}-l}{(\sum_{i=1}^{K}d_{i})}}_{L_{new}}\underbrace{\prod_{\tau=1}^{t}\left(\frac{S_{x_{\tau}}(\tau-1)}{\sum_{i=1}^{K}d_{i}}\right)^{(1-\sigma_{\tau})}}_{L_{rep}}$
$\displaystyle=\frac{\prod_{j=1}^{K}\prod_{l=0}^{S_{j}(t)-1}(d_{j}-l)\prod_{\tau=1}^{t}\left(S_{x_{\tau}}(\tau-1)\right)^{(1-\sigma_{\tau})}}{(\sum_{i=1}^{K}d_{i})^{t}}.$
(13)

where $\boldsymbol{d}=(d_{1},d_{2},\ldots d_{K})$. The factor $L_{new}$ above
arises from the new samples seen until time $t,$ whereas the factor $L_{rep}$
arises due to the repeated samples seen till time $t.$

The statistic $Y_{a,b}(t)$ used in the proposed family of algorithms is a
relaxation of the following statistic:

$\displaystyle
W_{a,b}(t)=\log\frac{\mathbb{E}_{\boldsymbol{d}^{\prime}\sim\mathcal{D}}\left[\mathcal{L}_{\boldsymbol{d}^{\prime}}(\boldsymbol{x}^{t},\boldsymbol{\sigma}^{t})\right]}{\sup_{\boldsymbol{d}^{\prime}\in\mathbb{N}^{K}\colon
d^{\prime}_{a}\leq
d^{\prime}_{b}}\mathcal{L}_{\boldsymbol{d}^{\prime}}(\boldsymbol{x}^{t},\boldsymbol{\sigma}^{t})}.$
(14)

Note that the numerator in (14) (inside the logarithm) is the average
likelihood of the observation sequence with respect to the prior distribution
$\mathcal{D}$ over problem instances $\boldsymbol{d}^{\prime}$. On the other
hand, the denominator is the supremum of the likelihood over problem instances
$\boldsymbol{d}^{\prime}$ that support the alternative hypothesis
$d^{\prime}_{a}\leq d^{\prime}_{b}.$ (Indeed, $W_{a,b}(t)$ is the natural
generalization of $Z_{a,b}(t),$ defined in Section 3, to the identity-based
sampling model.) It can be proved that using the statistic $W_{a,b}(t)$ in
place of $Y_{a,b}(t)$ in Algorithm 2 results in a family of $\delta$-PC,
asymptotically optimal algorithms (see the proofs of Theorems 4.5, 4.6).

However, using $W_{a,b}(t)$ directly in algorithms is challenging from a
computational standpoint. In particular, computing the expectation in the
numerator in (14) involves an infinite sum (over $\mathbb{N}^{K}$). More
crucially, computing the denominator in (14) involves a discrete optimization
over an infinite subset of $\mathbb{N}^{K}.$ To resolve these issues, we
design a computationally tractable lower bound $Y_{a,b}(t)$ of the statistic
$W_{a,b}(t),$ which preserves both soundness and asymptotic optimality of
stopping rule. We describe this design next, in three steps.

Step 1: We first note that $W_{a,b}(t)$ can be expressed as follows.

$\displaystyle W_{a,b}(t)$
$\displaystyle=\log\left(\sum_{\boldsymbol{d}^{\prime}\in\mathbb{N}^{K}}\frac{\prod_{j=1}^{K}\prod_{l=0}^{S_{j}(t)-1}(d^{\prime}_{j}-l){\mathbb{P}}_{\boldsymbol{d}^{\prime}\sim\mathcal{D}}(\boldsymbol{d}^{\prime})}{(\sum_{i=1}^{K}d^{\prime}_{i})^{t}}\right)$
$\displaystyle\qquad\qquad-\sup_{\boldsymbol{d}^{\prime}\in\mathbb{N}^{K}\colon
d^{\prime}_{a}\leq
d^{\prime}_{b}}\left\\{\sum_{j=1}^{K}\sum_{l=0}^{S_{j}(t)-1}\log(d^{\prime}_{j}-l)-t\log\left(\sum_{i=1}^{K}d^{\prime}_{i}\right)\right\\}$
$\displaystyle=:T_{1}-T_{2}.$

In the above representation, the factors in the likelihood that do not depend
on $\boldsymbol{d}^{\prime}$ have been cancelled across the numerator and
denominator of (14).

Step 2: The term $T_{1}$ can be lower bounded by restricting the summation to
a finite set that includes $\boldsymbol{d}^{\prime}=S(t)$ as follows:

$T_{1}\geq\log\left(\sum_{\boldsymbol{d}^{\prime}\in\mathcal{S}_{\alpha}(t)}\frac{\prod_{j=1}^{K}\prod_{l=0}^{S_{j}(t)-1}(d^{\prime}_{j}-l){\mathbb{P}}_{\boldsymbol{d}^{\prime}\sim\mathcal{D}}(\boldsymbol{d}^{\prime})}{(\sum_{i=1}^{K}d^{\prime}_{i})^{t}}\right)$
(15)

Note that the parameter $\alpha\in\mathbb{N}$ controls the size of the set
over which the above summation is performed. On one extreme, setting
$\alpha=1$ restricts the summation to a single term corresponding to
$\boldsymbol{d}^{\prime}=S(t).$ On the other extreme, as
$\alpha\rightarrow\infty,$ we recover the term $T_{1}$ exactly. Intermediate
values of $\alpha$ provide a trade-off between computational complexity (per
sampling epoch) and sample complexity.

Step 3: $T_{2}$ is upper bounded by (i) replacing
$\sum_{l=0}^{S_{j}(t)-1}\log(d^{\prime}_{j}-l)$ by the integral relaxation
$\int_{-1}^{S_{j}(t)}\log(d^{\prime}_{j}-v)dv,$ and (ii) performing the
supremum over $\mathbb{R}_{+}^{K}$ rather than $\mathbb{N}^{K}.$ Formally,

$\displaystyle
T_{2}\leq\sup_{\boldsymbol{d}^{\prime}\in\mathbb{R}_{+}^{K}\colon
d^{\prime}_{a}\leq
d^{\prime}_{b}}\underbrace{\left\\{\sum_{j\in\mathcal{K}^{(t)}}\int_{-1}^{S_{j}(t)}\log(d^{\prime}_{j}-v)dv-t\log\left(\sum_{i=1}^{K}d^{\prime}_{i}\right)\right\\}}_{f_{t}(\boldsymbol{d}^{\prime})}.$
(16)

Remarkably, the above continuous optimization of the function
$f_{t}(\boldsymbol{d}^{\prime})$ can be reduced to a one-dimensional
optimization.

######  Lemma 4.3.

When communities $a,b\in\mathcal{K}$ satisfy $S_{a}(t)\geq S_{b}(t)$, for
$t>\sum_{j\in\mathcal{K}}S_{j}(t)+K^{(t)}$, the function
$f_{t}(\boldsymbol{d}^{\prime})$ attains its supremum over
$\\{\boldsymbol{d}^{\prime}\in\mathbb{R}_{+}^{K}\colon d^{\prime}_{a}\leq
d^{\prime}_{b}\\}$ at

$\displaystyle
d^{a,b}_{a}(\gamma_{0})=d^{a,b}_{b}(\gamma_{0})=\frac{S_{a}(t)+S_{b}(t)+2\gamma_{0}^{2}+r(\gamma_{0})}{2(1-\gamma_{0}^{2})},\quad
d^{a,b}_{j}(\gamma_{0})=\frac{S_{j}(t)+\gamma_{0}}{1-\gamma_{0}}\ \forall
j\neq a,b,$

where $\gamma_{0}$ is the unique zero in $(0,1)$ of
$g(\gamma)=\log\left(\frac{1}{\gamma}\right)\Bigg{(}\frac{\sum_{j\in\mathcal{K}^{(t)}\setminus\\{a,b\\}}S_{j}(t)+\gamma(K^{(t)}-2)}{1-\gamma}+\frac{S_{a}(t)+S_{b}(t)+2\gamma^{2}+r(\gamma)}{(1-\gamma^{2})}\Bigg{)}-t$.

Lemma 4.3 enables a tractable computation of the upper bound in (16). It thus
follows from (15), (16), and Lemma 4.3 that

$\displaystyle W_{a,b}(t)\geq Y_{a,b}(t):=$
$\displaystyle\log\left(\sum_{\boldsymbol{d}^{\prime}\in\mathcal{S}_{\alpha}(t)}\frac{\prod_{j=1}^{K}\prod_{l=0}^{S_{j}(t)-1}(d^{\prime}_{j}-l){\mathbb{P}}_{\boldsymbol{d}^{\prime}\sim\mathcal{D}}(\boldsymbol{d}^{\prime})}{(\sum_{i=1}^{K}d^{\prime}_{i})^{t}}\right)$
$\displaystyle\qquad\qquad\qquad\qquad\quad-\sum_{j\in\mathcal{K}^{t}}\int_{-1}^{S_{j}(t)}\log(d^{a,b}_{j}(\gamma_{0})-v)dv+t\log\left(\sum_{i=1}^{K}d^{a,b}_{i}(\gamma_{0})\right)$
(17)

when $S_{a}(t)\geq S_{b}(t)$ for $t>\sum_{j\in\mathcal{K}}S_{j}(t)+K^{(t)}.$
Crucially, unlike the statistic $W_{a,b}(t),$ its relaxation $Y_{a,b}(t)$ is
computationally tractable. Also, note that when $S_{a}(t)\geq S_{b}(t)$ for
$t>\sum_{j\in\mathcal{K}}S_{j}(t)+K^{(t)},$ from (63),

$\displaystyle Y_{b,a}(t)=$
$\displaystyle\log\left(\sum_{\boldsymbol{d}^{\prime}\in\mathcal{S}_{\alpha}(t)}\frac{\prod_{j=1}^{K}\prod_{l=0}^{S_{j}(t)-1}(d^{\prime}_{j}-l){\mathbb{P}}_{\boldsymbol{d}^{\prime}\sim\mathcal{D}}(\boldsymbol{d}^{\prime})}{(\sum_{i=1}^{K}d^{\prime}_{i})^{t}}\right)-\sup_{\boldsymbol{d}^{\prime}\in\mathbb{R}_{+}^{K}}f_{t}(\boldsymbol{d}^{\prime})\leq
Y_{a,b}(t).$

The following lemma establishes the connection between $Y(t)$ and
$Y_{a,b}(t)$.

######  Lemma 4.4.

At any time $t>\sum_{j\in\mathcal{K}}S_{j}(t)+K^{(t)},$

$\displaystyle
Y(t)=\max_{a\in\mathcal{K}}\min_{b\in\mathcal{K}\setminus\\{a\\}}Y_{a,b}(t)=Y_{\tilde{a}_{t},\tilde{b}_{t}}(t).$

As we show next, the proposed algorithms based on this relaxation are
$\delta$-PC and asympotically optimal as $\delta\downarrow 0.$

###  4.3 Correctness and asymptotic optimality

We now establish that the proposed family of algorithms enjoys guarantees
analogous to those established before under identityless sampling.

######  Theorem 4.5.

Under the identity-based sampling model, given $\delta\in(0,1),$ IB-
CME$(\alpha,\theta)$ is $\delta$-PC.

######  Theorem 4.6.

Under the identity-based sampling model, given $\delta\in(0,1),$ the stopping
time $\tau_{\delta}$ for IB-CME$(\alpha,\theta)$ satisfies
${\mathbb{P}}(\tau_{\delta}<\infty)=1$ and

$\displaystyle{\mathbb{P}}\left(\limsup_{\delta\to
0}\frac{\tau_{\delta}}{\log(1/\delta)}\leq\left(\log\left(\frac{N-d_{2}+d_{1}}{N}\right)\right)^{-1}\right)=1.$
(18)

Moreover,

$\displaystyle\limsup_{\delta\to
0}\frac{{\mathbb{E}}[\tau_{\delta}]}{\log\left(\frac{1}{\delta}\right)}\leq\frac{1}{\log\left(\frac{N-d_{2}+d_{1}}{N}\right)}.$
(19)

The proofs of Theorem 4.5 and Theorem 4.6, which follow via arguments
analogous to those used to prove the corresponding statements under
identityless sampling, are presented in B.

We conclude with the following remarks.

  * 1.

Comparing Theorem 4.6 with Lemma 4.1, we see that the lower bound (on expected
stopping time) nearly matches the (almost sure) asymptotic upper bound; the
term $(d_{1}-d_{2}+1)$ in the former is replaced by $(d_{1}-d_{2})$ in the
latter. The same goes for the upper bound on expected sample complexity. This
establishes that our family of algorithms is asymptotic optimal in the limit
$\delta\downarrow 0;$ the small discrepancy between the upper and lower bounds
stems from the inherent discreteness of the space of problem instances.

  * 2.

The asymptotic optimality guarantee of Theorem 4.6 demonstrates that the
proposed algorithms do indeed optimally exploit identity information for
efficient community mode estimation. Interestingly, these algorithms are based
on simply keeping track of the number of distinct individuals seen from each
community.

  * 3.

The soundness and asymptotic optimality guarantees of the proposed family of
algorithms do not depend on the choices of the parameters $\theta$ (a
distribution suppored on $\mathbb{N}$) and $\alpha$ (a natural number).
Intuitively, soundness follows because the statistic we employ is a lower
bound of another sound statistic (derived using $W_{a,b}(\cdot)$). Asymptotic
optimality is a consequence of the (eventual) concentration of the likelihood
function around the actual instance parameters $d.$

  * 4.

That said, the choices of the parameters $\theta$ and $\alpha$ do influence
algorithm performance for moderate (and practical) values of $\delta.$
Interestingly, we find in our numerical case studies (see Section 5) that
setting $\alpha=1$ minimizes the computational complexity per sampling epoch,
without significantly affecting the sampling complexity. On the other hand,
choosing the distribution $\theta$ to have a _heavier tail_ results in a
significant reduction in the average stopping time.

  * 5.

Finally, we note that it is also possible to design a ‘1v1’ variant of IB-CME
using the same design principle as NI-ME-1v1. While it is easy to show that
such a 1v1 variant is sound, it turns out that it does not inherit the
asymptotic optimality properties of IB-CME. Mathematically, this is a
consquence of the specific form of the information theoretic lower bound under
the identity-based sampling model. Intuitively, the 1v1 variant is less
effective in the identity-based setting because, unlike in the identityless
case, discriminating between communities $a$ and $b$ is aided by observations
(specifically, collisions) from a third community $c.$

##  5 Experimental Results

In this section, we validate our theoretical results via numerical experiments
using both synthetic data as well as data gathered from real-world datasets.
We compare the performance of NI-ME (identityless setting), NI-ME-1v1 (which
is identical to PPR-1v1 proposed in Jain et al. [19]), and IB-CME (identity-
based setting). Recall that in the IB-CME algorithm, until
$t>\sum_{j\in\mathcal{K}}S_{j}(t)+K^{(t)}$ (i.e., until a certain number of
repeated samples occur), IB-CME relies on NI-ME to estimate the mode. We also
consider another variant of IB-CME that piggybacks on NI-ME-1v1 instead of NI-
ME.

We set the target error probability $\delta=0.1$ and average our results over
$100$ runs, where in each run we randomly sample from the underlying instance
and record the stopping times for all the algorithms. We should mention that
the mode is correctly identified in almost all runs of our experiments (in
other words, all algorithms are over-conservative from the standpoint of
error); we therefore focus primarily on the average stopping time.

For NI-ME our prior distribution $\mathcal{P}$ is fixed to be the Dirichlet
distribution. But for IB-CME, we also evaluate the effect of the choice of
prior distribution $\mathcal{D}$ as well as the parameter $\alpha$ which
provides a trade-off between computational complexity (per sampling epoch) and
sample complexity. We consider two different prior distributions
$\mathcal{D}$, by letting the associated pmf $\theta$ (9) be the Geometric
distribution with parameters $q=0.1$ and $q=0.9$ respectively. We consider
$\alpha=1$ and $\alpha=3$, where the latter requires significantly more
computational effort.

Algorithm | Parameters | Average Stopping | time
---|---|---|---
|  | $\mathcal{I}_{1}$ | $\mathcal{I}_{2}$
IB-CME |  $\alpha=1$, Geometric prior with $q=0.1$ | 239.4 | 413.65
|  $\alpha=1$, Geometric prior with $q=0.9$ | 626.08 | 1536.1
IB-CME with NI-ME-1v1 |  $\alpha=1$, Geometric prior with $q=0.1$ | 209.15 | 396.49
NI-ME |  | 669.85 | 3968.5
NI-ME-1v1/PPR-1v1 |  | 275.9 | 1410.3
IB-CME |  $\delta=0.1$, $\alpha=3$, Geometric prior with $q=0.1$ | 235.85 | 412.6500
Table 1: Comparison of average stopping times for
$\mathcal{I}_{1}=[20,12,8,5,5]$ and $\mathcal{I}_{2}=[20,16,6,4,4]$.

We present a comparison of the performance of NI-ME, NI-ME-1v1/PPR-1v1, IB-
CME, and IB-CME with NI-ME-1v1 in Table 1 in terms of the average stopping
time. We consider two instances $\mathcal{I}_{1}=[20,12,8,5,5]$ and
$\mathcal{I}_{2}=[20,16,6,4,4]$, both with $50$ individuals and $5$
communities each. Note that $\mathcal{I}_{2}$ is a harder instance than
$\mathcal{I}_{1}$ since the two largest community sizes are closer. Comparing
the two identityless sampling algorithms, we find that NI-ME empirically
performs worse than NI-ME-1v1/PPR-1v1, as anticipated. The average stopping
time for both instances $\mathcal{I}_{1}$ and $\mathcal{I}_{2}$ is lowest for
IB-CME with NI-ME-1v1 which uses identity-based sampling, with $\alpha=1$ and
the Geometric prior with $q=0.1$. For the easier instance $\mathcal{I}_{1}$
the average stopping time for IB-CME, for the heavier-tailed prior (Geometric
prior with $q=0.1$) is comparable to the average stopping time of PPR-1v1.
Thus for the easier instance, the identity information does not seem to
provide a significant boost in mode estimation. However, for the harder
instance $\mathcal{I}_{2}$, we can see from Table 1 that IB-CME performs much
better than NI-ME-1v1/PPR-1v1 with the heavier-tailed prior. This shows that
identity information plays a vital role in reducing the stopping time as the
instance gets harder.

We also note that compared to a sharply decreasing prior distribution like the
Geometric prior with $q=0.9$, a prior distribution with heavier tail like the
Geometric prior with $q=0.1$, significantly reduces the average stopping time
of IB-CME. Also, we observe that increasing the value of $\alpha$ from $1$ to
$3$ does not seem to have a significant impact on the average stopping time.
We could not evaluate even larger values of $\alpha$ due to the sharp increase
in computational complexity.

We also compare the performance of the various schemes in the scenario where
the target error probability $\delta$ as well as the ratios of the community
sizes is fixed, but the overall population size $N$ is scaled by a factor of
$\omega$. We choose $\alpha=1$ and a Geometric prior with $q=0.1$ for IB-CME
and IB-CME with NI-ME-1v1. The results for various values of $\omega$ are
presented in Table 2. We find that for small to moderate values of $N$,
identity-based mode estimation algorithms IB-CME and IB-CME with NI-ME-1v1
perform better than the identityless sampling algorithms NI-ME-1v1 and NI-ME.
But as $N$ becomes large, the performance of both IB-CME with NI-ME-1v1 and
NI-ME-1v1 become comparable. Interestingly however, we should note that our
analytical results (see Lemma 4.2) imply that the multiplicative gap between
the _lower bounds_ in the identityless and identity-based settings holds even
when the population size $N$ is large. We are not entirely sure whether the
contrast between the lower bounds and empirical performance is due to (i) an
inefficiency of our algorithms, or (ii) due to a looseness in our lower
bounds. Unfortunately, our methodological machinery is designed for the
scaling where the instance (and therefore $N$) is fixed and $\delta\downarrow
0,$ and not for the scaling where $\delta$ is fixed and $N$ is scaled up.
Finally, it is also important to note that $N$ is assumed to be unknown to the
learner. So in principle, even the absence of collisions (which is likely when
$N$ is large) provides additional information to the learner in the identity-
based sampling model; thus it might be possible to design an algorithm that
exploits this information better (our algorithm admittedly does not).

Figure 1: Average stopping time $\tau_{\delta}$ v/s $\log(\delta)$ for
$\boldsymbol{d}=[20,16,6,4,4]$.

Finally, we present the effect of varying the target error probability
$\delta$ on the average stopping time of the various schemes in Figure 1. We
consider the instance $\mathcal{I}_{2}$, and choose $\alpha=1$ and a Geometric
prior with $q=0.1$ for IB-CME and IB-CME with NI-ME-1v1. As expected, the
sample complexity varies linearly with $\log(\delta)$.

Algorithm | IB-CME | IB-CME | NI-ME-1v1/PPR-1v1 | NI-ME
---|---|---|---|---
| with NI-ME-1v1 |  |  |
Average Stopping time for |  |  |  |
$\omega=1,N=50$ | 710.535 | 711 | 6353.5 | 19705
$\omega=5,N=250$ | 1911.7 | 2008.1 | 6480.3 | 19707
$\omega=10,N=500$ | 3170.1 | 3538.9 | 6260.7 | 19518
$\omega=15,N=750$ | 4475.4 | 5076.1 | 6550.8 | 19727
$\omega=20,N=1000$ | 5262.5 | 6590.5 | 6220.5 | 20559
$\omega=25,N=1250$ | 6019.8 | 8077.9 | 6582.7 | 19873
$\omega=30,N=1500$ | 6344.6 | 9593.5 | 6220.5 | 20559
$\omega=35,N=1750$ | 6885.6 | 10995 | 6550.8 | 19727
$\omega=40,N=2000$ | 7102.3 | 12367 | 6550.8 | 19727
Table 2: Comparison of average stopping times for $\mathcal{I}_{3}=\omega[20,18,6,3,3].$ Algorithm | IB-CME | IB-CME | NI-ME-1v1/PPR-1v1 | NI-ME
---|---|---|---|---
| with NI-ME-1v1 |  |  |
|  | Average Stopping time |  |
$\text{Dataset}-1$ | 1411.7 | 1492.7 | 2061.3 | 13284
$\text{Dataset}-2$ | 3081.5 | 3717.1 | 4430.9 | 28166
$\text{Dataset}-3$ | 554.52 | 3049.2 | 505.98 | 3344.2
Table 3: Comparison of average stopping times for real-world datasets.

We also evaluate the various schemes on instances derived from three real-
world datasets of different sizes. For each dataset, we choose $\alpha=1$ and
a Geometric prior with $q=0.1$ for IB-CME and IB-CME with NI-ME-1v1. The first
dataset lists food orders placed by customers on an online portal across $179$
restaurants belonging to $14$ different cuisines [3]. We refer to this dataset
as $\text{Dataset}-1$. Mapping this data to our framework, the restaurants
correspond to the individual entities and the corresponding cuisines
represents the communities. The underlying instance created this way is given
by $[41,16,3,14,31,29,5,5,11,7,2,3,9,3]$ and the goal is to estimate the
cuisine with largest number of restaurants by using random sampling.

Next we consider a dataset, referred to as $\text{Dataset}-2$ henceforth,
which contains a list of $500$ top cities in $12$ different regions of the
world with respect to their innovation index [2]. We are interested in finding
the region with most number of innovative cities. Here, cities correspond to
the individual entities whereas the region they belong to represent the
communities. The instance created from this dataset is given by
$[19,39,14,44,18,139,13,12,39,25,20,118]$. The aim is to determine the region
with maximum number of innovative cities by using random sampling. Finally, we
consider $\text{Dataset}-3$, which consists of $1000$ top rated IMDb movies
under $14$ diffent genre [1]. Here the movies are individual entities and
their genres are the communities. The instance created from the dataset is
given by $[172,72,82,88,155,107,289,2,2,3,11,12,1,4]$. The goal here is to
determine the most popular genre i.e. the genre with maximum number of movies
listed.

Note that the three datasets have increasing population sizes and while the
first two datasets have similar gaps between the top two community sizes, the
third dataset has a much larger gap indicating an easier problem instance. The
performance results for the various mode estimation algorithms when used over
the above three datasets are presented in Table 3. For $\text{Dataset}-1$ and
$\text{Dataset}-2$ we can see that IB-CME with NI-ME-1v1 algorithm has the
lowest average stopping time. The identity-based algorithms perform better
than the identityless sampling algorithms, which illustrates the significant
reduction in sample complexity that identity information can provide. The NI-
ME-1v1 algorithm performs better than the NI-ME algorithm as expected.
However, for $\text{Dataset}-3$ which represents the easier problem instance,
the performance of algorithm IB-CME with NI-ME-1v1 is comparable to NI-ME-1v1
algorithm with NI-ME-1v1 performing slightly better. The performance of the
IB-CME algorithm is only slightly better than the NI-ME algorithm, which is
likely due to the fact that for a larger population size $N$ the advantage
provided by identity information is reduced due to lack of collisions or
repeated samples.

##  6 Concluding remarks

In this paper, we considered the learning task of online community mode
estimation in a fixed confidence setting, focusing on the role of identity
information. Our analysis relies heavily on the existing GLR-based machinery
for establishing correctness and asymptotic optimality of PAC algorithms (most
notably, the methodology developed in [15, 20]). Our key novelty is:
(i) From a modeling standpoint, we highlight the value of _identity_
information in mode estimation.
(ii) We modify the GLR statistic proposed in [20] to design a tractable
algorithm for the identityless sampling model. A superior ‘1v1’ variant of
this algorithm is also designed, which turns out to be identical to the state
of the art algorithm for (identityless) mode estimation–PPR-1v1 (see [19]),
which was designed using a different design recipe.
(ii) We design a sound stopping condition under a _Markovian_ observation
sequence (arising under identity-based sampling), and further design a
computationally tractable relaxation of the stopping statistic that preserves
both soundness and asymptotic optimality (Lemma 4.3 is crucial to this
relaxation); indeed, that the discrete likelihood optimization over
$\mathbb{N}^{K}$ in (14) can be tractably relaxed is far from trivial.

## References

  * IMD [2020] Imdb movies dataset.  https://www.kaggle.com/datasets/harshitshankhdhar/imdb-dataset-of-top-1000-movies-and-tv-shows, 2020\.  Accessed: 2023-08-07.
  * 500 [2021] Innovation cities index 2021 : Global 500.  https://innovation-cities.com/innovation-cities-index-2021-global-500/25718/, 2021\.  Accessed: 2023-08-08.
  * NYC [2023] Nyc restaurants data - food ordering and delivery.  https://www.kaggle.com/datasets/ahsan81/food-ordering-and-delivery-app-dataset, 2023\.  Accessed: 2023-02-06.
  * Acharya et al. [2016] Jayadev Acharya, Alon Orlitsky, Ananda Theertha Suresh, and Himanshu Tyagi.  Estimating rényi entropy of discrete distributions.  _IEEE Transactions on Information Theory_ , 63(1):38–56, 2016.
  * Bressan et al. [2015] Marco Bressan, Enoch Peserico, and Luca Pretto.  Simple set cardinality estimation through random sampling.  _arXiv preprint arXiv:1512.07901_ , 2015.
  * Bubeck et al. [2013] Sébastien Bubeck, Damien Ernst, and Aurélien Garivier.  Optimal discovery with probabilistic expert advice: finite time analysis and macroscopic optimality.  _Journal of Machine Learning Research_ , 14:601–623, 2013\.
  * Budianu et al. [2006] C. Budianu, S. Ben-David, and L. Tong.  Estimation of the number of operating sensors in large-scale sensor networks with mobile access.  _IEEE Transactions on Signal Processing_ , 54(5):1703–1715, 2006.
  * Caferov et al. [2015] Cafer Caferov, Barış Kaya, Ryan O’Donnell, and AC Cem Say.  Optimal bounds for estimating entropy with pmf queries.  In _International Symposium on Mathematical Foundations of Computer Science_ , pages 187–198. Springer, 2015.
  * Chen et al. [2018] Xiaowei Chen, Weiran Huang, Wei Chen, and John CS Lui.  Community exploration: from offline optimization to online learning.  In _Proceedings of the 32nd International Conference on Neural Information Processing Systems_ , 2018.
  * Chen et al. [2019] Xingyu Chen, Brandon Fain, Liang Lyu, and Kamesh Munagala.  Proportionally fair clustering.  In _International Conference on Machine Learning_ , pages 1032–1041. PMLR, 2019.
  * Chernoff [1959] Herman Chernoff.  Sequential design of experiments.  _The Annals of Mathematical Statistics_ , 30(3):755–770, 1959.
  * Chernoff [1964] Herman Chernoff.  Estimation of the mode.  _Annals of the Institute of Statistical Mathematics_ , 16(1):31–41, 1964.
  * Cover and Thomas [2012] Thomas M Cover and Joy A Thomas.  _Elements of Information Theory_.  John Wiley & Sons, 2012.
  * Finkelstein et al. [1998] Mark Finkelstein, Howard G. Tucker, and Jerry Alan Veeh.  Confidence intervals for the number of unseen types.  _Statistics & Probability Letters_, 37(4):423–430, 1998.
  * Garivier and Kaufmann [2016] Aurélien Garivier and Emilie Kaufmann.  Optimal best arm identification with fixed confidence.  In _Conference on Learning Theory_ , pages 998–1027. PMLR, 2016.
  * Hao and Orlitsky [2019] Yi Hao and Alon Orlitsky.  Data amplification: Instance-optimal property estimation.  _arXiv preprint arXiv:1903.01432_ , 2019.
  * Hoeffding [1994] Wassily Hoeffding.  Probability inequalities for sums of bounded random variables.  _The collected works of Wassily Hoeffding_ , pages 409–426, 1994\.
  * Jain et al. [2021] Shubham Anand Jain, Shreyas Goenka, Divyam Bapna, Nikhil Karamchandani, and Jayakrishnan Nair.  Sequential community mode estimation.  _Performance Evaluation_ , 152:102247, 2021.
  * Jain et al. [2022] Shubham Anand Jain, Rohan Shah, Sanit Gupta, Denil Mehta, Inderjeet J Nair, Jian Vora, Sushil Khyalia, Sourav Das, Vinay J Ribeiro, and Shivaram Kalyanakrishnan.  Pac mode estimation using PPR martingale confidence sequences.  In _AISTATS_ , 2022.
  * Karthik and Sundaresan [2020] PN Karthik and Rajesh Sundaresan.  Learning to detect an odd Markov arm.  _IEEE Transactions on Information Theory_ , 66(7):4324–4348, 2020.
  * Liu et al. [2021] Xutong Liu, Jinhang Zuo, Xiaowei Chen, Wei Chen, and John CS Lui.  Multi-layered network exploration via random walks: From offline optimization to online learning.  In _International Conference on Machine Learning_ , pages 7057–7066. PMLR, 2021.
  * Massoulié et al. [2006] Laurent Massoulié, Erwan Le Merrer, Anne-Marie Kermarrec, and Ayalvadi Ganesh.  Peer counting and sampling in overlay networks: random walk methods.  In _Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing_ , pages 123–132, 2006.
  * Maurer and Pontil [2009] Andreas Maurer and Massimiliano Pontil.  Empirical bernstein bounds and sample variance penalization.  _arXiv preprint arXiv:0907.3740_ , 2009.
  * Mazumdar and Saha [2017] Arya Mazumdar and Barna Saha.  Clustering with noisy queries.  _Advances in Neural Information Processing Systems_ , 30, 2017.
  * Parzen [1962] Emanuel Parzen.  On estimation of a probability density function and mode.  _The annals of mathematical statistics_ , 33(3):1065–1076, 1962.
  * Shah et al. [2020] Dhruti Shah, Tuhinangshu Choudhury, Nikhil Karamchandani, and Aditya Gopalan.  Sequential mode estimation with oracle queries.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , 2020.
  * Siegmund and Venkatraman [1995] David Siegmund and ES Venkatraman.  Using the generalized likelihood ratio statistic for sequential detection of a change-point.  _The Annals of Statistics_ , pages 255–271, 1995.
  * Waudby-Smith and Ramdas [2020] Ian Waudby-Smith and Aaditya Ramdas.  Confidence sequences for sampling without replacement.  _Advances in Neural Information Processing Systems_ , 33:20204–20214, 2020.
  * Wu and Yang [2018] Yihong Wu and Pengkun Yang.  Sample complexity of the distinct elements problem.  _Mathematical Statistics and Learning_ , 1(1):37–72, 2018.
  * Yun and Proutiere [2014] Se-Young Yun and Alexandre Proutiere.  Community detection via random and adaptive sampling.  In _Conference on learning theory_ , pages 138–175. PMLR, 2014.

##  Appendix A Identityless sampling

###### Proof of Lemma 3.2.

The statistic

$\displaystyle
Z_{a,b}(t):=\log\frac{{\mathbb{E}}_{\boldsymbol{p}^{\prime}\sim\mathcal{P}}[\mathcal{L}_{\boldsymbol{p}^{\prime}}(\boldsymbol{x}^{t})]}{\max_{\boldsymbol{p}^{\prime}\in\mathcal{S}:p^{\prime}_{a}\leq
p^{\prime}_{b}}\mathcal{L}_{\boldsymbol{p}^{\prime}}(\boldsymbol{x}^{t})}.$

For the Dirichlet prior on $\boldsymbol{p}^{\prime}\in\mathcal{S}$,

$\displaystyle{\mathbb{E}}_{\boldsymbol{p}^{\prime}\sim\mathcal{P}}[\mathcal{L}_{\boldsymbol{p}^{\prime}}(\boldsymbol{x}^{t})]$
$\displaystyle=\int_{\boldsymbol{p}^{\prime}\in\mathcal{S}}\prod_{i=1}^{K}p_{i}^{N_{i}(t)}.\frac{1}{B(1,1,\ldots,1)}dp^{\prime}_{1}dp^{\prime}_{2}\ldots
dp^{\prime}_{K}$
$\displaystyle\overset{(b)}{=}\frac{B(N_{1}(t)+1,N_{2}(t)+1,\ldots,N_{K}(t)+1)}{B(1,1,\ldots,1)}\int_{\boldsymbol{p}^{\prime}\in\mathcal{S}}\frac{\prod_{i=1}^{K}p_{i}^{N_{i}(t)}dp^{\prime}_{1}dp^{\prime}_{2}\ldots
dp^{\prime}_{K}}{B(N_{1}(t)+1,N_{2}(t)+1,\ldots,N_{K}(t)+1)}.$
$\displaystyle\overset{(c)}{=}\frac{B(N_{1}(t)+1,N_{2}(t)+1,\ldots,N_{K}(t)+1)}{B(1,1,\ldots,1)}.$
(20)

In $(b)$, $B(N_{1}(t)+1,N_{2}(t)+1,\ldots,N_{K}(t)+1)$ is the normalization
factor for a Dirichlet distribution with paramaters $\psi_{i}=N_{i}(t)+1$ for
all $i\in\mathcal{K}$. The equality $(c)$ follows as the integrad in $(b)$ is
the pdf of a Dirichlet distribution with parameters $\psi_{i}=N_{i}(t)+1$ for
all $i\in\mathcal{K}$. So, being the integral of a pdf over the entire domain,
it integrates to 1. Thus,

$\displaystyle
Z_{a,b}(t)=\log\frac{B(N_{1}(t)+1,N_{2}(t)+1,\ldots,N_{K}(t)+1)}{B(1,1,\ldots,1)}-\max_{\boldsymbol{p}^{\prime}\in\mathcal{S}\colon
p^{\prime}_{a}\leq
p^{\prime}_{b}}\log(\mathcal{L}_{\boldsymbol{p}^{\prime}}(\boldsymbol{x}^{t})).$

Consider the maximization: $\max_{\boldsymbol{p}^{\prime}\in\mathcal{S}\colon
p^{\prime}_{a}\leq
p^{\prime}_{b}}\log(\mathcal{L}_{\boldsymbol{p}^{\prime}}(\boldsymbol{x}^{t}))$
when $\hat{p}_{a}(t)\geq\hat{p}_{b}(t)$. This is a convex optimization.
Denoting the Lagrange multiplier associated with the constraint
$p^{\prime}_{a}\leq p^{\prime}_{b}$ by $\lambda,$ and the Lagrange multiplier
associated with the simplex constraint by $\nu,$ the KKT conditions imply that
the primal optimal point $\boldsymbol{p}^{*}$ and dual optimal points
$\lambda^{*}$, $\nu^{*}$ satisfy:

$\displaystyle p^{*}_{a}$ $\displaystyle\leq p^{*}_{b}$
$\displaystyle\lambda^{*}$ $\displaystyle\geq 0$
$\displaystyle\lambda^{*}(p^{*}_{a}-p^{*}_{b})$ $\displaystyle=0$
$\displaystyle\sum_{i=1}^{K}p^{*}_{i}-1$ $\displaystyle=0$
$\displaystyle-\frac{N_{i}(t)}{p^{*}_{i}}+\nu^{*}$ $\displaystyle=0\hskip
28.45274pt\forall i\in\mathcal{K}\setminus\\{a,b\\}$
$\displaystyle-\frac{N_{a}(t)}{p^{*}_{a}}+\lambda^{*}+\nu^{*}$
$\displaystyle=0$
$\displaystyle-\frac{N_{b}(t)}{p^{*}_{b}}-\lambda^{*}+\nu^{*}$
$\displaystyle=0.$

From first three conditions we can see that either $\lambda^{*}=0$ (then the
problem reduces to unconstrained maximization of the likelihood function) or
$p^{*}_{a}-p^{*}_{b}=0$. If $\lambda^{*}=0$ then $p^{*}_{i}=\hat{p}_{i}(t)$.
This would violate the constraint $p^{\prime}_{a}\leq p^{\prime}_{b}$ when
$\hat{p}_{a}(t)\geq\hat{p}_{b}(t)$. Taking $p^{*}_{a}=p^{*}_{b}$ and solving
the gradient equations we get $\nu^{*}=t$,
$\lambda^{*}=t\frac{N_{b}(t)-N_{a}(t)}{N_{b}(t)+N_{a}(t)}$ and
$p^{*}_{a}=p^{*}_{b}=\frac{N_{a}(t)+N_{b}(t)}{2t}=\frac{\hat{p}_{a}(t)+\hat{p}_{b}(t)}{2}$.
Therefore,

$\max_{\boldsymbol{p}^{\prime}\in\mathcal{S}\colon p^{\prime}_{a}\leq
p^{\prime}_{b}}\log(\mathcal{L}_{\boldsymbol{p}^{\prime}}(\boldsymbol{x}^{t}))=\sum_{i\in\mathcal{K}\setminus\\{a,b\\}}N_{i}(t)\log(\hat{p}_{i}(t))+(N_{a}(t)+N_{b}(t))\log\left(\frac{\hat{p}_{a}(t)+\hat{p}_{b}(t)}{2}\right).$
(21)

Thus $Z_{a,b}(t)$ simplifies as

$\displaystyle Z_{a,b}(t)$
$\displaystyle=\log\frac{B(N_{1}(t)+1,N_{2}(t)+1,\ldots,N_{K}(t)+1)}{B(1,1,\ldots,1)}$
$\displaystyle\hskip
85.35826pt-\sum_{i\in\mathcal{K}\setminus\\{a,b\\}}N_{i}(t)\log(\hat{p}_{i}(t))-(N_{a}(t)+N_{b}(t))\log\left(\frac{\hat{p}_{a}(t)+\hat{p}_{b}(t)}{2}\right).$

From the definition of $Z_{a,b}(t)$ and (20), when
$\hat{p}_{a}(t)\geq\hat{p}_{b}(t)$,

$\displaystyle Z_{b,a}(t)$
$\displaystyle=\log\frac{B(N_{1}(t)+1,N_{2}(t)+1,\ldots,N_{K}(t)+1)}{B(1,1,\ldots,1)}-\max_{\boldsymbol{p}^{\prime}\in\mathcal{S}\colon
p^{\prime}_{b}\leq
p^{\prime}_{a}}\log(\mathcal{L}_{\boldsymbol{p}^{\prime}}(\boldsymbol{x}^{t}))$
$\displaystyle\overset{(a)}{=}\log\frac{B(N_{1}(t)+1,N_{2}(t)+1,\ldots,N_{K}(t)+1)}{B(1,1,\ldots,1)}-\sum_{i=1}^{K}N_{i}(t)\log(\hat{p}_{i}(t)).$
(22)

In the above equation, $(a)$ follows from the fact that when
$\hat{p}_{a}(t)\geq\hat{p}_{b}(t)$,
$\max_{\boldsymbol{p}^{\prime}\in\mathcal{S}\colon p^{\prime}_{b}\leq
p^{\prime}_{a}}\log(\mathcal{L}_{\boldsymbol{p}^{\prime}}(\boldsymbol{x}^{t}))$
reduces to unconstrained maximization of the Log-Likelihood,
$\log(\mathcal{L}_{\boldsymbol{p}^{\prime}}(\boldsymbol{x}^{t}))$. This is
achieved at $p^{\prime}_{i}=\hat{p}_{i}(t)$ for all $i\in\mathcal{K}$. ∎

###### Proof of Lemma 3.3.

When $\hat{p}_{a}(t)\geq\hat{p}_{b}(t)$, from Lemma 3.2,

$\displaystyle\displaystyle Z_{a,b}(t)$
$\displaystyle=\log\frac{B(N_{1}(t)+1,N_{2}(t)+1,\ldots,N_{K}(t)+1)}{B(1,1,\ldots,1)}$
$\displaystyle\hskip
85.35826pt-\sum_{i\in\mathcal{K}\setminus\\{a,b\\}}N_{i}(t)\log(\hat{p}_{i}(t))-(N_{a}(t)+N_{b}(t))\log\left(\frac{\hat{p}_{a}(t)+\hat{p}_{b}(t)}{2}\right).$

and

$\displaystyle
Z_{b,a}(t)=\log\frac{B(N_{1}(t)+1,N_{2}(t)+1,\ldots,N_{K}(t)+1)}{B(1,1,\ldots,1)}-\sum_{i=1}^{K}N_{i}(t)\log(\hat{p}_{i}(t)).$
(23)

Comparing $Z_{a,b}(t)$ with $Z_{b,a}(t)$ we get

$Z_{a,b}(t)>Z_{b,a}(t)\text{ when }\hat{p}_{a}(t)\geq\hat{p}_{b}(t).$ (24)

Also, note that for any pair $a,b$, when $\hat{p}_{a}(t)\geq\hat{p}_{b}(t)$,
$Z_{b,a}(t)$ has the same value. Now, we compute

$\displaystyle Z(t)$
$\displaystyle=\max_{a\in\mathcal{K}}\min_{b\in\mathcal{K}\setminus\\{a\\}}Z_{a,b}(t)$
$\displaystyle=\max\left\\{\min_{b\neq\hat{a}_{t}}Z_{\hat{a}_{t},b}(t),\max_{x\neq\hat{a}_{t}}\min_{b\neq
x}Z_{x,b}(t)\right\\}$
$\displaystyle\overset{(b)}{=}\max\left\\{Z_{\hat{a}_{t},\hat{b}_{t}}(t),\max_{x\neq\hat{a}_{t}}Z_{x,\hat{a}_{t}}(t)\right\\}$
$\displaystyle\overset{(c)}{=}\max\left\\{Z_{\hat{a}_{t},\hat{b}_{t}}(t),Z_{\hat{b}_{t},\hat{a}_{t}}(t)\right\\}$
$\displaystyle\overset{(e)}{=}Z_{\hat{a}_{t},\hat{b}_{t}}(t).$

Equality $(b)$ follows because

$\max_{x\neq\hat{a}_{t}}\min_{b\neq
x}Z_{x,b}(t)=\max_{x\neq\hat{a}_{t}}\min_{b\neq
x}\left\\{Z_{x,\hat{a}_{t}}(t),\min_{b\neq\hat{a}_{t}}Z_{x,b}(t)\right\\}$

and $Z_{x,\hat{a}_{t}}(t)$ has the lowest value that $Z_{a,b}(t)$ can take
(see (23)). Equality $(c)$ follows as $Z_{x,\hat{a}_{t}}(t)$ has the same
value given in (23) for all $x$. The last equality $(e)$ follows from (24).

∎

###### Proof of Theorem 3.6.

Let $a^{*}$ denote the estimated mode. For $b\in\mathcal{K}$, let

$\mathit{E}_{b}^{t}=\\{\omega:\tau_{\delta}=t,a^{*}=b\\}$

be the set of sample paths for which the stopping time of NI-ME is $t$ and the
mode estimated is $b$. Note that

$\mathit{E}_{b}^{t_{1}}\cap\mathit{E}_{b}^{t_{2}}=\phi\text{ for all
}t_{1}\neq t_{2}.$

The probability of error in estimating the mode

$\displaystyle{\mathbb{P}}(a^{*}\neq 1)$
$\displaystyle=\sum_{b\in\mathcal{K}\setminus\\{1\\}}\sum_{t=0}^{\infty}\sum_{\omega\in\mathit{E}_{b}^{t}}\mathcal{L}_{\boldsymbol{p}}(\omega)$
$\displaystyle\leq\sum_{b\in\mathcal{K}\setminus\\{1\\}}\sum_{t=0}^{\infty}\sum_{\omega\in\mathit{E}_{b}^{t}}\max_{p^{\prime}_{1}\geq
p^{\prime}_{b}}\mathcal{L}_{\boldsymbol{p^{\prime}}}(\omega)$
$\displaystyle=\sum_{b\in\mathcal{K}\setminus\\{1\\}}\sum_{t=0}^{\infty}\sum_{\omega\in\mathit{E}_{b}^{t}}\frac{\max_{p^{\prime}_{1}\geq
p^{\prime}_{b}}\mathcal{L}_{\boldsymbol{p^{\prime}}}(\omega)}{{\mathbb{E}}_{\boldsymbol{p}^{\prime}\sim\mathcal{P}}[\mathcal{L}_{\boldsymbol{p}^{\prime}}(\omega)]}{\mathbb{E}}_{\boldsymbol{p}^{\prime}\sim\mathcal{P}}[\mathcal{L}_{\boldsymbol{p}^{\prime}}(\omega)]$
$\displaystyle\overset{(a_{1})}{=}\sum_{b\in\mathcal{K}\setminus\\{1\\}}\sum_{t=0}^{\infty}\sum_{\omega\in\mathit{E}_{b}^{t}}\exp(-Z_{b,1}(t)){\mathbb{E}}_{\boldsymbol{p}^{\prime}\sim\mathcal{P}}[\mathcal{L}_{\boldsymbol{p}^{\prime}}(\omega)]$
$\displaystyle\overset{(a_{2})}{\leq}\sum_{b\in\mathcal{K}\setminus\\{1\\}}\exp{-\beta(t,\delta)}\underbrace{\sum_{t=0}^{\infty}\sum_{\omega\in\mathit{E}_{b}^{t}}{\mathbb{E}}_{\boldsymbol{p}^{\prime}\sim\mathcal{P}}[\mathcal{L}_{\boldsymbol{p}^{\prime}}(\omega)]}_{(p*)}$
$\displaystyle\overset{(a_{3})}{\leq}\delta.$

Equality $(a_{1})$ follows from the definition of $Z_{a,b}(t)$. Inequality
$(a_{2})$ follows as $Z_{b,1}(t)$ will have crossed the threshold
$\beta(t,\delta)$ at the stopping time $t$ when mode is $b$. Inequality
$(a_{3})$ follows by taking
$\beta(t,\delta)=\log\left(\frac{K-1}{\delta}\right)$ as $(p*)$ is
${\mathbb{P}}(a^{*}=b)$ under an alternate probability distribution. ∎

###### Proof of Theorem 3.7.

proof of (5):
Let $\mathcal{E}$ be the event

$\mathcal{E}=\\{\forall
i\in\mathcal{K},\hat{p}_{i}(t)\xrightarrow[t\to\infty]{}p_{i}\\}.$

By the law of Large numbers the event $\mathcal{E}$ is of probability 1. For
the Dirichlet prior,

$\displaystyle Z(t)$
$\displaystyle=\log\frac{B(N_{1}(t)+1,N_{2}(t)+1,\ldots,N_{K}(t)+1)}{B(1,1,\ldots,1)}$
(25) $\displaystyle\hskip
85.35826pt-\sum_{i\in\mathcal{K}\setminus\\{\hat{a}_{t},\hat{b}_{t}\\}}N_{i}(t)\log(\hat{p}_{i}(t))-(N_{\hat{a}_{t}}(t)+N_{\hat{b}_{t}}(t))\log\left(\frac{\hat{p}_{\hat{a}_{t}}(t)+\hat{p}_{\hat{b}_{t}}(t)}{2}\right)$
$\displaystyle=\log\frac{\prod_{j=1}^{K}\Gamma(N_{j}(t)+1)\Gamma(K)}{\Gamma(t+K)}$
$\displaystyle\hskip
85.35826pt-\sum_{i\in\mathcal{K}\setminus\\{\hat{a}_{t},\hat{b}_{t}\\}}N_{i}(t)\log(\hat{p}_{i}(t))-(N_{\hat{a}_{t}}(t)+N_{\hat{b}_{t}}(t))\log\left(\frac{\hat{p}_{\hat{a}_{t}}(t)+\hat{p}_{\hat{b}_{t}}(t)}{2}\right)$
$\displaystyle=\log((K-1)!)+\sum_{j=1}^{K}\log(N_{j}(t)!)-\log((t+K-1)!)$
$\displaystyle\hskip
85.35826pt-\sum_{i\in\mathcal{K}\setminus\\{\hat{a}_{t},\hat{b}_{t}\\}}N_{i}(t)\log(\hat{p}_{i}(t))-(N_{\hat{a}_{t}}(t)+N_{\hat{b}_{t}}(t))\log\left(\frac{\hat{p}_{\hat{a}_{t}}(t)+\hat{p}_{\hat{b}_{t}}(t)}{2}\right).$
(26)

By Stirling’s approximation,

$\displaystyle N_{j}(t)!$ $\displaystyle\sim\sqrt{2\pi
N_{j}(t)}\left(\frac{N_{j}(t)}{e}\right)^{N_{j}(t)}$ $\displaystyle(t+K-1)!$
$\displaystyle\sim\sqrt{2\pi(t+K-1)}\left(\frac{t+K-1}{e}\right)^{t+K-1}$

as $t\to\infty.$ Using Stirling’s approximation, the RHS of (26) becomes

$\displaystyle\log((K-1)!)+\sum_{j=1}^{K}\log(N_{j}(t)!)-\log((t+K-1)!)$
$\displaystyle\hskip
28.45274pt-\sum_{i\in\mathcal{K}\setminus\\{\hat{a}_{t},\hat{b}_{t}\\}}N_{i}(t)\log(\hat{p}_{i}(t))-(N_{\hat{a}_{t}}(t)+N_{\hat{b}_{t}}(t))\log\left(\frac{\hat{p}_{\hat{a}_{t}}(t)+\hat{p}_{\hat{b}_{t}}(t)}{2}\right)$
$\displaystyle=\log((K-1)!)+\sum_{j=1}^{K}\log\left(\sqrt{2\pi
N_{j}(t)}\right)+\sum_{j=1}^{K}N_{j}(t)\log(N_{j}(t))-t$ $\displaystyle\hskip
28.45274pt-\log\left(\sqrt{2\pi(t+K-1)}\right)-(t+K-1)\log(t+K-1)+t+(K-1)$
$\displaystyle\hskip
56.9055pt-\sum_{i\in\mathcal{K}\setminus\\{\hat{a}_{t},\hat{b}_{t}\\}}N_{i}(t)\log(\hat{p}_{i}(t))-(N_{\hat{a}_{t}}(t)+N_{\hat{b}_{t}}(t))\log\left(\frac{\hat{p}_{\hat{a}_{t}}(t)+\hat{p}_{\hat{b}_{t}}(t)}{2}\right)$
$\displaystyle=\sum_{j=1}^{K}N_{j}(t)\log\left(\frac{N_{j}(t)}{t+K-1}\right)-\sum_{i\in\mathcal{K}\setminus\\{\hat{a}_{t},\hat{b}_{t}\\}}N_{i}(t)\log(\hat{p}_{i}(t))-(N_{\hat{a}_{t}}(t)+N_{\hat{b}_{t}}(t))\log\left(\frac{\hat{p}_{\hat{a}_{t}}(t)+\hat{p}_{\hat{b}_{t}}(t)}{2}\right)$
$\displaystyle\hskip
28.45274pt+\log((K-1)!)+\sum_{j=1}^{K}\log\left(\sqrt{2\pi
N_{j}(t)}\right)-\log\left(\sqrt{2\pi(t+K-1)}\right)-(K-1)\log(t+K-1)+(K-1).$
(27)

On $\mathcal{E}$, as $t\to\infty$,

$\displaystyle\frac{N_{j}(t)}{t+K-1}\to\hat{p}_{j}(t)\text{ and
}\hat{p}_{j}(t)\to p_{j}.$ (28)

So, as $t\to\infty$, from (26) and (27)

$\displaystyle\frac{Z(t)}{t}\to\sum_{j=1}^{K}p_{j}\log\left(p_{j}\right)-\sum_{i\in\mathcal{K}\setminus\\{1,2\\}}p_{j}\log(p_{i})-(p_{1}+p_{2})\log\left(\frac{p_{1}+p_{2}}{2}\right).$

Simplifying the limit above we get,

$\displaystyle\sum_{j=1}^{K}p_{j}\log\left(p_{i}\right)-\sum_{i\in\mathcal{K}\setminus\\{1,2\\}}p_{j}\log(p_{i})-(p_{1}+p_{2})\log\left(\frac{p_{1}+p_{2}}{2}\right)$
$\displaystyle=p_{1}\log(p_{1})+p_{2}\log(p_{2})-(p_{1}+p_{2})\log\left(\frac{p_{1}+p_{2}}{2}\right)$
$\displaystyle=(p_{1}+p_{2})\frac{p_{1}}{(p_{1}+p_{2})}\log\left(\frac{\frac{p_{1}}{(p_{1}+p_{2})}}{2}\right)+(p_{1}+p_{2})\frac{p_{2}}{(p_{1}+p_{2})}\log\left(\frac{\frac{p_{2}}{(p_{1}+p_{2})}}{2}\right)$
$\displaystyle=(p_{1}+p_{2})kl\left(\frac{p_{1}}{p_{1}+p_{2}},\frac{1}{2}\right).$

where $kl(x,y)=x\log(\frac{x}{y})+(1-x)\log(\frac{1-x}{1-y})$ is the KL
divergence of Bernoulli distribution. So, on $\mathcal{E}$ as $t\to\infty$,

$\displaystyle\frac{Z(t)}{t}\to(p_{1}+p_{2})kl\left(\frac{p_{1}}{p_{1}+p_{2}},\frac{1}{2}\right).$

So, there exists a time $t_{0}$ such that for $t>t_{0}$, and some $\epsilon>0$
,

$Z(t)>\frac{t}{1+\epsilon}(p_{1}+p_{2})kl\left(\frac{p_{1}}{p_{1}+p_{2}},\frac{1}{2}\right)$
(29)

Let
$g^{*}(\boldsymbol{p})=(p_{1}+p_{2})d\left(\frac{p_{1}}{p_{1}+p_{2}},\frac{1}{2}\right).$
Consequently,

$\displaystyle\tau_{\delta}$
$\displaystyle=\inf\\{t\in{\mathbb{N}}:Z(t)\geq\beta(t,\delta)\\}$
$\displaystyle\leq
t_{0}\vee\inf\left\\{t\in{\mathbb{N}}:t(1+\epsilon)^{-1}g^{*}(\boldsymbol{p})\geq\log\left(\frac{(K-1)}{\delta}\right)\right\\}$
$\displaystyle\leq
t_{0}\vee\log\left(\frac{K-1}{\delta}\right)(1+\epsilon)(g^{*}(\boldsymbol{p}))^{-1}$

Thus $\tau_{\delta}$ is finite on $\mathcal{E}$ for every $\delta\in(0,1)$ and
by letting $\epsilon$ go to zero we get

$\displaystyle\lim\sup_{\delta\to
0}\frac{\tau_{\delta}}{\log(\frac{1}{\delta})}\leq(g^{*}(\boldsymbol{p}))^{-1}.$

proof of (6):
Let $\zeta>0$. Let $\xi$ be some value less than $\frac{(p_{1}-p_{2})}{4}$. We
define
$I_{\xi}=[p_{1}-\xi,p_{1}+\xi]\times[p_{2}-\xi,p_{2}+\xi]\times\ldots\times[p_{k}-\xi,p_{k}+\xi].$
Let $T\in{\mathbb{N}}$. The event $\mathcal{E}_{T}$ is defined as

$\mathcal{E}_{T}=\cap_{t=T^{\zeta}}^{T}(\boldsymbol{\hat{p}}(t)\in I_{\xi}).$

From (26), for the Dirichlet prior,

$\displaystyle Z(t)$
$\displaystyle=\log((K-1)!)+\sum_{j=1}^{K}\log(N_{j}(t)!)-\log((t+K-1)!)$
$\displaystyle\hskip
85.35826pt-\sum_{i\in\mathcal{K}\setminus\\{\hat{a}_{t},\hat{b}_{t}\\}}N_{i}(t)\log(\hat{p}_{i}(t))-(N_{\hat{a}_{t}}(t)+N_{\hat{b}_{t}}(t))\log\left(\frac{\hat{p}_{\hat{a}_{t}}(t)+\hat{p}_{\hat{b}_{t}}(t)}{2}\right).$

By Stirling’s approximation,

$\displaystyle N_{j}(t)!$ $\displaystyle\sim\sqrt{2\pi
N_{j}(t)}\left(\frac{N_{j}(t)}{e}\right)^{N_{j}(t)}$ $\displaystyle(t+K-1)!$
$\displaystyle\sim\sqrt{2\pi(t+K-1)}\left(\frac{t+K-1}{e}\right)^{t+K-1}$

as $t\to\infty.$ On $\mathcal{E}_{T}$, for $t>T^{\zeta}$, $t(p_{j}-\xi)\leq
N_{j}(t)\leq t(p_{j}+\xi)$. So, on $\mathcal{E}_{T}$ there exists a time
$T_{1}>T^{\zeta}$ and some $\lambda>0$ such that for $t>T_{1}$,

$\displaystyle N_{j}(t)!$ $\displaystyle\geq\frac{1}{(1+\lambda)}\sqrt{2\pi
N_{j}(t)}\left(\frac{N_{j}(t)}{e}\right)^{N_{j}(t)}$ $\displaystyle(t+K-1)!$
$\displaystyle\leq\frac{1}{(1-\lambda)}\sqrt{2\pi(t+K-1)}\left(\frac{t+K-1}{e}\right)^{t+K-1}.$

Using Stirling’s approximation in the RHS of above equation of $Z(t)$, on
$\mathcal{E}_{T}$ for $t>T_{1}$, we get

$\displaystyle Z(t)$
$\displaystyle\geq\log((K-1)!)+\sum_{j=1}^{K}\log\left(\sqrt{2\pi
N_{j}(t)}\right)+\sum_{j=1}^{K}N_{j}(t)\log(N_{j}(t))-t-\log(1+\lambda)$
$\displaystyle\hskip
28.45274pt-\log\left(\sqrt{2\pi(t+K-1)}\right)-(t+K-1)\log(t+K-1)+t+(K-1)+\log(1-\lambda)$
$\displaystyle\hskip
56.9055pt-\sum_{i\in\mathcal{K}\setminus\\{1,2\\}}N_{i}(t)\log(\hat{p}_{i}(t))-(N_{1}(t)+N_{2}(t))\log\left(\frac{\hat{p}_{1}(t)+\hat{p}_{2}(t)}{2}\right)$
$\displaystyle=\sum_{j=1}^{K}N_{j}(t)\log\left(\frac{N_{j}(t)}{t+K-1}\right)-\sum_{i\in\mathcal{K}\setminus\\{a,b\\}}N_{i}(t)\log(\hat{p}_{i}(t))-(N_{1}(t)+N_{2}(t))\log\left(\frac{\hat{p}_{1}(t)+\hat{p}_{2}(t)}{2}\right)$
$\displaystyle\hskip
28.45274pt+\log((K-1)!)+\sum_{j=1}^{K}\log\left(\sqrt{2\pi N_{j}(t)}\right)$
$\displaystyle\hskip
56.9055pt-\log\left(\sqrt{2\pi(t+K-1)}\right)-(K-1)\log(t+K-1)+(K-1)+\log\left(\frac{1-\lambda}{1+\lambda}\right)$
$\displaystyle\geq\sum_{j=1}^{K}t(p_{j}-\xi)\log\left(\frac{t(p_{j}-\xi)}{t+K-1}\right)-\sum_{i\in\mathcal{K}\setminus\\{1,2\\}}t(p_{j}+\xi)\log((p_{j}+\xi))$
$\displaystyle\hskip
28.45274pt-t(p_{1}+p_{2}+2\xi)\log\left(\frac{p_{1}+p_{2}+2\xi}{2}\right)+\log((K-1)!)+\sum_{j=1}^{K}\log\left(\sqrt{2\pi
t(p_{j}-\xi)}\right)$ $\displaystyle\hskip
56.9055pt-\log\left(\sqrt{2\pi(t+K-1)}\right)-(K-1)\log(t+K-1)+(K-1)+\log\left(\frac{1-\lambda}{1+\lambda}\right).$

On $\mathcal{E}_{T}$, there exists a time $T_{2}>T_{1}$ such that for
$t>T_{2}$, for some $\varepsilon>0$,

$\displaystyle Z(t)$
$\displaystyle>\frac{t}{(1+\varepsilon)}\Bigg{(}\sum_{j=1}^{K}(p_{j}-\xi)\log\left(\frac{(p_{j}-\xi)}{t+K-1}\right)-\sum_{i\in\mathcal{K}\setminus\\{1,2\\}}(p_{j}+\xi)\log((p_{j}+\xi))$
$\displaystyle\hskip
28.45274pt-(p_{1}+p_{2}+2\xi)\log\left(\frac{p_{1}+p_{2}+2\xi}{2}\right)\Bigg{)}$
$\displaystyle=\frac{tf_{\xi}^{*}(\boldsymbol{p})}{(1+\varepsilon)},$

where
$f_{\xi}^{*}(\boldsymbol{p}):=\sum_{j=1}^{K}(p_{j}-\xi)\log\left(\frac{(p_{j}-\xi)}{t+K-1}\right)-\sum_{i\in\mathcal{K}\setminus\\{1,2\\}}(p_{j}+\xi)\log((p_{j}+\xi))-(p_{1}+p_{2}+2\xi)\log\left(\frac{p_{1}+p_{2}+2\xi}{2}\right).$
Let $T>T_{2}$. On $\mathcal{E}_{T}$,

$\displaystyle\min(\tau_{\delta},T)$ $\displaystyle\leq
T^{\zeta}+\sum_{t=T^{\zeta}}^{T}\mathbb{I}(\tau_{\delta}>t)$
$\displaystyle\leq
T^{\zeta}+\sum_{t=T^{\zeta}}^{T}\mathbb{I}(Z(t)\leq\beta(t,\delta))$
$\displaystyle\leq
T^{\zeta}+\sum_{t=T^{\zeta}}^{T}\mathbb{I}\left(\frac{tf_{\xi}^{*}(\boldsymbol{p})}{(1+\varepsilon)}\leq\beta(T,\delta)\right)$
$\displaystyle\leq
T^{\zeta}+\frac{\beta(T,\delta)(1+\varepsilon)}{f_{\xi}^{*}(\boldsymbol{p})}.$

We define,

$\displaystyle
T_{0}(\delta)=\inf\left\\{T\in{\mathbb{N}}:T^{\zeta}+\frac{\beta(T,\delta)(1+\varepsilon)}{f_{\xi}^{*}(\boldsymbol{p})}\leq
T\right\\},$

such that for every $T\geq\max(T_{0}(\delta),T_{2})$,
$\mathcal{E}_{T}\subseteq(\tau_{\delta}\leq T)$. So, for all
$T\geq\max(T_{0}(\delta),T_{2})$,

$\displaystyle{\mathbb{P}}(\tau_{\delta}>T)$
$\displaystyle\leq{\mathbb{P}}(\mathcal{E}_{T}^{c})$ $\displaystyle\text{ and
}{\mathbb{E}}[\tau_{\delta}]\leq
T_{0}(\delta)+T_{2}+\sum_{T=1}^{\infty}{\mathbb{P}}(\mathcal{E}_{T}^{c}).$
(30)

Let $\eta>0$. We define a constant

$C(\eta)=\inf\left\\{T\in{\mathbb{N}}:T-T^{\zeta}\geq\frac{T}{1+\eta}\right\\}$

thus,

$\displaystyle T_{0}(\delta)$ $\displaystyle\leq
C(\eta)+\inf\left\\{T\in{\mathbb{N}}:\frac{\beta(T,\delta)(1+\varepsilon)}{f_{\xi}^{*}(\boldsymbol{p})}\leq\frac{T}{1+\eta}\right\\}$
$\displaystyle=C(\eta)+\frac{\beta(T,\delta)(1+\varepsilon)(1+\eta)}{f_{\xi}^{*}(\boldsymbol{p})}.$
(31)

######  Lemma A.1.

For some $\zeta>0$,

${\mathbb{P}}(\mathcal{E}_{T}^{c})\leq B\exp(-C(T^{\zeta}+1))$ (32)

where $B=\frac{2K}{1-\exp(-2\xi^{2})}$ and $C=2\xi^{2}$.

From (30), (31) and (32),

$\displaystyle{\mathbb{E}}[\tau_{\delta}]\leq
C(\eta)+\frac{\log\left(\frac{K-1}{\delta}\right)(1+\varepsilon)(1+\eta)}{f_{\xi}^{*}(\boldsymbol{p})}+T_{2}+\sum_{T=1}^{\infty}B\exp(-C(T^{\zeta}+1)).$

The upper bound in the RHS of the above equation is finite only if
$\sum_{T=1}^{\infty}B\exp(-C(T^{\zeta}+1))$ if finite. Thus, $T^{\zeta}$ is
chosen such that $\sum_{T=1}^{\infty}B\exp(-C(T^{\zeta}+1))<\infty$. Taking
the limit

$\lim_{\xi\to 0}f_{\xi}^{*}(\boldsymbol{p})=g^{*}(\boldsymbol{p})$

and letting $\varepsilon$ and $\eta$ go to zero we get

$\displaystyle\lim\sup_{\delta\to
0}\frac{{\mathbb{E}}[\tau_{\delta}]}{\log(\frac{1}{\delta})}\leq(g^{*}(\boldsymbol{p}))^{-1}.$
(33)

proof of Lemma A.1

$\displaystyle{\mathbb{P}}(\mathcal{E}_{T}^{c})$
$\displaystyle\leq\sum_{t=T^{\zeta}}^{T}{\mathbb{P}}(\boldsymbol{\hat{p}}(t)\notin
I_{\xi})$ (34)
$\displaystyle\leq\sum_{t=T^{\zeta}}^{T}\sum_{a=1}^{K}\left[{\mathbb{P}}(\hat{p}_{a}(t)<p_{a}-\xi)+{\mathbb{P}}(\hat{p}_{a}(t)>p_{a}+\xi)\right].$
(35)

Let the random variable

$Z_{t}^{a}=\begin{cases}1&\text{ if }X_{t}=a\\\
0&\text{otherwise}.\end{cases}$ (36)

Since $Z_{t}^{a}\leq 1$, it is sub-Gaussian with parameter $\frac{1}{2}$. We
can write $\hat{p}_{a}(t)=\frac{1}{t}\sum_{j=1}^{t}Z_{j}^{a}$. By applying the
Hoeffding Bound (see Hoeffding [17]),

${\mathbb{P}}(\hat{p}_{a}(t)-p_{a}>\xi)\leq\exp(-2t\xi^{2})\text{ and
}{\mathbb{P}}(\hat{p}_{a}(t)-p_{a}<-\xi)\leq\exp(-2t\xi^{2}).$ (37)

So,

$\displaystyle{\mathbb{P}}(\mathcal{E}_{T}^{c})$ $\displaystyle\leq
2\sum_{t=T^{\zeta}}^{T}\sum_{a=1}^{K}\exp(-2t\xi^{2})$ (38)
$\displaystyle=2K\sum_{t=T^{\zeta}}^{T}\exp(-2t\xi^{2})$ (39)
$\displaystyle=2K\left(\frac{\exp(-2(T^{\zeta}+1)\xi^{2})-\exp(-2(T+1)\xi^{2})}{1-\exp(-2\xi^{2})}\right)$
(40) $\displaystyle\leq
2K\frac{\exp(-2(T^{\zeta}+1)\xi^{2})}{1-\exp(-2\xi^{2})}$ (41)
$\displaystyle=B\exp(-C(T^{\zeta}+1)).$ (42)

where $B=\frac{2K}{1-\exp(-2\xi^{2})}$ and $C=2\xi^{2}$. ∎

##  Appendix B Identity-based sampling

###### Proof of Lemma 4.1.

This proof uses ideas similar to the proof of Theorem 4 in Jain et al. [18].
Let $D=(d_{1},d_{2},\ldots d_{K})\in{\mathbb{N}}^{K}$ be an instance with
community one as the largest community and $N=\sum_{j=1}^{K}d_{j}$. Let
$D^{\prime}=(d^{\prime}_{1},d^{\prime}_{2},\ldots d^{\prime}_{K})$ be an
alternate instance in ${\mathbb{N}}^{K}$ such that the mode is not equal to
one and $d^{\prime}_{j}\geq d_{j}$ for all $j\in\mathcal{K}$ and
$N^{\prime}=\sum_{j=1}^{K}d^{\prime}_{j}>N$. Let $q_{D}(s,s^{\prime})$ and
$q_{D^{\prime}}(s,s^{\prime})$ denote probability of transition from state
$s=(s_{1},s_{2},\ldots,s_{K})$ to
$s^{\prime}=(s^{\prime}_{1},s^{\prime}_{2},\ldots,s^{\prime}_{K})$. So,
$q_{D}(s,s)=\frac{\sum_{j=1}^{K}s_{j}}{N}$ and
$q_{D}(s,s+e_{j})=\frac{d_{j}-s_{j}}{N}$, where $e_{j}$ is a $K$-length unit
vector with one in the $j^{th}$ position. Similarly,
$q_{D^{\prime}}(s,s)=\frac{\sum_{j=1}^{K}s_{j}}{N^{\prime}}$ and
$q_{D^{\prime}}(s,s+e_{j})=\frac{d^{\prime}_{j}-s_{j}}{N^{\prime}}$. Thus for
states $s$ and $s^{\prime}$ that are feasible under both $D$ and $D^{\prime}$,

$\log\left(\frac{q_{D}(s,s)}{q_{D^{\prime}}(s,s)}\right)=\log\left(\frac{N^{\prime}}{N}\right)$
(43)

and

$\displaystyle\log\left(\frac{q_{D}(s,s+e_{j})}{q_{D^{\prime}}(s,s+e_{j})}\right)$
$\displaystyle=\log\left(\frac{(N^{\prime})(d_{j}-s_{j})}{N(d^{\prime}_{j}-s_{j})}\right)$
$\displaystyle\leq\log\left(\frac{N^{\prime}}{N}\right).$ (44)

Given a state evolution $\left(S(1),S(2),\ldots S(\tau_{\delta})\right)$, from
Appendix D, proof of Theorem 4 in Jain et al. [18], the log-likelihood ratio
is

$\log\frac{{\mathbb{P}}_{D}\left(S(1),S(2),\ldots
S(\tau_{\delta})\right)}{{\mathbb{P}}_{D^{\prime}}\left(S(1),S(2),\ldots
S(\tau_{\delta})\right)}\leq\sum_{s,s^{\prime}}N(s,s^{\prime},\tau_{\delta})\log\left(\frac{q_{D}(s,s^{\prime})}{q_{D^{\prime}}(s,s^{\prime})}\right),$

where $N(s,s^{\prime},\tau_{\delta})$ denotes the number of transitions from
state $s$ to $s^{\prime}$ within time $\tau_{\delta}$. Also, expected value
with respect to $D$ of the log-likelihood ratio is

$\displaystyle{\mathbb{E}}_{D}\left[\log\frac{{\mathbb{P}}_{D}\left(S(1),S(2),\ldots
S(\tau_{\delta})\right)}{{\mathbb{P}}_{D^{\prime}}\left(S(1),S(2),\ldots
S(\tau_{\delta})\right)}\right]$
$\displaystyle\overset{(a)}{\geq}D(Ber({\mathbb{P}}_{D}(\hat{a}_{\tau_{\delta}})=1)||Ber({\mathbb{P}}_{D^{\prime}}(\hat{a}_{\tau_{\delta}})=1))$
$\displaystyle\overset{(b)}{\geq}kl(\delta,1-\delta)$
$\displaystyle\overset{(c)}{\geq}\log\left(\frac{1}{2.4\delta}\right).$

In $(a)$, $Ber(x)$ denotes the Bernoulli distribution with parameter
$x\in(0,1)$ and this inequality follows from the Data processing
inequality(see Cover and Thomas [13]). The inequalities $(b)$ and $(c)$ follow
from section 3.4 in Shah et al. [26]. Therefore, from the above inequality we
get

$\displaystyle\inf_{d^{\prime}\in
D^{\prime}}{\mathbb{E}}_{D}\left[\log\frac{{\mathbb{P}}_{D}\left(S(1),S(2),\ldots
S(\tau_{\delta})\right)}{{\mathbb{P}}_{D^{\prime}}\left(S(1),S(2),\ldots
S(\tau_{\delta})\right)}\right]\geq\log\left(\frac{1}{2.4\delta}\right)$
$\displaystyle\inf_{d^{\prime}\in
D^{\prime}}\sum_{s,s^{\prime}}{\mathbb{E}}_{D}[N(s,s^{\prime},\tau_{\delta})]\log\left(\frac{q_{D}(s,s^{\prime})}{q_{D^{\prime}}(s,s^{\prime})}\right)\geq\log\left(\frac{1}{2.4\delta}\right)$
$\displaystyle{\mathbb{E}}[\tau_{\delta}]\inf_{d^{\prime}\in
D^{\prime}}\log\left(\frac{N^{\prime}}{N}\right)\overset{(f)}{\geq}\log\left(\frac{1}{2.4\delta}\right).$

The inequality $(f)$ follows from (43), (44) and from the inequality
$\sum_{s,s^{\prime}}N(s,s^{\prime},t)\leq t$. The above infimum is obtained at
an alternate instance $D^{\prime}$ where $d^{\prime}_{j}=d_{j}$ for all $j\neq
2$ and $d_{2}=d_{1}+1$. Thus,

$\displaystyle{\mathbb{E}}_{D}[\tau_{\delta}]$
$\displaystyle\geq\frac{\log\left(\frac{1}{2.4\delta}\right)}{\log\left(\frac{N-d_{2}+d_{1}+1}{N}\right)}.$

∎

###### Proof of Lemma 4.2.

Consider the lower bound from Lemma 3.1 on the expected sample complexity
under the identityless sampling model, given by

$\displaystyle(p_{1}+p_{2})kl\left(\frac{p_{1}}{p_{1}+p_{2}},\frac{1}{2}\right)$
$\displaystyle=p_{1}\log\left(\frac{2p_{1}}{p_{1}+p_{2}}\right)+p_{2}\log\left(\frac{2p_{2}}{p_{1}+p_{2}}\right)$
$\displaystyle=(p_{1}-p_{2})\log\left(\frac{2p_{1}}{p_{1}+p_{2}}\right)+\underbrace{p_{2}\log\left(\frac{4p_{1}p_{2}}{(p_{1}+p_{2})^{2}}\right)}_{(a)}$
$\displaystyle\overset{(b)}{\leq}(p_{1}-p_{2})\log(2).$ (45)

Inequality $(b)$ follows by noting that the expression in $(a)$ is non-
positive since $2\sqrt{p_{1}p_{2}}\leq(p_{1}+p_{2})$. Now, consider the lower
bound from Lemma 4.1 on the expected sample complexity under the identity-
based sampling model, given by

$\displaystyle\log\left(\frac{N-d_{2}+d_{1}+1}{N}\right)$
$\displaystyle=\log\left(1+p_{1}-p_{2}+1/N\right)$
$\displaystyle\geq\log(1+p_{1}-p_{2})$

The function $\log(1+p_{1}-p_{2})$ is between $\log(1)$ and $\log(2)$ and for
$\alpha=1-(p_{1}-p_{2})$, as $\log$ is a concave function,

$\displaystyle\log\left(\frac{N-d_{2}+d_{1}+1}{N}\right)\geq\alpha\log(1)+(1-\alpha)\log(2)=(p_{1}-p_{2})\log(2).$
(46)

The result of Lemma 4.2 follows from (45), (46). Moreover,

$\displaystyle(p_{1}+p_{2})kl\left(\frac{p_{1}}{p_{1}+p_{2}},\frac{1}{2}\right)$
$\displaystyle=p_{1}\log\left(\frac{2p_{1}}{p_{1}+p_{2}}\right)+p_{2}\log\left(\frac{2p_{2}}{p_{1}+p_{2}}\right)$
$\displaystyle\overset{(c)}{<}p_{1}\left(\frac{2p_{1}}{p_{1}+p_{2}}-1\right)+p_{2}\left(\frac{2p_{2}}{p_{1}+p_{2}}-1\right)$
$\displaystyle=\frac{(p_{1}-p_{2})^{2}}{p_{1}+p_{2}}.$ (47)

The inequality $(c)$ follows as $\log(x)<x-1$ for $x>-1$. Thus, from (46) and
(47),

$\displaystyle\frac{\log\left(\frac{N-d_{2}+d_{1}+1}{N}\right)}{(p_{1}+p_{2})\
kl\left(\frac{p_{1}}{p_{1}+p_{2}},\frac{1}{2}\right)}>\frac{(p_{1}+p_{2})\log(2)}{(p_{1}-p_{2})}$
(48)

∎

###### Proof of Lemma 4.3.

The function

$f_{t}(\boldsymbol{d}^{\prime})=\left\\{\sum_{j\in\mathcal{K}^{(t)}}\int_{-1}^{S_{j}(t)}\log(d^{\prime}_{j}-v)dv-t\log\left(\sum_{i=1}^{K}d^{\prime}_{i}\right)\right\\}.$

The KKT conditions to find the supremum of $f_{t}(\boldsymbol{d}^{\prime})$
under the constraint $d^{\prime}_{a}-d^{\prime}_{b}\leq 0$ are listed as
follows for primal optimal point $\boldsymbol{d}^{*}$ and dual optimal point
$\lambda^{*}$

$\displaystyle d^{*}_{a}$ $\displaystyle\leq d^{*}_{b}$
$\displaystyle\lambda^{*}$ $\displaystyle\geq 0$
$\displaystyle\lambda^{*}(d^{*}_{a}-d^{*}_{b})$ $\displaystyle=0$
$\displaystyle\nabla
f_{t}(\boldsymbol{d}^{*})+\nabla\lambda^{*}(d^{*}_{a}-d^{*}_{b})$
$\displaystyle=0.$

So, for $j\in\mathcal{K}\setminus\\{a,b\\}$,

$\displaystyle\int_{-1}^{S_{j}(t)}\frac{1}{(d^{*}_{j}-y)}dy-\frac{t}{\left(\sum_{i=1}^{K}d^{*}_{i}\right)}$
$\displaystyle=0$
$\displaystyle\int_{d^{*}_{j}-S_{j}(t)}^{d^{*}_{j}+1}\frac{1}{x}dx-\frac{t}{\left(\sum_{i=1}^{K}d^{*}_{i}\right)}$
$\displaystyle=0$
$\displaystyle\log\left(\frac{d^{*}_{j}+1}{d^{*}_{j}-S_{j}(t)}\right)-\frac{t}{\left(\sum_{i=1}^{K}d^{*}_{i}\right)}$
$\displaystyle=0$

(ii) and for $j=a,b$

$\displaystyle\log\left(\frac{d^{*}_{a}+1}{d^{*}_{a}-S_{a}(t)}\right)-\frac{t}{\left(\sum_{i=1}^{K}d^{*}_{i}\right)}+\lambda$
$\displaystyle=0$
$\displaystyle\log\left(\frac{d^{*}_{b}+1}{d^{*}_{b}-S_{b}(t)}\right)-\frac{t}{\left(\sum_{i=1}^{K}d^{*}_{i}\right)}-\lambda$
$\displaystyle=0.$

From the first three KKT conditions we can see that either $\lambda^{*}=0$ or
$d^{*}_{a}-d^{*}_{b}=0$. If $\lambda^{*}=0$ then

$\displaystyle\frac{d^{*}_{j}+1}{d^{*}_{j}-S_{j}(t)}$
$\displaystyle=e^{\frac{t}{\left(\sum_{i=1}^{K}d^{*}_{i}\right)}}$
$\displaystyle
e^{\frac{-t}{\left(\sum_{i=1}^{K}d^{*}_{i}\right)}}\left(d^{*}_{j}+1\right)$
$\displaystyle=d^{*}_{j}-S_{j}(t)$ $\displaystyle d^{*}_{j}$
$\displaystyle=\frac{S_{j}(t)+e^{\frac{-t}{\left(\sum_{i=1}^{K}d^{*}_{i}\right)}}}{1-e^{\frac{-t}{\left(\sum_{i=1}^{K}d^{*}_{i}\right)}}}\text{
for all }j\in\mathcal{K}.$

Thus, when $S_{a}(t)>S_{b}(t)$, $d^{*}_{a}>d^{*}_{b}$. But this violates the
constraint. So, when $S_{a}(t)\geq S_{b}(t)$, taking $d^{*}_{a}=d^{*}_{b}$,
(i) for $j\in\mathcal{K}^{(t)}\setminus\\{a,b\\}$

$\displaystyle
d^{*}_{j}=\frac{S_{j}(t)+e^{\frac{-t}{\left(\sum_{i=1}^{K}d^{*}_{i}\right)}}}{1-e^{\frac{-t}{\left(\sum_{i=1}^{K}d^{*}_{i}\right)}}}\text{
for }j\in\mathcal{K}\setminus\\{a,b\\}$ (49)

(ii) and for $j=a,b$

$\displaystyle\log\left(\frac{(d^{*}_{a}+1)^{2}}{(d^{*}_{a}-S_{a}(t))(d^{*}_{a}-S_{b}(t))}\right)-\frac{2t}{\left(\sum_{i=1}^{K}d^{*}_{i}\right)}=0$
(50) $\displaystyle
e^{\frac{-2t}{\left(\sum_{i=1}^{K}d^{*}_{i}\right)}}(d^{*}_{a}+1)^{2}=(d^{*}_{a}-S_{a}(t))(d^{*}_{a}-S_{b}(t))$
$\displaystyle
d^{*}_{a}=d^{*}_{b}=\frac{S_{a}(t)+S_{b}(t)+2e^{\frac{-2t}{\left(\sum_{i=1}^{K}d^{*}_{i}\right)}}\pm
r\left(e^{\frac{-t}{\left(\sum_{i=1}^{K}d^{*}_{i}\right)}}\right)}{2\left(1-e^{\frac{-2t}{\left(\sum_{i=1}^{K}d^{*}_{i}\right)}}\right)}$
(51)

where
$r\left(e^{\frac{-t}{\left(\sum_{i=1}^{K}d^{\prime}_{i}\right)}}\right)=\sqrt{(S_{a}(t)-S_{b}(t))^{2}+4e^{\frac{-2t}{\left(\sum_{i=1}^{K}d^{\prime}_{i}\right)}}(1+S_{a}(t)+S_{b}(t)+S_{a}(t)S_{b}(t))}$.
Note: When $S_{a}(t)<S_{b}(t)$, by taking $\lambda^{*}=0$,
$d^{*}_{j}=\frac{S_{j}(t)+e^{\frac{-t}{\left(\sum_{i=1}^{K}d^{*}_{i}\right)}}}{1-e^{\frac{-t}{\left(\sum_{i=1}^{K}d^{*}_{i}\right)}}}$
for all $j\in\mathcal{K}$, the constraint $d^{*}_{a}\leq d^{*}_{b}$ is
satisfied. Therefore,

$\text{when
$S_{a}(t)<S_{b}(t)$,}\sup_{\boldsymbol{d}^{\prime}\in\mathbb{R}_{+}^{K}\colon
d^{\prime}_{a}\leq
d^{\prime}_{b}}f_{t}(\boldsymbol{d}^{\prime})=\sup_{\boldsymbol{d}^{\prime}\in\mathbb{R}_{+}^{K}}f_{t}(\boldsymbol{d}^{\prime}),$
(52)

the unconstrained supremum of $f_{t}(\boldsymbol{d}^{\prime})$.

Let $\gamma=e^{\frac{-t}{\left(\sum_{i=1}^{K}d^{\prime}_{i}\right)}}$ and
$\gamma_{0}=e^{\frac{-t}{\left(\sum_{i=1}^{K}d^{*}_{i}\right)}}$. By
substituting $\gamma$ in (49) and (51) in place of $\gamma_{0}$, we get the
expression of $d^{\prime}_{j}$, $d^{\prime}_{a}$ and $d^{\prime}_{b}$ in terms
of $\gamma$ as

$\displaystyle d^{\prime}_{j}$
$\displaystyle=\frac{S_{j}(t)+\gamma}{1-\gamma}\text{ for $j\neq a,b$ }\text{
and}$ (53) $\displaystyle d^{\prime}_{a}$
$\displaystyle=d^{\prime}_{b}=\frac{S_{a}(t)+S_{b}(t)+2\gamma^{2}\pm
r(\gamma)}{2(1-\gamma^{2})},$ (54)

where
$r\left(\gamma\right)=\sqrt{(S_{a}(t)-S_{b}(t))^{2}+4\gamma^{2}(1+S_{a}(t)+S_{b}(t)+S_{a}(t)S_{b}(t))}$.
Therefore, instead of a $K$-dimensional optimization problem we have a one-
dimensional optimization problem to find the optimal $\gamma_{0}$.

Claim:
$d^{\prime}_{a}=d^{\prime}_{b}=\frac{S_{a}(t)+S_{b}(t)+2\gamma^{2}-r(\gamma)}{2(1-\gamma^{2})}$
is not a valid solution.

###### Proof.

From (50) we can see that the valid value of $d^{\prime}_{a}$ is greater than
$S_{a}(t)$ at the critical point. We compare
$\frac{S_{a}(t)+S_{b}(t)+2\gamma^{2}-r(\gamma)}{2(1-\gamma^{2})}$ to
$S_{a}(t)$. For

$\displaystyle\frac{S_{a}(t)+S_{b}(t)+2\gamma^{2}-r(\gamma)}{2(1-\gamma^{2})}\leq
S_{a}(t)$ $\displaystyle S_{a}(t)+S_{b}(t)+2\gamma^{2}-r(\gamma)\leq
2S_{a}(t)(1-\gamma^{2})$ $\displaystyle
S_{a}(t)+S_{b}(t)+2\gamma^{2}-2S_{a}(t)+2S_{a}(t)\gamma^{2}\leq r(\gamma)$
$\displaystyle\left(\left(S_{b}(t)-S_{a}(t)\right)+2\gamma^{2}(1+S_{a}(t))\right)^{2}$
$\displaystyle\hskip
85.35826pt\leq(S_{a}(t)-S_{b}(t))^{2}+4\gamma^{2}(1+S_{a}(t)+S_{b}(t)+S_{a}(t)S_{b}(t))$
$\displaystyle 4\gamma^{4}(1+S_{a}(t))^{2}$ $\displaystyle\hskip
42.67912pt\leq
4\gamma^{2}(1+S_{a}(t)+S_{b}(t)+S_{a}(t)S_{b}(t)+(S_{a}(t)-S_{b}(t))(1+S_{a}(t)))$
$\displaystyle\gamma^{2}-1\leq 0$ $\displaystyle\gamma\leq 1.$

From the definition of $\gamma$ it is between $0$ and $1$. From the above
equation we can see that $\mathcal{S}_{a}(t)\geq$
$\frac{S_{a}(t)+S_{b}(t)+2\gamma^{2}-r(\gamma)}{2(1-\gamma^{2})}$ when
$\gamma\leq 1$. So
$\frac{S_{a}(t)+S_{b}(t)+2\gamma^{2}-r(\gamma)}{2(1-\gamma^{2})}$ is not a
valid solution. ∎

Let $N^{(a,b)}(\gamma)=\sum_{i=1}^{K}d^{\prime}_{i}$ be the sum of
$d^{\prime}_{j}$s written in terms of $\gamma$ given in (53) and (54).

$N^{(a,b)}(\gamma)=\frac{\sum_{j\in\mathcal{K}^{(t)}\setminus\\{a,b\\}}S_{j}(t)+\gamma(K^{(t)}-2)}{1-\gamma}+\frac{S_{a}(t)+S_{b}(t)+2\gamma^{2}+r(\gamma)}{(1-\gamma^{2})}$
(55)

Recall that
$\gamma=e^{\frac{-t}{\left(\sum_{i=1}^{K}d^{\prime}_{i}\right)}}=e^{\frac{-t}{\left(N^{(a,b)}(\gamma)\right)}}$.
Combining the expression of $N^{(a,b)}(\gamma)$ and the definition of
$\gamma$, the value of $\gamma$ at the critical point is given by,

$\gamma_{0}=\exp\left(\frac{-t}{\frac{\sum_{j\in\mathcal{K}^{(t)}\setminus\\{a,b\\}}S_{j}(t)+\gamma_{0}(K^{(t)}-2)}{1-\gamma_{0}}+\frac{S_{a}(t)+S_{b}(t)+2\gamma_{0}^{2}+r(\gamma_{0})}{(1-\gamma_{0}^{2})}}\right).$
(56)

From the expression of $\gamma_{0}$ we get

$\displaystyle\log\left(\frac{1}{\gamma_{0}}\right)=\frac{t}{\frac{\sum_{j\in\mathcal{K}^{(t)}\setminus\\{a,b\\}}S_{j}(t)+\gamma_{0}(K^{(t)}-2)}{1-\gamma_{0}}+\frac{S_{a}(t)+S_{b}(t)+2\gamma_{0}^{2}+r(\gamma_{0})}{(1-\gamma_{0}^{2})}}$
$\displaystyle\log\left(\frac{1}{\gamma_{0}}\right)\Bigg{(}\frac{\sum_{j\in\mathcal{K}^{(t)}\setminus\\{a,b\\}}S_{j}(t)+\gamma_{0}(K^{(t)}-2)}{1-\gamma_{0}}+\frac{S_{a}(t)+S_{b}(t)+2\gamma_{0}^{2}+r(\gamma_{0})}{(1-\gamma_{0}^{2})}\Bigg{)}-t=g(\gamma_{0})=0.$

######  Lemma B.1.

$g_{1}(\gamma)=\log\left(\frac{1}{\gamma}\right)\left(\frac{\sum_{j\in\mathcal{K}^{(t)}\setminus\\{a,b\\}}S_{j}(t)+\gamma(K^{(t)}-2)}{1-\gamma}+\frac{S_{a}(t)+S_{b}(t)+2\gamma^{2}+r(\gamma)}{(1-\gamma^{2})}\right)$
is a decreasing function of $\gamma$.

###### Proof.

Let
$h_{1}(\gamma)=\log\left(\frac{1}{\gamma}\right)\frac{\sum_{j\in\mathcal{K}^{(t)}\setminus\\{a,b\\}}S_{j}(t)+\gamma(K^{(t)}-2)}{1-\gamma}$.
The derivative of $h_{1}(\gamma)$ with respect to $\gamma$ is

$\displaystyle h^{\prime}_{1}(\gamma)$
$\displaystyle=\log\left(\frac{1}{\gamma}\right)\frac{\sum_{j\in\mathcal{K}^{(t)}\setminus\\{a,b\\}}S_{j}(t)+\gamma(K^{(t)}-2)}{(1-\gamma)^{2}}$
$\displaystyle\hskip
42.67912pt+\log\left(\frac{1}{\gamma}\right)\frac{(K^{(t)}-2)}{1-\gamma}-\frac{\sum_{j\in\mathcal{K}^{(t)}\setminus\\{a,b\\}}S_{j}(t)+\gamma(K^{(t)}-2)}{\gamma(1-\gamma)}$
$\displaystyle h^{\prime}_{1}(\gamma)(1-\gamma)$
$\displaystyle=\log\left(\frac{1}{\gamma}\right)\frac{\sum_{j\in\mathcal{K}^{(t)}\setminus\\{a,b\\}}S_{j}(t)+\gamma(K^{(t)}-2)}{1-\gamma}$
$\displaystyle\hskip
42.67912pt+\log\left(\frac{1}{\gamma}\right)(K^{(t)}-2)-\frac{\sum_{j\in\mathcal{K}^{(t)}\setminus\\{a,b\\}}S_{j}(t)+\gamma(K^{(t)}-2)}{\gamma}$
$\displaystyle h^{\prime}_{1}(\gamma)(1-\gamma)$
$\displaystyle=\sum_{j\in\mathcal{K}^{(t)}\setminus\\{a,b\\}}S_{j}(t)\left(\frac{\log\left(\frac{1}{\gamma}\right)}{1-\gamma}-\frac{1}{\gamma}\right)+(K^{(t)}-2)\left(\frac{\log\left(\frac{1}{\gamma}\right)}{1-\gamma}-1\right).$

For $h_{1}(\gamma)$ to be a decreasing function $\gamma$, we want

$\displaystyle\sum_{j\in\mathcal{K}^{(t)}\setminus\\{a,b\\}}S_{j}(t)\left(\frac{\log\left(\frac{1}{\gamma}\right)}{1-\gamma}-\frac{1}{\gamma}\right)+(K^{(t)}-2)\left(\frac{\log\left(\frac{1}{\gamma}\right)}{1-\gamma}-1\right)\leq
0$
$\displaystyle(K^{(t)}-2)\leq\sum_{j\in\mathcal{K}^{(t)}\setminus\\{a,b\\}}S_{j}(t)\underbrace{\frac{\left(\frac{1}{\gamma}-\frac{\log\left(\frac{1}{\gamma}\right)}{1-\gamma}\right)}{\left(\frac{\log\left(\frac{1}{\gamma}\right)}{1-\gamma}-1\right)}}_{\nu_{\gamma}}.$

By comparing the ratio $\nu_{\gamma}$ to one we get

$\displaystyle\frac{\left(\frac{1}{\gamma}-\frac{\log\left(\frac{1}{\gamma}\right)}{1-\gamma}\right)}{\left(\frac{\log\left(\frac{1}{\gamma}\right)}{1-\gamma}-1\right)}\geq
1$
$\displaystyle\frac{1}{\gamma}-\frac{\log\left(\frac{1}{\gamma}\right)}{1-\gamma}\geq\frac{\log\left(\frac{1}{\gamma}\right)}{1-\gamma}-1$
$\displaystyle\frac{1+\gamma}{\gamma}\geq
2\frac{\log\left(\frac{1}{\gamma}\right)}{1-\gamma}$ $\displaystyle
2\gamma\frac{\log\left(\frac{1}{\gamma}\right)}{1-\gamma^{2}}\leq 1$

So $2\gamma\frac{\log\left(\frac{1}{\gamma}\right)}{1-\gamma^{2}}$ should be
less than one for $\nu_{\gamma}$ to be geater than one.

######  Lemma B.2.

The ratio $2\gamma\frac{\log\left(\frac{1}{\gamma}\right)}{1-\gamma^{2}}$ is
less than or equal to 1.

###### Proof.

Let $h_{0}(\gamma)=1-\gamma^{2}-2\gamma\log(\frac{1}{\gamma})$. The function

$h_{0}(\gamma)\begin{cases}=0&\text{ at }\gamma=1\\\ \to 1&\text{as}\gamma\to
0.\end{cases}$

The derivative of $h_{0}(\gamma)$ is

$\displaystyle\frac{dh_{0}(\gamma)}{d\gamma}$
$\displaystyle=-2\gamma-2\log\left(\frac{1}{\gamma}\right)+2$
$\displaystyle=2\left(1-\gamma-\log\left(\frac{1}{\gamma}\right)\right)$
$\displaystyle=2(1-\gamma+\log(\gamma))$ $\displaystyle\leq 0\text{ as
}\log(\gamma)\leq\gamma-1\text{ for }\gamma>0.$

Thus $1-\gamma^{2}>2\gamma\log(\frac{1}{\gamma})$. ∎

From the above Lemma we can conclude that $\nu_{\gamma}\geq 1$. Therefore,
$h_{1}(\gamma)$ is a decreasing function $\gamma$ if
$(K^{(t)}-2)\leq\sum_{j\in\mathcal{K}^{(t)}\setminus\\{a,b\\}}S_{j}(t)$. This
is true since $\mathcal{K}^{(t)}$ is the set of integers in $\mathcal{K}$ for
which $S_{j}(t)>0$ and $K^{(t)}$ is the number of communities for which
$S_{j}(t)>0$.
Let
$h_{2}(\gamma)=\log\left(\frac{1}{\gamma}\right)\frac{S_{a}(t)+S_{b}(t)+2\gamma^{2}+r(\gamma)}{(1-\gamma^{2})}$.
The derivative of $h_{2}(\gamma)$ is

$\displaystyle h^{\prime}_{2}(\gamma)$
$\displaystyle=\frac{\log\left(\frac{1}{\gamma}\right)}{1-\gamma^{2}}(4\gamma+r^{\prime}(\gamma))+\frac{2\gamma\log\left(\frac{1}{\gamma}\right)}{(1-\gamma^{2})^{2}}(S_{a}(t)+S_{b}(t)+2\gamma^{2}+r(\gamma))$
$\displaystyle\hskip
113.81102pt-\frac{1}{\gamma(1-\gamma^{2})}(S_{a}(t)+S_{b}(t)+2\gamma^{2}+r(\gamma))$
$\displaystyle h^{\prime}_{2}(\gamma)(1-\gamma^{2})$
$\displaystyle=\underbrace{\frac{4\gamma\log\left(\frac{1}{\gamma}\right)}{1-\gamma^{2}}-2\gamma}_{pt_{1}}+\underbrace{\left(\frac{2\gamma\log\left(\frac{1}{\gamma}\right)}{1-\gamma^{2}}-\frac{1}{\gamma}\right)(S_{a}(t)+S_{b}(t))}_{pt_{2}}$
$\displaystyle\hskip
28.45274pt+\underbrace{\left(\frac{2\gamma\log\left(\frac{1}{\gamma}\right)}{1-\gamma^{2}}-\frac{1}{\gamma}\right)r(\gamma)}_{pt_{3}}+\underbrace{\log\left(\frac{1}{\gamma}\right)r^{\prime}(\gamma)}_{pt_{4}}.$

By multiplying the term $(S_{a}(t)-S_{b}(t))^{2}$ by $\gamma^{2}$ in
$r(\gamma)$ we get

$\displaystyle
r(\gamma)=\sqrt{(S_{a}(t)-S_{b}(t))^{2}+4\gamma^{2}(1+S_{a}(t)+S_{b}(t)+S_{a}(t)S_{b}(t))}$
$\displaystyle
r(\gamma)>\sqrt{(S_{a}(t)-S_{b}(t))^{2}\gamma^{2}+4\gamma^{2}(1+S_{a}(t)+S_{b}(t)+S_{a}(t)S_{b}(t))}$
$\displaystyle r(\gamma)>\gamma(S_{a}(t)+S_{b}(t)+2)\text{ as the value of
$\gamma$ is between $0$ and $1$.}$ (57)

The derivative of $r(\gamma)$ is

$\displaystyle r^{\prime}(\gamma)$
$\displaystyle=\frac{4\gamma(1+S_{a}(t)+S_{b}(t)+S_{a}(t)S_{b}(t))}{\sqrt{(S_{a}(t)-S_{b}(t))^{2}+4\gamma^{2}(1+S_{a}(t)+S_{b}(t)+S_{a}(t)S_{b}(t))}}$
$\displaystyle\leq\frac{4\gamma(S_{a}(t)+S_{b}(t))\frac{(1+S_{a}(t)+S_{b}(t)+S_{a}(t)S_{b}(t))}{(S_{a}(t)+S_{b}(t))}}{\sqrt{(4\gamma^{2}(1+S_{a}(t)+S_{b}(t)+S_{a}(t)S_{b}(t))}}$
$\displaystyle\leq
2(S_{a}(t)+S_{b}(t))\frac{\sqrt{1+S_{a}(t)+S_{b}(t)+S_{a}(t)S_{b}(t))}}{(S_{a}(t)+S_{b}(t))}$
$\displaystyle\leq 2(S_{a}(t)+S_{b}(t))$

From Lemma B.2, we know that
$2\gamma\frac{\log\left(\frac{1}{\gamma}\right)}{1-\gamma^{2}}\leq
1\leq\frac{1}{\gamma}$. So, using the above bounds on $r(\gamma)$ and
$r^{\prime}(\gamma)$ in the expression of
$h^{\prime}_{2}(\gamma)(1-\gamma^{2})$ we get

$\displaystyle h^{\prime}_{2}(\gamma)(1-\gamma^{2})$
$\displaystyle\leq\frac{4\gamma\log\left(\frac{1}{\gamma}\right)}{1-\gamma^{2}}-2\gamma+\left(\frac{2\gamma\log\left(\frac{1}{\gamma}\right)}{1-\gamma^{2}}-\frac{1}{\gamma}\right)(S_{a}(t)+S_{b}(t))$
$\displaystyle\hskip
28.45274pt+\left(\frac{2\gamma\log\left(\frac{1}{\gamma}\right)}{1-\gamma^{2}}-\frac{1}{\gamma}\right)(S_{a}(t)+S_{b}(t)+2)\gamma+2\log\left(\frac{1}{\gamma}\right)(S_{a}(t)+S_{b}(t))$
$\displaystyle=\frac{4\gamma(1+\gamma)\log\left(\frac{1}{\gamma}\right)}{1-\gamma^{2}}-2(1+\gamma)+(S_{a}(t)+S_{b}(t))\left(\frac{2\gamma\log\left(\frac{1}{\gamma}\right)}{1-\gamma^{2}}-\frac{1}{\gamma}\right)(1+\gamma)$
$\displaystyle\hskip
85.35826pt+2\log\left(\frac{1}{\gamma}\right)(S_{a}(t)+S_{b}(t))$
$\displaystyle=2(1+\gamma)\left(\frac{2\gamma\log\left(\frac{1}{\gamma}\right)}{1-\gamma^{2}}-1\right)+(S_{a}(t)+S_{b}(t))\frac{1+\gamma}{\gamma}\left(\frac{2\gamma\log\left(\frac{1}{\gamma}\right)}{1-\gamma^{2}}-1\right)$

From Lemma B.2,
$\frac{2\gamma\log\left(\frac{1}{\gamma}\right)}{1-\gamma^{2}}\leq 1$. So the
upper bound on $h^{\prime}_{2}(\gamma)$ is negative. Thus we can conclude that
$h_{2}(\gamma)$ is a decreasing function of $\gamma$. Since $h_{1}(\gamma)$
and $h_{2}(\gamma)$ are decreasing functions of $\gamma$,
$g_{1}(\gamma)=h_{1}(\gamma)+h_{2}(\gamma)$ is also a decreasing function of
$\gamma$. ∎

Thus a unique value of $\gamma$ is obtained by equating $g_{1}(\gamma)$ to
$t$. We get the optimal values of $\boldsymbol{d}^{\prime}$ by substituting
$\gamma_{0}$ in (53) and (54). We will look at the second order conditions to
check whether the critical point is indeed a local maximum. In order to do so
we calculate the following bordered Hessian matrix. Let $a=1$, $b=2$. The
second order derivatives of $f_{t}(\boldsymbol{d}^{\prime})$ are

$\displaystyle\frac{\partial^{2}f_{t}(\boldsymbol{d}^{\prime})}{\partial
d^{{}^{\prime}2}_{j}}$
$\displaystyle=\frac{1}{d^{\prime}_{j}+1}-\frac{1}{d^{\prime}_{j}-S_{j}(t)}+\frac{t}{\left(\sum_{i=1}^{K}d^{\prime}_{i}\right)^{2}}$
$\displaystyle=\frac{-(S_{j}(t)+1)}{(d^{\prime}_{j}+1)(d^{\prime}_{j}-S_{j}(t))}+\frac{t}{\left(\sum_{i=1}^{K}d^{\prime}_{i}\right)^{2}}\text{
for }j\in\mathcal{K}$
$\displaystyle\frac{\partial^{2}f_{t}(\boldsymbol{d}^{\prime})}{\partial
d^{\prime}_{j}d^{\prime}_{k}}$
$\displaystyle=\frac{t}{\left(\sum_{i=1}^{K}d^{\prime}_{i}\right)^{2}}\text{
for }j\neq k\in\mathcal{K}$

Under the constraint
$h^{1,2}(\boldsymbol{d}^{\prime})=d^{\prime}_{1}-d^{\prime}_{2}\leq 0$ the
bordered Hessian matrix for the maximization of
$f_{t}(\boldsymbol{d}^{\prime})$ is constructed as

$\displaystyle H_{f_{\boldsymbol{d^{\prime}}}(t)}$
$\displaystyle=\begin{bmatrix}0&\frac{\partial
h^{1,2}(\boldsymbol{d}^{\prime})}{\partial d^{\prime}_{1}}&\frac{\partial
h^{1,2}(\boldsymbol{d}^{\prime})}{\partial
d^{\prime}_{2}}&\ldots&\frac{\partial
h^{1,2}(\boldsymbol{d}^{\prime})}{\partial d^{\prime}_{K}}\\\ \frac{\partial
h^{1,2}(\boldsymbol{d}^{\prime})}{\partial
d^{\prime}_{1}}&\frac{\partial^{2}f_{t}(\boldsymbol{d}^{\prime})}{\partial
d^{{}^{\prime}2}_{1}}&\frac{\partial^{2}f_{t}(\boldsymbol{d}^{\prime})}{\partial
d^{\prime}_{2}d^{\prime}_{1}}&\ldots&\frac{\partial^{2}f_{t}(\boldsymbol{d}^{\prime})}{\partial
d^{\prime}_{k}d^{\prime}_{1}}\\\ \frac{\partial
h^{1,2}(\boldsymbol{d}^{\prime})}{\partial
d^{\prime}_{2}}&\frac{\partial^{2}f_{t}(\boldsymbol{d}^{\prime})}{\partial
d^{\prime}_{1}d^{\prime}_{2}}&\frac{\partial^{2}f_{t}(\boldsymbol{d}^{\prime})}{\partial
d^{{}^{\prime}2}_{2}}&\ldots&\frac{\partial^{2}f_{t}(\boldsymbol{d}^{\prime})}{\partial
d^{\prime}_{k}d^{\prime}_{2}}\\\ \vdots&\vdots&\vdots&\ddots&\vdots\\\
\frac{\partial h^{1,2}(\boldsymbol{d}^{\prime})}{\partial
d^{\prime}_{K}}&\frac{\partial^{2}f_{t}(\boldsymbol{d}^{\prime})}{\partial
d^{\prime}_{1}d^{\prime}_{k}}&\frac{\partial^{2}f_{t}(\boldsymbol{d}^{\prime})}{\partial
d^{\prime}_{2}d^{\prime}_{K}}&\ldots&\frac{\partial^{2}f_{t}(\boldsymbol{d}^{\prime})}{\partial
d^{{}^{\prime}2}_{k}}\end{bmatrix}$
$\displaystyle=\frac{t}{\left(\sum_{i=1}^{K}d^{\prime}_{i}\right)^{2}}\begin{bmatrix}0&-R^{\prime}_{0}&R^{\prime}_{0}&0&\ldots&0\\\
-R^{\prime}_{0}&1-R^{\prime}_{1}&1&1&\ldots&1\\\
R^{\prime}_{0}&1&1-R^{\prime}_{2}&1&\ldots&1\\\
\vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\\
\vdots&\vdots&\vdots&\vdots&\ddots&\vdots\\\
0&1&1&1&\ldots&1-R^{\prime}_{K}\end{bmatrix}$

where $R^{\prime}_{0}=\frac{\left(\sum_{i=1}^{K}d^{\prime}_{i}\right)^{2}}{t}$
and
$R^{\prime}_{j}=\frac{\frac{(S_{j}(t)+1)}{(d^{\prime}_{j}+1)(d^{\prime}_{j}-S_{j}(t))}}{\frac{t}{\left(\sum_{i=1}^{K}d^{\prime}_{i}\right)^{2}}}$.

######  Lemma B.3.

The last $K-1$ leading principal minors of the Bordered Hessain matrix
alternate in sign and the sign of the $l^{t}h$ principal minor is
$(-1)^{(l+1)}$.

###### Proof.

The $l^{th}$ principal minor of $H_{f_{\boldsymbol{d^{\prime}}}(t)}$ is

$|M^{p2}_{l}|=(-1)^{l+1}R_{0}^{{}^{\prime}2}(R^{\prime}_{1}+R^{\prime}_{2})R^{\prime}_{3}\ldots
R^{\prime}_{l-1}\left(1-\frac{4}{R^{\prime}_{1}+R^{\prime}_{2}}-\frac{1}{R^{\prime}_{3}}\ldots-\frac{1}{R^{\prime}_{l-1}}\right).$
(58)

At the critical point, for $j\in\mathcal{K}\setminus\\{1,2\\}$,
$d^{\prime}_{j}=\frac{S_{j}(t)+\gamma_{0}}{1-\gamma_{0}}$ and
$\frac{t}{\left(\sum_{i=1}^{K}d^{\prime}_{i}\right)}=\log\left(\frac{1}{\gamma_{0}}\right)$
(from (55) and (56)). So,

$\displaystyle\frac{1}{R^{\prime}_{j}}$
$\displaystyle=\frac{(d^{\prime}_{j}+1)(d^{\prime}_{j}-S_{j}(t))t}{(S_{j}(t)+1)\left(\sum_{i=1}^{K}d^{\prime}_{i}\right)^{2}}$
$\displaystyle=\frac{\gamma_{0}\log\left(\frac{1}{\gamma_{0}}\right)(S_{j}(t)+1)}{\left(\sum_{i=1}^{K}d^{\prime}_{i}\right)(1-\gamma_{0})^{2}}.$
(59)

Let $p=\frac{(d^{\prime}_{1}-S_{1}(t))}{(d^{\prime}_{1}+1)}$ and
$q=\frac{(d^{\prime}_{1}-S_{2}(t))}{(d^{\prime}_{1}+1)}$. For $j=1,2$ at the
critical point, from (50) we have
$\frac{(d^{\prime}_{1}-S_{1}(t))(d^{\prime}_{1}-S_{2}(t))}{(d^{\prime}_{1}+1)^{2}}=pq=\gamma_{0}^{2}$.
So,

$\displaystyle\frac{(S_{1}(t)+1)}{(d^{\prime}_{1}+1)(d^{\prime}_{1}-S_{1}(t))}+\frac{(S_{2}(t)+1)}{(d^{\prime}_{1}+1)(d^{\prime}_{1}-S_{2}(t))}$
$\displaystyle=\frac{(S_{1}(t)+1)(d^{\prime}_{1}-S_{2}(t))+(S_{2}(t)+1)(d^{\prime}_{1}-S_{1}(t))}{(d^{\prime}_{1}+1)(d^{\prime}_{1}-S_{1}(t))(d^{\prime}_{1}-S_{2}(t))}$
$\displaystyle=\frac{(1-p)q+(1-q)p}{(d^{\prime}_{1}+1)\gamma_{0}^{2}}$
$\displaystyle=\frac{(1-p)q+(1-q)p}{(d^{\prime}_{1}+1)\gamma_{0}^{2}}$
$\displaystyle=\frac{\frac{1}{p}+\frac{p}{\gamma_{0}^{2}}-2}{(d^{\prime}_{1}+1)}.$

Let $f(p)=\frac{1}{p}+\frac{p}{\gamma_{0}^{2}}-2$. The derivatve of $f(p)$,
$f^{\prime}(p)=\frac{-1}{p^{2}}+\frac{1}{\gamma_{0}^{2}}=0$ at $p=\gamma_{0}$
and $f^{\prime\prime}(p)>0$, so $f(p)$ takes minimum vale at $p=\gamma_{0}$
and $\min_{p}f(p)=\frac{2(1-\gamma_{0})}{\gamma_{0}}$. Therefore,
$\frac{(S_{1}(t)+1)}{(d^{\prime}_{1}+1)(d^{\prime}_{1}-S_{1}(t))}+\frac{(S_{2}(t)+1)}{(d^{\prime}_{1}+1)(d^{\prime}_{1}-S_{2}(t))}>\frac{2(1-\gamma_{0})}{(d^{\prime}_{1}+1)\gamma_{0}}$.
Using this bound on $\frac{4}{R^{\prime}_{1}+R^{\prime}_{2}}$ we get

$\displaystyle\frac{4}{R^{\prime}_{1}+R^{\prime}_{2}}$
$\displaystyle=\frac{4\log\left(\frac{1}{\gamma_{0}}\right)}{\left(\sum_{i=1}^{K}d^{\prime}_{i}\right)\left(\frac{(S_{1}(t)+1)}{(d^{\prime}_{1}+1)(d^{\prime}_{1}-S_{1}(t))}+\frac{(S_{2}(t)+1)}{(d^{\prime}_{1}+1)(d^{\prime}_{1}-S_{2}(t))}\right)}$
$\displaystyle\leq\frac{2\gamma_{0}\log\left(\frac{1}{\gamma_{0}}\right)(d^{\prime}_{1}+1)}{(1-\gamma_{0})\left(\sum_{i=1}^{K}d^{\prime}_{i}\right)}$
$\displaystyle=\frac{2\gamma_{0}\log\left(\frac{1}{\gamma_{0}}\right)(d^{\prime}_{1}+1)}{(1-\gamma_{0})\left(\sum_{i=1}^{K}d^{\prime}_{i}\right)}$
$\displaystyle=\frac{\gamma_{0}\log\left(\frac{1}{\gamma_{0}}\right)(S_{a}(t)+S_{b}(t)+r(\gamma_{0})+2)}{(1-\gamma_{0})(1-\gamma_{0}^{2})\left(\sum_{i=1}^{K}d^{\prime}_{i}\right)}$
$\displaystyle=\frac{\gamma_{0}\log\left(\frac{1}{\gamma_{0}}\right)(S_{a}(t)+S_{b}(t)+r(\gamma_{0})+2)}{(1+\gamma_{0})(1-\gamma_{0})^{2}\left(\sum_{i=1}^{K}d^{\prime}_{i}\right)}.$
(60)

Adding $\frac{1}{R_{j}}$ for all $j\in\mathcal{K}\setminus\\{1,2\\}$ and the
upper bound on $\frac{4}{R_{1}+R_{2}}$ from equations (59) and (60) gives

$\displaystyle\frac{4}{R^{\prime}_{1}+R^{\prime}_{2}}+\sum_{j\in\mathcal{K}\setminus\\{1,2\\}}\frac{1}{R_{j}}$
$\displaystyle\leq\frac{\gamma_{0}\log\left(\frac{1}{\gamma_{0}}\right)(S_{j}(t)+1)}{\left(\sum_{i=1}^{K}d^{\prime}_{i}\right)(1-\gamma_{0})^{2}}+\frac{\gamma_{0}\log\left(\frac{1}{\gamma_{0}}\right)(S_{1}(t)+S_{2}(t)+r(\gamma_{0})+2)}{(1+\gamma_{0})(1-\gamma_{0})^{2}\left(\sum_{i=1}^{K}d^{\prime}_{i}\right)}$
$\displaystyle=\frac{\gamma_{0}\log\left(\frac{1}{\gamma_{0}}\right)}{(1-\gamma_{0})^{2}\left(\sum_{i=1}^{K}d^{\prime}_{i}\right)}\left(\sum_{j\in\mathcal{K}\setminus\\{1,2\\}}(S_{j}(t)+1)+\frac{(S_{1}(t)+S_{2}(t)+r(\gamma_{0})+2)}{(1+\gamma_{0})}\right)$
$\displaystyle=\frac{\gamma_{0}\log\left(\frac{1}{\gamma_{0}}\right)}{(1-\gamma_{0})^{2}}\frac{\sum_{j\in\mathcal{K}\setminus\\{1,2\\}}(S_{j}(t)+1)+\frac{(S_{a}(t)+S_{b}(t)+r(\gamma_{0})+2)}{(1+\gamma_{0})}}{\frac{\sum_{j\in\mathcal{K}^{(t)}\setminus\\{1,2\\}}S_{j}(t)+\gamma_{0}(K^{(t)}-2)}{1-\gamma_{0}}+\frac{S_{1}(t)+S_{2}(t)+2\gamma_{0}^{2}+r(\gamma_{0})}{(1-\gamma_{0}^{2})}}\text{
(from \eqref{N_gamma})}$
$\displaystyle=\frac{\gamma_{0}\log\left(\frac{1}{\gamma_{0}}\right)}{(1-\gamma_{0})}\frac{\sum_{j\in\mathcal{K}\setminus\\{1,2\\}}S_{j}(t)+\gamma_{0}(K^{(t)}-2)+(1-\gamma_{0})(K^{(t)}-2)+\frac{(S_{1}(t)+S_{2}(t)+2\gamma_{0}^{2}+r(\gamma_{0})+2-2\gamma_{0}^{2})}{(1+\gamma_{0})}}{\sum_{j\in\mathcal{K}^{(t)}\setminus\\{1,2\\}}S_{j}(t)+\gamma_{0}(K^{(t)}-2)+\frac{S_{1}(t)+S_{2}(t)+2\gamma_{0}^{2}+r(\gamma_{0})}{(1+\gamma_{0})}}$
$\displaystyle=\frac{\gamma_{0}\log\left(\frac{1}{\gamma_{0}}\right)}{(1-\gamma_{0})}\left(1+\frac{(1-\gamma_{0})(K^{(t)}-2)+2(1-\gamma_{0})}{\sum_{j\in\mathcal{K}^{(t)}\setminus\\{1,2\\}}S_{j}(t)+\gamma_{0}(K^{(t)}-2)+\frac{S_{1}(t)+S_{2}(t)+2\gamma_{0}^{2}+r(\gamma_{0})}{(1+\gamma_{0})}}\right)$

Applying the lower bound on $r(\gamma)$ from (57) in the above equation and
simplifying gives

$\displaystyle\frac{4}{R^{\prime}_{1}+R^{\prime}_{2}}+\sum_{j\in\mathcal{K}\setminus\\{1,2\\}}\frac{1}{R_{j}}$
$\displaystyle\leq\frac{\gamma_{0}\log\left(\frac{1}{\gamma_{0}}\right)}{(1-\gamma_{0})}\left(1+\frac{K^{(t)}(1-\gamma_{0})}{\sum_{j\in\mathcal{K}^{(t)}\setminus\\{1,2\\}}S_{j}(t)+\gamma_{0}(K^{(t)}-2)+\frac{S_{1}(t)+S_{2}(t)+2\gamma_{0}^{2}+\gamma_{0}(S_{1}(t)+S_{2}(t)+2)}{(1+\gamma_{0})}}\right)$
$\displaystyle=\frac{\gamma_{0}\log\left(\frac{1}{\gamma_{0}}\right)}{(1-\gamma_{0})}\left(1+\frac{K^{(t)}(1-\gamma_{0})}{\sum_{j\in
K^{(t)}}S_{j}(t)+K^{(t)}\gamma_{0}}\right)$
$\displaystyle<\frac{\gamma_{0}\log\left(\frac{1}{\gamma_{0}}\right)}{(1-\gamma_{0})}\left(1+\frac{K^{(t)}(1-\gamma_{0})}{K^{(t)}(1+\gamma_{0})}\right)$
$\displaystyle=\frac{2\gamma_{0}\log\left(\frac{1}{\gamma_{0}}\right)}{(1-\gamma_{0}^{2})}<1\text{
(from lemma \ref{lemma_diff})}.$

So, from (58) and the bound above we can conclude that the last (K-1) leading
principal minors of the bordered Hessian matrix alternate in sign and the sign
of the $l^{th}$ principal minor is $(-1)^{l+1}$. This is a sufficient
condition for the critical point to be local maximum. This lemma is proved for
$a=1,b=2$. It can similarly be proved for any $a\in\mathcal{K}$ and
$b\in\mathcal{K}\setminus\\{a\\}$. ∎

From lemma B.3 we can say that the critical point is a local maximum. Since
there is a unique value of $\gamma$ for which $g(\gamma)=g_{1}(\gamma)-t$, the
critical point is indeed a global maximum. When $\gamma\to 1$, the ratio
$\frac{\log\left(\frac{1}{\gamma}\right)}{1-\gamma}$ tends to 1. So,

$\displaystyle g_{1}(\gamma)$
$\displaystyle=\frac{\log\left(\frac{1}{\gamma}\right)}{1-\gamma}\left(\sum_{j\in\mathcal{K}^{(t)}\setminus\\{a,b\\}}S_{j}(t)+\gamma(K^{(t)}-1)+\frac{S_{a}(t)+S_{b}(t)+2\gamma^{2}+r(\gamma)}{1+\gamma}\right)$
$\displaystyle\overset{(u)}{\to}\sum_{j\in\mathcal{K}}S_{j}(t)+K^{(t)}\text{
as }\gamma\to 1.$ (61)

The limit $(u)$ holds because from definition of $r(\gamma)$,
$r(1)=S_{a}(t)+S_{b}(t)+2$ and
$\sum_{j\in\mathcal{K}^{(t)}}S_{j}(t)=\sum_{j\in\mathcal{K}}S_{j}(t)$. Thus,
the zero of $g(\gamma)$ for $t=\sum_{j\in\mathcal{K}}S_{j}(t)+K^{(t)}$ is
obtained at $\gamma\to 1$. This implies that the values of $d^{\prime}_{j}$
for all $j\in\mathcal{K}$ tend to infinity. Thus the identity based rule
applies for $t>\sum_{j\in\mathcal{K}}S_{j}(t)+K^{(t)}.$ ∎

###### Proof of Lemma 4.4.

Let $t>\sum_{j\in\mathcal{K}}S_{j}(t)+K^{(t)}$. When $S_{a}(t)>S_{b}(t)$, from
(16), Lemma 4.3 and (4.2)

$\displaystyle Y_{a,b}(t)=$
$\displaystyle\log\left(\sum_{\boldsymbol{d}^{\prime}\in\mathcal{S}_{\alpha}(t)}\frac{\prod_{j=1}^{K}\prod_{l=0}^{S_{j}(t)-1}(d^{\prime}_{j}-l){\mathbb{P}}_{\boldsymbol{d}^{\prime}\sim\mathcal{D}}(\boldsymbol{d}^{\prime})}{(\sum_{i=1}^{K}d^{\prime}_{i})^{t}}\right)-\sup_{\boldsymbol{d}^{\prime}\in\mathbb{R}_{+}^{K}\colon
d^{\prime}_{a}\leq d^{\prime}_{b}}f_{t}(\boldsymbol{d}^{\prime}),$

Whereas from (52),

$\displaystyle Y_{b,a}(t)=$
$\displaystyle\log\left(\sum_{\boldsymbol{d}^{\prime}\in\mathcal{S}_{\alpha}(t)}\frac{\prod_{j=1}^{K}\prod_{l=0}^{S_{j}(t)-1}(d^{\prime}_{j}-l){\mathbb{P}}_{\boldsymbol{d}^{\prime}\sim\mathcal{D}}(\boldsymbol{d}^{\prime})}{(\sum_{i=1}^{K}d^{\prime}_{i})^{t}}\right)-\sup_{\boldsymbol{d}^{\prime}\in\mathbb{R}_{+}^{K}}f_{t}(\boldsymbol{d}^{\prime}).$
(63)

Comparing $Y_{a,b}(t)$ with $Y_{b,a}(t)$ we get

$Y_{a,b}(t)>Y_{b,a}(t)\text{ when }S_{a}(t)\geq S_{b}(t).$ (64)

Also, note that for any pair $a,b$, when $S_{a}(t)\geq S_{b}(t)$, $Y_{b,a}(t)$
has the same value given in (63). Following arguments similar to those in
Lemma 3.3,

$\displaystyle
Y(t)=\max_{a\in\mathcal{K}}\min_{b\in\mathcal{K}\setminus\\{a\\}}Y_{a,b}(t)=Y_{\tilde{a}_{t},\tilde{b}_{t}}(t).$

∎

###### Proof of Theorem 4.5.

If the mode is chosen by NI-ME, the mode is correct with probability atleast
$1-\delta$. This is evident from the proof of Theorem 3.6. Now, we prove the
correctness of mode chosen by the identity-based stopping rule when condition
(12) is satisfied. Let $a^{*}$ denote the mode. For $b\in\mathcal{K}$, let

$\mathit{E}_{b}^{t}=\\{\omega:\tau_{\delta}=t,a^{*}=b\\}$

be the set of sample paths for which the stopping time of identity-based
stopping rule is $t$ and the mode estimated is $b$. Note that

$\mathit{E}_{b}^{t_{1}}\cap\mathit{E}_{b}^{t_{2}}=\phi\text{ for all
}t_{1}\neq t_{2}.$

The probability of error in estimating the mode

$\displaystyle{\mathbb{P}}(a^{*}\neq 1)$
$\displaystyle=\sum_{b\in\mathcal{K}\setminus\\{1\\}}\sum_{t=0}^{\infty}\sum_{\omega\in\mathit{E}_{b}^{t}}\mathcal{L}_{\boldsymbol{d}}(\omega)$
$\displaystyle\leq\sum_{b\in\mathcal{K}\setminus\\{1\\}}\sum_{t=0}^{\infty}\sum_{\omega\in\mathit{E}_{b}^{t}}\sup_{d^{\prime}_{1}\geq
d^{\prime}_{b}}\mathcal{L}_{\boldsymbol{d^{\prime}}}(\omega)$
$\displaystyle{\mathbb{P}}(a^{*}\neq 1)$
$\displaystyle\leq\sum_{b\in\mathcal{K}\setminus\\{1\\}}\sum_{t=0}^{\infty}\sum_{\omega\in\mathit{E}_{b}^{t}}\frac{\sup_{d^{\prime}_{1}\geq
d^{\prime}_{b}}\mathcal{L}_{\boldsymbol{d^{\prime}}}(\omega)\mathbb{E}_{\boldsymbol{d}^{\prime}\sim\mathcal{D}}\left[\mathcal{L}_{\boldsymbol{d}^{\prime}}(\boldsymbol{x}^{t},\boldsymbol{\sigma}^{t})\right]}{\mathbb{E}_{\boldsymbol{d}^{\prime}\sim\mathcal{D}}\left[\mathcal{L}_{\boldsymbol{d}^{\prime}}(\boldsymbol{x}^{t},\boldsymbol{\sigma}^{t})\right]}$
$\displaystyle\overset{(1)}{\leq}\sum_{b\in\mathcal{K}\setminus\\{1\\}}\sum_{t=0}^{\infty}\sum_{\omega\in\mathit{E}_{b}^{t}}e^{-W_{b,1}(t)}\mathbb{E}_{\boldsymbol{d}^{\prime}\sim\mathcal{D}}\left[\mathcal{L}_{\boldsymbol{d}^{\prime}}(\boldsymbol{x}^{t},\boldsymbol{\sigma}^{t})\right]$
$\displaystyle\overset{(2)}{\leq}\sum_{b\in\mathcal{K}\setminus\\{1\\}}\sum_{t=0}^{\infty}\sum_{\omega\in\mathit{E}_{b}^{t}}e^{-Y_{b,1}(t)}\mathbb{E}_{\boldsymbol{d}^{\prime}\sim\mathcal{D}}\left[\mathcal{L}_{\boldsymbol{d}^{\prime}}(\boldsymbol{x}^{t},\boldsymbol{\sigma}^{t})\right].$

The inequality $(1)$ follows from the definition of $W_{a,b}(t)$ in (14) and
$(2)$ follows from (4.2). Since $Y_{b,1}(t)$ is greater than threshold
$\beta(t,\delta/2)$ at stopping time $t$,

$\displaystyle{\mathbb{P}}(a^{*}\neq 1)$
$\displaystyle\leq\sum_{b\in\mathcal{K}\setminus\\{1\\}}e^{-\beta(t,\delta/2)}\underbrace{\sum_{t=0}^{\infty}\sum_{\omega\in\mathit{E}_{b}^{t}}\mathbb{E}_{\boldsymbol{d}^{\prime}\sim\mathcal{D}}\left[\mathcal{L}_{\boldsymbol{d}^{\prime}}(\boldsymbol{x}^{t},\boldsymbol{\sigma}^{t})\right]}_{(p*)}$
$\displaystyle\leq\frac{\delta}{2},$

for $\beta(t,\delta/2)=\log\left(\frac{2(K-1)}{\delta}\right)$, as $(p*)$ is
${\mathbb{P}}(a^{*}=b)$ under an alternate probability distribution. ∎

###### Proof of Theorem 4.6.

Proof of (18):
Let event

$\mathcal{E}_{1}=\\{\forall
j\in\mathcal{K},S_{j}(t)\xrightarrow[t\to\infty]{}d_{j}\\}.$

######  Lemma B.4.

The event $\mathcal{E}_{1}$ is of probability 1.

###### Proof.

Let $A_{j,t}$ be the event that $j^{\text{th}}$ individual is not picked in
$t$ samples. Event $A_{j,t+1}\subset A_{j,t}$. The event that $j^{\text{th}}$
individual is not picked as $t\to\infty$ can be written as
$\cap_{t=1}^{\infty}A_{j,t}$. The probablity

$\displaystyle{\mathbb{P}}(\mathcal{E}_{1}^{c})$
$\displaystyle\leq{\mathbb{P}}(\cup_{j=1}^{N}\cap_{t=1}^{\infty}A_{j,t})$
$\displaystyle\leq\sum_{j=1}^{N}{\mathbb{P}}(\cap_{t=1}^{\infty}A_{j,t})$
$\displaystyle=\sum_{j=1}^{N}\lim_{t\to\infty}{\mathbb{P}}(A_{j,t})$
$\displaystyle=\sum_{j=1}^{N}\lim_{t\to\infty}\left(\frac{N-1}{N}\right)^{t}$
$\displaystyle=0.$

So, the event $\mathcal{E}_{1}$ is of probability 1 as $t\to\infty$. ∎

On $\mathcal{E}_{1}$, there exists a time $t_{1}>N$ such that for $t>t_{1}$,
$S_{j}(t)=d_{j}$. For $t>t_{1}$,

$\displaystyle Y(t)$
$\displaystyle=\log\left(\sum_{\boldsymbol{d}^{\prime}\in{\mathbb{N}}^{K},d_{j}\leq
d^{\prime}_{j}\leq\alpha
d_{j}}\frac{\prod_{j=1}^{K}\prod_{l=0}^{d_{j}-1}(d^{\prime}_{j}-l){\mathbb{P}}_{\boldsymbol{d}^{\prime}\sim\mathcal{D}}(\boldsymbol{d}^{\prime})}{(\sum_{i=1}^{K}d^{\prime}_{i})^{t}}\right)$
$\displaystyle\hskip
113.81102pt-\left(\sum_{j\in\mathcal{K}^{(t)}}\int_{-1}^{d_{j}}\log(d^{1,2}_{j}(\gamma_{0})-v)dv-t\log\left(\sum_{i=1}^{K}d^{1,2}_{i}(\gamma_{0})\right)\right).$

The summation