3.I.9C

Markov Chains
Part IB, 2006

A hungry student always chooses one of three places to get his lunch, basing his choice for one day on his gastronomic experience the day before. He sometimes tries a sandwich from Natasha's Patisserie: with probability 1/21 / 2 this is delicious so he returns the next day; if the sandwich is less than delicious, he chooses with equal probability 1/41 / 4 either to eat in Hall or to cook for himself. Food in Hall leaves no strong impression, so he chooses the next day each of the options with equal probability 1/31 / 3. However, since he is a hopeless cook, he never tries his own cooking two days running, always preferring to buy a sandwich the next day. On the first day of term the student has lunch in Hall. What is the probability that 60 days later he is again having lunch in Hall?

[ Note 00=10^{0}=1.]