Асимптотически достоверное событие

Асимптотически достоверное событие — событие, вероятность которого зависит от некоторого параметра $\text{[math]}$ $\text{[math]}$ $n$ $n$ и стремится к $\text{[math]}$ $\text{[math]}$ $1$ $1$ при $\text{[math]}$ $\text{[math]}$ $n$ $n$ стремящемся к бесконечности, то есть, вероятность данного события может быть сделана сколь угодно высокой путём увеличения $\text{[math]}$ $\text{[math]}$ $n$ $n$ . Про такое событие говорят, что оно происходит «с высокой вероятностью» (англ. with high probability, обычно сокращается до w.h.p.) или «асимптотически почти наверное» (asymptoticaly almost surely). Всякое почти достоверное событие (которое происходит с вероятностью $\text{[math]}$ $\text{[math]}$ $1$ $1$ ) асимпотически достоверно, обратное неверно.

Используется в информатике при асимптотическом анализе вероятностных алгоритмов. Например, если некоторый алгоритм работает на графах с $\text{[math]}$ $\text{[math]}$ $n$ $n$ вершинами и вероятность того, что алгоритм выдаст правильный результат равна $\text{[math]}$ $\text{[math]}$ $1-1/n$ $1-1/n$ , то при достаточно большом количестве вершин в графе вероятность того, что алгоритм выдаст правильный ответ будет близка к $\text{[math]}$ $\text{[math]}$ $1$ $1$ , то есть, можно говорить, что «алгоритм корректен с высокой вероятностью».

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

тест Миллера — Рабина: вероятностный алгоритм для проверки того, является ли число $\text{[math]}$ $\text{[math]}$ $n$ $n$ простым или составным, если $\text{[math]}$ $\text{[math]}$ $n$ $n$ — составное, то алгоритм определит это с высокой вероятностью;
алгоритм Фрейвалдса: рандомизированный алгоритм для проверки матричного произведения, работает быстрее известных детерминированных алгоритмов с высокой вероятностью;
декартово дерево: рандомизированное бинарное дерево поиска, высота которого логарифмична с высокой вероятностью.

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

Выделяется класс сложности BQP, состоящий из задач, для которых существуют полиномиальные квантовые алгоритмы, корректные с высокой вероятностью.

Ссылки Править

Métivier, Y.; Robson, J. M.; Saheb-Djahromi, N.; Zemmari, A. An optimal bit complexity randomized distributed MIS algorithm (англ.) // Distributed Computing : journal. — 2010. — Vol. 23, no. 5—6. — P. 331. — doi:10.1007/s00446-010-0121-5.
Principles of Distributed Computing (lecture 7) (неопр.). ETH Zurich. Дата обращения: 21 февраля 2015. Архивировано из оригинала 21 февраля 2015 года.