$\displaystyle{\hat{\Gamma}}({q}_{0}^{\prime})\leq\frac{266.45}{(f(1)-f(0))^{2}}d\log\left(\frac{2n}{\varepsilon}\right)$
(133)

for ${q}_{0}^{\prime}=\frac{1}{d+1}\in\left(\frac{{L}}{d},\frac{1}{d}\right)$,
and

$\displaystyle{\hat{\Gamma}}({q}_{0}^{\prime\prime})\leq\frac{266.45}{(f(2)-f(1))^{2}}d\log\left(\frac{2n}{\varepsilon}\right)$
(134)

for
${q}_{0}^{\prime\prime}=\frac{d}{d+1}\in\left(\frac{1}{d},\frac{{U}}{d}\right)$.
Since

$\displaystyle\min\left\\{\frac{1}{(f(1)-f(0))^{2}},\frac{1}{(f(2)-f(1))^{2}}\right\\}$
$\displaystyle\leq\frac{2}{(f(1)-f(0))^{2}+(f(2)-f(1))^{2}}$
$\displaystyle\leq\frac{4}{(f(2)-f(0))^{2}},$ (135)

it follows that

$\displaystyle{\hat{\Gamma}}({q}_{0})$
$\displaystyle\leq\min\left\\{\frac{266.45}{(f(1)-f(0))^{2}}d\log\left(\frac{2n}{\varepsilon}\right),\frac{266.45}{(f(2)-f(1))^{2}}d\log\left(\frac{2n}{\varepsilon}\right)\right\\}$
$\displaystyle\leq
266.45\times\min\left\\{\frac{1}{(f(1)-f(0))^{2}},\frac{1}{(f(2)-f(1))^{2}}\right\\}\times
d\log\left(\frac{2n}{\varepsilon}\right)$ $\displaystyle\leq
266.45\times\frac{4}{(f(2)-f(0))^{2}}d\log\left(\frac{2n}{\varepsilon}\right)$
$\displaystyle=266.45\times\frac{1}{{\beta}^{2}}\left(\frac{{U}-{L}}{f({U})-f({L})}\right)^{2}d\log\left(\frac{2n}{\varepsilon}\right)$
$\displaystyle\leq{376017\times\frac{1}{{\beta}^{2}}\left(\frac{{U}-{L}}{f({U})-f({L})}\right)^{2}d\log\left(\frac{2n}{\varepsilon}\right)}$
(136)

for some ${q}_{0}\in\left(\frac{{L}}{d},\frac{{U}}{d}\right)$.

  * •

$d\geq 3$: Applying Proposition 5 with ${L}^{\prime}=1$ and
${U}^{\prime}=d-1$, we have that ${{\alpha}}=\frac{1}{2}$

$\displaystyle{\hat{\Gamma}}({q}_{0}^{\prime})\leq
125339\times\left(\frac{d-2}{f(d-1)-f(1)}\right)^{2}d\log\left(\frac{2n}{\varepsilon}\right)$
(137)

for some ${q}_{0}^{\prime}\in\left(\frac{1}{d},\frac{d-1}{d}\right)$. On the
other hand, Proposition 6 gives

$\displaystyle{\hat{\Gamma}}({q}_{0}^{\prime\prime})\leq\frac{266.45}{(f(1)-f(0))^{2}}d\log\left(\frac{2n}{\varepsilon}\right)$
(138)

for
${q}_{0}^{\prime\prime}=\frac{1}{d+1}\in\left(\frac{{L}}{d},\frac{1}{d}\right)$,
and

$\displaystyle{\hat{\Gamma}}({q}_{0}^{\prime\prime\prime})\leq\frac{266.45}{(f(d)-f(d-1))^{2}}d\log\left(\frac{2n}{\varepsilon}\right)$
(139)

for
${q}_{0}^{\prime\prime\prime}=\frac{d}{d+1}\in\left(\frac{d-1}{d},\frac{{U}}{d}\right)$.
Since

$\displaystyle\min\left\\{\frac{1}{(f(1)-f(0))^{2}},\frac{1}{(f(d)-f(d-1))^{2}},\frac{(d-2)^{2}}{(f(d-1)-f(1))^{2}}\right\\}$
$\displaystyle\leq\frac{1+1+(d-2)^{2}}{(f(1)-f(0))^{2}+(f(d)-f(d-1))^{2}+(f(d-1)-f(1))^{2}}$
$\displaystyle\leq\frac{3d^{2}}{(f(d)-f(0))^{2}},$ (140)

it follows that

$\displaystyle{\hat{\Gamma}}({q}_{0})$
$\displaystyle\leq\min\Bigg{\\{}125339\times\left(\frac{d-2}{f(d-1)-f(1)}\right)^{2}d\log\left(\frac{2n}{\varepsilon}\right),\frac{266.45}{(f(1)-f(0))^{2}}d\log\left(\frac{2n}{\varepsilon}\right),$
$\displaystyle\kern
230.00035pt\frac{266.45}{(f(d)-f(d-1))^{2}}d\log\left(\frac{2n}{\varepsilon}\right)\Bigg{\\}}$
$\displaystyle\leq
125339\times\min\left\\{\frac{(d-2)^{2}}{(f(d-1)-f(1))^{2}},\frac{1}{(f(1)-f(0))^{2}},\frac{1}{(f(d)-f(d-1))^{2}}\right\\}\times
d\log\left(\frac{2n}{\varepsilon}\right)$ $\displaystyle\leq
376017\times\frac{d^{2}}{(f(d)-f(0))^{2}}d\log\left(\frac{2n}{\varepsilon}\right)$
$\displaystyle={376017\times\frac{1}{{\beta}^{2}}\left(\frac{{U}-{L}}{f({U})-f({L})}\right)^{2}d\log\left(\frac{2n}{\varepsilon}\right)}$
(141)

for some ${q}_{0}\in\left(\frac{{L}}{d},\frac{{U}}{d}\right)$.

Summarizing the above, we see that for any $0\leq{L}<{U}\leq d$, there exists
${q}_{0}\in\left(\frac{{L}}{d},\frac{{U}}{d}\right)$ such that

$\displaystyle{\hat{\Gamma}}({q}_{0})\leq{376017\times\frac{1}{{\beta}^{2}}\left(\frac{{U}-{L}}{f({U})-f({L})}\right)^{2}d\log\left(\frac{2n}{\varepsilon}\right)}.$

This along with the definitions of ${H(f)}$ and ${\beta}$ in (18) and (119),
respectively, yields

$\displaystyle{\hat{\Gamma}}({q}_{0})\leq
376017{H(f)}d\log\left(\frac{2n}{\varepsilon}\right)$ (142)

for some ${q}_{0}\in(0,1)$. Proposition 3 is proved.

##  Appendix E Proof of Proposition 5

The following technical result will serve as a stepping stone to establishing
Proposition 5.

###### Lemma 12

Let $d\geq 3$. For any ${L}^{\prime},{U}^{\prime}\in\\{1,\dots,d-1\\}$ with
${L}^{\prime}<{U}^{\prime}$ and $f({L}^{\prime})<f({U}^{\prime})$, there
exists ${q}_{0}\in\left(\frac{{L}^{\prime}}{d},\frac{{U}^{\prime}}{d}\right)$
such that ${\hat{\Gamma}}({q}_{0})$ defined in (14) satisfies

${\hat{\Gamma}}({q}_{0})\leq
1253.39\times\frac{(d-{L}^{\prime}){U}^{\prime}}{{\alpha}^{2}(d-{U}^{\prime}){L}^{\prime}}\left(\frac{{U}^{\prime}-{L}^{\prime}}{f({U}^{\prime})-f({L}^{\prime})}\right)^{2}d\log\left(\frac{2n}{\varepsilon}\right),$
(143)

where
${\alpha}:=\frac{1}{2}\min\left\\{{U}^{\prime}-{L}^{\prime},\sqrt{{L}^{\prime}},\sqrt{d-{U}^{\prime}}\right\\}$.

###### Proof:

See Appendix F. ∎

Comparing Proposition 5 and Lemma 12, we see that the main difference is the
$\frac{(d-{L}^{\prime}){U}^{\prime}}{(d-{U}^{\prime}){L}^{\prime}}$ term. In
the remainder of the proof, we manage to eliminate the
$\frac{(d-{L}^{\prime}){U}^{\prime}}{(d-{U}^{\prime}){L}^{\prime}}$ term from
(143). Since
${\alpha}=\frac{1}{2}\min\left\\{{U}^{\prime}-{L}^{\prime},\sqrt{{L}^{\prime}},\sqrt{d-{U}^{\prime}}\right\\}$,
we consider the following two cases.

Case i): ${\alpha}=\frac{{U}^{\prime}-{L}^{\prime}}{2}$, i.e.,

$\displaystyle{U}^{\prime}-{L}^{\prime}\leq\min\left\\{\sqrt{{L}^{\prime}},\sqrt{d-{U}^{\prime}}\right\\}.$
(144)

Then we immediately obtain

$\frac{(d-{L}^{\prime}){U}^{\prime}}{(d-{U}^{\prime}){L}^{\prime}}\leq\frac{(d-{U}^{\prime}+\sqrt{d-{U}^{\prime}})({L}^{\prime}+\sqrt{{L}^{\prime}})}{(d-{U}^{\prime}){L}^{\prime}}=\frac{\sqrt{d-{U}^{\prime}}+1}{\sqrt{d-{U}^{\prime}}}\cdot\frac{\sqrt{{L}^{\prime}}+1}{\sqrt{{L}^{\prime}}}\leq
2\times 2<25,$ (145)

where the second inequality follows from the assumption that
$1\leq{L}^{\prime}<{U}^{\prime}\leq d-1$. Substituting into (143), we have the
desired result (116).

Case ii): ${\alpha}\neq\frac{{U}^{\prime}-{L}^{\prime}}{2}$, i.e.,

${\alpha}=\frac{1}{2}\min\left\\{\sqrt{{L}^{\prime}},\sqrt{d-{U}^{\prime}}\right\\}<\frac{{U}^{\prime}-{L}^{\prime}}{2}.$
(146)

Define

$\displaystyle{\tau}$
$\displaystyle:=\left\lfloor\frac{{U}^{\prime}-{L}^{\prime}}{\lceil
2{{\alpha}}\rceil}\right\rfloor,$ (147) $\displaystyle{{\lambda}_{{i}}}$
$\displaystyle:={L}^{\prime}+{i}\cdot\lceil 2{{\alpha}}\rceil\text{ for
}{i}=0,\cdots,{\tau}-1,$ (148) $\displaystyle{{\lambda}_{{\tau}}}$
$\displaystyle:={U}^{\prime}.$ (149)

For the ease of notation, let

$\displaystyle{{{\alpha}}_{{i}}}:=\frac{1}{2}\min\left\\{{{\lambda}_{{i}+1}}-{{\lambda}_{{i}}},\sqrt{{{\lambda}_{{i}}}},\sqrt{d-{{\lambda}_{{i}+1}}}\right\\}\text{
for }{i}=0,\cdots,{\tau}-1.$ (150)

The following lemma shows that for all $i=0,\dots,{\tau}-1$,
${{{\alpha}}_{{i}}}$ is bounded from below by ${\alpha}$.

###### Lemma 13

${{{\alpha}}_{{i}}}\geq{{\alpha}}$ for all ${i}\in\\{0,\cdots,{\tau}-1\\}$.

###### Proof:

For ${i}=0,\cdots,{\tau}-1$, we have from (148) that

$\displaystyle{L}^{\prime}\leq{{\lambda}_{{i}}}<{{\lambda}_{{i}+1}}\leq{U}^{\prime}.$
(151)

It follows that

$\frac{1}{2}\min\left\\{\sqrt{{{\lambda}_{{i}}}},\sqrt{d-{{\lambda}_{{i}+1}}}\right\\}\geq\frac{1}{2}\min\left\\{\sqrt{{L}^{\prime}},\sqrt{d-{U}^{\prime}}\right\\}={{\alpha}}.$
(152)

Next, for ${i}=0,\cdots,{\tau}-2$,

$\frac{{{\lambda}_{{i}+1}}-{{\lambda}_{{i}}}}{2}=\frac{\lceil
2{{\alpha}}\rceil}{2}\geq{{\alpha}};$ (153)

for ${i}={\tau}-1$,

$\frac{{{\lambda}_{{\tau}}}-{{\lambda}_{{\tau}-1}}}{2}=\frac{{U}^{\prime}-{L}^{\prime}-({\tau}-1)\lceil
2{{\alpha}}\rceil}{2}\geq\frac{{U}^{\prime}-{L}^{\prime}-\left(\frac{{U}^{\prime}-{L}^{\prime}}{\lceil
2{{\alpha}}\rceil}-1\right)\lceil 2{{\alpha}}\rceil}{2}=\frac{\lceil
2{{\alpha}}\rceil}{2}\geq{{\alpha}}.$ (154)

Combining the above three inequalities, along with the definition of
${{{\alpha}}_{{i}}}$ in (150), yields the desired result. ∎

To complete the proof of Case ii), the following two lemmas will also be used.

###### Lemma 14

$\frac{(d-{{\lambda}_{{i}}}){{\lambda}_{{i}+1}}}{(d-{{\lambda}_{{i}+1}}){{\lambda}_{{i}}}}\leq
25$ for any ${i}=0,\cdots,{\tau}-1$.

###### Proof:

Observe that for any ${i}=0,\cdots,{\tau}-2$,

${{\lambda}_{{i}+1}}-{{\lambda}_{{i}}}=\lceil 2{{\alpha}}\rceil\leq
4{{\alpha}}+2;$ (155)

and for ${i}={\tau}-1$,

$\displaystyle{{\lambda}_{{\tau}}}-{{\lambda}_{{\tau}-1}}$
$\displaystyle={U}^{\prime}-({L}^{\prime}+({\tau}-1)\lceil 2{{\alpha}}\rceil)$
$\displaystyle={U}^{\prime}-{L}^{\prime}-\left(\left\lfloor\frac{{U}^{\prime}-{L}^{\prime}}{\lceil
2{{\alpha}}\rceil}\right\rfloor-1\right)\lceil 2{{\alpha}}\rceil$
$\displaystyle<{U}^{\prime}-{L}^{\prime}-\left(\frac{{U}^{\prime}-{L}^{\prime}}{\lceil
2{{\alpha}}\rceil}-2\right)\lceil 2{{\alpha}}\rceil$ $\displaystyle=2\lceil
2{{\alpha}}\rceil$ $\displaystyle\leq 4{{\alpha}}+2.$ (156)

It then follows that for all ${i}=0,\cdots,{\tau}-1$,

$\displaystyle{{\lambda}_{{i}+1}}-{{\lambda}_{{i}}}$ $\displaystyle\leq
4{{\alpha}}+2$
$\displaystyle=2\min\\{\sqrt{{L}^{\prime}},\sqrt{d-{U}^{\prime}}\\}+2$
$\displaystyle\leq 4\min\\{\sqrt{{L}^{\prime}},\sqrt{d-{U}^{\prime}}\\}$
$\displaystyle\leq
4\min\\{\sqrt{{{\lambda}_{{i}}}},\sqrt{d-{{\lambda}_{{i}+1}}}\\},$ (157)

where the equality follows from (146); the second inequality follows from the
assumption that $1\leq{L}^{\prime}<{U}^{\prime}\leq d-1$; the last inequality
follows from (151). Using this observation along with
$1\leq{{\lambda}_{{i}}}\leq{{\lambda}_{{i}+1}}\leq d-1$, we obtain

$\frac{(d-{{\lambda}_{{i}}}){{\lambda}_{{i}+1}}}{(d-{{\lambda}_{{i}+1}}){{\lambda}_{{i}}}}\leq\frac{(d-{{\lambda}_{{i}+1}}+4\sqrt{d-{{\lambda}_{{i}+1}}})({{\lambda}_{{i}}}+4\sqrt{{{\lambda}_{{i}}}})}{(d-{{\lambda}_{{i}+1}}){{\lambda}_{{i}}}}=\frac{(\sqrt{d-{{\lambda}_{{i}+1}}}+4)}{\sqrt{d-{{\lambda}_{{i}+1}}}}\cdot\frac{(\sqrt{{{\lambda}_{{i}}}}+4)}{\sqrt{{{\lambda}_{{i}}}}}\leq
5\times 5=25,$ (158)

which finishes the proof. ∎

###### Lemma 15

$\exists{\ell}\in\\{0,\cdots,{\tau}-1\\}$ such that
$\frac{f({{\lambda}_{{\ell}+1}})-f({{\lambda}_{{\ell}}})}{{{\lambda}_{{\ell}+1}}-{{\lambda}_{{\ell}}}}\geq\frac{f({U}^{\prime})-f({L}^{\prime})}{{U}^{\prime}-{L}^{\prime}}$.

###### Proof:

Suppose to the contrary that
$\frac{f({{\lambda}_{{i}+1}})-f({{\lambda}_{{i}}})}{({{\lambda}_{{i}+1}}-{{\lambda}_{{i}}})}<\frac{f({U}^{\prime})-f({L}^{\prime})}{{U}^{\prime}-{L}^{\prime}}$
for all ${i}=0,\cdots,{\tau}-1$. In other words,

$f({{\lambda}_{{i}+1}})-f({{\lambda}_{{i}}})<\frac{f({U}^{\prime})-f({L}^{\prime})}{{U}^{\prime}-{L}^{\prime}}({{\lambda}_{{i}+1}}-{{\lambda}_{{i}}}),\forall{i}=0,\cdots,{\tau}-1.$
(159)

Summing (159) over all ${i}\in\\{0,\cdots,{\tau}-1\\}$, we obtain that

$f({U}^{\prime})-f({L}^{\prime})=\sum\limits_{{i}=0}^{{\tau}-1}\left(f({{\lambda}_{{i}+1}})-f({{\lambda}_{{i}}})\right)<\sum\limits_{{i}=0}^{{\tau}-1}\frac{f({U}^{\prime})-f({L}^{\prime})}{{U}^{\prime}-{L}^{\prime}}({{\lambda}_{{i}+1}}-{{\lambda}_{{i}}})=f({U}^{\prime})-f({L}^{\prime})$
(160)

yielding a contradiction. Lemma 15 is proved. ∎

We are now ready to finish the proof of Case ii) using the above results. Upon
applying Lemma 12 with ${L}^{\prime}={{\lambda}_{{\ell}}}$ and
${U}^{\prime}={{\lambda}_{{\ell}+1}}$ as defined in Lemma 15, we have that
$\exists{q}_{0}\in\left(\frac{{{\lambda}_{{\ell}}}}{d},\frac{{{\lambda}_{{\ell}+1}}}{d}\right)$
such that

$\displaystyle{\hat{\Gamma}}({q}_{0})$ $\displaystyle\leq
1253.39\times\frac{(d-{{\lambda}_{{\ell}}}){{\lambda}_{{\ell}+1}}}{{{{\alpha}}_{{\ell}}}^{2}(d-{{\lambda}_{{\ell}+1}}){{\lambda}_{{\ell}}}}\left(\frac{{{\lambda}_{{\ell}+1}}-{{\lambda}_{{\ell}}}}{f({{\lambda}_{{\ell}+1}})-f({{\lambda}_{{\ell}}})}\right)^{2}d\log\left(\frac{2n}{\varepsilon}\right)$
$\displaystyle\leq
31334.75\times\frac{1}{{{{\alpha}}_{{\ell}}}^{2}}\left(\frac{{{\lambda}_{{\ell}+1}}-{{\lambda}_{{\ell}}}}{f({{\lambda}_{{\ell}+1}})-f({{\lambda}_{{\ell}}})}\right)^{2}d\log\left(\frac{2n}{\varepsilon}\right)$
$\displaystyle\leq
31334.75\times\frac{1}{{{{\alpha}}_{{\ell}}}^{2}}\left(\frac{{U}^{\prime}-{L}^{\prime}}{f({U}^{\prime})-f({L}^{\prime})}\right)^{2}d\log\left(\frac{2n}{\varepsilon}\right)$
$\displaystyle\leq
31334.75\times\frac{1}{{{\alpha}}^{2}}\left(\frac{{U}^{\prime}-{L}^{\prime}}{f({U}^{\prime})-f({L}^{\prime})}\right)^{2}d\log\left(\frac{2n}{\varepsilon}\right)$
(161)

where the second inequality follows from Lemma 14; the third inequality
follows from Lemma 15; the last inequality follows from Lemma 13. This
completes the proof of Proposition 5.

##  Appendix F Proof of Lemma 12

We now prove Lemma 12, first giving some preliminary lemmas.

###### Lemma 16

For any $j=1,\dots,d-1$, we have

$\frac{\sqrt{2\pi}}{e^{2}}\sqrt{\frac{d}{j(d-j)}}\leq\binom{d}{j}\left(\frac{j}{d}\right)^{j}\left(\frac{d-j}{d}\right)^{d-j}\leq\frac{e}{\pi}\sqrt{\frac{d}{j(d-j)}}.$

###### Proof:

We shall use the following well-known Stirling’s approximation [30] for the
factorial function.

######  Fact 2 (Stirling’s approximation [30])

$\sqrt{2\pi}\,n^{n+\frac{1}{2}}\,e^{-n}\leq n!\leq
e\,n^{n+\frac{1}{2}}\,e^{-n}.$ (162)

Using the upper and lower bounds on $n!$ in (162), we have

$\displaystyle\binom{d}{j}\left(\frac{j}{d}\right)^{j}\left(\frac{d-j}{d}\right)^{d-j}$
$\displaystyle=\frac{d!}{j!(d-j)!}\left(\frac{j}{d}\right)^{j}\left(\frac{d-j}{d}\right)^{d-j}$
$\displaystyle\geq\frac{\sqrt{2\pi}d^{d+1/2}e^{-d}}{ej^{j+1/2}e^{-j}e(d-j)^{d-j+1/2}e^{-d+j}}\left(\frac{j}{d}\right)^{j}\left(\frac{d-j}{d}\right)^{d-j}$
$\displaystyle=\frac{\sqrt{2\pi}}{e^{2}}\sqrt{\frac{d}{j(d-j)}}.$

Similarly, we also have

$\displaystyle\binom{d}{j}\left(\frac{j}{d}\right)^{j}\left(\frac{d-j}{d}\right)^{d-j}$
$\displaystyle=\frac{d!}{j!(d-j)!}\left(\frac{j}{d}\right)^{j}\left(\frac{d-j}{d}\right)^{d-j}$
$\displaystyle\leq\frac{ed^{d+1/2}e^{-d}}{\sqrt{2\pi}j^{j+1/2}e^{-j}\sqrt{2\pi}(d-j)^{d-j+1/2}e^{-d+j}}\left(\frac{j}{d}\right)^{j}\left(\frac{d-j}{d}\right)^{d-j}$
$\displaystyle=\frac{e}{2\pi}\sqrt{\frac{d}{j(d-j)}}.$

Combining the two bounds gives the desired result. ∎

###### Lemma 17

For any $j>i>0$ and $d>j+i$, we have

$\displaystyle\int_{\frac{j}{d}}^{\frac{j+i}{d}}{q}^{j}(1-{q})^{d-j}{\,\mathrm{d}}{q}$
$\displaystyle\geq\left(\frac{j}{d}\right)^{j}\left(\frac{d-j}{d}\right)^{d-j}\frac{j(d-j-i)}{id^{2}}\left(1-\exp\left(\frac{-i^{2}d}{j(d-j-i)}\right)\right),$
(163)
$\displaystyle\int_{\frac{j-i}{d}}^{\frac{j}{d}}{q}^{j}(1-{q})^{d-j}{\,\mathrm{d}}{q}$
$\displaystyle\geq\left(\frac{j}{d}\right)^{j}\left(\frac{d-j}{d}\right)^{d-j}\frac{(j-i)(d-j)}{id^{2}}\left(1-\exp\left(\frac{-i^{2}d}{(j-i)(d-j)}\right)\right).$
(164)

###### Proof:

We first prove (163). Define

$\displaystyle{\varphi}(x):=j\ln(j+xd)+(d-j)\ln(d-j-xd),\quad
x\in\left[-\frac{i}{d},\frac{i}{d}\right].$ (165)

Taking the derivative of ${\varphi}(x)$, we obtain that

${\varphi}^{\prime}(x)=\frac{-xd^{3}}{(j+xd)(d-j-
xd)}\geq\frac{-xd^{3}}{j(d-j-i)}\geq\frac{-id^{2}}{j(d-j-i)},\;\forall
x\in\left[0,\frac{i}{d}\right].$

This implies that

${\varphi}({t})-{\varphi}(0)=\int_{0}^{t}{\varphi}^{\prime}(x){\,\mathrm{d}}x\geq\int_{0}^{t}\frac{-id^{2}}{j(d-j-i)}{\,\mathrm{d}}x=\frac{-id^{2}}{j(d-j-i)}{t},\;\forall{t}\in\left[0,\frac{i}{d}\right].$
(166)

By the definition of ${\varphi}$ in (165), we have

$\displaystyle{\varphi}({t})-{\varphi}(0)=\ln\left(\left(\frac{j+{t}d}{j}\right)^{j}\left(\frac{d-j-{t}d}{d-j}\right)^{d-j}\right),\;\forall{t}\in\left[-\frac{i}{d},\frac{i}{d}\right].$
(167)

It follows that

$\displaystyle\int_{\frac{j}{d}}^{\frac{j+i}{d}}{q}^{j}(1-{q})^{d-j}{\,\mathrm{d}}{q}$
$\displaystyle=\int_{0}^{\frac{i}{d}}\left(\frac{j+{t}d}{d}\right)^{j}\left(\frac{d-j-{t}d}{d}\right)^{d-j}{\,\mathrm{d}}{t}$
$\displaystyle=\int_{0}^{\frac{i}{d}}\left(\frac{j}{d}\right)^{j}\left(\frac{d-j}{d}\right)^{d-j}\left(\frac{j+{t}d}{j}\right)^{j}\left(\frac{d-j-{t}d}{d-j}\right)^{d-j}{\,\mathrm{d}}{t}$
$\displaystyle=\left(\frac{j}{d}\right)^{j}\left(\frac{d-j}{d}\right)^{d-j}\int_{0}^{\frac{i}{d}}\exp({\varphi}({t})-{\varphi}(0)){\,\mathrm{d}}{t}$
$\displaystyle\geq\left(\frac{j}{d}\right)^{j}\left(\frac{d-j}{d}\right)^{d-j}\int_{0}^{\frac{i}{d}}\exp\left(\frac{-id^{2}}{j(d-j-i)}{t}\right){\,\mathrm{d}}{t}$
$\displaystyle=\left(\frac{j}{d}\right)^{j}\left(\frac{d-j}{d}\right)^{d-j}\frac{j(d-j-i)}{id^{2}}\left(1-\exp\left(\frac{-i^{2}d}{j(d-j-i)}\right)\right),$

where the first line follows by setting $q$ to equal $t+\frac{j}{d}$ for some
$t$; the third line follows from (167); the fourth line follows from (166).
This proves the desired inequality (163).

Next, we prove (164) by a similar argument. We see that

${\varphi}^{\prime}(x)=\frac{-xd^{3}}{(j+xd)(d-j-
xd)}\leq\frac{id^{2}}{(j-i)(d-j)},\;\forall x\in\left[-\frac{i}{d},0\right].$

This implies that

${\varphi}(0)-{\varphi}({t})=\int_{t}^{0}{\varphi}^{\prime}(x){\,\mathrm{d}}x\leq\int_{t}^{0}\frac{id^{2}}{(j-i)(d-j)}{\,\mathrm{d}}x=-\frac{id^{2}}{(j-i)(d-j)}{t},\;\forall{t}\in\left[-\frac{i}{d},0\right].$

Then we can deduce that

$\displaystyle\int_{\frac{j-i}{d}}^{\frac{j}{d}}{q}^{j}(1-{q})^{d-j}{\,\mathrm{d}}{q}$
$\displaystyle=\int_{-\frac{i}{d}}^{0}\left(\frac{j+{t}d}{d}\right)^{j}\left(\frac{d-j-{t}d}{d}\right)^{d-j}{\,\mathrm{d}}{t}$
$\displaystyle=\int_{-\frac{i}{d}}^{0}\left(\frac{j}{d}\right)^{j}\left(\frac{d-j}{d}\right)^{d-j}\left(\frac{j+{t}d}{j}\right)^{j}\left(\frac{d-j-{t}d}{d-j}\right)^{d-j}{\,\mathrm{d}}{t}$
$\displaystyle=\left(\frac{j}{d}\right)^{j}\left(\frac{d-j}{d}\right)^{d-j}\int_{-\frac{i}{d}}^{0}\exp({\varphi}({t})-{\varphi}(0)){\,\mathrm{d}}{t}$
$\displaystyle\geq\left(\frac{j}{d}\right)^{j}\left(\frac{d-j}{d}\right)^{d-j}\int_{-\frac{i}{d}}^{0}\exp\left(\frac{id^{2}}{(j-i)(d-j)}{t}\right){\,\mathrm{d}}{t}$
$\displaystyle=\left(\frac{j}{d}\right)^{j}\left(\frac{d-j}{d}\right)^{d-j}\frac{(j-i)(d-j)}{id^{2}}\left(1-\exp\left(\frac{-i^{2}d}{(j-i)(d-j)}\right)\right),$

which establishes the inequality (164). ∎

###### Lemma 18

Let ${L}^{\prime},{U}^{\prime}\in\\{1,\dots,d-1\\}$ with $d\geq 3$ and
${L}^{\prime}<{U}^{\prime}$, we have that for all
$j\in[{L}^{\prime},{U}^{\prime}]$,

$\int_{\frac{{L}^{\prime}}{d}}^{\frac{{U}^{\prime}}{d}}{q}^{j}(1-{q})^{d-j}{\,\mathrm{d}}{q}\geq\left(\frac{j}{d}\right)^{j}\left(\frac{d-j}{d}\right)^{d-j}\frac{{\alpha}}{2d},$

where
${\alpha}:=\frac{1}{2}\min\left\\{{U}^{\prime}-{L}^{\prime},\sqrt{{L}^{\prime}},\sqrt{d-{U}^{\prime}}\right\\}$.

###### Proof:

We split the proof into the following two cases, depending on whether $j$ is
in the range
$j\in\left[{L}^{\prime},\frac{{L}^{\prime}+{U}^{\prime}}{2}\right]$, or in the
range $j\in\left(\frac{{L}^{\prime}+{U}^{\prime}}{2},{U}^{\prime}\right]$.

Case i): ${L}^{\prime}\leq j\leq\frac{{U}^{\prime}+{L}^{\prime}}{2}$. It
follows that $j+{\alpha}\leq{U}^{\prime}<d$ since
${\alpha}\leq\frac{{U}^{\prime}-{L}^{\prime}}{2}$ by definition. We also have
$j>{\alpha}>0$ since ${L}^{\prime}>{\alpha}$ by definition. Thus
$j,d,i={\alpha}$ satisfy the premise of Lemma 17. Using the inequality (163)
with $i={\alpha}$, we obtain

$\displaystyle\int_{\frac{{L}^{\prime}}{d}}^{\frac{{U}^{\prime}}{d}}{q}^{j}(1-{q})^{d-j}{\,\mathrm{d}}{q}$
$\displaystyle\geq\int_{\frac{j}{d}}^{\frac{j+{\alpha}}{d}}{q}^{j}(1-{q})^{d-j}{\,\mathrm{d}}{q}$
$\displaystyle\geq\left(\frac{j}{d}\right)^{j}\left(\frac{d-j}{d}\right)^{d-j}\frac{j(d-j-{\alpha})}{{\alpha}d^{2}}\left(1-\exp\left(\frac{-{\alpha}^{2}d}{j(d-j-{\alpha})}\right)\right).$
(168)

Using the fact that

$\displaystyle 1-e^{-x}\geq\frac{1}{2}x(2-x),\;\forall x\geq 0,$ (169)

we have

$\displaystyle\frac{j(d-j-{\alpha})}{{\alpha}d^{2}}\left(1-\exp\left(\frac{-{\alpha}^{2}d}{j(d-j-{\alpha})}\right)\right)$
$\displaystyle\geq\frac{j(d-j-{\alpha})}{{\alpha}d^{2}}\times\frac{1}{2}\frac{{\alpha}^{2}d}{j(d-j-{\alpha})}\left(2-\frac{{\alpha}^{2}d}{j(d-j-{\alpha})}\right)$
$\displaystyle=\frac{{\alpha}}{2d}\left(2-\frac{{\alpha}^{2}d}{j(d-j-{\alpha})}\right).$
(170)

Next, we argue that $\frac{{\alpha}^{2}d}{j(d-j-{\alpha})}\leq 1$. This is
done by dividing into the following two sub-cases:

  * •

$j<\frac{d}{2}$:

$\frac{{\alpha}^{2}d}{j(d-j-{\alpha})}\leq\frac{\left(\frac{\sqrt{{L}^{\prime}}}{2}\right)^{2}d}{j\left(d-j-\frac{\sqrt{d-2}}{2}\right)}\leq\frac{\left(\frac{\sqrt{{L}^{\prime}}}{2}\right)^{2}d}{{L}^{\prime}\left(\frac{d}{2}-\frac{\sqrt{d-2}}{2}\right)}=\frac{d}{2\left(d-\sqrt{d-2}\right)}\leq
1,$

where the first inequality follows from the definition that
${\alpha}\leq\frac{\sqrt{{L}^{\prime}}}{2}\leq\frac{\sqrt{d-2}}{2}$; the
second inequality follows from the fact that ${L}^{\prime}\leq j<\frac{d}{2}$;
the last inequality follows from the assumption that $d\geq 3$.

  * •

$j\geq\frac{d}{2}$:

$\frac{{\alpha}^{2}d}{j(d-j-{\alpha})}\leq\frac{{\alpha}^{2}d}{\frac{d}{2}(d-{U}^{\prime})}\leq\frac{\left(\frac{\sqrt{d-{U}^{\prime}}}{2}\right)^{2}d}{\frac{d}{2}\left(d-{U}^{\prime}\right)}=\frac{1}{2}\leq
1,$

where the first inequality is because $j\geq\frac{d}{2}$ and
$j+{\alpha}\leq{U}^{\prime}$ as argued above; the second inequality is because
${\alpha}\leq\frac{\sqrt{d-{U}^{\prime}}}{2}$ by definition.

Using this observation along with (F) and (F), we conclude that

$\displaystyle\int_{\frac{{L}^{\prime}}{d}}^{\frac{{U}^{\prime}}{d}}{q}^{j}(1-{q})^{d-j}{\,\mathrm{d}}{q}$
$\displaystyle\geq\left(\frac{j}{d}\right)^{j}\left(\frac{d-j}{d}\right)^{d-j}\frac{{\alpha}}{2d}.$

Case ii): $\frac{{U}^{\prime}+{L}^{\prime}}{2}<j\leq{U}^{\prime}$. This case
can be proved in a similar manner as the above one. Note that
$j-{\alpha}\geq{L}^{\prime}>0$ since
${\alpha}\leq\frac{{U}^{\prime}-{L}^{\prime}}{2}$ by definition. We also have
$j+{\alpha}<d$ since ${\alpha}<d-{U}^{\prime}$. Hence $j,d,i={\alpha}$ satisfy
the premise of Lemma 17. Using the inequality (164) with $i={\alpha}$, we have

$\displaystyle\int_{\frac{{L}^{\prime}}{d}}^{\frac{{U}^{\prime}}{d}}{q}^{j}(1-{q})^{d-j}{\,\mathrm{d}}{q}$
$\displaystyle\geq\int_{\frac{j-{\alpha}}{d}}^{\frac{j}{d}}{q}^{j}(1-{q})^{d-j}{\,\mathrm{d}}{q}$
$\displaystyle\geq\left(\frac{j}{d}\right)^{j}\left(\frac{d-j}{d}\right)^{d-j}\frac{(j-{\alpha})(d-j)}{{\alpha}d^{2}}\left(1-\exp\left(\frac{-{\alpha}^{2}d}{(j-{\alpha})(d-j)}\right)\right).$

Applying the standard identity (169) again, we see that

$\displaystyle\frac{(j-{\alpha})(d-j)}{{\alpha}d^{2}}\left(1-\exp\left(\frac{-{\alpha}^{2}d}{(j-{\alpha})(d-j)}\right)\right)$
$\displaystyle\geq\frac{(j-{\alpha})(d-j)}{{\alpha}d^{2}}\times\frac{1}{2}\frac{{\alpha}^{2}d}{(j-{\alpha})(d-j)}\left(2-\frac{{\alpha}^{2}d}{(j-{\alpha})(d-j)}\right)$
$\displaystyle=\frac{{\alpha}}{2d}\left(2-\frac{{\alpha}^{2}d}{(j-{\alpha})(d-j)}\right).$

Similar to the above case, we prove
$\frac{{\alpha}^{2}d}{(j-{\alpha})(d-j)}\leq 1$ by considering the following
two sub-cases:

  * •

$j<\frac{d}{2}$:

$\frac{{\alpha}^{2}d}{(j-{\alpha})(d-j)}\leq\frac{{\alpha}^{2}d}{{L}^{\prime}\frac{d}{2}}\leq\frac{\left(\frac{\sqrt{{L}^{\prime}}}{2}\right)^{2}d}{{L}^{\prime}\frac{d}{2}}=\frac{1}{2}\leq
1,$

where the first inequality follows by noting that $j<\frac{d}{2}$ and
$j-{\alpha}\geq{L}^{\prime}$ as argued above; the second inequality follows
from the fact that ${\alpha}\leq\frac{\sqrt{{L}^{\prime}}}{2}$.

  * •

$j\geq\frac{d}{2}$:

$\frac{{\alpha}^{2}d}{(j-{\alpha})(d-j)}\leq\frac{{\alpha}^{2}d}{\left(\frac{d}{2}-{\alpha}\right)(d-{U}^{\prime})}\leq\frac{\left(\frac{\sqrt{d-{U}^{\prime}}}{2}\right)^{2}d}{\left(\frac{d}{2}-\frac{\sqrt{d-2}}{2}\right)(d-{U}^{\prime})}=\frac{d}{2\left(d-\sqrt{d-2}\right)}\leq
1,$

where the first inequality is because $\frac{d}{2}\leq j\leq{U}^{\prime}$; the
second inequality follows since
${\alpha}\leq\frac{\sqrt{d-{U}^{\prime}}}{2}\leq\frac{\sqrt{d-2}}{2}$ by its
definition; and the last inequality follows from $d\geq 3$.

It follows that

$\displaystyle\int_{\frac{{L}^{\prime}}{d}}^{\frac{{U}^{\prime}}{d}}{q}^{j}(1-{q})^{d-j}{\,\mathrm{d}}{q}$
$\displaystyle\geq\left(\frac{j}{d}\right)^{j}\left(\frac{d-j}{d}\right)^{d-j}\frac{{\alpha}}{2d}.$

Summarizing the two cases, Lemma 18 is proved. ∎

Using the above results, we are now in a position to prove Lemma 12. Recalling
from (83) that

${\Delta({q})}=\sum\limits_{j=0}^{d-1}\binom{d-1}{j}{q}^{j}(1-{q})^{d-j}(f(j+1)-f(j)).$

Note that ${\Delta({q})}$ is continuous w.r.t. ${q}$. Assuming
${L}^{\prime},{U}^{\prime}\in\\{1,\dots,d-1\\}$ with
${L}^{\prime}<{U}^{\prime}$ and $f({L}^{\prime})<f({U}^{\prime})$, we can
calculate the integral of ${\Delta({q})}$ for
${q}\in\left[\frac{{L}^{\prime}}{d},\frac{{U}^{\prime}}{d}\right]$ as follows:

$\displaystyle\int_{\frac{{L}^{\prime}}{d}}^{\frac{{U}^{\prime}}{d}}{\Delta({q})}{\,\mathrm{d}}q$
$\displaystyle=\int_{\frac{{L}^{\prime}}{d}}^{\frac{{U}^{\prime}}{d}}\sum\limits_{j=0}^{d-1}\binom{d-1}{j}{q}^{j}(1-{q})^{d-j}(f(j+1)-f(j)){\,\mathrm{d}}q$
$\displaystyle\geq\int_{\frac{{L}^{\prime}}{d}}^{\frac{{U}^{\prime}}{d}}\sum\limits_{j={L}^{\prime}}^{{U}^{\prime}-1}\binom{d-1}{j}{q}^{j}(1-{q})^{d-j}(f(j+1)-f(j)){\,\mathrm{d}}q$
$\displaystyle=\sum\limits_{j={L}^{\prime}}^{{U}^{\prime}-1}\frac{d-j}{d}\binom{d}{j}(f(j+1)-f(j))\int_{\frac{{L}^{\prime}}{d}}^{\frac{{U}^{\prime}}{d}}{q}^{j}(1-{q})^{d-j}{\,\mathrm{d}}q$
$\displaystyle\geq\sum\limits_{j={L}^{\prime}}^{{U}^{\prime}-1}\frac{d-j}{d}\binom{d}{j}(f(j+1)-f(j))\left(\frac{j}{d}\right)^{j}\left(\frac{d-j}{d}\right)^{d-j}\frac{{\alpha}}{2d}$
(171)
$\displaystyle\geq\sum\limits_{j={L}^{\prime}}^{{U}^{\prime}-1}\frac{\sqrt{2\pi}}{e^{2}}\sqrt{\frac{d}{j(d-j)}}\frac{d-j}{d}(f(j+1)-f(j))\frac{{\alpha}}{2d}$
(172)
$\displaystyle=\sum\limits_{j={L}^{\prime}}^{{U}^{\prime}-1}\sqrt{\frac{\pi{\alpha}^{2}(d-j)}{2e^{4}jd^{3}}}(f(j+1)-f(j))$
$\displaystyle\geq\sum\limits_{j={L}^{\prime}}^{{U}^{\prime}-1}\sqrt{\frac{\pi{\alpha}^{2}(d-{U}^{\prime})}{2e^{4}{U}^{\prime}d^{3}}}(f(j+1)-f(j))$
$\displaystyle=\sqrt{\frac{\pi{\alpha}^{2}(d-{U}^{\prime})}{2e^{4}{U}^{\prime}d^{3}}}(f({U}^{\prime})-f({L}^{\prime})),$
(173)

where (171) follows from Lemma 18 and
${\alpha}=\frac{1}{2}\min\left\\{{U}^{\prime}-{L}^{\prime},\sqrt{{L}^{\prime}},\sqrt{d-{U}^{\prime}}\right\\}$;
(172) follows from Lemma 16. By the mean value theorem, from (173), we know
there exists some
${q}_{0}\in\left(\frac{{L}^{\prime}}{d},\frac{{U}^{\prime}}{d}\right)$ such
that

${\Delta({q}_{0})}\geq\frac{\sqrt{\frac{\pi{\alpha}^{2}(d-{U}^{\prime})}{2e^{4}{U}^{\prime}d^{3}}}(f({U}^{\prime})-f({L}^{\prime}))}{\frac{{U}^{\prime}}{d}-\frac{{L}^{\prime}}{d}}=\sqrt{\frac{\pi{\alpha}^{2}(d-{U}^{\prime})}{2e^{4}{U}^{\prime}d}}\frac{f({U}^{\prime})-f({L}^{\prime})}{{U}^{\prime}-{L}^{\prime}}.$

Using this observation, we can bound ${\hat{\Gamma}}({q}_{0})$ in (14) as

$\displaystyle{\hat{\Gamma}}({q}_{0})=\frac{36.06(1-{q}_{0})}{{q}_{0}({\Delta({q}_{0})})^{2}}\log\left(\frac{2n}{\varepsilon}\right)$
$\displaystyle\leq\frac{36.06(1-{q}_{0})}{{q}_{0}}\times\frac{2e^{4}{U}^{\prime}d}{\pi{\alpha}^{2}(d-{U}^{\prime})}\left(\frac{{U}^{\prime}-{L}^{\prime}}{f({U}^{\prime})-f({L}^{\prime})}\right)^{2}\log\left(\frac{2n}{\varepsilon}\right)$
$\displaystyle\leq
1253.39\times\frac{(d-{L}^{\prime}){U}^{\prime}}{{\alpha}^{2}(d-{U}^{\prime}){L}^{\prime}}\left(\frac{{U}^{\prime}-{L}^{\prime}}{f({U}^{\prime})-f({L}^{\prime})}\right)^{2}d\log\left(\frac{2n}{\varepsilon}\right),$

which proves Lemma 12.

##  Appendix G Proof of Lemma 8

Suppose to the contrary that
${{q}^{*}}\in\left(0,\frac{1}{376017d^{3}}\right]\cup\left[1-\frac{1}{376017d^{3}},1\right)$.
From (83) we can bound

$\displaystyle\frac{{{q}^{*}}}{1-{{q}^{*}}}\left({\Delta({{q}^{*}})}\right)^{2}$
$\displaystyle=\left(\sum\limits_{j=0}^{d-1}\binom{d-1}{j}{{q}^{*}}^{j}(1-{{q}^{*}})^{d-j-1}(f(j+1)-f(j))\right)^{2}\cdot{{q}^{*}}(1-{{q}^{*}})$
$\displaystyle\leq\left(\sum\limits_{j=0}^{d-1}\binom{d-1}{j}{{q}^{*}}^{j}(1-{{q}^{*}})^{d-j-1}\left(f(d)-f(0)\right)\right)^{2}\cdot{{q}^{*}}(1-{{q}^{*}})$
$\displaystyle=(f(d)-f(0))^{2}\cdot{{q}^{*}}(1-{{q}^{*}})$
$\displaystyle\leq(f(d)-f(0))^{2}\times\frac{1}{376017d^{3}}\left(1-\frac{1}{376017d^{3}}\right)$
$\displaystyle\leq(f(d)-f(0))^{2}\times\frac{1}{376017d^{3}}.$

This along with the definition of ${\hat{\Gamma}}({q})$ in (14) yields that

${\hat{\Gamma}}({{q}^{*}})\geq
36.06\times\frac{376017d^{3}}{(f(d)-f(0))^{2}}\log\left(\frac{2n}{\varepsilon}\right).$
(174)

On the other hand, applying Proposition 3 with ${L}=0$ and ${U}=d$, we have
that $\exists{q}_{0}\in(0,1)$ such that

${\hat{\Gamma}}({q}_{0})\leq\frac{376017d^{3}}{(f(d)-f(0))^{2}}\log\left(\frac{2n}{\varepsilon}\right).$
(175)

From (174) and (175) we have that

${\hat{\Gamma}}({{q}^{*}})>{\hat{\Gamma}}({q}_{0}),$

which is a contradiction to the definition that
${{q}^{*}}=\operatorname*{argmin}_{{{q}^{*}}\in(0,1)}{\hat{\Gamma}}({q})$ in
(15). Hence we prove Lemma 8.

##  Appendix H Proof of Lemma 9

For notational simplicity, let $\varsigma=\frac{1}{376017d^{4}}$. It follows
from Lemma 8 that

$\displaystyle 0<\frac{\varsigma}{{{q}^{*}}}<\frac{1}{d}\text{ and
}0<\frac{\varsigma}{1-{{q}^{*}}}<\frac{1}{d}.$ (176)

For any
${\hat{{q}}^{*}}\in\left[{{q}^{*}}-\varsigma,{{q}^{*}}+\varsigma\right]$, we
have from (83) that

$\displaystyle\frac{{\hat{{q}}^{*}}}{1-{\hat{{q}}^{*}}}({\Delta({\hat{{q}}^{*}})})^{2}$
$\displaystyle=\left(\sum\limits_{j=0}^{d-1}\binom{d-1}{j}{\hat{{q}}^{*}}^{j}(1-{\hat{{q}}^{*}})^{d-j-1}(f(j+1)-f(j))\right)^{2}\cdot{\hat{{q}}^{*}}(1-{\hat{{q}}^{*}})$
$\displaystyle\geq\left(\sum\limits_{j=0}^{d-1}\binom{d-1}{j}({{q}^{*}}-\varsigma)^{j}(1-{{q}^{*}}-\varsigma)^{d-j-1}(f(j+1)-f(j))\right)^{2}\cdot({{q}^{*}}-\varsigma)(1-{{q}^{*}}-\varsigma)$
$\displaystyle=\left(\sum\limits_{j=0}^{d-1}\binom{d-1}{j}{{q}^{*}}^{j}\left(\frac{{{q}^{*}}-\varsigma}{{{q}^{*}}}\right)^{j}(1-{{q}^{*}})^{d-j-1}\left(\frac{1-{{q}^{*}}-\varsigma}{1-{{q}^{*}}}\right)^{d-j-1}(f(j+1)-f(j))\right)^{2}\cdot({{q}^{*}}-\varsigma)(1-{\hat{{q}}^{*}}-\varsigma)$
$\displaystyle\geq\left(\sum\limits_{j=0}^{d-1}\binom{d-1}{j}{{q}^{*}}^{j}\left(\frac{{{q}^{*}}-\varsigma}{{{q}^{*}}}\right)^{d-1}(1-{{q}^{*}})^{d-j-1}\left(\frac{1-{{q}^{*}}-\varsigma}{1-{{q}^{*}}}\right)^{d-1}(f(j+1)-f(j))\right)^{2}\cdot({{q}^{*}}-\varsigma)(1-{\hat{{q}}^{*}}-\varsigma)$
$\displaystyle=\left(\sum\limits_{j=0}^{d-1}\binom{d-1}{j}{{q}^{*}}^{j}(1-{{q}^{*}})^{d-j-1}(f(j+1)-f(j))\right)^{2}\cdot{{q}^{*}}(1-{{q}^{*}})\cdot\left(\frac{{{q}^{*}}-\varsigma}{{{q}^{*}}}\right)^{2d-1}\left(\frac{1-{{q}^{*}}-\varsigma}{1-{{q}^{*}}}\right)^{2d-1}$
$\displaystyle\geq\left(\sum\limits_{j=0}^{d-1}\binom{d-1}{j}{{q}^{*}}^{j}(1-{{q}^{*}})^{d-j-1}(f(j+1)-f(j))\right)^{2}\cdot{{q}^{*}}(1-{{q}^{*}})\cdot\left(1-\frac{1}{d}\right)^{2d-1}\left(1-\frac{1}{d}\right)^{2d-1}$
$\displaystyle\geq\left(\sum\limits_{j=0}^{d-1}\binom{d-1}{j}{{q}^{*}}^{j}(1-{{q}^{*}})^{d-j-1}(f(j+1)-f(j))\right)^{2}\times{{q}^{*}}(1-{{q}^{*}})\times\frac{1}{8}\times\frac{1}{8}$
$\displaystyle=\frac{1}{64}\times\frac{{{q}^{*}}({\Delta({{q}^{*}})})^{2}}{1-{{q}^{*}}}.$
(177)

Using (177) along with the definition of ${\hat{\Gamma}}({q})$ in (14), we
have

$\displaystyle{\hat{\Gamma}}({\hat{{q}}^{*}})\leq
64{\hat{\Gamma}}({{q}^{*}}).$ (178)

For any
${\hat{{q}}^{*}}\in\left[{{q}^{*}}-\varsigma,{{q}^{*}}+\varsigma\right]$, we
also have

$\displaystyle{P(+,{\hat{{q}}^{*}})}$
$\displaystyle=\sum\limits_{j=0}^{d-1}\binom{d-1}{j}{\hat{{q}}^{*}}^{j}(1-{\hat{{q}}^{*}})^{d-1-j}f(j+1)$
$\displaystyle\leq\sum\limits_{j=0}^{d-1}\binom{d-1}{j}({{q}^{*}}+\varsigma)^{j}(1-{{q}^{*}}+\varsigma)^{d-1-j}f(j+1)$
$\displaystyle\leq\sum\limits_{j=0}^{d-1}\binom{d-1}{j}{{q}^{*}}^{j}(1-{{q}^{*}})^{d-1-j}f(j+1)\cdot\left(\frac{{{q}^{*}}+\varsigma}{{{q}^{*}}}\right)^{d-1}\left(\frac{1-{{q}^{*}}+\varsigma}{1-{{q}^{*}}}\right)^{d-1}$
$\displaystyle\leq\sum\limits_{j=0}^{d-1}\binom{d-1}{j}{{q}^{*}}^{j}(1-{{q}^{*}})^{d-1-j}f(j+1)\cdot\left(1+\frac{1}{d}\right)^{d-1}\left(1+\frac{1}{d}\right)^{d-1}$
$\displaystyle\leq\sum\limits_{j=0}^{d-1}\binom{d-1}{j}{{q}^{*}}^{j}(1-{{q}^{*}})^{d-1-j}f(j+1)\cdot
e^{2}$ $\displaystyle=e^{2}{P(+,{{q}^{*}})}.$ (179)

And similarly,

$\displaystyle 1-{Q(+,{\hat{{q}}^{*}})}$
$\displaystyle=\sum\limits_{j=0}^{d-1}\binom{d-1}{j}{\hat{{q}}^{*}}^{j}(1-{\hat{{q}}^{*}})^{d-1-j}(1-f(j))$
$\displaystyle\leq\sum\limits_{j=0}^{d-1}\binom{d-1}{j}{{q}^{*}}^{j}(1-{{q}^{*}})^{d-1-j}(1-f(j))\cdot\left(\frac{{{q}^{*}}+\varsigma}{{{q}^{*}}}\right)^{d-1}\left(\frac{1-{{q}^{*}}+\varsigma}{1-{{q}^{*}}}\right)^{d-1}$
$\displaystyle\leq\sum\limits_{j=0}^{d-1}\binom{d-1}{j}{{q}^{*}}^{j}(1-{{q}^{*}})^{d-1-j}(1-f(j))\cdot\left(1+\frac{1}{d}\right)^{d-1}\left(1+\frac{1}{d}\right)^{d-1}$
$\displaystyle\leq\sum\limits_{j=0}^{d-1}\binom{d-1}{j}{{q}^{*}}^{j}(1-{{q}^{*}})^{d-1-j}(1-f(j))\cdot
e^{2}$ $\displaystyle=e^{2}(1-{Q(+,{{q}^{*}})}).$ (180)

Combining (179) and (180), along with the definition of ${P_{\min}({q})}$ in
(7), we have that

${P_{min}({\hat{{q}}^{*}})}\leq e^{2}P_{min}({{q}^{*}}).$ (181)

Finally, using (178) and (181) along with (14) implies that

${\Gamma({\hat{{q}}^{*}})}={\hat{\Gamma}}({\hat{{q}}^{*}}){P_{min}({\hat{{q}}^{*}})}\leq
64{\hat{\Gamma}}({{q}^{*}})e^{2}P_{min}({{q}^{*}})=64e^{2}{\Gamma}({{q}^{*}}),$

which completes the proof.

##  Appendix I Proof of Lemma 10

The proof of Lemma 10 will resort to the following technical lemma:

###### Lemma 19

For any ${b}\in(0,1)$ and ${c}\in(-{b},1-{b})$, it follows that

$-{b}\ln{b}+({b}+{c})\ln({b}+{c})\leq{c}(1+\ln{b})+\frac{{c}^{2}}{{b}}.$

###### Proof:

Since ${b}+{c}>0$, $\frac{{c}}{{b}}>-1$, we have

$\displaystyle 0$
$\displaystyle\leq({b}+{c})\left(\frac{{c}}{{b}}-\ln\left(1+\frac{{c}}{{b}}\right)\right)$
$\displaystyle={c}+\frac{{c}^{2}}{{b}}-({b}+{c})\ln({b}+{c})+({b}+{c})\ln{b},$

which, via simple rearrangement, gives the promised inequality. ∎

We now set out to prove Lemma 10. First, we have

$\displaystyle{H}({Y}_{i})-{H}({Y}_{i}|{Z}_{i})$
$\displaystyle={H}({Y}_{i})-\sum\limits_{{a}=0}^{d}\Pr({Z}_{i}={a}){H}({Y}_{i}|{Z}_{i}={a})$
$\displaystyle=\sum\limits_{{a}=0}^{d}\Pr({Z}_{i}={a})\left[{H}({Y}_{i})-{H}({Y}_{i}|{Z}_{i}={a})\right]$
(182)

For the sake of notational brevity, let ${\mu}={\mu}({\chi}_{i})$ and
${\sigma^{2}}={\sigma^{2}}({\chi}_{i})$. Since

$\displaystyle\Pr({Y}_{i}=1|{Z}_{i}={a})=f(a),$
$\displaystyle\Pr({Y}_{i}=1)=\sum\limits_{{a}=0}^{d}\Pr({Z}_{i}={a})\Pr({Y}_{i}=1|{Z}_{i}={a})=\sum\limits_{{a}=0}^{d}\Pr({Z}_{i}={a})f(a)={\mu},$

we have

$\displaystyle\begin{aligned}
{H}({Y}_{i})&=-{\mu}\log{\mu}-(1-{\mu})\log(1-{\mu})\\\
&=\left[-{\mu}\ln{\mu}-(1-{\mu})\ln(1-{\mu})\right]\log e,\\\
{H}({Y}_{i}|{Z}_{i}={a})&=-f({a})\log f({a})-(1-f({a}))\log(1-f({a}))\\\
&=\left[-f({a})\ln f({a})-(1-f({a}))\ln(1-f({a}))\right]\log e.\end{aligned}$
(183)

Next, we argue that

$\displaystyle\kern-5.0pt-{\mu}\ln{\mu}-(1-{\mu})\ln(1-{\mu})+f({a})\ln
f({a})+(1-f({a}))\ln(1-f({a}))$
$\displaystyle\leq(f({a})-{\mu})(\ln{\mu}-\ln(1-{\mu}))+\frac{(f({a})-{\mu})^{2}}{{\mu}(1-{\mu})}.$
(184)

This is done for each of the following possible cases.

  * •

When $f({a})=0$,

${\text{L.H.S.}}-{\text{R.H.S.}}=1-\frac{1}{1-{\mu}}-\ln(1-{\mu})\leq
0,\quad\forall\,0<{\mu}<1.$

  * •

When $f({a})=1$,

${\text{L.H.S.}}-{\text{R.H.S.}}=1-\frac{1}{{\mu}}-\ln{\mu}\leq
0,\quad\forall\,0<{\mu}<1.$

  * •

When $f({a})\in(0,1)$, applying Lemma 19 with ${b}={\mu}$ and
${c}=f({a})-{\mu}$ we obtain

$-{\mu}\ln{\mu}+f({a})\ln
f({a})\leq(f({a})-{\mu})(1+\ln{\mu})+\frac{(f({a})-{\mu})^{2}}{{\mu}}.$

Applying Lemma 19 again with ${b}=1-{\mu}$ and ${c}={\mu}-f({a})$, we obtain

$-(1-{\mu})\ln(1-{\mu})+(1-f({a}))\ln(1-f({a}))\leq({\mu}-f({a}))(1+\ln(1-{\mu}))+\frac{(f({a})-{\mu})^{2}}{1-{\mu}}.$

Upon combining the above two inequalities, we have
${\text{L.H.S.}}\leq{\text{R.H.S.}}$ as desired.

Substituting (183) and (184) into (I), we arrive at

$\displaystyle{H}({Y}_{i})-{H}({Y}_{i}|{Z}_{i})$
$\displaystyle\leq\sum\limits_{{a}=0}^{d}\Pr({Z}_{i}={a})\left[\left(f({a})-{\mu}\right)\left(\ln{\mu}-\ln(1-{\mu})\right)+\frac{(f({a})-{\mu})^{2}}{{\mu}(1-{\mu})}\right]\log
e$ $\displaystyle=\frac{{\sigma^{2}}\log e}{{\mu}(1-{\mu})}$

where the equality follows from (41). This proves Lemma 10.

##  Appendix J Proof of Lemma 11

We prove the claim by contradiction. To begin with, assume the contrary is
true, i.e.,

$\left({\gamma}({i})(f({i})-f({\eta}))\right)^{2}\leq\frac{{\sigma^{2}}({\chi}^{*})}{11}({i}-{\vartheta})^{2},\;\forall{i}\in\left\\{0,1,\dots,d-1,d\right\\}\setminus\\{{\eta}\\}.$
(185)

Noting that (185) always holds for ${i}={\eta}$. It then follows that

$\left({\gamma}({i})(f({i})-f({\eta}))\right)^{2}\leq\frac{{\sigma^{2}}({\chi}^{*})}{11}({i}-{\vartheta})^{2},\quad\forall{i}\in\\{0,1,\dots,d-1,d\\}.$
(186)

In the sequel, we adopt the convention that
$\frac{{i}-{\vartheta}}{{\gamma}({i})}=\frac{0}{0}=1$ for ${i}={\vartheta}$.
Then equation (186) can be equivalently written as

$\left(f({i})-f({\eta})\right)^{2}\leq\frac{{\sigma^{2}}({\chi}^{*})}{11}\cdot\left(\frac{{i}-{\vartheta}}{{\gamma}({i})}\right)^{2},\;\forall{i}\in\left\\{0,1,\dots,d-1,d\right\\}.$
(187)

For notational convenience, let

$p({i}):=\frac{\binom{d}{{i}}\binom{n-d}{{\chi}^{*}-{i}}}{\binom{n}{{\chi}^{*}}},\;\forall{i}\in\left\\{0,1,\dots,d-1,d\right\\}.$
(188)

By definition, $\left(p(0),\dots,p(d)\right)$ is the hypergeometric
distribution with parameters $n,d$ and ${\chi}^{*}$. The mean and variance
formulae for hypergeometric distributions $(n,d,{\chi}^{*})$ are,
respectively,

$\displaystyle{\chi}^{*}\frac{d}{n}\;\text{ and
}\;{\chi}^{*}\frac{d}{n}\cdot\frac{n-d}{n}\cdot\frac{n-{\chi}^{*}}{n-1}.$
(189)

Taking expectations on both sides of (187) w.r.t. the distribution (188), we
get

${\mathbb{E}}\left(\left(f({i})-f({\eta})\right)^{2}\right)\leq\frac{{\sigma^{2}}({\chi}^{*})}{11}{\mathbb{E}}\left(\left(\frac{{i}-{\vartheta}}{{\gamma}({i})}\right)^{2}\right).$
(190)

On the other hand,

$\displaystyle{\mathbb{E}}\left(\left(f({i})-f({\eta})\right)^{2}\right)$
$\displaystyle={\mathbb{E}}\left(\left(f({i})-{\mu}({\chi}^{*})\right)^{2}\right)+{\mathbb{E}}\left(\left({\mu}({\chi}^{*})-f({\eta})\right)^{2}\right)+{\mathbb{E}}\left(2\left(f({i})-{\mu}({\chi}^{*})\right)\left({\mu}({\chi}^{*})-f({\eta})\right)\right)$
$\displaystyle={\sigma^{2}}({\chi}^{*})+({\mu}({\chi}^{*})-f({\eta}))^{2}+0$
$\displaystyle\geq{\sigma^{2}}({\chi}^{*}),$ (191)

where the second line follows from (46) and (188). Combining (190) and (191),
we deduce that

${\mathbb{E}}\left(\left(\frac{{i}-{\vartheta}}{{\gamma}({i})}\right)^{2}\right)\geq
11.$ (192)

However, we will argue that
${\mathbb{E}}\left(\left(\frac{{i}-{\vartheta}}{{\gamma}({i})}\right)^{2}\right)<11$,
which is a contradiction to (192). This is proved for each of the two possible
cases:

  1. i)

${\vartheta}\in(0,1)\cup(d-1,d)$;

  2. ii)

${\vartheta}\in[1,d-1]$.

Case i): For ${\vartheta}\in(0,1)\cup(d-1,d)$, we have for any
${i}\in\\{0,\dots,d\\}$ that

$\min\left\\{{i}+1,d-{i}+1\right\\}\geq
1>\min\\{{\vartheta},d-{\vartheta}\\}.$ (193)

It then follows that

$\displaystyle\left(\frac{{i}-{\vartheta}}{{\gamma}({i})}\right)^{2}$
$\displaystyle=\frac{({i}-{\vartheta})^{2}}{\min\\{({i}-{\vartheta})^{2},{i}+1,d-{i}+1,{\vartheta}+1,d-{\vartheta}+1\\}}$
$\displaystyle\leq\frac{({i}-{\vartheta})^{2}}{\min\\{({i}-{\vartheta})^{2},{i}+1,d-{i}+1,{\vartheta},d-{\vartheta}\\}}$
$\displaystyle=\frac{({i}-{\vartheta})^{2}}{\min\\{({i}-{\vartheta})^{2},{\vartheta},d-{\vartheta}\\}}$
$\displaystyle\leq\frac{({i}-{\vartheta})^{2}}{({i}-{\vartheta})^{2}}+\frac{({i}-{\vartheta})^{2}}{\min\\{{\vartheta},d-{\vartheta}\\}}$
$\displaystyle=1+\frac{({i}-{\vartheta})^{2}\max\\{{\vartheta},d-{\vartheta}\\}}{{\vartheta}(d-{\vartheta})}$
$\displaystyle\leq
1+\frac{({i}-{\vartheta})^{2}d}{{\vartheta}(d-{\vartheta})}.$ (194)

Taking expectations on both sides of (J) w.r.t. the hypergeometric
distribution (188), we get

$\displaystyle{\mathbb{E}}\left(\left(\frac{{i}-{\vartheta}}{{\gamma}({i})}\right)^{2}\right)$
$\displaystyle\leq
1+\frac{d}{{\vartheta}(d-{\vartheta})}{\mathbb{E}}\left(({i}-{\vartheta})^{2}\right).$
(195)

From the mean formula in (189), we have that
${\mathbb{E}}({i})={\chi}^{*}\frac{d}{n}={\vartheta}$. Then using the variance
formula in (189), we have

$\displaystyle{\mathbb{E}}\left(({i}-{\vartheta})^{2}\right)={\chi}^{*}\frac{d}{n}\cdot\frac{n-d}{n}\cdot\frac{n-{\chi}^{*}}{n-1},$

which implies

$\displaystyle\frac{d}{{\vartheta}(d-{\vartheta})}{\mathbb{E}}\left(({i}-{\vartheta})^{2}\right)=\frac{n-d}{n-1}\leq
1.$ (196)

Note that (196) holds for all ${\vartheta}\in(0,d)$. Substituting (196) into
(195), we have
${\mathbb{E}}\left(\left(\frac{{i}-{\vartheta}}{{\gamma}({i})}\right)^{2}\right)\leq
2$.

Case ii): For ${\vartheta}\in[1,d-1]$, we must have $d\geq 2$. It follows that
for any $i\in\\{0,\dots,d\\}$,

$\displaystyle\left(\frac{{i}-{\vartheta}}{{\gamma}({i})}\right)^{2}$
$\displaystyle=\frac{({i}-{\vartheta})^{2}}{\min\\{({i}-{\vartheta})^{2},{i}+1,d-{i}+1,{\vartheta}+1,d-{\vartheta}+1\\}}$
$\displaystyle\leq\frac{({i}-{\vartheta})^{2}}{\min\\{({i}-{\vartheta})^{2},{i}+1,d-{i}+1,{\vartheta},d-{\vartheta}\\}}$
$\displaystyle\leq\frac{({i}-{\vartheta})^{2}}{({i}-{\vartheta})^{2}}+\frac{({i}-{\vartheta})^{2}}{\min\\{{i}+1,d-{i}+1\\}}+\frac{({i}-{\vartheta})^{2}}{\min\\{{\vartheta},d-{\vartheta}\\}}$
$\displaystyle=1+\frac{({i}-{\vartheta})^{2}\max\\{{i}+1,d-{i}+1\\}}{({i}+1)(d-{i}+1)}+\frac{({i}-{\vartheta})^{2}\max\\{{\vartheta},d-{\vartheta}\\}}{{\vartheta}(d-{\vartheta})}$
$\displaystyle\leq
1+\frac{({i}-{\vartheta})^{2}\left(d+1\right)}{({i}+1)(d-{i}+1)}+\frac{({i}-{\vartheta})^{2}d}{{\vartheta}(d-{\vartheta})}.$
(197)

Taking the expectation of (197) w.r.t. the hypergeometric distribution (188),
we have

$\displaystyle{\mathbb{E}}\left(\left(\frac{{i}-{\vartheta}}{{\gamma}({i})}\right)^{2}\right)$
$\displaystyle\leq
1+\left(d+1\right){\mathbb{E}}\left(\frac{({i}-{\vartheta})^{2}}{({i}+1)(d-{i}+1)}\right)+\frac{d}{{\vartheta}(d-{\vartheta})}{\mathbb{E}}\left(({i}-{\vartheta})^{2}\right)$
$\displaystyle\leq
2+\left(d+1\right){\mathbb{E}}\left(\frac{({i}-{\vartheta})^{2}}{({i}+1)(d-{i}+1)}\right),$
(198)

where the second line follows from (196) since it continues to hold for this
case.

Next, we proceed to bound the term on the right hand side of (J). We can
expand

$\displaystyle{\mathbb{E}}\left(\frac{({i}-{\vartheta})^{2}}{({i}+1)(d-{i}+1)}\right)$
$\displaystyle=\sum\limits_{{i}=0}^{d}\left(\frac{\binom{d}{{i}}\binom{n-d}{{\chi}^{*}-{i}}}{\binom{n}{{\chi}^{*}}}\cdot\frac{({i}-{\vartheta})^{2}}{({i}+1)(d-{i}+1)}\right)$
$\displaystyle=\sum\limits_{{i}=0}^{d}\left(\frac{\binom{d+2}{{i}+1}\binom{n-d}{{\chi}^{*}-{i}}}{\binom{n+2}{{\chi}^{*}+1}}\cdot\frac{(n+1)(n+2)}{({\chi}^{*}+1)(n-{\chi}^{*}+1)(d+1)(d+2)}\cdot({i}-{\vartheta})^{2}\right)$
$\displaystyle=\frac{(n+1)(n+2)}{({\chi}^{*}+1)(n-{\chi}^{*}+1)(d+1)(d+2)}\cdot\sum\limits_{{i}=0}^{d}\left(\frac{\binom{d+2}{{i}+1}\binom{n-d}{{\chi}^{*}-{i}}}{\binom{n+2}{{\chi}^{*}+1}}\cdot({i}-{\vartheta})^{2}\right)$
$\displaystyle\leq\frac{(n+1)(n+2)}{({\chi}^{*}+1)(n-{\chi}^{*}+1)(d+1)(d+2)}\cdot\sum\limits_{{i}=-1}^{d+1}\left(\frac{\binom{d+2}{{i}+1}\binom{n-d}{{\chi}^{*}-{i}}}{\binom{n+2}{{\chi}^{*}+1}}\cdot({i}-{\vartheta})^{2}\right)$
$\displaystyle=\frac{(n+1)(n+2)}{({\chi}^{*}+1)(n-{\chi}^{*}+1)(d+1)(d+2)}\cdot\sum\limits_{{i}=0}^{d+2}\left(\frac{\binom{d+2}{{i}}\binom{n-d}{{\chi}^{*}+1-{i}}}{\binom{n+2}{{\chi}^{*}+1}}\cdot({i}-{\vartheta}-1)^{2}\right).$
(199)

Using the formula for the mean of hypergeometric distributions
$(n+2,d+2,{\chi}^{*}+1)$, we have

$\sum\limits_{{i}=0}^{d+2}\left(\frac{\binom{d+2}{{i}}\binom{n-d}{{\chi}^{*}+1-{i}}}{\binom{n+2}{{\chi}^{*}+1}}\cdot{i}\right)=({\chi}^{*}+1)\frac{d+2}{n+2}.$

Then, using the formula for the variance of hypergeometric distributions
$(n+2,d+2,{\chi}^{*}+1)$, we have

$\displaystyle\kern-20.00003pt\sum\limits_{{i}=0}^{d+2}\left(\frac{\binom{d+2}{{i}}\binom{n-d}{{\chi}^{*}+1-{i}}}{\binom{n+2}{{\chi}^{*}+1}}\cdot({i}-{\vartheta}-1)^{2}\right)$
$\displaystyle=\sum\limits_{{i}=0}^{d+1}\left(\frac{\binom{d+2}{{i}}\binom{n-d}{{\chi}^{*}+1-{i}}}{\binom{n+2}{{\chi}^{*}+1}}\cdot\left({i}-({\chi}^{*}+1)\frac{d+2}{n+2}+({\chi}^{*}+1)\frac{d+2}{n+2}-{\vartheta}-1\right)^{2}\right)$
$\displaystyle=\sum\limits_{{i}=0}^{d+1}\left(\frac{\binom{d+2}{{i}}\binom{n-d}{{\chi}^{*}+1-{i}}}{\binom{n+2}{{\chi}^{*}+1}}\cdot\left({i}-({\chi}^{*}+1)\frac{d+2}{n+2}\right)^{2}\right)+\left(({\chi}^{*}+1)\frac{d+2}{n+2}-{\vartheta}-1\right)^{2}$
$\displaystyle=({\chi}^{*}+1)\frac{d+2}{n+2}\cdot\frac{n-d}{n+2}\cdot\frac{n-{\chi}^{*}+1}{n+1}+\left(({\chi}^{*}+1)\frac{d+2}{n+2}-{\vartheta}-1\right)^{2}$
$\displaystyle\leq({\chi}^{*}+1)\frac{d+2}{n+2}\cdot\frac{n-d}{n+2}\cdot\frac{n-{\chi}^{*}+1}{n+1}+4,$
(200)

where the last line follows from

$\displaystyle
0={\chi}^{*}\frac{d}{n}-{\vartheta}\leq({\chi}^{*}+1)\frac{d+2}{n+2}-{\vartheta}\leq({\chi}^{*}+1)\frac{d+2}{n}-{\vartheta}=\frac{d+2({\chi}^{*}+1)}{n}\leq
3.$

Substituting (200) into (199), we conclude that

$\displaystyle{\mathbb{E}}\left(\frac{({i}-{\vartheta})^{2}}{({i}+1)(d-{i}+1)}\right)$
$\displaystyle=\frac{1}{d+1}\cdot\frac{n-d}{n+2}+\frac{4(n+1)(n+2)}{({\chi}^{*}+1)(n-{\chi}^{*}+1)(d+1)(d+2)}$
$\displaystyle\leq\frac{1}{d+1}+\frac{4(n+1)(n+2)}{({\chi}^{*}+1)(n-{\chi}^{*}+1)(d+1)(d+2)}$
$\displaystyle\leq\frac{1}{d+1}+\frac{4}{d+1}\cdot\frac{n+2}{n+d}\cdot\frac{n+1}{n-\frac{n}{d}+1}\cdot\frac{d}{d+2}$
$\displaystyle\leq\frac{1}{d+1}+\frac{4}{d+1}\cdot\frac{n+1}{n-\frac{n}{2}+1}\cdot\frac{nd+2d}{nd+2d+2n+d^{2}}$
$\displaystyle<\frac{1}{d+1}+\frac{4}{d+1}\times 2\times 1$
$\displaystyle=\frac{9}{d+1},$ (201)

where the third line follows from

$\displaystyle({\chi}^{*}+1)(n-{\chi}^{*}+1)$
$\displaystyle=-\left({\chi}^{*}-\frac{n}{2}\right)^{2}+\frac{n^{2}}{4}+n+1$
$\displaystyle\geq-\left(\frac{n}{d}-\frac{n}{2}\right)^{2}+\frac{n^{2}}{4}+n+1$
$\displaystyle=\left(\frac{n}{d}+1\right)\left(n-\frac{n}{d}+1\right)$

since we have from (47) that $\frac{n}{d}\leq{\chi}^{*}\leq n-\frac{n}{d}$ for
$1\leq{\vartheta}\leq d-1$. Upon combining (J) and (201), we arrive at

$\displaystyle{\mathbb{E}}\left(\frac{({i}-{\vartheta})^{2}}{{\gamma}({i})^{2}}\right)<2+\left(d+1\right)\cdot\frac{9}{d+1}=11.$

Summarizing the above two cases, we see that
${\mathbb{E}}\left(\left(\frac{{i}-{\vartheta}}{{\gamma}({i})}\right)^{2}\right)<11$,
which contradicts (192). Therefore, the assumption in (185) is false and Lemma
11 is proved.

##  Appendix K Proof of Corollary 1

###  -1 Proof of Corollary 1-a)

###### Proof:

For test function (1), letting ${L}=0$ and ${U}=1$, we have from definition
(18) that ${H(f)}\leq 1$.111111Indeed, we have ${H(f)}=1$ for this test
function. The reverse inequality follows from (19). It then follows that the
upper bound in (21) scales as ${\cal O}\left(d\log n\right)$.

On the other hand, recall from Remark 4 that the lower bound in (24) scales as
$\Omega\left(\log\binom{n}{d}\right)$. Indeed, we can show that the lower
bound is precisely $\log\binom{n}{d}$, i.e., ${h(f)}=1$ for this test
function. To see this, noting that $f(0)=0$ and $f(a)=1,\forall a\geq 1$, we
can compute that

$\displaystyle{\mu}({\chi})=\sum\limits_{{a}=0}^{d}\frac{\binom{d}{{a}}\binom{n-d}{{\chi}-{a}}}{\binom{n}{{\chi}}}f({a})=1-\frac{\binom{n-d}{{\chi}}}{\binom{n}{{\chi}}},$
(202)
$\displaystyle\sum\limits_{{a}=0}^{d}\frac{\binom{d}{{a}}\binom{n-d}{{\chi}-{a}}}{\binom{n}{{\chi}}}f^{2}({a})=1-\frac{\binom{n-d}{{\chi}}}{\binom{n}{{\chi}}}.$
(203)

Since
$(f({a})-{\mu}({\chi}))^{2}=f^{2}({a})+{\mu}^{2}({\chi})-2f({a}){\mu}({\chi})$,
we have from (202) and (203) that

$\displaystyle{\sigma^{2}}({\chi})$
$\displaystyle=\sum\limits_{{a}=0}^{d}\frac{\binom{d}{{a}}\binom{n-d}{{\chi}-{a}}}{\binom{n}{{\chi}}}(f({a})-{\mu}({\chi}))^{2}$
$\displaystyle=\sum\limits_{{a}=0}^{d}\frac{\binom{d}{{a}}\binom{n-d}{{\chi}-{a}}}{\binom{n}{{\chi}}}f^{2}({a})-{\mu}^{2}({\chi})$
$\displaystyle=1-\frac{\binom{n-d}{{\chi}}}{\binom{n}{{\chi}}}-\left(1-\frac{\binom{n-d}{{\chi}}}{\binom{n}{{\chi}}}\right)^{2}$
$\displaystyle=\frac{\binom{n-d}{{\chi}}}{\binom{n}{{\chi}}}\left(1-\frac{\binom{n-d}{{\chi}}}{\binom{n}{{\chi}}}\right).$

It follows that

$\displaystyle\frac{{\mu}({\chi})(1-{\mu}({\chi}))}{{\sigma^{2}}({\chi})}=1,\;\forall{\chi}\in\\{1,\dots,n-1\\}.$

Thus we have ${h(f)}=1$ for this test function. Now the expression (24)
reduces to the classical Fano’s inequality based information theoretic lower
bound [27] on the number of tests required for $(1-\varepsilon)$-reliable
recovery

$T\geq\frac{1}{\log e}\left((1-\varepsilon)\log\binom{n}{d}-1\right).$

By standard arguments via Stirling’s approximation, this quantity scales as
$\Omega\left(d\log\frac{n}{d}\right)$.

Finally, the assumption that $d=n^{\theta},\theta\in(0,1)$ implies that our
upper and lower bounds are order-wise tight, both scaling as
$\Theta\left(d\log n\right)$. ∎

###  -2 Proof of Corollary 1-b)

###### Proof:

The proof is very similar to the proof of Corollary 1-a) and appears for
completeness. For test function (25), letting ${L}=\ell$ and ${U}=\ell+1$, we
have from (18) that ${H(f)}\leq 1.^{\ref{label:ft:H(f)=1}}$ Substituting into
(21), the upper bound scales as ${\cal O}\left(d\log n\right)$.

On the other hand, recall from Remark 4 that the lower bound in (24) scales as
$\Omega\left(\log\binom{n}{d}\right)$.121212By a similar argument to the one
above, one can show the lower bound is precisely $\log\binom{n}{d}$, i.e., we
also have ${h(f)}=1$ for this test function. By standard arguments via
Stirling’s approximation, $\log\binom{n}{d}$ is at least $d\log\frac{n}{d}$.
Using the assumption that $d=n^{\theta},\theta\in(0,1)$, we see that our upper
and lower bounds are order-wise tight, both scaling as $\Theta\left(d\log
n\right)$. ∎

###  -3 Proof of Corollary 1-c)

###### Proof:

For linear test function (26), letting
${L}=\left\lfloor\frac{d}{3}\right\rfloor$ and
${U}=\left\lceil\frac{2d}{3}\right\rceil$, we have that

$\displaystyle\min\left\\{{U}-{L},\sqrt{{L}+1},\sqrt{d-{U}+1}\right\\}$
$\displaystyle=\min\left\\{\left\lceil\frac{2d}{3}\right\rceil-\left\lfloor\frac{d}{3}\right\rfloor,\sqrt{\left\lfloor\frac{d}{3}\right\rfloor+1},\sqrt{d-\left\lceil\frac{2d}{3}\right\rceil+1}\right\\}$
$\displaystyle\geq\min\left\\{\frac{2d}{3}-\frac{d}{3},\sqrt{\frac{d}{3}-1+1},\sqrt{d-\left(\frac{2d}{3}+1\right)+1}\right\\}$
$\displaystyle=\sqrt{\frac{d}{3}}.$

It follows from (18) that

$\displaystyle{H(f)}$
$\displaystyle\leq\left(\frac{1}{\sqrt{\frac{d}{3}}}\times\frac{\left\lceil\frac{2d}{3}\right\rceil-\left\lfloor\frac{d}{3}\right\rfloor}{f\left(\left\lceil\frac{2d}{3}\right\rceil\right)-f\left(\left\lfloor\frac{d}{3}\right\rfloor\right)}\right)^{2}$
$\displaystyle=3d$

Plugging this into (21), the upper bound scales as ${\cal O}\left(d^{2}\log
n\right)$.

The mean and variance formulae for hypergeometric distributions with
parameters $n,d$ and ${\chi}$ are, respectively, ${\chi}\frac{d}{n}$ and
${\chi}\frac{d}{n}\frac{n-d}{n}\frac{n-{\chi}}{n-1}$. For this test function
we can therefore compute that

${\mu}({\chi})=\sum\limits_{{a}=0}^{d}\frac{\binom{d}{{a}}\binom{n-d}{{\chi}-{a}}}{\binom{n}{{\chi}}}f({a})=\frac{1}{d}\sum\limits_{{a}=0}^{d}\frac{\binom{d}{{a}}\binom{n-d}{{\chi}-{a}}}{\binom{n}{{\chi}}}{a}=\frac{{\chi}}{n},$

and

$\displaystyle{\sigma^{2}}({\chi})$
$\displaystyle=\sum\limits_{{a}=0}^{d}\frac{\binom{d}{{a}}\binom{n-d}{{\chi}-{a}}}{\binom{n}{{\chi}}}(f({a})-{\mu}({\chi}))^{2}$
$\displaystyle=\frac{1}{d^{2}}\sum\limits_{{a}=0}^{d}\frac{\binom{d}{{a}}\binom{n-d}{{\chi}-{a}}}{\binom{n}{{\chi}}}\left({a}-d{\mu}({\chi})\right)^{2}$
$\displaystyle=\frac{1}{d^{2}}\sum\limits_{{a}=0}^{d}\frac{\binom{d}{{a}}\binom{n-d}{{\chi}-{a}}}{\binom{n}{{\chi}}}\left({a}-{\chi}\frac{d}{n}\right)^{2}$
$\displaystyle=\frac{1}{d^{2}}\cdot{\chi}\frac{d}{n}\frac{n-d}{n}\frac{n-{\chi}}{n-1}$
$\displaystyle=\frac{{\chi}(n-{\chi})}{n^{2}}\cdot\frac{n-d}{d(n-1)}.$

It follows that

$\displaystyle\frac{{\mu}({\chi})(1-{\mu}({\chi}))}{{\sigma^{2}}({\chi})}=\frac{d(n-1)}{n-d}\geq
d,\quad\forall{\chi}\in\\{1,\dots,n-1\\}.$

This together with the definition of ${h(f)}$ in (23) implies ${h(f)}\geq d$.
Plugging into (24), we have

$T\geq\frac{1}{\log e}d\left((1-\varepsilon)\log\binom{n}{d}-1\right)$

which, by standard arguments via Stirling’s approximation, scales as
$\Omega\left(d^{2}\log\frac{n}{d}\right)$.

Finally, under the assumption that $d=n^{\theta},\theta\in(0,1)$, we see that
both the upper and lower bounds scale as $\Theta\left(d^{2}\log n\right)$.

∎

##  Appendix L Proof of Corollary 2

###### Proof:

Applying the inequalities in (8) to the definition of ${P_{\min}({q})}$ in
(7), we have

$\displaystyle\min\\{f(0),1-f(d)\\}\leq{P_{\min}({q})}\leq\min\\{f(d),1-f(0)\\},\quad\forall{q}\in(0,1).$
(204)

From Remark 3 we have

$\displaystyle f(0)(1-f(d))\leq{\mu}({\chi})(1-{\mu}({\chi}))\leq
f(d)(1-f(0)),\quad\forall{\chi}\in\\{1,\dots,n-1\\}.$ (205)

Combining (204) and (205), we see that

$\displaystyle\frac{\min\\{f(0),1-f(d)\\}}{f(d)(1-f(0))}\leq\frac{{P_{min}({{q}^{*}})}}{{\mu}({\chi}^{*})\left(1-{\mu}({\chi}^{*})\right)}\leq\frac{\min\\{f(d),1-f(0)\\}}{f(0)(1-f(d))}.$
(206)

Recalling the definition of noisy test functions, we have
$f(0),1-f(d)\in\Theta(1)$. It then follows from (206) that

$\frac{{P_{min}({{q}^{*}})}}{{\mu}({\chi}^{*})\left(1-{\mu}({\chi}^{*})\right)}\in\Theta(1).$

This along with Theorem 3 yields that our bounds are order-wise tight. ∎

##  Appendix M Proof of Lemma 3 (Estimating the Exact Number of Defectives)

Let us first analyze a useful subroutine, and then present the full algorithm.

###  -1 A useful subroutine

Let ${\hat{d}}\geq 2$ be a putative number of defective items, and consider
the goal of deciding whether $d\leq{\hat{d}}-1$ or $d\geq{\hat{d}}$. Towards
this end, we use a Bernoulli test design in which each item is independently
placed into each test with probability ${\zeta}$. Let
${{P}({\hat{d}},{\zeta})}$ denote the probability of having a positive test
outcome conditioned on $d={\hat{d}}$. It follows that

${{P}({\hat{d}},{\zeta})}=\sum\limits_{j=0}^{{\hat{d}}}\binom{{\hat{d}}}{j}{\zeta}^{j}(1-{\zeta})^{{\hat{d}}-j}f(j).$
(207)

Similar to (83), define

${\Delta({\hat{d}},{\zeta})}:=\sum\limits_{j=0}^{{\hat{d}}-1}\binom{{\hat{d}}-1}{j}{\zeta}^{j}(1-{\zeta})^{{\hat{d}}-j}\left(f(j+1)-f(j)\right).$
(208)

The subroutine ${\texttt{LoM}}({\hat{d}},{\zeta},{\epsilon})$ for deciding
whether $d\leq{\hat{d}}-1$ or $d\geq{\hat{d}}$ is described in Algorithm 1.

Algorithm 1 ${\texttt{LoM}}({\hat{d}},{\zeta},{\epsilon})$

1:Take ${t({\hat{d}},{\zeta},{\epsilon})}$ tests of the Bernoulli test design
with parameter ${\zeta}$, where
${t({\hat{d}},{\zeta},{\epsilon})}:=\left\lceil
8.32\left(\frac{1-{\zeta}}{{\zeta}{\Delta({\hat{d}},{\zeta})}}\right)^{2}\log\frac{1}{{\epsilon}}\right\rceil.$
(209)

2:Let ${t^{+}({\hat{d}},{\zeta},{\epsilon})}$ denote the number of tests with
positive outcome within these ${t({\hat{d}},{\zeta},{\epsilon})}$ tests. If
$\frac{{t^{+}({\hat{d}},{\zeta},{\epsilon})}}{{t({\hat{d}},{\zeta},{\epsilon})}}\leq{{P}({\hat{d}},{\zeta})}-\frac{{\zeta}}{2(1-{\zeta})}{\Delta({\hat{d}},{\zeta})},$
(210) return $d\leq{\hat{d}}-1$; otherwise, return $d\geq{\hat{d}}$.

###### Lemma 20

The error probability of ${\texttt{LoM}}({\hat{d}},{\zeta},{\epsilon})$ is at
most ${\epsilon}$.

###### Proof:

Let ${{P}({\hat{d}}-1,{\zeta})}$ denote the probability of having a positive
test outcome conditioned on $d={\hat{d}}-1$. It follows that

${{P}({\hat{d}}-1,{\zeta})}=\sum\limits_{j=0}^{{\hat{d}}-1}\binom{{\hat{d}}-1}{j}{\zeta}^{j}(1-{\zeta})^{{\hat{d}}-1-j}f(j).$

Then we have

$\displaystyle{{P}({\hat{d}},{\zeta})}-{{P}({\hat{d}}-1,{\zeta})}$
$\displaystyle=\sum\limits_{j=0}^{{\hat{d}}}\binom{{\hat{d}}}{j}{\zeta}^{j}(1-{\zeta})^{{\hat{d}}-j}f(j)-\sum\limits_{j=0}^{{\hat{d}}-1}\binom{{\hat{d}}-1}{j}{\zeta}^{j}(1-{\zeta})^{{\hat{d}}-1-j}f(j)$
$\displaystyle=(1-{\zeta})\sum\limits_{j=0}^{{\hat{d}}}\left(\binom{{\hat{d}}-1}{j}+\binom{{\hat{d}}-1}{j-1}\right){\zeta}^{j}(1-{\zeta})^{{\hat{d}}-1-j}f(j)-\sum\limits_{j=0}^{{\hat{d}}-1}\binom{{\hat{d}}-1}{j}{\zeta}^{j}(1-{\zeta})^{{\hat{d}}-1-j}f(j)$
$\displaystyle=(1-{\zeta})\sum\limits_{j=1}^{{\hat{d}}}\binom{{\hat{d}}-1}{j-1}{\zeta}^{j}(1-{\zeta})^{{\hat{d}}-1-j}f(j)-{\zeta}\sum\limits_{j=0}^{{\hat{d}}-1}\binom{{\hat{d}}-1}{j}{\zeta}^{j}(1-{\zeta})^{{\hat{d}}-1-j}f(j)$
$\displaystyle={\zeta}\sum\limits_{j=1}^{{\hat{d}}}\binom{{\hat{d}}-1}{j-1}{\zeta}^{j-1}(1-{\zeta})^{{\hat{d}}-j}f(j)-{\zeta}\sum\limits_{j=0}^{{\hat{d}}-1}\binom{{\hat{d}}-1}{j}{\zeta}^{j}(1-{\zeta})^{{\hat{d}}-1-j}f(j)$
$\displaystyle={\zeta}\sum\limits_{j=0}^{{\hat{d}}-1}\binom{{\hat{d}}-1}{j}{\zeta}^{j}(1-{\zeta})^{{\hat{d}}-1-j}(f(j+1)-f(j))$
$\displaystyle=\frac{{\zeta}}{1-{\zeta}}{\Delta({\hat{d}},{\zeta})}.$ (211)

Using this observation, the threshold equation (210) is equivalent to

$\frac{{t^{+}({\hat{d}},{\zeta},{\epsilon})}}{{t({\hat{d}},{\zeta},{\epsilon})}}\leq\frac{{{P}({\hat{d}},{\zeta})}+{{P}({\hat{d}}-1,{\zeta})}}{2}.$
(212)

For ${\texttt{LoM}}({\hat{d}},{\zeta},{\epsilon})$ two types of error can
happen:

  1. i)

We have $d\leq{\hat{d}}-1$, but is claimed to be $d\geq{\hat{d}}$;

  2. ii)

We have $d\geq{\hat{d}}$, but is claimed to be $d\leq{\hat{d}}-1$.

Case i): It is worth noting that
${t^{+}({\hat{d}},{\zeta},{\epsilon})}\sim\text{Binomial}\left({t({\hat{d}},{\zeta},{\epsilon})},{{P}(d,{\zeta})}\right)$.
From (212) we know the probability of error is

$\displaystyle\Pr\left(\frac{{t^{+}({\hat{d}},{\zeta},{\epsilon})}}{{t({\hat{d}},{\zeta},{\epsilon})}}>\frac{{{P}({\hat{d}},{\zeta})}+{{P}({\hat{d}}-1,{\zeta})}}{2}\right)$
$\displaystyle=\Pr\left({t^{+}({\hat{d}},{\zeta},{\epsilon})}>\frac{{{P}({\hat{d}},{\zeta})}+{{P}({\hat{d}}-1,{\zeta})}}{2}\cdot{t({\hat{d}},{\zeta},{\epsilon})}\right)$
$\displaystyle\leq\Pr\left(\text{Binomial}\left({t({\hat{d}},{\zeta},{\epsilon})},{{P}({\hat{d}}-1,{\zeta})}\right)>\frac{{{P}({\hat{d}},{\zeta})}+{{P}({\hat{d}}-1,{\zeta})}}{2}\cdot{t({\hat{d}},{\zeta},{\epsilon})}\right)$
$\displaystyle\leq\exp\left(-\frac{1}{3}\left(\frac{{{P}({\hat{d}},{\zeta})}-{{P}({\hat{d}}-1,{\zeta})}}{2{{P}({\hat{d}}-1,{\zeta})}}\right)^{2}\cdot{t({\hat{d}},{\zeta},{\epsilon})}{{P}({\hat{d}}-1,{\zeta})}\right)$
$\displaystyle\leq\exp\left(-\frac{\left({{P}({\hat{d}},{\zeta})}-{{P}({\hat{d}}-1,{\zeta})}\right)^{2}}{12}{t({\hat{d}},{\zeta},{\epsilon})}\right)$
$\displaystyle\leq{\epsilon}.$

where the first inequality follows from the fact that ${{P}(d,{\zeta})}$ is
monotonically increasing with respect to $d$ and $d\leq{\hat{d}}-1$; the
second inequality follows from Chernoff bound in Fact 1; the third inequality
follows from the fact that ${{P}({\hat{d}}-1,{\zeta})}\leq 1$; the last
inequality follows by substituting (209) and (211).

Case ii): The calculations are similar to Case i). Once again,
${t^{+}({\hat{d}},{\zeta},{\epsilon})}\sim\text{Binomial}\left({t({\hat{d}},{\zeta},{\epsilon})},{{P}(d,{\zeta})}\right)$.
We know from (212) that the probability of error is

$\displaystyle\Pr\left(\frac{{t^{+}({\hat{d}},{\zeta},{\epsilon})}}{{t({\hat{d}},{\zeta},{\epsilon})}}\leq\frac{{{P}({\hat{d}},{\zeta})}+{{P}({\hat{d}}-1,{\zeta})}}{2}\right)$
$\displaystyle=\Pr\left({t^{+}({\hat{d}},{\zeta},{\epsilon})}\leq\frac{{{P}({\hat{d}},{\zeta})}+{{P}({\hat{d}}-1,{\zeta})}}{2}\cdot{t({\hat{d}},{\zeta},{\epsilon})}\right)$
$\displaystyle\leq\Pr\left(\text{Binomial}\left({t({\hat{d}},{\zeta},{\epsilon})},{{P}({\hat{d}},{\zeta})}\right)\leq\frac{{{P}({\hat{d}},{\zeta})}+{{P}({\hat{d}}-1,{\zeta})}}{2}\cdot{t({\hat{d}},{\zeta},{\epsilon})}\right)$
$\displaystyle\leq\exp\left(-\frac{1}{3}\left(\frac{{{P}({\hat{d}},{\zeta})}-{{P}({\hat{d}}-1,{\zeta})}}{2{{P}({\hat{d}},{\zeta})}}\right)^{2}\cdot{t({\hat{d}},{\zeta},{\epsilon})}{{P}({\hat{d}},{\zeta})}\right)$
$\displaystyle\leq\exp\left(-\frac{\left({{P}({\hat{d}},{\zeta})}-{{P}({\hat{d}}-1,{\zeta})}\right)^{2}}{12}{t({\hat{d}},{\zeta},{\epsilon})}\right)$
$\displaystyle\leq{\epsilon}.$

where the first inequality follows from the fact that ${{P}(d,{\zeta})}$ is
monotonically increasing with respect to $d$ and $d\geq{\hat{d}}$; the second
inequality follows from Chernoff bound in Fact 1; the third inequality follow
from the fact that ${{P}({\hat{d}},{\zeta})}\leq 1$; the last inequality
follows by substituting (209) and (211).

Combining the two cases we conclude that the error probability of
${\texttt{LoM}}({\hat{d}},{\zeta},{\epsilon})$ is at most ${\epsilon}$. ∎

###  -2 Algorithm for exactly estimating $d$

Armed with the above subroutine
${\texttt{LoM}}({\hat{d}},{\zeta},{\epsilon})$, the algorithm for exactly
estimating $d$ is now described in Algorithm 2.

Algorithm 2 Exact estimation of $d$

1:$\textbf{Initialize }{\epsilon}\leftarrow\frac{{\varepsilon}}{2\log n+2}$,
${d_{u}}\leftarrow 2$

2:while true do

3: $\textbf{set
}{{\zeta}^{*}}=\operatorname*{argmin}_{{\zeta}\in(0,1)}\frac{1-{\zeta}}{{\zeta}({\Delta({d_{u}},{\zeta})})^{2}}$

4: $\textbf{run }{\texttt{LoM}}({d_{u}},{{\zeta}^{*}},{\epsilon})$

5: $\textbf{if }d\leq{d_{u}}-1\textbf{ then halt}$

6: $\textbf{else set }{d_{u}}\leftarrow 2{d_{u}}$

7:end while

8:$\textbf{set }{d_{l}}\leftarrow\frac{{d_{u}}}{2}$

9:while ${d_{u}}-{d_{l}}\geq 2$ do

10: $\textbf{set
}{d_{m}}=\left\lfloor\frac{{d_{l}}+{d_{u}}}{2}\right\rfloor\text{,
}{{\zeta}^{*}}=\operatorname*{argmin}_{{\zeta}\in(0,1)}\frac{1-{\zeta}}{{\zeta}({\Delta({d_{m}},{\zeta})})^{2}}$

11: $\textbf{run }{\texttt{LoM}}({d_{m}},{{\zeta}^{*}},{\epsilon})$

12: $\textbf{if }d\leq{d_{m}}-1\textbf{ then set }{d_{u}}\leftarrow{d_{m}}$

13: $\textbf{else set }{d_{l}}\leftarrow{d_{m}}$

14:end while

15:$\textbf{output }{d_{l}}$

We start by noting that both while loops in Algorithm 2 invoke at most
$\log(2d)$ calls to the subroutine
${\texttt{LoM}}({\hat{d}},{\zeta},{\epsilon})$. By Lemma 20 and the union
bound, we know that the error probability of Algorithm 2 is bounded from above
by

$2\log(2d)\cdot{\epsilon}=2\log(2d)\frac{{\varepsilon}}{2\log
n+2}\leq{\varepsilon}.$

From (209) we have

$\displaystyle{t({\hat{d}},{{\zeta}^{*}},{\epsilon})}$
$\displaystyle=\left\lceil
8.32\left(\frac{1-{{\zeta}^{*}}}{{{\zeta}^{*}}{\Delta({\hat{d}},{{\zeta}^{*}})}}\right)^{2}\log\frac{1}{{\epsilon}}\right\rceil$
$\displaystyle\leq\left\lceil
8.32\left(\frac{1-{{\zeta}^{*}}}{{{\zeta}^{*}}({\Delta({\hat{d}},{{\zeta}^{*}})})^{2}}\right)^{2}\log\frac{1}{{\epsilon}}\right\rceil$
$\displaystyle\leq
8.32\left(376017H(f,{\hat{d}})\,{\hat{d}}\right)^{2}\log\frac{1}{{\epsilon}}+1$
$\displaystyle=8.32\left(376017H(f,{\hat{d}})\,{\hat{d}}\right)^{2}\log\left(\frac{2\log
n+2}{{\varepsilon}}\right)+1.$

The first inequality follows by noting that
${\Delta({\hat{d}},{{\zeta}^{*}})}\leq 1$ since ${\Delta({\hat{d}},{\zeta})}$
in (208) is the same as ${\Delta({q})}$ in (83) (with
$({\hat{d}},{{\zeta}^{*}})$ in place of $(d,{q})$), and ${\Delta({q})}\leq 1$
for all ${q}$ by Lemma 1. The second inequality can be justified as follows:
The expression in $(\cdot)^{2}$ is similar to ${\hat{\Gamma}}({q})$ in (14).
By the same argument as in Proposition 3 and the discussions that follow, we
can bound the expression in $(\cdot)^{2}$ by
$376017H(f,{\hat{d}})\,{\hat{d}}$, where $H(f,{\hat{d}})$ is the same as
${H(f)}$ in (18) but with ${\hat{d}}$ in place of $d$.

Lastly, since ${\texttt{LoM}}({\hat{d}},{\zeta},{\epsilon})$ is called ${\cal
O}(\log d)$ times and ${\hat{d}}\in{\cal O}(d)$, the above inequality implies
that the total number of tests in Algorithm 2 scales as ${\cal
O}\left(\left({H(f)}d\right)^{2}\log d\log\left(\frac{\log
n}{{\varepsilon}}\right)\right)$. This completes the proof of Lemma 3.

## References

  * [1] R. Dorfman, “The detection of defective members of large populations,” _Ann. Math. Stats._ , vol. 14, no. 4, pp. 436–440, 1943.
  * [2] D. Du, F. K. Hwang, and F. Hwang, _Combinatorial group testing and its applications_. World Scientific, 2000, vol. 12.
  * [3] H. Q. Ngo and D.-Z. Du, “A survey on combinatorial group testing algorithms with applications to DNA library screening,” _Discrete mathematical problems with medical applications_ , vol. 55, pp. 171–182, 2000.
  * [4] A. J. Macula and L. J. Popyack, “A group testing method for finding patterns in data,” _Discret. Appl. Math._ , vol. 144, no. 1-2, pp. 149–157, 2004\.
  * [5] T. Berger, N. Mehravari, D. Towsley, and J. Wolf, “Random multiple-access communication and group testing,” _IEEE Trans. Commun._ , vol. 32, no. 7, pp. 769–779, Jul. 1984.
  * [6] J. K. Wolf, “Born again group testing: Multiaccess communications,” _IEEE Trans. Inf. Theory_ , vol. 31, no. 2, pp. 185–191, Mar. 1985.
  * [7] C. Gollier and O. Gossner, “Group testing against Covid-19,” _Covid Economics_ , vol. 2, 2020.
  * [8] P. Damaschke, “Threshold group testing,” in _General theory of information transfer and combinatorics_. Springer, 2006, pp. 707–718.
  * [9] H.-B. Chen and H.-L. Fu, “Nonadaptive algorithms for threshold group testing,” _Discret. Appl. Math._ , vol. 157, no. 7, pp. 1581–1585, 2009\.
  * [10] M. Cheraghchi, “Improved constructions for non-adaptive threshold group testing,” in _International Colloquium on Automata, Languages, and Programming_. Springer, 2010, pp. 552–564.
  * [11] G. De Marco, T. Jurdziński, D. R. Kowalski, M. Różański, and G. Stachowiak, “Subquadratic non-adaptive threshold group testing,” _J. Comput. Syst. Sci._ , vol. 111, pp. 42–56, 2020.
  * [12] T. V. Bui, M. Kuribayashi, M. Cheraghchi, and I. Echizen, “Efficiently decodable non-adaptive threshold group testing,” _IEEE Trans. Inf. Theory_ , vol. 65, no. 9, pp. 5519–5528, Sep. 2019.
  * [13] T. V. Bui, M. Cheraghchi, and I. Echizen, “Improved non-adaptive algorithms for threshold group testing with a gap,” in _Proc. IEEE Int. Symp. Inf. Theory (ISIT)_ , LA, CA, USA, Jun. 2020, pp. 1414–1419.
  * [14] C. L. Chan, S. Cai, M. Bakshi, S. Jaggi, and V. Saligrama, “Stochastic threshold group testing,” in _Proc. IEEE Inf. Theory Workshop (ITW)_ , Sevilla, Spain, Sep. 2013, pp. 1–5.
  * [15] A. Reisizadeh, P. Abdalla, and R. Pedarsani, “Sub-linear time stochastic threshold group testing via sparse-graph codes,” in _Proc. IEEE Inf. Theory Workshop (ITW)_ , Guangzhou, China, Nov. 2018, pp. 1–5.
  * [16] P. Damaschke and A. S. Muhammad, “Competitive group testing and learning hidden vertex covers with minimum adaptivity,” _Disc. Maths., Algs. and Apps._ , vol. 2, no. 03, pp. 291–311, 2010.
  * [17] M. Falahatgar, A. Jafarpour, A. Orlitsky, V. Pichapati, and A. T. Suresh, “Estimating the number of defectives with group testing,” in _Proc. IEEE Int. Symp. Inf. Theory (ISIT)_ , Barcelona, Spain, Jul. 2016, pp. 1376–1380.
  * [18] N. H. Bshouty, V. E. Bshouty-Hurani, G. Haddad, T. Hashem, F. Khoury, and O. Sharafy, “Adaptive group testing algorithms to estimate the number of defectives,” in _Alg. Learn. Theory (ALT)_ , 2018, pp. 93–110.
  * [19] S. A. Zenios and L. M. Wein, “Pooled testing for hiv prevalence estimation: exploiting the dilution effect,” _Stat. Med._ , vol. 17, no. 13, pp. 1447–1467, 1998.
  * [20] J. Scarlett and V. Cevher, “Near-optimal noisy group testing via separate decoding of items,” _IEEE J. Sel. Topics Signal Process._ , vol. 12, no. 5, pp. 902–915, Oct. 2018.
  * [21] J. Scarlett and O. Johnson, “Noisy non-adaptive group testing: A (near-) definite defectives approach,” _IEEE Trans. Inf. Theory_ , vol. 66, no. 6, pp. 3775–3797, Jun. 2020.
  * [22] G. K. Atia and V. Saligrama, “Boolean compressed sensing and noisy group testing,” _IEEE Trans. Inf. Theory_ , vol. 58, no. 3, pp. 1880–1901, Mar. 2012.
  * [23] J. Scarlett and V. Cevher, “Phase transitions in group testing,” in _Proc.27th ACM-SIAM Symp. Discrete Algorithms (SODA)_ , Jan. 2016, pp. 40–53.
  * [24] ——, “Limits on support recovery with probabilistic models: An information-theoretic framework,” _IEEE Trans. Inf. Theory_ , vol. 63, no. 1, pp. 593–620, Jan. 2017.
  * [25] M. Aldridge, “The capacity of Bernoulli nonadaptive group testing,” _IEEE Trans. Inf. Theory_ , vol. 63, no. 11, pp. 7142–7148, Nov. 2017.
  * [26] M. Aldridge, O. Johnson, and J. Scarlett, “Group testing: An information theory perspective,” _Found. Trends Commun. Inf. Theory_ , vol. 15, no. 3-4, pp. 196–392, 2019.
  * [27] C. L. Chan, S. Jaggi, V. Saligrama, and S. Agnihotri, “Non-adaptive group testing: Explicit bounds and novel algorithms,” _IEEE Trans. Inf. Theory_ , vol. 60, no. 5, pp. 3019–3035, May 2014.
  * [28] H. Chernoff _et al._ , “A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations,” _Ann. Math. Stats._ , vol. 23, no. 4, pp. 493–507, 1952.
  * [29] R. W. Yeung, _Information Theory and Network Coding_. New York, NY, USA: Springer, 2008.
  * [30] N. G. D. Bruijn, _Asymptotic Methods Analysis_. Chelmsford, MA, USA: Courier Corporation, 1981.


# Atomistic modeling of the
phonon dispersion and lattice properties of
free-standing $\langle$100$\rangle$ Si nanowires

Abhijeet Paul, Mathieu Luisier and Gerhard Klimeck  School of Electrical and
Computer Engineering and Network for Computational Nanotechnology,
Purdue University, West Lafayette, IN, USA- 47906, e-mail<EMAIL_ADDRESS>
###### Abstract

Phonon dispersions in $\langle$100$\rangle$ silicon nanowires (SiNW) are
modeled using a Modified Valence Force Field (MVFF) method based on atomistic
force constants. The model replicates the bulk Si phonon dispersion very well.
In SiNWs, apart from four acoustic like branches, a lot of flat branches
appear indicating strong phonon confinement in these nanowires and strongly
affecting their lattice properties. The sound velocity ($V_{snd}$) and the
lattice thermal conductance ($\kappa_{l}$) decrease as the wire cross-section
size is reduced whereas the specific heat ($C_{v}$) increases due to increased
phonon confinement and surface-to-volume ratio (SVR).

##  I Introduction

Silicon nanowires (SiNWs) are playing a vital role in areas ranging from CMOS
[1] to thermo-electricity [2]. The finite extent and increased surface-to-
volume ratio (SVR) in these nanowires result in very different phonon
dispersions compared to the bulk materials [3, 4]. This work investigates the
effect of geometrical confinement on the phonon dispersion, the sound velocity
($V_{snd}$), the specific heat ($C_{v}$), and the lattice thermal conductance
($\kappa_{l}$) in $\langle$100$\rangle$ SiNWs using a Modified Valence Force
Field (MVFF) model based on atomistic force constants.

Previous theoretical works have reported the calculation of phonon dispersions
in SiNWs using a continuum elastic model and Boltzmann transport equation [4],
atomistic first principle methods like DFPT (Density Functional Perturbation
Theory) [5, 6, 7, 8] and atomistic frozen phonon approaches like Keating-VFF
(KVFF) [9, 10]. Thermal conductivity in SiNWs has been studied previously
using the KVFF model [11, 12]. The continuum approaches fail to capture the
atomistic effects like anisotropy in $C_{v}$ for nanowires, etc., whereas the
first principle models cannot be extended to very large structures due to
their heavy computational requirement. The VFF model overcomes these
shortcoming by capturing the atomistic effects and solving phonon dispersions
and transport in realistic structures [9, 11]. However, a simple KVFF model
does not reproduce the bulk dispersions very well and hence cannot be used
confidently for nanostructures [13]. The MVFF model overcomes the verifiable
shortcomings in bulk. We use the MVFF model for phonon calculations in SiNWs
and believe them to be more robust and predictive than the KVFF model [13].

Figure 1: The short range interactions used for Phonon dispersion
calculations. The interactions are (a) bond-stretching($\alpha$), (b) bond-
bending($\beta$) (c) bond stretch coupling($\gamma$) (d) bond bending-
stretching coupling ($\delta$) (e) coplanar bond bending coupling($\lambda$).
Figure 2: Projected unitcell structure of a $\langle$100$\rangle$ oriented
Silicon nanowire. The white atoms (for visual guidance) show the freely
vibrating surface atoms. Grey colored atoms are inside the wire

This paper is organized in the following sections. Section II briefly presents
the phonon model and its application to SiNWs. Also the computation of
different wire lattice properties is outlined there. The results on phonon
dispersion and other lattice properties are presented in Sec. III. Conclusions
are summarized in Sec. IV

##  II Theory and Approach

###  II-A Modified VFF method

The Valence Force Field (VFF) model is a force constant based atomic potential
(U) calculation method. The MVFF model we present here is based on the
combination of two different extended VFF models, (a) VFF model from Sui et.
al. [14] which is suited for non-polar materials like Si, Ge and (b) VFF model
from Zunger et. al. [15] which is suited for polar materials like GaP, GaAs,
etc. These methods have successfully modelled the phonon dispersion in various
semiconductor materials [16, 14, 15]. The force constants represent the
various kinds of interaction between the atoms. For phonon modeling in diamond
(and zinc-blende) lattices we consider the following interactions (Fig. 1),
(a) bond-stretching ($\alpha$), (b) bond-bending ($\beta$) (c) bond stretch
coupling ($\gamma$) (d) bond bending-stretching coupling ($\delta$) and (e)
co-planar bond bending coupling ($\lambda$). The first two terms (a and b in
Fig. 1) are from the original Keating model [16], which are not sufficient to
reproduce the bulk phonon dispersion accurately in zinc-blende semiconductors
[14, 13]. Hence, higher order interactions (term c, d and e in Fig. 1) are
included in the original KVFF model. The force constants in the MVFF model
depend on the bond length and angle variations from the ideal value [14]. Due
to this reason MVFF is also known as the ‘quasi-anharmonic model’.

The motion of atoms in the semiconductor structure is captured by a dynamical
matrix (DM). The dynamical matrix is assembled using the second derivative
(Hessian) of the crystal potential energy (U). The bulk DM has periodic
boundary conditions along all the directions (Born-von Karman condition, Fig.
1) due to the assumed infinite material extent along all the directions. For
free-standing SiNW, periodic boundary conditions are applied only along the
length of the wire (X-axis) assuming an infinitely long wire, whereas the
surface atoms (Y-Z axis) are free to vibrate as illustrated in Fig. 2). The
complete calculation details are provided in Ref. [13].

###  II-B Lattice property calculations

A wealth of information can be extracted from the phonon spectrum of solids.
The description of the few important ones are provided below.

Sound Velocity: One important parameter is the group velocity ($V_{grp}$) of
the acoustic branches of the phonon dispersion. Near the Brillouin Zone (BZ)
center $V_{grp}$ characterizes the velocity of sound ($V_{snd}$) in the solid.
Depending on the acoustic phonon branch used for the calculation of $V_{grp}$,
the sound velocity can be either (a) longitudinal ($V_{snd,l}$) or (b)
transverse ($V_{snd,t}$). Thus, $V_{snd}$ is given by,

$V_{sndl/t}=V_{grp}=\frac{\partial\omega(\lambda,q)}{\partial
q}\Big{|}_{q\leftarrow 0},$ (1)

where, $\lambda$ and q are the phonon polarization (for longitudinal or
transverse direction) and wave vector respectively.

Figure 3: Comparison of the MVFF method (lines) and the experimental data
(dots) [17] for bulk Silicon phonon dispersion at 80K.

Lattice thermal properties: In a semiconductor where its two ends are
maintained at a small temperature difference ($\Delta T$), its specific heat
($C_{v}$) and thermal conductance ($\kappa_{l}$) can be evaluated from the
phonon dispersion using the Landauer’s formula [18]. The temperature dependent
specific heat is given by[19, 7],

$C_{v}(T)=k_{B}\sum_{n,q}\Big{[}\frac{\Big{(}\frac{\hbar\omega(n,q)}{k_{B}T}\Big{)}^{2}\cdot\exp\Big{(}\frac{-\hbar\omega(n,q)}{k_{B}T}\Big{)}}{(1-\exp\big{(}\frac{-\hbar\omega(n,q)}{k_{B}T)}\big{)}^{2}}\Big{]},$
(2)

where $k_{B}$, $\hbar$, T, and n are Boltzmann’s constant, reduced Planck’s
constant, mean temperature, and number of sub-bands, respectively. The
temperature dependent lattice thermal conductance ($\kappa_{l}$) for a 1D
conductor is given by [11, 6, 19],

$\kappa_{l}(T)=\hbar\int^{\omega_{max}}_{0}M(\omega)\cdot\omega\cdot\frac{\partial}{\partial
T}\Big{[}(\exp\big{(}\frac{\hbar\omega}{k_{B}T})-1\big{)}^{-1}\Big{]}d\omega,$
(3)

where, $M(\omega)$ is the number of modes at a given frequency $\omega$. In
the next section we present the results on phonon dispersion in SiNWs and the
lattice thermal properties.

TABLE I: Force constants used for Silicon in MVFF model Sp.const(N/m) | $\alpha$ | $\beta$ | $\gamma$ | $\delta$ | $\lambda$
---|---|---|---|---|---
Silicon | 45.1 | 4.89 | 0 | 1.36 | 9.14

##  III Results and Discussion

###  III-A Experimental benchmark

The MVFF model has been bench marked by calculating the phonon dispersions in
different bulk zinc-blende semiconductors. One of the representative
calculation is shown in Fig. 3 for bulk Si. The model accurately reproduces
the important features of the experimental phonon dispersion of Si (at 80K)
[17] in the entire BZ. The force constant values for Si are listed in Table.I.
The bond stretch coupling parameter ($\gamma$) is zero for Si. This term
contributes significantly for splitting the longitudinal optical (LO) and
longitudinal acoustic (LA) phonon branches near the BZ edge only in III-V
materials like GaAs, GaP [15].

###  III-B Nanowire phonon dispersions

Figure 4: Effect of cross-section size on the phonon dispersion in
$\langle$100$\rangle$ SiNW. The wire dimensions are (W = H) (a) 2nm (b) 4nm,
and (c) 6nm. As the cross-section size increases the number of phonon modes
within a given energy range increase as shown here. The geometrical
quantization increases the separation of bands in smaller wires. Figure 5:
Eigen modes of the atomic displacement shown in a SiNW with W, H = 1.63nm. The
atomic displacement are shown at $q_{x}\sim$ 0 for (a) mode = 1, (b) mode = 2.
These modes are called flexural modes and cause bending of the NW. (c) mode =
3, called the longitudinal mode causes atomic motion along the wire axis. (d)
mode = 4, called the torsional mode, observed only in wires, represents the
extra rotational degree of freedom.

The phonon dispersion is calculated in free-standing $\langle$100$\rangle$
SiNW where the surface atoms are allowed to vibrate freely (Fig. 2). The
dispersion in SiNWs with cross-section size (W=H) (a) 2nm, (b) 4nm, and (c)
6nm are compared in Fig. 4. The number of sub-bands increases as the wire
cross-section size increases due to an increased number of atoms (Fig. 4).
This results in a higher degree of vibrational freedom. A comparison of the
number of sub-bands within 10 meV of energy for the different SiNWs considered
here shows that the 2nm $\times$ 2nm structure has $\sim$ 40 sub-bands, the
4nm $\times$ 4nm has $\sim$ 90 sub-bands and the 6nm $\times$ 6nm has nearly
110 sub-bands (Fig. 4). The increased separation of phonon sub-bands in
smaller wires is a consequence of the geometrical confinement. The higher sub-
bands have mixed acoustic and optical branch like properties. Many of the sub-
bands in this regime have group velocities close to zero which again indicates
a strong phonon confinement in thin nanowires. In SiNWs these flat phonon
branches appear due to the zone-folding of acoustic branches from the bulk
phonon-dispersion (Fig. 3).

Eigen modes of oscillation: The first four vibrational Eigen modes are shown
in Fig. 5 (arrows show the displacement direction). The first two modes (Fig.
5 a, b) are the flexural modes responsible for NW bending perpendicular to the
NW axis. The Eigen frequencies for the lowest two phonon bands near the zone
center are $\propto q^{2}$. The next mode (Fig. 5 c) is the longitudinal mode.
The mode no. 4 is torsional mode which represents the extra degree of
rotational movement in free standing wires (Fig. 5 d). Mode no. 3 and 4 behave
like the bulk acoustic branches ($\propto q$ near the zone center) [10]. Mode
1 and 2 appear due to the free-standing nature of the nanowires which are not
available in bulk. Hence, new modes as well as new phonon dispersion branches
appear in SiNW which are very different from their bulk counterpart. This also
has a strong impact on the lattice properties of the wires which is discussed
in the following part.

###  III-C Lattice properties in SiNW

#### Sound velocity variation ($V_{snd}$)

The sound velocity ($V_{snd}$) is another way to compare the vibrational modes
in SiNWs. $V_{snd}$ is obtained using the sub-bands 3 and 4 (transverse and
longitudinal modes) of the phonon dispersion. $V_{snd}$ shows a reduction with
decreasing wire cross-section size (acoustic mode softening) [10] (Fig. 6).
This happens since the acoustic branches get flatter in small wires due to
phonon confinement. This strongly affects the thermal properties of the SiNWs
since the acoustic branches are mainly responsible for heat conduction. A
smaller sound velocity also results in smaller thermal conductance (discussed
later).

Figure 6: Sound Velocity ($V_{snd}$) in $\langle$100$\rangle$ SiNW with free
boundary. As a reference the bulk $V_{snd}$ is shown along the
$\langle$100$\rangle$ direction [20]. Increasing the wire diameter increases
the $V_{snd}$ since the vibrational degree of freedom increases. Figure 7:
Variation of the specific heat ($C_{v}$) in Silicon nanowires with width. As a
reference the specific heat for bulk Si is shown by a dashed line. SiNWs have
larger $C_{v}$ than bulk Si [7]. The specific heat increases as the cross-
section size of the wire decreases.

#### SiNW specific heat ($C_{V}$) variation

The specific heat of silicon nanowires increases with their decreasing cross-
section size (Fig. 7). This can be attributed to two reasons, (i) phonon
confinement due to small cross-section and (ii) an increased surface-to-volume
ratio (SVR) in smaller wires. Geometrical confinement separates the phonon
bands in energy with decreasing wire cross-section size (Fig. 4) which makes
only the few lower energy bands active at a given temperature (see Eq.2). This
explains the increasing energy needed to raise the temperature of the smaller
wires. Also the increasing SVR results in a higher partial phonon DOS
associated with the wire surface, which further enhances the specific heat
with decreasing wire cross-section [7].

Figure 8: Variation in the ballistic lattice thermal conductance
($\kappa_{l}$) (a) with temperature for different cross-section size SiNW and
(b) at room temperature (300K) for different NW width size.

#### Lattice thermal conductance ($\kappa_{l}$) variation

The modified phonon dispersion in SiNWs significantly affects the ballistic
$\kappa_{l}$ [11]. The ballistic $\kappa_{l}$ increases with temperature as
shown in Fig. 8a. The spread of the Bose-Einstein distribution
($F_{BD}=[\exp(\hbar\omega/k_{B}T)-1]^{-1}$ in energy increases with
increasing temperature. This results in a larger number of modes contributing
to the heat transfer [6] (see Eq. (3)). This explains the increased ballistic
$\kappa_{l}$ at elevated temperatures. Larger wires show more $\kappa_{l}$
since, (i) they have more phonon sub-bands resulting in more number of modes
(see Eq. (3)) and (ii) they have a higher acoustic velocity which is
responsible for larger heat conduction (Fig. 6). The ballistic $\kappa_{l}$ of
2nm $\times$ 2nm Si nanowire reduces by a factor of 8 as compared to the 6nm
$\times$ 6nm SiNW (Fig. 8b).

An important point to note here is that $\kappa_{l}$ is expected to decrease
further in smaller wires due to phonon scattering by other phonons, interfaces
and boundaries [11] which is neglected in the present study. The main message
here is that even ballistic phonons show a reduction in thermal conductance
with narrow SiNWs, which comes from (i) a modification of the phonon
dispersion (ii) phonon confinement effects in SiNWs.

##  IV Conclusions

A modified atomistic force constant based model has been developed for the
calculation of phonon dispersion in zinc-blende lattices. This model shows a
very good agreement with experimental bulk phonon data. An important impact of
device miniaturization is the presence of surfaces (and hence higher surface-
to-volume ratio) which affects the phonon dispersion in SiNW. The clear
demarcation of phonon bands as acoustic and optical branches become vague in
SiNW. This manifests itself in the form of modified lattice properties in
SiNWs compared to bulk Si. We find that decreasing wire cross-section reduces
the sound velocity and the lattice thermal conductance whereas the specific
heat increases. The geometry dependent calculation of phonon dispersion in
small nanowires is therefore important to properly understand their thermal
properties.

## Acknowledgments

The authors would like to acknowledge the computational resources from
nanoHUB.org, an National Science Foundation (NSF) funded, NCN project.
Financial support from MSD Focus Center, one of six research centers funded
under the Focus Center Research Program (FCRP), a Semiconductor Research
Corporation (SRC) entity, by the Nanoelectronics Research Initiative (NRI)
through the Midwest Institute for Nanoelectronics Discovery (MIND) and NSF
PetaApps, grant number OCI-0749140, are also acknowledged.

## References

  * [1] “ITRS Report 2009,” ITRS, Tech. Rep., 2009. [Online]. Available: www.itrs.net
  * [2] A. I. Hochbaum, R. Chen, R. D. Delgado, W. Liang, E. C. Garnett, M. Najarian, A. Majumdar, and P. Yang, “Enhanced thermoelectric performance of rough silicon nanowires,” _Nature_ , vol. 451, no. 7175, pp. 163–167, 2008.
  * [3] A. Buin, A. Verma, and M. Anantram, “Carrier-Phonon interaction in small cross-sectional silicon nanowires,” _Journal of Applied Physics_ , vol. 104, p. 053716, 2008.
  * [4] J. Zou and A. Balandin, “Phonon heat conduction in a semiconductor nanowire,” _Journal of Applied Physics_ , vol. 89, no. 5, pp. 2932–2938, 2001.
  * [5] H. Peelaers, B. Partoens, and F. M. Peeters, “Phonon Band Structure of Si Nanowires: A Stability Analysis,” _Nano Letters_ , vol. 9, no. 1, pp. 107–111, 2009.
  * [6] T. Markussen, A.-P. Jauho, and M. Brandbyge, “Heat Conductance Is Strongly Anisotropic for Pristine Silicon Nanowires,” _Nano Letters_ , vol. 8, no. 11, pp. 3771–3775, 2008.
  * [7] Y. Zhang, J. X. Cao, Y. Xiao, and X. H. Yan, “Phonon spectrum and specific heat of silicon nanowires,” _Journal of Applied Physics_ , vol. 102, no. 10, p. 104303, 2007.
  * [8] X. Li, K. Maute, M. L. Dunn, and R. Yang, “Strain effects on the thermal conductivity of nanostructures,” _Phys. Rev. B_ , vol. 81, no. 24, p. 245318, Jun 2010.
  * [9] N. Mingo and L. Yang, “Phonon transport in nanowires coated with an amorphous material: An atomistic Green’s function approach,” _Phys. Rev. B_ , vol. 68, no. 24, p. 245406, Dec 2003.
  * [10] T. Thonhauser and G. D. Mahan, “Phonon modes in Si [111] nanowires,” _Phys. Rev. B_ , vol. 69, no. 7, p. 075213, Feb 2004.
  * [11] N. Mingo, L. Yang, D. Li, and A. Majumdar, “Predicting the Thermal Conductivity of Si and Ge Nanowires,” _Nano Letters_ , vol. 3, no. 12, pp. 1713–1716, 2003.
  * [12] H. Zhao, Z. Tang, G. Li, and N. R. Aluru, “Quasiharmonic models for the calculation of thermodynamic properties of crystalline silicon under strain,” _Journal of Applied Physics_ , vol. 99, no. 6, p. 064314, 2006.
  * [13] A. Paul, M. Luisier, and G. Klimeck, “Modified valence force field approach for phonon dispersion: from zinc-blende bulk to nanowires Methodology and computational details,” _http://arxiv.org/abs/1009.6188_ , 2010.
  * [14] Z. Sui and I. P. Herman, “Effect of strain on phonons in Si, Ge, and Si/Ge heterostructures,” _Phys. Rev. B_ , vol. 48, no. 24, pp. 17 938–17 953, 1993.
  * [15] H. Fu, V. Ozolins, and Z. Alex, “Phonons in GaP quantum dots,” _Phys. Rev. B_ , vol. 59, no. 4, pp. 2881–2887, 1999.
  * [16] P. N. Keating, “Effect of Invariance Requirements on the Elastic Strain Energy of Crystals with Application to the Diamond Structure,” _Phys. Rev._ , vol. 145, no. 2, pp. 637–645, 1966.
  * [17] G. Nilsson and G. Nelin, “Study of the Homology between Silicon and Germanium by Thermal Neutron Spectrometry,” _Phys. Rev. B_ , vol. 6, no. 10, pp. 3777–3786, 1972.
  * [18] R. Landauer, “Spatial variation of currents and fields due to localized scatterers in metallic conduction,” _IBM J. Res. Dev._ , vol. 1, no. 3, pp. 223–231, 1957.
  * [19] D. C. Wallace, “Thermodynamics of crystals,” _Courier Dover Publications_ , 1998.
  * [20] M. G. Holland, “Analysis of Lattice Thermal Conductivity,” _Phys. Rev._ , vol. 132, no. 6, pp. 2461–2471, Dec 1963.