01 basic ideas

%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%20math%0A%20%20%20%20import%20random%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%20math%2C%20mo%2C%20pl%2C%20random%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%20Basic%20Ideas%20in%20Queueing%20Theory%0A%0A%20%20%20%20%23%23%20*Arrivals%2C%20Servers%2C%20and%20Utilization*%0A%0A%20%20%20%20Three%20concepts%20underpin%20every%20queueing%20model.%20The%20first%20is%20*Poisson%20arrivals*%3A%20when%20customers%20arrive%20independently%20at%20a%20constant%20average%20rate%20%24%5Clambda%24%2C%20gaps%20between%20consecutive%20arrivals%20follow%20an%20*exponential*%20distribution%20with%20mean%20%241%2F%5Clambda%24%2C%20and%20the%20count%20of%20arrivals%20in%20any%20window%20of%20width%20%24t%24%20follows%20a%20Poisson%20distribution%20with%20mean%20%24%5Clambda%20t%24.%20These%20two%20descriptions%20are%20equivalent%3A%20if%20one%20holds%2C%20the%20other%20must%20too.%0A%0A%20%20%20%20The%20second%20key%20idea%20is%20that%20the%20exponential%20distribution%20is%20*memoryless*.%20Knowing%20you%20have%20already%20waited%20%24s%24%20units%20gives%20no%20information%20about%20when%20the%20next%20arrival%20will%20come.%20This%20property%20makes%20the%20math%20simple%2C%20but%20means%20that%20the%20exponential%20distribution%20isn't%20a%20good%20fit%20for%20scenarios%20where%20events%20happen%20in%20bursts.%20Some%20of%20the%20later%20tutorials%20will%20explore%20models%20that%20handle%20this.%0A%0A%20%20%20%20The%20final%20concept%20is%20*server%20utilization*.%20A%20server%20completing%20work%20at%20rate%20%24%5Cmu%24%20has%20utilization%20%24%5Crho%20%3D%20%5Clambda%2F%5Cmu%24%2C%20which%20is%20the%20long-run%20fraction%20of%20time%20it%20is%20busy.%20The%20system%20is%20stable%20only%20when%20%24%5Crho%20%3C%201%24.%20When%20%24%5Crho%20%5Cgeq%201%24%2C%20arrivals%20outpace%20service%20and%20the%20queue%20grows%20without%20bound.%20Even%20at%20exact%20balance%20(%24%5Crho%20%3D%201%24)%2C%20randomness%20creates%20bursts%20that%20accumulate%20faster%20than%20the%20server%20recovers%2C%20so%20the%20expected%20queue%20length%20is%20infinite.%0A%0A%20%20%20%20The%20code%20below%20uses%20a%20discrete%20event%20simulation%20package%20called%20%5Basimpy%5D(https%3A%2F%2Fasimpy.readthedocs.io%2F)%20to%20model%20a%20simple%20job%20queue.%20The%20technical%20term%20for%20this%20kind%20of%20system%20is%20an%20*%5BM%2FM%2F1%20queue%5D(https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FM%2FM%2F1_queue)*%3A%20memoryless%20(Poisson)%20arrivals%2C%20memoryless%20service%20times%2C%20and%20one%20server.%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%0A%20%20%20%20)%0A%20%20%20%20arrival_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%22Arrival%20rate%20(%CE%BB)%22%0A%20%20%20%20)%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%20(%CE%BC)%22%0A%20%20%20%20)%0A%20%20%20%20window_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%3D1.0%2C%0A%20%20%20%20%20%20%20%20label%3D%22Counting%20window%22%0A%20%20%20%20)%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%0A%20%20%20%20)%0A%20%20%20%20run_button%20%3D%20mo.ui.button(label%3D%22Run%20simulation%22)%0A%20%20%20%20mo.vstack(%5Bsim_time_slider%2C%20arrival_rate_slider%2C%20service_rate_slider%2C%20window_slider%2C%20seed_input%2C%20run_button%5D)%0A%20%20%20%20return%20(%0A%20%20%20%20%20%20%20%20arrival_rate_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%20%20%20%20window_slider%2C%0A%20%20%20%20)%0A%0A%0A%40app.cell%0Adef%20_(%0A%20%20%20%20arrival_rate_slider%2C%0A%20%20%20%20random%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%20%20%20%20window_slider%2C%0A)%3A%0A%20%20%20%20SIM_TIME%20%3D%20int(sim_time_slider.value)%0A%20%20%20%20ARRIVAL_RATE%20%3D%20float(arrival_rate_slider.value)%0A%20%20%20%20SERVICE_RATE%20%3D%20float(service_rate_slider.value)%0A%20%20%20%20WINDOW%20%3D%20float(window_slider.value)%0A%20%20%20%20SEED%20%3D%20int(seed_input.value)%0A%20%20%20%20random.seed(SEED)%0A%20%20%20%20return%20ARRIVAL_RATE%2C%20SERVICE_RATE%2C%20SIM_TIME%2C%20WINDOW%0A%0A%0A%40app.cell%0Adef%20_(Process%2C%20random)%3A%0A%20%20%20%20class%20ArrivalSource(Process)%3A%0A%20%20%20%20%20%20%20%20%22%22%22Generates%20arrivals%20at%20a%20Poisson%20rate%20and%20records%20inter-arrival%20gaps.%22%22%22%0A%0A%20%20%20%20%20%20%20%20def%20init(self%2C%20rate%2C%20gaps)%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.gaps%20%3D%20gaps%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%20gap%20%3D%20random.expovariate(self.rate)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20await%20self.timeout(gap)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20self.gaps.append(gap)%0A%0A%20%20%20%20return%20(ArrivalSource%2C)%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%20total_service)%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.total_service%20%3D%20total_service%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%20async%20with%20self.server%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20svc%20%3D%20random.expovariate(SERVICE_RATE)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20await%20self.timeout(svc)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20self.total_service%5B0%5D%20%2B%3D%20svc%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%20total_service)%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.total_service%20%3D%20total_service%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.total_service)%0A%0A%20%20%20%20return%20(Arrivals%2C)%0A%0A%0A%40app.cell%0Adef%20_(%0A%20%20%20%20ARRIVAL_RATE%2C%0A%20%20%20%20ArrivalSource%2C%0A%20%20%20%20Environment%2C%0A%20%20%20%20SIM_TIME%2C%0A%20%20%20%20WINDOW%2C%0A%20%20%20%20alt%2C%0A%20%20%20%20math%2C%0A%20%20%20%20pl%2C%0A)%3A%0A%20%20%20%20def%20comparison()%3A%0A%20%20%20%20%20%20%20%20gaps%20%3D%20%5B%5D%0A%20%20%20%20%20%20%20%20env%20%3D%20Environment()%0A%20%20%20%20%20%20%20%20ArrivalSource(env%2C%20ARRIVAL_RATE%2C%20gaps)%0A%20%20%20%20%20%20%20%20env.run(until%3DSIM_TIME)%0A%20%20%20%20%20%20%20%20n%20%3D%20int(SIM_TIME%20%2F%20WINDOW)%0A%20%20%20%20%20%20%20%20counts%20%3D%20%5B0%5D%20*%20n%0A%20%20%20%20%20%20%20%20t%20%3D%200.0%0A%20%20%20%20%20%20%20%20for%20g%20in%20gaps%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20t%20%2B%3D%20g%0A%20%20%20%20%20%20%20%20%20%20%20%20w%20%3D%20int(t%20%2F%20WINDOW)%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20w%20%3C%20n%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20counts%5Bw%5D%20%2B%3D%201%0A%20%20%20%20%20%20%20%20freq%20%3D%20%7B%7D%0A%20%20%20%20%20%20%20%20for%20c%20in%20counts%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20freq%5Bc%5D%20%3D%20freq.get(c%2C%200)%20%2B%201%0A%20%20%20%20%20%20%20%20lam_w%20%3D%20ARRIVAL_RATE%20*%20WINDOW%0A%20%20%20%20%20%20%20%20return%20pl.DataFrame(%5B%0A%20%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22k%22%3A%20k%2C%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22observed%22%3A%20freq.get(k%2C%200)%20%2F%20n%2C%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22theory%22%3A%20(lam_w**k)%20*%20math.exp(-lam_w)%20%2F%20math.factorial(k)%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20k%20in%20range(max(counts)%20%2B%201)%0A%20%20%20%20%20%20%20%20%5D)%0A%0A%20%20%20%20_df%20%3D%20comparison().unpivot(%0A%20%20%20%20%20%20%20%20on%3D%5B%22observed%22%2C%20%22theory%22%5D%2C%20index%3D%22k%22%2C%20variable_name%3D%22source%22%2C%20value_name%3D%22probability%22%0A%20%20%20%20)%0A%20%20%20%20(%0A%20%20%20%20%20%20%20%20alt.Chart(_df).mark_bar(opacity%3D0.8)%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(%22k%3AO%22%2C%20title%3Df%22Arrivals%20per%20window%20(width%20%7BWINDOW%7D)%22)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20y%3Dalt.Y(%22probability%3AQ%22%2C%20title%3D%22Probability%22)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20color%3Dalt.Color(%22source%3AN%22%2C%20title%3D%22Series%22)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20xOffset%3D%22source%3AN%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20tooltip%3D%5B%22k%3AO%22%2C%20%22source%3AN%22%2C%20%22probability%3AQ%22%5D%2C%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20.properties(title%3Df%22Arrival%20Counts%3A%20Observed%20vs.%20Poisson(%CE%BB%3D%7BARRIVAL_RATE%7D)%22)%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(Arrivals%2C%20Environment%2C%20Resource%2C%20SERVICE_RATE%2C%20SIM_TIME)%3A%0A%20%20%20%20def%20simulate(rho)%3A%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%20total_service%20%3D%20%5B0.0%5D%0A%20%20%20%20%20%20%20%20Arrivals(env%2C%20rho%20*%20SERVICE_RATE%2C%20server%2C%20total_service)%0A%20%20%20%20%20%20%20%20env.run(until%3DSIM_TIME)%0A%20%20%20%20%20%20%20%20busy%20%3D%20total_service%5B0%5D%20%2F%20SIM_TIME%0A%20%20%20%20%20%20%20%20return%20%7B%22rho_target%22%3A%20rho%2C%20%22rho_observed%22%3A%20round(busy%2C%204)%2C%20%22idle_frac%22%3A%20round(1.0%20-%20busy%2C%204)%7D%0A%0A%20%20%20%20return%20(simulate%2C)%0A%0A%0A%40app.cell%0Adef%20_(pl%2C%20simulate)%3A%0A%20%20%20%20df_sim%20%3D%20pl.DataFrame(%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%2C%200.95%5D%5D)%0A%20%20%20%20df_sim%0A%20%20%20%20return%20(df_sim%2C)%0A%0A%0A%40app.cell%0Adef%20_(alt%2C%20df_sim)%3A%0A%20%20%20%20_df_plot%20%3D%20df_sim.unpivot(%0A%20%20%20%20%20%20%20%20on%3D%5B%22rho_observed%22%2C%20%22idle_frac%22%5D%2C%0A%20%20%20%20%20%20%20%20index%3D%22rho_target%22%2C%0A%20%20%20%20%20%20%20%20variable_name%3D%22metric%22%2C%0A%20%20%20%20%20%20%20%20value_name%3D%22fraction%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).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_target%3AQ%22%2C%20title%3D%22Target%20utilization%20(%CF%81%20%3D%20%CE%BB%2F%CE%BC)%22)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20y%3Dalt.Y(%22fraction%3AQ%22%2C%20title%3D%22Fraction%20of%20time%22)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20color%3Dalt.Color(%22metric%3AN%22%2C%20title%3D%22Metric%22)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20tooltip%3D%5B%22rho_target%3AQ%22%2C%20%22metric%3AN%22%2C%20%22fraction%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%22Server%20Utilization%3A%20Busy%20and%20Idle%20Fractions%20vs.%20%CF%81%22)%0A%20%20%20%20)%0A%20%20%20%20chart%0A%20%20%20%20return%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%23%20Understanding%20the%20Math%0A%0A%20%20%20%20%23%23%23%20Why%20inter-arrival%20gaps%20are%20exponential%0A%0A%20%20%20%20Divide%20%24%5B0%2C%20t%5D%24%20into%20%24n%24%20tiny%20slices%20of%20width%20%24%5CDelta%20%3D%20t%2Fn%24.%20The%20probability%20of%20an%20arrival%20in%20each%20slice%20is%20%24%5Capprox%20%5Clambda%5CDelta%24%3B%20slices%20are%20independent.%20The%20probability%20of%20no%20arrival%20across%20all%20%24n%24%20slices%20is%20%24(1%20-%20%5Clambda%20t%2Fn)%5En%20%5Cto%20e%5E%7B-%5Clambda%20t%7D%24%20as%20%24n%20%5Cto%20%5Cinfty%24.%20This%20is%20%24P(X%20%3E%20t)%24%20for%20the%20exponential%20distribution.%0A%0A%20%20%20%20%23%23%23%20Why%20mean%20equals%20standard%20deviation%20for%20the%20exponential%0A%0A%20%20%20%20If%20%24E%5BX%5D%20%3D%201%2F%5Clambda%24%2C%20then%20%24E%5BX%5E2%5D%20%3D%202%2F%5Clambda%5E2%24%2C%20so%20%24%5Ctext%7BVar%7D(X)%20%3D%202%2F%5Clambda%5E2%20-%201%2F%5Clambda%5E2%20%3D%201%2F%5Clambda%5E2%24%20and%20%24%5Ctext%7BSD%7D(X)%20%3D%201%2F%5Clambda%20%3D%20E%5BX%5D%24.%20Equal%20mean%20and%20standard%20deviation%20means%20roughly%20one-third%20of%20gaps%20are%20longer%20than%20the%20mean.%0A%0A%20%20%20%20%23%23%23%20Why%20the%20busy%20fraction%20equals%20%24%5Crho%24%0A%0A%20%20%20%20Over%20a%20long%20run%20%24T%24%2C%20about%20%24N%20%5Capprox%20%5Clambda%20T%24%20customers%20are%20served%2C%20each%20occupying%20the%20server%20for%20mean%20%241%2F%5Cmu%24.%20Total%20service%20time%20%24%5Capprox%20N%2F%5Cmu%20%3D%20%5Clambda%20T%2F%5Cmu%20%3D%20%5Crho%20T%24.%20Dividing%20by%20%24T%24%20gives%20busy%20fraction%20%24%3D%20%5Crho%24.%0A%0A%20%20%20%20%23%23%23%20Why%20%24%5Crho%20%3D%201%24%20is%20unstable%0A%0A%20%20%20%20At%20exact%20balance%2C%20the%20queue%20length%20after%20each%20service%20completion%20performs%20a%20symmetric%20random%20walk%20on%20the%20non-negative%20integers.%20This%20random%20walk%20is%20*null%20recurrent*%3A%20it%20returns%20to%20zero%20but%20with%20infinite%20expected%20return%20time%2C%20so%20the%20mean%20queue%20length%20is%20infinite%20even%20when%20arrivals%20and%20service%20are%20perfectly%20matched%20on%20average.%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