{"id":430,"date":"2012-03-10T21:10:12","date_gmt":"2012-03-11T03:10:12","guid":{"rendered":"http:\/\/linesoftangency.wordpress.com\/?p=430"},"modified":"2012-03-10T21:10:12","modified_gmt":"2012-03-11T03:10:12","slug":"cereal-boxes-redux","status":"publish","type":"post","link":"http:\/\/blog.chrislusto.com\/?p=430","title":{"rendered":"Cereal Boxes Redux"},"content":{"rendered":"

In my last post<\/a>, my students were wrestling with a question about cereal prizes.\u00a0 Namely, if there is one of three (uniformly distributed) prizes in every box, what's the probability that buying three boxes will result in my ending up with all three different prizes?\u00a0 Not so great, turns out.\u00a0 It's only 2\/9.\u00a0 Of course this raises another natural question: How many stupid freaking boxes do I have to buy in order to get all three prizes?<\/strong><\/p>\n

There's no answer, really.\u00a0 No number of boxes will mathematically guarantee<\/strong> my success.\u00a0 Just as I can theoretically flip a coin for as long as I'd like without ever getting tails, it's within the realm of possibility that no number of purchases will garner me all three prizes.\u00a0 But, just like the coin, students get the sense that it's extremely unlikely that you'd buy lots and lots of boxes without getting at least one of each prize.\u00a0 And they're right.\u00a0 So let's tweak the question a little: How many boxes do I have to buy on average<\/strong> in order to get all three prizes?\u00a0 That's more doable, at least experimentally.<\/p>\n

I have three sections of Advanced Algebra with 25 - 30 students apiece.\u00a0 I gave them all dice to simulate purchases and turned my classroom---for about ten minutes at least---into a mathematical sweatshop churning out Monte Carlo shopping sprees.\u00a0 The average numbers of purchases needed to acquire all prizes were 5.12<\/strong>, 5.00<\/strong>, and 5.42<\/strong>.\u00a0 How good are those estimates?<\/p>\n

\"\"<\/a>

Simulating cereal purchases with dice<\/p><\/div>\n

Here's my own simulation of 15,000 trials, generated in Python<\/a> and plotted in R<\/a>:<\/p>\n

\"\"<\/a><\/p>\n

I ended up with a mean of 5.498<\/strong> purchases<\/strong>, which is impressively close to the theoretical expected value of 5.5<\/strong>.\u00a0 So our little experiment wasn't too bad, especially since I'm positive there was a fair amount of miscounting, and precisely one die that's still MIA from excessively enthusiastic randomization.<\/p>\n

And now here's where I'm stuck.\u00a0 I can show my kids the simulation results.\u00a0 They have faith---even though we haven't formally talked about it yet---in the Law of Large Numbers<\/a>, and this will thoroughly convince them the answer is about 5.5.\u00a0 I can even tell them that the theoretical expected value is exactly<\/strong> 5.5.\u00a0 I can even<\/em> have them articulate that it will take them precisely one box to get the first new toy, and three boxes, on average, to get the last new toy (since the probability of getting it is 1\/3, they feel in their bones that they should have to buy an average of 3 boxes to get it).\u00a0 But I feel like we're still nowhere near justifying that the expected number of boxes for the second toy is 3\/2<\/strong>.<\/p>\n

For starters, a fair number of kids are still struggling with the idea that the expected value of a random variable doesn't have to be a value that the variable can actually attain<\/em>.\u00a0 I'm also not sure how to get at this next bit.\u00a0 The absolute certainty of getting a new prize in the first box is self-evident.\u00a0 The idea that, with a probability of success of 1\/3, it ought \"normally\" to take 3 tries to succeed is intuitive.\u00a0 But those just aren't enough data points to lead to the general conjecture (and truth) that, if the probability of success for a Bernoulli trial is p<\/em>, then the expected number of trials to succeed is <\/em>1\/p<\/em>.\u00a0 And that's exactly the fact we need to prove the theoretical solution.\u00a0 Really, that's what we need basically to solve the problem completely for any number of prizes.\u00a0 After that, it's straightforward:<\/p>\n

The probability of getting the first new prize is n\/n<\/em>.\u00a0 The probability of getting the second new prize is (n-1<\/em>)\/n<\/em> ... all the way down until we get the last new prize with probability 1\/n<\/em>.\u00a0 The expected numbers of boxes we need to get all those prizes are just the reciprocals of the probabilities, so we can add them all together...<\/p>\n

If X <\/em>is the number of boxes needed to get all n<\/em> prizes, then<\/p>\n

$latex E(X) = frac{n}{n} + frac{n}{n-1} + cdots + frac{n}{1} = n(frac{1}{n} + frac{1}{n-1} + cdots + frac{1}{1}) = n cdot H_n&s=2$<\/p>\n

where H<\/em>n<\/sub> is the n<\/em>th harmonic number<\/a>.\u00a0 Boom.<\/p>\n

Oh, but yeah, I'm stuck.
\n<\/em><\/em><\/em><\/p>\n","protected":false},"excerpt":{"rendered":"

In my last post, my students were wrestling with a question about cereal prizes.\u00a0 Namely, if there is one of three (uniformly distributed) prizes in every box, what's the probability that buying three boxes will result in my ending up with all three different prizes?\u00a0 Not so great, turns out.\u00a0 It's only 2\/9.\u00a0 Of course […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[2,3],"tags":[17,32,50,55],"class_list":["post-430","post","type-post","status-publish","format-standard","hentry","category-math-musing","category-math-teaching","tag-expected-value","tag-math","tag-simulations","tag-teaching"],"_links":{"self":[{"href":"http:\/\/blog.chrislusto.com\/index.php?rest_route=\/wp\/v2\/posts\/430","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/blog.chrislusto.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/blog.chrislusto.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/blog.chrislusto.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/blog.chrislusto.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=430"}],"version-history":[{"count":0,"href":"http:\/\/blog.chrislusto.com\/index.php?rest_route=\/wp\/v2\/posts\/430\/revisions"}],"wp:attachment":[{"href":"http:\/\/blog.chrislusto.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=430"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/blog.chrislusto.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=430"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/blog.chrislusto.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=430"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}