Случайный выбор, взвешенный по рангу

Question

Допустим, у меня есть коллекция n объектов, и что каждый объект имеет ранжирование, связанное с ним, и эти ранжирования соответствуют целочисленным значениям от 1 до n .

Теперь предположим, что я хочу произвольно выбрать объект из коллекции. Но я не хочу просто выбирать число от 1 до n в случайном порядке; вместо этого я хочу сделать так, чтобы я с большей вероятностью выбрал число выше в списке (с рейтингом ближе к 1).

Предлагаемое решение: Вместо выбора от 1 до n , выберите от 1 до m , где m - некоторое число, значительно больше чем n ; затем используйте некоторую функцию отображения f : [1, m ] → [1, n ], которая отображает больше чисел в более высокие ранги, чем в более низкие ранги. Например, f (1), f (2), f (3) могут все вернуть 1, тогда как f (м ) является единственным, который сопоставляется с n , поэтому вероятность получить 1 в три раза выше, чем n . Надеюсь, это имеет смысл.

Итак, мой вопрос: если это кажется разумным алгоритмом, что такое разумная функция f , которая выполняет это, и какое отношение m / n будет достаточно большим для округления не мешает никому не выбирать номера?

[В моем конкретном сценарии n может быть довольно большим (в тысячах), поэтому решения, подобные представленному здесь , не очень практичны для этой ситуации. Также выбор есть «с заменой»; т.е. я выбираю объект один раз, а затем возвращаюсь; Мне все равно, если я выберу его снова сразу в следующий раз.]

Answer 1

Вы можете сделать что-то вроде следующего:

double bias = 1.5; 
int index = (int)(n * (bias - sqrt(bias*bias -4.0*(bias-1.0)* random()))
                  / 2.0 / (bias-1));

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

Редактировать: Вот некоторый код Python для него.

def pick(n, bias):
    return int(n * (bias - sqrt(bias*bias -4.0*(bias-1.0)*random())) / 2.0 / (bias-1))

vals = [0]*10
for i in xrange(1000):
    vals[pick(10,1.5)] += 1
print vals
[153, 151, 115, 116, 97, 96, 87, 69, 66, 50]

Answer 2

Генерация K случайных чисел из интервала 1..n (K> 1) и выбор минимума!

У этого есть свойства, которые вы хотите, посмотрите демонстрацию распределений в http://www.sjsu.edu/faculty/watkins/samplemin.htm

Чтобы сделать эту работу с дробными значениями K (1

int m = random_int(1..n)
if (random_double(0..1) <= K - 1):
     m = min(m, random_int(1..n))

Таким образом, когда K приближается к 1 сверху, распределение становится все более и более плоским.

Answer 3

Я бы попробовал использовать обычный случайный подход (random.uniform(0, 1)), но возводя в квадрат вероятность.

Так как P{x} колеблется от 0 -> 1, P {x ^ 2} also ranges from 0 -> 1`.

Но вес неравномерен, так как небольшое число в квадрате все еще мало, а большее число в квадрате становится маленьким.

Просто мысль.

Answer 4

Я думаю, что вы действительно хотите, это функция f : [1, n ] → N (натуральные числа 0, 1, 2, .. .). Это назначило бы вес для каждого ранга. Затем вы хотите выбрать ранг k с вероятностью f (* k *) / (Σ f (* i *)), другими словами, этот ранг вес над суммой весов всех рангов. Чтобы сделать это, вы можете просто выбрать случайное целое число равномерно в течение интервала [1, Σ f (* i *)] и выяснить, в каком вы рейтинге, основываясь на вашей позиции; если вы находитесь в 1 ... f (1), выберите 1, если вы находитесь в f (1) +1 ... f (1) ) + f (2), выбор 2 и т. Д.

Один из возможных вариантов для f , который взвешивает маленькие ранги выше больших рангов, составляет f (* i *) = n - i + 1. Есть много других возможных вариантов.

Answer 5

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