Насколько случайным является JavaScript Math.random?

Question

В течение 6 лет у меня на сайте была генератор случайных чисел . В течение долгого времени это был первый или второй результат в Google для «генератора случайных чисел», и он использовался для определения десятков, если не сотен конкурсов и рисунков на дискуссионных форумах и в блогах (я знаю, потому что вижу рефералов в моем веб-логи и обычно иди посмотри).

Сегодня кто-то написал мне по электронной почте, чтобы сказать , что это может быть не так случайно, как я думал. Она попыталась сгенерировать очень большие случайные числа (например, от 1 до 10000000000000000000) и обнаружила, что они почти всегда были такое же количество цифр. Действительно, я обернул функцию в цикл, чтобы я мог генерировать тысячи чисел и, конечно же, для очень больших чисел вариация составляла всего около 2 порядков.

Почему?

Вот зацикленная версия, так что вы можете попробовать ее сами:

http://andrew.hedges.name/experiments/random/randomness.html

Он включает в себя как простую реализацию, взятую из Mozilla Developer Network , так и некоторый код 1997 года, который я стер с веб-страницы, которая больше не существует ("Central Randomizer 1.3" Пола Хоула). Просмотрите исходный код, чтобы увидеть, как работает каждый метод.

Я прочитал здесь и в другом месте о Мерсенн Твистер. Что меня интересует, так это то, почему не было бы большего различия в результатах из встроенной в JavaScript функции Math.random . Спасибо!

Answer 1

Даны числа от 1 до 100.

• 9 имеют 1 цифру (1-9)
• 90 имеет 2 цифры (10-99)
• 1 имеет 3 цифры (100)

Даны числа от 1 до 1000.

• 9 имеют 1 цифру
• 90 состоит из 2 цифр
• 900 состоит из 3 цифр
• 1 имеет 4 цифры

и т. Д.

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

Answer 2

Ваши результаты действительно ожидаемые. Если случайные числа равномерно распределены в диапазоне от 1 до 10 ^ n, можно ожидать, что около 9/10 чисел будут иметь n цифр, а еще 9/100 - n-1 цифр.

Answer 3

Там разные виды случайности. Math.random дает вам равномерное распределение чисел.

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

function random_powerlaw(mini, maxi) {
    return Math.ceil(Math.exp(Math.random()*(Math.log(maxi)-Math.log(mini)))*mini)
}

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

Существуют также другие распределения для случайных чисел, такие как нормальное распределение (также называемое распределением Гаусса).

Answer 4

В следующей статье объясняется, как math.random () в основных веб-браузерах (небезопасен): "Временное отслеживание пользователей в основных браузерах и междоменная информация Утечка и атаки ", Amid Klein (2008) . Он не сильнее обычных встроенных в PRNG функций Java или Windows.

С другой стороны, для реализации SFMT периода 2 ^ 19937-1 требуется 2496 байтов внутреннего состояния, поддерживаемого для каждой последовательности PRNG. Некоторые люди могут считать это непростительной стоимостью.

Answer 5

Выглядит совершенно случайно для меня! (Подсказка: это зависит от браузера.)

Лично я думаю, что моя реализация будет лучше, хотя я украл ее у XKCD , которого ВСЕГДА следует признать:

function random() {
  return 4; // Chosen by a fair dice throw. Guaranteed to be random.
}

Answer 6

Я попробовал генератор псевдослучайных чисел JS на Chaos Game .

Мой треугольник Серпинского говорит, что это довольно случайно:

Answer 7

Если вы используете число типа 10000000000000000000, вы выходите за пределы точности типа данных, который использует Javascript. Обратите внимание, что все сгенерированные числа заканчиваются на "00".

Answer 8

Что ж, если вы генерируете числа, скажем, до 1e6, вы, вероятно, получите все числа с примерно равной вероятностью. Это также означает, что у вас есть только один шанс из десяти получить число с одной цифрой меньше. Один шанс из ста получить на две цифры меньше и т. Д. Я сомневаюсь, что при использовании другого ГСЧ вы увидите большую разницу, потому что у вас равномерное распределение по числам, а не по их логарифму.

Answer 9

Неслучайные числа, равномерно распределенные от 1 до N, имеют одинаковые свойства. Обратите внимание, что (в некотором смысле) это вопрос точности. Равномерное распределение на 0-99 (в виде целых чисел) имеет 90% своих чисел, имеющих две цифры. Равномерное распределение по 0-999999 имеет 905 своих номеров, имеющих пять цифр.

Любой набор чисел (при некоторых не слишком ограничительных условиях) имеет плотность. Когда кто-то хочет обсудить «случайные» числа, плотность этих чисел должна быть указана (как отмечено выше). Общая плотность - это равномерная плотность. Есть и другие: экспоненциальная плотность, нормальная плотность и т. Д. Прежде чем предлагать генератор случайных чисел, нужно выбрать, какая плотность является релевантной. Кроме того, числа, приходящие из одной плотности, часто можно легко преобразовать в другую плотность кариозными средствами.