Random walks are ubiquitous in applications of mathematics.

They're in Google's search engine algorithm.

They're everywhere in finance.

They describe all kinds of biological movement on both a macroscopic and microscopic scale.

Let's dive into some of the math behind them.

9 00:00:23,880 --> 00:00:26,700 Mathematician George Polya liked to take morning walks through the woods.

And he noticed that he would regularly bump into the same couple.

This got him thinking, what are the odds that these two randomly walking groups bump into each other.

To answer this, we're going to have to build up a rigorous understanding of random walks.

A random walk is a very general type of random process.

It always involves taking a series of steps.

And the direction of the steps is determined probabilistically.

But, as we'll see during this episode, random walks take place in many different settings and according to many different rules.

Probably the most basic random walk is on the integers.

Let's say you start at the point 0.

You flip a coin with one side labeled plus and the other labeled minus.

If the coin lands plus you move right one.

If the coin lands minus you move left one.

So after one turn, there's a 1/2 probability you're standing on plus 1 and a 1/2 probability you're standing on minus 1.

After two turns, there's a 1/4 chance you're standing on minus 2, a 1/4 chance you're standing on plus 2, and a 1/2 chance it's 0.

After three turns, the odds are 1/8 it's minus 3, 1/8 it's plus 3, 3/8 it's minus 1, and 3/8 it's plus 1.

Let's do it one more time.

After four turns, the odds are 1/16 it's minus 4, 1/16 it's plus 4, 1/4 it's minus 2, 1/4 it's plus 2, and 3/8 it's 0.

Here's a few observations.

First, on the odd turns the random walk can only be on odd numbers.

And on the even turns, it can only be on even numbers.

Second, it mostly hovers around the middle, the number 0.

But the longer you flip the coin for, the more it can spread out.

The probabilities of a random walk being in a specific location begin to form a bell curve.

Notice that in the picture of the probability distribution after 100 coin flips, most of the time you'll be between plus 10 and minus 10.

Here's the more general version of that statement.

After N coin flips, you'll usually be between minus square root of N and plus square root of N. Let's introduce some notation so that we can make the second observation more precise.

Let Fi indicate the outcome of the i-th coin flip.

So F1 is the outcome of the first coin flip, F2 is the outcome of the second, and so on.

The Fi are what's called random variables.

The variables don't have a prescribed outcome.

They have a 50% chance of being plus 1 and a 50% chance of being minus 1.

So what's the expected, or average, value of Fi?

We calculate, 1/2 times plus 1 plus 1/2 times minus 1.

So the expected value is 0.

After we actually flip the coin the Fi have specific values.

So if your first three flips are plus 1, minus 1, plus 1, then F1 equals plus 1, F2 equals minus 1, and F3 equals plus 1.

Let n be some integer.

If we add F1 plus F2 plus F3 all the way up to Fn together, we get the location of the walk after n flips.

Let's call that Sn.

So Sn, the sum of the coin flips, is also a random variable.

It's actually the graphs from before that look like bell curves.

So S1, which is just F1, has a 1/2 chance of being plus 1 and a 1/2 chance of being minus 1.

And S2, the location after two flips or F1 plus F2, has a 1/4 chance of being minus 2, a 1/4 chance of being plus 2, and 1/2 chance of being 0.

Again, these have specific values after you flip.

So if your first three flips are plus 1, minus 1, plus 1, then F1 equals plus 1, F2 equals minus 1, and a F3 was plus 1.

And, S1 equals plus 1, S2 equals 0, and S3 equals plus 1.

So what's the expected, or average, value of Sn?

Well, it's the sum of the expected value of the first n coin flips.

So it's 0.

What we just looked at is a random walk on the integers, which is one dimensional.

But the whole thing works in any dimension.

For example, on the two dimensional integer lattice, which looks like a grid, you start at the origin, the point 0,0, and are equally likely to move up or down or left or right.

For an arbitrary number d, if you're randomly walking along a d dimensional integer lattice, there are 2 times d directions to move.

Since you're equally likely to move in any direction, there's a 1 over 2 times d chance you'll move in a specific direction.

Pretty much everything we've said so far is still true.

You're still most likely to be at the origin.

It's the expected value.

And after many steps, the distribution of the random walk will look like a bell curve, but in higher dimensions.

So for a two dimensional lattice, the distribution actually looks like a bell.

So back to Polya's question from the beginning.

What are the odds that two independent random walks bump into each other?

He quickly realized that in the case of a random walk on the integer lattice, this is the same as asking what are the odds that a random walk returns to its starting position.

Here's two definitions.

Call a random walk recurrent if it's guaranteed to return to its starting position.

Call a random walk transient if there's a positive probability that it never returns to its starting position.

In one and two dimensions, a random walk is recurrent.

There's a 100% chance it returns to its starting spot.

In fact, it'll return there infinitely many times.

So that answers Polya's question.

They're walking along the two dimensional ground and guaranteed to keep bumping into each other over and over again.

But a random walk on the integer lattice in dimensions 3 and higher is transient.

In 3 or 4 or 100 dimensions, there's a chance that the random walk will escape and never return to its starting spot.

Intuitively, this kind of makes sense.

In higher dimensions there's more space or options for where a random walk can wiggle off to.

A favorite joke among mathematicians is a drunk man will eventually find his way home, but a drunk bird may get lost forever.

The drunk man has no preferential direction.

He's equally likely to move in all directions.

We call that a simple random walk.

But in general, a random walk can have a bias or a preferential direction.

Let's look at this in one dimension.

Now, instead of flipping a fair coin, you're flipping a biased coin.

It has probability p of landing on plus and probability 1 minus p of landing on minus, where p is some number between 0 and 1.

So if p equals 1/2, we have a simple random walk, we were just looking at.

But if p equals 1/4 it has probability 1/4 of moving right and probability 3/4 of moving left.

So it's 3 times more likely to move left than right.

The smaller p is, the more it's biased to the left.

The bigger p is, the more it's biased to the right.

Before, we expected our random walk to hover near 0.

But now it should be moving.

Let's look at a similar computation as before to find out the expected value of one coin flip.

With probability p, the coin flip is plus 1.

And with probability 1 minus p, the coin flip is minus 1.

So the average value of the coin flips will be 2p minus 1.

Where will it be after n steps?

Let's compute the expected value.

Again, it's the sum of the expected values of the n flips.

So it's n times 2p minus 1.

For the sake of example, let's assume p equals 3/4.

That means there's a 3/4 chance of moving right, and a 1/4 chance of moving left.

So 2p minus 1 equals 1/2.

So after 10 moves, you'd expect to be at plus 5.

And after 100 moves, you'd expect to be at plus 50.

You're moving to the right with speed 1/2.

So 2p minus 1 is like the speed of the walk.

But the random walk isn't going to move at exactly that speed.

It'll fluctuate around that average.

Just like the simple random walk fluctuated around 0.

While the speed of the walk is similar to n, the fluctuations around that average or similar to the square root of n. So there's really two speeds happening here.

The average speed at which it's moving, which is like n, and the speed at which it's fluctuating around that average, which is like the square root of n. I want to point out for folks who saw our episode on Markov chains that a random walk is an example of a Markov chain.

Remember that a Markov chain was a set of states with arrows connecting them that told us how likely you are to jump from one state to another.

In that episode, we only looked at Markov chains with finitely many states.

But a random walk on the integers is an example of a Markov chain with infinitely many states.

Each of the infinitely many integers is a state.

And the probability transition functions are given by the equations probability of jumping from x to x plus 1 equals p, and the probability of jumping from x to x minus 1 equals 1 minus p. Random walks are everywhere.

They're not just on the integer lattice.

You can randomly walk through a graph like this.

A computer can randomly walk through websites, which is basically what Google's search algorithm is doing.

You can modify a random walk on the integers by requiring that it stop if it hits plus 10 or minus 10, what's known as gambler's ruin, a model of a simple gambling game.

You can also use random walks to model the stock market.

There's an endless number of interesting random walks.

What's your favorite?

Let us know in the comments.

See you next week on "Infinite Series."

Hey, all.

It's time for the annual PBS Digital Studios survey.

How did PBS react to the nearly 40,000 responses they got last year?

By creating this show.

You all asked for a math show and you got it.

So what do you want to see on YouTube in this upcoming year?

There's a link in the description to the survey.

It should only take 10 minutes to fill out, and 25 randomly selected participants get PBS t-shirts.

We're excited to hear what you're thinking.

Let's talk about your responses to Pick's theorem, the formula for finding the area of polygons with vertices on the integer lattice.

First, Jonathan Costello has an excellent correction.

He says, in your proof that planar graphs have Euler characteristic 2, I think you missed a step.

Since we're allowing loops on a single vertex, we need to consider whether the edge we pick is a loop or not.

If it's not, the logic works fine.

Contraction of the edge removes one edge and one node, and we're fine.

But if it's a loop, contraction of that edge removes one edge and one face.

This is still fine.

Faces and edges can cancel out too.

But the argument is subtly different between the two cases.

Thanks for pointing that out, Jonathan.

Petros Adamopolouos responded that this method is actually not the simplest for a computer, and then suggested a method for a computer to find the area of a polygon.

This made me curious.

Does anyone know other methods for a computer to find the area of a polygon?

What about an arbitrary shape?

Finally, Neiosis drew our attention to the shoelace formula, which I'd never heard of before.

It also finds the area of a polygon in a neat way that multiplies the vertex coordinates in a weird criss cross pattern, hence the name shoelace formula.

Go check it out.

See you next time.