19.23 Derandomization

Randomized algorithms are often easier to design and analyze than deterministic algorithms. A random pivot simplifies quicksort. Randomized rounding simplifies approximation algorithms. Random sampling simplifies large-scale data analysis.

A natural question follows:

If randomness helps so much, can we remove it?

Surprisingly, the answer is often yes.

Derandomization is the process of transforming a randomized algorithm into a deterministic one while preserving most or all of its guarantees. In many cases, the randomized algorithm serves as a blueprint. Once its probabilistic behavior is understood, the random choices can be replaced by carefully selected deterministic decisions.

This section introduces the main ideas behind derandomization and explains why randomized algorithms are often only the first step toward deterministic solutions.

Problem

Suppose a randomized algorithm produces a solution with expected value:

E[Solution Quality]
=
100

Each execution makes random choices.

Example:

if random.random() < 0.5:
    choose_left()
else:
    choose_right()

The algorithm works well on average.

However, some environments require:

• Reproducibility
• Deterministic execution
• Auditable decisions
• Regulatory compliance
• Predictable outputs

Can we obtain similar performance without randomness?

Existence Through Expectation

Many derandomization techniques begin with a simple observation.

Suppose:

E[X] = 100

Then at least one outcome must satisfy:

X ≥ 100

Otherwise every outcome would be smaller than 100, contradicting the expectation.

This means:

If a randomized algorithm
has good expected performance,

a good deterministic choice
must exist somewhere.

The challenge is finding it efficiently.

Example

Suppose an algorithm flips a coin.

Heads:

Score = 120

Tails:

Score = 80

Expected score:

(120 + 80) / 2
=
100

Because the expectation is 100:

At least one outcome
has score ≥ 100.

Specifically:

120

The existence is guaranteed.

Finding the good outcome is the goal of derandomization.

Method of Conditional Expectations

The most important derandomization technique is the method of conditional expectations.

Basic idea:

Replace random decisions
one at a time.

At each step:

1. Compute the expected value assuming a choice.
2. Compute the expected value assuming the alternative.
3. Select the better option.
4. Continue.

The final deterministic solution achieves at least the original expected value.

Simple Example

Suppose a randomized algorithm chooses:

x₁
x₂
x₃

each as:

0 or 1

with equal probability.

Expected objective:

10

Start with:

x₁

Compute:

Expected value if x₁ = 0
Expected value if x₁ = 1

Choose whichever expectation is larger.

Then repeat for:

x₂

and:

x₃

Eventually every variable becomes fixed.

The resulting deterministic solution achieves value at least:

10

Why It Works

Suppose:

E[X]
=
10

At the first decision:

E[X]
=
0.5 E[X | choice A]
+
0.5 E[X | choice B]

At least one conditional expectation must be:

≥ 10

Choose it.

The expectation never decreases.

Repeating this argument preserves the guarantee until all randomness disappears.

Randomized Rounding Revisited

Recall randomized rounding.

Fractional variable:

x = 0.7

Randomized choice:

1 with probability 0.7
0 with probability 0.3

Expected objective remains unchanged.

The method of conditional expectations replaces this random choice.

Instead:

Evaluate objective expectation
if x = 0

Evaluate objective expectation
if x = 1

Choose the better value.

Repeat for every variable.

The resulting solution becomes deterministic.

Example: Max-Cut

Given a graph:

G = (V, E)

place vertices into two groups.

Objective:

Maximize edges
crossing between groups.

Randomized algorithm:

Assign each vertex
left or right
with probability 1/2.

Each edge crosses with probability:

1/2

Expected cut size:

m / 2

where:

m

is the number of edges.

The conditional expectation method converts this into a deterministic:

1/2-approximation

without randomization.

Pessimistic Estimators

Sometimes conditional expectations are difficult to compute directly.

Instead use a pessimistic estimator.

A pessimistic estimator:

Upper bounds failure probability

or:

Lower bounds success quality.

The algorithm maintains this estimate while fixing variables.

If the estimate remains acceptable:

Final solution remains acceptable.

This technique is widely used in derandomizing Chernoff-bound arguments.

Small Sample Spaces

Another strategy reduces randomness instead of eliminating it entirely.

Suppose a randomized algorithm uses:

1000 random bits

Possible outcomes:

2^1000

enormous.

Often only a tiny subset of those random choices is actually needed.

Construct:

Small carefully designed sample space

and search it exhaustively.

The result becomes deterministic.

Pairwise Independence

Many analyses require less randomness than expected.

Example:

Hashing

may only require:

Pairwise independence.

Instead of choosing from all possible hash functions:

Choose from a small family.

This significantly reduces randomness requirements.

Many practical hashing schemes rely on this principle.

Limited Independence

Independence comes in levels.

Type	Description
Full independence	Every subset independent
k-wise independence	Any k variables independent
Pairwise independence	Any two independent

Many randomized algorithms work with:

Pairwise

or:

k-wise

independence.

This often enables efficient derandomization.

Expander Graphs

Expander graphs provide another powerful derandomization tool.

Expanders are sparse graphs with strong connectivity properties.

A random walk on an expander behaves similarly to truly random sampling.

Advantages:

• Fewer random bits
• Similar probabilistic guarantees
• Efficient construction

Expanders appear throughout theoretical computer science.

Pseudorandom Generators

A pseudorandom generator expands a short random seed into a long sequence that appears random to a particular class of algorithms.

Example:

20 random bits

generate:

1000 pseudorandom bits

If an algorithm cannot distinguish the sequence from true randomness:

The generator effectively
replaces randomness.

This is a central idea in modern complexity theory.

Example: Derandomizing Max-Cut

Randomized algorithm:

Assign vertices randomly.

Expected cut:

m / 2

Derandomized version:

1. Process vertices one at a time.
2. Compute expected cut size if vertex goes left.
3. Compute expected cut size if vertex goes right.
4. Choose better side.

Final cut:

≥ m / 2

No randomness remains.

The guarantee is unchanged.

Randomness vs Computation

Derandomization often exchanges:

Random bits

for:

Extra computation.

Example:

Version	Randomness	Computation
Randomized	High	Low
Derandomized	Low	Higher

The trade-off depends on application requirements.

Practical Examples

Derandomization appears in:

Scheduling

Replace randomized assignments with deterministic choices preserving load guarantees.

Network Design

Convert randomized constructions into deterministic network layouts.

Approximation Algorithms

Transform expected-value guarantees into deterministic guarantees.

Distributed Systems

Reduce dependence on random decisions.

Testing

Create deterministic test suites covering probabilistic behaviors.

Why Randomized Algorithms Still Matter

A common misconception:

If derandomization exists,
randomized algorithms are unnecessary.

The opposite is often true.

Randomized algorithms frequently:

• Reveal important structure.
• Simplify proofs.
• Suggest deterministic strategies.
• Provide easier analyses.

Many deterministic algorithms were discovered by first studying randomized versions.

Complexity-Theoretic Questions

One of the deepest questions in theoretical computer science asks:

Does randomness
fundamentally increase
computational power?

In complexity theory this appears as:

P
vs
BPP

where:

BPP

represents efficient probabilistic computation.

Many researchers believe:

P = BPP

meaning randomness can ultimately be removed without significant loss.

The question remains open.

Common Mistakes

Assuming Expectation Guarantees a Particular Outcome

Expectation guarantees existence, not discovery.

A derandomization method is still required.

Ignoring Computational Cost

Derandomization may increase runtime substantially.

Using Full Independence Unnecessarily

Limited independence often suffices.

Confusing Pseudorandomness with Randomness

Pseudorandom sequences only appear random to specific algorithms.

The distinction matters.

Discussion

Derandomization transforms probabilistic existence proofs into constructive deterministic algorithms. The central insight is that good expected performance implies the existence of good deterministic choices. Techniques such as conditional expectations, pessimistic estimators, limited independence, expander graphs, and pseudorandom generators provide systematic ways to discover those choices.

The broader lesson is that randomness is often a design tool rather than a requirement. Randomized algorithms reveal structure, simplify analysis, and guide algorithm development. Once that structure is understood, randomness can frequently be reduced or eliminated entirely. This interplay between randomness and determinism remains one of the most important themes in modern algorithm design.