The method of bounded differences Independent random variables:X-(X1,X2,...,X). 1,x2..,)satisfies the Lipschitz condition: |jx1,,n)-fx1,,xi1,yi,Xi+1,,xn)|≤Ci for arbitrary possible valuesx1,...,xn,yi. t>0: x>grxyfse( 2t2 Pr[f(X)≤E[f(X)】-t)≤expIndependent random variables: X=(X1, X2,..., Xn). The method of bounded differences f(x1, x2,..., xn) satisfies the Lipschitz condition: | f(x1, ..., xn) - f(x1,..., xi-1, yi, xi+1, ..., xn) | ≤ ci for arbitrary possible values x1, ..., xn, yi. t > 0 : Pr[f(X) E[f(X)] t] exp ✓ 2t 2 Pn i=1 c2 i ◆ Pr[f(X) E[f(X)] + t] exp ✓ 2t 2 Pn i=1 c2 i ◆