1.

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

mu({1})=p=1-mu({0})

nu({1})=q=1-nu({0})

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).

2.

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?

## Friday, April 24, 2009

Subscribe to:
Posts (Atom)