By ( 4), E[Z*/q − 1] = 0 and, using ( 5),
Plugging this into ( 6) shows that
desired.
, as
®
Since the expectation of the absolute value of N(0, 1)
is , by taking conditional expectations, we find
that
On the other hand, by Lemma 1, we note that
( 7)
Next, we prove that ||y|| 1 is sharply concentrated around its
mean E[||y|| 1] = kE[|y1|]. To do this, we begin by bounding the
moments of |y1| = |Sjbjrjuj|. Using conditional expectations,
we can show that, for any integer t ³ 0,
where U ∼ N(0, 1). It is well known that E[|U|t] = (t)t/2; and so,
by Lemma 1,
It follows that the moment generating function satisfies
Therefore, it converges for any 0 £ l < l0, where l0 is an absolute constant, and
Using independence, we find that
Meanwhile, Markov’s inequality and ( 7) imply that
for some l = Q(e). The constraint l < l0 corresponds to e
being smaller than some absolute constant. The same argument leads to a similar lower tail estimate. Our choice of
102 communicAtions of the Acm | FEbrUary 2010 | VoL. 53 | No. 2
k ensures that, for any x Î X, ||Fx|| 1 = ||y|| 1 deviates from its
mean by at most e with probability at least 0.95. By ( 7), this
implies that kE[| y1|] is itself concentrated around a1;=
with a relative error at most e; rescaling e by a constant factor and ensuring ( 3) proves the 1 claim of the first part of the
FJLT lemma.
The 2 case: We set
for a large enough constant c1.
Lemma 2. With probability at least
,
1. q/2 £ Zi £ 2q for all i = 1, …, k; and
2.
proof: If q = 1 then Z is the constant q and the claim is
trivial. Otherwise, q = c1d− 1 log2 n < 1. For any real l, the
function
is convex, hence achieves its maximum at the vertices
of the polytope P (same as in the proof of Lemma 1).
As argued before, therefore, E[elZ] £ E[elZ*]. We conclude
the proof of the first part with a union bound on standard tail estimates on the scaled binomial Z that we
derive from bounds on its moment generating function
E[el Z*] (e.g., Alon and Spencer6). For the second part, let
S = Sk i=1Zi. Again, the moment generating function of S is
bounded above by that of S ∼ m−1B(mk, q)—all Zi’s are
distributed as Z*—and the desired concentration bound
follows. ®
We assume from now on that the premise of Lemma
2 holds for all choices of x Î X. A union bound shows
that this happens with probability of at least 0.95. For each
i = 1,…, k the random variable is distributed as c2 with
one degree of freedom. It follows that, conditioned on Zi,
the expected value of y2 i is Zi/q and the moment generating
function of y2i is
Given any 0 < l < l0, for fixed l0, for large enough x, the
moment generating function converges and is equal to
We use here the fact that Zi/q = O( 1), which we derive from
the first part of Lemma 2. By independence, therefore,
