4
$\begingroup$

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$?

$\endgroup$
  • $\begingroup$ Can we assume Dr. G's theorem applies only for n>1? $\endgroup$ – DJClayworth Aug 4 '16 at 18:20
  • $\begingroup$ @DJClayworth yes, please. :) $\endgroup$ – Oray Aug 4 '16 at 18:24
  • 1
    $\begingroup$ @JonathanAllan no, because 1 and n are not consecutive numbers if n is not equal to 2. $\endgroup$ – Oray Aug 4 '16 at 18:36
  • 6
    $\begingroup$ Also I am going to submit two guesses: 1-1/e, 1/e cuz that is how math problems happen. $\endgroup$ – Going hamateur Aug 4 '16 at 18:38
  • 1
    $\begingroup$ I actually just started thinking about it a little more analytically, and since there are in the usual case 2 cards adjacent I think it is probably more like 1-1/e^2 but now is not the best time for me to attempt to do a more formal approach and see if I am wrong... (oops just realized it is more of a forward progression, I was double asking the question of adjacency since if a is next to b, b is next to a) $\endgroup$ – Going hamateur Aug 4 '16 at 18:42
6
$\begingroup$

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$):
enter image description here

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}}}$$

$\endgroup$
3
$\begingroup$

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}$

$\endgroup$
  • $\begingroup$ Apologies for any poor exponentials from lacking proper parentheses, I kind of rushed it. $\endgroup$ – Going hamateur Aug 4 '16 at 19:30
  • $\begingroup$ OK so you've shown it for the infinite case, and I've waved a dead chicken at it to convince that it is convergent - but neither of us have proved it can't go lower at some point :p $\endgroup$ – Jonathan Allan Aug 4 '16 at 19:38
  • $\begingroup$ I don't think getting adjacent pairs are independent events. Let's say the first two cards were 2 and 5. Now 1 and 3 have better chance not to have a consecutive card as neighbour when they appear, as 2 is already safe. $\endgroup$ – elias Aug 4 '16 at 19:38
  • $\begingroup$ of course you might be still right with the result, but the reasoning is false. $\endgroup$ – elias Aug 4 '16 at 19:40
  • $\begingroup$ @elias yeah it's one of those infinite cardinality fudges ;p $\endgroup$ – Jonathan Allan Aug 4 '16 at 19:51
1
$\begingroup$

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?)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.