# Approaching the coupon collector’s problem
with group drawings via Stein’s method

Carina Betken111Ruhr University Bochum, Germany. Email<EMAIL_ADDRESS>and Christoph Thäle222Ruhr University Bochum, Germany. Email:
<EMAIL_ADDRESS>
###### Abstract

In this paper the coupon collector’s problem with group drawings is studied.
Assume there are $n$ different coupons. At each time precisely $s$ of the $n$
coupons are drawn, where all choices are supposed to have equal probability.
The focus lies on the fluctuations, as $n\to\infty$, of the number
$Z_{n,s}(k_{n})$ of coupons that have not been drawn in the first $k_{n}$
drawings. Using a size-biased coupling construction together with Stein’s
method for normal approximation, a quantitative central limit theorem for
$Z_{n,s}(k_{n})$ is shown for the case that $k_{n}={n\over
s}(\alpha\log(n)+x)$, where $0<\alpha<1$ and $x\in\mathbb{R}$. The same
coupling construction is used to retrieve a quantitative Poisson limit theorem
in the boundary case $\alpha=1$, again using Stein’s method.

Keywords. Central limit theorem, coupon collector’s problem, Poisson limit
theorem, size-biased coupling, Stein’s method
MSC. 60C05, 60F05

##  1 Introduction

The coupon collector’s problem is an old problem of probability theory which
in its simplest form dates back to de Moivre, Laplace and Euler, see [4], [8]
and [12]. Whereas de Moivre used a die with $s$ faces to pose the problem,
Euler and Laplace used a lottery interpretation as motivation. However, a more
recent example for a situation in which the coupon collector’s problem occurs
is the collection of pictures of the participating players of all teams before
and during every World Cup. Typically, fans can buy the pictures in packages
of five or six. Two natural questions which arise are: How many packages does
one need to buy to get the full or a specific portion of the full set of
players? How many stickers are missing after one has bought $k$ packages? The
first question was for example studied in [3], [6], [7] or [16]. In the work
at hand we will deal with the latter of the two problems. The version of the
coupon collector’s problem we consider can be described as follows. Assume
there are $n$ different coupons. At each time we draw $s$ of these $n$
coupons, where we assume that each of the ${n\choose s}$ choices occurs with
the same probability. We are then interested in the distribution of the number
$Z_{n,s}(k_{n})$ of coupons that have not been drawn in the first $k=k_{n}$
drawings. In a conceptually equivalent interpretation the $n$ coupons are
represented by $n$ different cells numbered $1,\ldots,n$, and in each drawing
we place $s$ particles into $s$ distinct cells, see Figure 1. We are then
interested in the distribution of the number $Z_{n,s}(k_{n})$ of empty cells
after $k=k_{n}$ drawings.

Figure 1: Illustration of the cell interpretation with $n=7$ and $s=4$ in the
first three drawings.

The behaviour of $Z_{n,s}(k_{n})$ for the different regimes of $k_{n}$ has
been subject to numerous research works over the years. In [9] convergence
towards a normal limit is proved for the sublinear and linear regime, that is,
for $k_{n}=o(n)$ and $k_{n}=\alpha n$, respectively. In [15] the author proves
a central limit theorem for a generalized coupon collector’s problem allowing
for random package sizes $S$ in the lower superlinear regime, i.e., for
$\frac{k_{n}}{n}\rightarrow\infty\text{ and
}\limsup_{n}\frac{k_{n}}{n\log(n)}<\frac{1}{\mathbb{E}[S]}$ using a martingale
representation. In [11] the method of moments is used to prove normal
approximation for the case, where $n(\frac{k_{n}s}{n})^{r}\rightarrow\infty$
for all $r\in\mathbb{N}$ and $\mathbb{E}[Z_{n,s}(k_{n})]\rightarrow\infty$,
which covers our regime of normal approximation introduced below. However, no
rates of convergence are given in neither of the works mentioned so far. In
[17] the authors deduce rates of convergence in the Kolmogorov distance
towards a normal limit for $k_{n}=o(n\log(n))$ which are of order
$1/\sqrt{\operatorname{var}(Z_{n,s}(k_{n}))}$. We complement these bounds in
the case where $k_{n}$ is assumed to be of the form
$k_{n}=\frac{n}{s}(\alpha\log(n)+x)$ for some $\alpha\in(0,1)$ and
$x\in\mathbb{R}$. In the case $\alpha=1$, i.e. if
$k_{n}=\frac{n}{s}(\log(n)+x)$, the author in [10] uses the Stein-Chen method
to prove convergence towards a Poisson limit for the number of cells
containing exactly $r$ particles in a more general setting allowing for
multiple particles being placed in one cell at each step. The same question is
also studied in [14] and a Poisson limit is deduced. In the same work, the
authors show that for the special case $r=0$ the condition of equally probable
group drawings can be relaxed to a certain extend without losing the limiting
Poisson distribution. In [2, Theorem 6.F] the authors also prove rates of
convergence of order $\frac{\log(n)}{n}$ towards a Poisson distribution in
this regime, which are optimal in view of [2, Theorem 3.D] . For $r=0$ this
covers our setting of Poisson approximation with the same rates, which are
included here only for completeness and to demonstrate that both limit
theorems can be based on the same coupling argument.

As we have explained above, there exists a sharp asymptotic distributional
phase transition at $\alpha=1$ in the sense that for $\alpha\in(0,1)$ the
random variable $Z_{n,s}(k_{n})$ asymptotically follows a normal distribution
whereas for $\alpha=1$ we obtain a Poisson limit. However, in both cases we
use Stein’s method in combination with the same size-biased coupling
construction to prove upper bounds on the distance between $Z_{n,s}(k_{n})$
and Gaussian or Poisson random variable, respectively. Our results are
presented in the next section, while the coupling construction is explained in
Section 3. The proof of the normal approximation result for $\alpha\in(0,1)$
is the content of Section 4, while the Poisson limit theorem is derived in
Section 5.

##  2 Results

Denote by $(C_{i})_{i=1,\ldots n}$ the collection of cells in the coupon
collector’s problem and let $Z_{n,s}(k_{n})$ be the number of empty cells
after $k_{n}$ drawings, i.e.

$Z_{n,s}(k_{n})=\sum_{j=1}^{n}\mathbf{1}_{E_{n,j}(k_{n})},$

where $E_{n,j}(k)=\\{|C_{j}|=0\text{ after }k_{n}\text{ drawings}\\}$ and
where $|C_{j}|$ stands for the number of particles in cell $C_{j}$. Moreover,
we shall denote for two random variables $X$ and $Y$ by

$d_{W}(X,Y):=\sup_{h\in{\rm
Lip}(1)}\big{|}\mathbb{E}[h(X)]-\mathbb{E}[h(Y)]\big{|}$

the Wasserstein distance between $X$ and $Y$, where the supremum runs over all
Lipschitz functions $h:\mathbb{R}\to\mathbb{R}$ with Lipschitz constant less
than or equal to one. We consider the case where
$k_{n}=\frac{n}{s}(\alpha\log(n)+x)$ for fixed $s\in\mathbb{N}$,
$x\in\mathbb{R}$ and $\alpha\in(0,1)$. Note that since $k_{n}$ denotes the
number of drawings we always assume implicitly that $k_{n}$ is an integer, in
particular we assume that $n$ is large enough so that $k_{n}\geq 0$.
Furthermore, we define the centred and normalized random variables

$\displaystyle\tilde{Z}_{n,s}(k_{n}):=\frac{Z_{n,s}(k_{n})-\mathbb{E}[Z_{n,s}(k_{n})]}{\sqrt{\operatorname{var}(Z_{n,s}(k_{n}))}}.$
(2.1)

Throughout the paper we use the notation $C(x_{1},x_{2},\ldots)$ to indicate
that a constant $C\in(0,\infty)$ only depends on parameters
$x_{1},x_{2},\ldots$ of the model.

######  Theorem 1.

Put $k_{n}=\frac{n}{s}(\alpha\log(n)+x)$ for some $s\in\mathbb{N}$,
$x\in\mathbb{R}$ and $\alpha\in(0,1)$. Let $Z_{n,s}(k_{n})$ be the number of
empty cells after $k_{n}$ drawings as introduced above and denote by $G$ a
standard Gaussian random variable. Then there exist constants
$C=C(s,x)\in(0,\infty)$ and $N=N(s,x,\alpha)\in\mathbb{N}$ such that for all
$n\geq N$,

$\displaystyle
d_{W}(\tilde{Z}_{n,s}(k_{n}),G)\leq\begin{cases}C\frac{\sqrt{\log(n)}}{n^{\alpha}}&\text{
for }\alpha\in(0,\frac{1}{3}]\\\\[5.69046pt] Cn^{-{1\over 2}(1-\alpha)}&\text{
for }\alpha\in(\frac{1}{3},1).\end{cases}$ (2.2)

######  Remark 2.

  * (i)

Since $n^{-\frac{1}{2}(1-\alpha)}$ is of the same order as
$1/\sqrt{\operatorname{var}(Z_{n,s}(k_{n}))}$ we believe that the rate in
Theorem 1 is optimal at least in the regime $\alpha\in(1/3,1)$. We leave it as
an open problem to decide whether or not the rate is optimal for
$\alpha\in(0,1/3]$. On the other hand, Remark 5 shows that in this situation
the rate cannot be improved on the basis of the general normal approximation
bound (4.1) we use.

  * (ii)

One might ask whether the Wasserstein distance can be replaced by the
Kolmogorov distance
$d_{K}(\tilde{Z}_{n,s}(k_{n}),N)=\sup_{u\in\mathbb{R}}|\mathbb{P}(\tilde{Z}_{n,s}(k_{n})\leq
u)-\mathbb{P}(N\leq u)|$. As we shall explain in Remark 4 in more detail, this
is not possible by means of the size-biased coupling approach of Stein’s
method for normal approximation using our coupling construction. In fact, the
resulting bound does in this case not even tend to zero with $n$. On the other
hand, the presumably suboptimal bound $d_{K}(\tilde{Z}_{n,s}(k_{n}),N)\leq
C(\log(n))^{1/4}n^{-\alpha/2}$ for $0<\alpha\leq 1/3$ and
$d_{K}(\tilde{Z}_{n,s}(k_{n}),N)\leq Cn^{-\frac{1}{4}(1-\alpha)}$ for
$1/3<\alpha<1$ follows directly from the fact that the Kolmogorov distance can
always be bounded by the square-root of the Wasserstein distance.

The next result complements Theorem 1 by considering the case $\alpha=1$ for
which the upper bound (2.2) does not tend to zero, as $n\to\infty$. As
emphasized already above, the result is known from [2] and is included here
only for completeness. Similarly as above, for two random variables $X$ and
$Y$ we denote by

$d_{TV}(X,Y):=\sup_{A}\big{|}\mathbb{P}(X\in A)-\mathbb{P}(Y\in B)\big{|}$

the total variation distance between $X$ and $Y$, where the supremum is taken
over all Borel sets $A\subset\mathbb{R}$.

######  Theorem 3.

Put $k_{n}=\frac{n}{s}(\log(n)+x)$ for some $s\in\mathbb{N}$ and
$x\in\mathbb{R}$. Let $Z_{n,s}(k_{n})$ be the number of empty cells after
$k_{n}$ drawings as introduced above and denote by $W$ a Poisson random
variable with parameter $\lambda_{n}=\mathbb{E}[Z_{n,s}(k_{n})]$. Then there
exist constants $\tilde{C}=\tilde{C}(s,x)\in(0,\infty)$ and
$\tilde{N}=\tilde{N}(s,x)\in\mathbb{N}$ such that for all $n\geq\tilde{N}$,

$\displaystyle d_{TV}(Z_{n,s}(k_{n}),W)\leq\tilde{C}\,\frac{\log(n)}{n}.$

For the proof of both results we use Stein’s method in combination with a
size-biased coupling. We start by describing this coupling in the next
section.

##  3 Coupling construction

$1$$1$$1$$2$$2$$1$$2$$3$$3$$2$$3$$3$$1$$1$$1$$2$$2$$1$$2$$3$$3$$2$$3$$3$
Figure 2: Illustration of the coupling construction (continuation of Figure
1); the artificially isolated cell with label $I$ is the dashed one.

We are dealing with the coupon collector’s problem with $n$ coupons, which can
be interpreted as $n$ distinct cells. At each time step we place a fixed
number $s\leq n$ of particles in $s$ different cells. In order to keep track
of when particles are placed into cells, we label all particles in the $m$th
drawing with the letter $m$. Now, after $k_{n}$ placements, we choose one of
the $n$ cells, which we denote by $C_{I}$, uniformly at random and take all
particles out of it. For a particle labelled $j$ taken from $C_{I}$ we now
choose one of the $n-s$ cells not containing a particle with label $j$
uniformly and place the particle into it. We proceed in the same manner until
all particles from cell $I$ have been redistributed into the remaining $n-1$
cells, see Figure 2. Denote by $F_{n,j}^{I}$ the event that at least one
particle from cell $I$ is placed into cell $j$ and put
$\bar{F}_{n,j}^{I}:=(F_{n,j}^{I})^{c}$. Furthermore, we define
$E^{I}_{n,j}(k_{n}):=E_{n,j}(k_{n})\cap\bar{F}_{n,j}^{I}.$ For any $j\neq I$
we then have

$\displaystyle\mathbb{P}(E^{I}_{n,j}(k_{n}))$
$\displaystyle=\sum_{\ell=0}^{k_{n}}\mathbb{P}(E_{n,j}(k_{n})\cap\bar{F}_{n,j}^{I}\cap\\{|C_{I}|=\ell\\})$
$\displaystyle=\sum_{\ell=0}^{k_{n}}\mathbb{P}(\bar{F}_{n,j}^{I}\,|\,E_{n,j}(k_{n})\cap\\{|C_{I}|=\ell\\})\
\mathbb{P}(|C_{I}|=\ell\,|\,E_{n,j}(k_{n}))\ \mathbb{P}(E_{n,j}(k_{n})).$
(3.1)

Note that by construction we have

$\displaystyle\mathbb{P}(E_{n,j}(k_{n}))$
$\displaystyle=\Big{(}1-\frac{s}{n}\Big{)}^{k_{n}},$ (3.2)
$\displaystyle\mathbb{P}(|C_{I}|=\ell\,|\,E_{n,j}(k_{n}))$
$\displaystyle={k_{n}\choose\ell}\Big{(}\frac{s}{n-1}\Big{)}^{\ell}\Big{(}1-\frac{s}{n-1}\Big{)}^{k_{n}-\ell},$
(3.3)

since conditioning on the event $E_{n,j}(k_{n})$ simply means that we can only
place particles in $n-1$ instead of $n$ cells. In addition,

$\displaystyle\mathbb{P}(\bar{F}_{n,j}^{I}\,|\,E_{n,j}(k_{n})\cap\\{|C_{I}|=\ell\\})$
$\displaystyle=\Big{(}1-\frac{1}{n-s}\Big{)}^{\ell},$

since for each of the particles from cell $I$ the probability that it is
placed into an originally empty cell is $\frac{1}{n-s}$. Putting these
expressions back into (3) we obtain

$\displaystyle\mathbb{P}(E_{n,j}^{I}(k_{n}))$
$\displaystyle=\sum_{\ell=0}^{k_{n}}{k_{n}\choose\ell}\Big{(}\frac{s}{n-1}\Big{)}^{\ell}\Big{(}1-\frac{s}{n-1}\Big{)}^{k_{n}-\ell}\Big{(}1-\frac{1}{n-s}\Big{)}^{\ell}\,\Big{(}1-\frac{s}{n}\Big{)}^{k_{n}}$
$\displaystyle=\Big{(}1-\frac{s}{n-1}\Big{)}^{k_{n}}$
$\displaystyle=\mathbb{P}(E_{n,j}(k_{n})\,|\,E_{n,i}(k_{n}))$ (3.4)

for any $i\neq j$. We thus conclude that the random variable

$\displaystyle Z^{I}_{n,s}(k_{n}):=1+\sum_{\begin{subarray}{c}j=1\\\ j\neq
I\end{subarray}}^{n}\mathbf{1}_{E^{I}_{n,j}(k_{n})}$

has the $Z_{n,s}(k_{n})-$size biased distribution, meaning that

$\mathbb{P}(Z^{I}_{n,s}(k_{n})=y)={y\over\mathbb{E}[Z_{n,s}(k_{n})]}\mathbb{P}(Z_{n,s}(k_{n})=y),\qquad
y\in\\{0,1,\ldots,n\\},$

see [1].

######  Remark 4.

Theorem 5.6 in [1] provides a bound on the Kolmogorov distance between
$\tilde{Z}_{n,s}(k_{n})$ and a standard Gaussian random variable using a size-
biased coupling. However, for this to yield a central limit theorem one needs
that $|Z^{I}_{n,s}-Z_{n,s}|=o(\sqrt{n})$ almost surely, as $n\to\infty$. For
the coupling described above we have $|Z^{I}_{n,s}-Z_{n,s}|=n-s-1$ if in all
$k_{n}$ drawings the same $s$ cells are filled and the remaining $n-s$ cells
are filled when redistributing the $k_{n}$ particles of one of the filled
cells. Consequently, the result in [1] does not lead to a meaningful bound on
the Komogorov distance as already explained in part (ii) of the remark after
Theorem 1.

##  4 Proof of Theorem 1

Following [5, Theorem 1.1] the Wasserstein distance between
$\tilde{Z}_{n,s}=\tilde{Z}_{n,s}(k_{n})$ as defined in (2.1) and a standard
Gaussian random variable $G$ is bounded by

$\displaystyle
d_{W}(\tilde{Z}_{n,s},G)\leq\frac{\lambda_{n}}{\sigma_{n}^{2}}\sqrt{\operatorname{var}(\mathbb{E}[Z_{n,s}-Z^{I}_{n,s}|\mathcal{C}_{n}(k_{n})])}+\frac{\lambda_{n}}{\sigma_{n}^{3}}\mathbb{E}[(Z_{n,s}-Z^{I}_{n,s})^{2}],$
(4.1)

where $\mathcal{C}_{n}(k_{n})$ denotes the configuration of the $n$ cells
after $k_{n}$ drawings, $\lambda_{n}=\mathbb{E}[Z_{n,s}(k_{n})]$ and
$\sigma_{n}^{2}=\operatorname{var}(Z_{n,s}(k_{n}))$. In the next sections we
bound further the right-hand side of (4.1) by dealing with the individual
terms.

###  4.1 Expectation and variance

We start by bounding from above the expectation and from below the variance of
$Z_{n,s}$. First, we note that for $k_{n}=\frac{n}{s}(\alpha\log(n)+x)$ we
have

$\displaystyle\mathbb{P}(E_{n,j}(k_{n}))$
$\displaystyle=\Big{(}1-\frac{s}{n}\Big{)}^{k_{n}}=\bigg{(}\Big{(}1-\frac{s}{n}\Big{)}^{n/s}\bigg{)}^{\alpha\log(n)+x}\sim\
e^{-(\alpha\log(n)+x)}=\frac{\,e^{-x}}{n^{\alpha}},$ (4.2)

where we write $f(n)\sim g(n)$ for two functions $f,g:\mathbb{N}\to\mathbb{R}$
if $\displaystyle{\lim_{n\rightarrow\infty}\frac{f(n)}{g(n)}=1}$. Thus,

$\displaystyle\mathbb{E}[Z_{n,s}(k_{n})]=\sum_{j=1}^{n}\mathbb{P}(E_{n,j}(k_{n}))\sim
e^{-x}n^{1-\alpha}.$ (4.3)

In particular, we can find $n_{0}\in\mathbb{N}$, depending on $\alpha$, such
that for all $n\geq n_{0}$,

$\displaystyle\mathbb{P}(E_{n,j}(k_{n}))$
$\displaystyle\leq\frac{2\,e^{-x}}{n^{\alpha}}$ (4.4)

Similarly, we obtain

$\displaystyle\Big{(}1-\frac{s}{n}\Big{)}^{k_{n}}-\Big{(}1-\frac{s}{n-1}\Big{)}^{k_{n}}$
$\displaystyle=\Big{(}1-\frac{s}{n}\Big{)}^{k_{n}}\bigg{(}1-\Big{(}\frac{(n-1-s)n}{(n-1)(n-s)}\Big{)}^{k_{n}}\bigg{)}$
$\displaystyle\leq\Big{(}1-\frac{s}{n}\Big{)}^{k_{n}}\bigg{(}-k_{n}\Big{(}\frac{(n-1-s)n}{(n-1)(n-s)}-1\Big{)}\bigg{)}$
$\displaystyle=\Big{(}1-\frac{s}{n}\Big{)}^{k_{n}}\,k_{n}\,\frac{(n-1)(n-s)-(n-1-s)n}{(n-1)(n-s)}$
$\displaystyle=\Big{(}1-\frac{s}{n}\Big{)}^{k_{n}}\frac{k_{n}\,s}{(n-1)(n-s)}$
$\displaystyle\leq\frac{2e^{-x}(\alpha\log(n)+x)}{n^{1+\alpha}},$ (4.5)

for all $n\geq n_{1}$ for some $n_{1}=n_{1}(\alpha,s)\in\mathbb{N}$, where we
have used that

$\displaystyle 1-z^{k}\leq-k(z-1)$ (4.6)

for $z\in(0,1)$. Using that $\operatorname{var}({\bf
1}_{A})=\mathbb{P}(A)(1-\mathbb{P}(A))$ and $\operatorname{Cov}({\bf
1}_{A},{\bf 1}_{B})=\mathbb{P}(A\cap
B)-\mathbb{P}(A)\mathbb{P}(B)=\mathbb{P}(B)(\mathbb{P}(A|B)-\mathbb{P}(A))$,
we see that

$\displaystyle\operatorname{var}(Z_{n,s})$
$\displaystyle=\sum_{j=1}^{n}\operatorname{var}[\mathbf{1}_{E_{n,j}(k_{n})}]+\sum_{j=1}^{n}\sum_{\begin{subarray}{c}i=1\\\
i\neq
j\end{subarray}}^{n}\operatorname{Cov}[\mathbf{1}_{E_{n,j}(k_{n})},\mathbf{1}_{E_{n,i}(k_{n})}]$
$\displaystyle=\sum_{j=1}^{n}\mathbb{P}(E_{n,j}(k_{n}))(1-\mathbb{P}(E_{n,j}(k_{n})))$
$\displaystyle\qquad\qquad\qquad+\sum_{j=1}^{n}\sum_{\begin{subarray}{c}i=1\\\
i\neq
j\end{subarray}}^{n}[\mathbb{P}(E_{n,i}(k_{n}))(\mathbb{P}(E_{n,j}(k_{n})\,|\,E_{n,i}(k_{n}))-\mathbb{P}(E_{n,j}(k_{n})))]$
$\displaystyle=\bigg{(}1-\Big{(}1-\frac{s}{n}\Big{)}^{k_{n}}+(n-1)\Big{(}\Big{(}1-\frac{s}{n-1}\Big{)}^{k_{n}}-\Big{(}1-\frac{s}{n}\Big{)}^{k_{n}}\Big{)}\bigg{)}\mathbb{E}[Z_{n,s}].$

Applying now (4.1) we conclude that there exists a constant
$c_{1}(s,x)\in(0,\infty)$ such that for $n\geq\max\\{n_{0},n_{1}\\}$ the lower
variance bound

$\displaystyle\operatorname{var}(Z_{n,s})$
$\displaystyle\geq\Big{(}1-\frac{2e^{-x}}{n^{\alpha}}-\frac{2e^{-x}\,(\alpha\log(n)+x)}{n^{\alpha}}\Big{)}\mathbb{E}[Z_{n,s}]\geq
c_{1}(s,x)\,\mathbb{E}[Z_{n,s}],$ (4.7)

holds.

###  4.2 Bounding
$\operatorname{var}\big{(}\mathbb{E}[Z_{n,s}-Z^{I}_{n,s}|\mathcal{C}_{n}(k_{n})]\big{)}$

For the variance of the conditional expectation on the right-hand side in
(4.1) we obtain

$\displaystyle\operatorname{var}\big{(}\mathbb{E}[Z_{n,s}-Z^{I}_{n,s}|\mathcal{C}_{n}(k_{n})]\big{)}=\operatorname{var}\Big{(}\mathbb{E}\Big{[}\sum_{j=1}^{n}\mathbf{1}_{E_{n,j}(k_{n})\cap
F_{n,j}^{I}}|\mathcal{C}_{n}(k_{n})\Big{]}\Big{)}$
$\displaystyle=\mathbb{E}\Big{[}\Big{(}\sum_{j=1}^{n}\mathbb{E}[\mathbf{1}_{E_{n,j}(k_{n})\cap
F_{n,j}^{I}}|\mathcal{C}_{n}(k_{n})]\Big{)}^{2}\Big{]}-\mathbb{E}\Big{[}\sum_{j=1}^{n}\mathbb{E}[\mathbf{1}_{E_{n,j}(k_{n})\cap
F_{n,j}^{I}}|\mathcal{C}_{n}(k_{n})]\Big{]}^{2}$
$\displaystyle=\mathbb{E}\Big{[}\sum_{j=1}^{n}\mathbb{E}[\mathbf{1}_{E_{n,j}(k_{n})\cap
F_{n,j}^{I}}|\mathcal{C}_{n}(k_{n})]^{2}\Big{]}$
$\displaystyle\quad+\Bigg{(}\mathbb{E}\Big{[}\sum_{j=1}^{n}\sum_{\begin{subarray}{c}i=1\\\
i\neq j\end{subarray}}^{n}\,\mathbb{E}[\mathbf{1}_{E_{n,j}(k_{n})\cap
F_{n,j}^{I}}|\mathcal{C}_{n}(k_{n})]\,\mathbb{E}[\mathbf{1}_{E_{n,i}(k_{n})\cap
F_{n,i}^{I}}|\mathcal{C}_{n}(k_{n})]\Big{]}-\Big{[}\sum_{j=1}^{n}\mathbb{E}[\mathbf{1}_{E_{n,j}(k_{n})\cap
F_{n,j}^{I}}]\Big{]}^{2}\Bigg{)}$ $\displaystyle=:T_{1}+T_{2}.$ (4.8)

We start by dealing with $T_{1}$. Note that conditionally on the event
$E_{n,j}(k_{n})$ we have

$\mathbb{E}[\mathbf{1}_{F_{n,j}^{I}}|\mathcal{C}_{n}(k_{n})]=1-\Big{(}1-\frac{1}{n-s}\Big{)}^{|C_{I}|},$
(4.9)

so that with (4.6) we obtain

$\displaystyle
T_{1}=\mathbb{E}\Big{[}\sum_{j=1}^{n}\mathbf{1}_{E_{n,j}(k_{n})}\Big{(}1-\Big{(}1-\frac{1}{n-s}\Big{)}^{|C_{I}|}\Big{)}^{2}\Big{]}$
$\displaystyle\leq\frac{1}{(n-s)^{2}}\mathbb{E}\Big{[}\sum_{j=1}^{n}\mathbf{1}_{E_{n,j}(k_{n})}|C_{I}|^{2}\Big{]}.$

Denoting by $D^{I}_{m}$ the event that a particle is placed into cell $C_{I}$
in the $m$th drawing for some $m\in\\{1,\ldots,k_{n}\\}$ we see that

$\displaystyle\mathbb{E}[\mathbf{1}_{E_{n,j}(k_{n})}|C_{I}|^{2}]$
$\displaystyle=\mathbb{E}\Big{[}\mathbf{1}_{E_{n,j}(k_{n})}\Big{(}\sum_{m=1}^{k_{n}}\mathbf{1}_{D_{m}^{I}}\Big{)}^{2}\Big{]}$
$\displaystyle=\mathbb{E}\Big{[}\sum_{m=1}^{k_{n}}\mathbf{1}_{E_{n,j}(k_{n})}\mathbf{1}_{D_{m}^{I}}\Big{]}+\mathbb{E}\Big{[}\sum_{m=1}^{k_{n}}\sum_{\begin{subarray}{c}r=1\\\
r\neq
m\end{subarray}}^{k_{n}}\mathbf{1}_{E_{n,j}(k_{n})}\mathbf{1}_{D_{m}^{I}}\mathbf{1}_{D_{r}^{I}}\Big{]}$
$\displaystyle=\mathbb{P}(E_{n,j}(k_{n}))\Big{(}\sum_{m=1}^{k_{n}}\mathbb{P}(D_{m}^{I}\big{|}E_{n,j}(k_{n}))+\sum_{m=1}^{k_{n}}\sum_{\begin{subarray}{c}r=1\\\
r\neq m\end{subarray}}^{k_{n}}\mathbb{P}(D_{m}^{I}\cap
D_{r}^{I}\big{|}E_{n,j}(k_{n}))\Big{)}.$

Since all $s$-placements occur with the same probability and conditioning on
the event $E_{n,j}(k_{n})$ simply means that we can only place particles into
$n-1$ cells, we have

$\mathbb{P}(D_{m}^{I}\big{|}E_{n,j}(k_{n}))=\frac{s}{n-1}.$

As the drawings are independent of each other we get

$\displaystyle\sum_{m=1}^{k_{n}}\mathbb{P}(D_{m}^{I}\big{|}E_{n,j}(k_{n}))+\sum_{m=1}^{k_{n}}\sum_{\begin{subarray}{c}r=1\\\
r\neq m\end{subarray}}^{k_{n}}\mathbb{P}(D_{m}^{I}\cap
D_{r}^{I}\big{|}E_{n,j}(k_{n}))$
$\displaystyle=\sum_{m=1}^{k_{n}}\mathbb{P}(D_{m}^{I}\big{|}E_{n,j}(k_{n}))+\sum_{m=1}^{k_{n}}\sum_{\begin{subarray}{c}r=1\\\
r\neq
m\end{subarray}}^{k_{n}}\mathbb{P}(D_{m}^{I}\big{|}E_{n,j}(k_{n}))\mathbb{P}(D_{r}^{I}\big{|}E_{n,j}(k_{n}))=\frac{k_{n}s}{n-1}+\frac{k_{n}(k_{n}-1)s^{2}}{(n-1)^{2}}.$

Using also (4.2) we obtain that there exists a constant
$c_{2}(s,x)\in(0,\infty)$ such that we can bound $T_{1}$ by

$\displaystyle
T_{1}\leq\Big{(}1-\frac{s}{n}\Big{)}^{k_{n}}\frac{n}{(n-s)^{2}}\Big{(}\frac{k_{n}s}{n-1}+\frac{k_{n}(k_{n}-1)s^{2}}{(n-1)^{2}}\Big{)}\leq
c_{2}(s,x)\frac{\alpha^{2}\log(n)^{2}}{n^{1+\alpha}}.$ (4.10)

To deal with the term $T_{2}$ first note that by (3.2) and (3.3),

$\displaystyle\mathbb{E}[\mathbf{1}_{E_{n,j}(k_{n})\cap F_{n,j}^{I}}]$
$\displaystyle=\mathbb{P}(E_{n,j}(k_{n}))\mathbb{P}(F_{n,j}^{I}|E_{n,j}(k_{n}))$
$\displaystyle=\mathbb{P}(E_{n,j}(k_{n}))\sum_{\ell=0}^{k_{n}}\mathbb{P}(F_{n,j}^{I}|E_{n,j}(k_{n})\cap\\{|C_{I}|=\ell\\})\mathbb{P}(C_{I}|=\ell|E_{n,j}(k_{n}))$
$\displaystyle=\Big{(}1-\frac{s}{n}\Big{)}^{k_{n}}\sum_{\ell=0}^{k_{n}}\Big{(}1-\big{(}1-\frac{1}{n-s}\big{)}^{\ell}\Big{)}{k_{n}\choose\ell}\Big{(}\frac{s}{n-1}\Big{)}^{\ell}\Big{(}1-\frac{s}{n-1}\Big{)}^{k_{n}-\ell}$
$\displaystyle=\Big{(}1-\frac{s}{n}\Big{)}^{k_{n}}\Big{(}1-\sum_{\ell=0}^{k_{n}}\big{(}1-\frac{1}{n-s}\big{)}^{\ell}{k_{n}\choose\ell}\Big{(}\frac{s}{n-1}\Big{)}^{\ell}\Big{(}1-\frac{s}{n-1}\Big{)}^{k_{n}-\ell}\Big{)}$
$\displaystyle=\Big{(}1-\frac{s}{n}\Big{)}^{k_{n}}\Big{(}1-\Big{(}1-\frac{s}{(n-s)(n-1)}\Big{)}^{k_{n}}\Big{)}.$
(4.11)

Using (4.9) and slightly adapting (3.3), the first part of $T_{2}$ can be
handled in the following way:

$\displaystyle\mathbb{E}\Big{[}\mathbb{E}[\mathbf{1}_{E_{n,j}(k_{n})\cap
F_{n,j}^{I}}|\mathcal{C}_{n}(k_{n})]\,\mathbb{E}[\mathbf{1}_{E_{n,i}(k_{n})\cap
F_{n,i}^{I}}|\mathcal{C}_{n}(k_{n})]\Big{]}$
$\displaystyle=\mathbb{E}\Big{[}\mathbf{1}_{E_{n,i}(k_{n})}\mathbf{1}_{E_{n,j}(k_{n})}\Big{(}1-\big{(}1-\frac{1}{n-s}\big{)}^{|C_{I}|}\Big{)}^{2}\Big{]}$
$\displaystyle=\sum_{\ell=0}^{k_{n}}\Big{(}1-\big{(}1-\frac{1}{n-s}\big{)}^{\ell}\Big{)}^{2}\,\mathbb{P}(|C_{I}|=\ell|E_{n,i}(k_{n})\cap
E_{n,j}(k_{n}))\,\mathbb{P}(E_{n,i}(k_{n})\cap E_{n,j}(k_{n}))$
$\displaystyle=\Big{(}1-\frac{s}{n}\Big{)}^{k_{n}}\Big{(}1-\frac{s}{n-1}\Big{)}^{k_{n}}\sum_{\ell=0}^{k_{n}}\Big{(}1-\big{(}1-\frac{1}{n-s}\big{)}^{\ell}\Big{)}^{2}\,{k_{n}\choose\ell}\Big{(}\frac{s}{n-2}\Big{)}^{\ell}\Big{(}1-\frac{s}{n-2}\Big{)}^{k_{n}-\ell}$
$\displaystyle=\Big{(}1-\frac{s}{n}\Big{)}^{k_{n}}\Big{(}1-\frac{s}{n-1}\Big{)}^{k_{n}}$
$\displaystyle\qquad\qquad\times\sum_{\ell=0}^{k_{n}}\Big{(}1-2\big{(}1-\frac{1}{n-s}\big{)}^{\ell}+\big{(}1-\frac{1}{n-s}\big{)}^{2\ell}\Big{)}\,{k_{n}\choose\ell}\Big{(}\frac{s}{n-2}\Big{)}^{\ell}\Big{(}1-\frac{s}{n-2}\Big{)}^{k_{n}-\ell}$
$\displaystyle=\Big{(}1-\frac{s}{n}\Big{)}^{k_{n}}\Big{(}1-\frac{s}{n-1}\Big{)}^{k_{n}}$
$\displaystyle\qquad\qquad\times\Bigg{(}1-2\Big{(}1-\frac{s}{(n-2)(n-s)}\Big{)}^{k_{n}}+\Big{(}1-\frac{2s}{(n-2)(n-s)}+\frac{s}{(n-2)(n-s)^{2}}\Big{)}^{k_{n}}\Bigg{)},$

independently of $i$ and $j$. Combining this with (4.2) yields

$\displaystyle T_{2}$ $\displaystyle\leq
n^{2}\Big{(}1-\frac{s}{n}\Big{)}^{2k_{n}}\bigg{[}2\bigg{(}\Big{(}1-\frac{s}{(n-s)(n-1)}\Big{)}^{k_{n}}-\Big{(}1-\frac{s}{(n-s)(n-2)}\Big{)}^{k_{n}}\bigg{)}$
$\displaystyle\qquad\qquad\qquad\qquad+\Big{(}1-\frac{2s}{(n-s)(n-2)}+\frac{s}{(n-2)(n-s)^{2}}\Big{)}^{k_{n}}-\Big{(}1-\frac{s}{(n-s)(n-1)}\Big{)}^{2k_{n}}\bigg{]}.$

Now, there exists $n_{2}=n_{2}(\alpha,s)$ such that

$\displaystyle\Big{(}1-\frac{s}{(n-s)(n-1)}\Big{)}^{k_{n}}-\Big{(}1-\frac{s}{(n-s)(n-2)}\Big{)}^{k_{n}}\leq
2\frac{\alpha\log(n)+x}{n^{2}}$

and

$\displaystyle\Big{(}1-\frac{2s}{(n-s)(n-2)}+\frac{s}{(n-2)(n-s)^{2}}\Big{)}^{k_{n}}-\Big{(}1-\frac{s}{(n-s)(n-1)}\Big{)}^{2k_{n}}\leq
2\frac{\alpha\log(n)+x}{n^{2}}$

holds for all $n\geq n_{2}$. Combing this with (4.2) we can conclude that
there exists a constant $c_{3}(s,x)\in(0,\infty)$ such that for all
$n\geq\max\\{3,n_{2}\\}$,

$\displaystyle T_{2}\leq c_{3}(s,x)\frac{\alpha\log(n)}{n^{2\alpha}}.$ (4.12)

Putting the bounds (4.10) and (4.12) into (4.2) we see that there exists a
constant $c_{4}(s,x)\in(0,\infty)$ such that

$\displaystyle\operatorname{var}\big{(}\mathbb{E}[Z_{n,s}-Z^{I}_{n,s}|\mathcal{C}_{n}(k_{n})]\big{)}\leq
c_{2}(s,x)\frac{\alpha^{2}\log(n)^{2}}{n^{1+\alpha}}+c_{3}(s,x)\frac{\alpha\log(n)}{n^{2\alpha}}\leq
c_{4}(s,x)\frac{\alpha\log(n)}{n^{2\alpha}},$ (4.13)

for all $n\geq\max\\{3,n_{2}\\}$, since $\alpha<1$ by assumption.

######  Remark 5.

Using (4.2) and the exact expressions for the probabilities appearing there,
it can be shown that the order of (4.13) is optimal in the sense that one can
find another constant $\tilde{c}_{4}(s,x)\in(0,\infty)$ such that
$\operatorname{var}(\mathbb{E}[Z_{n,s}-Z^{I}_{n,s}|\mathcal{C}_{n}(k_{n})])\geq\tilde{c}_{4}(s,x)\frac{\alpha\log(n)}{n^{2\alpha}}$
for sufficiently large $n$.

###  4.3 Bounding $\mathbb{E}[(Z_{n,s}-Z^{I}_{n,s})^{2}]$

For the second term in (4.1) it remains to bound
$\mathbb{E}[(Z_{n,s}-Z^{I}_{n,s})^{2}]$. We have

$\displaystyle\mathbb{E}[(Z_{n,s}-Z^{I}_{n,s})^{2}]$
$\displaystyle\leq\mathbb{E}[\Big{(}\sum_{\begin{subarray}{c}j=1\\\ j\neq
I\end{subarray}}^{n}\mathbf{1}_{E_{n,j}(k_{n})\cap F_{n,j}^{I}}-1\Big{)}^{2}]$
$\displaystyle=\mathbb{E}\Big{[}\Big{(}\sum_{\begin{subarray}{c}j=1\\\ j\neq
I\end{subarray}}^{n}\mathbf{1}_{E_{n,j}(k_{n})\cap
F_{n,j}^{I}}\Big{)}^{2}\Big{]}-2\mathbb{E}\Big{[}\sum_{\begin{subarray}{c}j=1\\\
j\neq I\end{subarray}}^{n}\mathbf{1}_{E_{n,j}(k_{n})\cap F_{n,j}}\Big{]}+1$
$\displaystyle=\mathbb{E}\Big{[}\sum_{\begin{subarray}{c}j=1\\\ j\neq
I\end{subarray}}^{n}\sum_{\begin{subarray}{c}i=1\\\ i\neq
j,I\end{subarray}}^{n}\mathbf{1}_{E_{n,j}(k_{n})\cap
F_{n,j}^{I}}\mathbf{1}_{E_{n,i}(k_{n})\cap
F_{n,i}^{I}}\Big{]}-\mathbb{E}\Big{[}\sum_{\begin{subarray}{c}j=1\\\ j\neq
I\end{subarray}}^{n}\mathbf{1}_{E_{n,j}(k_{n})\cap F_{n,j}^{I}}\Big{]}+1,$
(4.14)

where the $-1$ in the first line comes from the artificially isolated cell
with index $I$. For the first sum note that

$\displaystyle\mathbb{P}(E_{n,i}(k_{n})\cap F_{n,i}^{I}\cap E_{n,j}(k_{n})\cap
F_{n,j}^{I})=\mathbb{P}(F^{I}_{n,i}(k_{n})\cap F_{n,j}^{I}|E_{n,j}(k_{n})\cap
E_{n,i})\,\mathbb{P}(E_{n,j}(k_{n})\cap E_{n,j}),$

where $\mathbb{P}(E_{n,j}(k_{n})\cap E_{n,j}(k_{n}))$ can be bounded using (3)
and (4.2). To bound the remaining probability, we observe that similar to the
considerations in (4.2) we have

$\displaystyle\mathbb{P}(F_{n,j}^{I}|E_{n,i}(k_{n})\cap E_{n,j}(k_{n}))$
$\displaystyle=\sum_{\ell=0}^{k_{n}}\mathbb{P}(F_{n,j}^{I}|E_{n,i}(k_{n})\cap
E_{n,j}(k_{n})\cap\\{|C_{I}|=\ell\\})\mathbb{P}(|C_{I}|=\ell|E_{n,i}(k_{n})\cap
E_{n,j}(k_{n}))$
$\displaystyle=\sum_{\ell=0}^{k_{n}}{k_{n}\choose\ell}\Big{(}1-\big{(}1-\frac{1}{n-s}\big{)}^{\ell}\Big{)}\Big{(}\frac{s}{n-2}\Big{)}^{\ell}\Big{(}1-\frac{s}{n-2}\Big{)}^{k_{n}-\ell}$
$\displaystyle=1-\Big{(}1-\frac{s}{(n-2)(n-s)}\Big{)}^{k_{n}},$

independently of the choice of $i$ and $j$. So we are left to deal with
$\mathbb{P}(F_{n,i}^{I}|E_{n,i}(k_{n})\cap E_{n,j}(k_{n})\cap F_{n,j}^{I})$.
It holds that for $i\neq j$

$\displaystyle\mathbb{P}(F_{n,i}^{I}|E_{n,j}(k_{n})\cap E_{n,i}(k_{n})\cap
F_{n,j}^{I})\leq\mathbb{P}(F_{n,i}^{I}|E_{n,i}(k_{n})\cap E_{n,j}(k_{n})),$

since the event $F_{n,j}^{I}$ implies that at least one particle from cell $I$
is placed into cell $C_{j},$ reducing the chances of cell $C_{i}$ receiving a
particle. Hence,

$\displaystyle\mathbb{P}(F_{n,i}^{I}\cap F_{n,j}^{I}|E_{n,i}(k_{n})\cap
E_{n,j}(k_{n}))\leq\Big{(}1-\Big{(}1-\frac{s}{(n-2)(n-s)}\Big{)}^{k_{n}}\Big{)}^{2}$

and we finally obtain that for $n\geq\max\\{n_{0},s\\}$,

$\displaystyle\mathbb{E}\Big{[}\sum_{\begin{subarray}{c}j=1\\\ j\neq
I\end{subarray}}^{n}\sum_{\begin{subarray}{c}i=1\\\ i\neq
j,I\end{subarray}}^{n}\mathbf{1}_{E_{n,j}(k_{n})\cap
F_{n,j}^{I}}\mathbf{1}_{E_{n,i}(k_{n})\cap F_{n,i}^{I}}\Big{]}$
$\displaystyle=\sum_{\begin{subarray}{c}j=1\\\ j\neq
I\end{subarray}}^{n}\sum_{\begin{subarray}{c}i=1\\\ i\neq
j,I\end{subarray}}^{n}\mathbb{P}(F_{n,i}^{I}\cap
F_{n,j}^{I}|E_{n,i}(k_{n})\cap E_{n,j}(k_{n}))\mathbb{P}(E_{n,i}(k_{n})\cap
E_{n,j}(k_{n}))$
$\displaystyle\leq(n-1)(n-2)\Big{(}1-\Big{(}1-\frac{s}{(n-2)(n-s)}\Big{)}^{k_{n}}\Big{)}^{2}\Big{(}1-\frac{s}{n}\Big{)}^{2k_{n}}$
$\displaystyle\leq(n-1)(n-2)\Big{(}k_{n}\frac{s}{(n-2)(n-s)}\Big{)}^{2}\Big{(}1-\frac{s}{n}\Big{)}^{2k_{n}}$
$\displaystyle\leq(n-1)(n-2)\Big{(}\frac{3(s+1)(\alpha\log(n)+x)}{n}\Big{)}^{2}\Big{(}\frac{2e^{-x}\alpha\log(n)}{n^{\alpha}}\Big{)}^{2}$
$\displaystyle\leq
36(s+1)^{2}e^{-2x}\frac{(\alpha\log(n)+x)^{2}}{n^{2\alpha}},$

where we have used (4.6) to arrive at the third line. Since according to (4.2)
the negative sum in (4.3) is of order $n^{-(\alpha+1)}$, we conclude that
there exists a constant $c_{5}(s,x)\in(0,\infty)$ such that for all
$n\geq\max\\{n_{0},s\\}$,

$\displaystyle\mathbb{E}[(Z_{n,s}-Z^{I}_{n,s})^{2}]\leq c_{5}(s,x).$ (4.15)

Combining the normal approximation bound (4.1) with the estimates (4.3),
(4.7), (4.13) and (4.15) we arrive at

$\displaystyle d_{W}(\tilde{Z}_{n,s},G)$
$\displaystyle\leq\frac{\lambda_{n}}{c_{1}(s,x)\lambda_{n}}\sqrt{c_{4}(s,x)\frac{\alpha\log(n)}{n^{2\alpha}}}+\frac{\lambda_{n}}{(c_{1}(s,x)\lambda_{n})^{\frac{3}{2}}}c_{5}(s,x)$
$\displaystyle\leq\begin{cases}C(s,x)\frac{\sqrt{\log(n)}}{n^{\alpha}}&\text{
for }\alpha\in(0,\frac{1}{3}]\\\\[5.69046pt] C(s,x)n^{-{1\over
2}(1-\alpha)}&\text{ for }\alpha\in(\frac{1}{3},1)\end{cases}$

for some constant $C(s,x)\in(0,\infty)$ and for all $n\geq
N:=\max\\{n_{0},n_{1},n_{2},3,s,e^{-x}\\}$. This proves Theorem 1.∎

##  5 Proof of Theorem 3

As already mentioned in the introduction, rates of convergence towards a
Poisson limit in the case $\alpha=1$ can be concluded from [2, Theorem 6.F].
Nevertheless, we give an alternative self-contained proof using the coupling
from Section 3.

It follows from [13, Theorem 4.13] that the total variation distance between
the number of empty cells in the coupon collector’s problem and a Poisson
random variable $W$ with parameter $\lambda_{n}=\mathbb{E}[Z_{n,s}(k_{n})]$
can be bounded using the following inequality:

$\displaystyle
d_{TV}(Z_{n,s}(k_{n}),W)\leq\min\\{1,\lambda_{n}\\}\,\mathbb{E}[Z_{n,s}(k_{n})+1-Z_{n,s}^{I}(k_{n})].$
(5.1)

For the expectation on the right the definitions of $Z_{n,s}(k_{n})$ and
$Z^{I}_{n,s}(k_{n})$ yield

$\displaystyle\mathbb{E}[Z_{n,s}(k_{n})+1-Z_{n,s}^{I}(k_{n})]$
$\displaystyle=\mathbb{E}[\mathbf{1}_{E_{n,I}(k_{n})}]+\mathbb{E}\Big{[}\sum_{j\neq
I}\mathbf{1}_{E_{n,j}(k_{n})}-\mathbf{1}_{E^{I}_{n,j}(k_{n})}\Big{]}$
$\displaystyle=\Big{(}1-\frac{s}{n}\Big{)}^{k}+(n-1)\bigg{(}\Big{(}1-\frac{s}{n}\Big{)}^{k}-\Big{(}1-\frac{s}{n-1}\Big{)}^{k}\bigg{)}.$

Combining (4.2) and (4.1) for $\alpha=1$ with (5.1) yields

$\displaystyle d_{TV}(Z_{n,s}(k_{n}),W)$
$\displaystyle\leq\min\\{1,\lambda_{n}\\}\,\mathbb{E}[Z_{n,s}(k_{n})+1-Z_{n,s}^{I}(k_{n})]$
$\displaystyle=\Big{(}1-\frac{s}{n}\Big{)}^{k}+(n-1)\bigg{(}\Big{(}1-\frac{s}{n}\Big{)}^{k}-\Big{(}1-\frac{s}{n-1}\Big{)}^{k}\bigg{)}$
$\displaystyle\leq\frac{2\,e^{-x}}{n}\Big{(}\log(n)+x+1\Big{)},$

for $n\geq\tilde{N}:=\max\\{n_{0},n_{1},e^{-(x+1)}\\}$, which completes the
proof of Theorem 3.∎

### Acknowledgement

This work has been supported by the DFG priority program SPP 2265 Random
Geometric Systems.

## References

  * [1] R. Arratia, L. Goldstein, F. Kochman: Size bias for one and all. Probab. Surveys 16, 1–61 (2019).
  * [2] A.D. Barbour, L. Holst, S. Janson: _Poisson Approximation_. Oxford University Press (1992).
  * [3] L.E. Baum, P. Billingsley: Asymptotic distributions for the coupon collector’s problem. Ann. Math. Statistics 36, 1835–1839 (1965).
  * [4] L. Euler: Solutio quarundam quaestionum difficiliorum in calculo probabilium. Opuscula Analytica, Vol. 2, 331–346 (1785).
  * [5] L. Goldstein, Y. Rinott: Multivariate normal approximations by Stein’s method and size bias couplings. J. Appl. Probab. 33, 1–17 (1996).
  * [6] N.L. Johnson, S. Kotz: _Urn Models and their Application: An Approach to Modern Discrete Probability Theory_. Wiley (1977).
  * [7] V.F. Kolchin, B.A. Sevastianov, V.P. Chistiakov: Random Allocations. Halsted Press Washington (1978).
  * [8] P.S. Laplace: Théorie Analytique des Probabilités. Courcier, Paris (1812).
  * [9] H. Mahmoud: Gaussian phases in generalized coupon collection. Adv. in Appl. Probab. 42, 994-1012. (2010)
  * [10] V.G. Mikhailov: A Poisson limit theorem in the scheme of group disposal of particels. Th. Probab. Appl. 22, 152–156 (1977).
  * [11] V.G. Mikhailov: Asymptotic normality of the number of empty cells for group allocation of particles. Th. Probab. Appl. 25, 82–90 (1980).
  * [12] A. de Moivre: The Doctrine of Chances. W. Pearson (1718).
  * [13] N. Ross: Fundamentals of Stein’s method. Probab. Surveys 8, 210–293 (2011).
  * [14] J. Schilling, N. Henze: Two Poisson limit theorems for the coupon collector’s problem with group drawings. J. Appl. Probab. 58, 966–977 (2021).
  * [15] R. T. Smythe. Generalized coupon collection: the superlinear case. J. Appl. Probab. 48, 189–199 (2011).
  * [16] W. Stadje: The collector’s problem with group drawings. Adv. in Appl. Probab. 22, 866–882 (1990).
  * [17] V.A. Vatutin, V.G. Mikhailov: Limit theorems for the number of empty cells in an equiprobable scheme for group allocation of particles. Th. Probab. Appl. 27, 734–743 (1983).


shows that

$\displaystyle S_{H}(y,x)=\int_{y}^{x}p^{+}_{H}(z)\ dz,$ $\displaystyle\qquad
S_{G}(y,x)=\int_{y}^{x}p^{+}_{G}(z)\ dz$ if $y\leqslant x$ $\displaystyle
S_{H}(y,x)=\int_{x}^{y}-p^{-}_{H}(z)\ dz,$ $\displaystyle\quad
S_{G}(y,x)=\int_{x}^{y}-p^{-}_{G}(z)\ dz$ if $y>x$

As a consequence, we derive the following result:

######  Proposition 6.1.

For every $y\in{\mathbb{R}}$ and $n\in\mathbb{N}$, we have

$S_{H}(y,y+n)=nP_{H}^{+},\qquad S_{H}(y,y-n)=n(-P_{H}^{-}).$

Furthermore, there exists positive constants $C$ and $\kappa$, such that

$-C\leqslant S_{G}(y,x)\leqslant\kappa|x-y|\qquad\hbox{for all
$x,y\in{\mathbb{R}}$.}$

###### Proof.

The first assertion is apparent from the formulae for $S_{H}$ provided above
and the periodicity of $p^{\pm}_{H}$. Let us consider the second assertion.
The lower bound for $S_{G}$ follows via the same argument used in the proof of
Proposition 4.1, with the only difference that here $\delta=0$ since
$c(G)=c(H)$. The upper bound is a general fact already remarked in Section
1.3. ∎

We record here for later use the following lemma.

######  Lemma 6.2.

For every $y\in\mathbb{R}$, we have

$\inf\\{S_{H}(\xi,x),\>\,\xi\in
y+\mathbb{Z}\,\\}=\min\\{S_{H}(\xi,x),\>\,\xi\in\big{(}y+\mathbb{Z}\big{)}\cap[x-1,x+1]\,\\}\qquad\hbox{for
all $x\in{\mathbb{R}}$.}$

###### Proof.

It is clearly enough to prove the following assertion:
Claim: let $\xi\in y+\mathbb{Z}$. If $|\xi-x|>1$, there exists $\eta\in
y+\mathbb{Z}$ such that

$|\eta-x|\leqslant|\xi-x|-1\qquad\hbox{and}\qquad S_{H}(\eta,x)\leqslant
S_{H}(\xi,x).$

Let us divide the proof in two cases.

If $x-\xi>1$, i.e. $\xi<x-1$, we have

$S_{H}(\xi,x)=S_{H}(\xi,\xi+1)+S_{H}(\xi+1,x)=P_{H}^{+}+S_{H}(\xi+1,x)\geqslant
S_{H}(\xi+1,x),$

and the claim holds true with $\eta:=\xi+1$.

If $\xi-x>1$, i.e. $\xi>x+1$, we have

$S_{H}(\xi,x)=S_{H}(\xi,\xi-1)+S_{H}(\xi-1,x)=(-P_{H}^{-})+S_{H}(\xi-1,x)\geqslant
S_{H}(\xi-1,x),$

and the claim holds true with $\eta:=\xi-1$. ∎

Let us denote by $\mathcal{E}(H)$ and $\mathcal{E}(G)$ the sets of equilibria
associated with $H$ and $G$, respectively. Since $G=H$ in
${\mathbb{R}}\setminus\operatorname{supp}(V)$, we have

$\mathcal{E}(H)\setminus\operatorname{supp}(V)=\mathcal{E}(G)\setminus\operatorname{supp}(V).$
(6.4)

The following holds:

######  Theorem 6.3.

There exists a bounded solution $u_{G}$ to (6.1).

###### Proof.

Let us set $u_{G}(x):=\inf_{y\in\mathcal{E}(G)}S_{G}(y,x)$. From (6.4), the
fact that $\mathcal{E}(H)$ is $\mathbb{Z}$-periodic and of Proposition 6.1, we
derive that $u_{G}$ is a well defined bounded, Lipschitz function.
Furthermore, as an infimum of viscosity solutions of (6.1), we get that
$u_{G}$ is a viscosity solution as well in view of Proposition 1.1. ∎

###  6.2. Asymptotic convergence

Let us denote by $u^{\lambda}_{G}$, $u^{\lambda}_{H}$ the solutions of the
discounted equations

$\displaystyle\lambda u+G(x,u^{\prime})=c\qquad\hbox{in $\mathbb{R}$,}$ (6.5)
$\displaystyle\lambda u+H(x,u^{\prime})=c\qquad\hbox{in $\mathbb{R}$.}$ (6.6)

We want to prove that the solutions $u^{\lambda}_{G}$ converge, as $\lambda\to
0^{+}$, to a specific solution of $u^{0}_{G}$ the critical equation (6.1). In
view of [17], we know that this is true for the solutions of (6.6), i.e.
$u^{\lambda}_{H}\rightrightarrows u^{0}_{H}$ in ${\mathbb{R}}$ where
$u^{0}_{H}$ is a solution to the critical equation (6.6), and this convergence
is actually uniform in ${\mathbb{R}}$ since all these functions are
$\mathbb{Z}$–periodic. Furthermore, $u^{0}_{H}$ is identified as the maximal
(sub-)solution $v$ to (6.2) such that

$\int_{{\mathbb{T}^{1}\times\mathbb{R}}}v(y)\,d\mu(y)\leqslant
0\qquad\hbox{for all $\mu\in\mathfrak{M}(H)$,}$ (6.7)

where $\mathfrak{M}(H)$ denotes the set of projected Mather measures for $H$.

The asymptotic convergence of the solutions $u^{\lambda}_{G}$ will be
established under the following assumption:

$u^{0}_{H}(x)=\sup\\{v(x)\,:\,\hbox{$v$ is a $\mathbb{Z}$-periodic subsolution
of \eqref{eq3 H critical} with $v\leqslant 0$ on $\mathcal{E}(H)$}\,\\}.$ (U)

This is motivated by the following fact.

######  Proposition 6.4.

Condition (U) is fulfilled in either one of the following cases:

  * (i)

when $\int_{0}^{1}p_{H}^{-}(x)dx<0<\int_{0}^{1}p_{H}^{+}(x)dx$;

  * (ii)

when
$\big{(}\int_{0}^{1}p_{H}^{-}(x)dx\big{)}\big{(}\int_{0}^{1}p_{H}^{+}(x)dx\big{)}=0$
and $H$ is Tonelli.

###### Proof.

We aim at showing that condition (6.7) is equivalent to $v\leqslant 0$ on
$\mathcal{E}(H)$. We first remark that any measure of the kind
$\delta_{(y,0)}$ with $y\in\mathcal{E}$ is a Mather measure, i.e. $\delta_{y}$
is a projected Mather measure for every $y\in\mathcal{E}(H)$. In order to
conclude, it suffices to show that any projected Mather measure has support
contained in $\mathcal{E}(H)$. Let $\mu:={\pi_{1}}_{\\#}\tilde{\mu}$ for some
Mather measure $\tilde{\mu}\in\tilde{\mathfrak{M}}(H)$. In case (i), pick
$\lambda\in(0,1)$ in such a way that the function

$w(x):=\int_{0}^{x}\big{(}\lambda
p_{H}^{-}(z)+(1-\lambda)p_{H}^{+}(z)\big{)}\,dz,\qquad x\in{\mathbb{R}}$

is $1$-periodic. It is easily seen that $w$ is a $C^{1}$-subsolution of the
critical equation (6.2) and it is strict in
${\mathbb{R}}\setminus\mathcal{E}(H)$. By using Fenchel inequality and the
fact that $\tilde{\mu}$ is closed, we have

$-c=\int_{{\mathbb{T}^{1}\times\mathbb{R}}}L_{H}(x,q)\,d\tilde{\mu}(x,q)\geqslant\int_{{\mathbb{T}^{1}\times\mathbb{R}}}w^{\prime}(x)q\,d\tilde{\mu}(x,q)-\int_{\mathbb{T}^{1}}H(x,w^{\prime}(x))\,d{\mu}(x)\geqslant-c,$

hence all inequalities are equalities. We infer that $H(x,w^{\prime}(x))=c$
for $\mu$-a.e. $x\in\mathbb{T}^{1}$, i.e.
$\operatorname{supp}(\mu)\subseteq\mathcal{E}(H)$.

In case (ii), it is well known, cf. [24, Theorem 1.6] that $\tilde{\mu}$ is
invariant under the Lagrangian flow. Since the set
$C:=\mathcal{E}(H)\times\\{0\\}$ is the maximal closed invariant set under the
Lagrangian flow, the support of $\tilde{\mu}$ needs to be contained in $C$. We
conclude that $\operatorname{supp}(\mu)\subseteq\mathcal{E}(H)$. ∎

######  Remark 6.5.

We refer the reader to the Appendix for an example of a non-Tonelli
Hamiltonian for which condition (U) is violated.

######  Theorem 6.6.

Assume condition (U) holds. We have

$u^{0}_{H}(x)=\inf\\{S_{H}(y,x)\,:\,y\in\mathcal{E}(H)\,\\}\qquad\hbox{for all
$x\in{\mathbb{R}}$.}$ (6.8)

###### Proof.

Let us call $u(x)$ the infimum appearing at the right-hand side of (6.8). The
fact that $u$ is a bounded solution to (6.2) can be proved as in Theorem 6.3.
The function $u$ is also $1$-periodic due to the fact that
$z+\mathcal{E}(H)=\mathcal{E}(H)$ and $S_{H}(y+z,x+z)=S_{H}(y,x)$ for every
$z\in\mathbb{Z}$ and $x,y\in{\mathbb{R}}$. Furthermore, since $S_{H}(y,y)=0$
for every $y\in\mathcal{E}(G)$, it is apparent from its very definition that
$u\leqslant 0$ on $\mathcal{E}(H)$. On the other hand, if $v$ is a 1-periodic
subsolution to (6.2) with $v\leqslant 0$ on $\mathcal{E}(G)$, in view of
Proposition 1.5 we have

$v(x)\leqslant v(y)+S_{G}(y,x)\leqslant S_{G}(y,x)\qquad\hbox{for all
$x\in{\mathbb{R}}$ and $y\in\mathcal{E}(G)$,}$

hence, by taking the infimum of the right-hand side term with respect to
$y\in\mathcal{E}(G)$, we get $v(x)\leqslant u(x)$ for all $x\in{\mathbb{R}}$.
∎

Let $u_{G}$ be the bounded solution of the critical equation (6.1). Since
$u_{G}^{-}:=u_{G}-\|u_{G}\|_{\infty}$ and
$u_{G}^{+}:=u_{G}+\|u_{G}\|_{\infty}$ are, respectively, a bounded negative
and positive solution of (6.1), from Proposition 1.15 we derive that the
functions $\\{u^{\lambda}_{G}\,:\,\lambda>0\\}$ are equi–bounded and
equi–Lipschitz on ${\mathbb{R}}$, and satisfy

$-2\|u_{G}\|_{\infty}\leqslant u^{-}_{G}(x)\leqslant
u^{\lambda}_{G}(x)\leqslant u^{+}_{G}(x)\leqslant
2\|u_{G}\|_{\infty}\qquad\hbox{for all $x\in{\mathbb{R}}$.}$ (6.9)

Let us denote by

$\omega\big{(}\\{u^{\lambda}_{G}\\}\big{)}:=\left\\{u\in\mbox{\rm
Lip}({\mathbb{R}})\,:\,u^{\lambda_{k}}_{G}\rightrightarrows u\ \hbox{in
${\mathbb{R}}$\quad for some sequence $\lambda_{k}\to 0$}\right\\}.$

Of course, our aim is to show that this set reduces to $\\{u^{0}_{G}\\}$. We
first have to identify a good candidate for $u^{0}_{G}$. Our guess is the
following:

$u^{0}_{G}(x):=\sup\left\\{v(x)\,:\,\hbox{$v\in{\mathfrak{S}_{b}}_{-}(G)$}\right\\}\qquad\hbox{$x\in{\mathbb{R}}$},$
(6.10)

where ${\mathfrak{S}_{b}}_{-}(G)$ denotes the family of bounded subsolutions
$v:{\mathbb{R}}\to\mathbb{R}$ of the critical equation (6.1) satisfying

$\int_{\mathbb{R}}v(y)\,d\mu(y)\leqslant\mathbbm{1}_{0}\big{(}c(G)-c_{f}(G)\big{)}\qquad\text{for
every $\mu\in\mathfrak{M}(G)$},$ (6.11)

where $\mathfrak{M}(G)$ denotes the set of projected Mather measures for $G$
and $\mathbbm{1}_{0}$ is the indicator function of the set $\\{0\\}$ in the
sense of convex analysis, i.e. $\mathbbm{1}_{0}(t)=0$ if $t=0$ and
$\mathbbm{1}_{0}(t)=+\infty$ otherwise. Note that in this case the right-hand
side of (6.11) is equal to 0 since $c(G)=c_{f}(G)$.

######  Theorem 6.7.

The following holds:

$u^{0}_{G}(x)=\sup\\{v(x)\,:\,\hbox{$v$ subsolution of \eqref{eq3 G critical}
such that $v\leqslant 0$ on $\mathcal{E}(G)$}\,\\}\qquad\hbox{for all
$x\in{\mathbb{R}}$.}$

In particular, $\displaystyle
u^{0}_{G}(x)=\inf_{y\in\mathcal{E}(G)}S_{G}(y,x)$ for all $x\in{\mathbb{R}}$,
and $u^{0}_{G}$ is a bounded solution to (6.1).

###### Proof.

The first assertion is a straightforward consequence of Corollary 3.4. The
second assertion can be proved arguing as in the proof of Theorem 6.6. ∎

Let us begin to study the asymptotic behavior of the solutions
$u^{\lambda}_{G}$ of the discounted equation (6.5).

######  Proposition 6.8.

Let $\lambda>0$. Then

$u^{\lambda}_{G}(y)\leqslant 0\qquad\hbox{for all $y\in\mathcal{E}(G)$.}$

In particular, $u\leqslant u^{0}_{G}$ in $\mathbb{R}$ for every
$u\in\omega\big{(}\\{u^{\lambda}_{G}\\}\big{)}$.

###### Proof.

Let $y\in\mathcal{E}(G)$. Then the stationary curve $\xi(t):=y$ for all
$t\leqslant 0$ satisfies

$L_{G}(\xi(t),\dot{\xi}(t))+c=L_{G}(y,0)+c=-\min_{p}G(y,p)+c=0\qquad\hbox{for
all $t\leqslant 0$}.$

By using $\xi$ as a competitor curve in formula (1.14) for
$u_{G}^{\lambda}(y)$, we obtain $u_{G}^{\lambda}(y)\leqslant 0$. We derive
that any fixed $u\in\omega\big{(}\\{u^{\lambda}_{G}\\}\big{)}$ is a bounded
solution of (6.1) satisfying $u\leqslant 0$ in $\mathcal{E}(G)$, hence
$u\leqslant u^{0}_{G}$ in $\mathbb{R}$ by the maximality property stated in
Theorem 6.7. ∎

In order to show that
$\omega\big{(}\\{u^{\lambda}_{G}\\}\big{)}=\\{u^{G}_{0}\\}$, we need to show
the converse inequality, i.e.

$u\geqslant u^{0}_{G}\qquad\hbox{for every
$u\in\omega\big{(}\\{u^{\lambda}_{G}\\}\big{)}$.}$ (6.12)

Let us show the following preliminary fact first.

######  Proposition 6.9.

Assume condition (U) holds. Then

$u^{0}_{H}(x)\geqslant u^{0}_{G}(x)\qquad\hbox{for all
$x\in\mathbb{R}\setminus[\underline{y}_{V}-1,\overline{y}_{V}+1]$.}$

###### Proof.

Let $x\in\mathbb{R}\setminus[\underline{y}_{V}-1,\overline{y}_{V}+1]$.
According to Lemma 6.2,

$u^{0}_{H}(x)=\min\\{S_{H}(y,x)\,:\,y\in\mathcal{E}(H)\cap[x-1,x+1]\,\\}.$

Since $[x-1,x+1]\cap\operatorname{supp}(V)=\emptyset$, we have that
$\mathcal{E}(G)\cap[x-1,x+1]=\mathcal{E}(H)\cap[x-1,x+1]$ and
$S_{H}(y,x)=S_{G}(y,x)$ for all $y\in[x-1,x+1]$. We conclude that

$u^{0}_{H}(x)=\min\\{S_{H}(y,x)\,:\,y\in\mathcal{E}(H)\cap[x-1,x+1]\,\\}\\\
=\min\\{S_{G}(y,x)\,:\,y\in\mathcal{E}(G)\cap[x-1,x+1]\,\\}\geqslant\min\\{S_{G}(y,x)\,:\,y\in\mathcal{E}(G)\,\\}=u^{0}_{G}(x).$

∎

We are now in position to prove the asymptotic convergence.

######  Theorem 6.10.

Assume condition (U) holds. Then the functions $u^{\lambda}_{G}$ uniformly
converge to the function $u^{0}_{G}$ given by (6.10) locally on ${\mathbb{R}}$
as $\lambda\to 0^{+}$.

###### Proof.

Let $\lambda_{n}\to 0$ be such that $u^{\lambda_{n}}_{G}$ locally uniformly
converge to some $u\in\mbox{\rm C}({\mathbb{R}})$. We have seen in Proposition
6.8 that

$u(x)\leqslant u^{0}_{G}(x)\qquad\hbox{for every $x\in{\mathbb{R}}$}.$

To prove the opposite inequality, let us fix $x\in{\mathbb{R}}$. According to
Proposition 1.18, there exists a monotone curve
$\gamma_{x}:(-\infty,0]\to{\mathbb{R}}$ with $\gamma_{x}(0)=x$ which is
optimal for $u^{0}_{G}(x)$. Pick $r>0$ big enough so that
$\\{x\\}\cup[\underline{y}_{V}-1,\overline{y}_{V}+1]\subseteq B_{r}$ and let
$\tilde{\mu}_{x,1}^{\lambda},\,\tilde{\mu}_{x,2}^{\lambda}$ be the probability
measures on ${\mathbb{R}\times\mathbb{R}}$ defined via (3.10) and (3.11),
respectively. Let us apply Proposition 3.8 with $v:=u^{0}_{G}$. By taking into
account that
$\operatorname{supp}({\tilde{\mu}}^{\lambda}_{x,2})\subseteq\big{(}\mathbb{R}\setminus[\underline{y}_{V}-1,\overline{y}_{V}+1]\big{)}\times\mathbb{R}$
and $u^{0}_{G}\leqslant u^{0}_{H}$ in
$\mathbb{R}\setminus[\underline{y}_{V}-1,\overline{y}_{V}+1]$, we get

$u^{\lambda}_{G}(x)\geqslant
u^{0}_{G}(x)-\left(\theta^{\lambda}_{x}\int_{{\mathbb{R}\times\mathbb{R}}}u^{0}_{G}(y)\,d{\tilde{\mu}}^{\lambda}_{x,1}(y,q)+(1-\theta^{\lambda}_{x})\int_{{\mathbb{R}\times\mathbb{R}}}u^{0}_{H}(y)\,d{\tilde{\mu}}^{\lambda}_{x,2}(y,q)\right)$

Now set $\lambda:=\lambda_{n}$ and send $n\to+\infty$ in the above inequality.
In view of Propositions 3.6 and 3.7, there exist measures
$\tilde{\mu}_{1,x}\in\mathscr{P}({\mathbb{R}\times\mathbb{R}})$ and
$\tilde{\mu}_{2,x}\in\mathscr{P}({\mathbb{T}^{1}\times\mathbb{R}})$ and
$\theta\in[0,1]$ such that

$u(x)\geqslant
u^{0}_{G}(x)-\theta\int_{{\mathbb{R}\times\mathbb{R}}}u^{0}_{G}\,d{\tilde{\mu}}_{x,1}-(1-\theta)\int_{{\mathbb{T}^{1}\times\mathbb{R}}}u_{H}^{0}\,d{\tilde{\mu}}_{x,2}.$
(6.13)

Furthermore, in view of Propositions 3.7,

$\int_{{\mathbb{R}\times\mathbb{R}}}u^{0}_{G}\,d{\tilde{\mu}}_{x,1}\leqslant
0\quad\hbox{if
$\theta\not=0$},\qquad\qquad\int_{{\mathbb{T}^{1}\times\mathbb{R}}}u_{H}^{0}\,d{\tilde{\mu}}_{x,2}\leqslant
0\quad\hbox{if $\theta\not=1$.}$

By exploiting this information in (6.13), we get $u(x)\geqslant u^{0}_{G}(x)$,
as it was to be shown. The proof is complete. ∎

## Appendix A

In this section we give an example of a continuous Hamiltonian $H$ on
${\mathbb{R}\times\mathbb{R}}$, 1–periodic in the $x$-variable, for which
condition (U) does not hold. The Hamiltonian $H$ is defined on
$[0,1]\times\mathbb{R}$ as follows:

$H(x,p):=(p-p_{1}(x))(p-p_{2}(x))+\varepsilon(x)|p-p_{1}(x)|\qquad\hbox{for
every $x\in[0,1]$ and $p\in\mathbb{R}$,}$

where $p_{1}(x):=-\cos(2\pi x)$ and $p_{2}(\cdot)$ is chosen in such a way
that $p_{2}(x)<p_{1}(x)$ for every $x\in(0,1)$ and

$\displaystyle\qquad p_{2}(x)=\begin{cases}-1&\hbox{for
$x\in\left[0,\dfrac{1}{2}+\dfrac{2}{100}\right]\cup\left[1-\dfrac{1}{100},1\right]$},\\\
\ &\\\ p_{1}(x)-\varepsilon_{1}&\hbox{for
$x\in\left[\dfrac{1}{2}+\dfrac{3}{100},1-\dfrac{3}{100}\right]$},\end{cases}$

with $\varepsilon_{1}>0$ small to be chosen later. The function
$\varepsilon(\cdot)$ is the piecewise affine function such that

$\varepsilon(0)=\varepsilon(1)=\dfrac{1}{100}\qquad\hbox{and}\qquad\varepsilon(x)=0\quad\hbox{for
all $x\in\left[\dfrac{1}{100},1-\dfrac{1}{100}\right]$}.$

We remark for later use that there exist $\rho>0$, independent of
$\varepsilon_{1}$, and $\varepsilon_{2}\in(0,\varepsilon_{1}]$ such that

$\displaystyle\varepsilon(x)+(p_{1}-p_{2})(x)\geqslant\rho\qquad\hbox{for all
$x\in\left[0,\dfrac{1}{2}+\dfrac{2}{100}\right]\cup\left[1-\dfrac{1}{100},1\right]$},$
(A.1)
$\displaystyle\varepsilon(x)+(p_{1}-p_{2})(x)\geqslant\varepsilon_{2}\qquad\hbox{for
all $x\in[0,1]$}.$

Let us show that $c_{f}(H)=c(H)=0$. To this aim, first note that the function
$u(x):=\int_{0}^{x}p_{1}(z)\,dz$ is a 1–periodic solution to the equation

$H(x,u^{\prime})=0\qquad\hbox{in $\mathbb{R}$.}$ (A.2)

This shows that $c_{f}(H)\leqslant c(H)=0$. The converse inequality can be
obtained as follows:

$c_{f}(H)=\max_{x}\min_{p}H(x,p)\geqslant\min_{p}H(0,p)=\min_{p}\left((p+1)^{2}+\dfrac{1}{100}|p+1|\right)=0.$

Furthermore, since $\min_{p}H(x,p)=\min_{p}(p-p_{1}(x))(p-p_{2}(x))<0$ for all
$x\in[1/100,1-1/100]$, we derive that the set of equilibria $\mathcal{E}(H)$
is contained in $[-1/100,1/100]+\mathbb{Z}$.

Let us now show that we are in case (ii) of Proposition 6.4. Indeed, the set

$Z_{H}(x):=\\{p\in\mathbb{R}\,:\,H(x,p)\leqslant 0\\}\qquad\hbox{for all
$x\in\mathbb{R}$}$

is a closed interval of the form $[p_{H}^{-}(x),p_{H}^{+}(x)]$. It is not hard
to see that $p_{H}^{+}(x)=p_{1}(x)$ for all $x\in\mathbb{R}$. We derive
$\int_{0}^{1}p^{+}_{H}(x)dx=\int_{0}^{1}p_{1}(x)dx=0.$ In this case, any
1-periodic subsolution $v$ to the critical equation (A.2) satisfies
$v^{\prime}(x)=p_{1}(x)$ for every $x\in\mathbb{R}$ (otherwise $v$ would not
be 1-periodic). In particular, 1-periodic subsolutions to (A.2) are unique up
to additive constants.

Now, let $\gamma:[0,T]\to\mathbb{R}$ be a curve satisfying $\gamma(0)=0,\
\gamma(T)=1$ and

$\dot{\gamma}(s)\in\varepsilon(\gamma(s))+(p_{1}-p_{2})(\gamma(s))\in\partial_{p}H\left(\gamma(s),p_{1}(\gamma(s))\right)\quad\hbox{for
all $s\in[0,T]$.}$

The measure $\tilde{\mu}\in\mathscr{P}({\mathbb{T}^{1}\times\mathbb{R}})$
defined as

$\int_{{\mathbb{R}\times\mathbb{R}}}f(y,q)\,d\tilde{\mu}:=\frac{1}{T}\int_{0}^{T}f\big{(}\gamma(s),\dot{\gamma}(s)\big{)}\,ds\qquad\hbox{for
every $f\in\mbox{\rm C}_{b}({\mathbb{T}^{1}\times\mathbb{R}})$}$ (A.3)

is a Mather measure. Indeed, it is closed, in the sense of Definition 3.1 with
$M:=\mathbb{T}^{1}$. Furthermore,

$L(\gamma(t),\dot{\gamma}(t))=p_{1}(\gamma(t))\dot{\gamma}(t)-H(\gamma(t),p_{1}(t))=\big{(}v\mbox{\scriptsize$\circ$}\gamma\big{)}^{\prime}(t)\qquad\hbox{for
every $t\in[0,T]$}$

and for any 1-periodic subsolution $v$ to (A.2), since
$v^{\prime}(x)=p_{1}(x)$ for all $x\in\mathbb{R}$, as remarked above. By
integrating this equality over $[0,T]$, we get that $\tilde{\mu}$ is a
minimizing Mather measure, cf. Theorem 3.2. Let us denote by $\mu$ the
projection of $\tilde{\mu}$ on $\mathbb{T}^{1}$ and by $u_{y}$, for every
fixed $y\in\mathbb{R}$, the unique 1-periodic solution to (A.2) such that
$u_{y}(y)=0$, i.e. the function $u_{y}(x):=\int_{y}^{x}p_{1}(z)dz$. We claim
that
Claim: there exists $\varepsilon_{1}>0$ small enough so that

$\int_{\mathbb{T}^{1}}u_{y}(x)\,d\mu(x)>0\qquad\hbox{for every
$y\in\left[-\dfrac{1}{100},\dfrac{1}{100}\right]$.}$

In particular, for such a choice of $\varepsilon_{1}$, condition (U) does not
hold. Indeed, the maximal 1-periodic subsolution $\hat{u}^{\,0}$ to (A.2)
satisfying $\hat{u}^{\,0}\leqslant 0$ on $\mathcal{E}(H)$ will be of the form
$u_{\hat{y}}$ for some $\hat{y}\in\mathcal{E}(H)$.

Let us proceed to prove the claim. We first notice that

$u_{y}(x)\geqslant 0\qquad\hbox{for every
$y\in\left[-\dfrac{1}{100},\dfrac{1}{100}\right]$ and
$x\in\left[\dfrac{1}{2}+\dfrac{1}{100},1-\dfrac{1}{100}\right]$.}$

Furthermore, there exists $\delta>0$ small enough such that

$u_{y}(x)\geqslant\delta\qquad\hbox{for every
$y\in\left[-\dfrac{1}{100},\dfrac{1}{100}\right]$ and
$x\in\left[\dfrac{1}{2}+\dfrac{3}{100},1-\dfrac{3}{100}\right]$.}$

We stress that such a $\delta>0$ is independent of $\varepsilon_{1}>0$. Let
$0<A<a<b<B<1$ such that

$\gamma(A)=\dfrac{1}{2}+\dfrac{2}{100},\quad\gamma(a)=\dfrac{1}{2}+\dfrac{3}{100},\quad\gamma(b)=1-\dfrac{3}{100},\quad\gamma(B)=1-\dfrac{1}{100}.$

From the definitions of $\gamma(\cdot)$ and $p_{1}(\cdot)$ and from (A.1) we
get

$\gamma(A)-\gamma(0)\geqslant\rho
A,\quad\gamma(b)-\gamma(a)=\varepsilon_{1}(b-a),\quad\gamma(1)-\gamma(B)\geqslant\rho(1-B),$

yielding in particular $A<1/\rho$, $1-B<1/\rho$ and
$b-a>1/(4\varepsilon_{1})$. Let us fix $y\in[-1/100,1/100]$. We have

$\displaystyle T\int_{\mathbb{T}^{1}}u_{y}\,d\,\mu$ $\displaystyle=$
$\displaystyle\int_{0}^{A}u_{y}(\gamma(t))\,dt+\int_{A}^{B}u_{y}(\gamma(t))\,dt+\int_{B}^{1}u_{y}(\gamma(t))\,dt$
$\displaystyle\geqslant$
$\displaystyle-2\|u_{y}\|_{\infty}(A+1-B)+\int_{a}^{b}u_{y}(\gamma(t))\,dt\geqslant-\dfrac{4}{\rho}+\dfrac{\delta}{4\varepsilon_{1}},$

where we have used the fact that $u_{y}(\gamma(t))\geqslant 0$ for all
$t\in[A,B]$ and $\|u_{y}\|_{\infty}\leqslant 1$. The claim readily follows
from this, by recalling that $\rho>0$ and $\delta>0$ do not depend on the
choice of $y\in[-1/100,1/100]$ and $\varepsilon_{1}>0$.

## References

  * [1] M. Arisawa and P.-L. Lions, On ergodic stochastic control, Comm. Partial Differential Equations, 23 (1998), pp. 2187–2217.
  * [2] S. N. Armstrong and H. V. Tran, Viscosity solutions of general viscous Hamilton-Jacobi equations, Math. Ann., 361 (2015), pp. 647–687.
  * [3] M. Bardi and I. Capuzzo-Dolcetta, Optimal control and viscosity solutions of Hamilton-Jacobi-Bellman equations, Systems & Control: Foundations & Applications, Birkhäuser Boston Inc., Boston, MA, 1997.  With appendices by Maurizio Falcone and Pierpaolo Soravia.
  * [4] M. Bardi and H. Kouhkouh, An Eikonal equation with vanishing Lagrangian arising in Global Optimization, arXiv e-prints, (2022), p. arXiv:2202.02561.
  * [5] G. Barles, Solutions de viscosité des équations de Hamilton-Jacobi, vol. 17 of Mathématiques & Applications (Berlin) [Mathematics & Applications], Springer-Verlag, Paris, 1994.
  * [6] P. Billingsley, Convergence of probability measures, Wiley Series in Probability and Statistics: Probability and Statistics, John Wiley & Sons, Inc., New York, second ed., 1999.  A Wiley-Interscience Publication.
  * [7] G. Buttazzo, M. Giaquinta, and S. Hildebrandt, One-dimensional variational problems. An introduction, vol. 15 of Oxford Lecture Series in Mathematics and its Applications, The Clarendon Press Oxford University Press, New York, 1998.
  * [8] F. Camilli and A. Siconolfi, Maximal subsolutions for a class of degenerate Hamilton-Jacobi problems, Indiana Univ. Math. J., 48 (1999), pp. 1111–1131.
  * [9] P. Cannarsa and C. Sinestrari, Semiconcave functions, Hamilton-Jacobi equations, and optimal control, Progress in Nonlinear Differential Equations and their Applications, 58, Birkhäuser Boston Inc., Boston, MA, 2004.
  * [10] I. Capuzzo-Dolcetta and H. Ishii, On the rate of convergence in homogenization of Hamilton-Jacobi equations, Indiana Univ. Math. J., 50 (2001), pp. 1113–1129.
  * [11] I. Capuzzo-Dolcetta and J.-L. Menaldi, Asymptotic behavior of the first order obstacle problem, J. Differential Equations, 75 (1988), pp. 303–328.
  * [12] P. Cardaliaguet and A. Porretta, Long time behavior of the master equation in mean field game theory, Anal. PDE, 12 (2019), pp. 1397–1453.
  * [13] Q. Chen, Convergence of solutions of hamilton-jacobi equations depending nonlinearly on the unknown function, Advances in Calculus of Variations, 0 (2021).
  * [14] Q. Chen, W. Cheng, H. Ishii, and K. Zhao, Vanishing contact structure problem and convergence of the viscosity solutions, Comm. Partial Differential Equations, 44 (2019), pp. 801–836.
  * [15] F. Colonius, Asymptotic behaviour of optimal control systems with low discount rates, Math. Oper. Res., 14 (1989), pp. 309–316.
  * [16] G. Contreras, Action potential and weak KAM solutions, Calc. Var. Partial Differential Equations, 13 (2001), pp. 427–458.
  * [17] A. Davini, A. Fathi, R. Iturriaga, and M. Zavidovique, Convergence of the solutions of the discounted Hamilton-Jacobi equation: convergence of the discounted solutions, Invent. Math., 206 (2016), pp. 29–55.
  * [18] A. Davini and A. Siconolfi, Exact and approximate correctors for stochastic Hamiltonians: the 1-dimensional case, Math. Ann., 345 (2009), pp. 749–782.
  * [19] A. Davini and L. Wang, On the vanishing discount problem from the negative direction, Discrete Contin. Dyn. Syst., 41 (2021), pp. 2377–2389.
  * [20] A. Davini and M. Zavidovique, Convergence of the solutions of discounted Hamilton-Jacobi systems, Adv. Calc. Var., 14 (2021), pp. 193–206.
  * [21] L. C. Evans, Periodic homogenisation of certain fully nonlinear partial differential equations, Proc. Roy. Soc. Edinburgh Sect. A, 120 (1992), pp. 245–265.
  * [22] A. Fathi, Weak KAM from a PDE point of view: viscosity solutions of the Hamilton-Jacobi equation and Aubry set, Proc. Roy. Soc. Edinburgh Sect. A, 142 (2012), pp. 1193–1236.
  * [23] A. Fathi and E. Maderna, Weak KAM theorem on non compact manifolds, NoDEA Nonlinear Differential Equations Appl., 14 (2007), pp. 1–27.
  * [24] A. Fathi and A. Siconolfi, Existence of $C^{1}$ critical subsolutions of the Hamilton-Jacobi equation, Invent. Math., 155 (2004), pp. 363–388.
  * [25] , PDE aspects of Aubry-Mather theory for quasiconvex Hamiltonians, Calc. Var. Partial Differential Equations, 22 (2005), pp. 185–228.
  * [26] L. Grüne and F. Wirth, On the rate of convergence of infinite horizon discounted optimal value functions, Nonlinear Anal. Real World Appl., 1 (2000), pp. 499–515.
  * [27] H. Ishii, The vanishing discount problem for monotone systems of Hamilton-Jacobi equations. Part 1: linear coupling, Math. Eng., 3 (2021), pp. Paper No. 032, 21.
  * [28] H. Ishii and L. Jin, The vanishing discount problem for monotone systems of Hamilton-Jacobi equations: part 2—nonlinear coupling, Calc. Var. Partial Differential Equations, 59 (2020), pp. Paper No. 140, 28.
  * [29] H. Ishii, H. Mitake, and H. V. Tran, The vanishing discount problem and viscosity Mather measures. Part 1: The problem on a torus, J. Math. Pures Appl. (9), 108 (2017), pp. 125–149.
  * [30] , The vanishing discount problem and viscosity Mather measures. Part 2: Boundary value problems, J. Math. Pures Appl. (9), 108 (2017), pp. 261–305.
  * [31] H. Ishii and A. Siconolfi, The vanishing discount problem for Hamilton-Jacobi equations in the Euclidean space, Comm. Partial Differential Equations, 45 (2020), pp. 525–560.
  * [32] R. Iturriaga and H. Sánchez-Morgado, Limit of the infinite horizon discounted Hamilton-Jacobi equation, Discrete Contin. Dyn. Syst. Ser. B, 15 (2011), pp. 623–635.
  * [33] P.-L. Lions, G. Papanicolaou, and S. Varadhan, Homogenization of Hamilton-Jacobi equation.  unpublished preprint, 1987.
  * [34] S. Marò and A. Sorrentino, Aubry-Mather theory for conformally symplectic systems, Comm. Math. Phys., 354 (2017), pp. 775–808.
  * [35] H. Mitake and H. V. Tran, Selection problems for a discount degenerate viscous Hamilton-Jacobi equation, Adv. Math., 306 (2017), pp. 684–703.
  * [36] A. Siconolfi, Hamilton-Jacobi equations and weak KAM theory, in Mathematics of complexity and dynamical systems. Vols. 1–3, Springer, New York, 2012, pp. 683–703.
  * [37] M. Zavidovique, Convergence of solutions for some degenerate discounted Hamilton–Jacobi equations, arXiv e-prints, (2020), p. arXiv:2006.00779.