We shuffle a deck by the following method:
Take the top card off the top of the deck and place back into the deck in a position chosen uniformly at random.
It is allowable that the top card will be put directly on top again.
Let denote the position of the Queen of Hearts at time . We assume that the Queen of Hearts starts on top, i.e. , and wish to compute the expected time for it to return to the top.
The probability transition matrix when there are a total of FIVE cards is:
What is the expected time until the shuffler sees the Queen of Hearts on top of the deck when there are 52 cards?
You may use the book, but you may not communicate with other students on this problem. Work smart! The solution does not require solving a 52-dimensional system of equations. (Hint: It may help to solve the 5-card case first and then attack the larger problem.)