04 sojourn time

%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%20Sojourn%20Time%0A%0A%20%20%20%20%23%23%20*How%20Long%20Does%20a%20Customer%20Actually%20Spend%20in%20the%20System%3F*%0A%0A%20%20%20%20The%20previous%20scenario%20measured%20%24L%24%2C%20the%20mean%20number%20of%20customers%20in%20the%20system%20at%20any%20moment.%20This%20scenario%20measures%20%24W%24%2C%20the%20mean%20time%20a%20single%20customer%20spends%20from%20arrival%20to%20departure.%20This%20is%20called%20the%20*sojourn%20time*%2C%20*residence%20time*%2C%20or%20*response%20time*%2C%20and%20has%20two%20components%3A%0A%0A%20%20%20%20-%20%24W_q%24%3A%20time%20spent%20waiting%20in%20the%20queue%20because%20the%20server%20is%20busy.%0A%20%20%20%20-%20%24W_s%24%3A%20time%20spent%20in%20service%20while%20the%20server%20is%20working%20on%20this%20customer.%0A%0A%20%20%20%20%24%24W%20%3D%20W_q%20%2B%20W_s%24%24%0A%20%20%20%20%22%22%22)%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%20The%20Surprising%20Finding%0A%0A%20%20%20%20For%20an%20M%2FM%2F1%20queue%2C%20the%20mean%20sojourn%20time%20is%3A%0A%0A%20%20%20%20%24%24W%20%3D%20%5Cfrac%7B1%7D%7B%5Cmu(1%20-%20%5Crho)%7D%24%24%0A%0A%20%20%20%20This%20blows%20up%20as%20%24%5Crho%20%5Cto%201%24%2C%20just%20like%20%24L%24.%20But%20the%20split%20between%20waiting%20and%20service%20shifts%20dramatically%20as%20load%20increases.%0A%0A%20%20%20%20%7C%20%24%5Crho%24%20%7C%20%24W_q%24%20(wait)%20%7C%20%24W_s%24%20(service)%20%7C%20%24W%24%20(total)%20%7C%0A%20%20%20%20%7C%3A---%3A%7C%3A---%3A%7C%3A---%3A%7C%3A---%3A%7C%0A%20%20%20%20%7C%200.1%20%7C%200.11%20%7C%201.00%20%7C%201.11%20%7C%0A%20%20%20%20%7C%200.5%20%7C%201.00%20%7C%201.00%20%7C%202.00%20%7C%0A%20%20%20%20%7C%200.9%20%7C%209.00%20%7C%201.00%20%7C%2010.00%20%7C%0A%0A%20%20%20%20The%20mean%20service%20time%20%24W_s%20%3D%201%2F%5Cmu%20%3D%201.0%24%20is%20constant%3A%20the%20server%20always%20takes%20the%20same%20average%20time%20to%20serve%20one%20customer.%20All%20the%20extra%20delay%20at%20high%20load%20is%20pure%20waiting%3A%20%24W_q%20%3D%20%5Crho%2F(%5Cmu(1-%5Crho))%24%20grows%20without%20bound%20while%20%24W_s%24%20stays%20fixed.%20At%20%24%5Crho%20%3D%200.9%24%2C%2090%25%20of%20a%20customer's%20time%20is%20spent%20waiting%20for%20the%20server%20to%20become%20free.%0A%0A%20%20%20%20This%20formula%20is%20closely%20connected%20to%20Little's%20Law%3A%0A%0A%20%20%20%20%24%24L%20%3D%20%5Clambda%20W%24%24%0A%0A%20%20%20%20Plugging%20in%20%24W%20%3D%201%2F(%5Cmu(1-%5Crho))%24%20and%20%24%5Clambda%20%3D%20%5Crho%5Cmu%24%3A%0A%0A%20%20%20%20%24%24L%20%3D%20%5Crho%5Cmu%20%5Ccdot%20%5Cfrac%7B1%7D%7B%5Cmu(1-%5Crho)%7D%20%3D%20%5Cfrac%7B%5Crho%7D%7B1-%5Crho%7D%24%24%0A%20%20%20%20%22%22%22)%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%20Implementation%0A%0A%20%20%20%20%60Customer%60%20records%20its%20arrival%20time%2C%20then%20captures%20the%20exact%20moment%20it%20enters%20service%20(%60service_start%20%3D%20self.now%60%20inside%20the%20%60async%20with%20self.server%3A%60%20block%2C%20which%20only%20executes%20once%20the%20resource%20is%20acquired).%20The%20wait%20time%20is%20%60service_start%20%E2%88%92%20arrival%60%20and%20the%20sojourn%20time%20is%20%60departure%20%E2%88%92%20arrival%60.%0A%0A%20%20%20%20A%20%60Monitor%60%20samples%20the%20%60in_system%60%20counter%20periodically%20to%20estimate%20%24L%24%20independently.%20The%20final%20dataframe%20reports%20%24W_q%24%2C%20%24W_s%24%2C%20%24W%24%2C%20the%20theoretical%20%24W%24%2C%20%24L%24%20from%20sampling%2C%20and%20%24L%24%20from%20Little's%20Law%2C%20allowing%20all%20three%20to%20be%20cross-checked.%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%3D1.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%2C%20sojourn_times%2C%20wait_times)%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%20%20%20%20%20%20%20%20%20%20%20%20self.sojourn_times%20%3D%20sojourn_times%0A%20%20%20%20%20%20%20%20%20%20%20%20self.wait_times%20%3D%20wait_times%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%20arrival%20%3D%20self.now%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%20service_start%20%3D%20self.now%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%20%20%20%20%20%20%20%20%20%20%20%20self.sojourn_times.append(self.now%20-%20arrival)%0A%20%20%20%20%20%20%20%20%20%20%20%20self.wait_times.append(service_start%20-%20arrival)%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%2C%20sojourn_times%2C%20wait_times)%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%20%20%20%20%20%20%20%20%20%20%20%20self.sojourn_times%20%3D%20sojourn_times%0A%20%20%20%20%20%20%20%20%20%20%20%20self.wait_times%20%3D%20wait_times%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%2C%20self.sojourn_times%2C%20self.wait_times)%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%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%20rate%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%20sojourn_times%20%3D%20%5B%5D%0A%20%20%20%20%20%20%20%20wait_times%20%3D%20%5B%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%20rate%2C%20server%2C%20in_system%2C%20sojourn_times%2C%20wait_times)%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%20mean_W%20%3D%20statistics.mean(sojourn_times)%0A%20%20%20%20%20%20%20%20mean_Wq%20%3D%20statistics.mean(wait_times)%0A%20%20%20%20%20%20%20%20mean_Ws%20%3D%20mean_W%20-%20mean_Wq%0A%20%20%20%20%20%20%20%20mean_L%20%3D%20statistics.mean(samples)%0A%20%20%20%20%20%20%20%20lam%20%3D%20len(sojourn_times)%20%2F%20SIM_TIME%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%22mean_Wq%22%3A%20round(mean_Wq%2C%204)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22mean_Ws%22%3A%20round(mean_Ws%2C%204)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22mean_W%22%3A%20round(mean_W%2C%204)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22theory_W%22%3A%20round(1.0%20%2F%20(SERVICE_RATE%20*%20(1.0%20-%20rho))%2C%204)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22L_sampled%22%3A%20round(mean_L%2C%204)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22L_little%22%3A%20round(lam%20*%20mean_W%2C%204)%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%20random.seed(SEED)%0A%20%20%20%20df%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%5D%5D)%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.select(%5B%22rho%22%2C%20%22mean_Wq%22%2C%20%22mean_Ws%22%5D).unpivot(%0A%20%20%20%20%20%20%20%20on%3D%5B%22mean_Wq%22%2C%20%22mean_Ws%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%22component%22%2C%0A%20%20%20%20%20%20%20%20value_name%3D%22time%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_area()%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(%22time%3AQ%22%2C%20title%3D%22Mean%20time%22%2C%20stack%3D%22zero%22)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20color%3Dalt.Color(%22component%3AN%22%2C%20title%3D%22Component%22)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20tooltip%3D%5B%22rho%3AQ%22%2C%20%22component%3AN%22%2C%20%22time%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%22Sojourn%20Time%20Components%3A%20Wq%20(waiting)%20%2B%20Ws%20(service)%20%3D%20W%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%20%24W_s%20%3D%201%2F%5Cmu%24%20regardless%20of%20%24%5Crho%24%0A%0A%20%20%20%20Service%20time%20is%20drawn%20from%20an%20exponential%20distribution%20with%20rate%20%24%5Cmu%24%2C%20so%20its%20mean%20is%20%241%2F%5Cmu%24.%20This%20is%20a%20property%20of%20the%20distribution%2C%20not%20of%20the%20queue.%20No%20matter%20how%20busy%20the%20server%20is%2C%20once%20it%20starts%20serving%20you%20it%20takes%20on%20average%20%241%2F%5Cmu%24%20time.%0A%0A%20%20%20%20%23%23%23%20Deriving%20%24W_q%24%0A%0A%20%20%20%20Since%20%24W%20%3D%20W_q%20%2B%20W_s%24%20and%20%24W_s%20%3D%201%2F%5Cmu%24%3A%0A%0A%20%20%20%20%24%24W_q%20%3D%20W%20-%20W_s%20%3D%20%5Cfrac%7B1%7D%7B%5Cmu(1-%5Crho)%7D%20-%20%5Cfrac%7B1%7D%7B%5Cmu%7D%0A%20%20%20%20%20%20%20%20%20%20%3D%20%5Cfrac%7B1%7D%7B%5Cmu%7D%5Cleft(%5Cfrac%7B1%7D%7B1-%5Crho%7D%20-%201%5Cright)%0A%20%20%20%20%20%20%20%20%20%20%3D%20%5Cfrac%7B1%7D%7B%5Cmu%7D%20%5Ccdot%20%5Cfrac%7B%5Crho%7D%7B1-%5Crho%7D%0A%20%20%20%20%20%20%20%20%20%20%3D%20%5Cfrac%7B%5Crho%7D%7B%5Cmu(1-%5Crho)%7D%24%24%0A%0A%20%20%20%20Note%20that%20%24W_q%20%3D%20%5Crho%20%5Ccdot%20W%24%3A%20at%20high%20load%2C%20almost%20all%20of%20%24W%24%20is%20waiting.%0A%0A%20%20%20%20%23%23%23%20Units%20check%0A%0A%20%20%20%20%24%5Clambda%24%20has%20units%20of%20%5Bcustomers%2Ftime%5D%3B%20%24W%24%20has%20units%20of%20%5Btime%5D%3B%20so%20%24L%20%3D%20%5Clambda%20W%24%20has%20units%20of%20%5Bcustomers%2Ftime%20%24%5Ctimes%24%20time%5D%20%24%3D%24%20%5Bcustomers%5D.%20This%20count%20of%20people%20is%20dimensionless%2C%20as%20it%20should%20be.%20Checking%20units%20this%20way%20is%20a%20quick%20sanity%20test%20whenever%20you%20apply%20Little's%20Law%20to%20a%20real%20problem.%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