Могу ли я добиться взвешенной случайности с помощью функции, возвращающей взвешенные логические значения?

Question

У меня есть метод, имитирующий несправедливую монету. Вы можете передать процентное значение, и оно сообщит вам, преуспели вы или нет, вернув логическое значение. Поэтому, если вы вызовете его с 0,25, он вернет true 25% времени.

Я пытаюсь выяснить, могу ли я использовать эту функцию для создания функции взвешенной случайности, которая работает как это: There is a 25% chance it returns x, a 40% chance it returns y, and a 35% chance it returns z. Это всего лишь пример. Я бы хотел, чтобы эта функция работала для неограниченного количества букв, но сложенные проценты должны равняться 1.

Хитрость в том, что я хочу думать об этом так, как я только что описал выше. Другими словами:

result = function ({.25, x}, {.4, y}, {.35, z})

result должно быть x 25% времени и так далее. Могу ли я реализовать эту функцию с помощью моей валюты?

Вот как я сформулировал это в комментарии ниже. Это может прояснить, о чем я прошу:

Исправьте мой logi c, если я здесь ошибаюсь, но скажем XY и Z у всех было .3333 ... Могу ли я использовать свою несправедливую монету, чтобы передать .3333 ... Если это вернет истину, это означает, что вы получите X в результате. Если он возвращает false, снова назовите меня несправедливым с .5, если это вернет истину, верните Y, в противном случае верните Z. Если это правильно, я не знаю, как заставить это работать, если числа НЕ .3333 и если есть более трех

Answer 1

Если у вас есть монеты с известной вероятностью выпадения орла

Предположим, у вас есть функция unfairCoin(p), которая производит выпадение орлов с известным вероятность p и решка в противном случае. Например, это может быть реализовано следующим образом:

function unfairCoin(p) {
   return Math.random() < p ? true : false;
}

Вот алгоритм, который решает вашу проблему с учетом unfairCoin, предполагая, что сумма всех задействованных вероятностей равна 1:

1. Установите cumu на 1.
2. Для каждого элемента, начиная с первого:
   1. Получите вероятность, связанную с выбранным элементом (назовите его p), и примите элемент с вероятностью p / cumu (например, через unfairCoin(p / cumu)). Если предмет принят, верните его.
   2. Если предмет не был принят, вычтите p из cumu.

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

РЕДАКТИРОВАТЬ (30 июля): Как я только что узнал, именно это Алгоритм уже был описан Китом Шварцем в Darts, Dice, and Coins , в «Моделирование загруженного D ie с помощью смещенной монеты». Эта страница также содержит доказательство его правильности.

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

1. Генерация однородного случайного целочисленного индекса в интервале [0, n), где n - количество предметов. Это можно сделать, например, с помощью Fast Dice Roller от J. Lumbroso, который использует только честные подбрасывания монет (unfairCoin(0.5)). Выберите элемент с заданным индексом (начиная с 0).
2. Получите вероятность, связанную с выбранным элементом (назовите его p) и примите его с вероятностью p (например, через unfairCoin(p)) . Если товар принят, верните его; в противном случае go к шагу 1.

Ожидаемая временная сложность этого алгоритма зависит от разницы между самой низкой и самой высокой вероятностью.

Если у вас есть монеты с unknown вероятность выпадения орла

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

1. Как превратить смещенную монету в честную.
2. Как превратить честную монету в заряженную д ie.

Другими словами, задача превратить смещенную монету в загруженную d ie.

Посмотрим, как можно решить эти две проблемы.

От смещенной к справедливой монеты

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

Здесь мы можем использовать алгоритм фон Неймана 1951 г. предвзятая монета в честную монету. Это работает следующим образом:

1. Отразить COIN() дважды.
2. Если оба результата - орел или оба - решка, go перейти к шагу 1.
3. Если первый результат - решка, а другой - решка, в качестве окончательного результата принимайте решку.
4. Если первый результат - решка, а другой - решка, в качестве окончательного результата принимайте решку.

Теперь у нас есть честная монета FAIRCOIN().

(Обратите внимание, что есть и другие способы производства честных монет таким способом, совокупно называемые экстракторами случайности , но, возможно, метод фон Неймана самый простой.)

От честных монет до загруженных игральных костей

Теперь способ превратить честные монеты в загруженные кости намного сложнее. Достаточно сказать, что есть много способов решить эту проблему, и самый новый из них называется Fast Loaded Dice Roller , который производит загруженный d ie с использованием справедливой монет (фактически, он использует в среднем до 6 подбрасываний честных монет больше, чем оптимальное количество для получения каждого загруженного рулона d ie). Алгоритм не совсем прост в реализации, но посмотрите мою Python реализацию и реализацию от авторов Fast Loaded Dice Roller .

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

Answer 2

Взгляните на это:

function weightedRandom(array) {
  // expected array: [[percent, var], [percent, var], ...] where sum of percents is 1
  var random=Math.random();
  var sofar=0;
  var index=-1;
  for(var i=0; i<array.length; i++) {
    if(sofar<random) index=i;
    sofar+=array[i][0];
  };
  return array[index][1];
}