Posted by: Gary Ernest Davis on: February 1, 2010

translation servicesTranslate | French translation Spanish translation translate German translate Chinese

Algebra is powerful because it allows us, among other things, to do arithmetic on the names of variables or unknown quantities and find specific numerical values for those variables or unknowns.

If, as some people assert (wrongly, in my view) that mathematics is *only* a language, then it is a very peculiar language indeed. In what other language can you carry out arithmetical operations on names?

Here is, in my opinion, a lovely example of how simple algebra allows us to find a complete and rigorous answer to what seems like a difficult problem.

The problem is this:

*Imagine you are standing at the beginning of a very long path, made from stone steps, as shown in the drawing, below:*

*You have a fair coin in your hand and you flip it. If the coin lands heads up you take 1 step forward; if it lands tails up you take 2 steps forward.*

*Keep doing this until you either land on step 20, or else you pass step 20.*

*Record whether you did or did not land on step 20.*

*Go back to step 1 and do this over.*

*Do it over many times.*

*With what probability – exactly or approximately – will you land on step 20?*

Here is how a smart physicist friend of mine answered this question:

“*Let’s see*” he said. “*By step 20 the transient behavior has died out, so there’s about the same probability of landing on any given step. That probability must therefore be the reciprocal of the expected value so the probability is approximately *.”

You might wonder why step 20, and not step 30, or step 100? So let’s ask with what probability would we land on step n where n could be

This probability is what we do not know, and wish to find.

Algebra begins by naming unknowns and variables, so let’s name the probability of landing on step n. We could call it “Brian” or “Shirley” but how about simply “p” for probability?

But, if p is the probability of landing on step n, shouldn’t we incorporate into the name something that tells us which step we’re at? Say, call this probability ““? After all, will presumably be different, so we don’t want to give them all the same name, p.

What do we know about this probability?

Experimenting with many coin tosses will soon convince you that what happens early on does not matter, and the only thing that is important for step n is whether you do, or do not land on step n-1.

How can you NOT land on step n?

The only way is to land on step n-1 and throw a tail, which skips us over step n and onto step n+1.

So the probability of NOT landing on step n is the probability of landing on step n-1 and then throwing a tail. Nothing that happened before step n-1 matters.

Here comes some arithmetic on the names of these probabilities.

The probability of landing on step n is so the probability of NOT landing on step n is .

The coin is fair so it lands tails up the time.

The tosses of the coin are independent, so the probability of not landing on step n is the probability of landing on step n-1 and then throwing a tail.

In terms of names, this says that .

Because these are names of numbers, we can do more arithmetic on the names, and so express .

Do the probabilities become approximately the same as n increases, just as the physicist asserted?

If they do then for large n, say , we will have so .

Doing some more arithmetic on the name we see that so .

So IF – and it might be a big “IF” – the probabilities become approximately equal then they must get closer to .

Do they, in fact, get closer to ?

To figure this out, let’s look at the difference between the probability of landing on step n and .

In terms of arithmetic on names, this is .

What do we know about this?

Well, we know .

Doing some more arithmetic on these names we see that .

Let’s give the difference between the probability of landing on step n and a name: let’s call it “*error(n)*“.

Our arithmetic on names tells us that *error(n)* *error(n-1)*.

So at each step the error changes sign and becomes half as big.

In other words the error approaches 0 very fast – exponentially fast – changing sign as we go from one step to the next.

So the probability of landing on step n does indeed approach – exponentially fast in fact – so that by step 20 it is very nearly .

A plot of versus n shows this clearly:

Amazing that from the one idea of how we could NOT land on a given step, we can do simple arithmetic on the names of probabilities and come up with this nifty graph.

Algebra has its uses (especially for those of us not as insightful as my physicist friend) !

This problem was originally posed to me with the person throwing a 6-sided die to determine how many steps to move forward (the number of dots on the face of the die that lands up).

For this problem there are more cases to consider how not to land on step n, for large n, but otherwise the reasoning is the same.

If you absorbed the physicist’s argument then you might argue that the answer in this case would be the reciprocal of , namely , and you would be right.

An analogous argument will show that for a k-segment spinner (see the picture, below), with numbers all equally likely, the probability of landing on step n, for large n, is approximately .

For example, for a 3-segment spinner the probability of landing on step n, for large n, is approximately .

3 | John Lame

June 29, 2010 at 2:56 pm

For some reason, when I read the article, I misread the rules to be that one steps *backwards* one step when throwing heads. As I read the reasoning, everything you said rang true (e.g. the only way to not land on step 20 is to eventually land on step 19 and roll tails).

However, empirically (yes i wrote a quick program), the actually probability of landing on the 20th (or nth) step if you step backwards upon throwing heads seems to be somewhere around 61.8 percent, not 66.7%

So now I’m confused. Is my program wrong? If not, then where is the incorrect assumption in the above argument if heads means step backwards 1 step and tails means step forward two steps. Also, what would be the approximate probability of landing on step n in this case (assuming you of course stop as soon as you reach or pass step n).

John

p.s. I do see the problem in the argument now. The probability of not landing on step n is indeed the probability of landing on step n-1 plus some stuff, but the “stuff” involves a lot of possibilities: (e.g. rolling tails, rolling heads+heads+tails+tails, etc.). But perhaps its interesting that a careless reading of the above article could lead one to believe that it doesn’t matter whether you step backwards or forwards on a roll of heads. And I still don’t have the actual answer. :)