Menu
Log in


Probability for card shuffles

<< First  < Prev   1   2   Next >  Last >> 
  • 9 Nov 2022 7:42 PM
    Reply # 12983185 on 12863509

    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

  • 19 Sep 2022 12:23 PM
    Reply # 12923660 on 12889047
    Berwin Turlach wrote:
    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.





    Thankyou for your response. Apologies for not having visited the forum for a while. It struck  me a curious thing that a "proper" shuffle could be an infinite process. Would it not also depend on the game being played? Am reading about Persi's work thankyou :)

    But in all seriousness I am not qualified to deconstruct the idea of randomness and what constitutes a random event

    I am also curious about all those wasting computer power thinking there are 52! combinations. There are many fewer than that in this problem

    Last modified: 19 Sep 2022 12:46 PM | Duncan Lowes
  • 29 Aug 2022 3:33 PM
    Reply # 12899274 on 12892711
    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

    1 file
    Last modified: 29 Aug 2022 3:38 PM | Andrew Robinson
  • 23 Aug 2022 8:26 PM
    Reply # 12892711 on 12869014
    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.


    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!

    To be honest,  I have truly twisted my brain thinking about it! 

    Any help would be greatly appreciated!

    Last modified: 23 Aug 2022 8:41 PM | Tom Kendall
  • 23 Aug 2022 2:06 AM
    Reply # 12891761 on 12891238
    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



  • 22 Aug 2022 3:47 PM
    Reply # 12891238 on 12863509

    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

  • 20 Aug 2022 1:01 AM
    Reply # 12889047 on 12888746
    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.





    Last modified: 20 Aug 2022 1:04 AM | Berwin Turlach
  • 19 Aug 2022 6:20 PM
    Reply # 12888746 on 12863509

    I feel anxious commenting on this but got as far as trying to work from a simpler pack

    Then I read the thread Chris put up and someone had used the exact same approach with a nice simple pack. I am asking the world to believe that I independently used the exact same simplification to try to understand the issue. Independently used my brain. Oops someone will challenge me on the independence of my approach and the other person's approach

    Work from there

    I reckon there is an exact mathematical expression, albeit extremely complicated to write out and calculate

    Apologies if this is wrong, and I will be very embarrassed if wrong, but I reckon the chance of the first two cards being a pair to be in the order of 1/17. What is remarkable is how many hands you would need to estimate that through simulation. I also worked out (I think) that given that the first two don't match as a pair the probability of the second two being a pair is in the order of 3/50

    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? Is there a test we can apply to test the hypothesis of a properly shuffled pack? And so it goes. Sorry for sounding flippant but it genuinely interests me


    Last modified: 19 Aug 2022 6:44 PM | Duncan Lowes
  • 1 Aug 2022 6:46 PM
    Reply # 12869046 on 12863509

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

  • 1 Aug 2022 3:20 PM
    Reply # 12869014 on 12863509

    "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.



<< First  < Prev   1   2   Next >  Last >> 
Powered by Wild Apricot Membership Software