Automata 9 part 1

Sample space (Ω)

The set of every possible outcome of a random experiment. The symbol Ω (capital Greek "omega") names this set.

Example: tossing 3 coins gives Ω = {HHH, HHT, HTH, HTT, THH, THT, TTH, TTT}.

To find its size, multiply the number of choices at each independent step. Example: 3 people each pick 1 of 3 menu items → 3 × 3 × 3 = 27 outcomes.

Event

Any subset (part) of the sample space Ω — a collection of outcomes you care about.

Example: with one die (Ω = {1,2,3,4,5,6}), the event "even number" is the subset {2, 4, 6}.

When all outcomes are equally likely, the probability of an event = (number of outcomes in it) ÷ (total number of outcomes).

Random variable (X)

A rule that assigns a number to each outcome. Written X : Ω → ℝ, meaning X takes an outcome from Ω and outputs a real number (ℝ = all real numbers).

Example: toss 3 coins, X = number of heads, so X(HHH) = 3 and X(HTH) = 2.

Another: roll a die, win £100 if even and lose £50 if odd, so X(2) = 100 and X(1) = −50.

Pr[X = j]

"X = j" means the event made up of all outcomes where the random variable X equals the value j. Pr[X = j] is the probability of that event: add up the probabilities of those outcomes.

Example: toss 3 fair coins, Y = number of heads. The outcomes with exactly 2 heads are {HHT, HTH, THH}, so Pr[Y = 2] = 3 × (1/8) = 3/8.

Probability by counting outcomes

When every outcome is equally likely: Pr[event] = (favourable outcomes) ÷ (total outcomes).

Example: roll two fair dice (36 equally likely outcomes). Sum = 9 happens for (3,6), (4,5), (5,4), (6,3) = 4 outcomes, so Pr = 4/36 = 1/9.

"Sum is even" has 18 such outcomes, so Pr = 18/36 = 1/2.

Disjoint vs independent events

Disjoint (mutually exclusive): events A and B can never both happen at once (they share no outcomes).

Independent: one happening does not change the chance of the other, tested by Pr[A and B] = Pr[A] × Pr[B].

These are different ideas. Example (two dice): "sum even" and "product is a multiple of 3" can occur together (NOT disjoint), yet Pr[A and B] = Pr[A] × Pr[B] holds (they ARE independent).

Expectation E[X]

The long-run average value of a random variable, weighted by probabilities. Formula: E[X] = Σ over all outcomes s of X(s) × Pr(s), where Σ means "sum". Just multiply each value by its probability and add.

Example: flip 2 fair coins, X = (number of heads)². Outcomes HH, HT, TH, TT give X = 4, 1, 1, 0, each with probability 1/4, so E[X] = (4+1+1+0)/4 = 1.5.

Note: E[X] need not be a value X can actually take.

Linearity of expectation

For ANY random variables X and Y (even if related): E[X + Y] = E[X] + E[Y], and E[cX] = c × E[X] for a constant c.

Extends to any number: E[X₁ + … + Xₖ] = E[X₁] + … + E[Xₖ].

Powerful because you can split a hard total into simple pieces and just add their expectations.

Indicator random variable

A random variable equal to 1 if some event happens and 0 if not. Its expectation equals the probability of the event: E[indicator] = 1 × Pr[happens] + 0 × Pr[doesn't] = Pr[happens].

Trick: to get the expected NUMBER of times something happens, sum one indicator per item and use linearity.

Example (max-exact-4SAT): a clause (OR of 4 literals on distinct variables) is unsatisfied by a random true/false assignment only if all 4 literals are false = (1/2)⁴ = 1/16, so it is satisfied with probability 15/16. Expected satisfied clauses = m × 15/16 = 15m/16.

Expected waiting time (geometric random variable)

Repeat an independent trial that succeeds with probability p until the first success; let X = number of trials needed. Then E[X] = 1/p.

Intuition: if each try succeeds with probability 1/10, you expect about 10 tries.

(Comes from Pr[first success on trial ℓ] = (1 − p)^(ℓ−1) × p.)

Coupon collector problem

Collect n different coupon types, one random (equally likely) coupon per box; X = boxes needed to get every type.

Split into phases: in phase j you already have j types, so a new type appears with probability (n − j)/n, needing on average n/(n − j) boxes.

Adding them (linearity): E[X] = n(1 + 1/2 + … + 1/n) = n × Hₙ, where Hₙ is the n-th harmonic sum. Since ln n ≤ Hₙ ≤ ln n + 1, we get E[X] ≈ n × ln n.

Two fair 6-sided dice are rolled independently. What is the probability that the sum of the numbers is 9?

• 1/12
• 1/6
• 1/9
• 1/18

1/9

Flip 2 fair coins independently. Let X be the square of the number of heads. What is E[X]?

• 1
• 1.5
• 2
• 0.5

1.5

In max-exact-4SAT each clause is an OR of exactly 4 literals on distinct variables, with m clauses. Each variable is set true/false uniformly at random. What is the expected number of satisfied clauses?

• m/16
• m/2
• 15m/16
• 7m/8

15m