История одного алерта или вероятность последовательности одинаковых событий Бернулли15.12.2024 16:30

Не так давно столкнулся с алертом, который работает следующим образом: раз в 10 секунд пробер делает HTTP-запрос до другого сервиса и увеличивает метрику со счетчиком ошибок, в случае провала. Если 6 раз подряд происходят ошибки, алерт активизируется и привлекает внимание человека. В моем конкретном случае за одним DNS именем целевого сервиса скрывается 10 различных IP-адресов, и в какой-то момент 2 из них стали отвечать чуть дольше обычного, приводя к периодическому срабатыванию данного алерта. Вначале я подумал, что вероятность такого срабатывания небольшая, интуитивно оценив ее в $\sim (2/10)^6 = 0.000064$ . Но алерт срабатывал в среднем раз в сутки, поэтому после нескольких дней я решил починить его. Тем не менее, ради любопытства стало интересно посчитать точную вероятность срабатывания его минимум раз в сутки, ибо она явно отличалась от данной выше оценки.

Сделаем важную оговорку — измерения пробера независимы друг от друга. Пусть q = 0.2 вероятность провала измерения, тогда 1-q = 0.8 вероятность успеха. Давайте посчитаем обратную вероятность: это будет проще. Обозначим за P_n ^k вероятность того, что цепочка измерений (событий) длиной не содержит подряд идущих ошибочных измерений. Возьмем за очевидную базу:

$P_n^k = 1, n \in {1}..{k-1}$ P_n^k = 1 - q^k, n=k

Теперь рассмотрим ситуацию n > k» src=«https://habrastorage.org/getpro/habr/upload_files/306/678/08a/30667808af06458a4127e10e8d0a9d8a.svg» />. Обозначим вероятность последовательности измерений длины <img alt= не содержащей подряд идущих неудачных измерений заканчивающуюся на успешное измерение и l-1 неуспешных за $Q_n^k(l), l \le k$ .

Пример для , значения :	Окончания последовательностей: 0 — успех, 1 — ошибка
1	`........0`
2	`.......01`
3	`......011`
4	`.....0111`
5	`....01111`
6	`...011111`

В силу независимости отдельных измерений имеем:

$Q_{n}^k(l) = P_{n-i}^k(1-q)q^{l-1}$

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

$P_n^k = \sum_{i=1}^{k}Q_{n}^k(i) =\sum_{i=1}^{k}P_{n-i}^k(1-q)q^{i-1}, n > k» src=«https://habrastorage.org/getpro/habr/upload_files/aea/6f7/c8a/aea6f7c8a62bfdd3410387fdf7562c73.svg» /> Таким образом, имеем рекурсивное определение обратной к интересующей нас вероятности. Давайте имплементируем это на Python: Отладочный скрипт с brute-force для маленьких n <div><pre><code class=$ from itertools import * q = 0.2 p = 1 - q k = 6 n = 20 all = list(product([0,1],repeat=n)) positive = 0 negative = 0 for seq in all: longestK = len(max(''.join(str(x) for x in seq).split('0'))) probability = 1 for item in seq: if item == 1: probability *= q else: probability *= p if longestK < k: positive += probability else: negative += probability print(positive, negative, positive + negative)

q = 0.2 # вероятность ошибочного измеренеия
p = 1 - q # вероятность успешного измерения
k = 6 # количество неуспешных измерений подряд, вызвающее срабатывание алерта
n = 8640 # 60s * 60m * 24h / 10s
# probabilities[n] - не случится для измерений длины n
probabilities = [1] * k # под индексом 0 - игнорируем
probabilities.append(1 - q ** k)

multipliers = [(p * q ** step) for step in range(0, k)]
multipliers.reverse()

for _ in range(k + 1, n + 1):
    multiplied = [a * b for a, b in zip(multipliers, probabilities[-k:])]
    probabilities.append(sum(multiplied))

print(1 - probabilities[n])

В результате для чисел выше получаем 0.35742 , что выглядит очень и очень много по сравнению с интуитивным предположением, чтобы пренебрегать срабатыванием данного алерта. Для наглядности можно посмотреть на график, который показывает, что при фиксированном и увеличении — количества измерений, вероятность появления цепочки ошибок длиной стремится к .

P.S. Ну и куда без этого: подписывайтесь на мой телеграмм канал, где я галлюцинирую на разные темы, буду рад новым читателям.