Randomized algorithms — Las Vegas, Monte Carlo: Foundations

This page assumes nothing. If you have never seen $E [\cdot]$ , $\sum$ , $Pr [\cdot]$ , or $(2 n)$ , start here. Every symbol used on the parent note is unpacked below, in an order where each idea stands on the previous one.

0. What is a "random variable"? (the seed of everything)

Before symbols, a picture. Imagine rolling a die. The number that lands up is not fixed — it depends on chance. A quantity like this is called a random variable: a number whose value is decided by an act of chance.

Figure — Randomized algorithms — Las Vegas, Monte Carlo

Figure s01 — A fair die's outcome $X$ has six possible values, each a bar of height $\frac{1}{6}$ . There is no single "the value" of $X$ ; instead there is a whole spread, and the orange arrow highlights that this spread — not one number — is what a random variable really is.

Las Vegas: the running time $T$ is a random variable; the answer is fixed-correct.
Monte Carlo: the answer is the random variable; the time is fixed.

1. Events and probability $Pr [\cdot]$ — "how often does this happen?"

Before we can measure chance, we need to name the thing whose chance we measure.

Picture it as a slice of a full pie. The whole pie is "everything that could happen" and has area $1$ . Your event is a wedge; its area is the probability.

The multiply rule is exactly why the parent's confidence-boosting works: $k$ independent wrong runs each of chance $q$ give a joint chance $q \cdot q \dots q = q^{k}$ .

Deeper foundations for these rules live in Probability and Expectation.

2. Independence — "one flip tells you nothing about the next"

Figure s02 — Two coin flips drawn as separate coins with a dotted "no influence" arrow between them. Because flip 2 cannot feel flip 1, their joint chance is the product of the single-flip chances — the picture behind $Pr [A \land B] = Pr [A] Pr [B]$ .

3. The $\sum$ (summation) symbol — "add up a whole list"

We will need to add up many chances, so let us earn the symbol before using it.

Picture a row of boxes, one per term, and $\sum$ as a rake sweeping them all into one pile.

4. Expectation $E [X]$ — "the long-run average value"

Now the single most important symbol on the parent page — and note it is built on $\sum$ , which we just introduced.

Picture the possible values as weights placed on a ruler, each weight sized by its probability. $E [X]$ is the balance point where the ruler tips level.

Figure s03 — Each possible value of $X$ is a bar whose position is the value and whose height is its probability. The orange fulcrum sits at $E [X]$ — the exact point where the loaded ruler balances. This is why we call the expectation the "centre of gravity" of the distribution.

Compare $E [X]$ against worst-case thinking in Amortized vs Expected Analysis.

5. Indicator variable $X_{ij}$ — "a yes/no turned into a 1/0"

6. The geometric distribution & $\frac{1}{p}$ — "how many tries until it works?"

Figure s04 — The bars show $Pr [N = k]$ : the chance the first success arrives on try $k$ . They shrink geometrically because each earlier try had to fail first. The orange dashed line marks the balance point $E [N] = \frac{1}{p}$ — the average number of tries.

7. The exponential $e^{x}$ and the bound $1 - x \leq e^{- x}$

8. Logarithm $ln$ , $lo g$ — "the undo button for exponentials"

Picture $ln$ as a shrinking ruler: multiplying the input only adds a little to the output. That slow growth is why $lo g n$ is small even for huge $n$ .

9. Binomial coefficient $(2 n)$ — "how many pairs?"

10. Markov's inequality — "big overshoots are rare"

Prerequisite map

Equipment checklist

Read each question, answer in your head, then reveal.

What is an "event" and how do we write "A and B"?

An event is a yes/no statement about a random outcome; "A and B" is written

A \land B

, the overlap of both.

What does

Pr [A] = 0.3

mean in plain words?

The event

A

is true about

30%

of the time if you repeat the experiment forever.

When may you multiply two probabilities together?

Only when the two events are independent (one doesn't affect the other):

Pr [A \land B] = Pr [A] Pr [B]

State the union bound and when it's useful.

Pr [A_{1} \lor \dots \lor A_{m}] \leq \sum Pr [A_{i}]

; it bounds the chance that at least one of many bad events happens, without needing independence.

What is

E [X]

intuitively, and which symbol is it built from?

The long-run average / balance point of

X

; built from the summation

\sum

State linearity of expectation and why dependence doesn't matter.

E [X_{1} + \dots + X_{m}] = E [X_{1}] + \dots + E [X_{m}]

; it just regroups the same summed numbers, so it never asks how the variables interact.

An indicator

X

1

on event

A

, else

0

. What is

E [X]

E [X] = Pr [A]

You retry until success, each try succeeds with prob

p

. Expected tries, and the one-line reason?

\frac{1}{p}

; a failure resets you to the start (memoryless), giving

E = 1 + (1 - p) E

Why is

1 - x \leq e^{- x}

true?

1 - x

is the tangent line of the convex curve

e^{- x}

x = 0

, and a convex curve stays above its tangents.

What does

ln

undo, and where does the topic use it?

It undoes

e^{x}

(exponents); used to solve

q^{k} \leq ε

for

k

and to get

H_{n} \approx ln n

What is

(2 n)

and where does it appear?

The number of unordered pairs

\frac{n ( n - 1 )}{2}

; the reciprocal of Karger's single-run success probability.

State Markov's inequality in words.

A non-negative variable exceeds

a

times its average with probability at most

\frac{1}{a}

See it all assembled on the parent: 3.7.19 Randomized algorithms — Las Vegas, Monte Carlo (Hinglish). Applications live in QuickSort, Quickselect, Primality Testing, and Min-Cut and Max-Flow.