Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.



[Mathqa]Re: Calculating Chernoff bound for Laplace distribution
Posted:
Mar 24, 2001 2:57 PM


Ruben Lysens wrote: > I've got a question about an example in Proakis' book 'Digital > Communications' (Example 216) (not off topic. This is about > probability, not Digital Communications) :
If you have any other questions about this sort of calculation (ie large deviations estimates in communication problems) may I recommend "Performance guarantees for communication networks" by ChengShang Chang, which (in my opinion) has a very readable basic introduction.
> I'd like to calculate the Chernoff bound for a Laplace distributed > random variable: > The Laplace pdf: p(y) = (1/2)*exp(y) > The Chernoff bound for the upper tail probability: > P(Y>=delta) >= exp(v*delta)*E(exp(v*Y))
I think this should be P(Y>=delta) <= exp... (for v>0, which it is in this case, if delta>0).
> So, to solve the above equation I need to find the moments E(Y*exp(v*Y)) > and E(exp(v*Y)) for the given pdf.
Do you know that E(Y exp(v Y)) = d/dv E(exp(v Y))? The right hand integral is a little easier to do.
> For the upper tail: y >= 0 > oo > E(Y*exp(v*Y)) = {y*exp(v*y)*(1/2)*exp(y)*dy > 0 > oo > = {(1/2)*y*exp((v1)*y)*dy > 0
This is correct. You should end up with 1/2 1/(1v)^2 for the upper tail. You should also end up with 1/2 1/(1+v)^2 for the lower tail.
> After applying partial integration etc. I end up with: > E(Y*exp(v*Y)) = 1/(1v)^2 for v < 1.
This is wrong. Perhaps you got the wrong answer for the lower tail.
Can I also suggest a different way to think about these? I suggest you try to solve this sort of problem by Prob(Y>=y) <= sup_{v in Reals} v y  L(v) where L(v) = log Expect exp(v Y). Of course this gives the same answer in this case  but it might be more helpful when the optimizing v does not exist.
Damon Wischik.
__________________



