No video :(

Queuing theory and Poisson process

Подписаться 225 тыс.

Просмотров 88 тыс.

50% 1

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!

Опубликовано:

26 июн 2023

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 114

@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 6 месяцев назад

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

@hamsterdam1942 Год назад

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

@FardeenKhan-mb1fs Год назад

This is what i am waiting for.

@mathemaniac Год назад

I see what you did there.

@gcespoir5125 Год назад

In a queue? 😅😅

@jankinsics 2 месяца назад

Same here. Debugging a queueing problem in production.

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

@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

@dwivedys Год назад

This is an unbelievably amazing video!!

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

@flanbenflen9069 8 месяцев назад

This is, simply put, extraordinary.

@racpa5 Год назад

Love your math videos.

@fibbooo1123 Год назад

Awesome video!

@danielchin1259 Год назад

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

@PhysicsRaja-ul3kc Год назад

Great video as usual man...

@MissPiggyM976 Год назад

Very well done, thanks!

@antonkot6250 11 месяцев назад

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

@multidimensionalminds 11 месяцев назад

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

@zaringers Год назад

It’s excellent, thank you!

@samirelzein1095 Год назад

very very nice job!

@AlirezaAroundItaly Месяц назад

Amazing video , thank you so much

@Taha-uc1if Год назад

great explanation

@mohammedel-naggar9394 Год назад

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

@user-is6zh9nl6r 5 месяцев назад

beautiful and helpful. Thanks

@CarlosRodriguez-mx2xy Год назад

Just Beautiful !!

@ayushsawarni490 Год назад

This is beautiful ❤️

@gurulinggbiradar6982 4 месяца назад

cleared my mind. thank you

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

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

@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 11 месяцев назад

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

@tsunningwah3471 Год назад

amazingvideo

@NIXNYKYO Год назад

Thanks!

@xX_swagger_Xx 3 месяца назад

you explained this way better than my professor

@PaPa-kr5yt Год назад

Hey thank you for the great content again 😀

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

@opexideas-karolbak1483 3 месяца назад

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

@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

@superuser8636 8 месяцев назад

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

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

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

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

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

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

@forresthu6204 Год назад

Thanks

@leonard8336 Год назад

music is quite loud

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

@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 7 месяцев назад

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

@habukichan Год назад

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

@orngng Год назад

hopeful freedom by asher fulero

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

@alex_zetsu Год назад

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

@marcelob.5300 Год назад

Great

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

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

@maggotroot Год назад

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

@tsunningwah3471 8 месяцев назад

good shit

@RevolutionibusOrbiumCoelestium Год назад

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

@tuongnguyen9391 11 месяцев назад

I wish there could be time stamp

@tomkerruish2982 Год назад

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

@maxresnick7753 8 месяцев назад

wen next video

@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

@JasonSchmidt12 24 дня назад

Still don't get it

@InquilineKea Год назад

ben hoffman once tld me to study this more

@Sky-pg6xy Год назад

I prefer the name “line-up theory” lol

@mrofnoctonod 3 месяца назад

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

@nicolasrosat5485 Год назад

Merci !

@tsunningwah3471 8 месяцев назад

ninin

@Phlosioneer Год назад

A good follow-up for people who want to see queue theory in practice is the defunctland fastpass/shapeland video: ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-9yjZpBq1XBE.html (it *does* get mathy)

@tsunningwah3471 8 месяцев назад

diu

@tsunningwah3471 Год назад

se x

@tsunningwah3471 8 месяцев назад

vvvvvvv swex

@tsunningwah3471 8 месяцев назад

b b b b