Automata 8 part 1

RA: Randomised algorithm

An algorithm that uses a source of random numbers and makes random choices while it runs.

Key consequence: its output and/or running time can be DIFFERENT on the same fixed input, run to run.

(A deterministic algorithm always does exactly the same thing for a given input.)

Trade-off: often much faster/simpler than a deterministic algorithm, but may give a wrong answer with some small probability.

RA: One-sided error

An error pattern where the algorithm is ALWAYS correct on one type of input, and only ever makes mistakes on the other type.

Example (bit-array test): if the array is all 0s it answers correctly every time (error = 0); if it isn't, it errs with probability at most 1/100.

Because errors only happen on one side, repeating the algorithm independently several times drives the error probability down.

RA: Sample space Ω

The set of ALL possible outcomes of a random experiment. Written Ω (capital "omega").

Examples: one coin toss → Ω = {H, T}; one die roll → Ω = {1, 2, 3, 4, 5, 6}.

RA: Event (E ⊆ Ω)

An event is any subset of the sample space. "E ⊆ Ω" reads "E is contained in Ω" — i.e. E is a group of outcomes you care about.

Examples (one die): "shows a multiple of 3" = {3, 6}; "shows an even number" = {2, 4, 6}; "coin shows heads" = {H}.

RA: Probability of an event Pr[E]

Every outcome i gets a probability mass Pr(i) ≥ 0, and all masses add up to 1: ∑ over all i of Pr(i) = 1.

The probability of an event is the sum of the masses of the outcomes inside it: Pr[E] = ∑ over i in E of Pr(i).

Example (fair die, E = even = {2,4,6}): Pr[E] = 1/6 + 1/6 + 1/6 = 1/2.

Also: Pr[∅] = 0 (the empty set ∅ = "nothing happens").

RA: Uniform distribution

Every outcome is equally likely. Each outcome i then has probability Pr(i) = 1 /

RA: Sample space of repeated / independent choices

Doing an experiment k independent times multiplies the outcomes. If each step has m equally-likely options, you get m^k equally-likely outcomes.

Two dice:

RA: Union, intersection, complement

For events on the same Ω:

Union E1 ∪ E2 = outcomes in E1 OR E2 (or both). Intersection E1 ∩ E2 = outcomes in BOTH (AND). Complement Ē (also ¬E or Ω \ E) = all outcomes NOT in E.

Example (die): odd {1,3,5} ∪ mult-of-3 {3,6} = {1,3,5,6}; ∩ = {3}; complement of {1,3,5} = {2,4,6}.

Useful fact: Pr[Ē] = 1 − Pr[E].

RA: Union bound

For ANY events E1, …, En: Pr[E1 ∪ … ∪ En] ≤ Pr[E1] + … + Pr[En].

In words: the chance that at least one of them happens is at most the sum of their individual chances.

Special case — if the events are disjoint (no overlap, Ei ∩ Ej = ∅ for every i ≠ j) it becomes an exact equality: Pr[E1 ∪ … ∪ En] = Pr[E1] + … + Pr[En].

RA: Conditional probability Pr[A

B]

RA: Independent events

Events E and F are independent if Pr[E ∩ F] = Pr[E] · Pr[F].

Equivalently, knowing F tells you nothing about E: Pr[E

RA Q1: Three people each independently order one of three menu items. What is the size of the sample space?

• 9
• 27
• 6
• 81

27 (each person has 3 choices, so 3 × 3 × 3 = 3^3 = 27)

RA Q2: Throw two fair dice independently. What is the probability the sum of the two numbers is 9?

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

1/9 (sums of 9: (3,6),(4,5),(5,4),(6,3) = 4 outcomes out of 36, so 4/36 = 1/9)

RA Q3: Throw two fair dice independently. What is the probability the product of the two numbers is a multiple of 3?

• 1/3
• 4/9
• 1/2
• 5/9

5/9 (product is a multiple of 3 unless NEITHER die shows 3 or 6: that "fail" chance is (4/6)^2 = 4/9, so answer = 1 − 4/9 = 5/9)