Friday, June 24, 2011

Probability Assignments Using Set

I'm gearing up for teaching my graduate course on randomized algorithms and probabilistic analysis next semester.  It's been a while since I've taught it, and I'm somewhat uncertain what to do with the course, precisely since I wrote the textbook.  Me lecturing from the textbook is boring, both for me and for them, but of course the textbook contains exactly what I think is important.

Somehow I'll have to have them read the textbook offline and try to do more online learning in class.  I'm working through creating some programming exercises based on the game Set. (Amazon picture below.)

Set is a great card came (wikipedia entry, or the Set web site).  As it says in Wikipedia, "The deck consists of 81 cards varying in four features: number (one, two, or three); symbol (diamond, squiggle, oval); shading (solid, striped, or open); and color (red, green, or purple)."  You turn over 12 cards, and look for a set, which is three cards so that for each feature, EITHER all cards are the same in that feature, or they are different.  So below is an example of a set.  (different in each feature).  If they cards were all green, it would still be a set -- they can be all the same in some features, and all the same in others, and still be a set. 

The first player to find a set picks it up, and replacement cards are dealt in to get you back to 12 cards. The player with the most cards at the end of the game wins. My eldest had already seen the game in school, and after a few months, she and I now are pretty competitively matched. I'd put it up there with Mastermind as a good mental exercise game for kids. 

So the reason I thought about Set for my class is that the game instructions say that the odds of not getting a set with 12 cards dealt out is 33 to 1.  (When this happens, or you can't find one, you can deal another card out;  with 15 cards, the claim is more than 2500:1.)  But when you play the game, it seems you don't find a set much more often.  While my daughters and I are probably missing some sets some of the time, it's also clear that conditional probability is coming into play here.  At any point in the game, there aren't 12 random cards on the table.  Most clearly, suppose I deal 12 cards, find a set, and replace the 3 cards.  What's left isn't 12 random cards;  it's 9 cards left after a set was removed, and 3 cards remaining from the deck.** 

This seems like a nice way to introduce conditional probability in a concrete but perhaps subtle way.  And it seems like there are plenty of other related questions one can ask as well.  (What's the probability of not finding a set on the kth turn, given a set has been found in the first k-1 turns...)  Feel free to suggest exercises.  (Apparently the largest number of cards without a set is 20.  I wonder if there's a short proof of that without just doing exhaustive search.)

At the very least, it will be a good excuse to get a couple of boxes of Set for the office.

Have to go.  My daughter just asked to play a game of Set... 

** Of course I'm not the first to have noticed this.  Peter Norvig posted on it as well


Anonymous said...

One exercise that might be useful as an example to drive home your "cards left on the table not random" point:

Show that if 26 sets have been removed, and that there are 3 cards left on the table, those remaining 3 cards *always* form a set.

Andy D said...

What's your model of which sets are removed by players? It wouldn't be a random set from those present, since some are harder to see. Does the kind of set you grab affect the conditional probabilities you mention?

For a given set of players, you could probably build a decent probability model for which sets they'll find; just gather data by having them play the computer version.

Michael Mitzenmacher said...

Hey Andy -- stop giving away parts of the assignment they're supposed to think about!

Though to the first order my model would be when multiple sets can be taken a random one is selected. Maybe a better model is to sort so that sets that are similar in more features have priority over sets that are different in more features. I don't think I care about that level of detail for the assignment, except to the extent they should be thinking about the underlying model assumptions and questioning them.

Unknown said...

"Apparently the largest number of cards without a set is 20. I wonder if there's a short proof of that without just doing exhaustive search."

Yes: Davis and Maclagan. The card game Set. The Mathematical Intelligencer, 25, No. 3, 2003, 33-40.

One might also think about the computational complexity of set.

Anonymous said...

Can I say that the degree of achieving a conditional statement (if x
then y) is equivalent to a conditional probability p(y|x)?

Henrik Warne said...

Through simulations similar to Peter Norvig’s, I found that the odds against there being no set in 12 cards when playing a game of Set start off at 30:1 for the first round. Then they quickly fall, and after about the 4:th round they are 14:1 and for the next 20 rounds they slowly fall towards 13:1. So for most of the rounds played, the odds are between 14:1 and 13:1.

Also, it turns out that for the probabilities it doesn’t matter much if a “most similar” set is picked, or if a random set is picked. See Set Probabilities Revisited for more details.