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

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

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

Если поймешь, черкани здесь обязательно

kobras · Сообщение **kobras** » 24 янв 2009, 18:21

krsnv писал(а):Source of the post
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
--------------------------------------------

я что-то не совсем условия понимаю. Как я понял для m=3 есть только одна пара чисел:
110
101
или я не прав?

a разобрался... не так прочитал

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

я что-то не совсем условия понимаю. Как я понял для m=3 есть только одна пара чисел:
110
101
или я не прав?
a разобрался... не так прочитал

да, структура в первом сообщении просто для наглядности
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 - второе число

порядок
0 1 1
1 1 0 - может быть любым

таким:
1 1 0
0 1 1

или, например, таким:
1 0 1
0 1 1

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

$1+4^{-m} \left(-1+3*2^m-3^{1+m}\right)$
Осталось понять c какого перепоя я её составил....

Всё, я разбрался. Inspektor, огромное спсибо!

kobras · Сообщение **kobras** » 24 янв 2009, 20:27

krsnv писал(а):Source of the post
$1+4^{-m} \left(-1+3*2^m-3^{1+m}\right)$
Осталось понять c какого перепоя я её составил....

Всё, я разбрался. Inspektor, огромное спсибо!

я тоже разобрался... пришел к той же формуле только в другом виде...
вопрос вы тоже c помощью рекурентных соотношений делали?

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

kobras писал(а):Source of the post
я тоже разобрался... пришел к той же формуле только в другом виде...
вопрос вы тоже c помощью рекурентных соотношений делали?

Да, я методом тыка(не научного, a простого) подобрал рекуррентную формулу по первым пяти(0,0,0,6,60) результатам.

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

Я делал так: переписал формулу в другом виде:
$1-\frac {3^{m+1}-3*2^m+1} {4^m}$
где $\frac {3^{m+1}-3*2^m+1} {4^m}$ - вероятность того, что не будет комбинации 01 или 10 или 11, рассчитать достаточно просто

kobras · Сообщение **kobras** » 24 янв 2009, 21:22

Ну я делал немного более трудно...
У меня было три формулы: A_{n}, B_{n}, C_{n}.
A_{n} - вероятность что в n-битовом числе длиной будет сходиться 1 из заданых пара битов
B_{n} - вероятность что в n-битовом числе длиной будет сходиться 2 из заданых пар битов
C_{n} - вероятность что в n-битовом числе длиной будет сходиться 3 из заданых пар битов

первое я считал следующем образом: верятность что на первой позиции нужная пара 0.25 что дальше в числе нас интерисует, дальше пусть на первом месте точно не нашая пара, пусть она на втором месте - вероятность 0.75*0.25 и так далее. Получилась геометрическая прогрессия и просумировал я отримал:
$A_{n}=0.25\frac {0.75^n-1} {0.75-1}=1-0.75^n$
Тепер ищем для двух пар. Вероятность что одна из нужных пар будет на первом месте 0.5, вероятность, что их не будет на первом месте тоже 0.5, отсюда формула:
$B_{n}=0.5A_{n-1}+0.5B_{n-1}$
если это решить, при этом подставляя $B_{2}=0.125$ имеем:
$B_{n}=0.5^n-2*0.75^n+1$
Ну и тепер последнее для 3. Пусть на 1 месте одна из нужных пар, это вероятность 0.75, вероятность что пар там не будет 0.25 и отсюда:
$C_{n}=0.75B_{n-1}+0.25C_{n-1}$
Если решить это ( $C_{3}=0.093750$ ) то получим результат:
$C_{n}=-0.25^n+3*0.5^n-3*0.75^N+1$
Самое трудное решать рекурентные соотношения.

krsnv · Сообщение **krsnv** » 25 янв 2009, 08:18

Вот более подробно решение через противоположные собития:
$P(01\cap10\cap11)=1-P(\bar{01}\cup\bar{10}\cup\bar{11})$

$P(\bar{01}\cup\bar{10}\cup\bar{11})=P(\bar{01})+P(\bar{10})+P(\bar{11})-P(\bar{01}\cap\bar{10})-P(\bar{01}\cap\bar{11})-P(\bar{10}\cap\bar{11})+P(\bar{01}\cap\bar{10}\cap\bar{11})=0.75^m+0.75^m+0.75^m-0.5^m-0.5^m-0.5^m+0.25^m==3*(\frac {3} {4})^m-3*(\frac {2} {4})^m+(\frac {1} {4})^m=\frac {3^{m+1}-3*2^m+1} {4^m}$

yourdomain.com