확률 이론의 고전적인 문제는 사건의 확률을보다 구체적인 사건으로 표현하는 것입니다. 가장 간단한 경우에, 하나는 말할 수 . 이벤트 A ∩ B에 대해 A B 를 작성해 봅시다 .
P[A∪B]=P[A]+P[B]−P[A∩B]AB
A∩B
P[∪Ai]
Ai
사건의 의존 구조는 꼭짓점 있는 가중 된 하이퍼 그래프로 생각할 수 있으며 , 가장자리의 가중치는 가장자리에있는 꼭짓점의 교차와 관련된 이벤트의 확률을 나타냅니다.
Ai포함 제외 스타일 인수는 더 크고 더 큰 이벤트 서브 세트를 함께 고려합니다. 이것은 Bonferroni 경계를 산출합니다 . 이 경계는 최대 크기 까지의 모서리에 대해 모든 가중치를 사용합니다 .
k의존성 구조가 “충분히 훌륭하다”면 Lovász Local Lemma를 사용하여 극단적 인 값 0과 1을 피할 수 있습니다. Bonferroni 접근 방식과 달리 LLL은 의존성 구조에 대한 대략적인 정보를 사용합니다.
이제 의존 구조에서 가중치가 상대적으로 적은 것이 0이 아니라고 가정하십시오. 또한, 페어 독립적 아직 독립적이지 (그리고 더 일반적으로,이 세트 것을 매우 수 많은 이벤트가 있다고 가정 이벤트가 상호 독립적이 아니라입니다 모든에 대한 -wise의 독립적 인 ).
kr
r<k
Bonferroni / Kounias 범위를 효율적으로 계산할 수있는 방식으로 개선하기 위해 이벤트의 종속 구조를 명시 적으로 사용할 수 있습니까?
나는 대답이 그렇다고 기대하며 참조에 대한 포인터를 높이 평가할 것입니다. 나는 1976 년 헌터의 논문을 알고 있지만 페어 와이즈 의존성 만 다룬다. Hunter는 크기 3 이상의 종속성 구조에서 가장자리를 무시하여 형성된 그래프에서 스패닝 트리를 고려합니다.
- 데이비드 헌터, 상부는 연합의 가능성에 대한 바운드 응용 확률의, 저널 (13) 597-603. http://www.jstor.org/stable/3212481
답변
Linial과 Nisan의 "대략적 인 클루 전-배제"논문에서 그 답을 찾을 수있을 것입니다 :
http://www.cs.huji.ac.il/~nati/PAPERS/approx_incl_excl.pdf