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

[provincialka]

Нашла в интернете такую историю:

Цитата:

Лектор дал студентам домашнее задание: подбросить монету 600 раз и записать последовательность О и Р (орлов и решек). Он предупредил их также, что если они попробуют просто написать случайную последовательность сами из головы, не подбрасывая, он это обнаружит. И действительно, в тех заданиях, что он собрал у студентов, в двух из них не было ни разу подряд шесть орлов или шесть решек - надежный знак того, что последовательность не случайная. Лектор вызывает к себе этих двоих студентов. Первый признается, что он действительно просто записал О и Р, как ему казалось случайным. Зато второй утверждает, что он на самом деле подбрасывал монету 600 раз и записывал за ней, но когда он увидел шесть орлов подряд, то подправил результат, потому что подумал, что учитель увидит эти шесть орлов подряд и решит, что последовательность не случайна.

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

Моделирование показало, что на 100 000 прогонов есть один с отрезком в 27 повторяющихся букв и ни одного, в котором их было бы максимум пять. Максимум 6 повторов бывало, но менее, чем в 1 проценте случаев. Из миллиона прогонов было 38, в которых максимальная длина отрезка равна 5. Но, конечно, в исходной истории ни миллиона, ни даже 100 000 студентов у преподавателя нет.

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

[mihaild]

ИМХО разве что в виде "оценить асимптотику" (=найти модуль максимального собственного значения, он правда нецелый).

[Yadryara]

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

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

Может быть всё-таки появится отрезок из одинаковых букв с максимальной длиной ровно $m$ букв?

Ибо далее в тексте(болд мой) максимум неоднократно упоминается:

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

Моделирование показало, что на 100 000 прогонов есть один с отрезком в 27 повторяющихся букв и ни одного, в котором их было бы максимум пять. Максимум 6 повторов бывало, но менее, чем в 1 проценте случаев. Из миллиона прогонов было 38, в которых максимальная длина отрезка равна 5.

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

Но что-то достаточно простого решения не просматривается

Ну так это же не самая простая комбинаторная задача. Пусть возьмут для начала не $600$, а хотя бы $6$ бросков.

Смогут ли найти такие вероятности?

$P( 6, 1) = \frac2{64}$

$P( 6, 2) = \frac{24}{64}$

$P( 6, 3) = \frac{22}{64}$

$P( 6, 4) = \frac{10}{64}$

$P( 6, 5) = \frac4{64}$

$P( 6, 6) = \frac2{64}$

[Yadryara]

Ещё повычислял и нашёл: A048004

Это числители искомых вероятностей. А знаменатели $2^{n-1}$.

Посчитано до $n=140$. То есть для $140$ бросков.

[provincialka]

Можно и про максимальное спросить, но я думала, что это сложнее. Хотела посчитать, что появится хотя бы 6 подряд.

Но я уже вижу, что задачка не для ТВ. Можно дать в статистике.

[Dmitriy40]

Если не требовать точного равенства $m$, то надо просто просуммировать: $\sum\limits_{i=m}^n P(n, i)$.
Но если вопрос о вероятности невыпадения строки длиной $m$ при $n$ бросках, то достаточно просуммировать $\sum\limits_{i=0}^{m-1} P(n, i)$ (вероятности выпадения всех строк короче $m$).
Для $n=600, m=6$ вероятность невыпадения составляет $0.01472889277458 \approx 1.47\%$, не так уж мало. Интересно почему у Вас получилось 38 из миллиона и 0 из ста тысяч.
Считалось пару секунд программой по формуле из OEIS (правда писал программу полчаса).

[mihaild]

Dmitriy40, у вас $P(n, i)$ это вероятность получить длиннейшую подстроку длиной ровно $I$?
Тогда вторая сумма должна быть от нуля (ну а вдруг орел не выпадет ни разу?), и вместе с первой давать $1$.

Вероятность того, что из $600$ бросков максимальная серия из орлов будет иметь длину ровно $n$ - на картинке.

[Dmitriy40]

mihaild
Да, $P(n,i)$ взял от Yadryara, он привёл её для $n=6$ и всех $i$, и она равна $P(n,k)=2T(n,k)/2^n$, где $T(n,k)$ берётся из A048004 (удвоение потому что не различаем последовательности орлов и решек).
График на картинке совпадает с моими вычислениями (если числа на нём удвоить), для $i=0 \ldots 15$: $0.000000$, $0.000000$, $0.000000$, $0.000000$, $0.000071$, $0.014658$, $0.167613$, $0.432357$, $0.500063$, $0.380954$, $0.234866$, $0.130238$, $0.068502$, $0.035095$, $0.017746$, $0.008915$.
Сумму можно и от нуля, согласен, поправлю, это логичнее, но численно она не изменится ($P(n,0)=0$).

-- 18.09.2021, 16:23 --

Интересно связано ли $0/10^5$ и $38/10^6$, что явно выбивается из вероятностей, с артефактами генератора случайных чисел при прогонах у provincialka ...

[Yadryara]

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

она равна $P(n,k)=2T(n,k)/2^n$, где $T(n,k)$ берётся из A048004
(удвоение потому что не различаем последовательности орлов и решек).

Да, не различаем. Но я вместо удвоения предложил наоборот вдвое уменьшить знаменатель, взяв $P(n,k)=\dfrac{T(n,k)}{2^{n-1}}$

Обнаружил, что там в первой же рекуррентной формуле есть ошибки.

Можно ли взглянуть на числители $T(600,1)$, ..., $T(600,6)$?

[venco]

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

Интересно связано ли $0/10^5$ и $38/10^6$, что явно выбивается из вероятностей, с артефактами генератора случайных чисел при прогонах у provincialka ...

Это вы просто неправильно посчитали. Я вчера считал, и получилось похоже на результат provincialka, но лень было вбивать матрицы. В OEIS, кстати, последовательности не было.

[Dmitriy40]

Yadryara
Мне удвоение показалось более логичным, а результат тот же.
Числители $T(600,1\ldots 15)$:

(Длинные числа!)

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

k= 1:289117532242004794657842939580523992192206081574833651083505729789364385249494747835588176048973824211799073812844695893338800
k= 2:700807927515209319703919656110904985720190564273728927174449393318844544118832456311147693474287827223544034590280514266879002491356850375432550518244301303196
k= 3:1104328042755954386320824567216377485763072493389864968788783627789917668277472692529025908780612163573893802542538816626102673973609068657811347934560841187329583701473956
k= 4:147074933269000430744730232888347281954754442423944038651420598928646041661597978060547563153220821207473952363371199598114353577172981806080972506876322789924495061432074210008
k= 5:30411808902652962586922105368190882705618102801009965823210890366003342948804331065813223236122586004662523653525648565692496030820301476522766621402751077196480252433600351153719
k= 6:347755923814266600087641996025482293071765314357120818677434698385772606400923265457843065007263143733323810942246434251114523849066507676339505260704260597474486272370233614578025
k= 7:897035112429980066950886430172585529641880706166863688853610486891124891861145297478069715246826966432638884313647796652292853154029319921243531674741482012482020986013900386006423
k= 8:1037509359853699222040353323704397314138432215441528828639057443671479731266891734834513499947748012166213012827161776163176869972745620508504930918585570242412029417780826633293177
k= 9:790386659931054161018560953395902682409839816179057191828066843229019020955589488910645561846788652240648589258080285685236562007488091388739578817539677394011672471007730088222855
k=10:487290342914887567428268511868035526656860026750957159447842643023559362907340024708997514622334574306716359108584612841571947409512289005908806999351222667496516301012058231344997
k=11:270212370245824109525880386625616244419136746555055568186534012918165267431685075373760635060656140402154628091932677261316034777201297207291301759966817452516688201145234276433339
k=12:142125204153675917427277447640626050100633446822547466245321639996481621514925162082809280157672080111385130501957996420347138940213342137807411188205494146445796146775778645471712
k=13:72813512208775219553727472775524630674212436409612012408075499664237249718806701391113105809542530959304970540713367770404446481973869601929612981320978067697971892293827186417745
k=14:36818717372373582792083664785126123020650317495237734239578845912770100831212089383723392572464268949439791583470330616330710337578114063116409204104835980693673497355280428619439
k=15:18496838427342109535636893493783811856324684140304453218076263462836839454431902728956911984357243762717253408227412013983840953724033283300552115706277645729324911178137445626624

Формулу использовал эту:

T(n, k) = 0 if k < 0 or k > n, 1 if k = 0 or k = n, 2T(n-1, k) + T(n-1, k-1) - 2T(n-2, k-1) + T(n-k-1, k-1) - T(n-k-2, k) otherwise.

Выборочно проверил свои вычисления для $T(140,5)$ и для $T(9,1\ldots9)$, с A048004 совпало, а $2T(5,1\ldots6)$ совпадает с Вашими $P(6,1\ldots6)$ (упс, тут походу кто-то промахнулся ...).

UPD.
Если для $n=600$ бросков брать $T(599,k)$, то вероятность невыпадения ни орлов ни решек для $m=k=6$ будет $P(n=600,k=6)=2T(n-1,k)/2^n=0.00742539835$, вдвое меньше, но всё равно $0.74\%$ совсем не мало, а числители:

(Оффтоп)

k=1:178684461669052552311410692812805706249615844217278044703496837914086683543763273909969771627106004287604844670397177991379600
k=2:381021570197524370637754439000355763949305217635445908446727754310840075438347239287935348301289401694097123559060648555249301028413006316160667800385698504208
k=3:572914415620408720232339277607681809689464836616171695959620082625931279761720552193837272387090263413952599486598803061491218396703197536317415961023841993079259142305472
k=4:74811181970850491869003470628141404025905445069572371825162007304910622385027170657001892747919785697423919866665894066874384804368034286468175364642414140924046747184629820064
k=5:15331091276366590442542406338966429499009375704080403237569180273349762069301855329475291406153486733025476891457691548405934872226008812150278452419896223393068489583295848426783
k=6:174514583189981439384123435758901816894789005868993690129358201291968381171833269985343355352061323732425246103503403474127074359415802545272921067540827959122638616134046019531487

[Yadryara]

Dmitriy40, Спасибо.

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

Формулу использовал эту:T(n, k) = 0 if k < 0 or k > n, 1 if k = 0 or k = n, 2T(n-1, k) + T(n-1, k-1) - 2T(n-2, k-1) + T(n-k-1, k-1) - T(n-k-2, k)

А разве не

$$T(n, k) = 2T(n-1, k) + T(n-1, k-1) - 2T(n-2, k-1) + T(n-k, k-1) - T(n-k-1, k)$$

?

[venco]

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

Ещё повычислял и нашёл: A048004

Это числители искомых вероятностей. А знаменатели $2^{n-1}$.

Это число повторяющихся единиц, а нужно ещё и нули учитывать.

[Yadryara]

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

В OEIS, кстати, последовательности не было.

Какой именно не было?

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

Это число повторяющихся единиц, а нужно ещё и нули учитывать.

Учитывал.

Давайте сверим $P(6,1)$, ..., $P(6,6)$ Свои значения я привёл. У Вас какие значения вероятностей получились?

[Dmitriy40]

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

А разве не

$$T(n, k) = 2T(n-1, k) + T(n-1, k-1) - 2T(n-2, k-1) + T(n-k, k-1) - T(n-k-1, k)$$

?

Эта не даёт Ваши $P(6,\ldots)$ вообще, ни удвоенных, никаких. Плюс тут $T(3,1)=3$ вместо $4$ (100,010,001,101). Значит наверное неправильная.

-- 18.09.2021, 17:21 --

venco похоже намекает что множества для 1 и для 0 частично пересекаются и потому удвоение сильно завышает вероятности.

-- 18.09.2021, 17:37 --

Давайте на примере $n=3$ разберём:
$P(3,0)=0:\varnothing$
$P(3,1)=2: 010_2, 101_2$
$P(3,2)=4: 001_2, 011_2, 100_2, 110_2$
$P(3,3)=2: 000_2, 111_2$
Общая сумма совпадает, $8$.
В A048004 строка $T(2,\ldots)=1,2,1$ - тоже совпадает после удвоения.

Для $n=4$:
$P(4,0)=0:\varnothing$
$P(4,1)=2: 0101_2, 1010_2$
$P(4,2)=8: 0010_2, 0011_2, 0100_2, 0110_2, 1001_2, 1011_2, 1100_2, 1101_2$
$P(4,3)=4: 0001_2, 0111_2, 1000_2, 1110_2$
$P(4,4)=2: 0000_2, 1111_2$
Тоже совпадает с $2T(3,\ldots)$ из A048004.

venco
Не вижу проблемы с удвоением. Поясните плиз?