If it probably exists, then it does
Вставка
- Опубліковано 23 лип 2022
- This is my individual submission for #Some2
Follow me on Tiktok! / sackvideo
Resources on the probabilistic method:
en.wikipedia.org/wiki/Probabi...
2012.cccg.ca/papers/paper13.pdf
www.cut-the-knot.org/Probabil...
theory.stanford.edu/~jvondrak...
www.amazon.com/Probabilistic-...
Corrections:
At 3:45 the last 2 lines should read "2^(k/2 + 1)
At 3:57 the "s" should be a "k"
"Did you do your math homework?"
"Well, there's a nonzero chance that I did."
"Fair enough. A+."
"I'm your son's maths teacher, Mr. Ian, but you can call me Al. I sometimes pretend to threaten my students with impossible problems to see what they can achieve."
Doing one's homework isn't the same as CORRECTLY doing one's homework. So the median: C.
@@ericdew2021 well there is a probability that i did my homework correctly. That means i did.
@@M1551NGN0 And there is a probability that you incorrectly did your homework, that means you did. A basic symmetry argument.
@@mathlitmusic3687 there is a probability that there is a probability of me doing probability
Ramsey is such a cool figure. Published so little but everything he published was super impactful.
Were all his titles super vague?
Not only he can can cook but also sick maths
@@DynestiGTI In olden days, it was quite common to publish with titles like "on a problem in set theory" "on a problem on polynomials" etc. So yes, most probably.
He should have done more meth like Erdos.
virgin mathematician: "Prove its existance!"
gigachad mathematician: "It can exist, therefore it does."
I think it's more like saying "The probability measure function must have measured some event where it exists, therefore it exists."
Modal realists: This, but unironically
yea, if i exist, i am
Or rather, it says "it can't not exist (else its P=0), so it does exist."
@@mathlitmusic3687 but how? a fair coin toss has a non zero P, but still can land tails, right?
You clearly know your stuff, and this is an interesting topic, but your content might benefit from longer videos where you go into more details about your explanations. I found that most of the things you were talking about went over my head, not because I don’t think I’d understand, but because it was glossed over too quickly.
Yeah, that
yup either make it more simple and easier to understand, or go longer with more details so we have some more time to think about it.
Or because I'm wasted
You wouldn’t understand
Totally agree. Great content/topics, pacing needs work.
This is such a well made video! One of my favourite some2 submissions - you had me hooked the entire time!
Glad you enjoyed it!
@@ASackVideo reads title. Probably a billion usd in my bank account, checks account disappointment. click bait title
so well made that I can't understand what the fuck he's talking about
@@ASackVideo Since TROCKA ARE DIRTY AND SHOULD NOT COUNT.how.can you solve it without the damn trick??
@@ASackVideo Thanks for sharing Inhave nonidea what Some 2..are you a mathematician?
My dad probably exists
w
He probably went to get milk.
Your presentation skills are on point. The pace at which you tackle this is anything but. Most of the video flew way over my head, it'll take like 5 rewatches and a lot of pausing for me to actually take in the math. I reckon some people got a lot out of it though, but I only really got a very broad overview.
Yeah I had to play in 1x speed and rewind a lot of times to justify the details of his examples. He glossed over a lot.
@@megamaser You had to play in 1x speed? Isn't that like.. the normal speed?
@@onecommunistboiListening to a lecture at the speed it was spoken is like watching paint dry, unless I'm actively engaged in a dialogue, then I need them to go slow so I can formulate my responses. My default is 2x to maximize efficiency but I scale it down as needed for full comprehension. Rarely go below 1.5 unless they have an accent or it's really dense or complicated. A lot of my friends do the same so I'm not sure what's "normal".
@@megamaser My roommate does like 3-4x speed, and then pauses for meaningful amounts of time in between to think, while I tend to 1x speed with liberal amounts of skipping parts (or just don't watch the lecture at all and skim the notes). Different strokes for different folks
@@megamaser I get that, and oftentimes I do that too.
Still I think it's weird to say a lecture is too fast because you have to watch at the intended speed:D
Wouldn't it make more sense to say all the other lectures are slow?
Just found this channel. Good stuff! Most of this went over my head but you present math in a very approachable manner! Can't wait to see more videos of this sort of stuff.
Nature: Whatever is not expressly forbidden is required.
An absolutely brilliant video of an intruiging topic with crystal clear explanations. Looking forward to see more of your content in the future!
The hardest problem for mathematicians, social interactions. i'm dead 💀
Great video, no filler at all and got straight to the point. Awesome!
Thank you for making this short enough to fit my attention span! Fascinating stuff.
this video blew my mind, really well done
This is the kind of thing that motivates me to study more math. What an amazing concept!
So happy that I stumbled upon your channel. Great video, good content.
UA-cam recommended me this. Although I didn't follow all the numbers I got the concept, which was extremly well explained! I like it!
0:50 Yet more proof that hexagons are, in fact, the bestagons
The covering points with disjoint unit disks problem has been my favorite for the past few months. I hope to see progress made on it, but I'm not super optimistic given that the last progress made was in 2012.
What if there are dots covering ~ 90.7% of the paper? Like somany dots packed together, but still covers less area compared to coins?
I might be wrong but i don't expect coins to cover all dots in that case cos coin areas aren't spread like dots, cos coin areas are like small concentrated chunks
@@GiggityGlen what do you mean by dots covering 90.7% of the paper? Dots don't cover anything, they have no area...
Fair point, what if the dots are like rational numbers? Take any small area, there's infinite points in there but there are more space to fill
@@GiggityGlen well yeah even points at all rational coordinates have no area because they're countably infinite
Yo, agree, but my point is the coins won't be able to cover all the points.
Well if there are also infinite tiny coins, they might cover actually. Nvm I'm drunk 🥴
Where did you first come into contact with this kind of method of proof? I remember that my first exposure to similar ideas to this was in a grad course on graph theory, but I assume there are other avenues of entry as well? In either case, it is a truly surprising way to prove mathematical statements, and I think the video did a good job of explaining how absurdly powerful the technique (that feels like it really shouldn't work) actually is. Good luck in SoME2, I think this video deserves to do well.
Thank you! I learned this in a grad course on the probabilistic method.
for me it was an CS undergrad course in probabilistic algorithms
Yeah, also first encountered this in graph theory. Specifically, the probabilistic proof that every graph G with m edges has a bipartite subgraph of at least m/2 edges.
For anyone who hasn't seen it:
For each vertex in G, randomly assign it a colour (red or blue) with equal probability. Now, for each edge, there are three possibilities:
1) the edge joins two red vertices (prob = 1/4)
2) it joins two blue vertices (prob = 1/4)
3) it joins a red and a blue vertex (prob = 1/2).
Define a subgraph H with vertex set equal to that of G, and edge set consisting of all edges that join one red and one blue vertex. The random colouring of G is a 2-colouring of H. Since each edge is in H with (independent) probability 1/2, the expected number of edges in H is m/2. Thus there must be at least one colouring of G that results in a subgraph of at least this size.
My first introduction to this was primality tests. In my CS data structures course, a few of the assignments were about implementing bignums (for storing and operating on huge integers, like > 2^64), and one of them was about checking whether the number was prime.
Brute-force tests using traditional methods are not possible at that scale, but there are probabilistic tests like Miller-Rabin that determine either that a number is definitely composite or that it may be prime. It has another integer input that is a random variable. For prime numbers, all random seeds will give you the same "may be prime" outcome. For composite numbers, there are some fraction of the random seeds that give you the "definitely composite" outcome - they are "witnesses" to the compositeness of the number. You repeat the test with different random inputs until either you find a witness, so it is composite, or you reach a certain number of iterations where the probability of it being composite despite not finding any witnesses is so astronomically low that you can assume that it is prime.
Make a video on p-adics
Saw u on TikTok, feeling great to find u here on UA-cam
Thanks for sharing these contents. You're doing a great job.
I actually needed this to win an argument, so thanks.
Really enjoyed this! If you feel like making more videos in the future, please do!
I was staring at the equation at 2:47 and couldn't see it... until I realized that if you draw a graph with k vertices, then you can just have a binary sequence like (0,1,0,0,0,1,0,1,...,1) with a term for every place an edge could possibly go, with 1 indicating the presence of an edge and 0 indicating the absence of an edge, and there are clearly 2^m such sequences, one of which represents a clique, so the chance of a clique is 1/(2^m) where m is the number of edges in a connected graph with k vertices.
This is so incredibly silly, I love it.
It makes sense but feels wrong, like a cheap party trick.
Lovely video. The actual bit at the end is honestly super cool.
Please do more of this they are really intresting
Ramsey Numbers we’re so unlearnable for me when I first took a graph theory class, I ended up dropping the class, but this video gave me so much more understanding, and I’m so glad because I’m retaking graph theory this upcoming semester!
a lot of this went right over my head
0:58 I don't understand how a packing efficiency of 90.7% means that on a random shift the E[# covered] is 9.07 for all possible configurations of points.
Why isn't it that for some configurations of points E[# covered] is < 9.07 and > 9.07 for some others?
Interesting video, btw :)
This uses a property called “linearity of expectation.” If we let X_i be 1 when point i is covered and 0 otherwise, then E[X_i] = .907.
X = X_1 + … + X_10 is the total number of points covered and by this property, E[X] = E[X_1] + … + E[X_10].
@@ASackVideo But doesnt the expected value assume the dots are randomly arranged? Why would we not assume there might exist an intentionally arranged configuration that will always fall outside of this packing grid arrangement? Even if the expected value of a randomly arranged 10 dots would have slightly over 10 dots covered, that doesnt mean 10 intentionally placed dots can fully be covered. There may exist specific situations where the expected value should really be 9 for some specific arrangements of ten dots.
@@eragon78 we computed that for every arrangement, the expectation of shifting the hexagons is 9.07 using this linearity of expectation property.
@@eragon78 ....no. What it assumes is the random position of the coins. Try to look from the perspective of each and every single dot instead as say the hexagonal coin packing configuration is shifted across every possible position. Of those possible positions, exactly 90.69% of them will cover the dot and the rest doesn't. This is true for every single dot, making the average coverage be necessarily 9.069 dots across all packing position. The rest of the argument is the same as in the video.
P.S.: I wonder if this will make it more clear... I wish I could visualize it but for now I will just try to explain with words. Keep track of the center of one coin across the space of all possible possibilities for the packing patterns; which is in the shape of -an equilateral triangle- _a parallelogram made of two equilateral triangles_ whose side is equal to the diameter of the coin. Now look at one dot, and color the paralelogram with red and white such that if the center of the coin is in red it means the dot is covered by the hexagonal packing otherwise not. You will find that 90.69% of the paralelogram's area is going to be colored red. Do the same thing for all dots -- the result will be the exact same; it's just that the position of the white area will be different. In any cases, the total sum of the red areas from all ten paralelograms will be 9.069 paralelograms. Now stack all of the paralelograms above one another and try to look at every single point of the paralelogram stack, and evaluate for any single point how many layers are colored red (imagine suppose we are 'compacting' the red areas down). Since the total sum of the areas is more than 9 paralelograms, it is necessary that there are some points in the paralelogram stack where all ten layers are red.
P.S. 2 (5 days after original comment): I made a desmos interactible for fun: www.desmos.com/calculator/l3zhktbwez
I originally made this for fun although I decided to share this to disprove someone being confidently incorrect before, although fotrunately the reply in question has now been deleted lol
@@Anonymous-jo2no no, i think I see it now. I did some more thinking into it and I think I understand now.
I was getting confused because I was thinking of another similar problem this kind of reminded me of. There are some key differences though which is why it doenst apply.
But I was thinking of that one problem where you have 100 boxes numbered 1 through 100 and also 100 slips of paper 1 through 100 and randomly place them into each box. Then you get 100 people each 1 through 100 and they have to go into the room one at a time and open 50 boxes. If ANY SINGLE person of the 100 fails to find their number, the entire group fails and is executed. However, there exist a strategy for this game where you can couple the success/fail together and instead of each person succeeding or failing independently of each other, they all succeed or fail at the same time. If you havent heard of this problem, the solution is to have everyone follow a loop starting with the box of their number and going to the next box that the paper inside each box they open says. So if they are number 13, they start on box 13, if box 13 has a paper with 84 on it, they open box 84, etc. This means the ENTIRE group will succeed if there are no loops of 51 or greater, or the MAJORITY will fail if there is a loop of 51 or greater. This couples all their win/losses together. Each individual person still has a 50/50 chance of being victorious or not, but that win chance is no longer independent of the other contestants. This method gets you around a 1/3 chance of success iirc.
Of course I do see now some of the key differences. Each person's individual chance of success is still 50%. It doesnt change by coupling them to the success chance of other people.
So for the dots, since the chance of being covered is greater than 90%, this means that even if they are coupled, they MUST retain that 90.7% chance of being covered on a random shift of the coin grid. The only way this is possible is if there exist at LEAST one situation in which all 10 coins are covered. So I do see the solution now. I was just confusing myself at first by drawing analogies to another problem it reminded me of, but thinking deeper about it I see my mistake now.
Thanks for the explanation though, helped me see my mistake.
Ah yes, the quintessential fractal, where the title describes the video and vice versa
Just finished watching, this was absolutely great! Super engaging, super informative, super intriguing
Thanks for the video.
Another book on the topic that might be useful for anyone interested in computer science is "Probability and computing". I'd especially recommend this book to anyone who is curious about theoretical aspects of machine learning - the new version has a chapter on the famous Vapnik-Chervonenkis dimension.
and this is exactly why I stopped going to parties
Excellent! Finally a short and fast math video!
(Like a one-page proof... You have to reread it twice, but at least it doesn't take two hours. And there aren't those annoying musical interludes!)
The really wild thing is that there are constructive proofs of certain theorems in probabilistic combinatorics (see: constructive lovász local lemma). You can then follow the proofs of these constructive probabilistic theorems to generate examples that witness the existence you are proving! This has been done recently to prove sharp bounds on certain counting problems.
This is so interesting. I like speed but I didn't understand it well. A follow up would be great going through the examples more slowly
Very interesting, and such a good exposition.
Ooo I feel so early to what is clearly about to be a huge channel. pre-congratulations.
thanks a lot!!! so nice reverb
hmmm can't wait to see this channel evolve
i really like the pacing. i wish my uni lectures could go at that speed lol
For some reason, I assumed this was a big video made by a decent size channel with 10K subscribers at a minimum. This is good content for such a relatively low number.
May the algorithm bless this video.
Ramsey numbers example was very cool
Another amazing video! :)
That quarter example is wild. Holy frick.
This sounds like the premise to the finite and infinite probability drives in the hitchhiker's guide to the galazy.
This is amazing, keep going :)
As you've said, this method pops up a lot in Ramsey Theory and of course was used immensely by Paul Erdos.
In particular, my favorite application is one I sadly don't remember the details of...but this was showing that there exists some graph with 2 different properties P1 and P2. You do so by showing that the probability of a graph having P1 is > .5 and the probability of it having P2 is also > .5, which means that there must be some graph that has both properties.
I'd love if someone reminded me what the specifics were! Something like "there exists a graph with chromatic number k and largest independent set size m..." but maybe something less related...
And I'm almost positive I found this in van Lint and Wilson's "A course in Combinatorics"
Last note - Ramsey graphs are incredibly interesting and cleverly built! Easily one of my favorite things from Ramsey Theory.
You might be thinking of the proof that there are graphs with arbitrarily large girth and chromatic number? (You’re right, that is a really fantastic application of the technique!)
@@zachgz That's 100% it! Thank you so much!
It's like the pigeonhole principle, but used for continuous things.
Cool concept!
That trick with the expected value is simultaneously the most cursed and incredible thing I have ever witnessed.
0:49 i think you just blew my mind
If u get the entire party stoned enough than they all click
This video is really cool and I defently enjoyed it but I think you really need to slow down a bit. The explanations were well done but felt a bit rushed out so I had to pause every few seconds which kinda destroyed the flow of the video :/
You can slow the video down using the UA-cam settings. You can slow it down all the way to 1/4 speed.
@@jjjccc728 yea..sure..
Yeah agreed, I think the content was very good, but the delivery was a bit too rushed.
really interesting concept thanks
This is fantastic!
Amazing video dude
Thank you!!
This was really interesting!
I’m going to have to revisit this video at a later date. It’s 2am and my head hurts, but it sounds like there’s a possible application to the happy endings theorem.
“Yeah, it might. Therefore it does.”
I now understand what my poor dog must go through when I talk to him
😅
This Ramsey guy must be fun at parties
Ohhh, I always use this when answering my exams!
The Pentagram of Social Interaction
I knew it all along
I thought this was going to be a discussion on modal logic, but I was pleasantly surprised to learn something new
@Michael Ah, but possible necessity entails necessity, so logicians are always looking within the weak sauce for the strong sauce
I have no clue why this was recommended to me but I enjoyed feeling my brain break in real time
one of the best videos
Beautiful video
i'm impressed, you managed to mention ramsey and the r of k problem without bringing up graham
This just came on my recommended and I start my first stat and prob class tomorrow, kinda scared ngl
Man that erdos quote was so good. How have I never heard it?
My combinatorics professor must have said that quote at least 3 times during the semester, on the multiple separate occasions that he brought up Ramsey numbers 😁
It also becomes invaluable when dealing with quantum mechanical probability states.
When you have eliminated all which is impossible, then whatever remains, however improbable, one must be the truth
I love this information, but the video was so fast paced. I would really like to see similar stuff explained with further detail in 10-20 minutes.
Reminds me of the classic joke:
An engineer is working at his desk in his office. His cigarette falls off the desk into the wastebasket, causing the papers within to burst into flames. The engineer looks around, sees a fire extinguisher, grabs it, puts out the flames, and goes back to work.
A physicist is working at his desk in another office and the same thing happens. He looks at the fire, looks at the fire extinguisher, and thinks "Fire requires fuel plus oxygen plus heat. The fire extinguisher will remove both the oxygen and the heat in the wastebasket. Ergo, no fire." He grabs the extinguisher, puts out the flames, and goes back to work.
A mathematician is working at his desk in another office and the same thing happens. He looks at the fire, looks at the fire extinguisher, and thinks for a minute, says "Ah! A solution exists!" and goes back to work.
You explained this perfectly.
I'll take your word for it and get ready to fight the aliens
Nice work sir :)
In my opinion the probabilistic method becomes more intuitive when you look at the converse version. If the probability is less than 1, then your set can not cover all cases. It is all about finding a sense of volume by which your set of interest has strictly less volume than the whole space, implying it can not cover the whole space and hence there exist points not in your set
Slight issue is that the volume of "valid entries" can be 1, but still be unequal to the entire sample space.
@@KGafterdark Well I am only saying that if the volume is strictly smaller then you will not cover all cases, you raised an issue with the reverse implication, if someone were to claim it.
"Well, it probably, probably exists"
I had to stop only because I was worried my brain was gonna explode
1:32 yo he’s tryna summon the stats demon
szekely et al 1998 proof of a bound on the min crossing number takes the probabilistic connection further by implementing the Expectation, showing that this method is not limited to just considering the base probabilities. and it was a rather complicated proof by Erdos and Szemeredi which was purely geometric that this superceeded. it works for graphs and is super short (from the book).
Writes a book about a party.
The party: Okeeeee lets gooooooo
Some nerds were really overthinking going to parties.
Reminds me a little of Anselm's ontological argument
Just to clarify the argument in a way I can follow. For some configuration of 10 points there is a probability Pi that exactly i points are covered by disks. The expected number of points being covered can then also be calculated by Sum(i*Pi)=P1+2*P2+3*P3+...+10*P10. If for any configuration P10 were to be zero, then that sum can at most be 9 (when P9=1). Since another method of calculating the expected number of points being covered resulted in a value higher than 9, you know that P10 cannot be zero.
If you were dealing with a configuration of 11 points though, you cannot use this method that easily. Because 11*90.7% = 9.977 < 10, so it could be that that P11 is zero if P10>0.977. But if you can prove that P10 must always be smaller than that, then I guess you can prove that 11 points must always be possible to cover as well.
*Mathematics:* "You should fight aliens."
Feel like there's some sort of mean-spirited joke I could make here but I'm not going to
1:10 Had to watch this twice to understand it, then it was like ..."wow, brilliant"
What??? I came out more confused than when I went in.
is this like continuous pigeon hole?
It has a similar flavour. In my mind, at least.
I was bored scrolling down the recommended page and saw this, now my brain hurts and I still don’t know anything he said
I’m getting flashbacks to the Improbability Drive in Hitchhiker’s Guide to the Galaxy.
As I remember the passage:
The galaxy’s smartest minds had given up on the drive, deeming it all but impossible. An interning grad student figured that if it were ‘nearly impossible’, it must simply be ‘very, very unlikely’, and calculated the odds of it being spontaneously popped into existence. He then fed the resulting number into an existing machine best known for transporting guests’ undergarments two feet to the left at parties as an ice-breaker, and the Improbability Drive popped into existence.
He later ‘disappeared mysteriously’ as, well, nobody likes a smartass.
Me using this method as a kid when my parents told me monsters don't exist. (A lot of existential dread as a child.)
This title and video reek of a video that'll eventually get millions of views
"hardest problems for mathematicians, *party planning* "
You are the only person I've seen pronounce "aliens" like I do
0:35 we can use smaller coins.
The probabilistic proof for the quarter problem works for n
This theorem also pops up in metaphysics in a modified way. 35 years ago when studying the Meditations of Descartes, we discussed the comments on his notion of a 'clear and distinct idea' having the attribute of existence. This is the famous 'unicorn' argument. Long story short, the position of his logic meant that 'if it does exist, it will exist in exactly the way we perceive it to be'. Once you develop this in a more modern context you come to the dilemma of existence before perception. With other words, only if you can think of it, can it be. Needless to say that for metaphysics this has all kinds of implications because it suggests existence creates itself.
Fucking awesome video of a genius concept