| dbo:abstract
|
- En mathématiques et plus particulièrement en théorie des probabilités, une suite d'évènements, indexée par les entiers naturels, se réalise avec grande probabilité si la probabilité que le n-ième évènement se réalise converge vers 1 à l'infini. (fr)
- In mathematics, an event that occurs with high probability (often shortened to w.h.p. or WHP) is one whose probability depends on a certain number n and goes to 1 as n goes to infinity, i.e. the probability of the event occurring can be made as close to 1 as desired by making n big enough. (en)
- Асимптотически достоверное событие — событие, вероятность которого зависит от некоторого параметра и стремится к при стремящемся к бесконечности, то есть, вероятность данного события может быть сделана сколь угодно высокой путём увеличения . Про такое событие говорят, что оно происходит «с высокой вероятностью» (англ. with high probability, обычно сокращается до w.h.p.) или «асимптотически почти наверное» (asymptoticaly almost surely). Всякое почти достоверное событие (которое происходит с вероятностью ) асимпотически достоверно, обратное неверно. Используется в информатике при асимптотическом анализе вероятностных алгоритмов. Например, если некоторый алгоритм работает на графах с вершинами и вероятность того, что алгоритм выдаст правильный результат равна , то при достаточно большом количестве вершин в графе вероятность того, что алгоритм выдаст правильный ответ будет близка к , то есть, можно говорить, что «алгоритм корректен с высокой вероятностью». Некоторые алгоритмы, использующие понятие асимптотической достоверности:
* тест Миллера — Рабина: вероятностный алгоритм для проверки того, является ли число простым или составным, если — составное, то алгоритм определит это с высокой вероятностью;
* алгоритм Фрейвалдса: рандомизированный алгоритм для проверки матричного произведения, работает быстрее известных детерминированных алгоритмов с высокой вероятностью;
* декартово дерево: рандомизированное бинарное дерево поиска, высота которого логарифмична с высокой вероятностью. В машинном обучении применяется схема вероятно приближённо корректного обучения, в котором конструируемая функция обладает низкой ошибкой обобщения с высокой вероятностью. Выделяется класс сложности BQP, состоящий из задач, для которых существуют полиномиальные квантовые алгоритмы, корректные с высокой вероятностью. (ru)
|
| rdfs:comment
|
- En mathématiques et plus particulièrement en théorie des probabilités, une suite d'évènements, indexée par les entiers naturels, se réalise avec grande probabilité si la probabilité que le n-ième évènement se réalise converge vers 1 à l'infini. (fr)
- In mathematics, an event that occurs with high probability (often shortened to w.h.p. or WHP) is one whose probability depends on a certain number n and goes to 1 as n goes to infinity, i.e. the probability of the event occurring can be made as close to 1 as desired by making n big enough. (en)
- Асимптотически достоверное событие — событие, вероятность которого зависит от некоторого параметра и стремится к при стремящемся к бесконечности, то есть, вероятность данного события может быть сделана сколь угодно высокой путём увеличения . Про такое событие говорят, что оно происходит «с высокой вероятностью» (англ. with high probability, обычно сокращается до w.h.p.) или «асимптотически почти наверное» (asymptoticaly almost surely). Всякое почти достоверное событие (которое происходит с вероятностью ) асимпотически достоверно, обратное неверно. (ru)
|
