Lesson 1

In the world of computer science, we often strive for certainty. We want our programs to be “deterministic”—producing the same output for a given input every single time. However, introducing a bit of “chaos” through randomization is actually one of the most powerful strategies in an algorithm designer's toolkit.

Here is why letting an algorithm “flip a coin” is often the smartest move.

• Breaking the “worst-case” trap.  Many classic algorithms have a “weak spot.” For example, the standard QuickSort algorithm is incredibly fast on average, but if it consistently picks a poor “pivot” element, its performance can collapse from \(O(n \log n)\) to \(\Omega(n^{2})\). By using a Randomized QuickSort, the algorithm chooses its pivot point at random. This ensures that no specific input (like a pre-sorted list) can consistently force the algorithm into its slowest state. It shifts the risk away from the data and onto a random variable, making the “worst case” practically impossible to hit.


• Efficiency and simplicity.  Randomized algorithms are often significantly simpler to code than their deterministic counterparts.
  • Simplicity.  Instead of complex balancing logic in a tree, you can use a Treap (a randomized search tree) which stays balanced with high probability just by assigning random priorities to nodes.
  
  
  • Speed.  In primality testing (checking if a number is prime), randomized algorithms like Miller–Rabin provide answers almost instantaneously for massive numbers, whereas deterministic methods are often too slow for practical use in cryptography.

• Solving the “unsolvable”.  In some fields, like high-dimensional physics or complex integration, calculating an exact answer is mathematically exhausting or impossible. Monte Carlo methods use random sampling to approximate these results. By taking enough “random shots” at a problem, you can converge on a highly accurate answer much faster than you could by checking every possible coordinate.
• Symmetry breaking in distributed systems.  In a network where multiple computers (nodes) need to communicate, they often run into “deadlocks” where everyone tries to do the same thing at the same time. If every node follows the exact same deterministic rule, they might stay stuck forever. Randomization allows nodes to “back off” for a random amount of time, breaking the symmetry and allowing the system to resume work. This is the backbone of how Ethernet and Wi-Fi handle data collisions.
• Machine Learning.  It is tempting to imagine that a text language model simply chooses the “best” next word again and again. In many systems, however, the model first assigns scores to many possible next tokens and then turns these scores into a probability distribution. The scores themselves are not probabilities: they can be negative, they do not sum to one, and only their relative values matter. Applying different transformations to those scores, combined with the use of randomness, allows one to introduce varying degrees of “creativity” into the model.