Tomer Berg<EMAIL_ADDRESS>
School of Electrical Engineering, Tel Aviv University and Or Ordentlich
<EMAIL_ADDRESS>
School of Computer Science and Engineering, Hebrew University of Jerusalem and
Ofer Shayevitz<EMAIL_ADDRESS>
School of Electrical Engineering, Tel Aviv University

# Deterministic Finite-Memory Bias Estimation

###### Abstract

In this paper we consider the problem of estimating a Bernoulli parameter
using finite memory. Let $X_{1},X_{2},\ldots$ be a sequence of independent
identically distributed Bernoulli random variables with expectation $\theta$,
where $\theta\in[0,1]$. Consider a finite-memory deterministic machine with
$S$ states, that updates its state $M_{n}\in\\{1,2,\ldots,S\\}$ at each time
according to the rule $M_{n}=f(M_{n-1},X_{n})$, where $f$ is a deterministic
time-invariant function. Assume that the machine outputs an estimate at each
time point according to some fixed mapping from the state space to the unit
interval. The quality of the estimation procedure is measured by the
asymptotic risk, which is the long-term average of the instantaneous quadratic
risk. The main contribution of this paper is an upper bound on the smallest
worst-case asymptotic risk any such machine can attain. This bound coincides
with a lower bound derived by Leighton and Rivest, to imply that $\Theta(1/S)$
is the minimax asymptotic risk for deterministic $S$-state machines. In
particular, our result disproves a longstanding $\Theta(\log S/S)$ conjecture
for this quantity, also posed by Leighton and Rivest.

###### keywords:

Learning with Memory Constraints, Parametric Estimation, Minimax Estimation.

##  1 Introduction

The statistical hardness of a parametric estimation problem has been
traditionally characterized by the number of independent samples from the
distribution $P_{\theta}$ one needs to see in order to accurately estimate
$\theta$. However, as the amount of available data is constantly increasing,
collecting enough samples for accurate estimation is becoming less of a
problem, provided that the parameter $\theta$ is of a relatively low
dimension. In this regime, it is the computational resources dedicated to the
estimation task, rather than the number of samples, that constitute the main
bottleneck determining the quality of estimation one can attain.

As a result, the topic of estimation / learning under computational
constraints is currently drawing considerable attention; in particular, the
problem of estimation / learning under memory constraints has been recently
studied in various different setups, as we further elaborate in Subsection
1.1. Despite this ongoing effort, there are still substantial gaps in the
understanding of the effects memory limitations can have on the minimal
possible estimation error. This work addresses such a gap in arguably the
simplest setup possible: estimation of a single parameter $\theta\in[0,1]$
from an infinite number of independent samples from $P_{\theta}$, using a
finite-memory learning algorithm.

Specifically, we consider the bias estimation problem, defined as follows:
$X_{1},X_{2},\ldots$ is a sequence of independent identically distributed
random variables drawn according to the $\mathsf{Bern}(\theta)$ distribution.
An $S$-state estimation procedure for this problem consists of two functions:
$f$, and $\hat{\theta}$, where $f:[S]\times\\{0,1\\}\rightarrow[S]$ is a
deterministic state transition (or memory update) function (here
$[S]=\\{1,\ldots,S\\}$), and $\hat{\theta}:[S]\rightarrow[0,1]$ is the
estimate function. Letting $M_{n}$ denote the state of the memory at time $n$,
this finite-state machine evolves according to the rule

$\displaystyle M_{0}$ $\displaystyle=s_{\text{init}},$ (1) $\displaystyle
M_{n}$ $\displaystyle=f(M_{n-1},X_{n})\in[S],$ (2)

for some predetermined initial state $s_{\text{init}}\in[S]$. If the machine
is stopped at time $n$, it outputs the estimation $\hat{\theta}(M_{n})$. We
define the (asymptotic) quadratic risk attained by this estimation procedure,
given that the true value of the parameter is $\theta$, to be111It is not
difficult to show that the limit exists due to the underlying finite-state
structure and the independence of the samples.

$\displaystyle
R_{\theta}(f,\hat{\theta})=\lim_{n\rightarrow\infty}\frac{1}{n}\sum_{i=1}^{n}\operatorname{\mathbb{E}}\left(\hat{\theta}(M_{i})-\theta\right)^{2}.$
(3)

We are interested in the _minimax risk_ of the estimation problem, defined as

$\displaystyle
R(S)\triangleq\min_{f,\hat{\theta}}\max_{\theta\in[0,1]}R_{\theta}(f,\hat{\theta}),$
(4)

where the minimum is taken over all $S$-state estimation procedures. This
paper derives an upper bound on the minimax risk, which together with a known
lower bound, establishes the exact behavior of the minimax risk with $S$.

Note that here the memory update function $f$ is not allowed to depend on
time. First, as our focus here is on upper bounds, it is always desirable to
use the weakest possible model. Moreover, the restriction to time-invariant
algorithms is operationally appealing, since storing the time index
necessarily incurs a memory cost. Furthermore, since the number of samples is
unbounded, just storing the code generating a time-varying algorithm may
require unbounded memory.

Besides memory, another resource that plays an important role here is
randomness. While allowing the use of randomization in the estimation
procedure may certainly help, this resource has a cost. Even if one has access
to unlimited randomness (which is the case in our setting, since randomness
can be easily extracted from the i.i.d. sequence $X_{1},X_{2},\ldots$),
storing this randomness places a toll on one’s memory budget, which needs to
be taken into account in our deterministic setup. One can nevertheless define
the randomized minimax risk of the estimation problem, to be the smallest
asymptotic risk that can be uniformly guaranteed when randomized state-
transition functions $f$ are allowed, i.e.,

$\displaystyle R_{\mathsf{rand}}(S)\triangleq\min_{\text{randomized
}f,\hat{\theta}}\,\max_{\theta\in[0,1]}R_{\theta}(f,\hat{\theta}),$ (5)

We emphasize that in the above, in contrast to the deterministic setup we
consider in this paper, randomness is “free” and not counted toward the memory
budget. Our main result is that, in contrast to what was conjectured by
[Leighton and Rivest(1986)], $R(S)$ and $R_{\mathsf{rand}}(S)$ are equal up to
constants independent of $S$.

Let us be more precise. Prior to this work, it was known that
$R_{\mathsf{rand}}(S)=\Theta(1/S)$. The upper bound was proved by
[Samaniego(1973)], who constructed an $S$-state randomized estimation
procedure that asymptotically induces a $\mathrm{Binomial}(S-1,\theta)$
stationary distribution on the memory state space. The lower bound was
established a decade later by [Leighton and Rivest(1986)], using the Markov
chain tree theorem. In the same paper, [Leighton and Rivest(1986)] further
constructed a deterministic $S$-state estimation procedure by de-randomizing
Samaniego’s construction, and as a result showed that $R(S)=O(\log{S}/S)$.
They then conjectured that this is the best possible asymptotic minimax risk
any deterministic $S$-state estimation procedure can attain, and further
stated the problem of proving or disproving this conjecture as the first out
of five open problems left for future research. A nice interpretation of their
conjecture is the naturally appealing claim that an optimal deterministic
algorithm can be obtained by de-randomizing the optimal random algorithm. In
their deterministic algorithm, which they believed to be optimal, randomness
is extracted from the measurements by augmenting each state with $O(\log(S))$
additional states, which increases the overall MSE (see Section III of
[Leighton and Rivest(1986)]). Surprisingly, we show that such a de-
randomization is suboptimal, thereby disproving the conjecture of Leighton and
Rivest.

######  Theorem 1.1.

$\displaystyle R(S)=O\left(\frac{1}{S}\right).$ (6)

Since deterministic $S$-state estimation procedures are a subset of the class
of $S$-state randomized estimation procedures, we clearly have $R(S)\geq
R_{\mathsf{rand}}(S)=\Omega(1/S)$, where the lower bound is due to [Leighton
and Rivest(1986)]. Consequently:

######  Corollary 1.2.

$\displaystyle R(S)=\Theta\left(\frac{1}{S}\right).$ (7)

###  1.1 Related work

The study of learning and estimation under memory constraints has been
initiated in the late 1960s by Cover and Hellman (with a precursor by
[Robbins(1956)]) and remained an active research area for a decade or so. It
has then been largely abandoned, but recently it has been again enjoying much
attention, due to the reasons described above, and many works have addressed
different aspects of the learning under memory constraints problem over the
last few years. See, e.g., [Steinhardt and Duchi(2015), Steinhardt et
al.(2016)Steinhardt, Valiant, and Wager, Raz(2018), Dagan and Shamir(2018),
Dagan et al.(2019)Dagan, Kur, and Shamir, Sharan et al.(2019)Sharan, Sidford,
and Valiant] for a far from exhaustive list of recent works.

Most of the old work on learning with finite memory has been focused on the
hypothesis testing problem. For the problem of deciding whether an i.i.d.
sequence was drawn from $\mathsf{Bern}(p)$ or $\mathsf{Bern}(q)$,
[Cover(1969)] described a time-varying finite-state machine with only $S=4$
states, whose error probability approaches zero with the sequence length. As
time-varying procedures suffer from the shortcomings described above, [Hellman
and Cover(1970)] addressed the same binary hypothesis testing problem within
the class of time-invariant randomized procedures. They have found an _exact_
characterization of the smallest attainable error probability for this
problem. To demonstrate the important role randomization plays in approaching
this value, the same authors show in [Hellman and Cover(1971)] that for any
memory size $S<\infty$ and $\delta>0$, there exists problems such that any
$S$-state deterministic procedure has probability of error
$\operatorname{\mathsf{P_{e}}}\geq\frac{1}{2}-\delta$, while their randomized
procedure from [Hellman and Cover(1970)] has
$\operatorname{\mathsf{P_{e}}}\leq\delta$. Note that one can simulate a
randomized procedure with a deterministic one by using some of the samples of
$\\{X_{n}\\}$ for randomness extraction, e.g., using [Von Neumann(1951)]
extraction. However, the extracted random bits must be stored, which could
result in a substantial increase in memory, see [Chandrasekaran(1970)]. In a
recent paper [Berg et al.(2020)Berg, Ordentlich, and Shayevitz] derived a
lower bound on the error probability attained by any $S$-state deterministic
procedure, showing that while the smallest attainable error probability
decreases exponentially fast with $S$ in both the randomized and the
deterministic setups, the base of the exponent can be arbitrarily larger in
the deterministic case.

One of the earlier works on estimation with finite memory is due to [Roberts
and Tooley(1970)], who tackled the problem of estimation under quadratic risk
for a random variable with additive noise. [Hellman(1974)] studied the problem
of estimating the mean $\theta$ of a Gaussian distribution and discovered a
$S$-state estimation procedure that asymptotically achieves the same Bayesian
quadratic risk as the optimal $S$-level quantizer $Q(\theta)$ for $\theta$,
where $Q:\mathbb{R}\to[S]$. As already described above, [Samaniego(1973)] and
[Leighton and Rivest(1986)] have showed that
$R_{\mathsf{rand}}(S)=\Theta(1/S)$. [Meron and Feder(2004), Ingber and
Feder(2006), Dar and Feder(2014)] studied the subject of finite-memory
universal prediction of sequences using randomized/deterministic machines.
More recently, [Jain and Tyagi(2018)] studied the shrinkage in memory between
the hypothesis testing and the estimation problem, namely the interesting fact
that a machine with $S$ states can distinguish between two coins with biases
that differ by $1/S$, whereas the best additive accuracy it can achieve in
estimating the bias is only $1/\sqrt{S}$. We further note that the problem of
estimating statistics with bounded memory is attracting considerable attention
in the machine learning literature lately, see, e.g., [Chien et
al.(2010)Chien, Ligett, and McGregor, Kontorovich(2012), McGregor et
al.(2012)McGregor, Pavan, Tirthapura, and Woodruff, Steinhardt and
Duchi(2015), Steinhardt et al.(2016)Steinhardt, Valiant, and Wager, Raz(2018),
Dagan and Shamir(2018), Dagan et al.(2019)Dagan, Kur, and Shamir, Sharan et
al.(2019)Sharan, Sidford, and Valiant]. Another closely related active line of
work is that of estimating statistics under limited communication, e.g.,
[Zhang et al.(2013)Zhang, Duchi, Jordan, and Wainwright, Garg et
al.(2014)Garg, Ma, and Nguyen, Braverman et al.(2016)Braverman, Garg, Ma,
Nguyen, and Woodruff, Xu and Raginsky(2017), Jordan et al.(2018)Jordan, Lee,
and Yang, Han et al.(2018a)Han, Özgür, and Weissman, Han et al.(2018b)Han,
Ozgur, and Weissman, Barnes et al.(2018)Barnes, Han, and Özgür, Acharya et
al.(2018)Acharya, Canonne, and Tyagi, Hadar et al.(2019)Hadar, Liu,
Polyanskiy, and Shayevitz, Hadar and Shayevitz(2019), Acharya et
al.(2020)Acharya, Canonne, and Tyagi].

##  2 Proof of Theorem 1.1

We now proceed to prove Theorem 1.1. We will describe our deterministic
$S$-state estimation procedure and show that it attains quadratic risk of
$O(1/S)$ uniformly for all $\theta\in[0,1]$. In this section we provide the
entire proof, but for clarity we rely on several technical claims whose proofs
are relegated to the next section or to the Appendix.

Recall from (1) and (2) that any deterministic $S$-state estimation procedure
corresponds to a finite-state machine with $S$ states, with at most two
outgoing edges from each state, one for $X_{i}=0$ and one for $X_{i}=1$.
Running this machine on an i.i.d. $\mathsf{Bern}{(\theta)}$ input sequence
$X_{1},X_{2},\ldots$, generates a Markov chain $\\{M_{n}\\}_{n=1}^{\infty}$,
where $M_{n}$ denotes the state of the machine at time $n$. We emphasize that
the distribution of the process $\\{M_{n}\\}$ depends on $\theta$, which is
the parameter we are trying to estimate. To lighten notation, we nevertheless
leave this dependence implicit. The construction we describe below trivially
achieves $R_{\theta}(f,\hat{\theta})=O(1/S)$ for $\theta=0$ and $\theta=1$,
and thus in the remainder of the paper we assume without loss of generality
that $\theta\in(0,1)$.

The high-level idea underlying our scheme is to break down the memory-
constrained estimation task into a sequence of memory-constrained (composite)
binary hypothesis testing sub-problems. In each such sub-problem, the goal is
to decide whether the true underlying parameter $\theta$ satisfies
$\\{\theta<q\\}$ or $\\{\theta>p\\}$, for some $0<q<p<1$. Those decisions are
then used in order to traverse an induced Markov chain in a way that enables
us to accurately estimate $\theta$.

Let us now describe the particular structure of the proposed machine. In our
construction, the state space $[S]$ is partitioned into $K$ disjoint sets
denoted by $\mathcal{S}_{1},\ldots,\mathcal{S}_{K}$, where the estimation
function value is the same inside each $\mathcal{S}_{k}$, i.e.,

$\displaystyle\hat{\theta}(s)=\hat{\theta}_{k},\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \forall
s\in\mathcal{S}_{k},\;k\in[K].$ (8)

The goal is to design a machine for which the stationary distribution of
$\\{M_{n}\\}$ corresponding to the parameter $\theta$ will concentrate on
states that belong to classes $\mathcal{S}_{k}$ for which
$(\theta-\hat{\theta}_{k})^{2}$ is the smallest. This goal is in general
easier to achieve when each set consists of a large number of states, which
corresponds to small $K$ (as the total number of states $S$ is fixed). On the
other hand, the quadratic risk such a machine can attain is obviously limited
by the number of different sets $K$, and in particular is $\Omega(1/K^{2})$,
as there must exist some $\theta\in[0,1]$ at distance $\Omega(1/K)$ from all
points $\hat{\theta}_{1},\ldots,\hat{\theta}_{K}$. Thus, the choice of $K$
should balance the tension between these two contrasting goals; specifically,
we will see that the choice $K=\Theta(\sqrt{S})$ is suitable to that end.

Since the estimator $\hat{\theta}$ depends on $\\{M_{n}\\}$ only through its
class, it is natural to define the _quantized process_
$\\{Q_{n}\\}_{n=1}^{\infty}$ obtained by the deterministic scalar mapping

$\displaystyle Q_{n}=\phi(M_{n}),\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ n=1,2,\ldots,$ (9)

where $\phi:[S]\to[K]$ maps each state to its set label (namely: $\phi(s)=k$
iff $s\in\mathcal{S}_{k}$). The process $\\{Q_{n}\\}$, as well as any process
on a finite alphabet, consists of _runs_ of the same letter. We can therefore
decompose it as $\\{S_{1},\tau_{1}\\},\\{S_{2},\tau_{2}\\},\ldots$, where
$S_{i}$ denotes the first letter in the $i$th run, and $\tau_{i}$ denotes its
length. We refer to the process $\\{S_{i}\\}_{i=1}^{\infty}$, supported on
$[K]$ as the _sampled process_ , and to $\\{\tau_{i}\\}_{i=1}^{\infty}$,
supported on $\mathbb{N}$, as the _holding times_ process. Note that both
$\\{S_{i}\\}$ and $\\{\tau_{i}\\}$ are deterministically determined by
$\\{Q_{n}\\}$ and hence, by the original process $\\{M_{n}\\}$. In general,
the sampled process can be complicated; however, in our construction, we
impose a particular structure that ensures that the sampled process
$\\{S_{n}\\}$ is also a Markov process. Specifically, for each $k\in[K]$ there
is an entry state $s_{k}\in\mathcal{S}_{k}$, such that all edges going out of
a state $\ell\notin\mathcal{S}_{k}$ to the set $\mathcal{S}_{k}$, go into the
entry state $s_{k}\in\mathcal{S}_{k}$. In other words, whenever $M_{n}$ enters
the set $\mathcal{S}_{k}$ from a different set, it does so through the
designated entry state only. This feature guarantees that at the beginning of
the $i$th run, the state of the original process $\\{M_{n}\\}$ is determined
by $S_{i}$, and consequently $\\{S_{i}\\}$ is indeed a Markov process itself.
Furthermore, conditioned on $S_{i}$, the holding time $\tau_{i}$ is
independent of the entire past. We denote the conditional distribution of
$\tau_{i}$ conditioned on the event $S_{i}=k$, by $P_{T_{k}}$. It will be
convenient to also define the random variables $T_{k}\sim P_{T_{k}}$, for
$k\in[K]$. In our construction, we further guarantee that any set
$\mathcal{S}_{k}$ is accessible from any other set $\mathcal{S}_{j}$, $j\neq
k$. This ensures that the underlying Markov process $\\{M_{n}\\}$ is ergodic,
and as a result, so is the sampled process $\\{S_{n}\\}$. We refer to the
structure described here, i.e., all sets are accessible from one another and
have entry states, as a _nested Markov structure_.

The ergodicity of $\\{M_{n}\\}$ immediately implies the ergodicity of the
quantized process $\\{Q_{n}\\}$, by (9). Denote by $\pi_{k}$ the stationary
probability of state $k$ for the process $\\{Q_{n}\\}$. We therefore have that
for a machine $f,\hat{\theta}$ of the type described above,

$\displaystyle
R_{\theta}=R_{\theta}(f,\hat{\theta})=\lim_{n\rightarrow\infty}\frac{1}{n}\sum_{i=1}^{n}\operatorname{\mathbb{E}}\left(\hat{\theta}(M_{i})-\theta\right)^{2}=\sum_{k=1}^{K}\pi_{k}\left(\hat{\theta}_{k}-\theta\right)^{2}.$
(10)

The next lemma determines the stationary distribution
$\\{\pi_{k}\\}_{k\in[K]}$ of the quantized process $\\{Q_{n}\\}$, in terms of
the stationary distribution $\\{\mu_{k}\\}_{k\in[K]}$ of the sampled process
$\\{S_{n}\\}$ and the expected holding times
$\\{\operatorname{\mathbb{E}}[T_{k}]\\}_{k\in[K]}$.

######  Lemma 2.1.

The unique stationary probability of state $k$ under the process $\\{Q_{n}\\}$
is

$\displaystyle\pi_{k}=\frac{\operatorname{\mathbb{E}}[T_{k}]\mu_{k}}{\sum_{j=1}^{M}\operatorname{\mathbb{E}}[T_{j}]\mu_{j}}.$
(11)

Combining Lemma 2.1 with (10), we have that the risk of such machine is

$\displaystyle R_{\theta}$
$\displaystyle=\sum_{k=1}^{K}\frac{\operatorname{\mathbb{E}}[T_{k}]\mu_{k}}{\sum_{j=1}^{M}\operatorname{\mathbb{E}}[T_{j}]\mu_{j}}\left(\hat{\theta}_{k}-\theta\right)^{2}.$
(12)

It is immediately evident from (12) that the asymptotic risk attained by a
machine with the nested Markov structure defined above depends only on the
stationary distribution of the sampled process $\\{S_{n}\\}$ and the expected
holding times. Ideally, we would like to construct this machine such that two
things would happen for every $\theta$:

  1. (i)

$\\{\mu_{k}\\}$ would be concentrated on states whose corresponding estimate
$\hat{\theta}_{k}$ is close to $\theta$;

  2. (ii)

The expected holding times for these states will be at least as large as those
of other states.

We now describe how our machine is designed to achieve the desired behaviour
(i) of $\\{\mu_{k}\\}$. Later, we will see that the desired behavior (ii) of
$\\{\mathbb{E}[T_{k}]\\}$ follows more or less automatically.

First, we set our estimators to be222The denominator is set to $K+2$ rather
than $K$ for minor technical reasons, in order to avoid dealing with
probabilities on the boundary of the simplex in the analysis.

$\displaystyle\hat{\theta}_{k}=\frac{k}{K+2},\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ k\in[K].$ (13)

We then design our machine such that the sampled process $\\{S_{n}\\}$ is a
random walk, that moves either one state left or one state right from each
state (except for the extreme states $1$ and $K$ that behave slightly
differently). In particular, the $k$th state in $\\{S_{n}\\}$ is connected
only to states $k+1$ and $k-1$ for all $k\in\\{2,\ldots,K-1\\}$. The precise
diagram for the sampled process $\\{S_{n}\\}$ is shown in Figure 1, where the
transition probabilities $\\{p_{k},q_{k}=1-p_{k}\\}_{k\in[K]}$ will depend on
$\theta$ through the construction of the original machine generating the
original Markov chain $\\{M_{n}\\}$. We design the machine in a way that
guarantees that the random walk $\\{S_{n}\\}$ has a strong _drift_ towards the
state $k$ whose corresponding estimator is closest to $\theta$. In particular,
if $\theta>\frac{k+1}{K+2}$ then $p_{k}>1-\epsilon$ and conversely, if
$\theta<\frac{k}{K+2}$ then $p_{k}<\epsilon$, for some $\epsilon<1/2$ and all
states $k\in\\{2,\ldots,K-1\\}$.

$1$$\cdots$$i$$\cdots$$K$$q_{2}$$q_{i}$$1$$q_{i+1}$$q_{K-1}$$q_{i-1}$$p_{2}$$p_{i-1}$$p_{i}$$1$$p_{i+1}$$p_{K-1}$
Figure 1: A sampled chain of $K$ states.

The desired drift behavior is enabled by constructing the sets
$\mathcal{S}_{1},\ldots,\mathcal{S}_{K}$ as _mini-chains_ , where the $k$th
mini-chain consists of $N_{k}$ states, and is designed to solve the composite
binary hypothesis testing problem:
$\mathcal{H}_{0}:\left\\{\theta>\frac{k+1}{K+2}\right\\}$ vs.
$\mathcal{H}_{1}:\left\\{\theta<\frac{k}{K+2}\right\\}$. Each mini-chain
$\mathcal{S}_{k}$ is initialized in its entry state $s_{k}$, and eventually
moves to the entry state $s_{k+1}$ of mini-chain $\mathcal{S}_{k+1}$ if it
decided in favor of hypothesis $\mathcal{H}_{0}$, or to the entry state
$s_{k-1}$ of mini-chain $\mathcal{S}_{k-1}$ if it decided in favor of
hypothesis $\mathcal{H}_{1}$. The time it takes it to “make a decision” is the
random holding time with some distribution $P_{T_{k}}$. Note that if the error
probability of the machine is smaller than $\epsilon<1/2$ under both
hypotheses, we will indeed attain the desired drift behavior. Our goal now is
to design mini-chains that attain small error probabilities with as few states
as possible. To that end, we appeal to [Berg et al.(2020)Berg, Ordentlich, and
Shayevitz], where the authors defined the following machine.333Their machine
was designed to solve the _simple_ binary hypothesis test
$\mathcal{H}_{0}:\\{\theta=p\\}$ vs. $\mathcal{H}_{1}:\\{\theta=q\\}$, but as
our analysis demonstrates, the difference between the two problems is not
significant.

######  Definition 2.2.

$\operatorname{\mathsf{RUNS}}(N,p,q)$ is the machine with $N\geq 4$ states
depicted in Figure 2, designed to decide between the hypotheses
$\mathcal{H}_{0}:\\{\theta>p\\}$ vs. $\mathcal{H}_{1}:\\{\theta<q\\}$, for
some $0<q<p<1$. The machine is initialized at state $s$ and evolves according
to the sequence of input bits $X_{1},X_{2},\ldots$. If the machine observes a
run of $N-s$ ones before observing a run of $s-1$ zeros, it decides
$\mathcal{H}_{0}$ and exists right. Otherwise, it decides $\mathcal{H}_{1}$
and exists left. The initial state of the machine is $s=f(N,p,q)$, where

$\displaystyle f(N,p,q)\triangleq 2+\left\lceil\frac{\log pq}{\log p(1-p)+\log
q(1-q)}(N-3)\right\rfloor,$ (14)

is an integer between $2$ and $N-1$. We denote the (worst case) error
probability of the machine by
$\operatorname{\mathsf{P_{e}}}^{\operatorname{\mathsf{RUNS}}(N,p,q)}=\max\left\\{p^{0}_{1},p^{1}_{0}\right\\}$,
where

$\displaystyle p^{0}_{1}$ $\displaystyle=\sup_{\theta<q}\leavevmode\nobreak\
\leavevmode\nobreak\ \Pr_{X_{1},X_{2}\ldots\stackrel{{\scriptstyle
i.i.d.}}{{\sim}}\mathsf{Bern}(\theta)}\left(\operatorname{\mathsf{RUNS}}(N,p,q)\text{
decides }\mathcal{H}_{0}\right),$ (15) $\displaystyle p^{1}_{0}$
$\displaystyle=\sup_{\theta>p}\leavevmode\nobreak\ \leavevmode\nobreak\
\Pr_{X_{1},X_{2}\ldots\stackrel{{\scriptstyle
i.i.d.}}{{\sim}}\mathsf{Bern}(\theta)}\left(\operatorname{\mathsf{RUNS}}(N,p,q)\text{
decides }\mathcal{H}_{1}\right).$ (16)

$1$$\cdots$$s$$\cdots$$N$$\cdots$$\cdots$$1-\theta$$1-\theta$$1-\theta$$1-\theta$$1-p$$\theta$$\theta$$\theta$$\theta$exit
left$\theta$exit right Figure 2: $\operatorname{\mathsf{RUNS}}(N,p,q)$ \-
Deterministic Binary Hypothesis Testing Machine

The next lemma demonstrates that with $N=O(K)$ states, the machine
$\operatorname{\mathsf{RUNS}}(N,p,q)$ can decide whether $\theta>p$ or
$\theta<q=p-1/K$ with constant error probability $\epsilon<1/2$. Thus, the
desired drift can be attained by mini-chains of $O(K)$ states.

######  Lemma 2.3.

For any $\frac{2}{K}\leq p\leq 1-\frac{1}{K}$, $q=p-\frac{1}{K}$ and
$0<\epsilon<1/2$, let444Logarithms in this paper are taken to base $2$.

$\displaystyle N=N(\epsilon,p,K)\triangleq 3+\left\lceil K\cdot
6\log\frac{2}{\epsilon\cdot\left(p-\frac{1}{K}\right)(1-p)}\right\rceil.$ (17)

Then

$\displaystyle\operatorname{\mathsf{P_{e}}}^{\operatorname{\mathsf{RUNS}}(N,p,q)}<\epsilon.$
(18)

We therefore take the $k$th mini-chain $\mathcal{S}_{k}$ as the machine
$\operatorname{\mathsf{RUNS}}(N_{k},p,q)$ with $q=\frac{k}{K+2}$,
$p=q+\frac{1}{K+2}=\frac{k+1}{K+2}$, and
$N_{k}=N(\epsilon,\frac{k+1}{K+2},K+2)$. The total number of states in our
machine is therefore (see calculation in the appendix)

$\displaystyle S$
$\displaystyle=\sum_{k=1}^{K}N_{k}=\sum_{k=1}^{K}N\left(\epsilon,\frac{k+1}{K+2},K+2\right)\leq
6(K+2)^{2}\log\left(\frac{2e}{\epsilon}\right),$ (19)

and the sampled chain $\\{S_{n}\\}$ indeed satisfies the desired drift
property: for all $2\leq k\leq K-1$ we have that if $\theta>\frac{k+1}{K+2}$
then $p_{k}>1-\epsilon$ whereas if $\theta<\frac{k}{K+2}$ then
$p_{k}<\epsilon$. Note that we did not quantify $p_{k}$ for the case where
$\theta\in\left[\frac{k}{K+2},\frac{k+1}{K+2}\right]$, but as will become
apparent below, it is indeed not needed for our analysis. Also note that
whenever the sampled chain reaches state $1$ it will immediately move back to
state $2$, and whenever it reaches state $K$ it will immediately move back to
state $K-1$ (that is, $p_{1}=1$ and $p_{K}=0$), but the holding times in those
states are nevertheless random (and may be very large if the underlying
$\theta$ is very close to $0$ or $1$, and dictated by the time it takes for
the corresponding $\operatorname{\mathsf{RUNS}}(N,p,q)$ mini-chains
$\mathcal{S}_{1}$ and $\mathcal{S}_{K}$ to reach a decision). The next lemma
shows that the drift property implies that if
$\theta\in\left[\frac{k}{K+2},\frac{k+1}{K+2}\right]$, then the stationary
probability $\mu_{j}$ of the $j$th state in the sampled chain decreases
exponentially with the “distance” $|j-k|$.

######  Lemma 2.4.

Assume that $\theta\in\left[\frac{k}{K+2},\frac{k+1}{K+2}\right]$. Then, the
stationary distribution of the sampled process $\\{S_{n}\\}$ induced by the
machine described above satisfies

$\displaystyle\mu_{k-i}\leq\mu_{k-1}\left(\frac{\epsilon}{1-\epsilon}\right)^{i-1}$
(20)

for $1\leq i\leq k-1$, and

$\displaystyle\mu_{k+i}\leq\mu_{k+1}\left(\frac{\epsilon}{1-\epsilon}\right)^{i-1}$
(21)

for $1\leq i\leq K-k$.

This shows that the stationary distribution of the sampled chain $\\{S_{n}\\}$
is indeed concentrated on the desired states. The next lemma deals with the
expected holding times, and lower bounds the ratio between the expected
holding time in the “correct state” $k$ and the expected holding time in any
other state of the sampled chain.

######  Lemma 2.5.

If $\theta<\frac{j}{K+2}$, then the expected holding time in state $i$
satisfies

$\displaystyle\operatorname{\mathbb{E}}[T_{j}]\geq(1-\epsilon)\operatorname{\mathbb{E}}[T_{i}]$
(22)

for all $i>j$. Similarly, if $\theta>\frac{j+1}{K+2}$, then the expected
holding time in state $i$ satisfies

$\displaystyle\operatorname{\mathbb{E}}[T_{j}]\geq(1-\epsilon)\operatorname{\mathbb{E}}[T_{i}]$
(23)

for all $i<j$.

We now combine (12) with Lemma 2.4 and Lemma 2.5 in order to upper bound the
asymptotic risk attained by our machine, and establish the claim
$R_{\theta}=O(1/S)$ for all $\theta\in(\frac{1}{K+2},\frac{K+1}{K+2})$. The
cases where $\theta\in[0,\frac{1}{K+2})$ and $\theta\in(\frac{K+1}{K+2},1]$
then follow easily from minor adjustments, and are treated in the appendix.

Assume that $\frac{k}{K+2}\leq\theta\leq\frac{k+1}{K+2}$ for some $k\in[K]$.
From (3), the asymptotic risk is then

$\displaystyle R_{\theta}$
$\displaystyle=\sum_{i=1}^{K}\frac{\operatorname{\mathbb{E}}[T_{i}]\mu_{i}}{\sum_{j=1}^{K}\operatorname{\mathbb{E}}[T_{j}]\mu_{j}}\left(\frac{i}{K+2}-\theta\right)^{2}$
(24)
$\displaystyle=\sum_{i=1}^{k-1}\frac{\operatorname{\mathbb{E}}[T_{i}]\mu_{i}}{\sum_{j=1}^{K}\operatorname{\mathbb{E}}[T_{j}]\mu_{j}}\left(\frac{i}{K+2}-\theta\right)^{2}+\frac{\operatorname{\mathbb{E}}[T_{k}]\mu_{k}}{\sum_{j=1}^{K}\operatorname{\mathbb{E}}[T_{j}]\mu_{j}}\left(\frac{k}{K+2}-\theta\right)^{2}$
$\displaystyle+\sum_{i=k+1}^{K}\frac{\operatorname{\mathbb{E}}[T_{i}]\mu_{i}}{\sum_{j=1}^{K}\operatorname{\mathbb{E}}[T_{j}]\mu_{j}}\left(\frac{i}{K+2}-\theta\right)^{2}$
(25)
$\displaystyle\leq\frac{1}{1-\epsilon}\sum_{i=1}^{k-1}\frac{\operatorname{\mathbb{E}}[T_{k-1}]\mu_{k-1}}{\sum_{j=1}^{K}\operatorname{\mathbb{E}}[T_{j}]\mu_{j}}\frac{\mu_{i}}{\mu_{k-1}}\left(\frac{i}{K+2}-\theta\right)^{2}+\frac{1}{(K+2)^{2}}$
$\displaystyle+\frac{1}{1-\epsilon}\sum_{i=k+1}^{K}\frac{\operatorname{\mathbb{E}}[T_{k+1}]\mu_{k+1}}{\sum_{j=1}^{K}\operatorname{\mathbb{E}}[T_{j}]\mu_{j}}\frac{\mu_{i}}{\mu_{k+1}}\left(\frac{i}{K+2}-\theta\right)^{2}$
(26)
$\displaystyle\leq\frac{1}{1-\epsilon}\sum_{i=1}^{k-1}\left(\frac{\epsilon}{1-\epsilon}\right)^{i-1}\left(\frac{i+1}{K+2}\right)^{2}+\frac{1}{(K+2)^{2}}+\frac{1}{1-\epsilon}\sum_{i=1}^{K-k}\left(\frac{\epsilon}{1-\epsilon}\right)^{i-1}\left(\frac{i+1}{K+2}\right)^{2}$
(27)
$\displaystyle\leq\frac{1}{(K+2)^{2}}\cdot\frac{1}{1-\epsilon}\left(2\cdot\sum_{i=1}^{\infty}\left(\frac{\epsilon}{1-\epsilon}\right)^{i-1}(i+1)^{2}+1\right)$
(28)
$\displaystyle\leq\frac{6\log\left(\frac{2e}{\epsilon}\right)}{S}\left(\frac{2\epsilon}{(1-2\epsilon)^{3}}+\frac{8(1-\epsilon)}{(1-2\epsilon)^{2}}+\frac{1}{1-\epsilon}\right),$
(29)

where (26) follows from Lemma 2.5, (27) follows from Lemma 2.4 and since
$\frac{\operatorname{\mathbb{E}}[T_{j}]\mu_{j}}{\sum_{k=1}^{M}\operatorname{\mathbb{E}}[T_{k}]\mu_{k}}\leq
1$, (28) is since we only add positive terms, and (29) is due to the identity
$\sum_{i=0}^{\infty}q^{i}(i+2)^{2}=\frac{q(1+q)+4(1-q)}{(1-q)^{3}}$ and by
substituting (19). Finally, substituting $\epsilon=1/100$ into (29) gives
$R_{\theta}<\frac{600}{S}$.

##  3 Proofs of Technical Claims

The following simple lemma will be useful for the proofs of Lemma 2.1 and
Lemma 2.4.

######  Lemma 3.1.

Let $\\{X_{n}\\}$ be a stationary process over some alphabet $\mathcal{S}$.
Then for any disjoint partition
$\mathcal{C}\cup\mathcal{C}^{\prime}=\mathcal{S}$, it holds that

$\displaystyle\Pr(X_{n}\in\mathcal{C},X_{n+1}\in\mathcal{C}^{\prime})=\Pr(X_{n}\in\mathcal{C}^{\prime},X_{n+1}\in\mathcal{C}).$
(30)

######  Proof 3.2.

For any disjoint partition $\mathcal{C}\cup\mathcal{C}^{\prime}=\mathcal{S}$
we have

$\displaystyle\Pr(X_{n+1}\in\mathcal{C}^{\prime})=\Pr(X_{n}\in\mathcal{C}^{\prime})=\Pr(X_{n}\in\mathcal{C}^{\prime},X_{n+1}\in\mathcal{C}^{\prime})+\Pr(X_{n}\in\mathcal{C}^{\prime},X_{n+1}\in\mathcal{C}).$
(31)

Subtracting $\Pr(X_{n}\in\mathcal{C}^{\prime},X_{n+1}\in\mathcal{C}^{\prime})$
from both sides, establishes the claim.

######  Proof 3.3.

of Lemma 2.1 : The proof is very similar to the derivation of the invariant
measure of a continuous-time Markov chain. Let $\\{M^{\prime}_{n}\\}$ be the
process defined as follows:

  1. 1.

Draw $M^{\prime}_{0}$ according to the stationary distribution of $M_{n}$.

  2. 2.

For $n>0$, draw $M^{\prime}_{n+1}|M^{\prime}_{n}\sim W$, where $W$ is the
Markov kernel of our chain.

  3. 3.

For $n<0$, draw $M^{\prime}_{n-1}|M^{\prime}_{n}\sim W^{\prime}$, where
$W^{\prime}$ is the reverse Markov kernel corresponding to the stationary
distribution.

Clearly, $\\{M^{\prime}_{n}\\}$ is a stationary ergodic process with marginal
distribution equal to the stationary distribution of $\\{M_{n}\\}$. Let
$Q^{\prime}_{n}=\phi(M^{\prime}_{n})$ where $\phi$ is the mapping to the set
label (similar to $Q_{n}$). Clearly, $\\{Q^{\prime}_{n}\\}$ is a stationary
process as well, and $\\{Q_{n}\\}$ converges to the marginal distribution of
$\\{Q^{\prime}_{n}\\}$. Recall that $\\{Q^{\prime}_{n}\\}$ is composed of runs
of consecutive letters of $[K]$, and that the length of each run is
independent of all past runs. The run-length random variables do depend on the
letter $k\in[K]$ of the run, and we denote by $T_{k}\sim P_{T_{k}}$ a generic
random variable corresponding to a run of the letter $k$. Furthermore, we
denote by $A_{k}(t)$ the event that a new run in $\\{Q^{\prime}_{n}\\}$ of
letters $k$ started at time $t$, and let the integer random variable
$Z_{t}\geq 1$ denote the number of symbols left in the current run at time $t$
(including the one at time $t$). If $Q^{\prime}_{0}=k$, this means that a run
of letters $k$ started at some time $-t$, and its corresponding $Z_{-t}$ was
greater than $t$. We can therefore write

$\displaystyle\pi_{k}$ $\displaystyle=\Pr\left(Q^{\prime}_{0}=k\right)$ (32)
$\displaystyle=\sum_{t=0}^{\infty}\Pr\left(A_{k}(-t),Z_{-t}>t\right)$ (33)
$\displaystyle=\sum_{t=0}^{\infty}\Pr\left(A_{k}(-t)\right)\Pr\left(T_{k}>t\right)$
(34)
$\displaystyle=\Pr\left(A_{k}(0)\right)\sum_{t=0}^{\infty}\Pr\left(T_{k}>t\right)$
(35)
$\displaystyle=\Pr\left(A_{k}(0)\right)\operatorname{\mathbb{E}}\left(T_{k}\right),$
(36)

where (34) follows since given that $A_{k}(t)$ occurred, $Z_{t}$ is
independent of everything that happened before this run began and has the
distribution $P_{T_{k}}$, (35) is from stationarity, and (36) is due to the
identity
$\sum_{t=0}^{\infty}\Pr\left(T_{k}>t\right)=\operatorname{\mathbb{E}}\left(T_{k}\right)$
for a non-negative random variable. Thus, from stationarity, for each $t$ we
have

$\displaystyle\Pr\left(A_{k}(t)\right)=\Pr\left(A_{k}(0)\right)=\frac{\pi_{k}}{\operatorname{\mathbb{E}}\left(T_{k}\right)}.$
(37)

Now, denote by $B_{k}(t)$ the event that a run of letters $k$ ended at time
$t$. Note that since $\\{Q^{\prime}_{n}\\}$ is stationary, Lemma 3.1 suggests
that the probability it enters a state $k$ is equal to the probability it
leaves a state $k$ at any given time, namely

$\displaystyle\Pr(B_{k}(t))=\Pr(A_{k}(t))=\frac{\pi_{k}}{\operatorname{\mathbb{E}}\left(T_{k}\right)},\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ k\in[k].$ (38)

Now consider the sampled Markov chain $\\{S_{n}\\}$, and denote its stationary
distribution for state $j$ by $\mu_{j}$, and its transition probability from
state $j$ to state $k$ by $P_{jk}$. We have

$\displaystyle\Pr\left(A_{k}(t+1)\right)$ $\displaystyle=\sum_{j\neq
k}\Pr\left(B_{j}(t)\right)P_{jk}.$ (39)

Substituting (37) into (39), we have

$\displaystyle\frac{\pi_{k}}{\operatorname{\mathbb{E}}\left(T_{k}\right)}=\sum_{j\neq
k}\frac{\pi_{j}}{\operatorname{\mathbb{E}}\left(T_{j}\right)}P_{jk}.$ (40)

Thus, the stationary distribution $\\{\pi_{k}\\}_{k\in[K]}$ of $\\{Q_{n}\\}$
must satisfy (40). Since $\\{\mu_{k}\\}_{k\in[K]}$ is the unique stationary
distribution of $\\{S_{n}\\}$, we have that

$\displaystyle\pi_{j}^{*}=\frac{\operatorname{\mathbb{E}}[T_{j}]\mu_{j}}{\sum_{k=1}^{M}\operatorname{\mathbb{E}}[T_{k}]\mu_{k}},\leavevmode\nobreak\
\leavevmode\nobreak\ j\in[K],$ (41)

is the unique distribution satisfying (40), and is consequently the stationary
distribution of $\\{Q_{n}\\}$, as claimed.

######  Proof 3.4.

of Lemma 2.4 : By construction, $\\{S_{n}\\}$ follows the transition
probability law plotted in Figure 1. For all $i\in\\{2,\ldots,K-2\\}$, we have
from Lemma 3.1 that by choosing the partition
$\mathcal{C}=\\{1,\ldots,i-1\\},\mathcal{C}^{\prime}=\\{i,\ldots,K\\}$ and
noting from Figure 1 that only adjacent states are connected,
$\mu_{i-1}p_{i-1}=\mu_{i}q_{i}$, or equivalently

$\displaystyle\mu_{i-1}$ $\displaystyle=\frac{q_{i}}{p_{i-1}}\mu_{i}.$ (42)

By construction of the mini-chains $\mathcal{S}_{i}$ and by Lemma 2.3, we have
that $q_{i}<\epsilon$ and $p_{i}>1-\epsilon$ for $i<k$. Thus, repeated
application of (42) yields

$\displaystyle\mu_{k-i}=\prod_{j=1}^{i}\frac{q_{k-j+1}}{p_{k-j}}\mu_{k}\leq\left(\frac{\epsilon}{1-\epsilon}\right)^{i-1}\mu_{k-1},$
(43)

for $2\leq i\leq k-1$. Similarly, since $p_{i}<\epsilon$ and
$q_{i}>1-\epsilon$ for $i>k$, we have

$\displaystyle\mu_{k+i}=\prod_{j=1}^{i}\frac{p_{k+j-1}}{q_{k+j}}\mu_{k}\leq\left(\frac{\epsilon}{1-\epsilon}\right)^{i-1}\mu_{k+1},$
(44)

for $1\leq i\leq K-1-k$. For the extreme states $1$ and $K$, by appealing to
Lemma 3.1 and recalling that $p_{1}=1$ and $q_{K}=1$, we have

$\displaystyle\mu_{1}=q_{2}\mu_{2}\leq\epsilon\mu_{2}<\frac{\epsilon}{1-\epsilon}\cdot\mu_{2},$
(45)

and

$\displaystyle\mu_{K}=p_{K-1}\mu_{K-1}\leq\epsilon\mu_{K-1}<\frac{\epsilon}{1-\epsilon}\cdot\mu_{K-1}.$
(46)

######  Proof 3.5.

of Lemma 2.5 : Fix $\theta$, and recall that each state $i$ in the sampled
chain corresponds to a
$\operatorname{\mathsf{RUNS}}\left(N_{i},\frac{i}{K+2},\frac{i+1}{K+2}\right)$
mini-chain in the original chain, where $N_{i}=N(\epsilon,\frac{i}{K+2},K+2)$
is as defined in (17). Restricting our attention to that mini-chain, denote by
$s_{i}=f\left(N_{i},\frac{i}{K+2},\frac{i+1}{K+2}\right)$ its initial state,
and denote by $T_{i}^{1}$ the first time a run of $N_{i}-s_{i}$ consecutive
ones is observed, and $T_{i}^{0}$ as the first time a run of $s_{i}-1$
consecutive zeros is observed. We exit the mini-chain when either a run of
$N_{i}-s_{i}$ consecutive ones or a run of $s_{i}-1$ consecutive zeros is
observed, so we have that the exit time $T_{i}$ satisfies $T_{i}\leq
T_{i}^{1}$ and $T_{i}\leq T_{i}^{0}$, which implies

$\displaystyle\operatorname{\mathbb{E}}[T_{i}]\leq\operatorname{\mathbb{E}}[T_{i}^{1}],$
(47)
$\displaystyle\operatorname{\mathbb{E}}[T_{i}]\leq\operatorname{\mathbb{E}}[T_{i}^{0}].$
(48)

Next, we observe that $i\mapsto s_{i}$ is monotonically non-increasing and
$i\mapsto N_{i}-s_{i}$ is monotonically non-decreasing. These facts can be
verified from the formulas (17) and (14) for $N(\epsilon,\frac{i}{K+2},K+2)$
and $f\left(N_{i},\frac{i}{K+2},\frac{i+1}{K+2}\right)$, respectively. Thus
the expected time to observe a run of $N_{i}-s_{i}$ consecutive ones is also
non-decreasing and we have

$\displaystyle\operatorname{\mathbb{E}}\left[T_{1}^{1}\right]\leq\operatorname{\mathbb{E}}\left[T_{2}^{1}\right]\leq\ldots\leq\operatorname{\mathbb{E}}\left[T_{j}^{1}\right],$
(49)

and similarly

$\displaystyle\operatorname{\mathbb{E}}\left[T_{S}^{0}\right]\leq\operatorname{\mathbb{E}}\left[T_{S-1}^{0}\right]\leq\ldots\leq\operatorname{\mathbb{E}}\left[T_{j}^{0}\right].$
(50)

Let $\\{W_{n}^{j}(\theta)\\}$ be a random walk in
$\operatorname{\mathsf{RUNS}}\left(N_{j},\frac{j}{K},\frac{j+1}{K}\right)$
under $\theta$, and let $W_{n}^{j}(\theta)\rightarrow 1$ (resp.
$W_{n}^{j}(\theta)\rightarrow 0$) denote the event that
$\\{W_{n}^{j}(\theta)\\}$ exits right (resp. exits left). We have

$\displaystyle
T_{j}^{1}=T_{j}+\left(T_{j}^{1}-T_{j}\right)\operatorname{\mathds{1}}(W_{n}^{j}(\theta)\rightarrow
0).$ (51)

By taking the expectation of both sides, we have

$\displaystyle\operatorname{\mathbb{E}}\left[T_{j}^{1}\right]$
$\displaystyle=\operatorname{\mathbb{E}}\left[T_{j}\right]+\operatorname{\mathbb{E}}\left[\left(T_{j}^{1}-T_{j}\right)\operatorname{\mathds{1}}(W_{n}^{j}(\theta)\rightarrow
0)\right]$ (52)
$\displaystyle=\operatorname{\mathbb{E}}\left[T_{j}\right]+\Pr(W_{n}^{j}(\theta)\rightarrow
0)\operatorname{\mathbb{E}}\left[T_{j}^{1}-T_{j}|W_{n}^{j}(\theta)\rightarrow
0\right]$ (53)
$\displaystyle=\operatorname{\mathbb{E}}\left[T_{j}\right]+\Pr(W_{n}^{j}(\theta)\rightarrow
0)\operatorname{\mathbb{E}}\left[T_{j}^{1}\right],$ (54)

due to

$\displaystyle\operatorname{\mathbb{E}}\left[T_{j}^{1}-T_{j}|W_{n}^{j}(\theta)\rightarrow
0\right]$
$\displaystyle=\sum_{t=1}^{\infty}\Pr(T_{j}=t|W_{n}^{j}(\theta)\rightarrow
0)\operatorname{\mathbb{E}}\left[T_{j}^{1}-T_{j}|T_{j}=t,W_{n}^{j}(\theta)\rightarrow
0\right]$ (55)
$\displaystyle=\sum_{t=1}^{\infty}\Pr(T_{j}=t|W_{n}^{j}(\theta)\rightarrow
0)\operatorname{\mathbb{E}}\left[T_{j}^{1}-t|T_{j}^{1}>t,W_{t}^{j}(\theta)=1\right]$
(56)
$\displaystyle=\sum_{t=1}^{\infty}\Pr(T_{j}=t|W_{n}^{j}(\theta)\rightarrow
0)\operatorname{\mathbb{E}}\left[T_{j}^{1}\right]$ (57)
$\displaystyle=\operatorname{\mathbb{E}}\left[T_{j}^{1}\right],$ (58)

where (56) is since no run of $N_{j}-s_{j}$ ones was observed until time $t$
and the last bit was $X_{t}=0$, and (57) follows from the memoryless property
of the chain. Thus,

$\displaystyle\operatorname{\mathbb{E}}\left[T_{j}\right]$
$\displaystyle=\Pr(W_{n}^{j}(\theta)\rightarrow
1)\operatorname{\mathbb{E}}\left[T_{j}^{1}\right],$ (59)
$\displaystyle\operatorname{\mathbb{E}}\left[T_{j}\right]$
$\displaystyle=\Pr(W_{n}^{j}(\theta)\rightarrow
0)\operatorname{\mathbb{E}}\left[T_{j}^{0}\right].$ (60)

Equation (22) now follows by recalling that $\Pr(W_{n}^{j}(\theta)\rightarrow
0)\geq 1-\epsilon$ for $\theta<\frac{j}{K}$ and by appealing to (50) and (48).
(23) is proven similarly by appealing to (49).

This work was supported by the ISF under Grants 1791/17 and 1495/18.

## References

  * [Acharya et al.(2018)Acharya, Canonne, and Tyagi] Jayadev Acharya, Clément L Canonne, and Himanshu Tyagi.  Distributed simulation and distributed inference.  _arXiv preprint arXiv:1804.06952_ , 2018.
  * [Acharya et al.(2020)Acharya, Canonne, and Tyagi] Jayadev Acharya, Clément L Canonne, and Himanshu Tyagi.  Inference under information constraints ii: Communication constraints and shared randomness.  _IEEE Transactions on Information Theory_ , 66(12):7856–7877, 2020.
  * [Barnes et al.(2018)Barnes, Han, and Özgür] Leighton Pate Barnes, Yanjun Han, and Ayfer Özgür.  A geometric characterization of Fisher information from quantized samples with applications to distributed statistical estimation.  In _2018 56th Annual Allerton Conference on Communication, Control, and Computing (Allerton)_ , pages 16–23. IEEE, 2018.
  * [Berg et al.(2020)Berg, Ordentlich, and Shayevitz] Tomer Berg, Or Ordentlich, and Ofer Shayevitz.  Binary hypothesis testing with deterministic finite-memory decision rules.  In _2020 IEEE International Symposium on Information Theory (ISIT)_ , pages 1259–1264. IEEE, 2020.
  * [Braverman et al.(2016)Braverman, Garg, Ma, Nguyen, and Woodruff] Mark Braverman, Ankit Garg, Tengyu Ma, Huy L Nguyen, and David P Woodruff.  Communication lower bounds for statistical estimation problems via a distributed data processing inequality.  In _Proceedings of the forty-eighth annual ACM symposium on Theory of Computing_ , pages 1011–1020. ACM, 2016.
  * [Chandrasekaran(1970)] Balakrishnan Chandrasekaran.  Finite-memory hypothesis testing–a critique (corresp.).  _IEEE Transactions on Information Theory_ , 16(4):494–496, 1970.
  * [Chien et al.(2010)Chien, Ligett, and McGregor] Steve Chien, Katrina Ligett, and Andrew McGregor.  Space-efficient estimation of robust statistics and distribution testing.  In _ICS_ , pages 251–265. Citeseer, 2010.
  * [Cover(1969)] Thomas M Cover.  Hypothesis testing with finite statistics.  _The Annals of Mathematical Statistics_ , 40(3):828–835, 1969.
  * [Dagan and Shamir(2018)] Yuval Dagan and Ohad Shamir.  Detecting correlations with little memory and communication.  In _Conference On Learning Theory_ , pages 1145–1198, 2018.
  * [Dagan et al.(2019)Dagan, Kur, and Shamir] Yuval Dagan, Gil Kur, and Ohad Shamir.  Space lower bounds for linear prediction in the streaming model.  In _Conference on Learning Theory_ , pages 929–954, 2019.
  * [Dar and Feder(2014)] Ronen Dar and Meir Feder.  Finite-memory prediction as well as the empirical mean.  _IEEE transactions on information theory_ , 60(8):4526–4543, 2014.
  * [Garg et al.(2014)Garg, Ma, and Nguyen] Ankit Garg, Tengyu Ma, and Huy L Nguyen.  On communication cost of distributed statistical estimation and dimensionality.  _arXiv preprint arXiv:1405.1665_ , 2014.
  * [Hadar and Shayevitz(2019)] Uri Hadar and Ofer Shayevitz.  Distributed estimation of gaussian correlations.  _IEEE Transactions on Information Theory_ , 65(9):5323–5338, 2019.
  * [Hadar et al.(2019)Hadar, Liu, Polyanskiy, and Shayevitz] Uri Hadar, Jingbo Liu, Yury Polyanskiy, and Ofer Shayevitz.  Communication complexity of estimating correlations.  In _Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing_ , pages 792–803, 2019.
  * [Han et al.(2018a)Han, Özgür, and Weissman] Yanjun Han, Ayfer Özgür, and Tsachy Weissman.  Geometric lower bounds for distributed parameter estimation under communication constraints.  In _Conference On Learning Theory_ , pages 3163–3188. PMLR, 2018a.
  * [Han et al.(2018b)Han, Ozgur, and Weissman] Yanjun Han, Ayfer Ozgur, and Tsachy Weissman.  Geometric lower bounds for distributed parameter estimation under communication constraints.  _Proceedings of Machine Learning Research_ , 75, 2018b.
  * [Hellman(1974)] Martin E Hellman.  Finite-memory algorithms for estimating the mean of a gaussian distribution (corresp.).  _IEEE Transactions on Information Theory_ , 20(3):382–384, 1974.
  * [Hellman and Cover(1970)] Martin E Hellman and Thomas M Cover.  Learning with finite memory.  _The Annals of Mathematical Statistics_ , pages 765–782, 1970.
  * [Hellman and Cover(1971)] Martin E Hellman and Thomas M Cover.  On memory saved by randomization.  _The Annals of Mathematical Statistics_ , 42(3):1075–1078, 1971.
  * [Ingber and Feder(2006)] Amir Ingber and Meir Feder.  Prediction of individual sequences using universal deterministic finite state machines.  In _2006 IEEE International Symposium on Information Theory_ , pages 421–425. IEEE, 2006.
  * [Jain and Tyagi(2018)] Ayush Jain and Himanshu Tyagi.  Effective memory shrinkage in estimation.  In _2018 IEEE International Symposium on Information Theory (ISIT)_ , pages 1071–1075. IEEE, 2018.
  * [Jordan et al.(2018)Jordan, Lee, and Yang] Michael I Jordan, Jason D Lee, and Yun Yang.  Communication-efficient distributed statistical inference.  _Journal of the American Statistical Association_ , 2018.
  * [Kontorovich(2012)] Leonid (Aryeh) Kontorovich.  Statistical estimation with bounded memory.  _Statistics and Computing_ , 22(5):1155–1164, 2012.
  * [Leighton and Rivest(1986)] F. Thomson Leighton and Ronald Rivest.  Estimating a probability using finite memory.  _IEEE Transactions on Information Theory_ , 32(6):733–742, 1986.
  * [McGregor et al.(2012)McGregor, Pavan, Tirthapura, and Woodruff] Andrew McGregor, A Pavan, Srikanta Tirthapura, and David Woodruff.  Space-efficient estimation of statistics over sub-sampled streams.  In _Proceedings of the 31st ACM SIGMOD-SIGACT-SIGAI symposium on Principles of Database Systems_ , pages 273–282, 2012.
  * [Meron and Feder(2004)] Eado Meron and Meir Feder.  Finite-memory universal prediction of individual sequences.  _IEEE Transactions on Information Theory_ , 50(7):1506–1523, 2004.
  * [Raz(2018)] Ran Raz.  Fast learning requires good memory: A time-space lower bound for parity learning.  _Journal of the ACM (JACM)_ , 66(1):3, 2018.
  * [Robbins(1956)] Herbert Robbins.  A sequential decision problem with a finite memory.  _Proceedings of the National Academy of Sciences of the United States of America_ , 42(12):920, 1956.
  * [Roberts and Tooley(1970)] Richard Roberts and J Tooley.  Estimation with finite memory.  _IEEE Transactions on Information Theory_ , 16(6):685–691, 1970.
  * [Samaniego(1973)] Francisco J. Samaniego.  Estimating a binomial parameter with finite memory.  _IEEE Transactions on Information Theory_ , 19(5):636–643, 1973.
  * [Sharan et al.(2019)Sharan, Sidford, and Valiant] Vatsal Sharan, Aaron Sidford, and Gregory Valiant.  Memory-sample tradeoffs for linear regression with small error.  In _Symposium on Theory of Computing (STOC)_ , 2019.
  * [Steinhardt and Duchi(2015)] Jacob Steinhardt and John Duchi.  Minimax rates for memory-bounded sparse linear regression.  In _Conference on Learning Theory_ , pages 1564–1587, 2015.
  * [Steinhardt et al.(2016)Steinhardt, Valiant, and Wager] Jacob Steinhardt, Gregory Valiant, and Stefan Wager.  Memory, communication, and statistical queries.  In _Conference on Learning Theory_ , pages 1490–1516, 2016.
  * [Von Neumann(1951)] John Von Neumann.  13\. various techniques used in connection with random digits.  _Appl. Math Ser_ , 12(36-38):5, 1951.
  * [Xu and Raginsky(2017)] A. Xu and M. Raginsky.  Information-theoretic lower bounds on Bayes risk in decentralized estimation.  _IEEE Transactions on Information Theory_ , 63(3):1580–1600, March 2017.
  * [Zhang et al.(2013)Zhang, Duchi, Jordan, and Wainwright] Yuchen Zhang, John Duchi, Michael I Jordan, and Martin J Wainwright.  Information-theoretic lower bounds for distributed statistical estimation with communication constraints.  In _Advances in Neural Information Processing Systems_ , pages 2328–2336, 2013.

##  Appendix A Bound on the error probability

To establish Lemma 2.3, we need to prove two supporting lemmas. First, we show
that $p^{1}_{0}$ is achieved by $\theta=q$, and $p^{0}_{1}$ is achieved by
$\theta=p$. Denote the probability of deciding $\mathcal{H}_{0}$ under
$\theta$ as $p_{0}(\theta)$, and the probability of deciding $\mathcal{H}_{1}$
under $\theta$ as $p_{1}(\theta)$.

######  Lemma A.1.

For $\operatorname{\mathsf{RUNS}}(N,p,q)$, if $\theta>p$, then
$p_{1}(\theta)\leq p_{1}(p)$. Similarly, if $\theta<q$, then
$p_{0}(\theta)\leq p_{0}(q)$.

######  Proof A.2.

We prove the first part of the claim, and the second follows symmetrically. To
that end, we use a coupling argument. Denote by $\\{W_{n}^{p}\\}$ the random
walk on $\operatorname{\mathsf{RUNS}}(N,p,q)$ under $p$ and
$\\{W_{n}^{\theta}\\}$ as the random walk on
$\operatorname{\mathsf{RUNS}}(N,p,q)$ under $\theta$, where here we assume the
extreme states $1$ and $N$ are absorbing, such that once the random walk
reaches one of these states, it stays there forever. We couple the two
processes using the following joint distribution for
$\left(\\{W_{n}^{p}\\},\\{W_{n}^{\theta}\\}\right)$: Let $\\{W_{n}^{p}\\}$ be
the standard walk on the chain under the $\mathsf{Bern}(p)$ sequence. For any
$n$, if $W_{n}^{p}$ goes one step to the right, $W_{n}^{\theta}$ goes one step
to the right as well. If $W_{n}^{p}$ goes one step to the left, we flip an
independent $\mathsf{Bern}\left(\frac{\theta-p}{1-p}\right)$ coin, and
$W_{n}^{\theta}$ goes one step to the right upon seeing $1$ or one step to the
left upon seeing $0$. It is easy to see that the marginal distribution under
$\\{W_{n}^{\theta}\\}$ corresponds to the chain under the
$\mathsf{Bern}(\theta)$ distribution, and this is therefore a valid coupling.
Our claim now immediately follows from the observation that under this
coupling, $W_{n}^{\theta}$ is never to the left of $W_{n}^{p}$.

Second, we prove the following lemma, which bounds the error probability of
$\operatorname{\mathsf{RUNS}}(N,p,q)$ when the hypotheses are $\frac{1}{K}$
apart.

######  Lemma A.3.

For any $\frac{2}{K}\leq p\leq 1-\frac{1}{K}$, $q=p-\frac{1}{K}$ and $N\geq
3+\left\lceil K\cdot 6\log\frac{2}{p_{\min}}\right\rceil$, it holds that

$\displaystyle\operatorname{\mathsf{P_{e}}}^{\operatorname{\mathsf{RUNS}}(N,p,q)}\leq\frac{2}{p_{\min}}\cdot\exp_{2}\left\\{-\frac{\left(1-\frac{1}{K\cdot
p}\right)\left(\frac{1}{K}H_{b}(p)-\frac{1}{K^{2}}\log
p\right)\left(N-3\right)}{\frac{1}{K}\left(1-2\left(p-\frac{1}{K}\right)\right)-2\left(p-\frac{1}{K}\right)\left(1-p+\frac{1}{K}\right)\log
p(1-p)}\right\\},$ (61)

where $p_{\min}=\min\\{p(1-p),q(1-q)\\}$ and $H_{b}(p)\triangleq-p\log
p-(1-p)\log(1-p)$ is the binary entropy of $p$.

######  Proof A.4.

In [Berg et al.(2020)Berg, Ordentlich, and Shayevitz], the authors showed that
for initial state $s$, we have

$\displaystyle p_{1}(p)$
$\displaystyle=\frac{1-p^{N-s}}{1+\frac{p^{N-s-1}}{(1-p)^{s-2}}-p^{N-s-1}}$
(62)
$\displaystyle\leq\frac{(1-p)^{s-2}}{p^{N-s-1}}\cdot\frac{1}{1-(1-p)^{s-2}},$
(63)

and

$\displaystyle p_{0}(q)$
$\displaystyle=\frac{1-(1-q)^{s-1}}{1+\frac{(1-q)^{s-2}}{q^{N-s-1}}-(1-q)^{s-2}}$
(64)
$\displaystyle\leq\frac{q^{N-s-1}}{(1-q)^{s-2}}\cdot\frac{1}{1-q^{N-s-1}}.$
(65)

Choosing $s=s^{*}$, where $s^{*}$ is

$\displaystyle 2+\frac{\log pq}{\log p(1-p)+\log q(1-q)}(N-3),$ (66)

we get

$\displaystyle\frac{(1-p)^{s^{*}-2}}{p^{N-s^{*}-1}}=\frac{q^{N-s^{*}-1}}{(1-q)^{s^{*}-2}}=2^{-r(p,q)(N-3)},$
(67)

where

$\displaystyle r(p,q)\triangleq\frac{\log p\log(1-q)-\log q\log(1-p)}{\log
p(1-p)+\log q(1-q)}.$ (68)

We therefore have, for $s=s^{*}$,

$\displaystyle\max\left\\{p_{0}(q),p_{1}(p)\right\\}\leq
2^{-r(p,q)(N-3)}\cdot\max\left\\{\frac{1}{1-(1-p)^{s^{*}-2}},\frac{1}{1-q^{N-s^{*}-1}}\right\\}.$
(69)

Recall that $s$ is a state in the chain so it must be an integer, whereas
$s^{*}$ may not be. Thus, we need to round $s^{*}$ either up or down, in which
case, both ratios in (67) $\frac{(1-p)^{s^{*}-2}}{p^{N-s^{*}-1}}$, and
$\frac{q^{N-s^{*}-1}}{(1-q)^{s^{*}-2}}$, will increase by at most
$\frac{1}{p_{\min}}$, where $p_{\min}=\min\\{p(1-p),q(1-q)\\}$. Furthermore,
for our choice of $N$, $\frac{2}{K}\leq p\leq 1-\frac{1}{K}$ and
$q=p-\frac{1}{K}$, we have that $3<s*<N-2$ and the rightmost part of (69) is
always upper bounded by $2$. Combining this with Lemma A.1, we therefore get
the bound

$\displaystyle\operatorname{\mathsf{P_{e}}}^{\operatorname{\mathsf{RUNS}}(N,p,q)}=\max\left\\{p^{0}_{1},p^{1}_{0}\right\\}=\max\left\\{p_{0}(q),p_{1}(p)\right\\}\leq\frac{2}{p_{\min}}\cdot
2^{-r(p,q)(N-3)}.$ (70)

Setting $p-q=\delta>0$, we have

$\displaystyle r\left(p,p-\delta\right)$ $\displaystyle=\frac{\log
p\log(1-p+\delta)-\log(p-\delta)\log(1-p)}{\log
p(1-p)+\log(p-\delta)(1-p+\delta)}$ (71) $\displaystyle=\frac{\log
p\left(\log(1-p)+\log\left(1+\frac{\delta}{1-p}\right)\right)-\left(\log
p+\log\left(1-\frac{\delta}{p}\right)\right)\log(1-p)}{\log
p(1-p)+\log(1-p)+\log\left(1+\frac{\delta}{1-p}\right)+\log
p+\log\left(1-\frac{\delta}{p}\right)}$ (72)
$\displaystyle\geq\frac{\frac{\delta}{1-p+\delta}\log
p+\frac{\delta}{p}\log(1-p)}{2\log
p(1-p)+\frac{\epsilon}{1-p+\delta}-\frac{\delta}{p-\delta}}$ (73)
$\displaystyle=-\frac{p-\delta}{p}\cdot\frac{\delta p\log
p+\delta(1-p+\delta)\log(1-p)}{2(p-\delta)(1-p+\delta)\log
p(1-p)-\delta(1-2(p-\delta))}$ (74)
$\displaystyle=\left(1-\frac{\delta}{p}\right)\cdot\frac{\delta
H_{b}(p)-\delta^{2}\log(1-p)}{\delta(1-2(p-\delta))-2(p-\delta)(1-p+\delta)\log
p(1-p)},$ (75)

where (73) follows from $\frac{x}{x+1}\leq\log(1+x)\leq x$ and (75) follows
from the definition of the binary entropy. The claim follows by substituting
$\delta=\frac{1}{K}$.

######  Proof A.5.

of Lemma 2.3 : Let $N=3+\lceil c\cdot K\rceil$, for some $c\geq
6\log\frac{2}{p_{\min}}$. From Lemma A.3,

$\displaystyle\operatorname{\mathsf{P_{e}}}^{\operatorname{\mathsf{RUNS}}\left(N,p,p-\frac{1}{K}\right)}\leq\frac{2}{p_{\min}}\cdot\exp_{2}\left\\{-\frac{c\left(1-\frac{1}{K\cdot
p}\right)\left(H_{b}(p)-\frac{1}{K}\log(1-p)\right)}{\frac{1}{K}\left(1-2\left(p-\frac{1}{K}\right)\right)-2\left(p-\frac{1}{K}\right)\left(1-p+\frac{1}{K}\right)\log
p(1-p)}\right\\}$ (76)

In order to guarantee
$\operatorname{\mathsf{P_{e}}}^{\operatorname{\mathsf{RUNS}}\left(N,p,p-\frac{1}{K}\right)}\leq\epsilon$,
it is sufficient to choose $c$ to be

$\displaystyle\frac{\frac{1}{K}\left(1-2\left(p-\frac{1}{K}\right)\right)-2\left(p-\frac{1}{K}\right)\left(1-p+\frac{1}{K}\right)\log
p(1-p)}{\left(1-\frac{1}{K\cdot
p}\right)\left(H_{b}(p)-\frac{1}{K}\log(1-p)\right)}\cdot\log\frac{2}{\epsilon
p_{\min}}.$ (77)

Upper bounding the first term in the brackets, we get

$\displaystyle\frac{\frac{1}{K}\left(1-2\left(p-\frac{1}{K}\right)\right)-2\left(p-\frac{1}{K}\right)\left(1-p+\frac{1}{K}\right)\log
p(1-p)}{\left(1-\frac{1}{K\cdot
p}\right)\left(H_{b}(p)-\frac{1}{K}\log(1-p)\right)}$ (78)
$\displaystyle\leq\frac{1}{1-\frac{1}{K\cdot
p}}\cdot\frac{\frac{1}{K}+2\left(H_{b}(p)-\frac{1}{K}\log(1-p)\right)}{H_{b}(p)-\frac{1}{K}\log(1-p)}$
(79) $\displaystyle=\frac{1}{1-\frac{1}{K\cdot p}}\left(2+\frac{1}{K\cdot
H_{b}(p)-\log(1-p)}\right)$ (80) $\displaystyle\leq\frac{3}{1-\frac{1}{K\cdot
p}}$ (81) $\displaystyle\leq 6,$ (82)

where (79), (81) and (82) follows since $p\geq\frac{2}{K}$ implies

  1. (i)

$H_{b}(p)-\frac{1}{K}\log(1-p)\geq-\left(p-\frac{1}{K}\right)\left(1-p+\frac{1}{K}\right)\log
p(1-p)$,

  2. (ii)

$K\cdot H_{b}(p)-\log(1-p)\geq 1$,

  3. (iii)

$\frac{1}{1-\frac{1}{K\cdot p}}\leq 2$.

Combining (82) and (77), noting that
$\min\left\\{p(1-p),\left(p-\frac{1}{K}\right)\left(1-p+\frac{1}{K}\right)\right\\}\geq\left(p-\frac{1}{K}\right)(1-p)$,
and choosing

$\displaystyle
c=c_{\epsilon,p}=6\log\frac{2}{\epsilon\left(p-\frac{1}{K}\right)(1-p)},$ (83)

the proof is concluded.

##  Appendix B Calculation of number of states $S$ in (19)

Using the expression in (17) for $N(\epsilon,p,K)$ we obtain

$\displaystyle S$ $\displaystyle=\sum_{k=1}^{K}N_{k}$ (84)
$\displaystyle=\sum_{k=1}^{K}N\left(\epsilon,\frac{k+1}{K+2},K+2\right)$ (85)
$\displaystyle\leq
4K+6(K+2)\sum_{k=1}^{K}\log\frac{2}{\epsilon\left(\frac{k}{K+2}\cdot\frac{K-k+1}{K+2}\right)}$
(86) $\displaystyle=4K+6K(K+2)\log\left(\frac{2}{\epsilon}\right)-6(K+2)\cdot
2\sum_{k=1}^{\frac{K}{2}}\log\left(\frac{k}{K+2}\cdot\frac{K-k+1}{K+2}\right)$
(87) $\displaystyle\leq
4K+6K(K+2)\log\left(\frac{2}{\epsilon}\right)-6(K+2)\cdot
2\sum_{k=1}^{\frac{K}{2}}\log\left(\frac{k}{K+2}\right)-6K(K+2)$ (88)
$\displaystyle\leq
4K+6K(K+2)\log\left(\frac{2}{\epsilon}\right)-6K(K+2)\log\left(\frac{K}{2e(K+2)}\right)-6K(K+2)$
(89) $\displaystyle\leq
4K+6K(K+2)\log\left(\frac{2e}{\epsilon}\right)+12(K+2)\leq
6(K+2)^{2}\log\left(\frac{2e}{\epsilon}\right),$ (90)

where (87) follows from the symmetry of
$\left(\frac{k}{K+2}\cdot\frac{K-k+1}{K+2}\right)$ around $k=\frac{K}{2}$,
(88) from $\frac{K-k+1}{K+2}\geq\frac{1}{2}$ for all $1\leq k\leq\frac{K}{2}$,
(89) is from $n!\geq\left(\frac{n}{e}\right)^{n}$ and (90) follows from
$\log(1+x)\geq\frac{x}{x+1}$.

##  Appendix C Proof of $R_{\theta}=O(1/S)$ for
$\theta\in\left[0,\frac{1}{K+2}\right)$ and
$\theta\in\left(\frac{K+1}{K+2},1\right]$

We shall prove the case $\theta\leq\frac{1}{K+2}$. The case of $\theta\geq
1-\frac{1}{K+2}$ follows from a symmetric argument. We show how previous
results imply that for very small $\theta$ the stationary distribution is
concentrated on the two leftmost states of the sampled chain. From there, the
proof is similar (yet not identical) to the proof of the general case. Let us
go step by step:

  * •

Firstly, Lemma 2.3 implies that $p_{k}<\epsilon$ for all $k>1$ in the chain of
Figure 1.

  * •

Now, a simplified (one-sided) version of Lemma 2.4 shows the stationary
distribution is exponentially decreasing for all states $\geq 2$. This follows
since eq. (44) still holds with $k=1$,

$\displaystyle\mu_{i+1}\leq\left(\frac{\epsilon}{1-\epsilon}\right)^{i-1}\mu_{2},$
(91)

for $1\leq i\leq K-1$.

  * •

Applying Lemma 2.5, eq. (22) states that
$\operatorname{\mathbb{E}}[T_{j}]>(1-\epsilon)\operatorname{\mathbb{E}}[T_{i}]$
for all $j\in[n]$ and $i>j$.

  * •

Calculate the risk $R_{\theta}$.

$\displaystyle R_{\theta}$
$\displaystyle=\sum_{i=1}^{K}\frac{\operatorname{\mathbb{E}}[T_{i}]\mu_{i}}{\sum_{j=1}^{K}\operatorname{\mathbb{E}}[T_{j}]\mu_{j}}\left(\frac{i}{K+2}-\theta\right)^{2}$
(92)
$\displaystyle=\frac{\operatorname{\mathbb{E}}[T_{1}]\mu_{1}}{\sum_{j=1}^{K}\operatorname{\mathbb{E}}[T_{j}]\mu_{j}}\left(\frac{1}{K+2}-\theta\right)^{2}+\sum_{i=2}^{K}\frac{\operatorname{\mathbb{E}}[T_{i}]\mu_{i}}{\sum_{j=1}^{K}\operatorname{\mathbb{E}}[T_{j}]\mu_{j}}\left(\frac{i}{K+2}-\theta\right)^{2}$
(93)
$\displaystyle\leq\frac{1}{(K+2)^{2}}+\frac{1}{1-\epsilon}\sum_{i=2}^{K}\frac{\operatorname{\mathbb{E}}[T_{2}]\mu_{2}}{\sum_{j=1}^{K}\operatorname{\mathbb{E}}[T_{j}]\mu_{j}}\frac{\mu_{i}}{\mu_{2}}\left(\frac{i}{K+2}-\theta\right)^{2}$
(94)
$\displaystyle\leq\frac{1}{(K+2)^{2}}+\frac{1}{1-\epsilon}\sum_{i=1}^{K-1}\left(\frac{\epsilon}{1-\epsilon}\right)^{i-1}\left(\frac{i+1}{K+2}\right)^{2}$
(95)
$\displaystyle\leq\frac{1}{(K+2)^{2}}\cdot\frac{1}{1-\epsilon}\left(\sum_{i=1}^{\infty}\left(\frac{\epsilon}{1-\epsilon}\right)^{i-1}(i+1)^{2}+1\right)$
(96)
$\displaystyle\leq\frac{6\log\left(\frac{2e}{\epsilon}\right)}{S}\left(\frac{\epsilon}{(1-2\epsilon)^{3}}+\frac{4(1-\epsilon)}{(1-2\epsilon)^{2}}+\frac{1}{1-\epsilon}\right),$
(97)

where (94) follows from Lemma 2.5, (95) follows from Lemma 2.4 and since
$\frac{\operatorname{\mathbb{E}}[T_{j}]\mu_{j}}{\sum_{k=1}^{M}\operatorname{\mathbb{E}}[T_{k}]\mu_{k}}\leq
1$, (96) is since we only add positive terms, and (97) is due to the identity
$\sum_{i=0}^{\infty}q^{i}(i+2)^{2}=\frac{q(1+q)+4(1-q)}{(1-q)^{3}}$ and by
substituting (19). Finally, substituting $\epsilon=1/100$ into (97) gives
$R_{\theta}<\frac{300}{S}$.