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?

Some thoughts.
All m! permutations of m cards can be produced by inserting the card marked ‘m’ into each of the m possible places in each of the (m – 1)! permutations of m – 1 cards. If a(m – 1, k) is the number of permutations of m – 1 cards that contain k successive pairs (s-pairs), then the insertion of card ‘m’ will have one of the following effects.
(A)  An Insertion just after card ‘m – 1’ will increase the number of s-pairs by 1.
(B)  An insertion that splits an s-pair will decrease the number of s-pairs by 1.
(C)  An Insertion in any other place will not change the number of s-pairs.
A, B and C can happen in 1, k and m – 1 – k ways respectively, and the resulting permutation will contain r s-pairs only if A, B and C are applied to permutations initially containing (k =) r – 1, r and r + 1 s-pairs respectively. This gives:

a(m, r) = a(m – 1, r – 1) + (r + 1) a(m – 1, r + 1) + (m – 1 – r) a(m – 1, r)   (1)

Using a(1, 0) = 1 and a(2, 0) = 1 allows evaluation for 0 <= r <= m – 1.

a(m, r)                         r =       0          1          2          3          4
            m =      1                      1
                        2                      1          1
                        3                      3          2          1
                        4                      11         9          3          1
                        5                      53         44         18         4          1          etc..

Using r = 0 in (1) gives:              a(m, 0) = a(m – 1, 1) + (m – 1) a(m – 1, 0)
and the using the fact that           a(m - 1, 1) = (m – 2) a(m – 2, 0)
gives:               a(m, 0) = (m – 2) a(m – 2, 0) + (m – 1) a(m – 1, 0)

Abbreviating a(m, 0) to A(m) we can then write:
     A(m) = (m – 1) A(m – 1) + (m – 2) A(m – 2) with A(1) = A(2) = 1        (2)
where A(m) is the number of permutations of m cards that contain no s-pairs.
[The number of perms with at least 1 s-pair will be m! – A(m)].

(2) allows easier evaluation of A(m) values, which are shown below together with A(m)/m! , the probability of no s-pairs.

m                     A(m)                 P(no s-pairs)      =
1                      1                      1/1                   1         
2                      1                      1/2                   0.5
3                      3                      3/6                   0.5
4                      11                     11/24                0.4583333333..
5                      53                     53/120              0.4416666667..
6                      309                   309/720            0.4291666667..
10                     1468457            long                  0.4046673832..
100                   big                    long                  0.3715582356..
1000                 big                                            0.3682473206..
10000               big                                            0.3679162291..

It appears that the probability of having no s-pairs tends to a limit which could well be 1/e (whose value is 0.36787944117..). The probability of at least one s-pair would then be 1 – 1/e, as Charlie conjectured.

However, I’ve not yet proved that this is the limit, though (2) should be sufficient information to complete a proof. I’ll keep trying.

Posted by Harry on 2009-12-18 00:18:57