Folks I am sorry for keeping this ball rolling, my interest lies more in finding the probabilities of finding unique events than the methods of creating the randomness.

I would love to discuss this further with anyone interested, as it is potentially part of a commercial venture, so also happy to discuss how best to reimburse for you time and expertise.  

If anyone would like to discuss further, feel free to reply with an email or phone number, or suggest a possible connection who may be willing to assist.

Cheers!

Tom

Tom Kendall wrote:

Andrew Robinson wrote:

"As the number of possible shuffles is so high, an analysis of a sample doesn't seem to be nearly accurate enough."

I don't share your intuition.  Perhaps I'm not following the problem. Can you say more about that?  And more about why you want exact probabilities?  It's a pretty easy experiment to simulate.

I just figure, that as there are 52! outcomes, taking a sample size of even a trillion shuffles does not seem to be a big enough sample size.   And if you start taking larger samples, there is too much data to analyse.

Here's my point of contention.  There's no reason that you can't take a large enough sample that it's informative without it being overwhelming.  After all, we take finite samples from infinite populations all the time :-)  I suggest that you simulate the problem. You can even do it multiple times and take the SD of the outcome to estimate the SE. Or you can assume that the outcome is logical (x = shuffle contains at least one pair) and therefore that the count is a binomial random variable and simulate to an arbitrary level of precision using a mode-based estimate of the standard error. 

So to give further clarification to the problem:

A friend and I were taking about the fact that no properly shuffled deck of cards has (almost certainly) ever been put into that order before, and likely will never be randomly shuffled into that order again.  

We then got into what the chances would be that a random - "properly" - shuffled deck would contain certain poker hands.  But the numbers started to baffle us.

For example, in looking for a pair, there are 12 possible combinations for any card to make a pair.  In this scenario, order matters, i.e., Ace(Hearts) Ace(Clubs) would be an independent outcome from Ace(Clubs) Ace(Hearts).  But then this pair can also appear in any 2 consecutive positions along the shuffle.  It could be the first and second position, it could be the 30th and 31st positions etc.  All of these are seperate outcomes.

Given there are 51 possible positions for a pair to appear, and 13 suits, it would seem to me that the number of pairs are 12 x 51 x 13 = 7956.  BUT, in our case, the order of the remaining cards is important, so there must be 50! possibilities.  Is that correct?  Because (7956 x 50!)/52! leaves a 300% chance of a unique shuffle containing a pair anywhere in the order!

Clearly a 300% chance isn't in the realm of probability as we know it ;-).  But John's answer below suggests that the expected number of times that this might happen is about 3 per shuffle.  

And my simulation gives a mean of about 2.88, and a probability of a random shuffle having at least one pair at 0.9546, with model-based standard error 0.00021.  R snippet is attached.  Does this help?

Cheers

Andrew

Alan Branford wrote:

I attended a combined conference in Perth between the Mathematics Society and the Statistics Society, I being a member of the latter. I cannot remember when it was, but 1992 strikes a chord. Persi Diaconis was the drawcard (pun intended) guest and he gave an inspirational public lecture on all manner of things to do with games and the like, in which the foundational assumptions such as a "fully" shuffled deck of cards were examined. Persi had famously determined how many shuffles were required when riffle shuffling (the deck being split into two packs of 26 cards and the two decks "riffled", that is one card from each deck in alternation). The answer was 7 or 8 or thereabouts. I also attended his lecture in the AMS part of the program that had led to that conclusion. It was an hour of algebra that I barely managed to avoid drowning in! One comment in this current discussion said something like "Persi did a bit in this area". I would say it was quite a lot more than a bit! ... Oh, I believe it's my bid: misere

Just got this Journal content alert, the lastest bit of Persi's contribution to this area:

Persi Diaconis, Soumik Pal,

Shuffling cards by spatial motion,

Stochastic Processes and their Applications,

Volume 152,

2022,

Pages 149-176,

ISSN 0304-4149,

https://doi.org/10.1016/j.spa.2022.06.023.

(https://www.sciencedirect.com/science/article/pii/S0304414922001582)

Abstract: We propose a model of card shuffling where a pack of cards, spread as points on a square table, are repeatedly gathered locally at random spots and then spread towards a random direction. A shuffling of the cards is then obtained by arranging the cards by their increasing x-coordinate values. When there are m cards on the table we show that this random ordering gets mixed in time Ologm. Explicit constants are evaluated in a diffusion limit when the position of m cards evolves as an interesting 2m-dimensional non-reversible reflected jump diffusion in time. Our main technique involves the use of multidimensional Skorokhod maps for double reflections in [0,1]2 in taking the discrete to continuous limit. The limiting computations are then based on the planar Brownian motion and properties of Bessel processes.

Keywords: Markov chains mixing time; Card shuffling; Reflected diffusions; Skorokhod maps; Planar Brownian motion; Stochastic flow of kernels

Duncan Lowes wrote:

[...]

It is a very interesting question and has exercised my brain for too long already

PS Also well outside my area of expertise but I am fascinated at the concept of a proper shuffle in different card games and how that may impact the probabilities. What is a proper shuffle?

[...]

There are many ways in which one can shuffle cards.  The question is how often does one have to shuffle so that the resulting deck can actually be modelled as being a random shuffle (i.e. every permutation being equally likely).

Persi Diaconis did (and does) some work in this area.  According to this work, if a riffle shuffle is used one should do at least 7.  With an overhand shuffle many more are needed (so many, that one will not be invited back by the other card players if one would insist on a proper shuffle).

Last time I heard Persi give a talk about this topic, he was studying the kind of shuffle where  one just spreads the card out over the table, then shuffles the cards around (like tiles before a game of mahjong) before putting them back into a stack again (cannot remember what he called this kind of shuffle).  The question he posed was how vigorously does one have to shuffle the cards to that the desk is a realisation of a random shuffle?  As there are 52! combination, an awful number of trials would be needed to check whether the resulting desks are uniformly distributed using a chi-square test. :)  His question was, how do we establish that something comes from a (discrete) uniform distribution if the number of possible outcomes is large and any experiment will lead to a table with most entries being zero and some having a one?  Apparently he had done a few 100 (1000s?) experiments with students.  Recording the order of the deck, then using this shuffle, recording the new order of the deck, rinse and repeat.  How to show that these could be viewed as realisations of i.i.d well shuffled desk of cards???

Finally, https://en.wikipedia.org/wiki/Shuffling mentions even more ways of shuffling cards, and has pointers t Persi's work.

Some questions here:

How exact does "exact" have to be?

And is this the real problem?

It is not difficult to get some approximate answers which I suspect are quite good approximations.  For example, if you take a random adjacent pair then the probability that it is a matched pair is clearly 3/51 (there are 3 available cards out of the 51 available that match the first of the pair).  Hence the expected number of pairs at this point in the pack is 3/51.  There are 51 such points and hence the expected number of matching pairs is 3.  To get the probabilities we need more information on the distribution but since points far enough apart are perhaps "reasonably" independent a first approximation would be close to Poisson.  Hence the probability of at least one pair would be about 1-exp(-3).