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?

$\endgroup$
7
  • $\begingroup$ You say that answer is represented by an integer. Do you mean an integer between $0$ and $\infty$ or it is bounded by two integers? $\endgroup$ Dec 9, 2012 at 11:40
  • $\begingroup$ Does that matter if one is taking the median value, rather than the mean? $\endgroup$ Dec 9, 2012 at 11:42
  • 1
    $\begingroup$ Median function can be converted to the summation of sign functions of your outcome. Shift the inverval $[a, b]$ by some value $c\in [a,b]$ to $y=0$: when $n\rightarrow\infty$, $\frac{1}{n}\sum_n sign(X_n)-c\rightarrow 0$ if $c$ is the true value. Then for all $c\in [a,b]$ there is one $c$ which minimizes the $\frac{1}{n}\sum_n sign(X_n)-c$ that is the true estimate. $\endgroup$ Dec 9, 2012 at 12:47
  • $\begingroup$ @Seyhmus: that's really interesting. How is assumed in this case $sign(0)$? $\endgroup$ Dec 9, 2012 at 13:44
  • $\begingroup$ It is direct translation from the continuous case. I would say $sign(0)=0.5$ and using the $floor$ function to the final result. $\endgroup$ Dec 9, 2012 at 13:55

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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)$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .