Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

i'm studing probabilistic algorithms: the ones that - with a great gain in efficency - sometimes could return a false response.

They return the true response with a probability of $\frac{3}{4}$. The the way to use them to lower the error probability is: runs $t$ times, compare results and gets the more frequent answer.

Those algos (that are for decision problems) can respond True or False, so two discrete random variables, and the binomial probability is used. Chernoff's inequality is important to get the number of $t$ for gain the desired fixed error.

Now, in my book there is this foruma:

$prob \, error <= e^{-2t(x-p)^2}$

where:

  • $p = \frac{3}{4}$ because is the probability of true response
  • $x = \frac{1}{2}$ because i want that the response is True for more of the half of $t$ indipendent executions

i use $prob \, error <= e^{-\frac{t}{8}}$ to get $t$ for a fixed $prob error$

now my question is.. what exactly are $x$ and $p$ in more formal way?

sorry for my bad english, i hope it's clear enough to understand

share|improve this question

1 Answer 1

up vote 7 down vote accepted

Chernoff's bound is a large deviation bound. Consider some binomial experiment $X \sim \mathrm{Bin}{n,p}$; thus $X$ is the sum of $n$ independent coins, each $1$ with probability $p$ and $0$ otherwise.

If $n$ is large then $X$ will be concentrated around its expectation $np$. Close to the expectation, $X$ behaves very similar to a normal variable with the same expectation and variance, i.e. $\mathcal{N}{np,np(1-p)}$. However, far from the center the probability decays much faster than a normal distribution, and one resorts to large deviation bounds.

For any constant $\Delta$, as $n$ grows bigger it becomes exponentially more unlikely that $|X-np| \geq n\Delta$; the quantitative version of this statement is given by Chernoff's bound. Put differently, we have a bound on $$\Pr[X \geq n(p+\Delta)] + \Pr[X \leq n(p-\Delta)];$$ the connection between the parameters $p,\Delta,x$ is that $x = p \pm \Delta$; $x$ is the threshold beyond which it is highly improbable that the average finds itself.

Original answer

Chernoff's bound is a bound on a probability that $\mathrm{Bin}(n,p)$ trials cross the $nx$ threshold. In your case, the algorithm is successful if the majority of answers are right, which means that the threshold in $n/2$.

If $p > x$, then Chernoff bounds the probability that $\mathrm{Bin}(n,p)$ is smaller than $nx$. (If $p < x$ then replace "smaller than" by "larger than".)

share|improve this answer
1  
thanks for your response, but i'm quite new in probability.. could you be a little more verbous? –  nkint Feb 7 '11 at 0:02

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.