Each morning a student takes one of the three books he owns from his shelf. The probability that he chooses book $i$ is $a_i$, where $0 < a_i < 1$ for $i=1,2,3$ and the choices on successive days are independent.
In the evening he replaces the book at the left-hand end of the shelf. If $P_n$ denotes the probability that on day $n$ the student finds the books in the order $1,2,3$, from left to right, show that, irrespective of the initial arrangement of the books, $P_n$ converges as $n\to\infty$ and find the limit.
Best Answer
There are 6 different orders. For each pair of orders, you can work out the probability of transition from one to the other. For example, if today they are in order 123, then tomorrow they will be in order 123 or 213 or 312 with probability $a_1,a_2,a_3$, respectively. So this is a Markov chain with 6 states, and you can write down the $6\times6$ transition matrix.
Now, what do you know about Markov chains? What do you know about conditions on the transition matrix that guarantee the existence of a state to which the chain converges regardless of the initial conditions? And can you prove that the matrix we got in the 1st paragraph satisfies the conditions?