## Sharing the ABRACADABRA problem with kids

Yesterday we did a fun project on Markov chains and sharing the “COVFEFE” problem with kids:

Sharing Markov chains and the “covfefe” problem with kids

For me math behind this problem was the most interesting math I learned in 2017:

The most interesting piece of math I learned in 2017 -> the “covfefe” problem

Today we moved on to a really neat surprise, and what makes the math behind this problem incredibly fun -> the “ABRACADABRA” problem.

First, we reviewed the ideas from yesterday:

After that review, we though through a few of the states and the transition probabilities in the new word. The transition probabilities are subtly different than in the “COVFEFE” problem:

Now we went to Mathematica to code in the ideas we discussed in part 2. We did about half of the coding on camera and did the other half off camera:

Finally, having finished the code we discussed what results we expected. I don’t see how anyone could get the right intuition here seeing the problem for the first time, so what do you expect here is almost an unfair question. Still, the boys had some nice ideas and then we checked out the results:

There are other approaches to these problems – the approach via Martingales, for example:

What that approach is also interesting (and incredible – you can solve the stopping time in your head!) I think the Markov chain approach is a bit more accessible to kidsd. Well . . . maybe because the math is buried in the background.

Anyway – super fun project, and an great piece of math to share with kids.

Advertisements

## Sharing Markov chains and the “COVFEFE” problem with kids

In 2017, the most interesting piece of math I learned can via Christopher Long and Nassim Taleb and related to the “COVFEFE” problem:

I wrote about the problem here:

The most interesting piece of math I learned in 2017 -> the “covfefe” problem

It turned out that we’ve looked at Markov chains before thanks to this great video from Kelsey Houston-Edwards:

Sharing Kelsey Houston-Edward’s Markov chain video with kids

I’d forgotten about that project, but when I mentioned to my younger son that we’d be looking at Markov chains today he told me he already knew about them!

So, I started today by having the boys watch the PBS Infinite Series video again. Here’s what they thought:

Next I introduced the “COVFEFE” problem. I was really happy how quickly the boys were able to pick up on how Markov chains could be used to solve this problem.

Next we looked at Nassim Taleb’s Mathematica code – that code is so clear that the problem becomes instantly accessible to kids, which is pretty amazing.

Finally, since things were going so well this morning, I introduced the word that we’ll study tomorrow -> ABRACADABRA. The kids were able to see why the transitions in this word were different. I’m excited to see how they think through the “ABRACADABRA” problem tomorrow!

The math behind this problem really was the most interesting math that I learned in 2017. It is really important math, too, and I’m excited that the Mathematica code makes some of the ideas accessible to kids. This was a fun one!

## The most interesting piece of math I learned in 2017 -> the COVFEFE problem

This question from a math exam in India was flying around math twitter last week:

I mistakenly thought the question was just sort of a fun joke and not all that interesting, but then I saw a series of tweets beginning with:

and ending with:

That last tweet was definitely a “wait . . . what??” moment for me.

Thinking about ABRACADABRA right off the bat was too hard, so I simplified the problem drastically too see what was going on. Suppose you are flipping a fair coin, what is the expected number of flips until you see the sequence H H? What about H T? These two problems are also, I think, great ways to introduce ideas about stopping time problems to kids. (the answers are 5 flips and 4 flips respectively).

Playing around with the easier problems showed me why the ABRACADABRA problem could have a longer stopping time than I would have guessed, but I couldn’t solve the problem exactly. Then I found this paper (written as part of an undergraduate research program at the University of Chicago!) which gave a wonderful explanation of the ABRACADABRA problem and (almost incredibly) a way to think about the problem that allows you to solve it in your head!

Martingale’s and the ABRACADABRA problem by Di Ai

After going through that paper I was happy to have learned some new ideas about stopping time problems and more or less moved on. But then one more nice surprise came from the COVFEFE problem when Nassim Taleb shared his Markov chain solution:

I’d never played with Markov chains in Mathematica (or, basically anywhere really) so I thought it would be fun to use what I learned from Taleb’s code to explore the ABRACADABRA problem. Working through that code gave me a much better understanding of Long’s “which states lead to which states” comment above. It took me a bit of time to realize, for example, that the state ABRA can move to the state AB, for example.

Again, copying Taleb’s code, here’s the transition matrix:

and the graph of the states plus the stopping time which matches 26^11 + 26^4 + 26:

It was fun to learn that the original COVFEFE problem was part of a class of problems that are much more subtle than they might seem at first glance. Learning about the connections to martingales and learning how to implement Markov chains in Mathematica was a really nice surprise, too.

## Revisiting non-transitive dice

We’ve done a few projects on non-transitive dice in the past:

Sharing Tim Gower’s non-transitive dice talk with kids

Non-Transitive Grime Dice

Today we’ve got some snow to shovel, so I was looking for a fairly light project this morning so we could get out the door to shovel. I grabbed our Grime dice off of the shelf and asked the kids to talk about them:

I asked the boys to pick two pairs of dice and test them to see which color would win. They worked independently and here’s how they explained what they found:

Finally, for a bit of a challenge, I had them work together to put the dice in a circular arrangement so that every color beat the one coming after it and lost to the one before it. This arrangement illustrates the seemingly odd non-transtive nature of these dice:

Although short, this was a fun exercise. These “Grime” dice are really fun for kids to play with!

## Revisiting card shuffling after seeing a talk by Persi Diaconis

Last week I took the boys to a talk given by Persi Diaconis at MIT:

Despite most of the talk going over their heads, the boys were really excited after the talk and had lots of different “shuffling” ideas that they wanted to explore.

Since this was going to be a long project, I divided it into two pieces – studying “pick up 52” with my younger son last night and studying shaking the cards in a box with both kids this morning.

The idea of using Shannon Entropy to study how random the shuffles are is something that we explored in these two prior projects:

Chard Shuffling and Shannon Entropy

Chard Shuffling and Shannon Entropy part 2

The original idea for those projects came from on an old Stackexchange post (well, the first comment) here:

See the first comment on this Stackexchange post

So, I kicked off the project last night with my younger son. Here are his thoughts about the Diaconis talk and about his “pick up 52” idea

We did 4 trials without re-sorting the cards in between. Here are some quick thoughts about how the deck was getting mixed up between the 2nd and 3rd throws:

After we finished I had my son do a few minutes of riffle shuffling to completely mix up the deck (starting from where the deck was after the 4th pick up 52). While he was doing that I entered the numbers from our throws into a spreadsheet.

The surprise was that even after the first throw the cards were really mixed up. I was even more surprised by this because he basically threw the deck in the air rather than what (to me anyway) is the normal way of throwing cards for pick up 52.

This morning we continued the project with my older son’s idea of putting the cards in a box and shaking the box. Here the introduction to that idea:

Here are some thoughts from my older son after the first mixing. He didn’t think they were all that mixed up. We did a total of 3 more mixings – the 3rd and 4th were off camera.

Finally, we wrapped up by reviewing the numbers for mixing the cards up in the box. The first mixing had more entropy than we thought, and after the 2nd mixing the cards appear to be pretty close to as mixed up as you can get (equivalent to about 10 riffle shuffles, I think).

This was a really fun project. The math you need to describe what’s going on here is much to advanced for kids (and worthy of a math lecture at MIT!), but kids can still have a lot of fun exploring some of the ideas. The seemingly simple idea of how can you measure how mixed up a shuffle is is a pretty interest idea all by itself.

## An instructive counting / probability question from Alexander Bogomolny

I saw this question from Alexander Bogomolny today through a tweet from Nassim Taleb:

It reminded me a bit of a fun question I saw from Christopher Long a few years ago:

A great introductory probability and stats problem I saw from Christopher Long

The first solution that came to mind for the dice question involved generating functions. Here’s the code I wrote in Mathematica:

The general idea was to look at powers of the polynomial $x + x^2 + x^3 + x^4 + x^5 + x^6$ and keep track of the coefficients for powers greater than $x^{12}$. The one tiny bit of difficulty is that you also have to strip off the powers of $x$ greater than $x^{12}$ after each stage (since you only want to count the first roll giving you a sum greater than 12). Here’s that polynomial cubed, for example:

The coefficients for $x^{13}$ through $x^{18}$ tell us the number of different ways to get a 13 through an 18 with three rolls.

The results of counting the polynomial coefficients are given below (columns give the number of ways to roll 13 through 18, and the rows are the dice rolls 3 through 13):

These counts don’t have the right weights, though, since 21 ways of getting a 13 on the 3rd roll have a much higher chance of happening than the 1 way of getting an 18 on the 13th roll. In fact each row has a weight 6x greater than the row immediately below it. Weighting the rows properly we get the following counts:

Now we just have to add up the columns and divide by $6^{13}$ to get the probabilities of ending on 13 through 18 (and do a weighted sum to get the expected final number) -> the probability of ending on a 13 is about 27.9% and the expected value of the final number is roughly 14.69:

This is a nice problem to show how generating functions can help you find exact answers to problems that seem to require simulations. It was fun to think through this one.

## 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.

## 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:

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:

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:

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:

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.

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:

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:

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:

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