Задачка по теории вероятнотей + комбинаторика

krsnv · Сообщение **krsnv** » 24 янв 2009, 12:58

Здравствуйте.
Помогите решить такую задачку по теории вероятностей.
Есть два случайных m-битовых числа. Определить вероятность того, что у этих чисел в одной из битовых позиций будет общая единица; плюс к этому в другой позиции у первого числа будет 1 у второго 0, плюс к этому в третьей позиции у первого числа будет 0 у второго 1. Остальные позиции не важны.

To есть два числа будут имет следующую структуру.

1 2 3 4 5 6 7 8 ... m - позиция
x 0 x 1 x 1 x x ... x - первое число
x 1 x 1 x 0 x x ... x - второе число

Заранее спасибо.

Draeden · Сообщение **Draeden** » 24 янв 2009, 13:02

Почему бы не сказать, что число таких пар равно числу пар чисел у которых три бита совпадают ?

krsnv · Сообщение **krsnv** » 24 янв 2009, 13:15

Draeden писал(а):Source of the post
Почему бы не сказать, что число таких пар равно числу пар чисел у которых три бита совпадают ?

Потому, что это не так

по идее должно быть что-то такое:
0.25³*C³_m*3!
но из этого еще что-то вычесть надо для учета повторяющихся вариантов

qwertylol · Сообщение **qwertylol** » 24 янв 2009, 13:29

Всего у нас $$2^m$$

вариантов. Из них удовлетворяющих условию:
Если по правилу умножения то $m\cdot(m-1)\cdot(m-2)\cdot$2^{m-3}$^2$
Если через размещения, то $A_m^3\cdot$2^{m-3}$^2$
Это одно и тоже.

krsnv · Сообщение **krsnv** » 24 янв 2009, 13:35

qwertylol писал(а):Source of the post
Всего у нас вариантов.

вариантов только первого числа, всего наверное $$4^m$$

вариантов

qwertylol · Сообщение **qwertylol** » 24 янв 2009, 13:40

krsnv писал(а):Source of the post
qwertylol писал(а):Source of the post
Всего у нас вариантов.

вариантов только первого числа, всего наверное вариантов

ну да, очепятался, c кем не бывает, суть-то ясна.

krsnv · Сообщение **krsnv** » 24 янв 2009, 13:50

qwertylol писал(а):Source of the post
суть-то ясна.

суть-то, конечно, ясна, но уже при m=6, вероятночть почти 2 получается

B общем я написал программу, которая делает перебор всех вариантов, вот ee результаты:
-------------------------------------------
m=3
Общее количество комбинаций 64
Удовлетворяющих условию 6
Вероятность 0.093750
--------------------------------------------
m=4
Общее количество комбинаций 256
Удовлетворяющих условию 60
Вероятность 0.234375
--------------------------------------------
m=5
Общее количество комбинаций 1024
Удовлетворяющих условию 390
Вероятность 0.380859
--------------------------------------------

qwertylol · Сообщение **qwertylol** » 24 янв 2009, 14:46

krsnv писал(а):Source of the post
суть-то, конечно, ясна, но уже при m=6, вероятночть почти 2 получается

B общем я написал программу, которая делает перебор всех вариантов, вот ee результаты:
-------------------------------------------
m=3
Общее количество комбинаций 64
Удовлетворяющих условию 6
Вероятность 0.093750
--------------------------------------------
m=4
Общее количество комбинаций 256
Удовлетворяющих условию 60
Вероятность 0.234375
--------------------------------------------
m=5
Общее количество комбинаций 1024
Удовлетворяющих условию 390
Вероятность 0.380859
--------------------------------------------

гм.. Ну вот такая формула подходит: $1+4^{-m} \left(-1+3 2^m-3^{1+m}\right)$

krsnv · Сообщение **krsnv** » 24 янв 2009, 15:03

гм.. Ну вот такая формула подходит: $1+4^{-m} \left(-1+3 2^m-3^{1+m}\right)$

методом подбора?
даже при m=3 не подходит она совсем.

Хотя нет, если вот так $1+4^{-m} \left(-1+3*2^m-3^{1+m}\right)$ , то всё OK

Проверил для других m - все идеально работает. Inspektor, объясни, как вывести эту формулу.

qwertylol · Сообщение **qwertylol** » 24 янв 2009, 15:08

krsnv писал(а):Source of the post
методом подбора?
даже при m=3 не подходит она совсем.

Хотя нет, если вот так $1+4^{-m} \left(-1+3*2^m-3^{1+m}\right)$ , то всё OK

Проверил для других m - все идеально работает. Inspektor, объясни, как вывести эту формулу.

Точно подходит для m=0,1,2,3,4,5,6. Более того, затем она стремится к единице при $m\to\infty$ .
Вот первые сто значений:

Осталось понять c какого перепоя я её составил....

yourdomain.com