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 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 |
For M=1 to 10 by counting---plus conjecture
