Does Java's Random Object create random numbers through equal opportunity?

I'm trying to write a short program that plays a dice game (normal 6 sided dice) for me. The first roll's number is added to the score. After the first roll, if I roll a 6 then the game stops and the score is recorded (without adding the 6). If a 6 is rolled on the first roll, that's fine and i开发者_如何学Pythont's added like any other number 1 through 5. I'm trying to run a bunch of iterations of this game such that I have a long list of scores pre-bust (a bust being a rolled 6). I rearrange those scores to be in order from smallest to largest and then find the median of the list which is the score at which it is optimal to stop.

For some reason I keep getting 13 when I run the program but I know for a fact that the answer should be 15. Would using Random in Java would have some sort of effect on the median? I don't exactly know how Random generates the numbers and whether it creates them with equal opportunity. Also, is there anything that just pops out that shouldn't work?

import java.util.*;
public class DiceRoller {

private static Random r = new Random();
private static final int games = 10001;
private static int[] totalScores = new int[games];
private static int index = 0;

public static void main(String[] args) {
    int score = 0; boolean firstRoll = true;
    while (index < games) {
        int roll = roll();
        if (firstRoll) {
            score += roll;
            firstRoll = false; 
        } else {
            if (roll == 6) {
                totalScores[index] = score;
                index++; 
                score = 0; firstRoll = true;
            } else {
                score += roll;
            }
        }
    } 
    System.out.println("The median is " + median() + ".");
}

public static int roll() {
    return r.nextInt(6) + 1;
}

public static int median() {
    Arrays.sort(totalScores);
    int temp = totalScores[games / 2];
    return temp;
}

}

You get 13 because that's the correct result. A little mathematics: if S is the random variable representing the score of any one of these games, then you can consider the Probability generating function f(z) of S. From the description of the game, this probability generating function satisfies the equation:

f(z) = (z + z^2 + z^3 + z^4 + z^5 + z^6) / 36 + f(z)(z + z^2 + z^3 + z^4 + z^5) / 6

This takes a bit of thought, or familiarity with this sort of construction: the left-hand term on the right-hand side takes account of the probabilities of getting 1 through 6 in a simple 2-roll game; the right-hand term involving f(z) takes account of games involving 3 or more rolls, expressing them in terms of the final pre-6 roll (which must be in the range 1 through 5) and the preceding rolls, whose probabilities we can express recursively using f again.

Anyway, after getting this far, one can rearrange to describe f as a rational function of z, and then expand as a power series, which begins:

f(z) = 1/36*z + 7/216*z^2 + 49/1296*z^3 + 343/7776*z^4 + 2401/46656*z^5 + 16807/279936*z^6 + 63217/1679616*z^7 + 388087/10077696*z^8 + 2335585/60466176*z^9 + 13681927/362797056*z^10 + 77103313/2176782336*z^11 + 409031959/13060694016*z^12 + 2371648321/78364164096*z^13 + 13583773735/470184984576*z^14 + ...

(I used Pari/GP to get this.)

The coefficient of z^k then describes the probability of the value of the game being k; thus there's a 1 in 36 chance of the score being 1, a 7 in 216 chance of getting 2, and so on. The sum of the first 12 coefficients is 0.472828864487196328..., while the sum of the first 13 coefficients is 0.5030933144224321950968.... So the median is indeed 13.

To provide an independent check, I wrote a quick Python program:

from __future__ import division
import random

def roll():
    return random.randint(1, 6)

def play():
    score = roll()
    while True:
        throw = roll()
        if throw == 6:
            break
        score += throw
    return score

all_scores = sorted(play() for _ in xrange(1000001))
print "median is: ",all_scores[len(all_scores) // 2]
print "fraction of scores <= 12: ",all_scores.index(13) / len(all_scores)
print "fraction of scores <= 13: ",all_scores.index(14) / len(all_scores)

Sure enough, here are the results:

iwasawa:~ mdickinson$ python dice_game.py 
median is:  13
fraction of scores <= 12:  0.472811527188
fraction of scores <= 13:  0.502863497137

So to answer your question, the results you're seeing are not evidence of any sort of weakness in Java's random number generation.

Random is not perfectly random and has some deficiencies. However for this use case you are very unlikely to notice the difference. You can assume every value 1 to 6 is equally likely.

For comparison here is another solution which counts the number of occurrences of a total rather than recording every value. As you can see this performs well even if you have 1000x more games. This works best when you have a small number of outcomes and a high number duplicates. It is naturally sorted.

import java.util.Random;

public class DiceRoller {
  private static final int MAX_VALUE = 300; // assume at most this total
  private static final int GAMES = 10000001;

  public static void main(String... args) {
    int[] count = new int[MAX_VALUE];
    Random rand = new Random();
    for (int i = 0; i < GAMES; i++)
      count[totalScore(rand)]++;
    System.out.println("The median is " + median(count, GAMES) + ".");
  }

  private static int median(int[] count, int games) {
    int findTotal = games/2;
    for (int i = 0; i < count.length; i++) {
      findTotal -= count[i];
      if (findTotal <= 0) return i;
    }
    throw new AssertionError();
  }

  private static int totalScore(Random rand) {
    int total = rand.nextInt(6) + 1;
    for(int n;(n = rand.nextInt(6) + 1) != 6;)
      total += n;
    return total;
  }
}

Here is some code that shows you the distribution of the results. It doesn't really answer the question, but maybe it helps you in your research.

package so7297660;

import java.util.Random;

public class DiceRoller {

  private static final int N = 10000000;
  private static final Random r = new Random();
  private static final int[] result = new int[100];

  public static int roll() {
    return r.nextInt(6) + 1;
  }

  private static int singleGame() {
    int score = roll();
    while (true) {
      int roll = roll();
      if (roll == 6) {
        return score;
      } else {
        score += roll;
      }
    }
  }

  private static int median() {
    int n = 0;
    for (int i = 0; i < result.length; i++) {
      if (n + result[i] >= N / 2) {
        return i;
      }
      n += result[i];
    }
    throw new IllegalStateException();
  }

  public static void main(String[] args) {
    for (int i = 0; i < N; i++) {
      int score = singleGame();
      int index = Math.min(score, result.length - 1);
      result[index]++;
    }
    for (int i = 0; i < result.length; i++) {
      System.out.println(i + "\t" + result[i]);
    }
    System.out.println("median\t" + median());
  }

}