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

 Supreme Successive Shuffle (Posted on 2009-12-15)
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.)
 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        32256010 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

 Search: Search body:
Forums (0)
Random Problem
Site Statistics
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox: