# Memory Complexity of Entropy Estimation

Tomer Berg, Or Ordentlich and Ofer Shayevitz

###### Abstract

We observe an infinite sequence of independent identically distributed random
variables $X_{1},X_{2},\ldots$ drawn from an unknown distribution $p$ over
$[n]$, and our goal is to estimate the entropy
$H(p)=-\operatorname{\mathbb{E}}[\log p(X)]$ within an $\varepsilon$-additive
error. To that end, at each time point we are allowed to update a finite-state
machine with $S$ states, using a possibly randomized but time-invariant rule,
where each state of the machine is assigned an entropy estimate. Our goal is
to characterize the minimax memory complexity $S^{*}$ of this problem, which
is the minimal number of states for which the estimation task is feasible with
probability at least $1-\delta$ asymptotically, uniformly in $p$.
Specifically, we show that there exist universal constants $C_{1}$ and $C_{2}$
such that $S^{*}\leq C_{1}\cdot\frac{n(\log n)^{4}}{\varepsilon^{2}\delta}$
for $\varepsilon$ not too small, and $S^{*}\geq C_{2}\cdot\max\\{n,\frac{\log
n}{\varepsilon}\\}$ for $\varepsilon$ not too large. The upper bound is proved
using approximate counting to estimate the logarithm of $p$, and a finite
memory bias estimation machine to estimate the expectation operation. The
lower bound is proved via a reduction of entropy estimation to uniformity
testing. We also apply these results to derive bounds on the memory complexity
of mutual information estimation.

##  I Introduction

The problem of inferring properties of an underlying distribution given sample
access is called statistical property estimation. A typical setup is as
follows: given independent samples $X_{1},\ldots,X_{n}$ from an unknown
distribution $p$, the objective is to estimate a property $g(p)$ (e.g.,
entropy, support size, $L_{p}$ norm, etc.) under some resource limitation. A
prominent example of such a limitation is the amount of available samples, and
this limitation gives rise to the notion of sample complexity, namely the
minimal number of samples one needs to see in order to estimate $g(p)$ with
some given accuracy. Many real–world machine learning and data analysis tasks
are limited by insufficient samples, and the challenge of inferring properties
of a distribution given a small sample size is encountered in a variety of
settings, including text data, customer data, and the study of genetic
mutations across a population. The sample complexity of property estimation
and, specifically, of entropy estimation, have therefore received much
attention in the literature (see Section II for details).

However, in many contemporary settings, collecting enough samples for accurate
estimation is less of a problem, and the bottleneck shifts to the
computational resources available for the task and, in particular, the
available memory size. In this work, we therefore focus on the problem of
estimation under memory constraints, and, in particular, entropy estimation.
In order to isolate the effect that finite memory has on the fundamental
limits of the problem, we let the number of samples we process be arbitrarily
large.

Formally, the problem is defined as follows. Let $\Delta_{n}$ be the
collection of all distributions over $[n]$. The Shannon entropy of
$p\in\Delta_{n}$ is $H(p)=-\sum_{x\in[n]}p(x)\log p(x)$. Given independent
samples $X_{1},X_{2},\ldots$ from an unknown $p\in\Delta_{n}$, we would like
to accurately estimate $H(p)$ using limited memory. To that end, an $S$-state
entropy estimator is a finite-state machine with $S$ states, defined by two
functions: The (possibly randomized) memory update function
$f:[S]\times[n]\rightarrow[S]$, describing the transition between states as a
function of an input sample, and the entropy estimate function
$\hat{H}:[S]\rightarrow[0,\log n]$, assigning an entropy estimate to each
state. Letting $M_{t}$ denote the state of the memory at time $t$, this
finite-state machine evolves according to the rule:

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

for some predetermined initial state $s_{\text{init}}\in[S]$. If the machine
is stopped at time $t$, it outputs the estimation $\hat{H}(M_{t})$. We
restrict the discussion to time-invariant memory update function $f$, since
storing the time index necessarily incurs a memory cost, and, furthermore,
since the number of samples is unbounded, simply storing the code generating a
time-varying algorithm may require unbounded memory. We say that an
$\epsilon$-error occurred at time $t$ if our estimate $\hat{H}(M_{t})$ is
$\varepsilon$-far from the correct entropy. Our figure of merit for the
estimator is taken to be its worst-case asymptotic $\epsilon$-error
probability:

$\displaystyle\operatorname{\mathsf{P_{e}}}(f,\hat{H},\epsilon)$
$\displaystyle=\underset{p\in\Delta_{n}}{\sup}\limsup_{t\rightarrow\infty}\Pr\left(|\hat{H}(M_{t})-H(p)|>\varepsilon\right).$
(3)

We are interested in the _minimax memory complexity_
$S^{*}(n,\varepsilon,\delta)$, defined as the smallest integer $s$ for which
there exist $(f,\hat{H})$ such that
$\operatorname{\mathsf{P_{e}}}(f,\hat{H},\epsilon)\leq\delta$.

Our main result is an upper bound on $S^{*}(n,\varepsilon,\delta)$, which
shows that $\log\frac{n}{\varepsilon^{2}}+o\left(\log n\right)$ bits suffice
for entropy estimation when $\varepsilon>10^{-5}$, thus improving upon the
best known upper bounds thus far ([1, 2]). While our focus here is on
minimizing the memory complexity of the problem in the limit of infinite
number of available samples, we further show that the estimation algorithm
attaining this memory complexity upper bound only requires $\tilde{O}(n^{c})$
samples, for any $c>1$.111The $\tilde{O}$ suppresses poly-logarithmic terms.
Thus, in entropy estimation one can achieve almost optimal sample complexity
and memory complexity, simultaneously. Our proposed algorithm approximates the
logarithm of $p(x)$, for a given $x\in[n]$, using a Morris counter [3]. The
inherent structure of the Morris counter is particularly suited for
constructing a nearly-unbiased estimator for $\log p(x)$, making it a natural
choice for memory efficient entropy estimation. In order to compute the mean
of these estimators, $\operatorname{\mathbb{E}}[\widehat{\log p(X)}]$, in a
memory efficient manner, a finite-memory bias estimation machine (e.g., [4,
5]) is leveraged for simulating the expectation operator. The performance of a
scheme based on this high-level idea is analyzed, and yields the following
upper bound on the memory complexity:

######  Theorem 1.

For any $c>1$, $\beta>0$, $0<\delta<1$ and
$\varepsilon=10^{-5}+\beta+\psi_{c}(n)$, we have

$\displaystyle S^{*}(n,\varepsilon,\delta)\leq\frac{(c+1)^{4}n\cdot(\log
n)^{4}}{\beta^{2}\delta},$ (4)

where

$\displaystyle\psi_{c}(n)=\min\left\\{1+n^{-(c-1)+\sqrt{\frac{c}{\log
n}}},2\cdot 10^{8}\cdot n^{-\frac{1}{2}\cdot(c-1)+\sqrt{\frac{c}{8\log
n}}}\right\\}=O\left(n^{-\frac{1}{2}\cdot(c-1)+\sqrt{\frac{c}{8\log
n}}}\right).$ (5)

Moreover, there is an algorithm that attains (4) whenever the number of
samples is $\Omega\left(\frac{n^{c}\cdot\mathop{\mathrm{poly}}(\log
n)}{\delta}\cdot\mathop{\mathrm{poly}}(\log(1/\delta))\right)$, and returns an
estimation of $H(p)$ within an $\varepsilon$-additive error with probability
at least $1-3\delta$.

Note that while $\psi_{c}(n)$ vanishes for large $n$, our bound is always
limited to $\varepsilon>10^{-5}$. This small bias is due to inherent
properties of the Morris counter, on which we elaborate in Section III. As in
this work we are more interested in the large entropy regime (in which the
entropy grows with the alphabet size $n$), the limitation of the attainable
additive error to values above $10^{-5}$ is typically a moderate one. We also
note that if $n$ is large and $\varepsilon$ not too small, one can choose $c$
arbitrarily close to $1$, resulting in an algorithm whose sample complexity
has similar dependence on $n$ as those of the limited-memory entropy
estimation algorithms proposed in [1] and [2], while requiring far less memory
states. This result might be of practical interest for applications in which
memory is a scarcer resource than samples, e.g., a limited memory high-speed
router that leverages entropy estimation to monitor IP network traffic [6].

Furthermore, we derive two lower bounds on the memory complexity. The first
lower bound shows that when $H(p)$ is close to $\log{n}$, the memory
complexity cannot be too small. This bound is obtained via a reduction of
entropy estimation to uniformity testing, by noting that thresholding the
output of a good entropy estimation machine around $\log{n}$ can be used to
decide whether $p$ is close to the uniform distribution or not. The bound then
follows from the $\Omega(n)$ lower bound of [7] on uniformity testing. The
second lower bound follows from the observation that, if the number of states
is too small, there must be some value of the entropy at distance greater than
$\varepsilon$ from all estimate values, hence for this value of the entropy we
err with probability $1$. Combining these lower bounds yields the following.

######  Theorem 2.

For any $\varepsilon>0$, we have

$\displaystyle S^{*}(n,\varepsilon,\delta)\geq\frac{\log n}{2\varepsilon}.$
(6)

Furthermore, if $\varepsilon<\frac{1}{4\ln 2}$, then

$\displaystyle S^{*}(n,\varepsilon,\delta)\geq n(1-2\sqrt{\varepsilon\ln 2}).$
(7)

One of several open problems posed by the authors of [1] is to prove a lower
bound on the space requirement of a sample optimal algorithm for entropy
estimation. Theorem 2 answers this question by giving a lower bound on the
memory size needed when the number of samples is infinite, which clearly also
holds for any finite number of samples. In the concluding section of the
paper, we extend our results to the mutual information estimation problem. Let
$(X,Y)\sim p_{XY}$, where $p_{XY}$ is an unknown distribution over
$[n]\times[m]$ such that the marginal distribution of $X$ is $p_{X}$ and the
marginal distribution of $Y$ is $p_{Y}$. The mutual information between $X$
and $Y$ is given as $I(X;Y)=H(X)+H(Y)-H(X,Y)$. We derive the following bounds
on the memory complexity of mutual information estimation, namely the minimal
number of states needed to estimate $I(X;Y)$ with additive error at most
$\varepsilon$ with probability of at least $1-\delta$, which we denote as
$S_{\text{MI}}^{*}(n,m,\varepsilon,\delta)$.

######  Theorem 3.

For any $c>1$, $\beta>0$ and $\varepsilon=3\cdot
10^{-5}+\beta+O\left(n^{-\frac{1}{2}\cdot(c-1)}\vee
m^{-\frac{1}{2}\cdot(c-1)}\right)$,

$\displaystyle
S_{\text{MI}}^{*}(n,m,\varepsilon,\delta)\leq\frac{(c+1)^{6}nm\cdot(\log
nm)^{6}}{\beta^{2}\delta}.$ (8)

For $\varepsilon<\frac{1}{12\ln 2}$, and if
$\frac{n}{\log^{3}n}=\Omega(\log^{7}m)$ and
$\frac{m}{\log^{3}m}=\Omega(\log^{7}n)$ both hold, then

$\displaystyle
S_{\text{MI}}^{*}(n,m,\varepsilon,\delta)=\Omega\left(\frac{n\cdot
m}{\log^{3}n\cdot\log^{3}m}\right).$ (9)

##  II Related work

The study of estimation under memory constraints has received far less
attention then the sample complexity of statistical estimation. References
[8], [9] studied this setting for hypothesis testing with finite memory, and
[10], [4] have studied estimating the bias of a coin using a finite state
machine. It has then been largely abandoned, but recently there has been a
revived interest in space-sample trade-offs in statistical estimation, and
many works have addressed different aspects of the learning under memory
constraints problem over the last few years. See, e.g., [11, 12, 13, 14, 15,
16, 17, 18, 19] for a non exhaustive list of recent works.

The problem of estimating the entropy with limited independent samples from
the distribution has a long history. It was originally addressed by [20], who
suggested the simple and natural empirical plug-in estimator. This estimator
outputs the entropy of the empirical distribution of the samples, and its
sample complexity [21] is
$\Theta\left(\frac{n}{\varepsilon}+\frac{\log^{2}n}{\varepsilon^{2}}\right)$.
[21] showed that the plug-in estimator is always consistent, and the resulting
sample complexity was shown to be linear in $n$. In the last two decades, many
efforts were made to improve the bounds on the sample complexity. Paninski
[22, 23]] was the first to prove that it is possible to consistently estimate
the entropy using sublinear sample size. While the scaling of the minimal
sample size of consistent estimation was shown to be $\frac{n}{\log n}$ in the
seminal results of [24, 25], the optimal dependence of the sample size on both
$n$ and $\varepsilon$ was not completely resolved until recently. In
particular, $\Omega\left(\frac{n}{\varepsilon\log n}\right)$ samples were
shown to be necessary, and the best upper bound on the sample complexity was
relied on an estimator based on linear programming that can achieve an
additive error $\varepsilon$ using $O\left(\frac{n}{\varepsilon^{2}\log
n}\right)$ samples [26]. This gap was partially amended in [27] by a different
estimator, which requires $O\left(\frac{n}{\varepsilon\log n}\right)$ samples
but is only valid when $\varepsilon$ is not too small. The sharp sample
complexity was shown by [28, 29, 29] to indeed be

$\displaystyle\Theta\left(\frac{n}{\varepsilon\log
n}+\frac{\log^{2}n}{\varepsilon^{2}}\right).$ (10)

The space-complexity (which is the minimal memory in bits needed for the
algorithm) of estimating the entropy of the empirical distribution of the data
stream is well-studied for worst-case data streams of a given length, see
[30], [6], [31]. Reference [32] addressed the problem of deciding if the
entropy of a distribution is above or beyond than some predefined threshold,
using algorithms with limited memory. The trade-off between sample complexity
and space/communication complexity for the entropy estimation of a
distribution is the subject of a more recent line of work. The earliest work
on the subject is [1], where the authors constructed an algorithm which is
guaranteed to work with
$O(k/\varepsilon^{3}\cdot\operatorname{polylog}(1/\varepsilon))$ samples and
any memory size $b\geq 20\log\left(\frac{k}{\varepsilon}\right)$ bits (which
corresponds to $O(n^{20}/\varepsilon^{20})$ memory states in our setup). Their
upper bound on the sample complexity was later improved by [2] to
$O(k/\varepsilon^{2}\cdot\operatorname{polylog}(1/\varepsilon))$ with space
complexity of $O\left(\log\left(\frac{k}{\varepsilon}\right)\right)$ bits. In
both the above works, the constant in the space complexity upper bound can be
shown to actually be smaller than $20$ by a careful analysis, but it cannot be
made smaller than $2$.

##  III Preliminaries

In this section, we introduce mathematical notations and some relevant
background for the paper.

###  III-A Notations

We write $[n]$ to denote the set $\\{1,\ldots,n\\}$, and consider discrete
distributions over $[n]$. We use the notation $p_{i}$ to denote the
probability of element $i$ in distribution $p$. When $X$ is a random variable
on $[n]$, $p_{X}$ denotes the random variable obtained by evaluating $p$ in
location $X$. The entropy of $p$ is defined as $H(p)=-\sum_{x\in[n]}p_{x}\log
p_{x}=\operatorname{\mathbb{E}}_{X\sim p}(-\log p_{X})$, where $H(p)=0$ for a
single mass distribution and $H(p)=\log n$ a uniform distribution over $[n]$.
The total variation distance between distributions $p$ and $q$ is defined as
half their $\ell^{1}$ distance, i.e.,
$d_{\mathsf{TV}}(p,q)=\frac{1}{2}||p-q||_{1}=\frac{1}{2}\sum_{i=1}^{n}|p_{i}-q_{i}|$,
and their KL (Kullback–Leibler) divergence is defined as
$D_{\text{KL}}(p||q)=\sum_{i=1}^{n}p_{i}\log\frac{p_{i}}{q_{i}}$. Logarithms
are taken to base 2.

###  III-B Morris Counter

Suppose one wishes to implement a counter that counts up to $m$. Maintaining
this counter exactly can be accomplished using $\log m$ bits. In the first
example of a non-trivial streaming algorithm, Morris gave a randomized
“approximate counter”, which allows one to retrieve a constant multiplicative
approximation to $m$ with high probability using only $O(\log\log m)$ bits
(see [3]). The Morris Counter was later analyzed in more detail by Flajolet
[33], who showed that $O(\log\log m+\log(1/\varepsilon)+\log(1/\delta))$ bits
of memory are sufficient to return a $(1\pm\varepsilon)$ approximation with
success probability $1-\delta$. A recent result of [34] shows that $O(\log\log
m+\log(1/\varepsilon)+\log\log(1/\delta))$ bits suffice for the same task.

The original Morris counter is a random state machine with the following
simple structure: At each state $l=1,2,3,\ldots,$ an increment causes the
counter to transition to state $l+1$ with probability $2^{-l}$, and to remain
in state $l$ with probability $1-2^{-l}$. This is formally a discrete time
pure birth process, which can be seen in Figure 1.

$1$$2$$3$$\cdots$$l$$\cdots$$2^{-1}$$2^{-2}$$2^{-3}$$2^{-l}$ Figure 1: The
original Morris counter

The performance of the above counter was characterized by Flajolet, who proved
the following theorem.

######  Theorem 4 ([33]).

Let $C_{m}$ be the value of the Morris counter after $m$ increments. It holds
that

$\displaystyle\operatorname{\mathbb{E}}(C_{m})=\log m+\mu+g(\log m)+\phi(m),$
(11)

where $\mu\approx-0.273$ is a known constant, $g(\cdot)$ is a periodic
function of amplitude less than $10^{-5}$,
$|\phi(m)|\leq\min\left\\{1,\frac{2^{\sqrt{16\log m}}\cdot(\log
m)^{4.5}}{2m}\right\\}$ and the expectation is over the randomness of the
counter.222In [33], Flajolet bounded $\phi(m)$ with $O(m^{-0.98})$. Here, we
carefully follow the constants in his derivation and provide an explicit upper
bound on the the error terms, since we are interested in bounds that can be
applied for finite $m$.

Thus, if we are interested in approximating $\log m$ using the counter, then
taking our estimator to be $C_{m}-\mu$ guarantees that on average our additive
error will not be more than $10^{-5}+\phi(m)$, a property that we leverage in
our entropy estimation algorithm.

###  III-C Finite-State Bias Estimation Machine

In the bias estimation problem, we are given access to i.i.d samples drawn
from the $\mathsf{Bern}(p)$ distribution, and we wish to estimate the value of
$p$ under the expected quadratic loss (also known as mean squared error
distortion measure). The $S$-state randomized machine with the state diagram
depicted in Figure 2, was purposed by [10] and later carefully analyzed by
[4], where it was shown to asymptotically induce a
$\mathrm{Binomial}(S-1,\theta)$ stationary distribution on the memory state
space. Thus, when this machine is initiated with a $\mathop{\mathrm{Bern}}(p)$
distribution and is run for a long enough time, it outputs an estimate
$\hat{p}$ that has
$\operatorname{\mathbb{E}}(\hat{p}-p)^{2}\leq\frac{1}{S-1}$. [4] further
showed that the machine is order-optimal, by proving a lower bound of
$\operatorname{\mathbb{E}}(\hat{p}-p)^{2}\geq\Omega(1/S)$ for any finite-state
estimator.

$1$$2$$\cdots$$S-1$$S$$q$$p$$\frac{1}{S-1}\cdot q$$\frac{S-2}{S-1}\cdot
q$$\frac{S-2}{S-1}\cdot p$$\frac{1}{S-1}\cdot p$$\frac{2}{S-1}\cdot
q$$\frac{2}{S-1}\cdot p$$\frac{S-2}{S-1}\cdot q$$\frac{1}{S-1}\cdot
p$$\frac{S-2}{S-1}\cdot p$$q$$\frac{1}{S-1}\cdot q$$p$ Figure 2: Randomized
bias estimation machine with $q=1-p$

##  IV Upper Bound - Entropy Estimation Algorithm

In this section we prove Theorem 1, that is, we show the existence of an
$S$-states randomized entropy estimation machine with
$S\leq\frac{(c+1)^{4}n\cdot(\log n)^{4}}{\beta^{2}\delta}$ states, for
$\varepsilon=10^{-5}+\beta$ and $n$ large enough. The basic idea is to let
nature draw some $X$ from $p$ and use a Morris counter to approximate $-\log
p_{X}$, then, since we are looking for $H(p)=\operatorname{\mathbb{E}}(-\log
p_{X})$, use a bias estimation machine to simulate the averaging operation, by
randomly generating coin tosses with bias that is proportionate to our
estimate of $-\log p_{X}$. The bias estimation machine is incremented whenever
a count is concluded in second Morris counter that simulates a clock, thus
essentially averaging our estimates over $x$ values. For a sufficiently large
number of samples, this averaging converges (approximately) to the mean of
$-\log p_{X}$, and thus outputs an approximation to the true underlying
entropy. We divide our presentation to four parts: in the first part we
describe the algorithm; in the second part we analyze the total number of
states used by the algorithm; in the third part we assume the bias estimation
machine is fed with an infinite number of i.i.d. samples and analyze the
performance of the algorithm; and in the fourth part we relax this assumption
by studying the mixing time of the Markovian process induced by our bias
estimation machine. This allows us to prove an upper bound on the number of
samples the developed algorithm requires.

###  IV-A Description of the algorithm

  1. 1.

In each iteration of the algorithm we collect a fresh sample $X\sim p$, and
store its value, which requires $n$ states. Denote the realization of this
random variable by $x$. We proceed to estimate $\log p_{x}$ based on more
fresh samples, using Morris counters.

  2. 2.

We use two Morris counters - one that approximates a clock, and one that
approximates a count for $x$ values:

     * •

The first counter has $M=\log T+1$ states, where $T$ is the smallest integral
power of $2$ larger than $\lceil n^{c}\rceil$ for some $c>1$. The counter
stops when we arrive at state $M$, which corresponds to some _random_ time
$N$. This counter essentially approximates a clock that counts until $\lceil
n^{c}\rceil$ samples from $p$ are observed and it uses at most $c\log n+2$
states.

     * •

The second counter runs in parallel to the first one and approximates the
logarithm of the number of observed $x$ values. It stops when the first
counter arrived at state $M$ and output its value, which we denote as
$C_{N_{x}}$. This counter also has $M$ states. The randomness used for the two
counters is statistically independent. In the event that the second counter
reached state $M$ before the first one, it also stops and outputs the value
$M$.333We ignore this case in the analysis since its contribution to the
estimation error can be shown to have a negligible effect. This follows since
if $p_{x}\leq 1-n^{-(c-1)}$ the probability of this event is extremely small,
otherwise, the contribution of $p_{x}$ to the entropy is negligible.

  3. 3.

Denoting the number of observed $x$ values in the previous stage as $N_{x}$,
we define $C_{N_{x}}^{\text{centered}}\triangleq
C_{N_{x}}-\mu-\operatorname{\mathbb{E}}\log N$ to be the centralized output of
the second counter. As we argue below, this is an almost unbiased estimator
for $-\log p_{x}$.

We now use the bias estimation machine with
$S_{\text{bias}}=\frac{M^{2}}{\beta^{2}\delta}+1$ states to simulate the
expectation operation, where $\beta>0$ is such that
$\varepsilon=10^{-5}+\beta$. Specifically, each time the first Morris counter
concludes a count, we generate a $\mathop{\mathrm{Ber}}(\theta_{N_{x}})$
random variable, with
$\theta_{N_{x}}=-\frac{C_{N_{x}}^{\text{centered}}}{M}+a$, and use it as the
input to our bias estimation machine. The offset $a\triangleq
1-\frac{\operatorname{\mathbb{E}}(\log N)+\mu}{M}$ guarantees that
$\theta_{N_{x}}\in[0,1)$ with probability $1$, as
$\theta_{N_{x}}=1-\frac{C_{N_{x}}}{M}$ and $1\leq C_{N_{x}}\leq M$ as it is
the output of a Morris counter with $M$ states. Our estimator for the entropy
$\hat{H}$ is the bias estimate of the machine, after subtraction of the known
offset $a$ and multiplication by $M$, that is, $\hat{H}=M(\hat{\theta}-a)$.

###  IV-B Number of states in our machine

In each time point, our algorithm keeps the value of $x$, the state of the
Morris counter approximating the clock, the state of the Morris counter
approximating the logarithm of the $x$ counter, and the state of the bias
estimation machine. Thus, calculating the product of the number of states
needed at each step, and recalling that $M=\log T+1\leq(c+1)\log n$, the total
number of states is

$\displaystyle S=n\cdot M\cdot M\cdot S_{\text{bias}}=n\cdot
M^{2}\cdot\left(\frac{M^{2}}{\beta^{2}\delta}+1\right)\leq\frac{(c+1)^{4}n\cdot(\log
n)^{4}}{\beta^{2}\delta}.$ (12)

###  IV-C Analysis of the algorithm

We first show that the random run time of the first Morris counter $N$ is
concentrated around $\lceil n^{c}\rceil$, by upper bounding $\Pr(N<m)$ in
Lemma 1, and then using it to upper bound
$\operatorname{\mathbb{E}}\left(N^{-\alpha}\right)$ in Lemma 2. We then show
that $\operatorname{\mathbb{E}}(C_{N_{x}}^{\text{centered}})$ is close to
$H(p)$ in expectation in Lemma 3. We conclude by showing in Lemma 6 that the
output of the bias estimation machine converges to the expectation of
$\theta_{N_{X}}$, which then implies that $\hat{H}=M(\hat{\theta}-a)$ is an
$\varepsilon$-additive estimator of $H(p)$ with probability at least
$1-\delta$. Expectations are taken with respect to the randomness at different
stages of the algorithm, and we implicitly state the random variables with
respect to which the expectations are taken, apart for the case where the
expectation is taken over all the randomness of the algorithm.

######  Lemma 1.

For $m=2^{\ell},1\leq\ell\leq M-1$, it holds that

$\displaystyle\Pr(N<m)\leq e\cdot 2^{-\frac{1}{2}\cdot(M-\ell-1)^{2}}$ (13)

###### Proof.

let $\tau_{k}$ be the time it takes to move from state $k$ to state $k+1$ in
the first Morris counter and note that $\tau_{k}\sim\text{Geo}(2^{-k})$.
Clearly, $N=\sum_{k=1}^{M-1}\tau_{k}$. The moment generating function of
$\tau_{k}$ is

$\displaystyle\mathbb{M}_{\tau_{k}}(s)\triangleq\operatorname{\mathbb{E}}\left(e^{s\tau_{k}}\right)=\frac{1}{1+2^{k}(e^{-s}-1)},$
(14)

and it is defined for all $s<-\ln(1-2^{-k})$. The moment generating function
of $N$ is therefore

$\displaystyle\mathbb{M}_{N}(s)=\prod_{k=1}^{M-1}\mathbb{M}_{\tau_{k}}(s)=\prod_{k=1}^{M-1}\frac{1}{1+2^{k}(e^{-s}-1)}.$
(15)

From Chernoff bound, it holds that $\Pr(N<m)\leq
e^{-sm}\cdot\mathbb{M}_{N}(s)$ for any $s<0$. Setting $s=-\ln(1+1/m)$, we get

$\displaystyle\Pr(N<m)$
$\displaystyle\leq\left(1+\frac{1}{m}\right)^{m}\cdot\prod_{k=1}^{M-1}\frac{1}{1+\frac{2^{k}}{m}}\leq
e\cdot 2^{-\sum_{k=1}^{M-1}\log\left(1+\frac{2^{k}}{m}\right)}.$ (16)

Now let $m=2^{\ell}$ for $1\leq\ell\leq M-1$. We conclude by lower bounding
the exponent:

$\displaystyle\sum_{k=1}^{M-1}\log(1+2^{k-\ell})$
$\displaystyle=\sum_{k=0}^{\ell-1}\log(1+2^{-k})+\sum_{k=1}^{M-\ell-1}\log(1+2^{k})$
(17) $\displaystyle\geq\sum_{k=1}^{M-\ell-1}k$ (18)
$\displaystyle\geq\frac{1}{2}\cdot(M-\ell-1)^{2}.$ (19)

∎

######  Lemma 2.

For any $0<\alpha\leq 1$, we have that

$\displaystyle\operatorname{\mathbb{E}}\left(N^{-\alpha}\right)\leq(e+1)n^{-c\cdot\alpha+v_{n}(\alpha)},$
(20)

where $v_{n}(\alpha)\triangleq\sqrt{\frac{\alpha^{3}c}{\log n}}$.

###### Proof.

Appealing to Lemma 1, for any $1\leq\ell\leq M-1,m=2^{\ell}$, we have

$\displaystyle\operatorname{\mathbb{E}}(N^{-\alpha})$
$\displaystyle\leq\Pr(N<m)+m^{-\alpha}\cdot\Pr(N\geq m)$ (21)
$\displaystyle\leq e\cdot
2^{-\frac{1}{2}\cdot(M-\ell-1)^{2}}+2^{-\ell\cdot\alpha}.$ (22)

Setting $\ell=M-1-\sqrt{2\alpha\cdot(M-1)}$ and recalling that $n^{c}\leq
2^{M-1}$, we get

$\displaystyle\operatorname{\mathbb{E}}(N^{-\alpha})\leq e\cdot
2^{-\alpha(M-1)}+2^{-\alpha(M-1)\cdot\left(1-\sqrt{\frac{2\alpha}{M-1}}\right)}\leq
e\cdot n^{-c\cdot\alpha}+n^{-c\cdot\alpha\left(1-\sqrt{\frac{\alpha}{c\log
n}}\right)}.$ (23)

∎

######  Lemma 3.

Let $\psi_{c}(n)=\min\left\\{1+(e+1)n^{-(c-1)+v_{n}(1)},C\cdot
n^{-\frac{1}{2}\cdot(c-1)+v_{n}(1/2)}\right\\}$, where $C=2(e+1)\cdot 10^{8}$.
Then

$\displaystyle|\operatorname{\mathbb{E}}(C_{N_{X}}^{\text{centered}})+H(p)|\leq
10^{-5}+\psi_{c}(n).$ (24)

###### Proof.

According to Theorem 4, the value of the Morris counter after $m$ updates is
close to $\log m$ in expectation, up to some small bias. Using this fact we
show that, given $N$ and $X=x$,
$\operatorname{\mathbb{E}}(C_{N_{X}}^{\text{centered}})$ is close to the
expected logarithm of a normalized Binomial($N,p_{x}$) random variable. Taking
the expectation over $X$, this gives us $-H(p)$ plus some bias. Write

$\displaystyle\operatorname{\mathbb{E}}(C_{N_{X}}^{\text{centered}})$
$\displaystyle=\operatorname{\mathbb{E}}(\operatorname{\mathbb{E}}_{C_{N_{X}}|_{X=x,N}}(C_{N_{x}}-\mu-\operatorname{\mathbb{E}}(\log
N)))$ (25) $\displaystyle=\operatorname{\mathbb{E}}(\log
N_{X}-\operatorname{\mathbb{E}}(\log N)+g(\log N_{X})+\phi(N_{X}))$ (26)
$\displaystyle=\operatorname{\mathbb{E}}\left(\log\frac{N_{X}}{N}\right)+\operatorname{\mathbb{E}}(\gamma_{N_{X}})$
(27) $\displaystyle=\operatorname{\mathbb{E}}(\log
p_{X})+\operatorname{\mathbb{E}}\left(\log\frac{N_{X}}{N\cdot
p_{X}}\right)+\operatorname{\mathbb{E}}(\gamma_{N_{X}})$ (28)
$\displaystyle=-H(p)+\operatorname{\mathbb{E}}\left(\log\frac{N_{X}}{N\cdot
p_{X}}\right)+\operatorname{\mathbb{E}}(\gamma_{N_{X}}),$ (29)

where $\gamma_{N_{x}}=g(\log N_{x})+\phi(N_{x})$. We conclude the proof by
showing that $\operatorname{\mathbb{E}}\left(\log\frac{N_{X}}{N\cdot
p_{X}}\right)$ is small in Lemma 4, and showing that
$\operatorname{\mathbb{E}}(\gamma_{N_{X}})$ is small in Lemma 5. ∎

######  Lemma 4.

It holds that

$\displaystyle 0\leq\operatorname{\mathbb{E}}\left(\log\frac{N_{X}}{N\cdot
p_{X}}\right)\leq(e+1)n^{-(c-1)+v_{n}(1)}.$ (30)

###### Proof.

We first show that $\operatorname{\mathbb{E}}\left(\log\frac{N_{X}}{N\cdot
p_{X}}\right)\geq 0$. By Jensen’s inequality and convexity of
$t\mapsto-\log(t)$

$\displaystyle\operatorname{\mathbb{E}}\left(\log\frac{N_{X}}{N\cdot
p_{X}}\right)$
$\displaystyle=\operatorname{\mathbb{E}}_{X,N}\left[\operatorname{\mathbb{E}}_{N_{X}|N,X}\left(-\log\frac{N\cdot
p_{X}}{N_{X}}\right)\right]$ (31)
$\displaystyle\geq-\operatorname{\mathbb{E}}_{X,N}\left[\log\left(N\cdot
p_{X}\cdot\operatorname{\mathbb{E}}_{N_{X}|N,X}\left[\frac{1}{N_{X}}\right]\right)\right].$
(32)

To establish non-negativity of
$\operatorname{\mathbb{E}}\left(\log\frac{N_{X}}{N\cdot p_{X}}\right)$, it
therefore suffices to show that
$\operatorname{\mathbb{E}}_{N_{X}|N,X=x}\left[\frac{1}{N_{X}}\right]\leq\frac{1}{p_{x}\cdot
N}$. To that end, recall that given $X=x$ and $N$, we have
$N_{X}\sim\mathop{\mathrm{Bin}}(N-1,p_{x})+1$. Thus, we indeed have

$\displaystyle\operatorname{\mathbb{E}}_{N_{X}|N,X=x}\left[\frac{1}{N_{X}}\right]$
$\displaystyle=\sum_{m=0}^{N-1}\frac{1}{m+1}{N-1\choose
m}p_{x}^{m}(1-p_{x})^{N-m-1}$
$\displaystyle=\sum_{m=0}^{N-1}\frac{1}{p_{x}\cdot N}{N\choose
m+1}p_{x}^{m+1}(1-p_{x})^{N-m-1}$
$\displaystyle=\frac{1-(1-p_{x})^{N}}{p_{x}\cdot N}$
$\displaystyle\leq\frac{1}{p_{x}\cdot N}.$ (33)

To upper bound $\operatorname{\mathbb{E}}\left(\log\frac{N_{X}}{N\cdot
p_{X}}\right)$, we use Jensen’s inequality and the concavity of $t\mapsto\log
t$, to obtain

$\displaystyle\operatorname{\mathbb{E}}_{N_{X}|N,X=x}\left(\log\frac{N_{X}}{N\cdot
p_{X}}\right)$
$\displaystyle\leq\log\left(\frac{\operatorname{\mathbb{E}}_{N_{X}|N,X=x}[N_{X}]}{N\cdot
p_{x}}\right)$ (34) $\displaystyle=\log\left(1+\frac{1-p_{x}}{N\cdot
p_{x}}\right)$ (35) $\displaystyle\leq\frac{1}{N\cdot p_{x}}.$ (36)

Thus, overall,

$\displaystyle\operatorname{\mathbb{E}}\left[\log\frac{N_{X}}{N\cdot
p_{X}}\right]$
$\displaystyle\leq\operatorname{\mathbb{E}}_{N,X}\left[\frac{1}{N\cdot
p_{X}}\right]$
$\displaystyle=\operatorname{\mathbb{E}}_{X}\left[\frac{1}{p_{X}}\right]\operatorname{\mathbb{E}}_{N}\left[\frac{1}{N}\right]$
$\displaystyle=n\cdot\operatorname{\mathbb{E}}_{N}\left[\frac{1}{N}\right]$

and appealing to Lemma 2 with $\alpha=1$, we have
$\operatorname{\mathbb{E}}\left[\log\frac{N_{X}}{N\cdot
p_{X}}\right]\leq(e+1)n^{-(c-1)+v_{n}(1)}$. ∎

######  Lemma 5.

It holds that

$\displaystyle\operatorname{\mathbb{E}}(\gamma_{N_{X}})\leq
10^{-5}+\min\\{1,C\cdot n^{-\frac{1}{2}\cdot(c-1)+v_{n}(1/2)}\\}.$ (37)

###### Proof.

Note that $\operatorname{\mathbb{E}}(g(\log N_{x}))\leq 10^{-5}$ is explicit
in Theorem 4 for any $x\in[n]$, and in particular,
$\operatorname{\mathbb{E}}(g(\log N_{X}))\leq 10^{-5}$. Thus, it remains to
upper bound $\operatorname{\mathbb{E}}(\phi(N_{X}))$. It is straightforward to
verify that $\phi(x)\leq\min\left\\{1,\frac{2\cdot 10^{8}}{\sqrt{x}}\right\\}$
for all $x\geq 1$, and consequently,

$\displaystyle\operatorname{\mathbb{E}}(\phi(N_{X}))\leq\operatorname{\mathbb{E}}\left[\min\left\\{1,\frac{2\cdot
10^{8}}{\sqrt{N_{X}}}\right\\}\right]\leq\min\left\\{1,2\cdot
10^{8}\operatorname{\mathbb{E}}\left[\sqrt{\frac{1}{N_{x}}}\right]\right\\}.$
(38)

From Jensen’s inequality, concavity of $t\mapsto\sqrt{t}$, and equation (33),

$\displaystyle\operatorname{\mathbb{E}}\left[\sqrt{\frac{1}{N_{X}}}\right]$
$\displaystyle=\operatorname{\mathbb{E}}_{N,X}\left[\operatorname{\mathbb{E}}_{N_{X}|N,X}\left[\sqrt{\frac{1}{N_{X}}}\right]\right]$
(39)
$\displaystyle\leq\operatorname{\mathbb{E}}_{N,X}\left[\sqrt{\operatorname{\mathbb{E}}_{N_{X}|N,X}\left[\frac{1}{N_{X}}\right]}\right]$
(40)
$\displaystyle\leq\operatorname{\mathbb{E}}_{N,X}\left[\sqrt{\frac{1}{p_{X}\cdot
N}}\right]$
$\displaystyle=\operatorname{\mathbb{E}}_{N}\left[\sqrt{\frac{1}{N}}\right]\operatorname{\mathbb{E}}_{X}\left[\sqrt{\frac{1}{p_{X}}}\right].$
(41)

Note that, again using Jensen’s inequality and concavity of
$t\mapsto\sqrt{t}$, we have

$\displaystyle\operatorname{\mathbb{E}}_{X}\left[\sqrt{\frac{1}{p_{X}}}\right]=\sum_{x=1}^{n}\sqrt{p_{x}}\leq
n\sqrt{\frac{1}{n}\sum_{x=1}^{n}p_{x}}=\sqrt{n}.$ (42)

Appealing to Lemma 2 with $\alpha=0.5$, we have

$\displaystyle\operatorname{\mathbb{E}}(N^{-0.5})\leq(e+1)n^{-\frac{c}{2}+v_{n}(1/2)}.$
(43)

Thus, substituting (42) and (43) into (41) and then into (38), and recalling
that $C=2(e+1)10^{8}$, we obtain the claimed result. ∎

######  Lemma 6.

Define the estimator $\hat{H}=M(\hat{\theta}-a)$, where $\hat{\theta}$ is the
output of the bias estimation machine with
$S_{\text{bias}}=\frac{M^{2}}{\beta^{2}\delta}+1$ states, to which we feed a
$\mathsf{Bern}(\theta_{N_{X}})$ sample at each iteration of our approximate
counter. Then,

$\displaystyle\Pr(|\hat{H}-(H(p)+b)|>\beta)\leq\delta,$ (44)

where $|b|\leq 10^{-5}+\psi_{c}(n)$.

###### Proof.

Averaging over $X$, we have that the overall bias of the binary random
variable we feed to the bias estimation machine is

$\displaystyle\theta\triangleq\operatorname{\mathbb{E}}(\theta_{N_{X}})=\operatorname{\mathbb{E}}\left(-\frac{C_{N_{X}}^{\text{centered}}}{M}+a\right)=\frac{H(p)+b}{M}+a,$
(45)

where $|b|\leq 10^{-5}+\psi_{c}(n)$ is an unknown offset that arises from
Lemma 3. Recalling that
$\operatorname{\mathbb{E}}(\hat{\theta}-\theta)^{2}\leq\frac{1}{S_{\text{bias}}-1}$,

$\displaystyle\operatorname{\mathbb{E}}(\hat{H}-(H(p)+b))^{2}=M^{2}\cdot\operatorname{\mathbb{E}}(\hat{\theta}-\theta)^{2}\leq\beta^{2}\delta,$
(46)

thus we have from Chebyshev’s inequality,

$\displaystyle\Pr(|\hat{H}-(H(p)+b)|>\beta)\leq\frac{\operatorname{\mathbb{E}}(\hat{H}-(H(p)+b))^{2}}{\beta^{2}}\leq\delta.$
(47)

Note that our upper bound on the additive error in estimation of $H(p)$ is
$\beta+|b|\leq\beta+10^{-5}+\psi_{c}(n)$, which limits our results to
estimation error $\varepsilon>10^{-5}+\psi_{c}(n)$. ∎

###  IV-D Sample complexity of our algorithm

In our algorithm, the number of observed samples is unbounded. In practice we
only need to observe $O(t_{\mathsf{mix}}(p))$ samples, where
$t_{\mathsf{mix}}(p)$ is the mixing time of our machine whenever the input is
$\mathop{\mathrm{Bern}}(p)$ samples, i.e., the minimal time it takes for the
total variation distance between the marginal distribution and the limiting
distribution to be small. In our case the bias estimation machine is only
incremented after an iteration of the first Morris counter is completed, and
the run time of each iteration is a random variable that is only bounded in
expectation. However, we note that this in fact implies the existence of a
good algorithm that has a bounded sample complexity; namely, running our
entropy estimation algorithm on $L$ samples is equivalent to running the bias
estimation machine from [10] on a random number of samples $k=k(L)$ times with
$p=\theta=\operatorname{\mathbb{E}}(\theta_{N_{X}})$. The randomness in $k(L)$
follows since the runtime $N_{i}$ of each iteration of the Morris counter
procedure is a random variable. Below, we use Chernoff’s bound to upper bound
the probability that $k(L)$ is small. This event is considered as an error in
our analysis. We now upper bound the mixing time of the bias estimation
machine from [10]. Whenever $k(L)$ is greater than this mixing time, the error
of our algorithms with $L$ samples is close to its asymptotic value.

To upper bound the mixing time, we use the coupling method. Recall that the
transition matrix $P$ of a Markov process $\\{X_{t}\\}_{t=0}^{\infty}$
supported on $\mathcal{X}$ is a matrix whose elements are
$\Pr(X_{t+1}=x^{\prime}|X_{t}=x)=P(x,x^{\prime})$, for any
$x,x^{\prime}\in\mathcal{X}\times\mathcal{X}$. We define a coupling of Markov
chains with transition matrix $P$ to be a process
$\\{X_{t},Y_{t}\\}_{t=0}^{\infty}$ with the property that both
$\\{X_{t}\\}_{t=0}^{\infty}$ and $\\{Y_{t}\\}_{t=0}^{\infty}$ are Markov
chains with transition matrix $P$, although the two chains may be correlated
and have different initial distributions. Given a Markov chain on
$\mathcal{X}$ with transition matrix $P$, a Markovian coupling of two
$P$-chains is a Markov chain $\\{X_{t},Y_{t}\\}_{t=0}^{\infty}$ with state
space $\mathcal{X}\times\mathcal{X}$, which satisfies, for all
$x,y,x^{\prime},y^{\prime}$,

$\displaystyle\Pr(X_{t+1}=x^{\prime}|X_{t}=x,Y_{t}=y)$
$\displaystyle=P(x,x^{\prime})$ (48)
$\displaystyle\Pr(Y_{t+1}=y^{\prime}|X_{t}=x,Y_{t}=y)$
$\displaystyle=P(y,y^{\prime}).$ (49)

Let $P^{t}(x_{0})$ be the marginal distribution of the chain at time $t$ when
initiated at $x_{0}$, and let $\pi$ be the unique stationary distribution.
Define the $\delta$-mixing time as

$\displaystyle
t_{\delta}^{*}\triangleq\min\\{t:d_{\mathsf{TV}}(P^{t}(x_{0}),\pi)\leq\delta\\},$
(50)

and $t_{\mathsf{mix}}\triangleq t_{1/4}^{*}$. We now show that the bias
estimation machine with $S$ states mixes in $\Theta(S\log S)$ time, uniformly
for all $p\in(0,1]$.

######  Theorem 5.

Let $t_{\mathsf{mix}}(p)$ denote the mixing time of the bias estimation
machine with $S$ states when the input is i.i.d $\mathsf{Bern}(p)$, and define
the worst-case mixing time to be $t^{*}=\max_{p\in(0,1]}t_{\mathsf{mix}}(p)$.
Then

$\displaystyle\ln(2)\cdot(S-1)\log(S-1)\leq t^{*}\leq 4S\log S.$ (51)

###### Proof.

The transition probabilities of the bias estimation machine of Figure 2 are
given, for $1<k<S$, as

$\displaystyle X_{t+1}|_{X_{t}=k}=\begin{cases}k+1,&\textit{w.p.
}\frac{S-k}{S-1}\cdot p,\\\ k,&\textit{w.p. }\frac{k-1}{S-1}\cdot
p+\frac{S-k}{S-1}\cdot q,\\\ k-1,&\textit{w.p. }\frac{k-1}{S-1}\cdot
q,\end{cases}$ (52)

and for the extreme states $\\{1,S\\}$ as

$\displaystyle X_{t+1}|_{X_{t}=1}=\begin{cases}2,&\textit{w.p. }p,\\\
1,&\textit{w.p. }q,\end{cases}\hskip
11.38109ptX_{t+1}|_{X_{t}=S}=\begin{cases}S,&\textit{w.p. }p,\\\
S-1,&\textit{w.p. }q.\end{cases}$ (53)

We construct a Markovian coupling in which the two chains stay together at all
times after their first simultaneous visit to a single state, that is

$\displaystyle\text{if }X_{s}=Y_{s}\text{ then }X_{t}=Y_{t}\text{ for all
}t\geq s.$ (54)

The following lemma, due to [35](Theorem 5.4), will give us an upper bound on
the mixing time using this coupling.

######  Lemma 7.

Let $\\{(X_{t},Y_{t})\\}$ be a Markovian coupling satisfying (54), for which
$X_{0}=x_{0}$ and $Y_{0}=y_{0}$. Let $\tau_{\mathsf{couple}}$ be the
coalescence time of the chains, that is,

$\displaystyle\tau_{\mathsf{couple}}\triangleq\min\\{t:X_{t}=Y_{t}\\}.$ (55)

Then

$\displaystyle t_{\mathsf{mix}}\leq
4\max_{x_{0},y_{0}\in\mathcal{X}}\operatorname{\mathbb{E}}(\tau_{\mathsf{couple}}).$
(56)

Assume w.l.o.g. that $x_{0}<y_{0}$ and let $U_{t}$ be an i.i.d sequence drawn
according to the $\mathop{\mathrm{Unif}}(0,1)$ distribution. We construct a
coupling on $(X_{t},Y_{t})$ such that, at each time point
$t<\tau_{\mathsf{couple}}$, $X_{t}$ and $Y_{t}$ are incremented in the
following manner:

$\displaystyle X_{t+1}|_{X_{t}=i}=\begin{cases}i+1,&\textit{if
}U_{t}\leq\frac{S-i}{S-1}\cdot p,\\\ i,&\textit{if }\frac{S-i}{S-1}\cdot p\leq
U_{t}\leq 1-\frac{i-1}{S-1}\cdot q,\\\ i-1,&\textit{if }1-\frac{i-1}{S-1}\cdot
q\leq U_{t}\leq 1,\end{cases}$ (57)

and

$\displaystyle Y_{t+1}|_{Y_{t}=j}=\begin{cases}j+1,&\textit{if
}U_{t}\leq\frac{S-j}{S-1}\cdot p,\\\ j,&\textit{if }\frac{S-j}{S-1}\cdot p\leq
U_{t}\leq 1-\frac{j-1}{S-1}\cdot q,\\\ j-1,&\textit{if }1-\frac{j-1}{S-1}\cdot
q\leq U_{t}\leq 1.\end{cases}$ (58)

One can validate that the transition probabilities are the correct ones, for
example

$\displaystyle\Pr(X_{t+1}=i|X_{t}=i)$
$\displaystyle=\Pr\left(\frac{S-i}{S-1}\cdot p\leq U_{t}\leq
1-\frac{i-1}{S-1}\cdot q\right)$ (59) $\displaystyle=1-\frac{i-1}{S-1}\cdot
q-\frac{S-i}{S-1}\cdot p$ (60) $\displaystyle=\frac{i-1}{S-1}\cdot
p+\frac{S-i}{S-1}\cdot q,$ (61)

and, similarly, $\Pr(Y_{t+1}=j|Y_{t}=j)=\frac{j-1}{S-1}\cdot
p+\frac{S-j}{S-1}\cdot q$. The other transition probabilities are easily
calculated. Note that $i<j$ implies $\frac{S-j}{S-1}<\frac{S-i}{S-1}$, thus
$Y_{t}$ cannot move right unless $X_{t}$ moves right and $X_{t}$ cannot move
left unless $Y_{t}$ moves left. Moreover, since $x_{0}<y_{0}$, we have $i<j$
for all $t<\tau_{\mathsf{couple}}$. This follows from construction, since
$\frac{S-i}{S-1}\cdot p$ is always smaller than $1-\frac{j-1}{S-1}\cdot q$,
implying that $X_{t}$ cannot jump over $Y_{t}$ when they are one-state apart.
Thus, the distance process $D_{t}\triangleq Y_{t}-X_{t}$, is a non-increasing
function of $t$, with initial state $D_{0}=y_{0}-x_{0}$, that can only
decrease by one unit at a time or stay unchanged. We have

$\displaystyle\Pr(D_{t+1}=D_{t}-1)$
$\displaystyle=\Pr(X_{t+1}=X_{t}+1,Y_{t=1}=Y_{t})+\Pr(Y_{t+1}=Y_{t}-1,X_{t=1}=X_{t})$
(62) $\displaystyle=\Pr\left(\frac{S-Y_{t}}{S-1}\cdot p\leq
U_{t}\leq\frac{S-X_{t}}{S-1}\cdot p\right)+\Pr\left(1-\frac{Y_{t}-1}{S-1}\cdot
q\leq U_{t}\leq 1-\frac{X_{t}-1}{S-1}\cdot q\right)$ (63)
$\displaystyle=\frac{Y_{t}-X_{t}}{S-1}\cdot p+\frac{Y_{t}-X_{t}}{S-1}\cdot q$
(64) $\displaystyle=\frac{D_{t}}{S-1}.$ (65)

The expected coupling time is now the expected time it takes for $D_{t}$ to
decrease from $D_{0}$ to $D_{t}$, thus in order to maximize it under the given
coupling, we need to maximize $D_{0}$, which corresponds to setting
$X_{0}=1,y_{0}=S$. For $D_{0}=S-1$, consider the process $M_{t}\triangleq
D_{0}-D_{t}$, which is a non-decreasing function of $t$ that goes from $0$ to
$S-1$ and has
$\Pr(M_{t+1}=M_{t}+1)=\Pr(D_{t+1}=D_{t}-1)=\frac{D_{t}}{S-1}=1-\frac{M_{t}}{S-1}$.
Then this process is no other than the Coupon Collector process with $S-1$
coupons, and the expected coupling time in our chain in identical to the
expected number of coupons collected until the set contains all $S-1$ types,
which according to [35], Proposition 2.3., is

$\displaystyle\operatorname{\mathbb{E}}(\tau_{\mathsf{couple}})=(S-1)\cdot\sum_{k=1}^{S-1}\frac{1}{k}\leq(S-1)(\ln(S-1)+1)\leq
S\log(S).$ (66)

To show that this upper bound is indeed tight, consider the case of $p=1$. In
this case, the chain of Figure 2 is simply the Coupon Collector process with
$S-1$ coupons, thus, letting $\tau$ be the (random) time it takes to collect
all coupons, we have

$\displaystyle\operatorname{\mathbb{E}}(\tau)=(S-1)\cdot\sum_{k=1}^{S-1}\frac{1}{k}\geq\ln(2)\cdot(S-1)\log(S-1).$
(67)

∎

From [35], Eq. (4.34), we have that the $\delta$-mixing time $t_{\delta}^{*}$
can be upper bounded in terms on the mixing time by

$\displaystyle
t_{\delta}^{*}\leq\left\lceil\log\left(\frac{1}{\delta}\right)\right\rceil\cdot
t_{\mathsf{mix}}.$ (68)

Let

$\displaystyle k\triangleq 8\log\left(\frac{1}{\delta}\right)\frac{(\log
4n^{c})^{2}}{\beta^{2}\delta}\log\left(\frac{(\log
4n^{c})^{2}}{\beta^{2}\delta}\right),$ (69)

and note that from equation (68), Theorem 5, and substituting
$S_{\text{bias}}=\frac{M^{2}}{\beta^{2}\delta}+1$, we have that the
$\delta$-mixing time of the bias estimation machine is at most $k$. Let
$N_{1},N_{2},\ldots,N_{k}$ be the first $k$ i.i.d. Morris counter running
times, which are all distributed as $N$ in the analysis from Section IV. Lemma
8 uses the concentration of $N$ to show that, with probability $1-\delta$, the
number of samples we need to observe until the bias machine mixes is not
large.

######  Lemma 8.

Let $m=4n^{c}\cdot\ln\left(\frac{5k}{\delta}\right)$. Then

$\displaystyle\Pr\left(\sum_{i=1}^{k}N_{i}>k\cdot m\right)\leq\delta.$ (70)

###### Proof.

Recall that for all $i\in\mathbb{N}$, we have

$\displaystyle\mathbb{M}_{N_{i}}(s)=\prod_{j=1}^{M-1}\frac{1}{1+2^{j}(e^{-s}-1)},$
(71)

which is defined for all $s<-\ln(1-2^{-(M-1)})=-\ln(1-1/T)$. As $T\leq
2n^{c}$, $\mathbb{M}_{N_{i}}(t)$ is well defined for $s=-\ln(1-1/4n^{c})$,
thus we have from Chernoff bound,

$\displaystyle\Pr(N_{i}>m)$ $\displaystyle\leq
e^{-sm}\cdot\mathbb{M}_{N_{i}}(s)$ (72)
$\displaystyle=\left(1-\frac{1}{4n^{c}}\right)^{m}\cdot\prod_{j=1}^{M-1}\frac{1}{1-\frac{2^{j}}{4n^{c}}}$
(73)
$\displaystyle\leq\left(1-\frac{1}{4n^{c}}\right)^{m}\cdot\prod_{j=1}^{M-1}\frac{1}{1-2^{-j}}$
(74) $\displaystyle\leq
5\exp\left\\{-\frac{m}{4n^{c}}\right\\}=\frac{\delta}{k}$ (75)

where in (74) we used the fact that
$\frac{2^{j}}{4n^{c}}\leq\frac{2^{j}}{2T}=2^{j-M}$, and in (75) we used the
bound $\prod_{j=1}^{M}(1-2^{-j})\geq\frac{1}{4}+\frac{1}{2^{M+1}}$, which can
be proved via induction. Consequently, the probability that at least one of
the random variables $N_{1},\ldots,N_{k}$ is greater than $m$ is at most
$1-\left(1-\frac{\delta}{k}\right)^{k}\leq\delta$, which implies the statement
of the lemma. ∎

We conclude with the following lemma, which connects Theorem 5 and Lemma 8 to
show that our entropy estimator performs well even if the number of input
samples is $\tilde{O}(n^{c}/\delta)$.

######  Lemma 9.

Let the algorithm of Theorem 1 run on $L=k\cdot m$ samples, and output the
estimate $\hat{H}_{M_{L}}$. Then with probability at least $1-3\delta$,
$\hat{H}_{M_{L}}$ is within $\varepsilon$-additive error from $H(p)$.

###### Proof.

Lemma 8 implies that, with probability at least $1-\delta$, after observing
$k\cdot m$ samples, the bias estimation machine has been incremented at least
$k$ times. Recall that, by definition, after $t\geq t_{\delta}^{*}$ increments
of the bias estimation machine, we have that
$d_{\mathsf{TV}}(P^{t}(x_{0}),\pi)\leq\delta$, and that our $S$-states entropy
estimator has $\sum_{i\in\hat{H}_{\bar{\varepsilon}}}\pi_{i}<\delta$, where
$\hat{H}_{\bar{\varepsilon}}=\\{i\in[S]:|\hat{H}_{i}-H(p)|>\varepsilon\\}$.
Thus, from a union bound, a fraction of $2\delta$ of the distribution
$P^{t}(x_{0})$ (at most) is supported on $\hat{H}_{\bar{\varepsilon}}$.
Putting it all together, we have that a finite-time algorithm that outputs an
estimate $\hat{H}(M_{L})$ after

$\displaystyle L=k\cdot
m=\Omega\left(\frac{n^{c}\cdot\mathop{\mathrm{poly}}(\log
n)}{\delta}\cdot\mathop{\mathrm{poly}}(\log(1/\delta))\right)$ (76)

will be $\varepsilon$-far from the correct entropy with probability at most
$3\delta$. ∎

##  V Lower Bounds

In this section we prove Theorem 2. The $\Omega(n)$ bound is proved via
reduction to uniformity testing. For the $\frac{\log n}{2\varepsilon}$ bound,
we use a simple quantization argument. Assume that $S<\frac{\log
n}{2\varepsilon}$. Then there must be two consecutive estimate values
$\hat{H}_{1},\hat{H}_{2}\in[0,\log n]$ such that
$\hat{H}_{2}-\hat{H}_{1}>2\varepsilon$. This implies that
$H=(\hat{H}_{1}+\hat{H}_{2})/2$ has
$|H-\hat{H}_{1}|=|H-\hat{H}_{2}|>\varepsilon$. Thus, for this value of the
entropy, we have $\Pr(|\hat{H}(M_{t})-H|>\varepsilon)=1$ for all
$t\in\mathbb{N}$.

###  V-A Proof of the $(1-2\sqrt{\varepsilon\ln 2})n$ bound

An ($\varepsilon,\delta$) uniformity tester can distinguish (with probability
$0<\delta<1/2$) between the case where $p$ is uniform and the case where $p$
is $\varepsilon$-far from uniform in total variation. Assume we have an
($\varepsilon,\delta$) entropy estimator. Then we can obtain an
($\tilde{\varepsilon}=\sqrt{\varepsilon\ln 2},\delta$) uniformity tester using
the following protocol: the tester declares that $p$ is uniform if
$\hat{H}>\log n-\varepsilon$, and that $p$ is $\tilde{\varepsilon}$-far from
uniform if $\hat{H}<\log n-\varepsilon$. We now argue that this is indeed an
($\tilde{\varepsilon},\delta$) uniformity tester, in which case the
$(1-2\tilde{\varepsilon})n$ lower bound will follow immediately from the lower
bound on uniformity testing of [7]. If $p=u$, where $u$ is the uniform
distribution over $[n]$, then $H(p)=\log n$ and $\hat{H}>\log n-\varepsilon$
with probability at least $1-\delta$, so our tester will correctly declare
“uniform” with probability at least $1-\delta$. If
$d_{\mathsf{TV}}(p,u)>\sqrt{\varepsilon\ln 2}$, then from Pinsker’s inequality
( [36], Lemma $11.6.1$),

$\displaystyle 2\varepsilon<\frac{2}{\ln 2}d_{\mathsf{TV}}(p,u)^{2}\leq
D(p||u)=\log n-H(p),$ (77)

which implies $H(p)<\log n-2\varepsilon$ and $\hat{H}<\log n-\varepsilon$ with
probability at least $1-\delta$. Thus, our tester will correctly declare “far
from uniform” with probability at least $1-\delta$.

##  VI Memory Complexity of Mutual Information Estimation

We extend our results to the problem of mutual information estimation. The
upper bound follows by a slight tweaking of our entropy estimation machine,
and the lower bound follows by noting the close relation between mutual
information and joint entropy, and lower bounding the memory complexity of the
latter.

###  VI-A Sketch of Upper Bound achieving algorithm

  1. 1.

Let nature randomly draw some $(X,Y)=(x,y)\in[n]\times[m]$ according to
$p_{XY}$, and keep that value of $(x,y)$ for the following stages. This
requires $n\cdot m$ states.

  2. 2.

We use four Morris counters - one that approximates a clock, one that
approximates a count for $x$ values, one that approximates a count for $y$
values, and one that approximates a count for the pair $(x,y)$:

     * •

The first counter has $M=\log T+1$ states, where $T$ is the next power of $2$
after $\lceil(n\cdot m)^{c}\rceil$. The random stopping time of the counter is
$N$. This counter approximates a clock that counts until $\lceil(n\cdot
m)^{c}\rceil$ samples from the distribution are observed. This takes at most
$c\log(n\cdot m)+2$ states.

     * •

The second, third and fourth counters run in parallel to the first one and
approximate a counter for $x$, a counter for $y$, and a counter for the pair
$(x,y)$, and we denote their outputs as $C_{N_{x}}$, $C_{N_{y}}$ and
$C_{N_{xy}}$, respectively. Each of these counters contains $M$ states.

  3. 3.

Let $C_{\text{MI}}=C_{N_{x}}+C_{N_{y}}-C_{N_{xy}}$, and define
$C_{\text{MI}}^{\text{centered}}=C_{\text{MI}}-\mu-\operatorname{\mathbb{E}}\log
N$. For the reasons outlined in Section IV, the expectation of
$C_{\text{MI}}^{\text{centered}}$ is equal to $-\log p_{x}-\log p_{y}+\log
p_{xy}$ plus some bias

$\displaystyle|b_{\text{MI}}|\leq 3\cdot
10^{-5}+O\left(n^{-\frac{1}{2}\cdot(c-1)}\vee
m^{-\frac{1}{2}\cdot(c-1)}\right).$ (78)

  4. 4.

We simulate the expectation operation using a bias estimation machine with
$S_{\text{bias}}=\frac{9M^{2}}{\beta^{2}\delta}+1$ states. Let
$\theta_{N_{xy}}=-\frac{C_{\text{MI}}^{\text{centered}}}{3M}+a$, where
$a\triangleq\frac{2M-\operatorname{\mathbb{E}}(\log N)-\mu}{3M}$ is a known
offset that we add to guarantee that $\theta_{N_{xy}}\in[0,1)$ with
probability $1$. Averaging over $(X,Y)=(x,y)$, our bias is
$\theta_{\text{MI}}=\operatorname{\mathbb{E}}(\theta_{N_{XY}})=\frac{I(X;Y)+b_{\text{MI}}}{3M}+a$.
After subtraction of $a$ and multiplication by $3M$, that is, setting
$\hat{I}=3M(\hat{\theta}_{\text{MI}}-a)$ we get an (almost) unbiased estimator
for $I(X;Y)$. As we have

$\displaystyle\operatorname{\mathbb{E}}(\hat{I}-(I(X;Y)+b_{\text{MI}}))^{2}=9M^{2}\cdot\operatorname{\mathbb{E}}(\hat{\theta}_{\text{MI}}-\theta_{\text{MI}})^{2}\leq\beta^{2}\delta,$
(79)

Chebyshev’s inequality implies that
$\Pr(|\hat{I}-(I(X;Y)+b_{\text{MI}})|>\beta)\leq\delta$. The total number of
states is thus the product of the number of states at each step,

$\displaystyle S=nm\cdot
M^{4}\cdot\left(\frac{9M^{2}}{\beta^{2}\delta}+1\right)\leq\frac{9nm\cdot(c+1)^{6}(\log
nm)^{6}}{\beta^{2}\delta},$ (80)

for $\beta>0$, $\varepsilon=3\cdot
10^{-5}+\beta+O\left(n^{-\frac{1}{2}\cdot(c-1)}\vee
m^{-\frac{1}{2}\cdot(c-1)}\right)$.

###  VI-B Lower Bound

For simplicity of proof, let $\varepsilon,\delta\geq\frac{1}{100}$, and recall
that $\varepsilon<\frac{1}{12\ln 2}$. Our lower bound from Theorem 2 implies
that for joint entropy estimation of $H(X,Y)$ where $(X,Y)\in[n]\times[m]$,
the memory complexity is $\Omega(n\cdot m)$. Assume that we have a mutual
information estimation machine that returns an estimate of $I(X;Y)$ with
additive error at most $\varepsilon$ with probability at least $1-\delta$
using $S_{\text{MI}}^{*}(n,m,\varepsilon,\delta)$ states. We show below an
algorithm that uses this machine as a black box and estimates
$H(X,Y)=H(X)+H(Y)-I(X;Y)$ with additive error of at most $3\varepsilon$ with
probability at least $1-3\delta$ using $S_{\text{MI}}^{*}\cdot
O(\log^{3}n\cdot\log^{3}m)$ states. Since estimation of $H(X,Y)$ requires
$S^{*}(n\cdot m,3\varepsilon,3\delta)=\Omega(n\cdot m)$, this must imply that

$\displaystyle
S_{\text{MI}}^{*}(n,m,\varepsilon,\delta)>\Omega\left(\frac{n\cdot
m}{\log^{3}n\cdot\log^{3}m}\right).$ (81)

We now describe such an algorithm. The algorithm has $3$ modes. It starts in
mode $1$, in which $H(X)$ is estimated. It then moves to mode $2$, in which
$H(Y)$ is estimated, and finally it moves to mode $3$ in which $I(X;Y)$ is
estimated. The estimation of these $3$ quantities is done using

$\displaystyle\tilde{S}=\max\\{S^{*}(n,\varepsilon,\delta),S^{*}(m,\varepsilon,\delta),S_{\text{MI}}^{*}(n,m,\varepsilon,\delta)\\}$
(82)

states. Those states are “reused” once the algorithm switches its mode of
operation. The current mode is stored using $S_{1}=3$ states.

In mode $1$, the algorithm estimates $H(X)$ using the Morris-counter based
machine we introduced in Section IV, which uses $S^{*}(n,\varepsilon,\delta)$
states. After a long enough time, the estimate will be accurate enough, and we
will then stop the machine and store that value. In order to decide if enough
time has passed, we must ensure that the bias estimation machine with
$S_{\text{Bias}}=O(\log^{2}n)$ number of states, to which we feed
$\mathrm{Ber}(\theta_{N_{X}})$ samples, is sufficiently mixed. From Theorem 5,
we have that the mixing time of the bias estimation machine is at most
$4S_{\text{Bias}}\log S_{\text{Bias}}\leq O(\log^{3}n)$. Thus, we will let the
machine run for $\log^{k}n$ samples of independent
$\mathrm{Ber}(\theta_{N_{X}})$ random variables for $k>>3$, and then stop it,
which would guarantee it is sufficiently mixed. To determine when to stop the
machine without using a memory consuming clock, we will use another Morris
counter with $S_{2}=O(\log\log^{k}n)=O(\log\log n)$ states. We will also store
the state of the bias estimation machine, which corresponds to our estimate
$\hat{H}(X)$ of $H(X)$, using $S_{3}=S_{\text{Bias}}=O(\log^{2}n)$ states. At
this point, the algorithm switches to mode $2$, and estimates $H(Y)$ with the
algorithm from Section IV, which uses $S^{*}(m,\varepsilon,\delta)$ states. As
in mode $1$, we use a Morris counter of $S_{4}=O(\log\log m)$ states to
determine when the machine is sufficiently mixed and can be stopped, and store
the state of the bias estimation machine, which corresponds to the estimate
$\hat{H}(Y)$ of $H(Y)$, using $S_{5}=O(\log^{2}m)$ states. The process then
moves to state $3$ where $I(X;Y)$ is estimated using the black-box machine
with $S_{\text{MI}}^{*}(n,m,\varepsilon,\delta)$ states. From this time
onward, the machine estimates $H(X,Y)$ as
$\hat{H}(X)+\hat{H}(Y)-\hat{I}(X;Y)$, where $\hat{I}(X;Y)$ is the current
estimate of the black box machine. All in all, this algorithm produces a
$(3\varepsilon,3\delta)$ (recall that we assumed $\delta,\varepsilon\geq
1/100$) estimate of $H(X,Y)$ using

$\displaystyle S\leq\tilde{S}\prod_{i=1}^{5}S_{i}=\tilde{S}\cdot
O(\log^{3}n\cdot\log^{3}m),$ (83)

which implies that

$\displaystyle\tilde{S}=\Omega\left(\frac{S}{\log^{3}n\log^{3}m}\right)=\Omega\left(\frac{S^{*}(n,m,3\varepsilon,3\delta)}{\log^{3}n\log^{3}m}\right)=\Omega\left(\frac{n\cdot
m}{\log^{3}n\log^{3}m}\right).$ (84)

Finally, since Theorem 1 states that
$S^{*}(n,\varepsilon,\delta)=O(n\cdot\log^{4}n)$ and
$S^{*}(m,\varepsilon,\delta)=O(m\cdot\log^{4}m)$, and we assumed that
$\frac{n}{\log^{3}n}=\Omega(\log^{7}m)$ and
$\frac{m}{\log^{3}m}=\Omega(\log^{7}n)$, we must therefore have that

$\displaystyle
S_{\text{MI}}^{*}(n,m,\varepsilon,\delta)=\Omega\left(\frac{n\cdot
m}{\log^{3}n\cdot\log^{3}m}\right).$ (85)

## Acknowledgements

This work was supported by the ISF under Grants 1641/21 and 1766/22.

## References

  * [1] J. Acharya, S. Bhadane, P. Indyk, and Z. Sun, “Estimating entropy of distributions in constant space,” arXiv preprint arXiv:1911.07976, 2019\.
  * [2] M. Aliakbarpour, A. McGregor, J. Nelson, and E. Waingarten, “Estimation of entropy in constant space with improved sample complexity,” arXiv preprint arXiv:2205.09804, 2022.
  * [3] R. Morris, “Counting large numbers of events in small registers,” Communications of the ACM, vol. 21, no. 10, pp. 840–842, 1978.
  * [4] F. Leighton and R. Rivest, “Estimating a probability using finite memory,” IEEE Transactions on Information Theory, vol. 32, no. 6, pp. 733–742, 1986\.
  * [5] T. Berg, O. Ordentlich, and O. Shayevitz, “Deterministic finite-memory bias estimation,” in Conference on Learning Theory, pp. 566–585, PMLR, 2021\.
  * [6] A. Chakrabarti, K. Do Ba, and S. Muthukrishnan, “Estimating entropy and entropy norm on data streams,” Internet Mathematics, vol. 3, no. 1, pp. 63–78, 2006.
  * [7] T. Berg, O. Ordentlich, and O. Shayevitz, “On the memory complexity of uniformity testing,” in Conference on Learning Theory, pp. 3506–3523, PMLR, 2022.
  * [8] T. M. Cover et al., “Hypothesis testing with finite statistics,” The Annals of Mathematical Statistics, vol. 40, no. 3, pp. 828–835, 1969.
  * [9] M. E. Hellman and T. M. Cover, “Learning with finite memory,” The Annals of Mathematical Statistics, pp. 765–782, 1970.
  * [10] F. J. Samaniego, “Estimating a binomial parameter with finite memory,” IEEE Transactions on Information Theory, vol. 19, no. 5, pp. 636–643, 1973.
  * [11] J. Steinhardt and J. Duchi, “Minimax rates for memory-bounded sparse linear regression,” in Conference on Learning Theory, pp. 1564–1587, 2015.
  * [12] J. Steinhardt, G. Valiant, and S. Wager, “Memory, communication, and statistical queries,” in Conference on Learning Theory, pp. 1490–1516, 2016.
  * [13] R. Raz, “Fast learning requires good memory: A time-space lower bound for parity learning,” Journal of the ACM (JACM), vol. 66, no. 1, p. 3, 2018\.
  * [14] Y. Dagan and O. Shamir, “Detecting correlations with little memory and communication,” in Conference On Learning Theory, pp. 1145–1198, 2018\.
  * [15] A. Jain and H. Tyagi, “Effective memory shrinkage in estimation,” in 2018 IEEE International Symposium on Information Theory (ISIT), pp. 1071–1075, IEEE, 2018.
  * [16] Y. Dagan, G. Kur, and O. Shamir, “Space lower bounds for linear prediction in the streaming model,” in Conference on Learning Theory, pp. 929–954, 2019\.
  * [17] V. Sharan, A. Sidford, and G. Valiant, “Memory-sample tradeoffs for linear regression with small error,” in Symposium on Theory of Computing (STOC), 2019.
  * [18] S. Garg, P. K. Kothari, P. Liu, and R. Raz, “Memory-sample lower bounds for learning parity with noise,” in 24th International Conference on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2021 and 25th International Conference on Randomization and Computation, RANDOM 2021, p. 60, Schloss Dagstuhl-Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2021.
  * [19] A. Pensia, V. Jog, and P.-L. Loh, “Communication-constrained hypothesis testing: Optimality, robustness, and reverse data processing inequalities,” arXiv preprint arXiv:2206.02765, 2022.
  * [20] G. P. Basharin, “On a statistical estimate for the entropy of a sequence of independent random variables,” Theory of Probability & Its Applications, vol. 4, no. 3, pp. 333–336, 1959.
  * [21] A. Antos and I. Kontoyiannis, “Convergence properties of functional estimates for discrete distributions,” Random Structures & Algorithms, vol. 19, no. 3-4, pp. 163–193, 2001.
  * [22] L. Paninski, “Estimation of entropy and mutual information,” Neural computation, vol. 15, no. 6, pp. 1191–1253, 2003.
  * [23] L. Paninski, “Estimating entropy on m bins given fewer than m samples,” IEEE Transactions on Information Theory, vol. 50, no. 9, pp. 2200–2203, 2004\.
  * [24] G. Valiant and P. Valiant, “A clt and tight lower bounds for estimating entropy.,” in Electron. Colloquium Comput. Complex., vol. 17, p. 179, 2010\.
  * [25] G. Valiant and P. Valiant, “Estimating the unseen: an n/log (n)-sample estimator for entropy and support size, shown optimal via new clts,” in Proceedings of the forty-third annual ACM symposium on Theory of computing, pp. 685–694, 2011.
  * [26] P. Valiant and G. Valiant, “Estimating the unseen: Improved estimators for entropy and other properties.,” in NIPS, pp. 2157–2165, 2013.
  * [27] G. Valiant and P. Valiant, “The power of linear estimators,” in 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, pp. 403–412, IEEE, 2011.
  * [28] J. Jiao, K. Venkat, Y. Han, and T. Weissman, “Minimax estimation of functionals of discrete distributions,” IEEE Transactions on Information Theory, vol. 61, no. 5, pp. 2835–2885, 2015.
  * [29] Y. Wu and P. Yang, “Minimax rates of entropy estimation on large alphabets via best polynomial approximation,” IEEE Transactions on Information Theory, vol. 62, no. 6, pp. 3702–3720, 2016.
  * [30] A. Lall, V. Sekar, M. Ogihara, J. Xu, and H. Zhang, “Data streaming algorithms for estimating entropy of network traffic,” ACM SIGMETRICS Performance Evaluation Review, vol. 34, no. 1, pp. 145–156, 2006.
  * [31] S. Guha, A. McGregor, and S. Venkatasubramanian, “Sublinear estimation of entropy and information distances,” ACM Transactions on Algorithms (TALG), vol. 5, no. 4, pp. 1–16, 2009.
  * [32] S. Chien, K. Ligett, and A. McGregor, “Space-efficient estimation of robust statistics and distribution testing.,” in ICS, pp. 251–265, Citeseer, 2010\.
  * [33] P. Flajolet, “Approximate counting: a detailed analysis,” BIT Numerical Mathematics, vol. 25, no. 1, pp. 113–134, 1985.
  * [34] J. Nelson and H. Yu, “Optimal bounds for approximate counting,” arXiv preprint arXiv:2010.02116, 2020.
  * [35] D. A. Levin and Y. Peres, Markov chains and mixing times, vol. 107.  American Mathematical Soc., 2017.
  * [36] T. M. Cover and J. A. Thomas, Elements of information theory.  John Wiley & Sons, 2012.


fixmeTotalCounter [500] Human-centered computing HCI theory, concepts and
models rightsretained 978-1-4503-6819-3/20/04

# Conceptualizing the Relationship between AI Explanations and User Agency

Iyadunni Adenuga

Jonathan Dodge

Penn State University  University Park, PA 16802, USA<EMAIL_ADDRESS>Penn
State University  University Park, PA 16802, USA<EMAIL_ADDRESS>
(2023)

###### Abstract

We grapple with the question: _How, for whom and why should explainable
artificial intelligence (XAI) aim to support the user goal of agency?_ In
particular, we analyze the relationship between agency and explanations
through a user-centric lens through case studies and thought experiments. We
find that explanation serves as one of several possible first steps for agency
by allowing the user convert forethought to outcome in a more effective manner
in future interactions. Also, we observe that XAI systems might better cater
to laypersons, particularly “tinkerers,” when combining explanations and user
control, so they can make meaningful changes.

###### keywords:

Explainability; Agency; AI systems

###### doi:

https://doi.org/10.1145/3334480.XXXXXXX

††conference: CHI Workshops ’23 April 23–28, 2023, Hamburg, Germany

##  1 Introduction

Complex technologies are commonplace in today’s society, with examples
including reinforcement learning, deep neural networks, or other forms of
artificial intelligence (AI). Criticisms have plagued the acceptance of these
technologies due to the opaque nature of the algorithms and the erasure of
user influence (i.e., creating an automated experience). For example, high-
stakes scenarios (e.g. law enforcement, medicine, etc.) traditionally require
human experts that go through rigorous training, who are then accountable to
human stakeholders. Thus, it is unsurprising that such decision makers prefer
worse-performing, interpretable models over opaque models [45].

Beyond experts, laypeople also desire a level of control and understanding of
the complex AI systems that affect them [48, 40]. Legal regimes (e.g.,
European Union General Data Protection Regulation [18] and White House
Executive Order [23]) align with such observations by highlighting the
importance of human agency over these systems and the need for these systems
to explain and justify their results.

However, making AI systems more _agentic_ is not as widely studied as making
them _explainable_. This paper attempts to describe how designing for agency
fits with XAI, namely: 1) the relationship between agency and explanations and
2) agency in scenarios with two and three user groups.

##  2 What is an Explanation?

Explanation is a human phenomenon that strongly relates with peoples’ mental
models, understanding and knowledge of “why an outcome happened” [26]. Its
social interactive characteristic [26] means there’s some level of
communication (which may be continuous) occurring between the explain-_er_ and
explain-_ee_.

Relationship between Agency and Explanations in an XAI system

Today, AI systems are a major part of our environment. If the target users do
not understand the model, they usually cannot assess or appropriately rely
[38] on it. To address this, post-hoc methods aim to make opaque AI methods
(e.g. neural networks, ensemble models, etc.) more “understandable” without
compromising accuracy [4, 14]. There are two main approaches employed by post-
hoc techniques: _opaque box_ (operates on the input/output boundary; e.g.,
LIME [36], LORE [21]) and _transparent box_ (operates on the internal
structures; e.g., deconvnet model method [50] and network dissection [8, 9]).

[90pt]  From Zhang and Lim paper [51], user interface of Counterfactual
Explanation for Voice-Emotion Recognition system (best viewed digitally).

Existing XAI systems that utilize the opaque- and transparent-box approaches
described above do not fit the requirements laid out in prior work for
“everyday” explanations understandable to the layperson [33]. AI explanations
created based on human characteristics (e.g. preferences, reasoning and
perception methods) are more relatable and effective [46, 51, 29]. In their
work about connecting existing XAI techniques to user expectations for
explanations, Liao et al. [30] propose a “question-driven framework” that
encourages an interactive explanation experience [30] via meaningful
interrogative dialogue [33].

##  3 What is Agency?

People have an innate need to control the course of their lives and predict
the outcomes of situations, no matter the difficulty [6]. Humans feel a sense
of agency when we believe that our _“conscious intention caused a voluntary
action”_ [47]. Agency is an internal “human” feeling that is outwardly
expressed by intentional actions. If people do not feel in control, they might
abandon the on-going task or distrust their actions, especially in hard
situations [5].

A technology that affords agency is “flexible” to the user’s interactions
inputs and interests such that they can modify their experience [49, 43]. The
control a person has in a typical environment (such as while utilizing
technology) can be weighted by: 1) the presence of relevant actions; 2) the
relationship between the actions of a user and the outcome in the environment;
3) the ability of a user to predict the outcome of their actions, and; 4) the
ability of the user to trace the cause of an outcome [42].

Researchers have shown agentic interactions have positive effects such as
improved user experience and satisfaction and more appropriate trust [19, 24,
44]. The many AI systems stakeholders with low technical knowledge should also
experience these benefits, as per the ACM Code of Ethics: _“…all people are
stakeholders in computing”_ [2].

##  4 How are Agency and Explanation Related?

The answer to this question is not straightforward, but we will attempt an
answer for AI systems. Existing human-centered XAI systems prioritize
providing explanations in an understandable, visually appealing format with an
assumption of improved agency in the represented artifact. There is no
_direct_ measure for the “actual” agency a user experienced while interacting
with such a system. _Self-reporting_ only measures agency _perceived_ by
users, which is a proxy for “actual” agency. Teasing out the modalities of the
relationship between explanation and agency is the first step in deducing the
“actual” agency in XAI systems.

The agency process starts from a person’s _forethought_ to their performance
of an action and then, observation of the action’s outcome. The aim of
explanations is to improve the consumers’ understanding of their environment.
Providing explanations can contribute to consumers’ sense of agency by
informing their initial _forethought_ so they perform the appropriate actions
to successfully complete their task. People with higher need for control are
more likely to seek more information and clarifications in a work environment
[20]. This shows that even before the introduction of explanations to a
scenario, an individual has an inherent agency requirement—and that such
requirements will vary among users.

Studies on designing agency in AI systems, such as interactive machine
learning, have primarily focused on users with technical know-how, and in its
absence, requires additional technical training for end-users for them to
understand and use the provided agentic functions [41, 15]. End-users with no
access to technical training can still benefit from an agentic experience with
explanations.

[20pt]  The original Rube Goldberg machine, as depicted in the cartoon
“Professor Butts and the Self-Operating Napkin.” The machine functions as
follows: _“Soup spoon (A) is raised to mouth, pulling string (B) and thereby
jerking ladle (C), which throws cracker (D) past toucan (E). Toucan jumps
after cracker and perch (F) tilts, upsetting seeds (G) into pail (H). Extra
weight in pail pulls cord (I), which opens and ignites lighter (J), setting
off skyrocket (K), which causes sickle (L) to cut string (M), allowing
pendulum with attached napkin to swing back and forth, thereby wiping chin.”_
https://en.wikipedia.org/wiki/Rube_Goldberg_machine Users can take an active
role in their absorption of an explanation. Zhang and Lim [51] studied
providing relatable explanations for a vocal-emotion recognition system, the
participants preferred and utilized more effectively the “Counterfactual
Sample + Cues” explanation (Figure 2). The user interface for this explanation
required active play-through and listening to alternative voices to detect
vocal differences. Another method for involving people in the explanation
process is to obtain input from them to create “selective” explanations [29].
Here, the user customizes the types of received explanations to their taste.

Tastes vary, for example GenderMag [10] identified facets describing people’s
cognitive styles. One important axis is _learning style_ , with people who
gain understanding by “tinkering” with the technology on one end. To cater to
tinkerers, XAI system designs should have control functions. These functions
would accept different kinds of user inputs and then provide appropriate
visible outcomes, allowing the system to _“be actionable”_ [28]. On the other
end of the learning style axis are people who gain understanding _by process_.
Process-oriented learners may benefit from assessment _processes_ , such as
After-Action Review for AI (AAR/AI) [13]. Later, Khanna et al. [27] found
participants helped participants examine and effectively use explanations to
identify AI faults, observing a moderate-sized practical effect.

There are situations when XAI systems cannot honor user inputs [41]. How
should the system react? For low-stakes scenarios, illusory agency may be a
useful tool. Game designers use this as a complementary mechanism to preserve
their rigid game-story narrative [12, 32]. To allow for continued user agency,
the user is able to observe the effect of their input but the input has no
effect on the underlying algorithms. Vaccaro et al. [44] showed in a social
media setting that users _“felt more satisfied with the presence of controls”_
regardless of their effectiveness. Some everyday systems that already utilize
illusory agency include crosswalk buttons and elevator close-door buttons.
Illusory agency should only be designed to supplement the already present
“real” agentic experience in low-stakes scenarios so as to avoid user
deception and minimize the effects of ethical issues. Example of such
scenarios that might benefit from illusory agency include XAI systems in
training environments [17].

##  5 How Does One Increase or Decrease Agency?

We will use two examples to illustrate adjusting agency. The first example is
to consider wiping your mouth with a napkin using direct manipulation vs with
a Rube Goldberg machine, depicted in Figure 4. Rube Goldberg machines are
famous for having a simple input, which then initiates a complicated chain
reaction generating a simple output. In this case, the simple input is lifting
a spoon, the long chain reaction is via the crackers, toucan, string, etc.,
and the simple output is wiping one’s mouth.

[10pt]  Notional curve depicting agency as a function of number of controls.
When moving from no controls to few controls, agency gain enjoys a direct
relationship. But at some point, the extra controls will overwhelm the user,
either taking the form of a plateau (red curve) or even a downturn (blue
curve).  [-35pt]  1) Add/remove source documents 2) Add/remove sections, where
sections are subtopics of the document title 3) Add/remove words and/or
sentences 4) View the order relation of the summary sentences in a concept
graph 5) View actual sentences contributed by each document to the overall
summary output Key functionality found in Living Documents.

As Figure 4 shows, the machine automates the functioning of the napkin to the
point that its use is involuntary. Suppose we changed the simple input to be
pushing a button, which is more typical of modern technology. Now, consider
how much agency the user has in each case. It seems fairly obvious that agency
would be highest with direct manipulation, then with button-interface Rube
Goldberg machine, and finally the unmodified Rube Goldberg machine. The
reasoning is that with direct manipulation, one could manifest whatever wiping
approach they desire: arbitrary direction, length of time, and so on. Note
that all of the previously compared interactions lead to same _outcome_ , but
are different in terms of controllability [37]. According to Shneiderman [39],
high levels of automation and human control can co-exist in a technical
artifact. They illustrate this in their description of the digital camera and
elevator where agency is afforded by the inclusion of a button and settings
page respectively. This is similar to the surface-level agency button
introduced above, to the Rube Goldberg machine. Would increasing agency
require addition of extra buttons/settings or introducing a more manual and
influential process (i.e., less automation)? If we assume adding a feature and
accompanying button increases perceived agency, what is the amount of UI
complexity at which agency gains diminish or turn negative (See Figure 5 for
an illustration)?

Thus, we have illustrated a tension between manual processes (which have the
highest agency) vs automation (which reduces agency). The open question is,
how much agency does one lose when a process undergoes automation? To answer
this question, we turn to our second example: Living Documents [3]. Living
Documents is an interactive multi-document text summarization system,
providing the control functions found in Table 5.

What would agency treatment levels look like in Living Documents? The highest-
level of agency is full access to all functionality in the system (full-
agency, see Table 5) while the automation level has no user controls (no-
agency). This means it would work like a typical text summarization system
such that the only input-output operation is the user providing the source
documents and receiving the summary result. The interaction designer can
decide on intermediate level(s) based on specified criteria. Our criterion is
“magnitude of impact” (document $\rightarrow$ sections $\rightarrow$
sentences/words), so our some-agency treatment has functionality 3 to 5 in
Table 5.

##  6 Agency and/or Explanations, for whom?

Now, we would like to broaden the previously discussed system-user agency
cases to where there are _multiple types_ of users, leading to a more complex
tradeoff relationship. From an explanation perspective, we know that
explanations may need to account for different domain expertise, cognitive
abilities, context of use, and audience. Users have varied needs for an XAI
system [30] and do not have a homogeneous process for interacting with models
[41]. The agency perspective is less well studied.

Consider the case of a rideshare application called Co-opRide, which is an
algorithmic manager for _two_ user groups: drivers and riders. What is the
right agency balance to strike between these three parties (the third is Co-
opRide)? Suppose Co-opRide offers a design feature that drivers can veto
riders. This would increase the agency of the drivers at the expense of the
riders’ agency, as well as that of the system provider. Imagine being a rider
receiving vetoes from several drivers, based on your low population density
location or even worse, cultural markers present in your name. This might lead
to long wait times and negative customer sentiment. Should the XAI system
alert riders that a driver vetoed them? Each time? How should the XAI system
provide notification of the veto and/or explain the decision? If there are no
satisfying agentic actions available, why should the system provide
explanation at all? In the case where the rider’s waiting time increases over
time as a result of receiving multiple driver vetoes, provision of
explanations by the algorithmic XAI platform becomes even more imperative.

The example of the driver veto feature suggests “The Agency Tradeoff Game”
might be zero-sum, though this it is not totally clear that it cannot be
positive-sum or negative-sum. It is also an open question whether or not a
stable solution exists. As an example, “Hotelling’s game” (see margin) has a
stable solution with two players, but the three-player version has no stable
solution ([35], Chapter 3).

††margin:  Hotelling’s Game [22] Suppose two competing shops are located along
the length of street, with customers spread equally along the street. Each
customer will always choose the nearer shop. With two shops, the consumer
ideal has shops at $\frac{1}{4}$ and $\frac{3}{4}$. However, this is unstable,
since both shops can claim more customers by moving toward the middle. The
stable solution has both at $\frac{1}{2}$. (E.g., this is why Lowe’s and Home
Depot are often co-located.)

XAI platforms interact with groups of humans; as a result, agency occurring on
a _collective_ basis becomes relevant. When individuals perform a joint
action, they can feel individual and/or collective (joint) agency [31]. The
individual perceived self-efficacy of multiple members of a group forms
collective efficacy which can lead to meaningful social change [5, 7]. People
are usually interested in the experiences of their fellow people and this has
led to calls for social explanations [30, 16]. Enabling social explanations
means there can be a joint platform for “knowledge sharing” and “social
learning” [16]. People can confidently contest the decisions by an AI system
and if some form of collective agency has been designed in the system, they
can effect popular meaningful change.

For an example of collective agency as a result of the conditions in an AI
system, consider work by Calacci and Pentland [11]. Shipt, a grocery delivery
service with an AI algorithmic manager, was initially explainable and
transparent about its wage calculation process. The introduction of a wage-
processing opaque-box algorithm to Shipt led to the implementation of social
explanations, albeit on a platform (called Shipt Calculator [11]) external to
the AI system. Workers anonymously provided screenshots of their payment
history and the Shipt Calculator aggregated the payment information and
provided the observed wage difference to the workers. These authors discovered
a paycut for 41 percent of the workers in their study. Similar occurrences
with Doordash led to change in the pay and tipping model as well as a class-
action lawsuit [34, 25]. XAI systems that allow social explanations and
collective agency would ensure a cooperative approach so that only beneficial
improvements are implemented on the platform.

##  7 Concluding Remarks

We do not claim that our statement of the relationship between agency and
explanation is complete. As an example, perhaps agency and explanations might
share multiple simultaneous relationships. We believe that recognizing and
formalizing these relationship(s) would ensure that XAI designers take the
closely-related extra step of designing for _agency_ while working on
explainability.

## References

  * [1]
  * [2] ACM. 2018.  ACM Code of Ethics and Professional Conduct.  (2018).  https://www.acm.org/code-of-ethics
  * [3] Iyadunni J Adenuga, Benjamin V Hanrahan, Chen Wu, and Prasenjit Mitra. 2022.  Living Documents: Designing for User Agency over Automated Text Summarization. In CHI Conference on Human Factors in Computing Systems Extended Abstracts. 1–6.
  * [4] Alejandro Barredo Arrieta, Natalia Díaz-Rodríguez, Javier Del Ser, Adrien Bennetot, Siham Tabik, Alberto Barbado, Salvador García, Sergio Gil-López, Daniel Molina, Richard Benjamins, and others. 2020.  Explainable Artificial Intelligence (XAI): Concepts, taxonomies, opportunities and challenges toward responsible AI.  Information fusion 58 (2020), 82–115.
  * [5] Albert Bandura. 1982.  Self-efficacy mechanism in human agency.  American psychologist 37, 2 (1982), 122.
  * [6] Albert Bandura. 1996a.  Reflections on human agency: Part I.  Constructivism in the Human Sciences 1, 2 (1996), 3.
  * [7] Albert Bandura. 1996b.  Reflections on human agency: Part II.  Constructivism in the Human Sciences 1, 3/4 (1996), 5.
  * [8] David Bau, Bolei Zhou, Aditya Khosla, Aude Oliva, and Antonio Torralba. 2017.  Network dissection: Quantifying interpretability of deep visual representations. In Proceedings of the IEEE conference on computer vision and pattern recognition. 6541–6549.
  * [9] David Bau, Jun-Yan Zhu, Hendrik Strobelt, Agata Lapedriza, Bolei Zhou, and Antonio Torralba. 2020.  Understanding the role of individual units in a deep neural network.  Proceedings of the National Academy of Sciences 117, 48 (2020), 30071–30078.
  * [10] Margaret Burnett, Simone Stumpf, Jamie Macbeth, Stephann Makri, Laura Beckwith, Irwin Kwan, Anicia Peters, and William Jernigan. 2016.  GenderMag: A method for evaluating software’s gender inclusiveness.  Interacting with Computers 28, 6 (2016), 760–787.
  * [11] Dan Calacci and Alex Pentland. 2022.  Bargaining with the Black-Box: Designing and Deploying Worker-Centric Tools to Audit Algorithmic Management.  Proc. ACM Hum.-Comput. Interact. 6, CSCW2, Article 428 (nov 2022), 24 pages.  DOI:http://dx.doi.org/10.1145/3570601
  * [12] Timothy Day and Jichen Zhu. 2017.  Agency informing techniques: Communicating player agency in interactive narratives. In Proceedings of the 12th International Conference on the Foundations of Digital Games. 1–4.
  * [13] Jonathan Dodge, Roli Khanna, Jed Irvine, Kin-ho Lam, Theresa Mai, Zhengxian Lin, Nicholas Kiddle, Evan Newman, Andrew Anderson, Sai Raja, Caleb Matthews, Christopher Perdriau, Margaret Burnett, and Alan Fern. 2021.  After-Action Review for AI (AAR/AI).  ACM Trans. Interact. Intell. Syst. 11, 3–4, Article 29 (sep 2021), 35 pages.  DOI:http://dx.doi.org/10.1145/3453173
  * [14] Filip Karlo Došilović, Mario Brčić, and Nikica Hlupić. 2018.  Explainable artificial intelligence: A survey. In 2018 41st International convention on information and communication technology, electronics and microelectronics (MIPRO). IEEE, 0210–0215.
  * [15] John J Dudley and Per Ola Kristensson. 2018.  A review of user interface design for interactive machine learning.  ACM Transactions on Interactive Intelligent Systems (TiiS) 8, 2 (2018), 1–37.
  * [16] Upol Ehsan, Q Vera Liao, Michael Muller, Mark O Riedl, and Justin D Weisz. 2021.  Expanding explainability: Towards social transparency in ai systems. In Proceedings of the 2021 CHI Conference on Human Factors in Computing Systems. 1–19.
  * [17] Krzysztof Fiok, Farzad V Farahani, Waldemar Karwowski, and Tareq Ahram. 2022.  Explainable artificial intelligence for education and training.  The Journal of Defense Modeling and Simulation 19, 2 (2022), 133–144.
  * [18] GDPR. 2018.  European Union General Data Protection Regulation, Article 15 - “Right of access by the data subject”.  (2018).  http://www.privacy-regulation.eu/en/article-15-right-of-access-by-the-data-subject-GDPR.htm Accessed: 1/16/2019.
  * [19] Andreas Girgensohn, Sara A Bly, Frank Shipman, John S Boreczky, and Lynn Wilcox. 2001.  Home Video Editing Made Easy-Balancing Automation and User Control.. In INTERACT, Vol. 1. 464–471.
  * [20] Michael Goller and Christian Harteis. 2017.  Human agency at work: Towards a clarification and operationalisation of the concept.  In Agency at work. Springer, 85–103.
  * [21] Riccardo Guidotti, Anna Monreale, Fosca Giannotti, Dino Pedreschi, Salvatore Ruggieri, and Franco Turini. 2019.  Factual and counterfactual explanations for black box decision making.  IEEE Intelligent Systems 34, 6 (2019), 14–23.
  * [22] Harold Hotelling. 1929.  Stability in Competition.  The Economic Journal 39, 153 (1929), 41–57.  http://www.jstor.org/stable/2224214
  * [23] White House. 2022.  Blueprint for an AI Bill of Rights.  (2022).  https://www.whitehouse.gov/ostp/ai-bill-of-rights/ Last accessed: 10/13/22.
  * [24] Jina Huh, Martha Pollack, Hadi Katebi, Karem Sakallah, and Ned Kirsch. 2010.  Incorporating user control in automated interactive scheduling systems. In Proceedings of the 8th ACM Conference on Designing Interactive Systems. 306–309.
  * [25] Catie Keck. 2019.  DoorDash tip-skimming scheme prompts class action lawsuit seeking all those tips that didn’t go to drivers.  (Jul 2019).  https://gizmodo.com/doordash-tip-skimming-scheme-prompts-clash-action-lawsu-1836820630
  * [26] Frank C Keil. 2006.  Explanation and understanding.  Annual review of psychology 57 (2006), 227.
  * [27] Roli Khanna, Jonathan Dodge, Andrew Anderson, Rupika Dikkala, Jed Irvine, Zeyad Shureih, Kin-ho Lam, Caleb R Matthews, Zhengxian Lin, Minsuk Kahng, and others. 2022.  Finding AI’s faults with AAR/AI: An empirical study.  ACM Transactions on Interactive Intelligent Systems (TiiS) 12, 1 (2022), 1–33.
  * [28] Todd Kulesza, Margaret Burnett, Weng-Keen Wong, and Simone Stumpf. 2015\.  Principles of explanatory debugging to personalize interactive machine learning. In Proceedings of the 20th international conference on intelligent user interfaces. 126–137.
  * [29] Vivian Lai, Yiming Zhang, Chacha Chen, Q Vera Liao, and Chenhao Tan. 2023.  Selective Explanations: Leveraging Human Input to Align Explainable AI.  arXiv preprint arXiv:2301.09656 (2023).
  * [30] Q Vera Liao, Daniel Gruen, and Sarah Miller. 2020.  Questioning the AI: informing design practices for explainable AI user experiences. In Proceedings of the 2020 CHI Conference on Human Factors in Computing Systems. 1–15.
  * [31] Janeen D Loehr. 2022.  The sense of agency in joint action: An integrative review.  Psychonomic Bulletin & Review (2022), 1–29.
  * [32] Esther MacCallum-Stewart and Justin Parsler. 2007.  Illusory agency in vampire: The masquerade–Bloodlines.  Dichtung Digital. Journal für Kunst und Kultur digitaler Medien 9, 1 (2007), 1–17.
  * [33] Brent Mittelstadt, Chris Russell, and Sandra Wachter. 2019.  Explaining explanations in AI. In Proceedings of the conference on fairness, accountability, and transparency. 279–288.
  * [34] Andy Newman. 2019.  Doordash changes tipping model after uproar from customers.  (Jul 2019).  https://www.nytimes.com/2019/07/24/nyregion/doordash-tip-policy.html?action=click& module=Intentional& pgtype=Article
  * [35] Martin J. Osborne. 2004.  An introduction to game theory.  Oxford Univ. Press, New York, NY [u.a.].  http://gso.gbv.de/DB=2.1/CMD?ACT=SRCHA&SRT=YOP&IKT=1016&TRM=ppn+369342747&sourceid=fbw_bibsonomy
  * [36] Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. 2016.  " Why should i trust you?" Explaining the predictions of any classifier. In Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining. 1135–1144.
  * [37] Quentin Roy, Futian Zhang, and Daniel Vogel. 2019.  Automation Accuracy Is Good, but High Controllability May Be Better. In Proceedings of the 2019 CHI Conference on Human Factors in Computing Systems (CHI ’19). Association for Computing Machinery, New York, NY, USA, 1–8.  DOI:http://dx.doi.org/10.1145/3290605.3300750
  * [38] Max Schemmer, Niklas Kuehl, Carina Benz, Andrea Bartos, and Gerhard Satzger. 2023.  Appropriate Reliance on AI Advice: Conceptualization and the Effect of Explanations. In Proceedings of the 28th International Conference on Intelligent User Interfaces (IUI ’23). Association for Computing Machinery, New York, NY, USA, 410–422.  DOI:http://dx.doi.org/10.1145/3581641.3584066
  * [39] Ben Shneiderman. 2020.  Human-centered artificial intelligence: Reliable, safe & trustworthy.  International Journal of Human–Computer Interaction 36, 6 (2020), 495–504.
  * [40] Ben Shneiderman, Catherine Plaisant, Maxine Cohen, Steven Jacobs, Niklas Elmqvist, and Nicholoas Diakopoulos. 2016.  Grand Challenges for HCI Researchers.  Interactions 23, 5 (aug 2016), 24–25.  DOI:http://dx.doi.org/10.1145/2977645
  * [41] Alison Smith-Renner, Varun Kumar, Jordan Boyd-Graber, Kevin Seppi, and Leah Findlater. 2020.  Digging into User Control: Perceptions of Adherence and Instability in Transparent Models. In Proceedings of the 25th International Conference on Intelligent User Interfaces (IUI ’20). Association for Computing Machinery, New York, NY, USA, 519–530.  DOI:http://dx.doi.org/10.1145/3377325.3377491
  * [42] Suzanne C Thompson, Wade Armstrong, and Craig Thomas. 1998.  Illusions of control, underestimations, and accuracy: a control heuristic explanation.  Psychological bulletin 123, 2 (1998), 143.
  * [43] David Thue, Vadim Bulitko, Marcia Spetch, and Trevon Romanuik. 2010.  Player agency and the relevance of decisions. In Joint International Conference on Interactive Digital Storytelling. Springer, 210–215.
  * [44] Kristen Vaccaro, Dylan Huang, Motahhare Eslami, Christian Sandvig, Kevin Hamilton, and Karrie Karahalios. 2018.  The Illusion of Control: Placebo Effects of Control Settings. In Proceedings of the 2018 CHI Conference on Human Factors in Computing Systems (CHI ’18). Association for Computing Machinery, New York, NY, USA, 1–13.  DOI:http://dx.doi.org/10.1145/3173574.3173590
  * [45] Michael Veale, Max Van Kleek, and Reuben Binns. 2018.  Fairness and Accountability Design Needs for Algorithmic Support in High-Stakes Public Sector Decision-Making. In Proceedings of the 2018 CHI Conference on Human Factors in Computing Systems (CHI ’18). ACM, New York, NY, USA, Article 440, 14 pages.  DOI:http://dx.doi.org/10.1145/3173574.3174014
  * [46] Danding Wang, Qian Yang, Ashraf Abdul, and Brian Y Lim. 2019.  Designing theory-driven user-centric explainable AI. In Proceedings of the 2019 CHI conference on human factors in computing systems. 1–15.
  * [47] Daniel M Wegner and Thalia Wheatley. 1999.  Apparent mental causation: Sources of the experience of will.  American psychologist 54, 7 (1999), 480.
  * [48] Allison Woodruff, Sarah E. Fox, Steven Rousso-Schindler, and Jeffrey Warshaw. 2018.  A Qualitative Exploration of Perceptions of Algorithmic Fairness. In Proceedings of the 2018 CHI Conference on Human Factors in Computing Systems (CHI ’18). Association for Computing Machinery, New York, NY, USA, 1–14.  DOI:http://dx.doi.org/10.1145/3173574.3174230
  * [49] Peta Wyeth. 2007.  Agency, tangible technology and young children. In Proceedings of the 6th international conference on Interaction design and children. 101–104.
  * [50] Matthew D Zeiler and Rob Fergus. 2014.  Visualizing and understanding convolutional networks. In European conference on computer vision. Springer, 818–833.
  * [51] Wencan Zhang and Brian Y Lim. 2022.  Towards relatable explainable AI with the perceptual process. In Proceedings of the 2022 CHI Conference on Human Factors in Computing Systems. 1–24.