Равновероятный Random. Почему все делают неправильно?

@Toxa33rus · Регистрация: 16.04.2009

Студворк — интернет-сервис помощи студентам

Всем привет!
В любом учебнике по программированию (и любых исходниках программ) в теме генерации случайных чисел пишут примерно так:

Java
1
2
3
4
      int a = 0; // Начальное значение диапазона - "от"
      int b = 10; // Конечное значение диапазона - "до"
      
      int random_number = a + (int) (Math.random() * b); // Генерация случайного числа

Мы знаем, что функция генерирующая случайное число выдает число от 0 включительно до 1 не включительно. Например, 0.8451192811534175.
Что мне тут не нравится? А вот что: при таком подходе вероятность выпадения значений не одинакова!
Чтоб это понять представим что генератор выдает от 0 до 1 числа с шагом 0,1 (0; 0,1; 0,2 ... 0,9).
Попробуем теперь получить целые от 0 до 3, вот все возможные варианты:
0*4=0
0,1*4=0,4 = 0
0,2*4=0,8 = 0
0,3*4=1,2 = 1
0,4*4=1,6 = 1
0,5*4=2.0 = 2
0,6*4=2,4 = 2
0,7*4=2,8 = 2
0,8*4=3,2 = 3
0,9*4=3,6 = 3

И что видим: три нуля и три двойки, но две единицы и две тройки.
Конечно при большей точности вероятность очень незначительно отличается от 1/n, но, черт возьми, вероятности-то не равны.

Как доработать алгоритм чтоб он выдавал точно равновероятные значения?

Байт · 27.04.2017, 20:50

Toxa33rus, Это конечно круто! Заменить 0.8451192811534175. на 0.8, а потом голову ломать, что же здесь не так.
Хочу заметить, что 0.249 дает 0 дает при умножении на 4 - ноль, а 0.251 - единицу.

Сообщение от Toxa33rus

Почему все делают неправильно?

А вот это совершенно порочная постановка вопроса. Тут было уместнее сказать, "Почему это у меня такая фигня получается? Не кривоваты ли руки мои? Тем ли местом я думаю?"

Не говоря уже о том, что формула, вами приведенная неверна. Не думаю, что в любом учебнике и во многих кодах была приведена эта формула. Скорее всего, вы ее неправильно переписали.
А по поводу достаточной рандомности могу сказать, что она будет неплоха для b-a до порядка 10⁹. Дальше возможны огрехи, но чтобы их уловить, придется сделать довольно глубокий статистический анализ.
Правда, если функция, принимающая аргументом это случайное число, не непрерывна, стандартной рандомности не хватает. В этом случае прибегают к повторному вызову функции random. Например, первый вызов заполняет целую часть аргумента, второй - дробную. Но эти детали, имхо, к вашему вопросу не относятся.

@Toxa33rus · 27.04.2017, 21:04 **[ТС]**

Байт, покажите правильную формулу получения случайного числа от 2 до 35.

Сообщение от Байт

Заменить 0.8451192811534175. на 0.8, а потом голову ломать, что же здесь не так.

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

Байт · 27.04.2017, 21:24

Сообщение от Toxa33rus

покажите правильную формулу получения случайного числа от 2 до 5.

Я не знаю вашего языка, но скорее всего (a<= x < b)

Java
1
2
3
      int a = 2; // Начальное значение диапазона - "от"
      int b = 5; // Конечное значение диапазона - "до"
      int random_number = a + (int) (Math.random() * (b-a); // Генерация случайного числа

Сообщение от Toxa33rus

аналогия

Так это аналогия? Простите, принял за чистую монету. О большем наборе возможных значений в моем посте 2 речь идет дальше.

Добавлено через 4 минуты
А на границе возможностей, да, будут огрехи. Пытаться бороться с ними можно повторным вызовом.
И, конечно, при ОЧЕНЬ СЕРЬЕЗНЫХ исследованиях не забывать, что числа, которые выдает конечный автомат, могут быть не более чем ПСЕВДОслучайными.

@Toxa33rus · 27.04.2017, 21:30 **[ТС]**

Сообщение от Байт

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

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

Добавлено через 4 минуты

Сообщение от Байт

А на границе возможностей, да, будут огрехи.

Даже не на границе. Достаточно сгенерировать от 0 до 2 (включительно) и у нас из 10¹⁶ попыток два числа выпадут 3*333*333*333*333*333 раза, а одно 3*333*333*333*333*334.

@helter · 27.04.2017, 22:20

Что это ― (int)? У нас в математике нет такого. Используйте стандартные обозначения или поясняйте.

@Toxa33rus · 27.04.2017, 23:30 **[ТС]**

Сообщение от helter

Что это ― (int)?

Приведение к целому (отбрасываем дробную часть).

@helter · 28.04.2017, 00:37

Сообщение от Toxa33rus

Приведение к целому (отбрасываем дробную часть).

Это называется целая часть. В математике обозначается [x] или $https://www.cyberforum.ru/cgi-bin/latex.cgi?\lfloor x \rfloor$ , а в программировании часто называется floor. Есть и другие стандартные функции, преобразующие вещественные числа в целые: округление, ceiling.

Ну целая часть, так целая часть. Если случайная величина X равномерно распределена на [0, 1], то легко проверить, что a + [bX] ― дискретная случайная величина, которая с одинаковой вероятностью принимает значения a, a + 1, ..., b - 1. В качестве простого упражнения можете убедиться в этом, подсчитав вероятности. Значит, формула правильная. А ваши манипуляции с числами ― что они доказывают?

@Toxa33rus · 28.04.2017, 00:58 **[ТС]**

Сообщение от helter

Если случайная величина X равномерно распределена на [0, 1]...

Равномерно, но кол-во значений конечно, а значит не на любое кол-во равных частей мы можем разбить эту последовательность. Значит в некоторых случаях вероятности не будут равны.
Вот о чем я. А манипуляции с числами это просто упрощенное объяснение этого.

@helter · 28.04.2017, 01:24

Сообщение от Toxa33rus

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

Я говорю о математике. В математике число значений равномерно распределённой величины бесконечно. В компьютер ничего бесконечно, конечно, не влезет, но всё равно в промежутке [0, 1] чисел типа double очень много. Практически вероятность принятия одного из 10 значений может оказаться не 0.1, а, скажем, 0.100000001, а вероятность другого ― 0.099999999 (числа с потолка). Так ли это важно в типичном приложении?

@Toxa33rus · 28.04.2017, 12:22 **[ТС]**

Сообщение от helter

Так ли это важно в типичном приложении?

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

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

Предлагаю что-то типа такого:
- мы хотим получить случайные числа [0, 5] (всего 6 вариантов);
- будем считать что нулю соответствует диапазон [0, 0.1), единице - [0.1, 0.2), и т.д.;
- значит мы можем работать только с диапазоном [0, 0.6), при генерации числа вне этого диапазона производим повторную генерацию.

Если требуются двузначные числа, то использовать будем две значащие цифры и т.д.
Верно ли я понимаю что в этом случае вероятности будут абсолютно равны?

Ну а проблема такого подхода в том что если первая цифра верхней границы близка к 1, то повторных генерирований может быть много, пока не попадем в нужный диапазон. Например, если мы хотим получить [0, 12], то из [0, 1) мы сможем использовать только [0, 0.13) - всего 7,7%, что приведет к десяткам лишних генерация случайных чисел.

@helter · 28.04.2017, 17:53

Сообщение от Toxa33rus

- будем считать что нулю соответствует диапазон [0, 0.1), единице - [0.1, 0.2), и т.д.;

Не пойдёт, в двоичной записи одна десятая — периодическая дробь, компьютер её обрезает.

Вообще, в меру своего скромного разумения я думаю, что надо работать со случайными битами. Заботиться, чтобы они генерировались как можно случайнее. А все эти вещественнозначные Math.random суть обёртки, которые не годятся для суровой криптографической программы.

gnupg черпает энтропию из /dev/random, если не ошибаюсь.

@Toxa33rus · 28.04.2017, 21:01 **[ТС]**

Сообщение от helter

А все эти вещественнозначные Math.random суть обёртки, которые не годятся для суровой криптографической программы.

Увы, но это действительно так.

Сообщение от helter

gnupg черпает энтропию из /dev/random, если не ошибаюсь.

Да, либо /dev/random, либо /dev/urandom. Но опять проблема та же

У нас есть последовательность бит, т. е. мы прочитали nx2⁸ бит данных. Что дальше с ней делать? Опять приходим к ситуации что мы должны взять только часть, которую мы сможем разбить поровну. Или может я уже торможу.

Для упрощения будем считать что мы имеем шестнадцатеричную строку "3F AB 10 13 4A B7 D9 07", а хотим теперь получить случайное выпадение игральной кости [1, 6].
Один символ строки принимает 1 из 256 значений [0, 255].
Значит надо как и ранее брать диапазон [0, 252) и делить его на 6 ( [0, 42), [42, 84)... и т. д.), а если вышли из него, то брать следующий символ строки.

Может кто-то придумает как сделать так, чтоб избавиться от возможных повторных запросов символов?

Новые блоги и статьи Все статьи Все блоги /
Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .	Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .
Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .	Фото: Daniel Greenwood kumehtar 13.11.2025	Расскажи мне о Мире, бродяга kumehtar 12.11.2025 — Расскажи мне о Мире, бродяга, Ты же видел моря и метели. Как сменялись короны и стяги, Как эпохи стрелою летели. - Этот мир — это крылья и горы, Снег и пламя, любовь и тревоги, И бескрайние. . .	PowerShell Snippets iNNOKENTIY21 11.11.2025 Модуль PowerShell 5. 1+ : Snippets. psm1 У меня модуль расположен в пользовательской папке модулей, по умолчанию: \Documents\WindowsPowerShell\Modules\Snippets\ А в самом низу файла-профиля. . .

@helter 4528 / 3522 / 358 Регистрация: 12.03.2013 Сообщений: 6,038
	27.04.2017, 22:20
	Что это ― (int)? У нас в математике нет такого. Используйте стандартные обозначения или поясняйте. 0