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

Асимптотически достоверное событие — событие, вероятность которого зависит от некоторого параметра $n$ и стремится к $1$ при $n$ стремящемся к бесконечности, то есть, вероятность данного события может быть сделана сколь угодно высокой путём увеличения $n$. Про такое событие говорят, что оно происходит «с высокой вероятностью» (Шаблон:Lang-en, обычно сокращается до Шаблон:Lang-en2) или «асимптотически почти наверное» (Шаблон:Lang-en2). Всякое почти достоверное событие (которое происходит с вероятностью $1$) асимптотически достоверно, обратное неверно.

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

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

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

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

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

Ссылки

• Шаблон:Статья
• Шаблон:Cite web