11. Randomized Alg Fundamentals

In complexity theory: only access to random bit. Can use the sum of $n$ of them to get $\mathrm{Bin}(n,0.5)$. Can set each digit to random bit to get uniform distribution.

Indirect approach for expected value:

Monte Carlo

Def.: correctness is random, runtime is not.

Can only reduce error if:

• One-sided error (ex. primality test: only YES can have error)
• Error probability < 1/2

For MC algorithm that chooses majority: $N=\lceil 4{\epsilon }^{-2}\ln {\delta }^{-1}\rceil$

Las Vegas

Def.: runtime is random, correctness is not $⟺$ algorithm that’s always correct but sometimes outputs “I don’t know” if takes too long (reverse by repeating until answer). Can be converted into Monte Carlo by returning random value.

Probability that we get “???” $N$ times for a LV algorithm $\le (1-\epsilon {)}^N\le {\mathrm{e}}^{-\epsilon N}\le {\mathrm{e}}^{-\epsilon \cdot \frac{1}{\epsilon }\cdot \ln \frac{1}{\delta }}\le \delta$, which is correct $⟹$ $N=\lceil {\epsilon }^{-1}\ln {\delta }^{-1}\rceil$

Optimization

$\mathrm{Pr}[A(\mathcal{I})\ge f(\mathcal{I})]\ge \epsilon$

If it calls the algorithm $N=\lceil {\epsilon }^{-1}\ln {\delta }^{-1}\rceil$: $\mathrm{Pr}[{\mathcal{A}}_{\delta }\ge f(\mathcal{I})]\ge 1-\delta$