Один на миллион

16 April 2012 theory math

Вам наверное приходилось слышать что-то вроде: “Этого не может быть. Вероятность этого менее одной миллионной”. В бытовом понимании одна миллионная это некая несвершимая вероятность. Другими словами, этого просто не может произойти. Но насколько это вeрятное событие, если вы повторите эксперимент миллион раз? Конечно, вероятность наблюдать событие растет если вы повторяете эксперимент много раз подряд. Но все равно мы зачастую подсознательно пытаемся игнорировать такие события считая их невероятными.

Тем не менее, в современных Интернет-системах которые обрабатывают миллионы запросов в сутки не заметить в течение дня событие с вероятностью в одну миллионную довольно сложно. И вот почему. Вероятность что интересующее нас событие (с исходной вероятностью 1/n) не проявит себя ни в одном из n независимых экспериментов равно:

В этой формуле $\frac{1}{n}$ — вероятность события которое реализуется в одном эксперименте из . соответственно вероятность что это событие не реализуется в ходе эксперимента. Ну и не тяжело догодаться что $(1-\frac{1}{n})^n$ это вероятность с которой это событие не реализуется в ходе независимых экспериментов. Для n = 1 000, если вы его подставите в формулу, итоговое значение вероятности составит 0.368 или 36.8%. Для n = 1 000 000, значение вероятности составит… те же самые 36.8%! Редкость события всегда уравновешивается частотой повторения испытаний.

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

Второй замечательный предел интенсивно используется при решении дифференциальных уравнений, но нас интересует одно из следствий этого предела.

Этот предел говорит нам о том что при растущем n, значение выражения стремится к значению , которое является той самой константой приблизительно равной 0.368.

Я не буду здесь приводить доказательство этого следствия второго замечательного предела. Предел разумного количества формул на один пост достигнут :).

Теперь давайте соберем все это вместе. Предположим что у вас есть некий баг (скажем, race condition в многопоточном приложении), который воспроизводится с вероятностью один на миллион. Фактически что говорит этот предел – если вы обслужите за день миллион запросов то вероятность того что этот баг не порявит себя ни в одном из запросов ~37%. То есть с вероятностью ~63% этот баг даст о себе знать хотя бы один раз за сутки.

Из этого можно сделать еще один вывод. Чем больше запросов вы обрабатываете за сутки, тем более редкие явления вы будете наблюдать в течение суток. 100 000 запросов в сутки? Тогда вероятность для вас не редкость. 10 000 000? Тогда и одной десятимиллионной вас не удивишь.

Да пребудет с вами нормальное распределение!