Генератор псевдослучайных чисел с зависимой вероятностью вывода нужных чисел?

Question

[StanSemenoff]

Есть задача:


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


Пример:


Массив m = [1, 3, 7, 19]. Мы вызываем нашу функцию getMyRand() передавая в нее массив (или диапазон, если нет массива). В результате получаем какие-то такие значения (номер вызова функции — возвращенное значение):


1 — 19

2 — 7

3 — 19

4 — 19

5 — 3

6 — 19

7 — 7

8 — 1

9 — 19

10 — 7

11 — 19

12 — 7

13 — 3

14 — 19

15 — 19

и т.д.


Если есть какие мысли, как подступиться к такой функции, хотелось бы услышать и пообсуждать.


Чем она может быть интересна? Например, написать бота, который будет посещать сайты и симулировать просмотры страниц близко к поведению человека.

Answer 1

[dlinyj]

Элементарно Ватсон, вам нужна функция, которая будет давать случайные числа с заданным распределением.
Например:

возвращать чаще большие значения

— это экспоненциальная, или показательная функция. Я как-то занимался данным вопросом. Вам нужно сделать обратное преобразование функции распределения и просто подставлять туда свои значения и на выходе иметь с нужным распределением.

Comments

[dlinyj]

Вот например. Экспоненциальное распределение у нас имеет функцию:



То обратная функция этого распределения будет:

rand_number=-lambda*(log(drand48()));

Где drand48() — функция нахождения случайных чисел, я брал её у товарища Eddy_Em тут eddy-em.livejournal.com/2573.html.

Результат распределения вот:

[dlinyj]

Задача, правда на несколько порядков усложнится, если вы решите использовать «нетрадиционную» функцию распределения. Там уже могучий матан будет.

[StanSemenoff]

В целом, мысль уловил, пляшем от какой-нибудь функции распределения и подбираем необходимые нам параметры, то что надо, спасибо.

[dlinyj]

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

[StanSemenoff]

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

[dlinyj]

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

Answer 2

[StanSemenoff]

Написал быстрый тестовый скрипт на PHP:

<?php
$m = [];
for ($i = 0; $i < 1000; $i++)
{
	$rnd = (int) (10 * log(rand(3, 50)));
	$m[$rnd] = isset($m[$rnd]) ? $m[$rnd] + 1 : 0;
}
ksort($m);
foreach ($m as $i => $cnt)
    echo "<div style='margin: 2px; color: #fff; padding: 3px; background: #696; width: ".($cnt * 10)."px;'>$i</div>\n";
?>

Comments

[dlinyj]

А покажите сразу два распределения: до подстановки и после. Похоже не очень чистый алгоритм генерации случайных чисел. Хотя таки да, работает :)

[dlinyj]

И количество итераций увеличите до десятков тысяч. Кстати, для выбора количества точек на распределение я использую следующую формулу (в какой-то диссертации подсмотрел)

n_rasp=(unsigned int)(0.4*pow((double)string_count,0.4));

Где string_count — это количество исходных точек.

Answer 3

[Stdit]

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

— Нам нужен генератор псч, скажем от 0 до 99 с варьируемой вероятностю выпадения чисел.
— Заводим массив из 10000 элементов. Все числа заносим в массив по 100 раз.
— Выбирая из массива число со случайным (через обычный гпсч) индексом от 0 до 9999, мы получим число от 0 до 99 с равной вероятностью.
— Для уменьшения вероятности выпадения числа нужно уменьшить количество этих чисел в массиве. Например, если число «8» будет входить в массив не 100, а 50 раз — то его вероятность выпадения будет вдвое ниже, чем остальных.
— Для увеличения вероятности выпадения числа расширяем массив и добавляем ещё таких чисел.

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

Comments

[dlinyj]

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

[StanSemenoff]

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

[Stdit]

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

Answer 4

[morincer]

Для варианта конечной дискретной последовательности (как в Вашем случае) задача решается достаточно просто вариацией метода Монте-Карло.

Допустим у нас есть массив A натуральных чисел от 0 до n (0, 1, ..., n — 1) и для каждого из этих чисел задана вероятность его генерации p(a_i) (естественно, сумма всех вероятностей равна 1). Идея метода: разделить отрезок [0;1) на n отрезков, длина каждого из которых равна вероятности появления соответствующего числа из массива А. Далее, уже стандартным генератором ПСЧ выбираем число в диапазоне [0;1) и проверяем в какой из отрезков оно попало. Соответствующий данному отрезку элемент исходного массива возвращаем в качестве результата работы нашего генератора.
Реализацию алгоритма оставим читателю в качестве домашнего задания :)

Comments

[dlinyj]

По моему выше habrahabr.ru/qa/37831/#answer_145399 уже предложили менее научно сформулированное решение. Недостаток очевиден, который я изложил тут: habrahabr.ru/qa/37831/#comment_180425 — для большой дискретности чисел, нужен громадный массив!

[morincer]

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

Answer 5

[bloodyvlad]

Мое тупое, но рабочее решение описано тут habrahabr.ru/post/194598/ — доработанную версию использовал в последнем проекте. Генерирует все по моим правилам, быстро и четко.

Answer 6

[bloodyvlad]

перенес в QA — habrahabr.ru/qa/47196/