Dr. G's Interesting Theorem on Playing Cards

Question

Dr. G has spent his last weekend with analyzing $n$ number of cards which are numbered from $1$ to $n$. He has a fair shuffling machine for his cards and while playing and drawing some cards, he uses his shuffling machine all the time.

After a while, he noticed something interesting. He usually encounters two consecutive numbered cards at least once while drawing the cards orderly or randomly without shuffling them back to the deck until he has no card in the deck.

First of all, he got shocked how come he encounters two consecutive numbered cards most of the time after shuffling them in a fair shuffling machine because there were many cards he was drawing and firstly the chance to see two consecutive cards in a row seemed very low to him. Then he noticed something and he put some numbers on a paper and come up with an interesting theorem.

Dr. G's Theorem: Even if there are infinite number of cards which are numbered sequentially from $1$ to $n$, where $n$ is a positive integer number, your chance to encounter two consecutive numbered cards at least once cannot be less than $x \%$ until you draw all the cards which are shuffled fairly.

Is this theorem true, if so, what is $x$?

Answer 1

Not a proof...

Theorem is likely true with $x\approx 0.86467$ probably $x=1-e^{-2}$

Because

It seems to converge pretty fast ($n$ on x-axis, $P(\text{consecutive})$ on y-axis - note bottom is not $0$):

Python code:

Binomial, $\binom{n}{k}$:

def choose(n, k):
    '''Returns the number of ways to choose k items from n items'''
    reflect = n - k
    if k > reflect:
        if k > n:
            return 0
        k = reflect
    if k == 0:
        return 1
    for nMinusIPlus1, i in zip(range(n - 1, n - k, -1), range(2, k + 1)):
        n = n * nMinusIPlus1 // i
    return n

Factorial, $n!$:

fact=lambda n: n and n*fact(n-1) or 1

The number of shuffles of n cards is the number of permutations which is $n!$.

The number of permutations which have no consecutive cards:

noConsecutive=lambda n: sum((-1) ** (n - k) * fact(k) * sum(choose(i + k - 1, k - 1) * choose(k, n - i - k) for i in range(n - k + 1)) for k in range(1, n+1))

The chance of getting a deal with any two consecutive cards is therefore:

def chanceConsecutives(n):
    total = fact(n)
    return (total - noConsecutive(n)) / total

The plot shown uses matplotlib but

let us take a look at that right tail:

>>> for n in range(94, 101):
...     n, chanceConsecutives(n)
...
(94, 0.8646959031912789)
(95, 0.8646952442738943)
(96, 0.8646946060214447)
(97, 0.8646939875787265)
(98, 0.8646933881343243)
(99, 0.8646928069179473)
(100, 0.8646922431979533)
>>>

and a bit further out:

>>> for n in range(394, 401):
...     n, chanceConsecutives(n)
...
(394, 0.8646664677798308)
(395, 0.8646664589063986)
(396, 0.8646664501002465)
(397, 0.8646664413606958)
(398, 0.8646664326870768)
(399, 0.8646664240787278)
(400, 0.8646664155349957)
>>>

---

Mathematics now...

We need to show that $P(n)$

will never fall below out theorised threshold:$$P(n)=1-\frac1{n!}\sum_{k=1}^n{(-1)^{n-k}k!\sum_{i=0}^{n-k}{\binom{i+k-1}{k-1}\binom{k}{n-i-k}}}$$

Answer 2

What are the odds in the infinite case? Well I choose the infinite case to neglect the two edge cases.

So we are going to have a $\frac{2}{n}$ chance for each new card that is either above or below it. This is going to happen n times.
So the odds of not getting an adjacent pair are $\frac{n-2}{n}$. And this happens as n (from what I can tell) independent events. So we get $\frac{n-2}{n}^{n}$.
Now by cool mathemagic: this is $1-\frac{1}{e^2}$
Why? Well a well known identity is $\frac{n+1}{n}^{n} = e$ and $\frac{n-1}{n}^{n} = \frac{1}{e}$for really large n $\frac{n-2}{n}$ is effectively equal to $\frac{n-1}{n}^{2}$
So we get ${\frac{n-1}{n}^{2}}^n$ which is ${\frac{n-1}{n}^{2n}}$ or ${\frac{n-1}{n}^{n}}^2$ or $\frac{1}{e}^2$.
So the final answer is $1-\frac{1}{e^2}$

Answer 3

Dr. G is

correct

as can be seen by looking at the last entry under "Formula" at

http://oeis.org/A002464 which says that asymptotically the number of permutations with no adjacent pairs is $1/e^2$ of all of them.

Presumably

the correct value of $x$ is $1-1/e^2$, but that doesn't follow from the above unless we know that the fraction with no adjacent pairs increases monotonically, which looks likely but I don't see how to prove. (Perhaps with a little work it follows from the recurrence relation, or from the asymptotic formula if its error bounds can be made explicit?)