1
$\begingroup$

I am going through this algorithms and data structure course which implements a queue DS to simulate a printing queue. Following is the solution described:

To model this situation we need to use some probabilities. For example, students may print a paper from 1 to 20 pages in length. If each length from 1 to 20 is equally likely, the actual length for a print task can be simulated by using a random number between 1 and 20 inclusive. This means that there is equal chance of any length from 1 to 20 appearing. If there are 10 students in the lab and each prints twice, then there are 20 print tasks per hour on average. What is the chance that at any given second, a print task is going to be created? The way to answer this is to consider the ratio of tasks to time. Twenty tasks per hour means that on average there will be one task every 180 seconds:

20 𝑡𝑎𝑠𝑘𝑠 / 1 ℎ𝑜𝑢𝑟 × 1 ℎ𝑜𝑢𝑟 / 60 𝑚𝑖𝑛𝑢𝑡𝑒𝑠 × 1 𝑚𝑖𝑛𝑢𝑡𝑒 / 60 𝑠𝑒𝑐𝑜𝑛𝑑𝑠 = 1 𝑡𝑎𝑠𝑘 / 180 𝑠𝑒𝑐𝑜𝑛𝑑𝑠

For every second we can simulate the chance that a print task occurs by generating a random number between 1 and 180 inclusive. If the number is 180, we say a task has been created.

Note that it is possible that many tasks could be created in a row or we may wait quite a while for a task to appear. That is the nature of simulation. You want to simulate the real situation as closely as possible given that you know general parameters.

I have doubt in the assumption that probability of each task is 1/180. Shouldn't probability for each task 1/20 since there are 20 tasks in total? It could be the considered average per second rate but how is this probability of each task happening every second?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

The reasoning in the tutorial is simple, if you have 20 tasks in 3600 seconds = 1 hour, assuming uniform distribution, then the probability of having a task in a particular second will be $20/3600 = 1/180$.

Note that this logic assumes a second can have at most one task. When the number of tasks is small and time resolution is high, this is logical and a simple approximation. Normally, if we are to choose a particular second for each task independent of others, having at least one task at a chosen second is calculated as below, where we also account for collisions: $$1-\left({3599\over3600}\right)^{20}\approx 0.00554\approx\frac{20}{3600}$$

Improve this answer
$\endgroup$
9
  • $\begingroup$ Yeah that's true but I assume any second can have up to 20 tasks. $\endgroup$
    – Coddy
    Commented Jan 4, 2020 at 14:42
  • $\begingroup$ I made a mistake so re-writing it. Is it ok to say that the probability is equivalent to the probability of putting at least 1 ball (out of 20) in one of the 3600 bins. Actually it should be $\frac{\binom{20}{1}+\binom{20}{2}+..+\binom{20}{20}}{\binom{3600}{1}+\binom{3600}{2}+...+\binom{3600}{20}}$ $\endgroup$
    – Coddy
    Commented Jan 4, 2020 at 14:56
  • $\begingroup$ No, if you calculate this, you'll see that it's much much closer to $0$. I think your way of counting things is flawed. $\endgroup$
    – gunes
    Commented Jan 4, 2020 at 15:52
  • $\begingroup$ If you assume that only 1 task can occur per second then the probability becomes really easy. It's simply $\frac{\binom{20}{1}}{\binom{3600}{1}}$ but if that assumption isn't true then it becomes difficult. $\endgroup$
    – Coddy
    Commented Jan 4, 2020 at 16:01
  • $\begingroup$ If that assumption is not true, the answer is the formula I gave in the end of my post. It's still simple to write, but a bit harder to calculate; while simple to approximate. $\endgroup$
    – gunes
    Commented Jan 4, 2020 at 16:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.