Source: Placement Test of a Quant Company at IITB in 2010
Problem: Consider a random walk around the edges of a square. From any vertex, the probability of moving to any adjacent vertex is 0.5. Suppose the walk stops as soon as after all traversing through all the vertices, you return to your starting vertex. What is the expected path length?
Update (Nov 10, 2010):
1) First solution posted by Naval Chopra (Final year student, CSE, IIT Bombay) in comments!
2) A more elegant solution posted by Ankush Agarwal (Third Year undergraduate student, CSE, IIT Bombay) in comments! He has also posted a mathematica code for verifying his solution :)
3) A similar solution posted by Yash in comments (with a minor typo though)
Thanks a lot for the active participation!