1.II.19D

Markov Chains
Part IB, 2005

Every night Lancelot and Guinevere sit down with four guests for a meal at a circular dining table. The six diners are equally spaced around the table and just before each meal two individuals are chosen at random and they exchange places from the previous night while the other four diners stay in the same places they occupied at the last meal; the choices on successive nights are made independently. On the first night Lancelot and Guinevere are seated next to each other.

Find the probability that they are seated diametrically opposite each other on the (n+1)(n+1) th night at the round table, n1n \geqslant 1.