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.
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))
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.
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.
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!
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!
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.
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.
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?
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!
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.
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 ...
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.
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.
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..
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.
>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
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
Thank you for the excellent description of the theory, especially for the pleasant appearance and voice of the narrator and the beautiful video design. 👌
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
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.
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.
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.
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.
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.
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 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.
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
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.
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!
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.
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
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.
5:11 That's misleading. A circle has nothing to do with this example, because we are limited to 4 specific directions. Distances are Manhattan rather than Euler. The correct shape would be a diamond (aka a square tilted 45 degrees).
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.
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 explanations on this channel are way more advanced then numberphile, not sure if it's a good thing or a bad thing. But often I feel like I don't know what's going on on this channel where on numberphile it's fairly simple. I don't know why that is
The distribution you start drawing at 2.09 does not take the odd/even effect into account. It is also confusing that the probabilities seem to increase all the time, despite the fact that they should sum to 1.
This may not be the place to discuss this but i did some calculations and if all the bits in a 1 TB hard drive were able to have 3 states instead of 2, the same hard drive would be able to store 1.5^43 or about 31 million binary terabytes of data. A video on this would be greatly appreciated.
Your math is wrong. Stuff like this is already done on solid state drives, and done with sometimes up to 8 states per memory cell. You don't get anywhere close to the kind of improvements you're suggesting. The math below is logarithm heavy, and because we're talking about information theory here, we're going to assume that logarithms are base 2 by default. I'm also going to refer to bits, trits, digits, etc. as symbols. Going to a different number of states per symbol (i.e., going from bits to trits) scales with log (B) / log (A) where A is the original number of states per symbol, and B is the new number of states. This means switching from bits to trits (2 states to 3) only increases capacity by a factor of 1.58, not 31,000,000. The reason being that memory capacity is based on the logarithm of the number of possible states. A single bit has 2 possible states. Combine 8 bits, and together they have 256 possible states. However, this isn't a 128x increase in the amount of data. It's an 8x increase because of the logarithmic scaling. If we add another bit, we go up to 512 possible states, but we only increase the data by a factor of 9/8. Suppose we switch to 16 states per symbol, rather than 3. This simplifies our math, plus this system is already in use in the form of hexadecimal notation of numbers. Each symbol has 16 states, meaning it's the equivalent to log(16), or 4 bits. Not 8x like your math seems to suggest. This also doesn't compound like you seem to be suggesting in your math. Adding another symbol doesn't mean we have an additional 4x as much data. It just means that we added the equivalent to another 4 bits. You can check this against base 10 too. If we have 4 digits, that gives us 10^4 states, or 10,000. 4 bits on the other hand gives us 2^4 states, or 16. If it scaled the way that you suggest, moving from bits to digits would provide us with 5^4 more information, meaning that 4 digits would be the equivalent to (5^4) * 4 bits, or 2,500 bits. In other words, representing the number 9,999 in a computer would take 312.5 bytes, rather than the 13.288 bits (
I don't have any knowledge of information theory. So I was guessing my speculation would be most probably incorrect. However, I'd like to give you the same example that I thought of. Perhaps you can tell me the flaw in it. Any file stored in the binary hard drive is a binary number. Say the number 0010011100010000. This requires 16 bits of space. However, when we store the same number in base 3, it becomes 111201101 and requires only 9 bits of space to store and we can store another number in the remaining 7 bits. I realize that the space gained doesn't scale up exponentially as I imagined but I think it's fairly certain that the more bits we have, the more space we gain. So it does increase in a quasi-exponential manner.
Only the total number of states scales that way. The total amount of data (in bits) scales with the logarithm of the number of states. If we have 5 bits we can calculate the number of possible states: 2 * 2 * 2 * 2 * 2 = 32 It scales this way because one bit has two states: 0 and 1. If we add another bit, we get 00, 01, 10, and 11. Having N bits means that for every state that we have with N-1 bits, we have a version followed by a 0, and a version followed by a 1. Thus, N bits gives us 2^N possible states. If we change to 3 possible states per symbol, the only thing that changes is that we now get 3 variations each time we add another symbol. More states mean that we can store larger numbers, for the same reason that allowing more digits on a calculator lets you work with bigger numbers. Decimal notation is just a number system with ten states per symbol. More bits means that you can store bigger numbers, and yes, the size of the numbers scale exponentially with the number of states. However, a problem arises when we want to store multiple numbers. Let's say we want to store two numbers, each of which exists in a range from 0-255, meaning that it takes up 8 bits. Each set of 8 bits gives us 256 possible states. To store two numbers independently, we need to calculate the number of possible states that two numbers together will take. We can add a layer of abstraction here and think of each number as it's own 256-state symbol, meaning that the two numbers give us 256 * 256 possible states, or 65536 possible states. Taking the logarithm of this shows us that this requires exactly 16 bits. If we decide we want to store 3 numbers, that goes up to 24 bits. 4 requires 32, 5 requires 40, and so on. Adding more numbers increases the amount of data required linearly, because the number of total states that all the numbers can be in together increases exponentially. The exponential and logarithmic growth cancel out, and we're left with linear growth. Yes, you get small improvements from going to a number system with more states per symbol, but it doesn't compound. You still get exponential growth, and the logarithm still cancels it out. It grows faster than binary, but only by a finite factor. 3 states per symbol means each symbol is the same as log2(3) bits, meaning that N 3-state symbols only correlates to ~1.58N bits. 4-state symbols increases this to 2N bits, 10 to ~3.32N bits, and so on. We can also work backwards here. Say we want to be able to represent 10x as much data in the same number of symbols in binary. In order to do that, we need to pick a number system where each symbol is the equivalent of 10 bits. We can figure this out really easily, as N bits correlates to 2^N states. We punch our numbers in and we end up with a requirement of 1024 states per symbol. If we want an 11x improvement over binary, this doubles to 2048, and continues to grow exponentially as we demand more efficiency. So essentially, the size of the numbers you can work with grow exponentially with the number of bits, but storing multiple numbers requires exponentially more states anyway, so the benefits cancel out. Going to a different number of states per symbol just means that you're able to get to the same number of states with fewer symbols, but that improvement only scales with the logarithm of the number of symbols, so you end up with diminishing returns, as you need to increase the number of states exponentially to get linear improvements.
Feynstein 100 you get little less than 1.6 bits extra per bit-to-trit transition, so 1TB drive where it could store 3 states per unit instead of 2 would store 1.6 terabytes worth of data. If you modified each bit to store 4 states, that would mean you turned each bit into two bits, so you'd have 2 terabyte drive now instead.
we are very lucky that there is a non-zero postive probability for a random walk in 3D not to come back to 0. Indeed, thanks to that photons created at the center of the sun still manage to get out of the sun and get to earth! :)
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".
I'm pretty certain that there's a nonzero probability of a 1D or 2D random walk never returning to the starting position. The coin could always flip against the direction of the starting position time and time again forever. All outcomes of fair coins (50/50 for 1D) (25/25/25/25 for 2D) or even of biased coins are nonzero, so there's always that chance of moving away from the starting position after each flip. The probability of that walk occurring is infinitesimal after an infinitely long time, but it must still exist. Thus 1D and 2D random integer walks are transient.
· 0xFFF1 wait did you just say that multiplying 0.5 by itself infinitely many times doesn't converge to 0? For any finite coin flips, you're right, there is a non-zero probability of never returning. For infinite? Not quite.
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?
+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.
I am from Romania and I recognize the white and red string attached to your wrist as a traditional Eastern European custom that happens during spring. I am very curious about how that came to be and whether I am wrong about the custom being Eastern European.
I'm not sure "google's search algorithm is doing" random walk. now there may be some kind of random walk involved in their page ranking algorithm, but the "search algorithm" sounds more like the "crawler" which I suspect uses an "exhaustive traversal".
Are random walk applicable to issues involving wave function collapse? I am wondering about this question since I watched a PBS digital studios video, " How time becomes a space inside a black hole?" Here is the same question I posed there: When we video record an event in a film, doesn't time become space ( 2 dimensional) ? When we replay that video, doesn't that space reverse to time? An observer at the same recorded frequency ( 28 frames/sec) not only experiences time but space in that reference framework of that event. Neither black nor white holes are evident since all the activities occur in the same world line "now". What kind of mathematical singularity does this situation describe? Would any one ( including the host of this series - Kelsey Houston-Edwards) care to answer? Thanks
I'm wondering if the fact that 3 is the smallest number of dimensions for a transient random walk is linked with the fact that 3 is also the number of dimensions of space as we perceive it. Something like.. if space where less that 3d, then all force fields would not propagate outwards but collapse in a point instead, and nothing wouid exist.
An interesting random walk would be a "Tron" random walk or "Snake" random walk. Where the path isn't allowed to cross over itself. I could only imagine how complicated that would make the math. Lol. Edit: I looked it up, and they're apparently called self-avoiding random walks. Fair enough.
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".
I prefer a slight modification to the shoelace formula, which I ended up implementing yesterday for another purpose. First, instead of (x_1 * y_2) - (x_2 * y_1), I prefer to look at the expression (x_2 - x_1) * (y_2 + y_1) / 2. In practice, the division by 2 is factored out to the end. The fact that it has fewer multiplications is mostly irrelevant, but does mean it can be faster on some processors. I prefer it because the geometric interpretation is simpler. The points (x_1, y_1), (x_2, y_2), (x_1, 0), and (x_2, 0) form a trapezoid. The difference in x-coordinates multiplied by the average height is the area of the trapezoid. The sum of all of these terms is the signed area of the polygon: positive if the points are clockwise and negative if the points are anticlockwise*. If you use this formula on a figure-eight or some other polygon that crosses itself, the result will be the positive area minus the negative area. Yesterday, I wanted to determine if my polygons were clockwise or anti-clockwise, so I didn't bother dividing by 2 at the end; I just checked the sign of the result. *If your coordinate system has y reversed, which is common in web development, swap which one is positive. Alternately, think of "clockwise" as meaning "negative angles".
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.
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))
This channel is seriously making so many of the concepts underlying the stats I'm learning in grad school intuitive! Such a great video.
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.
I like this girl! She's so smart!
my favorite random walk are the photons trying to scape from the sun and taking hundreds of years to do so
i find your description of math as both a practical and intellectual property fascinating. please keep it up.
Im so glad this channel exists
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.
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!
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!
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.
2 steps forward, one step back; you're still moving forward.
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.
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?
That explains the gallahs that eat our berries.
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.
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!
you are way better than my prof in explaining this, i dont know how my prof was even hired to teach this course
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.
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 ...
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.
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 used Random walks for laying out rooms in a dungeon generator a while ago, that was a fun application. Great video.
- *Pascal's* *triangle* *in* *1D!!*
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..
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.
West Chess,example: Markov Chains. Random Walk10:30 stock market.
Me 15 minutes ago: "the stock market is astrology for dudebros"
Me now: "the stock market is a random walk for dudebros"
this channel makes me love math
Another gem from Kelsey HE.
There's nothing more gratifying than seeing abstract math being put in the real world.
I love this series! Thank you so much.
>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
7:35 my 5.5 inches agrees with this
Thank you for the excellent description of the theory, especially for the pleasant appearance and voice of the narrator and the beautiful video design. 👌
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 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.
Your explanation is as beautiful as you are.
Congratulations on this video and the channel !!! I really enjoyed this information. Thank you.
*I'm loving the use of these engineering videos instead of physics.*
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?
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.
My favourite random walk is the one where I get to see nice scenery and get some exercise.
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.
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.
My favorite is Kac's correlated random walk, which gives a hyperbolic PDE in its 'diffusion' limit. :)
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.
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
So easy to understand and they said skipping math was bad
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.
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.
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!
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.
who writes music for these? it sounds great
This is awesome, thank you PBS Digital
Fascinating expose thanks very much!
Thanx it helped me lot for my quiz
The more I watch your videos the more I regret not doing a PhD in Mathematics. In combinatorics and group theory to be precise.
you lost me at hello 😂
I love your last t-shirt
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
she say 'minus' the cutest i've ever heard it being said..
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.
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🤣
Our life itself is an example of random walk
5:11 That's misleading. A circle has nothing to do with this example, because we are limited to 4 specific directions. Distances are Manhattan rather than Euler. The correct shape would be a diamond (aka a square tilted 45 degrees).
I used to work on active brownian motion, so these kind of models are my favorite random walks^^
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
I love this channel keep up the great content
This channel is very interesting. I LOVE IT
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 explanations on this channel are way more advanced then numberphile, not sure if it's a good thing or a bad thing.
But often I feel like I don't know what's going on on this channel where on numberphile it's fairly simple. I don't know why that is
The distribution you start drawing at 2.09 does not take the odd/even effect into account. It is also confusing that the probabilities seem to increase all the time, despite the fact that they should sum to 1.
This may not be the place to discuss this but i did some calculations and if all the bits in a 1 TB hard drive were able to have 3 states instead of 2, the same hard drive would be able to store 1.5^43 or about 31 million binary terabytes of data. A video on this would be greatly appreciated.
Your math is wrong. Stuff like this is already done on solid state drives, and done with sometimes up to 8 states per memory cell. You don't get anywhere close to the kind of improvements you're suggesting.
The math below is logarithm heavy, and because we're talking about information theory here, we're going to assume that logarithms are base 2 by default. I'm also going to refer to bits, trits, digits, etc. as symbols.
Going to a different number of states per symbol (i.e., going from bits to trits) scales with log (B) / log (A) where A is the original number of states per symbol, and B is the new number of states. This means switching from bits to trits (2 states to 3) only increases capacity by a factor of 1.58, not 31,000,000.
The reason being that memory capacity is based on the logarithm of the number of possible states. A single bit has 2 possible states. Combine 8 bits, and together they have 256 possible states. However, this isn't a 128x increase in the amount of data. It's an 8x increase because of the logarithmic scaling. If we add another bit, we go up to 512 possible states, but we only increase the data by a factor of 9/8.
Suppose we switch to 16 states per symbol, rather than 3. This simplifies our math, plus this system is already in use in the form of hexadecimal notation of numbers. Each symbol has 16 states, meaning it's the equivalent to log(16), or 4 bits. Not 8x like your math seems to suggest. This also doesn't compound like you seem to be suggesting in your math. Adding another symbol doesn't mean we have an additional 4x as much data. It just means that we added the equivalent to another 4 bits.
You can check this against base 10 too. If we have 4 digits, that gives us 10^4 states, or 10,000. 4 bits on the other hand gives us 2^4 states, or 16. If it scaled the way that you suggest, moving from bits to digits would provide us with 5^4 more information, meaning that 4 digits would be the equivalent to (5^4) * 4 bits, or 2,500 bits. In other words, representing the number 9,999 in a computer would take 312.5 bytes, rather than the 13.288 bits (
I don't have any knowledge of information theory. So I was guessing my speculation would be most probably incorrect. However, I'd like to give you the same example that I thought of. Perhaps you can tell me the flaw in it. Any file stored in the binary hard drive is a binary number. Say the number 0010011100010000. This requires 16 bits of space. However, when we store the same number in base 3, it becomes 111201101 and requires only 9 bits of space to store and we can store another number in the remaining 7 bits. I realize that the space gained doesn't scale up exponentially as I imagined but I think it's fairly certain that the more bits we have, the more space we gain. So it does increase in a quasi-exponential manner.
Only the total number of states scales that way. The total amount of data (in bits) scales with the logarithm of the number of states.
If we have 5 bits we can calculate the number of possible states:
2 * 2 * 2 * 2 * 2 = 32
It scales this way because one bit has two states: 0 and 1. If we add another bit, we get 00, 01, 10, and 11. Having N bits means that for every state that we have with N-1 bits, we have a version followed by a 0, and a version followed by a 1. Thus, N bits gives us 2^N possible states.
If we change to 3 possible states per symbol, the only thing that changes is that we now get 3 variations each time we add another symbol.
More states mean that we can store larger numbers, for the same reason that allowing more digits on a calculator lets you work with bigger numbers. Decimal notation is just a number system with ten states per symbol.
More bits means that you can store bigger numbers, and yes, the size of the numbers scale exponentially with the number of states. However, a problem arises when we want to store multiple numbers. Let's say we want to store two numbers, each of which exists in a range from 0-255, meaning that it takes up 8 bits.
Each set of 8 bits gives us 256 possible states. To store two numbers independently, we need to calculate the number of possible states that two numbers together will take. We can add a layer of abstraction here and think of each number as it's own 256-state symbol, meaning that the two numbers give us 256 * 256 possible states, or 65536 possible states. Taking the logarithm of this shows us that this requires exactly 16 bits. If we decide we want to store 3 numbers, that goes up to 24 bits. 4 requires 32, 5 requires 40, and so on. Adding more numbers increases the amount of data required linearly, because the number of total states that all the numbers can be in together increases exponentially. The exponential and logarithmic growth cancel out, and we're left with linear growth.
Yes, you get small improvements from going to a number system with more states per symbol, but it doesn't compound. You still get exponential growth, and the logarithm still cancels it out. It grows faster than binary, but only by a finite factor. 3 states per symbol means each symbol is the same as log2(3) bits, meaning that N 3-state symbols only correlates to ~1.58N bits. 4-state symbols increases this to 2N bits, 10 to ~3.32N bits, and so on.
We can also work backwards here. Say we want to be able to represent 10x as much data in the same number of symbols in binary. In order to do that, we need to pick a number system where each symbol is the equivalent of 10 bits. We can figure this out really easily, as N bits correlates to 2^N states. We punch our numbers in and we end up with a requirement of 1024 states per symbol. If we want an 11x improvement over binary, this doubles to 2048, and continues to grow exponentially as we demand more efficiency.
So essentially, the size of the numbers you can work with grow exponentially with the number of bits, but storing multiple numbers requires exponentially more states anyway, so the benefits cancel out. Going to a different number of states per symbol just means that you're able to get to the same number of states with fewer symbols, but that improvement only scales with the logarithm of the number of symbols, so you end up with diminishing returns, as you need to increase the number of states exponentially to get linear improvements.
Feynstein 100 you get little less than 1.6 bits extra per bit-to-trit transition, so 1TB drive where it could store 3 states per unit instead of 2 would store 1.6 terabytes worth of data. If you modified each bit to store 4 states, that would mean you turned each bit into two bits, so you'd have 2 terabyte drive now instead.
we are very lucky that there is a non-zero postive probability for a random walk in 3D not to come back to 0. Indeed, thanks to that photons created at the center of the sun still manage to get out of the sun and get to earth! :)
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".
I'm pretty certain that there's a nonzero probability of a 1D or 2D random walk never returning to the starting position. The coin could always flip against the direction of the starting position time and time again forever. All outcomes of fair coins (50/50 for 1D) (25/25/25/25 for 2D) or even of biased coins are nonzero, so there's always that chance of moving away from the starting position after each flip. The probability of that walk occurring is infinitesimal after an infinitely long time, but it must still exist. Thus 1D and 2D random integer walks are transient.
· 0xFFF1 wait did you just say that multiplying 0.5 by itself infinitely many times doesn't converge to 0? For any finite coin flips, you're right, there is a non-zero probability of never returning. For infinite? Not quite.
Pls don't even start to talk about infinitesimals, pls :)
Wow! That's a great and crystal clear explanation.
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.
Wouldn't it be appropriate to link the PBS Space Time's journal club video with an annotation/hyperlink at 10:08?
Cool video though.
Well presented, and excellent explanation to answer George Polya's starting question. Thanks for the video!
Thank you for this great explanation! You described everything very clear!!!
I am from Romania and I recognize the white and red string attached to your wrist as a traditional Eastern European custom that happens during spring. I am very curious about how that came to be and whether I am wrong about the custom being Eastern European.
I'm not sure "google's search algorithm is doing" random walk. now there may be some kind of random walk involved in their page ranking algorithm, but the "search algorithm" sounds more like the "crawler" which I suspect uses an "exhaustive traversal".
Muy buen documental ...gracias...saludos ..saludos a todos
🇨🇱
I LOVE the t-shirt "let \epsilone < 0" ! ! !
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?
Are random walk applicable to issues involving wave function collapse? I am wondering about this question since I watched a PBS digital studios video, " How time becomes a space inside a black hole?" Here is the same question I posed there: When we video record an event in a film, doesn't time become space ( 2 dimensional) ? When we replay that video, doesn't that space reverse to time? An observer at the same recorded frequency ( 28 frames/sec) not only experiences time but space in that reference framework of that event. Neither black nor white holes are evident since all the activities occur in the same world line "now". What kind of mathematical singularity does this situation describe? Would any one ( including the host of this series - Kelsey Houston-Edwards) care to answer? Thanks
I can't wait for Kelsey to get her PhD and be featured on Numberphile / other Maths RUclips channels.
Love The Music A Minute In To Video
I'm wondering if the fact that 3 is the smallest number of dimensions for a transient random walk is linked with the fact that 3 is also the number of dimensions of space as we perceive it. Something like.. if space where less that 3d, then all force fields would not propagate outwards but collapse in a point instead, and nothing wouid exist.
An interesting random walk would be a "Tron" random walk or "Snake" random walk. Where the path isn't allowed to cross over itself. I could only imagine how complicated that would make the math. Lol.
Edit: I looked it up, and they're apparently called self-avoiding random walks. Fair enough.
my favourite Random Walk would need to be the Mayan or Aztec calendars - may the force be with you, if you understand it's three dimensional counter
I love the explanation. Amazing. thanks a lot
To get the approximate Area of a polygon you can use a Monte-Carlo Simulation. If that counts.
i like the random walk on PBS
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!
I prefer a slight modification to the shoelace formula, which I ended up implementing yesterday for another purpose.
First, instead of (x_1 * y_2) - (x_2 * y_1), I prefer to look at the expression (x_2 - x_1) * (y_2 + y_1) / 2. In practice, the division by 2 is factored out to the end. The fact that it has fewer multiplications is mostly irrelevant, but does mean it can be faster on some processors. I prefer it because the geometric interpretation is simpler. The points (x_1, y_1), (x_2, y_2), (x_1, 0), and (x_2, 0) form a trapezoid. The difference in x-coordinates multiplied by the average height is the area of the trapezoid. The sum of all of these terms is the signed area of the polygon: positive if the points are clockwise and negative if the points are anticlockwise*. If you use this formula on a figure-eight or some other polygon that crosses itself, the result will be the positive area minus the negative area.
Yesterday, I wanted to determine if my polygons were clockwise or anti-clockwise, so I didn't bother dividing by 2 at the end; I just checked the sign of the result.
*If your coordinate system has y reversed, which is common in web development, swap which one is positive. Alternately, think of "clockwise" as meaning "negative angles".