Слияние, прореживание и времена событий

Если можешь доказать независимость двух прореженных счётчиков и отличаешь равномерные точки от первого прихода, переходи к «Теперь сам».

Как думаешь, два типа делят один ресурс случайности

Общий счётчик за минуту пуассоновский со средним 5. Каждое событие независимо становится типом A с вероятностью 0,4, иначе типом B. Кажется, что больше A обязательно означает меньше B, поскольку оба типа берутся из одного потока.

Если заранее зафиксировать общее число, это действительно так. Но исходная сумма сама случайна. В полном опыте дополнительные события A могут появляться вместе с увеличением суммы, не отнимая B. Точный расчёт покажет, что два безусловных счётчика независимы. Это пример, в котором условная и безусловная зависимости устроены по-разному.

На что это похоже

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

Но фильтр «красить по очереди» работает иначе. Он оставляет почти одинаковые количества двух цветов в каждом длинном отрезке: разница не больше одного. Такое ограничение связывает счётчики, хотя доля каждого цвета может быть близка к половине. Одной средней доли для независимого прореживания недостаточно.

Механизм: интенсивности при слиянии и разделении

Пусть N₁,N₂ независимы и имеют интенсивности λ₁,λ₂. Их сумма N=N₁+N₂ начинает с нуля и сохраняет независимость непересекающихся приращений. На малом h вероятность ровно одного события равна (λ₁+λ₂)h+o(h), а двух или более - o(h). Значит сумма удовлетворяет условиям процесса Пуассона с интенсивностью λ₁+λ₂.

Для независимого присвоения метки A с постоянной вероятностью p интенсивность A равна λp: на малом шаге нужно одно исходное событие и нужная метка. Метки независимы между событиями и от исходных времён. Это даёт пуассоновский закон каждого типа, но для взаимной независимости двух потоков отдельно проверим совместный закон.

При n типах с вероятностями p₁,…,pₙ, сумма которых равна 1, получаем независимые потоки λpᵢ. В обратном направлении событие объединённого потока принадлежит i-му исходному с вероятностью λᵢ/Σλⱼ. Это та же пропорция, что в экспоненциальной гонке.

Правило

Слияние требует независимости исходных потоков. Прореживание требует независимых постоянных меток. При этих условиях интенсивности складываются или умножаются на вероятность метки. При условии N(t)=n упорядоченные времена T₁<…<Tₙ имеют ту же совместную модель, что отсортированные n независимых U[0,t].

Последнее условие меняет закон времени первого события. Без него T₁ экспоненциален и может быть больше t. С ним первый момент обязательно находится внутри [0,t] и является минимумом n равномерных точек. Нельзя одновременно пользоваться обоими законами в одной условной задаче.

Разбор: совместный закон двух типов

Обозначим θ=λt. Для целых a,b≥0 общее число должно равняться a+b, после чего из этих событий выбираем a меток A. Получаем P(A=a,B=b)=exp(−θ)θ^(a+b)/(a+b)! · C(a+b,a)p^a(1−p)^b. Факториал общего числа сокращается с биномиальным коэффициентом.

Результат равен exp(−θp)(θp)^a/a! · exp(−θ(1−p))(θ(1−p))^b/b!. Это произведение двух пуассоновских масс. Значит A и B независимы на данном интервале. На непересекающихся интервалах исходные события и метки тоже независимы, поэтому независимы два процесса целиком.

import math
from fractions import Fraction


def poisson(k, mean):
    return math.exp(-mean) * mean ** k / math.factorial(k)


mean, chance = 5, 0.4
left, right = 1, 2
n = left + right
joint = (poisson(n, mean) * math.comb(n, left)
         * chance ** left * (1 - chance) ** right)
product = (poisson(left, mean * chance)
           * poisson(right, mean * (1 - chance)))
print("P(A=1,B=2) =", f"{joint:.6f}")
print("произведение =", f"{product:.6f}")
assert abs(joint - product) < 1e-12
print("N(6)=2, среднее первого =", Fraction(6, 3))
print("N(6)=2, среднее второго =", Fraction(12, 3))
print("P(первый <=1 | N(6)=2) =", 1 - Fraction(5, 6) ** 2)

P(A=1,B=2) = 0.060642
произведение = 0.060642
N(6)=2, среднее первого = 2
N(6)=2, среднее второго = 4
P(первый <=1 | N(6)=2) = 11/36

При θ=5,p=0,4 счётчики имеют средние 2 и 3. Две первые строки вычислены разными выражениями и совпадают. Но при условии A+B=3 знание A=1 однозначно задаёт B=2. Независимость до условия не распространяется автоматически на условный эксперимент.

Разбор: где находятся два прихода за шесть минут

Предположим, N(6)=2. Неупорядоченные времена эквивалентны двум независимым U[0,6]. После сортировки средние первого и второго равны 2 и 4, а не оба 3. Вероятность первого времени не больше 1 равна 1−(5/6)²=11/36.

Почему условные точки равномерны? Для упорядоченных узких окон около t₁,…,tₙ внутри [0,t] независимость приращений даёт совместную вероятность примерно exp(−λt)λ^n dt₁…dtₙ: по одному приходу в каждом окне и ни одного вне окон. Делим на P(N(t)=n)=exp(−λt)(λt)^n/n! и получаем постоянную условную плотность n!/t^n на области 0<t₁<…<tₙ<t. Это плотность отсортированных равномерных точек.

При n=2 один неупорядоченный приход имеет вероятность 1/6 попасть в первую минуту. Первый по времени имеет вероятность 11/36, потому что достаточно хотя бы одной точки в этой минуте. Вероятность второй точки зависит от того, где оказалась первая: упорядоченные времена не независимы.

Ещё одно следствие: условно на N(t)=n число событий в [0,s] имеет Bin(n,s/t), 0≤s≤t. Для шести минут и двух событий это биномиальный счётчик по двум равномерным точкам, а не независимый от числа событий на оставшемся отрезке.

Что ломается без этого

Удваивают одну и ту же ленту и называют это слиянием двух независимых потоков. Результирующий счётчик прыгает сразу на два; пуассоновские малые приращения с интенсивностью 2λ так не устроены. Независимость входов нельзя заменить одинаковым законом каждого.

Или выбирают тип по состоянию очереди и сохраняют формулу независимого прореживания. Такая маршрутизация может быть полезна, но метки уже зависят от истории. Её надо анализировать новой моделью, а не только подставить среднюю долю направленных заявок.

Зачем это в работе

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

Теперь сам

Независимые потоки имеют интенсивности 3 и 7 в минуту. Какова интенсивность объединения и вероятность принадлежности его следующего события первому источнику? Если за две минуты известно ровно три события, каково среднее времени второго?