Friday, April 24, 2009

2 inequalities


Let mu and nu be two Bernoulli measures on {0,1}, with biases p and q, respectively. Thus,

Let P and Q be the n-fold products of mu and nu, respectively. Thus, P and Q are two probability measures on {0,1}^n.

Show that
||P-Q|| <= n|p-q|
where ||.|| is the total variation norm (and <= is a poor man's way of writing \leq in plain text).


Now assume that q = 1/2; thus Q is the uniform measure on {0,1}^n.

Show that
||P-Q|| <= C n^(1/2) |p-1/2|

where C>0 is some fixed universal constant. (Hint: Pinsker's inequality might come in handy.)

Are these novel or already known?


Ryan O'Donnell said...

Known, I would say. In fact, so long as p and q are close and not too close to 0 and 1, then the total variation distance is O(sqrt(n)).

See, e.g., Exercise 21 (with solution) here:

(or some of the calculations here:

Prasad said...

For any two distributions P,Q on an arbitrary domain, with statistical distance d, the statistical distance between P^n, Q^n grows as O(\sqrt(n)H(P,Q)).

where H(P,Q) is the Hellinger distance between distributions P,Q.

This can be found in Lemmas 3.1,3.2 in the paper :

Rounding Parallel Repetitions of Unique Games

Aryeh said...

Many thanks to Ryan and Prasad for the helpful pointers!