Randomized Algorithms

• If algorithm has better Average-Case Run-Time than worst-case time, then we randomize it.
• Randomized Algorithms is one which relies on some random input in addion to the input.
• Goal: shift dependency of run-time from what we can’t control (input) to what we can control (random numbers).

Example:

• random(2) = 1 → swap $A[n-2]$ and $A[n-1]$
• random(2) = 0 → don’t
• Observe: $Pr(goodcase)=\frac{1}{2}=Pr(badcase)$

• random choices $R=<x,x^{{}^{\prime }}{x}^{{}^{\prime \prime }}{x}^{{}^{\prime \prime \prime }},...>=<x,R>$
• $Pr(R)=Pr(x=good)\times Pr(R^{{}^{\prime }})+Pr(x=bad)\times Pr(R^{{}^{\prime }})$