Top Chef Mathematics
If you like food, Washington DC, hubris, or reality television, then chances are you are a fan of Bravo's cooking competition Top Chef. Every year the show takes a group of aspiring chefs, places them in a house in a new city, and throws weekly challenges their way. Following the Survivor template, every week one chef is voted off, and at the end someone is crowned Top Chef (and given a large check). This season, the action takes place in our nation's capitol.
Now, a show such as this might seem to have very little to do with mathematics. But look, and ye shall find. In the second episode of this past season, the chefs were paired up for one of the challenges. There were 16 chefs at the time, combining to make 8 pairs. The pairing was determined by drawing knives: 16 knives were presented in a knife block, and each had a number on it from 1 to 8. The number was printed on the blade, so each chef would walk to the block, draw a knife, and read the number. The knives were not replaced afterwards. Pairs were formed by people who drew the same number.
This dude loves the number 3.
In this particular episode, the first six numbers drawn were 2, 1, 3, 6, 7, and 7. In particular, the first pair was formed on the 6th draw. This leads to a natural question: how long would you expect it to take before the first pair is formed? Six draws seemed a bit long to me (I would have expected the first pair to have been formed sooner), so I immediately set about trying to understand the answer to this question.
To ease ourselves into it, let's simplify things. Instead of 8 pairs, suppose there were only 3. And instead of knives, which are dangerous and pointy, let's suppose people were choosing balls from a bag. Rather than differentiating the balls by writing numbers on them, let's differentiate them by color. So suppose you have a bag with 3 pairs of balls: one pair red, one pair green, and one pair blue.
The game is this: you draw a ball from a bag and put it aside. You keep doing this until you have drawn a pair. The question is how long it will take before the first pair is drawn.
Right away we see that you will get a pair some time between your second and your fourth draw. Obviously you can't get a pair after only drawing one ball, so you need a minimum of two draws. On the other hand, if you don't have a pair after drawing three, you must have one ball of each color, which means your fourth draw MUST give you a pair of some color.
Given this observation, we can now start to calculate probabilities. What is the probability that you will have a pair after two draws? Well, this happens precisely when your first and second draw are the same color. The probability of this happening is equal to 1/5, since there is no restriction on the first ball you draw, but then there is a 1 in 5 chance that the second one you draw will be the other ball with the same color.
You have a 1 in 5 chance of picking the second green ball after picking the first one, for example.
What about the probability that you'll have a pair after exactly three draws? In order for this to happen, your second draw must be a different color than the first, and your third draw must be the same color as either your first or second draw. Of the 5 balls remaining after your first draw, 4 will have a different color from the first, meaning that the probability of drawing a second ball which is a different color than the first is 4/5. Similarly, the probability of drawing a third ball which is the same color as either the first or the second ball is 1/2 (see the picture below). Thus, by the laws of conditional probability, the odds that you will have a pair after your third draw is 4/5 × 1/2 = 2/5.
You have a 2 in 4 (i.e. 1 in 2) chance of pulling a blue or green ball given that the results of your first two draws were blue and green, for example.
The same argument works when calculating the odds that the pair will come on the fourth draw. There is no restriction on the first draw, there is a 4/5 chance that your second draw will be a different color from the first, there is a 1/2 chance that the third draw will be a different color from the second, and there is then a 100% chance that your fourth draw will be the same color as one of your earlier draws. This again gives a probability of 2/5. We see that the probabilities add up to one, as they should.
Given these probabilities we can also calculate the expected value: on average, how many draws will you need before you get a pair? Since the probability of two draws is 1/5, the probability of three draws is 2/5, and the probability of four draws is 4/5, we see that the average is
2 × 1/5 + 3 × 2/5 + 4 × 2/5 = 16/5 = 3.2.
In other words, on average you will need 3.2 draws before you come up with a pair.
It's more interesting, of course, to deal with c different colors, rather than just 3. We can still perform this analysis, and try to find probabilities and expectations. Suppose we have c pairs of balls, each pair of a different color. We draw the balls without replacement from a bag until we find a pair of the same color, then we stop. We can define a random variable Yc to be the draw on which we complete our first pair. For example, in the case c = 3 above, we saw that Y3 = 2 with probability 1/5, Y3 = 3 with probability 2/5, and Y3 = 4 with probability 2/5.
As before, notice that Yc must take a value between 2 and c + 1. This is because we can't draw a pair before our 2nd draw, and after c draws, the worst case scenario is for us to have each ball of a different color. Since we have exhausted all color possibilities, the (c + 1)st draw must give us a pair (in essence we are applying the Pigeonhole Principle). So, to describe the behavior of Yc we need to calculate the probability that Yc = k for k between 2 and c + 1.
The same sort of argument as in the simple case c = 3 works here. Suppose you want to calculate P(Yc = k). In order to find your first pair on the kth draw, you need to NOT draw a pair on your 2nd, 3rd, 4th, ..., or (k - 1)st draw, and then have the color on the kth draw match one of the colors you have already drawn. Since there are a total of 2c balls in the bag to begin with, we see that the odds of not drawing a pair on the 2nd draw is , the odds of not drawing a pair on the 3rd draw is (since there are 2c - 2 balls remaining, and you want to avoid 2 that are colors you've already drawn, leaving you with 2c - 2 - 2 = 2c - 4 options), and so on, so that the odds of not getting a pair on the (k - 1)st draw is . Meanwhile, in order to draw a pair on your kth draw, you must pull one of the k - 1 colors that have already been pulled. Since there are 2c - k + 1 balls remaining, the probability that this happens is .
Combining these, we see that
(Recall that the binomial coefficient is given by , and as usual n! = n × (n – 1) × ... 3 × 2 × 1 is the product of all integers from 1 to n.) With this formula, we can now see how likely it was for the first pairing on Top Chef to have occurred on or after the 6th draw. In this case there are 8 pairs, so c = 8, and we see that
which comes out to 16/39, or roughly 41.03%.
Of course, there's still the question of expectation: approximately how large do we expect Yc to be (remember we saw that E(Y3) = 16/5)? I'll spare you the details, but one can show that for general c, the expected value is given by
In particular, in the case c = 8 from Top Chef, we find that $latex E(Y3) = 32768/6435, which is approximately 5.09. So on average, for c = 8 we expect to find a pair after a little more than 5 draws.
For the more advanced reader, one final question: what happens to the expected value as c grows large? As it turns out, we can write the expected value in a very nice form in terms of the Gamma function (which one can think of as a generalization of the factorial to the entire real line). Using the doubling formula , the interested reader can show that
If one then uses Stirling's formula to approximate the Gamma function, it follows that
in other words as . What a wonderful asymptotic! This tells us that the number of draws we will need from a bag of c pairs before obtaining our first pair grows like the square root of c times a factor of . We can compare the estimate given here for E(Y8) with the exact value computed above – in doing so, we find that . So indeed, the approximation is fairly close to the true value (and the approximation will only get better as c grows).
There are many related questions one could ask. For example, what if instead of pairs, we look at collections of triplets, or quadruplets? What if we consider formation of the 2nd pair or 3rd pair instead of only considering the 1st pair? What if we allow for different numbers of balls of each color (e.g. 2 red balls and 3 green balls)? But I've already gone on too long, so I will leave these questions for another time. I don't know if these questions go by a certain name or not - I couldn't find this particular problem anywhere. If anyone knows of a paper or book where these problems are discussed, I would be much obliged.
In the mean time, I will close with a picture of Tom Colicchio looking like a badass. Clearly the worlds of chefs and rock stars have collided - will mathematicians be next?
(Kudos to Dr. Moore for some helpful commentary.)
Psst ... did you know I have a brand new website full of interactive stories? You can check it out here!
comments powered by Disqus