What are the odds of that?

November 17, 2006 7:47 AM

A regular deck of 52 cards is shuffled and turned face up one by one. What are the odds of going through the whole deck and finding at least one set of two consecutive cards which have the same value? (ie, a pair).

Over 30 years ago, I went through a period in 5th or 6th grade where I became fascinated by how it seemed like I could never end up running through the whole deck without encountering at least 1 pair. It was like magic to me. Someone out there must be able to easily calculate the exact probability of this and put a number to my wonderment.

posted by jaimev to grab bag (27 comments total)

It's not a simple question, at least if you want an exact answer. It's easy enough to determine that the probability of the second card having the same value as the first is 3/51. And it's easy enough to determine that of the 48/51 times where the first two cards are unequal, 3/50 of those will have the second card equal the third. But after that it gets tricky: if you get no pairs among the first three cards, the probability of the fourth card matching the third depends on whether the first and third cards matched (if they did, it's 2/49; if not, 3/49). You get into all sorts of complex conditional probabilities real quick, and I don't see an easy way around that.

If you want an approximation, a Monte Carlo method might be appropriate. (Basically, have a computer simulate shuffling a deck of cards many thousands of times and see how often it happens.)
posted by DevilsAdvocate at 8:01 AM on November 17, 2006

This is totally cheating, but assuming you were drawing from an deck with an infinite amount of each card the chances of NOT getting a pair with each draw are (12/13). Since you'd be flipping 51 times for a standard deck that would be 12/13 ^ 51, or about 1.7% of not getting a pair - 98.3% chance of pairing at some point during the flipping.

Of course this is totally wrong when confronted with a real deck, but I don't know how much and in which direction.
posted by true at 8:17 AM on November 17, 2006

i wrote a simulation... i would use the monte carlo method; more of a simulation.

  do {

		deck = FULL_DECK_MASK;

		found = 0;

		for (i = 0; i < 1; i++) {br>
			for (j = 0; j < nb_cards; j++) {br>
				if ((mask =CARDS_pick_random(&deck,RANDVAL)) < 0) {br>
					ABORT(10); }



				for (k=0;k
					if ((rank_masks[k]&mask) &&

						(rank_masks[k]&prev_mask)) {

						found = 1;

						break; } /* if */

				} /* for */



                                if (found)

                                    break;

				prev_mask = mask;

			}



			total++;

			total_found += found;



			printf("%d %d %.5f\n", total_found, total, ((float)total_found/(float)total)*100);

		}

	} while (1);           

it produced this....

618349 645296 95.82409

now its up to the real mathematicians to vet this.
posted by sleslie at 8:22 AM on November 17, 2006

Another Monte Carlo:


number_of_trials = 100000;

for ii = 1:number_of_trials
deck = randperm(52);
number = mod(deck,13);
f = find(number(1:51)==number(2:52));
number_of_pairs(ii) = length(f);
end

probability_of_at_least_one_pair = length(find(number_of_pairs)>1)/number_of_trials
average_number_of_pairs = mean(number_of_pairs)

It produces:

probability_of_success =

0.9549


average_number_of_pairs =

3.0036


In other words, you expect to get a pair 19 times out of 20. And the average number of pairs on each run through the deck is 3.
posted by beniamino at 8:29 AM on November 17, 2006

(probability_of_at_least_one_pair equals probability_of_success)
posted by beniamino at 8:32 AM on November 17, 2006

I wrote a similar simulation to sleslie's but came up with 95.4% after a million trials.

Here's my code:

while(true)

{

	++$sample;

	$last = ';

	$paired = false;

	$deck->shuffle();

	$i = 0;

	while($i < 52 && !$paired)br>
	{

		$index = $deck->order[$i];

		$value = $deck->cards[$index]->value;

		if($last == $value)

		{

			$paired = true;	

			++$pairs;

		}

		$last = $value;

		++$i;

	}

	$rate = $pairs / $sample;

	if($sample % 100 == 0)

	{

		echo "Found $pairs paired decks out of $sample: $rate\n";

	}

}

I think (but could very well be wrong) that sleslie has a small error-- a deck would be considered paired if its first card is the same as the last one from the previous simulation. prev_mask needs to be reset for each run.
posted by justkevin at 8:36 AM on November 17, 2006

thanks justkevin, you are right. I got 95.4% after the error you corrected was implemented.
posted by sleslie at 8:48 AM on November 17, 2006

Given a card, the odds that the next card doesn't match is 48/51. There are 51 pairs. Each pair can be considered independently -- the odds don't change as the deck is dealt. So, the probability that all 51 pairs don't match are (48/51)^51, or 0.0454. The odds that at least one pair matches is 1-(48/51)^51, or 0.9546.
posted by blue mustard at 9:46 AM on November 17, 2006

Wait -- why don't the odds change as the deck is dealt? I mean, if I get an ace on draw 1, then sure -- my odds are 48/51 of getting an ace on draw 2. But if I get an ace on draws 1, 3, and 7, aren't my odds of an ace on draw 8 only 1/45?

Is it simply that by discarding aces early, I increase the odds of non-ace pairs later? Do those probabilities effectively cancel out, meaning that we can treat the draws independently even though they're technically not?
posted by nickmark at 10:59 AM on November 17, 2006

@nickmark - If you wanted to know what the odds of hitting a pair on the nth card, then we would need to do dependent draws. But since we want it abstractly, we don't need to do drawing without replacement.

An example: in theory, the odds of a pair on the last two cards is the exact same as a pair on the first two, a priori. In practice, by the time you got to the last two cards, you would know for certain whether the last card would be a pair or not, just by looking at all the previous cards. That's not the same as the theoretical probability.
posted by allan at 11:36 AM on November 17, 2006

Yes, nickmark is right--the odds do change as the deck is dealt, and blue mustard is wrong. (And shame on jaimev for marking that as best answer!!)

A demonstration that blue mustard is wrong can be seen by applying his reasoning to a simpler deck. Suppose we have a deck of only four cards: AS, AH, 2S, 2H. And we want to know the probability that, when shuffled, this deck will contain at least one consecutive pair.

According to blue mustard's reasoning: "Given a card, the odds that the next card doesn't match is 2/3. There are 3 pairs. Each pair can be considered independently -- the odds don't change as the deck is dealt. So, the probability that all 3 pairs don't match are (2/3)^3 [i.e., 8/27], or 0.2963. The odds that at least one pair matches is 1-(2/3)^3 [i.e., 19/27], or 0.7037."

But with such a small deck, it is relatively simple to exhaustively list all 24 possible orders of the shuffled deck, and upon doing so we find that the probability of getting at least one pair is not 19/27, but 16/24, or 0.6667.
posted by DevilsAdvocate at 11:37 AM on November 17, 2006

Now, what are the odds using a Svengali deck?
posted by yeti at 11:40 AM on November 17, 2006

The question is whether a shuffled deck either has two consecutive matched cards. We don't know that the first card is an ace. Any card has equal chance of being in any pair, which is why the pairs can be considered independent.

If one was to examine the deck a card at a time, as you describe, the probability of a match will change as each card is revealed. But that's not the same question.
posted by blue mustard at 11:48 AM on November 17, 2006

An example: in theory, the odds of a pair on the last two cards is the exact same as a pair on the first two, a priori.

While the two probabilites are the same, a priori, the two events (cards 1 and 2 being a pair, and cards 51 and 52 being a pair) are not independent. Thus, you cannot simply multiply probabilities to get the overall probability.

As an illustration, suppose we shuffle a "deck" of two cards, one red and one black. What is the probability that the first card is red? 1/2. What is the probability that the second card is red? 1/2. So what is the probability that both cards are red? Do we say that it's 1/4, because 1/2*1/2=1/4? Of course not. Even though we have calculated the probability of the first card being red, and that of the second card being red, correctly, we cannot calculate the probability that both cards are red simply by multiplying the probabilities, because the events are not independent.

Likewise, while you are correct that the probability of the first two cards not matching is 48/51, and the probability of the last two cards not matching is also 48/51 (as well as any two consecutive cards), the events are not independent, and thus you cannot calculate the overall probability simply by multiplying the individual probabilities.
posted by DevilsAdvocate at 11:49 AM on November 17, 2006

If you can get 51 chance pairs of 2 with a possibility of 39 total pairs (overlapping quads adds up to three pairs), then you have a theoretical probability of ₅₁C₂ divided by ₃₉C₂, where _nC_k is n!/k!(n-k)!

This is (51!/49!2!)/(39!/37!2!) or 2550/1482

= 1.72
posted by Brian B. at 11:50 AM on November 17, 2006

If one was to examine the deck a card at a time, as you describe, the probability of a match will change as each card is revealed. But that's not the same question.

It's exactly the same question. Whether the entire deck is turned over at once, or whether it's revealed one card at a time does not affect whether the deck contains two consecutive matched cards.

"We shuffle a deck of cards. What is the probability that two consecutive cards are a pair?"

"We shuffle a deck of cards, and then look at the cards, from the top, one at a time. What is the probability that two consecutive cards are a pair?"

Are you seriously suggesting that these two questions have different answers? If so, please explain, given the simplified deck of four cards I described above (two aces and two twos) which one has the answer 18/27, and which has the answer 16/24.
posted by DevilsAdvocate at 11:54 AM on November 17, 2006

= 1.72

Probabilities are generally between 0 and 1.
posted by DevilsAdvocate at 11:56 AM on November 17, 2006

I like DevilsAdvocate example of (AS,AH,2S,2H). It does seem to indicate I'm wrong. I'm not yet buying DA's description of why I'm wrong though.... hmm....

"What is the probability that two consecutive cards are a pair?"
My point is that if you ask this question after you've looked at the first two cards, you get a different answer than if you ask before looking at any cards.
posted by blue mustard at 12:07 PM on November 17, 2006

My point is that if you ask this question after you've looked at the first two cards, you get a different answer than if you ask before looking at any cards.

Yes, that's true. I'm not saying the probability of the deck containing at least one pair, once we know what the first two cards are, is the same as the probability prior to that knowledge. (After all, if the first two cards match, then the probability of the deck containing at least one pair is 1!) I'm saying that we have to take those subsequent probabilities into account in order to answer the original question.

Looking at (AS, AH, 2S, 2H) again: the probability that the first two cards do not match is 2/3. The probability that the second and third cards do not match is 2/3. The probability that the last two cards do not match is 2/3. On this, we agree. What I'm saying is that these three events are not independent, therefore we cannot simply multiply the probabilities together to determine the probability of all three events happening.
posted by DevilsAdvocate at 12:19 PM on November 17, 2006

To further the analogy, this is what I'm saying is the correct way to analyze (AS, AH, 2S, 2H), without listing out all the possible orders:

1. P(C1=C2) = 1/3
2. P(C1≠C2) = 2/3
- 2A. given (C1≠C2), P(C2=C3) = 1/2. Thus, P(C1≠C2 & C2=C3) = 2/3*1/2 = 1/3.
- 2B. given (C1≠C2), P(C2≠C3) = 1/2. Thus, P(C1≠C2 & C2≠C3) = 2/3 * 1/2 = 1/3.
- - 2B1. Given (C1≠C2 & C2≠C3), P(C3=C4)=0. Thus, P(C1≠C2 & C2≠C3 & C3=C4) = 1/3*0=0.
- - 2B2. Given (C1≠C2 & C2≠C3), P(C3≠C4)=1. Thus, P(C1≠C2 & C2≠C3 & C3≠C4) = 1/3*1 = 1/3.

Probability of at least one pair = P(C1=C2)+P(C1≠C2 & C2=C3)+P(C1≠C2 & C2≠C3 & C3=C4) {since they are mutually exclusive, we can add their probabilities} = 1/3 + 1/3 + 0 = 2/3.
posted by DevilsAdvocate at 12:39 PM on November 17, 2006

OK, I think I've got an exact answer. Well, not exact in terms of the actual fractional probability, but exact in the sense that it's derived rather than approximated, and that the actual fractional probability could be worked out the same way I've done this, if you wanted to work with 60-digit numbers or so.

Here's an overview of how I proceeded: Imagine a point in the process of drawing cards, one at a time, from a shuffled deck, and for which no pair has yet appeared. You can provide all the information you need for the analysis with just six (actually five) numbers:
*Number of ranks with four undrawn cards
*Number of ranks with three undrawn cards
*Number of ranks with two undrawn cards
*Number of ranks with one undrawn cards
*Number of ranks with zero undrawn cards
{Since these first five numbers must add up to thirteen, the fifth is unnecessary, but I'm including it for clarity}
*Number of remaining cards which match the most-recently drawn card.

Let's represent the contents of the cards yet to be drawn as the first five numbers separated by periods, with an asterisk following the group corresponding to the number of cards matching the most recently drawn card. For example, 9.2*.1.1.0 means there are nine ranks where all four cards have yet to be drawn; two ranks with three cards yet to be drawn, one of which is also the rank of the most recently drawn card; one rank with two cards yet to be drawn; one rank with one card yet to be drawn; and no ranks for which all four cards have been drawn already. Thus, there are currently 9*4+2*3+1*2+1*1=45 cards which have not been drawn yet.

Representing the deck in this way, we have all the information we need to determine a) the probability of the next drawn card matching the last drawn card; and b) if it doesn't match, the probabilities of proceeding to each possible next state.

Thus, from the initial state 13.0.0.0.0, (no asterisk since no card has been drawn yet), we proceed to 12.1*.0.0.0 with probability 1.

Given 12.1*.0.0.0, we get a pair with probability 3/51, and proceed to 11.2*.0.0.0 with probability 48/51.

Given 11.2*.0.0.0, we get a pair with probability 3/50; get to 11.1.1*.0.0 with probability 3/50; and get to 10.3*.0.0.0 with probability 44/50. Since the probability of getting to 11.2*.0.0.0 in the first place was 48/51, that means the overall probability of reaching 11.1.1*.0.0 is (48/51)*(3/50) = 144/2550. And the overall probability of reaching 10.3*.0.0.0 is (48/51)*(44/50) = 2112/2550. The probability of getting to 11.2*.0.0.0 and then getting a pair with the next card draw is (48/51)*(3/50) = 144/2550. The total probability of getting a pair within the first three cards is 3/51+144/2550 = 194/2550.

And so forth. (It gets a bit more complicated later on, as some of the states can be reached by more than one pathway. You just have to add together the probabilities of reaching that state via each individual pathway.)

When we represent the undrawn cards in this way, it turns out that we have "only" 7263 states that have to be considered. After a few hours in Excel, I've come up with 0.954523718 as the probability of having at least one pair. That is, the probability of reaching the final state 0.0.0.0.13* (i.e., no pairs) is 0.045476282. Subject to roundoff errors in Excel, etc.

So while not an exact answer, blue mustard's 1-(48/51)^51 is pretty darn close.
posted by DevilsAdvocate at 1:26 PM on November 17, 2006

The total probability of getting a pair within the first three cards is 3/51+144/2550 = 194/2550.

Er, 294/2550, that is.
posted by DevilsAdvocate at 1:32 PM on November 17, 2006

That's amazing. Not that the probability of a pair is so high, but that treating deals as dependent or independent yields such similar answers. Is that typical when we have large numbers of possible outcomes and a large variety of "successful" outcomes?
posted by nickmark at 1:44 PM on November 17, 2006

As you may have noticed, blue mustard's calculation matches the three monte carlo simulations, to within three decimal places in one case.

Blue mustard's approximation becomes correct as the number of cards in the deck gets larger. The approximation is poor for a deck of four cards but is very good for a deck of 52 cards. The reason for this is that the pairs become more like independent probabilities as the size of the deck grows. If you had an infinite deck they would be truely independent.
posted by JackFlash at 1:55 PM on November 17, 2006

The current state of my Monte Carlo simulation is:

# trials -------- probability
105690000 0.9545190652
105700000 0.9545192242
105710000 0.9545194211
105720000 0.9545196084

I don't have error bars, but the simulation is converging somewhere between 0.95451 and 0.95453.

That's in good agreement with DevilsAdvocate's 0.95452..., and contradicts blue mustard's 1-(48/51)^51) = 0.95458...

[Of course, my random numbers may be bad etc etc.]
posted by beniamino at 1:55 PM on November 17, 2006

whats the probability of turning up the first card, and then finding a pair in the deck that matches the value of the first card? i think it is around 0.04
posted by edtut at 2:28 AM on November 18, 2006

whats the probability of turning up the first card, and then finding a pair in the deck that matches the value of the first card?

That's quite a bit easier than the original question. Although a bit of clarification is required: if the second card matches the first, are you counting that as a pair? Or do you mean there must be a consecutive pair which matches the value of the first card within the remaining 51 cards?

There are 51C3 = 20825 ways for the three cards matching the first card to be arranged within the 51 cards. Of these, 50P2-49 = 2401 ways such that at least two of those three are consecutive. (Consider condensing the "pair" to a single card, and you now essentially have 2 different cards arranged among 50--unless the three cards are all consecutive (49 ways)--which you've just counted twice.) So if the second card matching the first, in and of itself, does not constitute a pair, the probability of a pair whose value matches the first card is 2401/20825 = 49/425 = ~0.115.

If the second card matching the first does count as a pair, there's an additional 49C2-48 = 1128 ways for that to happen (excluding any with other pairs also present, since we already counted those). So in that case the probability of a pair matching the initial card is 3529/20825 = ~0.169.
posted by DevilsAdvocate at 10:44 AM on November 20, 2006