Cím: Egy dugómodell
Szerző(k):  Balázs Márton 
Füzet: 2003/május, 301 - 307. oldal  PDF file
Témakör(ök): Szakmai cikkek

Balázs Márton
BME Matematikai Intézet
 

Autózás közben bizonyára mindenki került már közlekedési dugóba. Talán arra az érdekes jelenségre is felfigyelt, hogy dugóba hirtelen kerül az ember. Nyugodt és egyenletes haladás után hirtelen észleljük a torlódást, és az autó vezetője legtöbbször csak intenzív fékezéssel tudja elkerülni a balesetet. Merőben mást tapasztalunk viszont, amikor kiérünk a dugóból. Egy dugó kétféleképp érhet véget:
1. Lassan araszolva elérünk ahhoz a helyhez (útlezáráshoz vagy egyéb akadályhoz), ami a problémát okozza, és onnan kezdve saját tempónkban tudunk haladni. Mi most nem ezzel a lehetőséggel szeretnénk foglalkozni.
2. A dugót kiváltó ok hirtelen megszűnik, vagyis eljön az az időpont, amikor az akadály magától eltűnik (pl. elhaladt a diplomáciai küldöttség és a rendőrség megnyitja az utat, vagy szabadra vált a vasúti fénysorompó).
Minket a továbbiakban ez a második eset érdekel. Az autók elindulnak, a dugó lassan feloszlik. Érdekes módon az ilyen magától ritkuló dugóból lassan lehet csak kijönni. Az ember azt veszi észre, hogy lépés helyett már kocogó sebességben megy a sor, aztán lassan felgyorsul harmincra, negyvenre, ... Percek is eltelnek, mire teljesen kijutunk a dugóból és felvesszük saját menettempónkat. Miért viselkedik ennyire különbözően egy forgalmi dugó eleje és vége? Mi a különbség, hogyan lehetne ezt megmagyarázni?
A forgalom két alapvető tulajdonságát érdemes itt figyelembe venni. Az egyik, hogy az autóvezetők nem egyformák, sőt még egy vezető is többféleképp reagálhat hasonló helyzetekre. Van tehát a forgalomban egyfajta véletlenség. A másik, hogy az egymás előtt haladó autók akadályozzák egymást. Ha sokan vannak az úton, az előttünk levő autó közel van, akkor lassan tudunk csak haladni.
A következőkben bemutatunk egy egyszerű modellt, amelyben megtalálható ez a két tulajdonság. Megmutatjuk, hogy már ezzel az egyszerű modellel is képesek vagyunk megmagyarázni a dugók eleje és vége közötti különbséget.
 
Az exponenciális véletlen idő
 

Modellünkben a véletlent furcsa vekkerek fogják szolgáltatni, először ezekkel ismerkedünk meg. Ezek nem egy adott időpontra vannak beállítva, hanem attól fogva, hogy a 0 időpillanatban bekapcsoljuk őket, elkezdenek működni, és egy véletlenül kiválasztott pillanatban szólalnak meg. Ennek a véletlennek is vannak azonban (valószínűségi) szabályai. Annak valószínűsége, hogy egy ilyen vekker a [0,t] időintervallumban nem szólal meg,
P(t)=e-t=(1e)t0,368t,
ahol ,,e'' a természetes logaritmus alapszáma, értéke körülbelül 2,718. (Itt az időt alkalmasan választott egységekben, pl. másodpercekben mérjük, tehát t dimenziótlan.) Az ilyen tulajdonságú véletlen időt véletlen exponenciális időnek nevezzük. Ez a véletlen idő a számológépek véletlenszám-generátorával is jól modellezhető: vegyünk egy 0 és 1 közötti véletlen számot ( RND vagy  RAN gomb), ennek e alapú logaritmusát ( ln gomb), majd az eredmény ellentettjét ( +/- gomb). Az eredmény olyan tulajdonságú véletlen mennyiség, mint a véletlen exponenciális idő: egy adott t>0 számnál éppen e-t valószínűséggel lesz nagyobb.
Két fontos tulajdonsága van az ilyen valószínűségnek. Az első ‐ amiért pont az 1/e alapot választottuk P(t)-ben ‐ akkor derül ki, ha a P(t) függvényt kis pozitív t értékekre ábrázoljuk. Tudományos számológépünk ex gombja szolgál az exponenciális függvény értékének kiszámítására adott x helyen. Ennek használatával könnyen meggyőződhetünk arról, hogy t0 esetén
P(t)=e-t1-t,
és ez annál pontosabban teljesül, minél közelebb esik a t szám a nullához. Ez tehát annak valószínűsége, hogy kis t idő alatt nem szólal meg a vekker; ezért annak valószínűsége, hogy egy piciny t időn belül megszólal: 1-P(t)t.
A másik tulajdonsághoz tekintsük azokat az eseteket, amikor az első másodpercben nem szólal meg a vekker. Az ilyen esetek körében milyen valószínű az, hogy az ezt követő s másodpercben sem szólal meg, vagyis az ilyen esetek hányad részében lesz még további s másodpercig csöndes a vekker? Így is feltehetjük a kérdést: hányad része a P(1+s) valószínűség P(1)-nek? Egyszerű számolás mutatja, hogy
P(1+s)P(1)=(1e)1+s(1e)1=(1e)s=P(s).
Megállapíthatjuk tehát, hogy azon esetek körében, amikor 1 másodpercig nem csörög a vekker, annak valószínűsége, hogy a rákövetkező s másodpercben sem csörög, ugyanannyi (nevezetesen P(s)), mintha a vekkert csak az első másodperc végén kapcsoltuk volna be. Az ilyen vekkernek tehát ‐ a valódi ébresztőórától eltérően ‐ nincs memóriája: ha az első másodperc végén ránézünk és azt tapasztaljuk, hogy még nem csörgött, akkor onnan kezdve ugyanúgy viselkedik, mintha csak most kapcsoltuk volna be. Természetesen ugyanezt 1 másodperc helyett bármely T idővel is elmondhattuk volna.
A fizikában is találkozhatunk ilyen típusú ,,órákkal'': egy radioaktív izotóp atom vagy egy ,,elemi részecske'' bomlása exponenciális véletlen ideig tart; ezek a részecskék annyira elemi objektumok, hogy ,,nincs nekik memóriájuk''. Ugyancsak exponenciális valószínűségeloszlást követ a bicikligumik defektje is. Néha kifog a kerékpáros egy szöget az úton, de ha bizonyos ideig elkerülte a defektet, ettől a ténytől nem nő meg (és nem is csökken) annak valószínűsége, hogy az elkövetkező t időben szögbe szalad. A kerékpárguminak (ha az anyagának öregedésétől eltekintünk) nincs memóriája, emiatt a véletlenszerűen elszórt szögeket tartalmazó úton a gumidefekt valószínűsége ugyanolyan képletekkel írható le, mint az exponenciálisan véletlen időben megszólaló vekker.
A következőkhöz egyszerre több vekkerre lesz szükségünk. Mi történik, ha több ilyen vekker ketyeg egymás mellett, egymástól függetlenül? Tudjuk, hogy kicsiny t időtartam alatt egy exponenciális véletlen vekker kb. t valószínűséggel szólal meg. Mi a valószínűsége, hogy egy piros és egy kék vekker közül mindkettő megszólal t-időn belül? A valószínűség szorzódik (mint ahogy annak esélye, hogy két dobókockával dobva mindkettő hatost fog mutatni 1616=136), tehát ez a keresett valószínűség kb. t2. Kis t érték esetén t2 sokkal kisebb t-nél. Ezért annak valószínűsége, hogy mindkét vekker megszólal t időtartam alatt, elhanyagolható annak valószínűségéhez képest, hogy mondjuk a kék vekker megszólal ezen időtartam alatt (mondhattuk volna a piros vekkert is). Ha több vekkerünk van, akkor is elhanyagolhatjuk annak valószínűségét, hogy közülük kettő is megszólal t időtartam alatt, annak valószínűségéhez képest, hogy valamelyikük egyedül szólal meg a t időtartamban. Annak esélye pedig, hogy három vagy még több vekker is szól a [0,t] időintervallumban, még sokkal kisebb. Ezért több vekker alkalmazása esetén nem kell figyelembe vennünk azt a lehetőséget, hogy kicsiny t időtartam alatt egynél több vekker is megszólal. (Ez természetesen nem pontos állítás, de precízzé tehető, és megmutatható, hogy további gondolatmenetünk során alkalmazható.)
Ha C darab exponenciális véletlen vekkerünk ketyeg egymás mellett, akkor mi az esélye, hogy kicsiny t idő alatt legalább egy megszólal közülük? Lehet, hogy az első szólal meg, lehet, hogy a második, harmadik stb. Külön-külön körülbelül t valószínűséggel szólalnak meg, és elhanyagolhatjuk azokat az eseteket, amikor t idő alatt több is megszólal (ez lényeges!), ezért annak esélye, hogy közülük legalább egy megszólal, közelítőleg Ct.
 
Az ugró golyók modellje
 

Most már készen állunk arra, hogy felvázoljuk modellünket az autókról.
Képzeljünk el dobozokat egymás mellett egy körön elhelyezve, melyeket -N-től N-ig megszámoztunk. Az N-edik doboz után a -N-edik doboz következik, ezért N+1 helyett mindig -N-t értsünk. Minden dobozban 0 vagy 1 darab golyó lehet, de 2 vagy több golyó nem fér egy dobozba. Kezdetben a dobozokba elosztunk M darab teljesen egyforma golyót. A rendszer egy állapota azt írja le, hogy melyik dobozban van golyó és melyikben nincsen. Minden doboz alá képzeletben elhelyezünk egy-egy, egymástól teljesen függetlenül működő exponenciális véletlen vekkert. A szabály a következő: ha valamelyik doboz alatti vekker megszólal, és a dobozban van golyó, a következő dobozban viszont nincs, akkor a vekker fölötti golyó átugrik a következő dobozba. Egyéb esetekben ‐ azaz ha a megszólaló vekker fölötti doboz üres, vagy nem üres, de a következő dobozban már van egy golyó ‐ a vekker megszólalására nem történik semmi. Mindegyik vekker a megszólalása után rögtön elhallgat, és újra készenléti állapotba kerül (várja, hogy exponenciálisan véletlen idő múlva megszólalhasson).
Milyen állapotai vannak egy ily módon indított rendszernek? Az n-edik doboz állapotát (-NnN) jelképezze ωn:
ωn:={1,ha az  n-edik dobozban van golyó;0,ha az  n-edik doboz üres.
Összesen mindig M darab golyónk és -N-től N-ig számozva 2N+1 darab dobozunk van, így rendszerünk állapotát az olyan szám (2N+1)-esek írják le, melyekben M darab 1-es és 2N+1-M darab 0 található. Például három lehetséges állapot a következő:
ω=(0,...,0,1,1,...,1,1,0,0,...,0),ω'=(0,...,0,1,1,...,1,0,1,0,...,0),ω''=(0,...,0,0,1,...,1,1,1,0,...,0).
Az ω állapotban az M darab golyó az 1...M számú dobozokban helyezkedik el. Ebből közvetlen átmenet lehetséges az ω' állapotba az M-edik dobozban levő golyó ugrásával. Viszont csak sok lépésen keresztül érhető el az ω'' állapot, melyben a golyók a második, harmadik, ..., M+1-dik dobozban találhatók.
Mi történik, ha rendszerünket elindítjuk a fenti ω állapotból? Az első lépés a szabályok szerint csak az ω' állapot lehet (az M-edik vekker exponenciális véletlen ideje után). A második lépésre azonban már több lehetőségünk van, a harmadikra még több, és így tovább. Hogy melyik lesz mondjuk az ötödik lépés, és hogy mikor fog bekövetkezni, függ a véletlen vekkerek megszólalási idejétől. Nyilvánvaló, hogy biztosat nem tudunk állítani a rendszerről, csupán annyit, hogy t idő után lesz valamilyen valószínűsége annak, hogy a rendszert egy másik állapotban (például ω''-ben) találjuk. Egy állapot valószínűségét úgy képzelhetjük el, hogy nagyon sok modell-rendszert tekintünk egyszerre, és megnézzük, hogy ezek hányad részében látjuk az adott állapotot. Az elején minden rendszer ω állapotban volt, így induláskor az ω állapot valószínűsége 1, és minden más állapot valószínűsége 0. Ahogy az idő telik, a golyók ugrálni kezdenek, és a modellek közül egyre kevesebb marad a kiindulási ω állapotban; t-kor már egy részüket ilyen, más részüket olyan állapotban találjuk. Eszerint tehát ω valószínűsége lecsökkent, míg más állapotok valószínűsége nullánál már nagyobb lesz; az állapotok valószínűségei gyorsan változni kezdenek, és már 1-nél kisebb lesz a valószínűsége, hogy a rendszer t-kor is ω-ban lesz. Az egyes állapotok valószínűségei tehát időben változnak.
Felmerül a kérdés, mik lehetnek az állapotok azon valószínűségei, amelyek a golyók ugrálásával már nem változnak; vagyis ha sok modellt különböző állapotokból indítunk, hányad részüket indítsuk ilyen, olyan, illetve amolyan állapotból, hogy t-kor is ugyanolyan hányaduk legyen ilyen, olyan, illetve amolyan állapotban? Ha mondjuk ω' állapotból indítjuk a modellek egy részét, azok közül néhány már elhagyja az ω' állapotot, viszont más állapotokból indított modellek egy része ω'-be kerülhet t idő múlva. Így t-kor a modellek ugyanakkora hányadát találjuk az ω' állapotban, mint induláskor, vagyis az ω' állapot valószínűsége nem változott. Az ilyen, időben nem változó állapot-valószínűségeket egyensúlyi valószínűségeknek nevezzük. Azt mondjuk, hogy a rendszer egyensúlyban van, ha minden állapotban épp az ahhoz tartozó egyensúlyi valószínűséggel találjuk. A definícióból következik, hogy ha a modell egyensúlyban van, azaz egy adott t0 pillanatban a P(ω(t0)=η) valószínűségek épp egybeesnek az egyensúlyi valószínűségekkel, akkor ez így is marad: minden t>0-ra
P(ω(t0+t)=η)=P(ω(t0)=η).

Most megmutatjuk, hogyan lehet a modellt egyensúlyból, azaz egyensúlyi valószínűségekkel kiválasztott véletlen állapotból indítani.
 
1. tétel. Először válasszuk meg tetszőleges véletlenszerű módon az összes golyók M számát. M rögzítése után (legyen mondjuk M=m) az m golyós állapotok közül mindegyiknek ugyanakkora esélyt adva válasszunk ki egyet. Adott m-re tehát minden m golyót tartalmazó állapot valószínűsége egyforma, nevezzük ezt p(m)-nek. Ezek az ugró golyók modelljének egyensúlyi valószínűségei lesznek.
 

Majdnem-bizonyítás. Rögzítsünk egy m-golyós η állapotot. Ebbe az állapotba nyilván csak m-golyós állapotokból kerülhetett a rendszer, hiszen a golyók ugrálása során számuk nem változik. Legyen t0 nagy, t kicsiny. Elég megmutatni, hogy ha t0-kor minden m-golyós állapot valószínűsége p(m), akkor
P(ω(t0+t)=η)=p(m)
is teljesül t0+t-kor. Ha ez igaz, akkor η tetszőleges volta miatt t0+t-kor is minden m-golyós állapot valószínűsége p(m), ez tehát az egyensúlyi valószínűség értéke.
Mi lehet ω(t0), ha ω(t0+t)=η? Mivel t kicsiny, elég legfeljebb egy lépést figyelembe venni, azaz ω(t0) vagy megegyezett η-val, vagy mindössze egyetlen lépésre volt tőle. Jelölje C az η állapotban található 0-1 párok, vagyis azon helyek számát, ahol egy 0 mellett jobbra egy 1-es található (beleértve esetleg az N-edik és a -N-edik helyet is). Ha egy ilyen pár 1-esét a pár 0-jának helyére rakjuk, akkor egy olyan állapotot kapunk, ahonnan egy lépés (az egyes visszaugrása) után juthatunk η-ba. Így elkészíthetjük az η mind a C darab ősét: azokat az állapotokat, amelyek egy lépésre vannak η-tól. Lehet tehát, hogy ω(t0)C darab ős egyike volt; ennek esélye Cp(m), hiszen mindegyik ős m-golyós, és az ilyenek valószínűsége feltevésünk szerint p(m). Annak az esélye pedig, hogy t0 és t0+t között megszólaljon az az egyetlen vekker, amitől a megfelelő egyes ugrásával az ősből kialakul η, körülbelül t. Így
P(ω(t0+t)=η  és  ω(t0)  az  η  őse)Cp(m)t.
Az is lehetséges azonban, hogy ω(t0) már eleve η-val egyezett meg; ennek valószínűsége (mint minden más állapotnak is) p(m). Az η állapotban ugyanannyi 0‐1 pár van, mint 1‐0 pár (próbáljunk csak meg a körben elhelyezett helyekre olyan állapotot rajzolni, amelyben nem így van!), tehát az 1‐0 párok száma is C. Ha t0-tól t0+t-ig e C darab pár 1-ese alatt bármelyik vekker megszólalna, akkor az 1-es ugrana, és ω(t0+t) már nem η-val egyezne meg. ω(t0)=η esetén tehát az szükséges, hogy a C darab kritikus vekker közül egy se szólaljon meg; ennek valószínűsége kb. 1-Ct. Ezért
P(ω(t0+t)=η  és  ω(t0)=η)p(m)(1-Ct).
A két lehetőség valószínűségeit összeadva:
P(ω(t0+t)=η)Cp(m)t+p(m)(1-Ct)=p(m),
tehát t0+t-kor is p(m) a valószínűsége a (tetszőlegesen kiválasztott) m-golyós η állapotnak. A  jellel jelzett közelítések egyre kisebb és kisebb t értékek esetén egyre pontosabbá válnak, így a t0 határátmenettel ez a bizonyítás precízzé tehető.
 

A közlekedési dugók megértéséhez olyan egyensúlyi valószínűségekre lesz szükségünk, melyek előállítására egy furcsa eljárást alkalmazunk. Rögzítsünk egy 0<ϱ<1 számot, és tegyünk a 2N+1 doboz mindegyikébe egymástól függetlenül ϱ valószínűséggel golyót, míg 1-ϱ valószínűséggel hagyjuk az adott dobozt üresen. Ezen eljárás szerint egy adott m golyós állapot valószínűsége, azaz annak esélye, hogy az előre kijelölt m dobozba kerül golyó, és a többi doboz üres marad, nyilván nem függ attól, hogy melyik m dobozba kell golyót tennünk; a valószínűség csak m értékétől függ. Így ezzel az eljárással az adott golyószámú állapotok közül egyenlő eséllyel választunk, tehát a tétel szerint a modell egyensúlyi valószínűségeit kapjuk. (Eljárásunk alapján p(m)=ϱm(1-ϱ)2N+1-m adódik, de ez most számunkra nem lényeges.)
Ezzel a speciális választással kezelhető marad a modell nagyon sok doboz esetén is. Képzeljük el, hogy N értékét nagyon nagyra választjuk. A lehetséges állapotok száma rendkívüli mértékben megnő, egyre nehezebb számon tartani őket. Ekkor is gond nélkül megtehetjük viszont, hogy minden dobozba egymástól függetlenül ϱ valószínűséggel teszünk golyót, és 1-ϱ eséllyel nem teszünk golyót; ez az eljárás nem érzékeny N értékére. Ezentúl tehát N-et nagyon nagynak fogjuk választani, az előbb leírt egyensúllyal. Mi a nulladik sorszámú doboz környékén vizsgálódunk (tőlünk balra a negatív, jobbra a pozitív sorszámú dobozok vannak), és már nem is látjuk a nagyon távoli -N-edik és N-edik dobozokat.
Képzeljük magunkat egy golyó helyébe egy egyensúlyi modellben (azaz egy autós helyébe a dugóban). Mi a valószínűsége, hogy kicsiny t idő alatt lépünk egyet jobbra? Ehhez az szükséges, hogy tőlünk jobbra ne legyen golyó (azaz előttünk ne álljon autó) ‐ ennek 1-ϱ az esélye egyensúlyban ‐ valamint, hogy alattunk megszólaljon az exponenciális vekker ‐ ennek valószínűsége t. Összességében kicsiny t idő alatt (1-ϱ)t eséllyel lépünk egyet, így átlagsebességünk 1-ϱ. Igaz tehát, hogy minél sűrűbben helyezkednek el a golyók (ϱ közel van 1-hez), annál lassabb az előrehaladás. A teljes dugónak ϱ=1 felel meg, ekkor minden helyen golyó van, semelyik golyó sem tud lépni.
Ezt a modellt bonyolult módszerekkel vizsgálni lehet abban az esetben, ha nagyon messziről nézünk rá. (Képzeljünk el egy repülőt, ahonnan nem látszanak az egyes autók, csak az autópálya színéből következtethetünk arra, hogy milyen sűrű a forgalom.) Azt is meg lehet határozni, hogy mi történik két speciális esetben: ha a bal oldalon, ahonnan az autók (golyók) érkeznek, ritka a forgalom (ϱ kicsi), míg a jobb oldalon sűrű (ϱ közelebb van egyhez), illetve fordítva, ha a bal oldalon sűrű a forgalom és a jobb oldalon ritka. Az első esetben az autók a dugóba érkeznek, míg a második esetben a dugóból kifelé tartanak, szétoszlanak. Ezek már természetesen nem egyensúlyi eloszlások, ennek megfelelően egy ilyen helyzet folyamatosan változik.
 
2. tétel. Messziről nézve a rendszert, ha a bal oldalon kisebb a ϱ értéke mint a jobb oldalon, akkor a két rész közötti határ egyre élesebb lesz, míg egyszer csak kialakul egy éles határvonal, amitől balra egy kisebb, jobbra egy nagyobb értékű sűrűség tapasztalható. Ha viszont a bal oldalon nagyobb a ϱ értéke, mint a jobb oldalon, akkor a kettő közötti átmenet egyre inkább kisimul, elmosódik; itt tehát nem alakul ki éles határvonal.
 

(A bizonyításhoz a valószínűségszámítás és a parciális differenciálegyenletek témaköreinek mély és nehéz módszereit kell felhasználni.) Ez a tétel megmagyarázza, hogy miért kell nagyot fékezni ha dugóba érünk: a jól járható ritka forgalmú rész és a dugó között magától kialakul egy nagyon éles határvonal, azaz egy pillanat alatt a dugóban találjuk magunkat. Másfelől ha kiérünk a dugóból és oszlik a sor, az a második esetnek felel meg, mely szerint a dugóból egy egyre inkább elmosódó, határozatlan részen keresztül jutunk ki, és ez bizony hosszú ideig tarthat.
 

A szerző köszönetét fejezi ki Dr. Vetier Andrásnak, akinek tanácsai és hasznos észrevételei sokat segítettek a cikk megírásában.