2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

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

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Задача про подбрасывание монеты
Сообщение05.07.2014, 22:06 


02/10/12
91
Привет!
Подскажите пожалуйста:
Найти вероятность того, что при пяти подбрасываниях монеты герб выпадет по крайней мере 3 раза подряд.

Решаю по формуле включений-исключений
C_3^1 \cdot 4/2^5 - C_2^1*1/16+1/2^5

Ответ неправильный. Если выкинуть послднее слагаемое, то вроде бы верно.

 Профиль  
                  
 
 Re: Задача про подбрасываение монеты
Сообщение05.07.2014, 22:32 


10/06/12
38
разбейте лучше на несовместные события, потом сложите, и все получится

 Профиль  
                  
 
 Re: Задача про подбрасываение монеты
Сообщение05.07.2014, 22:34 


02/10/12
91
Это я уже пробовал.
Но есть еще другая задача, где подбрасываний 10.
И кажется что метод включений-исключений все равно должен работать 8(

 Профиль  
                  
 
 Re: Задача про подбрасываение монеты
Сообщение05.07.2014, 22:51 


10/06/12
38
опять же через сумму несовместных - 3 герба по 10 ячейкам лягут 7-ю вариантами (то есть 10-k, k=3:10, сочетания из 10-к по 1 суммируете и умножаете на $1/1024 $) а как вы здесь представляете включение-исключение. в чем совместность?

-- 05.07.2014, 22:55 --

хотя неправ, надо еще считать варианты три герба встретятся два раза на 10 подбрасываниях, например

 Профиль  
                  
 
 Re: Задача про подбрасываение монеты
Сообщение05.07.2014, 23:02 
Заслуженный участник


27/04/09
28128
Рассмотрите такие вероятности:
$p_3(n)$ того, что три герба подряд встретились в каких-нибудь предыдущих $n$ подбрасываниях;
$p_2(n)$ того, что последними в серии предыдущих $n$ подбрасываний были, с сохранением порядка, не-герб, герб, герб;
$p_1(n)$ того, что последними в серии предыдущих $n$ подбрасываний были, с сохранением порядка, не-герб и герб;
$p_0(n)$ того, что последним подбрасыванием из предыдущих $n$ был не герб
и выразите $p_i(n)$ через $p_i(n-1)$. Получатся рекуррентные соотношения, из которых можно будет найти $p_3(n)$ для любого $n$, зная, что $p_0(0) = 1$ и $p_1(0) = p_2(0) = p_3(0) = 0$.

 Профиль  
                  
 
 Re: Задача про подбрасываение монеты
Сообщение05.07.2014, 23:09 


02/10/12
91
Спасибо, попробую. А не подскажите где ошибка в моей формуле? Я рассуждал так - вероятность что есть три герба подряд, минус вероятность четыре герба подряд плюс пять подряд.. Кажется классическая формула...

 Профиль  
                  
 
 Re: Задача про подбрасываение монеты
Сообщение05.07.2014, 23:45 
Заслуженный участник


27/04/09
28128
oxid в сообщении #884364 писал(а):
А не подскажите где ошибка в моей формуле?
Ошибка — это вещь не всегда локализуемая. :wink:

Хотя вот странно, у вас в формуле есть и $\cdot$ и $*$ — к чему бы это… Но ведь это не та ошибка, которую вы бы хотели?

 Профиль  
                  
 
 Re: Задача про подбрасываение монеты
Сообщение06.07.2014, 13:28 


02/10/12
91
Локализовал ошибку. В число всех комбинаций с тремя орлами входит 3 комбинации когда выпали только орлы. А в число комбинаций с 4 орлами входит 2 таких. Т.е нужно только два члена это суммы. И обычная формула тут видимо не действует.


Правда не получается как то обобщить.

 Профиль  
                  
 
 Re: Задача про подбрасываение монеты
Сообщение06.07.2014, 15:28 
Заслуженный участник


27/04/09
28128
Обобщить можно рекуррентную последовательность $(p_0, p_1, p_2, p_3)$. Точнее, она уже и так обобщена — какое нужно $n$, то и берите. :-) То, что она рекуррентно задана здесь, не значит, что её нельзя задать нерекуррентно. А если вы увидите там матрицу — вообще хорошо.

Может, попробуете составить соотношения?

 Профиль  
                  
 
 Re: Задача про подбрасываение монеты
Сообщение06.07.2014, 17:40 


02/10/12
91
Попробовал, но как-то не очень продвинулся

p_3(n) = p_3(n-3) \cdot 7/8 + (1-p_3(n-3))\cdot1/8 +  ((1-p_3(n-3))\cdot7/8 )(p_2(n-3)/2 + p_2(n-3)/4 +  p_1(n-3)/4 ) + p_3(n-3)/8

Т.е разбиваем пространство на 4 непресекающихся события -
либо 3 орла это три последних подбрасывания, либо они лежат среди n-3 первых подбрасываний. Либо они лежат "между", либо одновременно и там и там.
Между могут лежать вот такими способами - poo|о..., роо|оо..., ро|оо...

 Профиль  
                  
 
 Re: Задача про подбрасываение монеты
Сообщение06.07.2014, 18:23 


20/03/14
12041
 !  Aarnikotka
Замечание за неиспользование тега math. post884357.html#p884357

 Профиль  
                  
 
 Re: Задача про подбрасываение монеты
Сообщение06.07.2014, 20:24 
Заслуженный участник


27/04/09
28128
oxid в сообщении #884604 писал(а):
Попробовал, но как-то не очень продвинулся
$$p_3(n) = p_3(n-3) \cdot 7/8 + (1-p_3(n-3))\cdot1/8 +  ((1-p_3(n-3))\cdot7/8 )(p_2(n-3)/2 + p_2(n-3)/4 +  p_1(n-3)/4 ) + p_3(n-3)/8$$
Не-не-не, никаких $n-3$! Только $n-1$.

Думаю, я плохо объяснил, в чём соль способа и что вообще надо делать.

Для каждой последовательности бросков известно, есть в ней три герба подряд или нет. Бросание монеты переводит одну последовательность в другую, но при этом трёхгербовость появляется или не появляется у новой последовательности не как попало, а довольно по простому закону.

Когда мы получим трёхгербовую последовательность? Если она уже была такая и выпало что угодно, или если она не была трёхгербовая, но в конце у неё было два герба, и выпал герб. Ага, а последовательность такого вида как может получиться? Единственным образом — если была не трёхгербовая последовательность с не-гербом и гербом в конце и выпал герб. Ну а такая как может получиться? Если была не трёхгербовая последовательность, у которой в конце не герб, и выпал герб. Под конец, последовательность последнего вида может получиться из любой не трёхгербовой последовательности выпадением не-герба.

В самом начале у нас пустая последовательность, которую логично отнести к последнему типу; и назовём эти типы соответственно 3, 2, 1 и 0. Заметьте, что последовательность обязательно одного из этих типов, так что ничего не пропущено в описании.

Теперь представим, что мы что-то там набросали $n$ раз и не знаем, что это за последовательность, но можем знать, например, пару-другую вероятностей. К сожалению, выше в
arseniiv в сообщении #884363 писал(а):
$p_3(n)$ того, что три герба подряд встретились в каких-нибудь предыдущих $n$ подбрасываниях;
$p_2(n)$ того, что последними в серии предыдущих $n$ подбрасываний были, с сохранением порядка, не-герб, герб, герб;
$p_1(n)$ того, что последними в серии предыдущих $n$ подбрасываний были, с сохранением порядка, не-герб и герб;
$p_0(n)$ того, что последним подбрасыванием из предыдущих $n$ был не герб
я выразился неточно, и это могло вас запутать. $p_0, p_1, p_2$ относятся именно к не трёхгербовым последовательностям. (Тогда $p_0(n)+p_1(n)+p_2(n)+p_3(n) = 1$ для любого $n$, это потом можно использовать для проверки.)

Зная, как последовательности типов 3, 2, 1 и 0 получаются друг из друга, мы можем записать аналогичные соотношения для вероятностей $p_i(n)$ (каждой, иначе ответ не получится) через (все) $p_j(n-1)$. В меньшие длины уходить не надо, потому что это избыточно и всё только усложнит.

Попробуйте теперь снова.

-- Вс июл 06, 2014 23:39:36 --

Можно разбить последовательности на большее число классов, но это опять только усложнит дорогу к ответу.

Подобным способом можно строить ДКА, распознающий во входной строке вхождения какого-то заданного множества подстрок. В нашем случае — последовательности (герб, герб, герб). По построенному конечному автомату можно, если вероятности появления символов (у нас это результаты бросания монеты), получить цепь Маркова и вот этот метод вычисления вероятности того, что в последовательности есть какая-то подпоследовательность (или какая-то из нескольких!). Если вы знаете про конечные автоматы в достаточной мере, это может помочь в понимании манипуляций выше, мне кажется.

 Профиль  
                  
 
 Re: Задача про подбрасываение монеты
Сообщение08.07.2014, 22:17 


02/10/12
91
Получились такие соотношения
$p_3(n) = p_3(n-1) + p_2(n-1)/2$
$p_2(n) = p_1(n-1)/2$
$p_1(n) = p_0(n-1)/2$
$p_0(n) = n > 0 ? 1/2 : 1$

В таком варианте выдает верный ответ.
Но, при больших n он переваливает через 1 ;)

$p_3(n) = p_3(n-1) + (1- p_3(n-1)) p_2(n-1)/2$
Тут ответ выдается неверный, но при больших n работает корректно.

Проверял программой на python

 Профиль  
                  
 
 Re: Задача про подбрасываение монеты
Сообщение09.07.2014, 01:02 
Заслуженный участник


27/04/09
28128
Вот верный:$$\mathbf p(n) \equiv \begin{bmatrix} p_3(n) \\ p_2(n) \\ p_1(n) \\ p_0(n) \end{bmatrix} = \begin{bmatrix} 1 & 1/2 & 0 & 0 \\ 0 & 0 & 1/2 & 0 \\ 0 & 0 & 0 & 1/2 \\ 0 & 1/2 & 1/2 & 1/2 \end{bmatrix} \begin{bmatrix} p_3(n-1) \\ p_2(n-1) \\ p_1(n-1) \\ p_0(n-1) \end{bmatrix} \equiv A\mathbf p(n-1).$$(В таком виде удобнее смотреть на вероятности переходов.)

Видно, что вы только в одном уравнении — для $p_0$ — забыли, что трёхгербовая последовательность никак уже «назад» не вернётся, и вид у него будет $p_0(n) = (p_2(n-1) + p_1(n-1) + p_0(n-1))/2$. (Проверку можно не писать, потому что здесь достаточно, чтобы эти соотношения были верны даже только при $n>0$.)

А теперь — магия. С пустой последовательностью всё ясно: как я выше уже писал, в ней нет гербов (да, поиграю КО :lol: ), т. е.$$\mathbf p(0) = \begin{bmatrix} 0 \\ 0 \\ 0 \\ 1 \end{bmatrix}.$$Чтобы получить $p_3(1)$, получим все вероятности $\mathbf p(1)$, умножив слева на матрицу вероятностей переходов:$$\mathbf p(1) = A\mathbf p(0).$$Чтобыполучить $p_3(2)$, получим все вероятности $\mathbf p(2)$, умножив снова:$$\mathbf p(2) = A\mathbf p(1) = A^2\mathbf p(0).$$Можно увидеть (и при желании строго доказать матиндукцией), что$$\mathbf p(n) = A^n\mathbf p(0).$$Это, в сущности, решение, потому что в конце надо взять первую компоненту, а это тоже оформляемо умножением на матрицу. Возвести $A$ в натуральную степень можно «за одно действие» разными способами, напр., с помощью жордановой нормальной формы (слова страшные, а так-то всё несложно; можете, например, в этой теме посмотреть, хотя лучше почитать).

 Профиль  
                  
 
 Re: Задача про подбрасываение монеты
Сообщение12.07.2014, 22:22 


02/10/12
91
Спасибо, это очень интересный метод!

Но может ли кто про формулу прояснить?

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 23 ]  На страницу 1, 2  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
cron
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group