Генерация экспоненциального распределения размеров ковша

Question

Учитывая серию поступающих предметов, я хочу назначить каждый из них на ведро по мере его поступления. Ведро может быть либо новым (тем, которое никогда ранее не использовалось, которого имеется бесконечное количество) или это может быть существующее ведро. Если я посмотрю на количество сегментов с одним элементом, число с двумя, число с тремя и т. Д., Я хочу, чтобы эти количества сегментов следовали экспоненциальному распределению. Надеюсь, я правильно говорю - если 80% корзин имеют 1 предмет, то 16% должны иметь две, 3,2% должны иметь три, и т. Д. В общем, количество ведер размера k должно быть 1 / p. столько, сколько количество ведер размера k-1 и доля ведер размера 1 должно быть (1-p), чтобы математика работала правильно.

Если бы я знал количество предметов заранее, это было бы легко: я бы знал, сколько ведер каждого размера, поэтому я мог бы просто складывать предметы в столько ведер каждого размера, сколько мне было нужно. Или, если бы я просто генерировал размеры сегментов, было бы легко, даже если бы я заранее не знал сумму: каждый новый сегмент имеет вероятность (1-p) размера 1, (1-p) p размера 2, (1-р) р ^ 2, размер 3, (1-р) р ^ 3, размер 4 и т. Д.

Но я обрабатываю предметов , поэтому, когда я получаю предмет, мне нужно выбрать корзину: либо существующую, либо новую. Если я сделаю новое ведро, то получу еще одно размером 1. Но если я выберу существующее размером k, то получу еще одно ведро размера k + 1 и на одно меньше размера. к. Так, какова должна быть вероятность выбора сегмента размером k (где k может быть нулем, чтобы указать создание нового сегмента)? И как это связано с р?

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

А может и так, но я просто что-то упускаю. (И я не могу понять, как Google это тоже.)

Answer 1

Экспоненциальное распределение имеет поддержку на всех положительных реалах; ваше распределение поддерживает положительные целые числа (это дискретное распределение вероятностей), и оно называется геометрическим распределением . ^{( W )} [Вероятности обычно записываются в виде параметра, который равен 1 & минус; (ваш p), но это тривиальная деталь.]

На самом деле, ваш выбор геометрического распределения является хорошим, если вы знаете только среднее значение:

Среди всех дискретных распределений вероятностей, поддерживаемых в {1, 2, 3, ...} с заданным ожидаемым значением μ, геометрическое распределение X с параметром p = 1 / μ - это распределение с наибольшей энтропией.

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

While there are items left:
    Pick a "bucket size" k according to the desired distribution
    /* E.g., for the geometric distribution with mean 1.5, 
       you could toss a coin with bias 0.667 until you get a head,
       then you'll get k=1 for 66.7% of the time, k=2 for 22.2%, k=3 for 7.4% etc., 
       with k being 1.5 on average (in expectation) */
    Put the next k items into one (new) bucket.

Обратите внимание, что вам не нужно знать количество предметов. Если предположить, что число достаточно велико, проблемы (такие как дисперсия в распределениях и «остатки» в конце) не будут иметь большого значения.

Answer 2

Вот мои два цента: когда вы читаете предметы, ведите счетчик как ведер, так и предметов, и используйте его для вычисления количества предметов в ведре. Если порог предметов / корзин превышает 1,5, вы помещаете следующий предмет в новую корзину. Если нет, вы назначаете следующий элемент в случайно выбранный существующий сегмент.

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

Answer 3

Вот как бы я это сделал.

Для каждого входящего элемента нарисуйте число из равномерного распределения по (0,1). Это ваш CDF для геометрического распределения , который, как заметил выше комментатор, то, что вы ищете. Тогда вам нужен контейнер ln ((1-CDF) / (1-p)). Предположим, что вы только что поместили элементы в группы 1 и 2, а затем вы получите элемент, предназначенный для группы 5, нет проблем, просто используйте хеш-таблицу для отслеживания заполненных вами групп.