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

alex_past · №1

Извините, если это оффтоп. У меня вопрос не столько по конкретному коду, сколько по алгоритму.
Не могу целый день допереть, как это можно сделать просто и эффективно.
Помогите, пожалуйста, кто сталкивался.

Задача такая: есть массив из n элементов. Мне нужно из него выбрать случайный элемент. Но не с равной вероятностью. Например, чтобы чем ближе к хвосту массива, тем реже (или чаще, неважно) элемент выбирался. Скажем, чтобы последние элементы выбирались в k раз чаще первых. Распределение вероятностей между этими двумя точками (первым и последним эл-тами) может быть любым (в идеале - линейным, т.е., чтобы вероятность выбора конкретного эл-та росла линейно от его индекса), погрешности k тоже допустимы... лишь бы алгоритм был шустрым, чтобы всё можно было сделать на интерпретируемом языке вроде JavaScript.

Отредактировано alex_past (19-03-2009 05:48:17)

ПротопопулуS · №2

i = n * Math.round(1/Math.random()); //i - индекс элемента массива.
Гарантирует гиперболическую зависимость между распределением вероятности.
Элементы с большим номером будут выбираться чаще. Математика 8-го класса блин! :lol:
Чтобы избежать исключения, надо в дроби к random() добавить хоть чуть-чуть, т.е. 1/(Math.random()+0.0000001) :cool:

Отредактировано ПротопопулуS (19-03-2009 06:00:56)

alex_past · №3

Спасибо огромное!
Я тоже сразу об этом подумал Но сижу третьи сутки в глубокой отладке, башка не варит совершенно, так что никак не могу сообразить: как мне при этом получить требуемое k (отношение вероятностей выбора первого и последнего эл-тов задано и должно быть фиксировано независимо от числа элементов, которое может меняться)

Отредактировано alex_past (19-03-2009 06:01:50)

Forest · №4

ПротопопулуS
Только наверное округлять надо не так, а i = Math.round(n/Math.random());

ПротопопулуS · №5

Forest, а верное однако замечание!!! :cool:

alex_past · №6

Спасибо вам обоим.
Принцип понятен. Но так я получаю отношение вероятностей выбора первого и последнего эл-тов, зависящее от размера массива. А мне нужно, чтобы оно было фиксированным. Этот параметр задаётся извне - самим условием задачи

ПротопопулуS · №7

Но так я получаю отношение вероятностей выбора первого и последнего эл-тов, зависящее от размера массива.

Тут от числа n зависит только номер индекса элемента, а не распределение вероятности,
т.е. чем больше элементов в массиве, тем соответственно больше индекс.

alex_past · №8

Увы, нет
Такая штука, конечно, не сработает:

Выделить код

Код:

i = Math.round(n/Math.random());

- она ведь будет давать индексы i не от 0 до n, а от n до бесконечности. А вот если попробовать её переписать правильно (нормировать как угодно), то сразу будет видно, что отношение вероятностей выбора первого эл-та к последнему задать не выйдет.

ПротопопулуS · №9

В таком случае можно попробовать:

i = Math.round( n * x^2) или i = Math.round( n * x^(1/2)), где x = Math.random();

Вроде должно сработать. В первом случае чаще будут выбираться первые элементы массива.
Надо ещё добавить, что чем выше степень, тем больше разница между вероятностями.

Отредактировано ПротопопулуS (19-03-2009 11:29:17)

alex_past · №10

Вот оно, спасибище!
Я Ваш погробжизненный должник
Вот так примерно оно должно выглядеть:

Выделить код

Код:

i=Math.round(Math.random()*Math.random()*n);

Или как у Вас - просто один рандом взять и его в какую-то степень возвести, не обязательно в квадрат.
Теперь осталось понять, как это дело нормировать. Чтобы вышло что-то вроде функции, куда можно передать n и k и получить случайное i.
Отосплюсь - соображу

Отредактировано alex_past (19-03-2009 12:02:09)

Forest · №11

Но это всё конечно подгонки
И по-хорошему надо злобно ботать тервер на эту тему (хотя мб это можно и найти)

Но можно попробовать сделать так (но не то, чтобы это совсем просто):
Дано:
1. Равномерное распределение на [0.,1.) (Math.random());
2. Интервал получения нужной случайной величины [a,b];
3. Распределение этой случайной величины в виде массива F(a:b), где в каждом элементе содержится вероятность получения этого значения (и сумма по всем должна быть == 1.).
Подготовка:
4. По F сделаем правильную функцию распределения P: уже на [a,b-1] (так как (P(b)==1.) - не принципиально - вопрос построения поиска), но в i-ом элементе содержится вероятность всех значение <= i.
Замечание:
5. Равномерное распределение на [a,b] получается как a+Math.round((b-a+1)*Math.random()).
Решение:
а) Получаем r=Math.random();
б) Ищем r в P (бинарным поиском должно быть очень быстро);
в) Найденный индекс и будет нашей случайной величиной.

Вроде нигде не ошибся

Отредактировано Forest (20-03-2009 09:31:44)

alex_past · №12

Спасибо большое!
А я отоспался и за час всё сделал
Чтобы закрыть тему - соберу все советы в кучу: авось, кому-то ещё пригодится.
Итак, мне надо было получить линейно нарастающее распределение вероятностей выбора элементов:

Отличный совет дал ПротопопулуS для нелинейных распределений, причем степенью (a) можно регулировать изгиб. На псевдокоде:

Выделить код

Код:

i=round((random()^a)*n);

Совет для произвольных распределений Forest еще лучше:

Аппроксимируем распределение такой ступенчатой функцией. Заводим массив размером M, хранящий значения "ступенек" (в сумме - единицу), а еще лучше - нарастающую сумму с нулевого эл-та и по текущий. Чем больше погрешность допустима, тем меньше можно сделать массив.
Кидаем кости - получаем рандомное число от 0 до 1, циклом по массиву (или бинарным поиском) находим индекс эл-та, хранящего эту нарастающую сумму.
Но число наших исходных эл-тов (из которых в результате нам и надо выбрать случайный) равно N. То есть, каждый эл-т массива вероятностей представляет N/M эл-тов исходного набора. Поэтому, получив индекс, кидаем кости ещё раз, и полученное число в диапазоне 0...1 добавляем к индексу. Потом остается только умножить на N/M и округлить, и получаем индекс эл-та исходного набора.

Но мне нужен был частный случай - линейно нарастающая вероятность. И этот случай можно реализовать гораздо проще.
Гляньте на верхнюю картинку. По х там индексы, по y - нормированная вероятность (т.е., последний эл-т выпадает в K раз чаще первого)
Кидая кости, получаем случайное число. Просто будем считать, что случайное число соответствует отношению площадей, а не индексу напрямую, вот и всё
Нам нужно кинуть кости, получить число R в диапазоне 0...1, а потом найти, для какого индекса отношение площади фигуры - ограниченной осями, красной линией и вертикалью от этого индекса - к площади всей фигуры (т.е., ограниченной вертикалью от максимального индекса) равно R. Наша программа всего лишь должна уметь решать простейшее квадратное уравнение

Отредактировано alex_past (20-03-2009 11:02:11)

Forest · №13

alex_past

Чем больше погрешность допустима, тем меньше можно сделать массив.

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

Аппроксимируем распределение такой ступенчатой функцией.

Но в случае линейной функции это всё не нужно - достаточно взять значения функции в середине ячеек (собственно это будет метод прямоугольников для интегрирования) и пронормировать.

Наша программа всего лишь должна уметь решать простейшее квадратное уравнение

Минус такого подхода - он работает только для такой прямой - изменение угла потребует переделки программы.
И при этом ещё неизвестно, какая реализация проще и быстрее.
Но для учебного примера наверное правильнее реализовывать то, что придумал сам

alex_past · №14

Forest пишет

alex_past
Чем больше погрешность допустима, тем меньше можно сделать массив.
При чём тут это? Ведь диапазон целых у нас ограничен, так что регулировать точность таким образом нельзя

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

Аппроксимируем распределение такой ступенчатой функцией.
Но в случае линейной функции это всё не нужно - достаточно взять значения функции в середине ячеек (собственно это будет метод прямоугольников для интегрирования) и пронормировать.

Мы говорим об одном и том же Значения в серединах ячеек - они и хранятся в "аппроксимирующем" массиве Действительно, это метод прямоугольников.

Наша программа всего лишь должна уметь решать простейшее квадратное уравнение
Минус такого подхода - он работает только для такой прямой - изменение угла потребует переделки программы.
И при этом ещё неизвестно, какая реализация проще и быстрее.
Но для учебного примера наверное правильнее реализовывать то, что придумал сам

Согласен. Но есть для меня принципиальный плюс в таком решении: оно будет куда меньше грузить сервер. Дело в том, что пример это не учебный, но и не слишком серьёзный. Мне понадобилось для сайта (на PHP) сделать что-то вроде локальной баннерокрутилки, которая будет показывать в подвале страницы несколько случайных авторских статей. И при этом нужно, чтобы, чем выше оценка статьи, тем чаще она крутилась. Вот, собственно, и всё
Сами понимаете, что особая точность мне не нужна, просто сначала до того отупел, сидя в отладке, что сходу не сообразил, как это на коленке сделать, а потом заинтересовала сама задачка

Спасибо и Вам, и ПротопопулуS, вы мне в самом деле здорово помогли. Тем более, что я уже вижу, куда не помешает присобачить более серьезный вариант - вроде предложенного вами.

Отредактировано alex_past (22-03-2009 10:00:14)

Полезная информация

№119-03-2009 05:41:27