Queuing theory and Poisson process
HTML-код
- Опубликовано: 23 авг 2024
- Queuing theory is indispensable, but here is an introduction to the simplest queuing model - an M/M/1 queue. Also included is the discussion on Poisson process, which is the underlying assumption for the M/M/1 queue.
Second channel video on variance of Poisson distribution: • Poisson distribution (...
To me, this is mainly a "prequel" which serves as a prerequisite for the next video, even though the next video is not as long.
For the files created for this video, please visit www.mathemania... and enter the password:
queuingmodelM/M/1
and follow the instructions on the website. If you can't enter the website, watch the latest video! It always changes when a new video is up.
Sources:
Different queues:
M/M/1 queue: en.wikipedia.o...
M/M/c queue: en.wikipedia.o...
M/M/∞ queue: en.wikipedia.o...
M/G/1 queue: en.wikipedia.o...
M/G/k queue: en.wikipedia.o...
G/M/1 queue: en.wikipedia.o...
G/G/1 queue: en.wikipedia.o...
Jackson Network: en.wikipedia.o...
More general queues: en.wikipedia.o...
The (transient) solution: Computer Networks and Systems. New York, NY: Springer New York. p. 72 (uses moment-generating function and Laplace transforms); for more details, see Gross, D. and Harris, C.M., Fundamentals of Queueing Theory, Wiley, New York, 1974, 1985. (Section 3.11.2)
Other related sources:
Markov Chains: www.statslab.c...
Birth-and-death chain: en.wikipedia.o...
Bessel functions (for the solution to the differential equations): en.wikipedia.o...
Other than commenting on the video, you are very welcome to fill in a Google form linked below, which helps me make better videos by catering for your math levels:
forms.gle/QJ29...
If you want to know more interesting Mathematics, stay tuned for the next video!
SUBSCRIBE and see you in the next video!
If you are wondering how I made all these videos, even though it is stylistically similar to 3Blue1Brown, I don't use his animation engine Manim, but I use PowerPoint, GeoGebra, and (sometimes) Mathematica to produce the videos.
Social media:
Facebook: / mathemaniacyt
Instagram: / _mathemaniac_
Twitter: / mathemaniacyt
Patreon: / mathemaniac (support if you want to and can afford to!)
Merch: mathemaniac.my...
Ko-fi: ko-fi.com/math... [for one-time support]
For my contact email, check my About page on a PC.
See you next time!
This video primarily serves as the prerequisite of the next video, which is going to be out soon. The prerequisite only includes Poisson distribution, but I thought it might be a little less textbook-like if I associate this with queuing theory.
Thank you so much for such a clear and simple explanation.
Please upload the next video!!!
Thanks again.
This is what i am waiting for.
I see what you did there.
In a queue? 😅😅
Same here. Debugging a queueing problem in production.
This video actually shows why, out of all things, Poisson distribution appears when studying radioactive decay
Mathemaniac and 3b1b both uploading probability videos on the same day? Awesome!
1 hour apart
No kiddding
Haha, I honestly haven't communicated with Grant whatsoever.
What are the odds?
Normally I would watch the entire video before commenting, but I was so surprised by how the first few minutes of the video explained how probability works with time, and that’s something I’ve been wondering for a while. Great content as always!
I just have some video editing feedback. Some people (like myself) keep subtitles on. So don't use the bottom ~10% for important information, like the results of certain equations. It gets blocked, and having to toggle subtitles off and on just to see parts of the video can get annoying. Consider where the viewers' vision typically rest and put things you want to bring their attention to near the center of the screen. Having to look towards the peripherals can be distracting and just extra work, making information transfer harder. Anyways, keep up the good work!
The derivations at 9:40 neglect the possibility of a customer arriving and a customer leaving in the same time step. These events were assumed to be independent, so it cannot also be assumed that they cannot coincide. If the queue is in state 3, and a customer arrives and a customer leaves in the same time step, the queue is still in state 3 -- not state 2. The term should have a factor of 1-λ/n to stipulate that a customer did not arrive on that time step. Similarly, the term for the state 1 => 2 transition should have a factor of 1-μ/n to stipulate that a customer did not depart on that time step -- since otherwise the queue would still be in state 1.
And there should be another state 2 term for if a customer arrives and a customer departs in the same time step when already in state 2.
So the equation should be:
p_2(t+1/n)=p_2(t)((1-λ/n)(1-μ/n)+(λ/n)(μ/n)) + p_3(t)(μ/n)(1-λ/n) + p_1(t)(λ/n)(1-μ/n)
In state 0, the events cannot be independent -- a customer can only depart in that time step if they arrived in that time step (were served within a single time step). The only way to interpret the departure probability in this scenario is as the probability that a customer departs given that a customer arrives. This however results in the same term for the probability for their intersection as when they were independent.
The equation for state 0 becomes:
p_0(t+1/n)=p_2(t)((1-λ/n)+(λ/n)(μ/n)) + p_1(t)(μ/n)(1-λ/n)
If instead it is assumed that the events cannot coincide, and that λ/n and μ/n are still the total probabilities of the events, then we get the following relationships:
let A be the event for arrival and D be the event for departure:
P(A∩D)=P(D∩A)=0
P(A)=P(A∩D)+P(A∩¬D)
P(A)=P(A∩¬D)
P(D)=P(D∩A)+P(D∩¬A)
P(D)=P(D∩¬A)
P(¬A∩¬D)=1-(P(A∩¬D)+P(¬A∩D)+P(A∩D))
P(¬A∩¬D)=1-(P(D)+P(A))
This still results in a discrepancy from the derivation in the video, since the state-n no-transition term is based on the P(¬A∩¬D)=(1-P(D))(1-P(A)) of independent events instead of the P(¬A∩¬D)=1-(P(D)+P(A)) of mutually exclusive events. Also note that the mutually-exclusive condition imposes the condition of P(D)+P(A) ≤ 1
I was also thinking this and was looking for a comment talking about it. Note, however, that even if we assume they can coincide in the finite n case, the contribution is of order O(1/n^2) and so becomes negligible as we take the limit - this means the final result is still correct (as somebody else said elsewhere in the comments, Mathemaniac does leave a note at 8:29 which notes this, though they don't mention it in the narration)
@@alucs6362 I watch youtube with captions on. the note was covered up!
@@klikkolee Understandable! I had also not seen it before I read this other comment (I originally going to comment that I assume they hadn't included it because it was negligible in the limit, but no need to assume in this case!)
All equations (from start to finish) are wrong for finite n, as every term that vanishes for n->inf is neglected.
The trick of *invariant distribution* is so profoundly generalizable, once you get used to it, you'll start to use it every where.
Probably the best math video I've seen in couple of years (with lambda over mu probability :) )
You can watch "Science of Queues and Psychology of Waiting: Revealing the Secrets of Queueing Theory"
nice video, i have an exam on ODE's this friday, so i was immediately thinking about how to write the ODE in terms of a matrix, we didnt have infinitely big systems, so it was really fun to see one
This is an unbelievably amazing video!!
This is, simply put, extraordinary.
you explained this way better than my professor
Very clear explanation. Thank you, your the best ❤, keep making awesome videos like that !
Wonderful explicative video!! I will do Probability and Statistics next semester so it will be handy in some months.
When evaluation state k and looking at probability contributions to pk(t + 1/n): Why is the contribution from state k+1 not pk+1(t)(u/n)(1-lambda/n)?
In other words when we are in state k+1 shouldn't there only be a contribution when a departure happens AND no new arrival comes in the interval?
Same for the contribution from k-1
A lot of these contributions might cancel out though
I’m guessing it’s because 8:29 mentions how that possibility is negligible.
@Mathemaniac
Please respond and free us from this hell
I think you are absolutely right!
I'm thinking the same thing
in the equation at 9:34, shouldn't the 2 departures from p2 to p1 and p3 at time = t be incorporated to the state at time = t+1? I don't understand why they are excluded.
At 03:35 you divide the numerator of the factorial fraction by n from (lambda/n)^k but it seems you forgot to apply the ^k to the denominator. Where is the (1/n^(k-1))??
I liked the piano music while doing math manipulation. It was relaxing.
Amazing video , thank you so much
Awesome video!
great job in explaining it. I didn't understand it from MIT.
The equations of transition are not valid at finite n, as multiple hops cases are not included. What Would have been needed is explicitly saying that the remainder is o(1/n).
Probability videos by Mathemaniac and 3b1b within the same hour? What are the chances!
And both about probability! Hard to assume independence...
Queuing theory is also heavily used in telecommunications
Yes! I don't know enough to put this into the video, but it is in a couple of textbooks about computing systems as well!
All of this made perfect sense to me in class and I hated doing it with a passion. These feelings were unrelated. I just hate the procedure, despite how obvious it is.
Love your math videos.
Hey thank you for the great content again 😀
No surprise I went to a strong ratio/root test with absolute convergence for a window which you explain later in the video as a trained eye from Calc 2 can see from taking the limit and evaluating the expression that plugging infinity into the LHS before setting up the Diffeq that it will evaluate to 0 without diffeq or stats but you make a great explanation with visuals. Kudos 🎉❤
Great video as usual man...
Question for the 10 minute mark: isn't there a fourth way we arrive at p_k: we start at p_k, and someone leaves, and someone arrives: p_k(t)*lambda/n*mu/n (as distinguished from no one coming and no one leaving)
Fantastic video! I think I finally learned that concept after having seen it from a far a bunch of times :)
Just a tiny bit of feedback: I personally thought that when you talked about the limiting case for the differential equations it was a bit confusing how you described the process of rewriting this in terms of a difference quotient, because somehow it sounded (even though it was completely right of course) weird that you would change the two terms on the right hand side differently. Maybe this is like a pedagogical thing? Maybe you could have done subtraction (as a whole) and then multiplication for both terms instead of seemingly doing one set of operations (subtraction and multiplication) on one term and another set of operations (just multiplication) on the other term. Hope I got across what I meant to convey, and again: Love the video! Keep up the great work👍
Hi, you can watch "Science of Queues and Psychology of Waiting: Revealing the Secrets of Queueing Theory"
I came across a description that the relationship [VA/system flow time] is called "flow efficiency".
Is there a name for the relationship [Servie Time/system flow time], maybe flow utilization???
(assuming VA/unit is an effective part of Service Time.)
It’s excellent, thank you!
With several service desks, it's obvious that the customers would requeue in order to decrease their wait time, so it's not that insane that customers from "within" the queue may be served, not just the head. We need an infinite amount of desks and an infinite amount of customers who can teleport to the queue of their choice when it becomes shorter than the one they're currently at, no problem!
not true, there's no guarantee or requirement that every queue provides the same service, so customers won't necessarily rearrange themselves. for example, in a store like Walmart there are checkouts, self-checkouts, customer service checkouts, electronics checkouts, gun checkouts, and tobacco checkouts, all of which provide slightly different services and multiple of which may be visited by a single customer in a single trip to the store. These different queues form a Jackson network.
Very well done, thanks!
cleared my mind. thank you
Curiously for me, I recently learned about this and queuing theory last semester (2022) in a course about simulating processes. A bit late for the finals but I passed the class anyway!
beautiful and helpful. Thanks
Wouldn't a more typical service model be that each customer, when they get to the front of the queue, leaves in an constant amount of time from when they arrive, or some probability distribution? How would that work out?
Modeled by an M/G/k queue where arrivals are memory less and service time is a general distribution. Makes practical sense but is harder to analyze mathematically
Why the other vid is on the 2nd channel, if you don't mind my asking? I note there are math education videos like here, and your opinion vids, generally with the property that they are anything else. Is it really better to split the education videos between the two? They are harder to find there.
Mainly because I can't find a narrative that pushes variance here - it is not really needed anywhere later on in the video, and it is probably also an extra minute or two, which is not really good for audience retention. I mean, a few probability videos on the channel also have the same property: the Stein's paradox and the random walk ones also have a "more technical" video on the second channel.
I can't put the second video on this channel either because the second video will tank the performance of the video, making the channel performing worse than it already is.
This is beautiful ❤️
A memoryless arrival is a reasonable approximation a lot of the time but memoryless service rate... less so.
Just Beautiful !!
music is quite loud
very very nice job!
great explanation
why dont you use colors matching to a concept? Now there are too many of them and they, generally, just look random.
Thanks!
That queue seems to be composed of anonymous people. Queue anon... nah, it couldn't be. Could it?🤪
What about the possibility that any customer arriving delays the service as they are being a “Karen”? How do you account for that?
@mathemaniac
at around 15:56 -> try to make the volume of the music match the volume of your voice
Other than that, all good, like:)
So according to maths, do I switch to the other queue or just stay I this one which was shorter but goes also seemingly slower???
Interestingly, related but not exactly the same phenomenon is discussed so widely that there is a name: wait/walk dilemma. The wiki article says, "The wait/walk dilemma occurs when waiting for a bus at a bus stop, when the duration of the wait may exceed the time needed to arrive at a destination by another means, especially walking."
can I ask what was the song while evaluating the limit? thanks 🙏🙏
hopeful freedom by asher fulero
Thanks
amazingvideo
I wish there could be time stamp
Whoa just watched the video that finds the relationship between ums and public speakers that uses the same maths. What are the chances :p
ben hoffman once tld me to study this more
None of this means anything in Africa where queuing is not taught from childhood as a societal norm.
Great
wen next video
I prefer the name “line-up theory” lol
good shit
A good follow-up for people who want to see queue theory in practice is the defunctland fastpass/shapeland video: ruclips.net/video/9yjZpBq1XBE/видео.html (it *does* get mathy)
25 minutes on queuing, and I didn't hear the name Erlang even once.
You can watch "Science of Queues and Psychology of Waiting: Revealing the Secrets of Queueing Theory"
For an actual explanation: Khan Academy
diu
se x
ninin
Merci !
b b b b
There's something fishy about this process
Oui Poisson
vvvvvvv swex
jesus bro pay a narrator at this point. unbearable
What about the time interval tending towards zero?
You can watch "Science of Queues and Psychology of Waiting: Revealing the Secrets of Queueing Theory"
Thanks!