Tag probability

Sharing Nassim Taleb’s dart probability problem with kids

Last week Nassim Taleb posted a fun probability problem on Twitter:

I “live blogged” my work on this problem at the link below and eventually found the solution (though after a long detour):

Sort of live blogging a solution to a problem posed by Nassim Taleb

One of the boys had to leave early this morning for a school event, so I was looking for a quick project. With some of the work I did in Mathematica on Taleb’s problem still up on my computer screen, I decided to run through the problem with the boys. The point here wasn’t for them to figure out the solution, but rather to see a neat example of counting techniques used to solve a challenging problem.

I started by explaining the problem and asking them to take a guess at the answer. The boys also had some interesting thoughts about the probability of the balls all ending up in different boxes.

Next we went to Mathematica to walk through my approach to solving the problem. In talking through my approach these ideas from number theory and combinatorics come up:

(1) Partitions of an integer,
(2) Binomial coefficients,
(3) Complimentary counting,
(4) Permutations and combinations, and
(5) Correcting for over counting.

Here’s our quick talk through one solution to Taleb’s problem (and, again, this isn’t intended as a “discovery” exercise, rather we are just walking through my solution) :

To wrap up we returned to the idea of the balls spreading out completely -> a maximum of 1 ball per box. Both boys thought this case was pretty likely and were pretty surprised to find it was less likely than ending up with 3 or more balls in a box!

This problem is little bit on the advanced side for 8th and 6th graders to solve on their own, but they can still understand the ideas in the solution. Also, there are some fun surprises in this problem – the chance of the balls spreading out completely was much lower than they thought, for example – so I think despite being a bit advanced, it is a fun problem to share with kids.

Advertisements

Sort of live blogging a solution to a problem posed by Nassim Taleb

This morning Nassim Taleb posed this problem on Twitter:

A later tweet clarified that the problem was asking for “at least 3.”

I wanted to write up my solution because I think that it is important to share the thought process rather than just the answer to a question. I’ve written up solutions to similar problems before and was originally inspired to write posts like this one after seeing Tim Gowers “live blog” a solution to an IMO problem.

A couple of notes to be clear:

(Edit) (0) Make sure to read all the way to the bottom as I now have corrected a counting mistake

(1) I’m not sure this solution is correct (EDIT – with the final correction at the bottom I am now much more confident),

(2) Incredibly, two keyboards broke while typing up this post, so sorry if there are typos. It is a miracle that the latex formulas work.

Anyway . . .

I understood the problem to be the same question as this one:

You have 8 balls and 16 boxes numbered 1 through 16. For each ball you select a box uniformly at random and place the ball in the selected box. After placing the 8th ball in one of the boxes, what is the probability that at least one box contains at least 3 balls.

My first inclination was to do a quick back of the envelope calculation using the Poisson and Binomial distributions:

FirstTry

So, assuming a Poisson distribution for the number of balls in each box (with expected value 1/2), the probability of 3 or more balls in a box is about 1.44%. The probability that no boxes have 3 is (1 – 0.0143877)^16 which is about 80%. So the probability of at least one box having 3 or more balls would be around 20%.

The same calculation assuming a binomial distribution with 8 balls having a 1/16 chance of going in a box leads to a guess of around 16% for the probability of a box having at least 3 balls.

I knew that neither of these approaches was correct, but I thought that starting this way would give me a sense of what the right answer would be.

Next I asked how many different ways there were to put 8 balls into 16 boxes. This question is a classic “stars and bars” question from combinatorics. The answer is 23 \choose 8 which is 490,314.

So, how can I makes sense of these 490,314 different ways to put the balls in the boxes?

My first thought here was to look at the partitions of 8, since no matter how the balls are distributed, the sum of the number of balls in each box has to be 8. Turns out there are 22 ways to partition 8:

Mathematica2

Since there are only 5 partitions with only 2’s and 1’s, I figured I’d just count the different ways that those partitions could occur in the 16 boxes.

So, for example:

(1) [1,1,1,1,1,1,1,1] can occur in 16 \choose 8 = 12,870 ways

(2) [2,1,1,1,1,1,1] can occur in 16 \choose 1 * 15 \choose 6 = 80,080 ways

The full calculations for the partitions with only 2’s and 1’s and the ones that include numbers 3 or greater are here:

Mathematica3

So, I had to check these calculations a bunch of times since the ones we want to exclude add up to only 258,570 out of 490,314 -> not even close to 80%. But, checking and checking and checking kept getting me to the same answer.

The total ways to distribute the balls in ways that at least one box gets 3 or more balls is 231,744, and thus the probability of a box getting at least 3 balls is 231,744 / 490,314 which is roughly 47.3%. This probability is much higher than I would have guessed.

Later I saw this follow up tweet from Taleb:

Taleb2

I spent the rest of the day trying to come up with a better formulation, but really was not that successful. The best I could come up with was a formulation using generating functions.

The total number of ways to distribute the 8 balls into 16 boxes is given by the coefficient of x^8 in the polynomial:

(1 + x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7 + x^8)^{16}

Luckily that number is 490,314.

Similarly, the total number of ways to distribute the 8 balls into 16 boxes with at most 2 balls per box is given by the coefficient of x^8 in the polynomial:

(1 + x + x^2)^{16}

and that number is also what we found above -> 258,570.

Math4.jpg

So, we get the same answer as above.

The generating function approach also gives a way to solve the general problem in the second part of Taleb’s tweet. We’d just look at the coefficients of x^n in these two polynomials:

(1 + x + x^2 + x^3 +\ldots + x^{n-1} + x^n)^{d}, and

(1 + x + x^2 + x^3 +\ldots + x^{m-2} + x^{m-1})^{d}.

Then do the same calculation as above.

However, although this approach with generating functions is easy to describe, it really isn’t much easier to calculate, so I doubt it was the reformulation that Taleb had in mind.

(EDIT that goes from here to the end)

[I’ve had to steal a keyboard from my son since one broken keyboard doesn’t type symbols like $, [], and {} making latex formulas impossible and the other doesn’t type the letter t. 4:00 am problems!]

At 4:00 am I woke up and realized an error in the approach. By that time there were a few comments on twitter also pointing out the under counting.

the error in counting comes in assuming the each distribution of balls coming from a partition of 8 is equally likely. That’s not the case. The distribution [1,1,1,1,1,1,1,1] can indeed occur in 16 \choose 8 ways, but there are also 8! (8 factorial, I mean, in case it displays incorrectly) arrangements for each of those ways.

However, the distribution [2,1,1,1,1,1,1] which occurs in 16 \choose 1 * 15 \choose 6 has 8! / 2! different arrangements.

So, factoring in that under counting leads to the following correct count for the cases with only 1’s and 2’s:

Mathematica5.jpg

The 3,567,874,400 cases are out of a total of 16^8 cases and thus the probability of having a 3 in more than one box is given by:

Math6

So, the result is (happily) closer to the back of the envelope result that’d get and I don’t have to worry that the Poisson / Binomial approximations are way off!

Now, back to bed 🙂

Sharing Tim Gowers’s nontransitive dice talk with kids

During the week I attending a neat talk at Harvard given by Tim Gowers. The talk was about a intransitive dice. Not all of the details in the talk are accessible to kids, but many of the ideas are. After the talk I wrote down some ideas to share and sort of a sketch of a project:

Thinking about how to share Tim Gowers’s talk on intransitive dice with kids

One of the Gowers’s blog posts about intransitive dice is here if you want to see some of the original discussion of the problem:

One of Tim Gowers’s blog posts on intransitive dice

We started the project today by reviewing some basic ideas about intransitive dice. After that I explaine some of the conditions that Gowers imposed on the dice to make the ideas about intransitive dice a little easier to study:

The next thing we talked about was 4-sided dice. There are five 4-sided dice meeting Gowers’s criteria. I thought that a good initial project for kids would be finding these 5 dice.

Now that we had the five 4-sided dice, I had the kids choose some of the dice and see which one would win against the other one. This was an accessible exercise, too. Slightly unluckily they chose dice that tied each other, but it was still good to go through the task.

Now we moved to the computer. I wrote some simple code to study 4-sided through 9-sided dice. Here we looked at the 4-sided dice. Although it took a moment for the kids to understand the output of the code, once they did they began to notice a few patterns and had some new ideas about what was going on.

Having understood more what was going on with 4-sided dice, we moved on to looking at 6-sided dice. Here we began to see that it is actually pretty hard to guess ahead of time which dice are going to perform well.

Finally we looked at the output of the program for the 9-sided dice. It is pretty neat to see the distribution of outcomes.

There are definitely ideas about nontransitive dice that are accessible to kids. I would love to spend more time thinking through some of the ideas here and find more ways for kids to explore them.

Exploring Elchanan Mossel’s fantastic probability problem with kids

Saw a really great problem via a Lior Patcher tweet:

Here’s the problem:

You throw a dice until you get 6. What is the expected number of throws (including the throw giving 6) conditioned on the event that
all throws gave even numbers.

Here are direct links to Kalai’s two blog posts on the problem:

Gil Kalai’s “TYI 30: Expected number of dice rolls

Gil Kalai’s follow up post: Elchanan Mossel’s Amazing Dice Paradox (Your Answers to TYI 30)

It is fun to click through to the first Kalai blog post linked above to cast your vote for the answer if you haven’t seen the problem before.

We actually started the project today by doing that:

Next we rolled some 6-sided dice to see how this game worked. I note seeing the video that a few of the rolls went off camera, sorry about that 🙂

At the end we discussed what we saw and why what we found was a little surprising.

The next part of the project was having the boys play the game off camera until they found 5 rolls meeting the criteria.

After this exercise the boys started to gain some confidence that the answer to the problem was 3/2.

Now I walked them through what I think is the easiest solution to understand. It comes from a comment on the first Gil Kalai’s blog post linked above:

ProbabilityComment

Listening to this discussion now, I wish I would have done a better job explaining this particular solution. Still, I hope the discussion is instructive.

Finally, we went to Mathematica to evaluation the sum from the last video and then to explore the problem via a short program I wrote.

At the end of this video the boys some up their thoughts on the problem.

I love this problem. It isn’t that often I run across a clever problem that is interesting for both professional mathematicians and kids. Those problems are absolute

Playing with Jim Propp’s essay on Arthur Engel

Jim Propp’s August 2017 blog post is absolutely terrific:

Prof. Engel’s Marvelously Improbably Machines

Even though we are visiting my parents in Omaha, I couldn’t resist having the boys watch the video in the essay and then play with the challenge problem.

Here’s what they thought after watching the video – the nice thing is that they were able to understand the problem Propp was discussing [also, I shot these videos with my phone, so they probably don’t have quote the quality or stability of our usual math videos]:

Next I had them play the game that Propp explained in his video. The idea here was to make sure that they understood how the [amazing!] solution to the problem shown in the video:

Next we tried the challenge problem from the essay. I almost didn’t do this part of the project, but I’m glad I did. It turned out that there were a few ideas in the Propp’s video that the boys thought they understood but there was a bit more explanation required. Once they got past those small stumbling blocks, they were able to solve the problem.

I’m really excited to dive a little deeper into the method of solving probability problems that Propp explains in his essay. What makes me the most excited is that the method came from someone thinking about how to explain probability to kids.

The last video shows that understanding Engel’s method does take a little time. Once kids get the general idea, though, I think they’ll find that applying to a wide variety of problems is pretty easy. It is amazing how such a simple method can made fairly complex probability problems accessible to kids.

Talking a bit more about my son’s probability problem

Yesterday we did a fun project on a probability problem / game my son was working on. The game involves rolling three 10-sided dice and adding up the numbers. Repeat the process until you’ve seen one of the sums 40 times. Yesterday 15 was the winner:

img_2432

Here’s yesterday’s project:

A probability and stats problem with dice my younger son was working on today

I wrote a short program on Mathematica to play my son’s game 1,000,000 times. I was interested to see how each of the boys would interpret the results.

Here’s what my older son had to say:

Here’s what my younger son had to say:

It is interesting to hear what kids have to say about the various probabilities and distributions. The results of the 1,000,000 simulations are probably pretty surprising. This problem that my son made up is actually a pretty fun problem to explore with kids.

A probability and stats problem with dice my younger son was working on today

When I got up this morning my younger son was playing some sort of dice game in the kitchen. An hour later he was still rolling dice so I finally asked him what he was doing:

It turns out what he was actually trying to was find the first sum that would appear 40 times, but I only understood that later.

This seemed like an easy activity to turn into a project, so we got started by having him explain what he was doing:

Next we turned to Mathematica to play around a little bit with the problem. I had to explain some terms first (and sorry I had part of the screen out of view for a bit). After explaining those terms we looked at the distribution of the sums:

Finally we wrapped up by taking a very deep dive into the distribution of the sum of three 10 sided dice. The kids were able to understand the probability of getting a 3 or a 30, and then we talked about a few of the other probabilities that Mathematica was showing us.

Later in the morning my son finished his game. 15 was the first roll to appear 40 times.

It was really fun to base a project on a math problem that my son came up with on his own.

The “Dungeons and Dragons” problem

My kids have suddenly been drawn into D&D. They are having a ton of fun with it and I thought that there was at least one fun little math problem we could talk through that related to the game.

At the start of the game you create a character with various properties. To determine the value of some (maybe all) of those properties you roll four 6-sided dice and add up the three highest numbers.

The question we looked at today was what is the expected value of that sum?

First we introduced the problem and come up with a few ideas about what the answer might be.

Next we did 10 trials to see what average we’d find:

Now we had a longish talk about how you might solve the problem. The boys jumped to a computer simulation pretty quickly. After talking about how that simulation would work we talked about how to solve a similar problem with two dice.

Finally, we did go the computer to see what the answer would be. Talking about how to write the program was pretty fun.

Nice project – I might revisit this one to talk through the geometry of the solution of the 2 and 3 dice problem and see if the boys can figure out how to generalize to the 4 dice case.

The coupon collection problem with kids

Yesterday my younger son was playing a dice game (explained in the first video) that reminded me a bit of the coupon collection problem. I thought it would be fun to try out that problem with the boys this morning. We were a little low energy, but I think it was still a good project. I’ll have to figure out how to revisit it to make sure the points stuck.

Here’s the introduction, including the game my son was playing:

Next we worked through one case of the problem – rolling dice trying to collect 6 “coupons”. My older son thought it would take 15 rolls and my younger son thought it was take 20.

Now I tried to help the kids dive into the math. We ended up going down a path that was much more complicated than I intended. I’m not sure why I made the choice that I did here, but . . . it happens sometimes 🙂

So, at the end of the last video we were caught in a seemingly complicated infinite series. I tried to explain why the expression we had on the board had to be equal to one. Then I tried to explain why the expected number of rolls had to be greater than one. The explanation here is a disaster, though.

Now that things had gone totally off the rails, I tried to pull it back. Luckily things did go better, and it was easier for the boys to see the expected number of rolls when there were fewer open slots.

Finally I wanted to show the kids how the ideas we talked about here would apply to a more difficult problem – say 100 coupons. We got off on the wrong foot here, but we eventually saw how the ideas we’d talked about previously applied.

Despite the low energy and going doing a path that was a bit too complicated, I think this is a fun problem for kids to study. It looks very difficult initially, but through a bit of calculation (and maybe a bit of hand waving) we can break it down into some smaller problems that we are able to solve. Putting the solutions of those smaller problems together, we can show that the solution to the original coupon collection problem isn’t too hard to understand.

e

Connecting yesterday’s probability project with a few old 3d geometry projects

In yesterday’s project we were studying a fun probability question posed by Alexander Bogomolny:

That project is here:

Working through an Alexander Bogomolny probability problem with kids

While writing up the project, I noticed that I had misunderstood one of the
geometry ideas that my older son had mentioned. That was a shame because his idea was actually much better than the one I heard, and it connected to several projects that we’ve done in the past:

Paula

 

Learning 3d geometry with Paula Beardell Krieg’s Pyrmaids

Revisiting an old James Tanton / James Key Pyramid project

Overnight I printed the pieces we needed to explore my son’s approach to solving the problem and we revisited the problem again this morning. You’ll need to go to yesterday’s project to see what leads up to the point where we start, but the short story is that we are trying to find the volume of one piece of a shape that looks like a cube with a hole in it (I briefly show the two relevant shapes at the end of the video below):

Next we used my son’s division of the shape to find the volume. The calculation is easier (and more natural geometrically, I think) than what we did yesterday.

It is always really fun to have prior projects connect with a current one. It is also pretty amazing to find yet another project where these little pyramids show up!