CLRS Solutions | Exercise 5.1-3 | Probabilistic Analysis and Randomized Algorithms

Suppose that you want to output 0 with probability $1/2$ and 1 with probability $1/2$. At your disposal is a procedure $\textsc{Biased-Random}$, that outputs either 0 or 1. It outputs 1 with some probability $p$ and 0 with probability $1 - p$, where $0 < p < 1$, but you do not know what $p$ is. Give an algorithm that uses $\textsc{Biased-Random}$ as a subroutine, and returns an unbiased answer, returning 0 with probability $1/2$ and 1 with probability $1/2$. What is the expected running time of your algorithm as a function of $p$?

The key insight is to call $\textsc{Biased-Random}$ twice and observe the pattern of results.

The Clever Trick

If we call $\textsc{Biased-Random}$ twice:

\[\begin {align*} P(00) &= (1-p) \cdot (1-p) = (1-p)^2 \\ P(01) &= (1-p) \cdot p = p(1-p) \\ P(10) &= p \cdot (1-p) = p(1-p) \\ P(11) &= p \cdot p = p^2 \end {align*}\]

Note that probabilities of $P(01)$ and $P(10)$ are equal, regardless of the value of $p$. This gives us our unbiased source:

If we get $(0,1)$, return 0
If we get $(1,0)$, return 1
If we get $(0,0)$ or $(1,1)$, discard and try again

$$\textsc {Unbiased-Random }()$$$$\begin{aligned}1& \quad \textbf {while }true \\2& \quad \qquad x=\textsc {Biased-Random}() \\3& \quad \qquad y=\textsc {Biased-Random}() \\4& \quad \qquad \textbf {if }x=0\text { and }y=1 \\5& \quad \qquad \qquad \textbf {return }0 \\6& \quad \qquad \textbf {if }x=1\text { and }y=0 \\7& \quad \qquad \qquad \textbf {return }1 \\\end{aligned}$$

Analysis of Expected Running Time

Each iteration makes 2 calls to $\textsc{Biased-Random}$ and takes $\Theta(1)$ time.

The probability of accepting a pair (returning a value) is:

\[P(\text{accept}) = P(01) + P(10) = 2p(1-p)\]

The expected number of iterations is:

\[E[\text{iterations}] = \frac{1}{P(\text{accept})} = \frac{1}{2p(1-p)}\]

Each iteration makes 2 calls to $\textsc{Biased-Random}$, so the expected number of calls is:

\[E[\text{calls}] = \frac{2}{2p(1-p)} = \frac{1}{p(1-p)}\]

Therefore, the expected running time is $\Theta(1/[p(1-p)])$.

Understanding the Running Time

The function $p(1-p)$ is maximized when $p = 1/2$ (giving $p(1-p) = 1/4$), and approaches 0 as $p$ approaches 0 or 1.

Best case: When $p = 1/2$, $E[\text{calls}] = 4$
Worst case: When $p$ is very close to 0 or 1, we need many iterations

For example:

If $p = 0.9$, then $E[\text{calls}] = 1/(0.9 \cdot 0.1) = 11.11$
If $p = 0.99$, then $E[\text{calls}] = 1/(0.99 \cdot 0.01) = 101.01$

Python Implementation

import random def BiasedRandom(p): """ Simulates BIASED-RANDOM with probability p of returning 1 Args: p: probability of returning 1 (between 0 and 1) Returns: 1 with probability p, 0 with probability (1-p) """ return 1 if random.random() < p else 0 def UnbiasedRandom(p): """ Generates an unbiased random bit using a biased source Args: p: bias of the source (probability of 1) Returns: 0 or 1, each with probability 1/2 """ while True: x = BiasedRandom(p) y = BiasedRandom(p) if x == 0 and y == 1: return 0 if x == 1 and y == 0: return 1 # If (0,0) or (1,1), discard and try again # Test with different bias values print("Testing Unbiased-Random with various bias values:\n") for p in [0.1, 0.3, 0.5, 0.7, 0.9]: print(f"Bias p = {p}") # Count number of calls to BiasedRandom call_count = 0 original_biased = BiasedRandom def counted_biased(bias): global call_count call_count += 1 return original_biased(bias) # Generate samples and count calls BiasedRandom = counted_biased samples = 1000 zeros = 0 ones = 0 for _ in range(samples): result = UnbiasedRandom(p) if result == 0: zeros += 1 else: ones += 1 BiasedRandom = original_biased avg_calls = call_count / samples theoretical = 1 / (p * (1 - p)) print(f" Results: 0's = {zeros}, 1's = {ones}") print(f" Average calls per output: {avg_calls:.2f}") print(f" Theoretical expectation: {theoretical:.2f}") print() print("As expected, when p = 0.5, we need the fewest calls (~4).") print("When p is extreme (close to 0 or 1), we need many more calls.")