Концепция быстрой вероятности: N-битные строки

Question

Концепция быстрой вероятности: N-битные строки

Предположим, вы сгенерировали N-битную строку (состоящую только из 1 и 0). Сумма всех этих 0 и 1 равна X. Какова вероятность того, что X нечетно, если N нечетно? Какова вероятность того, что X нечетно, если N четно?

Поскольку вероятность того, что бит равен 0 или 1, составляет 50%, я бы предположил, что оба ответа равны 50%. Однако я не совсем прав. Могу ли я получить некоторые идеи о том, как решить эту проблему? любая помощь будет с благодарностью.

0

computer-science probability probability-theory

Источник

user1371110 02 май '12 в 21:28

3 ответа

Другие вопросы по тегам computer-science probability probability-theory

user129570 02 май '12 в 21:30 2012-05-02 21:30 · Answer 1 · 2012-05-02 21:30

Не по теме, но я укушу

Сколько возможных строк длины N? Сколько из них имеют даже бит-сумму? Сколько из них имеют нечетную битовую сумму?

Другими словами, предположим, что есть a четные (N-1) строки и b нечетная длина -(N-1) строк. Чтобы сформировать строку длины N, добавьте либо 0, либо 1. Это приводит к a+b четные строки и a+b нечетные строки.

user977472 02 май '12 в 22:15 2012-05-02 22:15 · Answer 2 · 2012-05-02 22:15

Существует 50% вероятность того, что X нечетный.

Если N равно 1, единственными возможными строками являются 0 и 1, так что есть вероятность 50%, что X нечетно.

Возможные строки, когда N=2, - это строки с N = 1 с добавлением 0 или 1: 00, 01, 10, 11. Поскольку шансы уже равны 50% для N = 1, а шансы равны 50% для цифры при добавлении, шансы для N=2 составляют 50%.

user408734 08 май '12 в 19:37 2012-05-08 19:37 · Answer 3 · 2012-05-08 19:37

Ваша интуиция верна. Может быть, было бы полезно увидеть это формально.

Биты, которые равны 0 и 1 с вероятностью 1/2, являются случайными величинами распределения Бернулли параметра p=1/2. Сумма N независимых бернуллиевских случайных величин параметра следует (по определению) биномиальному распределению с параметрами (N,p). Таким образом, ваша сумма является биномиальным распределением с параметром (N,1/2).

Смотрите страницу Википедии на биномиальном дистрибутиве.

Теперь вероятность P, что число является (скажем) четным:

P = Sum[Binomial[n,k]*1/2^n,k=all even values between 0 and n]

P = Sum[Binomial[n, 2 k]*1/2^n, k=0..Floor[n/2]]

P = 1/2 * Sum[Binomial[Floor[n/2],k]*1/2^n, k=0..Floor[n/2]]

И эта сумма, как известно, равна единице (это биноминальная формула Ньютона), так что вы остались с

P = 1/2

Этот вопрос был бы более уместным для Math StackExchange, и я имею в виду, что я мог бы использовать LaTeX в ответе:)