Date: 01/30/09 (Algorithms)    Keywords: html, java

I’m hoping someone here might know why this is not working as expected. I’m attempting to generate pseudo-random throws of dice in Java. In each round I generate 15 values from 1 to 6. From the player’s perspective, 5 dice are rolled, and any or all of them may be re-rolled one or twice. I implement this by taking the first roll from the first 5 values, whichever dice are not held on the first re-roll from the corresponding 6th to 10th values, and whichever are not held on the second re-roll from the 11th to 15th values.

I became suspicious that something was not right, and I believe I have shown that to be so. I’ve tried two sources of random numbers: one is the Random class built into Java (which is a linear congruential generator); the other is an implementation of the Mersenne twister. Both exhibit the same anomalies, so I presume the fault must lie in the routine that reduces the range to six integers, which is common to both.

package randomtest;
import net.goui.util.MTRandom;  // http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/VERSIONS/JAVA/MTRandom.java
import java.util.Random;        // http://java.sun.com/j2se/1.4.2/docs/api/java/util/Random.html

public class Main {
    
    static class Roller {
        Random rng = new Random();           // alternate: new MTRandom()
        static int roll[] = new int[15];
        Roller() {
        }
        public void start() {for (int i=0; i<15; ++i) roll[i] = rng.nextInt(6) + 1;}
    }

    static Roller roller = new Roller();
    static int freq12[]  = {0, 0, 0, 0, 0, 0, 0};
    static int freq13[]  = {0, 0, 0, 0, 0, 0, 0};
    static int freq23[]  = {0, 0, 0, 0, 0, 0, 0};
    static int freq123[] = {0, 0, 0, 0, 0, 0, 0};
    
    public static void main(String[] args) {
    
        for (int n = 0; n < 10000000; ++n) {
            roller.start();
            for (int i=0; i<5; ++i) {
                int r1 = Roller.roll[i];
                int r2 = Roller.roll[i+5];
                int r3 = Roller.roll[i+10];
                if (r1 == r2) ++freq12[Roller.roll[r1]];
                if (r1 == r3) ++freq13[Roller.roll[r1]];
                if (r2 == r3) ++freq23[Roller.roll[r2]];
                if (r1 == r2 && r2 == r3) ++freq123[Roller.roll[r2]];
            }
            if ((n+1)%1000000 == 0) System.out.println("Trial " + (n+1) + ".");
        }

        System.out.println("Expected is: 1388889 / 1388889 / 1388889 / 231481.");
        for (int n=1;n<7;++n)
            System.out.println("Frequency of " + n + " repeating = "
                + freq12[n] + " / " + freq13[n] + " / " + freq23[n] + " / " + freq123[n] + ".");
    }

}

================================================================

Using java.util.Random:

Expected is: 1388889 / 1388889 / 1388889 / 231481.
Frequency of 1 repeating = 1388407 / 1479475 / 1293479 / 230274.
Frequency of 2 repeating = 1388173 / 1479752 / 1295680 / 231701.
Frequency of 3 repeating = 1388272 / 1482455 / 1295064 / 231626.
Frequency of 4 repeating = 1389251 / 1482245 / 1299079 / 232087.
Frequency of 5 repeating = 1386727 / 1205065 / 1574504 / 231813.
Frequency of 6 repeating = 1387655 / 1201628 / 1573153 / 230599.

Expected is: 1388889 / 1388889 / 1388889 / 231481.
Frequency of 1 repeating = 1388231 / 1481334 / 1294928 / 231923.
Frequency of 2 repeating = 1389308 / 1480868 / 1296429 / 230650.
Frequency of 3 repeating = 1388965 / 1479818 / 1295699 / 230441.
Frequency of 4 repeating = 1390373 / 1483708 / 1295996 / 231994.
Frequency of 5 repeating = 1388448 / 1203915 / 1574332 / 232041.
Frequency of 6 repeating = 1387842 / 1204130 / 1573698 / 230794.

Expected is: 1388889 / 1388889 / 1388889 / 231481.
Frequency of 1 repeating = 1389463 / 1480259 / 1295834 / 231346.
Frequency of 2 repeating = 1390002 / 1481980 / 1295481 / 231499.
Frequency of 3 repeating = 1391705 / 1482439 / 1296473 / 232614.
Frequency of 4 repeating = 1387626 / 1481225 / 1296746 / 231314.
Frequency of 5 repeating = 1388892 / 1203113 / 1572535 / 231855.
Frequency of 6 repeating = 1389320 / 1205755 / 1573967 / 231393.

================================================================

Using net.goui.util.MTRandom:

Expected is: 1388889 / 1388889 / 1388889 / 231481.
Frequency of 1 repeating = 1387599 / 1483090 / 1297874 / 231546.
Frequency of 2 repeating = 1388028 / 1479094 / 1295584 / 230952.
Frequency of 3 repeating = 1388372 / 1481956 / 1295757 / 231383.
Frequency of 4 repeating = 1388979 / 1481177 / 1296873 / 231376.
Frequency of 5 repeating = 1389075 / 1204569 / 1573831 / 231396.
Frequency of 6 repeating = 1389061 / 1204809 / 1574539 / 232224.

Expected is: 1388889 / 1388889 / 1388889 / 231481.
Frequency of 1 repeating = 1389284 / 1481200 / 1296447 / 231230.
Frequency of 2 repeating = 1391831 / 1480311 / 1295396 / 231499.
Frequency of 3 repeating = 1388017 / 1483176 / 1295311 / 231774.
Frequency of 4 repeating = 1390365 / 1481329 / 1295701 / 231424.
Frequency of 5 repeating = 1388466 / 1204211 / 1573249 / 231480.
Frequency of 6 repeating = 1387819 / 1204227 / 1571301 / 230896.

Expected is: 1388889 / 1388889 / 1388889 / 231481.
Frequency of 1 repeating = 1386641 / 1481585 / 1294466 / 231443.
Frequency of 2 repeating = 1388663 / 1481050 / 1295534 / 231235.
Frequency of 3 repeating = 1389067 / 1481547 / 1296505 / 232172.
Frequency of 4 repeating = 1390075 / 1482439 / 1298168 / 232068.
Frequency of 5 repeating = 1388224 / 1203076 / 1574220 / 230492.
Frequency of 6 repeating = 1389230 / 1203987 / 1575746 / 231630.

I previously tested the frequencies of each number — they are as expected; but there seems to be correlation between values in certain positions in the 15-number groups I’m generating, and I don’t know why, nor how to go about eliminating it.

Any insight and/or advice would be greatly appreciated.

Source: http://algorithms.livejournal.com/101403.html