# PAC Mode Estimation using PPR Martingale Confidence Sequences

Shubham Anand Jain
Indian Institute of Technology Bombay
Mumbai, India 400076
<EMAIL_ADDRESS>
&Sanit Gupta
Indian Institute of Technology Bombay
Mumbai, India 400076
<EMAIL_ADDRESS>
&Denil Mehta11footnotemark: 1
Indian Institute of Technology Bombay
Mumbai, India 400076
<EMAIL_ADDRESS>
&Inderjeet Jayakumar Nair11footnotemark: 1
Indian Institute of Technology Bombay
Mumbai, India 400076
<EMAIL_ADDRESS>
&Rohan Shah11footnotemark: 1
Indian Institute of Technology Bombay
Mumbai, India 400076
<EMAIL_ADDRESS>
&Jian Vora11footnotemark: 1
Indian Institute of Technology Bombay
Mumbai, India 400076
<EMAIL_ADDRESS>
&Sushil Khyalia
Indian Institute of Technology Bombay
Mumbai, India 400076
<EMAIL_ADDRESS>
&Sourav Das
University of Illinois at Urbana-Champaign
<EMAIL_ADDRESS>
&Vinay J. Ribeiro
Indian Institute of Technology Bombay
Mumbai, India 400076
<EMAIL_ADDRESS>
&Shivaram Kalyanakrishnan
Indian Institute of Technology Bombay
Mumbai, India 400076
<EMAIL_ADDRESS>
Equal contribution

###### Abstract

We consider the problem of correctly identifying the mode of a discrete
distribution $\mathcal{P}$ with sufficiently high probability by observing a
sequence of i.i.d. samples drawn according to $\mathcal{P}$. This problem
reduces to the estimation of a single parameter when $\mathcal{P}$ has a
support set of size $K=2$. Noting the efficiency of prior-posterior-ratio
(PPR) martingale confidence sequences [1] for handling this special case, we
propose a generalisation to mode estimation, in which $\mathcal{P}$ may take
$K\geq 2$ values. We observe that the “one-versus-one” principle yields a more
efficient generalisation than the “one-versus-rest” alternative. Our resulting
stopping rule, denoted PPR-ME, is optimal in its sample complexity up to a
logarithmic factor. Moreover, PPR-ME empirically outperforms several other
competing approaches for mode estimation. We demonstrate the gains offered by
PPR-ME in two practical applications: (1) sample-based forecasting of the
winner in indirect election systems, and (2) efficient verification of smart
contracts in permissionless blockchains.

##  1 Introduction

We investigate the problem of estimating the mode of a given, arbitrary
discrete probability distribution $\mathcal{P}=(p,v,K)$ by observing a
sequence of i.i.d. samples drawn according to $\mathcal{P}$. Here
$\mathcal{P}$ takes values from the support set
$\\{v_{1},v_{2},\dots,v_{K}\\}$ for some $K\geq 2$; for $1\leq i\leq K$, the
probability of obtaining $v_{i}$ from $\mathcal{P}$ is $p_{i}$. We assume that
$\mathcal{P}$ has a unique mode, and without loss of generality,
$p_{1}>p_{2}\geq p_{3}\geq p_{4}\geq\dots\geq p_{K}$ (which makes $v_{1}$ the
mode).

Our aim is to provide a procedure $\mathcal{L}$ to identify the mode of
$\mathcal{P}$. At each step $t\geq 1$, $\mathcal{L}$ can either ask for a
sample $x^{t}\sim\mathcal{P}$ or it can terminate and declare its answer. For
“mistake probability” $\delta\in(0,1)$, $L$ is said to be $\delta$-correct if
for every qualifying discrete distribution $\mathcal{P}$, $L$ terminates with
probability $1$ and correctly identifies the mode of $\mathcal{P}$ with
probability at least $1-\delta$. If $\mathcal{L}$ terminates after observing
the sequence of samples $x^{1},x^{2},\dots,x^{T}$ for some $T\geq 1$, we may
assume that its answer is the most frequent value of $\mathcal{P}$ in this
sequence, since it can be argued that no other choice can decrease the mistake
probability across all problem instances. Hence, it is convenient to view
$\mathcal{L}$ simply as a stopping rule, which only needs to decide when to
terminate. We aim to devise a $\delta$-correct stopping rule $\mathcal{L}$
with low sample complexity—informally the number of samples $T$ observed
before stopping.

In order to make our problem “properly” PAC, we could introduce a tolerance
parameter $\epsilon$, with the implication that any returned value with
associated probability at least $p_{1}-\epsilon$ will be treated as correct.
We omit this generalisation, noting that it can be handled quite easily by the
methods proposed in the paper. In fact, our version with $\epsilon=0$ exactly
matches the problem defined by Shah et al. [2], whose algorithms and analysis
are our primary baseline. Shah et al. [2] effectively “settle” the PAC mode
estimation problem from a theoretical perspective. First they show the
following lower bound.

######  Theorem 1 (Lower bound [2]).

Fix $\delta\in(0,1)$, $K\geq 2$, and a $\delta$-correct stopping rule
$\mathcal{L}$. On each problem instance $\mathcal{P}=(p,v,K)$, the expected
number of samples observed by $\mathcal{L}$ is at least

$\frac{p_{1}}{(p_{1}-p_{2})^{2}}\ln\left(\frac{1}{2.4\delta}\right).$

They also give a stopping rule, $\mathcal{A}_{1}$, whose sample complexity is
within a logarithmic factor.

######  Theorem 2 ($\mathcal{A}_{1}$ upper bound [2]).

Fix $\delta\in(0,1)$, $K\geq 2$, and problem instance $\mathcal{P}=(p,v,K)$.
When $\mathcal{A}_{1}$ is run on $\mathcal{P}$, with probability $1-\delta$,
the number of samples it observes is at most

$\frac{592}{3}\frac{p_{1}}{(p_{1}-p_{2})^{2}}\ln\left(\frac{592}{3}\sqrt{\frac{K}{\delta}}\frac{p_{1}}{(p_{1}-p_{2})^{2}}\right).$

In this paper, we approach the PAC mode estimation problem from a different
perspective. In recent work, Waudby-Smith and Ramdas [1] propose prior-
posterior-ratio (PPR) martingale confidence sequences, a novel framework to
obtain “anytime” confidence bounds on unknown parameters of a probability
distribution. The resulting stopping rule is simple, with no need for tuning,
and yet works surprisingly well in practice, for example to estimate the
parameter of a Bernoulli distribution by sampling. Encouraged by this
empirical finding, we undertake the generalisation of the PPR martingale test
to mode estimation, wherein the $K$-valued input distribution $\mathcal{P}$
has $K-1$ parameters, for some $K\geq 2$. We denote our generalised stopping
rule PPR-ME (PPR applied to mode estimation).

In Section 2, we upper-bound the sample complexity of PPR-ME for the base case
of $K=2$, showing it to be optimal up to a logarithmic factor for the well-
studied “Bernoulli” setting. This finding might independently bear
significance to the push for tighter confidence bounds in the bandits
literature [3, 4]. In Section 3, we describe PPR-ME for $K\geq 2$ and derive
an upper bound on its sample complexity. Interestingly, this upper bound also
matches the lower bound in Theorem 1 up to a logarithmic factor, and
marginally improves upon the constant factor in the upper bound from Theorem
2. In sections 2 and 3, we also provide empirical comparisons between PPR-ME
and other approaches to PAC mode estimation. We find strong support for using
“one-versus-one” comparisons for mode estimation (as in PPR-ME), as opposed to
a “one-versus-rest” approach (as in $\mathcal{A}_{1}$ [2]).

Over the years, the mode estimation problem has received attention in many
different contexts [5, 6, 7]. We illustrate the gains obtained from PPR-ME in
two contrasting real-life applications. In Section 4, we show that PPR-ME,
used as a subroutine, can reduce the sample complexity of winner-forecasting
in indirect elections [8]. In Section 5, we illustrate the relevance of PPR-ME
for probabilistic verification in permissionless blockchains [9]. We conclude
with a summary in Section 6.

##  2 PPR Martingale Confidence Sequences

In this section, we consider the “base case” of mode estimation, in which
$\mathcal{P}$ takes exactly $K=2$ values. Notice that $\mathcal{P}(p,v,2)$ is
a Bernoulli distribution that generates $v_{1}$ with probability $p_{1}$ and
$v_{2}$ with probability $p_{2}=1-p_{1}$. Treating $p_{1}\in[0,1]$ as the sole
parameter of the distribution, our task is to devise a $\delta$-correct
stopping rule to test if $p_{1}>\frac{1}{2}$. Since $p_{1}$ may be arbitrarily
close to $\frac{1}{2}$, it is not possible to decide beforehand how many
samples suffice for the test to succeed. An unfortunate consequence of having
a random stopping time is that it cannot be used directly within concentration
inequalities such as Chernoff bounds. Rather, stopping rules invariably go
through a union bound over all possible stopping times, dividing the mistake
probability $\delta$ among them [10, 11]. Although there has been progress
towards optimising this apportioning of $\delta$ [4, 12], resulting methods
still have tunable parameters in their “decay rates” that govern the stopping
time.

The recent development of “time-uniform” or “anytime” Chernoff bounds [13]
relieve the experimenter of the burden of parameter-tuning. Arising from this
line of research is the framework of prior-posterior-ratio (PPR) martingale
confidence sequences [1], which result in a simple and intuitive stopping
rule. Although the rule may be applied to a wide range of single-parameter
families, we restrict our upcoming discussion to the Bernoulli case at hand:
that is, to test whether $p_{1}>\frac{1}{2}$.

To apply the PPR martingale framework, we maintain a belief distribution $\pi$
for $p_{1}$ over its range $[0,1]$, and update $\pi$ according to Bayes’ rule
as samples are observed. Our aim is still to provide a frequentist guarantee
of that holds for all possible values of $p_{1}$ ($\delta$-correctness). To
this end we must ensure that the prior distribution $\pi^{0}$ gives non-zero
density to all possible values of $p_{1}$. We do so by adopting the uniform
prior $\pi^{0}(\hat{p}_{1})=1$ for $\hat{p}_{1}\in[0,1]$. For $t\geq 1$, we
update our belief distribution after observing sample $x^{t}$, as follows.

$\pi^{t}(\hat{p}_{1})=\frac{\pi^{t-1}(\hat{p}_{1})\cdot(\hat{p}_{1})^{\mathbf{1}[x^{t}=v_{1}]}\cdot(1-\hat{p}_{1})^{\mathbf{1}[x^{t}=v_{2}]}}{\int_{\rho=0}^{1}\pi^{t-1}(\rho)\cdot(\rho)^{\mathbf{1}[x^{t}=v_{1}]}\cdot(1-\rho)^{\mathbf{1}[x^{t}=v_{2}]}d\rho}.$

The prior-posterior-ratio (PPR) at $\hat{p}_{1}\in[0,1]$ is given by
$R^{t}(\hat{p}_{1})=\frac{\pi^{0}(\hat{p}_{1})}{\pi^{t}(\hat{p}_{1})}$. Making
use of the fact that the PPR evaluated at the true parameter value, $p_{1}$,
is a martingale, it can be shown that the sequence of sets
$(C^{t})_{t=0}^{\infty}$, where
$C^{t}\operatorname*{\stackrel{{\scriptstyle\text{\tiny
def}}}{{=}}}\\{\hat{p}_{1}:R^{t}(\hat{p}_{1})<\frac{1}{\delta}\\}$, is a
$(1-\delta)$-confidence sequence for $p_{1}$ [1]. In other words, we have the
“anytime” guarantee that

$\mathbb{P}\\{\>\exists\>t\geq 0:p_{1}\notin C^{t}\\}\leq\delta.$ (1)

The belief distribution $\pi^{t}$ and hence the PPR $R^{t}$ assume a
convenient form if initialised with the uniform prior. Suppose the sequence of
samples up to time $t$ is $x^{1},x^{2},\dots,x^{t}$, which contains
$s^{t}_{1}$ occurrences of $v_{1}$ and $s^{t}_{2}=t-s_{1}$ occurrences of
$v_{2}$. Then for $t\geq 0$ and $\hat{p}_{1}\in[0,1]$, we obtain
$\pi_{t}(\hat{p}_{1})=\text{Beta}(\hat{p}_{1};s^{t}_{1}+1,s^{t}_{2}+1)$. We
can terminate as soon as the $(1-\delta)$-confidence sequence on $p_{1}$ does
not contain $\frac{1}{2}$. For easy readability, let us define indices
$\text{first}(t)$ and $\text{second}(t)$, where
$(\text{first}(t),\text{second}(t))\in\\{(1,2),(2,1)\\}$ satisfy
$s^{t}_{\text{first}(t)}\geq s^{t}_{\text{second}(t)}$. We obtain the
following simple simple stopping rule, applied at each time step $t\geq 1$.

PPR-Bernoulli: Stop and declare $v_{\text{first}(t)}$ as mode iff
$\text{Beta}\left(\frac{1}{2};s^{t}_{\text{first}(t)}+1,s^{t}_{\text{second}(t)}+1\right)\leq\delta$.

The $\delta$-correctness of this stopping is immediate from (1), itself a
proven result [1]. However, we are not aware of any existing analysis of its
stopping time. We obtain the following upper bound by expanding out the Beta
density function at $\frac{1}{2}$ and bounding tail probabilities using
Chernoff bounds. The detailed working, which also involves steps to optimise
constants, is provided in Appendix A.

######  Lemma 3 (PPR-Bernoulli upper bound).

Fix $\delta\in(0,1)$ and problem instance $\mathcal{P}=(p,v,2)$. When PPR-
Bernoulli is run on $\mathcal{P}$, with probability $1-\delta$, the number of
samples it observes is at most

$\frac{20.775p_{1}}{(p_{1}-\frac{1}{2})^{2}}\ln\left(\frac{2.49}{(p_{1}-\frac{1}{2})^{2}\delta}\right).$

Like the result in Theorem 2, the lemma upper-bounds the sample complexity
only on the event that a mistake is not made. However, we can obtain an upper
bound on the expected sample complexity, with only the constants changed, by
adopting a doubling trick—wherein the procedure is repeatedly performed with
increasing budgets and decreasing mistake probabilities, until it terminates.
The “$p_{1}$” in the numerator of the upper bound above can be ignored as a
constant factor since $p_{1}\in(\frac{1}{2},1]$, but the explicit form is
convenient for our generalisation to $K\geq 2$, which we take up in the next
section.

It is worth noting that the LHS of the PPR-Bernoulli stopping rule can be
evaluated exactly as a rational using integer arithmetic, requiring a only
lightweight incremental update after each sample. This implementation of the
PPR-Bernoulli stopping rule is arguably simpler than the numerical
optimisation needed by many other stopping rules, as we see shortly.

###  2.1 Empirical comparison with other Stopping Rules for $K=2$

We present experimental results comparing PPR-Bernoulli with other stopping
rules from the literature. The predominant approach is to construct lower and
upper confidence bounds on $p_{1}$ that hold with probability $1-\delta_{t}$
for each $t\geq 1$, satisfying $\sum_{t=0}^{\infty}\delta_{t}\leq\delta$. The
$\delta$-correctness of the procedure is ensured by terminating only when the
lower confidence bound exceeds $\frac{1}{2}$ or the upper confidence bound
falls below $\frac{1}{2}$. A common choice is to set
$\delta_{t}=k\frac{\delta}{t^{\alpha}}$, with constants $k$ and $\alpha$ tuned
for efficiency while ensuring $\delta$-correctness. As representatives of this
approach, we pick the LUCB and KL-LUCB algorithms of Kaufmann and
Kalyanakrishnan [11]. The former inverts Hoeffding’s inequality to obtain
lower and upper confidence bounds, while the latter uses a tighter Chernoff
bound. Although these algorithms themselves are meant for bandit applications,
their efficiency crucially depends on the tightness of the confidence bounds
applied to each arm. The tuned confidence bounds [11] therefore become
suitable baselines for our comparison. Details of our implementation of the
LUCB and KL-LUCB confidence bounds, as well as forthcoming ones, are provided
in Appendix C. Links to code and related instructions are given in Appendix D.

With the intent of avoiding a naïve union bound over time, Garivier applies a
so-called peeling argument to divide time into increasingly-sized slices. He
obtains confidence regions by associating the random stopping time with a
self-normalised process. The resulting stopping rule, which we denote KL-SN,
still has a tunable parameter “c”, which we set as recommended by Garivier
[12].

Although the $\mathcal{A}_{1}$ algorithm of Shah et al. [2] is designed
specifically for mode estimation, we include it in this comparison to observe
its performance when $K=2$. In this special case, the algorithm reduces to an
application of an empirical Bernstein bound given by Maurer and Pontil [14].

In Figure 1(a), we observe the stopping times of the different rules as
$p_{1}$ is varied, for mistake probability $\delta=0.01$. KL-LUCB shows a
marginal improvement over (Hoeffding) LUCB, while KL-SN clearly outperforms
both. However, PPR-Bernoulli is significantly more efficient than even KL-SN.
Given its simplicity and non-reliance on parameter-tuning, PPR-Bernoulli
therefore becomes an attractive proposition for stopping problems.
Surprisingly, in spite of using variance information, $\mathcal{A}_{1}$
registers the worst performance among all the methods compared in this
experiment. We attribute this result to slack in the constants used in its
stopping rule, which future work can possibly tighten, while still ensuring
$\delta$-correctness. Figure 1(b) affirms the trend among the stopping rules
when they are applied to the same distribution ($p_{1}=0.65$), but with
varying mistake probability $\delta$.

(a)

(b)

Figure 1: Comparison of stopping rules for the Bernoulli case ($K=2$). Both
plots show sample complexity: in (a) as $p_{1}$ is varied, and in (b) as
$\delta$ is varied. The results are averages from 100 runs. Error bars show
one standard error (in both plots very small).

##  3 PPR-ME Stopping Rule for Mode Estimation

In this section, we present our generalisation of the PPR-Bernoulli stopping
rule to the problem of mode estimation: that is, when the support set is of
size $K\geq 2$. In the broader machine learning literature, the most common
approaches for generalising $2$-class problems to more classes are “one-
versus-one” (denoted 1v1) and “one versus rest” (denoted 1vr). We investigate
both approaches, and present them in turn. Interestingly, we observe
overwhelming evidence in favour of using the 1v1 approach for mode estimation.
Thus, the PPR-ME stopping rule that we propose based on the investigation in
this paper is the same as PPR-1v1, which we describe next.

###  3.1 One-versus-one (1v1) Approach

In the first $t\geq 1$ samples, let the number of occurrences of value $v_{i}$
be $s_{i}(t)$, $1\leq i\leq K$. The 1v1 generalisation proceeds based on the
idea that if $v_{i}$ is to be declared the mode, we need to be sufficiently
sure that $v_{i}$ is more probable than $v_{j}$ for
$i,j\in\\{1,2,\dots,K\\},i\neq j$. In keeping, we simultaneously run PPR-
Bernoulli tests on each $(i,j)$ pair with mistake probability
$\frac{\delta}{K-1}$. Each $(i,j)$ test relies solely on the number of
occurrences of $v_{i}$ and $v_{j}$, disregarding other values. Hence it
amounts to observing samples from a Bernoulli variable with parameter
$\frac{p_{i}}{p_{i}+p_{j}}$, and verifying which side of $\frac{1}{2}$ its
mean lies. The overall procedure stops when some $i\in\\{1,2,\dots,K\\}$ has
won each of its tests. By a union bound, we obtain that with probability at
least $1-\delta$, the (true) mode $v_{1}$ will not ever lose a test. Thus,
upon termination, $v_{1}$ is returned with probability at least $1-\delta$.

Whereas the description above suggests we need to monitor $\binom{K}{2}$ tests
at each step, closer inspection reveals that a much lighter implementation is
possible. As before, let $\text{first}(t)$ denote the index of the most-
frequently occurring value (with arbitrary tie-breaking) after $t$ samples:
that is, $s^{t}_{\text{first}(t)}\geq s^{t}_{i}$ for $i\in\\{1,2,\dots,K\\}$.
Now, if at all a winner is identified after $t$ samples, clearly it must be
$v_{\text{first}(t)}$, which has as many occurrences as any other value.
Hence, we only need to track tests involving $v_{\text{first}(t)}$. Now, it is
also immediate that $v_{\text{first}(t)}$ wins all its tests if and only if it
defeats the second most frequently occurring value, which we denote
$\text{second}(t)$: that is,
$\text{second}(t)\in\\{1,2,\dots,K\\},\text{second}(t)\neq\text{first}(t)$
satisfies $s^{t}_{\text{second}(t)}\geq s^{t}_{i}$ for
$i\in\\{1,2,\dots,K\\}\setminus\\{\text{first}(t)\\}$. Hence, we may implement
our stopping rule, denoted PPR-1v1, using a single PPR-Bernoulli test at each
step $t\geq 1$.

PPR-1v1: Stop and declare $v_{\text{first}(t)}$ as mode iff
$\text{Beta}\left(\frac{1}{2};s^{t}_{\text{first}(t)}+1,s^{t}_{\text{second}(t)}+1\right)\leq\frac{\delta}{K-1}$.

Whereas a $\Theta(K)$ initialisation step is needed to initialise all counts
to zero, observe that the computation needed at each step $t\geq 1$ is only
$\Theta(1)$—which suffices for identifying $\text{first}(t)$ and
$\text{second}(t)$ based on their previous values, and incrementing the count
of the $x_{t}$. Interestingly, we are able to show a sample complexity upper
bound for this simple procedure to improve upon the one from Theorem 2 [2],
albeit by a small constant factor.

######  Theorem 4 (PPR-1v1 upper bound).

Fix $\delta\in(0,1)$, $K\geq 2$, and problem instance $\mathcal{P}=(p,v,K)$.
When PPR-ME is run on $\mathcal{P}$, with probability $1-\delta$, the number
of samples it observes is at most

$t^{\star}=\frac{194.07p_{1}}{(p_{1}-p_{2})^{2}}\ln\left(\sqrt{\frac{79.68(K-1)}{\delta}}\frac{p_{1}}{(p_{1}-p_{2})}\right).$

###### Proof.

Fix arbitrary $t>t^{\star}$ and $j\geq 2$. Our strategy is to show that with
sufficiently high probability, $v_{1}$ and $v_{j}$ will have separated before
$t$ pulls. First, let $Z_{t}$ denote the sum of the number of occurrences of
$v_{1}$ and $v_{j}$ in the first $t$ samples: that is,
$Z^{t}=s^{t}_{1}+s^{t}_{j}$. Clearly $Z_{t}$ is a binomial random variable
with parameters $t$ and $(p_{1}+p_{j})$, We argue that $Z^{t}$ cannot fall too
far below its mean. Concretely, take $\delta^{\prime}=\frac{\delta}{2(K-1)}$
and $l=\sqrt{\frac{2\ln(\frac{1}{\delta^{\prime}})}{(p_{1}+p_{2})t}}$. A
Chernoff bound yields

$\mathbb{P}\\{Z_{t}\leq(1-l)(p_{1}+p_{j})t\\}\leq\exp\left(-\frac{l^{2}(p_{1}+p_{j})t}{2}\right)\leq\delta^{\prime}$

for our choice of $l$. Thus, with probability at least $1-\delta^{\prime}$,
$v_{1}$ and $v_{j}$ together have more than $(1-l)(p_{1}+p_{j})t$ samples.
Now, the test to separate $v_{1}$ and $v_{j}$ is PPR-Bernoulli on a Bernoulli
variable with parameter $q_{1}=\frac{p_{1}}{p_{1}+p_{j}}>\frac{1}{2}$.
Although PPR-ME runs this test with mistake probability $\frac{\delta}{K-1}$,
imagine running it with mistake probability
$\delta^{\prime}=\frac{\delta}{2(K-1)}$. The latter test would necessarily
incur equal or more samples on every run. Yet, from Lemma 3, we know that with
probability at least $1-\delta^{\prime}$, the latter will terminate after at
most
$u=\frac{20.775q_{1}}{(q_{1}-\frac{1}{2})^{2}}\ln\left(\frac{2.49}{(q_{1}-\frac{1}{2})^{2}\delta^{\prime}}\right)$
samples. It can be verified that for $t>t^{\star}$, $u<(1-l)(p_{1}+p_{j})t$
(calculation shown in Appendix B). In other words, the probability that
$v_{1}$ and $v_{j}$ have not separated before $t$ pulls is at most
$2\delta^{\prime}$.

Since the argument above holds for arbitrary $j\geq 2$, a union bound
establishes that with probability at least $1-\delta$, $v_{1}$ must have
separated from all other values—implying termination—before $t$ pulls. ∎

###  3.2 One-versus-rest (1vr) Approach

Notice that under PPR-1v1, sample $x^{t}$ at each step $t\geq 1$ contributes
to only $K-1$ tests; $\binom{K-1}{2}$ tests corresponding to values other than
$x^{t}$ receive no information. The 1vr approach becomes an alternative to
address this apparent wastage of information. Under the 1vr scheme, we
associate a Bernoulli variable $B_{i}$ with each value $v_{i}$, $1\leq i\leq
K$, which has probability $p_{i}$ of generating $v_{i}$, and probability
$1-p_{i}$ of generating its negation “$\neg v_{i}$”. Consequently, each sample
of $\mathcal{P}$ adds to one of the outcomes of $B_{i}$ for each
$i\in\\{1,2,\dots,K\\}$. We draw an anytime confidence sequence for $B_{i}$
with mistake probability $\frac{\delta}{K}$, and terminate after $t\geq 1$
samples if the confidence set of $B_{\text{first}(t)}$ does not overlap with
any of the others. Invoking the PPR martingale confidence sequence, we note
that with probability at least $1-\frac{\delta}{K}$, $p_{i}$ will lie in all
the intervals $(\text{LCB}^{t}_{i},\text{UCB}^{t}_{i})$, $t\geq 1$, where

$\text{LCB}^{t}_{i}=\min\left\\{\hat{p}\in[0,1]:\pi^{t}(\hat{p})=\frac{\delta}{K}\right\\}\text{
and
}\text{UCB}^{t}_{i}=\max\left\\{\hat{p}\in[0,1]:\pi^{t}(\hat{p})=\frac{\delta}{K}\right\\}$

can be computed numerically. The $\delta$-correctness of the 1vr rule,
summarised below, is established by applying a union bound on the mistake
probabilities of each $B_{i}$, $1\leq i\leq K$.

PPR-1vr: Stop and declare $v_{\text{first}(t)}$ as mode iff for $1\leq i\leq
K$, $i\neq\text{first}(t)$,
$\text{LCB}^{t}_{\text{first}(t)}\geq\text{UCB}^{t}_{i}.$

###  3.3 Empirical Comparisons with other Stopping Rules for Mode Estimation

The $\mathcal{A}_{1}$ algorithm of Shah et al. [2] is essentially a 1vr
approach that uses Empirical Bernstein confidence bounds [14]. Noting that it
can just as well be implemented in a 1v1 form, we include such a variant,
denoted $\mathcal{A}_{1}$-1v1, in our experimental comparisons with PPR. For
good measure, we also include 1v1 and 1vr variants based on the KL-SN
confidence bound [12], which finished second to PPR-Bernoulli for $K=2$ (see
Section 2). Table 1 shows the performance of 1v1 and 1vr versions of PPR,
$\mathcal{A}_{1}$, and KL-SN on a variety of distributions. We observe the
same trend on each problem instance: (1) The 1v1 variant of each stopping rule
outperforms the corresponding 1vr variant, and (2) PPR is most sample-
efficient, followed by KL-SN and $\mathcal{A}_{1}$. In line with the upper
bound from theorems 2 and 4, it does appear that the sample complexity is
largely determined by $p_{1}$ and $p_{2}$ (identical for instances
$\mathcal{P}_{5}$ and $\mathcal{P}_{6}$) in the table. The logarithmic
dependence on $K$ results in a slightly larger number of samples for all these
methods on $\mathcal{P}_{6}$.

Table 1: Sample complexity comparison for mode estimation, run with mistake probability $\delta=0.01$. The number after the $\times$ symbol indicates the multiplicity of that particular probability value in the distribution; thus $\mathcal{P}_{1}$ has $p=(0.5,0.25,0.25)$. The values reported are averages from 100 or more runs, and show one standard error. Distribution | K | Type |  $\mathcal{A}_{1}$ [2] |  KL-SN [12] | PPR
---|---|---|---|---|---
$\mathcal{P}_{1}$: .5, .25 $\times$ 2 | 3 | 1vr |  1344$\pm$20 |  444$\pm$14 |  262$\pm$12
1v1 |  1157$\pm$19 |  346$\pm$13 | 218$\pm$11
$\mathcal{P}_{2}$: .4, .2 $\times$ 3 | 4 | 1vr |  1919$\pm$29 |  662$\pm$18 |  397$\pm$15
1v1 |  1515$\pm$25 |  472$\pm$15 | 298$\pm$13
$\mathcal{P}_{3}$: .2, .1 $\times$ 8 | 9 | 1vr |  5082$\pm$51 |  3767$\pm$68 |  1201$\pm$29
1v1 |  3340$\pm$43 |  1138$\pm$32 | 789$\pm$28
$\mathcal{P}_{4}$: .1, .05 $\times$ 18 | 19 | 1vr |  12014$\pm$129 |  4540$\pm$80 |  2850$\pm$55
1v1 |  7351$\pm$88 |  2554$\pm$56 | 1840$\pm$53
$\mathcal{P}_{5}$: .35, .33, .12, .1 $\times$ 2 | 5 | 1vr |  155277$\pm$2356 |  63739$\pm$2238 |  38001$\pm$1311
1v1 |  117988$\pm$2078 |  47205$\pm$1291 | 33660$\pm$1125
$\mathcal{P}_{6}$: .35, .33, .04 $\times$ 8 | 10 | 1vr |  158254$\pm$2442 |  66939$\pm$2241 |  41963$\pm$1330
1v1 |  121150$\pm$2183 |  49576$\pm$1341 | 36693$\pm$1185

Interestingly, not only do the 1v1 variants of each method perform better than
1vr in aggregate, we observe that they terminate before the 1vr variants on
every single run. Intuitively, it appears that although the 1vr variants
update all their $K$ tests with each sample, the condition to separate any two
variables becomes weaker than that under the corresponding 1v1 variant. We
discuss this effect in Appendix E. It is also worth noting that PPR-1v1, which
can be implemented with a constant number of arithmetic operations, is
computationally the fastest among the methods presented in this section.

##  4 Application: Winner-forecasting in Indirect Elections

Opinion polls—deployed to gauge public perception of competing products in a
market, or to forecast the winner of an upcoming election—are a natural
application of mode estimation. In fact, the algorithms discussed in Section 3
can all be applied with only minor alterations to plurality systems, wherein
the task is precisely that of determining the choice preferred by the largest
fraction of the target population. Waudby-Smith and Ramdas [1] illustrate the
use of PPR martingale confidence sequences precisely on this application.
Specifically they consider the construction of confidence sequences when polls
receive without-replacement samples from finite populations.

In parliamentary democracies such as India [15] and the United Kingdom [16],
individuals in each constituency (or seat)—typically a geographically
contiguous region—elect a party based on plurality; the party winning the most
seats forms the government. This two-level structure is followed both to elect
governments in each state, and for the entire country. Forecasting the winning
party in such an indirect voting system calls for a more sophisticated
sampling procedure. Whereas it would suffice to separately identify the winner
from each seat by sampling, it might be wasteful to do so when the overall
winning party has a clear majority in its number of seats. Rather, one could
potentially use the results currently available from all the constituencies to
decide which ones to query next.

In this section, we consider a procedure that (1) keeps track of the current
winners and leaders at the aggregate level, and (2) at each step samples the
constituencies that appear most promising to confirm the aggregate trend. In
principle, this algorithm, denoted DCB (for “Difference in Confidence Bounds”)
can be coupled with any algorithm that uses confidence bounds for mode
estimation. Yet, we obtain the best results when DCB uses PPR-ME as a
subroutine, thereby highlighting the relevance of PPR-ME not only as a
stopping rule, but also as an input to on-line decision making.

DCB takes cue from the LUCB algorithm for best-arm identification in bandits
[10]. At each step $t$, it identifies two parties, $a^{t}$ and $b^{t}$, that
appear the most promising to win the overall election: these parties are
picked based on their current number of wins and “leads” in individual
constituencies. Subsequently the algorithm chooses a constituency each for
$a^{t}$ and $b^{t}$, samples from which could “most” help distinguish the
tally of the two. We provide a detailed specification of DCB in Appendix F.

###  4.1 Performance when Coupled with DCB

We compare DCB with a round-robin strategy for picking the next constituency
to sample. Both approaches can be implemented with different stopping rules,
which are also varied. Table 2 shows our results on two recent (and
contrasting) elections conducted in India.111Election results are in the
public domain; the authors accessed them at https://www.indiavotes.com/. In
the 2014 national elections, the winning party secured 282 seats from among
543, giving it a very large victory over the second-place party, which won 44
seats. The second problem instance is from a closer contest in the state of
Bihar, in which the top three parties won 80, 71, and 53 seats, of a total
242.

Table 2: Sample complexity of various stopping rules when coupled with (1) round-robin (RR) polling of constituencies and (2) DCB. All experiments are run with mistake probability $\delta=0.01$. Values shown are averages from 10 runs, and show one standard error. “Seats resolved” indicates the number of constituencies in which a winner was identified before the overall procedure terminated. Algorithm | India-2014 (543 seats) | Bihar-2015 (242 seats)
---|---|---
Samples | Seats | Samples | Seats
Resolved | Resolved
RR-$\mathcal{A}_{1}$-1v1 |  1578946 $\pm$ 10255 |  239 $\pm$ 2 |  4201429 $\pm$ 43932 |  221 $\pm$ 1
RR-$\mathcal{A}_{1}$-1vr |  1767464 $\pm$ 15828 |  234 $\pm$ 1 |  4841406 $\pm$ 58188 |  222 $\pm$ 1
RR-KLSN-1v1 |  610181 $\pm$ 7072 |  240 $\pm$ 2 |  2198678 $\pm$ 44514 |  221 $\pm$ 1
RR-KLSN-1vr |  726512 $\pm$ 6186 |  236 $\pm$ 2 |  2668729 $\pm$ 47535 |  222 $\pm$ 2
RR-PPR-1v1 | 471661 $\pm$ 7373 |  241 $\pm$ 3 | 1813213 $\pm$ 42081 |  221 $\pm$ 1
RR-PPR-1vr |  560815 $\pm$ 7778 |  238 $\pm$ 2 |  2054171 $\pm$ 40394 |  221 $\pm$ 1
DCB-$\mathcal{A}_{1}$-1v1 |  856678 $\pm$ 3935 |  182 $\pm$ 1 |  2301936 $\pm$ 36399 |  135 $\pm$ 1
DCB-$\mathcal{A}_{1}$-1vr |  951684 $\pm$ 5246 |  180 $\pm$ 1 |  2481552 $\pm$ 21483 |  134 $\pm$ 1
DCB-KLSN-1v1 |  325265 $\pm$ 2096 |  186 $\pm$ 2 |  1127963 $\pm$ 22191 |  139 $\pm$ 2
DCB-KLSN-1vr |  376108 $\pm$ 4067 |  181 $\pm$ 1 |  1312027 $\pm$ 22892 |  139 $\pm$ 1
DCB-PPR-1v1 | 256911 $\pm$ 2096 |  188 $\pm$ 1 | 883389 $\pm$ 15581 |  142 $\pm$ 2
DCB-PPR-1vr |  296580 $\pm$ 2372 |  184 $\pm$ 1 |  993495 $\pm$ 18859 |  139 $\pm$ 1

While it is not the central feature of this paper, it is worth noting that the
DCB strategy indeed improves over round-robin polling by roughly a factor of
two, regardless of the stopping rule. As intended, it does not waste samples
on constituencies that are inconsequential to the overall result (observed in
the “seats resolved” columns). Of more direct relevance to the theme of the
paper is that even when embedded within a decision-making outer loop, PPR
continues to outperform $\mathcal{A}_{1}$ and KL-SN, and the 1v1 approach
still dominates 1vr.

It must be emphasised that in practice, election surveys typically have the
financial budget only for a few thousands of samples, and the time only for a
single-stage (non-sequential) poll [8]. Opinion polls must also cope with
difficulties in obtaining truthful votes and samples drawn uniformly at random
from a population [17]. We have conveniently assumed a more abstract setting
primarily to tease apart the efficiency of different stopping rules for mode
estimation. We believe the numerical superiority of PPR-1v1 makes it a good
choice for embedding within more complex and realistic models, although we
leave the exercise of doing so to future work.

##  5 Application: Verifying Smart Contracts in Permissionless Blockchains

Our second application of PAC mode estimation is in a domain of growing
contemporary relevance. Permissionless blockchains such as Bitcoin [18] and
Ethereum [19] allow uncertified agents to join a pool of service providers,
also called nodes. A recent feature that has emerged in such blockchains is
the execution of “smart contracts” [9, 19], which could include, for example,
running computationally-heavy jobs such as machine learning algorithms. In an
ideal world, a client who requires a computation to be performed can simply
enter into a smart contract with some particular node in the blockchain, and
pay a transaction cost for the service. Unfortunately, there is no guarantee
that nodes in a permissionless blockchain are honest. A “Byzantine” (or
malicious) node could easily return a quick-to-compute, incorrect output, to
the detriment of the client.

In recent work, Das et al. [9] propose an approach for the probabilistic
verification of smart contracts. Abstractly, assume that the computation to be
performed for the client is deterministic, and it has a (yet unknown) output
$o_{\text{correct}}$. The proposed model accommodates any blockchain in which
the fraction of Byzantine nodes is at most $f_{\max}\in[0,\frac{1}{2})$. With
this assumption, it becomes feasible to give a probabilistic guarantee on
obtaining the correct output. For any fixed mistake probability
$\delta\in(0,1)$, the client could ship out the computation to
$\Theta\left(\frac{1}{(\frac{1}{2}-f_{\max})^{2}}\log(\frac{1}{\delta})\right)$
nodes, and take their majority response as the answer, thereby ensuring
$\delta$-correctness. Unfortunately, transaction costs can be substantial,
especially those for computationally-intensive contracts. Hence, it is in the
client’s interest to minimise the number of nodes queried to achieve the same
probabilistic guarantee. For example, a sequential procedure could potentially
query fewer nodes if $f\ll f_{\max}$.

###  5.1 Comparison with SPRT

Our contribution in the context of this application is to propose PPR-ME as an
alternative to Wald’s Sequential Probability Ratio Test (SPRT) [20], which is
used by Das et al. [9] for their verification procedure. This classical test
finds use in many other engineering applications [21, 22], some of which could
also benefit from the advantages of PPR-ME over SPRT.

To apply SPRT for verifying smart contracts, Das et al. [9] assume that out of
the total of $N$ nodes in the blockchain, batches of size $m$, chosen
uniformly at random, can be queried in sequence. For simplicity assume the
answers returned are from the set $\\{0,1,2,\dots\\}$. Let $q=\frac{m}{N}$,
and $c_{i,t}$ be the number of times answer $i$ is reported in the $t^{th}$
step, $i\geq 0$, $t\geq 1$. Defining $l_{i,T}=\sum_{t=1}^{T}(2c_{i,t}-m)m$, a
derivation [9] establishes that $\delta$-correct SPRT stops at time $T$,
giving $i$ as the answer if

$l_{i,T}>\ln\left(\frac{1-\delta}{\delta}\right)\frac{2q(1-q)N(1-f_{\max})f_{\max}}{1-2f_{\max}}.$

The primary disadvantage of SPRT in this context is the need for the user to
provide $f_{\max}$, which is used in the stopping rule. While a lower value of
$f_{\max}$ will improve the efficiency of the rule, unfortunately
$\delta$-correctness no longer holds if $f$, the true fraction of Byzantine
nodes, exceeds $f_{max}$. Figure 2(a) plots the empirical error made by SPRT
(averaged over 50,000 runs) on a problem instance in which the Byzantine nodes
all give the same (incorrect) answer. We fix $f_{\max}=0.1$, and plot the
error for different settings of $f$. The blockchain has $N=1600$ nodes, of
which SPRT samples $m=20$ at a time. Although the test is run using mistake
probability $\delta=0.005$, observe that the empirical error exceeds $\delta$
when $f>f_{\max}$.

Since the verification task at hand is precisely that of PAC mode estimation,
PPR-ME becomes a viable alternative, especially since it does not need the
knowledge of $f_{\max}$. In fact, PPR-ME can identify the mode even if its
associated probability is less than $\frac{1}{2}$ (although in this case, it
can no longer be guaranteed that the mode is $o_{\text{correct}}$, since the
Byzantine nodes may collude). Observe from Figure 2(a) that unlike SPRT, the
empirical error rate of PPR-ME (equivalent to PPR-Bernoulli since we have set
$K=2$) remains within $\delta$ even for $f>f_{\max}$.

In Figure 2(b), we compare the sample complexities of PPR-ME and SPRT. Whereas
other problem parameters (including $f_{max}$) stay the same as before, we
consider an instance in which $K=10$. The single correct answer is given by a
$(1-f)$-fraction of the nodes, while $9$ different incorrect answers are given
by the Byzantine nodes, each equally common. The version of SPRT used is a 1vr
adaptation of the basic procedure [9] to $K=10$. First, we observe that SPRT
terminates before PPR-1v1 and PPR-1vr at all values of $f$. The PPR algorithms
pay this price for having to assure $\delta$-correctness at all values of
$f<\frac{1}{2}$, unlike SPRT, which does so only for $f<f_{max}$. We show the
performance of another PPR variant, denoted “PPR-Adaptive”, in the same plot.
In reality, we cannot be sure about the number of answers $K$ that will be
returned by the blockchain’s nodes–and hence cannot use it in our stopping
rule. Under PPR-Adaptive, which is a 1v1 strategy, the overall mistake
probability $\delta$ is divided into the infinite sequence
$k\frac{\delta}{1^{2}},k\frac{\delta}{2^{2}},k\frac{\delta}{3^{2}},\dots$
(with $k=\frac{6}{\pi^{2}}$). Whenever a new answer is revealed, it is
inserted into the list of possible answers, and its pairwise tests given
mistake probabilities from the unused portion of the sequence. In principle,
PPR-Adaptive can accommodate any number of answers, incurring only a small
increase in sample complexity, as visible from Figure 2(b).

(a)

(b)

Figure 2: Comparisons with SPRT for the probabilistic verification of smart
contracts, obtained with parameter settings $N=1600$, $m=20$, $\delta=0.005$,
$f_{max}=0.1$. Plot (a) shows the empirical error rates of the algorithms as
the true Byzantine fraction $f$ is varied, taking $K=2$. Plot (b) shows the
sample complexity of various algorithms against varying $f$, on an instance
with $K=10$ answers.

##  6 Conclusion

In this paper, we apply the framework of PPR martingale confidence sequences
to the problem of PAC mode estimation. Our investigation follows two different
dimensions that play a significant role in determining the efficiency of
stopping rules. First is the tightness of the confidence bounds used
internally in the stopping rule. By separately focusing on the Bernoulli case,
we show that the PPR martingale stopping rule is sample-efficient both in
theory and in practice. Our analysis as well as experiments may be of
independent interest to research on pure exploration problems in stochastic
bandits. The second aspect of mode estimation is the template applied to
generalise from $K=2$ to $K\geq 2$, which can typically be applied with any
valid confidence bounds. Of the two major choices—“one-versus-one” (1v1) and
“one-versus-rest” (1vr)—we find 1v1 to be the more efficient.

The PPR-ME algorithm that combines both ideas is simple, computationally
efficient, yet significantly more sample-efficient not only than the recently-
proposed $\mathcal{A}_{1}$ algorithm [2], but many other baselines (including
an improved variant of $\mathcal{A}_{1}$ that we include in our experiments).
To illustrate the practical relevance of PPR-ME, we present two separate real-
world applications in which it can offer significant advantages over earlier
approaches. In sample-based election forecasting, PPR-ME significantly reduces
the sample complexity when paired with the DCB sampling strategy. Analysing
the sample complexity of DCB in terms of its problem parameters remains an
avenue for future work, which could contribute to a growing literature on
sample-based techniques in social choice theory [23, 24]. Our second
application, to probabilistic verification in blockchains, is based on PPR-ME
being relatively assumption-free, which makes it a promising algorithm for
many industrial applications.

## References

  * [1] Ian Waudby-Smith and Aaditya Ramdas.  Confidence sequences for sampling without replacement.  In Advances in Neural Information Processing Systems, volume 33, pages 20204–20214. Curran Associates, Inc., 2020.
  * [2] Dhruti Shah, Tuhinangshu Choudhury, Nikhil Karamchandani, and Aditya Gopalan.  Sequential mode estimation with oracle queries.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 5644–5651. AAAI Press, 2020.
  * [3] Emilie Kaufmann and Wouter Koolen.  Mixture martingales revisited with applications to sequential tests and confidence intervals.  arXiv preprint arXiv:1811.11419, 2018.
  * [4] Kevin Jamieson, Matthew Malloy, Robert Nowak, and Sébastien Bubeck.  lil’ ucb : An optimal exploration algorithm for multi-armed bandits.  In Proceedings of The 27th Conference on Learning Theory, volume 35 of Proceedings of Machine Learning Research, pages 423–439. PMLR, 2014.
  * [5] Emanuel Parzen.  On estimation of a probability density function and mode.  The Annals of Mathematical Statistics, 33(3):1065–1076, 1962.
  * [6] Gurmeet Singh Manku and Rajeev Motwani.  Approximate frequency counts over data streams.  In Proceedings of the 28th International Conference on Very Large Data Bases, VLDB ’02, page 346–357. VLDB Endowment, 2002.
  * [7] J. Misra and David Gries.  Finding repeated elements.  Science of Computer Programming, 2(2):143–152, 1982.
  * [8] Rajeeva Karandikar.  Power and limitations of opinion polls in the context of Indian parliamentary democracy.  In Special Proceeding of 20th Annual Conference of SSCA, pages 09 – 16. Society of Statistics, Computer and Applications, 2018.
  * [9] Sourav Das, Vinay Joseph Ribeiro, and Abhijeet Anand.  YODA: enabling computationally intensive contracts on blockchains with byzantine and selfish nodes.  In 26th Annual Network and Distributed System Security Symposium, NDSS. The Internet Society, 2019.
  * [10] Shivaram Kalyanakrishnan, Ambuj Tewari, Peter Auer, and Peter Stone.  PAC subset selection in stochastic multi-armed bandits.  In Proceedings of the 29th International Conference on International Conference on Machine Learning, ICML’12, page 227–234. Omnipress, 2012.
  * [11] Emilie Kaufmann and Shivaram Kalyanakrishnan.  Information complexity in bandit subset selection.  In Proceedings of the 26th Annual Conference on Learning Theory, volume 30 of Proceedings of Machine Learning Research, pages 228–251. PMLR, 2013.
  * [12] Aurélien Garivier.  Informational confidence bounds for self-normalized averages and applications.  In 2013 IEEE Information Theory Workshop (ITW), pages 1–5. IEEE press, 2013.
  * [13] Steven R Howard, Aaditya Ramdas, Jon McAuliffe, Jasjeet Sekhon, et al.  Time-uniform Chernoff bounds via nonnegative supermartingales.  Probability Surveys, 17:257–317, 2020.
  * [14] Andreas Maurer and Massimiliano Pontil.  Empirical Bernstein bounds and sample variance penalization.  arXiv preprint arXiv:0907.3740, 2009.
  * [15] Rajeeva L. Karandikar, Clive Payne, and Yogendra Yadav.  Predicting the 1998 Indian parliamentary election.  Electoral Studies, 21(1):69–89, 2002.
  * [16] Clive Payne.  Election forecasting in the UK: The BBC’s experience.  Euramerica, 33, 2003.
  * [17] Paul Perry.  Certain problems in election survey methodology.  The Public Opinion Quarterly, 43(3):312–325, 1979.
  * [18] Satoshi Nakamoto.  Bitcoin: A peer-to-peer electronic cash system, http://bitcoin.org/bitcoin.pdf.
  * [19] Vitalik Buterin et al.  A next-generation smart contract and decentralized application platform, https://cryptorating.eu/whitepapers/Ethereum/Ethereum_white_paper.pdf.
  * [20] A. Wald.  Sequential Tests of Statistical Hypotheses.  The Annals of Mathematical Statistics, 16(2):117 – 186, 1945.
  * [21] Kenny C. Gross and Keith E. Humenik.  Sequential probability ratio test for nuclear plant component surveillance.  Nuclear Technology, 93(2):131–137, 1991.
  * [22] R. Chen, J.-M. Park, and K. Bian.  Robust distributed spectrum sensing in cognitive radio networks.  In IEEE INFOCOM 2008 - The 27th Conference on Computer Communications, pages 1876–1884. IEEE Press, 2008.
  * [23] Palash Dey and Arnab Bhattacharyya.  Sample complexity for winner prediction in elections.  In Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems, AAMAS ’15, page 1421–1430. International Foundation for Autonomous Agents and Multiagent Systems, 2015.
  * [24] Arun Rajkumar, Suprovat Ghoshal, Lek-Heng Lim, and Shivani Agarwal.  Ranking from stochastic pairwise preferences: Recovering condorcet winners and tournament solution sets at the top.  In Proceedings of the 32nd International Conference on Machine Learning, volume 37 of Proceedings of Machine Learning Research, pages 665–673. PMLR, 2015.

##  Appendix A Proof of Lemma 3

For a problem instance $\mathcal{P}=(p,v,2)$, our parameters are $p_{1}$ and
$p_{2}=1-p_{1}$, with $p_{1}>0.5$. It suffices to maintain a confidence
sequence on $p_{1}$; termination is achieved when this confidence sequence no
longer contains $\frac{1}{2}$. To upper-bound the number of samples needed for
termination, we proceed in three steps.

  1. 1.

At time $t$, there are $2^{t}$ possible 0-1 sequence that the Bernoulli
variable can produce in $t$ steps. Let $X^{t}$ be a random variable denoting
this $t$-length 0-1 sequence. Let $k$ denote the number of $1$’s in $X^{t}$.
In Section A.1, we find the range of $k$ for which
$\mathds{1}\left\\{R_{t}(\frac{1}{2})\geq\frac{1}{\delta}\right\\}$.

  2. 2.

Next, in Section A.2, we use the range of $k$ derived in Section A.1 to derive
a sufficient condition for $t$ to be the sample complexity.

  3. 3.

In Section A.3, we use the sufficient condition derived in Section A.2 to
obtain a closed-form sample complexity upper bound. We separately take up two
cases, $p_{1}\leq 0.6$, and $p_{1}>0.6$, so as to tighten the constants in the
upper bound.

###  A.1 Finding a Range of $k$ for which
$\mathds{1}\left\\{R_{t}(\frac{1}{2})\geq\frac{1}{\delta}\right\\}$

The stopping rule does not terminate at $t$ so long as
$R_{t}\left(\frac{1}{2}\right)<\frac{1}{\delta}$.

$\displaystyle\mathbb{P}\left(R_{t}\left(\frac{1}{2}\right)\geq\frac{1}{\delta}\right)=\sum_{X^{t}}\mathds{1}\left\\{R_{t}\left(\frac{1}{2}\right)\geq\frac{1}{\delta}\right\\}P_{p_{1}}(X^{t})$

The expression inside the indicator random variable can be simplified to
obtain the following:

$\displaystyle\mathds{1}\left\\{R_{t}\left(\frac{1}{2}\right)\geq\frac{1}{\delta}\right\\}=\mathds{1}\left\\{\frac{1}{\pi_{t}(1/2)}\geq\frac{1}{\delta}\right\\}=\mathds{1}\left\\{\frac{\int_{\eta=0}^{1}P_{\eta}(X^{t})d\eta}{P_{1/2}(X^{t})}\geq\frac{1}{\delta}\right\\}.$

The sum inside the indicator function is independent of the position of 0-1
outcomes within the sequence $X^{t}$ and only depends on the number of zeros
and ones in the instance. Suppose we consider the instances which contain $k$
ones; then, we have

$\displaystyle\mathds{1}\left\\{R_{t}\left(\frac{1}{2}\right)\geq\frac{1}{\delta}\right\\}=\mathds{1}\left\\{\delta\geq\frac{(t+1)!}{k!(t-k)!}\left(\frac{1}{2}\right)^{k}\left(\frac{1}{2}\right)^{t-k}\right\\}.$

From the above equations, we derive the exact expression for
$\mathbb{P}(R_{t}(\frac{1}{2})\geq\frac{1}{\delta})$:

$\displaystyle\mathbb{P}\left(R_{t}\left(\frac{1}{2}\right)\geq\frac{1}{\delta}\right)=\sum_{k=0}^{t}\binom{t}{k}p_{1}^{k}(1-p_{1})^{t-k}\mathds{1}\left\\{\delta\geq\frac{(t+1)!}{k!(t-k)!}2^{-t}\right\\}.$

We now break the expression into two parts.

$\displaystyle\mathbb{P}\left(R_{t}\left(\frac{1}{2}\right)\geq\frac{1}{\delta}\right)$
$\displaystyle=\sum_{k=0}^{t}\binom{t}{k}p_{1}^{k}(1-p_{1})^{t-k}\mathds{1}\left\\{\delta\geq\frac{(t+1)!}{k!(t-k)!}2^{-t}\right\\}$
$\displaystyle=$
$\displaystyle\sum_{k=0}^{\left\lfloor{\frac{t}{2}}\right\rfloor}\binom{t}{k}p_{1}^{k}(1-p_{1})^{t-k}\mathds{1}\left\\{\frac{\delta}{t+1}\geq\binom{t}{k}2^{-t}\right\\}+$
$\displaystyle\sum_{k=\left\lfloor{\frac{t}{2}}\right\rfloor+1}^{t}\binom{t}{k}p_{1}^{k}(1-p_{1})^{t-k}\mathds{1}\left\\{\frac{\delta}{t+1}\geq\binom{t}{t-k}2^{-t}\right\\}.$

We have split the summation in this manner as it allows to use the following
commonly-known 222See, for example, https://arxiv.org/pdf/1406.7872.pdf.
inequality for the binomial coefficients inside the indicator function.

$\binom{t}{\alpha t}\leq 2^{tH_{b}(\alpha)}\,\,\text{where $t\in\mathbb{N}$
and $\alpha\in\left[0,\frac{1}{2}\right].$}$

The definition of binary entropy function $H_{b}$ for $p\in[0,1]$ is:

$H_{b}(p)=\begin{cases}0&p\in\\{0,1\\},\\\
-p\log_{2}p-(1-p)\log_{2}(1-p)&\text{otherwise.}\\\ \end{cases}$

Invoking this inequality in the probability expression, we arrive at the lower
bound:

$\displaystyle\mathbb{P}\left(R_{t}\left(\frac{1}{2}\right)\geq\frac{1}{\delta}\right)\geq$
$\displaystyle\sum_{k=0}^{\left\lfloor{\frac{t}{2}}\right\rfloor}\binom{t}{k}p_{1}^{k}(1-p_{1})^{t-k}\mathds{1}\left\\{\frac{1}{t}\log_{2}\left(\frac{\delta}{t+1}\right)+1\geq
H_{b}\left(\frac{k}{t}\right)\right\\}+$
$\displaystyle\sum_{k=\left\lfloor{\frac{t}{2}}\right\rfloor+1}^{t}\binom{t}{k}p_{1}^{k}(1-p_{1})^{t-k}\mathds{1}\left\\{\frac{1}{t}\log_{2}\left(\frac{\delta}{t+1}\right)+1\geq
H_{b}\left(\frac{t-k}{t}\right)\right\\}.$

Using the fact that

$H_{b}(p)\leq 2\sqrt{p(1-p)}\,\,\text{if}\,\,p\leq\frac{1}{2},$

the summation is further lower-bounded:

$\displaystyle\mathbb{P}\left(R_{t}\left(\frac{1}{2}\right)\geq\frac{1}{\delta}\right)\geq$
$\displaystyle\sum_{k=0}^{t}\binom{t}{k}p_{1}^{k}(1-p_{1})^{t-k}\mathds{1}\left\\{\frac{1}{2}\left[\log_{2}\left(\frac{\delta}{t+1}\right)+t\right]\geq\sqrt{k(t-k)}\right\\}.$

We will later see that for the $t$ we find as the bound,
$\log_{2}\left(\frac{\delta}{t+1}\right)+t\geq 0$. Hence, we can take the
square of both sides. By using that fact and solving the quadratic, the range
of $k$ which satisfies the condition inside the indicator function is:

$k\in\left[0,\frac{t-\sqrt{t^{2}-4\beta^{2}}}{2}\right]\bigcup\left[\frac{t+\sqrt{t^{2}-4\beta^{2}}}{2},t\right]\,\,\text{where}\,\,\beta=\frac{1}{2}\left[\log_{2}\left(\frac{\delta}{t+1}\right)+t\right].$

Slightly loosening this bound, we get

$\displaystyle
k\in\left[0,\frac{t-\sqrt{2t\log_{2}\left(\frac{t+1}{\delta}\right)}}{2}\right]\bigcup\left[\frac{t+\sqrt{2t\log_{2}\left(\frac{t+1}{\delta}\right)}}{2},t\right].$

In short, if $k$ lies in the range above, then it must satisfy
$\mathds{1}\left\\{R_{t}(\frac{1}{2})\geq\frac{1}{\delta}\right\\}$. Call this
range $R$.

###  A.2 Finding a Sufficient condition for $t$ to be the Sample Complexity

We will lower bound the probability of $\sum_{k\in R}p_{1}^{k}(1-p_{1})^{t-k}$
by $1-\delta$, and thus find the values of $t$ satisfying this equation. To
that end, we use another commonly-known 333See Theorem 2.1 in
https://arxiv.org/abs/1801.03365. result to bound the tail probability for a
binomial random variable: for $\epsilon>0$,

$\displaystyle\mathbb{P}(H(t)\geq(p_{1}+\epsilon)t)\leq
e^{-D_{KL}(p_{1}+\epsilon||p_{1})t},$
$\displaystyle\mathbb{P}(H(t)\leq(p_{1}-\epsilon)t)\leq
e^{-D_{KL}(p_{1}-\epsilon||p_{1})t}.$

Using this in our working, considering $H(t)$ as a binomial random variable,
we get

$\displaystyle\sum_{k=(p_{1}-\epsilon)t}^{(p_{1}+\epsilon)t}\binom{t}{k}p_{1}^{k}(1-p_{1})^{t-k}=\mathbb{P}\left(\left(p_{1}-\epsilon\right)t\leq
H(t)\leq\left(p_{1}+\epsilon\right)t\right)$ $\displaystyle\geq
1-e^{-D_{KL}(p_{1}+\epsilon||p_{1})t}-e^{-D_{KL}(p_{1}-\epsilon||p_{1})t}$
$\displaystyle\implies\mathbb{P}\left(R_{t}\left(\frac{1}{2}\right)\leq\frac{1}{\delta}\right)\leq
e^{-D_{KL}(p_{1}+\epsilon||p_{1})t}+e^{-D_{KL}(p_{1}-\epsilon||p_{1})t}.$

We want
$\mathbb{P}\left(R_{t}\left(\frac{1}{2}\right)>\frac{1}{\delta}\right)\geq
1-\delta$. A sufficient condition for the above to hold is

$\displaystyle\max\left(e^{-D_{KL}(p_{1}+\epsilon||p_{1})t},e^{-D_{KL}(p_{1}-\epsilon||p_{1})t}\right)\leq\frac{\delta}{2}$
$\displaystyle\implies
t\times\min(D_{KL}(p_{1}+\epsilon||p_{1}),D_{KL}(p_{1}-\epsilon||p_{1}))\geq\ln\left(\frac{2}{\delta}\right)$

We note that $p_{1}>\frac{1}{2}$. We take a short detour to prove the
following fact.

######  Fact 5.

$D_{KL}(c+y||c)\geq D_{KL}(c-y||c)$, $c>0.5,y\leq 1-c$.

###### Proof.

We want to show that

$\displaystyle D_{KL}(c+y||c)\geq D_{KL}(c-y||c),c>0.5,y\leq 1-c$
$\displaystyle\Leftrightarrow(c+y)\log\left(\frac{c+y}{c}\right)+(1-c-y)\ln\left(\frac{1-c-y}{c}\right)\geq(c-y)\ln\left(\frac{c-y}{c}\right)+(1-c+y)\ln\left(\frac{1-c+y}{c}\right)$
$\displaystyle\Leftrightarrow(c+y)\ln(c+y)+(1-c-y)\ln(1-c-y)\geq(c-y)\ln(c-y)+(1-c+y)\ln(1-c+y).$

Let

$\displaystyle
f(y)=(c+y)\ln(c+y)+(1-c-y)\ln(1-c-y)-(c-y)\ln(c-y)-(1-c+y)\ln(1-c+y).$
$\displaystyle\text{Then
}f^{\prime}(y)=\ln\left(\frac{(c+y)(c-y)}{(1-c+y)(1-c-y)}\right).$
$\displaystyle c\geq 1-c\implies\frac{c^{2}-y^{2}}{(1-c)^{2}-y^{2}}\geq
1\implies\ln\left(\frac{(c+y)(c-y)}{(1-c+y)(1-c-y)}\right)\geq 0$
$\displaystyle\implies f^{\prime}(y)\geq 0.$

Thus, we showed that $f^{\prime}(y)\geq 0$. Since $f(0)=0$, we have $f(y)\geq
0\>\forall\>y\in\left[0,1-c\right]$. ∎

Thus, we are left with the sufficient condition for $t$ as

$\displaystyle t\times
D_{KL}(p_{1}-\epsilon||p_{1})\geq\ln\left(\frac{2}{\delta}\right),$
$\displaystyle\epsilon=p_{1}-\frac{1}{2}\left(1+\sqrt{\frac{2\log_{2}\left(\frac{t+1}{\delta}\right)}{t}}\right),\epsilon\geq
0.$

We will note that $\epsilon\geq 0$ holds later. For now, we try to find
stronger sufficient conditions on $t$. To that end, we use that

$\displaystyle D_{KL}(x||y)\geq\frac{(x-y)^{2}}{2y},x\leq y$
$\displaystyle\implies
D_{KL}\left(p_{1}-\epsilon||p_{1}\right)\geq\frac{\epsilon^{2}}{2p_{1}}.$

So, a sufficient condition for

$\displaystyle t\times
D_{KL}(p_{1}-\epsilon||p_{1})\geq\ln\left(\frac{2}{\delta}\right)$

is given as

$\displaystyle\frac{t\epsilon^{2}}{2p_{1}}\geq\ln\left(\frac{2}{\delta}\right)$
$\displaystyle\implies
t\geq\frac{2p_{1}}{\epsilon^{2}}\ln\left(\frac{2}{\delta}\right).$

To find a sufficient condition for $t$ to satisfy the above, we can find a
lower bound on $\epsilon^{2}$ and use it in the expression above. We have

$\displaystyle\epsilon^{2}=\left(\left(p_{1}-\frac{1}{2}\right)-\sqrt{\frac{\log_{2}\left(\frac{t+1}{\delta}\right)}{2t}}\right)^{2}$
$\displaystyle=\left(p_{1}-\frac{1}{2}\right)^{2}+\frac{\log_{2}\left(\frac{t+1}{\delta}\right)}{2t}-2\left(p_{1}-\frac{1}{2}\right)\sqrt{\frac{\log_{2}\left(\frac{t+1}{\delta}\right)}{2t}}$
$\displaystyle\implies\epsilon^{2}\geq\left(p_{1}-\frac{1}{2}\right)^{2}-2\left(p_{1}-\frac{1}{2}\right)\sqrt{\frac{\log_{2}\left(\frac{t+1}{\delta}\right)}{2t}}.$

###  A.3 Constant factor tightening

To obtain our final bound, we consider two cases: $p_{1}\leq 0.6,p_{1}>0.6$.

####  A.3.1 Case 1: $p_{1}\leq 0.6$

We will find a sufficient condition on $t$ for the fact that

$\displaystyle\frac{t}{C_{1}}\left(p_{1}-\frac{1}{2}\right)^{2}\geq\log_{2}\left(\frac{t+1}{\delta}\right)$
(2)

where $C_{1}=2.4488$.
Earlier in the proof, we have used the fact that
$\log_{2}\left(\frac{\delta}{t+1}\right)+t\geq 0$. We first prove this fact.
For $p_{1}\in(\frac{1}{2},1]$,
$\frac{\left(p_{1}-\frac{1}{2}\right)^{2}}{C_{1}}\leq 1$. So, from (2), we can
easily see that $\log_{2}\left(\frac{\delta}{t+1}\right)+t\geq 0$.
We find a sufficient $t$ such that

$\displaystyle\frac{t}{C_{1}}\left(p_{1}-\frac{1}{2}\right)^{2}\geq\log_{2}\left(\frac{t+1}{\delta}\right)$
$\displaystyle\implies
t\geq\frac{C_{1}}{(p_{1}-\frac{1}{2})^{2}}\log_{2}\left(\frac{t+1}{\delta}\right).$

We let $t$ be of the form

$\displaystyle
t=\frac{C_{1}C_{2}}{(p_{1}-\frac{1}{2})^{2}}\log_{2}\left(\frac{C_{1}}{(p_{1}-\frac{1}{2})^{2}\delta}\right),$

where $C_{2}$ is a constant. Note that, for this choice of $t$, (We will show
later that $t\geq 4000$ is also true for the first line below to hold),

$\displaystyle t+1\leq 1.00025t.$
$\displaystyle\frac{C_{1}}{(p_{1}-\frac{1}{2})^{2}}\log_{2}\left(\frac{t+1}{\delta}\right)\leq\frac{C_{1}}{(p_{1}-\frac{1}{2})^{2}}\log_{2}\left(\frac{1.00025t}{\delta}\right).$
$\displaystyle\frac{C_{1}}{(p_{1}-\frac{1}{2})^{2}}\log_{2}\left(\frac{t+1}{\delta}\right)\leq\frac{C_{1}}{(p_{1}-\frac{1}{2})^{2}}\log_{2}(1.00025C_{2})+0.3839\frac{C_{1}}{(p_{1}-\frac{1}{2})^{2}}\log_{2}\left(\frac{C_{1}}{(\theta-\frac{1}{2})^{2}\delta}\right)+$
$\displaystyle\frac{C_{1}}{(p_{1}-\frac{1}{2})^{2}}\log_{2}\left(\frac{C_{1}}{(p_{1}-\frac{1}{2})^{2}\delta}\right),$

where the last step is true because

$\displaystyle\log_{2}\left(\log_{2}\left(\frac{C_{1}}{(p_{1}-\frac{1}{2})^{2}\delta}\right)\right)\leq
0.3839\log_{2}\left(\frac{C_{1}}{(p_{1}-\frac{1}{2})^{2}\delta}\right)$

using that, for $x\geq 200$,

$\displaystyle\log_{2}\left(\log_{2}\left(x\right)\right)\leq
0.3839\log_{2}\left(x\right).$

Thus, we get

$\displaystyle\frac{C_{1}}{(p_{1}-\frac{1}{2})^{2}}\log_{2}\left(\frac{t+1}{\delta}\right)\leq\frac{C_{1}}{(p_{1}-\frac{1}{2})^{2}}\log_{2}\left(\frac{C_{1}}{(p_{1}-\frac{1}{2})^{2}\delta}\right)\left(1.3839+\log_{2}\left(1.00025C_{2}\right)\right)$
$\displaystyle\leq\frac{C_{1}}{(p_{1}-\frac{1}{2})^{2}}\log_{2}\left(\frac{C_{1}}{(p_{1}-\frac{1}{2})^{2}\delta}\right)C_{2}$

where the last step is true when $C_{2}=2.9402$. Thus,

$\displaystyle
t=\frac{2C_{1}C_{2}p_{1}}{(p_{1}-\frac{1}{2})^{2}}\log_{2}\left(\frac{C_{1}}{(p_{1}-\frac{1}{2})^{2}\delta}\right)\implies
t=\frac{C_{3}p_{1}}{(p_{1}-\frac{1}{2})^{2}}\ln\left(\frac{C_{1}}{(p_{1}-\frac{1}{2})^{2}\delta}\right),$

where $C_{3}=20.775\geq 2C_{1}C_{2}\log_{2}(e)$ satisfies the above
inequality.

So now, if the condition on $t$ is satisfied, we have

$\displaystyle\epsilon^{2}\geq\left(p_{1}-\frac{1}{2}\right)^{2}-2\left(p_{1}-\frac{1}{2}\right)\sqrt{\frac{\log_{2}\left(\frac{t+1}{\delta}\right)}{2t}}\geq\left(p_{1}-\frac{1}{2}\right)^{2}-2\left(p_{1}-\frac{1}{2}\right)\frac{\left(p_{1}-\frac{1}{2}\right)}{2.21305}$
$\displaystyle\implies\epsilon^{2}\geq
C_{4}\left(p_{1}-\frac{1}{2}\right)^{2},$

where $C_{4}=0.09627$.
Previously, we had remarked that it was sufficient to have

$\displaystyle
t\geq\frac{2p_{1}}{\epsilon^{2}}\ln\left(\frac{2}{\delta}\right).$

We can loosen this by using the lower bound on $\epsilon$ to: it is sufficient
to satisfy

$\displaystyle
t\geq\frac{C_{5}p_{1}}{\left(p_{1}-\frac{1}{2}\right)^{2}}\ln\left(\frac{2}{\delta}\right),$

where $C_{5}=20.775$.
To make both the lower bound on $\epsilon$ and the above equation valid, we
note that the following choice of $t$ works:

$\displaystyle
t=\frac{C_{5}p_{1}}{\left(p_{1}-\frac{1}{2}\right)^{2}}\max\left(\left(\ln\left(\frac{C_{1}}{(p_{1}-\frac{1}{2})^{2}\delta}\right),\ln\left(\frac{2}{\delta}\right)\right)\right)$

We note that this leaves us with the following choice of $t$:

$\displaystyle
t=\frac{20.775p_{1}}{\left(p_{1}-\frac{1}{2}\right)^{2}}\left(\ln\left(\frac{2.45}{(p_{1}-\frac{1}{2})^{2}\delta}\right)\right)$

Note that $t\geq 4000$, since $p_{1}\leq 0.6$.

####  A.3.2 Case 2: $p_{1}>0.6$

We will find a sufficient condition on $t$ for the fact that

$\displaystyle\frac{t}{C_{1}}\left(p_{1}-\frac{1}{2}\right)^{2}\geq\log_{2}\left(\frac{t+1}{\delta}\right)$

where $C_{1}=2.4877$.
Using the same argument as in case 1, here also we can prove that
$\log_{2}\left(\frac{\delta}{t+1}\right)+t\geq 0$.
We find a sufficient $t$ such that

$\displaystyle\frac{t}{C_{1}}\left(p_{1}-\frac{1}{2}\right)^{2}\geq\log_{2}\left(\frac{t+1}{\delta}\right)$
$\displaystyle\implies
t\geq\frac{C_{1}}{(p_{1}-\frac{1}{2})^{2}}\log_{2}\left(\frac{t+1}{\delta}\right).$

We let $t$ be of the form

$\displaystyle
t=\frac{C_{1}C_{2}}{(p_{1}-\frac{1}{2})^{2}}\log_{2}\left(\frac{C_{1}}{(p_{1}-\frac{1}{2})^{2}\delta}\right),$

where $C_{2}$ is a constant.
Note that, for this choice of $t$, (We will show later that $t\geq 100$ is
also true for the first line to hold)

$\displaystyle t+1\leq 1.01t.$
$\displaystyle\frac{C_{1}}{(p_{1}-\frac{1}{2})^{2}}\log_{2}\left(\frac{t+1}{\delta}\right)\leq\frac{C_{1}}{(p_{1}-\frac{1}{2})^{2}}\log_{2}\left(\frac{1.01t}{\delta}\right).$
$\displaystyle\frac{C_{1}}{(p_{1}-\frac{1}{2})^{2}}\log_{2}\left(\frac{t+1}{\delta}\right)\leq\frac{C_{1}}{(p_{1}-\frac{1}{2})^{2}}\log_{2}(1.01C_{2})+0.5228\frac{C_{1}}{(p_{1}-\frac{1}{2})^{2}}\log_{2}\left(\frac{C_{1}}{(\theta-\frac{1}{2})^{2}\delta}\right)+$
$\displaystyle\frac{C_{1}}{(p_{1}-\frac{1}{2})^{2}}\log_{2}\left(\frac{C_{1}}{(p_{1}-\frac{1}{2})^{2}\delta}\right),$

where the last step is true because

$\displaystyle\log_{2}\left(\log_{2}\left(\frac{C_{1}}{(p_{1}-\frac{1}{2})^{2}\delta}\right)\right)\leq
0.5228\log_{2}\left(\frac{C_{1}}{(p_{1}-\frac{1}{2})^{2}\delta}\right)$

using that, for $x\geq 9.64$,

$\displaystyle\log_{2}\left(\log_{2}\left((x\right)\right)\leq
0.5228\log_{2}\left(x\right)$

Thus, we get

$\displaystyle\frac{C_{1}}{(p_{1}-\frac{1}{2})^{2}}\log_{2}\left(\frac{t+1}{\delta}\right)\leq\frac{C_{1}}{(p_{1}-\frac{1}{2})^{2}}\log_{2}\left(\frac{C_{1}}{(p_{1}-\frac{1}{2})^{2}\delta}\right)\left(1.5228+\log_{2}\left(1.01C_{2}\right)\right)$
$\displaystyle\leq\frac{C_{1}}{(p_{1}-\frac{1}{2})^{2}}\log_{2}\left(\frac{C_{1}}{(p_{1}-\frac{1}{2})^{2}\delta}\right)C_{2},$

where the last step is true when $C_{2}=3.228$. Thus, using that $p_{1}>0.6$
by writing that $\frac{p_{1}}{0.6}\geq 1$, we have that

$\displaystyle
t=\frac{1.67C_{1}C_{2}p_{1}}{(p_{1}-\frac{1}{2})^{2}}\log_{2}\left(\frac{C_{1}}{(p_{1}-\frac{1}{2})^{2}\delta}\right)\implies
t=\frac{C_{3}p_{1}}{(p_{1}-\frac{1}{2})^{2}}\ln\left(\frac{C_{1}}{(p_{1}-\frac{1}{2})^{2}\delta}\right),$

where $C_{3}=19.35\geq 1.67C_{1}C_{2}\log_{2}(e)$ satisfies the above
inequality.

So now, if the condition on $t$ is satisfied, we have

$\displaystyle\epsilon^{2}\geq\left(p_{1}-\frac{1}{2}\right)^{2}-2\left(p_{1}-\frac{1}{2}\right)\sqrt{\frac{\log_{2}\left(\frac{t+1}{\delta}\right)}{2t}}\geq\left(p_{1}-\frac{1}{2}\right)^{2}-2\left(p_{1}-\frac{1}{2}\right)\frac{\left(p_{1}-\frac{1}{2}\right)}{2.2305}$
$\displaystyle\implies\epsilon^{2}\geq
C_{4}\left(p_{1}-\frac{1}{2}\right)^{2},$

where $C_{4}=0.1033$.
Previously, we had remarked that it was sufficient to have

$\displaystyle
t\geq\frac{2p_{1}}{\epsilon^{2}}\ln\left(\frac{2}{\delta}\right).$

We can loosen this by using the lower bound on $\epsilon$ to: it is sufficient
to satisfy

$\displaystyle
t\geq\frac{C_{5}p_{1}}{\left(p_{1}-\frac{1}{2}\right)^{2}}\ln\left(\frac{2}{\delta}\right),$

where $C_{5}=19.36$.
To make both the lower bound on $\epsilon$ and the above equation valid, we
note that the following choice of $t$ works:

$\displaystyle
t=\frac{C_{5}p_{1}}{\left(p_{1}-\frac{1}{2}\right)^{2}}\max\left(\left(\ln\left(\frac{C_{1}}{(p_{1}-\frac{1}{2})^{2}\delta}\right),\ln\left(\frac{2}{\delta}\right)\right)\right).$

We note that this leaves us with the following choice of $t$:

$\displaystyle
t=\frac{19.36p_{1}}{\left(p_{1}-\frac{1}{2}\right)^{2}}\left(\ln\left(\frac{2.49}{(p_{1}-\frac{1}{2})^{2}\delta}\right)\right)$

Note that $t\geq 106$.

Combining both the above bounds, we have that

$\displaystyle
t=\frac{19.36p_{1}}{\left(p_{1}-\frac{1}{2}\right)^{2}}\left(\ln\left(\frac{2.49}{(p_{1}-\frac{1}{2})^{2}\delta}\right)\right)$

is sufficient.

Looking over both cases, we note

$\displaystyle
t=\frac{20.775p_{1}}{\left(p_{1}-\frac{1}{2}\right)^{2}}\left(\ln\left(\frac{2.49}{(p_{1}-\frac{1}{2})^{2}\delta}\right)\right)$

is sufficient. We denote $C_{6}=20.775,C_{7}=2.49$ to get

$\displaystyle
t=\frac{C_{6}p_{1}}{\left(p_{1}-\frac{1}{2}\right)^{2}}\left(\ln\left(\frac{C_{7}}{(p_{1}-\frac{1}{2})^{2}\delta}\right)\right)$

as an upper bound on the sample complexity of PPR-Bernoulli with probability
atleast $1-\delta$.

##  Appendix B Calculation in Proof of Theorem 4

We have to show $u<(1-l)(p_{1}+p_{j})t$ for $t>t^{\star}$, where

$\displaystyle u$
$\displaystyle=\frac{20.775q_{1}}{(q_{1}-\frac{1}{2})^{2}}\ln\left(\frac{2.49}{(q_{1}-\frac{1}{2})^{2}\delta^{\prime}}\right),$
$\displaystyle q_{1}$ $\displaystyle=\frac{p_{1}}{p_{1}+p_{j}},$
$\displaystyle l$
$\displaystyle=\sqrt{\frac{2\ln(1/\delta^{\prime})}{(p_{1}+p_{j})t}},\text{
and}$ $\displaystyle t^{\star}$
$\displaystyle=\frac{194.07p_{1}}{(p_{1}-p_{2})^{2}}\ln\left(\sqrt{\frac{79.68(k-1)}{\delta}}\frac{p_{1}}{(p_{1}-p_{2})}\right).$

First, observe that

$u=\frac{83.1p_{1}(p_{1}+p_{j})}{(p_{1}-p_{j})^{2}}\ln\left(\frac{9.96(p_{1}+p_{j})^{2}}{(p_{1}-p_{j})^{2}\delta^{\prime}}\right)\leq\frac{83.1p_{1}(p_{1}+p_{j})}{(p_{1}-p_{2})^{2}}\ln\left(\frac{39.84p_{1}^{2}}{(p_{1}-p_{2})^{2}\delta^{\prime}}\right).$

Thus, we have

$\displaystyle\frac{u}{(p_{1}+p_{j})t^{*}}<0.85640\frac{\ln\left(\frac{39.84p_{1}^{2}}{(p_{1}-p_{2})^{2}\delta^{\prime}}\right)}{\ln\left(\frac{79.68(k-1)}{\delta}\frac{p_{1}^{2}}{(p_{1}-p_{2})^{2}}\right)}=0.85640.$

It suffices to show that $l\leq 0.1436$, which is established by the steps
below.

$\displaystyle l^{2}$
$\displaystyle\leq\frac{2\ln\left(1/\delta^{\prime}\right)(p_{1}-p_{2})^{2}}{(p_{1}+p_{j})97.035p_{1}\ln\left(\frac{79.68(k-1)p_{1}^{2}}{\delta(p_{1}-p_{2})^{2}}\right)}\leq\frac{2(p_{1}-p_{2})^{2}}{(p_{1}+p_{j})97.035p_{1}}\leq\frac{2}{97.035}$
$\displaystyle\implies l\leq\frac{1}{\sqrt{97.035/2}}<0.1436.$

##  Appendix C Implementation Details

We specify the various baseline algorithms used in our comparisons in sections
2 and 3. For actual code see Appendix D.

Whether the implementation is 1v1 or 1vr, each algorithm has an atomic
operation to maintain upper and lower confidence bounds on the parameter of a
Bernoulli distribution.

  * •

In the 1v1 approach, there is a separate Bernoulli associated with each pair
of values $v_{i}$ and $v_{j}$ for $i\leq i<j\leq k$ (hence a Bernoulli with
mean $\frac{p_{i}}{p_{i}+p_{j}}$). Each confidence bound is drawn with mistake
probability $\frac{\delta}{K-1}$, which ensures $\delta$-correctness upon
termination.

  * •

In the 1vr approach, there is a separate Bernoulli associated with each value
$v_{i}$ for $i\leq i\leq k$, taking $\neg v_{i}$ as its other outcome (hence a
Bernoulli with mean $p_{i}$). To ensure $\delta$-correctness upon termination,
the mistake probability used is $\frac{\delta}{K}$.

The actual confidence bounds used in different algorithms are listed below. In
1v1, the total number of samples ($t$) shown in the confidence bounds is to be
taken as the sum of the number of occurrences of the corresponding
$(v_{i},v_{j})$ pair in question, while under 1vr, it is the total number of
samples of $\mathcal{P}$ observed yet. Below we denote the empirical mean
after $t$ samples $\hat{p}^{t}$, and the mistake probability associated with
the confidence bound $\alpha$.

###  C.1 $\mathcal{A}_{1}$ [2]

We implement the algorithm as given in the original paper [2], which defines a
confidence width

$\beta^{t}=\sqrt{\frac{2V^{t}\text{ln}(4t^{2}/\alpha)}{t}}+\frac{7\text{ln}(4t^{2}/\alpha)}{3(t-1)}$

after $t$ samples, where $V^{t}$ is the empirical variance of the samples.
Lower and upper confidence bounds are given by $\hat{p}^{t}\pm\beta^{t}$.

###  C.2 LUCB [10] and KL-LUCB [11]

For LUCB [10] and KL-LUCB [11], the “exploration rate” used is
$\beta(t,\alpha)=\text{ln}(\frac{405.5t^{1.1}}{\alpha})$, which ensures
$\alpha$ correctness when a union bound over $t$ is performed [11].

LUCB sets its lower and upper confidence bounds as
$\hat{p}^{t}\pm\sqrt{\frac{\beta(t,\alpha)}{2t}}$. KL-LUCB obtains them by
performing a numerical computation to obtain the lower and upper confidence
bounds as given below.

KL-LUCB lower confidence bound
$\displaystyle=\min\\{q\in[0,\hat{p}^{t}]:t\times
D_{KL}(\hat{p}^{t}||q)\leq\beta(t,\alpha)\\};$ KL-LUCB upper confidence bound
$\displaystyle=\max\\{q\in[\hat{p}^{t},1]:t\times
D_{KL}(\hat{p}^{t}||q)\leq\beta(t,\alpha)\\}.$

###  C.3 KL-SN [12]

KL-SN [12] uses a more sophisticated exploration rate so as to avoid a naïve
union bound over time. We first find $\gamma>1$ that satisfies the following
equation, and thereafter set the exploration rate as given below.

$2e^{2}\gamma e^{-\gamma}=\alpha\text{ and
}\beta(t,\alpha)=\frac{\gamma(1+\text{ln}(\gamma))}{(\gamma-1)\text{ln}(\gamma)}\text{ln(ln}(t))+\gamma.$

Using the above exploration rate, the confidence bounds are constructed in the
same way as KL-LUCB.

KL-SN lower confidence bound $\displaystyle=\min\\{q\in[0,\hat{p}^{t}]:t\times
D_{KL}(\hat{p}^{t}||q)\leq\beta(t,\alpha)\\};$ KL-SN upper confidence bound
$\displaystyle=\max\\{q\in[\hat{p}^{t},1]:t\times
D_{KL}(\hat{p}^{t}||q)\leq\beta(t,\alpha)\\}.$

##  Appendix D Code Details

The code used to run our experiments (from sections 2, 3, 4, and 5) is
included in the supplementary material in a zip file. Below we provide details
on the running time of our algorithms on a couple of problem instances, which
are indicative of their relative order in general.

The results in Table 1 were obtained by performing each of the experiments for
$100$ iterations, with mistake probability $\delta=0.01$. For the last $3$
rows, for all algorithms except KL-SN 1v1, $200$ iterations were used so as to
reduce the error bars. A running-time comparison of all the algorithms across
the $100$ runs is given in Table 3. The runs were performed on an Intel Core
i7-8750H CPU @ 2.20GHz processor.

Table 3: Average running time and one standard error of mode estimation
algorithms across $100$ iterations, distribution
$\mathcal{P}_{6}=(.35,.33,.04\times 8)$ from Table 1.

.  Algorithm Type Run time (seconds) $\mathcal{A}_{1}$ 1vr 9.01 $\pm$ 0.2 1v1
6.65 $\pm$ 0.17 KL-SN 1vr 169.47 $\pm$ 5.76 1v1 17.23 $\pm$ 0.68 PPR 1vr 51.5
$\pm$ 2.37 1v1 1.28 $\pm$ 0.06

The results in Table 2 were obtained by performing each of the experiments for
10 random seeds and setting the mistake probability to $0.01$. The sampling of
the votes from each of the constituencies were done with a batch size of 200.
We used Google’s colaboratory services 444https://colab.research.google.com/
for performing the experiments associated to Table 2.

Table 4: Average running time of various stopping rules when coupled with (1) round-robin (RR) polling of constituencies and (2) DCB. All experiments are run with mistake probability $\delta=0.01$. Values shown below are averages from 3 runs, and show one standard error.  Algorithm | India-2014 (543 seats) | Bihar-2015 (242 seats)
---|---|---
Run time (seconds) | Run time (seconds)
RR-$\mathcal{A}_{1}$-1v1 |  137.57 $\pm$ 1.04 |  247.29 $\pm$ 3.90
RR-$\mathcal{A}_{1}$-1vr |  315.22 $\pm$ 4.69 |  332.65 $\pm$ 11.54
RR-KLSN-1v1 |  57.46 $\pm$ 0.33 |  138.62 $\pm$ 5.41
RR-KLSN-1vr |  247.02 $\pm$ 0.98 |  249.33 $\pm$ 3.64
RR-PPR-1v1 | 48.01 $\pm$ 0.58 | 105.16 $\pm$ 4.40
RR-PPR-1vr |  248.62 $\pm$ 4.90 |  247.32 $\pm$ 10.12
DCB-$\mathcal{A}_{1}$-1v1 |  2959.36 $\pm$ 15.39 |  1464.87 $\pm$ 30.54
DCB-$\mathcal{A}_{1}$-1vr |  1864.51 $\pm$ 8.49 |  723.34 $\pm$ 14.32
DCB-KLSN-1v1 |  3007.40 $\pm$ 40.55 |  3714.78 $\pm$ 14.15
DCB-KLSN-1vr |  629.23 $\pm$ 1.35 |  358.71 $\pm$ 12.26
DCB-PPR-1v1 | 36.21 $\pm$ 0.21 | 63.98 $\pm$ 2.60
DCB-PPR-1vr |  503.82 $\pm$ 4.21 |  316.38 $\pm$ 3.76

##  Appendix E Relating Termination of 1v1 and 1vr Algorithms

In this section, we explain our empirical observation that 1v1 versions of
algorithms terminate before their 1vr counterparts with theoretical arguments.
In Section E.1, we provide a relatively straightforward proof that the 1v1
versions of LUCB and $\mathcal{A}_{1}$ always terminate before their
corresponding 1vr versions. In Section E.2, we work towards proving that
PPR-1v1 always terminates before PPR-1vr, and we reduce this claim to an
inequality on beta functions, which we conjecture to be true, and have
verified empirically for a range of values. In Section E.3, we consider the
multi-dimensional version of the PPR martingale stopping rule (denoted PPR-
MD), which serves as an alternative for designing a stopping rule for mode
estimation. This rule would use a Dirichlet prior (which is the conjugate of
the multinomial distribution), and is analogous to the multi-variate PPR
considered in Appendix C of [1]. We show that PPR-MD always stops after
PPR-1v1 on every run.

###  E.1 LUCB and $\mathcal{A}_{1}$ algorithms

LUCB:  Suppose we run both the variants of LUCB algorithm with
$\delta^{\prime}=\frac{\delta}{K}$, where $\delta$ is the mistake probability
(in reality, we run the 1v1 with $\frac{\delta}{K-1}$; so it is even better).
We will show that LUCB-1vr termination implies LUCB-1v1 termination. The LUCB
algorithm can differentiate some $i,j\in\\{1,2,..,K\\}$ such that $i\neq j$
when

$\displaystyle\hat{p}_{i}-\sqrt{\frac{\ln(\frac{405.5t^{1.1}}{\delta^{\prime}})}{2t}}\geq\hat{p}_{j}+\sqrt{\frac{\ln(\frac{405.5t^{1.1}}{\delta^{\prime}})}{2t}},$

where $\hat{p}_{i}$ denotes the empirical mean corresponds to observation $i$.
For 1v1, the corresponding condition for differentiating $i,j$ will be

$\displaystyle\frac{\hat{p}_{i}}{\hat{p}_{i}+\hat{p}_{j}}-\sqrt{\frac{\ln(\frac{405.5t_{ij}^{1.1}}{\delta^{\prime}})}{2t_{ij}}}\geq\frac{\hat{p}_{j}}{\hat{p}_{i}+\hat{p}_{j}}+\sqrt{\frac{\ln(\frac{405.5Kt_{ij}^{1.1}}{\delta^{\prime}})}{2t_{ij}}},$

where $t_{ij}$ denotes the total number of samples coming from $p_{i}$ and
$p_{j}$. Thus, to prove 1vr termination implies 1v1 termination, It is
sufficient to prove that: If it is true that

$\displaystyle\hat{p}_{i}-\sqrt{\frac{\ln(\frac{405.5t^{1.1}}{\delta^{\prime}})}{2t}}\geq\hat{p}_{j}+\sqrt{\frac{\ln(\frac{405.5t^{1.1}}{\delta^{\prime}})}{2t}}$

then, it is also true that

$\displaystyle\frac{\hat{p}_{i}}{\hat{p}_{i}+\hat{p}_{j}}-\sqrt{\frac{\ln(\frac{405.5t_{ij}^{1.1}}{\delta^{\prime}})}{2t_{ij}}}\geq\frac{\hat{p}_{j}}{\hat{p}_{i}+\hat{p}_{j}}+\sqrt{\frac{\ln(\frac{405.5Kt_{ij}^{1.1}}{\delta^{\prime}})}{2t_{ij}}}.$

We have

$\displaystyle\hat{p}_{i}-\hat{p}_{j}\geq
2\sqrt{\frac{\ln(\frac{405.5t^{1.1}}{\delta^{\prime}})}{2t}},\text{ }$
$\displaystyle\therefore\frac{\hat{p}_{i}-\hat{p}_{j}}{2(\hat{p}_{i}+\hat{p}_{j})\sqrt{\frac{\ln(\frac{405.5t_{ij}^{1.1}}{\delta^{\prime}})}{2t_{ij}}}}\geq\frac{\sqrt{\frac{\ln(\frac{405.5t^{1.1}}{\delta^{\prime}})}{2t}}}{(\hat{p}_{i}+\hat{p}_{j})\sqrt{\frac{\ln(\frac{405.5t_{ij}^{1.1}}{\delta^{\prime}})}{2t_{ij}}}}.$

Using the fact that $\hat{p}_{i}+\hat{p}_{j}=\frac{t_{ij}}{t}$ and the above
inequality, we get

$\displaystyle\frac{\hat{p}_{i}-\hat{p}_{j}}{2(\hat{p}_{i}+\hat{p}_{j})\sqrt{\frac{\ln(\frac{405.5t_{ij}^{1.1}}{\delta^{\prime}})}{2t_{ij}}}}\geq\frac{\sqrt{t\ln(\frac{405.5t^{1.1}}{\delta^{\prime}})}}{\sqrt{t_{ij}\ln(\frac{405.5*t_{ij}^{1.1}}{\delta^{\prime}})}}.$

Since $\sqrt{t\ln(\frac{405.5t^{1.1}}{\delta^{\prime}})}$ is an increasing
function in $t$, and we know that $t_{ij}\leq t$, we have

$\displaystyle\frac{\hat{p}_{i}-\hat{p}_{j}}{2(\hat{p}_{i}+\hat{p}_{j})\sqrt{\frac{\ln(\frac{405.5t_{ij}^{1.1}}{\delta^{\prime}})}{2t_{ij}}}}\geq\frac{\sqrt{t\ln(\frac{405.5t^{1.1}}{\delta^{\prime}})}}{\sqrt{t_{ij}\ln(\frac{405.5*t_{ij}^{1.1}}{\delta^{\prime}})}}\geq
1,$
$\displaystyle\therefore\frac{\hat{p}_{i}}{\hat{p}_{i}+\hat{p}_{j}}-\sqrt{\frac{\ln(\frac{405.5t_{ij}^{1.1}}{\delta^{\prime}})}{2t_{ij}}}\geq\frac{\hat{p}_{j}}{\hat{p}_{i}+\hat{p}_{j}}+\sqrt{\frac{\ln(\frac{405.5Kt_{ij}^{1.1}}{\delta^{\prime}})}{2t_{ij}}}.$

Hence, we showed that the 1v1 variant of LUCB algorithm always terminates
before its 1vr variant.

$\mathcal{A}_{1}$ algorithm: Suppose we run both the variants of
$\mathcal{A}_{1}$ algorithm with $\delta^{\prime}=\frac{\delta}{K}$, where
$\delta$ is the mistake probability (As above, we actually run 1v1 with
$\frac{\delta}{K-1}$, so 1v1 will terminate even faster). The
$\mathcal{A}_{1}$ algorithm differentiates between $i,j\in\\{1,2,..,K\\}$ such
that $i\neq j$ and $i$ is the winner when

$\displaystyle\hat{p}_{i}-\sqrt{\frac{2V_{t}(Z^{i})\ln\left(\frac{4t^{2}}{\delta^{\prime}}\right)}{t}}-\frac{7\ln\left(\frac{4t^{2}}{\delta^{\prime}}\right)}{3(t-1)}\geq\hat{p}_{j}+\sqrt{\frac{2V_{t}(Z^{j})\ln\left(\frac{4t^{2}}{\delta^{\prime}}\right)}{t}}+\frac{7\ln\left(\frac{4t^{2}}{\delta^{\prime}}\right)}{3(t-1)},$

where

$\displaystyle V_{t}(Z^{i})=\frac{x_{i}(t-x_{i})}{t(t-1)},$

in which $x_{i}$ denotes the total number of samples coming from $v_{i}$.
Similarly, the condition for there to be a winner between $i,j$ in
$\mathcal{A}_{1}$ 1v1 will be:

$\displaystyle\frac{\hat{p}_{i}}{\hat{p}_{i}+\hat{p}_{j}}-\sqrt{\frac{2V_{t_{ij}}(Z^{i})\ln\left(\frac{4t_{ij}^{2}}{\delta^{\prime}}\right)}{t_{ij}}}-\frac{7\ln\left(\frac{4t_{ij}^{2}}{\delta^{\prime}}\right)}{3(t_{ij}-1)}\geq\frac{\hat{p}_{j}}{\hat{p}_{i}+\hat{p}_{j}}+\sqrt{\frac{2V_{t_{ij}}(Z^{j})\ln\left(\frac{4t_{ij}^{2}}{\delta^{\prime}}\right)}{t_{ij}}}+\frac{7\ln\left(\frac{4t_{ij}^{2}}{\delta^{\prime}}\right)}{3(t_{ij}-1)},$

where $t_{ij}=t_{i}+t_{j}$ denotes the total number of samples coming from
$v_{i}$ and $v_{j}$, and $t_{i}$ denotes the number of samples coming from
$v_{i}$.
To prove 1vr termination implies 1v1 termination, It is sufficient to prove
that: If it is true that

$\displaystyle\hat{p}_{i}-\sqrt{\frac{2V_{t}(Z^{i})\ln\left(\frac{4t^{2}}{\delta^{\prime}}\right)}{t}}-\frac{7\ln\left(\frac{4t^{2}}{\delta^{\prime}}\right)}{3(t-1)}\geq\hat{p}_{j}+\sqrt{\frac{2V_{t}(Z^{j})\ln\left(\frac{4t^{2}}{\delta^{\prime}}\right)}{t}}+\frac{7\ln\left(\frac{4t^{2}}{\delta^{\prime}}\right)}{3(t-1)}$

then, it is also true that

$\displaystyle\frac{\hat{p}_{i}}{\hat{p}_{i}+\hat{p}_{j}}-\sqrt{\frac{2V_{t_{ij}}(Z^{i})\ln\left(\frac{4t_{ij}^{2}}{\delta^{\prime}}\right)}{t_{ij}}}-\frac{7\ln\left(\frac{4t_{ij}^{2}}{\delta^{\prime}}\right)}{3(t_{ij}-1)}\geq\frac{\hat{p}_{j}}{\hat{p}_{i}+\hat{p}_{j}}+\sqrt{\frac{2V_{t_{ij}}(Z^{j})\ln\left(\frac{4t_{ij}^{2}}{\delta^{\prime}}\right)}{t_{ij}}}+\frac{7\ln\left(\frac{4t_{ij}^{2}}{\delta^{\prime}}\right)}{3(t_{ij}-1)}$

Using the same steps as in LUCB, we get

$\displaystyle\frac{\hat{p}_{i}-\hat{p}_{j}}{2(\hat{p}_{i}+\hat{p}_{j})\left(\sqrt{\frac{2V_{t_{ij}}(Z^{i})\ln\left(\frac{4t_{ij}^{2}}{\delta^{\prime}}\right)}{t_{ij}}}+\sqrt{\frac{2V_{t_{ij}}(Z^{j})\ln\left(\frac{4t_{ij}^{2}}{\delta^{\prime}}\right)}{t_{ij}}}+\frac{2*7\ln\left(\frac{4t_{ij}^{2}}{\delta^{\prime}}\right)}{3(t_{ij}-1)}\right)}$
$\displaystyle\geq\frac{\left(\sqrt{2tV_{t}(Z^{i})\ln\left(\frac{4t^{2}}{\delta^{\prime}}\right)}+\sqrt{2tV_{t}(Z^{j})\ln\left(\frac{4t^{2}}{\delta^{\prime}}\right)}+\frac{2*7t\ln\left(\frac{4t^{2}}{\delta^{\prime}}\right)}{3(t-1)}\right)}{\left(\sqrt{2t_{ij}V_{t_{ij}}(Z^{i})\ln\left(\frac{4t_{ij}^{2}}{\delta^{\prime}}\right)}+\sqrt{2t_{ij}V_{t_{ij}}(Z^{j})\ln\left(\frac{4t_{ij}^{2}}{\delta^{\prime}}\right)}+\frac{2*7t_{ij}\ln\left(\frac{4t_{ij}^{2}}{\delta^{\prime}}\right)}{3(t_{ij}-1)}\right)}.$

We need to prove that the above expression is $\geq 1$. We note that
$\sqrt{2tV_{t}(Z^{j})\ln\left(\frac{4t^{2}}{\delta^{\prime}}\right)}$,
$\sqrt{2tV_{t}(Z^{j})\ln\left(\frac{4t^{2}}{\delta^{\prime}}\right)}$ are
increasing functions in $t$. Let
$f(t)=\frac{2*7t\ln\left(\frac{4t^{2}}{\delta^{\prime}}\right)}{3(t-1)}$. We
write down the differential:

$\displaystyle f^{\prime}(t)\propto
2(t-1)-\ln\left(\frac{4t^{2}}{\delta}\right).$

Thus, for $t$ such that $2(t-1)\geq\ln\left(\frac{4t^{2}}{\delta}\right)$,
$f(t)$ is an increasing function. We now look at the minimum value of $t_{i}$
possible, and we show that $t_{i}$ is always such that $f(t)$ is an increasing
function for $t\geq t_{i}$. We proceed to look at a scenario in which lowest
possible value for $t_{i}$ is observed. Consider the case in which we observe
$t\hat{p_{i}}$ samples with value $v_{i}$ (thus, the empirical mode is
$\hat{p_{i}}$ for $v_{i}$). Let’s assume that $\mathcal{A}_{1}$ 1vr algorithm
declares $i$ as the mode after observing $t\hat{p_{i}}$ samples of $v_{i}$. We
assume that $j$ has $0$ samples, and then find the value of $t$ that arises.
Termination of $\mathcal{A}_{1}$ algorithm after $t$ observations suggests (we
ignore the empirical mean term, as it makes our lower bound on $t$ only
bigger):

$\displaystyle\hat{p_{i}}-\frac{7\ln\left(\frac{4t^{2}}{\delta^{\prime}}\right)}{3(t-1)}\geq
0+\frac{7\ln\left(\frac{4t^{2}}{\delta^{\prime}}\right)}{3(t-1)}$
$\displaystyle\implies\hat{p_{i}}\geq\frac{14\ln\left(\frac{4t^{2}}{\delta^{\prime}}\right)}{3(t-1)}.$

Using the fact that $t\hat{p_{i}}=t_{i}$, we arrive at:

$\displaystyle\frac{3\hat{p_{i}}(t-1)}{14}\geq\ln\left(\frac{4t^{2}}{\delta^{\prime}}\right)$
$\displaystyle\implies\frac{3(t_{i}-\hat{p_{i}})}{14}\geq\ln\left(\frac{4t^{2}}{\delta^{\prime}}\right)\geq\ln\left(\frac{4t_{i}^{2}}{\delta^{\prime}}\right).$

To show $2(t_{i}-1)\geq\ln\left(\frac{4t_{i}^{2}}{\delta}\right)$, it is
sufficient to show that $2(t_{i}-1)\geq\frac{3}{14}(t_{i}-\hat{p_{i}})$. For
proving this, we make a mild assumption that $t_{i}\geq 2$ as _practically_
$\mathcal{A}_{1}$ algorithm would need more than 2 samples from $v_{i}$ to
declare $v_{i}$ as the mode. Under this assumption, we get:

$\displaystyle
2(t_{i}-1)-\frac{3}{14}(t_{i}-\hat{p_{i}})=\frac{25}{14}\hat{t_{i}}-2+\frac{3}{14}\hat{p_{i}}\geq\frac{11}{7}+\frac{3}{14}\hat{p_{i}}>0.$

Hence, we note that

$\displaystyle\frac{\left(\sqrt{2tV_{t}(Z^{i})\ln\left(\frac{4t^{2}}{\delta^{\prime}}\right)}+\sqrt{2tV_{t}(Z^{j})\ln\left(\frac{4t^{2}}{\delta^{\prime}}\right)}+\frac{2*7t\ln\left(\frac{4t^{2}}{\delta^{\prime}}\right)}{3(t-1)}\right)}{\left(\sqrt{2t_{ij}V_{t_{ij}}(Z^{i})\ln\left(\frac{4t_{ij}^{2}}{\delta^{\prime}}\right)}+\sqrt{2t_{ij}V_{t_{ij}}(Z^{j})\ln\left(\frac{4t_{ij}^{2}}{\delta^{\prime}}\right)}+\frac{2*7t_{ij}\ln\left(\frac{4t_{ij}^{2}}{\delta^{\prime}}\right)}{3(t_{ij}-1)}\right)}\geq
1$

since all the $3$ terms are increasing, and thus $\mathcal{A}_{1}$ 1vr always
stops after $\mathcal{A}_{1}$ 1v1.

###  E.2 PPR

Suppose party $i,j$ have confidence sequences which do not intersect at some
time $t$. Let the number of samples from party $i$ be $x$, and the number of
samples from party $j$ be $y$, and without loss of generality assume $x>y$.
Let $f$ be the number of samples from parties which are not $i$ or $j$. Then,
the condition for party $i,j$ having confidence sequences which do not
intersect can be written as

$\displaystyle\exists\>\theta\in\left[\frac{y}{x+y+f},\frac{x}{x+y+f}\right]\text{
such that }$
$\displaystyle\frac{1}{\beta_{x+1,y+f+1}(\theta)}\geq\frac{K}{\delta},$
$\displaystyle\frac{1}{\beta_{y+1,x+f+1}(\theta)}\geq\frac{K}{\delta}.$

Parties $i,j$ have a winner between them in PPR-1v1 when

$\displaystyle\frac{1}{\beta_{x+1,y+1}\left(\frac{1}{2}\right)}\geq\frac{K-1}{\delta}.$

We will attempt to show that party $i,j$ having disjoint confidence sequences
in PPR-1vr implies party $i,j$ having a winner between them in PPR-1v1. This
will imply that PPR-1v1 always terminates before PPR-1vr. Noting that

$\displaystyle\beta_{x,y}(\theta)=\frac{\theta^{x-1}(1-\theta)^{y-1}}{B(x,y)}$
$\displaystyle\text{where }B(x,y)=\frac{\Gamma(x)\Gamma(y)}{\Gamma(x+y)},$

we are given that

$\displaystyle\frac{\delta}{K}\geq\frac{\theta^{x}(1-\theta)^{y+f}}{B(x+1,y+f+1)},$
$\displaystyle\frac{\delta}{K}\geq\frac{\theta^{y}(1-\theta)^{x+f}}{B(y+1,x+f+1)}.$

And we wish to show that

$\displaystyle\frac{\delta}{K-1}\geq\frac{1}{2^{x+y}B(x+1,y+1)}.$

We denote

$\displaystyle\frac{\theta^{x}(1-\theta)^{y+f}}{B(x+1,y+f+1)}=L_{1}(\theta),$
$\displaystyle\frac{\theta^{y}(1-\theta)^{x+f}}{B(y+1,x+f+1)}=L_{2}(\theta).$

Thus, it is sufficient to show that,
$\forall\>\theta\in\left[\frac{y}{x+y+f},\frac{x}{x+y+f}\right]$,

$\displaystyle\max\left(L_{1}(\theta),L_{2}(\theta)\right)\geq\frac{K-1}{K2^{x+y}B(x+1,y+1)}.$

Consider

$\displaystyle L_{1}^{\prime}(\theta)\propto x(1-\theta)-(y+f)\theta,$
$\displaystyle L_{1}^{\prime}(\theta)\propto x-(x+y+f)\theta$
$\displaystyle\implies L_{1}^{\prime}(\theta)\geq
0\>\forall\>\theta\leq\frac{x}{x+y+f}.$

Similarly, consider

$\displaystyle L_{2}^{\prime}(\theta)\propto y(1-\theta)-(x+f)\theta$
$\displaystyle L_{2}^{\prime}(\theta)\propto y-(x+y+f)\theta,$
$\displaystyle\implies L_{2}^{\prime}(\theta)\leq
0\>\forall\>\theta\geq\frac{y}{x+y+f}.$

Thus, we note that in our range of $\theta,L_{1}(\theta)$ is increasing and
$L_{2}(\theta)$ is decreasing. Consider $\theta^{*}$ such that
$L_{1}(\theta^{*})=L_{2}(\theta^{*})$. We will prove that considering only the
value $\theta=\theta^{*}$ is sufficient to prove that

$\displaystyle\max\left(L_{1}(\theta),L_{2}(\theta)\right)\geq\frac{K-1}{K2^{x+y}B(x+1,y+1)}$

for the entire range of
$\theta\in\left[\frac{y}{x+y+f},\frac{x}{x+y+f}\right]$. First, we prove that
$\theta^{*}$ lies in this range itself. The equation
$L_{1}(\theta^{*})=L_{2}(\theta^{*})$ gives us the implicit equation

$\displaystyle\left(\frac{\theta^{*}}{1-\theta^{*}}\right)=\left[\frac{x!(y+f)!}{y!(x+f)!}\right]^{\frac{1}{x-y}}.$

We first prove $\theta^{*}\geq\frac{y}{x+y+f}$. This is the same as showing
that $\frac{\theta^{*}}{1-\theta^{*}}\geq\frac{y}{x+f}$. We show that

$\displaystyle\frac{y}{x+f}\leq\left[\frac{x!(y+f)!}{y!(x+f)!}\right]^{\frac{1}{x-y}}$
$\displaystyle\Leftrightarrow\left(\frac{y}{x+f}\right)^{x-y}\leq\left[\frac{(y+1)(y+2)...(y+f)}{(x+1)(x+2)...(x+f)}\right].$

To prove the above inequality, first note that

$\displaystyle\frac{y}{x+f}\leq\frac{y+1}{x+f}.$

Hence, it is sufficient now to show

$\displaystyle\left(\frac{y}{x+f}\right)^{x-y-1}\leq\left[\frac{(y+2)...(y+f)}{(x+1)(x+2)...(x+f-1)}\right].$

We know that $y<x$. Suppose that $y=x-1$; then the above equation has both LHS
= 1 and RHS = 1, hence it is true. Otherwise, if $y<x-1$, we have

$\displaystyle\frac{y}{x+f}\leq\frac{y+2}{x+f-1}.$

And proceeding in a similar fashion, we can show inductively that

$\displaystyle\frac{y}{x+f}\leq\left[\frac{x!(y+f)!}{y!(x+f)!}\right]^{\frac{1}{x-y}}.$

In the same way, we can also show that

$\displaystyle\frac{x}{y+f}\geq\left[\frac{x!(y+f)!}{y!(x+f)!}\right]^{\frac{1}{x-y}}.$

This proves that $\theta^{*}\in\left[\frac{y}{x+y+f},\frac{x}{x+y+f}\right]$.
Moreover, since $L_{1}(\theta)$ is increasing and $L_{2}(\theta)$ is
decreasing, we have that

$\displaystyle L_{1}(\theta^{*})\leq L_{1}(\theta),\theta\geq\theta^{*},$
$\displaystyle L_{2}(\theta^{*})\geq L_{2}(\theta),\theta\leq\theta^{*}.$

Combining the above two equations and noting that
$L_{1}(\theta^{*})=L_{2}(\theta^{*})$, we get that

$\displaystyle\max\left(L_{1}(\theta^{*}),L_{2}(\theta^{*})\right)\leq\max\left(L_{1}(\theta),L_{2}(\theta)\right),\theta\in\left[\frac{y}{x+y+f},\frac{x}{x+y+f}\right].$

Thus, if we show that

$\displaystyle\max\left(L_{1}(\theta^{*}),L_{2}(\theta^{*})\right)\geq\frac{K-1}{K2^{x+y}B(x+1,y+1)}$

we are done. We need to show that

$\displaystyle\frac{\left(\theta^{*}\right)^{x}(1-\theta^{*})^{y+f}}{B(x+1,y+f+1)}\geq\frac{K-1}{K2^{x+y}B(x+1,y+1)},$
$\displaystyle\text{where
}\left(\frac{\theta^{*}}{1-\theta^{*}}\right)=\left[\frac{x!(y+f)!}{y!(x+f)!}\right]^{\frac{1}{x-y}}.$

We ran computer simulations to verify the correctness of the above equation
exhaustively for all values of $x,y,f$ in $[1,100]$. Thus, we conjecture that
the above equation is true for all $x,y,f>0$ such that $x>y$.

###  E.3 Comparison with Multidimensional PPR (PPR-MD)

The Dirichlet distribution is the conjugate prior of the Multinomial
distribution, and hence can be used to implement a PPR-based stopping rule,
which is similar in principle to the multi-variate PPR given in Appendix C in
[1]. In specific, the PDF of the Dirichlet distribution is given as

$\displaystyle pdf(x)=\frac{\prod_{i=1}^{K}x_{i}^{\alpha_{i}-1}}{B(\alpha)},$
$\displaystyle
B(\alpha)=\frac{\prod_{i}\Gamma(\alpha_{i})}{\Gamma(\sum_{i}\alpha_{i})}.$

At each time-step $t$, we maintain a confidence set ${C}^{t}$ with
$x\in[0,1]^{k}$, such that
$C^{t}\operatorname*{\stackrel{{\scriptstyle\text{\tiny
def}}}{{=}}}\\{x:R^{t}(x)<\frac{1}{\delta}\\}$. We stop at time $t$ when all
the $x\in C^{t}$ have the same unique mode. We call this stopping rule PPR-MD
(Multi-dimensional). We note that, with prior $\alpha=[1,...,1]$,

$\displaystyle
R_{t}(x)=\frac{1}{(K-1)!}\times\frac{B(\alpha)}{\prod_{i=1}^{K}x_{i}^{\alpha_{i}-1}}$

We will show that if the PPR-MD stopping rule stops at a point, then PPR-1v1
would also have stopped. In other words, PPR-MD stopping implies PPR-1v1
stopping on every run.

Let the number of observations from $v_{1},v_{2},...,v_{K}$ until timestep $t$
be $s_{1},s_{2},...,s_{K}$. Without loss of generality, order them such that
$s_{1}\geq s_{2}\geq...\geq s_{K}$. We denote the empirical means as
$\mu_{i}=\frac{s_{i}}{\sum_{i}s_{i}}$. We note that, when PPR-MD stops,
$x_{1}=(\frac{\mu_{1}+\mu_{2}}{2},\frac{\mu_{1}+\mu_{2}}{2},\mu_{3},...,\mu_{K})$
must not lie in the confidence set. Explicitly,

$\displaystyle\frac{\left(\frac{\mu_{1}+\mu_{2}}{2}\right)^{s_{1}+s_{2}}\mu_{3}^{s_{3}}...\mu_{K}^{s_{K}}}{s_{1}!s_{2}!...s_{K}!}\leq\frac{\delta}{(K-1)!}.$

We divide our proof into two parts. First, we show the implication for $K=3$,
and then we extend our proof to general $K\geq 3$.

####  E.3.1 Proof for $K=3$

When $K=3$, PPR-1v1 stops when

$\displaystyle\frac{\left(\frac{1}{2}\right)^{s_{1}+s_{2}}(s_{1}+s_{2}+1)!}{s_{1}!s_{2}!}\leq\frac{\delta}{2}$

and PPR-MD stopping implies that (using that $K=3$)

$\displaystyle\frac{\left(\frac{\mu_{1}+\mu_{2}}{2}\right)^{s_{1}+s_{2}}\mu_{3}^{s_{3}}(s_{1}+s_{2}+s_{3}+2)!}{s_{1}!s_{2}!s_{3}!}\leq\frac{\delta}{2}.$

If we can show that

$\displaystyle\frac{\left(\frac{\mu_{1}+\mu_{2}}{2}\right)^{s_{1}+s_{2}}\mu_{3}^{s_{3}}(s_{1}+s_{2}+s_{3}+2)!}{s_{1}!s_{2}!s_{3}!}\geq\frac{\left(\frac{1}{2}\right)^{s_{1}+s_{2}}(s_{1}+s_{2}+1)!}{s_{1}!s_{2}!},$

for all $s_{1},s_{2},s_{3}$ such that $s_{1}\geq s_{2}\geq s_{3}$, then PPR-MD
stopping will imply PPR-1v1 stopping for $K=3$.

We note that this is equivalent to showing

$\displaystyle(\mu_{1}+\mu_{2})^{s_{1}+s_{2}}\mu_{3}^{s_{3}}\geq\frac{s_{3}!(s_{1}+s_{2}+1)!}{(s_{1}+s_{2}+s_{3}+2)!}$
$\displaystyle\Leftrightarrow\frac{(s_{1}+s_{2})^{s_{1}+s_{2}}s_{3}^{s_{3}}}{(s_{1}+s_{2}+s_{3})^{s_{1}+s_{2}+s_{3}}}\geq\frac{s_{3}!(s_{1}+s_{2}+1)!}{(s_{1}+s_{2}+s_{3}+2)!}$
$\displaystyle\Leftrightarrow\frac{x^{x}y^{y}}{(x+y)^{x+y}}\geq\frac{(x+1)!y!}{(x+y+2)!},\text{
where }x=s_{1}+s_{2},y=s_{3}$

for all $x,y,$ such that $y\geq 0,x\geq 2y$. Note that, when $y=0$, the
$y^{y}$ term tends to $1$; hence, the above statement is true. Subsequently,
we will consider $y>0$. Let

$\displaystyle f(x,y)=\frac{x^{x}y^{y}(x+2)....(x+y+2)}{y!(x+y)^{x+y}}$

We want to show that

$\displaystyle f(x,y)\geq 1\text{ when }y>0,x\geq 2y.$

We show this in two steps. First, we show that $f(x,y)$ is an increasing
function of $x$ when $y$ is fixed. Since $f(x,y)$ is increasing in $x$, we
then choose the minimum value of $x$ with fixed $y$ (i.e, $x=2y$) and prove
that $f(2y,y)\geq 1$ for all $y>0$, which implies that $f(x,y)\geq 1$ for all
$y>0,x\geq 2y$.

#####  E.3.1.1 Showing that $f(x,y)$ is increasing in $x$

Recapping, we need to show that

$\displaystyle
f(x,y)=\frac{y^{y}(x+2)...(x+y+2)}{y!(x+y)^{y}\left(1+\frac{y}{x}\right)^{x}}$

is increasing with respect to $x$ while keeping $y$ fixed. We write down the
partial derivative of $\ln(f(x,y))$ with respect to $x$ as follows:

$\displaystyle\frac{\partial\ln(f(x,y))}{\partial
x}=\sum_{j=2}^{y}\frac{1}{x+j}-\frac{y}{x+y}+\frac{1}{x+y+2}+\frac{1}{x+y+1}+1-\frac{x}{x+y}-\ln\left(\frac{x+y}{x}\right)$
$\displaystyle\implies\frac{\partial\ln(f(x,y))}{\partial
x}=\sum_{j=2}^{y}\frac{1}{x+j}+\frac{1}{x+y+2}+\frac{1}{x+y+1}-\ln\left(\frac{x+y}{x}\right).$

We note that

$\displaystyle\frac{1}{x+j}\geq\int_{w=j}^{w=j+1}\frac{1}{x+w}dw=\ln\left(\frac{x+j+1}{x+j}\right)$
$\displaystyle\implies\sum_{j=2}^{y}\frac{1}{x+j}\geq\ln\left(\frac{x+y+1}{x+2}\right).$

Thus, if we show that

$\displaystyle
g(x,y)=\ln\left(\frac{x+y+1}{x+2}\right)+\frac{1}{x+y+2}+\frac{1}{x+y+1}-\ln\left(\frac{x+y}{x}\right)\geq
0\text{ when }y>0,x\geq 2y$

this is sufficient to show that $\frac{\partial\ln(f(x,y))}{\partial x}\geq
0\text{ when }y\geq 0,x\geq 2y$. We combine terms to get

$\displaystyle
g(x,y)=\frac{1}{x+y+2}+\frac{1}{x+y+1}-\ln\left(\frac{(x+y)(x+2)}{(x+y+1)x}\right)$

We will now show that keeping $x$ fixed, $g(x,y)$ is a decreasing function of
$y$. Hence, it will be sufficient to consider the maximum possible value of
$y$ to show that $g(x,y)\geq 0$. We see that

$\displaystyle\frac{\partial g(x,y)}{\partial
y}=-\left(\frac{3x^{3}+x^{2}(9y+11)+x(9y^{2}+22y+13)+3y^{3}+11y^{2}+13y+4}{(x+y)(x+y+1)^{2}(x+y+2)^{2}}\right)$
$\displaystyle\implies\frac{\partial g(x,y)}{\partial y}\leq 0,y>0,x\geq 2y.$

Hence, $g(x,y)$ is decreasing in $y$. Thus, it is enough to consider the
maximal possible value of $y$ for a fixed $x$ to show that $g(x,y)\geq 0$. For
a fixed $x$, the maximum possible $y$ is $\frac{x}{2}$. Hence, we have that

$\displaystyle
h(x)=g(x,x/2)=\frac{2}{3x+4}+\frac{2}{3x+2}-\ln\left(\frac{3(x+2)}{(3x+2)}\right),$

and we need to show that $h(x)\geq 0\text{ when }x>0$. We have

$\displaystyle
h^{\prime}(x)=-\left(\frac{8(9x^{2}+21x+14)}{(x+2)(3x+2)^{2}(3x+4)^{2}}\right)$
$\displaystyle\implies h^{\prime}(x)\leq 0\text{ when }x>0.$

Thus, $h(x)$ is a decreasing function of $x$. We see that, as
$x\rightarrow\infty,h(x)\rightarrow 0$. Thus, $h(x)\geq 0\text{ when }x>0$.
This means that $g(x,x/2)\geq 0\implies g(x,y)\geq 0\implies\frac{\partial
f(x,y)}{\partial x}\geq 0$ which implies that $f(x,y)$ is an increasing
function of $x$.

#####  E.3.1.2 Showing that $f(x,y)\geq 1$

Since $f(x,y)$ is an increasing function of $x$ when $y$ is fixed, it is
sufficient to show that $f(x,y)\geq 1$ for the minimum possible value of $x$.
We note that the minimum possible value of $x$ is $x=2y$. We have

$\displaystyle
f(2y,y)-1=\frac{y^{y}(2y+2)...(3y+2)-y!(3y)^{y}\left(\frac{3}{2}\right)^{2y}}{y!(3y)^{y}\left(\frac{3}{2}\right)^{2y}}.$

The denominator is positive. We show that the numerator is positive for all
$y>0$.

$\displaystyle
h(2y,y)=y^{y}(2y+2)...(3y+2)-y!(3y)^{y}\left(\frac{3}{2}\right)^{2y}$
$\displaystyle\implies
h(2y,y)=y^{y}\left((2y+2)...(3y+2)-y!\left(\frac{27}{4}\right)^{y}\right).$

Let

$\displaystyle c(y)=(2y+2)...(3y+2)-y!\left(\frac{27}{4}\right)^{y}.$

We will show that $c(y)>0\text{ when }y>0$. First, We note that $c(1)>0$. We
now use induction; assume that $c(y)>0$ for some $y$. We will show that
$c(y+1)>0$. We have that

$\displaystyle c(y)=(2y+2)...(3y+2)-y!\left(\frac{27}{4}\right)^{y}>0$
$\displaystyle\implies
d(y)=\frac{(2y+2)...(3y+2)}{y!\left(\frac{27}{4}\right)^{y}}>1.$

We want to show that

$\displaystyle c(y+1)=(2y+4)...(3y+5)-(y+1)!\left(\frac{27}{4}\right)^{y+1}>0$
$\displaystyle\Leftrightarrow
d(y+1)=\frac{(2y+4)...(3y+5)}{(y+1)!\left(\frac{27}{4}\right)^{y+1}}>1.$

We will show that

$\displaystyle\frac{d(y+1)}{d(y)}=\frac{(3y+3)(3y+4)(3y+5)}{(2y+2)(2y+3)(y+1)\frac{27}{4}}>1$
$\displaystyle\Leftrightarrow(3y+3)(3y+4)(3y+5)-(2y+2)(2y+3)(y+1)\frac{27}{4}>0.$

We note that the last expression turns out to be a quadratic in $y$ which is
always positive when $y>0$. Hence, $\frac{d(y+1)}{d(y)}>1$ when $y>0$. Thus,
since by our induction hypothesis we have that $d(y)>1,y>0$ and by our proof
above we have that $\frac{d(y+1)}{d(y)}>1,y>0$, we note that this implies
$d(y+1)=d(y)\frac{d(y+1)}{d(y)}>1$, which is what we wanted to show in our
induction step. Hence, proved.

####  E.3.2 Extending to general $K$

For a general $K$, PPR-1v1 stops when

$\displaystyle\frac{\left(\frac{1}{2}\right)^{s_{1}+s_{2}}(s_{1}+s_{2}+1)!}{s_{1}!s_{2}!}\leq\frac{\delta}{K-1}$

and when PPR-MD stops, it is true that (by choosing
$x=\left(\frac{\mu_{1}+\mu_{2}}{2},\frac{\mu_{1}+\mu_{2}}{2},\mu_{3},...\mu_{K}\right)$

$\displaystyle\frac{\left(\frac{\mu_{1}+\mu_{2}}{2}\right)^{s_{1}+s_{2}}\mu_{3}^{s_{3}}\mu_{4}^{s_{4}}...\mu_{K}^{s_{K}}(s_{1}+s_{2}+s_{3}+s_{4}+...+s_{K}+K-1)!}{s_{1}!s_{2}!s_{3}!s_{4}!...s_{K}!}\leq\frac{\delta}{(K-1)!}.$

If we show that

$\displaystyle\frac{(K-2)!\left(\frac{\mu_{1}+\mu_{2}}{2}\right)^{s_{1}+s_{2}}\mu_{3}^{s_{3}}\mu_{4}^{s_{4}}..\mu_{K}^{s_{K}}(s_{1}+s_{2}+s_{3}+s_{4}+...+s_{K}+K-1)!}{s_{1}!s_{2}!s_{3}!s_{4}!...s_{K}!}\geq$
$\displaystyle\frac{\left(\frac{1}{2}\right)^{s_{1}+s_{2}}(s_{1}+s_{2}+1)!}{s_{1}!s_{2}!},$

then PPR-MD stopping will imply PPR-1v1 stopping. We will show this by using a
sequence of inequalities as follows;

$\displaystyle\frac{(K-2)!\left(\frac{\mu_{1}+\mu_{2}}{2}\right)^{s_{1}+s_{2}}\mu_{3}^{s_{3}}\mu_{4}^{s_{4}}..\mu_{K}^{s_{K}}(s_{1}+s_{2}+s_{3}+s_{4}+...+s_{K}+K-1)!}{s_{1}!s_{2}!s_{3}!s_{4}!...s_{K}!}\geq$
$\displaystyle\frac{(K-3)!\left(\frac{\mu_{1}+\mu_{2}}{2}\right)^{s_{1}+s_{2}}\mu_{3}^{s_{3}}...\mu_{K-1}^{s_{K-1}}(s_{1}+s_{2}+s_{3}+...+s_{K-1}+K-2)!}{s_{1}!s_{2}!s_{3}!...s_{K-1}!}\geq...\geq$
$\displaystyle\frac{\left(\frac{1}{2}\right)^{s_{1}+s_{2}}(s_{1}+s_{2}+1)!}{s_{1}!s_{2}!}.$

We will show the first inequality, and the rest follow the same structure
except the last (for $K=3$), which was already shown in the subsection above.
Note that the last inequality does not follow the same structure due to the
lack of $\frac{\mu_{1}+\mu_{2}}{2}$ term in the RHS, since this does not show
up in the PPR-1v1 expression. Showing the first inequality is equivalent to
showing

$\displaystyle(K-2)\mu_{K}^{s_{K}}\geq\frac{(s_{1}+s_{2}+...+s_{K-1}+K-2)!s_{K}!}{(s_{1}+s_{2}+...+s_{K}+K-1)!}$
$\displaystyle\Leftrightarrow(K-2)\frac{s_{K}^{s_{K}}}{(s_{1}+s_{2}+...+s_{K})^{s_{K}}}\geq\frac{(s_{1}+s_{2}+...+s_{K-1}+K-2)!s_{K}!}{(s_{1}+s_{2}+...+s_{K}+K-1)!}$
$\displaystyle\Leftrightarrow(K-2)\frac{y^{y}}{(x+y)^{y}}\geq\frac{(x+K-2)!y!}{(x+y+K-1)!},x\geq(K-1)y,\text{
where }x=s_{1}+s_{2}+..+s_{K-1},y=s_{K}.$

We already know that

$\displaystyle\frac{x^{x}y^{y}}{(x+y)^{x+y}}\geq\frac{(x+1)!y!}{(x+y+2)!},\text{
where }x\geq 2y,y>0$

from our proof for $K=3$. In this equation, multiplying the LHS by
$\frac{(K-2)(x+y)^{x}}{x^{x}}$ which is a factor greater than $1$, and
multiplying the RHS by $\frac{(x+2)...(x+K-2)}{(x+y+3)...(x+y+K-1)}$, which is
a factor lesser than $1$, we have the inequality that

$\displaystyle\frac{x^{x}}{(x+y)^{y}}\geq\frac{(x+K-2)!y!}{(x+y+K-1)!},x\geq
2y$

which directly implies what we wanted to show. Hence, even in the case of $K$
parties, PPR-MD stopping implies PPR-1v1 stopping.

##  Appendix F DCB Algorithm

We describe the DCB (“Difference in Confidence Bounds”) algorithm for sampling
constituencies in the indirect election winner-forecasting problem from
Section 4.

Suppose we have $C$ constituencies. For ease of explanation, we assume that
all the constituencies have the same set of $K\geq 2$ parties (in reality we
maintain a separate list for each constituency). Although constituencies have
finite populations, these are usually large enough to ignore the benefit of
without-replacement samples; we simply view each response as a sample from a
discrete distribution.

After $t\geq 1$ samples have been obtained from the population, let
$\text{LCB}^{t}(c,i)$ and $\text{UCB}^{t}(c,i)$ denote (1vr) lower and upper
confidence bounds, respectively, on the the (true) fraction of votes to be
cast for party $i\in\\{1,2,\dots,K\\}$ in constituency
$c\in\\{1,2,\dots,C\\}$. If applying a 1v1 procedure for mode estimation, we
have separate confidence bounds $\text{LCB}^{t}(c,i,j)$ and
$\text{UCB}^{t}(c,i,j)$ for each pair of parties $i,j\in\\{1,2,\dots,K\\}$,
$i\neq j$. The permitted mistake probability $\delta$ is divided equally among
the constituencies.

The key idea in the DCB algorithm is to keep lower and upper confidence bounds
on the wins of each party (across constituencies), and to use this information
to guide sampling. For party $i\in\\{1,2,\dots,K\\}$, the current number of
wins ($\text{wins}^{t}_{i}$) and losses ($\text{losses}^{t}_{i}$) can be
obtained by verifying whether its confidence bounds within each constituency
have separated accordingly from other parties. We also use
$\text{leads}^{t}_{i}$ to denote the number of constituencies in which $i$ has
polled the most votes yet, but has not yet won. Thus, we have
$\text{LCB}^{t}_{i}=\text{wins}^{t}_{i}\text{, and
}\text{UCB}^{t}_{i}=C-\text{losses}^{t}_{i}.$

Observe that the overall winner can be declared as soon as one party’s LCB
exceeds the UCB of all the other parties. On the other hand, when the winner
is yet to be identified, one would ideally like to focus on “potential”
winners, rather than query a constituency whose result does not seem relevant
to the big picture. Taking cue from the LUCB algorithm for bandits [10], the
first step under DCB is to identify two contenders for the top position: party
$a^{t}=\operatorname*{argmax}_{i\in\\{1,2,\dots,K\\}}(\text{wins}^{t}_{i}+\text{leads}^{t}_{i})$,
and party
$b^{t}=\operatorname*{argmax}_{i\in\\{1,2,\dots,K\\}\setminus\\{a^{t}\\}}\text{UCB}^{t}_{i}$.
Optimistic that sampling can reveal a win for $a^{t}$ and a loss for
$b^{t}$—which would take us closer to termination—DCB picks one “promising”
constituency each for $a^{t}$ and $b^{t}$. These constituencies, denoted
$c^{t}_{1}$ and $c^{t}_{2}$, are defined below for use with both 1v1 and 1vr
confidence bounds. The idea is the same: $c^{t}_{1}$ is the constituency in
which $a^{t}$ appears poised to win by a large margin, and $c^{t}_{2}$ is the
constituency in which $b^{t}$ appears poised to lose by a large margin.

$\displaystyle c^{t}_{1}$
$\displaystyle=\begin{cases}\operatorname*{argmax}_{c}\min_{j\in\\{1,2,\dots,K\\}}(\text{UCB}(c,a^{t},j)-\text{LCB}(c,a^{t},j))&\text{(1v1),}\\\
\operatorname*{argmax}_{c}\min_{j\in\\{1,2,\dots,K\\}}(\text{UCB}(c,a^{t})-\text{LCB}(c,j))&\text{(1vr),}\end{cases}$
$\displaystyle c^{t}_{2}$
$\displaystyle=\begin{cases}\operatorname*{argmax}_{c}\max_{j\in\\{1,2,\dots,K\\}}(\text{UCB}(c,j,b^{t})-\text{LCB}(c,j,b^{t}))&\text{(1v1),}\\\
\operatorname*{argmax}_{c}\max_{j\in\\{1,2,\dots,K\\}}(\text{UCB}(c,j)-\text{LCB}(c,b^{t}))&\text{(1vr).}\end{cases}$

The outer “$\operatorname*{argmax}$” in all the definitions above is over all
constituencies where the concerned party ($a^{t}$ or $b^{t}$) is still in
contention: that is, it has not yet won or lost the constituency. The DCB
algorithm queries $c^{t}_{1}$ and $c^{t}_{2}$ at each time step $t$, and
terminates once an overall winner has been identified.