выбор случайного элемента набора мощности

Question

Для проблемы, над которой я сейчас работаю, я хотел бы получить достаточно равномерный случайный выбор из набора мощности данного набора. К сожалению, это касается статистики, которую я совсем не изучал (что мне нужно исправить сейчас, когда я начинаю заниматься реальным программированием), поэтому я хотел опробовать свое решение среди людей, которые его знают.

Если данный набор имеет размер n, то существует (nk) = n! / [K! (Nk)!] Подмножеств размера k, а общий размер N набора мощности дается как сумма (nk) более к от 0 до п. (также дано как 2 ⁿ , но я не думаю, что это здесь полезно. Я мог бы , очевидно, был быть неправильным).

Так что мой план - разделить [0, 1] на интервалы:

 [0, (n 0)/N] 

 ((n 0)/N, [(n 0) + (n 1)]/N] 

 ([(n 0) + (n 1)]/N, [(n 0) + (n 1) + (n 2)]/N]

  ... 

 ([N - (n n)]/N, 1]

Алгоритмически интервалы строятся путем взятия наибольшего элемента предыдущего интервала за наибольшую нижнюю границу нового интервала, добавляя к нему (n j) / N, чтобы получить наибольший элемент. Надеюсь, это понятно.

Затем я могу выяснить, сколько элементов находится в случайном подмножестве, выбрав равномерное число с плавающей точкой в ​​[0, 1] и сопоставив его с индексом интервала, которому он принадлежит. Оттуда я могу выбрать случайное подмножество подходящего размера.

1. Я вполне уверен (с простой интуитивной точки зрения), что моя схема обеспечивает равномерный выбор размера подмножества (равномерного по отношению к общему количеству подмножеств. равномерное на множестве {1, 2, .., n} размеров).

2. Я использую библиотеку (Python's random.sample), чтобы получить подмножество заданного размера, поэтому я уверен, что это будет равномерно.

Таким образом, мой вопрос заключается в том, позволяет ли объединение двух описанных мной способов сделать выбор случайного подмножества случайного размера равномерным. Если ответ - много работы, тогда я с радостью приму указания о том, как это можно доказать, и сделаю эту работу для себя. Кроме того, если есть лучший способ сделать это, то я, конечно, был бы рад этому.

Answer 1

Я думаю, вы проделаете долгий путь.Вы были близки, когда упомянули размер мощности, установленный как 2 ⁿ .Если вы хотите выбрать случайный элемент из набора мощности набора размером n, сгенерируйте случайное целое число в диапазоне [0, 2 ⁿ ) и используйте двоичное представление целого числа, чтобы выбратьсоответствующий элемент из набора мощности.

Например, предположим, что S = {a, b, c, d, e}.В этом случае блок питания содержит 2 ⁵ = 32 элемента.Создайте случайное число от 0 до 31, например, 18. Бинарное представление 18 - это 10010, поэтому вы должны выбрать первый и четвертый элементы S. Тогда ваш случайный элемент набора мощности будет {a, d}.

Answer 2

Рассмотрим каждый элемент данного набора по очереди и с вероятностью 1/2 решим включить его в набор результатов.