An unexpected application of the harmonic series
ฝัง
- เผยแพร่เมื่อ 25 ก.พ. 2020
- Sign up with brilliant and get 20% off your annual subscription: brilliant.org/ZachStar/
STEMerch Store: stemerch.com/
Support the Channel: / zachstar
PayPal(one time donation): www.paypal.me/ZachStarYT
►Follow me
Instagram: / zachstar
Twitter: / imzachstar
Animations: Brainup Studios ( brainup.in/ )
►My Setup:
Space Pictures: amzn.to/2CC4Kqj
Magnetic Floating Globe: amzn.to/2VgPdn0
Camera: amzn.to/2RivYu5
Mic: amzn.to/35bKiri
Tripod: amzn.to/2RgMTNL
Equilibrium Tube: amzn.to/2SowDrh
►Check out the my Amazon Store: www.amazon.com/shop/zachstar
Man it's really bothering me how these cars are driving on a "1 lane road" that's clearly drawn as a 4 lane road and all of the cars are twice the size of the lanes and they're driving on top of the yellow line.
😂
I'm glad I saw your comment 3 years later, had a good laugh because I genuinely did not realize this until I read the comment and went back in the video
Math quickies are my favorite kind 😫
🥵🥵😏
in England, "Quicky" means something else altogether.
@@klam77 i think that might be the joke
@@klam77
1) Quickie/Quicky means the same thing no matter where you are.
2) Congratulations, you just figured out the joke.
@@whannabi Lol yeah
Transit regulations don't approve how you represented "one single lane in which you can't pass other cars"
But the subject is interesting
just imagine someone is blocking the other lane as well
This actually gives a good intuition as to why the sum of the harmonic series diverges. Of course there would be infinite groups, it wouldn’t make sense otherwise.
About a year or so ago I found a very similar thing relating permutations to the harmonic series: You can split any permutation into a number of "loops", e.g. (3 5 1 2 4) consists of the loops 3 -> 1 -> back to 3, and 5 -> 4 -> 2 -> back to 5. Fixpoints would count as loops of length 1.
The interesting thing I found is that for randomly selected permutations of length n, the expected number of such loops turns out to be:
1 + 1/2 + 1/3 + 1/4 + ... + 1/n
Did you find a proof for this?
What do you mean by relating permutations to the harmonic series? Could you elaborate please?
What's the dynamic between creating these loops? From your description it seems like it could possibly be arbitrary
what you call a "loop" is actually called a cycle. For those looking for a proof, i'd suggest looking for "average number of cycles of a permutation". You can also search what's an orbit of an element of a permutation, it's closely related to cycles of permutations.
@@shahnawazhaque7243 I guess it means you first get 3, then, you go to index 3, find 1, then you go to index 1 and find 3. that is one loop/circle.
Here's another application :
It's also the expected number of times we would overwrite what we think the maximum/minimum is in a single pass of the selection sort.
Over the entire sort, it becomes sum((n+1-k)/k, k, 1 → n) = (n+1) * H_n - n
Note : Selection sort is the algorithm where check you check the unsorted part of the list for maximum/minimum, and place it at the appropriate position
It's fantastic, because I ran into the harmonic sequence with a similar problem at work. I needed to take the max of a set of IID values multiple times, and that also follows a harmonic sequence when calculating how the mean of the result shifts in the final result. It uses a lot of the same logic as shown here, even if the specific problem is different. This was fantastic, thank you!
Very interesting, Zach, I love your content, I always learn something
Thanks man that made me to think how could permutations and combination are applied to real life and made my concepts on harmonic series damn clear!
What happens if the underlying distribution of speeds for each given car is different, would that affect the expected number of groups?
Yeah it would, this video uses a uniform distribution for the number of cars which is why the second car has an exact probability of 1/2 or being slower, if it was something like a normal distribution then the probability of the second car being slower would be dependent on the mean of the distribution (unless the first car is going exactly the same speed as the mean speed, in which case it would still be a half). Which wouldn't result in the nice 1+1/2+1/3... formula as seen in the video
It depends on whether you have specific knowledge of the distribution for each individual car. If you know, for example, that cars arriving earlier will tend to be faster than cars arriving later, then yes you can get a different answer for expected number of groups. If you don't have specific knowledge of individual cars and can't differentiate between their distributions, then the probability of one random car going faster than another random car is going to be 1/2 no matter what their actual underlying distribution is.
@@letao12Not necessarily, if the cars' speeds were distributed normally with say, a mean of 10 and s.d. of 1 and the first car, by some really low chance, ended up going 0.001 mph then it would be VERY likely the second car would be going faster. Similarly using the same distribution if the first car somehow ended up going 30000mph you can be nearly certain the second car would be going slower. Even if the first car was only going 1mph under the mean of the distribution (or 9mph) the probability would still be less than a half that the next car would be going slower (doing some rough calculations using X~N(10, 1) the chance of the car going slower than the first if the first is going 9mph is roughly 0.2696, way less than a half). If you want to compare two cars' speeds where the underlying distributions are different then that would require probabilty methods way too complex for a youtube comment section but I can offer this heuristic example: if the average velocity of the first car is 10mph (s.d.=1mph) and the average velocity for the second is 11mph (s.d=1mph) and the first car is going at 9mph, are you SURE that it's still 1/2 chance the second car is going slower?
The point is you don't have any of that information. Yes if you have specific information about individual cars then that changes the probability. But you don't. You don't know if the first car is going above or below the mean. You don't know what their distributions are. As long as you don't know those things, you can't get any probability other than 1/2.
@@letao12 The probability in that case is less like a half and closer to just being undefinable. You do know that the speed must be greater than zero though (as the road is single lane and cars going backwards would overlap with cars going forward completely nullifying the whole point of the groups), which means that if you're assuming a completely unknown distribution the probability would still be dependent on the speed of the first car as you know the second speed must be greater than zero.
Also love a math quickie man! Cheers for the information
Very interesting ! As always.
Just found out about this guy last night and have been binging since. Keep up the good work my dude 👍🏼
Your videos were pivotal in me chosing my major. I'm thinking of majoring in applied mathematics or EE
I love your vídeos so much! I actualy really don't like math/physics, and i want to go to psychology/nurse school. But your vídeos are so interesting that i binge watch them!
nice! keep up the good work
This shows why zipper merging when one lane is closing moves the most traffic faster
Great real world application of harmonic series!
Good one as always ❤
Surely that 50% chance is assuming there are the same amount of speeds greater and smaller than a given speed. Since this requires an infinite amount of speeds to exist you would need negative speeds to be considered. Or considering the chance something is higher or lower deviates based on the value, which could be modelled using normal or binomial distribution
So what happens if u have negative speeds? I am gonna work on it when i have time. Also what would u need to change in this car problem to get pi^2/6.
@@xxnotmuchxx
This was a really long time ago i don't remember what i was saying. I'll rewatch the video later on
What about now @@theou1883
😮😮 Amezing. I didn't understand fully but I think very interesting This application .
Great someone did something on harmonic series
great video, as usual
Nice explanation of grouping
We were studying p series in college and my friend asked me why the p series converges for p>1 and diverges for other values, other than the formal proof. He asked me whether there was a graphical/intuitive way of proving it. What exactly differentiates p=1(harmonic series) from, say, p=1.000001?
One way to prove the divergence of the harmonic series is to "round" every fraction down to the largest power of a half smaller than or equal to it. So, you get 1/2+1/4+1/4+1/8... Combining identical terms will each give one half, and adding one half together infinitely many times is infinite.
If you use P very close to 1, but slightly bigger, and instead "round" up to (1/2)^PN , such that it's the smallest result larger, you'll get an over estimate.
Now, if you combine identical terms, the result for each combination is (1/2)^(PN-N) or (1/2)^(P-1)N, which is an exponential series, and converges
This might be the formal proof you were talking about, but you could compare the p-series to the p-integral (just replace the sigma with an integral sign). If the integral converges, then so does the series, and if the integral diverges, so does the series (as long as the function is decreasing and positive, which it is). Then you can easily solve the integral to see what p values converge
The integral test is easier to visualize.
Graph the funcion 1/x and compare that to the left (or right) Riemmann sums of 1/x with a step size of 1.
Since the area under the function 1/x diverges, so does the the Riemman sum
@@sergiolozavillarroel3784 the question he is asking is why does it converge for any higher exponent
Thanks guys for your answers. I appreciate it
This is the last, 10th problem on the 2020 promys (6 week oxford math "summer camp") application sheet too. (Also one of the few ones I managed to solve on my own. No, I'm not applying.)
edit: I did things differently, this is simpler, but hey I'm still proud of my own method..
I also realized this. I think this problem is asked on the promys app in some form or another pretty much every year. Initially, I came up with a different recursive formula, then realized it simplified to the harmonic series. Probably my favorite of the problems I have completed so far.
Zach star , you are really a star man!
Your videos were very helpful....can you suggest some books or maybe video lectures that might help in improving my competitive programming(which requires high level logical and discrete math )
Hey Zach, great job on the video! Could you please do a video on tensors? That and differential geometry are really hard to understand from books......
do you have a videos on information transfer and stuff like that?
@Zach Star I wonder where you get the content for your videos
What if each speed was independently, uniformly selected from some fixed range? The scenario you describes models a uniform distribution *of orderings*.
The application is that as the density of the traffic increase, the "slow groups" will merge with incoming "fast groups".
I was thinking on a similar problem the other day:
Considering an infinite road with infinite amount of traffic i.e. every car has a car in front (for simplicity purpuses let's consider every car has the same dimensions and there's no relative speed between to cars i.e they are at the same speed )what would be the maximum speed of every car at a given the density of cars in order to keep a safe distance (let's say 2 seconds gap)?
Wouldn't you just divide the distance between any two cars by 2? So for a 5 meter gap between each car a safe speed would be 2.5m/s
I’m still waiting for history of mathematics part 2
People unconsciously slow down when coming up to a tunnel, because there's this big mountain they can't see past. So they'll definitely be entering the tunnel at a slower speed than exiting, and I think that would have a better effect.
Probably best to look at this on a flat bridge if you want to observe it yourself.
Damn bro !
4:24 why does it have to be 1/3? why would it be wrong if we see it as "having 50% chance slower than the 1st, hence +1/2"?
In the scenario that the second car happens to be slower than the first, then the second car will make a new group. Then whether or not the third car makes a new group is dependent on the speed of the third car compared to the second car, and not just the first like we would in the other scenarios. Thus the probability of making a group is lower than 1/2.
@@StealthSecrecy ah thanks
The Harmonic Series diverges => "You can't get there from here."
Can you make a video about how to get into biotechnology?
Nice
1:26 The fastest car will leave the screen making zooming out necessary.
Please explain why the expected finite population size of a population with fluctuating population size over generations is the harmonic mean of the population sizes of all the generations. Also, why equivalent resistance of a parallel circuit is the harmonic mean of all the individual parallelly connected resistors' resistance? Why is equivalent capacitance follow harmonic mean formula in case of series circuit? Are these three phenomena somehow related deep down? Or is it just coincidence that they follow the same type of mean? Lastly, can we view harmonic series as the harmonic mean of consecutive natural numbers? Does viewing this way infer any deeper meaning?
this could be useful for autonomous cars, not an absolute answer, just a small piece of the intricate puzzle
Linearity of expectation very nicely lets you gloss over any kind of issues you might have with "interference". For instance, if all the first four cars are the slowest one yet, does that change the probability for the fifth car compared to if only the first one is the slowest yet? Maybe not, but we don't care, because expectation is linear.
please someone help me answer this question!!
ill be forever grateful
Question 1 (5 marks)
Trace the values of m and n in the following algorithm when a = 3 and b = 6.
begin
Input a, b;
m := 1;
n := a;
while m ≠ b do
begin
n := n * a;
m := m + 1;
end;
Output n;
end;
Describe, in words, the output from the above algorithm for general integers a
and b, when b > 0. (4 marks)
What happens if b ≤ 0? (1 mark)
when b > 0 the output is a^b, when b
Great day
Superb! One thought experiment: what would happen if you counted GAPS instead of GROUPS? Would the harmonic series change?
@Sebastian Henkins yeah no you're right. The gaps are just N-1. I wasn't thinking clearly
Dude, you are uploading an insane amount of high quality content in such short amounts of time.You have the most insane work ethic of any TH-camr I've ever seen. Keep it up man, your channel is skyrocketing.
Can you make a video about the mathematics of traffic jams?
At 3:39 shouldn't the white car with the speed of 58 units form a new group right behind the blue one?
Yes, that follows for a stream of cars that have been following each other for a very long time....but not in the real world, I overtake slow cars
Can anyone please tell me how could I improve at my PnC skills to make much of the maths simple?
Thats where you're wrong bro. There's more to this. Fantastic example, this is amazing.
This was asked as a coding interview questions that I appread for. 😮. 🤦🏻♂️🤦🏻♂️🤦🏻♂️
oh what was the question?
@@urmudder8867 I don't recall exactly, though it was similar to the question framed here. I was appearing for a swe interview and this was the question I was asked to code.
Very fascinating and entertaining. But clearly it doesn't work for the Cross Bronx or more importantly, the Van Wyck. Because NO ONE beats the Van Wyck! :)
Great video as always!
Thanks Noah!
2 weeks ago?!. Do you make the video private before publishing it to the public?
Vemo The virtuoso yes, he posts it earlier for patreon supporters ;)
swag video
realistically, this doesn't or shouldn't happen. Who in their right mind would tailgate someone like that after the road was just cleared of a tree? Most likely, people would just go the speed limit and honk at the slow guy to make him speed up, or just conform to the slow guy until they were allowed to pass him
I think one application of this problem specifically is that it can help explain (and therefore predict and prevent) traffic jams.
how would you do this?
Is there a rigorous proof of this? Any lead to it or idea of how to prove it mathematically would be appreciated
Having not found a proof to it, did the proof myself, pretty nice.
This may be very applicable for streetcar lines since streetcars can’t pass each other.
The only unit for speed that makes sense is nano C (nc). 10^-9 * speed of light
You don't drive a car right atop the yellow line!
Is this realistic? Assuming the lead car in any group having 1/n probability.?
i like it!
55 light years per plank unit of time is not that slow buddyguy
yes but there is another kind of annoying -----> people constantly changing speed!
I wonder what kind of math describes that xD
I'm gonna guess it has something to do with chaos.
The only thing I did not understand, unfortunately was why the third car in the lane has 1/3 chance of being the slowest in the group.
Awesome video nevertheless.
Since we're considering random cars going at random speeds that we don't know, each car must have an equal chance of being the slowest one in the group. It wouldn't make sense if one car had a better chance of being the slowest than any other. So out of 3 cars, the chance each one can be the slowest is 1/3.
@@letao12 Ah, I see! I had my reasoning backwards, trying to think about randomly select numbers in an interval. The logic works for 1 and 2 cars, but by the third car, I started to get into some nasty problems due to dependencies on the values of the velocities previously selected. Thanks for the reply
Ahh, yes, of course.
This formula will help accelerate my plans for global domination
...of drones that follow people and cars around to play animè series for them.
*(every evil laugh ever)*
Down voted for no mention of the distribution for the RNG. Youre assuming uniform distribution.
Hi Zach, love your channel, but reckon you've made an error in your bridge section.
Firstly, applying a Reductio ad absurdum, after infinite cars have entered, the next lead car would be moving at zero speed, and the tunnel would empty forever. Clearly not what happens, so where is the error of logic?
You are making an assumption that all cars approaching the tunnel are part of the same initial (but subsequently separated) group. This is not how the real world works out - upstream events cut the infinite group up into "traffic light" sized bites, each of which *independently* follows the mathematics you describe. Therefore, the lead mini group of the trailing macro group will almost always be traveling faster than the group in front (the last mini group of the earlier macro group).
I'd expect that if correctly analysed you would find that average speed at the tunnel exit exactly matched entrance speed, as would be required to prevent the tunnel emptying forever, or forming a permanent gridlock.
13th
Transit regulations don't approve how you represented "one single lane in which you can't overpass"
that car going 55 can suck it.
Are annoying? You mean dangerous to themselves and others?
That is very dependent.
If each subsequent group gets slower, at some point you would have so many groups that the cars at the back would have to drive at 0 speed, how many cars would it take to reach that limit?
If we take speeds as continuous (as real numbers, not integers), then you can have an infinite number of different speeds going slower than the first car (assuming the first car isn't already at 0). For example, you can have the first group going at 1.1, the second group going at 1.01, the third group going at 1.001, and so on. Each group is slower than the previous but no one ever needs to go slower than 1.
There is also negative speed which they drive backwards :D
@@letao12 right, but what if we take integers
@@Errenium Right, so it depends on the max speed we choose for the initial car, so lets say if we have max speed of 100, then in theory we could have 100 groups, each with a speed 1 lower than the one before it, but talking in terms of mean distributions or just plain probabilities, if we choose the max speed to be lets say 100, what would be the expected amount of groups in such a scenario?
@@Errenium interesting approach, thanks :)
Is this an ad with information that worth nothing?