Какие есть алгоритмы для выдачи результата из заданого списка с определенной вероятностью?

Question

[vitvad]

Задача:
Есть исходный набор данных в виде массива. Для каждого элемента массива указана вероятность его появления в результате.
Нужно написать функцию которая каждый раз при вызове будет возвращать один случайный элемент из массива с заданой вероятностью.

примеры применения:
- AB тестирование - есть 3 страницы которые должны показываться пользователям при заходе на сайт с вероятность 50%, 35% и 15% соответственно
- Словарь который будет показывать одно из слов содержащихся в памяти каждые 3 минуты. При этом новые слова будут показываться чаще чем старые.

Мне в голову приходит только решение в "лоб". УПРОЩЕННЫЙ вариант ниже (JavaScript):

function probabilityRandom(chanceA, chanceB, chanceC, items) {
	var totalWeight = chanceA + chanceB + chanceC;
	// generate random number in range from 1 to `totalWeight`
	var tmp = 1 + (Math.random() * totalWeight);

	if(0 < tmp && tmp <= chanceA){
		return items[0];
	}
	if(chanceA < tmp && tmp <= chanceA + chanceB){
		return items[0];
	}

	if(chanceA + chanceB < tmp && tmp <= chanceA + chanceB + chanceC){
		return items[0];
	}
}

probabilityRandom(50, 35, 15, ["first", "second", "third"]);

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

PS.

Comments

[vitvad]

для тех кому интересна теория:
en.wikipedia.org/wiki/Alias_method
www.jstatsoft.org/v11/i03

реализация:
python: code.activestate.com/recipes/576564-walkers-alias-...
ruby: https://github.com/cantino/walker_method
js: https://github.com/ThoughtLeadr/Walker-Random-Node

в остальных ответах так же интересные вещи

Answer 1

[B@rmaley.e><e]

Метод Уолкера (см. тут, снизу). Хорош тем, что после линейного предподсчёта можно отвечать на запрос за O(1).

Answer 2

[bobrovskyserg]

Самая сложная математика:
на оси x откладываете отрезки:
[0.0 .. 0.2) - Вася
[0.2 .. 0.5) - Петя
[0.5 .. 1.0) - Кузя
Генерите random в диапазоне 0 .. 1
На чей отрезок выпало - тому и водить.
Код на Питоне:

from random import random
from bisect import bisect_left

data = {"Вася": 2,
        "Петя": 3,
        "Кузя": 5}

scalefactor = sum(data.values())
names, scale = [], [0.]
for name, weight in data.items():
    names.append(name)
    scale.append(scale[-1] + weight / scalefactor)

#  посмотрим, хорошо ли работает
counter = {name: 0 for name in names}

for i in range(10000):
    x = random()
    idx = bisect_left(scale, x) - 1
    name = names[idx]
    counter[name] += 1
print(counter)

Comments

[DISaccount]

Опередили.

[vitvad]

DISaccount , bobrovskyserg в целом весь алгоритм ваших решений сводится к моему решению указаному в описании, если я правильно все понял

[bobrovskyserg]

vitvad:
Если нет каких-то специальных библиотек, делающих то же самое, но быстрее (написанных на С) - это - один из разумных выходов.
Причешите своё решение (у вас код зависит от числа вариантов) - и будет щастье.

[vitvad]

bobrovskyserg: как я описал выше - это был упрощенный вариант что бы показать мою идею. Спасибо за код на Python - потренировался :)

Answer 3

[Adamos]

Самая простая математика: генерите ДВА случайных числа.
Одно - индекс элемента в массиве.
Второе - от 0 до 1, сравниваете со значением вероятности для этого элемента, заданным в том же виде.
Если сгенерированное больше заданного - повторяете алгоритм.

Comments

[vitvad]

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

[Adamos]

Это решается тоже просто: вводим в неравенство множитель, увеличивающийся на каждой итерации...

[SeptiM]

В целом можно сразу ускорить, поделив все вероятности на p_max. Равномерное распределение будет сэмплиться за O(1). Беда, если есть один тяжелый элемент под 0.999 и много легких по eps. Такое будет сэмплиться за O(n).

[Adamos]

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

Answer 4

[Константин Китманов]

Probability and Games, есть псевдокод
github://jotson/LootTable.js, имплементация на JS.

Comments

[vitvad]

спасибо, понравился LootTable.js, алгоритм тоже описаного мной, но убрали лишнее сравнение.

Answer 5

[DISaccount]

Элементарно, Ватсон.
С Вашего позволения, я переформулирую задачу.
У Вас имеется гистограмма (частоты появления) элементов. Вам необходимо, чтобы на тысячу экспериментов, у Вас частота появления заданного элемента, приближалась к некой заданной частоте из гистограммы. Тогда, берете произвольный промежуток, скажем от 1 до 1000, и делите его в пропорциях, согласно Вашей гистограмме. Например. У Вас 2 элемента: один появляется с частотой 2/3, второй с частотой 1/3. Тогда делим промежуток от 1-1000 на 2 куска, один от 1 до ~300, второй от ~301 до 1000. В зависимости от того, на какой участок попала случайно сгенерированная величина, тот элемент и берете.