Dependency Graph ·“Bad”events A1,,Am Dependency degree d: each A;is mutually independent of all except d other events Definition (independence): A is independent of B if Pr[A B]Pr[A]or B is impossible. Ao is mutually independent of A1,...,A if Ao is independent of every event B=BA...A B,where each B;=A;or Aj.• “Bad” events A , 1,…, Am Dependency Graph Dependency degree : each is mutually independent of all except other events d Ai ≤ d Definition (independence): is independent of if or is impossible. is mutually independent of if is independent of every event , where each or . A B Pr[A ∣ B] = Pr[A] B A0 A1, …, Am A0 B = B1 ∧ ⋯ ∧ Bm Bi = Ai Ai