Асимптотически достоверное событие — событие, вероятность которого зависит от некоторого параметра и стремится к при стремящемся к бесконечности, то есть, вероятность данного события может быть сделана сколь угодно высокой путём увеличения . Про такое событие говорят, что оно происходит «с высокой вероятностью» (, обычно сокращается до ) или «асимптотически почти наверное» (). Всякое почти достоверное событие (которое происходит с вероятностью ) асимптотически достоверно, обратное неверно.
Используется в информатике при асимптотическом анализе вероятностных алгоритмов. Например, если некоторый алгоритм работает на графах с вершинами и вероятность того, что алгоритм выдаст правильный результат равна , то при достаточно большом количестве вершин в графе вероятность того, что алгоритм выдаст правильный ответ будет близка к , то есть, можно говорить, что «алгоритм корректен с высокой вероятностью».
Некоторые алгоритмы, использующие понятие асимптотической достоверности: тест Миллера — Рабина: вероятностный алгоритм для проверки того, является ли число простым или составным, если — составное, то алгоритм определит это с высокой вероятностью; алгоритм Фрейвалдса: рандомизированный алгоритм для проверки матричного произведения, работает быстрее известных детерминированных алгоритмов с высокой вероятностью; декартово дерево: рандомизированное бинарное дерево поиска, высота которого логарифмична с высокой вероятностью.
В машинном обучении применяется схема вероятно приближённо корректного обучения, в котором конструируемая функция обладает низкой ошибкой обобщения с высокой вероятностью.
Выделяется класс сложности BQP, состоящий из задач, для которых существуют полиномиальные квантовые алгоритмы, корректные с высокой вероятностью.
Ссылки
Категория:Теория вероятностей