2012. szeptember 5, 15:30
K¨ oMaL, 2012. szeptember (1. lap)
P´ olya-f´ ele urnamodell II.
4. Egy´ eb ¨ onmeger˝ os´ıt˝ o folyamatok 4.1. V´ egtelen sok sz´ın az urn´ aban Kor´ abban ´ıg´ert¨ uk, hogy sz´ ot ejt¨ unk arr´ol, hogyan tudn´ank el´erni, hogy ne csak egy el˝ ore r¨ ogz´ıtett, v´eges sz´ınhalmazb´ol szerepelhessen goly´o az urn´aban. Tegy¨ unk az urn´ aba kezdetben puszt´ an egy darab goly´ot, aminek speci´alis szerepe lesz, nevezz¨ uk fekete goly´ onak, ´es m´odos´ıtsuk a goly´oh´ uz´ asi algoritmust egy kiss´e a k¨ovetkez˝ok´eppen. Ugyan´ ugy mint eddig, egy l´epes kezd˝odj¨on azzal, hogy kih´ uzunk egy goly´ ot v´eletlenszer˝ uen az urn´ ab´ol. Hogyha a) a fekete goly´ ot h´ uzzuk, akkor a visszat´etel´evel egyid˝oben egy u ´j goly´ot is tesz¨ unk az urn´ aba, de nem feket´et, hanem egy olyan sz´ın˝ ut, amilyen ott addig m´eg nem szerepelt, b) ha pedig nem a fekete goly´ ot h´ uzzuk, akkor u ´gy j´arjunk el, mint kor´abban, az eredeti P´olya-urna eset´eben, azaz a kih´ uzott sz´ınnel megegyez˝oen tegy¨ unk u ´j goly´ ot az urn´ aba. 4.2. K´ınai vend´ egl˝ o folyamat A fent v´ azolt modell, illetve ennek tov´abbi ´altal´anos´ıt´asai nagy jelent˝os´eget kapnak olyan modellez´esi esetekben, amikor egy v´eletlen adathalmazt csoportokra kell osztani, de a csoportok sz´ ama el˝ore nem ismert. A modellcsal´ad neve k´ınai ” vend´egl˝ o folyamat”. Hogy a n´ev ne csak sz´ orakoztat´ oan hangozz´ek, hanem ´erthet˝ov´e ´es megjegyezhet˝ov´e is v´ aljon, a modellcsal´ ad alapeset´et az irodalomban elterjedt m´odot k¨ovetve a k¨ovetkez˝ o p´eld´ aval illusztr´ aljuk. K´epzelj¨ unk el egy k´ınai vend´egl˝ot, amelyben v´egtelen sok, v´egtelen kapacit´ as´ u kerek asztal tal´alhat´o. Kezdetben minden asztal u ¨res, majd egyes´evel kezdenek meg´erkezni a vend´egek. Az ´erkez˝o vend´eg eld¨onti, hogy megkezd egy u ´j asztalt, vagy pedig v´eletlenszer˝ uen v´alaszt a jelenl´ev˝o emberek k¨oz¨ ul valakit, ´es le¨ ul az ˝o bal oldal´ ara (akik esetleg m´ar az illet˝o bal oldal´an u ¨ltek, azok illedelmesen helyet szor´ıtanak az ´erkez˝onek). Az u ´j asztal v´alaszt´as´anak val´osz´ın˝ us´eg´et a k¨ ovetkez˝ ok´epp hat´ arozzuk meg. Ha ´erkez´esekor n vend´eg tart´ozkodik m´ar a vend´egl˝ oben, akkor az u ´ j vend´eg a) u ´j asztalt kezd, ennek val´ osz´ın˝ us´ege 1/(n + 1), vagy b) v´alaszt egyet a m´ar ottl´ev˝ o emberek k¨oz¨ ul v´eletlenszer˝ uen, ´es mell´e u ¨l le, ez n a marad´ek n+1 val´ osz´ın˝ us´eggel t¨ort´enik. B´armely m´ar ott l´ev˝o ember v´alaszt´ as´ anak val´ osz´ın˝ us´ege teh´ at
1 . n+1
K¨ oz´ episkolai Matematikai ´ es Fizikai Lapok, 2012/6
1
2012. szeptember 5, 15:30
K¨ oMaL, 2012. szeptember (2. lap)
A le´ır´ as a legels˝ o vend´egre is ´erv´enyes, hiszen az ˝o eset´eben az u ´j asztal v´alaszt´ as´ anak val´ osz´ın˝ us´ege 1-nek ad´odik a k´epletb˝ ol. Egy-egy u ´j asztal megkezd´ese megfeleltethet˝o a P´olya-f´ele modell 4.1-beli v´altozat´aban a fekete goly´ o h´ uz´ asanak, ´ıgy minden asztal a k´ınai vend´egl˝oben term´eszetes m´odon egy-egy sz´ın az urn´ aban. Egy kiszemelt asztaln´al u ¨l˝o emberek sz´ama ilyen m´ odon megfelel az ehhez az asztalhoz tartoz´o sz´ın˝ u goly´ok sz´am´anak. Hogy mi´ert van ´ertelme m´egis k¨ ul¨ on modellk´ent tekinteni a k´ınai vend´egl˝o folyamatra, az az ´altal´ anosabb eset le´ır´ asakor lesz l´athat´o (l´asd 4.4. szakasz). 4.3. Ropi-t¨ oredez´ esi folyamat Bizony´ıt´ as n´elk¨ ul jegyezz¨ uk itt meg, hogy a k´ınai vend´egl˝o folyamatnak is van ´ertelme v´egtelen hat´ areset´er˝ ol besz´elni. Ezzel egy m´ asik besz´el˝o nev˝ u folyamathoz, az u ´gynevezett ropi-t¨ oredez´esi folyamathoz jutunk. A ropi-t¨ oredez´esi folyamat a k¨ ovetkez˝ot jelenti. Vesz¨ unk egy egys´egnyi hossz´ us´ag´ u ropit, ´es v´eletlenszer˝ uen kett´et¨orj¨ uk, a t¨or´esi pontnak a ropi bal sz´el´et˝ol val´o t´avols´ ag´ at egyenletes eloszl´ as szerint v´alasztva. A bal kez¨ unkben maradt ropidarabot f´elretessz¨ uk. Ezut´ an a jobb kez¨ unkben l´ev˝o ropidarabot tekintj¨ uk egys´egnyi hossz´ us´ ag´ unak, megint let¨ or¨ unk bel˝ole egy egyenletes eloszl´as szerint kisorsolt hossz´ us´ ag´ u darabot, f´elretessz¨ uk, ´es ´ıgy tov´abb. A v´eg´en az eredeti ropinak egy v´eletlen, v´egtelen felt¨ oredez´es´et kapjuk. A kapcsolat a ropi-t¨ oredez´es ´es a k´ınai vend´egl˝o folyamat k¨oz¨ott az, hogy ha v´egtelen hossz´ u id˝ o m´ ulva” megn´ezz¨ uk, hogy a vend´egl˝oben milyen ar´anyban ” u onek megkezdett asztaln´al, az ´epp megfelel az egys´egnyi ¨lnek az emberek az els˝ hossz´ us´ ag´ u ropib´ ol els˝ onek let¨ ort darabka hossz´anak. A m´asodik asztal n´epszer˝ us´ege a m´ asodikk´ent let¨ ort ropidarab hossza, ´es ´ıgy tov´abb. Hihet˝ ov´e v´ alik ez az ´all´ıt´ as, ha megfontoljuk a k¨ovetkez˝oket. A 4.1. fejezetbeli modellben gondolatban az els˝ o sz´ın kiv´etel´evel az ¨osszes t¨obbire v´ aljunk sz´ınva” kokk´a”, azaz a m´asodik, harmadik, stb. sz´ıneket mossuk ¨ossze egyetlen sz´ınn´e. Ezzel felfedezt¨ uk a k´et sz´ın˝ u esetet a v´egtelen sok sz´ın˝ u modellbe ´agyazva. Kor´abban l´attuk, hogy a k´et sz´ınt tartalmaz´ o modellben az els˝o sz´ın ar´any´anak eloszl´asa az egyenleteshez tart – ez teh´ at magyar´azza a jelen modellben az els˝o sz´ın ar´any´anak egyenletes eloszl´ as´ at a limeszben. Most pedig tekints¨ uk csak azokat a v´eletlen l´epes´eket, amikor nem az els˝o, hanem valamelyik m´ asik sz´ınb˝ ol tesz¨ unk u ´ jat az urn´aba. Ezzel let¨ort¨ uk” a ropib´ol az ” els˝o sz´ınnek megfelel˝ o r´eszt, ´es csak a t¨obbivel foglalkozunk. Az im´enti gondolatmenetet folytatva tov´ abb, most a m´asodik sz´ınt k¨ ul¨onb¨oztetj¨ uk meg, a harmadik sz´ınt˝ol kezdve a t¨ obbit viszont tekints¨ uk egyform´anak. L´atjuk ilyen m´odon, hogy a m´asodik sz´ın ar´ any´ at a limeszben val´oban a marad´ek ropidarab egyenletes v´eletlen kett´et¨ or´esek´ent kaphatjuk (´es ´ıgy tov´abb).
4.1. feladat. V´ alasszunk az {1, 2, . . . , n} halmaz ¨ osszes permut´ aci´ oi k¨ oz¨ ul egyet egyenletesen v´eletlen¨ ul. Mi a val´ osz´ın˝ us´ege, hogy az a ciklus, amelyikbe az 1-es sz´ am esik, ´epp k hossz´ u? 2
K¨ oz´ episkolai Matematikai ´ es Fizikai Lapok, 2012/6
2012. szeptember 5, 15:30
K¨ oMaL, 2012. szeptember (3. lap)
4.2. feladat. V´ alasszunk az ¨ osszes n elem˝ u permut´ aci´ o k¨ oz¨ ul egyet egyenletesen v´eletlen¨ ul. Mi a val´ osz´ın˝ us´ege, hogy a benne szerepl˝ o leghosszabb ciklus n/2-n´el hosszabb? ´ 4.4. Altal´ anosabb eset A k´ınai vend´egl˝ o folyamatnak l´eteznek ´altal´anosabb esetei. Egyik ilyen az, amikor r¨ogz´ıt¨ unk egy tetsz˝oleges pozit´ıv val´os sz´amot, α ∈ R+ , mint a modell param´eter´et. Az u ´j vend´eg v´eletlen d¨ ont´esi szab´alya ezzel a param´eterrel a k¨ovetkez˝ok´epp m´odosul. Ha az ´erkez´esekor a jelen l´ev˝o vend´egek sz´ ama n, akkor az u ´j vend´eg α a) u ´j asztalt bont, ennek val´ osz´ın˝ us´ege n+α , vagy b) egyenletesen v´ alaszt egyet a m´ar jelenl´ev˝o vend´egek k¨oz¨ ul, ´es mellette foglal 1 helyet, azaz b´ armely m´ar jelenl´ev˝o vend´eg v´alaszt´as´anak es´elye n+α . Annak a val´ osz´ın˝ us´ege teh´ at, hogy egy kiszemelt, ´eppen k vend´eggel rendelkez˝o asztalt k v´alaszt, n+α . Az α param´eter nagys´ aga hat´ arozza meg, hogy hossz´ u id˝o m´ ulva kev´es asztalhoz t¨om¨ or¨ ult nagy l´etsz´ am´ u csoportokat fogunk-e l´atni (kicsi α esete), vagy pedig sok-sok asztaln´ al elsz´ ortan u ¨lnek majd az emberek (nagy α esete). A P´olya-f´ele urnamodellnek a 4.1. fejezetben v´ azolt esete az α = 1 param´eterv´alaszt´asnak felel meg, ami ´epp a kicsi” ´es a nagy” param´etertartom´anyt v´alasztja el egym´ast´ol. ” ” ´ Altal´ anos α param´eter eset´en a k´ınai vend´egl˝onek megfelel˝o p´alcika t¨oredez´esi folyamat annyiban m´odosul, hogy nem egyenletes, hanem (α-t´ol f¨ ugg˝o) param´eter˝ u B´eta eloszl´ assal t¨ orj¨ uk le a darabk´ akat. 4.5. V´ eletlen fa A 4.2. fejezetben v´ azolt k´ınai vend´egl˝o folyamat kapcs´an term´eszetes m´odon felmer¨ ulhet benn¨ unk az ig´eny, hogy az asztalok adott pillanatbeli n´epszer˝ us´eg´en” ” t´ ul azt is sz´ amon tartsuk, az egyes vend´egek mi´ert” az adott helyre u ¨ltek le. M´as ” sz´oval, hogy ki volt az a vend´eg, akire a v´alaszt´asuk esett: mennyire n´epszer˝ uek” ” az egyes egy´enek. Olyan ez, mintha azt k´erdezn´enk, melyik vend´egnek h´any le” sz´armazottja” van, abban az ´ertelemben, hogy h´any ember u ¨lt le az illet˝o vend´eg asztal´ahoz k¨ ozvetve vagy k¨ ozvetlen¨ ul miatta. Tekints¨ unk egy olyan csal´ adf´ at, melyben csak az apa-fi´ u kapcsolatokat jel¨olj¨ uk (b´armely emberhez teh´ at csak egy sz¨ ul˝ot tartunk nyilv´an). Mik¨ozben v´eletlen¨ ul fejlesztj¨ uk a k´ınai vend´egl˝ o folyamatot, rajzoljunk fel l´ep´esr˝ol l´ep´esre egy f´at, amiben a vend´egek ilyen kapcsolatait” reprezent´aljuk (ld. 6. ´ abra). ” Kezdetben, amikor u ¨res a vend´egl˝o, rajzoljuk meg a fa gy¨oker´et, azaz egyetlen cs´ ucsot. Az els˝ o l´ep´esben meg´erkezik az els˝o vend´eg, ekkor rajzoljunk a fa els˝o szintj´ere egy u ´j cs´ ucsot (c´ımk´ezz¨ uk 1-gyel), ´es k¨oss¨ uk ¨ossze a gy¨ok´errel. A k¨ovetkez˝o l´ep´esben j¨ on a m´ asodik vend´eg, ´es v´alaszt mag´anak v´eletlen¨ ul egy helyet. Jel¨olj¨ uk ezt egy u ´ j cs´ uccsal (2-es c´ımk´evel) a f´aban a k¨ovetkez˝ok´eppen: a) ha a vend´eg u ´j asztalt bont, akkor rajzoljuk az u ´j cs´ ucsot az els˝o szintre, ´es k¨ oss¨ uk ¨ ossze a gy¨ ok´errel,
K¨ oz´ episkolai Matematikai ´ es Fizikai Lapok, 2012/6
3
2012. szeptember 5, 15:30
K¨ oMaL, 2012. szeptember (4. lap)
6. ´ abra. V´eletlen fa az els˝ o kilenc l´ep´es ut´ an
b) ha pedig az els˝ o vend´eg mell´e u ´j cs´ ucsot a fa m´asodik szintj´ere ¨lt le, akkor az u rajzoljuk, ´es k¨ oss¨ uk ¨ ossze az 1-es cs´ uccsal. A t¨ obbi vend´eg helyv´ alaszt´ as´ at hasonl´oan sz´amon tartjuk egy-egy u ´j cs´ ucs megjelen´ıt´es´evel a f´aban: a vend´eg ´erkez´esi sorsz´am´aval c´ımk´ezett cs´ ucsot az ´altala v´alasztott r´egi vend´eg fiak´ent” rajzoljuk a csal´adf´aba. A c´ımk´ek haszn´alata ” biztos´ıtja, hogy az azonos ap´ ahoz” tartoz´ o fi´ uk” k¨oz¨ott a korbeli sorrend rekonst” ” ru´alhat´ o legyen. Ezzel egy v´eletlen¨ ul n¨ oveked˝ o fa folyamatot hoztunk l´etre, melyr˝ol egy-egy pillanatk´epet az 6. ´es a 7. ´ abr´ an l´ athatunk.
7. ´ abra. V´eletlen fa kilencvenkilenc l´ep´es ut´ an
Vil´agos, hogy a fa gy¨ oker´et˝ ol 1 t´avols´agra l´ev˝o cs´ ucsok a k´ınai vend´egl˝oben az u ´ j asztalt kezd˝ o vend´egeknek felelnek meg, ´es ha egy kalapba vessz¨ uk” az ” ucsot, amely egy-egy ilyen u ´ j´ıt´o hajlam´ u vend´eghez tartoz´o r´eszf´aban ¨osszes olyan cs´ tal´alhat´ o, akkor a k´ınai vend´egl˝ oben l´etrej¨ov˝o asztalokn´al u ¨l˝o vend´egek csoportjait l´atjuk a f´ aban. Gazdagabb strukt´ ur´ at nyert¨ unk azonban ezzel a reprezent´aci´oval: seg´ıts´eg´evel azonnal szembet˝ un˝ ov´e v´ alik p´eld´ aul a modellben megh´ uz´od´o ¨onhasonl´os´ag. Ha azt a v´eletlen pillanatot tekintj¨ uk ugyanis, amikor a k-adik asztalt” megkezdi valaki, ´es ” onnant´ ol kezdve csak azokra a v´eletlen id˝opontokra koncentr´alunk, amikor valaki m´as ahhoz a k-adik asztalhoz csatlakozik, akkor l´athajuk, hogy az itt kialakul´o v´eletlen r´eszfa pontosan ugyanolyan szab´alyszer˝ us´eg szerint ´ep¨ ul, mint a teljes fa, vagy mint ak´ armelyik m´ asik asztalnak megfelel˝o m´asik r´eszfa. 4
K¨ oz´ episkolai Matematikai ´ es Fizikai Lapok, 2012/6
2012. szeptember 5, 15:30
K¨ oMaL, 2012. szeptember (5. lap)
V´eletlen f´ak illetve gr´ afok n¨ oveked´es´enek h´ıress´e v´alt vizsg´alata tal´alhat´o [1]ben. Az ott t´ argyalt n¨ oveked´esi szab´alyn´al ´altal´anosabb szab´alyok eset´en n¨oveked˝o v´eletlen f´ akra vonatkoz´ o eredm´enyek´ert l´asd [2]-t. ¨ 4.6. Onmeger˝ os´ıt´ es ( reinforcement”) ” A P´ olya-urna ´es a t¨ obbi, jelen cikkben v´azolt modell mind az u ´gynevezett re” inforcement”, vagy ¨ onmeger˝ os´ıt´es jelens´eg´et mutatj´ ak. Ilyen matematikai modell magyar´ azza teh´ at p´eld´ aul azt is, hogy mi´ert lett olyan els¨opr˝oen sikeres a Facebook. Egyre t¨ obb emberben van ig´eny arra, hogy csatlakozzon valamelyik k¨oz¨oss´egi oldalhoz, ´es ahhoz csatlakoznak, ahov´a megh´ıvja ˝oket valaki. ´Igy a sok potenci´alis k¨oz¨ oss´egi oldal k¨ oz¨ ul a v´eletlen v´alasztja ki, hogy melyik lesz a legnagyobb. A v´eletlens´eg azonban egy id˝ o eltelt´evel befagy”, ahogy egyre t¨obb ´es t¨obb em” ber csatlakozik, az egyes u ´j r´esztvev˝ok hat´asa egyre kisebb ´es kisebb. Ut´olag m´ar nagyon sikeresnek mondhat´ o a Facebook, de ha az elej´en egy kicsit m´as a piros ´es z¨old goly´ ok ar´ anya, akkor lehet, hogy m´ask´ent alakultak volna a dolgok. ´ ak forr´ 5. Abr´ asai A szimul´ aci´ ot Python nyelven ´ırtam. Az ezzel gener´alt adatokat a 2. ´es 3. ´ abr´ ak eset´eben Gnuplot programmal, a 7. ´ abra eset´eben pedig a szint´en ingyenesen el´erhet˝ o, nagym´eret˝ u gr´afok testreszabott kirajzol´as´ ara alkalmas Cytoscape programmal rajzoltam meg. Az 5. ´ abra Gnuplottal k´esz¨ ult, a k´od alapja a http://en.wikipedia.org/wiki/File:Beta_distribution_pdf.svg honlapon el´erhet˝ o k´ odr´eszlet. A 4. ´es a 6. ´ abr´ at a LATEX tikz csomagj´aval k´esz´ıtettem.
Hivatkoz´ asok [1] Albert-L´ aszl´ o Barab´ asi, R´eka Albert, Emergence of scaling in random networks, American Association for the Advancement of Science. Science, Vol. 286 (1999). [2] Anna Rudas, B´alint T´oth, Benedek Valk´o, Random trees and general branching processes, Random Structures and Algorithms 31 (2007), 186–202. Rudas Anna Budapesti M˝ uszaki ´es Gazdas´ agtudom´ anyi Egyetem Matematika- ´es Sz´ am´ıt´ astudom´ anyok Doktori Iskola
[email protected]
K¨ oz´ episkolai Matematikai ´ es Fizikai Lapok, 2012/6
5
