Consider Example 4.2-1 for k books. Show that in the long run, all k! permutations are asymptotically equally likely.

Example 4.2-1

Consider the process of random rearrangements with P given in (1.2.3). It is straightforward to verify that for such a matrix, equation (4.2.2) is true for π=(1/6, ..., 1/6), meaning that, as t →∞, all arrangements are asymptotically becoming equally likely.

In Exercise 24, it is suggested to show that the same is true for any number of objects being shuffled. Let us call a way of shuffling perfect if it leads to equal probabilities of all possible permutations regardless of the initial arrangements of the objects. We see that a simple shuffling as in our example is close to a perfect one for a large number of iterations.