Randomness improves algorithms… hear me out…
One of the domains that I am interested in is Approximate Algorithms (you can find a bunch of essays by me on my website), and if there is one thing I have learned from it, it’s that randomness is a tool you can use to build simple, efficient solutions.
Here’s how randomness helps…
Caches sample the data to do approximate eviction, saving exhaustive computation and high memory overhead of running a DLL-based LRU.
Randomness helps you escape local optima and lets you jump out of bad spots. For example, the Traveling Salesman Problem with simulated annealing.
When exact answers are costly, randomness gives near-correct results with high confidence. For example, Morris Counter that saves a good chunk of space but does efficient approximate counting.
Even in eviction, sometimes just evicting a random element gives better results than sophisticated algorithms. For example, one-random and two-random evictions in caches have proven to do better with less overhead.
It is funny that the thing we usually ignore turns out to be a clean way to solve complex problems.
This thought was sparked by a related article I was reading today. Linked in the comments.
Hope this helps.