A large deviations problem
Yesterday I copied a couple of chapters from two of my prof’s large deviations books (Shwartz and Weiss, Dembo and Zeitouni), and today I started to read them. I’m stuck on the following exercise:
Show that in the case of fair coin flips, if
is the number of heads obtained in
flips and
is an integer,
and does not grow with
I think the way to do this is:
- Estimate
with some large deviation principle - Use the fact that
Being able to approximate the quantity in the hint doesn’t help too much. A generalization for 
would maybe help, but …
The hint is wrong (and so is the generalization). Sure, you have 
and the first term on the right hand side goes to 
, but the second term grows too fast for you to say 
. The error actually grows with .
Aargh! I just spent 30 minutes writing a Mathematica code to see if that expectation does indeed converge to 
, only to realize when I finished that it’s virtually useless. Can you tell me why? I wonder if I can use my shiny new skill-set from last term to make a MCMC algorithm for testing the convergence …
Possibly relevant posts:
- What I’ve learned about Large Deviation Theory (3/30/2007)
- I can finally move on (or, a deviation result proved) (11/5/2008)
- kvetching about probability (3/28/2007)
The hint is true in the same sense that n^2 + n = n^2 for large n. (ie. it’s an asymptotic statement.) The generalization is (n choose .8n+k) = (n choose .8n) * (1/4)^k * (1+ O(1/n)).
Comment by Anonymous — 4/5/2007 @ 4:41 pm
Sure, I can see that the relative error of the approximation is decreasing. My question is, is that sufficient to ensure that the expectation converges to 1/3? It doesn’t seem to.
Comment by Alex — 4/5/2007 @ 5:01 pm
Remember you’re dividing by P(x >= .8n) = 2^-n * (n choose .8n) * (4/3 + O(1/n)), so it’s all good.
Comment by Anonymous — 4/5/2007 @ 5:25 pm