FREE Algorithms LESSON · Algorithms
Choose under uncertainty
Randomization, approximation, and online decisions
Sometimes the honest algorithm returns a bounded compromise.
Exact optimization can be computationally infeasible, future inputs may be unavailable, or adversaries may exploit deterministic behavior. Randomized algorithms state a probability model; approximation algorithms state a quality bound; online algorithms compare decisions made without the future against an ideal offline solution. Each replaces an impossible promise with a precise, decision-relevant guarantee.
A weaker guarantee is intellectually strong when its boundary is explicit and useful.
Randomness does not excuse unreproducible evidence.
A randomized system still needs controlled seeds for debugging, repeated trials for estimates, and analysis of tail outcomes rather than only the mean. If an adversary can observe or influence the random choices, assumptions about independence may fail. Production use also needs a decision about which rare failures are tolerable.
Report a distribution and a bound, not one fortunate run.