2014 dxdy logo

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

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


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


Посмотреть правила форума



Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Броски до заданного количества успехов
Сообщение10.04.2024, 11:26 


14/02/20
863
Пусть я бросаю монетку до того момента, как у меня выпадут $m$ орлов подряд. Сколько в среднем бросков мне понадобится?

Допустим, я хочу найти вероятность того, что мне потребовалось $n$ бросков ($n\geqslant m$, очевидно). Тогда последние из них - это $m$ орлов, это повлияет на вероятность, но с ними все ясно. Предыдущая обязана быть решка, их все отбросим. Очевидно, что в предыдущих не должно быть $m$ орлов подряд, этого будет достаточно. Но сколько таких комбинаций существует?

Обозначим $N_n$ количество комбинаций из $n$ нулей и единиц, скажем, в которой нет $m$ единиц подряд. Тогда можно составить милую рекуррентную формулу:

$N_n = N_{n-1} + N_{n-2} + ... + N_{n-m}$

В принципе, из этой формулы нужно получить нужное значение. В целом можно даже решить это линейное однородное разностное уравнение (интересно, что поскольку, очевидно, характер роста тут как минимум экспоненциальный, можно сделать вывод, что корни у характеристического уравнения все действительны, или нет?), только как его решишь, да и даже если решишь, ответ не будет слишком полезен (сумма $n$-ных степеней иррациональных чисел, дающая натуральные числа, не особо полезно).

С другой стороны, моделирование показывает, что зависимость в любом случае не какая-то простая... возможно, только так ответ и получается, и он будет "кривой". Что скажете?

 Профиль  
                  
 
 Re: Броски до заданного количества успехов
Сообщение10.04.2024, 11:38 
Заслуженный участник
Аватара пользователя


30/01/09
7060
artempalkin в сообщении #1635920 писал(а):
Пусть я бросаю монетку до того момента, как у меня выпадут $m$ орлов подряд. Сколько в среднем бросков мне понадобится?

artempalkin в сообщении #1635920 писал(а):
Что скажете?

Что-то мне припоминается, что случай $m=2$ тут на форуме был. Для начала попробуйте разобраться с таким упрощением условия.

 Профиль  
                  
 
 Re: Броски до заданного количества успехов
Сообщение10.04.2024, 11:41 


14/02/20
863
мат-ламер в сообщении #1635922 писал(а):
Что-то мне припоминается, что случай $m=2$ тут на форуме был. Для начала попробуйте разобраться с таким упрощением условия.

Да, тут я разобрался. Там даже характеристическое уравнение явно решается, то есть можно выписать красивый вид... или они как-то по-другому подходили? не скинете ссылку на тему, если есть?

 Профиль  
                  
 
 Re: Броски до заданного количества успехов
Сообщение10.04.2024, 11:55 
Заслуженный участник
Аватара пользователя


30/01/09
7060
artempalkin в сообщении #1635923 писал(а):
не скинете ссылку на тему, если есть?

https://dxdy.ru/topic156148.html

 Профиль  
                  
 
 Re: Броски до заданного количества успехов
Сообщение10.04.2024, 12:45 
Заслуженный участник
Аватара пользователя


13/08/08
14494
Не утерпел и упросил комп покидать монетку
m= 1 n=2.01
m= 2 n=6.00
m= 3 n=14.36
m= 4 n=30.02
m= 5 n=62.06
m= 6 n=126.07
m= 7 n=254.39
m= 8 n=500.98
Получается приближённое удвоение и чем дальше, тем приближённее :?:

(Оффтоп)

Код:
{\\ coin tosses up to m wins
for( m=1,8,
   n=0;
   for( j=1,100000,
     k=0;
     for( i=1,3000,
       if( random(2),k++,k=0 );
       if( k==m, n+=i;  break );
     );
   );
   printf("m=%2d n=%.2f\n",m,n/100000);
);
}

 Профиль  
                  
 
 Re: Броски до заданного количества успехов
Сообщение10.04.2024, 13:28 
Заслуженный участник
Аватара пользователя


16/07/14
9090
Цюрих
Тут проще без состояний. Пусть в текущей серии $0$ орлов, а нам нужно $m$. Пусть в среднем надо ждать $X_m$. У нас есть варианты: сразу решка; один орел, а потом решка; два орла, а потом решка; ..., $m - 1$ орлов, а потом решка; $m$ орлов. В первом варианте ждать еще $1 + X_m$, во втором $2 + X_m$ и т.д., вероятности каждого варианта тоже легко выписываются.

 Профиль  
                  
 
 Re: Броски до заданного количества успехов
Сообщение10.04.2024, 16:11 
Заслуженный участник


12/08/10
1676
gris в сообщении #1635936 писал(а):
Получается приближённое удвоение и чем дальше, тем приближённее

В вашем коде большая погрешность: неудачные последовательности считаются за 0 бросков, а их там больше 3000.

 Профиль  
                  
 
 Re: Броски до заданного количества успехов
Сообщение10.04.2024, 17:26 
Заслуженный участник
Аватара пользователя


13/08/08
14494
Null, спасибо. Согласен, что 3000 маловато для 8 и больше орлов подряд. Но для 7 погрешность не слишком большая, ведь вероятность, что до 3000 бросков не попадётся 7 орлов подряд пара тысячных процента и такие серии можно считать ошибкой эксперимента :-) . Для 8 орлов надо, конечно кидать монетку 5000 раз и на пятитысячном неудачном броске просто добавить 5028 к n.

 Профиль  
                  
 
 Re: Броски до заданного количества успехов
Сообщение10.04.2024, 20:37 
Заслуженный участник
Аватара пользователя


13/08/08
14494
Null, посмотрите, пожалуйста.

(Оффтоп)

Код:
{\\ coin tosses up to m wins
mmax=10;
ns=100000; \\number of tests
vm=vector(mmax);\\where we got m chickens in row for the first time
for( j=1,ns,
  m=1; \\we are waiting for m chickens in row
  i=0; \\throw number
  k=0; \\number of chickens in raw on the current throw
  while( m<mmax+1,
    i++;
    if( random(2),k++,k=0 );
    if( k==m, vm[m]+=i; m++ );
  );
);
for( i=1,mmax, printf("m=%2d n=%.2f\n",i,vm[i]/ns));
}


m= 1 n=2.00
m= 2 n=6.01
m= 3 n=14.02
m= 4 n=30.07
m= 5 n=62.28
m= 6 n=126.70
m= 7 n=255.62
m= 8 n=512.71
m= 9 n=1020.90
m=10 n=2043.50
m=11 n=4088.90
m=12 n=8171.17

 Профиль  
                  
 
 Re: Броски до заданного количества успехов
Сообщение11.04.2024, 07:44 
Заслуженный участник


12/08/10
1676
gris в сообщении #1635989 писал(а):
Null, посмотрите, пожалуйста.
При низких $m$ завышение получается почему-то. А при высоких занижение. Должно быть $2, 6, 14, 30, 62, 126, 254, 510, 1022, 2046$ Рандом кривой или где-то еще ошибка.

 Профиль  
                  
 
 Re: Броски до заданного количества успехов
Сообщение11.04.2024, 08:13 


16/09/23
27
В 1м приближении если p - вероятность успеха, то для получения n- успехов подряд нужно в среднем
m=1/(q*p^n)-1/q, где q=1-p

 Профиль  
                  
 
 Re: Броски до заданного количества успехов
Сообщение11.04.2024, 08:45 
Заслуженный участник
Аватара пользователя


13/08/08
14494
Null, ну на рандом не решусь даже коситься :-) . Отклонения бывают даже на миллионе тестов, но не систематические. Алгоритм вроде бы простой и длинные последовательности учитываются. Бывают и очень длинные (для 12 орлов отмечается и 110000, но очень редко) , но не настолько длинные и частые, чтобы влиять на второй знак после запятой. Но тревожно: где это влияние?
Хотя теория учитывает последовательности неограниченной длины и уменьшение в эксперименте естественно :?:

 Профиль  
                  
 
 Re: Броски до заданного количества успехов
Сообщение11.04.2024, 09:07 


26/08/11
2097
$E=2(2^m-1)$

Пусть $a_n$ - матожидание числа бросков до успеха, при уже выпавших $n$ орлов подряд. Нас интересует $a_0$
Пусть $a_0=x$.
Еще $a_n=\dfrac 1 2 (1+a_{n+1})+\dfrac 1 2 (1+a_0)$
Или
$a_{n+1}=2a_n-2-x$

Тоесть
$a_n=x-2(2^n-1)$

Ну и $a_m=0$

 Профиль  
                  
 
 Re: Броски до заданного количества успехов
Сообщение11.04.2024, 15:19 


14/02/20
863
Shadow в сообщении #1636031 писал(а):
$E=2(2^m-1)$

Пусть $a_n$ - матожидание числа бросков до успеха, при уже выпавших $n$ орлов подряд. Нас интересует $a_0$
Пусть $a_0=x$.
Еще $a_n=\dfrac 1 2 (1+a_{n+1})+\dfrac 1 2 (1+a_0)$
Или
$a_{n+1}=2a_n-2-x$

Тоесть
$a_n=x-2(2^n-1)$

Дааа, это, конечно, круто... Вроде бы формула подходит хорошо!

Единственное, я с теоретической точки зрения не совсем понимаю вот это вот:
Shadow в сообщении #1636031 писал(а):
$a_n=\dfrac 1 2 (1+a_{n+1})+\dfrac 1 2 (1+a_0)$

Здесь же речь идет о соотношении матожиданий... интуитивно смысл понятен, но теоретического основания не понимаю...

 Профиль  
                  
 
 Re: Броски до заданного количества успехов
Сообщение11.04.2024, 18:36 


26/08/11
2097
Ну, можно и так:

$E_0=0$

$E_{m+1}=E_m+1+\dfrac 1 2 [E_m+1+\dfrac 1 2(E_m+1+\ldots$

движок ругается, но скобок не закрываю, там бесконечная прогрессия

Думаю, смысл понятен - для того, чтобы достичь $m+1$ орлов, нужно сначала достичь $m$, сделать бросок, и, если не повезет начать все сначала.

Сумма геометрических прогрессий, да и вообще $E_{m+1}=E_m+1+\dfrac 1 2 E_{m+1}$

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

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



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

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


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

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