random(a,b) через random(0,1)

[VoprosT]

Читаю "Алгоритмы: Построение и анализ", задача: есть фукнция $random(0,1)$, которая возвращает $0$ или $1$ с одинаковой вероятностью = $\frac{1}{2}$. Необходимо реализовать функцию $random(a,b)$, которая возвращает целое число из отрезка $[a,b]$ только посредством вызова функции $random(0,1)$.
Придумал что-то такое(код написан на python3):

from random import randint
def myrandom(a,b):
    a1 = a
    for i in range(b-a):
        a1 += randint(0,1)
    return a1

Но уж больно средние числа она возвращает из отрезка. Подскажите, пожалуйста, в каком моменте надо пересмотреть решение? Ну, я житейски понимаю свою ошибку: прибавляя $(b-a)$ раз $random(0,1)$ к $a$, я в среднем и получу $a + \frac{b-a}{2} = \frac{a+b}{2}$, но в какую сторону лучше пойти?

[wrest]

VoprosT в сообщении #1484842 писал(а):

Подскажите, пожалуйста, в каком моменте надо пересмотреть решение? Ну, я житейски понимаю

Тут как раз житейство плохо работает. Вернее, если вы опять доведёте до абсурда и сложите очень много случайных величин ($(b-a) \gg 1$), получите ЦПТ, ибо сумма равномерно распределенных величин не рапределена равномерно

[Dmitriy40]

Вызовом random(0,1) получать по одному биту, накапливать их в дополнительной переменной $c$. Вызывать столько раз, чтобы позиция старшего бита была больше $b-a$ (лучше во много раз больше). После накопления вычислить $f()=a + c (b-a)/2^n$ (приведение числа $c$ к диапазону $[a,b]$). Аккуратно проверить возможное равенство левой и правой границе диапазона, может там где-то придётся сделать $\pm 1$ числу перед делением. Как-то так.

Другим вариантом того же алгоритма будет представить число $c$ как дробь (собственно $c/2^n$ выше это и делает) и накапливать биты дробной части, столько чтобы при умножении $f()=a+c(b-a)$ младший значащий бит оставался ещё в дробной части. И тоже проверить достижение правой границы.

[arseniiv]

VoprosT в сообщении #1484842 писал(а):

Но уж больно средние числа она возвращает из отрезка.

О, вы переоткрыли биномиальное распределение.

А вот алгоритм, точно дающий равномерное распределение: накапливаем биты, пока не накопится альтернатив не меньше чем нам надо, после чего выдаём результат, если он среди первых $|a..b| = b - a + 1$ альтернатив, а если нет, вычитаем $|a..b|$ альтернатив и продолжаем удваивать их число, пока опять их не станет достаточно, и т. д. пока нам наконец не повезёт. После этого мы можем сохранить оставшиеся альтернативы, чтобы сэкономить энтропию, выданную нам генератором, а можем и не экономить и начать с одной альтернативы. Алгоритм придумал не я, но я его жутко люблю.

Пример, потому что лень было сделать описание вменяемым: допустим, нам надо сгенерировать 0..4. Будем считать удачными лексикографически первые альтернативы из полного списка возможных. Пошли генерировать:

ε: одна альтернатива, мало.
ε —1→ 1: две 0, 1, мало.
1 —0→ 10: четыре 00, 01, 10, 11, мало.
10 —1→ 101: восемь 000..111 — но получившееся у нас 101 не попадает в 000..100. Эти пять альтернатив сгорают. Теперь у нас три альтернативы 101, 110, 111.
101 —1→ 1011: шесть 1010, 1011, 1100, 1101, 1110, 1111, мы попали наконец в первые пять, так что выдаём 1 (1010 соответствует 0, …, 1110 соответствует 4).

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

Оно конечно кодируется много проще, чем описано тут. Неподходящие альтернативы всегда соответствуют какому-то концу списка двоичных строк, упорядоченных лексикографически, так что мы можем накапливать биты в целом числе и потом когда полное количество альтернатив выходит больше $|a..b|$, если в числе меньше $|a..b|$, выдавать его (плюс $a$), а если больше, вычитать из него $|a..b|$ так же как и из количества альтернатив и продолжать попытки.

-- Вс сен 27, 2020 03:00:29 --

Другое описание от Null: https://dxdy.ru/post947484.html#p947484.

-- Вс сен 27, 2020 03:03:21 --

Dmitriy40 в сообщении #1484846 писал(а):

Другим вариантом того же алгоритма будет представить число $c$ как дробь (собственно $c/2^n$ выше это и делает) и накапливать биты дробной части, столько чтобы при умножении $f()=a+c(b-a)$ младший значащий бит оставался ещё в дробной части. И тоже проверить достижение правой границы.

А, ну это же вроде то же самое? Но зато в формулировке выше не надо проверять границы.

[VoprosT]

arseniiv в сообщении #1484868 писал(а):

VoprosT в сообщении #1484842 писал(а):

Но уж больно средние числа она возвращает из отрезка.

О, вы переоткрыли биномиальное распределение.

Ура!

Так, похоже звёздочка у задачи была неспроста, пока не дорос до таких рассуждений, вернусь к этому чуть позже, Dmitriy40 и arseniiv, спасибо!

[arseniiv]

VoprosT
Ну в общем вы сами можете переоткрыть похожий алгоритм — тут в моём случае применяется простой принцип, который часто применяется в симуляции различных вероятностных распределений — генерация с отбраковкой. Например как сгенерировать точку, распределённую равномерно внутри круга? Не самый плохой алгоритм — сгенерировать равномерно распределённую внутри квадрата точку (а это просто пара координат, распределённых равномерно на отрезке и независимых друг от друга, что обычно у нас есть из коробки, хотя и не в текущей теме) и если она лежит в круге (что легко проверяется: $x^2 + y^2 < 1$?), то мы в шляпе, а если не лежит, то вздохнуть и генерировать её ещё раз, пока не станет лежать. Будет отбраковываться $1-\pi/4\approx 21\%$ случаев, что довольно плохо, и потому обычно генерируют не так, но во многих случаях такой принцип применяется.

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

[B@R5uk]

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

[arseniiv]

Ага, отбраковка без всякой экономии энтропии! Зато быстренько.

[B@R5uk]

Ну, если делать всё красиво, то должно получиться что-то такое:

Используется синтаксис Java

import java.util.*;

public class RandomN_from_Random2 {
        
        private static final Random rand = new Random ();
        
        private static final int num = 50000000;
        private static final int limit = 5;
        private static final int [] stat = new int [limit];
        private static int bitsCount = 0; 
        
        public static void main (String [] args) {
                int k;
                for (k = 0; num > k; ++k) {
                        ++stat [getRandomN (limit)];
                }
                for (k = 0; limit > k; ++k) {
                        System .out .println (k + ": " + stat [k]);
                }
                System .out .println ("Bits count: " + bitsCount);
        }
        
        private static int getRandomN (int limit) {
                int capValue, result;
                capValue = 1;
                result = 0;
                while (true) {
                        capValue <<= 1;
                        result <<= 1;
                        result += getRandom2 ();
                        if (limit <= capValue) {
                                if (limit > result) {
                                        return result;
                                } else {
                                        capValue -= limit;
                                        result -= limit;
                                }
                        }
                }
        }
        
        private static int getRandom2 () {
                ++bitsCount;
                return rand .nextInt (2);
        }
}
 

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

Используется синтаксис Text

0: 9999966
1: 10000088
2: 10004420
3: 9998599
4: 9996927
Bits count: 179999789

0: 9998921
1: 10002279
2: 9999109
3: 10002665
4: 9997026
Bits count: 180009061

0: 10002430
1: 9999696
2: 9993854
3: 9998651
4: 10005369
Bits count: 179990661
 

В пределах погрешности распределение выглядит равномерным.

[bondkim137]

arseniiv в сообщении #1490604 писал(а):

отбраковка без всякой экономии энтропии

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

[arseniiv]

bondkim137 в сообщении #1507770 писал(а):

А когда бывает целесобразно ее экономить?

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