馃攳
What is a Random Walk? | Infinite Series - YouTube
Channel: PBS Infinite Series
[0]
[Music]
[2]
random walks are ubiquitous in
[4]
applications of mathematics they're in
[7]
Google search engine algorithms are
[8]
everywhere in finance they describe all
[11]
kinds of biological movement on both a
[13]
macroscopic and microscopic scale let's
[16]
dive into some of the math behind them
[19]
[Music]
[23]
mathematician george p贸lya like to take
[26]
morning walks through the woods and he
[28]
noticed that he would regularly bump
[29]
into the same couple just got him
[32]
thinking what are the odds that these
[34]
two randomly walking groups bump into
[37]
each other to answer this we're going to
[40]
have to build up a rigorous
[41]
understanding of random walks a random
[44]
walk is a very general type of random
[46]
process it always involves taking a
[49]
series of steps and the direction of the
[52]
steps is determined probabilistically
[54]
but as we'll see during this episode
[57]
random walks take place in many
[59]
different settings and according to many
[61]
different rules probably the most basic
[63]
random walk is on the integers let's say
[67]
you start at the point zero you flip a
[69]
coin with one side labeled plus and the
[71]
other labels - if the coin lands plus
[74]
you move right one if the coin lands -
[76]
you move left one so after one turn
[79]
there's a 1/2 probability you're
[81]
standing on plus 1 and a 1/2 probability
[83]
you're standing on minus 1 after 2 turns
[86]
there's a 1/4 chance you're standing on
[88]
minus 2 a 1/4 chance you're standing on
[91]
plus 2 and a 1/2 chance it's zero after
[94]
three turns the odds are one a fifth
[96]
minus three 1/8 is +3 3/8 minus 1 and
[100]
3/8 plus 1 let's do it one more time
[103]
after four turns the odds are 1/16 it's
[107]
- 4 1/16 is plus 4 1/4 is minus 2 1/4 is
[111]
plus two and 3/8 it's zero here's a few
[115]
observations first on the odd turns the
[119]
random walk can only be on odd numbers
[121]
and on the even turns it can only be on
[124]
even-numbered seconds it mostly hovers
[127]
around the middle the number 0 but the
[130]
longer you flip the coin for the mole
[132]
it can spread out the probabilities of a
[135]
random walk being in a specific location
[137]
begin to form a bell curve notice that
[141]
in the picture of the probability
[142]
distribution after a hundred coin flips
[144]
most of the time she'll be between plus
[147]
10 and minus 10 here's the more general
[150]
version of that statement after n coin
[153]
flips you'll usually be between minus
[155]
square root of N and plus square root of
[157]
n let's introduce some notation so that
[160]
we can make the second observation more
[161]
precise let fi indicate the outcome of
[165]
the is coin flip so f1 is the outcome of
[168]
the first coin flip
[169]
f2 is the outcome of the second and so
[171]
on the SI are what's called random
[174]
variables the variables don't have a
[176]
prescribed outcome they have a fifty
[178]
percent chance of being plus one and a
[180]
fifty percent chance of being minus one
[182]
so what's the expected or average value
[185]
of F five we calculate one half x plus
[189]
one plus one half x minus one so the
[191]
expected value is zero after we actually
[195]
flip the coin the F I have specific
[198]
values so if your first three flips are
[200]
plus one minus one is plus 1 then F one
[204]
equals plus 1 F 2 equals minus 1 and s 3
[206]
equals plus one let n be some integer if
[210]
we add F 1 plus F 2 plus F 3 all the way
[213]
up to FN together we get the location of
[216]
the walk after n flip let's call that FN
[219]
so FN the sum of the coin flips is also
[223]
a random variable it's actually the
[225]
graph from before that look like bell
[227]
curve so s 1 which is just F 1 has a 1/2
[231]
chance of being plus 1 and a 1/2 chance
[233]
of being minus 1 and s 2 the location
[236]
after 2 flips or F 1 plus F 2 has a 1/4
[240]
chance of being minus 2 a 1/4 chance of
[243]
being plus 2 and a 1/2 chance of being 0
[245]
again these have specific values after
[248]
you slick so if your first three flips
[251]
are plus 1 minus 1 plus 1 then F 1
[254]
equals plus 1 F 2 equals minus 1 and s 3
[256]
with plus 1 and s 1 equals plus 1 s 2
[259]
equals 0 and s 3 equals plus 1
[262]
so what's the expected or average value
[265]
of SN well it's the sum of the expected
[269]
value of the first and coin flips so
[272]
it's zero what we just looked at is a
[274]
random walk on the integers which is
[276]
one-dimensional but the whole thing
[278]
works in any dimension for example on
[281]
the two-dimensional integer lattice
[282]
which looks like a grid you start at the
[285]
origin the point zero zero and are
[287]
equally likely to move up or down or
[289]
left or right for an arbitrary number D
[292]
if you're randomly walking along a
[294]
d-dimensional integer lattice there are
[297]
two times D directions to move since
[300]
you're equally likely to move in any
[301]
direction there's a 1 over 2 times D
[303]
chance you'll move in a specific
[305]
direction pretty much everything we've
[307]
said so far it's still true you're still
[310]
most likely to be at the origin it's the
[312]
expected value and after many steps the
[315]
distribution of the random walk will
[317]
look like a bell curve but in higher
[319]
dimensions so for a two-dimensional
[321]
lattice the distribution actually looks
[323]
like a bell so back to polios question
[326]
from the beginning what are the odds
[328]
that two independent random walks of
[330]
been to each other he quickly realized
[332]
that in the case of a random walk on the
[335]
integer lattice this is the same as
[337]
asking what are the odds that a random
[339]
walk returns to its starting position
[342]
here's two definitions call a random
[345]
walk recurrent if it's guaranteed to
[347]
return to a starting position call a
[349]
random walk transient if there's a
[352]
positive probability that it never
[353]
returns to its starting position in one
[356]
in two dimensions a random walk is
[358]
recurrent there's a 100% chance it
[361]
returns to its starting spots in fact it
[364]
will return there infinitely many times
[366]
so that answers polios question they're
[369]
walking along with two-dimensional
[371]
ground and guaranteed to keep bumping
[373]
into each other over and over again but
[376]
a random walk on the integer lattice in
[379]
dimensions three and higher is transient
[382]
in three or four or 100 dimensions
[385]
there's a chance that the random walk
[387]
will escape and never return to its
[389]
starting spot intuitively this kind of
[392]
makes sense in higher dimensions there's
[394]
more space or
[395]
options for where a random walk we go
[397]
off to a favorite joke among
[399]
mathematicians is a drunk man will
[402]
eventually find his way home
[403]
but a drunk bird may get lost forever
[405]
the drunk man has no preferential
[407]
direction he's equally likely to move in
[411]
all directions we call that a simple
[414]
random walk but in general a random walk
[417]
can have a bias or a preferential
[419]
direction let's look at this in one
[421]
dimension now
[423]
instead of flipping a fair coin you're
[426]
flipping a biased coin it has
[428]
probability P of landing on + and
[431]
probability 1 minus P of landing on -
[434]
where P is some number between 0 and 1
[436]
so if P equals 1/2 we have a simple
[440]
random walk we were just looking at but
[443]
if P equals 1/4
[445]
it has probability 1/4 of moving rights
[448]
and probability 3/4 of moving left so
[451]
it's 3 times more likely to move left
[453]
and right the smaller P is the more
[456]
aspires to the left the bigger P is the
[459]
mores biased to the right before we
[461]
expect our random walk to hover near 0
[463]
but now it should be moving let's look
[466]
at a similar computation as before to
[469]
find out the expected value of one coin
[471]
flip with probability P the coin flip is
[475]
plus 1 and with probability 1 minus P
[477]
the coin flip is minus 1 so the average
[480]
value of the coin flips will be 2 P
[483]
minus 1 where will it be after n steps
[487]
let's compute the expected value again
[490]
it's the sum of the expected values of
[492]
the end slips so it's n times 2 P minus
[496]
1 for the sake of example let's assume P
[499]
equals 3/4 that means there's a 3/4
[503]
chance of moving right and a 1/4 chance
[505]
of moving left
[507]
so 2p minus 1 equals 1/2 so after 10
[512]
moves
[512]
you'd expect to be at plus 5 and after
[515]
100 moves you'd expect to be a plus 50
[517]
you're moving to the right with speed
[520]
1/2 so 2 P minus 1 is like the speed of
[524]
the walk but the random walk isn't going
[527]
to move at exactly
[528]
that feed it will fluctuate around that
[530]
average just like the simple random walk
[533]
fluctuated around zero while the speed
[536]
of the walk is similar to n the
[539]
fluctuation around that average are
[541]
similar to the square root of n so
[543]
there's really two speeds happening here
[545]
the average speed at which is moving
[548]
which is like N and the speed at which
[551]
is fluctuating around that average which
[553]
is like the square root of n I want to
[555]
point out for folks who saw our episode
[557]
on Markov chains that a random walk is
[560]
an example of a Markov chain remember
[563]
that a Markov chain was a set of states
[565]
with arrows connecting them that told us
[567]
how likely you are to jump from one
[569]
state to another in that episode we only
[572]
looked at Markov chains with finitely
[574]
many states but a random walk from the
[576]
integers is an example of a Markov chain
[578]
with infinitely many states each of the
[581]
infinitely many integers is a state and
[584]
the probability transition functions are
[586]
given by the equation probability of
[589]
jumping from X to X plus 1 equals P and
[591]
the probability of jumping from X to X
[594]
minus 1 equals 1 minus P random walks
[597]
are everywhere they're not just on the
[600]
integer lattice you can randomly walk
[602]
through a graph like this a computer can
[605]
randomly walk through websites which is
[607]
basically what Google search algorithm
[609]
is doing you can modify a random walk on
[612]
the integers by requiring that it stops
[614]
if it hits plus 10 or minus 10 what's
[617]
known as scan blurs ruin a model of a
[620]
simple gambling game you can also use
[622]
random walks to model the stock market
[624]
there's an endless number of interesting
[627]
random walks what's your favorite let us
[630]
know in the comments see you next week
[632]
on infinite series hey y'all it's time
[635]
for the annual PBS Digital Studios
[636]
survey how did PDFs react to the nearly
[640]
40,000 responses they got last year by
[643]
creating this show you all asked for a
[646]
map show and you got it so what do you
[649]
want to see on YouTube in this upcoming
[650]
year there's a link in the description
[653]
to the survey it should only take 10
[655]
minutes to fill out and 25 randomly
[657]
selected participant
[658]
get PBS t-shirts we're excited to hear
[661]
what you're thinking let's talk about
[662]
your responses to picks theorem the
[664]
formula for finding the area of polygons
[666]
with vertices on the integer lattice
[669]
first Jonathan Casio has an excellent
[672]
correction he says and you're proof that
[675]
planar graphs have Euler characteristic
[677]
2 I think you missed a step
[679]
since we're allowing loops on a single
[682]
vertex we need to consider whether the
[684]
edge we pick is a loop or not if it's
[687]
not the logic works fine contraction of
[689]
that edge removes one edge and one node
[691]
and we're fine but if it's a loop
[693]
contraction of that edge removes one
[696]
edge and one face this is still fine
[699]
faces and edges can cancel out too but
[702]
the argument is subtly different between
[704]
the two cases thanks for pointing that
[706]
out Jonathan Petros a Demopolis
[708]
responded that this method is actually
[710]
not the simplest for a computer and then
[713]
suggested a method for a computer to
[715]
find the area of a polygon this made me
[718]
curious does anyone know other methods
[720]
for a computer to find the area of a
[722]
polygon what about arbitrary shape
[725]
finally meiosis drew our attention to
[729]
the shoelace formula which i've never
[731]
heard of before it also finds the area
[734]
of a polygon in a neat way that
[735]
multiplies the vertex coordinates in a
[737]
weird crisscross pattern hence the name
[740]
shoelace formula go check it out see you
[743]
next time
[745]
[Music]
Most Recent Videos:
You can go back to the homepage right here: Homepage