np\mathbb{E}[X\sqrt{\min\\{X,a\\}\min\\{X,b\\}}\mathds{1}(X\geq 4)],$

where the second inequality above uses the fact that
$Y\sqrt{\min\\{Y,a\\}\min\\{Y,b\\}}\mathds{1}(Y\geq
4)\leq(X_{1}+Y)\sqrt{\min\\{(X_{1}+Y),a\\}\min\\{(X_{1}+Y),b\\}}\mathds{1}(X_{1}+Y\geq
4)$. On the other hand, using inequality (i), we can obtain

$\displaystyle n\mathrm{(II)}\leavevmode\nobreak\
\lesssim\lambda\min\\{ab,a\lambda,\lambda^{2}+\lambda\\}.$ (17)

Combining pieces. By the Efron–Stein inequality (Lemma 8), we obtained that

$\displaystyle\mathrm{Var}\bigl{[}X\sqrt{\min\\{X,a\\}\min\\{X,b\\}}\mathds{1}(X\geq
4)\bigr{]}\lesssim n\mathrm{(I)}+n\mathrm{(II)}.$

By focusing on $n\mathrm{(I)}$, the bound given in (15) together with Lemma 4
shows that

$\displaystyle
n\mathrm{(I)}\lesssim\min\\{np,\sqrt{ab}\\}\mathbb{E}\bigl{[}X\sqrt{\min\\{X,a\\}\min\\{X,b\\}}\mathds{1}(X\geq
4)\bigr{]}.$

Therefore, it suffices to prove

$\displaystyle
n\mathrm{(II)}\lesssim\min\\{np,\sqrt{ab}\\}\mathbb{E}\bigl{[}X\sqrt{\min\\{X,a\\}\min\\{X,b\\}}\mathds{1}(X\geq
4)\bigr{]}.$ (18)

Due to the inequality established in (16), we know that

$\displaystyle n\mathrm{(II)}\lesssim
np\mathbb{E}\bigl{[}X\sqrt{\min\\{X,a\\}\min\\{X,b\\}}\mathds{1}(X\geq
4)\bigr{]}\quad\text{for all $n\geq 9$ and $p\in[0,1]$.}$

Hence, by assuming $\lambda=np>1$ (when $\lambda\leq 1$,
$\min\\{\lambda,\sqrt{ab}\\}=\lambda$), we only need to prove that

$\displaystyle
n\mathrm{(II)}\lesssim\sqrt{ab}\mathbb{E}\bigl{[}X\sqrt{\min\\{X,a\\}\min\\{X,b\\}}\mathds{1}(X\geq
4)\bigr{]},$

which is implied by

$\displaystyle\lambda\min\\{ab,a\lambda,\lambda^{2}+\lambda\\}\lesssim\sqrt{ab}\min\bigl{\\{}\lambda\sqrt{\min(\lambda,a)\min(\lambda,b)},\lambda^{4}\bigr{\\}},$

due to Lemma 4 and the previous result (17). Moreover, since we assume
$\lambda>1$, the above condition is satisfied when

$\displaystyle\min\\{(ab)^{2},a^{2}\lambda^{2}\\}\lesssim
ab\min(\lambda,a)\min(\lambda,b).$ (19)

Now we see that

  * •

if $\lambda\leq a\leq b$, the sufficient condition (19) becomes

$\displaystyle a^{2}\lambda^{2}\lesssim ab\lambda^{2}\ \Longleftrightarrow\
a\lesssim b,$

  * •

if $a\leq\lambda\leq b$, the sufficient condition (19) becomes

$\displaystyle a^{2}\lambda^{2}\lesssim a^{2}b\lambda\ \Longleftrightarrow\
\lambda\lesssim b,$

  * •

if $a\leq b\leq\lambda$, the sufficient condition (19) becomes

$\displaystyle(ab)^{2}\lesssim(ab)^{2}.$

Therefore we verify the sufficient condition (19) and thus complete the proof
of Lemma 3.

###  C.8 Proof of Lemma 4

The proof of this lemma essentially follows the same lines of the proof of
Claim 2.3 in Canonne et al., (2018). There are only two conditions that we
need to check for a binomial random variable.

Condition 1. Suppose that $\lambda<8$. For a Poisson random variable
$Y\sim\mathrm{Poisson}(\lambda)$, Canonne et al., (2018) shows that

$\displaystyle\mathbb{E}\bigl{[}Y\sqrt{\min\\{Y,a\\}\min\\{Y,b\\}}\mathds{1}(Y\geq
4)\bigr{]}\geq\frac{1}{768}\min\bigl{\\{}\lambda\sqrt{\min(\lambda,a)\min(\lambda,b)},\lambda^{4}\bigr{\\}}.$
(20)

The main step for the above result is $\mathbb{P}(Y=4)\geq\lambda^{4}/(4!)$.
We claim that the same bound holds for $X\sim\mathrm{Binomial}(n,p)$ where
$n\geq 9$ up to some constant factor. Indeed, we can write

$\displaystyle\mathbb{P}(X=4)\leavevmode\nobreak\ =\leavevmode\nobreak\ $
$\displaystyle\binom{n}{4}p^{4}(1-p)^{n-4}$
$\displaystyle\geq\leavevmode\nobreak\ $
$\displaystyle\frac{14}{729}\lambda^{4}\biggl{(}1-\frac{\lambda}{n}\biggr{)}^{n-4}$
$\displaystyle\geq\leavevmode\nobreak\ $
$\displaystyle\frac{14}{729}\biggl{(}1-\frac{8}{9}\biggr{)}^{5}\lambda^{4},$

where the inequalities use the fact that $n\geq 9$ and $\lambda<8$. We then
follow the same steps in Canonne et al., (2018) and conclude that inequality
(20) holds when $Y$ is replaced by $X$ up to some constant factor.

Condition 2. The second condition Canonne et al., (2018) makes use of is that
for $Y\sim\mathrm{Poisson}(\lambda)$ and $\lambda\geq 8$,
$\mathbb{P}(Y\geq\lfloor\lambda/2\rfloor)\geq 1/2$. We now prove that the same
inequality holds for $X\sim\mathrm{Binomial}(n,p)$. First assume that
$\lfloor\lambda/2\rfloor\neq 0$. Otherwise, the claim is trivial. By
Chebyshev’s inequality

$\displaystyle\mathbb{P}(X<\lfloor\lambda/2\rfloor)\leavevmode\nobreak\
=\leavevmode\nobreak\ $
$\displaystyle\mathbb{P}(-X+\lambda>\lambda-\lfloor\lambda/2\rfloor)$
$\displaystyle\leq\leavevmode\nobreak\ $
$\displaystyle\frac{\mathrm{Var}[X]}{(\lambda-\lfloor\lambda/2\rfloor)^{2}}\leq\frac{4\lambda}{\lambda^{2}}=\frac{4}{\lambda}.$

Now $\mathbb{P}(X\geq\lfloor\lambda/2\rfloor)\geq 1/2$ holds since we assume
$\lambda\geq 8$. Given this probability bound, we can follow the same lines of
the proof in Canonne et al., (2018) and show that

$\displaystyle\mathbb{E}\bigl{[}X\sqrt{\min\\{X,a\\}\min\\{X,b\\}}\mathds{1}(X\geq
4)\bigr{]}\gtrsim\min\bigl{\\{}\lambda\sqrt{\min(\lambda,a)\min(\lambda,b)},\lambda^{4}\bigr{\\}}.$

for $\lambda\geq 8$. This completes the proof of Lemma 4.

###  C.9 Proof of Lemma 6

Both statements follow by applying Lemma 5 with specific choices of
$A_{1},A_{2},f_{1},f_{2}$. In particular, the first result holds by taking
$A_{1}=\\{i\\}$, $A_{2}=\\{j\\}$, and $f_{1}(x)=f_{2}(x)=x\mathds{1}(x\geq
4)$. The second statement follows similarly by taking $A_{1}=\\{i\\}$,
$A_{2}=\\{j\\}$, and $f_{1}(x)=f_{2}(x)=x\mathds{1}(x\geq
4)\sqrt{\min\\{x,\ell_{1}\\}\min\\{x,\ell_{2}\\}}$.

###  C.10 Proof of Lemma 7

By the definition of the quantile function and letting $V_{0}:=V$,
$q_{1-\alpha}$ can be written as

$\displaystyle q_{1-\alpha}\leavevmode\nobreak\ =\leavevmode\nobreak\ $
$\displaystyle\inf\bigg{\\{}x\in\mathbb{R}:1-\alpha\leq\frac{1}{B+1}\sum_{i=0}^{B}\mathds{1}\big{(}V_{i}\leq
x\big{)}\bigg{\\}}$ $\displaystyle=\leavevmode\nobreak\ $ $\displaystyle
V_{(k)},$

where $V_{(k)}$ is the $k=\lceil(1-\alpha)(B+1)\rceil$th order statistic of
$\\{V_{0},V_{1},\ldots,V_{B}\\}$. Given this representation, we see that
$V\leq q_{1-\alpha}$ holds if and only if

$\displaystyle\frac{1}{B+1}\sum_{i=0}^{B}\mathds{1}\bigl{(}V_{i}<V\bigr{)}<1-\alpha,$

which is equivalent to

$\displaystyle\frac{1}{B+1}\Biggl{[}\sum_{i=1}^{B}\mathds{1}(V_{i}\geq
V)+1\Biggr{]}>\alpha.$

This completes the proof of Lemma 7.