- 5
- 454 733
Spectral Collective
Hungary
Registrace 10. 08. 2021
The Longest Increasing Subsequence
CLARIFICATIONS/ERRATA:
* In the limit shape theorem, the probability should tend to 1, not 0.
* Technically, the random matrix shown in the video is a GOE matrix (it has real entries) not a GUE matrix (which has complex entries). The Tracy-Widom distribution being discussed here corresponds to GUE, not GOE, but I found that a matrix of complex numbers wasn't as nice to look at so I cheated a bit with the animation.
* Not every optimization problems over independent random noise is expected to have Tracy-Widom fluctuations, but many of the models that are expected to have such fluctuations can be phrased as optimization problems.
--------------------------------------------------------------------
This video assumes that the viewer has taken a course in probability theory. I hope it is still somewhat understandable and enjoyable even without that prerequisite, but for brevity I needed to take for granted many of the concepts usually covered in such a course.
For more details, check out "The Surprising Mathematics of Longest Increasing Subsequences" by Dan Romik. The cover of this book was used in the video with the author's permission.
This video was made by Vilas Winstein, with music by Aranka Hrušková. It is an entry in the third Summer of Math Exposition (#SoME3).
--------------------------------------------------------------------
Chapters:
0:00 Introduction
1:36 Heuristic
6:21 Proof Idea
13:18 Fluctuations
16:14 Conclusion
* In the limit shape theorem, the probability should tend to 1, not 0.
* Technically, the random matrix shown in the video is a GOE matrix (it has real entries) not a GUE matrix (which has complex entries). The Tracy-Widom distribution being discussed here corresponds to GUE, not GOE, but I found that a matrix of complex numbers wasn't as nice to look at so I cheated a bit with the animation.
* Not every optimization problems over independent random noise is expected to have Tracy-Widom fluctuations, but many of the models that are expected to have such fluctuations can be phrased as optimization problems.
--------------------------------------------------------------------
This video assumes that the viewer has taken a course in probability theory. I hope it is still somewhat understandable and enjoyable even without that prerequisite, but for brevity I needed to take for granted many of the concepts usually covered in such a course.
For more details, check out "The Surprising Mathematics of Longest Increasing Subsequences" by Dan Romik. The cover of this book was used in the video with the author's permission.
This video was made by Vilas Winstein, with music by Aranka Hrušková. It is an entry in the third Summer of Math Exposition (#SoME3).
--------------------------------------------------------------------
Chapters:
0:00 Introduction
1:36 Heuristic
6:21 Proof Idea
13:18 Fluctuations
16:14 Conclusion
zhlédnutí: 51 608
Video
Percolation: a Mathematical Phase Transition
zhlédnutí 349KPřed rokem
SOURCES Percolation - Béla Bollobás and Oliver Riordan Cambridge University Press, New York, 2006. Sixty Years of Percolation - Hugo Duminil-Copin www.ihes.fr/~duminil/publi/2018ICM.pdf Percolation - Geoffrey Grimmett volume 321 of Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. Springer-Verlag, Berlin, second edition, 1999. NOTES Note at 10:42 -...
Mathematical Animation with Manim - Lecture Recording
zhlédnutí 6KPřed 2 lety
Lecture by Vilas Winstein at the Alfréd Rényi Institute of Mathematics on 2022/02/16.
The Canopy Tree: An Example of a Graph Limit
zhlédnutí 8KPřed 2 lety
In this video, we compute the Benjamini-Schramm graph limit of the sequence of complete finite binary trees. If you don't already know what Benjamini-Schramm convergence is, please watch our previous video, which gives an introduction to the concept.
What is the limit of a sequence of graphs?? | Benjamini-Schramm Convergence
zhlédnutí 41KPřed 2 lety
This is an introduction to the mathematical concept of Benjamini-Schramm convergence, which is a type of graph limit theory which works well for sparse graphs. We hope that most of it is understandable by a wide audience with some mathematical background (including some prior exposure to graph theory), but to get the most out of the video it is helpful to know some probability theory and genera...
This was really neat and also very soothing? Love the oboe in the background :)
It's a clarinet 😉
@@arankahruskova4433 dang and I was so sure lol
Great work! Can this theory be applied to Neural Networks to understand why/how they work, since so little is understood from a theoretical POV?
This is a nice video. Thankyou
Love tjis
Brilliant video. I love the background music.
thank you vilas for bringing your video to my attention. i enjoyed it very much. and it brought to mind a question i had, even from back in my days of physics and math - although it has become more sharp or clear in my mind in recent years: the assumption of independence. within mathematical modelling that is used to simplify the math. and yet, with the physical reality of what guatama called 'dependence co-arising' or what heisenberg called 'the uncertainty principle', that is an assumption that will forever keep the model outside the bounds of the experience of the real material world. have mathematical modelling been done to assume that the 'decison-action' of gate affects that of neighbouring gates? guy from oaxaca.
Great video! Congratulations on your outstanding work. If I weren't already in love with percolation, your presentation would surely win me over 😉. Hugo Duminil-Copin
Beautiful subject! I admire the way you presented it.
Keep up the lessons yun blood. Imma go percolate to burger king get me some chicken. West side!
The discussion of infinite clusters in this video was quite confusing to me. I think it would have helped to define that term, rather than simply stating that it takes over. Is an infinite cluster just the one that grows to fill the entire field when p=1? It seems pretty clear that there can only be one for a given set of probabilities, so the question at 9:53 threw me off. Perhaps the infinite cluster is the one that's the largest for a given value of p? Or one that connects to all four edges of the field?
suppose there's an infinite number of nodes. we might imagine that there's an infinite subset of such nodes that are connected. for visulasiation purposes you might think of a square lattice with random connection that are infinite
Gracias por tu video.
imagine how understanding this concept and social networking/information could augment one's ability. Lucy!!! You have some percolating to do!! Oh Ricky!
Just came back to this video when I remembered how impressive this video was to me. Just Bernoulli percolation per se is already interesting in and of itself, but once he mentioned how this relates to states of matter, I truly had my mind blown!
Thanks for sharing such an insightful video!
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.
Brilliant exposition! And ... some questions. I can understand assuming uniform distribution but! What if the original space had a 2d or 3d Gaussian distribution with one set of parameters and incoming changes all had a revised 2d or 3d Gaussian distribution. All, of course, acting on a nearest neighbor basis. Additional complexity?: as time evolved nearest neighborhood changes also compete with random introductions of the alternative phase within its neighborhood. In other words there are probabilities of change in each similar percolation region by (a) nearest neighbor influence and (b) randomness such as a change like a random parachute landing of different color. So all told, 4 variables. Gaussian 1 and 2, Randomness 3 and 4 with all 4 having potentially similar or different variables?
Very succinct and pretty modelling. Thanks for the upload!
this is so cool
The area of an nxn square is n^2, not n as stated around 6:00. This implies that the Poisson process is not the correct model for a random permutation as the number of points is proportional to the area, not the side.
The square has side length sqrt(n), not n.
@@SpectralCollective The square has the side of the given sequence, n. We are trying to prove that the longest subsequence is 2 sqrt(n). The square thus has an area of n^2. If you change the side of the square to sqrt(n), then you are trying to prove that the longest subsequence is 2 sqrt(sqrt9(n)). It doesn't improve your situation.
Awesome video!
Hello! This video is great-- can anyone/in the comments help me to understand which program can be used for the 3D visualization of the cubic lattice like that? Thank you!
my head exploded
10:27 >_>
It's like infinite small raindrops drops on an infinite grid, from no drop to full up. It may have some dry area everywhere, but there are going to be a huge body of water someplace. And in certain situation, it well be infinitly large.
Its time 4 da percolator
This is an amazing, topical video. thank you!
bong
10:59 And so the best texture in Doom is born
How do you do the simulations?
Wokeism is everywhere now - even matter is transitioning to something it more readily identifies as
In what sense is the ability of simple rules to give rise to complex behavior in need of explanation. You apply the rules and it does. Why would you expect that wouldn't be possible? I mean, it feels like asking how can big prime1 x big prime2 = n (all in base 10). That's what happens if you apply the rules and what would have made you expect it wouldn't?
Perhaps the question should rather be: what characteristics do "simple rules" have to have in order to allow for complex structures?
Came here for perculation, got a map of the Holy Roman Empire at 12:28.
Indeed there was a kind of percolation going on within this empire due to marriages between all these princes (mergers) and divisions due to succession, governed by statistical processes. Nice observation.
I am wondering, if the system is in a state, where an infinite cluster exists, and I chose a random node in the graph, what's the probability of this node being part of the infinite cluster? I'd assume it depends on the p of the current system, as when p = 1, all nodes are in the cluster, but what happens for pc <= p < 1? Since the graph is infinite, there should always be an infinite number of nodes that aren't part of the infinite cluster, but at the same time there is an infinite number of nodes that are part of the infinite cluster... so... would it just always be a 50% chance?
What a beautiful proof due to Peierls, and a terrific explanation of it by yourself. Thank you for the last 27 minutes.
I am a simple man, I see percolation, I want coffee, I click like
what are the possible applications of that subject, please ?
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!
What is the power spectrum of cluster sizes? I wonder if there's some connection to the CMB power spectrum/Baryon acoustic oscillations at the critical parameter?
That's what you see when you have anemia
A minor remark for 13:39. All compact metric spaces are separable so one does not need to hypothesize separability in the statement of Prokhorov's theorem.
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
"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!
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?
14:00 I understood until this time-point.
same
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.
There's always a mathematical pattern hidden behind probability 12:13 czcams.com/video/sHCZkSBPIS0/video.html There too, some symmetry is hiding in rescaling.
1:00 335/113 is a terrible approximation of pi, being as it's 2.964...
Yep that was a typo. It should have been 355/113
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
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"