sheldon ross

Question

Consider the following technique for shuffling a
deck of n cards: For any initial ordering of the
cards, go through the deck one card at a time and
at each card, flip a fair coin. If the coin comes
up heads, then leave the card where it is; if the
coin comes up tails, then move that card to the
end of the deck. After the coin has been flipped n
times, say that one round has been completed. For
instance, if n = 4 and the initial ordering is 1, 2, 3,
4, then if the successive flips result in the outcome
h, t, t, h, then the ordering at the end of the round
is 1, 4, 2, 3. Assuming that all possible outcomes of
the sequence of n coin flips are equally likely, what
is the probability that the ordering after one round
is the same as the initial ordering?

Answer 1

Here we have to construct solution for larger problem using smaller problems i.e. first we consider n=2 , then n=3, based on the observation we can conclude for higher value of 'n'..

For  n = 2,

Say the initial  ordering is  { 1 , 2 } , then the instances of 2 tosses where this order will be preserved are : { HH , HT , TT } and violated for  { TH } ..

Hence P(order is preserved for n = 2)   =  3 / 4

Now for n = 3 , we have to ignore those instances which end  in  "TH" as we have seen in previous subproblem that "TH" creates the violation and hence adding either head or tail before it wont help..

Hence instances remaining   =   8 - 2   =   6..

Now out of these 6 instances , we cannot add tail to "HH" and "HT" because it will put the first element at the last preserving the last 2 elements (2 and 3) thereby disturbing the overall order..However , tail can be added to "TT" because if we perform the second operation as mentioned in question to {1,2,3} , then we will get back {1,2,3} only..Also as "HH" and "HT" are already valid as shown in previous subproblem , adding head wont create a problem..

Hence favorable outcomes  =   6 - 2    =  4 

Hence P(order remains same for n = 3)    =   4 / 8

Now these 4 favorable outcomes will be considered for  n  =  4..

As similar to approach described for n = 3 , except the instance "TTT" , for all other 3 valid instances , we can have head in front not tail..For "TTT" , we can have either head or tail..

Hence P(order remains same for n = 4)     =  5 / 16

This way for any general integer 'n' , we can generalise as :

P(order remains same after n tosses)       =  (n + 1) / 2ⁿ

Hence the required probability should be   (n + 1) / 2ⁿ