What is a Random Walk? | Infinite Series
Вставка
- Опубліковано 22 бер 2017
- Viewers like you help make PBS (Thank you 😃) . Support your local PBS Member Station here: to.pbs.org/donateinfi
To understand finance, search algorithms and even evolution you need to understand Random Walks. Tell PBS what types of shows you want to see at www.surveymonkey.com/r/pbsds2017 25 random participants in the survey will receive PBS t-shirts.
Tweet at us! @pbsinfinite
Facebook: pbsinfinite series
Email us! pbsinfiniteseries [at] gmail [dot] com
Previous Episode - Proving Pick’s Theorem
• Proving Pick's Theorem...
Markov Chains
• Can a Chess Piece Expl...
Written and Hosted by Kelsey Houston-Edwards
Produced by Rusty Ward
Graphics by Ray Lux
Made by Kornhaber Brown (www.kornhaberbrown.com)
Random Walks are used in finance, computer science, psychology, biology and dozens of other scientific fields. They’re one of the most frequently used mathematical processes. So exactly what are Random Walks and how do they work?
Comments answered by Kelsey:
Petros Adamopoulos
• Proving Pick's Theorem...
Jonathan Castello
• Proving Pick's Theorem...
Niosus
• Proving Pick's Theorem...
And that is why so many biological reactions take place on membranes. Instead of molecules bumping into one another in three dimensions (free in solute), they are confined to two dimensions (on a membrane). Speeds up the processes greatly.
+
This is why interdisciplinary conversation is so necessary! Stealing this comment for teaching, definitely.
+
Valdagast perhaps catalysts also?
+
First, we need to establish a ministry of random walks.
Scorpy_ that would be Silly
This comment.
This channel is seriously making so many of the concepts underlying the stats I'm learning in grad school intuitive! Such a great video.
I like this girl! She's so smart!
11:50 YES! there is an amazingly beautiful algorithm for finding the area of ANY closed non-intersecting polytope using recursion. So simple that if you are familiar with the divergence theorem (which obviously you are but others might not be), I can just throw the proof in a couple(ish) lines in this comment.
The "volume" V (content) of a polytope can be written as the integral:
V = ∫1dv (where we are integrating over the polytope)
However, since the divergence of 𝐱 is n, 1 can be rewritten as (1/n)∇∙𝐱 where 𝐱 is the position vector and n is the number of dimensions of the polytope, so V becomes
V = (1/n)∫∇∙𝐱dv
but we can apply the divergence theorem here and get
V = (1/n)∮𝐱∙dA (where we are integrating over the "faces" (facets) of the polytope)
but now we can split this integral into a sum of integrals over each face
V = (1/n)∑∫𝐱∙dA
which simplifies to
V = (1/n)∑∫𝐱∙𝐧dA (where 𝐧 is the normal of the facet)
but since each facet of the polytope is flat, by definition 𝐱∙𝐧 is constant.
so pick any point 𝐱₀ on the facet and this turns into
V = (1/n)∑𝐱₀∙𝐧∫1dA
but ∫1dv is just the area A of the facet, so
V = (1/n)∑𝐱₀∙𝐧A
So this means that to find the content of any polytope, all we need to do is sum the areas times any point dot the normals of each face and divide by the number of dimensions of the shape, (where the areas can each be found by this exact same process recursing down until we get to edges or vertices (where vertices have content 1)) and then the we have the content.
Now maybe it's just me, but I find this result to be extremely cool in the sense that it means that you can write a function of only about 5 lines that will be able to compute the area, volume, hypervolume, or whatever else of any non-intersecting polytope in a very flexible and general way.
Now, to address the confused computer scientists out there, I do realize that this formula requires the normals of each facet, and that in order to get each normal, you need to take a square root to get the length of a vector which is a computationally expensive task. However, I'd still argue that this is still a cool algorithm. Also, there may be a way to avoid square roots by cleverly using squared lengths and certain ways of computing normal vectors, but I'm not sure.
Also, I do still believe that this is technically an O(n) algorithm. I am not a computer scientist or student, so I am not sure, but considering that through recursion this effectively just boils down to a sum over vertices, I do think this would be considered O(n).
(and finally, I do realize that I totally just pulled a math and said something was "amazingly simple" and subsequently used things like multivariable integrals, vector algebra, and the divergence theorem which I don't think everyone here is familiar with, but I hope this still was informative for some people (and that I didn't make some glaring mistake))
i find your description of math as both a practical and intellectual property fascinating. please keep it up.
Thanks for this awesome video! It was just the perfect amount of depth to gain an intuitive understanding of Random Walk, and to spark a interest about this topic to actually start reading the textbook of my CS probability course! Subscribed!
I love this series! Thank you so much.
Random Walk @The thoughts you think are magnetic: if you think positive=u attract positive things, if you think negative=u attract negative energies. If you think randomly (Random Walk) with more tendency toward positive= you move toward positive and vice versa. if ...
1:10 - 1:55 Is that a Pascal triangle? I'm pretty sure it is. But why?
EDIT: I was being silly. *Of course* it's a Pascal triangle. After all, we made this by the same process - by adding the values of the two neighbors on the one higher level. Disregard my question, I didn't think.
Thank you for the excellent description of the theory, especially for the pleasant appearance and voice of the narrator and the beautiful video design. 👌
Love the topic of randomness, thanks for this. Seeing the graphs reminded me of electron clouds and excited fields, and it made me wonder; do random walks actually apply in those scenarios?
Im so glad this channel exists
Congratulations on this video and the channel !!! I really enjoyed this information. Thank you.
another application for people interested in fluid dynamics: random walks are one way to model how small droplets or particles are tossed around by turbulent fluctuations.. Quite important for all sorts of environmental and industrial flows.
This is awesome, thank you PBS Digital
my favorite random walk are the photons trying to scape from the sun and taking hundreds of years to do so
2 steps forward, one step back; you're still moving forward.
Hi! I love this channel very much and I'd like to make a suggestion.
I really enjoy understanding the logic behind an equation but when you provide us with a simplified answer such as -sqrtN or sqrtN I have no idea what the equation looked like before simplification unless I grab a pen and pencil, which is often times inconvenient. Do you think you could always show the expanded or semi expanded equation before showing the simplified one? It'd really help a lot!
Thank you for this great explanation! You described everything very clear!!!
Fascinating expose thanks very much!
I used Random walks for laying out rooms in a dungeon generator a while ago, that was a fun application. Great video.
I love the explanation. Amazing. thanks a lot
Well presented, and excellent explanation to answer George Polya's starting question. Thanks for the video!
Wow! That's a great and crystal clear explanation.
My favourite use of Markov chains was my own use of them in my MSc Mathematics dissertation. I used Markov chains to represent disease transmission - my states were what stage of the disease you can be in. I compared their effectiveness to standard SIR black box mathematical models and they were surprisingly accurate!
>spends ages explaining what F_i means
>doesn't explain why 3D random walks are transient when 1 and 2 D random walks aren't
Keep the maths flowing, pbs
Yeah was wondering the same thing.
I think it might be intentional. Gives you something to ponder.
Intentionally explaining the same thing over and over again? No thanks, I am not a US-citizen.
Aaaa what's the answer?
Take a metallic 2D disk of radius R with surface resistivity ρ. Suppose that there is a tension of 1Volts between the center of the disk and the boundary of the disk. As R→∞, you can verify that the current going from the center to the boundary goes to zero. The effective resistance between the center and the boundary increases to infinity as R→∞.
Now do the same experiment with a 3D ball of radius R. You will see (or compute) that the current does not go to zero when R→∞. The effective resistance between the center and the boundary does not go to infinity as R→∞.
Since electrons basically do random walks, you can guess that there is a connection between the effective resistance growing or not to infinity and the transience/recurrence od a 2D/3D random walk. If the resistance goes to infinity, electrons will have difficulties to reach the boundary of the disk and thus stay near the origin: the walk is recurrent. On the contrary, if the resistance does not grow too much, the electrons will eventually go far away from the origin and never come back: the walk is transient
Another gem from Kelsey HE.
Thanx it helped me lot for my quiz
I have also noticed that the 1d non biased integer walk after n steps looks like the nth step of the summing triangle: 1,1(/2); 1,2,1(/4); 1,3,3,1(/8); 1,4,6,4,1(/16 and so on). But the random walk resembles a bell graph. So the summing triangle as some mysterious connection with the bell graph.
This channel is very interesting. I LOVE IT
you are way better than my prof in explaining this, i dont know how my prof was even hired to teach this course
I love this channel keep up the great content
Wow, this is an awesome series. Wish I knew about it earlier. Only if stochastic calculus was taught this way before jumping into measure theory framework immediately.
I used to work on active brownian motion, so these kind of models are my favorite random walks^^
I love your last t-shirt
I LOVE the t-shirt "let \epsilone < 0" ! ! !
So easy to understand and they said skipping math was bad
My favourite random walk is a walk over a parameter space, where each position represents a configuration of a set of parameters of a statistical model, and each step is evaluated against the loglikelihood value of the model with the parameters given by the suggested new point and the observed data. For a model with only two parameters, there is a neat visualisation of such a random walk: a surface in a three dimensional space, where the height of a point on the surface represents the likelihood of the model given the parameters of that point.
To continue the metaphor one could envision the "walker" (a robot that takes the steps of the random walk) droping a grain of sand at every point it visits, slowly changing the shape of the surface it walks on.
In the limit, such a walk produces a surface which "shows" the likelihood of all combinations of parameter values, and the highest point on the surface corresponds to the combination of parameter values with the highest likelihood.
As someone who's struggled quite a bit with the epsilon-delta definition in Calculus, the shirt your wearing in he comment responses made me laugh.
this channel makes me love math
Here are some suggestions
- Cool applications of Linear algebra
- Monte Carlo (can this be used to find the area of a polygon?)
- Randomized primality testing
- Automata, P vs NP etc..
I suspect the shoelace formula is in the end the same idea as my suggestion. To compute the signed area of each triangle, you can simply take the cross product of two edges divided by 2. If we take the fixed point to be (0,0) and use the two edges coming out of it, it simplifies down to just the coordinates of the points in the polygon. Pretty neat.
- *Pascal's* *triangle* *in* *1D!!*
It's rather a good thing that random walks in 3 space are transient. Photons released by fission reactions in a star's core must make random walks, bouncing off other particles, before finally reaching the star's outer layer where they escape as sunshine.
I do not get the intuition of a random walk being transient at above 2D. Yes, the walk has more wiggle room in 3D, but so does a 2D compared to 1D.
Konsta Peltoniemi +
If you represent the probability that the walk will be at the origin after t*2 steps as (no joke) an infinite series (the first couple of terms for a 1d system are .5 and .375, as she gave toward the beginning of the video), the sum will come out to greater than 1 for one- and two-dimensional systems, and less than 1 for higher-dimensional systems.
Someone in the comments pointed out that in 2 dimensions, you have 4 directions to move in and can split the lattice into 4 quadrants, while in 3 dimensions you have 6 directions that you can move in but 8 octants of space to move into. You have 2*(D) directions to walk in and 2^(Dimensions) regions of space. Idk how this relates to anything, but it's a difference that doesn't exist in 1D or 2D and then does exist in all higher dimensions.
mvmlego1212 and Aj Goff - thank you! You both helped me understand :)
This is just a guess, but maybe it has to do with the fact that lines generically intersecting in R1 and R2 but not in Rn, n>2. It's a topological consequence, I believe it's called transversality.
Muy buen documental ...gracias...saludos ..saludos a todos
🇨🇱
I can't be the only person that thinks Kelsey is the most gorgeous person I've seen am I?
you're not
what is her instagram btw?
Love The Music A Minute In To Video
My favorite is Kac's correlated random walk, which gives a hyperbolic PDE in its 'diffusion' limit. :)
photons leaving the centers of stars do so in a random walk; they take millions of years to get out, then 8 minutes to get to earth.
Super vidéos ! merci :)
You are amazing!
My favorite random walk has got to be Einstein's random walk, which models Brownian motion and thereby laid the theoretical foundations for experiment to demonstrate the existence of molecules.
My favorite random walk is the path a photon takes as it makes it's way from the core of the Sun, where it's produced by nuclear fusion, to the edge of the Sun where it can finally escape into space. Since the Sun is do dense at it's core, the photon can only travel a centimeter or so before being absorbed by an atom and re-radiated in a random direction. Predictions vary for the average time it will take a photon to escape the Sun, but some estimates put it in the range of millions of years. The only reason they escape at all is that we live in 3 dimensions and their random walk will on average move away from their starting location.
Just in case somebody is interested, I am currently struggling with random walks in a specific science field. I am doing my thesis project on spectroscopy. Part of it consists on measuring the time that a laser beam takes to decay from a given value to cero. The problem is that the laser light is not constant, so it is sometimes brighter and others fainter. This causes the time of decay to vary randomly. The sum of the decay times is kind of a random walk.
awesome !
thanks for the video :)
thank you! I now understand stats!!
There's nothing more gratifying than seeing abstract math being put in the real world.
My favourite random walk is the one where I get to see nice scenery and get some exercise.
That \epsilon < 0 made my day :D
Coming back to random walk. There is a nice problem with shape of a trajectory of random walk. For example consider random walk in 3D. Now take a lot of trajectories of same lenght. For every point in a trajectory you can assign a mass point. Now you can calculate moment of inertia of that trajectory treated as stiff massive curve (or set of massive points joined with stiff massless rods). Then put all trajectories in a manner that you first allign axis of highest moment of inertia then rotate all around it to allign the axis of lowest one. What is the "shape" of this thing? Cause now you broke the symmetry due to those rotations and it is not spherical at all. I saw the statment of a problem somewhere but dunno how to solve it :D Would appreciate to see some hints :D
thank you so much!!!!!!!!
*I'm loving the use of these engineering videos instead of physics.*
West Chess,example: Markov Chains. Random Walk10:30 stock market.
There also exists a drunk creature in a fractional dimension, somewhere between 2 and 3. This creature doesn't return home -- because it is homeless.
she say 'minus' the cutest i've ever heard it being said..
That "let $\eps < 0$" just makes me hurt inside.
I love that joke too
Another good math joke I like is, "There is only 1 group up to homomorphism"
So we went to ridiculous math jokes now? Ok thats my favourite:
A mathematician was once asked wether he believe in the one true god. His answer was "Yes, up to ismorphism".
A lecturer at my Uni did that on a differential geometry exam a couple years back, almost everyone got the problem wrong...
John: that monster!
very helpful video
My favorite random walk is across web pages, when reading stuff, clicking on hyperlinks or checking references, to wonder after two hours how I came to end on the specific site. OK, I cheated. This walk was not random... However it felt quite random, maybe unpredictable. Cheated again, by my cognitive biases. Oh well. Free will is an illusion.
+
If you walk across any web pages, it might not be so random, but if you just use the youtube suggestions....
You might like the wiki game then.
Free Will is not just an illusion, it's based might very well lie in quantum mechanics
Four colour problem in more dimensions? Like three-dimensional? Do a video about that, please!
J. H.
Thats answered very in detail on one of the comments on Numberphile's video about the four color problem.
But he short answer is that the number of colors you'd need depends on the amount of regions you're coloring and it can be infinite.
Actually the problem was solved in 2D, was it not? That no matter how many regions you have in VALID 2D map (so no overlapping or crossing "countries"), you only need 4 colors at most (or less) to color them. It would be very interesting to see how it's in 3D, that's correct.
sMt3X Yeah, it was solved in 2d and 2 and 4 have multiple connections (exponentials, multiplication, etc...) so I'd like to see how it would work out in 3d.
I think that's not a problem: if you have three or more dimensions you will need infinit many colours.
do you mean
1: 2D-shapes in 3D, 4D, ...
or
2: 3D shapes in 4D, 4D shapes in 5D?
I once tried to explain this to two managers where I work; it turns out that a project's end date undergo a random walk as the project proceeds, it diverges away from the plan.
They kept insisting it 'averaged out'. But it doesn't, it diverges as sqrt(n).
They totally didn't get it, and one of them had something like an MSc in maths. ;) They kept looking at me like I was nuts.
My favorite ramdom walk is the random walk of a photon that is emmited on the core of the sun and delays a couple thousand years to reach the photosphere and escape to the space
i like the random walk on PBS
I love that video simply because one of the commentors on the Markov Chain video didn't want to believe that it is possible to not return in higher dimensions.
Also, even in 1 or 2 dimensions, you don't HAVE to return to the origin. Theres no law who would force that. It just has 0 chance not to happen.
who writes music for these? it sounds great
Either his bed (the starting point) is in the woods or he is not walking randomly.
Nobody walks randomly and always bump into same people, that is a stalker definition, not random.
Now i do not have time to make a check but probably the motivation random walks in 1D and 2D are always expected to be recurrent is related to the motivation for why Chaos cannot be observed in continous 2D systems by virtue of Poincare-Bendixon theorem.
my fav is the self avoiding one
Nice! a very intuitive explanation. I am wondering if possible to talk about "Allen variance" since it is a great tool to analyze random process.
A drunk man will eventually find his way home, but a drunk bird may lose forever at 6:40 haha🤣
great video
Our life itself is an example of random walk
Quick question: We know the walk moves standard deviation n^(1/2) in 1D but what is it for higher dimensions? n^(1/(n+1))?
Me 15 minutes ago: "the stock market is astrology for dudebros"
Me now: "the stock market is a random walk for dudebros"
you lost me at hello 😂
My favorite random walk is the one involved in the photons that escape the Sun. They are created at the Sun's core, and take thousands of years via random walk to get all the way outside and into outer space. And as it seems, if it wasn't because the Sun is tridimensional, some photons would never leave
Correct me if I'm wrong, but I think that taking infintly many steps in the random walk model creates the normal distribution. Is it right?
The two final comments in the video are actually the same algorithm. The shoelaces in the final comment are determinants (cross products) which calculate the area of a part of the polygon, as proposed by the second to last comment. The shoelaces are very easy to implement in a computer.
I am not sure about arbitrary shapes. In a computer you would almost certainly approximate the shape with a polygon - which can be done to arbitrary precision - but smooth curves or surfaces would require integrals. And integrals can be pretty hard, which is why they are also approximated with polygons!
So then... Why are 1D and 2D walks guaranteed to return to the starting position? Couldn't they just go down the positive integer line each time and never return?
Recurrent means "the chance of geting back to 0 is 100%". You can go left everytime, but the chance for that is 0%.
Why? Its zero or infinitesimal?
0
+Raphael -- The thing is, you don't need to step only one direction to never return to the starting point, you just need to always have stepped one direction more than you've stepped the opposite direction.
Raphael Schmidpeter Yes, as Nick said, I still don't understand how the probability of moving continuously away from the start (or any sequence that doesn't come back to the origin) could have a probability of 0.
My favorite is stocks. I ended up here because the financial “Random Walk Theory” was negating any predictability in stocks. After watching the video it’s clear that what I had in mind is more likely the answer imbedded in the theory that was somehow contorted. We can predict the markets using probabilities.
I know what I want to see more of :-)
Follow-up about polygon areas: Petros' and Niosus' comments actually talk about the same method, as the area of a triangle can be calculated as the cross product of the vectors defining its sides. More specifically, in a triangle ABC, the area is equal to ||AB x AC||/2. So, add those cross products together (relative to an arbitrary pivot), divide by two in the end and there you go, that's the sum of the areas of all triangles. The sign of the cross products will even take care of concavity! From there, the shoelace method brings it all down to a single equation by picking the origin as the pivot, which simplifies things. In fact, it only uses basic arithmetic operations, which is great from a computational point of view and avoids any annoying trigonometry. Not only that, but it can deal with any non-self-intersecting polygon, even ones which can't be fit onto a grid (think of polygons with parallel sides with relative irrational lengths). ;-)
The more I watch your videos the more I regret not doing a PhD in Mathematics. In combinatorics and group theory to be precise.
Filled the survey
I am a newcomer to these mathematical topics and have a question related to dimensions. Does the amount of data I want to analyse determine my dimension?Lets say, the more data I have, the higher my dimension? Thanks
You used a binary randomizing option for building the 100 step graph from the random walk along the integer line. What would the 100 step graph look like in a random walk along that same integer line that used a base randomizing element greater than 2? Would it simply be a less developed graph that will eventually look the same given enough steps?
thank u
How about some group theory? Random walks coming from groups can model many phenomena, for example questions like how many shuffles do you need before a deck of cards is "randomized".
To get the approximate Area of a polygon you can use a Monte-Carlo Simulation. If that counts.
There's a subtle point to make when determining whether a random walk is recurrent or transient, having to do with measure theory.
Consider the 1-D random walk. While the probability of returning to the origin is 1, this doesn't mean that the random walk can never return. (Consider for example a sequence of all +1's). What it means is that the set of all random walks that never return has measure 0.
In practice, we might as well say that the random walk can never return, but in theory it can still do so if the random walk just so happens to fall into the set of measure 0.
When assigning probabilities in continuous spaces, the probability if any particular point, such as a particular random walk, is typically 0. So the events we are interested in are all the points that satisfy some condition (such as all the random walks that return to the origin).
This always feels a bit like cheating.