Queuing theory and Poisson process

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.mathemaniac.co.uk/download 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.org/wiki/M/M/1_q...
M/M/c queue: en.wikipedia.org/wiki/M/M/c_q...
M/M/∞ queue: en.wikipedia.org/wiki/M/M/%E2...
M/G/1 queue: en.wikipedia.org/wiki/M/G/1_q...
M/G/k queue: en.wikipedia.org/wiki/M/G/k_q...
G/M/1 queue: en.wikipedia.org/wiki/G/M/1_q...
G/G/1 queue: en.wikipedia.org/wiki/G/G/1_q...
Jackson Network: en.wikipedia.org/wiki/Jackson...
More general queues: en.wikipedia.org/wiki/Kendall...
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.cam.ac.uk/~james...
Birth-and-death chain: en.wikipedia.org/wiki/Birth%E...
Bessel functions (for the solution to the differential equations): en.wikipedia.org/wiki/Bessel_...
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/QJ29hocF9uQAyZyH6
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.myspreadshop.co.uk
Ko-fi: ko-fi.com/mathemaniac [for one-time support]
For my contact email, check my About page on a PC.
See you next time!

[@mathemaniac]

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.

[@adityakulkarni8352]

Thank you so much for such a clear and simple explanation. Please upload the next video!!! Thanks again.

[@FardeenKhan-mb1fs]

This is what i am waiting for.

[@mathemaniac]

I see what you did there.

[@gczhu5125]

In a queue? 😅😅

[@jankinsics]

Same here. Debugging a queueing problem in production.

[@hamsterdam1942]

This video actually shows why, out of all things, Poisson distribution appears when studying radioactive decay

[@johnchessant3012]

Mathemaniac and 3b1b both uploading probability videos on the same day? Awesome!

[@16876]

1 hour apart

[@ridazouga4144]

No kiddding

[@mathemaniac]

Haha, I honestly haven't communicated with Grant whatsoever.

[@MarshallLevin]

What are the odds?

[@libberator5891]

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!

[@ryancantpvp]

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!

[@dwivedys]

This is an unbelievably amazing video!!

[@ariebaudoin4824]

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

[@flanbenflen9069]

This is, simply put, extraordinary.

[@uhah1235]

Very clear explanation. Thank you, your the best ❤, keep making awesome videos like that !

[@klikkolee]

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)

[@klikkolee]

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

[@alucs6362]

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)

[@klikkolee]

@@alucs6362 I watch youtube with captions on. the note was covered up!

[@alucs6362]

@@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!)

[@deinauge7894]

All equations (from start to finish) are wrong for finite n, as every term that vanishes for n->inf is neglected.

[@alejandrom.4680]

Wonderful explicative video!! I will do Probability and Statistics next semester so it will be handy in some months.

[@fibbooo1123]

Awesome video!

[@racpa5]

Love your math videos.

[@PhysicsRaja-ul3kc]

Great video as usual man...

[@MissPiggyM976]

Very well done, thanks!

[@danielchin1259]

The trick of *invariant distribution* is so profoundly generalizable, once you get used to it, you'll start to use it every where.

[@AlirezaAroundItaly]

Amazing video , thank you so much

[@mohammedel-naggar9394]

great job in explaining it. I didn't understand it from MIT.

[@zaringers]

It’s excellent, thank you!

[@antonkot6250]

Probably the best math video I've seen in couple of years (with lambda over mu probability :) )

[@multidimensionalminds]

You can watch "Science of Queues and Psychology of Waiting: Revealing the Secrets of Queueing Theory"

[@user-is6zh9nl6r]

beautiful and helpful. Thanks

[@gurulinggbiradar6982]

cleared my mind. thank you

[@Tomyb15]

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!

[@Taha-uc1if]

great explanation

[@samirelzein1095]

very very nice job!

[@CarlosRodriguez-mx2xy]

Just Beautiful !!

[@ayushsawarni490]

This is beautiful ❤️

[@baonguyen-ct6nj]

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.

[@josephjepson6756]

I liked the piano music while doing math manipulation. It was relaxing.

[@sceKernelDestroy]

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👍

[@multidimensionalminds]

Hi, you can watch "Science of Queues and Psychology of Waiting: Revealing the Secrets of Queueing Theory"

[@xX_swagger_Xx]

you explained this way better than my professor

[@PaPa-kr5yt]

Hey thank you for the great content again 😀

[@superuser8636]

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 🎉❤

[@NIXNYKYO]

Thanks!

[@opexideas-karolbak1483]

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.)

[@tsunningwah3471]

amazingvideo

[@ANunes06]

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.

[@scalex1882]

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))??

[@forresthu6204]

Thanks

[@etienneparcollet727]

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).

[@nektariosorfanoudakis2270]

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!

[@tissuepaper9962]

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.

[@HoSza1]

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???

[@mathemaniac]

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."

[@fresheFresse]

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

[@fresheFresse]

A lot of these contributions might cancel out though

[@ryancantpvp]

I’m guessing it’s because 8:29 mentions how that possibility is negligible.

[@jakoolaboo]

@Mathemaniac Please respond and free us from this hell

[@jakoolaboo]

I think you are absolutely right!

[@MiroslawHorbal]

I'm thinking the same thing

[@cykkm]

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.

[@mathemaniac]

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.

[@marcelob.5300]

Great

[@DrJRMCFC]

Queuing theory is also heavily used in telecommunications

[@mathemaniac]

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!

[@et2124]

@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:)

[@1.4142]

Probability videos by Mathemaniac and 3b1b within the same hour? What are the chances!

[@Jarretinha]

And both about probability! Hard to assume independence...

[@alex_zetsu]

A memoryless arrival is a reasonable approximation a lot of the time but memoryless service rate... less so.

[@habukichan]

can I ask what was the song while evaluating the limit? thanks 🙏🙏

[@orngng]

hopeful freedom by asher fulero

[@benhsu42]

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)

[@SolomonUcko]

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?

[@ethgraham]

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

[@tsunningwah3471]

good shit

[@tomkerruish2982]

That queue seems to be composed of anonymous people. Queue anon... nah, it couldn't be. Could it?🤪

[@maggotroot]

why dont you use colors matching to a concept? Now there are too many of them and they, generally, just look random.

[@leonard8336]

music is quite loud

[@RevolutionibusOrbiumCoelestium]

What about the possibility that any customer arriving delays the service as they are being a “Karen”? How do you account for that?

[@MrBricks148]

Whoa just watched the video that finds the relationship between ums and public speakers that uses the same maths. What are the chances :p

[@InquilineKea]

ben hoffman once tld me to study this more

[@tuongnguyen9391]

I wish there could be time stamp

[@maxresnick7753]

wen next video

[@Sky-pg6xy]

I prefer the name “line-up theory” lol

[@Phlosioneer]

A good follow-up for people who want to see queue theory in practice is the defunctland fastpass/shapeland video: kzbin.info/www/bejne/b6rNi6N4ppaLeKc (it *does* get mathy)

[@nicolasrosat5485]

Merci !

[@tsunningwah3471]

ninin

[@eswyatt]

For an actual explanation: Khan Academy

[@steveunderwood3683]

25 minutes on queuing, and I didn't hear the name Erlang even once.

[@multidimensionalminds]

You can watch "Science of Queues and Psychology of Waiting: Revealing the Secrets of Queueing Theory"

[@tsunningwah3471]

se x

[@tsunningwah3471]

b b b b

[@tsunningwah3471]

vvvvvvv swex

[@tsunningwah3471]

diu

[@mrofnoctonod]

None of this means anything in Africa where queuing is not taught from childhood as a societal norm.

[@thomasjames1067]

There's something fishy about this process

[@merchamyn]

Oui Poisson

[@xenonmob]

jesus bro pay a narrator at this point. unbearable

[@Lolwutdesu9000]

What about the time interval tending towards zero?

[@multidimensionalminds]

You can watch "Science of Queues and Psychology of Waiting: Revealing the Secrets of Queueing Theory"

[@benhsu42]

Thanks!