Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Topic: [Mathqa]Re: Calculating Chernoff bound for Laplace distribution
Replies: 0

 D.J. Wischik Posts: 3 Registered: 12/8/04
[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 2-1-6) (not off topic. This is about
> probability, not Digital Communications) :

(ie large deviations estimates in communication problems) may I
recommend "Performance guarantees for communication networks"
by Cheng-Shang 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((v-1)*y)*dy
> 0

This is correct. You should end up with
1/2 1/(1-v)^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/(1-v)^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.

__________________