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