Генерация отсортировала случайный ints без вида? O (n)

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

Если вы возьмете диапазон чисел от 1 до 1000, и вам нужно будет использовать 100 из этих чисел, дельта должна быть как минимум 10, иначе вы не сможете достичь 1000 отметка. Как насчет того, чтобы поработать, чтобы продемонстрировать это в действии ...

Вероятность любого заданного числа в равномерно распределенной случайной выборке составляет 100/1000, например, 1/10 - никакого шока, возьмите это за основу.

Предполагая, вы начинаете использовать дельту, и эта дельта равна всего 10.

Шансы получить число 1 составляют 1/10 - кажется, нормально. Шансы на получение числа 2 составляют 1/10 + (1/10 * 1/10) (потому что вы можете получить 2 дельты из 1 подряд или просто получить 2 в качестве первой дельты). Шансы на получение числа 3 равны 1/10 + (1/10 * 1/10 * 1/10) + (1/10 * 1/10) + (1/10 * 1/10)

Первый случай - дельта 3, второй - 3 дельты из 1 подряд, третий случай - дельта 1, за которой следует 2, а четвертый случай - дельта 2, за которой следует 1.

Ради того, чтобы я мог печатать пальцами, мы не будем генерировать комбинации, которые достигают 5.

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

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

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

Я думаю, что это будет очень похоже, но крайности будут другими из-за нормализации. Например, 100 чисел, выбранных случайным образом от 1 до 100, могут быть 1. Однако все 100 чисел, созданных с использованием вашей системы, могут иметь дельты 0,01, но когда вы их нормализуете, вы увеличите их до диапазона 1 -> 100, что будет означать, что у вас никогда не будет такой странной возможности набора очень низких чисел.

Ответ Алока и комментарий Дэна Дайера указывают на то, что использование ] экспоненциальное распределение для дельт даст равномерное распределение целых чисел.

Итак, новая версия образца кода в вопросе будет:

import random,sys
running = 0
max = 1000
deltas = [random.expovariate(1.0) for i in range(0,11)]
floats = []
for d in deltas:
    running += d
    floats.append(running)
upper = floats.pop()
ints = [int(round(f/upper*max)) for f in floats]
print(ints)

Обратите внимание на использование random.expovariate (1.0) , Python-генератор случайных чисел с экспоненциальным распределением (очень полезно!). Здесь оно вызывается со средним значением 1,0, но поскольку сценарий нормализует последнее число в последовательности, само среднее значение не имеет значения.

Вывод (справедливый бросок кубиков):

[11, 43, 148, 212, 249, 458, 539, 725, 779, 871]

Q: Будет ли результирующее распределение целых чисел таким же, как генерация 100 случайных целых чисел из равномерно распределенной функции плотности вероятности?

A: Каждая дельта будет равномерно распределена. Центральная предельная теорема говорит нам, что распределение суммы большого числа таких отклонений (поскольку они имеют конечное среднее значение и дисперсию) будет стремиться к нормальному распределению. Следовательно, более поздние отклонения в вашей последовательности не будут распределены равномерно.

Таким образом, краткий ответ - «нет». Боюсь, что я не могу дать простое решение , не занимаясь алгеброй. У меня сегодня нет времени на это!

Вы можете сделать это за два прохода;

на первом проходе, сгенерировать дельты между 0 и (MAX_RAND / n)

на втором проходе, нормализовать случайные числа, чтобы они были в пределах

По-прежнему O (n), с хорошим местоположением ссылки.

Ссылка (1979) в ответ Алока интересна. Он дает алгоритм для генерации статистики равномерного порядка не сложением, а последовательным умножением:

max = 1.
for i = N downto 1 do
   out[i] = max = max * RAND^(1/i)

где RAND равномерно на [0,1). Таким образом, вам не нужно выполнять нормализацию в конце и даже не хранить числа в массиве; вы можете использовать это как итератор.

Экспоненциальное распределение: теория, методы и приложения Автор Н. Балакришнан, Асит П. Басу дает другой вывод этого алгоритма на стр. 22 и цитирует Мальмквиста (1950).