Yao's techniqe

Seems to be a powerful tool for bound the performance of random algorithm. Here is an introduction:
http://www.cs.pitt.edu/~kirk/cs2150/yao/yao.html