Aug 28 2010
On Permutations, Probabilities and Psychology
Shuffling an array of items is a common topic in programming, especially as an academic exercise. In my previous post, I wrote about a different approach towards cards shuffling in programming – which is to not do it. Instead, you can randomly select and remove an item from the array whenever you need to retrieve an item. As far as distribution of probabilities goes, there is no difference between the two methods.
The seemingly controversial topic received some interesting comments. Due to certain fallacies introduced by a commenter, I thought I should clarify those points for the benefit of any reader who might become confused after reading his comments. My reply got a little too long, so I am posting it here.
Permutations
pantelis wrote:
“if you have 2 objects there are 2 possible arrangements of them. If you have 3 there are 6 and if you have 52 there are 52! (1*2*3*…*52). So, the probability of a particular hand (consisting of 52 cards) is 1/52! According to your math the probability of a given sequence is (1/52)^52 which means that there are 52^52 possible arrangements. and that is simply wrong.”
pantelis wrote:
“your math is wrong. i already gave you a counter proof of that: 52 items can be arranged in 52! ways. this is a fact of life, ever since pascal, bernoulli, and poisson (and their gambling habits) have founded statistics. therefore, the probability of one particular hand (it doesn’t matter which) is 1/52! your math results in (1/52)^52.”
Actually, my math results in 51!.
I never quite understood how pantelis arrived at the 52^52 permutations (he was reminded about “remaining cards” and he seems to understand the concept of “drawing without replacement”).
When you shuffle an array of 52 items, the number of ways they can be arranged is 52!.
When you randomly select and remove one item from an array until all items have been removed, the number of ways that the items can be arranged is still 52!.
When you randomly select an item from an array without removing it for the next selection, then for a sequence of 52 picks, there are 52^52 permutations.
In any case, for our discussion on “shuffle and draw from top” vs “random pick on demand”, the number of permutations does not really matter. It is the distribution of probabilities for each card that matters.
Probabilities
pantelis wrote:
“we agree that the probability of a particular card be drawn first is 1/52. after the first card is drawn, there is no such thing as “for a card to be drawn as the second card, it must not be drawn as the first card – got that? The chance of that happening is 98.08% (51/52)”. pardon me, but, i haven’t got that.”
pantelis wrote:
“the probability of a particular card to be drawn second is equal to 1/51, because there is only one favorable outcome (that particular card) and 51 possible outcomes, to be drawn third is 1/50 and so on.”
That is where pantelis went wrong. That is exactly the misconception I highlighted in the original post. It is wrong to think that if you randomly pick and remove a card from a deck of 52 cards, the distribution of probabilities will be skewed.
Consider an example.
The probability of a certain card, say Ace of Spades, being drawn as the third card is the compounded probability of three events that MUST occur:
(i) Aces of Spades NOT being drawn as first card (51/52 chance); and
(i) Aces of Spades NOT being drawn as second card (50/51 chance); and
(ii) Aces of Spades bring drawn as third card (1/50 chance).
Therefore, the chance of a particular card (eg. Ace of Spades) being drawn as the third card is
51/52 x 50/51 x 1/50 = 1/52.
pantelis wrote:
“after the first card is drawn the probability of the second card not been drawn as the first card is 1 (because we are certain that the second card was not drawn first).”
That is a bad twist of words resulting in the wrong framing of the problem at hand, which led to the wrong math. We are interested in the probability of “a particular card not being drawn as the first card”, not “the second card not being drawn as the first card”.
pantelis wrote:
“according to your logic the probability of a particular card been drawn first, second, or last is 1/52… “
Yes, that is exactly what I am saying.
The distribution of probabilities for each card must be statistically fair, and it is. Whether you shuffle the deck and draw the cards sequentially, or you pick a card at random each time, the distribution of the probabilities remain the same.
Consider the following scenarios:
(i) You take a fresh deck of 52 cards, shuffle it, draw 2 cards from the top of the deck and discard them. What is the chance of the next card drawn (ie 3rd card) from the top of the deck to be Ace of Spades?
(ii) You take a fresh deck of 52 cards, shuffle it, draw 1 card from the top of the deck and discard it. Shuffle the deck again, draw another card from the top of the deck and discard it. Shuffle the deck again. What is the chance of the next card drawn from the top of the deck to be Ace of Spades?
(iii) You take a fresh deck of 52 cards. Now, don’t shuffle it. Let’s ask Paul the Octopus, who is completely innocent and ignorant of the way a fresh deck of cards is prearranged, to truly randomly pick one card from the deck and discard it. Ask him/it to do it again a second time, also completely randomly without bias. What is the chance of the third card Paul picks, truly randomly without bias, from the deck of remaining cards to be Ace of Spades?
The answer: 1/52. Same for (i), (ii) and (iii).
Now, do the above again, this time revealing the cards as they are drawn. Assuming that neither the first nor second card is Ace of Spades, what is the chance that the third card would be Ace of Spades?
The answer: 1/50. Unlike in (i), (ii) and (iii), there is a stipulated condition here that Ace of Spades is not picked as the 1st or 2nd card.
As the above shows, whether you shuffle a deck and then draw from the top, or pick cards at random, or shuffle and reshuffle multiple times, the probability of a particular card being drawn at a particular position remains the same.
I hope that clears things up about permutations and probabilities.
Psychology
jason wrote:
“When shuffling a deck (or multiple decks) of cards in the “real” world (ok, so we don’t live in the Matrix), once the cards are shuffled they stay in that order until they’re dealt (or reshuffled). So randomly picking a card at deal-time does not actually maintain the “reality” of shuffling prior to dealing any cards, though it nets a similar result. Ultimately, I’d agree there’s no serious issue with this, but…it feels “righter” to me to go the pre-shuffle route.”
jason brought up a completely valid point – one of psychological barrier. People get so caught up with “shuffling”, that they forgot the real purpose behind it. It “feels” right to go the shuffle route only because that is what we do in the non-digital world.
The reason behind the “shuffle” in non-digital games is to introduce randomness. There was no other way. Computers can implement their own randomizers, thus my question for the need for a shuffle. I will also debate that the way computer shuffles an array of cards typically does not maintain the “reality” too, because the algorithm will not accurately simulate shuffling by hand.
Does it really matter for cards to stay in a predefined order? It only serves to give players a false sense of fairness where distribution of “luck” is concerned. It only matters to players who superstitiously believes that shuffling the deck changes the distribution of luck for a given round of game. When a deck is shuffled, players believe that their “luck” is fixed for that round of game. However, where probabilities are concerned, they remain the same.
The order of the cards will matter to players who can somehow see the sequence of the cards. But that is akin to hackers who employ memory inspection to see the sequence of a shuffled deck (another reason for not doing shuffles in software).
The only time having cards stay in a predefined order will be for situations where the sequence of the cards is revealed. But that is also equivalent to picking one card randomly until all cards are drawn and revealed.
I agree that the psychological barrier can be tough to crack. After all, most people do not define “luck” as “the probability of achieving a favorable outcome”.
However, the mental beast is one that can be tamed and re-programmed. In the past, dealers in casinos used to shuffle by hand. Nowadays, (continuous) shuffling machines are used. The human touch is missing (where is the “cut” which some gamblers believe affects the distribution of luck?), but it has not affected the traffic. Patrons have been re-programmed to accept the new system. Likewise for slot machines, the game has been digitized and degenerated to simple presses of a button rather than the pulling of levers. These changes have warped “reality” and have actually made games run faster (and casinos make more money running more games per minute).
The “reality” has changed, only because mindsets have.
Strange concept