5 ms·

This article epitomizes a phenomena that I don't like. It starts with a simple subject, and a mildly interesting result. Then obfuscates it with an unenlighte

by btilly 6y ago

This article epitomizes a phenomena that I don't like. It starts with a simple subject, and a mildly interesting result. Then obfuscates it with an unenlightening and confusing model. Then shows how to do lots of exploratory programming with that model and create apparently surprising results. Then uses it to sell the modeling tool so that you too can come to surprising results about things in a way that does not enlighten. Here is the simple subject. If jobs are randomly coming in at the same speed that a worker can work, you will get a line. The lines can grow without bound, and the average length of the line is linear in the amount of time this has been going on. Therefore the amount of time spend waiting in line grows quadratically with how long this has been going on. Add a second worker and the average length of line becomes a fixed, small number. Time waiting is now linear. Add jobs as fast as both workers can work and voila, lines start growing again! There are a lot of interesting results in queuing theory. But the stated style of experiment doesn't seem like a good way to figure it out.

hyperpape 6y ago
"If jobs are randomly coming in at the same speed that a worker can work, you will get a line. The lines can grow without bound, and the average length of the line is linear in the amount of time this has been going on. Therefore the amount of time spend waiting in line grows quadratically with how long this has been going on." I don't think this is true, unless I'm misunderstanding your description. Do you mean if the work comes in faster than the worker can process it? If work arrives at the same rate the worker can process it, the depth of the queue is a random walk starting at zero, with the restriction that it can never go below zero. I'm not sure how that behaves, but it definitely grows much less than linearly. Python simulation code below: import random def random_walk(steps): count = 0 max_count = 0 for step in range(steps): if count > 0: count -= 1 if random.random() > .5: count += 2 max_count = max(count, max_count) if step in [2 ** i for i in range(14)]: print(f"step={step}, count={count}, max_count={max_count}") for i in range(10): random_walk(2**13 + 1)
- deleted 6y ago
  [deleted]
- Jtsummers 6y ago
  Along with the probability distribution on arrivals, there’s a probability distribution on work times. There’s a chance that a job takes longer than average, which would cause the queue to grow longer. You might say, “Yeah, but they could also be shorter than average.” And you’d be right. But consider: If the average job takes 5 steps, then “shorter” means 1-4. Longer means 6-infinite. A single job taking 25 steps (5x average) would require either a lull in arrivals (statistically possible but unlikely) or a series of short jobs to balance it out. And while waiting for the queue to die down, yet another job could take longer than average setting you back again. You can only improve the queue in small increments, but you can increase it arbitrarily with one bad job.
  - hyperpape 6y ago
    What distribution are you thinking of?
    - Jtsummers 6y ago
      Usually arrival is a Poisson distribution and work time is an exponential distribution, IIRC. But I’ll admit I’m rusty on the stats since it’s been nearly 15 years since I was in college, and professionally I haven’t had to use it much.
      - hyperpape 6y ago
        I tried an exponential distribution with its mean equal to the rate work is processed and got the same result. Edit: same qualitative result (substantially sublinear). Didn’t try to fit it to a distribution.
      - btilly 6y ago
        To be more precise, the mathematical models usually assume that people arrive at one rate regardless of how recently someone arrived, and work finishes at another rate regardless of how long you have been working. This makes the time between arrivals, and the time to complete a job both exponential distributions. It also makes the number of arrivals while a job is being worked on into a Poisson distribution. For a computer simulation you can simplify this even further by forgetting about time and focusing on events. If the worker is busy, the next event is either a new arrival or a job completion with a probability based on the rates.
titzer 6y ago
Thank you, your comment was more enlightening than that entire article!
andrepd 6y ago
A pet peeve of mine is demonstrating things through programming than can much more easily and clearly be shown with math.
- esyir 6y ago
  Funny, mine is the exact opposite of yours.
  - eru 6y ago
    The exact opposite would be: > A pet peeve of mine is showing things much more easily and clearly with math than demonstrating them through programming. You probably meant something like > A pet peeve of mine is demonstrating things through math that can much more easily and clearly be shown with programming. I don't think andrepd would disagree with the latter. Basically, pick the clearest way to show things.
    - inopinatus 6y ago
      Not sure about this. The opposite of a pet peeve would necessarily be a undomesticated, wild, or feral peeve. In this case, by simple inversion that'd be demonstrating things through programming, that would be more challenging to prove with mathematics. By such a standard, the four-colour theorem would be an example of a feral peeve. However, the work of Agner Krarup Erlang would not.
fizwhiz 6y ago
Spot on, I think if the author spent 30min watching an introductory queuing theory video they'd realize that there's so many factors: * Workload distribution (heavy tailed, exponential, uniform etc.) * Scheduling policies (FirstComeFirstServe, ShortestRemainingProcessingTime etc.) * Arrival rate of the jobs (poisson, uniform etc.) in comparison to their "service" rate
- manicstoic 6y ago
  any recommendations in particular? would love to dip a toe into this (not the author)
  - arthurcolle 6y ago
    https://www.ecosia.org/videos?q=introductory%20queuing%20theory https://www.ecosia.org/videos?q=introductory%20queuing%20the...
  - fizwhiz 6y ago
    https://www.youtube.com/watch?v=rT7WR89GMC4 https://www.youtube.com/watch?v=rT7WR89GMC4
pfortuny 6y ago
This is nitpicking a little but “randomly” requires a very specific definition of the distribution function. Uniform? Poisson? Gaussian? Geometric?...
- ddulaney 6y ago
  I’m not sure what the parent was referring to, but the simplest and most common queue model uses a poisson process[0] for both queue entries and exits, which means inter arrival and processing times are both exponentially distributed. This is called an M/M/1 queue,[1] and waiting times can be analyzed with Little’s law, though that breaks down at the inflection point where service times are identical to waiting times. [0]: https://en.m.wikipedia.org/wiki/Poisson_point_process https://en.m.wikipedia.org/wiki/Poisson_point_process [1]: https://en.m.wikipedia.org/wiki/M/M/1_queue https://en.m.wikipedia.org/wiki/M/M/1_queue

by btilly 6y ago

hyperpape 6y ago

"If jobs are randomly coming in at the same speed that a worker can work, you will get a line. The lines can grow without bound, and the average length of the line is linear in the amount of time this has been going on. Therefore the amount of time spend waiting in line grows quadratically with how long this has been going on." I don't think this is true, unless I'm misunderstanding your description. Do you mean if the work comes in faster than the worker can process it? If work arrives at the same rate the worker can process it, the depth of the queue is a random walk starting at zero, with the restriction that it can never go below zero. I'm not sure how that behaves, but it definitely grows much less than linearly. Python simulation code below: import random def random_walk(steps): count = 0 max_count = 0 for step in range(steps): if count > 0: count -= 1 if random.random() > .5: count += 2 max_count = max(count, max_count) if step in [2 ** i for i in range(14)]: print(f"step={step}, count={count}, max_count={max_count}") for i in range(10): random_walk(2**13 + 1)

deleted 6y ago
[deleted]
Jtsummers 6y ago
Along with the probability distribution on arrivals, there’s a probability distribution on work times. There’s a chance that a job takes longer than average, which would cause the queue to grow longer. You might say, “Yeah, but they could also be shorter than average.” And you’d be right. But consider: If the average job takes 5 steps, then “shorter” means 1-4. Longer means 6-infinite. A single job taking 25 steps (5x average) would require either a lull in arrivals (statistically possible but unlikely) or a series of short jobs to balance it out. And while waiting for the queue to die down, yet another job could take longer than average setting you back again. You can only improve the queue in small increments, but you can increase it arbitrarily with one bad job.
- hyperpape 6y ago
  What distribution are you thinking of?
  - Jtsummers 6y ago
    Usually arrival is a Poisson distribution and work time is an exponential distribution, IIRC. But I’ll admit I’m rusty on the stats since it’s been nearly 15 years since I was in college, and professionally I haven’t had to use it much.
    - hyperpape 6y ago
      I tried an exponential distribution with its mean equal to the rate work is processed and got the same result. Edit: same qualitative result (substantially sublinear). Didn’t try to fit it to a distribution.
    - btilly 6y ago
      To be more precise, the mathematical models usually assume that people arrive at one rate regardless of how recently someone arrived, and work finishes at another rate regardless of how long you have been working. This makes the time between arrivals, and the time to complete a job both exponential distributions. It also makes the number of arrivals while a job is being worked on into a Poisson distribution. For a computer simulation you can simplify this even further by forgetting about time and focusing on events. If the worker is busy, the next event is either a new arrival or a job completion with a probability based on the rates.

titzer 6y ago

Thank you, your comment was more enlightening than that entire article!

andrepd 6y ago

A pet peeve of mine is demonstrating things through programming than can much more easily and clearly be shown with math.

esyir 6y ago
Funny, mine is the exact opposite of yours.
- eru 6y ago
  The exact opposite would be: > A pet peeve of mine is showing things much more easily and clearly with math than demonstrating them through programming. You probably meant something like > A pet peeve of mine is demonstrating things through math that can much more easily and clearly be shown with programming. I don't think andrepd would disagree with the latter. Basically, pick the clearest way to show things.
  - inopinatus 6y ago
    Not sure about this. The opposite of a pet peeve would necessarily be a undomesticated, wild, or feral peeve. In this case, by simple inversion that'd be demonstrating things through programming, that would be more challenging to prove with mathematics. By such a standard, the four-colour theorem would be an example of a feral peeve. However, the work of Agner Krarup Erlang would not.

fizwhiz 6y ago

Spot on, I think if the author spent 30min watching an introductory queuing theory video they'd realize that there's so many factors: * Workload distribution (heavy tailed, exponential, uniform etc.) * Scheduling policies (FirstComeFirstServe, ShortestRemainingProcessingTime etc.) * Arrival rate of the jobs (poisson, uniform etc.) in comparison to their "service" rate

manicstoic 6y ago
any recommendations in particular? would love to dip a toe into this (not the author)
- arthurcolle 6y ago
  https://www.ecosia.org/videos?q=introductory%20queuing%20theory https://www.ecosia.org/videos?q=introductory%20queuing%20the...
- fizwhiz 6y ago
  https://www.youtube.com/watch?v=rT7WR89GMC4 https://www.youtube.com/watch?v=rT7WR89GMC4

pfortuny 6y ago

This is nitpicking a little but “randomly” requires a very specific definition of the distribution function. Uniform? Poisson? Gaussian? Geometric?...

ddulaney 6y ago
I’m not sure what the parent was referring to, but the simplest and most common queue model uses a poisson process[0] for both queue entries and exits, which means inter arrival and processing times are both exponentially distributed. This is called an M/M/1 queue,[1] and waiting times can be analyzed with Little’s law, though that breaks down at the inflection point where service times are identical to waiting times. [0]: https://en.m.wikipedia.org/wiki/Poisson_point_process https://en.m.wikipedia.org/wiki/Poisson_point_process [1]: https://en.m.wikipedia.org/wiki/M/M/1_queue https://en.m.wikipedia.org/wiki/M/M/1_queue