Stochastics: Take home test problem, due Thursday at 5pm in LIT 460

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 Z_n denote the position of the Queen of Hearts at time n.  We assume that the Queen of Hearts starts on top, i.e. Z_0 = 1, 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:

\displaystyle P = \begin{pmatrix} \frac15 & \frac15 & \frac15 & \frac 15 & \frac15 \\ \frac45 & \frac15 & 0 & 0 & 0 \\ 0& \frac35 & \frac25 & 0 & 0 \\ 0 & 0 & \frac25 & \frac35 & 0 \\ & 0 & 0 & \frac15 & \frac45 \end{pmatrix}

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.)

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s