Первые 100-о значения из "случайной последовательности".
(вариант с одним rnd !, от двух rnd лучше явно не станет)

Твой тест просто показывает, что _в_очень_большом_ псевдослучайном числе очень много и примерно одинаково знаменателей от 1 до ...не более 20...

Весь алгоритм можно свести к формуле:

сгенерировать BigInteger методом сложения многих случайных чисел от 0 до N
взять остаток от деления этого BigInteger на M

НО !
1) Так как мы знаем, что очень большой BigInteger будет подчинять не "равномерному распределению", а будет "нормальное распределение"

То, следующим шагом нужно доказать/опровергнуть, что значение mod % M из случайного числа подчиняющегося "нормальному распределению" будет подчиняться "равномерному распределению"

Я не математик, т.ч. я пасс )))

2)
Кроме всего прочего, нужно доказать, что не будет корреляции между соседними значениями. В вырожденных случаях (напрмер N < M), такая корреляция явно наблюдается.

В случае M > N, как мне кажется, корреляция тоже должна быть. "Двойной" рандом, такую корреляцию конечно будет сглаживать, но это как-то из пушки по воробьям (плюс двойной рандом должен портить генератор, давая вместо "равномерного" "нормальное" распределение)

3)
Двойной вызов рандома, с чисто "програмной" точки зрения расточительно. Кроме того, смысл двойного (а не тройного, пятерного, десятерного) - я вообще не понимаю.

DimaT,

Доказать, что алгоритм работает - крайне сложно
Доказать, что алгоритм НЕ работает - крайне легко, привести пример, когда он не работает

ЗАЧЕМ ?

И так уже есть случайное число (псевдослучайное), зачем в него что-то совать?

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

На входе есть последовательность случайных 0 / 1 (пусть аппаратный датчик случайных чисел), нам нужно последовательность 0..3

Теорема 1. У меня есть чувство, что если мы из последовательности случайных бит склееваем случайный байт, то он будет "равномерно распределен" (требуется доказательство!). Собственно суммирования тут нет.

Теорема 2. Так же, есть такое чувство, что если взять случайные байты и расклееть их на биты - будет аналогично (требуется доказательство)

а вот дальше, уже аксиома: из "большого числа" мы всегда можем __экономно__ нарезать любое кол-во чисел в другой системе счисления

Т.е. получаем queue из двух алгоритмов
1) Т.е. один алгоритм должен digit'ы в системе счисления N наталкивать
new_value = value * N + digitIn
2) С другого конца, алгоритм digit'ы в системе счисления M выталкивать
digitOut = value mod M
new_value = value / M

Что-то пока не сообразить, как отслеживать текущее кол-во актуальных digit'ов в value и когда собственно запускать считывание следующего digit'а (((

Как-то доказательство лично для меня не убедительно

"там будет вызвано getRandomN() максимум k раз"
"мы получаем N ^k равновероятных исходов"

если кол-во вызовов getRandomN может быть разным (на что намекает слово максимум в предыдущем предложении), то получим не N ^k , а какое-то число <= N ^k