Про такие слова в статье есть информация, но уже ближе к концу. Рекуррентное соотношение в том виде, в каком оно дано в начале, для fuf строить нельзя, вы правы
Вероятность при этом можно определить как матожидание периода выпадения благоприятного исхода
В конце вы предложили нормальное определение, через отношение. С ним я согласен. Но вот с 17/26^4 я согласиться не могу, это неправильный ответ, и в статье сказано почему. Количество событий в числителе просто не такое, проверьте те же рассуждения хотя бы для строк длиной 8, для них можно получить точный ответ на листке бумаги, это 5*26^4-1. Единицу отнимать - обязательно, потому что она соответствует строке с двумя вхождениями плохого слова. Я не усложняю решение, это вы пытаетесь его упростить, при этом допускаете ошибку в рассуждениях. Пожалуйста, ознакомьтесь с содержанием статьи ещё раз, спасибо!
Определение вероятности выглядит совершенно иначе, в нём не участвует бесконечный поток символов. Так или иначе, вы повторили распространённую ошибку, связанную с числом 17. В статье объяснено, почему этот ответ неверный. В комментариях к статье есть более подробные объяснения.
Блин, не сразу заметил, что это сообщения от двух разных людей. То то я и думал, что-то не стыкуется немного стиль оформления и размышления) Мне нужно быть внимательнее
Я затупил, извиняюсь, там действительно возведение в степень. Попробую объяснить, почему возведение в степень даёт неточный ответ. Формулу возведения в степень вы, я полагаю, взяли из схемы Бернулли (https://ru.wikipedia.org/wiki/Схема_Бернулли) как частный случай. Для того, чтобы схема Бернулли работала, у вас должна быть последовательность независимых событий. Цитирую: результат очередного эксперимента не должен зависеть от результатов предыдущих экспериментов. В случае же, когда вы движетесь по конкретному слову и проверяете его подслова, события являются зависимыми. Например, после прочтения слова FUCK, следующим словом для проверки будет UCK* - т.е. 100% не FUCK. Вероятность следующего события зависит от предыдущего события. Т.е. не соблюдены необходимые условия примения формулы. Надеюсь так яснее. Ещё раз извиняюсь за свой затуп в прошлом комментарии. Если говоришь кому-то, что он не прав, самому лучше не ошибаться :)
Нам известна вероятность встретить хотя-бы раз слово FUCK в строке.
Неизвестна, это именно та вероятность, которую я искал в статье, но допустим. Кажется вы поставили задачу "найти вероятность встретить FUCK ровно один раз". Её можно решать предложенным вами подходом, но очень сложно.
Мы можем (можем же?) посчитать вероятность встретить слово FUCK два раза в строке
Наверное? Повторюсь, кажется очень сложным. А вообще, согласно приведённой схеме, для того, чтобы посчитать вероятность вхождения ровно один раз, мы должны посчитать вероятность вхождения ровно два раза. Это кажется контринтуитивным, как будто решаем более сложную задачу ради более простой. Думаю, что такой путь никуда нас не приведёт.
Проблема в том, что для умножения вероятностей применяется лишь в конкретных случаях. Но это даже не важно, потому что вы, скорее всего, имели ввиду умножение на 17, а не возведение в 17-ю степень, то есть сумму вероятностей (это же подтверждает ваш ответ, не совпадающий с тем, что дала бы формула). Почти та же самая формула рассмотрена в статье, в разделе 2 про аппроксимацию. Под статьёй, в комментариях, было приведено множество дополнительных аргументов в пользу того, что аппроксимация неточная. Ваша же конкретная формула ошибочна по той же причине - вы складываете вероятности событий, которые пересекаются. В этом случае необходимо вычитать вероятности пересечения. Нельзя просто взять и умножить на 17, это так не работает :)
private static final String ETALON = "2143";
private static final int K = 5, N = 10;
public static void main(String[] args) {
// K ^ N
long kn = 1;
for (int i = 0; i < N; i++) {
kn *= K;
}
long count = 0;
for (long i = 0; i < kn; i++) {
// Format string with 0 padding.
String str = Long.toString(i + kn, K).substring(1);
if (str.contains(ETALON)) {
count++;
}
}
System.out.println(count + " / " + kn);
}
У вас вышло 109375 / 9 765 625. Точный ответ, если я не ошибся при вычислении на телефоне (код напишу уже утром) - 109225 / 9 765 625. То есть чуть-чуть меньше. И это легко проверяется полным перебором в программе. Точность вероятностной проверки не позволит вам доказать правильность вашей формулы, потому что погрешность вычисления получается больше, чем ошибка формулы.
Вы же сами знаете, что такое вероятность? Беседа зашла в тупик. Отвечаю последний раз. У нас есть вероятностное пространство, состоящее из всех строк длины 10. Это пространство - конечно. Возможные исходы - это подмножества данного вероятностного пространства. Вероятности исходов равны числу элементов в них, делëному на число элементов в вероятностном пространстве. Исход, который нас интересует - конкретное подмножество строк. Мы можем программно вычислить и само подмножество, и его размер. Всё, что я написал - это основы основ. Я не понимаю, в чём вы хотите меня убедить, не зная базовых определений. Пожалуйста, не будьте настолько самоуверенным чтобы даже не допускать собственной неправоты. Подумайте ещё раз перед ответом. Повторите теорию. И тогда поймëте, где вы ошиблись. EDIT: забыл сказать. Распределение, естественно, равномерное
И вы НИКОГДА не пролучите точное значение из программы. Для точного значения требуется сделать БЕСКОНЕЧНОЕ число попыток
Вы серьёзно? Это даже не смешно. То есть я не могу в программе сгенерировать ВСЕ строки длиной 10 из алфавита, в котором 5 символов? Так то могу. Вы же знаете, что такое дискретное распределение? Кажется самое время подтянуть матчасть
Не могли бы вы в коде сгенерировать все возможные строки по 1 разу, чтобы получить точное значение вместо приблизительного? Чтобы сравнивать наверняка, без погрешностей? Кажется, текущие значения достаточно малы, чтобы программа могла быстро со всем справиться. Спасибо!
Смотрите, если последним прочитанным кортежем был ??FU, то CK?? дальше читать "нельзя", если FUCK хотим исключить, а если последним был ?FUC, то "нельзя" читать K???. Вероятности разные для разных букв. Матрица как раз описывает вероятности перехода из одного состояния в другое.
Никакого автомата нет, просто обработка идет сразу 4 символа за раз. И все.
Автомат есть, но неявный. Есть пары кортежей, которые дают слово FUCK, есть которые не дают. Эти пары отвечают за разные рёбра в автомате, и за разные состояния, в том числе ими как-то должны определяться конечные состояния.
Но прикол в том, что вероятность этого зависит от того что придет в ЭТОЙ четверке и предыдущей
Всё верно, именно поэтому я написал, что вероятность там условная. И именно поэтому ваша формула неверна.
Просто подставьте конкретные значения в вашу формулу и сравните с настоящим значением, которое можно получить (к примеру) полным перебором, или другим аналитическим способом (главное быть аккуратным).
И получаеться в итоге обычная функция (1 - А)^N.
Эту формулу легко опровергнуть. Если подставить N = 0, то мы должны получить вероятность, равную 0. У вас получается вероятность, равная 1. Если же подставить N = 1 (это число кортежей, верно?), то должно получиться 1/26^4. Верность данного значения, полагаю, никто не будет ставить под сомнение. Отсюда следовало бы, что A = 1-1/26^4. Далее, для N = 2 ваша формула даёт вероятность (1 - A)^2 = 1/26^8. Данная вероятность уже ни при каких условиях не может быть верной, поскольку она бы означала, что есть только одно слово из всех. Если попробовать повторить те же рассуждения с вашей более ранней формулой вида (1 - 1/26^4)(1 - A)^N, то возникают те же проблемы при подстановке 0, 1, 2 в качестве N. Проверка - важный этап вывода формулы, она может указать на закравшиеся ошибки.
В статье я привёл значения, которые можно проверить с помощью ручки-бумаги. Это (например) вероятности для строки длины 0, 4 и 8. Они равны, соответственно, 0, 1/26^4 и 5/26^4 - 1/26^8. Моё предложение - подберите формулу, которая работала бы хотя-бы на этих трёх вариантах. Если вы считаете, что эти 3 числа неверны, то прошу обосновать, в чём на ваш взгляд у меня ошибка. Спасибо!
Насколько я вижу, вы тоже построили конечный автомат, в котором символы для перехода - это четвёрки. Далее вы попробовали использовать простую формулу, возводящую число в степень, для оценки вероятности, но дело в том, что вероятность на каждом шаге - условная, именно поэтому необходимо возводить в степень матрицу, а не одно число. Тут же буквально цепь Маркова. Это если совсем вкратце. На самом деле я затрудняюсь кратко объяснить, почему возведение числа в степень - ошибочно, а долгое объяснение - и писать будет долго. Могу предложить поиграться с более короткими строками. Дело в том, что при любом правильном подходе формулы должны получиться одни и те же, ну или как минимум тождественные, это было показано в статье. Если это не так - нужно искать ошибку в рассуждениях
Предлагаю вам подставить в ваши формулы конкретные небольшие значения n/m/k и проверить, совпадают ли они с истиным решением (которое легко получить перебором на листочке)
Как правило не входит, это дополнительное ограничение, которое задаётся только явным образом
Про такие слова в статье есть информация, но уже ближе к концу. Рекуррентное соотношение в том виде, в каком оно дано в начале, для fuf строить нельзя, вы правы
В конце вы предложили нормальное определение, через отношение. С ним я согласен. Но вот с 17/26^4 я согласиться не могу, это неправильный ответ, и в статье сказано почему. Количество событий в числителе просто не такое, проверьте те же рассуждения хотя бы для строк длиной 8, для них можно получить точный ответ на листке бумаги, это 5*26^4-1. Единицу отнимать - обязательно, потому что она соответствует строке с двумя вхождениями плохого слова.
Я не усложняю решение, это вы пытаетесь его упростить, при этом допускаете ошибку в рассуждениях. Пожалуйста, ознакомьтесь с содержанием статьи ещё раз, спасибо!
Определение вероятности выглядит совершенно иначе, в нём не участвует бесконечный поток символов.
Так или иначе, вы повторили распространённую ошибку, связанную с числом 17. В статье объяснено, почему этот ответ неверный. В комментариях к статье есть более подробные объяснения.
Блин, не сразу заметил, что это сообщения от двух разных людей. То то я и думал, что-то не стыкуется немного стиль оформления и размышления) Мне нужно быть внимательнее
В такой формулировке гораздо понятнее, спасибо!
Да, этой формуле мне противопоставить нечего, она выглядит совершенно верной.
Я затупил, извиняюсь, там действительно возведение в степень.
Попробую объяснить, почему возведение в степень даёт неточный ответ. Формулу возведения в степень вы, я полагаю, взяли из схемы Бернулли (https://ru.wikipedia.org/wiki/Схема_Бернулли) как частный случай. Для того, чтобы схема Бернулли работала, у вас должна быть последовательность независимых событий.
Цитирую: результат очередного эксперимента не должен зависеть от результатов предыдущих экспериментов.
В случае же, когда вы движетесь по конкретному слову и проверяете его подслова, события являются зависимыми. Например, после прочтения слова FUCK, следующим словом для проверки будет UCK* - т.е. 100% не FUCK. Вероятность следующего события зависит от предыдущего события. Т.е. не соблюдены необходимые условия примения формулы. Надеюсь так яснее.
Ещё раз извиняюсь за свой затуп в прошлом комментарии. Если говоришь кому-то, что он не прав, самому лучше не ошибаться :)
Неизвестна, это именно та вероятность, которую я искал в статье, но допустим. Кажется вы поставили задачу "найти вероятность встретить FUCK ровно один раз".
Её можно решать предложенным вами подходом, но очень сложно.
Наверное? Повторюсь, кажется очень сложным.
А вообще, согласно приведённой схеме, для того, чтобы посчитать вероятность вхождения ровно один раз, мы должны посчитать вероятность вхождения ровно два раза. Это кажется контринтуитивным, как будто решаем более сложную задачу ради более простой. Думаю, что такой путь никуда нас не приведёт.
Проблема в том, что для умножения вероятностей применяется лишь в конкретных случаях. Но это даже не важно, потому что вы, скорее всего, имели ввиду умножение на 17, а не возведение в 17-ю степень, то есть сумму вероятностей (это же подтверждает ваш ответ, не совпадающий с тем, что дала бы формула).
Почти та же самая формула рассмотрена в статье, в разделе 2 про аппроксимацию. Под статьёй, в комментариях, было приведено множество дополнительных аргументов в пользу того, что аппроксимация неточная.
Ваша же конкретная формула ошибочна по той же причине - вы складываете вероятности событий, которые пересекаются. В этом случае необходимо вычитать вероятности пересечения. Нельзя просто взять и умножить на 17, это так не работает :)
Ответ тот же, что я дал вчера: 109225 / 9765625
У вас вышло 109375 / 9 765 625.
Точный ответ, если я не ошибся при вычислении на телефоне (код напишу уже утром) - 109225 / 9 765 625.
То есть чуть-чуть меньше. И это легко проверяется полным перебором в программе.
Точность вероятностной проверки не позволит вам доказать правильность вашей формулы, потому что погрешность вычисления получается больше, чем ошибка формулы.
Вы же сами знаете, что такое вероятность? Беседа зашла в тупик.
Отвечаю последний раз. У нас есть вероятностное пространство, состоящее из всех строк длины 10. Это пространство - конечно.
Возможные исходы - это подмножества данного вероятностного пространства. Вероятности исходов равны числу элементов в них, делëному на число элементов в вероятностном пространстве.
Исход, который нас интересует - конкретное подмножество строк. Мы можем программно вычислить и само подмножество, и его размер.
Всё, что я написал - это основы основ. Я не понимаю, в чём вы хотите меня убедить, не зная базовых определений. Пожалуйста, не будьте настолько самоуверенным чтобы даже не допускать собственной неправоты. Подумайте ещё раз перед ответом. Повторите теорию. И тогда поймëте, где вы ошиблись.
EDIT: забыл сказать. Распределение, естественно, равномерное
Так она на этих 3х вариантах работает? А на остальных?
Вы серьёзно? Это даже не смешно. То есть я не могу в программе сгенерировать ВСЕ строки длиной 10 из алфавита, в котором 5 символов? Так то могу.
Вы же знаете, что такое дискретное распределение? Кажется самое время подтянуть матчасть
Не могли бы вы в коде сгенерировать все возможные строки по 1 разу, чтобы получить точное значение вместо приблизительного? Чтобы сравнивать наверняка, без погрешностей?
Кажется, текущие значения достаточно малы, чтобы программа могла быстро со всем справиться. Спасибо!
Смотрите, если последним прочитанным кортежем был ??FU, то CK?? дальше читать "нельзя", если FUCK хотим исключить, а если последним был ?FUC, то "нельзя" читать K???. Вероятности разные для разных букв. Матрица как раз описывает вероятности перехода из одного состояния в другое.
Автомат есть, но неявный. Есть пары кортежей, которые дают слово FUCK, есть которые не дают. Эти пары отвечают за разные рёбра в автомате, и за разные состояния, в том числе ими как-то должны определяться конечные состояния.
Всё верно, именно поэтому я написал, что вероятность там условная. И именно поэтому ваша формула неверна.
Просто подставьте конкретные значения в вашу формулу и сравните с настоящим значением, которое можно получить (к примеру) полным перебором, или другим аналитическим способом (главное быть аккуратным).
Эту формулу легко опровергнуть. Если подставить
N = 0, то мы должны получить вероятность, равную 0. У вас получается вероятность, равная 1. Если же подставитьN = 1(это число кортежей, верно?), то должно получиться1/26^4. Верность данного значения, полагаю, никто не будет ставить под сомнение. Отсюда следовало бы, чтоA = 1-1/26^4.Далее, для
N = 2ваша формула даёт вероятность(1 - A)^2 = 1/26^8. Данная вероятность уже ни при каких условиях не может быть верной, поскольку она бы означала, что есть только одно слово из всех.Если попробовать повторить те же рассуждения с вашей более ранней формулой вида
(1 - 1/26^4)(1 - A)^N, то возникают те же проблемы при подстановке 0, 1, 2 в качестве N.Проверка - важный этап вывода формулы, она может указать на закравшиеся ошибки.
В статье я привёл значения, которые можно проверить с помощью ручки-бумаги. Это (например) вероятности для строки длины 0, 4 и 8. Они равны, соответственно,
0,1/26^4и5/26^4 - 1/26^8. Моё предложение - подберите формулу, которая работала бы хотя-бы на этих трёх вариантах.Если вы считаете, что эти 3 числа неверны, то прошу обосновать, в чём на ваш взгляд у меня ошибка. Спасибо!
Насколько я вижу, вы тоже построили конечный автомат, в котором символы для перехода - это четвёрки. Далее вы попробовали использовать простую формулу, возводящую число в степень, для оценки вероятности, но дело в том, что вероятность на каждом шаге - условная, именно поэтому необходимо возводить в степень матрицу, а не одно число. Тут же буквально цепь Маркова. Это если совсем вкратце.
На самом деле я затрудняюсь кратко объяснить, почему возведение числа в степень - ошибочно, а долгое объяснение - и писать будет долго. Могу предложить поиграться с более короткими строками.
Дело в том, что при любом правильном подходе формулы должны получиться одни и те же, ну или как минимум тождественные, это было показано в статье. Если это не так - нужно искать ошибку в рассуждениях
Предлагаю вам подставить в ваши формулы конкретные небольшие значения n/m/k и проверить, совпадают ли они с истиным решением (которое легко получить перебором на листочке)
У него ответ - 0.0000372010, у меня ответ - 0.0000372006. Числа близкие, но разные, это важно
А что нельзя то, интересная задача! Сходу как решать тоже не знаю, но на досуге подумаю, спасибо!