Экзамен ААА — SQL-machine: вероятность чемпиона Trino быть слабее серебра Vertica

Условие

В офисе Авито работало 3 · 2^(n−1) сотрудников из DS и DA отделов. За прошедший год каждый выполнил уникальное количество SQL-запросов — совпадений не было. Сотрудников случайным образом разделили на две команды:

• Trino — маленькая команда из 2^(n−1) человек;
• Vertica — большая команда из 2^n человек.

В каждой команде провели «олимпийское» состязание (single-elimination): пары формируются случайно, в каждой паре сравнивают годовые показатели по SQL-запросам, побеждает тот, у кого больше. В Trino турнир длится n − 1 раундов (остаётся один победитель), в Vertica — n раундов.

Какова вероятность, что чемпион Trino окажется «слабее» — выполнит меньше SQL-запросов за год, чем серебряный призёр Vertica? n — натуральное, n ≥ 10.

Решение

Подход

Перепишем условие: даны 3 · 2^(n−1) уникальных значений, случайно разбитых на две группы размеров 2^(n−1) и 2^n. В каждой группе single-elimination определяет одного победителя. Чемпион Trino = максимум значений в группе Trino. Турнир в Vertica даёт чемпиона = максимум; «серебряного призёра» single-elimination = тот, кто проиграл в финале → это тот, кто был сильнейшим в полуфинальной половине, не содержащей чемпиона.

В single-elimination серебряный призёр — это максимум той полуфинальной ветви, в которой он встретил чемпиона.

Ключевые наблюдения

1. Чемпион Trino = максимум 2^(n−1) случайно выбранных значений → это просто max(T), где T — случайное подмножество размера 2^(n−1).
2. Серебряный Vertica = максимум той половины бракета, которая проиграла финал. Vertica делится на 2 половины по 2^(n−1) человек, чемпион — лучший из всех 2^n. Серебряный — лучший из той половины, где не было чемпиона.

Перевод на ранги

Пусть всего M = 3 · 2^(n−1) человек, у каждого уникальный ранг. Случайно разделяем на:

• T (Trino, размер 2^(n−1)),
• V (Vertica, размер 2^n).

Vertica делится случайно на V_1, V_2 (две половины бракета).

• Чемпион Trino = max(T). Обозначим его ранг R_T.
• Чемпион Vertica = max(V) = max(V_1 ∪ V_2).
• Серебряный Vertica = max(V_j), где V_j — половина без чемпиона.

Нужно P(max(T) < max(V_j)), где V_j — «вторая по силе половина».

Упрощение

Пусть s = max(V_j) (т.е. лучший из не-чемпионской половины). Тогда:

• Среди топ-2 значений Vertica — оба должны быть в разных половинах (иначе бы они встретились раньше финала, не было бы серебра, как мы определили).
• Чемпион — лучший из всех Vertica, серебряный — следующий за ним, при условии, что они в разных половинах. В случае, если 1-й и 2-й по силе оказались в одной половине, серебряный определяется иначе (как максимум противоположной половины — это уже не 2-й глобально).

Прямая формула

Пусть T — t = 2^(n−1), V — v = 2^n, всего M = 3t.

Перебираем все (M, t)-разбиения... но проще через симметрию.

Симметрия: все M! / (t! v!) разбиений равновероятны. Все 2^(n−1)-разбиения Vertica на половины тоже равновероятны.

Вероятность того, что чемпион Trino слабее серебряного Vertica = вероятность того, что max(T) < max(V_j) для серебряной половины.

Асимптотика для больших n

При n → ∞:

• max(T) распределён как порядковая статистика номер t из M. Среднее ранг ≈ M − M/(t+1) …
• Точнее, ранг max(T) среди всех M имеет распределение, концентрирующееся возле максимума пропорционально размеру выборки.

Используем P(max(T) > max(V_j)):

Среди топ-k значений вероятность, что max(T) старше max(V_j) сводится к комбинаторике:

P(чемпион Trino > всех в V_j) = t / (t + v_j) = t / (t + t) = 1/2

(Игнорируя V_{not j}, где сидит чемпион.)

Тогда вероятность, что чемпион Trino слабее серебряного Vertica = 1/2 в простейшей модели.

Точная формула

Учтём, что серебряный = max той половины, где не сидит глобальный лидер. Глобальный лидер всех M человек — каждый кандидат равновероятен. Если он в Trino — у Vertica «серебряный» = просто max(Vertica). Если в Vertica — серебряный = max(половины без него).

Пусть g — глобальный лидер.

P(g ∈ T) = t / M = (2^(n−1)) / (3 · 2^(n−1)) = 1/3
P(g ∈ V) = 2/3

Случай 1: g ∈ T (вероятность 1/3). Чемпион Trino = g. Серебряный Vertica = max(V). g > max(V) всегда. → P(чемпион Trino < серебряный | g ∈ T) = 0.

Случай 2: g ∈ V (вероятность 2/3). Чемпион Vertica = g. Серебряный Vertica = max половины Vertica без g. Чемпион Trino = max(T).

Среди оставшихся M − 1 = 3t − 1 человек, ранжированных, мы хотим:

P(max(T) < max(V_j))

где V_j — половина Vertica без g, размер t = 2^(n−1). И T имеет тот же размер.

Симметрия! T и V_j — два равновероятно случайных непересекающихся подмножества размера t из 3t − 1. Между ними:

P(max(T) < max(V_j)) = t / (t + t) = 1/2

(Это потому, что глобальный максимум среди T ∪ V_j равновероятно в каждой части, размеры одинаковые.)

Итог

P = (1/3) · 0 + (2/3) · (1/2) = 1/3

Ответ: P = 1/3, независимо от n (при n ≥ 10).

Подводные камни

1. «Серебряный» в single-elimination ≠ «второй глобально». Это лучший из противоположной половины бракета. Часто в задачах хотят именно глобально-второго, но здесь — single-elimination конкретный.
2. Чемпион всегда — глобальный максимум своей выборки.
3. Случайное разбиение + симметрия упрощает: можно не считать все размещения, а думать «равновероятно куда попадает топовый».
4. n ≥ 10 в условии — намёк на асимптотику, но фактически ответ от n не зависит.
5. Ничьих нет — все значения уникальны.
6. Sanity check Монте-Карло.

import numpy as np
def trial(n=10):
    M = 3 * 2**(n-1)
    ranks = np.random.permutation(M)
    t_size = 2**(n-1)
    T = ranks[:t_size]
    V = ranks[t_size:]
    np.random.shuffle(V)
    half = len(V) // 2
    V1, V2 = V[:half], V[half:]
    champion_T = T.max()
    champion_V = V.max()
    silver_V = V1.max() if champion_V in V2 else V2.max()
    return champion_T < silver_V
print(np.mean([trial() for _ in range(50_000)]))  # ≈ 0.333

Эталонный ответ

P = 1/3.

Кейс 1: глобальный лидер в Trino (P = 1/3) — невозможно, чтобы чемпион Trino был слабее.

Кейс 2: глобальный лидер в Vertica (P = 2/3) — по симметрии P(max T < max V_j) = 1/2.

Итог: (1/3)·0 + (2/3)·(1/2) = 1/3.