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?
The following program tracks the numbers for M = 1 to 10:
DECLARE SUB permute (a$)
DEFDBL AZ
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 M1 possible next numbers and M1 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 20091215 11:52:44 