A technique that pops up in various areas that allows one to obtain more powerful results.
For instance:
- In game theory, Nash equilibria do not always exist if players are restricted to deterministic strategies. However, if they are allowed to randomize their strategies, then a Nash equilibrium does always exist.
- When designing algorithms, randomization is often used (so called “randomized algorithms”) to improve results. The intuition is that an adversary who is choosing the inputs to your algorithm can be at a disadvantage if you randomize certain choices, and this makes your algorithm fundamentally more powerful.
- In 2023, Manole and Ramdas noted that randomized versions of Markov’s, Chebyshev’s, Chernoff’s, and Ville’s inequalities exist (see randomized inequalities).
- The uniformly most powerful test for simple vs simple discrete distributions requires randomization: Neyman-Pearson lemma for discrete distributions.