Exercises — Randomized algorithms — Las Vegas, Monte Carlo

Recall the mnemonic: Las Vegas = correct always, time varies. Monte Carlo = on time, answer risky.

• (a) Las Vegas. The output is a fully sorted array — never wrong. Only the number of comparisons is random. See QuickSort.
• (b) Monte Carlo (one-sided). Fixed number of rounds; may wrongly call a composite "prime." See Primality Testing.
• (c) Monte Carlo (one-sided). Fixed contraction procedure; may return a cut that is too large. See Min-Cut and Max-Flow.
• (d) Las Vegas. Always returns the true $k$-th smallest; only the running time is random. See Quickselect.

Las Vegas: the random variable is the running time $T$ (correctness is guaranteed). Monte Carlo: the random variable is the correctness of the answer (time is fixed/bounded).

Running time is random ::: Las Vegas Answer is random ::: Monte Carlo

WHY geometric: each attempt is an independent coin flip with success prob $p$, so the number of attempts until the first success is a geometric random variable, and $E[N]=\frac{1}{p}$. $E[N]=\frac{1}{p}=\frac{1}{0.2}=5\text{ attempts.}$ WHAT this means: on average you try 5 times before hitting a success.

WHY the total work is just $c\cdot E[N]$: every attempt costs the same fixed $c$ units, and linearity of expectation (see Probability and Expectation) says $E[\text{work}]=E[c\cdot N]=c\cdot E[N]$ — we can pull the constant cost out of the expectation, so we never need the full distribution of $N$, only its mean. $E[\text{work}]=c\cdot E[N]=\frac{c}{p}=\frac{5}{0.2}=25\text{ units.}$

WHY multiply: independent runs ⇒ the joint "all wrong" probability is the product $q^k$, which shrinks exponentially. (a) $\mathrm{Pr}[\text{error}]\le q^{10}={\left(\frac{1}{4}\right)}^{10}=4^{-10}=\frac{1}{1048576}\approx 9.5\times 10^{-7}.$ (b) Solve $q^k\le \epsilon$. Take the natural log of both sides: $\ln (q^k)=k\ln q\le \ln \epsilon .$ Here is the delicate part: since $0<q<1$, we have $\ln q<0$ (it is negative). Dividing an inequality by a negative number flips the direction of $\le$ into $\ge$. So $k\ge \frac{\ln \epsilon }{\ln q}=\frac{\ln (1/\epsilon )}{\ln (1/q)}=\frac{\ln (10^9)}{\ln 4}=\frac{20.723}{1.386}\approx \mathrm{14.95.}$ (The last equality just rewrites the two negatives $\ln \epsilon /\ln q$ as the positive ratio $\ln (1/\epsilon )/\ln (1/q)$.) Round up (you cannot do a fraction of a run): $k=15$ runs.

WHY Markov: running time $T$ is non-negative, and we only know its mean $E[T]$ — Markov's inequality is exactly the tool that bounds "how often a non-negative variable exceeds a threshold" using only the mean. Markov says $\mathrm{Pr}[T\ge a]\le \frac{E[T]}{a}$. (a) With $a=500$: $\mathrm{Pr}[T\ge 500]\le \frac{100}{500}=0.2=20\%.$ So with a $500$ ms budget the converted Monte Carlo errs at most $20\%$ of the time. (b) We want $\frac{E[T]}{B}\le 0.05$. Solve for $B$: $B\ge \frac{E[T]}{0.05}=\frac{100}{0.05}=2000\text{ ms.}$

$\left(\genfrac{}{}{0ex}{}{n}{2}\right)=\frac{n(n-1)}{2}$. For $n=10$: $\left(\genfrac{}{}{0ex}{}{10}{2}\right)=45$. (a) Single-run success $\ge \frac{1}{45}\approx 0.0222$. (b) Single-run failure $\le 1-\frac{1}{45}=\frac{44}{45}\approx 0.9778$. (c) WHY $1-x\le e^{-x}$: it turns the awkward product $(1-x{)}^T$ into a clean exponential we can read off. With $x=1/\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ and $T=\left(\genfrac{}{}{0ex}{}{n}{2}\right)\ln n$: $\mathrm{Pr}[\text{all }T\text{ miss}]\le {\left(1-\frac{1}{\left(\genfrac{}{}{0ex}{}{n}{2}\right)}\right)}^T\le e^{-T/\left(\genfrac{}{}{0ex}{}{n}{2}\right)}=e^{-\ln n}=\frac{1}{n}.$ For $n=10$: $T=45\cdot \ln 10=45\cdot 2.3026\approx 103.6$, so $T=104$ runs suffice.

WHY the harmonic sum appears: two ranks $i<j$ are compared iff one of them is the first pivot chosen among the $j-i+1$ elements between them — probability $\frac{2}{j-i+1}$. Linearity of expectation (see Probability and Expectation) lets us add these per-pair probabilities, and the sum collapses into harmonic terms. (a) $H_8=1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{5}+\frac{1}{6}+\frac{1}{7}+\frac{1}{8}=\frac{761}{280}\approx \mathrm{2.7179.}$ (b) $2n{H}_8=2\cdot 8\cdot 2.7179\approx \mathrm{43.49.}$ So expected comparisons $\le \approx 43.5$ for $n=8$. (c) Since $H_n\approx \ln n$ grows logarithmically, $2n{H}_n=O(n\log n)$ in expectation on every input. The $O(n^2)$ worst case needs a specific unlucky coin sequence, not a bad input — and the adversary cannot control your coins. Contrast with deterministic pivots in Amortized vs Expected Analysis.

WHY this becomes Las Vegas: each round we produce a candidate and check it. We stop only when the check passes, so the output is always correct — the only random thing is how many rounds we needed. That is precisely the Las Vegas retry loop with success prob $p$. (a) $E[N]=\frac{1}{p}=\frac{1}{0.4}=2.5\text{ rounds.}$ (b) Each round costs $t+v=3+1=4$ ms: $E[\text{time}]=\frac{t+v}{p}=\frac{4}{0.4}=10\text{ ms.}$

(a) The last run is wrong $40\%$ of the time — a single run gives no confidence at all. Because the error is two-sided, you cannot trust any one output; you must aggregate. Majority voting lets independent correct runs outvote the wrong ones (see Chernoff Bounds). WHY the Chernoff/Hoeffding bound and NOT the one-sided $q^k$ trick: the $q^k$ trick works only when there is a certain side (e.g. Miller–Rabin's "composite" is never wrong), so a single unanimous risky answer is trustworthy. Here both answers can be wrong, so unanimity is meaningless — the right question is "how often does the majority of $k$ runs land on the wrong side?" That is a question about a sum of independent 0/1 votes deviating from its mean, and the tool built exactly for bounding such sum-deviations is the Chernoff/Hoeffding concentration inequality — see Chernoff Bounds. (b) Let $\delta =p-\frac{1}{2}=0.6-0.5=0.1$. We need $e^{-2k{\delta }^2}\le 0.01=\epsilon .$ Take logs: $-2k{\delta }^2\le \ln (0.01)$, i.e. $k\ge \frac{\ln (1/\epsilon )}{2{\delta }^2}=\frac{\ln (100)}{2\cdot 0.01}=\frac{4.6052}{0.02}=\mathrm{230.26.}$ Round up to an odd integer (odd avoids ties in the vote): $k=231$. Check: $e^{-2\cdot 231\cdot 0.01}=e^{-4.62}\approx 0.0098\le 0.01$. ✓

(a) Markov on the non-negative time $T$ with $E[T]=50$, threshold $200$: $\mathrm{Pr}[T\ge 200]\le \frac{50}{200}=0.25=25\%.$ When the cutoff triggers we guess, so the cutoff-LV fails at most $25\%$ of the time. (b) Native MC has guaranteed error $q=0.1=10\%$, which is smaller than the cutoff-LV's $25\%$ bound. So within the $200$ ms budget the native Monte Carlo is the safer choice — $10\%<25\%$.

Cutoff-LV worst-case error ::: at most $25\%$ (Markov bound) Native-MC error ::: $\le 10\%$ Better option under 200 ms ::: native Monte Carlo