4
$\begingroup$

I was learning for the test, when I spotted problem that I cannot deal with:

We have an algorithm that gives correct answer with a probability $p>\frac{1}{2}$. For simplicity assume that the answer is an integer. To increase the probability of obtaining the correct result we execute this algorithm $n$ times and we take the median of the results. Estimate the probability of getting the correct answer.

Maybe Markov's or Chebyshev's inequality will be useful? But I don't know how to approach taking this median. Can anyone help?

  • 0
    Yes you are right.$floor$should be taken for the summation and $1/n$ shouldnt be there.2012-12-09

2 Answers 2

2

Let the correct answer be $\xi$ and the outcome of the repetitions be $x_1,x_2,\ldots,x_n$ respectively. $\Pr{(x_i=\xi)} = p \quad \forall i$ This makes the overall experiment a binomial distribution with $n$ attempts and $p$ probability of succeeding in each trial.

If $\xi$ is the median of the $n$ trials, then the necessary and sufficient conditions are $\Pr{(x_i\geq\xi)} = 0.5 \quad \& \quad\Pr{(x_i\leq\xi)} = 0.5 $

The probability of this happening is the answer you are looking for i.e. $\Pr(\Pr{(x_i\geq\xi)} = 0.5)$. In order to do this, you need to know the skewness of your errors i.e. what are the chances that the output will be greater than the real answer . The data given is insufficient.

A bound can be given by the observation that if out of $n$ observations, if more than half of the values are equal, then they are also equal to the median. So, the lower bound on this will be given by the probability that at least half of the answers are correct. It can be calculated straightforward by using CDF of binomial distribution with parameters $(n,p)$

3

For the median not to give the correct answer, there must be at least $\lceil \frac{n+1}2\rceil$ outcomes that are too low or at least $\lceil \frac{n+1}2\rceil$ outcomes that are too high. Not knowing whether "too high" and "too low" occur with the same probability, we can only give a lower bound for the probability that the median gives the correct answer and this bound is given by the probability of more than $\frac n2$ successes in a $(n,p)$ Bernoulli experiment.