Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Stochastic queue simulation

  1. Jul 22, 2015 #1
    Hello guys!
    I am learning a bit on queue theory in one of my courses, and decided to try and do some simulations even though it is not mandatory. (Curriculum only covers the steady state, where it can be treated mathematically with ease).

    Im looking at a birth-death process, where the time til next birth and next death are both exponentially distributed.

    My algorithm:
    ---------------------------------------------------------------------------------------------------------------------------------------------
    Intitialization: Set state to [itex]n=0[/itex](Number of people in queue and getting service) , set current time [itex]t=0[/itex], choose end simulation time [itex]t_{max}[/itex]

    Loop until the time [itex]t[/itex] has reached [itex]t_{max}[/itex]:
    - Get two random numbers from exponential distributions. One representing time until next death. One until next birth. The two numbers have different rate parameters.
    - Choose the lowest of these two numbers as [itex]\Delta t[/itex].
    - Set the state to [itex]n+1[/itex] or [itex]n-1[/itex], depending on which of the numbers were chosen.
    - Update the time [itex]t \rightarrow t +\Delta t[/itex].
    - Save the state and time period.
    End loop.
    ----------------------------------------------------------------------------------------------------------------------------------------------

    This process is repeated many times, and used to create probability densities for each of the states.

    My question:
    My algorithm simply discards the higher of the two randomly generated numbers. The state is then updated and two new random numbers are generated. Is this correct, or should the value of the second number be taken into account somehow after changing to the next state? The rate parameters of the probability distributions are not generally the same at each state.
     
  2. jcsd
  3. Jul 22, 2015 #2

    FactChecker

    User Avatar
    Science Advisor
    Gold Member

    It seems like that might distort the distributions so that larger interval times are more likely to be rejected. There is no reason to throw away the longer interval time. Generate only a new interval time for the one that just happened (birth or death) and compare it with the other remaining time to see which happens first. Then there would be no question about the distributions being distorted.

    PS. With exponential interval times, your current algorithm might be correct, but that is a special case. Unless you can verify it is correct, avoid throwing away the longer interval time.
     
  4. Jul 23, 2015 #3
    Okay, thanks.

    I do see a problem with this though: The rate parameters in the exponential distributions are different for the different states, which isnt taken into account if u use the time interval generated for the previous state. Say: U get two random numbers: 1 min (birth), 40 mins (death). In the next state, it doesn't seem reasonable to use the higher number for death since the rate parameter for death in this state might be much higher(say 1 / 1sec)

    With my method there is the following problem though: If a person is say 0.5 seconds away from birth as another just "died", this person simply disappears. Maybe this is ok with exponential distributions? I don't know. Or maybe the problem is a bit harder than i imagined xD
     
  5. Jul 23, 2015 #4

    FactChecker

    User Avatar
    Science Advisor
    Gold Member

    I agree. The next time of a birth should only be generated when a birth occurs. So the series of births is generated independent of the deaths. So the births will have an exponential distribution. If you generate an exceptionally long time for the next birth event, there may be several deaths before that birth occurs. If you are simulating a situation with a limited pool of objects, you will need to be sure that there is an object available to die. The best way to simulate this is an object-oriented approach where each object generated by a birth is immediately assigned a time of death. The appropriate parameters should be used for each type of event that is generated. The new of birth and death are then scheduled on the time line. (Actually, there is no reason to schedule an object's death till it's time of birth is reached.) But the "life expectancy" is not what you are given for modeling the time of death, so the distribution of deaths will not have the desired exponential distribution.

    I think that the closest you can reasonably come to retaining exponential death distributions is to generate the next birth every time a birth occurs, and generate a new death every time a death occurs -- each using the correct parameters. Then only record a death if there is a live object. But if it hits that constraint, the final distribution of deaths may not have the same exponential distribution that you started with.
     
    Last edited: Jul 23, 2015
  6. Jul 23, 2015 #5
    A better way to simulate this would be as two poisson processes with a single fixed time interval.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Stochastic queue simulation
  1. Stochastic Processes (Replies: 2)

  2. Queueing Theory (Replies: 20)

  3. Stochastic processess (Replies: 1)

Loading...