Java случайные проценты

В паре ответов предлагается выбрать случайные проценты и взять разницу между ними. Как отмечает Никита Райбек, это не даст равномерного распределения по всем возможностям; в частности, нули будут встречаться реже, чем ожидалось.

Чтобы исправить это, подумайте о том, чтобы начать со 100 "процентов" и вставить делители. Я покажу пример с 10:

 % % % % % % % % % % 

Есть одиннадцать мест, куда можно вставить делитель: между любыми двумя процентами, в начале или в конце. Итак, вставьте один:

 % % % % / % % % % % % 

Это означает выбор четырех и шести. Теперь вставьте еще один делитель. На этот раз мест двенадцать, потому что уже вставленный делитель создает дополнительный. В частности, есть два способа получить

 % % % % / / % % % % % % 

- вставить до или после предыдущего разделителя. Вы можете продолжать процесс, пока не получите столько делителей, сколько вам нужно (на один меньше, чем количество процентов)

 % % / % / % / / % % % / % % % / 

Это соответствует 2,1,1,0,3,3,0.

Мы можем доказать, что это дает равномерное распределение. Число разбиений 100 на k частей равно биномиальному коэффициенту 100+k-1, выбираем k-1. То есть (100+k-1)(100+k-2)... 101 / (k-1)(k-2)*...*2*1 Таким образом, вероятность выбора любого конкретного состава равна обратной величине. Поскольку мы вставляем делители по одному, сначала мы выбираем из 101 позиции, затем 102, 103 и т.д., пока не дойдем до 100+k-1. Поэтому вероятность любой конкретной последовательности вставок равна 1 / (100+k-1)*...*101. Сколько последовательностей вставок приводят к одному и тому же составу? Окончательный состав содержит k-1 делителей. Они могли быть вставлены в любом порядке, поэтому существует (k-1)! последовательностей, которые приводят к данной композиции. Поэтому вероятность любой конкретной композиции именно такова, какой она должна быть.

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

Сгенерируйте n случайных целых чисел с любым диапазоном (назовите их a[1]... a[n]). Суммируйте целые числа и назовите это b. Ваши проценты будут [a[1]/b, ..., a[n]/b].

Edit: хорошие замечания, округление результатов до суммы ровно 100 нетривиально. Одним из подходов было бы взять пол a[x]/b для x в 1...n как ваши целые числа, затем распределить оставшиеся единицы 100-(сумма целых чисел) случайным образом. Я не уверен, что это внесет какую-либо погрешность в результат.

Эта проблема известна как равномерная выборка из симплекса, и Википедия дает два алгоритма:

http://en.wikipedia.org/wiki/Simplex#Random_sampling

См. Также следующие связанные вопросы:

• Образец равномерно случайным образом из n-мерного единичного симплекса
• Построение распределения вероятностей

Создайте массив. В каждую из частей этого массива случайным образом занесите по 100 %. Пример показывает n=7.

import java.util.Random;

public class random100 {
    public static void main (String [] args) {
        Random rnd = new Random();
            int percents[] = new int[7];
            for (int i = 0; i < 100; i++) {
                int bucket = rnd.nextInt(7);
                percents[bucket] = percents[bucket] + 1;
            }
        for (int i = 0; i < 7; i++) {
            System.out.println("bucket " + i + ": " + percents[i]);
        }

    }

}

Ключ состоит в том, чтобы сгенерировать N случайных чисел от 0 до 100, но использовать их как «маркеры», а не конечную последовательность чисел для вывода. Затем вы просматриваете свой список маркеров в возрастающем порядке, вычисляя каждый процент для вывода как (текущий маркер - предыдущий маркер).

Это даст гораздо более равномерное распределение, чем простая генерация и вывод каждого числа по одному.

Пример

import java.util.Random;
import java.util.TreeSet;
import java.util.SortedSet;

public class Main {
  public static void main(String[] args) {
    Random rnd = new Random();
    SortedSet<Integer> set = new TreeSet<Integer>();

    for (int i=0; i<9; ++i) {
      set.add(rnd.nextInt(101));
    }

    if (set.last() < 100) {
      set.add(100);
    }    

    int prev = 0;
    int total = 0;    
    int output;

    for (int j : set) {
      output = j - prev;
      total += output;
      System.err.println(String.format("Value: %d, Output: %d, Total So Far: %d", j, output, total));
      prev = j;
    }
  }
}

Выход

$ java Main
Value: 0, Output: 0, Total So Far: 0
Value: 2, Output: 2, Total So Far: 2
Value: 55, Output: 53, Total So Far: 55
Value: 56, Output: 1, Total So Far: 56
Value: 57, Output: 1, Total So Far: 57
Value: 69, Output: 12, Total So Far: 69
Value: 71, Output: 2, Total So Far: 71
Value: 80, Output: 9, Total So Far: 80
Value: 92, Output: 12, Total So Far: 92
Value: 100, Output: 8, Total So Far: 100

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

1. Генерируем n-1 целых чисел от 0,...100, скажем a[i] для i = 0, до n-2.
2. Пусть total - сумма этих чисел
3. Вычислите b[i] = floor(100*a[i]/total) для i = 0, to n-2
4. Установите b[n-1] = 100 - (b[0] + ... b[n-2]).

Тогда b - это ваш результирующий массив процентов.

Последний из них будет смещен, но остальные должны быть равномерными.

Конечно, если вы хотите сделать это более точным способом, вам придется использовать выборку Гиббса или Metropolis hastings.

Выбрав числа описанным вами способом, измените порядок номеров. Таким образом, окончательный список чисел имеет более равномерное распределение.

Однако обратите внимание, что независимо от того, что вы делаете, вы не можете получить идеально равномерное распределение, поскольку, как только вы начинаете выбирать числа, ваши случайные испытания не являются независимыми. См. Ответ Этайлора.

Обратите также внимание на то, что описанный вами алгоритм может не дать вам требуемого результата. Последнее число не может быть случайным, так как оно должно составлять 100.

Первое, очевидное решение.

do
    int[] a = new int[n];
    for (int i = 0; i < n; ++i) {
        a[i] = random number between 0 and 100;
    }
until sum(a) == 100;

Он не идеален с точки зрения сложности (количество итераций для достижения суммы 100 может быть довольно большим), но распределение определенно «беспристрастно».

редактировать
Аналогичная проблема: как сгенерировать случайную точку в круге с радиусом 1 и центром в (0, 0)? Решение: продолжайте генерировать случайные точки в диапазоне (квадрат) [-1..1, -1..1], пока одна из них не войдет в круг :)

Возможно, вам нужно определить, что вы действительно подразумеваете под "предвзятостью" - но если все, что вас волнует, это то, что распределение чисел не зависит от их положения, то вы можете просто создать числа "предвзятым" образом, а затем рандомизировать их положение.

Другим "беспристрастным" методом было бы создание n-1 случайных процентов, их сортировка (назовем это x1 x2 x3...), а затем определение конечных процентов:

x1
x2 - x1
x3 - x2
...
100 - x(n-1)

Таким образом, вы получите n случайных чисел, которые складываются в 100.

У меня была аналогичная проблема, и в итоге я сделал, как вы сказали, генерируя случайные целые числа до разницы суммы существующих целых чисел и предела.Затем я произвел случайный порядок целых чисел. Это сработало очень хорошо. Это было для генетического алгоритма.

Представьте, что у вас есть 100 камней и N ведер, в которые их нужно положить. Вы можете взять все 100 и положить в случайное ведро. Таким образом, общая сумма будет равна 100, с которой вы начали, и не будет смещения между сегментами.

public static int[] randomBuckets(int total, int n_buckets) {
    int[] buckets = new int[n_buckets];
    Random rand = new Random();
    for(int i=0;i<total;i++)
        buckets[rand.nextInt(n_buckets)]++;
    return buckets;
}

public static void main(String... args) {
    for(int i=2; i<=10;i++)
        System.out.println(Arrays.toString(randomBuckets(100, i)));
}

Печать

[55, 45]
[38, 34, 28]
[22, 21, 32, 25]
[28, 24, 18, 15, 15]
[17, 14, 13, 21, 18, 17]
[17, 19, 14, 15, 6, 15, 14]
[11, 14, 14, 14, 4, 17, 9, 17]
[13, 12, 15, 12, 8, 10, 9, 11, 10]
[11, 13, 12, 6, 6, 11, 13, 3, 15, 10]

По мере увеличения счетчика распределение приближается к равномерному.

System.out.println(Arrays.toString(randomBuckets(100000000, 100)));

Печать

[1000076, 1000612, 999600, 999480, 998226, 998303, 1000528, 1000450, 999529, 
998480, 998903, 1002685, 999230, 1000631, 1001171, 997757, 1000349, 1000527, 
1002408, 1000852, 1000450, 999318, 999453, 1000099, 1000759, 1000426, 999404, 
1000758, 1000939, 999950, 1000493, 1001396, 1001007, 999258, 1001709, 1000593,
1000614, 1000667, 1000168, 999448, 999350, 1000479, 999991, 999778, 1000513, 
998812, 1001295, 999314, 1000738, 1000211, 999855, 999349, 999842, 999635, 
999301, 1001707, 998224, 1000577, 999405, 998760, 1000036, 1000110, 1002471, 
1000234, 1000975, 998688, 999434, 999660, 1001741, 999834, 998855, 1001009, 
999523, 1000207, 998885, 999598, 998375, 1000319, 1000660, 1001727, 1000546, 
1000438, 999815, 998121, 1001128, 1000191, 998609, 998535, 999617, 1001895, 
999230, 998968, 999844, 999392, 999669, 999407, 998380, 1000732, 998778, 1000522]