07 late merge

%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%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%20Event%2C%20Process%2C%20Queue%0A%0A%20%20%20%20return%20Environment%2C%20Event%2C%20Process%2C%20Queue%2C%20alt%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%20Late%20Merge%0A%0A%20%20%20%20%23%23%20*Courtesy%20Reduces%20Throughput*%0A%0A%20%20%20%20A%20two-lane%20road%20narrows%20to%20one%20lane%20at%20a%20construction%20zone.%20Drivers%20face%20a%20choice%3A%0A%0A%20%20%20%20-%20Early%20(courtesy)%20merge%3A%20upon%20seeing%20the%20%22Lane%20Ends%20Ahead%22%20sign%2C%20drivers%20immediately%20move%20from%20the%20closing%20lane%20into%20the%20open%20lane.%0A%20%20%20%20-%20Late%20(zipper)%20merge%3A%20drivers%20use%20both%20lanes%20all%20the%20way%20to%20the%20merge%20point%2C%20then%20alternate%20%E2%80%94%20one%20car%20from%20each%20lane%20in%20turn%2C%20like%20a%20zipper.%0A%0A%20%20%20%20It%20turns%20out%20that%20late%20merging%20produces%20higher%20throughput%20and%20shorter%20queues%20than%20early%20merging%2C%20even%20though%20it%20feels%20less%20polite.%20Early%20merging%20creates%20a%20single%20long%20queue%20that%20wastes%20the%20closing%20lane's%20capacity.%20Late%20merging%20fully%20utilises%20both%20lanes%20up%20to%20the%20bottleneck%2C%20then%20processes%20cars%20at%20the%20same%20rate%20with%20a%20zipper%20pattern.%20This%20result%20is%20not%20merely%20theoretical%3A%20the%20Minnesota%20Department%20of%20Transportation%2C%20the%20German%20ADAC%2C%20and%20the%20UK%20Highway%20Code%20all%20recommend%20late%20merging%20in%20slow-moving%20traffic%20precisely%20because%20it%20is%20provably%20more%20efficient.%0A%0A%20%20%20%20The%20primary%20benefit%20of%20late%20merging%20is%20higher%20throughput%3A%20more%20cars%20complete%20the%20merge%20per%20unit%20time.%20Mean%20sojourn%20time%20for%20individual%20cars%20may%20actually%20be%20slightly%20longer%20under%20late%20merge%2C%20because%20the%20larger%20total%20buffer%20admits%20more%20cars%20into%20the%20system%2C%20increasing%20average%20queue%20occupancy.%20By%20Little's%20Law%20%24L%20%3D%20%5Clambda%20W%24%2C%20if%20%24%5Clambda%24%20grows%20faster%20than%20%24L%24%20falls%2C%20%24W%24%20rises.%20This%20is%20not%20a%20disadvantage%3A%20it%20means%20more%20drivers%20successfully%20pass%20through%20rather%20than%20being%20turned%20away.%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%20Why%20Early%20Merging%20Hurts%0A%0A%20%20%20%20With%20early%20merging%3A%0A%0A%20%20%20%20-%20All%20%24N%24%20cars%20queue%20in%20one%20lane%20of%20capacity%20%24K%24.%0A%20%20%20%20-%20When%20the%20single%20queue%20is%20full%20(%24K%24%20cars)%2C%20arriving%20cars%20are%20turned%20away%20(blocking)%2C%20reducing%20throughput.%0A%20%20%20%20-%20The%20merge%20point%20processes%20at%20rate%20%24%5Cmu%24%20regardless%2C%20but%20there%20are%20fewer%20cars%20available%20to%20process%20(the%20second%20lane%20is%20empty%20and%20wasted).%0A%0A%20%20%20%20With%20late%20merging%3A%0A%0A%20%20%20%20-%20Cars%20distribute%20across%20two%20lanes%2C%20each%20of%20capacity%20%24K%24%20(total%20%242K%24).%0A%20%20%20%20-%20The%20merge%20point%20receives%20supply%20from%20both%20lanes%2C%20reducing%20starvation.%0A%20%20%20%20-%20Blocking%20occurs%20only%20when%20*both*%20lanes%20are%20simultaneously%20full%2C%20a%20rarer%20event.%0A%0A%20%20%20%20The%20key%20metric%20is%20the%20*blocking%20probability*%3A%20the%20fraction%20of%20arriving%20cars%20turned%20away%20because%20the%20pre-merge%20buffer%20is%20full.%20Let%20%24%5Crho%20%3D%20%5Clambda%2F%5Cmu%24%20be%20the%20utilisation%20of%20the%20merge%20bottleneck.%20For%20a%20finite-buffer%20M%2FM%2F1%2FK%20queue%20the%20blocking%20probability%20is%3A%0A%0A%20%20%20%20%24%24P_%7B%5Ctext%7Bblock%7D%7D%20%3D%20%5Cfrac%7B(1-%5Crho)%5Crho%5EK%7D%7B1%20-%20%5Crho%5E%7BK%2B1%7D%7D%24%24%0A%0A%20%20%20%20Early%20merge%20has%20buffer%20%24K%24%3B%20late%20merge%20effectively%20has%20buffer%20%242K%24%20(spread%20across%20two%20lanes).%20Since%20%24P_%7B%5Ctext%7Bblock%7D%7D%24%20decreases%20exponentially%20in%20%24K%24%2C%20doubling%20the%20available%20buffer%20dramatically%20reduces%20blocking.%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-%20**Early%20merge**%3A%20one%20%60Queue(max_capacity%3DLANE_CAPACITY)%60%20feeds%20a%20single%20%60MergeServer%60.%20Arrivals%20that%20find%20the%20lane%20full%20are%20counted%20as%20blocked%20and%20turned%20away.%0A%20%20%20%20-%20**Late%20merge**%3A%20two%20%60Queue(max_capacity%3DLANE_CAPACITY)%60%20instances%20feed%20a%20zipper%20%60MergeServer%60%20that%20alternates%20between%20lanes.%20Arrivals%20pick%20the%20shorter%20lane%3B%20a%20car%20is%20blocked%20only%20if%20its%20chosen%20lane%20is%20full.%0A%0A%20%20%20%20Both%20systems%20have%20the%20same%20total%20arrival%20rate%20%24%5Clambda%24%20and%20merge%20service%20rate%20%24%5Cmu%24.%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%20lane_capacity_slider%20%3D%20mo.ui.slider(%0A%20%20%20%20%20%20%20%20start%3D2%2C%0A%20%20%20%20%20%20%20%20stop%3D30%2C%0A%20%20%20%20%20%20%20%20step%3D1%2C%0A%20%20%20%20%20%20%20%20value%3D10%2C%0A%20%20%20%20%20%20%20%20label%3D%22Lane%20capacity%20(K)%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%20lane_capacity_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%20lane_capacity_slider%2C%20seed_input%2C%20sim_time_slider%0A%0A%0A%40app.cell%0Adef%20_(lane_capacity_slider%2C%20seed_input%2C%20sim_time_slider)%3A%0A%20%20%20%20SIM_TIME%20%3D%20int(sim_time_slider.value)%0A%20%20%20%20LANE_CAPACITY%20%3D%20int(lane_capacity_slider.value)%0A%20%20%20%20SEED%20%3D%20int(seed_input.value)%0A%20%20%20%20ARRIVAL_RATE%20%3D%201.85%0A%20%20%20%20MERGE_RATE%20%3D%202.0%0A%20%20%20%20RHO%20%3D%20ARRIVAL_RATE%20%2F%20MERGE_RATE%0A%20%20%20%20return%20ARRIVAL_RATE%2C%20LANE_CAPACITY%2C%20MERGE_RATE%2C%20RHO%2C%20SEED%2C%20SIM_TIME%0A%0A%0A%40app.cell%0Adef%20_(Event%2C%20Process)%3A%0A%20%20%20%20class%20EarlyMergeCar(Process)%3A%0A%20%20%20%20%20%20%20%20def%20init(self%2C%20lane%2C%20sojourn_times%2C%20blocked)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20self.lane%20%3D%20lane%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.blocked%20%3D%20blocked%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%20if%20self.lane.is_full()%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20self.blocked.append(1)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%0A%20%20%20%20%20%20%20%20%20%20%20%20done%20%3D%20Event(self._env)%0A%20%20%20%20%20%20%20%20%20%20%20%20await%20self.lane.put((arrival%2C%20done))%0A%20%20%20%20%20%20%20%20%20%20%20%20await%20done%0A%20%20%20%20%20%20%20%20%20%20%20%20self.sojourn_times.append(self.now%20-%20arrival)%0A%0A%20%20%20%20return%20(EarlyMergeCar%2C)%0A%0A%0A%40app.cell%0Adef%20_(Event%2C%20Process)%3A%0A%20%20%20%20class%20LateMergeCar(Process)%3A%0A%20%20%20%20%20%20%20%20def%20init(self%2C%20lane1%2C%20lane2%2C%20sojourn_times%2C%20blocked)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20self.lane1%20%3D%20lane1%0A%20%20%20%20%20%20%20%20%20%20%20%20self.lane2%20%3D%20lane2%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.blocked%20%3D%20blocked%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%20target%20%3D%20(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20self.lane1%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20len(self.lane1._items)%20%3C%3D%20len(self.lane2._items)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20else%20self.lane2%0A%20%20%20%20%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20target.is_full()%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20self.blocked.append(1)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%0A%20%20%20%20%20%20%20%20%20%20%20%20done%20%3D%20Event(self._env)%0A%20%20%20%20%20%20%20%20%20%20%20%20await%20target.put((arrival%2C%20done))%0A%20%20%20%20%20%20%20%20%20%20%20%20await%20done%0A%20%20%20%20%20%20%20%20%20%20%20%20self.sojourn_times.append(self.now%20-%20arrival)%0A%0A%20%20%20%20return%20(LateMergeCar%2C)%0A%0A%0A%40app.cell%0Adef%20_(MERGE_RATE%2C%20Process%2C%20random)%3A%0A%20%20%20%20class%20MergeServer(Process)%3A%0A%20%20%20%20%20%20%20%20def%20init(self%2C%20lanes%2C%20zipper)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20self.lanes%20%3D%20lanes%0A%20%20%20%20%20%20%20%20%20%20%20%20self.zipper%20%3D%20zipper%0A%20%20%20%20%20%20%20%20%20%20%20%20self._turn%20%3D%200%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%20if%20self.zipper%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20served%20%3D%20False%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20for%20_%20in%20range(len(self.lanes))%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20idx%20%3D%20self._turn%20%25%20len(self.lanes)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20self._turn%20%2B%3D%201%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20not%20self.lanes%5Bidx%5D.is_empty()%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_%2C%20arrival%2C%20done%20%3D%20(self.now%2C)%20%2B%20(await%20self.lanes%5Bidx%5D.get())%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20await%20self.timeout(random.expovariate(MERGE_RATE))%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20done.succeed()%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20served%20%3D%20True%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20break%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20not%20served%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20await%20self.timeout(0.05)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_%2C%20arrival%2C%20done%20%3D%20(self.now%2C)%20%2B%20(await%20self.lanes%5B0%5D.get())%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20await%20self.timeout(random.expovariate(MERGE_RATE))%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20done.succeed()%0A%0A%0A%20%20%20%20return%20(MergeServer%2C)%0A%0A%0A%40app.cell%0Adef%20_(ARRIVAL_RATE%2C%20EarlyMergeCar%2C%20LateMergeCar%2C%20Process%2C%20random)%3A%0A%20%20%20%20class%20ArrivalStream(Process)%3A%0A%20%20%20%20%20%20%20%20def%20init(self%2C%20lanes%2C%20sojourn_times%2C%20blocked%2C%20zipper)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20self.lanes%20%3D%20lanes%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.blocked%20%3D%20blocked%0A%20%20%20%20%20%20%20%20%20%20%20%20self.zipper%20%3D%20zipper%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(ARRIVAL_RATE))%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20self.zipper%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20LateMergeCar(self._env%2C%20self.lanes%5B0%5D%2C%20self.lanes%5B1%5D%2C%20self.sojourn_times%2C%20self.blocked)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20EarlyMergeCar(self._env%2C%20self.lanes%5B0%5D%2C%20self.sojourn_times%2C%20self.blocked)%0A%0A%20%20%20%20return%20(ArrivalStream%2C)%0A%0A%0A%40app.cell%0Adef%20_(ArrivalStream%2C%20Environment%2C%20MergeServer%2C%20Queue%2C%20SEED%2C%20SIM_TIME%2C%20random)%3A%0A%20%20%20%20def%20run_scenario(zipper%2C%20k)%3A%0A%20%20%20%20%20%20%20%20random.seed(SEED)%0A%20%20%20%20%20%20%20%20env%20%3D%20Environment()%0A%20%20%20%20%20%20%20%20sojourn_times%20%3D%20%5B%5D%0A%20%20%20%20%20%20%20%20blocked%20%3D%20%5B%5D%0A%0A%20%20%20%20%20%20%20%20if%20zipper%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20lanes%20%3D%20%5BQueue(env%2C%20max_capacity%3Dk)%2C%20Queue(env%2C%20max_capacity%3Dk)%5D%0A%20%20%20%20%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20lanes%20%3D%20%5BQueue(env%2C%20max_capacity%3Dk)%5D%0A%20%20%20%20%20%20%20%20ArrivalStream(env%2C%20lanes%2C%20sojourn_times%2C%20blocked%2C%20zipper)%0A%20%20%20%20%20%20%20%20MergeServer(env%2C%20lanes%2C%20zipper)%0A%20%20%20%20%20%20%20%20env.run(until%3DSIM_TIME)%0A%20%20%20%20%20%20%20%20total%20%3D%20len(sojourn_times)%20%2B%20len(blocked)%0A%20%20%20%20%20%20%20%20blocked_pct%20%3D%20100.0%20*%20len(blocked)%20%2F%20total%20if%20total%20else%200.0%0A%20%20%20%20%20%20%20%20throughput%20%3D%20len(sojourn_times)%20%2F%20SIM_TIME%0A%20%20%20%20%20%20%20%20mean_sojourn%20%3D%20sum(sojourn_times)%20%2F%20len(sojourn_times)%20if%20sojourn_times%20else%200.0%0A%20%20%20%20%20%20%20%20return%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%22throughput%22%3A%20throughput%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22blocked_pct%22%3A%20blocked_pct%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22mean_sojourn%22%3A%20mean_sojourn%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22total_buffer%22%3A%20k%20*%20(2%20if%20zipper%20else%201)%2C%0A%20%20%20%20%20%20%20%20%7D%0A%0A%20%20%20%20return%20(run_scenario%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(ARRIVAL_RATE%2C%20MERGE_RATE%2C%20RHO%2C%20mo)%3A%0A%20%20%20%20mo.md(f%22%22%22%0A%20%20%20%20%23%23%20Main%20Results%0A%0A%20%20%20%20Arrival%20rate%3A%20%7BARRIVAL_RATE%7D%2Funit%2C%20merge%20service%20rate%3A%20%7BMERGE_RATE%7D%2Funit%2C%0A%20%20%20%20utilisation%20%CF%81%20%3D%20%7BRHO%3A.3f%7D%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(LANE_CAPACITY%2C%20pl%2C%20run_scenario)%3A%0A%20%20%20%20early%20%3D%20run_scenario(zipper%3DFalse%2C%20k%3DLANE_CAPACITY)%0A%20%20%20%20late%20%3D%20run_scenario(zipper%3DTrue%2C%20k%3DLANE_CAPACITY)%0A%20%20%20%20df_main%20%3D%20pl.DataFrame(%5B%0A%20%20%20%20%20%20%20%20%7B%22strategy%22%3A%20%22early%22%2C%20**early%7D%2C%0A%20%20%20%20%20%20%20%20%7B%22strategy%22%3A%20%22late%22%2C%20**late%7D%2C%0A%20%20%20%20%5D)%0A%20%20%20%20df_main%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(%22%22%22%0A%20%20%20%20%23%23%20Effect%20of%20Buffer%20Size%20on%20Blocking%20Rate%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(pl%2C%20run_scenario)%3A%0A%20%20%20%20def%20sweep()%3A%0A%20%20%20%20%20%20%20%20sweep_rows%20%3D%20%5B%5D%0A%20%20%20%20%20%20%20%20for%20k%20in%20%5B5%2C%2010%2C%2015%2C%2020%2C%2030%5D%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20ep%20%3D%20run_scenario(zipper%3DFalse%2C%20k%3Dk)%5B%22blocked_pct%22%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20lp%20%3D%20run_scenario(zipper%3DTrue%2C%20k%3Dk)%5B%22blocked_pct%22%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20sweep_rows.append(%7B%22buffer_k%22%3A%20k%2C%20%22early_blocked_pct%22%3A%20ep%2C%20%22late_blocked_pct%22%3A%20lp%7D)%0A%20%20%20%20%20%20%20%20return%20pl.DataFrame(sweep_rows)%0A%0A%20%20%20%20df_sweep%20%3D%20sweep()%0A%20%20%20%20df_sweep%0A%20%20%20%20return%20(df_sweep%2C)%0A%0A%0A%40app.cell%0Adef%20_(alt%2C%20df_sweep)%3A%0A%20%20%20%20df_plot%20%3D%20df_sweep.unpivot(%0A%20%20%20%20%20%20%20%20on%3D%5B%22early_blocked_pct%22%2C%20%22late_blocked_pct%22%5D%2C%0A%20%20%20%20%20%20%20%20index%3D%22buffer_k%22%2C%0A%20%20%20%20%20%20%20%20variable_name%3D%22strategy%22%2C%0A%20%20%20%20%20%20%20%20value_name%3D%22blocked_pct%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(%22buffer_k%3AQ%22%2C%20title%3D%22Buffer%20size%20per%20lane%20(K)%22)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20y%3Dalt.Y(%22blocked_pct%3AQ%22%2C%20title%3D%22Blocked%20cars%20(%25)%22)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20color%3Dalt.Color(%22strategy%3AN%22%2C%20title%3D%22Merge%20strategy%22)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20tooltip%3D%5B%22buffer_k%3AQ%22%2C%20%22strategy%3AN%22%2C%20%22blocked_pct%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%22Late%20Merge%3A%20Blocked%20Cars%20vs.%20Buffer%20Size%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%20The%20finite-buffer%20formula%0A%0A%20%20%20%20For%20a%20queue%20with%20random%20arrivals%2C%20exponential%20service%2C%20a%20single%20server%2C%20and%20a%20buffer%20that%20holds%20at%20most%20%24K%24%20cars%20(the%20M%2FM%2F1%2FK%20model)%2C%20the%20blocking%20probability%20is%3A%0A%0A%20%20%20%20%24%24P_%7B%5Ctext%7Bblock%7D%7D%20%3D%20%5Cfrac%7B(1-%5Crho)%5C%2C%5Crho%5EK%7D%7B1%20-%20%5Crho%5E%7BK%2B1%7D%7D%24%24%0A%0A%20%20%20%20As%20usual%2C%20%24%5Crho%20%3D%20%5Clambda%2F%5Cmu%24%20is%20the%20utilization.%20Notice%20that%20the%20numerator%20contains%20%24%5Crho%5EK%24.%20Because%20%24%5Crho%20%3C%201%24%2C%20increasing%20%24K%24%20by%201%20multiplies%20the%20numerator%20by%20%24%5Crho%20%3C%201%24%2C%20shrinking%20%24P_%7B%5Ctext%7Bblock%7D%7D%24%20faster%20than%20linearly.%20Each%20extra%20slot%20in%20the%20buffer%20is%20more%20valuable%20than%20a%20simple%20linear%20reduction%20would%20suggest.%0A%0A%20%20%20%20%23%23%23%20Early%20vs.%20late%20merge%20in%20terms%20of%20%24K%24%0A%0A%20%20%20%20Early%20merging%20creates%20a%20single%20queue%20with%20buffer%20%24K%24%3A%20one%20lane's%20worth%20of%20space.%20Late%20merging%20uses%20both%20lanes%20up%20to%20the%20merge%20point%2C%20creating%20an%20effective%20buffer%20of%20%242K%24%20cars%20total.%20Plugging%20%242K%24%20into%20the%20formula%20instead%20of%20%24K%24%20replaces%20%24%5Crho%5EK%24%20with%20%24%5Crho%5E%7B2K%7D%20%3D%20(%5Crho%5EK)%5E2%24.%20Since%20%24%5Crho%5EK%20%3C%201%24%2C%20squaring%20it%20makes%20it%20much%20smaller.%20This%20is%20the%20why%20doubling%20the%20buffer%20dramatically%20reduces%20blocking.%0A%0A%20%20%20%20%23%23%23%20Intuition%20about%20two%20lanes%0A%0A%20%20%20%20Here%20is%20another%20way%20to%20see%20it.%20Under%20late%20merge%2C%20both%20lanes%20must%20be%20simultaneously%20full%20for%20a%20car%20to%20be%20blocked.%20Suppose%20each%20individual%20lane%20is%20full%20with%20probability%20%24p%24.%20If%20the%20two%20lanes%20are%20roughly%20independent%2C%20the%20probability%20both%20are%20full%20at%20once%20is%20approximately%20%24p%5E2%24.%20For%20example%2C%20if%20%24p%20%3D%200.3%24%2C%20then%20%24p%5E2%20%3D%200.09%24%20%E2%80%94%20blocking%20drops%20from%2030%25%20to%209%25.%20Two%20lanes%20are%20dramatically%20more%20forgiving%20than%20one.%0A%0A%20%20%20%20%23%23%23%20Connection%20to%20throughput%0A%0A%20%20%20%20Throughput%20is%20the%20rate%20at%20which%20cars%20successfully%20pass%20through%20the%20merge%3A%20%24%5Ctext%7Bthroughput%7D%20%3D%20%5Clambda%20%5Ccdot%20(1%20-%20P_%7B%5Ctext%7Bblock%7D%7D)%24.%20Every%20blocked%20car%20is%20a%20car%20that%20does%20not%20get%20through.%20Reducing%20%24P_%7B%5Ctext%7Bblock%7D%7D%24%20by%20doubling%20%24K%24%20therefore%20raises%20throughput%20nearly%20proportionally.%20Late%20merge%20does%20not%20speed%20up%20the%20bottleneck%20(the%20merge%20point%20still%20processes%20cars%20at%20rate%20%24%5Cmu%24)%20but%20it%20ensures%20the%20bottleneck%20is%20never%20starved%20of%20cars%20to%20process%2C%20maximizing%20the%20number%20of%20drivers%20who%20make%20it%20through.%0A%0A%20%20%20%20%23%23%23%20The%20broader%20lesson%0A%0A%20%20%20%20The%20key%20insight%20is%20that%20the%20*structure*%20of%20a%20waiting%20space%20matters%2C%20not%20just%20its%20total%20size.%20Two%20separate%20lanes%20of%20capacity%20%24K%24%20each%20are%20far%20better%20than%20one%20lane%20of%20capacity%20%242K%24%20because%20blocking%20requires%20both%20lanes%20to%20fill%20simultaneously.%20This%20logic%20generalises%20widely%3A%20in%20computer%20networks%2C%20having%20multiple%20independent%20paths%20reduces%20the%20chance%20a%20single%20congested%20link%20stalls%20all%20traffic%3B%20in%20hospitals%2C%20pooling%20patients%20across%20several%20triage%20nurses%20reduces%20the%20chance%20one%20idle%20nurse%20sits%20beside%20an%20overwhelmed%20colleague.%20Wherever%20there%20is%20a%20finite%20buffer%20feeding%20a%20shared%20bottleneck%2C%20the%20late-merge%20principle%20applies%3A%20spread%20the%20waiting%20space%20across%20parallel%20channels%20and%20blocking%20probability%20falls%20dramatically.%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