Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
Drexel University 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 2-1-6) (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 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.
__________________
|
|
|
|
