2
$\begingroup$

For example, if we have an Ace of spades, the next card cannot be an Ace nor spades.

Edit: Assuming that we pick one particular shuffle amongst all possible ones

$\endgroup$
15
  • $\begingroup$ Assuming a randomly picked shuffle from all possible shuffles? Very interesting (and on first sight tough) problem. $\endgroup$
    – orlp
    Jun 23, 2018 at 22:38
  • $\begingroup$ @orlp yes, sorry for not clarifying! $\endgroup$ Jun 23, 2018 at 22:44
  • $\begingroup$ @J. Dionisio: What is the source of the problem? $\endgroup$
    – quasi
    Jun 23, 2018 at 22:46
  • 2
    $\begingroup$ To have an idea of whether this was a programming contest problem (implying brute force would likely be the only real solution), a math contest problem (implying there may be some chance at a nice but difficult closed form), a textbook problem (implying an easy closed form), or a problem that was made up (implying there is a chance that the problem is not even answerable in the first place) $\endgroup$
    – JMoravitz
    Jun 23, 2018 at 23:13
  • 1
    $\begingroup$ @J. Dionisio: It's easy to make up combinatorial problems for which an exact symbolic answer is not likely to be achievable. If the problem was from a book or competition, the reader would expect the problem to have a known answer, so might be willing to spend a fair amount of time on it. In the future, please provide such context. In this case, the context is "a problem my cousin made up". That's fine, but we should at least be advised of it. $\endgroup$
    – quasi
    Jun 23, 2018 at 23:15

2 Answers 2

4
$\begingroup$

To get a complete enumeration and thus an exact value for the probability, we can classify ranks according to which suits are left in them. There are $2^4$ different suit patterns for the $13$ ranks, onto which they can be distributed in $\binom{16+13-1}{16-1}=\binom{28}{15}=37442160$ different ways. We also have to remember which card was last played, for which there are at most $52$ possibilities, so we have at most $52\cdot37442160=1946992320\approx2\cdot10^9$ different states to process. We can do this stepping through the $52$ cards one at a time and tallying the number of admissible ways there are to reach the possible states.

Here's Java code that does this. The result is that

$$ 1609436968954808435644946271743718475717055824496860279603200 $$

different deals out of the total of

$$ 52!=80658175170943878571660636856403766975289505440883277824000000000000 $$

are admissible, which yields a probability

\begin{eqnarray*} &\frac{1609436968954808435644946271743718475717055824496860279603200 }{80658175170943878571660636856403766975289505440883277824000000000000}\\\\&=\frac{5258385993865270320943168907713343815039252427}{263528070245000096386506036857149662453104640000000000}\\\\&\approx1.9954\cdot10^{-8} \end{eqnarray*}

in good agreement with Ross' estimate and quasi's simulation.

Note that I didn't make use of the permutational symmetry among the suits. That would require a bit more programming effort, but would further substantially reduce the number of states that need to be processed.

$\endgroup$
1
  • $\begingroup$ I like the approach (+1). I'll try to verify your results when I get a chance. $\endgroup$
    – quasi
    Jun 25, 2018 at 14:36
2
$\begingroup$

Roughly speaking each card after the first has a $\frac {15}{51}$ chance of causing a failure, or a $\frac {36}{51}$ chance of success. This ignores correlations between the cards, but should not be far wrong. To succeed $51$ times in a row, the chances would be $$\left ( \frac {36}{51}\right)^{51} \approx 1.9\cdot 10^{-8}$$

$\endgroup$
6
  • 1
    $\begingroup$ I probably didn't express myself well, but I'm looking for an exact solution $\endgroup$ Jun 23, 2018 at 23:08
  • 1
    $\begingroup$ I suspect an exact solution is very hard. I think this is convincing that it is very rare. $\endgroup$ Jun 23, 2018 at 23:10
  • 2
    $\begingroup$ Your heuristic estimate seems fine to me (+1). I would guess that an exact symbolic solution is not achievable, even with computer assistance. $\endgroup$
    – quasi
    Jun 23, 2018 at 23:23
  • $\begingroup$ @nbegginer $36!/51!$ has nothing to do with the problem. The result of $(\frac{36}{\color{red}{52}})^{51}$ (note the denominator change) would be correct for dealing $52$ cards from an infinite shoe (i.e. dealing with replacement), but accounting for replacement in this problem does not simply mean "turn the numerator and denominator into factorials." The correct expression, as discussed elsewhere in this thread, is going to be far too messy and is still expected to result in a final answer around $10^{-8}$, certainly not in the range of $10^{-24}$. $\endgroup$
    – JMoravitz
    Jun 24, 2018 at 0:05
  • $\begingroup$ Using a simulation with $10^{\,10}$ randomly shuffled decks, exactly $195$ of them satisfied the specified restrictions. Hence, noting that $$\frac{195}{10^{\,10}}=1.95{\times}10^{-8}$$ the simulation provides empirical support for Ross Millikan's heuristic estimate. $\endgroup$
    – quasi
    Jun 24, 2018 at 8:48

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .