Серии "орлов" и "решек" при бросании монеты

Логические задачи

Серии "орлов" и "решек" при бросании монеты

Сообщение Dendr » 05 июн 2014, 14:06

Раз начался разговор в теме про данетку, то предложу в качестве отдельной задачи.

Экспериментатор бросает монетку N раз подряд и записывает результаты в строчку. Он ожидает, что в его ряду окажется отрезок, содержащий только "орлы" или только "решки" (неважно что) длины n. Какова вероятность P(N, n) того, что этого не произойдет?
К данетке: какова вероятность того, что студент честно будет бросать монетку и записывать результаты, и в итоге не получит ожидаемых профессором 6 одинаковых подряд? (в обозначениях задачи - P(600, 6))

Замечание. Если выпала серия длиной k, то по определению принимается, что выпала и серия длиной (k-1).

Примечание 1. Очевидно, что P(N, 1)=2/(2^N): это отвечает случаям ОРОРОР... и РОРОРО...
Примечание 2. Вычислить P(N, 2) возможно в явном виде, но при больших n придется записывать в виде рекуррентной формулы.

Для самопроверки советую рассмотреть случай, когда 6 бросков всего, и определить вероятности выпадения серий из 1, 2 и т.д. орлов или решек.
Шесть - достаточно большое число, чтобы не получить правильные числа случайно, даже допустив ошибку, но достаточно малое, чтобы перебрать варианты вручную.
(кстати, без ограничения общности первое выпадение можно - и так удобнее! - обозначить за "ноль" и считать выборку из 2^(N-1) случаев, ища серии из нулей и единиц)
Длина самой длинной серии 1 - то есть только 010101 - 1 случай.
Длина серии 2 - 12 случаев (001001, 001010, 001011, 001100, 001101, 010010, 010011, 010100, 010110, 011001, 011010, 011011)
Длина серии 3 - 11 случаев (000100, 000101, 000110, 000111, 001000, 001110, 010001, 010111, 011000, 011100, 011101)
Длина серии 4 - 5 случаев (000010, 000011, 001111, 010000, 011110)
Длина серии 5 - 2 случая (000001, 011111)
Длина серии 6 - 1 случай (000000)

1+12+11+5+2+1=32=2^5 - найдены все комбинации
То есть точные значения вероятностей:
P(6, 1)=1/32
P(6, 2)=13/32
P(6, 3)=24/32=3/4
P(6, 4)=29/32
P(6, 5)=31/32
P(6, 6)=1
Аватара пользователя
Dendr
Акула пера
Акула пера
 
Сообщения: 5717
Зарегистрирован: 06 май 2005, 15:11
Откуда: Раменское, Мос.обл.

Re: Серии "орлов" и "решек" при бросании монеты

Сообщение Юляша » 06 июн 2014, 14:39

Ну, рекурсивная-то формула получается:

Вероятность "успеха" (получения серии по меньшей мере в n одинаковых результатов при N бросаниях):

P(N,n)=1/2^(n-1)+СИГМА (от i=1 до n-1) (P(N-i,n)/2^i)

P(N,n)=0, при N<n.

---- добавление

А вообще-то это ведь линейное разностное уравнение, которое решается через характеристический многочлен...

---- еще добавление

Немножко хулиганская подстановка (тоже через матпрограмму) дала вероятность неуспеха примерно равную 1/27384, что очень близко к первичному результату...
Нас двое - я и папа
И погромче нас были витии Да не сделали пользы пером. Дураков не убавим в России, А на умных тоску наведем.
Юляша
Популярный автор
Популярный автор
 
Сообщения: 3115
Зарегистрирован: 15 янв 2009, 12:32

Re: Серии "орлов" и "решек" при бросании монеты

Сообщение Dendr » 06 июн 2014, 18:46

Можно и проще. Тогда вероятности вычисляются на бумажке (но долго), или загоняются в Эксель парой движений.
Аватара пользователя
Dendr
Акула пера
Акула пера
 
Сообщения: 5717
Зарегистрирован: 06 май 2005, 15:11
Откуда: Раменское, Мос.обл.

Re: Серии "орлов" и "решек" при бросании монеты

Сообщение Dendr » 06 июн 2014, 18:48

И нет там разностных уравнений, если на то пошло, а есть свертка (которую, повторюсь, можно и обойти)
Аватара пользователя
Dendr
Акула пера
Акула пера
 
Сообщения: 5717
Зарегистрирован: 06 май 2005, 15:11
Откуда: Раменское, Мос.обл.

Re: Серии "орлов" и "решек" при бросании монеты

Сообщение Юляша » 09 июн 2014, 08:47

Тут вопрос трактовки - в математике практически все можно сделать разными способами.

Де факто вероятность асимптотически определяется максимальным по модулю корнем уравнения x**5-x**4/2-x**3/4-x**2/8-x/16-1/32=0

Excel дает в качестве корня 0,982974115721485, а вероятность "по калькулятору" получается 3,6520668177848671573130959192044e-5, что примерно равно 1/27382.
Нас двое - я и папа
И погромче нас были витии Да не сделали пользы пером. Дураков не убавим в России, А на умных тоску наведем.
Юляша
Популярный автор
Популярный автор
 
Сообщения: 3115
Зарегистрирован: 15 янв 2009, 12:32

Re: Серии "орлов" и "решек" при бросании монеты

Сообщение Dendr » 09 июн 2014, 20:47

Если есть Эксель, то асимптоту считать и не нужно.

Вот так можно решить проще: рассмотрим последовательности нулей и единиц длиной N. Без ограничения общности можно считать, что она начинается с нуля, тогда у нас будет 2^(N-1) вариантов.

Пусть теперь A(N, n) - число вариантов, в которых самая длинная непрерывная серия нулей или единиц не больше n.
Они, как можно видеть, делятся на n подтипов: j-й тип начинается с j нулей (1<=j<=n), после чего либо конец ряда, либо ряд длины (N-j), начинающийся с единицы. Инвертируем его, получим ряд, начинающийся с нуля? в котором самая длинная серия опять же не превышает n в длину - и становится очевидным, что всего рядов j-го типа будет A(N-j, n).

Следовательно, A(N, n)=A(N-1, n)+A(N-2, n)+...+A(N-n, n) - можно сказать, обобщенный ряд Фиббоначи.
По определению можем положить:
A(N<0, n)=0 (нет отрицательных рядов)
A(0, n)=1 (пустой ряд может быть только один)
A(1, n)=1 (ряд единичной длины единственный по построению)

Тогда можно применять выведенную формулу: A(2, n)=A(1, n)+A(0, n)=2, если n>=2. И это правильный ответ: всего комбинаций две (00 и 01), и обе они отвечают n=2. Если n=1, A(2, 1)=A(1, 1)=1 - действительно, это "01".

Ну и так далее - эту формулу можно вставить в Эксель без видимых проблем, достаточно автозаполнения. И подсчитать вероятность точно можно на раз-два: P(N, n)=A(N, n)/2^(N-1)

Точная формула легко получается для n=2 (так как формула для обычного ряда Фиббоначи известна), а для более высоких фиксированных n придется эмпирикой. Впрочем, не такая уж и эмпирика: все-таки ряд при больших N мало отличается от геометрической прогрессии.
Аватара пользователя
Dendr
Акула пера
Акула пера
 
Сообщения: 5717
Зарегистрирован: 06 май 2005, 15:11
Откуда: Раменское, Мос.обл.

Re: Серии "орлов" и "решек" при бросании монеты

Сообщение Юляша » 10 июн 2014, 08:13

Dendr писал(а): Впрочем, не такая уж и эмпирика: все-таки ряд при больших N мало отличается от геометрической прогрессии.


Так об этом и речь. И знаменатель этой прогрессии - корень того самого приведенного мною характеристического уравнения. Это, так сказать, вместо эмпирики...
Нас двое - я и папа
И погромче нас были витии Да не сделали пользы пером. Дураков не убавим в России, А на умных тоску наведем.
Юляша
Популярный автор
Популярный автор
 
Сообщения: 3115
Зарегистрирован: 15 янв 2009, 12:32

Re: Серии "орлов" и "решек" при бросании монеты

Сообщение Dendr » 10 июн 2014, 22:33

Знаменатель - да, но константу все равно надо подбирать "вручную" - подставив в формулу, скажем, 10-й член, вычисленный точно. Это для n=2 она точно известна...

Раз пошло такое дело, вот отсюда можно смотреть:
http://en.wikipedia.org/wiki/Generaliza ... ci_numbers
Аватара пользователя
Dendr
Акула пера
Акула пера
 
Сообщения: 5717
Зарегистрирован: 06 май 2005, 15:11
Откуда: Раменское, Мос.обл.


Вернуться в Задачки

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

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