Самый быстрый способ сгенерировать число с геометрическим распределением - PullRequest
Новая
       45

Самый быстрый способ сгенерировать число с геометрическим распределением

0 голосов
/ 19 сентября 2019

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

0: p = 0.5
1: p = 0.25
2: p = 0.125
...

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

1 Ответ

1 голос
/ 20 сентября 2019

Это нормальное распределение затухания распадаемости.

Проблема, с которой вы сталкиваетесь, заключается не в том, чтобы определить, что это правильное распределение, а в том, чтобы создать генератор случайных чисел, обладающий этим свойством.Обычно вы работаете, взяв за основу другой генератор случайных чисел, и пытаетесь применить функцию, которая из этого генератора известных свойств вы получите числа, распределенные по-новому.

Для вашего подхода я несколько раз использовалстандартный генератор случайных чисел (генератор плоских чисел между [0..1), в качестве источника), если я применю к нему функцию, скажем (просто предположение) функции log(x), вы получите график примерно так: 

|->    x
|->      x
|->         x
|->              x
|->                         x
|->                                                            x
+====================================================================

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

Интеграл в эту функцию (которая дает вам вероятностьналичие X <= a) задается функцией, представленной ниже: </p> 

|->                                                            X
|->                         X
|->              x
|->         X     
|->      X                   
|->    X                                                        
+====================================================================
       0

, и она обратная (логарифмированная функция приведена ниже, зеркально отраженная на биссектрисе XY): 

|          |
|    X     |
|          |
|  X       |
|X         |
+=============
 0         1

который равен -log(1-x) (но -log(x) будет достаточно, поскольку x является случайным числом от 0 до 1). 

double y = -A * log(unit_random());

, в котором A является некоторой константой, специфичной для получения большего или меньшего среднегоGE.y будет иметь ожидаемый ответ, всегда unit_random() - это плоское распределение с равным распределением вероятностей в единичном интервале.

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

#include <math.h>
#include <limits.h>
#include <stdlib.h>
#include <stdio.h>

#include "gr.h"

double
geometric_random(void)
{
        double n = random();

        return -log(fabs(n) / INT_MAX);
} /* geometric_random */

производит желаемые случайные значения со средним значением 1.0.Чтобы получить среднее значение M, просто умножьте возвращаемые им значения на M.

A полный пример опубликован в github, с программой тестирования montecarlo для тестирования на распространениесвойства.Чтобы выполнить его, запустите: 

$ make
$ gr -n 10000000 | mc -n 100 -b 20 >mc.out

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

Вывод: 

                   n: 10000000
               sum_x: 10007209.0488715283572674
              sum_x2: 20023758.8835431151092052
               avg_x: 1.0007209048871528
              sdev_x: 1.0004667205707121
               min_x: 0.0000002696179218
               max_x: 17.2248827198513297
             below_A:      0
[0.0000000000000000, 0.2000000000000000]1811635
[0.2000000000000000, 0.4000000000000000]1484598: 0.8194796413184775
[0.4000000000000000, 0.6000000000000001]1213219: 0.8172037144061894
[0.6000000000000001, 0.8000000000000000]994937: 0.8200802987754066
[0.8000000000000000, 1.0000000000000000]813669: 0.8178095698521615
[1.0000000000000000, 1.2000000000000000]666035: 0.8185576690275775
[1.2000000000000000, 1.3999999999999999]545997: 0.8197722341918968
[1.3999999999999999, 1.5999999999999999]447841: 0.8202261184585263
[1.5999999999999999, 1.7999999999999998]365854: 0.8169283294740768
[1.7999999999999998, 1.9999999999999998]300525: 0.8214342333280489
[1.9999999999999998, 2.1999999999999997]246141: 0.8190366857998502
[2.1999999999999997, 2.3999999999999999]201303: 0.8178361183224250
[2.3999999999999999, 2.6000000000000001]164134: 0.8153579430013462
[2.6000000000000001, 2.8000000000000003]134768: 0.8210852108642938
[2.8000000000000003, 3.0000000000000004]110564: 0.8204024694289446
[3.0000000000000004, 3.2000000000000006] 90139: 0.8152653666654607
[3.2000000000000006, 3.4000000000000008] 74252: 0.8237499861325287
[3.4000000000000008, 3.6000000000000010] 60746: 0.8181059096051285
[3.6000000000000010, 3.8000000000000012] 49701: 0.8181773285483818
[3.8000000000000012, 4.0000000000000009] 40559: 0.8160600390334198
[4.0000000000000009, 4.2000000000000011] 33344: 0.8221109987918834
[4.2000000000000011, 4.4000000000000012] 27077: 0.8120501439539347
[4.4000000000000012, 4.6000000000000014] 22338: 0.8249806108505373
[4.6000000000000014, 4.8000000000000016] 18370: 0.8223654758707136
[4.8000000000000016, 5.0000000000000018] 15016: 0.8174197060424605
...
...