태그 보관물: big-list

big-list

더 깊은 구조를 드러내는 증거 표준 증거 ( Randomized Algorithms 교재)는 Markov

Chernoff 경계에 대한 표준 증거 ( Randomized Algorithms 교재)는 Markov 부등식과 모멘트 생성 기능을 사용합니다. 약간의 Taylor 확장이 적용되었습니다. 너무 어렵지는 않지만 다소 기계적입니다.

그러나 결과를 이끌어내는 더 깊은 구조를 노출시키는 다른 Chernoff 바운드 증거가 있습니다. 예를 들어, 종이의 종류로 예시의 방법을 통해 이동 정보 이론적 버전있다 Impagliazzo 및 Kabanets 뿐만 아니라 산조이 다스 굽타 의해이 짧은 포스트 . 이 후자의 증명은 표준 결과의 일반화를 제공한다는 점에서 “직관적”이며 지수의 재미있는 용어가 나오는 곳을 설명합니다 (KL- 분산).

그러한 것들의 좋은 예는 무엇입니까? 보다 구체적으로, 다음 규칙이 있습니다.

  1. 성명서는 합리적으로 잘 알려져 있어야합니다 (어떤 종류의 대학원 수업에서 강의 할 내용).
  2. 교과서 또는 “일반적으로”가르치는 표준 참고 자료에 “표준”증거가 있어야합니다.
  3. 잘 알려지지 않았고, 일반적으로 가르치지 않으며,보다 일반적인 진술을 입증하거나 그 진술을 더 깊은 수학적 구조와 연결시키는 대체 증거가 있어야합니다.

두 가지 예부터 시작하겠습니다.

  1. chernoff 경계

    • “교과서”증명 : 마르코프 불평등, 모멘트 생성 기능, 테일러 확장 (MR)
    • 흔하지 않고 통찰력있는 증거 : KL- 분산과 관련된 유형의 방법, 꼬리 지수
  2. 슈바르츠-지펠 펠레 마

    • “교과서”증명 : 단 변량 다항식이 포함 된 기본 사례. 변수 수에 대한 유도
    • “흔하지 않은”증거 : Dana Moshkovitz (및 Vognsen ) 를 통한 기하학적 인수

답변 당 하나의 예를 참조하십시오.

ps 나는 반드시 흔한 증거 가르쳐야 한다는 것을 암시하는 것은 아닙니다 . 직접적인 증거는 종종 학생들에게 더 쉽습니다. 그러나 “증거가 이해하는 데 도움이된다”는 점에서 이러한 대체 증명은 매우 유용합니다.



답변

나는 교과서에서 “흔하지 않은”증거를 보았 기 때문에 이것이 당신이 찾고있는 것이 확실하지 않지만 퀵 정렬을위한 O (n log n) 시간입니다.

  • “교과서”증명 : 무작위 재발 관계를 설정하고 원하는 솔루션이 있음을 유도하여 증명합니다.

  • “흔하지 않은”증거 : 두 요소가 비교 될 확률에 대한 간단한 공식을 찾으십시오 (d는 정렬 된 순서의 순위 간의 차이 인 2 / (d + 1)에 불과 함). 비교할 예상 쌍 수를 계산합니다.

교과서 증명은 창의적 통찰력이 덜 필요하지만, 드문 증거는 다른 알고리즘 분석에 매우 유용한 기법을 소개합니다 (예 : 계산 기하학의 무작위 증분 알고리즘).


답변

BPP가 에 있다는 증거인 복잡성에서 하나를 버리겠습니다 . 교과서 증거 Lautemann 때문에, 단지 적어입니다 표현을하고 간단한 확률 인수와 함께 작동을 보여줍니다. 드문 증명 : 하드 기능 (추측 맞춰, 확인 경도)와 니산-Wigderson 발생기 끼우.

Σ2


답변

나는에이나는엑스나는

±1

엑스나는

σ=에이2

2

이자형[(나는에이나는엑스나는)]=나는1,,나는(j=1에이나는j)이자형[j=1엑스나는j]나는1,,나는(j=1|에이나는j|)이자형[j=1엑스나는j]=나는1<<나는아르 자형1,,아르 자형j아르 자형j=j 아르 자형j>0(아르 자형1,,아르 자형)(j=1|에이나는j|아르 자형j)(j=1이자형[엑스나는j아르 자형j])

아르 자형j

0

1

엑스나는

나는

아르 자형j

0

아르 자형j

1

이자형[(나는에이나는엑스나는)]이자형[(나는|에이나는|나는)]

2

나는|에이나는|나는

에이2

에이2!/(2/2(/2)!)

에이2/2

아르 자형[|나는에이나는엑스나는|>λ]<2영형()λ에이2/2

=λ2/(기음에이22)

기음

이자형엑스(Ω(λ2/에이22))

엑스나는


답변

에이

아르 자형나는

나는

에이

나는(아르 자형나는!)1/아르 자형나는.


답변