Нестандартное решение олимпиадной задачи по теорверу

[General]

Задача.
Какова вероятность того, что при бросании монеты серия из трёх орлов подряд выпадет раньше, чем серия из двух решек подряд?

Эта задача была на Всеукраинской студенческой олимпиаде по математике в 2005 году в Севастополе. Оценивалась она в 12 баллов (всего за правильное решение всех 10 задач можно было получить, по-моему, 60 баллов).

Решение.
Будем обозначать выпадение орла как 0, а решку – как 1. Найдём сначала, сколько существует последовательностей из 0 и 1 длины n таких, которые заканчиваются ровно тремя нулями и не содержат других троек нулей и пар единиц. Обозначим это количество как Х(n), а выделенное жирным условие как Условие 1. Оно нам потом ещё пригодится.

Понятно, что для n=1 или 2 таких последовательностей не существует. Для n=3 возможна только единственная: 000. Далее цепочки длины n+1 можно получать из цепочек длины n, подставляя в качестве первого символа 0 или 1, с тем, чтобы продолжало выполняться Условие 1. Первые несколько шагов представлены в таблице.

\begin{tabular}{|c|c|c|} \hline n& X(n) & Возможные цепочки \\ \hline 1& 0 & - \\ \hline 2& 0 & - \\ \hline 3& 1 & 000 \\ \hline 4& 1 & 1000 \\ \hline 5& 1 & 01000 \\ \hline 6& 2 & 101000; 001000 \\ \hline 7& 2 & 0101000; 1001000 \\ \hline 8& 3 & 00101000; 10101000; 01001000 \\ \hline 9& 4 & 100101000; 010101000; 001001000; 101001000 \\ \hline \end{tabular}
Более наглядно процесс образования цепочек большей длины показывает вот такое дерево:



Поскольку всего цепочек из 0 и 1 длины n - $2^n$, то вероятность того, что три орла выпадут раньше двух решек после ровно n бросков, составляет $ \frac{X(n)}{2^n}$. Таким образом, для вычисления искомой вероятности требуется найти сумму $ \frac{X(1)}{2^1}+ \frac{X(2)}{ 2^2}+ \frac{X(3)}{ 2^3}+ \frac{X(4)}{ 2^4}+…$

Для этого сначала нужно найти общую формулу X(n). Введём 3 вспомогательных величины.
A(n) – количество цепочек из 0 и 1 длины n, которые удовлетворяют Условию 1 и начинаются с 00
B(n) – количество цепочек из 0 и 1 длины n, которые удовлетворяют Условию 1 и начинаются с 01
C(n) – количество цепочек из 0 и 1 длины n, которые удовлетворяют Условию 1 и начинаются с 10

При образовании цепочки длины n+1 перед каждой цепочкой, начинающейся с 00 для соблюдения Условия 1 можно ставить только 1, перед цепочками на 10 – только 0, а перед цепочками на 01 можно ставить и 0 и 1.

Получаем:
A(n+1) = B(n)
B(n+1) = C(n)
C(n+1) = A(n)+B(n)

Далее
A(n+2) = B(n+1) = C(n)
B(n+2) = C(n+1) = A(n)+B(n)
C(n+2) = A(n+1)+B(n+1) = B(n)+ C(n)

И ещё один шаг:
A(n+3) = B(n+2) = A(n)+B(n)
B(n+3) = C(n+2) = B(n)+ C(n)
C(n+3) = A(n+2)+B(n+2) = A(n)+B(n)+ C(n)

Тогда
X(n+3) = A(n+3)+B(n+3)+C(n+3) = 2A(n)+3B(n)+2C(n) = X(n+1)+X(n)
Мы получили для X(n) рекуррентную формулу.

К сожалению, я тогда не умел решать разностные уравнения, но интуитивно чувствовал, что, по аналогии с последовательностью Фибоначчи, X(n) можно в общем виде представить в виде суммы нескольких геометрических прогрессий, основанием одной из которых должен быть корень уравнения $\lambda^3=\lambda+1$, о чём и написал в решении. Тогда и сумма $\sum \limits_{n=1}^{\infty}{\frac{X(n)}{2^n}}$ разложится в несколько геометрических прогрессий, которые затем легко свернутся.

За решение тогда поставили то ли 1 балл, то ли вообще 0. Я, разумеется, пошёл аппелировать. На аппеляции я в первый раз встретился с dm’ом. Он разобрался в моём решении, сказал, что ход моих мыслей верный и рассказал, как нужно решать разностные уравнения. Другое дело, что дальнейшее решение по предполагаемому мной пути заняло бы время, намного большее уже потраченного. Однако свои 6 баллов я получил и в итоге вышел на 2е место с разрывом с первым в 1 балл (если бы не ступил при решении детской 4-х балльной задачи – было б первое).

Вечером пришла идея, как найти искомую сумму ряда, не решая характеристического уравнения $\lambda^3=\lambda+1$, а зная только произведение, сумму и сумму попарных произведений его корней из теоремы Виета. После достаточно объёмных преобразований сумма находилась. Я показал записи Дмитрию Юрьевичу и мы тогда решили, что это была бы интересная тема для статьи про нестандартное решение задачи на теорию вероятности.

Однако дома я всё откладывал оформление на потом и тема как-то забылась. Ну а сейчас наконец-то собрался и решил описать своё решение. Тем более что, позже покрутив эту задачу, я понял, как можно ещё проще найти сумму ряда.

Итак, дано:
X(n+3) = X(n+1)+X(n)
Найти:
$\sum \limits_{n=1}^{\infty}{\frac{X(n)}{2^n}}$

Пусть
$S= \frac{X(3)}{2^3}+ \frac{X(4)}{ 2^4}+ \frac{X(5)}{2^5}+\frac{X(6)}{2^6}+\frac{X(7)}{2^7}+…$
(члены X(1) и X(2), равные 0, просто опустим)

Разделим сумму на 4
$\frac{S}{4}=\frac{X(3)}{2^5}+ \frac{X(4)}{ 2^6}+ \frac{X(5)}{2^7}+\frac{X(6)}{2^8}+\frac{X(7)}{2^9}+…$

А тепер разделим её на 8
$\frac{S}{8}=\frac{X(3)}{2^6}+ \frac{X(4)}{ 2^7}+ \frac{X(5)}{2^8}+\frac{X(6)}{2^9}+\frac{X(7)}{2^10}+…$

И сложим последние 2 величины:
$\frac{S}{4}+\frac{S}{8}=\frac{X(3)}{ 2^5}+ \frac{X(3)+X(4)}{2^6}+ \frac{X(4) +X(5)}{ 2^7}+ \frac{X(5) +X(6)}{2^8}+\frac{X(6) +X(7)}{2^9}+\frac{X(7) +X(8)}{2^{10}}+…=\frac{X(3)}{ 2^5}+ \frac{X(6)}{2^6}+ \frac{X(7)}{ 2^7}+ \frac{X(8)}{2^8}+\frac{X(9)}{2^9}+\frac{X(10)}{2^{10}}+…=\frac{X(3)}{ 2^5}+S-\frac{X(3)}{2^3}- \frac{X(4)}{ 2^4}- \frac{X(5)}{2^5}$

Подставив значения, решаем уравнение:
$\frac{S}{4}+\frac{S}{8}=\frac{1}{32}+S-\frac{1}{8}-\frac{1}{16}-\frac{1}{32}$
Откуда S=0.3

Следовательно, при бросании монеты с вероятностью 30% 3 орла подряд выпадут раньше двух решек подряд.

Вот так вот, через 3 с половиной года наконец-то выкладываю своё решение в виде статьи. У себя на http://intelmath.narod.ru думаю продолжить писать статьи на математические и околоматематические темы, идеи которых возникали давно, но всё откладывались в долгий ящик.

[TOTAL]

$P$ --- искомая вероятность (что $000$ встретится раньше, чем $11$)
$P_0$ --- искомая вероятность, если первым выпал $0$
$P_1$ --- искомая вероятность, если первым выпал $1$

$P=\frac{1}{2} \left( \frac{1}{2} +\frac{1}{2} P_1 \right)$
$P=\frac{1}{2} P_0 +\frac{1}{2} P_1$
$P_1=\frac{1}{2} P_0$

Откуда $P=\frac{3}{10}$

[Архипов]

TOTAL писал(а):

$P$ --- искомая вероятность (что $000$ встретится раньше, чем $11$)
$P_0$ --- искомая вероятность, если первым выпал $0$
$P_1$ --- искомая вероятность, если первым выпал $1$

$P=\frac{1}{2} \left( \frac{1}{2} +\frac{1}{2} P_1 \right)$
$P=\frac{1}{2} P_0 +\frac{1}{2} P_1$
$P_1=\frac{1}{2} P_0$

Откуда $P=\frac{3}{10}$

А почему $P_1=\frac{1}{2} P_0$ ? Ведь эти вероятности равны друг другу("выпал первым единственный О" или "выпала первой единственная 1" составляют полную группу событий).

Вероятность одной из заданных комбинаций выпасть первой, оказывается, зависит от количества выполненных бросков (то есть не постоянная).

Р1(ООО)=0 - _____________Р1(РР)=0 - при 1 броске
Р2(ООО)=0________.Р2(РР)=1/4=0,25 - при 2 бросках
Р3(ООО)=1/3=0,333..___.Р3(РР)=0,66...- при 3 бросках
Р4(ООО)=3/11=0,27...___Р4(РР)=0,73...- при 4 бросках
Р5(ООО)=7/24=0,29...___Р5(РР)=0,71...- при 5 бросках

Возможно, в задаче не хватает корректного условия (или указать количество бросков, или броски прекращаются при первом же выпадении одной из комбинаций). То есть не указано условия завершения процедуры. А раз не указано, то имеем право закончить процедуру при двух бросках, например.
Или условие обсуждаемой задачи предусматривает совместное появление двух событий (ООО и РР) или (РР и ООО) ?

[General]

TOTAL
Красиво! По-моему, оригинальное решение, которое, конечно, короче моего было, и то длиннее.

Архипов

Архипов в сообщении #145141 писал(а):

А почему $P_1=\frac{1}{2}P_0$ ?

Если первый раз выпадает единица, то если и после этого выпадет единица, то событие вооще не наступит, а если же выпадет 0 (с вероятностью $\frac {1}{2}$), то вероятность превратится в $P_0$
Поэтому $P_1=\frac{1}{2}*0+\frac{1}{2}P_0$

Т.к. учитывается первое выпадение 000 или 11, то можно действительно считать, что броски прекращаются сразу после выпадения одной из этих последовательностей.

[Gelhenec]

TOTAL в сообщении #145112 писал(а):

$P$ --- искомая вероятность (что $000$ встретится раньше, чем $11$)
$P_0$ --- искомая вероятность, если первым выпал $0$
$P_1$ --- искомая вероятность, если первым выпал $1$

$P=\frac{1}{2} \left( \frac{1}{2} +\frac{1}{2} P_1 \right)$
$P=\frac{1}{2} P_0 +\frac{1}{2} P_1$
$P_1=\frac{1}{2} P_0$

Откуда $P=\frac{3}{10}$

Объясните, пожалуйста, как получаются 1-е и 3-е равенства

[Gelhenec]

Люди добрые, скажите как получается первая формула

[Deggial]

Gelhenec, замечание за искусственный подъем темы бессодержательным сообщением.

[green5]

Странно, численно P гдето 0.428.
Мож кто найдет ошибку:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int brand()
{
  return rand()&1;
}
void test()
{
  int n1=0, n2=0;
  srand(time(0));
  int ii = 33*1000*1000;
  for(int i=0;i<ii;i++)
  {
    int a1 = brand();
    int a2 = brand();
    int a3 = brand();
    int z;
    while(1)
    {
      if(a1==1 && a2==1) { z=1; break; }
      if(a1==0 && a2==0 && a3==0) { z=2; break; }
      a1 = a2;
      a2 = a3;
      a3 = brand();
    }
    if(z==1) n1++;
    if(z==2) n2++;
  }
  printf("%f\n",(double)n2/n1);
}
int main(int ac,char *av[])
{
  int nn = av[1] ? atoi(av[1]):10;
  for(int n=0;n<nn;n++) test();
  return 0;
}

0.428754
0.428650
0.428485
0.428363
0.428855
0.428594
0.428613
0.428539
0.428444
0.428675

[Shadow]

Deggial в сообщении #924890 писал(а):

Странно, численно P гдето 0.428.
Мож кто найдет ошибку:

Почему печатаете $\dfrac{n_2}{n_1}$? Надо $\dfrac{n_2}{n_1+n_2}$ печатать - отношение числа успехов к общему числу испытаний
И поскольку в действительности $p_2=\dfrac{3}{10},p_1=\dfrac{7}{10}$ вот и получается у Вас $\dfrac{3}{7}\approx 0.4285$

[VAL]

Gelhenec в сообщении #924844 писал(а):

Люди добрые, скажите как получается первая формула

Внешняя $\frac12$ - это вероятность того, что два 0 выпадут раньше, чем две 1.
После этого с вероятностью $\frac12$ выпадет третий 0 и с такой же вероятностью 1.

[green5]

Нашли bug, спс.