The Probabilistic Method CSP C1,C2,...Cm defined onx1,x2....xn sampling random values ofx1,x2,..., Bad event Ai:constraint Ci is violated None of the ad troPr The probabilistic method:being good is possible >0 Pr i=1The Probabilistic Method • sampling random values of x1, x2, ..., xn • Bad event Ai: constraint Ci is violated • None of the bad events occurs with prob: • The probabilistic method: being good is possible Pr" ^ m i Ai # Pr" ^ m i=1 Ai # > 0 CSP C1, C2, ..., Cm defined on x1, x2, ..., xn