{"id":399,"date":"2012-03-07T16:25:51","date_gmt":"2012-03-07T22:25:51","guid":{"rendered":"http:\/\/linesoftangency.wordpress.com\/?p=399"},"modified":"2012-03-07T16:25:51","modified_gmt":"2012-03-07T22:25:51","slug":"pruning-tree-diagrams","status":"publish","type":"post","link":"http:\/\/blog.chrislusto.com\/?p=399","title":{"rendered":"Pruning Tree Diagrams"},"content":{"rendered":"

A few days ago we opened up with some group work surrounding the following problem.\u00a0 I gave no guidance other than, \"One representative will share your solution with the class.\"<\/p>\n

My favorite cereal has just announced that it's going to start including prizes in the box.\u00a0 There is one of three different prizes in every package.\u00a0 My mom, being cheap and largely unwilling to purchase the kind of cereal that has prizes in it, has agreed to buy me exactly three boxes.\u00a0 What is the probability that, at the end of opening the three boxes, I will have collected all three<\/strong> different prizes?<\/p><\/blockquote>\n

It's a very JV, training-wheels version of the coupon collector's problem<\/a>, but it's nice for a couple of reasons:<\/p>\n

    \n
  1. The actual coupon collector's problem is several years out of reach, but it's a goody, so why not introduce the basics of it?<\/li>\n
  2. There is a meaningful conversation to be had about independence<\/a>.\u00a0 (Does drawing a prize from Box 1 change the probabilities for Box 2?\u00a0 Truly?\u00a0 Appreciably?\u00a0 Is it okay to assume, for simplicity, that it doesn't?\u00a0 How many prizes need to be out there in the world for us to feel comfortable treating this thing as if it were a drawing with replacement<\/strong>?\u00a0 If everybody else is buying up cereal---and prizes---uniformly, does that bring things closer<\/strong> to true independence?\u00a0 farther away?<\/em>)<\/li>\n
  3. There are enough intuitive wrong answers to require some deeper discussion: e.g, 1\/3<\/strong> (Since all the probabilities along the way are 1\/3, shouldn't the final probability of success also be 1\/3?<\/em>), 1\/27<\/strong> (There are three chances of 1\/3 each, so I multiplied them together.<\/em>), and 1\/9<\/strong> (There are three shots at three prizes, so nine outcomes, and I want the one where I get all different toys.<\/em>)\u00a0 The correct answer, by the by, is 6\/27 or 2\/9<\/strong> (try it out).<\/li>\n<\/ol>\n

    Many groups jumped right into working with the raw numbers (see wrong answers above).\u00a0 A few tried, with varying levels of success, to list all the outcomes individually (interestingly, a lot of these groups correctly counted 27 possibilities, but then woefully miscounted the number of successes...hmmm).\u00a0 A small but determined handful of groups used tree diagrams<\/a> to help them reason about outcomes sequentially.<\/p>\n

    This business of using tree diagrams was pleasantly surprising.\u00a0 We hadn't yet introduced them in class, and I hadn't made any suggestions whatsoever about how to tackle the problem, so I thought it was nice to see a spark of recollection.\u00a0 That said, it's not terribly<\/em> surprising; presumably these kids have used them before.\u00a0 But I did run across one student, Z, who interpreted<\/strong> his tree diagram in novel way---to me at least.<\/p>\n

    Most students, when looking at a tree diagram, hunt for paths that meet the criteria for success.\u00a0 Here's a path where I get Prize 1, then Prize 2, then Prize 3.\u00a0 Here's another where I get Prize 1, then Prize 3, then Prize 2...\u00a0 <\/em>The algorithm goes something like, follow a path event-by-event and, if you ultimately arrive at the compound event of interest, tally up a success.\u00a0 Repeat until you're out of paths.\u00a0 That is, most students see each path as an stand-alone entity to be checked, and then either counted or ignored.<\/p>\n

    What Z did was different in three important ways.\u00a0 First of all, he found his solutions via subtraction rather than addition.\u00a0 Second, he attacked the problem in a very visual---almost geometric<\/strong>---way.\u00a0 And third, he didn't treat each path separately; rather, Z searched for equivalence classes of paths within the overall tree.<\/p>\n

    Z's (paraphrased) explanation goes as follows:<\/p>\n

    First I erased all of the straight paths, because they mean I get the same prize in every box.\u00a0 Then I erased all of the paths that were almost<\/em> straight, but had one segment that was crooked, which means I get two of the same prize.\u00a0 And then I was left with the paths that were the most<\/em> crooked, which means I get a different prize each time.<\/p><\/blockquote>\n

    Looking at his diagram, I noticed that Z hadn't even labeled the segments; he simply drew the three stages, with three possibilities at each node, and then deleted everything that wasn't maximally crooked.\u00a0 How awesome is that?\u00a0 In fact, taking this tack made it really easy for him to answer more complicated followup questions.\u00a0 Since he'd already considered the other cases, he could readily figure out the probability of getting three of the same prize (the 3<\/strong> branches he pruned first), or getting only two different prizes (the next 18 <\/strong>trimmings<\/em>).\u00a0 He could even quickly recognize the probability of getting the same prize twice in a row, followed by a different one (the 6<\/strong> branches he trimmed that went off in one direction, followed by a straight-crooked<\/strong> pattern).<\/p>\n

    [youtube=http:\/\/www.youtube.com\/watch?v=jfJb_afqA0M]<\/p>\n

    Of course this method isn't particularly efficient.\u00a0 He had to cut away 21 paths to get down to 6.\u00a0 For n<\/em> prizes and boxes, you end up pruning nn<\/sup> --- n!<\/em> branches.\u00a0 Since nn<\/sup><\/em> grows much, much faster, than n!<\/em>, Z's algorithm becomes prohibitively tedious in a hurry.\u00a0 If there are 5 prizes and 5 boxes, that's already 3005<\/strong> branches that need to be lopped off.\u00a0 So yes, it's inefficient, but then again so are tree diagrams.\u00a0 Without more sophisticated tools under his belt, that's not too shabby.\u00a0 What the algorithm lacks in computational efficiency, it makes up for in conceptual thoughtfulness.\u00a0 I'll take it that tradeoff any day of the week.<\/p>\n","protected":false},"excerpt":{"rendered":"

    A few days ago we opened up with some group work surrounding the following problem.\u00a0 I gave no guidance other than, \"One representative will share your solution with the class.\" My favorite cereal has just announced that it's going to start including prizes in the box.\u00a0 There is one of three different prizes in every […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3],"tags":[32,46,55,57],"class_list":["post-399","post","type-post","status-publish","format-standard","hentry","category-math-teaching","tag-math","tag-probability","tag-teaching","tag-tree-diagrams"],"_links":{"self":[{"href":"http:\/\/blog.chrislusto.com\/index.php?rest_route=\/wp\/v2\/posts\/399","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=399"}],"version-history":[{"count":0,"href":"http:\/\/blog.chrislusto.com\/index.php?rest_route=\/wp\/v2\/posts\/399\/revisions"}],"wp:attachment":[{"href":"http:\/\/blog.chrislusto.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=399"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/blog.chrislusto.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=399"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/blog.chrislusto.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=399"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}