Какую вероятностную функцию использовать
Я хочу вероятностно выбрать «n» ребер из «e »dge_in_sorted_order в векторе.
Но я хочу использовать вероятность при выборе. И я также хочу не выбирать большие края в начале.
так что все равно, что придавать больший вес меньшим краям в начале, а когда я беру края,
Я бы придавал все больше и больше веса остальным краям.
какую вероятностную функцию n и e выбрать?
while( edgesTaken < n ) {
for each edge i and edgesTaken < n
probability = pdf( edgesTaken, i)
if ( prob > THRESHOLD )
take the edge
}
Решение
Вам нужна функция квантиля для нужного вам распределения. Нарисуйте случайное число, используя стандартный генератор, чтобы получить q, равномерно распределенное в [0, 1). Затем вызовите функцию квантиля с параметром q. Полученный случайный набор будет иметь требуемое распределение.
Другие решения
Вероятность того, что первое ребро равно 1, выбирают (n-1, e-1) / выбирают (n, e).
В более общем смысле вероятность того, что первое ребро равно k, равна
[выберите (n-k, e-1) / выберите (n, e)] * 1 / k
Вам также может понадобиться вероятность того, что в 1-k есть ровно одно ребро:
[Выбрать (п-к, е-1) / выбрать (п, е)]
Отсюда я думаю, что вы можете обернуть вещи!
Постскриптум Просто для пояснения, три функции дают отношение количества способов выбора ребер, которые удовлетворяют их условию, к выбору (n, e), которое является числом способов выбора e ребер из n.