Взвешенный выборка без замены и отрицательных весов

Question

У меня есть необычная проблема выборки, которую я пытаюсь реализовать для техники Монте-Карло. Я знаю, что есть связанные вопросы и ответы относительно полностью положительной проблемы.

У меня есть список n весов w_1, ..., w_n, и мне нужно выбрать k элементов, обозначенных s_1, ..., s_k say. Распределение вероятности, которое я хочу отбирать, равно

p (s_1, ..., s_k) = | w_s_1 + ... + w_s_k |/P_total

где P_total - коэффициент нормировки (сумма всех возможных p (s, ...) без P_total). Мне все равно, как элементы упорядочены для моей цели.

Обратите внимание, что часть w_i может быть меньше нуля и знаков абсолютной величины выше. С чисто неотрицательным w_i это распределение относительно просто с помощью выборки без замены - метод дерева, который является наиболее эффективным, насколько я могу судить. Однако с некоторыми отрицательными весами я чувствую, что должен прибегать к явным написанию каждой возможности и выборки из этого экспоненциально большого набора. Любые предложения или идеи будут оценены!

Answer 1

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