Skip to content

Instantly share code, notes, and snippets.

@joriki
Created May 13, 2012 23:27
Show Gist options
  • Save joriki/2690768 to your computer and use it in GitHub Desktop.
Save joriki/2690768 to your computer and use it in GitHub Desktop.
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
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;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment