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

[Yadryara]

Dmitriy40 в сообщении #1532110 писал(а):

Вы сравнили друг с другом, всё сошлось, но назвали величины неправильно, это не максимум $k$, а ровно $k$. Ошибся venco, Вы с ним согласились, не поправили.

Ну что же, сутки прошли, уважаемый venco промолчал. Тогда я скажу.

А я вот не считал и не считаю, что venco здесь ошибся. Потому и не поправил. Обратите внимание, речь о максимумах идёт с самого первого поста. Я уже выделял болдом, сделаю это и сейчас.

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

Количество строк разной длины с разной максимальной длиной повторений начинается так:

$\begin{matrix} 2 \\ 2 & 2 \\ 2 & 4 & 2 \\ 2 & 8 & 4 & 2 \\ 2 & 14 & 10 & 4 & 2\\ 2 & 24 & 22 & 10 & 4 & 2\\ 2 & 40 & 46 & 24 & 10 & 4 & 2\\ 2 & 66 & 94 & 54 & 24 & 10 & 4 & 2\end{matrix}$

Да, о максимумах здесь речь снова идёт. Это наш знаменитый треугольник, то бишь удвоенные элементы матрицы $T(n, k)$ в программе.

Как мы его формируем? Допустим, вручную. Я в своё время вручную дошёл как раз до $8$-й строчки и только тогда заглянул в OEIS.

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

Вот встретилась у нас такая серия из $8$-ми бросков:

$$01100001$$

Какой столбец нам наращивать на $1$ ? У нас здесь есть и $0$, и $1$, и $00$, и $11$, и $000$, и $0000$. Да, подстрока из трёх нулей подряд тоже есть. Ответ: по подстроке максимальной длины, то есть $4$, то есть наращиваем $4$-й столбец. Всего таких серий(из $8$ бросков с максимальной длиной $4$) — $54$.

То есть для формирования треугольника, максимумы нам необходимы. Не обязательно при этом складывать те или иные его элементы между собой. Случаи, когда это нужно делать, лучше оговаривать отдельно. А именно про сумму сказано не было:

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

Для $n=600$ вероятности получить максимальный повтор $1..6$ равны:

То есть надо использовать элементы первых $6$-ти столбцов $600$-й строки. Но не складывать их.

Dmitriy40 в сообщении #1532113 писал(а):

Да уже ничего, все разногласия в цифрах устранены,

Вот здесь mihaild был не согласен:

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

Где-то лишняя двойка, должно быть в два раза меньше (в варианте, когда мы требуем чтобы ни нуль ни единица не повторялись больше 6 раз).

[Nemiroff]

provincialka в сообщении #1531934 писал(а):

Например, найти вероятность того, что при $n$ бросках появится отрезок одинаковых букв длины $m$ (в тексте $n=600, m=6$). Но что-то достаточно простого решения не просматривается (может, просто устала к концу недели )

Кидали уже ссылки? Невозможно читать тему.
https://math.stackexchange.com/question ... lli-trials
https://math.stackexchange.com/question ... ect=1&lq=1

[Dmitriy40]

А, вот в каком смысле. Тогда да, в $T[]$ конечно же случаи когда максимальная длина ровно $m$. И тогда и Вы и venco правы. А я неправильно понял ваши слова.
Я то больше ориентировался на вопрос ТС с какой вероятностью не выпадет $m=6$ вообще, для ответа на него и надо просуммировать вероятности $m=0\ldots5$. А для ответа на вопрос "какова вероятность выпадения не длиннее $m=6$" просуммировать надо $m=0\ldots6$ — вот это я и считал "получить максимальный повтор $6$" из слов venco, т.е. повтор любой длины не больше шести, разница к чему именно относить слово "максимальный".

Yadryara
Признаю, ошибся в понимании слов, соответственно и моё напоминание было ошибочным.

[wrest]

(Dmitry40, о хеше. Или кеше.)

Dmitriy40 в сообщении #1532098 писал(а):

Модификация кода не слишком сложна, но или замедлит расчёты (если делать сдвигом матрицы) или потребует аккуратности (если реализовать кольцевую структуру) или нужно найти в PARI готовую удобную структуру (типа хэш дерева).

Я давеча боролся с рекурсивными вычислениями тут: post1403180.html#p1403180
Вкратце, сперва создаётся карта (словарь)
T=Map()
Далее, начинается функция rT
rT(n,k)={
my(res=0);
Сперва идут тривиальные проверки, затем проверяется вычислено ли уже значение для n,k и если да, то возвращается оно
if(mapisdefined(T,[n,k],&res),  return(res));
Если нет, то значение вычисляется (рекурсивно) и кладется в карту
res=rT(n,k-1)+rT(n-k,k); и т.п. - тут собсно рекурсивное вычисление/формула
mapput(T,[n,k],res); - кладем к карту
return(res)} - возвращаем вычисленное
Т.е. вместо матрицы T - карта T.
Вдруг пригодится...

[zykov]

provincialka в сообщении #1531934 писал(а):

Есть ли смысл давать эту задачку как вероятностную? Или использовать исключительно для моделирования?

Стандартная задача на Марковские процессы. Легко точно решается.
Вот аналогичную задачу я на другом форуме расписывал:
http://e-science11.ru/viewtopic.php?f=4&t=1013
Решение: http://e-science11.ru/viewtopic.php?p=2661#p2661

[Yadryara]

zykov в сообщении #1532295 писал(а):

Стандартная задача на Марковские процессы. Легко точно решается.

Ну раз это легко, то приведите, пожалуйста, решение здесь. Как получить, например, вот эти числа?

$P(600, 1) \approx \quad 4.819840\cdot 10^{-181}$

$P(600, 2) \approx \quad 8.612305\cdot 10^{-56}$

$P(600, 3) \approx \quad 1.836463\cdot 10^{-22}$

$P(600, 4) \approx \quad 2.761356\cdot 10^{-10}$

$P(600, 5) \approx \quad 3.605779\cdot 10^{-05}$

$P(600, 6) \approx \quad 7.389340\cdot 10^{-03}$

Первое число — да, можно:

$$P(600, 1) = \frac{1}{2^{599}} \approx 4.819840\cdot 10^{-181}$$

[zykov]

Не вижу нигде точного определения P.
Приведу для примера решение другой задачи. Это решение легко адаптировать для поиска другой схожей вероятности.

Задача:
Симметричную монету бросают 600 раз. Найти вероятность того, что где-то хотя бы раз встретится последовательность из 6 или более орлов подряд.

Конечный автомат имеет 7 состояний. Перед первым броском он находится в состоянии 1.
Для состояний 1-6, если выпал орел, переходим в следующее состояние, если выпала решка, переходим в состояние 1.
Для состояния 7, всегда переходим обратно в 7.

Мы попадаем в состояние 7, только если где-то встретили подряд 6 орлов. И потом остаёмся в нём независимо от выпавшей монеты.
Вероятность прехода автомата не зависит от предистории. Т.е. имеем Марковскую цепь.
Сопоставим автомату матрицу вероятностей переходов:
$ M=\begin{bmatrix} 1/2 & 1/2 & 1/2 & 1/2 & 1/2 & 1/2 & 0 \\ 1/2 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1/2 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1/2 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1/2 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1/2 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1/2 & 1 \end{bmatrix} $
Если перед броском вероятности распределения по этим 7 состояниям записать в вектор, то вероятности после броска будут соответствовать вектору полученному умножением матрицы $M$ на исходный вектор.
Перед первым броском вектор вероятностей $v_0$ имел 1 в первом элементе и нули в остальных.
После 600 бросков вектор вероятностей равен $v_{600}=M^{600} v_0$.

Последний элемент вектора $v_{600}$ даёт вероятность того, что где-то встретилась последовательность минимум из 6 орлов.
Загоняем эту матрицу в wxMaxima и считаем.
Получаем точный ответ:

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

4022418636660881789783286947111076312977335907792792569794035475713533858444831211039568114143044106104073170561072216072243940215650975123138577666921686806972099126185501174029
/
4052261297735344686047273304385899561535592023674254785152009111026028136145418111718463914987406049109568248643848426935932764722081811824108276205189417663145685354884286644224
 

Что примерно равно $0.9926355536127098$.

[tonven]

Берём стандартный генератор random(0, 1), по априорному верный в данном ЯП.

const
  n = 600; // Длина проверяемой последовательности
begin
  var pMen := new integer[n]; // П-сть человека
  var pRan := new integer[n]; // П-сть ЯП
  loop 1000 do
  begin
    var z := 0; // Отклонение от случайности
    for var i := 0 to n - 1 do // Сначала нарабатываем статистику
    begin
      (pMen[i], pRan[i]) := (random(2), random(2));
      z += sqr(pMen[i] - pRan[i]);
    end;
    z.Print;
  end;
end.

Получаем результаты для ориентировки:

288 299 276 289 293 318 298 307 303 310 301 301 287 306 303 304 292 300 304 308 288 279 303 300 299 294 297 296 312 305 318 295 307 297 298 281 288 299 295 309 297 303 313 284 299 283 296 319 301 327 302 286 279 316 321 287 294 308 288 289 299 308 300 292 286 293 313 298 300 310 301 304 315 304 309 296 302 315 291 316 296 312 312 317 284 292 299 299 312 310 315 307 301 297 310 312 291 288 297 315 291 303 296 315 289 284 304 326 293 307 312 285 300 295 285 287 327 297 309 311 319 286 290 301 276 292 299 320 286 293 283 285 297 289 299 296 330 303 300 326 298 278 298 279 308 313 333 279 315 282 312 303 302 290 289 303 319 280 294 305 317 314 291 308 293 312 308 289 297 294 299 297 298 306 298 286 282 294 317 298 300 294 292 274 270 300 301 314 294 300 321 273 289 312 277 312 284 311 303 299 316 307 298 289 290 303 326 296 299 314 309 310 288 300 282 299 299 285 299 282 290 293 282 323 310 279 283 278 299 293 305 308 287 314 310 305 304 276 300 295 293 282 276 313 276 296 298 289 280 292 277 297 314 290 306 319 289 302 314 300 278 334 289 300 302 289 302 303 283 314 283 299 287 321 326 318 318 287 300 302 293 313 284 305 319 280 296 307 305 280 287 299 287 304 282 299 315 322 298 313 304 291 280 290 294 299 306 300 305 292 318 307 292 296 288 291 283 322 304 295 302 307 318 291 286 313 295 298 301 282 281 314 291 304 286 308 312 298 283 286 317 281 305 298 299 302 285 277 283 289 301 310 295 295 314 296 304 299 297 317 298 294 294 287 306 309 289 317 309 295 290 291 301 277 297 303 298 308 296 302 300 283 305 283 296 314 276 320 313 281 275 294 299 298 314 310 284 294 305 295 292 306 307 311 300 297 287 276 307 281 294 307 288 295 299 300 306 299 306 294 296 301 291 296 288 298 300 309 293 293 295 327 299 298 292 303 293 307 330 318 320 297 302 302 299 281 288 310 301 280 283 313 297 307 290 303 296 288 284 310 277 271 299 289 296 307 299 307 321 297 292 287 305 302 284 300 287 281 304 314 304 283 296 305 306 318 299 294 300 294 300 301 277 304 303 307 300 305 313 289 275 286 307 292 275 294 292 324 303 305 272 320 305 304 296 283 316 286 295 318 300 296 294 292 317 303 327 284 306 292 302 299 310 321 312 283 282 308 292 297 308 309 300 288 305 293 295 296 298 295 301 310 309 278 292 301 309 305 290 280 295 304 320 285 290 289 298 305 286 293 299 308 309 306 282 294 296 299 294 304 298 288 311 302 308 308 293 322 306 315 299 302 308 288 294 307 302 303 300 304 289 296 290 284 305 310 313 291 321 308 312 300 303 296 286 284 272 292 275 307 293 305 289 274 312 321 312 319 281 311 299 297 302 310 279 324 292 296 297 326 312 272 308 303 286 300 305 312 309 303 290 295 296 293 307 306 306 308 316 289 294 301 303 291 290 306 286 290 287 298 288 288 305 303 304 288 293 312 306 306 299 292 289 310 292 305 321 319 283 290 291 307 290 307 323 306 296 275 283 298 318 292 304 307 292 310 311 296 293 309 283 303 304 306 272 285 306 313 289 300 296 322 305 303 277 285 308 333 303 313 293 316 312 297 311 298 296 322 309 314 297 315 316 302 291 299 297 288 289 325 294 274 303 307 287 293 307 284 315 305 300 295 277 283 301 285 300 309 280 291 308 303 303 311 294 302 293 288 299 300 311 311 300 303 265 300 313 286 297 310 299 299 287 282 303 307 291 285 286 312 303 303 319 313 305 315 291 285 297 303 297 288 335 295 287 314 310 290 301 301 300 284 296 297 294 303 310 311 314 283 311 312 305 290 293 298 295 277 284 290 309 295 286 296 321 290 295 303 313 277 300 292 305 316 296 304 296 291 294 301 289 288 305 290 289 306 285 289 293 300 301 292 313 289 301 304 291 305 288 267 307 299 305 284 297 305 314 298 281 300 304 311 304 316 315 291 307 304 292 288 290 304 313 309 305 312 330 296 295 288 309 318 302 299 312 280 307 296 314 303 280 318 307 308 311 321 302 289 276 298 277 298 306 293 301 312 293 312 309 305 291 290 294 301 322 299 303 310 286 300 299 306 296 292 298 315 299 286 302 304 313 314 310 312 285 317 307 288 288 308 301 312 287 295 303 293 303 305 286 300 283 296 295 286 307 303 313 296 305 308 298 289 326 290 314 303 294 282 294 282

Теперь заменяем pMen на "человеческую". Если z сильно отличается от $300\pm30$, то студент халявничал.

[zykov]

zykov в сообщении #1532376 писал(а):

Задача:
Симметричную монету бросают 600 раз. Найти вероятность того, что где-то хотя бы раз встретится последовательность из 6 или более орлов подряд.

Аналогично можно обсчитать задачу:
Симметричную монету бросают 600 раз. Найти вероятность того, что где-то хотя бы раз встретится последовательность из 6 или более ОДИНАКОВЫХ ЗНАЧЕНИЙ подряд.
Видимо эта задача, которую имел ввиду ТС.

Так же строим автомат с 12 состояниями и матрицу 12x12. Возводим в степень 600, умножаем на такой же вектор и получаем точную вероятность:

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

2074682972685611213143545186572415632123877646547683685067198039991713414238280345700359424061912513514745275920033001894751117424087966664428750777240506174444819523676747299833343
/
2074757784440496479256203931845580575506223116121218449997828664845326405706454073199853524473551897144098943305650394591197575537705887653943437417056981843530590901700754761842688
 

Примерно равно $0.9999639419331517 = 1 - 3.605806684825463\;10^{-5}$

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

$P(600, 5) \approx \quad 3.605779\cdot 10^{-05}$

Видимо соответсвует этому P(600, 5).

[Dmitriy40]

Нет, соответствует этому (сумме справа):

Dmitriy40 в сообщении #1532107 писал(а):

P(600,5)=3.605779071267587 e-5 vs Sum(P(600,1...5))=3.605806684824211 e-5

[Yadryara]

zykov, Спасибо.

zykov в сообщении #1532376 писал(а):

Не вижу нигде точного определения P.

Ну так смотреть надо внимательнее. Уже столько раз это здесь обсудили.

Если мы говорим о решении задачи, то должно быть не соответствие, а точное равенство.

$$P(600, 1) + P(600, 2) + P(600, 3) + P(600, 4) + P(600, 5) \approx 3.605806684824211\cdot 10^{-5}$$

Однако ж имеются отличия, начиная с 13-го знака:

$3.605806684824211$

$3.605806684825463$

-- 23.09.2021, 03:16 --

zykov, хотя, если Вашу дробь аккуратно посчитать, то сходятся эти самые первые $16$ знаков.

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

Да, видимо, абсолютно совпадают результаты. Работает и такая версия программы:

nn=600;kk=6;T=matrix(nn,kk);
{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=1,kk+1, T[n,1]=1; for(k=2,min(n,kk), T[n,k]=rT(n-1,k-1)); );
print();print("   ",2^(nn-1)-vecsum(T[nn,1..5]));print();print();print("   ",2^(nn-1));print();

Выдает отдельно числитель и знаменатель Вашей дроби.