02 queue formation

%23%20%2F%2F%2F%20script%0A%23%20requires-python%20%3D%20%22%3E%3D3.13%22%0A%23%20dependencies%20%3D%20%5B%0A%23%20%20%20%20%20%22altair%22%2C%0A%23%20%20%20%20%20%22asimpy%22%2C%0A%23%20%20%20%20%20%22marimo%22%2C%0A%23%20%20%20%20%20%22polars%22%2C%0A%23%20%5D%0A%23%20%2F%2F%2F%0A%0Aimport%20marimo%0A%0A__generated_with%20%3D%20%220.20.4%22%0Aapp%20%3D%20marimo.App(width%3D%22medium%22)%0A%0A%0A%40app.cell%0Adef%20_()%3A%0A%20%20%20%20import%20marimo%20as%20mo%0A%20%20%20%20import%20random%0A%20%20%20%20import%20statistics%0A%0A%20%20%20%20import%20altair%20as%20alt%0A%20%20%20%20import%20polars%20as%20pl%0A%0A%20%20%20%20from%20asimpy%20import%20Environment%2C%20Process%2C%20Resource%0A%0A%20%20%20%20return%20Environment%2C%20Process%2C%20Resource%2C%20alt%2C%20mo%2C%20pl%2C%20random%2C%20statistics%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%20Queue%20Formation%0A%0A%20%20%20%20%23%23%20*Randomness%20Creates%20Waiting%20Even%20with%20Spare%20Capacity*%0A%0A%20%20%20%20We%20now%20combine%20arrivals%20(Poisson%20at%20rate%20%24%5Clambda%24)%20with%20a%20server%20(exponential%20service%20at%20rate%20%24%5Cmu%24)%20into%20a%20complete%20queue.%20%20The%20system%20is%20stable%20because%20%24%5Crho%20%3D%20%5Clambda%2F%5Cmu%20%3C%201%24%2C%20which%20means%20that%20on%20average%2C%20the%20server%20handles%20more%20work%20than%20arrives.%0A%0A%20%20%20%20Our%20first%20question%20is%2C%20how%20long%20is%20the%20queue%3F%20The%20surprising%20answer%20is%20that%20even%20when%20the%20server%20has%20plenty%20of%20spare%20capacity%2C%20customers%20wait.%20%20The%20mean%20number%20of%20customers%20in%20the%20system%20(both%20waiting%20and%20being%20served)%20is%3A%0A%0A%20%20%20%20%24%24L%20%3D%20%5Cfrac%7B%5Crho%7D%7B1%20-%20%5Crho%7D%24%24%0A%0A%20%20%20%20The%20table%20below%20gives%20some%20representative%20values%3A%0A%0A%20%20%20%20%7C%20%24%5Crho%24%20%7C%20%24L%24%20%7C%0A%20%20%20%20%7C%3A---%3A%7C%3A---%3A%7C%0A%20%20%20%20%7C%200.1%20%7C%200.11%20%7C%0A%20%20%20%20%7C%200.5%20%7C%201.00%20%7C%0A%20%20%20%20%7C%200.8%20%7C%204.00%20%7C%0A%20%20%20%20%7C%200.9%20%7C%209.00%20%7C%0A%0A%20%20%20%20When%20%24%5Crho%20%3D%200.5%24%2C%20half%20the%20server's%20capacity%20is%20idle%2C%20but%20there%20is%20on%20average%20one%20customer%20in%20the%20system%20at%20any%20moment.%20%20That%20customer%20either%20had%20to%20wait%20for%20a%20previous%20customer%2C%20or%20is%20currently%20being%20served.%20%20The%20queue%20is%20*never*%20consistently%20empty%2C%20even%20at%20moderate%20load.%0A%0A%20%20%20%20The%20formula%20also%20explains%20why%20simple%20queues%20are%20so%20sensitive%20to%20utilization%3A%20%24L%24%20blows%20up%20as%20%24%5Crho%20%5Cto%201%24.%20One%20way%20to%20think%20about%20this%20is%20that%20the%20denominator%20%24(1%20-%20%5Crho)%24%20is%20the%20spare%20capacity.%20As%20spare%20capacity%20vanishes%2C%20queue%20length%20increases.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Why%20Queues%20Form%20at%20All%0A%0A%20%20%20%20With%20deterministic%20arrivals%20and%20service%20(every%20customer%20arrives%20exactly%20%241%2F%5Clambda%24%20apart%20and%20takes%20exactly%20%241%2F%5Cmu%24)%2C%20a%20server%20with%20%24%5Crho%20%3C%201%24%20would%20never%20form%20a%20queue%3A%20each%20customer%20would%20depart%20before%20the%20next%20arrived.%20Randomness%20changes%20this.%20Sometimes%20three%20customers%20arrive%20close%20together%20before%20the%20server%20finishes%20even%20one%2C%20so%20the%20server%20falls%20briefly%20behind.%20While%20it%20recovers%2C%20customers%20wait.%20%20These%20temporary%20pileups%20are%20unavoidable%20whenever%20inter-arrival%20or%20service%20times%20have%20any%20variance.%0A%0A%20%20%20%20The%20probability%20that%20exactly%20%24n%24%20customers%20are%20in%20an%20M%2FM%2F1%20system%20at%20steady%20state%20is%3A%0A%0A%20%20%20%20%24%24P(N%20%3D%20n)%20%3D%20(1%20-%20%5Crho)%5C%2C%5Crho%5En%20%5Cqquad%20n%20%3D%200%2C%201%2C%202%2C%20%5Cldots%24%24%0A%0A%20%20%20%20This%20is%20a%20*geometric%20distribution*%20with%20success%20probability%20%241%20-%20%5Crho%24.%20The%20formula%20says%20the%20server%20is%20idle%20(i.e.%2C%20n%3D0)%20with%20probability%20%241%20-%20%5Crho%24%2C%20which%20is%20consistent%20with%20the%20utilization%20result%20from%20the%20previous%20scenario.%20Each%20additional%20customer%20in%20the%20system%20is%20%24%5Crho%24%20times%20less%20likely%20than%20the%20previous%20count.%0A%0A%20%20%20%20This%20formula%20%24L%20%3D%20%5Crho%2F(1-%5Crho)%24%20is%20the%20foundation%20of%20the%20later%20M%2FM%2F1%20nonlinearity%20scenario%2C%20which%20shows%20the%20practical%20consequences%20of%20the%20%24(1-%5Crho)%24%20denominator.%20Every%20queue-length%20formula%20in%20queueing%20theory%20has%20a%20similar%20structure%3A%20a%20traffic%20factor%20%24%5Crho%24%20divided%20by%20a%20spare-capacity%20factor%20%24(1%20-%20%5Crho)%24%2C%20possibly%20multiplied%20by%20a%20variability%20correction.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Implementation%0A%0A%20%20%20%20A%20%60Customer%60%20process%20increments%20a%20shared%20%60in_system%60%20counter%20on%20arrival%20and%20decrements%20it%20on%20departure.%20%20A%20%60Monitor%60%20process%20samples%20%60in_system%5B0%5D%60%20every%20%60SAMPLE_INTERVAL%60%20time%20units.%20%20After%20the%20simulation%2C%20the%20mean%20of%20the%20samples%20estimates%20%24L%24.%20%20The%20theoretical%20value%20%24%5Crho%2F(1-%5Crho)%24%20is%20computed%20and%20compared.%20By%20the%20law%20of%20large%20numbers%2C%20this%20converges%20to%20the%20true%20steady-state%20mean%20as%20the%20simulation%20time%20grows.%0A%0A%20%20%20%20The%20simulation%20sweeps%20%24%5Crho%24%20from%200.1%20to%200.9%2C%20confirming%20the%20formula%20at%20each%20load%20level.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(mo)%3A%0A%20%20%20%20sim_time_slider%20%3D%20mo.ui.slider(%0A%20%20%20%20%20%20%20%20start%3D0%2C%0A%20%20%20%20%20%20%20%20stop%3D100_000%2C%0A%20%20%20%20%20%20%20%20step%3D1_000%2C%0A%20%20%20%20%20%20%20%20value%3D20_000%2C%0A%20%20%20%20%20%20%20%20label%3D%22Simulation%20time%22%2C%0A%20%20%20%20)%0A%0A%20%20%20%20service_rate_slider%20%3D%20mo.ui.slider(%0A%20%20%20%20%20%20%20%20start%3D1.0%2C%0A%20%20%20%20%20%20%20%20stop%3D5.0%2C%0A%20%20%20%20%20%20%20%20step%3D0.01%2C%0A%20%20%20%20%20%20%20%20value%3D2.0%2C%0A%20%20%20%20%20%20%20%20label%3D%22Service%20rate%22%2C%0A%20%20%20%20)%0A%0A%20%20%20%20sample_interval_slider%20%3D%20mo.ui.slider(%0A%20%20%20%20%20%20%20%20start%3D1.0%2C%0A%20%20%20%20%20%20%20%20stop%3D5.0%2C%0A%20%20%20%20%20%20%20%20step%3D1.0%2C%0A%20%20%20%20%20%20%20%20value%3D1.0%2C%0A%20%20%20%20%20%20%20%20label%3D%22Sample%20interval%22%2C%0A%20%20%20%20)%0A%0A%20%20%20%20seed_input%20%3D%20mo.ui.number(%0A%20%20%20%20%20%20%20%20value%3D192%2C%0A%20%20%20%20%20%20%20%20step%3D1%2C%0A%20%20%20%20%20%20%20%20label%3D%22Random%20seed%22%2C%0A%20%20%20%20)%0A%0A%20%20%20%20run_button%20%3D%20mo.ui.button(label%3D%22Run%20simulation%22)%0A%0A%20%20%20%20mo.vstack(%5B%0A%20%20%20%20%20%20%20%20sim_time_slider%2C%0A%20%20%20%20%20%20%20%20service_rate_slider%2C%0A%20%20%20%20%20%20%20%20sample_interval_slider%2C%0A%20%20%20%20%20%20%20%20seed_input%2C%0A%20%20%20%20%20%20%20%20run_button%2C%0A%20%20%20%20%5D)%0A%20%20%20%20return%20(%0A%20%20%20%20%20%20%20%20sample_interval_slider%2C%0A%20%20%20%20%20%20%20%20seed_input%2C%0A%20%20%20%20%20%20%20%20service_rate_slider%2C%0A%20%20%20%20%20%20%20%20sim_time_slider%2C%0A%20%20%20%20)%0A%0A%0A%40app.cell%0Adef%20_(%0A%20%20%20%20sample_interval_slider%2C%0A%20%20%20%20seed_input%2C%0A%20%20%20%20service_rate_slider%2C%0A%20%20%20%20sim_time_slider%2C%0A)%3A%0A%20%20%20%20SIM_TIME%20%3D%20int(sim_time_slider.value)%0A%20%20%20%20SERVICE_RATE%20%3D%20float(service_rate_slider.value)%0A%20%20%20%20SAMPLE_INTERVAL%20%3D%20float(sample_interval_slider.value)%0A%20%20%20%20SEED%20%3D%20int(seed_input.value)%0A%20%20%20%20return%20SAMPLE_INTERVAL%2C%20SEED%2C%20SERVICE_RATE%2C%20SIM_TIME%0A%0A%0A%40app.cell%0Adef%20_(Process%2C%20SERVICE_RATE%2C%20random)%3A%0A%20%20%20%20class%20Customer(Process)%3A%0A%20%20%20%20%20%20%20%20def%20init(self%2C%20server%2C%20in_system)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20self.server%20%3D%20server%0A%20%20%20%20%20%20%20%20%20%20%20%20self.in_system%20%3D%20in_system%0A%0A%20%20%20%20%20%20%20%20async%20def%20run(self)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20self.in_system%5B0%5D%20%2B%3D%201%0A%20%20%20%20%20%20%20%20%20%20%20%20async%20with%20self.server%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20await%20self.timeout(random.expovariate(SERVICE_RATE))%0A%20%20%20%20%20%20%20%20%20%20%20%20self.in_system%5B0%5D%20-%3D%201%0A%0A%20%20%20%20return%20(Customer%2C)%0A%0A%0A%40app.cell%0Adef%20_(Customer%2C%20Process%2C%20random)%3A%0A%20%20%20%20class%20Arrivals(Process)%3A%0A%20%20%20%20%20%20%20%20def%20init(self%2C%20rate%2C%20server%2C%20in_system)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20self.rate%20%3D%20rate%0A%20%20%20%20%20%20%20%20%20%20%20%20self.server%20%3D%20server%0A%20%20%20%20%20%20%20%20%20%20%20%20self.in_system%20%3D%20in_system%0A%0A%20%20%20%20%20%20%20%20async%20def%20run(self)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20while%20True%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20await%20self.timeout(random.expovariate(self.rate))%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20Customer(self._env%2C%20self.server%2C%20self.in_system)%0A%0A%20%20%20%20return%20(Arrivals%2C)%0A%0A%0A%40app.cell%0Adef%20_(Process%2C%20SAMPLE_INTERVAL)%3A%0A%20%20%20%20class%20Monitor(Process)%3A%0A%20%20%20%20%20%20%20%20%22%22%22Samples%20total%20customers%20in%20system%20at%20regular%20intervals.%22%22%22%0A%0A%20%20%20%20%20%20%20%20def%20init(self%2C%20in_system%2C%20samples)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20self.in_system%20%3D%20in_system%0A%20%20%20%20%20%20%20%20%20%20%20%20self.samples%20%3D%20samples%0A%0A%20%20%20%20%20%20%20%20async%20def%20run(self)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20while%20True%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20self.samples.append(self.in_system%5B0%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20await%20self.timeout(SAMPLE_INTERVAL)%0A%0A%20%20%20%20return%20(Monitor%2C)%0A%0A%0A%40app.cell%0Adef%20_(%0A%20%20%20%20Arrivals%2C%0A%20%20%20%20Environment%2C%0A%20%20%20%20Monitor%2C%0A%20%20%20%20Resource%2C%0A%20%20%20%20SERVICE_RATE%2C%0A%20%20%20%20SIM_TIME%2C%0A%20%20%20%20statistics%2C%0A)%3A%0A%20%20%20%20def%20simulate(rho)%3A%0A%20%20%20%20%20%20%20%20arrival_rate%20%3D%20rho%20*%20SERVICE_RATE%0A%20%20%20%20%20%20%20%20env%20%3D%20Environment()%0A%20%20%20%20%20%20%20%20server%20%3D%20Resource(env%2C%20capacity%3D1)%0A%20%20%20%20%20%20%20%20in_system%20%3D%20%5B0%5D%0A%20%20%20%20%20%20%20%20samples%20%3D%20%5B%5D%0A%20%20%20%20%20%20%20%20Arrivals(env%2C%20arrival_rate%2C%20server%2C%20in_system)%0A%20%20%20%20%20%20%20%20Monitor(env%2C%20in_system%2C%20samples)%0A%20%20%20%20%20%20%20%20env.run(until%3DSIM_TIME)%0A%20%20%20%20%20%20%20%20sim_L%20%3D%20statistics.mean(samples)%0A%20%20%20%20%20%20%20%20theory_L%20%3D%20rho%20%2F%20(1.0%20-%20rho)%0A%20%20%20%20%20%20%20%20return%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%22rho%22%3A%20rho%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22sim_L%22%3A%20round(sim_L%2C%204)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22theory_L%22%3A%20round(theory_L%2C%204)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22error_pct%22%3A%20round(100.0%20*%20(sim_L%20-%20theory_L)%20%2F%20theory_L%2C%202)%2C%0A%20%20%20%20%20%20%20%20%7D%0A%0A%20%20%20%20return%20(simulate%2C)%0A%0A%0A%40app.cell%0Adef%20_(SEED%2C%20pl%2C%20random%2C%20simulate)%3A%0A%20%20%20%20def%20sweep()%3A%0A%20%20%20%20%20%20%20%20rows%20%3D%20%5Bsimulate(rho)%20for%20rho%20in%20%5B0.1%2C%200.2%2C%200.3%2C%200.4%2C%200.5%2C%200.6%2C%200.7%2C%200.8%2C%200.9%5D%5D%0A%20%20%20%20%20%20%20%20return%20pl.DataFrame(rows)%0A%0A%20%20%20%20random.seed(SEED)%0A%20%20%20%20df%20%3D%20sweep()%0A%20%20%20%20df%0A%20%20%20%20return%20(df%2C)%0A%0A%0A%40app.cell%0Adef%20_(alt%2C%20df)%3A%0A%20%20%20%20df_plot%20%3D%20df.unpivot(%0A%20%20%20%20%20%20%20%20on%3D%5B%22sim_L%22%2C%20%22theory_L%22%5D%2C%0A%20%20%20%20%20%20%20%20index%3D%22rho%22%2C%0A%20%20%20%20%20%20%20%20variable_name%3D%22source%22%2C%0A%20%20%20%20%20%20%20%20value_name%3D%22L%22%2C%0A%20%20%20%20)%0A%20%20%20%20chart%20%3D%20(%0A%20%20%20%20%20%20%20%20alt.Chart(df_plot)%0A%20%20%20%20%20%20%20%20.mark_line(point%3DTrue)%0A%20%20%20%20%20%20%20%20.encode(%0A%20%20%20%20%20%20%20%20%20%20%20%20x%3Dalt.X(%22rho%3AQ%22%2C%20title%3D%22Utilization%20(%CF%81)%22)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20y%3Dalt.Y(%22L%3AQ%22%2C%20title%3D%22Mean%20customers%20in%20system%20(L)%22)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20color%3Dalt.Color(%22source%3AN%22%2C%20title%3D%22Source%22)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20tooltip%3D%5B%22rho%3AQ%22%2C%20%22source%3AN%22%2C%20%22L%3AQ%22%5D%2C%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20.properties(title%3D%22Queue%20Formation%3A%20Simulated%20vs.%20Theoretical%20L%20%3D%20%CF%81%2F(1%E2%88%92%CF%81)%22)%0A%20%20%20%20)%0A%20%20%20%20chart%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Understanding%20the%20Math%0A%0A%20%20%20%20%23%23%23%20Why%20is%20the%20queue%20length%20geometric%3F%0A%0A%20%20%20%20The%20M%2FM%2F1%20queue%20can%20be%20analyzed%20as%20a%20random%20walk%20on%20the%20non-negative%20integers.%20%20When%20the%20server%20is%20busy%2C%20the%20queue%20grows%20by%201%20with%20each%20arrival%20(with%20rate%20%24%5Clambda%24)%20and%20shrinks%20by%201%20with%20each%20service%20completion%20(with%20rate%20%24%5Cmu%24).%20%20The%20ratio%20%24%5Clambda%2F%5Cmu%20%3D%20%5Crho%24%20is%20the%20probability%20that%20the%20queue%20grows%20rather%20than%20shrinks%20at%20the%20next%20event.%20Under%20steady%20state%2C%20the%20probability%20of%20being%20at%20level%20%24n%24%20is%20proportional%20to%20%24%5Crho%5En%24%20%E2%80%94%20because%20reaching%20level%20%24n%24%20requires%20%24n%24%20consecutive%20%22up%22%20steps.%20Normalizing%20so%20the%20probabilities%20sum%20to%201%20gives%20%24(1-%5Crho)%5Crho%5En%24.%0A%0A%20%20%20%20%23%23%23%20Deriving%20%24L%20%3D%20%5Crho%2F(1-%5Crho)%24%20from%20the%20geometric%20distribution%0A%0A%20%20%20%20Given%20%24P(N%20%3D%20n)%20%3D%20(1%20-%20%5Crho)%5Crho%5En%24%2C%20the%20mean%20is%3A%0A%0A%20%20%20%20%24%24L%20%3D%20E%5BN%5D%20%3D%20%5Csum_%7Bn%3D0%7D%5E%7B%5Cinfty%7D%20n%20%5Ccdot%20(1-%5Crho)%5Crho%5En%20%3D%20(1-%5Crho)%20%5Csum_%7Bn%3D0%7D%5E%7B%5Cinfty%7D%20n%5Crho%5En%24%24%0A%0A%20%20%20%20A%20result%20from%20basic%20calculus%20is%20that%20the%20geometric%20series%20%24%5Csum_%7Bn%3D0%7D%5E%7B%5Cinfty%7D%20%5Crho%5En%20%3D%201%2F(1-%5Crho)%24.%20%20Differentiating%20both%20sides%20with%20respect%20to%20%24%5Crho%24%3A%0A%0A%20%20%20%20%24%24%5Csum_%7Bn%3D0%7D%5E%7B%5Cinfty%7D%20n%5Crho%5E%7Bn-1%7D%20%3D%20%5Cfrac%7B1%7D%7B(1-%5Crho)%5E2%7D%24%24%0A%0A%20%20%20%20Multiply%20both%20sides%20by%20%24%5Crho%24%3A%0A%0A%20%20%20%20%24%24%5Csum_%7Bn%3D0%7D%5E%7B%5Cinfty%7D%20n%5Crho%5En%20%3D%20%5Cfrac%7B%5Crho%7D%7B(1-%5Crho)%5E2%7D%24%24%0A%0A%20%20%20%20Substituting%20back%3A%0A%0A%20%20%20%20%24%24L%20%3D%20(1-%5Crho)%20%5Ccdot%20%5Cfrac%7B%5Crho%7D%7B(1-%5Crho)%5E2%7D%20%3D%20%5Cfrac%7B%5Crho%7D%7B1-%5Crho%7D%24%24%0A%0A%20%20%20%20%23%23%23%20Checking%20the%20formula%20at%20the%20boundaries%0A%0A%20%20%20%20When%20%24%5Crho%20%5Cto%200%24%3A%20there%20are%20almost%20no%20arrivals%2C%20so%20%24L%20%5Cto%200%24%2C%20i.e.%2C%20the%20server%20is%20nearly%20always%20idle.%0A%0A%20%20%20%20When%20%24%5Crho%20%5Cto%201%24%3A%20the%20spare%20capacity%20is%20%24(1-%5Crho)%20%5Cto%200%24%2C%20so%20%24L%20%5Cto%20%5Cinfty%24%2C%20i.e.%2C%20the%20queue%20grows%20without%20bound.%0A%0A%20%20%20%20Both%20limits%20match%20physical%20intuition.%20%20Note%20that%20the%20formula%20is%20exact%20(not%20an%20approximation)%20for%20an%20M%2FM%2F1%20queues%20in%20steady%20state.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0Aif%20__name__%20%3D%3D%20%22__main__%22%3A%0A%20%20%20%20app.run()%0A