Mádi-Nagy Gergely * A feladat pontos leírása. Tekintsünk darab tetszõleges eseményt, jelöljük ezeket a következõképpen: ,...,

Mádi-Nagy Gergely* AZ ESEMÉNYEK UNIÓJÁNAK VALÓSZÍNÛSÉGE – BECSLÉS A TÖBBVÁLTOZÓS DISZKRÉT MOMENTUM PROBLÉMA SEGÍTSÉGÉVEL Az események uniója valószínûsége becslésére szolgáló elsõ fontos eredmények a BooleBonferroni egyenlõtlenségek, melyek a 19-20. század fordulóján születtek. Azóta a becslési módszerek sokat finomodtak, ugyanazon információhalmaz segítségével sokkal pontosabb becsléseket tudunk adni. A dolgozat célja, hogy röviden bemutassa a többváltozós diszkrét momentum problémán (TDMP) alapuló becslések módszertanát és numerikus példákon keresztül szemléltesse annak hatékonyságát. Bevezetésünkben ismertetjük a megoldandó feladatot, majd említünk néhány közgazdaságtani alkalmazást, végül pedig áttekintést nyújtunk a szokásos becslési módszertanokról. A következõ fejezetben definiáljuk a TDMP-feladatot, és bemutatjuk, hogy segítségével miként tudunk az unió valószínûségére becsléseket adni. Végül megoldunk két numerikus feladatot több, napjainkban használt, becslési eljárás segítségével. A legjobb eredményeket a dolgozatban ismertetett TDMP-n alapuló módszerrel kapjuk.

A feladat pontos leírása Tekintsünk darab tetszõleges eseményt, jelöljük ezeket a következõképpen:

A1 , A2 ,..., An Célunk, hogy becslést adjunk ezek uniójának valószínûségére. Tegyük fel, hogy csak két eseményünk van, és adottak az egyes események valószínûségei és metszetük valószínûsége. Ekkor az alábbi képlet megadja az unió valószínûségének pontos értékét:

*

adjunktus, Budapesti Mûszaki és Gazdaságtudományi Egyetem, Matematikai Intézet

Doktorok és doktoranduszok

147

Három eseményre hasonló gondolatmenettel kapjuk:

Ha ezeket a képleteket általánosítani akarjuk, szükségünk van a k -adik binomiális momentum fogalmára:

A fenti képletben az összes lehetséges módon kiválasztottunk k darab eseményt, tekintettük ezek metszeteinek a valószínûségét, majd ezeket a mennyiségeket összeadtuk. A binomiális momentumok segítségével már felírható az ún. szita-formula (Poincaré-formula):

Sajnos a gyakorlatban, már kevés esemény esetén is problémát jelent (lényegében lehetetlen) az összes binomiális momentum kiszámolása, így általában csak S1 , S 2 ,..., S m áll rendelkezésünkre, ahol m jóval kisebb, mint n . A Boole-Bonferroni egyenlõtlenség erre az esetre ad választ. Azt mondja, hogy ha a szita-formula összegét úgy vágjuk le, hogy a legutolsó tag kivonással szerepel, akkor alsó, ha úgy, hogy az utolsó tag összeadással szerepel, akkor felsõ korlátot kapunk. Képlettel:

Három esemény esetén az alábbi alsó korlátot kapjuk, ha m = 2 :

Az m = 1 esetben az alábbi felsõ korlátot kapjuk:

148

XXI. Század – Tudományos Közlemények 2009/22

A dolgozatban az alábbi feladattípust vizsgáljuk. Adottak a következõ valószínûségek:

ahol k = 1,2,.., m . Ezek alapján szeretnénk becslést adni a

valószínûségre. Vegyük észre, hogy ha a fenti valószínûségek adottak, akkor S1 , S 2 ,..., S m számolható. Így a Boole-Bonferroni egyenlõtlenség korlátai becslést adnak az unió valószínûségére. A késõbbiekben ezeknél pontosabb becslésekkel foglalkozunk.

Gazdasági alkalmazások A fenti feladat segítségével közelítést adhatunk többdimenziós eloszlásfüggvények értékeinek kiszámításához. Legyen ( X 1 , X 2 ,..., X n ) egy valószínûségi vektorváltozó, egy F eloszlásfüggvénnyel. Szeretnénk kiszámolni F ( x1 , x 2 ,..., x n ) értékét. Ha az n értéke nagy (nagyobb, mint 30), akkor a numerikus integrálási eljárások csõdöt mondanak. Kisebb dimenziókra viszont az eloszlásfüggvény kiszámolása nem jelent problémát. Ezek alapján az alábbi megfeleltetést alkalmazhatjuk. Tegyük fel, hogy m dimenzióig ki tudjuk az eloszlásfüggvényt számolni. Az eseményeket az alábbi módon definiáljuk:

Ekkor:

Azonban a De Morgan-azonosság miatt:

Tehát, ha becslést adunk A1 , A2 ,..., An uniójára, akkor egyúttal becslést adunk F ( x1 , x 2 ,..., x n ) értékére is. Ha m dimenzióig kiszámolhatók az eloszlásfüggvények, akkor legfeljebb m esemény metszetének a valószínûsége is kiszámolható. Képlettel:

és így tovább, a szita-formulát megfelelõen alkalmazva. Tehát ez esetben pontosan a dolgozat elõzõ szakaszában definiált alapfeladathoz jutottunk.

Doktorok és doktoranduszok

149

Többdimenziós eloszlásfüggvény értékének kiszámolására a gazdaság több területén is szükség van. Egyrészt portfoliók hozamszámításánál szükség lehet az egyes értékpapírok hozamaiból képzett valószínûségi vektorváltozó eloszlásának becslésre. Itt általában az egyes hozamok normális vagy lognormális eloszlást követnek és egymással korrelálnak. A másik gyakori alkalmazás a sztochasztikus idotervezési feladat (PERT). Ennek megoldása során egyik fontos részfeladat a többdimenziós normális eloszlás eloszlásfüggvénye értékének becslése. Ezeken kívül minden, több véletlen változót használó, tervezési és modellezési problémánál pontosabb eredményt kapunk, ha a valószínuségi változókat együtt tekintjük (pl. nem tesszük fel, hogy függetlenek), és ilyenkor szükség van a többdimenziós eloszlásfüggvény értékeinek kiszámítására. A következõ szakasz módszerei a szimulációnál hatékonyabb eszközök többdimenziós eloszlások becslésére.

Becslési eljárások Az egyik megközelítés gráfelméleti módszereken alapul. Itt arról van szó, hogy az események egy gráf pontjai, két esemény metszete a gráf megfelelõ élének felel meg. Hipergráfokat tekintve lehetséges az események hármas, négyes stb. metszeteinek a reprezentálása is. A megfelelõ (általában fa) struktúrákat tekintve ezen a gráfon, meghatározható, hogy mely eseménymetszeteket és milyen elõjellel kell a becslõösszegbe szerepeltetni, ahhoz hogy megfelelõ alsó ill. felsõ korlátokat kapjunk. Az elsõ, az m = 2 esetre, használható felsõ becslést adó eljárás a Hunter-Worsley-féle felsõ korlát (Hunter, 1976). Ennél pontosabb becslést adnak, az m = 3 esetre, a cseresznyefa-korlátok (Bukszár – Prékopa, 2001), illetve, nagyobb m -ek esetére a hipercseresznyefa- korlátok (Bukszár – Szántai , 2002). A másik módszer a binomiális diszkrét momentum problémán alapul. Az egyváltozós diszkrét binomiális momentum probléma megoldása az S1 , S 2 ,..., S m megadott értékei alapján kiszámolja a lehetséges legjobb korlátokat. A módszer kidolgozása, illetve a feladatot megoldó hatékony algoritmus kidolgozása Prékopa András nevéhez fûzõdik (Prékopa, 1988, 1990a, 1990b). Képlettel adott korlátok találhatók (Boros – Prékopa, 1989) cikkében. A többváltozós diszkrét momentum probléma kidolgozása ugyancsak Prékopa nevéhez fûzõdik (Prékopa, 1992). További eredmények, hatékony megoldási módszerek találhatók még a (Prékopa, 1998, 2000) és (Mádi-Nagy – Prékopa, 2004) dolgozatokban. Az utóbbi idõkig az események uniójának valószínûségére használt TDMP megoldása nehézségekbe ütközött. Az áttörést Mádi-Nagy (2007) dolgozata hozta meg, mely egy közelítõ megoldási módszert publikál. A numerikus példákban a TDMP korlátainál ezt használjuk.

Korlátok az unió valószínûségére a TDMP segítségével Továbbra is n eseményünk van. Osszuk szét õket s darab rész eseménysorozatra. A j edik sorozat tagjait jelölje A j1 , K , A jn j , j = 1, K , s . Természetesen n1 + L + n s = n . Az X j valószínûségi változó, Z j = {z j 0 , K , z jn j } tartóval, legyen egyenlõ a j -edik sorozatban bekövetkezett események számával, j = 1, K , s . Ekkor az ( X 1 , K , X s ) véletlen vektorhoz tartozó (α 1 , K , α s ) -rendû kereszt-binomiális momentumot az alábbi képlettel definiálhatjuk:

150

XXI. Század – Tudományos Közlemények 2009/22

Látható, hogy α 1 + K + α s ≤ m esetén a fenti momentumok kiszámolhatók. Legyen

Ezek után az unió valószínûségének becslésére felírhatjuk az alábbi TDMP-feladatot:

Vegyük észre, hogy a fenti TDMP egy lineáris programozási feladat! Az Sα1Kα s értékei ismertek ( S 0K0 = 1 ), az ismeretlen változók a pi1Kis valószínûségek. Sajnos az együttható mátrix inverze numerikusan nehezen számolható, így sem a szimplex módszerrel, sem egyéb általános megoldó algoritmussal belátható futási idõvel a feladat nem oldható meg. Szerencsére az alábbi H esetén (Mádi-Nagy, 2007) algoritmusa jó közelítõ megoldást ad.

A következõ szakaszban ezt a modellt használjuk becslésre különbözõ esemény részsorozatokra m = m j = 3 értékekkel.

Doktorok és doktoranduszok

151

Numerikus eredmények Két eseményrendszert definiálunk. Mindegyikben 12 esemény szerepel: A1 , A2 ,..., A12 . Mindkét esetben 16 lehetséges kimenetelt tekintünk, jelölje ezeket x1 , x 2 ,..., x16 , az elõfordulásuk valószínûségeit pedig jelölje P ( x1 ), P ( x 2 ),..., P ( x16 ) . Az események és a kimenetelek I I I közti összefüggést a I rendszerben az R = ( rij ) mátrixszal definiáljuk, ahol rij = 1 , ha az I xi kimenetel esetén az A j esemény bekövetkezik, különben rij = 0 . A II rendszert ugyanígy definiálja az R II mátrix. (A mátrixokat véletlenszerûen generáltuk, különbözõ sûrûséggel).

Vegyük észre, hogy az x16 kivételével minden kimenetel esetén legalább egy esemény bekövetkezik. Így az unió valószínûsége:

A kimenetelek valószínûségeit három különbözõ esetre definiáltuk:

152

XXI. Század – Tudományos Közlemények 2009/22

Az alábbiakban az események uniójára kapott felsõ korlátokat szolgáltató eredményeket ismertetjük. Az elsõ oszlopban az egyváltozós diszkrét momentum probléma S1 , S 2 , S 3 momentumokon alapuló korlátai szerepelnek. Utána a Mádi-Nagy-féle TDMP-korlátok következnek, az alábbi részsorozat rendszerekre.

Végül a gráfelméleti eszközöket használó cseresznyefa-korlátok szerepelnek. Az I rendszer eredményei:

A II rendszer eredményei:

Az eredmények azt mutatják, hogy a fenti eseményrendszerek esetében az egyes események, az eseménypárok metszetei és az eseményhármasok metszetei valószínûségének ismeretében a TDMP-n alapuló becslési eljárás adja a legjobb eredményt. További numerikus példák, hasonlóan jó eredményekkel találhatók még Mádi-Nagy (2007) dolgozatában.

Doktorok és doktoranduszok

153

Felhasznált irodalom Bukszár József – Prékopa András (2001): Probability Bounds with Cherry Trees. Mathematics of Operations Research, 26. évf., 1. szám, 174–192. Bukszár József – Szántai Tamás (2002): Probability bounds given by hypercherry trees. Optimization Methods and Software, 17. évf., 409–422. Hunter, David (1976): An upper bound for the probability of a union. Journal of Applied Probability, 13. évf., 597–603. Mádi-Nagy Gergely – Prékopa András (2004): On Multivariate Discrete Moment Problems and their Applications to Bounding Expectations and Probabilities. Mathematics of Operations Research, 29. évf., 2. szám, 229–258. Mádi-Nagy Gergely (2007): On Multivariate Discrete Moment Problems: Generalization of the Bivariate Min Algorithm for Higher Dimensions. RUTCOR Research Report, 13-2007, SIAM Journal on Optimization, elfogadva. Prékopa András (1988): Boole-Bonferoni Inequalities and Linear Programming. Operations Research, 36. évf., 1. szám, 145–162. Prékopa András (1990a): Sharp bounds on probabilities using linear programming. Operations Research, 38. évf., 227–239. Prékopa András (1990b): The discrete moment problem and Linear Programming. Discrete Applied Mathematics, 27. évf., 235–254. Prékopa András (1992): Inequalities on Expectations Based on the Knowledge of Multivariate Moments. In: M. Shaked – Y.L. Tong (szerk.): Stochastic Inequalities, Institute of Mathematical Statistics. Lecture Notes – Monograph Series, 22. évf., 309–331. Prékopa András (1998): Bounds on Probabilities and Expectations Using Multivariate Moments of Discrete Distributions. Studia Scientiarum Mathematicarum Hungarica, 34. évf., 349–378. Prékopa András (2000): On Multivariate Discrete Higher Order Convex Functions and their Applications. RUTCOR Research Report, 39-2000. Továbbá: In: Proceedings of the Sixth International Conference on Generalized Convexity and Monotonicity, Karlovasi, Samos, Greece, augusztus 29 – szeptember 2. Megjelenés alatt.

154

XXI. Század – Tudományos Közlemények 2009/22