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