Original article: w:With high probability
수학(mathematics)에서, 높은 확률과 함께(with high probability, 종종 w.h.p. 또는 WHP로 약칭됨) 발생하는 사건은 그 확률이 특정 숫자 n에 따라 달라지고 n이 무한대로 갈수록 1로 가는 사건, 즉, 사건 발생의 확률이 n을 충분히 크게 만듦으로써 원하는 대로 1로 만들 수 있습니다.
Applications
WHP라는 용어는 특히 컴퓨터 과학(computer science), 확률적 알고리듬(probabilistic algorithms)의 해석에서 사용됩니다. 예를 들어, n개의 노드를 갖는 그래프에서 특정 확률적 알고리듬을 생각해 보십시오. 만약 알고리듬이 정확한 답을 반환할 확률이 \(1-1/n\)이면, 노드의 개수가 매우 많을 때 알고리듬은 1에 매우 가까운 확률로 정확합니다. 이 사실은 알고리듬이 올바른 WHP라고 말함으로써 간단히 표현됩니다.
이 용어가 사용되는 몇 가지 예는 다음과 같습니다:
- 밀러-라빈 소수성 테스트(Miller–Rabin primality test): 주어진 숫자 n이 소수인지 합성수인지 테스트하기 위한 확률적 알고리듬. 만약 n이 합성수이면, 테스트는 n을 합성 WHP로 감지할 것입니다. 우리가 운이 좋지 않을 가능성이 적고 테스트에서 n이 소수라고 생각할 것입니다. 그러나, 다른 무작위화를 갖는 테스트를 여러 번 실행하면 오류 확률을 무한정 줄일 수 있습니다.
- 프레이발츠의 알고리듬(Freivalds' algorithm): 행렬 곱셈을 검증하기 위한 무작위 알고리듬. 그것은 결정론적 알고리듬 WHP보다 빠르게 실행됩니다.
- Treap: 무작위 이진 검색 트리. 그것의 높이는 로그 WHP입니다. 퓨전 트리(Fusion tree)는 관련된 데이터 구조입니다.
- Online codes: 사용자가 원본 메시지 WHP를 복구할 수 있는 무작위 코드.
- BQP: 올바른 WHP인 다항식-시간 양자 알고리듬이 있는 문제의 복잡성 클래스.
- Probably approximately correct learning: 학습된 함수가 낮은 일반화-오류 WHP를 가지는 기계-학습 과정.
- Gossip protocols: 각 노드에서 일정한 양의 네트워크 자원을 사용하고 단일 장애 지점이 없도록 전체 클러스터에 메시지를 안정적으로 전달하기 위해 분산 시스템(distributed systems)에서 사용되는 통신 프로토콜(communication protocol).
See also
References
- 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.
