С большой вероятностью

В математике событие, которое происходит с высокой вероятностью (часто сокращается до wp или WHP ), — это событие, вероятность которого зависит от определенного числа n и стремится к 1 при стремлении n к бесконечности, т. е. вероятность возникновения события может быть сделана максимально близкой к 1. до 1 по желанию, сделав n достаточно большим.

Приложения

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

Некоторые примеры использования этого термина:

• Тест на простоту Миллера-Рабина : вероятностный алгоритм проверки того, является ли данное число n простым или составным. Если n является составным, тест обнаружит n как составное WHP. Есть небольшая вероятность, что нам не повезет и тест посчитает, что n простое. Но вероятность ошибки можно уменьшить на неопределенный срок, проведя тест много раз с разной рандомизацией.
• Алгоритм Фрейвалдса : рандомизированный алгоритм проверки умножения матриц. Он работает быстрее, чем детерминированные алгоритмы WHP.
• Treap : рандомизированное двоичное дерево поиска. Его высота равна логарифму WHP. Дерево слияния — это связанная структура данных.
• Онлайн-коды : рандомизированные коды, которые позволяют пользователю восстановить исходное сообщение WHP.
• BQP : класс сложности задач, для которых существуют квантовые алгоритмы с полиномиальным временем, правильные WHP.
• Вероятно, приблизительно правильное обучение : процесс машинного обучения, в котором изученная функция имеет низкую ошибку обобщения WHP.
• Протоколы сплетен : протокол связи , используемый в распределенных системах для надежной доставки сообщений всему кластеру, используя постоянный объем сетевых ресурсов на каждом узле и гарантируя отсутствие единой точки отказа.

См. также

• Рандомизированный алгоритм
• Почти наверняка

Ссылки

• Метивье, Ю.; Робсон, Дж. М.; Сахеб-Джахроми, Н.; Земмари, А. (2010). «Рандомизированный распределенный алгоритм MIS с оптимальной битовой сложностью». Распределенные вычисления . 23 (5–6): 331. doi : 10.1007/s00446-010-0121-5 .
• «Принципы распределенных вычислений (лекция 7)» (PDF) . ETH Цюрих . Проверено 21 февраля 2015 г.