Равномерно случайные выборки двоичных строк длины N, когда N большое

Question

I sh, чтобы сгенерировать случайную двоичную строку длиной N, так чтобы каждая из возможных 2 ^ N строк была выбрана равномерно случайным образом. Обратите внимание, что выбор 1 или 0 с равной вероятностью для построения строки не работает, поскольку с высокой вероятностью строка содержит равные числа 0 и 1, и поэтому такие строки генерируются с большей вероятностью. Другой способ - создать список всех 2 ^ N строк, а затем выбрать одну из них. Однако, это быстро становится непрактичным, когда N даже 30. Мне нужно работать с N = 500. Как я могу достичь этого? Если бы у python была встроенная функция для такой вещи, было бы еще лучше.

Редактировать Очевидно, я задал неправильный вопрос; Извинения. То, что я хотел, было равномерное распределение по числу 1 в строке. Таким образом, строка только с двумя единицами должна быть такой же вероятной, как строка со всеми единицами. Я мог бы достичь этого, хотя.

Answer 1

Вы неправильно поняли, как работают вероятности. Равномерный случайный выбор каждого бита приводит к точно желаемому распределению.

Это правда, что это приведет к генерации строк с примерно равными числами 0 и 1, но это именно то, что должно быть сделано, поскольку наиболее вероятно битовые строки имеют близкие к равным числам 0 и 1 с . Каждая отдельная возможная цепочка битов по-прежнему имеет вероятность выбора 1/2 ^ N.

(Это не означает, что вы должны реализовать это, вручную выбирая биты по одному с random.choice, хотя. будет медленным. Что-то вроде '{:0{}b}'.format(random.getrandbits(N), N) будет быстрее.)