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 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?

share|improve this question
    
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? –  the_candyman Dec 9 '12 at 11:40
    
Does that matter if one is taking the median value, rather than the mean? –  Simon Hayward Dec 9 '12 at 11:42
1  
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. –  Seyhmus Güngören Dec 9 '12 at 12:47
    
@Seyhmus: that's really interesting. How is assumed in this case $sign(0)$? –  the_candyman Dec 9 '12 at 13:44
    
It is direct translation from the continuous case. I would say $sign(0)=0.5$ and using the $floor$ function to the final result. –  Seyhmus Güngören Dec 9 '12 at 13:55

2 Answers 2

up vote 2 down vote accepted

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

share|improve this answer

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.

share|improve this answer

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.