# On the consistency of the Kozachenko-Leonenko entropy estimate

Luc Devroye Luc Devroye, School of Computer Science, McGill University,
Montreal, Canada<EMAIL_ADDRESS>Luc’s research was supported by a
Discovery Grant from NSERC. László Györfi László Györfi, Department of
Computer Science and Information Theory, Budapest University of Technology and
Economics, Budapest, Hungary<EMAIL_ADDRESS>
###### Abstract

We revisit the problem of the estimation of the differential entropy $H(f)$ of
a random vector $X$ in $R^{d}$ with density $f$, assuming that $H(f)$ exists
and is finite. In this note, we study the consistency of the popular nearest
neighbor estimate $H_{n}$ of Kozachenko and Leonenko. Without any smoothness
condition we show that the estimate is consistent ($E\\{|H_{n}-H(f)|\\}\to 0$
as $n\to\infty$) if and only if ${\mathbb{E}}\\{\log(\|X\|+1)\\}<\infty$.
Furthermore, if $X$ has compact support, then $H_{n}\to H(f)$ almost surely.

Index terms: differential entropy estimate, consistency conditions

##  1 Introduction

The differential entropy of a random ${\mathbb{R}}^{d}$-valued vector $X$ with
probability density function $f$ is

$H(f)=-\int f(x)\ln f(x)dx=-{\mathbb{E}}\\{f(X)\\}$ (1)

when this integral exists.

The objective of this paper is to study an estimate of (1) based on
independent and identically distributed samples $X_{1},\dots X_{n}$, with
density $f$.

Estimation of the differential entropy has a long history. The early part of
that story was described by Beirlant et al. [2]. Since then, there has been
considerable activity on the topic. There are estimates based on kernel
methods (Joe [20]; Györfi and van der Meulen [17]; Hall and Morton [18];
Shwartz et al. [27]; Paninski and Yajima [26]; Krishnamurthy et al. [23];
Kandasamy et al. [21]), on wavelet functions, (Donoho et al. [10]; Delyon et
al. [8], and Chesneau et al. [6]), on partitioning methods (Stowell et al.
[33]), and on nearest neighbour strategies (Kozachenko and Leonenko [22];
Tsybakov and Van der Meulen [34]; Singh et al. [29]; Sricharan, Raich, and
Hero [31]; Sricharan, Wei, and Hero [32]; Singh and Póczos [30]; Gao, Oh, and
Viswanath [13] and [12]; Delattre and Fournier [7]; Lord, Sun, and Bollt [24];
Berrett, Samworth, and Yuan [3]). Other related work deals with general
properties of functional estimation (see, e.g., Birgé and Massart [5]) or
sufficient conditions of consistency of the so-called integral estimate $\int
f_{n}\log(1/f_{n})$ when $f_{n}$ is a general density estimate (see, e.g.,
Godavarti [14]).

There has been particular interest in minimax rates of convergence,
culminating in the paper by Han, Jiao, Weissman and Wu [19] who obtained the
minimax rates for classes of densities on the unit cube of ${\mathbb{R}}^{d}$
that are Besov balls or Hölder (Lipschitz) balls of smoothness parameters $s$.
Their rates are of exact order $\max(1/(n\log n)^{s/(s+d)},1/\sqrt{n})$. For
standard Lipschitz densities, the minimax rate is of exact order $1/\sqrt{n}$
(achieving the parametric rate) for dimension one, but it is $1/(n\log
n)^{-1/(d+1)}$ when $d>1$. They also construct a kernel-based estimate that is
minimax optimal for these classes.

Most of the previous work assumes compact support, and thus sidesteps the
thorny issue of infinite tails. The objective of this note is merely to give a
complete characterization of the consistency of the popular Kozachenko-
Leonenko estimate [22] for estimating the differential entropy. Without any
smoothness condition on the density $f$ we study three types of consistency:
strong, $L_{1}$ and weak.

It is an open research problem, whether there exists an entropy estimate such
that it is consistent under the only condition that $H(f)$ is finite. The most
obvious way of estimating the differential entropy is the partitioning-based
estimate. If the corresponding partition is deterministic, then we conjecture
that there exist no deterministic partitions such that the relating
differential entropy estimate is a.s. consistent for any finite differential
entropy. The significant breakthrough in this respect is due to Wang,
Kulkarni, Verdu [35] and Silva, Narayanan [28]. They suggested data-dependent
partitioning, for which the partitioning-based estimates of Kullback-Leibler
(KL) divergence and of mutual information are strongly consistent under the
only condition that the KL-divergence and the mutual information are finite,
respectively. We guess that a universally consistent entropy estimate can be
derived from data dependent partitioning.

For the cross-validation estimate or leave-one-out entropy estimate, $f_{n,i}$
denotes a density estimate based on $X_{1},\dots X_{n}$ leaving $X_{i}$ out,
and the corresponding entropy estimate is of the form

$H_{n}=-\frac{1}{n}\sum_{i=1}^{n}\ln f_{n,i}(X_{i}).$ (2)

Kozachenko and Leonenko [22] introduced the nearest neighbor entropy estimate
as follows. Let $R_{n,i}(x)$, $x\in{\mathbb{R}}^{d}$, be defined by

$\displaystyle R_{n,i}(x)=\min_{j\neq i,j\leq n}\|x-X_{j}\|,$

where $\|\cdot\|$ denotes the Euclidean norm. Then the nearest neighbor
entropy estimate is

$\displaystyle
H_{n}=\frac{1}{n}\sum_{i=1}^{n}\ln((n-1)R_{n,i}(X_{i})^{d}v_{d})+C_{E},$ (3)

where $C_{E}=-\int_{0}^{\infty}e^{-t}\ln tdt=0.5772...$ is the Euler-
Mascheroni constant and $v_{d}$ denotes the volume of the unit sphere in
${\mathbb{R}}^{d}$. The estimate in (3) has the form of (2) if $f_{n,i}$ is a
constant multiple of the first-nearest-neighbor (1-NN) density estimate:

$\displaystyle f_{n,i}(x)=\frac{1}{(n-1)\min_{j\neq i,j\leq
n}\|x-X_{j}\|^{d}v_{d}e^{C_{E}}}.$

Notice that this particular $f_{n,i}$ is not consistent in $L_{1}$, because

$\displaystyle\int f_{n,i}(x)dx=\infty.$

Furthermore, $f_{n,i}(x)$ is unbounded at the $X_{j},j\neq i$. Also,
$f_{n,i}(x)$ does not in general tend to $f(x)$ in probability, i.e., the
density estimates $f_{n,i}$ are not weakly consistent.

Under some mild conditions on the density $f$, Kozachenko and Leonenko [22]
proved the mean square consistency. Biau and Devroye [4] showed that for
bounded $X$, if $\int f(x)\ln^{2}(f(x)+1)dx<\infty$, then $H_{n}\to H(f)$ in
probability.

For smooth densities, Berrett, Samworth and Yuan [3], Delattre and Fournier
[7] and Tsybakov and van der Meulen [34] studied the rate of convergence of
$H_{n}$ and of its extensions to many nearest neighbors.

In this paper we show that for bounded $X$ the Kozachenko-Leonenko estimate is
strongly consistent. Furthermore, give a necessary and sufficient tail
condition for $L_{1}$ consistency. In addition, construct a counterexample on
weak consistency for a uniform density on an unbounded set. The proofs are
presented in the last section.

##  2 Consistency results

For bounded $X$, without any smoothness condition on the density $f$ the
Kozachenko-Leonenko estimate is strongly consistent:

######  Theorem 1.

If the support of $f$ is bounded and

$\displaystyle\int f(x)\ln(f(x)+1)dx<\infty,$ (4)

then

$\displaystyle\lim_{n\rightarrow\infty}H_{n}=H(f)$ (5)

a.s.

Next, we present a necessary and sufficient tail condition on the consistency
in $L_{1}$:

######  Theorem 2.

Assume that $H(f)$ is finite. For any density $f$,

$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{E}}\\{|H_{n}-H(f)|\\}=0$ (6)

if and only if

$\displaystyle{\mathbb{E}}\\{(\ln\|X\|)^{+}\\}<\infty.$ (7)

If ${\mathbb{E}}\\{(\ln\|X\|)^{+}\\}=\infty$, then maybe the expectations
${\mathbb{E}}\\{\ln\|X\|\\}$ and ${\mathbb{E}}\\{\ln R_{n,1}(X_{1})\\}$ don’t
exist. However, for finite $H(f)$, we show that the expectation
${\mathbb{E}}\\{H_{n}\\}$ is well defined such that it is larger than
$-\infty$.

As sufficient condition, (7) appeared in the studies of distribution and
density estimates consistent in KL-divergence. For discrete distributions
concentrated to the set of positive integers, Györfi, Páli and van der Meulen
[16] proved that a distribution with finite Shannon entropy cannot be
estimated consistently in KL-divergence. It means that for any distribution
estimate $p_{n}=(p_{n,1},p_{n,2},\dots)$ there exist a distribution
$p=(p_{1},p_{2},\dots)$ with finite Shannon entropy such that for the KL-
divergence

$\displaystyle
KL(p,p_{n})=\sum_{i=1}^{\infty}p_{i}\ln\frac{p_{i}}{p_{n,i}}=\infty$

for all $n$ a.s. However, under (7) one can construct a distribution estimate
$p_{n}$ such that $KL(p,p_{n})\to 0$ a.s. This positive finding has been
generalized to density estimation consistent in KL-divergence. For the
condition (7), one can create a density $g$ of power tail such that the
mixture of the ordinary histogram and of this $g$ is consistent in KL-
divergence, see Barron, Györfi and van der Meulen [1].

Theorem 2 is a complete characterization of the consistency in $L_{1}$. In
fact, we show that there are two cases:

  * •

either ${\mathbb{E}}\\{(\ln\|X\|)^{+}\\}=\infty$ and then
${\mathbb{E}}\\{H_{n}\\}=\infty$, for all $n$,

  * •

or ${\mathbb{E}}\\{(\ln\|X\|)^{+}\\}<\infty$ and then
$\lim_{n\rightarrow\infty}{\mathbb{E}}\\{|H_{n}-H(f)|\\}=0$.

In the sequel, we show an example, where the density is uniform on an
unbounded set and $H_{n}\to\infty$ in probability..

Denote by $\lambda$ the Lebesgue measure and by $\mu$ the distribution of $X$.
For $d=1$, let

$\displaystyle f={\mathbb{I}}_{A},$

where $A=\cup_{j}A_{j}$ with disjoint intervals $A_{j}$ such that
$\lambda(A)=1$. Then, $X$ is uniformly distributed on $A$ and therefore
$H(f)=0$. For $j\geq 1$, let $\Delta_{j}=\frac{1}{j(j+1)}$ and
$a_{j}=2^{2^{j}}$. Set $A=\cup_{j\geq 1}[a_{j},a_{j}+\Delta_{j}]$. Then
$\lambda(A)=1$. Note that in this example
${\mathbb{E}}\\{(\ln\|X\|)^{+}\\}=\infty$, and therefore
${\mathbb{E}}\\{H_{n}\\}=\infty$, for all $n$.

######  Theorem 3.

In this setup, $\lim_{n\rightarrow\infty}H_{n}=\infty$ in probability.

##  3 Proofs

###### Proof of Theorem 1.

Put

$\displaystyle\bar{f}_{h}(x)=\frac{\mu(B(x,h))}{\lambda(B(x,h))}=\frac{\int_{B(x,h)}f(z)dz}{\lambda(B(x,h))},$

where $B(x,h)$ stands for the sphere centered at $x$ and having the radius
$r$. Then,

$\displaystyle H_{n}-H(f)$
$\displaystyle=\frac{1}{n}\sum_{i=1}^{n}\ln((n-1)\lambda(B(X_{i},R_{n,i}(X_{i}))))+C_{E}-H(f)$
$\displaystyle=-\frac{1}{n}\sum_{i=1}^{n}\ln\frac{\mu(B(X_{i},R_{n,i}(X_{i})))}{\lambda(B(X_{i},R_{n,i}(X_{i})))}-H(f)+\frac{1}{n}\sum_{i=1}^{n}\ln((n-1)\mu(B(X_{i},R_{n,i}(X_{i}))))+C_{E}$
$\displaystyle=\tilde{H}_{n}-H(f)+M_{n}+C_{E},$

where

$\displaystyle\tilde{H}_{n}$
$\displaystyle=-\frac{1}{n}\sum_{i=1}^{n}\ln\bar{f}_{R_{n,i}(X_{i})}(X_{i}),$

and

$\displaystyle M_{n}$
$\displaystyle=\frac{1}{n}\sum_{i=1}^{n}\ln((n-1)\mu(B(X_{i},R_{n,i}(X_{i})))).$

Biau and Devroye [4] showed that the distribution of $M_{n}$ does not depend
on the density $f$, and ${\mathbb{E}}\\{M_{n}\\}=-C_{E}+O(1/n)$ and
${\mathbb{V}ar}(M_{n})=O(1/n)$. The problem left is to show

$\displaystyle M_{n}-{\mathbb{E}}\\{M_{n}\\}\to 0$ (8)

a.s. and

$\displaystyle\tilde{H}_{n}\to H(f)$ (9)

a.s.
The proof of (8) relies on the following extension of the Efron-Stein
inequality for the centered higher moments:

######  Lemma 1.

(Devroye et al. [9]) Let $Z=(Z_{1},\ldots,Z_{n})$ be a collection of
independent random variables taking values in some measurable set $A$ and
denote by $Z^{(i)}=(Z_{1},\ldots,Z_{i-1},Z_{i+1},\ldots,Z_{n})$ the collection
with the $i$-th random variable dropped. Let $f:A^{n}\to{\mathbb{R}}$ be a
measurable real-valued function and the function
$g_{i}:A^{n-1}\to{\mathbb{R}}$ is obtained from $f$ by dropping the $i$-th
argument, $i=1,\dots,n$. Then for any integer $q\geq 1$,

$\displaystyle{\mathbb{E}}\left[(f(Z)-{\mathbb{E}}f(Z))^{2q}\right]\leq(cq)^{q}{\mathbb{E}}\left[\left(\sum_{i=1}^{n}\left(f(Z)-g_{i}(Z^{(i)})\right)^{2}\right)^{q}\right]$
$\displaystyle\qquad+(cq)^{q}{\mathbb{E}}\left[\left(\sum_{i=1}^{n}{\mathbb{E}}\left[\left(f(Z)-g_{i}(Z^{(i)})\right)^{2}\mid
Z_{1},\dots,Z_{i-1},Z_{i+1},\dots,Z_{n}\right]\right)^{q}\right],$ (10)

with a universal constant $c<5.1$.

For the term $M_{n}-{\mathbb{E}}\\{M_{n}\\}$, define $M_{n}^{(i)}$ as $M_{n}$
without the $i$-th term. We apply Lemma 1 with $q=2$:

$\displaystyle{\mathbb{E}}\left[\left(M_{n}-{\mathbb{E}}\\{M_{n}\\}\right)^{4}\right]$
$\displaystyle\leq(c2)^{2}{\mathbb{E}}\left[\left(\sum_{i=1}^{n}\left(M_{n}-M_{n}^{(i)}\right)^{2}\right)^{2}\right]$
$\displaystyle\quad+(c2)^{2}{\mathbb{E}}\left[\left(\sum_{i=1}^{n}{\mathbb{E}}\left[\left(M_{n}-M_{n}^{(i)}\right)^{2}\mid
X_{1},\dots,X_{i-1},X_{i+1},\dots,X_{n}\right]\right)^{2}\right]$
$\displaystyle\leq
2^{3}c^{2}n^{2}{\mathbb{E}}\left[\left(M_{n}-M_{n}^{(n)}\right)^{4}\right]$
$\displaystyle=2^{3}c^{2}n^{2}{\mathbb{E}}\left[\left(M_{n}-\frac{n-1}{n}M_{n-1}\right)^{4}\right].$

Noting that

$\displaystyle\left(M_{n}-\frac{n-1}{n}M_{n-1}\right)^{4}$
$\displaystyle=\frac{1}{n^{4}}\left(\sum_{i=1}^{n}\ln((n-1)\mu(B(X_{i},R_{n,i}(X_{i}))))-\sum_{i=1}^{n-1}\ln((n-2)\mu(B(X_{i},R_{n-1,i}(X_{i}))))\right)^{4}$
$\displaystyle=\frac{1}{n^{4}}\Big{(}-\ln((n-1)\mu(B(X_{n},R_{n,n}(X_{n}))))+(n-1)\ln\frac{n-2}{n-1}$
$\displaystyle\quad+\sum_{i=1}^{n-1}\ln\frac{\mu(B(X_{i},R_{n-1,i}(X_{i})))}{\mu(B(X_{i},R_{n,i}(X_{i})))}{\mathbb{I}}_{R_{n,i}(X_{i})<R_{n-1,i}(X_{i})}\Big{)}^{4},$

the $c_{r}$-inequality and Jensen’s inequality imply that

$\displaystyle{\mathbb{E}}\left[\left(M_{n}-{\mathbb{E}}\\{M_{n}\\}\right)^{4}\right]$
$\displaystyle\leq\frac{2^{3}3^{3}c^{2}}{n^{2}}\Big{(}{\mathbb{E}}\left[\left(\ln((n-1)\mu(B(X_{n},R_{n,n}(X_{n}))))\right)^{4}\right]+1$
$\displaystyle+{\mathbb{E}}\left[\left(\sum_{i=1}^{n-1}\ln\frac{\mu(B(X_{i},R_{n-1,i}(X_{i})))}{\mu(B(X_{i},R_{n,i}(X_{i})))}{\mathbb{I}}_{R_{n,i}(X_{i})<R_{n-1,i}(X_{i})}\right)^{4}\right]\Big{)}$
$\displaystyle\leq\frac{6^{3}c^{2}}{n^{2}}\Big{(}{\mathbb{E}}\left[\left(\ln((n-1)\mu(B(X_{n},R_{n,n}(X_{n}))))\right)^{4}\right]+1$
$\displaystyle+{\mathbb{E}}\left[\left(\sum_{i=1}^{n-1}{\mathbb{I}}_{R_{n,i}(X_{i})<R_{n-1,i}(X_{i})}\right)^{3}\sum_{i=1}^{n-1}\left(\ln\frac{\mu(B(X_{i},R_{n-1,i}(X_{i})))}{\mu(B(X_{i},R_{n,i}(X_{i})))}\right)^{4}\right]\Big{)}.$

For any $x$, $\mu(B(x,\|x-X_{i}\|))$ is uniformly distributed on $[0,1]$ (see
Section 1.2 in [4]), and therefore

$\displaystyle(n-1)\mu(B(X_{n},R_{n,n}(X_{n})))$
$\displaystyle=(n-1)\mu(B(X_{n},\min_{1\leq i\leq n-1}\|X_{i}-X_{n}\|))$
$\displaystyle=(n-1)\min_{1\leq i\leq n-1}\mu(B(X_{n},\|X_{i}-X_{n}\|)).$

It implies, that for given $X_{n}$

$\displaystyle(n-1)\mu(B(X_{n},R_{n,n}(X_{n})))$
$\displaystyle\stackrel{{\scriptstyle{\cal L}}}{{=}}(n-1)\min_{1\leq i\leq
n-1}U_{i},$

where $\stackrel{{\scriptstyle{\cal L}}}{{=}}$ denotes equality in
distribution, and $U_{1},\dots,U_{n-1}$ are i.i.d. uniform on $[0,1]$. Thus,

$\displaystyle{\mathbb{E}}\left[\left(\ln((n-1)\mu(B(X_{n},R_{n,n}(X_{n}))))\right)^{4}\right]$
$\displaystyle={\mathbb{E}}\left[\left(\ln\left((n-1)\min_{1\leq i\leq
n-1}U_{i}\right)\right)^{4}\right]=O(1).$

Lemma 20.6 in [4] yields

$\displaystyle\sum_{i=1}^{n-1}{\mathbb{I}}_{R_{n,i}(X_{i})<R_{n-1,i}(X_{i})}$
$\displaystyle=\sum_{i=1}^{n-1}{\mathbb{I}}_{\|X_{i}-X_{n}\|<R_{n-1,i}(X_{i})}\leq\gamma_{d}$

a.s., where $\gamma_{d}$ is the minimal number of cones of angle $\pi/6$ that
cover ${\mathbb{R}}^{d}$. Thus,

$\displaystyle{\mathbb{E}}\left[\left(M_{n}-{\mathbb{E}}\\{M_{n}\\}\right)^{4}\right]$
$\displaystyle\leq\frac{6^{3}c^{2}}{n^{2}}\left(O(1)+\gamma_{d}^{3}(n-1){\mathbb{E}}\left[\left(\ln\frac{\mu(B(X_{1},R_{n-1,1}(X_{1})))}{\mu(B(X_{1},R_{n,1}(X_{1})))}\right)^{4}\right]\right).$

One has

$\displaystyle(n-1){\mathbb{E}}\left[\left(\ln\frac{\mu(B(X_{1},R_{n-1,1}(X_{1})))}{\mu(B(X_{1},R_{n,1}(X_{1})))}\right)^{4}\right]$
$\displaystyle=(n-1)\int_{0}^{\infty}{\mathbb{P}}\left\\{\left(\ln\frac{\mu(B(X_{1},R_{n-1,1}(X_{1})))}{\mu(B(X_{1},R_{n,1}(X_{1})))}\right)^{4}\geq
s\right\\}ds$
$\displaystyle=(n-1)\int_{0}^{\infty}{\mathbb{E}}\left[{\mathbb{P}}\left\\{\frac{\mu(B(X_{1},R_{n-1,1}(X_{1})))}{\mu(B(X_{1},\|X_{1}-X_{n}\|))}\geq
e^{s^{1/4}}\mid X_{1},\dots,X_{n-1}\right\\}\right]ds$
$\displaystyle=(n-1)\int_{0}^{\infty}{\mathbb{E}}\left[{\mathbb{P}}\left\\{\mu(B(X_{1},R_{n-1,1}(X_{1})))e^{-s^{1/4}}\geq\mu(B(X_{1},\|X_{1}-X_{n}\|))\mid
X_{1},\dots,X_{n-1}\right\\}\right]ds$
$\displaystyle=(n-1)\int_{0}^{\infty}{\mathbb{E}}\left[\mu(B(X_{1},R_{n-1,1}(X_{1})))\right]e^{-s^{1/4}}ds$
$\displaystyle\leq\int_{0}^{\infty}e^{-s^{1/4}}ds.$

These limit relations imply

$\displaystyle{\mathbb{E}}\left[\left(M_{n}-{\mathbb{E}}\\{M_{n}\\}\right)^{4}\right]=O(1/n^{2})~{},$

which together with the Borel-Cantelli Lemma yields (8).
In the proof of (9) we apply Breiman’s generalized ergodic theorem (see Lemma
27.2 in [15]):

######  Lemma 2.

Let $X_{1},X_{2},\dots$ be a stationary and ergodic sequence. If
$F_{n}=F_{n}(\\{X_{i}\\})$, $n=1,2,\dots$ are random functions such that

$\displaystyle F_{n}(X_{1})\to F(X_{1})$ (11)

a.s. and

$\displaystyle{\mathbb{E}}\\{\sup_{n}|F_{n}(X_{1})|\\}<\infty,$ (12)

then

$\displaystyle\frac{1}{n}\sum_{i=1}^{n}F_{n}(X_{i})\to{\mathbb{E}}\\{F(X_{1})\\}$
(13)

a.s.

If $X^{\prime}_{n}(x)$ stands for the second nearest neighbor of $x$ among
$X_{1},\dots,X_{n}$, then $R_{n,i}(X_{i})=\|X^{\prime}_{n}(X_{i})-X_{i}\|$ and
so

$\displaystyle\bar{f}_{R_{n,i}(X_{i})}(X_{i})$
$\displaystyle=\bar{f}_{\|X^{\prime}_{n}(X_{i})-X_{i}\|}(X_{i})$

and

$\displaystyle\tilde{H}_{n}$
$\displaystyle=-\frac{1}{n}\sum_{i=1}^{n}\ln\bar{f}_{\|X^{\prime}_{n}(X_{i})-X_{i}\|}(X_{i}).$

Therefore, (9) means that

$\displaystyle-\frac{1}{n}\sum_{i=1}^{n}\ln\bar{f}_{\|X^{\prime}_{n}(X_{i})-X_{i}\|}(X_{i})\to
H(f)$ (14)

a.s. Defining

$\displaystyle F_{n}(x)=-\ln\bar{f}_{\|X^{\prime}_{n}(x)-x\|}(x)$

and

$\displaystyle F(x)=-\ln f(x),$

we verify the conditions of Lemma 2. The Lebesgue differentiation theorem (cf.
Theorem 20.18 in [4]) yields that

$\displaystyle\lim_{r\downarrow 0}\bar{f}_{r}(x)=f(x)$

for $\lambda$-almost all $x$. The Cover-Hart theorem (cf. Lemma 2.2 in [4])
implies

$\displaystyle\|X^{\prime}_{n}(x)-x\|\to 0$

a.s. for $\mu$-almost all $x$. As $\mu$ is absolutely continuous with respect
to $\lambda$, these limit relations result in

$\displaystyle\bar{f}_{\|X^{\prime}_{n}(x)-x\|}(x)\to f(x)$

a.s. for $\mu$-almost all $x$, from which (11) follows. Let $L$ denote an
upper bound on $\|X\|$. Introduce the Hardy-Littlewood maximal functions

$\displaystyle f^{*}(x)=\sup_{h>0}\bar{f}_{h}(x)$

and

$\displaystyle g^{*}(x)=\sup_{2L>h>0}\frac{1}{\bar{f}_{h}(x)}$

(4) implies that

$\displaystyle\int f(x)\ln(f^{*}(x)+1)dx<\infty,$ (15)

while if, in addition, $X$ is bounded, then

$\displaystyle\int f(x)\ln(g^{*}(x)+1)dx<\infty,$ (16)

see page 82 in [4]. Note that (16) is the only item in the proof, where the
boundedness of $X$ is used. Thus,

$\displaystyle|\ln\bar{f}_{\|X^{\prime}_{n}(x)-x\|}(x)|$
$\displaystyle=(\ln\bar{f}_{\|X^{\prime}_{n}(x)-x\|}(x))^{+}+\left(\ln\frac{1}{\bar{f}_{\|X^{\prime}_{n}(x)-x\|}(x)}\right)^{+}$
$\displaystyle\leq\ln(f^{*}(x)+1)+\ln(g^{*}(x)+1),$

and so (15) and (16) result in

$\displaystyle{\mathbb{E}}\\{\sup_{n}|\ln\bar{f}_{\|X^{\prime}_{n}(X_{1})-X_{1}\|}(X_{1})|\\}$
$\displaystyle\leq\int f(x)\ln(f^{*}(x)+1)dx+\int
f(x)\ln(g^{*}(x)+1)dx<\infty,$

which yields (12), and the conditions of Lemma 2 are verified.
Note, that similarly to the proof of (8), we can show the universal strong law
of the sum nearest neighbor balls: for any density $f$,

$\displaystyle\sum_{i=1}^{n}\mu\left(B\left(X_{i},\min_{j\neq i,j\leq
n}\|X_{i}-X_{j}\|\right)\right)$ $\displaystyle\to 1$

a.s. $\Box$

###### Proof of Theorem 2.

First we have to show that the expectation ${\mathbb{E}}\\{H_{n}\\}$ and
equivalently ${\mathbb{E}}\\{\tilde{H}_{n}\\}$ exist. Jensen’s inequality
implies that

$\displaystyle{\mathbb{E}}\\{(\tilde{H}_{n})^{-}\\}$
$\displaystyle={\mathbb{E}}\left\\{\left(-\frac{1}{n}\sum_{i=1}^{n}\ln\bar{f}_{R_{n,i}(X_{i})}(X_{i})\right)^{-}\right\\}$
$\displaystyle\geq\frac{1}{n}\sum_{i=1}^{n}{\mathbb{E}}\left\\{\left(-\ln\bar{f}_{R_{n,i}(X_{i})}(X_{i})\right)^{-}\right\\}$
$\displaystyle={\mathbb{E}}\left\\{\left(-\ln\bar{f}_{R_{n,1}(X_{1})}(X_{1})\right)^{-}\right\\}$
$\displaystyle\geq-\int f(x)(\ln f^{*}(x))^{+}dx$ $\displaystyle>-\infty,$

when

$\displaystyle\int f(x)\ln\frac{f^{*}(x)}{f(x)}dx<\infty.$ (17)

Choose $0<L<\mathop{\rm ess\,sup}_{x}f(x)$. Jensen’s inequality implies

$\displaystyle\int
f(x)\ln\frac{f^{*}(x)}{f(x)}{\mathbb{I}}_{f(x)>L}dx\leq\left(\int
f(x){\mathbb{I}}_{f(x)>L}dx\right)\ln\frac{\int
f^{*}(x){\mathbb{I}}_{f(x)>L}dx}{\int f(x){\mathbb{I}}_{f(x)>L}dx}<\infty,$

because (4) together with

$\displaystyle\lambda(\\{x:f(x)>L\\})<\infty$

yields

$\displaystyle\int f^{*}(x){\mathbb{I}}_{f(x)>L}dx<\infty,$

see Fefferman and Stein [11]. Furthermore,

$\displaystyle\int f(x)\ln\frac{f^{*}(x)}{f(x)}{\mathbb{I}}_{f(x)\leq L}dx$
$\displaystyle=\int f(x)\ln f^{*}(x){\mathbb{I}}_{f(x)\leq L}dx-\int f(x)\ln
f(x){\mathbb{I}}_{f(x)\leq L}dx$ $\displaystyle\leq
L\int\ln\max\\{f^{*}(x),1\\}dx-\int f(x)\ln f(x){\mathbb{I}}_{f(x)\leq L}dx.$

Fefferman and Stein [11] proved that

$\displaystyle\lambda(\\{x:f^{*}(x)>t\\})\leq\frac{c}{t},$ (18)

with $t>0$ such that $c$ depends only on the dimension $d$, see also (a) of
Lemma 10.47 in [36]. By (18),

$\displaystyle\int\ln\max\\{f^{*}(x),1\\}dx$
$\displaystyle=\int_{0}^{\infty}\lambda(\\{x:\ln\max\\{f^{*}(x),1\\}>t\\})dt$
$\displaystyle=\int_{0}^{\infty}\lambda(\\{x:\max\\{f^{*}(x),1\\}>e^{t}\\})dt$
$\displaystyle=\int_{0}^{\infty}\lambda(\\{x:f^{*}(x)>e^{t}\\})dt$
$\displaystyle\leq\int_{0}^{\infty}\frac{c}{e^{t}}dt$ $\displaystyle=c.$

Thus, (17) is verified and so we proved that ${\mathbb{E}}\\{\tilde{H}_{n}\\}$
exists.
Assume that ${\mathbb{E}}\\{(\ln\|X\|)^{+}\\}=\infty$. Then, for any
$x\in{\mathbb{R}}^{d}$, ${\mathbb{E}}\\{(\ln\|X-x\|)^{+}\\}=\infty$ and
therefore ${\mathbb{E}}\\{(\ln
R_{2,1}(X_{1}))^{+}\\}={\mathbb{E}}\\{(\ln\|X_{1}-X_{2}\|)^{+}\\}=\infty$.
Next we show that ${\mathbb{E}}\\{(\ln
R_{n,1}(X_{1}))^{+}\\}={\mathbb{E}}\\{\min_{2\leq i\leq
n}(\ln\|X_{1}-X_{i}\|)^{+}\\}=\infty$, too: Find $r$ such that
$\mu(B(0,r))=1/2$. Then

$\displaystyle{\mathbb{E}}\left\\{\left(\ln
R_{n,1}(X_{1})\right)^{+}\right\\}$
$\displaystyle\geq{\mathbb{E}}\left\\{\left(\ln\frac{\|X_{1}\|}{2}\right)^{+}{\mathbb{I}}_{\|X_{1}\|\geq
2r}{\mathbb{I}}_{X_{2},\dots,X_{n}\in B(0,r)}\right\\}$
$\displaystyle=\frac{1}{2^{n-1}}{\mathbb{E}}\left\\{\left(\ln\frac{\|X_{1}\|}{2}\right)^{+}{\mathbb{I}}_{\|X_{1}\|\geq
2r}\right\\}$ $\displaystyle=\infty.$

Thus,

$\displaystyle{\mathbb{E}}\\{\tilde{H}_{n}\\}$
$\displaystyle=-\int{\mathbb{E}}\left\\{\ln\bar{f}_{R_{n,1}(x)}(x)\right\\}f(x)dx$
$\displaystyle\geq\int{\mathbb{E}}\left\\{\left(\ln\frac{\lambda(B(x,R_{n,1}(x)))}{\mu(B(x,R_{n,1}(x)))}\right)^{+}\right\\}f(x)dx$
$\displaystyle\geq\int{\mathbb{E}}\left\\{\left(\ln\lambda(B(x,R_{n,1}(x)))\right)^{+}\right\\}f(x)dx$
$\displaystyle\geq d{\mathbb{E}}\left\\{\left(\ln
R_{n,1}(X_{1})\right)^{+}\right\\}$ $\displaystyle=\infty,$ (19)

which yields the necessary part of the theorem:

$\displaystyle{\mathbb{E}}\\{|\tilde{H}_{n}-H(f)|\\}$ $\displaystyle=\infty.$

Assume that ${\mathbb{E}}\\{(\ln\|X\|)^{+}\\}<\infty$. Notice that

$\displaystyle{\mathbb{E}}\\{H_{n}\\}$
$\displaystyle={\mathbb{E}}\\{\ln((n-1)R_{n,1}(X_{1})^{d}v_{d})\\}+C_{E}$
$\displaystyle\leq\ln(n-1)+{\mathbb{E}}\\{\ln(R_{2,1}(X_{1})^{d}v_{d})\\}+C_{E}$
$\displaystyle\leq\ln(n-1)+{\mathbb{E}}\\{(\ln(\|X_{2}-X_{1}\|^{d}v_{d}))^{+}\\}+C_{E}$
$\displaystyle<\infty.$ (20)

(3) and (3) means that ${\mathbb{E}}\\{H_{n}\\}<\infty$ iff (7) holds. By the
proof of Theorem 1, (6) is equivalent to

$\displaystyle{\mathbb{E}}\\{|\tilde{H}_{n}-H(f)|\\}$ $\displaystyle\to 0.$
(21)

Note that for $a\in{\mathbb{R}}$, $|a|=2a^{+}-a$ and thus, one has

$\displaystyle{\mathbb{E}}\\{|\tilde{H}_{n}-H(f)|\\}$
$\displaystyle\leq\int{\mathbb{E}}\left\\{\left|\ln\frac{\bar{f}_{R_{n,1}(x)}(x)}{f(x)}\right|\right\\}f(x)dx$
$\displaystyle=2\int{\mathbb{E}}\left\\{\left(\ln\frac{\bar{f}_{R_{n,1}(x)}(x)}{f(x)}\right)^{+}\right\\}f(x)dx+{\mathbb{E}}\\{\tilde{H}_{n}\\}-H(f).$

We show that

$\displaystyle\int{\mathbb{E}}\left\\{\left(\ln\frac{\bar{f}_{R_{n,1}(x)}(x)}{f(x)}\right)^{+}\right\\}f(x)dx\to
0$ (22)

and

$\displaystyle{\mathbb{E}}\\{\tilde{H}_{n}\\}=-\int{\mathbb{E}}\left\\{\ln\bar{f}_{R_{n,1}(x)}(x)\right\\}f(x)dx\to
H(f).$ (23)

Concerning (22), we have a domination:

$\displaystyle\left(\ln\frac{\bar{f}_{R_{n,1}(x)}(x)}{f(x)}\right)^{+}$
$\displaystyle\leq\left(\ln\frac{f^{*}(x)}{f(x)}\right)^{+}=\ln\frac{f^{*}(x)}{f(x)},$

and therefore (17) and the pointwise convergence yield (22).
With respect to (23), note that (22) implies that

$\displaystyle(H(f)-{\mathbb{E}}\\{\tilde{H}_{n}\\})^{+}$
$\displaystyle\leq\int{\mathbb{E}}\left\\{\left(\ln\frac{\bar{f}_{R_{n,1}(x)}(x)}{f(x)}\right)^{+}\right\\}f(x)dx\to
0$

and therefore

$\displaystyle\liminf_{n}{\mathbb{E}}\\{\tilde{H}_{n}\\}\geq H(f).$

So, we need to show

$\displaystyle\limsup_{n}{\mathbb{E}}\\{\tilde{H}_{n}\\}\leq H(f).$ (24)

For

$\displaystyle g^{*}_{r}(x)=\inf_{0<h\leq r}\bar{f}_{h}(x),$

we have that

$\displaystyle{\mathbb{E}}\\{\tilde{H}_{n}\\}$
$\displaystyle=-{\mathbb{E}}\left\\{\int
f(x)\ln\bar{f}_{R_{n,1}(x)}(x)dx\right\\}$
$\displaystyle=-{\mathbb{E}}\left\\{\int{\mathbb{I}}_{R_{n,1}(x)\leq
r}f(x)\ln\bar{f}_{R_{n,1}(x)}(x)dx\right\\}-{\mathbb{E}}\left\\{\int{\mathbb{I}}_{R_{n,1}(x)>r}f(x)\ln\bar{f}_{R_{n,1}(x)}(x)dx\right\\}$
$\displaystyle\leq-\int f(x)\ln g^{*}_{r}(x)dx+{\mathbb{E}}\left\\{\int
f(x)\left(\ln\frac{\lambda(B(x,R_{n,1}(x)))}{\mu(B(x,r))}\right)^{+}dx\right\\}.$

The integrand of the last term tends to $0$ a.s. for $\mu$-almost all $x$ and
the convergence is dominated by

$\displaystyle{\mathbb{E}}\left\\{\int
f(x)\left(\ln\frac{\lambda(B(x,R_{2,1}(x)))}{\mu(B(x,r))}\right)^{+}dx\right\\}<\infty,$

which follows from

$\displaystyle{\mathbb{E}}\\{\tilde{H}_{2}\\}$
$\displaystyle={\mathbb{E}}\left\\{\int
f(x)\ln\frac{\lambda(B(x,R_{2,1}(x)))}{\mu(B(x,R_{2,1}(x)))}dx\right\\}<\infty.$

Thus, by the dominated convergence theorem

$\displaystyle{\mathbb{E}}\left\\{\int
f(x)\left(\ln\frac{\lambda(B(x,R_{n,1}(x)))}{\mu(B(x,r))}\right)^{+}dx\right\\}\to
0,$

and so

$\displaystyle\limsup_{n}{\mathbb{E}}\\{\tilde{H}_{n}\\}$
$\displaystyle\leq-\int f(x)\ln g^{*}_{r}(x)dx.$

Therefore,

$\displaystyle\limsup_{n}{\mathbb{E}}\\{\tilde{H}_{n}\\}$
$\displaystyle\leq-\sup_{0<r}\int f(x)\ln g^{*}_{r}(x)dx=-\lim_{r\downarrow
0}\int f(x)\ln g^{*}_{r}(x)dx=H(f).$

Thus, (24) is verified and so the proof of the sufficient part of the theorem
is complete. $\Box$

###### Proof of Theorem 3.

The data can be represented as follows: let $Y_{1},\dots,Y_{n}$ be i.i.d. such
that

$\displaystyle{\mathbb{P}}\\{Y_{i}=j\\}=\Delta_{j}.$

Let $U_{1},\dots,U_{n}$ be i.i.d. uniform on $[0,1]$. Set

$\displaystyle X_{i}=a_{Y_{i}}+\Delta_{Y_{i}}U_{i}.$

We will recall two things from the theory of order statistics:

  * (i)

If $U_{1},\dots,U_{n}$ are i.i.d. uniform on $[0,1]$, then the smallest
neighbor distance $Z^{*}_{n}$ (the smallest 1-spacings) satisfies

$\displaystyle Z^{*}_{n}\to E$

in distribution, where $E$ is standard exponential.

  * (ii)

With probability one,

$\displaystyle\max_{1\leq i\leq n}Y_{i}\geq n^{1/2}$

except finitely often.

###### Proof.

$\displaystyle{\mathbb{P}}\left\\{\max_{1\leq i\leq n}Y_{i}\leq
n^{1/2}\right\\}$ $\displaystyle=(1-{\mathbb{P}}\\{Y_{i}>n^{1/2}\\})^{n}\leq
e^{-n^{1/2}}.$

Apply Borel-Cantelli.

  * (iii)

If $Y^{**},Y^{*}$ are the largest and second largest $Y_{i}$’s, then

$\displaystyle{\mathbb{P}}\\{Y^{**}=Y^{*}\\}$ $\displaystyle\to 0.$

###### Proof.

$\displaystyle{\mathbb{P}}\\{Y^{**}=Y^{*}\\}$
$\displaystyle\leq\binom{n}{2}{\mathbb{P}}\left\\{Y_{1}=Y_{2}\geq\max_{3\leq
i\leq n}Y_{i}\right\\}$ $\displaystyle\leq
n^{2}\sum_{i=1}^{\infty}\Delta_{i}^{2}(1-1/(i+1))^{n-2}$ $\displaystyle\leq
n^{2}\sum_{i\leq
n^{5/6}}\Delta_{i}^{2}e^{-(n-2)/(i+1)}+n^{2}\sum_{i>n^{5/6}}\Delta_{i}^{2}.$

The first term on the right hand side is less than

$\displaystyle n^{2}\sum_{i\leq n^{5/6}}e^{-(n-2)/(n^{5/6}+1)}$
$\displaystyle=e^{-n^{1/6}(1+o(1))}\to 0,$

while the second term on the right hand side is

$\displaystyle O(n^{2}/n^{5/6})$ $\displaystyle=O(1/\sqrt{n})\to 0.$

For the sake of simplicity, consider the negative of the estimate in (3)
without the bias correction:

$\displaystyle\ell_{n}=\frac{1}{n}\sum_{i=1}^{n}\log_{2}\frac{1}{nZ_{i}},$
(25)

where $Z_{i}=\min_{j\neq i,j\leq n}|X_{i}-X_{j}|$. We show that
$\ell_{n}\to-\infty$ in probability, which implies the theorem. Let $Y^{**}$
and $Y^{*}$ be the $Y$-values of the largest and second largest $X_{i}$’s. Let
$Z^{**}$ be the nearest neighbor distance for to largest $X_{i}$’s. This is
also the distance between the two largest $X_{i}$’s. If $Y^{**}\neq Y^{*}$,
then

$\displaystyle Z^{**}$ $\displaystyle\geq
a_{Y^{**}}-a_{Y^{*}}-\Delta_{Y^{*}}\geq\frac{1}{2}a_{Y^{**}}=\frac{1}{2}2^{2^{Y^{**}}}.$

Furthermore, all other nearest neighbor distances are $\geq$ (in distribution)
the minimal distance between $n$ uniform order statistics (by pushing the
intervals of $A$ together), and this is $(1/n^{2})$ times something that tends
in law to a standard exponential $E$. So, by (ii)

$\displaystyle\ell_{n}$
$\displaystyle\leq\frac{1}{n}\log_{2}\left[\frac{2}{2^{2^{Y^{**}}}}\right]+\log_{2}\left[\frac{n}{E+o_{P}(1)}\right]$
$\displaystyle=-\frac{2^{Y^{**}}-1}{n}+O_{P}(\log_{2}n)$
$\displaystyle\leq-\frac{1}{n}{\mathbb{I}}_{Y^{**}\leq\sqrt{n}}-\frac{2^{\sqrt{n}}-1}{n}{\mathbb{I}}_{Y^{**}>\sqrt{n}}+O_{P}(\log_{2}n).$

Thus,

$\displaystyle{\mathbb{P}}\left\\{\ell_{n}>-\frac{2^{\sqrt{n}}}{2n}\right\\}$
$\displaystyle\leq{\mathbb{P}}\\{Y^{**}=Y^{*}\\}+{\mathbb{P}}\\{Y^{**}\leq\sqrt{n}\\}\to
0,$

where we applied (iii). $\Box$

## References

  * [1] A. R. Barron, L. Györfi, E. C. van der Meulen. Distribution estimation consistent in total variation and two types of information divergence. IEEE Trans. Information Theory, 38:1437–1454, 1992.
  * [2] J. Beirlant, E. J. Dudewicz, L. Györfi, E. C. van der Meulen. Nonparametric entropy estimation: an overview, International J. Mathematical and Statistical Sciences, 6:17–39, 1997.
  * [3] T. B. Berrett, R. J. Samworth and M. Yuan. Efficient multivariate entropy estimation via k-nearest neighbour distances. Annals of Statistics, 47:288–318, 2019.
  * [4] G. Biau and L. Devroye. _Lectures on the Nearest Neighbor Method._ Springer—Verlag, Cham, 2015.
  * [5] L. Birgé and P. Massart. Estimation of integral functionals of a density. The Annals of Statistics, 23:11–29, 1995.
  * [6] C. Chesneau, F. Navarro, O. S. Serea. A note on the adaptive estimation of the differential entropy by wavelet methods. Commentationes Mathematicae Universitatis Carolinae, 58:87–100, 2017.
  * [7] S. Delattre and N. Fournier. On the Kozachenko–Leonenko entropy estimator. J. Statistical Planning and Inference, 185:69-–93, 2017.
  * [8] B. Delyon and A. Juditsky. On minimax wavelet estimators. Applied Computational Harmonic Analysis, 3:215–228, 1996.
  * [9] L. Devroye, L. Györfi, G. Lugosi, H. Walk. A nearest neighbor estimate of the residual variance. Electronic Journal of Statistics, 12:1752–1778, 2018.
  * [10] D. L. Donoho, I. M. Johnstone, G. Kerkyacharian and D. Picard. Density estimation by wavelet thresholding. Annals of Statistics, 24:508–539, 1996.
  * [11] C. Fefferman, E.M. Stein. Some maximal inequalities. Am. J. Math. 93:107–115, 1971.
  * [12] W. Gao, S. Oh and P. Viswanath. Density functional estimators with k-nearest neighbor bandwidths. In Proceedings of the 2017 IEEE International Symposium on Information Theory (ISIT), Aachen, Germany, 25–30 June 2017; pp. 1351–1355, 2017.
  * [13] W. Gao, S. Oh and P. Viswanath. Breaking the bandwidth barrier: Geometrical adaptive entropy estimation. In Proceedings of the Advances in Neural Information Processing Systems 29 (NIPS 2016), Barcelona, Spain, 5–10 December 2016; pp. 2460–2468, 2016.
  * [14] M. Godavarti. Convergence of differential entropies. IEEE Transactions on Information Theory, 50:1–6, 2004.
  * [15] L. Györfi, M. Kohler, A. Krzyżak and H. Walk. A Distribution-Free Theory of Nonparametric Regression, Springer–Verlag, New York, 2002.
  * [16] L. Györfi, I. Páli and E. C. van der Meulen. There is no universal source code for infinite alphabet. IEEE Trans. Information Theory, 40:267–271, 1994.
  * [17] L. Györfi and E. C. van der Meulen. On the nonparametric estimation of entropy functional. In Nonparametric Functional Estimation and Related Topics, Ed. G. Roussas, Kluwer Academic Publisher, pages 81–95, 1991.
  * [18] P. Hall and S. C. Morton. On the estimation of entropy. Annals of the Institute of Statistical Mathematics, 45:69–88, 1993
  * [19] Y. Han, J. Jiao, T. Weissman, Y. Wu. Optimal rates of entropy estimation over Lipschitz balls. Ann. Statist. 48:3228–3250, 2020.
  * [20] H. Joe. Estimation of entropy and other functionals of a multivariate density. Annals of the Institute of Statistical Mathematics, 41:683–697, 1989.
  * [21] K. Kandasamy, A. Krishnamurthy, B. Póczos and L. Wasserman. Nonparametric von Mises estimators for entropies, divergences and mutual informations. In Advances in Neural Information Processing Systems, pages 397–405, 2015
  * [22] L. F. Kozachenko and N. N. Leonenko. Sample estimate of entropy of a random vector. Problems of Information Transmission, 23:95–101, 1987.
  * [23] A. Krishnamurthy, K. Kandasamy, B. Póczos and L. Wasserman. Nonparametric estimation of Rényi divergence and friends. In International Conference on Machine Learning, pages 919–927, 2014
  * [24] W. M. Lord, J. Sun and E. M. Bollt. Geometric k-nearest neighbor estimation of entropy and mutual information. Chaos: An Interdisciplinary Journal of Nonlinear Science, 28, 033114, 2018.
  * [25] U. Ozertem, I. Uysal and D. Erdogmus. Continuously differentiable sample-spacing entropy estimates. IEEE Trans. Neural Networks, 19:1978–1984, 2008.
  * [26] L. Paninski and M. Yajima. Undersmoothed kernel entropy estimators. IEEE Transactions on Information Theory, 54:4384–4388, 2008.
  * [27] S. Shwartz, M. Zibulevsky and Y. Y. Schechner. Fast kernel entropy estimation and optimization. Signal Process., 85:1045–1058, 2005.
  * [28] J. Silva and S. Narayanan. Nonproduct data-dependent partitions for mutual information estimation: strong consistency and applications. _IEEE Trans. Signal Processing_ , 58:3497–3511, 2010.
  * [29] H. Singh, N. Misra. V. Hnizdo, A. Fedorowicz and E. Demchuk. Nearest neighbor estimates of entropy. Am. J. Math. Manag. Sci. 23:301–321, 2003.
  * [30] S. Singh and B. Póczos. Finite-sample analysis of fixed-k nearest neighbor density functional estimators. In Advances in Neural Information Processing Systems, pages 1217–1225, 2016.
  * [31] K. Sricharan, R. Raich and A. O. Hero. Estimation of nonlinear functionals of densities with confidence. IEEE Transactions on Information Theory, 58:4135–4159, 2012
  * [32] K. Sricharan, D. Wei and A. O. Hero. Ensemble estimators for multivariate entropy estimation. IEEE Transactions on Information Theory, 59:4374–4388, 2013.
  * [33] D. Stowell and M. D. Plumbley. Fast multidimensional entropy estimation by k-d partitioning. IEEE Signal Processing Letters, 16:537–540, 2009.
  * [34] A. B. Tsybakov and E. C. van der Meulen. Root-n consistent estimators of entropy for densities with unbounded support. Scand. J. Statist., 23:75–83, 1994.
  * [35] Q. Wang, S. R. Kulkarni and S. Verdu. Divergence estimation of continuous distributions based on data-dependent partitions. _IEEE Trans. Information Theory_ , 51:3064–3074, 2005.
  * [36] R. L. Wheeden and A. Zygmund. _Measure and Integral._ Marcel Dekker, New York, 1977.


# COVID-19 in Africa – outbreak despite interventions?

Malte Schröder  Chair for Network Dynamics, Cluster of Excellence Physics of
Life, Institute for Theoretical Physics and Center for Advancing Electronics
Dresden (cfaed), Technical University of Dresden, Helmholtzstr. 18, 01069
Dresden, Germany  Andreas Bossert  Center of Methods in Social Sciences,
Department of Social Sciences, Georg August University Göttingen, Goßlerstraße
19, 37073 Göttingen, Germany  Next Generation Mobility (NGM), Department of
Dynamics of Complex Fluids, Max-Planck-Institute for Dynamics and Self-
Organization, Am Fassberg 17, 37077 Göttingen, Germany  Moritz Kersting  Next
Generation Mobility (NGM), Department of Dynamics of Complex Fluids, Max-
Planck-Institute for Dynamics and Self-Organization, Am Fassberg 17, 37077
Göttingen, Germany  Chair of Statistics, Department of Economics, Georg August
University Göttingen, Humboldtallee 3, 37073 Göttingen, Germany  Sebastian
Aeffner  Institute for Diagnostic and Interventional Radiology, University
Medical Center Göttingen, Robert-Koch-Straße 40, 37075 Göttingen, Germany
Justin Coetzee  GoMetro, 10 Church Street, Durbanville, Cape Town, South
Africa, 7550  Marc Timme  Chair for Network Dynamics, Cluster of Excellence
Physics of Life, Institute for Theoretical Physics and Center for Advancing
Electronics Dresden (cfaed), Technical University of Dresden, Helmholtzstr.
18, 01069 Dresden, Germany  Institute for the Dynamics of Complex Systems,
Faculty of Physics, Georg August University of Göttingen, Friedrich-Hund-Platz
1, 37077 Göttingen, Germany  Jan Schlüter  Next Generation Mobility (NGM),
Department of Dynamics of Complex Fluids, Max-Planck-Institute for Dynamics
and Self-Organization, Am Fassberg 17, 37077 Göttingen, Germany  Institute for
the Dynamics of Complex Systems, Faculty of Physics, Georg August University
of Göttingen, Friedrich-Hund-Platz 1, 37077 Göttingen, Germany

###### Abstract

In Africa, while most countries report some COVID-19 cases, the fraction of
reported patients is low, with about $20\,000$ cases compared to the more than
$2.3$ million cases reported globally as of April 18, 2020. Few African
countries have reported case numbers above one thousand, with South Africa
reporting $3\,034$ cases being hit hardest in Sub-Saharan Africa. Several
African countries, especially South Africa, have already taken strong non-
pharmaceutical interventions that include physical distancing, restricted
economic, educational and leisure activities and reduced human mobility
options. The required strengths and overall effectiveness of such
interventions, however, are debated because of simultaneous but opposing
interests in most African countries: strongly limited health care capacities
and testing capabilities largely conflict with pressured national economies
and socio-economic hardships on the individual level, limiting compliance to
intervention targets. Here we investigate implications of interventions on the
COVID-19 outbreak dynamics, focusing on South Africa before and after the
national lockdown enacted on March 27, 2020. Our analysis shows that initial
exponential growth of existing case numbers is consistent with doubling times
of about $2.5$ days. After lockdown, the growth remains exponential, now with
doubling times of 18 days, but still in contrast to subexponential growth
reported for Hubei/China after lockdown. Moreover, a scenario analysis of a
computational data-driven agent based mobility model for the Nelson Mandela
Bay Municipality (with $1.14$ million inhabitants) hints that keeping current
levels of intervention measures and compliance until the end of April is of
insufficient length and still too weak, too unspecific or too inconsistently
complied with to not overload local intensive care capacity. Yet, enduring,
slightly stronger, more specific interventions combined with sufficient
compliance may constitute a viable option for interventions for regions in
South Africa and potentially for large parts of the African continent.

## Executive Summary

Evidence before this study. Several studies have analyzed the ongoing outbreak
of the Corona Virus Disease 2019 (COVID-19) in China and several European
countries. However, conditions in African countries are vastly different and
often fragile, with conflicting limitations of both the health care system and
socio-economic conditions, posing difficult challenges for decisions about
enacting and lifting interventions. These countries are currently in the early
stages of the outbreak and have been reporting a small but rapidly increasing
number of patients diagnosed with COVID-19. Several countries have taken
different intervention measures to counter a large-scale COVID-19 outbreak. In
particular, in South Africa, with the largest number of cases in Sub-Saharan
Africa, case numbers are known to less rapidly increase after national
lockdown on March 27, 2020.

Added value of this study. This study reports a quantitative analysis of the
case number dynamics reported by the World Health Organization and Johns
Hopkins University until including April 18, 2020, both for Africa overall and
South Africa specifically, before and after national lockdown. It also reports
and analyzes results of an agent-based mobility simulation for the Nelson
Mandela Bay Municipality, South Africa ($1.14$ million inhabitants). This case
study relies on detailed large-scale mobility survey data of about 10% of the
population and on estimates of the fractions by which interventions decrease
specific activities. The simulational data on outbreak dynamics thus provide
qualitative order of magnitude estimates of trends consistent with past data.
Combined, both analyses may help to better understand the implications of
interventions on and estimate the dynamics of the number of (critically)
infected patients.

Implications of all the available evidence. The results suggest that current
interventions are not yet sufficient to contain a larger-scale outbreak.
Interventions slightly stronger than those implemented today or a higher
degree of compliance to the enacted lockdown, in combination with longer-
lasting measures than currently announced for South Africa may help bound the
case numbers such that the number of critical patients remains at or below
(and does not massively overburden) the local capacity of intensive care
units. Strategies for strengthening or lifting interventions should be advised
by advanced data analytics and predictive modeling estimates, for instance for
evaluating necessary time intervals and required levels of interventions.
Overall, the study points to a potentially viable chance for effective non-
pharmaceutical countermeasures against COVID-19 epidemics in South Africa,
with suggestions for Health Policy for large parts of the African continent
and, generally, disadvantaged countries and regions.

## Introduction

The severe acute respiratory syndrom coronavirus 2 (SARS-CoV-2) has reached
more than 200 countries and territories across all continents 1, 2. By death
toll, the resulting Corona Virus Disease 2019 (COVID-19) outbreak will likely
soon become the largest pandemic of the 21st century so far 3. There is
currently no specific medical intervention known against SARS-CoV-2 and
preventive vaccination options are not yet available. The resulting vast
number, broad geographical distribution, and intensity of globally enacted
socio-economic interventions is unprecedented in modern human history.

Mainland China was the first region hit by the outbreak in January 2020 and
had taken rapid and severe interventions including an almost complete lockdown
for eleven weeks. It thereby succeeded to suppress the outbreak dynamics to
subexponential growth patterns 4 and in April 2020 is reporting a total of
$83\,500$ cases and at most 130 new cases daily for now more than four weeks.2
As of April 18th, several countries in Europe are reporting more than
$100\,000$ cases each and the United States alone reports above $700\,000$
cases. At the same time, Africa as a continent with a population of $1.3$
billion people as of 2018 5 has reported only about $21\,000$ cases and about
$1\,000$ (approximately $4.8$%) deaths. 6, 7, 2 Of those, the largest number
of COVID-19 patients is reported in South Africa with $3\,034$ cases and 52
(about $1.7$%) deaths as of April 18, 2020.8, 2 Across all these countries,
the total number of cases is rapidly increasing.

Across the African continent, national economic constraints, individual
poverty, low health literacy rates, weaker health care systems and cultural
practices lead to reduced option spaces on personal and governmental levels
and may all contribute to more severe consequences of the COVID-19 outbreak
and negatively influence containment as well as recording, testing and medical
treatment 9. Similar conditions will hold for most countries of the Global
South, calling for particular attention on African countries 10.

In general, health care systems in African countries feature only a small
number of available intensive care units (ICUs) compared to most countries of
the Global North.11, 12 At the same time, African countries are under
particular pressure due to economic constraints on both national and personal
levels. Besides strong repercussions on national economic productivity
expected for any large-scale lockdown, a large fraction of the population is
unable to fully comply with severe lockdown measures due to their personal
financial situation. An African task force for coronavirus preparedness and
response (AFTCOR) has been established to manage these combined and
conflicting constraints both for the current COVID-19 outbreak and for future
preparedness 13. Their work focuses on enabling medical diagnosis and
screening options, clinical treatment of COVID-19 patients, infection
prevention and control in health care facilities, supply chain management, and
the communication of risks to experts and the public. Qualitative and
quantitative data analytics and estimates of the outbreak dynamics and
evaluating containment options essentially underlie but are not in the focus
of their work.

South Africa offers a comparatively high capacity of intensive care units
(ICUs) to respond to outbreaks, with estimates ranging from maximally $7\,195$
ICU beds theoretically in existence to $2\,926$ practically available
nationwide across both public and private sectors 14. The order of magnitude
of these numbers is consistent with earlier reports.15 However, the factually
available ICU beds have likely declined during the past decade necessitating
rationing and triage (prioritisation) decisions that have been frequently
necessary in South Africa even in times before COVID-19, particularly in the
publicly funded health sector.14, 16 Moreover ICU capacity in the private
sector is not readily and generally accessible.

## Influence of lockdown on past case numbers

On March 5, 2020, the first COVID-19 patient has been confirmed in South
Africa and after starting with specific smaller measures from March 15
onwards, the South African government enacted a national lockdown effective
March 27, 2020. This lockdown includes measures such as the complete closure
of childcare, institutions of primary and higher education as well as all
public leisure activities, severe physical distancing rules, an estimated 70%
reduction of shopping, 85% of on-site work force and a 90% reduction in other
activities. An initial formal reduction of shared publicly available mobility
services by about 75% was, after protests, revised to about 30% reduction17
(estimates by GoMetro, South Africa). These shared mobility services provide a
large fraction of transportation and constitute one of the special conditions
in South Africa and many other African countries.18 For instance in South
Africa, instead of formal public transit, transportation is dominated by
private, semi-regulated minibus taxis with typically 15 seats.18 Due to their
mass usage, usually high occupancy and the close contact between passengers in
the vehicles, these mobility services may contribute substantially to the
spread of COVID-19.

Fitting the number of total reported cases in South Africa before and after
the national lockdown (Figure 1) indicates that the lockdown drastically
reduces the relative increase in case numbers, as quantified by the growth
exponent, decreasing from $r=0.32$ per day in the beginning of the outbreak to
about $r=0.27$ per day just before the lockdown and down to $r=0.038$ per day
after the lockdown, reflecting an increase of the doubling time from about
$2.5$ to about $18$ days (Fig. 1, panels A and B). The immediate switch to
slower growth at the date of the official lockdown may be originating from
several factors that remain unknown. For instance, the number of patients
tested per day has substantially increased initially 19, 8 and tests may have
been delayed at the very onset. In any given region, the first person infected
is likely detected only after exhibiting symptoms while later cases may be
identified by preemptive contact tracing and thereby identified as they
appear, ideally before showing symptoms. Other contributing factors may
include stochastic small number fluctuations occurring at the onset of any
epidemic outbreak, already existing awareness of the COVID-19 outbreak and
many individuals taking partial countermeasures before the official national
lockdown.

As the number of cases in South Africa makes up a substantial share of all
reported cases throughout Africa, the effect also becomes visible in the data
for the entire continent (Fig. 1A,B). For Africa as a whole, growth exponents
dropped from about $r=0.22$ to $r=0.086$. The data for Africa suggest a
further decrease of the exponent, ongoing after the South African lockdown.
This downtrending may be associated with measures taken up at different points
in time in the most strongly affected countries of Northern Africa, and the
vastly heterogeneous case numbers, test coverage and reporting of cases across
African countries, all entangling with the reduced number, but still large
share of South African COVID-19 patients.

While the growth exponents have been substantially reduced, between a factor
of $7.1$ (South Africa) and a factor of $2.6$ (all of Africa), the growth
remains exponential, even three weeks into the lockdown. This is in stark
contrast to the outbreak dynamics in Mainland China, where the strict
containment measures of the Hubei region has led to subexponential growth 20
followed by a massive decrease of new case numbers within weeks after lockdown
2. The unbroken exponential growth trend in South Africa is also indicated by
the number of newly infected people per week steeply increasing when displayed
as a function of the total number of infected (Figure 1C), instead of curving
down.

## Modeling future scenarios

The current national lockdown has been extended from an original three weeks
(until April 17, 2020) with relaxations now suggested for the beginning of
May, 2020. We thus ran scenario simulations to estimate future case numbers
and probe responses to different intervention strengths and durations. We
employed a computational data-driven, agent based transport model for the
Nelson Mandela Bay Municipality (NMBM, Eastern Cape, South Africa, $1.14$
million inhabitants) 21 with lockdown fractions of work, leisure, and shopping
activities and complete lockdown of childcare and educational institutions, in
line with measures currently implemented in South Africa. To reflect potential
non-compliance with enacted lockdown measures, the simulations took only a 85%
reduction of other activities; for minibus taxi services we took a 50%
effective reduction of passengers, to reflect the tradeoff between non-
compliance and the reduction in demand due to less people required or wishing
to travel caused by the other lockdown measures and the outbreak (estimates by
GoMetro, South Africa).

Our simulations are consistent with the growth exponents of the total number
of infected individuals both before and after national lockdown, indicating
growth factors of about $r=0.32\pm 0.01$ and about $r=0.04\pm 0.02$,
respectively (Figure 2A,B). The exponents cannot be specified more exactly due
to the unpredictable stochastic factors in the transmission process creating
substantial variations in particular at low case numbers, sampled over in
simulations with ten random realizations each. Importantly, there are
simulated case dynamics that display an early (within April, 2020) saturation
of the total number of cases at $10\,000$ or below. However, the ensemble of
simulations of the lockdown scenario suggests an ongoing outbreak either
entirely without saturation or with early but non-persistent saturation and
renewed increase in May. Figure 2C displays the same data of the dynamics in a
state space characterizing the epidemics without referring to absolute time
(as in Fig. 1C), thereby enabling to compare system-wide potential pathways.
The results illustrate that current lockdown measures substantially slow the
spread of the outbreak in all realizations, but only 1 out of 10 realizations
manages to completely stop the outbreak while hundreds of thousands of people
become infected in the other realizations in the Nelson Mandela Bay
Municipality alone.

To evaluate the expected outbreak dynamics and the maximal number of critical
patients requiring intensive care, we studied four different scenarios by
agent-based simulations, again ten realizations per scenario (Figure 3).
Entirely lifting the currently enacted lockdown on May 1 would cause an
immediate rise of infected patient numbers and a delayed rapid rise of
critical patient numbers drastically beyond the ICU capacity available in NMBM
(estimated to be $50$ based on downscaling (proportional, by population size)
the $267$ ICU beds expected to be available in the entire Eastern Cape
Province 22). Whereas the exact numbers will depend on details of the
simulation, further simulations (not shown) indicate a manifold overload of
ICU capacity also after varying mobility parameters. Lifting lockdown by 25%
two weeks later, i.e. on May 15, still would cause massive rise in case
numbers and ICU overload in early June. Maintaining current lockdown
conditions strongly slows the outbreak, yet our simulations suggest that such
interventions together with current compliance are marginally insufficient to
contain the epidemic long term and keep the number of critical patients below
ICU capacity (Fig. 3B and C), as suggested already by our data analysis of
past case numbers (Figure 1). Finally a fourth scenario of slightly
strengthening current interventions, either by slightly stricter, possibly
even more specific lockdown regulations, by increasing compliance, or a
combination both (90% reduction of shopping and other, 95% reduction of work
activities and complete restriction of all other activities including public
mobility in the simulations), may keep the number of critical COVID-19
patients at or below the ICU capacity and may largely contain the epidemic by
end of June 2020.

##  I Discussion

The analysis of reported past case data is robust and suggests that the
outbreak currently still grows too quickly to contain the number of critical
COVID-19 patients significantly below available ICU capacities nation-wide.
The main potential causes of errors in the analysis of past data may be biased
or undersampled testing and reporting of case numbers.

Predicting future case numbers and the number of critical patients under
different scenario conditions is much more difficult. The most difficult
challenge is the bridging of scales between known or estimated country-wide
overall conditions and specific urban level scenarios (at $1.14$ million
people) that are again subsampled at about 10% of the population, not
primarily due to simulational constraints but due to the availability of
socio-economic and travel data for about $100\,000$ people only.21 Combined
with the COVID-19 outbreak being at an early stage, the number of infected
patients is of an order of magnitude between $10^{1}$ and $10^{3}$ in NMBM,
thereby causing strong stochastic number fluctuations that make individual
predictions unreliable. We attempted to compensate for such fluctuations
partially by running ensemble simulations for 10 random realizations, with a
random subsample of initial patients infected (and thus varying their
location, household size, employment status etc.). As the results are based on
limited ensemble simulations, they likely underestimate the probability of
extreme outcomes such as strong increase or random decay of the outbreak.

##  II Conclusion

The results reported above suggest that current lockdown levels may be just
marginally insufficient to prevent a massive COVID-19 outbreak in South
Africa. As the increase in case numbers is still exponential and not
subexponential as reported for Mainland China 20, South Africa may be still in
the unfortunate situation to become for the African continent what Italy has
been for Europe23, with potentially devastating consequences.

A rapid large-scale infection within weeks to a few months, the likely outcome
if the national lockdown was lifted or relaxed early May8, implies a manifold
overload of ICU capacity. Interventions slightly stronger than those
implemented today, or even a higher degree of compliance to the enacted
lockdown alone may constitute a viable chance for effective countermeasures
for regions in South Africa and potentially for large parts of the African
continent.

However, a number of boundary conditions beyond those known for past major
hubs of the COVID-19 pandemic in countries like Mainland China, the United
States or Italy 23 need to be taken into account simultaneously. Most African
countries find themselves under much stronger socio-economic and health care
system constraints than countries of the Global North.

For instance, a large fraction of the work force both is at lower-income
levels and simultaneously has no fall-back option to remote work. As many of
such work activities are not tagged ”essential” in the sense of the lockdown,
people often have zero income or immediately fall into extreme poverty.
Moreover, even where remote work is possible, it comes with additional
challenges 24. Still, South Africa is potentially in a better position than
many other African countries, so the conclusions (for South Africa
specifically) might be conservative in this sense.

The South African health situation includes a high risk of COVID-19
coinfections for patients with, e.g., HIV/AIDS or forms of tuberculosis (TBC)
and implies additional challenges. According to the WHO 2019, South Africa
ranks 4th globally in the number of TBC infections per capita and 3rd for
those coinfected with TBC and HIV. Moreover, the South African population
infected with TBC alone is about $320\,000$ ($0.5\%$, about 20 times higher
rate than in Europe) and a total of $7.7$ million people ($13\%$) are infected
with HIV as of 2018.25, 26

Therefore, regulatory decision against COVID-19 cannot only keep in mind
short-term economic constraints.17 A large-scale outbreak and massive ICU
overload may have drastic consequences for the country as a whole, including
societal and economic but also psychological, and ethical issues (compare 27).
Thinking of economic constraints should also imply thinking of long-term
implications, for both economy and society. This perspective underlines again
the coaction advocated by the United Nation’s Sustainable Development Goals
(SDGs), in particular Good Health and Wellbeing (SDG 3), Sustainable Cities
and Transportation (SDG 11), and Reduced Inequality both within and among
countries (SGD 10) in the context of COVID-19.

An integrated perspective on such goals may help paving the way to a fair and
sustained solution of the COVID-19 crisis and future pandemics across African
countries as well as for individuals, groups and regions in a position much
more fragile than common for countries of the Global North, as also underlined
by the proposed CoHERE programme.28

## References

  * (1) World Health Organization.  Coronavirus disease 2019 (COVID-19) situation report – 56, 2020\.  https://www.who.int/docs/default-source/coronaviruse/situation-reports/20200316-sitrep-56-covid-19.pdf?sfvrsn=9fda7db2_6 (accessed April 17–20, 2020).
  * (2) Johns Hopkins Center for Systems Science and Engineering.  Coronavirus covid-19 global cases, 2020.  https://coronavirus.jhu.edu (accessed April 20, 2020).
  * (3) E. Callaway, D. Cyranoski, S. Mallapaty, E. Stoye, and J. Tollefson.  The coronavirus pandemic in five powerful charts.  Nature, 579(7800):482–483, 2020.
  * (4) B. F. Maier and D. Brockmann.  Effective containment explains subexponential growth in recent confirmed covid-19 cases in china.  Science, 2020.
  * (5) United Nations, Department of Economic and Social Affairs, Population Division.  World population prospects 2019, 2019.  http://population.un.org (accessed April 17, 2020).
  * (6) WHO.  Who covid-19 dashboard.  https://covid19.who.int (accessed April 18, 2020).
  * (7) Africa Center for Disease Control and Prevention.  Outbreak brief number 13: Covid-19 pandemic.  https://africacdc.org/download/outbreak-brief-number-13-covid-19-pandemic-14-april-2020/ (accessed April 17, 2020).
  * (8) National Department of Health - Republic of South Africa.  COVID-19 Corona Virus South African Resource Portal.  https://sacoronavirus.co.za/ (accessed April 17, 2020).
  * (9) T. P. Velavan and C. G. Meyer.  The covid-19 epidemic.  Trop. Med. Int. Health, 25(3):278–280, 2020.
  * (10) J. N. Nkengasong and W. Mankoula.  Looming threat of COVID-19 infection in Africa: act collectively, and fast.  The Lancet, 395(10227):841–842, 2020.
  * (11) WHO.  WHO African region COVID-19 readiness status v2.  https://app.powerbi.com/view?r=eyJrIjoiMzQwODk3NDYtOTIwYy00MWRjLWJiMTUtOTgzZmJmYmJmZDcxIiwidCI6ImY2MTBjMGI3LWJkMjQtNGIzOS04MTBiLTNkYzI4MGFmYjU5MCIsImMiOjh9 (accessed April 17, 2020).
  * (12) S. Murthy, A. Leligdowicz, and N. K. J. Adhikari.  Intensive care unit capacity in low-income countries: a systematic review.  PLoS ONE, 10(1), 2015.
  * (13) J. Hopman, B. Allegranzi, and S. Mehtar.  Managing COVID-19 in low-and middle-income countries.  JAMA, 2020.
  * (14) A. van den Heever.  Projections on SA health system and whether there are enough hospital beds to cope.  Daily Maverick COVID-19 online resource and news portal.  https://www.dailymaverick.co.za/article/2020-03-16-projections-on-sa-health-system-and-whether-there-enough-hospital-beds-to-cope/ (accessed April 18, 2020).
  * (15) S. Bhagwanjee and J. Scribante.  National audit of critical care resources in South Africa–unit and bed distribution.  South African Medical Journal, 97(12):1311–1314, 2007.
  * (16) G. M. Joynt, P. D. Gopalan, A. Argent, S. Chetty, R. Wise, V. K. W. Lai, E. Hodgson, A. Lee, I. Joubert, S. Mokgokong, S. Tshukutsoane, G. A. Richards, C. Menezes, R. L. Mathivha, B. Espen, B. Levy, K. Asante, and F. Paruk.  The critical care society of Southern Africa consensus statement on ICU triage and rationing (conictri).  Southern African Journal of Critical Care (Online), 35(1):36–52, 2019.
  * (17) CNBC Africa.  South Africa’s lockdown taxi regulations revised.  https://www.cnbcafrica.com/news/2020/04/01/south-africas-lockdown-taxi-regulations-revised (accessed April 18, 2020).
  * (18) K. K. Govender.  Exploring public transport service quality: the case of mini-bus taxi service in South Africa.  Eurasian Bus Rev., 6:101–116, 2016.
  * (19) Wikipedia.  2020 coronavirus pandemic in South Africa.  https://en.wikipedia.org/wiki/2020_coronavirus_pandemic_in_South_Africa (accessed April 17, 2020).
  * (20) D. Martín-Calvo, A. Aleta, A. Pentland, Y. Moreno, and E. Moro.  Effectiveness of social distancing strategies for protecting a community from a pandemic with a data driven contact network based on census and real-world mobility data.  Working paper, https://covid-19-sds.github.io (accessed April 18, 2020).
  * (21) A. Bossert, M. Kersting, M. Timme, M. Schröder, A. Feki, J. Coetzee, and J. Schlüter.  Limited containment options of covid-19 outbreak revealed by regional agent-based simulations for South Africa.  arXiv preprint arXiv:2004.05513, 2020.
  * (22) K. Naidoo, J. Singh, and U. Lalloo.  A critical analysis of ICU/HC beds in South Africa: 2008-2009.  South African Medical Journal, 103(10), 2013.
  * (23) A. Remuzzi and G. Remuzzi.  Covid-19 and italy: what next?  The Lancet, 395(10231):1225 – 1228, 2020.
  * (24) J. Watson (Jobnet Africa).  How to effectively manage remote employees in Africa.  https://www.jobnetafrica.com/blog/article/95-how-to-effectively-manage-remote-employees-in-africa (accessed April 18, 2020).
  * (25) World Health Organization, Geneva.  Global tuberculosis report 2019, 2019.
  * (26) UNAIDS Data for South Africa.  https://www.unaids.org/en/regionscountries/countries/southafrica (accessed April 18, 2020).
  * (27) D. Ramathuba and N. Ramathuba.  Ethical conflicts experienced by intensive care unit health professionals in a regional hospital, Limpopo province, South Africa.  Health SA Gesondheid – J. Interdisc. Health Sci., 25:9, 2020.
  * (28) R. Horton.  CoHERE—A call for a post-pandemic health strategy.  The Lancet, 395:P1242, 2020.

### Funding

MS and MT acknowledge support by the German National Science Foundation
(Deutsche Forschungsgemeinschaft, DFG) and the Saxonian State Ministry for
Higher Education, Research and the Arts under Germany’s Excellence Strategy –
EXC-2068 – 390729961 – Cluster of Excellence Physics of Life (PoL) and the
Center for Advancing Electronics Dresden (cfaed).

### Role of Funding Sources

The funders had no role in study design, data collection, data analysis, data
interpretation, writing of the article, or the decision to submit for
publication. All authors had full access to all the data reported in the study
and were responsible for the decision to submit the Article for publication.

### Contributors

MS, MT and JS conceived and designed research. MS and MT worked out and
evaluated the analysis driven by past case data. AB and MK designed, set up
and adapted the simulation software and ran simulations, supervised by JS. AB,
MK and JS evaluated the simulation data, advised by MS and MT. MS and MT
provided theoretical background and advised on general data analysis and data
presentation. SA advised on health care data and provided medical background.
MS and MT wrote the basic version of the manuscript. JC provided local data
and advised on conditions for mobility simulations. All authors interpreted
the results and contributed to revising and editing the manuscript.

### Declaration of interest

We declare no competing interests.

Fig. 1. COVID-19 in Africa and South Africa. (A) and (B) The number of
confirmed COVID-19 patients in Africa (gray squares) and specifically South
Africa (black disks) from March 1, 2020 until April 16, 2020, on (A) linear
and (B) logarithmic scales. Best exponential fits (colored lines) yield growth
rates $r$ where the total number of (reported) infected patients
$N\propto\exp(r\,t)$ where $t$ measures time in days. (C) State space
representing the number of newly reported patients as a function of the total
of reported people infected (including the recovered), eliminating absolute
time. Straight solid line of slope 1 indicates pure exponential growth The
impact of the lockdown executed on March 27 is clearly visible (vertical lines
in panels A and B).

Fig. 2. Estimated COVID-19 cases for the Nelson Mandela Bay Municipality,
South Africa. (A, B) Simulation of the outbreak without interventions (red
fit) and with current interventions (orange fit) on (A) linear and (B)
logarithmic scales. Thin grey lines represent individual simulations, the
solid black lines represent their averages. Growth rates are consistent with
the observations for South Africa in the beginning of the outbreak (without
lockdown) and after the lockdown (compare Figure 1). (C) State space
representing the number of newly reported patients as a function of the total
of reported people infected (including the recovered), eliminating absolute
time. While the lockdown measures slow the spread of the outbreak, the growth
remains exponential for some time (compare also Figure 1C).

Fig. 3. Influence of intervention policies  (A) Number of active infections
over time. Solid lines indicate averages across realizations, shaded areas
indicate standard deviation. Color encodes the four scenarios: lockdown lifted
May 1st (red), lockdown relaxed by 25% on May 15 (orange), maintain current
lockdown until June 30 (yellow), and enforcing lockdown or increasing
compliance from May 1, 2020 (green). (B) Number of critical patients and
estimated capacity available in NMBM (horizontal dotted line). Data encoding
as in (A). The dashed vertical line illustrates the available ICU capacity.
(C) Maximum number of patients requiring intensive care during the outbreak
until end of June 2020, across scenarios (color code as before). Bars indicate
averages across realizations and standard deviation, small disks individual
realizations. Note that these numbers may increase after June 2020, for
example when maintaining the lockdown (compare upwards trend in panel B). All
data based on ten realizations of agent-based simulations for each of four
scenarios for NMBM, South Africa.