Здравствуйте!

Можно ли как-то подсчитать вероятность того что сумма (s1-s2)+(s3-s4) будет равна 0,
если числа s1,s2,s3,s4 -12 битные и распределены по равномерному распределению.

Спасибо!

Можно и легко. На бумаге в клеточку... Сводится к двум числам...

Если числа распределены по павномерному распределению (т.е. плотности распределения всех чисел - непрерывные), то вероятность что их сумма будет равна нулю (или любому другому наперед заданному числу) равна нулю. Можно посчитать только плотность вероятности в какой-то точке или вероятность того, что сумма попадет в дифференциально малую окрестность этой точки...

СПС,А можно формулкой кинуть??



СПС, хорошо и как подсчитать такую верятность не подскажете??

Сообщение отредактировал -=Vitaly=- - Feb 22 2007, 13:18

ПЖЛСТ

В яндексе ищете "плотность суммы случайных величин". Находите например это (следствие 11)
Для каждой суммы (у Вас - разности) находите две плотности вероятности. Потом находите плотность вероятности их суммы, обозначим его f(s). Значение произведения f(0)ds и будет искомлй ветояностью попадания суммы в окрестность нуля с дифференциально малым размером ds. Если размер интервала не мал, то надо считать интеграл f(s)ds по всем интервалу.

Если числа s1, s2, s3, s4 независимые, то вероятность того, что сумма будет равна 0, равна 1/(4096^2).

Ошибочка. 1/4096^2 - это вероятность того, что S1 == S2 И S3 == S4. Последовательность 1, 2, 4, 3 дает нулевую сумму, но таким событием не является.

Мое число - 1.6e-4

Тоже не то. Правильно - 1.22е-4. В своём первом ответе не учёл знаки чисел(:-(.

Правильно ли?

Событие - что S1 + S3 == S2 + S4;
Рассмотрим случайную величину S1 + S2. Это сумма двух равномерно распределенных величин. Её распределение можно посчитать в лоб - треугольник.
Состоящий из двух линейных прогрессий. Правда, центральная точка единственная.
Чтобы получить вероятность того, что две такие величины совпадут - нужно этот треугольник возвести в квадрат и просуммировать.

У меня получилось примерно 1.6e-4. Признаюсь, мне было лень считать сумму квадратов линейной прогрессии (хоть Кнут и утверждает, что проще посчитать на бумаге) - я воспользовался Матлабом.

Поскольку числа знаковые и распределения равномерные, то можно рассматривать выражение s1+s2+s3+s4 вместо s1-s2+s3-s4.

Для одного случайного числа распределение равномерное, в виде прямоугольника от -2048 до 2047 и высотой 1/4096. Для двух чисел s1+s2 распределение будет треугольное, от -4096 до 4095 и максимумом 1/4096 в нуле. Для двух других будет то же самое.

Для четырёх чисел распределение будет из четырёх одинаковых кусков параболы, размещенных в диапазоне от -8192 до 8191 (похоже на кривую Гаусса). Нужно найти значение в 0 (максимум). Если завернуть куски гиперболы от -8192 до -4096 и от 4096 до 8191, то получим прямоугольник шириной 8192 и площадью 1.

Осюда легко вычисляется высота, т.е. 1/8192=1.22е-4, а это и есть значение в 0. Как-то так. Поправьте, если где ошибся, я частенько бываю небрежен.

В первом ответе я не прочитал ограничение про 12-ти битное представление чисел. В этом случае вероятность нулевой суммы не равна нулю, т.к. распределение становится дискретным, а не непрерывным как я предположил вначале (тут была ошибка). Остальные рассуждения остаются в силе. Для того, чтобы проинтегрировать дискретное распределение в указанной формуле оно представляется в виде гребенки равноотстоящих дельта-функций, расположенных в точках от 0 до N-1 c шагом единица, N=2^12. Вес каждой дельта-функции p0=1/N.

Плотность вероятности разностей s1-s2 или s3-s4 (если числе - независимы) также представляется в виде гребенки дельтафункций, но уже в пределах от -N+1 до N-1 (так получается после свертки). Вес каждой функции p1 = p0^2*(N-abs(n)), n меняется от -N+1 до N-1.

Для получения вероятности нулевого значения нжно свернуть между собой две плотности вероятности для разностей (см.формулу) и рассчитать значение свертки в нулевой точке. В результате - вероятность нулевой суммы P = SUM{p0^4*(N-abs(n))^2}, n меняется от -N+1 до N-1.

Численный ответ: P = 1.6276e-004

Огромное спасибо!!!!
Не перевелись еще ОТЦЫ на Руси !!!
Всем

Господа, да вы что!!! Зачем человека вводите в заблуждение? Какая плотность? Какие окрестности? Ведь ясно написано - числа 12-ти разрядные!!! Равномерное распрделение(а не плотность!!!!!!!!!) P(x) = 1/4096

Проверил Монтей Карлой (10e9 испытаний):

- если "сумма", как и сами числа, тоже 12-бит (т.е. происходят переполнения разрядной сетки:
0x800 - 0x000 + 0x800 - 0x000 == 0x000 ), то вероятность: 2.447e-4

- если сумма 14-бит (т.е. имеет достаточную разрядность, чтобы "суммировать" без преполнений:
0x800 - 0x000 + 0x800 - 0x000 == 0x1000 ), то вероятность: 1.629e-4



Сообщение отредактировал vladv - Mar 22 2007, 22:53