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

В теме Комбинаторика и пространство исходов · Учебная карта
Главная мысль
Серия — максимальный непустой блок одинаковых соседних исходов. Для двоичной последовательности длины 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). Например, процесс может повторять предыдущий символ гораздо чаще, чем независимая модель с той же долей единиц. Тогда среднее число серий уменьшится, хотя отдельная вероятность единицы не изменилась.
Знание числа единиц тоже не определяет число серий: одинаковый состав можно сгруппировать или чередовать. Для длинной серии успехов требуется другой подсчёт, учитывающий перекрывающиеся окна. Удобно в начале задачи явно написать, что ищется: число всех максимальных блоков, число смен или наличие блока заданной длины. Это разные статистики одной строки.
От чтения к действию
А теперь — вы
Частые вопросы
Нужно ли считать подблоки внутри длинной серии?
Нет. Серия здесь максимальна. Блок из трёх единиц считается одной серией, а не несколькими отдельными сериями меньшей длины.
Почему можно складывать ожидания зависимых индикаторов?
Линейность ожидания не требует независимости. Независимость символов использована только для вычисления вероятности смены на одной границе.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Почему попарная независимость не гарантирует совместную
Проверьте независимость трёх событий на всех пересечениях и построьте пример, где каждая пара независима, а вся тройка — нет.
Открыть темуПочему последние недостающие типы увеличивают ожидание полного набора
Разложите сбор полного равновероятного набора на этапы ожидания нового типа и объясните, почему последние типы требуют больше попыток.
Открыть тему