Game Theory
Game Theory is one field in which randomized algorithms are quite important. One particular use of randomized algorithms in game theory is game tree evaluation. A game tree is a tree data structure in which each generation of nodes switches between the labels MAX and MIN. The MIN type node returns the smallest value of its children nodes. The MAX type returns the largest. Each of the leaves of the tree has a certain value, and so by evaluating the game tree, one can determine the return value of the root. In the case below, the root would return 1.
A randomized algorithm is more efficient at evaluating a game tree than a deterministic algorithm. A deterministic algorithm evaluates the children nodes in a set fashion, say left to right. By doing so, this approach could often be inefficient if it had to check both nodes. For example, if the algorithm is evaluating the children of a MIN node, it is looking for a 0. If it reads the children nodes from left to right and the left child is a 1, then it will also have to check the right node. Thus, in a worst case adversarial situation, the adversary could deliberately put the 0 on the right every time, thereby significantly slowing down the algorithm. Randomized algorithms avoid this pitfall by choosing the child node randomly. Doings so, the average number of steps for a tree of the above size (3 generations), regardless of an adversary, would be 3/2. This is much better than the worst case scenario performance of the deterministic algorithm, which would require 2 steps. While this difference may not seem like much, one must keep in mind that the above game tree is extremely simplified. As the complexity increases, the deterministic algorithm's average number of steps will increase much faster than that of the randomized version.
If you'd like to learn more about game theory, check out the work that our sophomore college classmates have done on their game theory web page.