Ответ 1
Алгоритм Павлоса Эфраиммида и Пола Спиракиса решает именно эту проблему. Оригинальная статья с полными доказательствами опубликована с заголовком "Взвешенная случайная выборка с резервуаром" в "Обращениях обработки информации 2006", но вы можете найти простое резюме здесь.
Алгоритм работает следующим образом. Прежде всего, обратите внимание, что другой способ решить невзвешенную выборку коллектора - это присвоить каждому элементу случайный идентификатор R между 0 и 1 и поэтапно (скажем, с кучей) отслеживать верхние k идентификаторы. Теперь посмотрим на взвешенную версию, и пусть i-й элемент имеет вес w_i. Затем мы модифицируем алгоритм, выбирая id i-го элемента как R ^ (1/w_i), где R снова равномерно распределено в (0,1).
Другая статья, говорящая об этом алгоритме, - этот от людей Cloudera.