Равномерное распределение и порядковые статистики

Если выводишь среднее первой из n равномерных точек и объясняешь знаменатель n+1, переходи к «Теперь сам».

Как думаешь, где будет первая из трёх точек

Три независимых запроса получают случайную задержку от 0 до 1 секунды. Средняя задержка каждого равна 1/2. Чему равно среднее самой ранней? Ответ 1/2 был бы верен для заранее выбранного запроса, а здесь выбирается тот, которому выпало меньше. Эта операция меняет закон.

Если все три задержки больше y, минимум тоже больше y. Вероятность равна (1−y)³. При y=1/2 она составляет 1/8. Значит с вероятностью 7/8 хотя бы один запрос уже готов в первой половине секунды. Теперь среднее минимума можно получить площадью под этим хвостом, а не предположением, что три точки обязательно стоят равномерной сеткой.

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

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

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

Механизм: условие укорачивает равномерный интервал

Для a<b плотность равна 1/(b−a) внутри [a,b] и нулю вне. На внутренней части F(x)=(x−a)/(b−a); слева функция равна 0, справа 1. Вероятность участка - его длина, делённая на длину всего интервала. Включение концов на результат не влияет, поскольку масса точки нулевая.

Пусть известно, что X лежит в [c,d] внутри [a,b], причём c<d. Вероятность этого события (d−c)/(b−a). Совместное событие для участка [c,x] имеет вероятность (x−c)/(b−a). Деление сокращает исходную длину, и условный CDF становится (x−c)/(d−c). Получили U[c,d].

Линейное преобразование X=a+(b−a)U, где U~U[0,1], строит нужный равномерный закон. Оно сохраняет относительные длины и растягивает их в b−a раз. Поэтому среднее сдвигается и масштабируется как значение, а дисперсия умножается на (b−a)².

Правило

Для U[a,b] среднее равно (a+b)/2, дисперсия (b−a)²/12. Условие на внутренний интервал положительной длины даёт равномерный закон на этом интервале. Для n независимых U[a,b] после сортировки Y₁≤…≤Yₙ имеем E[Yₖ]=a+(b−a)k/(n+1). Формула относится к среднему по экспериментам и не обещает равных промежутков в одной выборке.

Откуда 1/12? Для U~U[0,1] интеграл ∫₀¹u du равен 1/2, второй момент ∫₀¹u²du равен 1/3. Разность 1/3−1/4=1/12. Сдвиг a не меняет отклонений от среднего, а растяжение b−a умножает каждое отклонение на этот коэффициент и его квадрат на квадрат коэффициента.

Разбор: минимальная задержка

Обозначим минимум n независимых U[0,1] через Y₁. Для 0≤y≤1 P(Y₁>y)=(1−y)^n: каждая точка должна оказаться правее y. Суммирование хвоста даёт E[Y₁]=∫₀¹(1−y)^n dy=1/(n+1). При n=3 это 1/4, а не 1/3 и не 1/2.

Для общего номера k можно посчитать CDF: событие Yₖ≤y означает, что как минимум k исходных точек не больше y. Число таких точек биномиально с параметрами n,y, поэтому P(Yₖ≤y)=Σⱼ₌ₖⁿ C(n,j)y^j(1−y)^(n−j). Для трёх точек и y=1/2 получаются 7/8, 1/2, 1/8 для номеров 1,2,3. Эти вероятности различаются, хотя исходные точки имели одинаковый закон.

from fractions import Fraction
from math import comb


def order_cdf(n, k, x):
    return sum(comb(n, j) * x ** j * (1 - x) ** (n - j)
               for j in range(k, n + 1))


for k in [1, 2, 3]:
    print("номер", k, "E =", Fraction(k, 4),
          "P(Y <= 1/2) =", order_cdf(3, k, Fraction(1, 2)))
print("U[2,8], среднее =", Fraction(2 + 8, 2))
print("U[2,8], дисперсия =", Fraction((8 - 2) ** 2, 12))
print("U[0,10] при X<=5, P(X<=2) =", Fraction(2, 5))

номер 1 E = 1/4 P(Y <= 1/2) = 7/8
номер 2 E = 1/2 P(Y <= 1/2) = 1/2
номер 3 E = 3/4 P(Y <= 1/2) = 1/8
U[2,8], среднее = 5
U[2,8], дисперсия = 3
U[0,10] при X<=5, P(X<=2) = 2/5

Столбец «номер» относится к позиции после сортировки, не к исходному имени запроса. Программа считает CDF через количество точек слева, а средние через формулу. Обе части используют один и тот же n=3. В последних строках показаны уже другие параметры равномерного интервала.

Разбор: почему все n+1 промежутков имеют одинаковое среднее

Возьмём ещё одну независимую точку U~U[0,1] в дополнение к исходным n. Если Yₖ оказалось равно y, вероятность U≤Yₖ равна y: дополнительная точка равномерна и не зависит от исходной выборки. Усредняя эту вероятность по всем значениям Yₖ, получаем P(U≤Yₖ)=E[Yₖ].

Теперь посмотрим на место U среди всех n+1 точек. Ничьи имеют вероятность ноль. Все метки точек равноправны: перестановка их имён не меняет опыт, потому что величины независимы и имеют один равномерный закон. Для каждого места r ровно одна метка занимает его. Вероятности всех n+1 меток одинаковы и в сумме равны 1, значит вероятность места r для U равна 1/(n+1).

Событие U≤Yₖ означает, что место U среди n+1 точек одно из первых k. Если перед U уже стоят k исходных точек, она правее Yₖ; если стоят меньше k, она левее Yₖ. Поэтому P(U≤Yₖ)=k/(n+1). Совместив два способа посчитать эту вероятность, получили нужное среднее.

Средние промежутки теперь следуют без многомерного исчисления: крайние положения заданы Y₀=0 и Yₙ₊₁=1, а средняя длина между соседями равна E[Yⱼ₊₁]−E[Yⱼ]=1/(n+1). Линейность среднего применима, хотя сами промежутки зависимы.

Для интервала [2,8] с тремя точками среднее второго положения равно 2+6·2/4=5, а первого 2+6/4=3,5. Само положение не обязано совпасть с этими числами. Например, все три точки могут оказаться близко к 8. Тогда внутренние промежутки малы, а первый велик, но при повторениях такие конфигурации уравновешиваются другими.

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

Считают n вместо n+1, забывая крайний промежуток. Или используют среднее случайно выбранной точки для минимума. Обе ошибки заметны уже для n=1: единственная U[0,1] имеет среднее 1/2, а формула 1/n дала бы 1. Проверка самого маленького размера помогает выявить неверный знаменатель.

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

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

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

Теперь сам

Пять независимых точек равномерны на [10,22]. Найди среднее самой ранней и четвёртой по порядку. Затем скажи, равны ли средние промежутки постоянным промежуткам в каждом эксперименте.