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

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

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

$P_n^k = 1, n \in {1}..{k-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-l}^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$

Таким образом, имеем рекурсивное определение обратной к интересующей нас вероятности. Давайте имплементируем это на Python:

Отладочный скрипт с brute-force для маленьких n

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])

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