Экспоненциальное ожидание и гонка событий

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

Как думаешь, таймер уже обязан сработать

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

Такая модель описывает постоянную интенсивность события при отсутствии сведений о накопленном износе. Она не подходит к каждой жизненной задержке: если срок равномерно выбран от 0 до 10 секунд и прошло девять, оставшийся закон уже находится в интервале [0,1], а не [0,10].

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

Несколько сторожевых датчиков независимо ждут первое событие. Быстрее сработает система с большим суммарным числом возможностей, но конкретный победитель заранее не определён. Интенсивность измеряет частоту возможностей на единицу времени; среднее ожидание имеет обратные единицы.

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

Механизм: хвост и отсутствие памяти

Для λ>0 плотность равна λexp(−λt) на t≥0, CDF равен 1−exp(−λt). Экспонента exp(x)=e^x уже встречалась в хвостовых оценках. Суммирование хвоста даёт E[T]=∫₀∞exp(−λt)dt=1/λ. Для второго момента используем ту же площадь хвоста с весом: при фиксированном x≥0 имеем x²=∫₀ˣ2t dt, поэтому E[T²]=∫₀∞2t·P(T>t)dt=2∫₀∞t·exp(−λt)dt. Последний интеграл считаем, представив t=∫₀ᵗ1 ds. В области 0≤s≤t можно поменять порядок неотрицательных площадей: сначала интегрировать t от s до бесконечности, затем s от 0 до бесконечности. Получается ∫₀∞(∫ₛ∞exp(−λt)dt)ds = ∫₀∞exp(−λs)/λ ds=1/λ². Итак, E[T²]=2/λ², дисперсия 2/λ²−(1/λ)²=1/λ².

Для s,t≥0 условная вероятность P(T>t+s | T>t)=exp(−λ(t+s))/exp(−λt)=exp(−λs). Это и есть отсутствие памяти. Среди невырожденных неотрицательных непрерывных ожиданий с обычной непрерывностью хвоста оно выделяет экспоненциальный закон. Действительно, хвост S должен удовлетворять S(t+s)=S(t)S(s), S(0)=1. Сначала на рациональных временах, затем по непрерывности получаем S(t)=exp(−λt) для некоторого λ>0.

Правило

Минимум независимых Exp(λ₁),…,Exp(λₙ) имеет закон Exp(Σλᵢ). Вероятность, что первым сработает i-й таймер, равна λᵢ/Σλⱼ. Независимость и экспоненциальная форма обязательны. При смене состояния, которая меняет интенсивности, следующая гонка строится уже с новыми параметрами.

Для закона минимума перемножаем хвосты: P(min(Tᵢ)>t)=∏exp(−λᵢt)=exp(−tΣλᵢ). Для победы i интегрируем вероятность его срабатывания в момент t и выживания всех остальных до t: ∫₀∞λᵢexp(−λᵢt)∏ⱼ≠ᵢexp(−λⱼt)dt=λᵢ/Σλⱼ. Равные точные времена имеют вероятность ноль, поэтому неоднозначной ничьей нет.

Разбор: два свободных места

Два сервера заканчивают независимые экспоненциальные работы с интенсивностями 2 и 3 в минуту. Если оба заняты, среднее до первого свободного места равно 1/5 минуты, то есть 12 секунд. Вероятность, что первым освободится первый сервер, равна 2/5, второй - 3/5.

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

import math
from fractions import Fraction


def urn(total, power):
    dist = {(1, 1): Fraction(1)}
    for _ in range(total - 2):
        new = {}
        for (x, y), probability in dist.items():
            p = Fraction(x ** power, x ** power + y ** power)
            moves = [((x + 1, y), p), ((x, y + 1), 1 - p)]
            for state, chance in moves:
                old = new.get(state, Fraction(0))
                new[state] = old + probability * chance
        dist = new
    return [str(dist[(x, total - x)]) for x in range(1, total)]


rate = 2
s, t = 0.4, 0.7
conditional = math.exp(-rate * (s + t)) / math.exp(-rate * t)
print("хвост остатка =", f"{conditional:.6f}")
print("хвост нового таймера =", f"{math.exp(-rate * s):.6f}")
print("гонка 2 и 3: среднее =", Fraction(1, 5))
print("победа первого =", Fraction(2, 5))
print("6 шаров, p=1:", urn(6, 1))
print("6 шаров, p=2:", urn(6, 2))

хвост остатка = 0.449329
хвост нового таймера = 0.449329
гонка 2 и 3: среднее = 1/5
победа первого = 2/5
6 шаров, p=1: ['1/5', '1/5', '1/5', '1/5', '1/5']
6 шаров, p=2: ['144/425', '261/2210', '28/325', '261/2210', '144/425']

Первые строки численно проверяют отношение хвостов для λ=2, следующие - точные ответы гонки. Две последние строки относятся к другой модели: распределению количества шаров после шести шагов общего счёта. Они показывают конечный эффект обратной связи; доказательство бесконечного поведения ниже не заменяется этим маленьким перебором.

Разбор: усиленная обратная связь и случайная монополия

В каждой из двух корзин сначала по одному шару. При x,y шарах выбираем первую с вероятностью x^p/(x^p+y^p). Для p=1 распределение её наполнения при общем числе n равномерно на 1,…,n−1: переход из двух соседних состояний даёт суммарную вероятность 1/(n−1) на предыдущем шаге и 1/n на следующем. При p>1 преимущество большей корзины усиливается. Для внутреннего состояния k при переходе от n к n+1 шарам сумма двух вероятностей равна (1/(n−1))·((k−1)/n+(n−k)/n)=1/n; на крайних состояниях нулевое слагаемое просто отсутствует.

Для доказательства назначим корзине с z шарами независимое ожидание Exp(z^p) до следующего шара. Гонка этих часов даёт именно нужные вероятности, а отсутствие памяти позволяет продолжать после победы любой корзины. Теперь каждую временную последовательность можно рассматривать отдельно. Её суммарное время до бесконечного числа приходов равно F=Σₙ≥₁Tₙ. При p>1 среднее E[F]=Σₙ≥₁1/n^p≤1+1/(p−1) конечно. Неотрицательная величина с конечным средним конечна почти наверное.

Два суммарных времени F₁,F₂ почти наверное различны. Если зафиксировать все часы кроме первого в первой корзине, равенство потребовало бы от этого непрерывного ожидания ровно одного значения, вероятность чего ноль. Пусть F₁<F₂. До момента F₁ вторая последовательность успеет дать лишь конечное число событий, а первая - сколь угодно много. В объединённом порядке событий после некоторого случайного номера все шары получают только первую корзину. Случай F₂<F₁ симметричен. Любое положительное начальное наполнение лишь сдвигает начало двух сходящихся рядов; тот же вывод сохраняется.

Это почти верная монополия: с вероятностью 1 существует конечный случайный предел наполнения проигравшей корзины. Теорема не утверждает, что один общий предел известен заранее для всех реализаций. Вспомогательное непрерывное время имеет накопление бесконечного числа событий; оно служит доказательством порядка дискретных выборов, а не обычными физическими часами, которые можно безусловно продолжать после накопления.

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

Путают интенсивность λ и среднее 1/λ. Если вероятность события за маленькое h примерно λh, увеличение λ ускоряет часы, а не замедляет их. Проверяй единицы: «события в секунду» превращаются в секунды только после обращения.

Также нельзя из большой вероятности победы сделать вывод о заранее определённом победителе или сроке. Даже при положительной обратной связи меньшая корзина может выиграть. Конечная симуляция показывает один отрезок траектории; утверждение «после некоторого шага навсегда» требует отдельного рассуждения.

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

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

Теперь сам

Три независимых таймера имеют интенсивности 1,2,5 в секунду. Найди среднее до первого события и вероятность победы второго. Можно ли после просмотра миллиона шаров доказать, что монополия уже наступила навсегда?