Arthur Engel's abacus method of solving probability problems, applied to https://fivethirtyeight.com/features/... .

Welcome back to Barefoot Math.

Our topic today is Arthur Engel’s invention

of the probabilistic abacus.

When you hear the word "abacus", you probably picture

the Chinese-Japanese kind, with beads that slide on rods.

But there are also older, more primitive abacuses,

in which beads just get moved around on a board; no rods are involved.

That’s closer to the kind of abacus we’ll

be using today.

Back in the 1970s, the German mathematician and computer scientist Arthur Engel

was visiting the U.S. and looking for a way to teach probability theory to fourth graders.

He ended up creating something marvelous:

a way to design

custom abacuses that solve probability problems.

I’m going to dive in and show you how to

use Engel’s method to answer a question

that appeared in the blog FiveThirtyEight

on Sept. 9, 2016, as the week’s Riddler puzzle.

The problem was contributed by Bruce Torrence,

a math professor at Randolph Macon College.

Lots of people solved the problem, but as

far as I know I’m the only person

who solved it using Engel’s method.

Here’s the problem, slightly rephrased:

Eustace and four friends find a $100 bill

on the floor, and they decide to award it

randomly, winner take all.

The five of them sit around a table and play

a game in rounds.

During each round, one of three things can

happen, each of which has probability 1/3:

The bill can move one position clockwise,

or the bill can move one position counterclockwise,

or the game ends and the person with the bill

in front of him or her wins the money.

What are the chances that Eustace wins the

money if the bill starts out in front of him?

Part of what makes the problem tricky is that we can’t know ahead of time how long the game will last.

It’s incredibly unlikely that the game will

last a million rounds, but it’s possible,

and we’ll get the wrong answer if we neglect

that ever-so-unlikely possibility.

Nonetheless, the problem has a reasonable

answer: it’s 5/11, or just under a half.

But how can we derive this answer?

Let’s build an abacus for Torrence’s problem.

There are five places the money can be on

the table, and five people who can pocket

the money, so we create an abacus with ten

spots on it:

five inner spots representing where the money

is on the table (the green one corresponding

to the money being in front of Eustace) ——

ignore these chocolate chips for now! ——

and five outer spots representing who takes

the money home

(the red one corresponds to Eustace taking the money home).

We imagine a token (again, nothing to do with

these chocolate chips) that represents the

money and a three-sided die with sides marked

Clockwise, Counterclockwise, and Out,

telling us where to move the token.

(If you don’t have a three-sided die (and

I don’t), just use use a six-sided die that

has two faces marked Clockwise, two marked

Counterclockwise, and two marked Out.)

If the die is fair, then this is the same

process as the one Prof. Torrence describes,

and the question he’s asking is,

if the token starts out on the green inner spot,

what’s the chance that it ends up

on the red outer spot?

Here comes Engel’s stroke of brilliance.

Let’s keep this board but change the rules.

We’ll use lots of tokens, which we’ll

now call chips — mine will be chocolate —

and we’ll impose a rule for moving the

chips around:

as soon as a spot in the inner ring has three

or more chips, we slide one of the chips Clockwise,

one of the chips Counterclockwise, and one

of the chips Out to the outer ring.

The operation of sliding away three chips

is an example of what mathematicians call chip-firing.

Now that we’ve built Engel’s device, we

have to initialize it the right way.

I’ve already done this.

We load each spot in the inner ring with as many chips as we can without causing any chip-firing to happen.

That means we put two chips on each of the

five inner spots,

because a third chip would cause that chip to fire.

This configuration, with two chips on each

of the inner spots, is called

the maximal stable loading, or the critical loading.

Now the actual computation can start.

It’s a bit like Swine in a Line, except

it's for only one player, and the player has

no freedom of choice at all about where to

add a chip, and chips fire in threesomes instead

of pairs, and the arrangement is not a line

but a circle.

On each move, we add a chip at the green spot,

and then we do chip-firing operations

until we can’t do any more chip-firing.

And then we add another chip at the green

spot, and then do more chip-firing operations

until we can’t do any more chip-firing.

And so on.

Until, at some point, we recognize that we’re

back at the maximal stable loading of the

five inner spots: two chips at each spot.

When that happens, the distribution of the

chips on the five outer spots tells us exactly

how likely it is that a given person gets

to take the $100 bill home.

So let’s see it!

Add a chip at the green spot.

Now there are three chips there, so we send one to each of the neighbors and one goes out.

Ah but now there’s three chips over there,

so send one of them out and

one of them to each of the neighbors.

And there’s three chips over there, so send

one of them out and one to each of the neighbors.

And there’s three chips there so send one

of them out and one to each of the neighbors.

And now there’s four chips there, so send

one of them out and one to each of the neighbors.

And now no more firing can happen because none of the five inner spots have three or more chips on them.

So what do we do? Add another chip on the green spot. Hey, we’ve got three chips!

So send one of them out and one to each of

the inner circle neighbors of the green spot.

Can we do any more firing? No, not yet. So, add another chip here.

Can we do any firing? Nope.

Can we do any firing? Nope.

Can we do any firing? Yes we can.

So send one chip out and one to each of the

neighbors.

Can we do any firing? Yes we can.

One chip goes out and we send one to each

of the neighbors.

And likewise over here: one chip goes out

and one goes to each of the neighbors.

And now no more firing can happen at this

point.

So, it’s time to add another chip at the

green spot.

There’s three!

We send one out, and one to each of the neighbors.

And now, no more firing can happen until we

add one, two, three chips.

And then one chip goes out and one chip goes

to each of the neighbors.

No more firing can happen. So we add another chip here, and another chip here,

and —— oh wait! Look!

We’re back at the original critical loading!

Each of the inner spots has two chips on it!

So we stop the computation, and we read off

the answer to the original problem.

There are 11 chips in the outer ring, and

of those 11, exactly 5 are on the red spot.

So the answer to Torrence’s problem, according

to the abacus method, is the fraction 5/11.

Eustace has a 5-out-of-11 chance of being

the one to keep the hundred dollar bill.

What’s more, each of Eustace’s neighbors

has a 2-out-of-11 chance,

and each of his non-neighbors has a 1-out-of-11

chance.

I said that Engel came up with this method when he was

teaching probability theory to fourth graders.

The usual way of doing problems like this

involves adding and multiplying fractions,

which most fourth graders aren't comfortable

with,

or worse, simultaneous systems of linear equations,

which most fourth graders haven't even heard of.

There’s even a calculus method for solving

problems like this using infinite series computations!

Engel's abacus method doesn't involve anything

more complicated than moving chips around

and, at the end, writing down two whole numbers

with a slash between them.

This method works for many problems.

Next time I’ll apply it to some much simpler

problems, so you can see a curious relationship

between Engel’s probability abacuses and

the more traditional kind of abacuses that

were introduced for recording and manipulating

numbers.

Now, I haven’t told you why this abacus

method works.

If you’re the kind of person who doesn’t

like to use a tool without knowing how it

does its magic, my Mathematical Enchantments

essay for the month of August

will include some links that may interest you.

But even without knowing why the probabilistic

abacus works, I hope you’ll agree that it’s

a tasty way to solve problems in discrete

probability theory.