Последовательный Хи-Квадрат и процесс Бесселя

Начнем с простого описания процесса динамического сплитования: день ото дня трафик пользователей разбивается на в группы A и B в установленной пропорции как 50/50. Мы хотим тестом проверять день ото дня, а нет ли сильного расхождения с этими ожиданиями, корректно ли работает сплитование.

На конец дня day мы знаем объем трафика, например, n_day, поэтому зная сколько попало в А_day за это день, легко можно рассчитать B_day = n_day - A_day. То есть фактически “свободно” может меняться по объему людей лишь одна из k сторон, вторая определяется автоматически, наша степень свободы тогда d = k - 1 = 1, ну и смотреть поэтому достаточно только на A день ото дня:

Пускай у нас каждый день заходит 1000 человек, на каждый день будем считать суммарный с прошлыми днями размер выборки А:

Рассчитаем разницу, Diff, между A и ожиданиями по А:

Рассмотрим на графике этот Diff:

Несмотря на то, что есть как будто тенденция вниз, в симуляции я закладывал верность H0: что разбиение действительно 50/50, отсюда мы имеем дело с частной реализацией случайного блуждания.

Вот как могло бы получить иначе при тех же условиях честного сплита:

На самом деле мы наблюдаем классическое случайное блуждание из-за E(Diff) = 0. Чуть формализуем: у нас есть сумма отклонений, Diff, которая эволюционирует со временем, что соответствует случайного блуждания, W_t:

Сразу проговорим: t у нас принимает значения от 0 до 1, но где 1 - это момент окончания эксперимента. То есть значения между 0 и 1 это “доля” набора аудитории от целевого значения.

Чем еще, кроме E(Diff)=0, докажем, что это случайное блуждание?

• Независимость шагов: то, какой пользователь придет следующим (в группу А или B), никак не зависит от того, кто пришел раньше. Это значит, что наше отклонение на каждом шаге "забывает" прошлое и делает новое случайное отклонение
• Накопление: наш Diff сейчас - это предыдущий Diff плюс отклонение, которую получили в этот момент.

В виду пункта про накопление отмечу, что в математике сумма бесконечно малых случайных отклонений соответствует Винеровскому процессу, случайного блуждания с непрерывным временем, то есть наша эволюция суммы Diff'а почти сводима к этому процессу, однако для него характерна дисперсия W_t = t, - то есть чем дольше процесс, тем пропорционально больше разброс.

Попробуем это учесть для корректности нашего приближения к W_t, умножив последнее на K, корректируй коэффициент, который нам надо будет оценить:

1) Для начала слегка перепишем наше выражение: так как наблюдения (Obs) - это размер выборки, например, по A (обозначим индексом "1"), а ожидания (Exp) это у нас сколько должно было быть по A как доля, p_1, от полного объема аудитории, N_t, то:

2) Рассмотрим дисперсию, D, нашей перезаписи.

3) По свойству дисперсии D(aX) = a^2*D(X):

4) Теперь внимание на левую часть. Что такое n_1,t ? Это количество людей, которые попали в А к моменту t. Раз уж мы занимаемся статистикой, то каждый пользователь - это случайная величина X_i, которая принимает значение 1 (попал в группу 1) или 0 (не попал). Тогда количество людей в первой группе к моменту N_t это просто сумма:

А это сумма Бернулли по сути биномиальная величина, её дисперсия хорошо известна, классика же:

Но у нас-то D(n_1,t - p_1*N_t)! Ничего страшного, остаточный член, p_1*N_t это константа, так как это фиксированное ожидание на некоторый момент, а по свойству дисперсии D(X+a) = D(X), значит:

5) Теперь заменим N_t на N*t, где N - конец эксперимента. Это логично, ведь мы получаем на момент t долю от N, а t у нас от 0 до 1. Ну и p1(1-p1) заменим на сигму^2:

Тогда: 

6) D(W) = t к моменту t, тогда:

7) Выходит:

Следовательно:

Смотрим на левую часть -> там все также сверху наблюдения против ожиданий, а внизу еще и стандартизация. Это сильно напоминает вдоль и поперёк изученный Хи-Квадрат, не хватает только квадратов в числителе и знаменателе, так давайте возведем обе части в квадрат!

То есть квадрат Винеровского процесса, то есть квадрат нашего блуждания Diff, описывается Хи-Квадратам, что крайне удобно: готовые расчетные таблицы для значимости и пр. Fit -> test!

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

Сразу обобщим для случая A/B/C и более:

Рассмотрим левую часть. Если мы суммируем квадраты независимых случайных блужданий и далее берем из этой суммы корень, то мы получаем то, что называется процессом Бесселя (вы знаете эту фамилию по поправке выборочной дисперсии n-1):

Тут можно мыслить себе это как аналог евклидового расстояния для случайных блужданий. Коль уж блуждание часто ассоциируют с походкой пьяного, то пускай будет пьяный матрос, у которого есть ром, точнее только широта и долгота, d=2. Вот он вышел из припортового кабака, зашагал и попал некоторую точку на момент t. Расстояние от кабака до точки и будет это R.

Итого, возвращаясь к нашему преобразование получается, что на каждый момент t у нас есть свое распределение Хи-Квадрат, далее почти по классике, задавай правильно границы значимости, соблюдай ошибку 1-го рода. Проблема в том, что на каждый момент времени задать одну и ту же альфу мы не можем, иначе ошибаться мы будем чаще желаемого.

Поэтому здорово, что подобные решение этого мы с вами разбирали в контексте Group Sequential Testing, одно из возможных, это разбить через α-spending функцию α(t) базовую альфу на несколько так, чтоб в сумме у нас было 0.05. Например, в первый день = 0.005, в пятый = 0.015, а на последний = 0.03. Цена этого одна: в конце теста мощности для проверки SRM будет меньше, чем при классическом сценарии fix horizon из-за альфы 0.03 вместо 0.05. 

Тут бы и закончить, но… что если мы можем подобрать α-spending функцию, согласованную с случайным блужданием? 

Отмечу момент у Вити:

- при H0 у нас будет сходимость по распределению (будут, условно, одинаково распределены) между T и процессом Бесселя:

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

Давайте глубо посмотрим на случайное блуждание: что если рассмотреть наш Diff между А и ожиданиями по A в логике реального время, то есть непрерывно?

Сделаем это через пользователей. Пускай у нас есть статус попадания в группу для каждого человека, X, такой, что если = 1, то  A, если = -1, то B. Запускаем трафик и в порядке очереди для каждого подкидываем честную монетку, где Орел = 1, Решка = -1, это нам и даст группу этого человека. Отсюда Diff первого дня мы можем записать как:

А real-time тогда было бы так, где Diff будет S - сумма:

Что можно переупаковать так:

Результат, - и всё тот же W_t, - одной из симуляции:

При этом сумма квадратов W_t или просто квадрат R ведёт себя, с учетом нормировки на расчетное количество юзеров, так:

Критические значения

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

Поэтому нужно использовать функцию, которая будет “охватывать”, “обволакивать” этот “пилу”, которая, условно, на любом участке может стремительно изменить свое поведение, то есть нужна такая функция, которая будет отталкиваться от изменения скорости процесса со временем. Рассмотрим несколько вариантов:

Для последних функций двух в самый первый момент времени t будет стоять 95-ый квантиль Хи-Квадрата, чтобы создать буфер между первым значением нашего блуждания и границей значимости. 

Далее отметим, что все функции непрерывные, но красная сначала прирастает очень медленно, что создает риск того, что блуждание ее пересечёт, а далее резко возрастает, сильно опережая темп целевой величины. Это само по себе намекает на то, что должен быть как-то учет темп приращения скорости процесса.

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

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

Получается, желтая B(t) лучше остальных именно потому, что она повторяет максимальную кривизну шума, а поэтому является наилучшим кандидатом для границ значимости. Я недаром сказал два раза слово “максимально”: граница идет всегда по самому высокому краю, а значит, - если переводить это альфу, - на каждый момент t у нас будет очень жесткий уровень значимости, то есть очень малые альфы. В свою очередь это означает, что нам нет острой необходимости заботится о сумме альф = 0.05, они примерно таковыми и будут, то есть гарантируется математическая робастность теста при любом количестве проверок. С одной оговоркой: на конец теста у нас будет совсем уж крохотная альфа для проверки SRM, но у всего есть своя цена.

Итого, если мы хорошо можем оценить процесс, то можем и вывести максимальные границы его движения, что даст нам все для автоматического мониторинга, где не надо планировать кол-во подглядываний. Другое дело, что все это немалая нагрузка при масштабировании на ряд тестов одновременно. И не проще ли пойти в заранее согласованные подглядывания по упомянутому ранее GST? Это буквально можно сделать "на коленке" с большей мощностью, понятными моментами для подглядывания, легкоcтью поддержки и погружения в метод и пр. Мой ответ такой: если бы выбирал меж всех этих методов, то на текущий момент это был бы GST.

Опорный материал

Последовательный критерий хи-квадрат для проверки SRM, см. в комментариях презентацию