Броски до заданного количества успехов

[artempalkin]

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

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

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

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

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

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

[мат-ламер]

artempalkin в сообщении #1635920 писал(а):

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

artempalkin в сообщении #1635920 писал(а):

Что скажете?

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

[artempalkin]

мат-ламер в сообщении #1635922 писал(а):

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

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

[мат-ламер]

artempalkin в сообщении #1635923 писал(а):

не скинете ссылку на тему, если есть?

https://dxdy.ru/topic156148.html

[gris]

Не утерпел и упросил комп покидать монетку
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);
); 
}

[mihaild]

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

[Null]

gris в сообщении #1635936 писал(а):

Получается приближённое удвоение и чем дальше, тем приближённее

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

[gris]

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

[gris]

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

[Null]

gris в сообщении #1635989 писал(а):

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

При низких $m$ завышение получается почему-то. А при высоких занижение. Должно быть $2, 6, 14, 30, 62, 126, 254, 510, 1022, 2046$ Рандом кривой или где-то еще ошибка.

[vacsol]

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

[gris]

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

[Shadow]

$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$

[artempalkin]

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)$

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

[Shadow]

Ну, можно и так:

$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}$