Tuesday, March 30, 2010

Markov chains and mixing

[@ 3:30pm. 30 March, 2010. SIC-305 KReSIT]
Ayush

Toy problem: A website has n questions. If you're shown one random question per click, prove that it takes O(n log n) clicks on avg to see all the questions.