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

Как посчитать номер попытки заданного по счёту успеха

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

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

В теме Случайные величины и распределения · Учебная карта

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

Если независимые попытки имеют постоянную вероятность успеха p, то номер N наступления r-го успеха удовлетворяет P(N=k)=C(k−1,r−1)pʳ(1−p)ᵏ⁻ʳ при k≥r. Здесь считают все попытки, включая последнюю успешную.

Что именно считает случайная величина

В отрицательном биномиальном распределении встречаются два соглашения: считать число неудач до заданного успеха или номер попытки, на которой он наступил. Здесь используем второе. Если нужно получить r успехов, на k-й попытке последний из них должен произойти впервые; поэтому k не меньше r, а сама последняя попытка обязательно успешна.

Первые k−1 попыток содержат ровно r−1 успехов и k−r неудач. Их можно расположить C(k−1,r−1) способами. Вероятность каждого допустимого расположения вместе с последним успехом равна pʳ(1−p)ᵏ⁻ʳ. Нельзя использовать C(k,r): оно допустило бы варианты, в которых нужный успех достигнут раньше последнего номера.

Посчитайте расположения до последнего шага

Пусть p=1/2 и требуется третий успех ровно на пятой попытке. Последняя уже закреплена как успех. На первых четырёх местах выбираем два успеха шестью способами, поэтому вероятность равна 6/32=3/16. Строка с тремя успехами среди пяти не всегда подходит: если все они оказались в начале, третий успех наступил раньше.

Модель требует независимых одинаковых попыток. Выбор без возвращения из конечного набора меняет вероятность следующего успеха и не соответствует этой формуле автоматически. Также надо различать «ровно на k-й» и «не позже k-й»: для второго события удобен подсчёт не менее r успехов в первых k испытаниях.

Пример

Вероятность успеха 0,4. Найдите вероятность второго успеха ровно на четвёртой попытке.

В первых трёх попытках должен быть один успех: три расположения. Получаем 3·0,4²·0,6²=0,1728. Четвёртая попытка уже входит в две степени p, отдельный дополнительный множитель успеха не нужен.

Края и ожидание

При p=1 успех случается в каждой попытке и N=r с вероятностью один. При p=0 нужный положительный по счёту успех никогда не наступит, поэтому конечного номера нет. Для 0<p<1 средний номер r-го успеха равен r/p: его можно представить суммой r независимых геометрических ожиданий между успехами.

Число неудач F=N−r имеет другую поддержку, начиная с нуля. Если справочник или программа возвращает распределение для F, перед сравнением значений нужно прибавить r или изменить индекс. Разница соглашений не является разницей самой вероятностной идеи, но без явного указания легко получить сдвиг ответа на несколько попыток.

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

А теперь — вы

Независимые попытки имеют p=1/2. Какова вероятность второго успеха ровно на третьей попытке?

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

Почему коэффициент C(k−1,r−1), а не C(k,r)?

Последняя попытка обязана быть успехом. Располагают только предыдущие r−1 успехов на первых k−1 местах.

Число неудач и номер последней попытки совпадают?

Нет. Между ними разница r: N=F+r. Поэтому надо проверить соглашение используемой формулы или программы.

Углублённый разбор

Остаточное ожидание нескольких успехов: условная смесь незавершённых запусков

После незавершения серии остаточное ожидание заданного успеха зависит от скрытого накопленного счёта. Отрицательно-биномиальное ожидание нескольких успехов не обладает геометрическим отсутствием памяти.

Перед началом: Комбинаторный подсчёт конечных исходов; Индикаторы и независимые испытания.

Определение и постановка

Если нужно r успехов, а к дате n известно Sₙ=s<r, остаётся ждать r−s новых успехов. В независимой серии с общим шансом p среднее остаточное число попыток равно (r−s)/p.

Вывод и вычислительный критерий

Условие Tᵣ>n сообщает лишь Sₙ<r, но обычно не раскрывает точный s. Поэтому прогноз остатка строится как смесь по допустимым накопленным счётчикам с весами P(Sₙ=s|Sₙ<r). Эти веса вычисляются нормировкой биномиальных масс на событии незавершения.

Следовательно, E(Tᵣ−n|Tᵣ>n)=Σₛ₌₀ʳ⁻¹[(r−s)/p]P(Sₙ=s|Sₙ<r). Слагаемые с невозможным s имеют нулевой вес. Среднее не обязано совпадать с исходным r/p и обычно меняется с n.

Условия и границы вывода

Для r=1 незавершение однозначно означает ноль успехов. Смесь исчезает, остаётся исходное геометрическое ожидание одного успеха. Именно эта особенность обеспечивает отсутствие памяти в простейшем случае.

Для r>1 информация о незавершении не эквивалентна новому старту. Часть отобранных запусков уже накопила успехи и приблизилась к цели. Условный прогноз должен сохранять эти накопленные состояния, а не обнулять историю.

Если раскрыть не только факт незавершения, но и точный счёт s, зависимость будущего ожидания от номера даты исчезнет при постоянном p. Однако зависимость от числа оставшихся успехов сохраняется. Это различает достаточную информацию о состоянии процесса и неполное наблюдение его статуса. При изменяющемся шансе p или зависимых попытках даже точный счёт может оказаться недостаточным для прогноза; тогда необходимо описать скрытый режим либо дополнительные характеристики истории. Формула смеси верна как разложение по состояниям, но входящие условные ожидания уже не обязаны равняться (r−s)/p.

Разобранная задача

Условие. В честной независимой серии ждут второго успеха. После двух попыток известно лишь, что серия ещё не закончилась. Найдите среднее число дополнительных попыток.

  1. Незавершение после двух попыток допускает префиксы 00,01,10; каждый имеет исходную вероятность 1/4.
  2. При условии незавершения эти три префикса равновероятны. Ноль успехов имеет условный вес 1/3, один успех — 2/3.
  3. После 00 нужны два успеха со средним ожиданием 4. После 01 или10 нужен один успех со средним ожиданием 2.
  4. Усредняем оставшиеся сроки: (1/3)·4+(2/3)·2=8/3 дополнительных попытки.

Ответ. Условное среднее остаточного срока равно 8/3 попытки, а не исходным четырём.

Проверка. Для второго срока P(T₂>2)=3/4 и P(T₂>3)=1/2. Поэтому условная вероятность ждать ещё более одной попытки равна 2/3, тогда как от нового старта T₂>1 достоверно. Это независимо опровергает отсутствие памяти.

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

Проверьте понимание

Что требуется усреднить при известном только незавершении?

Вопросы к этой главе

Почему нельзя получить ответ 4−2=2?

Завершившиеся к этому сроку запуски исключены условием. Среднее оставшихся запусков изменилось, поэтому безусловное среднее нельзя просто сдвинуть по времени.

Нужно ли различать префиксы 01 и10?

Для постоянного p их будущий прогноз одинаков: оба содержат один успех. Веса разных накопленных счётов важны, порядок при данных предпосылках значения не имеет.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

Время первого и второго успеха: зависимость моментов остановки

Моменты последовательных успехов зависимы, хотя промежутки ожидания между успехами независимы. Второй срок включает первый как часть суммы.

Перед началом: Комбинаторный подсчёт конечных исходов; Индикаторы и независимые испытания.

Определение и постановка

В независимой серии с общим p промежутки G₁,G₂,… независимы и геометрически распределены на 1,2,… . Срок r-го успеха равен Tᵣ=G₁+…+Gᵣ.

Вывод и вычислительный критерий

Для r≤s общие слагаемые дают Cov(Tᵣ,Tₛ)=Var(Tᵣ)=r(1−p)/p². Непересекающиеся дополнительные промежутки имеют нулевую ковариацию с Tᵣ.

После нормировки получается Corr(Tᵣ,Tₛ)=sqrt(r/s), если 0<p<1. Параметр p сокращается, но это не означает независимость или одинаковое распределение сроков.

Условия и границы вывода

При p=1 все сроки постоянны и корреляция не определена из-за нулевых дисперсий. При изменяющихся вероятностях испытаний независимость одинаковых геометрических промежутков уже не гарантирована.

Зависимость сроков возникает структурно, даже без общего скрытого фактора. Нельзя подставлять независимость попыток как независимость произвольных функций одной последовательности.

Для двух сроков T₂ и T₄ общими являются первые два геометрических промежутка. При честной монете их ковариация равна четырём, а дисперсии равны четырём и восьми. Корреляция снова равна единице, делённой на корень из двух. Такое совпадение объясняется одинаковым отношением номеров успехов два к четырём, а не совпадением самих распределений сроков. Если номера всё дальше раздвигаются при фиксированном первом номере, корреляция убывает к нулю. При этом ковариация остаётся прежней: растёт лишь дополнительный независимый разброс более позднего срока. Поэтому малую корреляцию нельзя переводить в утверждение о малой абсолютной общей неопределённости без указания масштабов.

Разность T₂−T₁ имеет то же геометрическое распределение, что и T₁, но независима от него. Равенство распределений здесь не означает равенства случайных величин; разные промежутки используют непересекающиеся части последовательности после соответствующих успехов.

Разобранная задача

Условие. Для честной независимой серии найдите Cov(T₁,T₂) и Corr(T₁,T₂).

  1. У геометрического промежутка при p=1/2 среднее равно 2, дисперсия равна 2.
  2. T₁=G₁, а T₂=G₁+G₂, где G₁ и G₂ независимы.
  3. Ковариация равна Var G₁+Cov(G₁,G₂)=2+0=2.
  4. Дисперсия T₂ равна 4, поэтому корреляция равна 2/sqrt(2·4)=1/sqrt2.

Ответ. Ковариация равна 2, корреляция равна 1/√2.

Проверка. Условное среднее E(T₂|T₁)=T₁+2. Ковариация T₁ с этим условным средним равна Var T₁=2, что подтверждает ответ другим разложением.

Где легко ошибиться. Независимые приращения сроков не делают независимыми накопленные сроки: они имеют общую случайную часть.

Проверьте понимание

Какие величины независимы в серии независимых испытаний с одной и той же вероятностью успеха 0<p<1?

Вопросы к этой главе

Почему корреляция положительна?

Долгое ожидание первого успеха целиком переносится в срок второго. Независимое ожидание следующего успеха добавляет разброс, но не отменяет общий сдвиг.

Можно ли получить независимость T₁ и T₂?

В данной невырожденной модели нет. Всегда T₂>T₁, и условное среднее второго срока линейно зависит от первого.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

Неравные купоны: ожидание полного набора через включения и исключения

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

Перед началом: Конечная модель вероятностей; Математическое ожидание и дисперсия.

Хвост описывает ещё не увиденные категории

Каждая независимая попытка даёт ровно одну из k категорий с постоянными положительными вероятностями pᵢ, сумма которых равна единице. Время T — номер попытки, после которой впервые увидены все категории. Начальное состояние коллекции пустое, а все повторные появления уже известных категорий всё равно расходуют попытку.

После n попыток коллекция неполна, если отсутствует хотя бы одна категория. Для непустого подмножества A вероятность не увидеть ни одной его категории равна (1−p(A))ⁿ, где p(A)=Σᵢ∈A pᵢ. Независимость попыток позволяет возвести одну вероятность в степень, но отсутствие разных категорий не является независимым событием.

Включения и исключения исправляют пересечения

Применяем формулу объединения к событиям отсутствия отдельных категорий. Получаем P(T>n)=Σ_{A≠∅}(−1)^{|A|+1}(1−p(A))ⁿ. Одно отсутствие прибавляется, двойное пересечение вычитается, тройное снова прибавляется. Именно эти пересечения не позволяют сложить отдельные времена ожидания.

Для положительного целочисленного T имеем E T=Σₙ≥₀P(T>n). Подмножеств конечное число, а p(A)>0, поэтому каждую геометрическую сумму можно вычислить точно: E T=Σ_{A≠∅}(−1)^{|A|+1}/p(A). Случай p(A)=1 даёт сумму с единственным ненулевым первым членом, равную единице.

Редкая категория и независимый контроль

При нулевой вероятности хотя бы одной требуемой категории коллекция никогда не завершится и конечная формула с делением на p(A) неприменима. При малой положительной вероятности среднее может быть большим, даже когда остальные категории появляются часто. Число категорий само по себе не определяет длительность.

Другой точный подход хранит множество уже увиденных категорий. Из каждого такого состояния уравнение первого шага учитывает повтор и переход к большему множеству. В небольшой задаче решение этих уравнений независимо проверяет формулу подмножеств и помогает обнаружить неверный знак перед парным пересечением.

Коллекция из трёх неодинаковых категорий

Условие. В независимых попытках категории A,B,C имеют вероятности 1/2,1/3,1/6. Сколько попыток в среднем нужно до первого полного набора всех трёх категорий?

  1. Одиночные члены формулы дают 1/(1/2)+1/(1/3)+1/(1/6)=2+3+6=11.
  2. Для пар получаем 1/(5/6)=6/5, 1/(2/3)=3/2 и 1/(1/2)=2. Их нужно вычесть, поскольку ожидания отдельных отсутствий пересекаются.
  3. Тройное пересечение добавляет 1/(1/2+1/3+1/6)=1. Итог 11−6/5−3/2−2+1=73/10.
  4. Ответ больше трёх попыток, поскольку повторные категории допустимы. Для сравнения, равные вероятности трёх категорий дали бы 3+3/2+1=11/2, что является иной моделью.

Ответ. Среднее время полного набора равно 73/10=7,3 попытки.

Проверка. Рекурсия по семи неполным множествам увиденного даёт то же значение. Например, если не хватает только C, осталось в среднем 6 попыток; затем уравнения для двух отсутствующих категорий определяют предыдущие состояния без включений и исключений.

Где легко ошибиться. Сумма 1/pᵢ=11 считает перекрывающиеся времена так, словно наблюдения для каждой категории проводились отдельно. Здесь идёт одна общая последовательность, поэтому ожидание полного набора определяется максимумом взаимосвязанных времён первого появления, а не их суммой.

Проверьте понимание

Каково среднее число попыток до полного набора в данной модели?

Вопросы к этой главе

Почему сумма хвостов начинается с n=0?

До первой попытки коллекция заведомо неполна, поэтому P(T>0)=1. Пропуск этого члена уменьшил бы математическое ожидание ровно на единицу.

Можно ли применять формулу, если категория зависит от предыдущей?

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

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • Flajolet–Gardy–Thimonier 1992, §4, Theorem 4.1

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

Остановка на успехе: правдоподобие и пространство повторений

Одна и та же последовательность успехов и неудач может возникнуть в двух планах: с фиксированным числом попыток или с остановкой на нужном успехе. Их правдоподобия похожи, но повторяемые выборочные пространства различны.

Перед началом: Условная вероятность; Точная арифметика.

Остановка включена в закон записи

Пусть независимые испытания имеют общую вероятность успеха p. В фиксированном плане наблюдают X успехов за n попыток, и масса счёта равна C(n,x)pˣ(1−p)^(n−x). При остановке на r-м успехе случайным становится номер T, причём P(T=t)=C(t−1,r−1)pʳ(1−p)^(t−r). Последний исход обязательно успешен, поэтому коэффициент считает размещение только первых r−1 успехов в t−1 местах.

Одинаковое ядро не означает одинаковый план

Если получены n=t и x=r, оба правдоподобия как функции p пропорциональны pʳ(1−p)^(t−r). Их максимумы и байесовские обновления при одном prior совпадают, поскольку комбинаторные множители не зависят от p. Однако вероятности возможных других данных рассчитываются по разным наборам: фиксированный план допускает любой X при данном n, остановочный — разные T при данном r. Частотные хвосты и покрытие интервалов должны учитывать именно этот набор повторений.

Граничные оценки нуждаются в проверке

В обоих описаниях внутренний максимум ядра достигается при p̂=r/t, если 0<r<t. Это не доказывает несмещённость r/T при остановочном плане. При r=1 и p<1 функция 1/T нелинейна, и её среднее отличается от p. Если в фиксированном плане встретились ноль успехов, остановка на положительном r ещё вообще не завершилась бы. Поэтому нельзя переносить крайние исходы между экспериментами только по внешнему сходству готовой формулы.

Разобранная задача

Условие. Наблюдалась запись неудача, неудача, успех. Сравните правдоподобие p при плане ровно трёх попыток со счётом X=1 и при плане остановки на первом успехе с T=3. Найдите максимум и отношение правдоподобий кандидатов p=1/2 и p=1/3.

  1. Для фиксированного счёта масса равна 3p(1−p)². Для остановочного номера масса равна p(1−p)², поскольку первый успех обязан стоять последним.
  2. Множитель три не зависит от p, поэтому обе функции имеют одинаковый относительный профиль по параметру.
  3. Производная логарифма ядра равна 1/p−2/(1−p). Приравнивание нулю даёт p̂=1/3; знак второй производной отрицателен.
  4. Отношение ядра при половине и трети равно [(1/2)(1/2)²]/[(1/3)(2/3)²]=(1/8)/(4/27)=27/32.

Ответ. Оба плана дают максимум 1/3 и отношение правдоподобий 27/32 для двух кандидатов. Их распределения повторных данных остаются различными.

Проверка. Если хранить полную конкретную трёхсимвольную запись, её вероятность в фиксированном плане тоже равна p(1−p)². Коэффициент три появился только после объединения трёх записей с одним успехом, подтверждая его независимость от параметра.

Где легко ошибиться. Не превращайте совпадение правдоподобий в утверждение о совпадении точных p-значений всех процедур. Хвостовая область определяется планом и выбранной статистикой, а не только ядром наблюдённого случая.

Проверьте понимание

Какая оценка максимального правдоподобия получена?

Вопросы к этой главе

Почему последняя попытка выделена в остановочном законе?

Без успеха на последней позиции первый успех наступил бы раньше или эксперимент ещё продолжался бы. Условие остановки исключает остальные расположения последнего исхода.

Нужно ли скрывать правило остановки при публикации?

Нет. Оно необходимо для воспроизводимого описания данных и любых гарантий повторения плана, даже если для конкретного likelihood-вывода даёт лишь постоянный множитель.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • R Core: The Negative Binomial Distribution

    Число неудач до заданного успеха и его поддержка; различие остановленного и фиксированного планов разобрано отдельно.

Ожидание слова: самоперекрытие и автомат неполных совпадений

У HHH и HTH одинаковая вероятность в заранее выбранном окне, но разные средние времена первого появления. Причину обнаруживает память о незавершённом префиксе: неудачный символ иногда сохраняет часть уже накопленного совпадения.

Перед началом: Рекурсия по первому шагу; Независимые испытания Bernoulli.

Одно окно и первое появление — разные вопросы

Независимые броски честной монеты, наблюдение начинается до первого броска. Время включает символ, впервые завершивший заданное слово.

В фиксированных трёх бросках каждая из восьми строк имеет вероятность 1/8. Однако последовательные окна перекрываются двумя символами. Их индикаторы зависимы, поэтому последовательность окон нельзя объявить независимыми попытками с вероятностью успеха 1/8. Геометрическое среднее восемь тогда не обосновано. Кроме того, три орла где угодно и три орла подряд определяют разные остановки.

Для слова w будем хранить самый длинный суффикс уже увиденной строки, который одновременно является префиксом w. Любое более раннее содержимое не влияет на возможность завершить слово следующим символом. Это минимальная полезная память для данной задачи; она описывает совпадение букв, а не число всех успехов за всё наблюдение.

Неудача может оставить подходящий суффикс

Для HTH состояния до поглощения обозначим ∅, H, HT. Из ∅ орёл переводит в H, решка оставляет ∅. Из H ещё один орёл сохраняет H: последний символ снова начинает искомое слово. Решка переводит в HT. Из HT орёл завершает поиск, а решка возвращает в ∅. После найденного слова расчёт первого появления останавливается.

Пусть e₀,e₁,e₂ — оставшиеся средние времена из этих трёх состояний. Каждый переход тратит один бросок, поэтому e₀=1+(e₀+e₁)/2, e₁=1+(e₁+e₂)/2, e₂=1+e₀/2. Для HHH второй переход иной: из HH решка обнуляет совпадение, а орёл поглощает. Поэтому его третье уравнение такое же, но второе принимает вид e₁=1+(e₀+e₂)/2.

Как проверить состояние и интерпретировать разницу

Сначала проверяют каждый переход на коротких строках. После HH в поиске HTH состояние действительно H, а не ∅; после HTT подходящего непустого префикса нет. Затем подставляют найденные ожидания во все уравнения. Это защищает от арифметически правильного решения неправильного автомата. Для независимой численной проверки можно суммировать вероятности ещё не завершённого поиска по конечным горизонтам.

У HHH собственные начальные и конечные фрагменты совпадают на длинах один и два; у HTH — только на длине один. В этих двух честных примерах ожидания равны соответственно 8+4+2 и 8+2. Такой разбор объясняет роль самоперекрытия. Здесь он служит проверкой результата уравнений, а не заменяет доказательство универсальной формулы для любого алфавита или зависимых символов.

Два слова длины три

Условие. Для честной монеты найдите средние времена первого появления HTH и HHH, начав с пустой истории. Сравните их с ожиданием третьего орла без требования последовательности.

  1. Для HTH первое уравнение даёт e₁=e₀−2, а второе e₂=e₁−2=e₀−4. Третье требует e₀−4=1+e₀/2.
  2. Получаем e₀=10, e₁=8, e₂=6. Подстановка проверяет все три перехода и единицу времени на завершающем броске.
  3. Для HHH первое уравнение снова даёт e₁=e₀−2. Второе даёт e₂=e₀−6; третье — e₂=1+e₀/2. Отсюда e₀=14, e₁=12, e₂=8.
  4. Третий орёл без требования соседства имеет средний номер 3/(1/2)=6. Числа 6,10,14 относятся к трём разным правилам остановки.

Ответ. Средние времена HTH и HHH равны 10 и 14 броскам; третий орёл без ограничения соседства появляется в среднем на шестом.

Проверка. Для HTH значения дают 10=1+(10+8)/2, 8=1+(8+6)/2, 6=1+10/2. Для HHH отдельно получаем 14=1+(14+12)/2,12=1+(14+8)/2,8=1+14/2. Суммы обратных вероятностей совпадающих краевых фрагментов дают 8+2 и 8+4+2.

Где легко ошибиться. Вероятность слова в одном окне не обращается автоматически в среднее время первого появления. Перекрывающиеся окна разделяют символы и не являются независимыми испытаниями.

Проверьте понимание

Каково среднее время первого появления HTH в разобранном примере статьи с честной монетой?

Вопросы к этой главе

Нужно ли всегда после неудачи возвращаться в пустое состояние?

Нет. После HH при поиске HTH последний H уже начинает следующий возможный экземпляр. Потеря этого суффикса завышает ожидание и меняет распределение остановки.

Что изменится при зависимых бросках?

Одного совпавшего префикса может быть недостаточно. Нужно добавить состояние источника, определяющее закон следующего символа, и заново составить переходы. Числа 10 и 14 относятся к независимой честной монете.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • UC Berkeley Prob140, Waiting Till a Pattern Appears

    Поддерживает представление поиска слова цепью префиксов и анализ первого шага. Здесь переходы двух коротких слов выписаны и сопоставлены самостоятельно.

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

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

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