Comments 87
… теперь я знаю как у меня получалось писать код все это время…
Хорошо было бы добавить среднее количество символов для строки «ааа» и «авс», чтобы увидеть, насколько проще набрать первую из них.
Или я вообще не правильно понял условия?
(Позже попробую перечитать ещё раз, с учётом того, что вы там что-то исправили в статье. Я, признаюсь, не вникал в ваши формулы и код.)
Единственное изменение в статье — это замечание в самом начале о том. что считать будем нажатия по клавишам а не время в секундах.
Вот бесконечный поток символов, в котором я считаю количество вхождений подстрок, что однозначно определяет вероятности вхождения подстрок, что однозначно определяет мат-ожидание встретить ту или иную строку. И эти величины для любых подстрок одинаковой длины равны.
(Всё ещё без перечитывания статьи отвечаю, возможно, у автора введены дополнительные ограничения, меняющие решение, которые я не уловил. Я условия задачи принимаю «классические», как, например, в https://ru.wikipedia.org/wiki/Теорема_о_бесконечных_обезьянах .)
Хотя бы элементарно P(строка встретилась первый раз в позиции 2) = P(строка не встретилась в позиции 1) * P(строка не встретилась в позиции 2 | строка не встретилась в позиции 1) — и второй множитель в общем случае не равен P(строка не встретилась в позиции 2).
Например, если нам гарантируется, что на одной монетке орел и решка при бросках чередуются, а вторая — честно случайная, то вероятность того, что на 1й орел выпадет раньше, чем на второй, равна 1/4 [при первом броске на 1й орел, на 2й решка] + 1/8 [при первом броске на 1й орел, на 2й орел; при втором броске на 2й решка] = 3/8, а вероятность того, что на 2й орел выпадет раньше 1/4 [при первом броске на 1й решка, на 2й орел] — т.е. вероятности отличаются, хотя вероятность получить орла в каждой позиции одинакова.
Эти лишние невозможные отрезки нельзя учитывать. Потому что обезьяна никогда не сможет напечатать строку из трех символов всего одним нажатием. Если такие пары исключить, то в бесконечной строке получается меньше отрезков (которые можно учитывать) между двумя подряд идущими включениями подстроки, а значит матожидание будет больше.
(Допускаю, что ошибаюсь, не понимая дополнительных условий в вашей задаче и опираясь на решение в Википедии. Я всё ещё не перечитал вашу статью, так что не тратьте на меня время пока.)
Ну вот приводили пример с монетками. Пусть наши строки будут "aaa" и "baa", а алфавит только {a,b}. Тогда, только если "aaa" в потоке встречается не на первом месте, то перед ним будет буква "b", а значит "baa" встречается почти всегда раньше, чем "aaa" в любом потоке. Так как мы считаем до первого вхождения — то мат. ожидание меньше.
Еще раз, ваша ошибка в том, что вы заменяете мат. ожидание до первого события на обратную величину к частоте события. Это верно только для Пуассоновских потоков. Поток в нашей задаче таким не является. Потому что для строки "aaa" событие может произойти 2 раза подряд, а для строки "abc" — не может никогда.
А ничего что вы при этом ввели новое условие — "а алфавит только {a,b}."
Ничего подобного в вашем примере нет. По мне это как сравнивать булево и десятичное сложения (т.е. одно из них как бы становится "умножением"))).
И да, я знаю что такое мат-ожидание… И на абсолютно случайных последовательерстях вероятность встретить паттерн «abc» раньше, чем паттерн «aaa» на самом деле равна 0, честно-честно (при этом естественно не считая «aaaa» за 2 вхождения строки «aaa»).
Хотя может объясните мне, почему вы все же считаете «abcd» за 2 разных вхождения — строки «abc» и строки «bcd» — потому что вы это на самом деле делаете… Но два раза «aaa» никак низя… :)
Маленький алфавит — это для наглядности. Но это условие нисколько не влияет на то, что строки "aaa" и "baa" точно так же равновероятны. Но в этом примере очевидно, что "baa" встречается раньше.
Точно так же, но это менее очевидно "abc" для всего алфавита всречается раньше "aaa". Интуиция тут такая — когда набрана первая буква "a" из "abc" можно или набрать вторую букву, или снова набрать "a" или набрать какой-то нерелевантный мусор. Для строки "aaa" можно только набрать вторую букву или какой-то мусор. Варианта остаться с одной набранной буквой — нет. Тут любая ошибка делает так, что на конце текущей последовательности вообще нет правильно набранного текста. Для "abc" есть вариант сделать не серьезную ошибку, которого для "aaa" нет.
Вот вам — поэкспериментируйте. https://jsfiddle.net/zwnfft73/4/
В alf задается сколько букв в алфавите, в iter — сколько итераций делать. Для "aaa" ответ всегда больше чем для "abc".
вы не правы в том смысле что если вероятностно (а не интуитивно) посмотреть на "a" и какой-то мусор, и "b" и какой-то мусор, то оно в профиль одинаково (и тут размер алфавита важен, только по стольку поскольку он не равен двум).
Остальные вопросы вы (и комментаторы ниже, судя по смыслу) решили проигнорировать… Ну да ладно, я к сожалению вышку на уровне профессора не знаю, чтобы вам по полочкам разложить, типа нутром понимаю, но как собак — ни скажу)))
Простите, дискуссия вышла из под контроля. Если вы продублируете вопросы, я на них с удовольствием отвечу.
Да, это противоречит интуиции, но все приведенные тут в комментариях симуляции показывают одно и то же. Мат. ожидание для разных строк не одинаково, как и выведено в посте математически.
вы вероятно не про-то, я говорил не про статью, а лишь про способ притянуть в качестве объяснение пример с булевым алфавитом. И только...
Пример с булевым алфавитом разрушает довод "строки встречаются в бесконечном потоке равновероятно => первое вхождение на одинаковом расстоянии". Для больших алфавитов нет такого простого и очевидного примера, к сожалению. Но даже для всех 26 символов получается вот что (для строк "aaa" и "baa"): Перед первой строкой "aaa" почти в одном их 26 случаев идет символ "b", а значит вторая строка встречается раньше в 1/26 всех потоков. Обратного эффекта нет, поэтому появляется перекос.
Пример с булевым алфавитом разрушает довод "строки встречаются в бесконечном потоке равновероятно => первое вхождение на одинаковом расстоянии".
для строк "aaa" и "baa" — т.е. вы сознательно совершаете ту же ошибку снова применяя булевы значения (уже не на булевом алфавите). Хотя размер алфавита в общем-то вы совершенно правильно связали с эффектом названым вами "перекосом".
Что например для строк "aaa" и "baz"? Т.е. во первых не используя чисто булев алфавит, а во вторых исключив (помоему важнейший здесь) другой параметер — одна из строк начинается или оканчивается подстрокой другого паттерна.
Что здесь где перед чем чаще будет встречаться?
Вот выше в ветке вы сами предложили не путать теплое с мягким (я про ваше "неверно посчитается как 2 вхождения строки", потому как интересно только первое вхождение), здесь же, думается мне, вы делаете это сами (я про теплое с мягким).
Попытаюсь объяснить: дело в том, что вы здесь путаете частотные и вероятностные характеристики. Потому как "первое вхождение на одинаковом расстоянии" у них действительно равновероятно находится на том же самом месте.
У вас проблема в чем: например вы генерируете грубо говоря 26 * N последовательностей и говорите, что частный случай где "baa" находится чаще раньше чем "aaa" — есть факт.
При этом делая две ошибки (даже три на самом деле):
- во первых, грубо говоря "обезьяна печатает 1 раз" т.е. тупо случайная последовательность символов одна единственная (а не 26 и не 26*N); соответственно и вероятности что нахождения первой "aaa" в сравнении с первой "baa" (что наоборот) одинаковы.
- во вторых, ваш подход к объяснению с коротким алфавитом как бы не совсем "честен", ибо используете вы частный случай, где одна подстрока содержится в другой, но главное на самом деле практически исключаете здесь бесконечную последовательность случайных величин (ряда) с достаточной плотностью распределения;
- ну и в третьих, последовательности для поиска просто настолько коротки, что при частотном анализе все это и вырождается в частный случай...
Еще раз, это не про сабж конкретно, т.к. сама статья имхо замечательная, и насколько осилил мат-часть, даже (наверно) правильно все доказано (по теме мат-ожидания уже лет двадцать ничего не делал, да и мозг плавится после тяжелого трудового дня))).
Я вам только про "неправильность" что ли вашего примера и некоторые ваши замечания и выкладки про вероятности и смешивания последней с мат-ожиданием. И ни за что другое :)))
Примерно в 1.16 раз быстрее обнаруживается строка 'abc', чем 'aaa' на потоке случайно распределённых символов 'abcdefg', действительно.
Согласно формуле, для строки «aaa» нужно 18278 нажатий в среднем, а для «abc» — 17576. Разница будет еще заметнее, если ограничится алфавитом только из трех букв (39 против 27).
Для 'AAA' (с алфавитом 'ABC'):
alxr@loginsin ~ $ avr=0 ; for((cnt=0;cnt<500;++cnt)) ; do I=0 ; S="" ; while(true) ; do CHR="\x"`printf "%x" $[(RANDOM%3) + 65]`; CC=`printf $CHR` ; S="${S}${CC}" ; if [ "${S}" == "A" -o "${S}" == "AA" -o "${S}" == "AAA" ] ; then if [ "${S}" == "AAA" ] ; then break ; fi ; else S="" ; fi ; I=$[I+1] ; done ; avr=$[avr+I] ; echo "$cnt: $I" ; done ; echo $[avr/500]
...
37
alxr@loginsin ~ $ avr=0 ; for((cnt=0;cnt<500;++cnt)) ; do I=0 ; S="" ; while(true) ; do CHR="\x"`printf "%x" $[(RANDOM%3) + 65]`; CC=`printf $CHR` ; S="${S}${CC}" ; if [ "${S}" == "A" -o "${S}" == "AB" -o "${S}" == "ABC" ] ; then if [ "${S}" == "ABC" ] ; then break ; fi ; else S="" ; fi ; I=$[I+1] ; done ; avr=$[avr+I] ; echo "$cnt: $I" ; done ; echo $[avr/500]
...
37
При перепроверках числа примерно одинаковые. Можно и упростить, но хотелось увидеть сами строчки из буковок :)
Если сделать так:
alxr@loginsin ~ $ avr=0 ; for((cnt=0;cnt<50;++cnt)) ; do I=0 ; S="" ; while(true) ; do CHR="\x"`printf "%x" $[(RANDOM%26) + 65]`; CC=`printf $CHR` ; S="${S}${CC}" ; if [ "${S}" == "A" -o "${S}" == "AB" -o "${S}" == "ABC" ] ; then if [ "${S}" == "ABC" ] ; then break ; fi ; else S="" ; fi ; I=$[I+1] ; done ; avr=$[avr+I] ; echo "$cnt: $I" ; done ; echo $[avr/500]
То алфавит будет 'A...Z'. Ждать придется подольше, но числа действительно где-то рядом с обозначенными:
Для 'AAA'
0: 11896
1: 20309
2: 74986
3: 2185
^C
Для 'ABC'
0: 15595
1: 13412
2: 11241
3: 2308
^C
В случае с алфавитом 'A..Z' строка 'AAA' действительно появляется значительно реже
Из утверждения
среднее время до первого появления строки 'abc' меньше среднего времени до первого появления строки 'aaa'
не следует утверждение
строка 'abc' в среднем появляется раньше строки 'aaa'.
Автор доказывает совершенно корректно первое утверждение. Второе же, безусловно, является неверным. Если вы делаете ставку на то, какая строка появится первой, то ваши шансы строго 50 на 50. Но если вы платите за каждое появление символа по одной монете, то ставить надо на строку 'abc'. Ждать её в среднем придётся меньше.
Чтобы прочувствовать разницу между этими утверждениями, вот вам ещё пара условных примеров из жизни. Представьте остановку, на которую приходят по определённому расписанию маршрутка и автобус.
Ситуация 1
И автобус, и маршрутка ходят с одинаковыми интервалами, но маршрутка едет всегда непосредственно перед автобусом. Тогда среднее время ожидания автобуса и среднее время ожидания маршрутки равны, но когда бы вы ни пришли на остановку, первой появится маршрутка.
Ситуация 2
Пусть теперь автобус ходит вдвое реже, но появляется непосредственно перед каждой второй маршруткой. Шансы увидеть первым автобус или маршрутку уравнялись, но среднее время ожидания автобуса вдвое больше.
Это все равно что после черного надо ставить на красное, а после красного на черное, потому что такие комбинации встретятся раньше чем «черное черное» или «красное красное».
Тысячи людей так думали и проигрывали в казино огромные деньги. А ТУТ автор взял и изобрел денежную машину! Ну удачи ему!
Это все равно что изобрести вечный двигатель. ХИТРЫХ формул и механизмов вечных двигателей тысячи, только не один так и не заработал!
Почитайте апдейт к статье.
В чем здесь ошибка? После того как автомат построен случайное блуждание никак не зависит от назначенных ребрам символов. Или вы тоже сомневаетесь в правдивости первого утверждения в статье? Его доказательство хорошо расписано в Википедии (https://ru.wikipedia.org/wiki/Теорема_о_бесконечных_обезьянах).
Конечно, в задаче об обезьянах всеми этими особенностями пренебрегают, т.к. это лишь «лирическое» описание мат-модели, есть в ней и покруче расхождения с реальностью (вечная жизнь мартышек, вечный ресурс печатных машинок, вечный интерес печатать, вечный надсмотрщик, проверяющий текст на совпадения и т.д.)
На импровизированной полке расположились в ряд шесть стопок отпечатанного текста, каждая около фута толщиной. Бэйнбридж не без усилия поднял одну из стопок и положил её перед профессором Мэллардом.
— Результат деятельности шимпанзе А, которого мы зовем Биллом, — сказал он просто.
"Оливер Твист, сочинение Чарлза Диккенса," — увидел профессор Мэллард. Он прочитал первую страницу рукописи. Потом вторую. Потом лихорадочно перелистал всю рукопись до конца.
— Вы хотите сказать, — спросил он, — что этот шимпанзе написал…
— Слово в слово и запятая в запятую, — ответил Бэйнбридж. — Янг, мой дворецкий, и я сверили её с изданием, которое есть в моей библиотеке. Как только Билл кончил, он сразу начал печатать социологические труды итальянца Вильфредо Парето. Если он и дальше будет работать в таком темпе, к концу месяца закончит и это.
— И все шимпанзе… — с трудом произнес побледневший профессор Мэллард. — И все они…
— О да, все они пишут книги, которые, по моим расчетам, должны быть в Британском музее. Проза Джона Донна, кое-что из Анатоля Франса, Копан Дойль, Гален, избранные пьесы Сомерсета Моэма, Марсель Пруст, мемуары покойной Марри Румынской и еще монография какого-то доктора Вилея о болотных травах Мэна и Массачусетса. Я могу подвести итог, Мэллард: с тех пор как четыре недели назад я начал этот эксперимент, ни один из шимпанзе не испортил буквально ни одного листа бумаги.
> все символы набираются равновероятно (с вероятностью 1/26).
Что-то тут не так. Даже если взять русский алфавит, то уже будет 33 буквы, а если тот, что был до революции, то 35. Ну и вставки на французском языке ещё нужно добавить, а это ещё 26 букв. Плюс знаки препинания и прочее.
var str1 = «чч»;
var str2 = «чк»;
var c1 = 0;
var c2 = 0;
var rnd = new Random();
for (var i = 1; i < 100000; i++)
{
var str = "";
while (str.IndexOf(str1) < 0 && str.IndexOf(str2) < 0)
{
if (rnd.Next(2) == 0)
str += 'к';
else
str += 'ч';
}
if (str.IndexOf(str1) >= 0)
c1++;
if (str.IndexOf(str2) >= 0)
c2++;
}
Console.WriteLine("{0} {1}", c1, c2);
http://csharppad.com/gist/d29770ed3b4179d1ee7691a592b2c99a
var str1 = «чч»;
var str2 = «чк»;
var c1 = 0;
var c2 = 0;
var n1 = 0;
var n2 = 0;
var rnd = new Random();
for (var i = 1; i < 100000; i++)
{
var str = "";
while (str.IndexOf(str1) < 0 && str.IndexOf(str2) < 0)
{
if (rnd.Next(2) == 0)
str += 'к';
else
str += 'ч';
}
if (str.IndexOf(str1) >= 0)
{
c1++;
n1 += str.Length;
}
if (str.IndexOf(str2) >= 0)
{
c2++;
n2 += str.Length;
}
}
Console.WriteLine("{0} {1}", c1, n1);
Console.WriteLine("{0} {1}", c2, n2);
http://csharppad.com/gist/b5b51c377ff9ab0101d93470aceb3542
Проблема в том, что вы считаете количество нажатий до первой встречи строки str1 при том что строка str2 ни разу не встретилась (и наоборот для второй строки). Это совсем другие величины. Можно этот пример довести до абсурда и считать сразу для всех четырех возможных строчек. Тогда цикл while у вас всегда завершится на второй итерации, что, согласитесь, странно. И вы подсчитаете для каждой строки сумму из двоек. Более того у вас при этом ответ не сойдется с текущей вашей программой.
Надо или разделить на 2 параллельных цикла отдельно для str1 и str2, или гнать цикл while пока не встретятся ОБЕ строки, запоминая где первый раз каждая из них попалась.
Если посадить сто тысячь обезьян то примерно половина из них сначала наберет ЧК, а вторая половина ЧЧ. При этом они наберут примерно одинаковое количество букв. В чем проблема в моей программе?
Проблема в том, что вы проводите другой эксперимент. Вы выгоняете обезьян из-за машинки когда они напечатали или одно или другое. В исходной же задаче обезьяна печатает пока не наберет только одну заданную строку. Этот эксперимент для двух разных строк дает разные результаты.
Да, вероятности встретить сначала "чч" или "чк" одинаковы.
Я не говорил нигде про вероятность получить сначала одно или другое. Я считал среднее количество нажатий.
Кстати, из того, что матожидание одной величины больше матожидания второй величины никак не следует, что первая окажется больше второй в более чем половине случаев.
Если обезьяна уже набрала ЧЧ, я не считаю сколько ей еще надо нажать клавиш чтобы в той же строке набрать ЧК. А вы как раз ЭТО считаете.
А именно это и надо считать.
Измените ваш код для работы только с ОДНОЙ строкой. Мы же считаем как тяжело получить одну строку, именно ту, которую выбрали? Потом запустите этот код для разных строк "чч" и "чк" и вы получите разные результаты.
Вот вы никак не понимаете разницу между вопросами:
1) из двух строк выберете ту, которая встретится раньше в случайном тексте (правильный ответ — неважно)
2) выберете строку так, чтоб для ее печати потребовалось в среднем меньше символов (ответ — "чк" лучше "чч")
На первый взгляд кажется, что если в среднем требуется меньше символов, то и встречаться первый раз строка должна раньше других. Но это не так.
Да из 100 тысяч обезьян примерно половина напечатает сначала "чч" а примерно половина "чк" (если выгонять их когда случится одно из двух). Но если первые 50 тысяч заставить печатать пока они не наберут "чч", а вторые 50 тысяч — пока они не наберут "чк", то первые обезьяны напечатают более длинные тексты.
Да из 100 тысяч обезьян
Моя литературная память не может промолчать...
Я молчу. Это мой общий ключ. Теперь придется переупаковывать все базы данных. Тёмный Дайвер подносит трубку к Чингизу. Тот почему-то смотрит на меня почти с таким же негодованием, как и на Тёмного Дайвера. Но голос сохраняет спокойным:
— Открыл первый шифр? Хорошо. Теперь набирай ключ… он простой… ламерский…
Вот оно в чем дело!
— Это фраза, первая буква строчная, все остальные прописные. Пробелы значимы. В конце должна стоять точка. Набирай… и повторяй по буквам.
Чего он тянет…
Чингиз выдыхает и ледяным голосом произносит:
— Сорок тысяч обезьян в жопу сунули банан.
— Сергей Лукьяненко. "Фальшивые зеркала"
По автору AB будет на 1.5 раза легче набрать чем AA (при алфавите из 2 символов). Это было бы сразу заметно.
Автор считает мат. ожидание в НАБОРЕ строк и из этого делает вывод что АБ набрать быстрее.
А мы набираем всего ОДНУ строку и потом смотрим что встретилось раньше. И тут мат ожидание будет равным.
Эта программа считает не то — количество вхождений. Оно будет одинаковым.
Вот программа, которая считает то, про что в задаче и спрашивается — https://jsfiddle.net/zwnfft73/4/
Поиграйтесь прямо в браузере — результаты разные.
У меня ранее возникал вопрос, только в другой интерпретации, а именно: когда программа «Антиплагиат», в любом из институтов, потеряет свою целесообразность. Ведь при написании диплома, мало кто пишет на какую-нибудь новую тему, или исследует предметную область, ранее неизвестную человеку. Большинство использует книги, статьи интернета, лекции преподавателей (многие из этих лекции, были лекциями предыдущих преподавателей). И как скоро возникнет ситуация, что уже все предметные области расписаны на столько, что уже просто нечего будет написать.
Задача про обезьян и бесконечность