Давай бросим кубик

Допустим, я хочу создать в своей программе возможность бросать кубик. Не задумываясь, мы вызываем встроенную функцию Math.random () в JavaScript (или эквивалент на любом другом языке) и настраиваем ее с помощью некоторых простых манипуляций до желаемого диапазона. Но действительно ли это число случайное? Словарное определение random описывается следующим образом:

«Сделано, сделано, происходит или выбрано без метода или сознательного решения».

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

Взгляд на MDN для Math.random () дает нам некоторое представление о том, что на самом деле происходит за сценой.

«Псевдослучайное число в диапазоне 0–1 (включая 0, но не 1) с приблизительно равномерным распределением в этом диапазоне - которое затем можно масштабировать до желаемого диапазона. Реализация выбирает начальное начальное число для алгоритма генерации случайных чисел; он не может быть выбран или сброшен пользователем ».

Генератор псевдослучайных чисел

Случайные числа, сгенерированные нашими программами, на самом деле являются псевдослучайными числами, потому что числа, генерируемые алгоритмом, по определению не являются случайными. Однако эти числа кажутся достаточно случайными, и большинство пользователей на них не жалуется. Существует множество реализаций генератора псевдослучайных чисел (ГПСЧ), и они различаются от языка к языку. Многие ГПСЧ сегодня используют метод линейной конгруэнтности. Вот формула того, как получить следующее случайное число x ₙ₊₁ на основе предыдущего случайного числа x ₙ:

k, c и m - константы, выбранные пользователем для создания последовательности. Для запуска всего процесса выбирается начальное число 𝑥₀ seed.

Не все реализации одинаковы. Например, если мы выбрали k = 23, c = 51 и m = 100 с начальным начальным значением 𝑥₀ = 19, мы можем увидеть, как быстро последовательность начинает повторяться:

function randomNumGenerator(k, c, m, seed, loop) {
    let prevNum = seed
    let randNums = [seed]
    for(let i = 0; i < loop; i++) {
        prevNum = (k * prevNum + c) % m
        randNums.push(prevNum)
    }
    console.log(randNums.join())
}
randomNumGenerator(23, 51, 100, 19, 22)
//=>19,88,75,76,99,28,95,36,79,68,15,96,59,8,35,56,39,48,55,16,19,88

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

Могу ли я быть более «случайным»?

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

Если мы немного изменим m на 101, мы увидим значительное изменение периода с 20 до 50.

randomNumGenerator(23, 51, 101, 19, 50)
//=>19,84,64,8,33,2,97,60,17,38,16,15,93,69,22,52,35,48,44,53,58,72,91,23,75,59,95,14,70,45,76,82,18,61,40,62,63,86,9,56,26,43,30,34,25,20,6,88,55,3,19

Если мы более осознанно выберем значения m и c, мы сможем увеличить длину периода, чтобы наши числа казались более случайными. Если мы выберем m как степень двойки, например 2³² или 2⁶⁴, или если m или c являются относительно простыми, мы можем приблизиться к обману наши пользователи, что числа случайны.

Логистическая карта

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

Начиная с начального значения между 0 и 1, последовательность значений будет перемещаться назад и вперед в пределах подинтервала [a, b] между 0 и 1. Затем мы можем преобразовать это с помощью следующего

Однако это ведет себя хаотично только для определенных значений r; в частности 𝑟 ›3.56995.

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

Хаос: когда настоящее определяет будущее, но приблизительное настоящее не определяет будущее приблизительно.

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

Все еще не верите в свой язык программирования?

Ваш компьютер действительно неплохо генерирует случайные числа. Не язык программирования, а сам компьютер. Есть числа, которые можно создать, более близкие к истинной случайности, с помощью аппаратного генератора случайных чисел (HRNG). Эти числа генерируются на основе физических процессов, а не алгоритма. Ваша операционная система имеет гораздо больший источник данных, чем выбранное пользователем начальное значение для создания случайного числа, такого как температура процессора, количество секунд с момента нажатия последней клавиши, количество пикселей от предыдущей позиции мыши. Эти события, вероятно, непредсказуемы и намного ближе отражают случайность.

Как узнать, достаточно ли я выгляжу случайно?

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

string1 = "abcabcabcabcabcabcabcabcabcabc"
string2 = "31832jdksnckjanlml201lakcnqwli"

Мы можем легко распознать шаблон строки 1 как повторяющуюся букву «abc», но сложно собрать шаблон для строки 2. В этом случае строка2 более сложная, чем строка1. Теория Чайтина-Колмогорова помогает нам измерить этот тип сложности.

Теория Чайтина-Колмогорова измеряет сложность конечной последовательности с точки зрения длины кратчайшей программы, которая ее сгенерирует.

function generateString1() {
    return "abc".repeat(10)
}
function generateString2() {
    return "31832jdksnckjanlml201lakcnqwli"
}

В приведенных выше функциях мы видим, что generateString1 содержит меньше символов, чем generateString2, но они генерируют строку той же длины. Колмогоровская сложность string2 больше, чем string1.

Это можно проиллюстрировать дополнительно, если мы увеличим длину обеих строк до 60. Длина generateString1 будет иметь такое же количество символов, но generateString2 расширит оператор return на дополнительные 30 символов.

function generateString1() {
    return "abc".repeat(20)
}
//=>abcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabc
function generateString2() {
    return "31832jdksnckjanlml201lakgcnqwli92jsksmz01pq26hsunx81lz01me92"
}
//=>31832jdksnckjanlml201lakgcnqwli92jsksmz01pq26hsunx81lz01me92

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