Случайный объект Java создает случайные числа через равные возможности?

Question

Я пытаюсь написать короткую программу, которая играет в игру в кости (обычные 6-гранные кости) для меня. Номер первого броска добавляется к счету. После первого броска, если я бросаю 6, игра останавливается и счет записывается (без добавления 6). Если на первом броске выпадает 6, это нормально, и оно добавляется, как и любое другое число с 1 по 5. Я пытаюсь запустить кучу итераций в этой игре так, чтобы у меня был длинный список результатов перед бюстом ( бюст свернутый 6). Я переставляю эти оценки в порядке от наименьшего к наибольшему, а затем нахожу медиану списка, то есть оценку, на которой оптимально остановиться.

По какой-то причине я продолжаю получать 13, когда я запускаю программу, но я точно знаю, что ответ должен быть 15. Будет ли использование Random в Java каким-то образом влиять на медиану? Я точно не знаю, как Random генерирует числа и создает ли они их с равными возможностями. Кроме того, есть что-то, что просто не может работать?

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;
}

}

Answer 1

Вы получите 13, потому что это правильный результат.Немного математики: если S является случайной величиной, представляющей счет в любой из этих игр, то вы можете рассмотреть функцию генерации вероятности f(z) из S.Исходя из описания игры, эта функция, генерирующая вероятность, удовлетворяет уравнению:

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

Это требует некоторого размышления или знакомства с такой конструкцией: левый терминс правой стороны учитывает вероятности получения от 1 до 6 в простой игре с 2 бросками;правое слагаемое, включающее f (z), учитывает игры с участием 3 или более бросков, выражая их в терминах финального броска до 6 (который должен быть в диапазоне от 1 до 5) и предыдущих бросков, вероятности которых мыможно рекурсивно выразить, используя f снова.

В любом случае, пройдя этот путь, можно перегруппировать, описать f как рациональную функцию z, а затем расширить как степенной ряд, который начинается:

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 + ...

(я использовал Пари / ГП , чтобы получить это.)

Затем коэффициент z^k описывает вероятностьстоимость игры k;таким образом, есть шанс 1 к 36 при счете 1, шанс 7 к 216 получить 2 и так далее.Сумма первых 12 коэффициентов равна 0.472828864487196328..., а сумма первых 13 коэффициентов равна 0.5030933144224321950968....Таким образом, медиана действительно равна 13.

Чтобы обеспечить независимую проверку, я написал небольшую программу на Python:

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)

Конечно, вот результаты:

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

Итак, чтобы ответить на ваш вопрос, результаты, которые вы видите, не свидетельствуют о какой-либо слабости в генерации случайных чисел в Java.

Answer 2

Рандом не является абсолютно случайным и имеет некоторые недостатки.Однако в этом случае вы вряд ли заметите разницу.Можно предположить, что одинаково вероятны все значения от 1 до 6.

Для сравнения приведено еще одно решение, которое подсчитывает количество вхождений итога, а не записывает каждое значение.Как видите, это хорошо работает, даже если у вас в 1000 раз больше игр.Это работает лучше всего, когда у вас есть небольшое количество результатов и большое количество дубликатов.Это естественно отсортировано.

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;
  }
}

Answer 3

Вот код, который показывает вам распределение результатов.Это на самом деле не отвечает на вопрос, но, возможно, это поможет вам в ваших исследованиях.

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());
  }

}