Отрезки из повторяющихся исходов

[venco]

Количество строк разной длины с разной максимальной длиной повторений начинается так:
$\begin{matrix}1\\ 0 & 2 \\ 0 & 2 & 2 \\ 0 & 2 & 4 & 2 \\ 0 & 2 & 8 & 4 & 2 \\ 0 & 2 & 14 & 10 & 4 & 2\end{matrix}$

До длины 4 это совпадает с A329860, но дальше начинаются расхождения, и полностью этой таблицы в OEIS нет.

[Yadryara]

Dmitriy40, Вы на PARI делали? Можно на код взглянуть?

Чего голову-то морочить, переходя к $600$ бросков, если ещё о $6$ не все договорились. Для $6$ бросков всего-то $64$ варианта. Нужно взять их и все перечислить.

$max=1$

010101

101010

$2$ варианта.


$max=2$

001001
001010
001011
001100
001101
011001
011010
011011
010010
010011
010110
010100

110110
110101
110100
110011
110010
100110
100101
100100
101101
101100
101001
101011

$24$ варианта.


$max=3$

000100
000101
000110
000111
011100
011101
010001
001110
001000
011000
010111

111011
111010
111001
111000
100011
100010
101110
110001
110111
100111
101000

$22$ варианта.


$max=4$

000010
000011
011110
010000
001111

111101
111100
100001
101111
110000

$10$ вариантов.


$max=5$

000001
011111

111110
100000

$4$ варианта.


$max=6$

000000

111111

$2$ варианта.

Итого : $2+24+22+10+4+2 = 64$ варианта.

[mihaild]

Там нельзя просто удваивать - есть последовательности, в которых максимальная длина как нулей, так и единиц, $6$, и такие последовательности мы посчитаем дважды. Например строк, в которых ни нули, ни единицы не встречаются подряд, всего две, а в которых не встречаются подряд только нули - $\approx 2^{416}$. И даже последовательностей, в которых максимальное число одинаковых цифр подряд равно $10$, в $1.62$, а не в $2$ раза, меньше чем последовательностей, в которых максимальное число идущих подряд нулей $10$.

[provincialka]

Надеюсь, я правильно запрограммировала вычисление длин отрезков...

Используется синтаксис C

lll<-NULL
n<-600; m<-1000000
for (i in 1:m) {
  sample(0:1,n,rep=TRUE)->x
  diff(which(c(x,-1)!=c(-1,x)))->ll
  lll<-c(lll,max(ll))
}
table(lll)
 

Пересчитала ещё раз, данные немного поменялись. Вот частота максимумов из миллиона:

$$\begin{matrix} 5& 6 & 7 & 8 & 9 & 10 & 11 &12 &13&14 &... \\ 22& 7585 & 83872 & 216251 & 250036 & 189880 & 117287& 65298 &34544 &17466 & ... \end{matrix}$$

и так до 32

[Yadryara]

mihaild в сообщении #1531999 писал(а):

Там нельзя просто удваивать - есть последовательности, в которых максимальная длина как нулей, так и единиц, $6$, и такие последовательности мы посчитаем дважды.

Вот я привёл все $64$ варианта для $6$-ти бросков. Что-то я там посчитал неправильно?

На всякий случай обращаю внимание, что нижняя группа(отделённая пустой строкой) для каждого максимума является инверсией соответствующей верхней строки. Таким образом, для подсчёта вероятностей можно было рассмотреть не $64$ варианта, а $32$, но я для избежания привёл все.

Что-то я не посчитал? Что-то посчитал боле одного раза?

[Dmitriy40]

Yadryara
Странно что Вы не нашли A048003, она прямо сразу даёт Ваши $P(n,k)$, в частности $P(6,1 \ldots 6)=(2, 24, 22, 10, 4, 2)$ там с 16-й позиции.

[Yadryara]

Dmitriy40, так это не $P$. Через $P$ принято обозначать вероятности, то есть в нашем случае дроби. А числители это у нас $T$. Не забывайте, пожалуйста.

Ничего странного. Я же написал про инверсию. Так что я сразу стал искать устоявшиеся половинные значения $T$ — $1, 2, 5, 12, 28$

[Dmitriy40]

Yadryara в сообщении #1531998 писал(а):

Вы на PARI делали? Можно на код взглянуть?

Конечно, но там из-за особенностей PARI много лишнего:

nn=600; kk=6;
T=matrix(nn, kk); T[1,1]=1;
{rT(n,k)=
   if(k<0 || k>n, return(0));
   if(k==0 || k==n || n==0, return(1));
   2*rT(n-1,k)+rT(n-1,k-1)-2*rT(n-2,k-1)+rT(n-k-1,k-1)-rT(n-k-2,k);
}
for(n=2,kk+2, for(k=1,min(n,kk), T[n,k]=rT(n,k)););
for(n=kk+3,nn, T[n,1]=2*T[n-1,1]+1-2*1+1-T[n-1-2,1]; for(k=2,kk, T[n,k]=2*T[n-1,k]+T[n-1,k-1]-2*T[n-2,k-1]+T[n-k-1,k-1]-T[n-k-2,k]););
print(vecsum(T[nn-1,1..5])/2^nn*2.);

Разбил на два цикла потому что рекурсивная rT() слишком медленно работает при больших $n,k$. А выделил случай $k=1$ отдельно т.к. массивы начинаются с 1 и не стал усложнять себе задачу смещением индексов.

[mihaild]

Yadryara в сообщении #1532001 писал(а):

Что-то я там посчитал неправильно?

Я не знаю, что вы там хотели посчитать, поэтому не знаю и правильно ли вы это посчитали:)

Вообще, предлагаю договориться об обозначениях: $A(n, k)$ - число последовательностей длины $n$, не содержащих более $k$ нулей подряд; $B(n, k)$ - число последовательностей длины $n$, не содержащих более $k$ одинаковых цифр подряд, начинающихся с нуля; $P(n, k)$ - вероятность, что максимальное число нулей подряд в последовательности длины $n$ будет ровно $k$, $Q(n, k)$ - вероятность того, что максимальное число одинаковых цифр подряд в последовательности длины $n$ будет ровно $k$.

КО передает что $P(n, k) = \frac{A(n, k) - A(n, k - 1)}{2^n}$ и $Q(n, k) = 2\frac{B(n, k) - B(n, k - 1)}{2^n}$, так что думать достаточно о $A$ и $B$. Он же сообщает рекурренты: $A(n, k) = \sum\limits_{i = 0}^k A(n - i - 1, k) + [n \leq k]$ и $B(n, k) = \sum\limits_{i = 1}^k B(n - i, k)$. Дальше встает вопрос, как это посчитать руками, и мне кажется, что ответ - никак.

[Yadryara]

mihaild в сообщении #1532005 писал(а):

Я не знаю, что вы там хотели посчитать, поэтому не знаю и правильно ли вы это посчитали:)

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

Хорошо, ещё раз.

Я искал вероятность того, что ровно после $n$ бросков появится хотя бы один отрезок из одинаковых цифр с максимальной длиной ровно $m$ букв.

И расписал полную группу событий для случая $n=6$.

[mihaild]

Yadryara в сообщении #1532007 писал(а):

появится хотя бы один отрезок из одинаковых цифр с максимальной длиной ровно $m$ букв

Вот это плохо сформулирована. "хотя бы один отрезок с максимальной длиной" - что-то странное. Видимо, вы имеете в виду "появится хотя бы один отрезок с длиной $m$ и не появится ни одного с длиной $m + 1$".

[Yadryara]

mihaild в сообщении #1532008 писал(а):

Вот это плохо сформулирована. "хотя бы один отрезок с максимальной длиной" - что-то странное. Видимо, вы имеете в виду "появится хотя бы один отрезок с длиной $m$ и не появится ни одного с длиной $m + 1$".

Конечно!

mihaild в сообщении #1532005 писал(а):

$Q(n, k)$ - вероятность того, что максимальное число одинаковых цифр подряд в последовательности длины $n$ будет ровно $k$.

Я это сразу обозначил как $P(n, k)$ Зачем же переобозначать?

-- 18.09.2021, 18:58 --

provincialka, я не знаю C, но можете ли Вы заменить $600$ на $6$ и перезапустить программу?

-- 18.09.2021, 19:15 --

venco в сообщении #1531997 писал(а):

Количество строк разной длины с разной максимальной длиной повторений начинается так:
$\begin{matrix}1\\ 0 & 2 \\ 0 & 2 & 2 \\ 0 & 2 & 4 & 2 \\ 0 & 2 & 8 & 4 & 2 \\ 0 & 2 & 14 & 10 & 4 & 2\end{matrix}$

До длины 4 это совпадает с A329860, но дальше начинаются расхождения, и полностью этой таблицы в OEIS нет.

Полностью?? Конечно нет таблицы бесконечной длины.

Да и зачем она нужна, если есть A048004 и A048003, если уж охота возиться с бОльшими числами.

[venco]

Как оказалось, оба варианта (с потвором 1, и с любым повтором) эквивалентны и сводятся к разбиению натурального числа на натуральные слагаемые.

Для $n=600$ вероятности получить максимальный повтор $1..6$ равны:
$4.8198\cdot 10^{-181}, 8.6123\cdot 10^{-56}, 1.83646\cdot 10^{-22}, 2.76136\cdot 10^{-10}, 3.60578\cdot 10^{-05}, 0.00738934$

[provincialka]

Yadryara в сообщении #1532009 писал(а):

я не знаю C, но можете ли Вы заменить $600$ на $6$ и перезапустить программу?

Это не Си, это R. сейчас запущу.
Вот результат на миллион прогонов

$$\begin{matrix} 1& 2 & 3 & 4 & 5 & 6 \\ 31441& 374866 & 343248 & 156832 & 62197 & 31416 \end{matrix}$$

Для первого и последнего чисел точное значение $1000000\cdot 2^{-5}=31250$, так как в этих случаях состав последовательности вполне определяется первой выпавшей буквой.

[venco]

Я оценил ассимптотику и получил, что уже для 10000 бросков вероятность получить максимум 6 повторов $1.66722\cdot10^{-36}$