높은 확률로
With high probability수학에서 높은 확률로 발생하는 사건(흔히 w.h.p. 또는 WHP로 단축됨)은 확률이 특정 숫자 n에 의존하고 n이 무한대로 가면서 1로 가는 사건, 즉 n을 충분히 크게 만들어 원하는 만큼 1에 가깝게 만들 수 있는 사건이다.
적용들
WHP라는 용어는 확률론적 알고리즘 분석에서 특히 컴퓨터 공학에서 사용된다.예를 들어, 노드가 n개인 그래프에서 특정 확률 알고리즘을 고려하십시오.알고리즘이 정답을 반환할 확률이 1 - / 1-1/인 경우 노드 수가 매우 클 때 알고리즘은 1에 가까운 확률로 정확하다.이 사실은 알고리즘이 정확한 WHP라는 말로 금방 표현된다.
이 용어를 사용하는 몇 가지 예는 다음과 같다.
- Miller-Rabin primality test: 주어진 숫자 n이 primary인지 복합적인지를 테스트하기 위한 확률론적 알고리즘.n이 복합적인 경우, 테스트는 n을 복합적인 WHP로 감지한다.우리가 운이 없을 가능성이 적으며 시험은 n이 프라임이라고 생각할 것이다.그러나 다른 무작위로 여러 번 테스트를 실행하면 오차의 확률을 무한정 줄일 수 있다.
- Freivalds 알고리즘: 행렬 곱셈을 확인하기 위한 랜덤화 알고리즘.그것은 결정론적 알고리즘 WHP보다 더 빨리 실행된다.
- Treap: 임의의 이진 검색 트리.그것의 높이는 로그 WHP이다.퓨전 트리는 관련 데이터 구조다.
- 온라인 코드: 사용자가 원본 메시지 WHP를 복구할 수 있는 임의 코드.
- BQP: 정확한 WHP인 다항식 시간 양자 알고리즘이 존재하는 문제의 복잡도 등급이다.
- 대략적으로 정확한 학습: 학습된 기능이 낮은 일반화 오류 WHP를 갖는 기계 학습 프로세스.
- 가십 프로토콜: 각 노드의 일정한 네트워크 자원을 사용하여 전체 클러스터에 메시지를 신뢰성 있게 전달하고 단일 장애 지점이 없도록 하기 위해 분산 시스템에서 사용되는 통신 프로토콜.
참고 항목
참조
- Métivier, Y.; Robson, J. M.; Saheb-Djahromi, N.; Zemmari, A. (2010). "An optimal bit complexity randomized distributed MIS algorithm". Distributed Computing. 23 (5–6): 331. doi:10.1007/s00446-010-0121-5.
- "Principles of Distributed Computing (lecture 7)" (PDF). ETH Zurich. Retrieved 21 February 2015.
