Skip to content

Probability & Randomized Algorithms

Basic rules

  • Conditional probability: \(P(A\mid B) = P(A \cap B) / P(B)\) when \(P(B) > 0\).
  • Expectation linearity: \(E[X+Y] = E[X] + E[Y]\) even if \(X,Y\) are not independent.
  • Independent events: \(P(A \cap B) = P(A) P(B)\).

Randomized algorithms

  • Monte Carlo: may be wrong with small probability; run many trials to drive error down.
  • Las Vegas: always correct; runtime is random (e.g. quicksort pivot).
  • Random hashing: pick hash parameters from a large space to reduce collision probability.

Competitive programming

Often: expected value DP, counting equally likely outcomes, or randomized search / primality (Miller–Rabin).