A discrete-event simulation holds a calendar of scheduled events and advances the clock to the earliest of them, skipping every instant at which nothing happens. The state changes, new events are scheduled from the new state, and the calendar is the model. The output is a time average, and it is an estimate of the steady-state value with everything the previous two pages attached to it.
Core ideas
Three ideas. The first is the mechanism, the second is what the mechanism produces, and the third is the one that keeps this course honest about it.
A discrete-event simulation is three things: a state, a list of scheduled future events, and a clock. The loop is: take the earliest event, move the clock to it, apply its effect to the state, schedule whatever that state now implies. There is no time step, and the instants between events are never visited because nothing happens at them.
The number in system is a step function of the clock. Its time average over a window is the area under it divided by the window's length — and that area is also the sum of the customers' times in the system, one rectangle per customer. The two readings of the same area are Little's Law, and as a statement about one run's own averages it is an identity rather than a model.
The number this page produces is not the long-run mean; it is an estimate of it. Reseed and it lands somewhere else, and the spread of where it lands is what the standard error measures. The exact value is available here only because this particular queue was solved exactly in “Markov Chains, Decisions and Queues”, which is what makes this page a measurement rather than an assertion.
The material
How the event loop works, what it produces, and how far one run of it is from the answer.
A simulation in which the state changes only at a countable set of event times. The simulator holds the current state, a calendar of events scheduled for future times, and a clock. Each step removes the earliest calendar entry, advances the clock to its time, applies its effect, and schedules any events the new state implies.
The model on this page is the single-server queue the earlier course solved exactly: in each slot an arrival occurs with probability p, and a customer in service completes with probability q, so a service duration is a geometric variate on {1, 2, 3, …}. Both are sampled by inverse transform from the seeded stream, so the run is reproducible and every figure it produces is a fraction.
For a quantity N(t) that is constant between events, the time average over [0, T) is (1/T)∫N(t) dt, which for a step function is the sum of N times the length of each interval, divided by T. It is not the average of the values N took; it is the average weighted by how long it took them.
That distinction costs people real errors. A queue that holds one customer for nine hundred slots and nine customers for one hundred has a time average of 1.8 and an unweighted average over its two distinct states of 5. Only the first is the number anyone wants, and only the first is what the area under the curve gives you.
Customer 1 arrives at slot 3 and leaves at 4. Customer 2 arrives at 5 with a service of three slots; customers 3 and 4 arrive at 6 and 7 and queue behind it. At clock 8 two events share the instant: customer 2 departs and customer 5 arrives. The departure is taken first, so immediately after it the system holds two, and the arrival then takes it to three. Nothing whatever happens at slots 0, 1, 2, and the clock never visits them.
The tie at clock 8 is not a detail. A simulator that answered “who is in the system at time t?” by testing arrival ≤ t < departure would count the arriving customer as present at the instant the departure is being processed, and its headcount would disagree with its own list of names. The rule — departures before arrivals at the same instant — has to be stated once and then obeyed by every part of the program that asks the question.
The gap of 0.0335 is not a defect of the simulation and not a rounding error; there is no rounding anywhere in it. It is one draw of a random quantity whose expectation is near 12/5, and reseeding moves it: the same model at seed 0 gives 1.9660, at seed 2 gives 2.7300, at seed 3 gives 2.5300. A page that printed only the first of those would be reporting a coincidence.
The area under the occupancy curve is both the integral of the number in system and the sum of the customers' times in it. Divide it by the horizon and you get the time average; divide the sum of times by the number of customers and you get the mean time in system; divide the number of customers by the horizon and you get the arrival rate. The three are then related by L = λW as a matter of arithmetic, with no assumption about the model at all.
It is worth being precise about the horizon, because the panel uses two of them and they differ. Over the trace's own horizon — from slot 0 to the last departure, at slot 2005 — the arrival rate is 776/2005 and the mean time in system is 4733/776, and their product is 4733/2005 ≈ 2.3606. The panel's time average divides the same area by the 2000 slots the run was asked for, giving 4733/2000 ≈ 2.3665. Same area, two denominators, and the identity holds for whichever one you choose consistently.
One thing that is often called a mistake here and is not: this is a slotted model, so stepping one slot at a time is the model, and next-event simulation is the efficient form of the same computation. The two agree slot for slot and differ only in how much work they do. They part company for systems in continuous time, which this path does not sample.
Interactive
The clock does not tick — it jumps to the next scheduled event, and the calendar is the model
Method
Five steps, and the third is the one that is skipped in every implementation that later disagrees with itself.
For this queue: how many are in the system, and who. Anything derivable — the queue length, whether the server is busy — is derived, not stored, because two copies of one fact are two copies that can disagree.
The first arrival, and nothing more. A calendar that starts with a hundred pre-generated arrivals is a different program: it cannot let the state decide what happens next, which is the one thing the method is for.
Two events can share an instant. Departures before arrivals is the convention here; the opposite convention is equally defensible and gives different numbers. What is not defensible is one rule in the event loop and another in the code that reports the state.
Not to the next tick. The instants in between are not simulated at all, and the whole economy of the method is that a thousand empty slots cost nothing.
Add N × (new clock − old clock) at every event. That running total is the integral of the occupancy, it is the sum of the customers' times, and it is the numerator of every average the run will report.
The panel's opening run, at p = 2/5, q = 1/2, seed 1. Twelve customers make twenty-four events, which is a calendar that fits on a screen and is twice as long as anyone wants to keep by hand.
Read the pair at clock 8 twice. After event 6 the system holds two customers and the waiting list holds one name; after event 7 it holds three and the list holds two. A headcount recomputed from the clock alone would report three at both instants, and the list of names would report two at the first — a program that disagrees with itself about a number it prints in two places.
The gaps are where the method earns its keep. Between the departure at slot 17 and the arrival at slot 26 nothing whatever happens, and a next-event simulator does no work at all for those nine slots. Over two thousand slots this run has fifteen hundred and fifty-two events, and a fixed-tick loop would take two thousand steps to reach the same numbers.
For a faded rehearsal, switch the panel to the faster server, q = 3/5, and predict the two headline figures before reading them. The supplied first move is that the exact long-run mean drops from 12/5 to 6/5 and the busy fraction from 4/5 to 2/3. Say whether the arrival times change, and why, and then check the first four rows of the log against your answer.
You should be able to run an event calendar by hand for ten events, state and obey a tie-breaking rule for simultaneous events, accumulate the area under the occupancy curve and turn it into a time average, read the same area as λ times W, and say what reseeding does to every figure the run produced.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.