Engel Machines, part 1

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

English subtitle

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.