RANDOMIZED ALGORITHMS

Leveraging Expectation for Performance

Lesson 01 // Probabilistic Inference

Why Shuffle?

Standard Quicksort has a worst-case complexity of \(O(n^2)\). This happens with sorted or nearly-sorted data.

The Solution: Introduce randomness.

"By choosing a pivot uniformly at random, we decouple the algorithm's performance from the input distribution."

O(n log n)

Expected Runtime

Random Pivots minimize unbalanced splits

The Mathematician's Best Friend

Linearity of Expectation

For any random variables \(X_1, X_2, \dots, X_n\):

\[ E[\sum X_i] = \sum E[X_i] \]

Crucially, this holds even if the variables are **not independent**.

Indicator Random Variables

To analyze Randomized Quicksort, we define indicator variables for every pair of elements \((i, j)\):

\( X_{ij} = I\{z_i \text{ is compared to } z_j\} \)

Total comparisons \( X = \sum_{i=1}^{n-1} \sum_{j=i+1}^n X_{ij} \).

By Linearity: \( E[X] = \sum \sum E[X_{ij}] = \sum \sum P(z_i \text{ is compared to } z_j) \).

The Probability of Comparison

Step 02 // Derivation

Two elements \(z_i\) and \(z_j\) are compared **if and only if** either \(z_i\) or \(z_j\) is chosen as a pivot before any other element in the set \(\{z_i, \dots, z_j\}\) is chosen.

The size of this set is \(j - i + 1\).

\( P(X_{ij} = 1) = \frac{2}{j - i + 1} \)

Summing it up:

\[ E[X] = \sum_{i=1}^{n-1} \sum_{j=i+1}^n \frac{2}{j-i+1} \]

Let \(k = j-i\):

\[ E[X] \approx 2 \sum_{i=1}^{n} \sum_{k=1}^{n-i} \frac{1}{k+1} \]

\[ E[X] = 2n \ln n + O(n) \]

Result: The expected runtime is \(\Theta(n \log n)\).

Key Takeaway

Expectation allows us to characterize "average" performance without making assumptions about the input distribution. We control the randomness, which makes the analysis robust.

Indicator Variables

Breaking complex sums into binary choices.

Linearity

Sums of expectations always work.

Input Robustness

Performance is guaranteed for any data.

Probabilistic Algorithms and Inference

Expectation in Randomized Algorithms

EM Algorithm and Latent Variables

MCMC and Inference Methods

Expectation in Reinforcement Learning

Probabilistic Solver Project

Algorithm Efficiency Slides

Algorithm Efficiency Teacher Guide

Algorithm Analysis Workshop Handout

Hidden Patterns Slides

Hidden Patterns Teacher Guide

Hidden Patterns Student Lab Handout

Random Walk Slides

Random Walk Teacher Guide

The MCMC Cipher Challenge Handout

Slippery Rewards Slides

Slippery Rewards Teacher Guide

Bellman Equation Workshop Handout

Solver Project Slides

Solver Project Teacher Guide

Solver Project Handout

Similar Sequences

The Addicted Brain

Neurobiology of Mental Illness

Flow Force

Teri Minami

Le Pouvoir Solaire

dimitri0681

Metabolic Engines

dimitri0681

Human Origins

Scientific Method Mystery

Human Nature and Conflict

Molecular Survival Strategies

Body Systems Blueprint

Neighbor Planets

Entropy and Energy Flow

Gravity Paradox

Thermal Trackers

Picnic Particles Chemistry

Cosmic Voyage

Green Grid Future

Symbiotic Systems

Ice Age Explorers

Habitat Detectives

Root Cause Investigation

Strategic Hazard Assessment and Risk Control

OSHA Standards and Compliance

Agitation Anatomy

Access Keys: Screen Reader Navigation and Context

Mouseless Mastery Sequence

System Architect Navigation

Keyboard Navigators

Focus Jumpers

Cursor Quest Navigation