19.6 Exercises 267
W.l.o.g. assume thatp≤ 1 /2. Now use Lemma 19.7 to show that
y P
1 ,...,yj
y∼Pp[hS(x)^6 =y]≤
(
1 +
√
8
k
)
y∼Pp[^1 [p>^1 /2]^6 =y].
yP∼p[^1 [p>^1 /2]^6 =y] =p= min{p,^1 −p}≤min{η(x),^1 −η(x)}+|p−η(x)|.
- Combine all the preceding to obtain that the second summand in Equa-
tion (19.3) is bounded by
(
1 +
√
8
k
)
LD(h?) + 3c
√
d.
- User= (2/)dto obtain that:
E
S
[LD(hS)]≤
(
1 +
√
8
k
)
LD(h?) + 3c
√
d+2(2/)
dk
m
.
Set= 2m−^1 /(d+1)and use
6 cm−^1 /(d+1)
√
d+
2 k
e
m−^1 /(d+1)≤
(
6 c
√
d+k
)
m−^1 /(d+1)
to conclude the proof.
