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

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

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

источник

2012-05-02 Butts Masterson

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

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

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

источник

2012-05-02 21:30:18

Там должно быть 2^п возможно N -length, и если мы возьмем только нечетные или четные строки, это будет 2^(n-1), правильно? –

Индукция, мой дорогой Ватсон! –

Извините, у меня проблемы с подключением точек. Я использую индукцию для поддержки своей 50-процентной теории или ее использования, чтобы каким-то образом получить другой ответ? –

Существует 50% шанс, что X является нечетным.

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

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

источник

2012-05-02 22:15:56 Joe

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

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

См. Wikipedia's page on the Binomial distribution.

Теперь вероятность 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]]

И эта сумма хорошо известно, равна единице (это Newton's binomial formula), так что вы остаетесь с

P = 1/2

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

источник

2012-05-08 19:37:09

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

ответ

Смежные вопросы