All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Probability
Supreme Successive Shuffle (Posted on 2009-12-15) Difficulty: 4 of 5
A deck of M cards is numbered 1 to M and shuffled, and dealt from top to bottom.

Denoting the probability of dealing at least one pair of successive cards in their proper order (that is, a 1 followed by a 2 or, a 2 followed by a 3, and so on) at any position in the deck by s(M), determine s(M) as M → ∞ (The pairs may overlap. For example, for M=5, we have two successive pairs corresponding to 73452.)

As a bonus, what is the expected number of such successive pairs in an M card deck as a function of M?

No Solution Yet Submitted by K Sengupta    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
Some Thoughts For M=1 to 10 by counting---plus conjecture | Comment 1 of 9

The following program tracks the numbers for M = 1 to 10:

DECLARE SUB permute (a$)
DEFDBL A-Z
FOR i = 1 TO 10
 hitCt = 0: hitTot = 0: ct = 0
 s$ = ""
 FOR j = 0 TO i - 1
   s$ = s$ + LTRIM$(STR$(j))
 NEXT
 h$ = s$
 DO
  hit = 0
  FOR i = 1 TO i - 1
   IF VAL(MID$(s$, i + 1, 1)) = VAL(MID$(s$, i, 1)) + 1 THEN hit = hit + 1
  NEXT
  IF hit THEN hitCt = hitCt + 1: hitTot = hitTot + hit
  ct = ct + 1
 
  permute s$
 LOOP UNTIL h$ = s$
 PRINT USING "## "; i;
 PRINT USING "#######"; ct;
 PRINT USING "##############"; hitCt; hitTot
NEXT

 

The resulting table is:

                  at least    total number
 M permutations   one hit       of hits
 1       1             0             0
 2       2             1             1
 3       6             3             4
 4      24            13            18
 5     120            67            96
 6     720           411           600
 7    5040          2921          4320
 8   40320         23633         35280
 9  362880        214551        322560
10 3628800       2160343       3265920


So for example, when M=5, the probability is 67/120 ~= .5583333 that there will be at least one pair of successive cards, and the expected number is 96/120 = 4/5 = .8.

By M=10 the probability of at least one has reached about .5953326168430335 and the expected number has reached .9.

Can we get a formula out of this?

Conjecture:

Similar to the probability that a large number of people separated from their hats will result in one or more being reunited at random with their own hat, there are M-1 possible next numbers and M-1 chances for this to be the next cardinal number, so the expected number would approach 1. In such a situation the probability that there would be no match (no hit) would approach 1/e, so the probability there'd be at least one hit would approach 1 - 1/e or about .6321205588285577.


  Posted by Charlie on 2009-12-15 11:52:44
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (8)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information