Вероятность и статистика · объяснение и практика

Как соседство исходов меняет подсчёт серий в двоичной последовательности

Посчитайте максимальные серии одинаковых символов через смены соседей и найдите среднее число серий без ложного предположения об их независимости.

Рука ставит оранжевый столбик между двумя синими столбиками разной высоты.

В теме Комбинаторика и пространство исходов · Учебная карта

Главная мысль

Серия — максимальный непустой блок одинаковых соседних исходов. Для двоичной последовательности длины n≥1 число серий равно единице плюс числу смен между соседними позициями.

Максимальный блок считается один раз

В строке 001110011 серии имеют вид 00, 111, 00, 11. Всего их четыре. Внутри блока 111 можно увидеть отдельные единицы и пары, но они не являются дополнительными максимальными сериями. Поэтому задача о количестве серий отличается от задачи о числе вхождений подстроки или максимальной длине цепочки успехов.

Каждая новая серия после первой начинается там, где соседний символ отличается от предыдущего. Между n позициями есть n−1 соседних границ. Это даёт точное равенство R=1+I₁+…+Iₙ₋₁, где каждый индикатор равен единице при смене. Пустая последовательность требует отдельного определения и не входит в формулу с первой обязательной серией.

Линейность ожидания не требует независимых границ

Пусть символы независимы и каждый равен единице с вероятностью p. На одной границе смена происходит как 01 или 10, её вероятность равна 2p(1−p). Поэтому E[R]=1+(n−1)·2p(1−p). Соседние индикаторы используют общие символы и вообще могут быть зависимы, но для сложения ожиданий их независимость не нужна.

Для восьми независимых равновероятных двоичных символов ожидаемое число серий равно 1+7/2=4,5. Само наблюдаемое число серий всегда целое, но среднее по разным возможным строкам может быть дробным. Нельзя округлять ожидание до ближайшего количества и объявлять его единственным наиболее вероятным результатом.

Пример

В строке 111001011 посчитайте серии и смены.

Разбиение: 111|00|1|0|11. Серий пять, смен четыре. Одна исходная серия уже существует до первой проверки соседей, поэтому число серий на единицу больше числа смен.

Зависимость исходов меняет вероятности смен

Если символы идут с зависимостью, общая формула через индикаторы сохраняется, но вероятность смены не обязана равняться 2p(1−p). Например, процесс может повторять предыдущий символ гораздо чаще, чем независимая модель с той же долей единиц. Тогда среднее число серий уменьшится, хотя отдельная вероятность единицы не изменилась.

Знание числа единиц тоже не определяет число серий: одинаковый состав можно сгруппировать или чередовать. Для длинной серии успехов требуется другой подсчёт, учитывающий перекрывающиеся окна. Удобно в начале задачи явно написать, что ищется: число всех максимальных блоков, число смен или наличие блока заданной длины. Это разные статистики одной строки.

От чтения к действию

А теперь — вы

Пять независимых символов равновероятно равны 0 или 1. Каково ожидаемое число максимальных серий?

Частые вопросы

Нужно ли считать подблоки внутри длинной серии?

Нет. Серия здесь максимальна. Блок из трёх единиц считается одной серией, а не несколькими отдельными сериями меньшей длины.

Почему можно складывать ожидания зависимых индикаторов?

Линейность ожидания не требует независимости. Независимость символов использована только для вычисления вероятности смены на одной границе.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться