건너 뛰기 목록에 대한 MIT 강의를 시청했습니다. 전반적으로 나는 자료를 이해하지만 한 가지가 있습니다. “높은 확률”이란 무엇입니까? 전혀 이해하지 못합니다. 강의 노트 를 보았지만 여전히 이해하지 못했습니다.
그냥 “$ \ alpha \ geq1 $에 대해 $ E $가 적어도 $ 1 − O (1 / n ^) 확률로 발생하는 상수의 적절한 선택이있는 경우 이벤트 $ E $는 높은 확률 (whp)로 발생합니다. \ alpha) $ “.
algorithmist.com 의 항목도 도움이되지 않았습니다.
무엇이 $ \ alpha $ 그리고 $ 1 − O (1 / n ^ \ alpha) $는 무엇입니까? 이 점을 이해하지 못하면 “$ n $ 요소 건너 뛰기 목록의 모든 검색에 $ O (\ lg n) $ 비용이들 가능성이 높을수록 높은 확률로”분석이 혼란스러워집니다.
댓글
- 무작위와 확률 알고리즘은 같은 것이 아닙니다 .
답변
$ p_n $ 확률로 발생하는 경우 $ n $ 매개 변수와 관련하여 이벤트가 높은 확률로 발생합니다. 및 $ \ lim_ {n \ to \ infty} p_n = 1 $. 일반적으로 $ n $ 매개 변수는 컨텍스트에서 명확합니다. 예를 들어,이 경우 목록에있는 요소의 수일 것입니다.
강의 노트에서 “높은 확률로”의 정의는 훨씬 더 구체적이며 $ p_n $가 얼마나 빨리 수렴해야 하는지를 지정합니다. $ 1 $까지 : $ C, \ alpha > 0 $에 대해 $ p_n \ geq C / n ^ \ alpha $ 확률로 발생하면 이벤트가 높은 확률로 발생합니다. 예를 들어 $ \ {0, \ ldots, n \} $에서 임의의 숫자를 선택하면 0이 아닐 확률이 $ 1-1 / (n + 1)이므로 확률이 높은 0이 아닙니다. \ geq 1-1 / n $ (이 경우 $ C = \ alpha = 1 $)
설명
- 제한 기준은 다음과 같습니다. " 거의 확실하게 "라고도합니다. 나는 " 높은 확률 "이 기하 급수적 인 비율로 1에 접근하는 확률을 언급 할 때 주로 사용되는 것을 보았습니다.
- " whp " 참조 일반적으로 " 거의 확실히 , 정의하지 않고 사용할 때 항상 이것이 제가 말하는 의미입니다. 그러나보다 일반적으로 " whp "는 1에 접근하거나 다 항적으로 1에 접근하거나 기하 급수적으로 1에 접근 함을 의미 할 수 있습니다. 후자의 의미로 사용하는 경우 명시 적으로 정의해야합니다.
- 정말로 당신은 ' $ p_n = 1-\ frac {를 호출합니다. 1} {\ log ^ * n} $ " 높은 확률로 "? ;)하지만 예 : 안전하려면 어떤 경우 에든 상황에서 의미하는 바를 정의하세요.
- WHP를 공식적으로 정의하는 표준 참조 (예 : 교과서)는 무엇입니까? 위키 백과 en.wikipedia.org/wiki/With_high_probability 에 WHP에 대한 기사를 작성하려고했지만 출처가 없어 삭제 제안을했기 때문에 출처를 찾고 있습니다 ..
- 표준 복잡도와 알고리즘 교과서를 확인할 수 있습니다. 그러나 참고 문헌을 찾았더라도 '이 특정 교과서 '의 용어 사용 일뿐입니다. 특정 " 증명 "<없이 공통 정의로 명시 적으로 정의하는 것이 ' 가장 좋습니다. / div>.