2
$\begingroup$

I have been reading the randomized algorithm book by Rajeev Motwani and Prabhakar Raghavan. In section 3.5 they have introduced principle of deferred decision which is a different probability space. The example they provided is a clock solitaire game. The game is as follows. Initially 52 cards are randomly grouped into 4 cards of 13 piles. The piles are labeled $1,2,3,...,10,Q,J,K,A$. The game starts by drawing a card from $K$ labeled pile. The next draw will be taken place from the pile with the face value of the drawn card. For an example suppose the drawn card is 7, then we go to the pile labeled $7$ and pick a card from this pile. We continue in this fashion. The game ends when we reach an empty pile. And one wins if all the piles are empty when the game ends. It is easy to show that the last card drawn must have face value $K$.

Now, to analyze the probability of winning, the author assumes a different probability space named "Principle of deferred decision". The idea is to "let the random choices unfold with the progress of the game, rather than fix the entire set of choices in advance." With this, they conclude that the probability of winning i.e., the probability that 52nd card being $K$ is 1/13. Can anyone explain why this is 1/13?

$\endgroup$
  • 1
    $\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Jun 7 '16 at 20:17
1
$\begingroup$

You can show that as long as the game goes on, the next card being picked is a random card chosen uniformly among the cards not already picked. We can imagine the same process continuing even if the game does stop. From that point of view, what we have is a completely random order of the deck; the game stops once the fourth king is reached; we win if the fourth king is the last card. Now the probability that the fourth king is the last card is the same as the probability that the last card is a king, which is 1/13.

$\endgroup$
  • $\begingroup$ As far I understand, the probability of picking a card with face value "x" at any stage of the game is 1/13. Am I correct? $\endgroup$ – user2104150 Jun 9 '16 at 16:48
  • $\begingroup$ Depends on whether you're conditioning on what cards have been revealed so far. If you've seen all four aces, then the probability to see an ace drops to zero. The probability that the 11th card is an ace (assuming the game continues somehow even if you get stuck in the middle) is indeed 1/13. $\endgroup$ – Yuval Filmus Jun 9 '16 at 20:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.