Find the optimal strategy in a variant of the best choice problem where the median is to be selected; see http://math.stackexchange.com/questions/33227

Question33227.java

import java.util.Random;

public class Question33227 {
    public static void main (String [] args) {
        int n = Integer.parseInt (args [0]);
        int n2 = n / 2;

        int [] d = new int [n];
        for (int i = 0;i < d.length;i++)
            d [i] = -1;

        double a = 0;
        for (int i = n - 1;i >= 0;i--) {
            double sum = 0;
            double p = (i + 1.) / (n * binomialCoefficient (n2 + n2,i));
            for (int j = 0;j <= i;j++) { // position of current candidate in candidates seen
                int above = j;
                int below = i - j;
                double q = binomialCoefficient (n2,above) * binomialCoefficient (n2,below) * p;
                if (q > a) {
                    sum += q;
                    if (d [i] == -1)
                        d [i] = j;
                }
                else
                    sum += a;
            }
            a = sum / (i + 1.);
            System.out.println (i + " : " + d [i] + " / " + a);
        }

        final int ntrials = 1000000;

        int successes = 0;
        Random random = new Random ();

        for (int k = 0;k < ntrials;k++) {
            for (int i = 0;i < n;i++) {
                int rank = random.nextInt (i + 1);
                if (d [i] != -1 && rank >= d [i] && rank <= i - d [i]) {
                    for (int j = i + 1;j < n;j++)
                        if (random.nextInt (j + 1) <= rank)
                            rank++;
                    if (rank == n2)
                        successes++;
                    break;
                }
            }
        }

        System.out.println (successes / (double) ntrials);
    }

    static double binomialCoefficient (int n,int k) {
        double binomial = 1;
        int top = n;
        int bottom = 0;

        for (int i = 0;i < k;i++) {
            binomial *= top--;
            binomial /= ++bottom;
        }

        return binomial;
    }
}