It's incredible how we've developed math able to distill the "uniform" parts of randomness into more deterministic objects at larger scales! I think this is pretty much the overall strategy as constructions like the central limit theorem - and just as beautiful. Hadn't heard of the Tracy-Widom distribution though. Great video!
I'd like to give an additional note regarding the end of the video: In problems with a lot of independence, the normal distribution arises quite often (central limit theorem, for example) This type of independence is intimately related to the commutativity of random variables: XY is distributed the same as YX If we instead consider random variables that aren't commutative anymore (For example, random matrices), we get out an entirely different theory of probability, known as *Free Probability Theory*. This theory was only developed very recently in mathematics (1970-80) The notion of independence we get is no longer the original E(X)E(Y) = E(XY), but a (more complicated) "Free Independence" which works for non commutative random variables. It turns out, under this new theory: - a central limit theorm exists, which is the SEMICIRCULAR DISTRIBUTION - Random matrices like Wigner Ensembles have limiting distribution equal to the semicircle Id recommend reading Chapter 1-2 of "Free probability and Random Matrices" by Mingo and Speicher to look at the relation between Commutative/Non commutative and Normal/Semicircular distributions
This reminds me of my second problem in my first programming class : Find the longest and shortest, increasing and decreasing subsequences of uniform difference in a list of numbers. That list was not a permutation of an ordered list. Several numbers appeared multiple times. That was to be programmed in FORTRAN, submitted to a remote mainframe as batch work.
"High level" science vulgarisation is one of the most beautiful things the internet era will have brought to mankind. This channel is yet another example out of many. Thanks a lot!
he dropped a masterpiece and left, honestly i can't imagine the amount of work behind this video but i am grateful to be able to watch it for free so thank you
Thanks for watching! These videos do take a lot of work, but I plan to continue participating in the summer of math exposition so probably will keep making about one video per year
9:44 Also interesting here is the fact that these probabilities sum to 1 gives the neat result that the sum of the squares of the different numbers of Young tableaux equals n!. I had seen this before using representation theory of symmetric groups, but this is an amazing new perspective on it.
Great video. Regarding your comment at the end, about how in math you can go from not knowing anything about a particular field, to understanding the statement of an active research problem in about thirty minutes is really spot on and I couldn't agree more. One of my professors researches polynomial automorphisms. He explained to me, after my first year of college, what the field is about and the Jacobian conjecture in thirty to fourty minutes.. That's really how quick it can be to reach the edge of human knowledge.
Did not expect the Gaussian curve to show up at the end. I've kinda grown on it and the math of statistics in recent years. This was a fascinating video. For something that seemed ludicrous to prove, like x×2^(1/2), you did a great job showing an intuitive proof for it. Very nice video!
When you reframe the problem as random points in a box, surely there's an issue with some points possibly being collinear. Perhaps it has probability zero so does not matter?
Any co-linearity occurs in a lower dimensional (affine) manifold of the full space, therefore probability zero, so the (finite) union of all possible co-linearities is still probability zero.
Eyy, I heard a little about the Tracey-Widom distribution when I was (misguidedly) trying to come up with a notion of a uniform distribution on the set of permutations over the natural numbers. Cool to see it again. (I have since concluded that there probably isn’t such a distribution, because I’m pretty sure that that group isn’t compact under the topology on it one gets from viewing it as a limit of permutation groups. So, the thing I was attempting presumably doesn’t work. But I do still wonder if, in the same way that there is no uniform probability distribution over the reals, the Gaussian distributions of increasing stddev are sorta kinda what one might naturally use instead as a natural prior over the reals, whether there might be a similarly natural family of distributions over permutations of the set of natural numbers?)
@@jake5331 you can embed S_n in S_{n+1} (so, e.g. {(1,3),(2,1),(3,2)} would get sent to {(1,3),(2,1),(3,2),(4,4)} ) And, with this directed system of groups and group homomorphisms, one can take the direct limit. (So, take the union over all the groups, and then if one of the homomorphisms sends x to y, identify x and y. This works as a group because, for any two elements from different groups in the directed system, find a group where there is a homomorphism in the system from each of the two groups to that one, and then take the image of the two elements there, and then apply the group operation there. This probably wasn’t a very good explanation of direct limits. Wikipedia has a better one.)
@@OMGYavani That doesn’t necessarily prevent it. The group U(1) also has cardinality of the reals (it is isomorphic to R/Z), and, as a compact group, it has a normalized Haar measure. The issue isn’t one of cardinality, but is instead (I think) for the same reason that the group of integers under addition has no uniform probability distribution : because it isn’t compact.
It's always lovely seeing RSK and young tableaux in the wild! Haven't watched the video yet but am sure it would be wonderful. How long did it take you to make the video?
This one took about 3 weeks of consistent work to make. I had been thinking about the script and coming up with ideas for animations for a few months before that though.
i love your videos so much, you are able to implement a clear explanation with amazing visuals that catch the eye, and thereby the attention. Are you planning to cover different subjects other than graph theory related stuff? I'd love to see what you are able to do with number theory or abstract algebra, but again keep up the good work!
Thank you! I (Vilas) am currently a PhD student studying probability theory, so it’s unlikely that I’ll make a long video about anything too distant from my research. Not impossible, but don’t get your hopes up!
@@SpectralCollective Oh thats cool! I'll take this as motivation to maybe make something myself! I'm still studying in high school but I managed to teach myself a lot of algebra and number theory, and the more incomprehensible a definition or a theorem is, the more I want to go down the rabbithole. Since on youtube I can't always find everything I wanna know, I'm looking forward to produce something by myself, and you're videos are just the perfect example of what I would like to do! You really deserve a lil more attention in the educational maths community.
I cant remember who the quote is attributed to but in a math book i read a few years ago there was a great heuristic about rigorous mathematical proofs: "you should never try to prove something whose truth is not almost obvious"
Very interesting video! I have a couple of questions if you don't mind. At the end, the crystallization animation has white diagonal lines. Is this a visual artifact? Should the Robinson-Schensted algorithm feel intuitive (could I have come up with it)? I was surprised that Young tableaux/diagrams were the key to that proof. Interestingly enough, Young diagrams are absolutely necessary to understand the representation theory of the symmetric group. Perhaps permutations and Young diagrams have a deeper connection than I thought.
The "crystal" simulation is a model called ballistic deposition, where blocks are raining from the sky in columns (like tetris) but the blocks will also stick to each other on the side. Every white pixel is a hole in the crystal caused by some blocks not falling all the way to the bottom of their column. The lines that you see are actually emergent behavior, and I can't really explain why these "canyons" form. Here's a cool video about this model: czcams.com/video/Z6XP3n-Sjiw/video.html I wouldn't say you should be able to come up with the Robinson-Schensted algorithm by yourself necessarily, it's not that obvious. But it is only one step away from something called "patience sorting" which may be easier to come up with.
Great video! Is there some simple heuristic/intuition why the constant is equal to 2? If you approximate the process by a uniform grid of points, it looks like the constant is in that ballpark but I am wondering if there is a more precise heuristic argument one can make.
This is the best video I've seen this month. Been trying to find a book on mathematics behind algorithms. Like proofs and such things. Can you recommend any similar books?
I'm currently researching Random matrix theory (although a different area) and I love this video! I knew about the longest increasing subsequence problem before and its relation to TW, but I didnt know how that connection was made. However, Young Tableaux arise in relation to non-crossing partitions of sets, which again are related to GUEs. I'm wondering, is the Young Diagrams limit shape being semicircular related to the Semicircular distribution?
Actually, the curved portion of the limit shape is not quite a segment of a circle, so I don’t think this is related to the semicircle law at all. The proof of the limit shape theorem works by carefully analyzing the plancherel distribution and proving a large deviation type result about the shape of the (finite) Young diagrams
The semicircle law and the limit shape of a random Young diagram are related in the sense that they are found as minimizers of closely related functionals. In the case of GUE random matrices the semicircle optimizes a quadratic form f -> + , while in the case of random Young diagram, the limit shape minimizes another quadratic form + . The difference between the quadratic forms is only in the linear part. If one studies the edge of the limit shapes related such quadratic forms (including potentials more general than V or W) one is guaranteed to obtain the Tracy-Widom distribution.
You didn't need to go the extra mile and explain the fluctuations. Just knowing the asymptotic behavior is usually good enough for these random processes.
@SpectralCollective 6 is less than 7, so the increasing subsequence is broken at that point. The longest increasing subsequence in "1276589" is "127", which is a length of three. The video seemed to include the "89" after "65" to give a length of five. Perhaps I don't know the definition of "subsequence " that is being used.
It's incredible how we've developed math able to distill the "uniform" parts of randomness into more deterministic objects at larger scales! I think this is pretty much the overall strategy as constructions like the central limit theorem - and just as beautiful. Hadn't heard of the Tracy-Widom distribution though. Great video!
I'd like to give an additional note regarding the end of the video:
In problems with a lot of independence, the normal distribution arises quite often (central limit theorem, for example)
This type of independence is intimately related to the commutativity of random variables: XY is distributed the same as YX
If we instead consider random variables that aren't commutative anymore (For example, random matrices), we get out an entirely different theory of probability, known as *Free Probability Theory*. This theory was only developed very recently in mathematics (1970-80)
The notion of independence we get is no longer the original E(X)E(Y) = E(XY), but a (more complicated) "Free Independence" which works for non commutative random variables.
It turns out, under this new theory:
- a central limit theorm exists, which is the SEMICIRCULAR DISTRIBUTION
- Random matrices like Wigner Ensembles have limiting distribution equal to the semicircle
Id recommend reading Chapter 1-2 of "Free probability and Random Matrices" by Mingo and Speicher to look at the relation between Commutative/Non commutative and Normal/Semicircular distributions
I cannot believe there is a book called "The Surprising Mathematics of Longest Increasing Subsequences"
Surprising, right?
This reminds me of my second problem in my first programming class : Find the longest and shortest, increasing and decreasing subsequences of uniform difference in a list of numbers. That list was not a permutation of an ordered list. Several numbers appeared multiple times. That was to be programmed in FORTRAN, submitted to a remote mainframe as batch work.
basically ancient competitive programming
"High level" science vulgarisation is one of the most beautiful things the internet era will have brought to mankind. This channel is yet another example out of many. Thanks a lot!
What are your other favourite examples?
he dropped a masterpiece and left, honestly i can't imagine the amount of work behind this video but i am grateful to be able to watch it for free so thank you
Thanks for watching! These videos do take a lot of work, but I plan to continue participating in the summer of math exposition so probably will keep making about one video per year
9:44 Also interesting here is the fact that these probabilities sum to 1 gives the neat result that the sum of the squares of the different numbers of Young tableaux equals n!. I had seen this before using representation theory of symmetric groups, but this is an amazing new perspective on it.
Great video. Regarding your comment at the end, about how in math you can go from not knowing anything about a particular field, to understanding the statement of an active research problem in about thirty minutes is really spot on and I couldn't agree more. One of my professors researches polynomial automorphisms. He explained to me, after my first year of college, what the field is about and the Jacobian conjecture in thirty to fourty minutes.. That's really how quick it can be to reach the edge of human knowledge.
I really liked the incremental introduction that lead to the frame at 1:30.
Just like last year, one of the better some3 submissions
Did not expect the Gaussian curve to show up at the end. I've kinda grown on it and the math of statistics in recent years.
This was a fascinating video. For something that seemed ludicrous to prove, like x×2^(1/2), you did a great job showing an intuitive proof for it. Very nice video!
When you reframe the problem as random points in a box, surely there's an issue with some points possibly being collinear. Perhaps it has probability zero so does not matter?
Any co-linearity occurs in a lower dimensional (affine) manifold of the full space, therefore probability zero, so the (finite) union of all possible co-linearities is still probability zero.
very good video, well done. i loved your percolation video and watched it last night to sleep. thank you. so good to see you make more maths videos
Eyy, I heard a little about the Tracey-Widom distribution when I was (misguidedly) trying to come up with a notion of a uniform distribution on the set of permutations over the natural numbers. Cool to see it again.
(I have since concluded that there probably isn’t such a distribution, because I’m pretty sure that that group isn’t compact under the topology on it one gets from viewing it as a limit of permutation groups.
So, the thing I was attempting presumably doesn’t work. But I do still wonder if, in the same way that there is no uniform probability distribution over the reals, the Gaussian distributions of increasing stddev are sorta kinda what one might naturally use instead as a natural prior over the reals, whether there might be a similarly natural family of distributions over permutations of the set of natural numbers?)
I'm trying to think of one, but so far I've got nothing!
How is the group of permutations of N a limit of permutation groups?
@@jake5331 you can embed S_n in S_{n+1} (so, e.g. {(1,3),(2,1),(3,2)} would get sent to {(1,3),(2,1),(3,2),(4,4)} )
And, with this directed system of groups and group homomorphisms, one can take the direct limit.
(So, take the union over all the groups, and then if one of the homomorphisms sends x to y, identify x and y. This works as a group because, for any two elements from different groups in the directed system, find a group where there is a homomorphism in the system from each of the two groups to that one, and then take the image of the two elements there, and then apply the group operation there.
This probably wasn’t a very good explanation of direct limits. Wikipedia has a better one.)
Permutarions of natural numbers are exactly like reals in cardinality so there is no wonder that there isnt uniform distribution for them
@@OMGYavani That doesn’t necessarily prevent it. The group U(1) also has cardinality of the reals (it is isomorphic to R/Z), and, as a compact group, it has a normalized Haar measure.
The issue isn’t one of cardinality, but is instead (I think) for the same reason that the group of integers under addition has no uniform probability distribution : because it isn’t compact.
It's always lovely seeing RSK and young tableaux in the wild! Haven't watched the video yet but am sure it would be wonderful.
How long did it take you to make the video?
This one took about 3 weeks of consistent work to make. I had been thinking about the script and coming up with ideas for animations for a few months before that though.
Very well done video! Thanks for pushing the frontier of my knowledge.
i love your videos so much, you are able to implement a clear explanation with amazing visuals that catch the eye, and thereby the attention. Are you planning to cover different subjects other than graph theory related stuff? I'd love to see what you are able to do with number theory or abstract algebra, but again keep up the good work!
Thank you! I (Vilas) am currently a PhD student studying probability theory, so it’s unlikely that I’ll make a long video about anything too distant from my research. Not impossible, but don’t get your hopes up!
@@SpectralCollective Oh thats cool! I'll take this as motivation to maybe make something myself! I'm still studying in high school but I managed to teach myself a lot of algebra and number theory, and the more incomprehensible a definition or a theorem is, the more I want to go down the rabbithole. Since on youtube I can't always find everything I wanna know, I'm looking forward to produce something by myself, and you're videos are just the perfect example of what I would like to do! You really deserve a lil more attention in the educational maths community.
I cant remember who the quote is attributed to but in a math book i read a few years ago there was a great heuristic about rigorous mathematical proofs: "you should never try to prove something whose truth is not almost obvious"
Very interesting video! I have a couple of questions if you don't mind.
At the end, the crystallization animation has white diagonal lines. Is this a visual artifact?
Should the Robinson-Schensted algorithm feel intuitive (could I have come up with it)? I was surprised that Young tableaux/diagrams were the key to that proof.
Interestingly enough, Young diagrams are absolutely necessary to understand the representation theory of the symmetric group. Perhaps permutations and Young diagrams have a deeper connection than I thought.
The "crystal" simulation is a model called ballistic deposition, where blocks are raining from the sky in columns (like tetris) but the blocks will also stick to each other on the side. Every white pixel is a hole in the crystal caused by some blocks not falling all the way to the bottom of their column. The lines that you see are actually emergent behavior, and I can't really explain why these "canyons" form. Here's a cool video about this model: czcams.com/video/Z6XP3n-Sjiw/video.html
I wouldn't say you should be able to come up with the Robinson-Schensted algorithm by yourself necessarily, it's not that obvious. But it is only one step away from something called "patience sorting" which may be easier to come up with.
Great video! Is there some simple heuristic/intuition why the constant is equal to 2? If you approximate the process by a uniform grid of points, it looks like the constant is in that ballpark but I am wondering if there is a more precise heuristic argument one can make.
The heuristic in the video explains why the constant is equal to 2: the maximal length up-right path through a box of area n has length 2*sqrt(n)
Another masterpiece!
Beautiful work
This is the best video I've seen this month. Been trying to find a book on mathematics behind algorithms. Like proofs and such things. Can you recommend any similar books?
One minute and my brain already hurts
I'd love to see a vid on the connection between the table structure and the representation of the symmetric group briefly mentioned
At 11:45, shouldn't the Limit Shape Theorem state that the probability goes to 1?
Yes, it should, good catch!
wake up babe new spectral collective video just dropped ❤❤
I'm currently researching Random matrix theory (although a different area) and I love this video!
I knew about the longest increasing subsequence problem before and its relation to TW, but I didnt know how that connection was made.
However, Young Tableaux arise in relation to non-crossing partitions of sets, which again are related to GUEs. I'm wondering, is the Young Diagrams limit shape being semicircular related to the Semicircular distribution?
Actually, the curved portion of the limit shape is not quite a segment of a circle, so I don’t think this is related to the semicircle law at all. The proof of the limit shape theorem works by carefully analyzing the plancherel distribution and proving a large deviation type result about the shape of the (finite) Young diagrams
The semicircle law and the limit shape of a random Young diagram are related in the sense that they are found as minimizers of closely related functionals.
In the case of GUE random matrices the semicircle optimizes a quadratic form f -> + , while in the case of random Young diagram, the limit shape minimizes another quadratic form + . The difference between the quadratic forms is only in the linear part.
If one studies the edge of the limit shapes related such quadratic forms (including potentials more general than V or W) one is guaranteed to obtain the Tracy-Widom distribution.
Fantastic video!
Awesome video!
this is so cool
OMG - there is a whole book about it ???
Yes there is! And it is very detailed and well-written…
your video quality is amazing, also what font is that?
It’s just the standard LaTeX font
what are the possible applications of that subject, please ?
11:41 so it isn't square with a quater circle cut out?
That’s right, the curve is not a quarter circle
You didn't need to go the extra mile and explain the fluctuations. Just knowing the asymptotic behavior is usually good enough for these random processes.
I think it depends on what you're trying to do with it. Personally, I find the fluctuations interesting as well!
fantastic animation. how did you do it? also very clear and well explained.
Almost all of the animations were made using Manim, which is a python library for mathematical animation
Why doesn't the "65" in "1276589" break the subsequence to be a length of three?
What do you mean?
@SpectralCollective 6 is less than 7, so the increasing subsequence is broken at that point. The longest increasing subsequence in "1276589" is "127", which is a length of three. The video seemed to include the "89" after "65" to give a length of five.
Perhaps I don't know the definition of "subsequence " that is being used.
Oh I see, yes in this video a subsequence doesn’t have to be contiguous, there can be gaps
can you make a video of just the zooming out of a box
that animation takes quite a lot of computer time to make, so probably not in the near future, but maybe eventually!
Babe wakeup
Before watching the video let me guess what this video is about by the title: my guess is the Erdos-Szekeres Theorem
not exactly, but that theorem is quite related!
@@SpectralCollective yea but this topic is also very interesting, nice video!
First!
I liked your visualisations. Can you share your code for this video? I assume you are using manim, a git repository would be ideal. 😊