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

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

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

• тест Миллера — Рабина : вероятностный алгоритм для проверки того, является ли число ${\displaystyle n}$ простым или составным, если ${\displaystyle 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 : .
• (неопр.) . ETH Zurich. Дата обращения: 21 февраля 2015. Архивировано из 21 февраля 2015 года.