3. A3. Valószínűségi eloszlások

A valószínűség az eseményhalmazokon definiált olyan mérték, amely az alábbi három axiómát elégíti ki:

  1. Minden esemény mértéke egy 0 és 1 közötti szám. Ezt a következőképpen írjuk: 0 ≤ P(E = ei) ≤ 1, ahol az E egy eseményt képviselő véletlen változó, és az ei-k az E lehetséges értékei. Általánosságban a véletlen változókat nagybetűkkel, az értékeit pedig kisbetűkkel jelöljük.

  2. Az egész halmaz mértéke 1; azaz

  3. Diszjunkt halmazok uniójának a valószínűsége az egyedi események valószínűségeinek összege, azaz P(E = e1E = e2) = P(E = e1) + P(E = e2), ahol e1 és e2 diszjunktak.

Egy valószínűségi modell (probabilistic model) a kölcsönösen egymást kizáró, lehetséges kimenetelek mintateréből áll, és minden kimenetel valószínűségi mértékéből. A holnapi időjárás modelljében például a kimenetelek a következők lehetnek: napos, felhős, esős vagy havas. Ezen kimenetelek egy részhalmaza képvisel egy eseményt. A csapadékesemény például az {esős, havas} részhalmaz.

A ⟨P(E = e1), …, P(E = en)⟩ értékekből képzett vektor jelölésére a P(E)-t fogjuk használni. A P(ei) jelölést szintén használni fogjuk a P(E = ei) rövidítésére, hasonlóan a -ként rövidítjük.

A P(B|A) feltételes valószínűséget a P(B A)/P(A) definiálja. A és B feltételesen függetlenek, ha P(B|A) = P(B) [vagy ekvivalens módon P(A|B) = P(A)]. Folytonos változók esetén az értékek halmaza végtelen, és hacsak pontszerű tüskék nincsenek, mindegyik érték valószínűsége 0. Emiatt egy valószínűségi sűrűségfüggvényt (probability density function) definiálunk, amit szintén P(X)-szel fogunk jelölni. P(X) jelentése a P(A) diszkrét valószínűségi függvénytől kissé eltér. A P(X = c) sűrűségfüggvény-érték az a valószínűség, hogy az X a c körüli intervallumba esik, elosztva az intervallum hosszával, és határátmenetet képezve, ahogy az intervallum hossza tart a 0-hoz:

A sűrűségfüggvénynek nemnegatívnak kell lennie minden x-re, és teljesítenie kell, hogy:

Definiálhatunk egy valószínűségi eloszlásfüggvényt (cumulative probability density function), F(X)-et is, ami annak a valószínűsége, hogy a véletlen változó x-nél kisebb:

Jegyezzük meg, hogy a valószínűségi sűrűségfüggvénynek létezik egysége, az eloszlásfüggvény viszont egység nélküli. Ha az X-et például másodpercben mérjük, akkor a sűrűséget Hz-ben (azaz 1/s) fogjuk. Ha X a méterben mért háromdimenziós tér egy pontja, akkor a sűrűséget 1/m3-ben mérjük.

Az egyik legfontosabb valószínűség-eloszlás a Gauss-eloszlás (Gaussian distribution), amit normális eloszlásnak (normal distribution) is szokás nevezni. A μ középértékű és σ szórású (σ2 varianciájú) Gauss-eloszlás definíciója:

ahol x egy folytonos változó –∞-től +∞-ig terjedő értékkészlettel. μ = 0 és σ 2 =1 mellett kapjuk a standard normális eloszlás (standard normal distribution) speciális esetet. Egy d dimenziós x vektor feletti eloszlás a többváltozós Gauss-eloszlás (multivariate Gaussian distribution):

ahol μ az eloszlás középértékvektora, Σ pedig a kovarianciamátrix (covariance matrix).

A standard normális eloszlás egydimenziós eloszlásfüggvénye:

ahol az erf(x) az ún. hibafüggvény (error function), amelynek zárt alakja nincs.

A központi határeloszlás tétele (central limit theorem) azt mondja, hogy n véletlen változó középértékének az eloszlása a normális eloszláshoz tart, ha n tart végtelenhez. Igaz ez a véletlen változók majdnem minden halmazára, hacsak valamelyik véges alhalmaz varianciája a többit nem fogja dominálni.

3.1. Irodalmi és történeti megjegyzések

A számítógépes tudományokban ma oly elterjedten használt O() jelölést (nagy ordó) P. G. H. Bachmann német matematikus vezette be a számelmélettel kapcsolatban (Bachmann, 1894). Az NP-teljesség koncepcióját Cook (Cook, 1971) dolgozta ki, míg a problémák egymásra redukálásának modern módszertanát Karpnak köszönhetjük (Karp, 1972). Munkásságukért mindketten Turing-díjban – a számítógépes tudományok legmagasabb elismerésében – részesültek.

Az algoritmusok elemzésére és tervezésére irányuló klasszikus munkák között találjuk a (Knuth, 1973; Aho és társai, 1974) műveket. Újabb adalékok Tarjantól (Tarjan, 1983) és a Cormen, Leiserson és Rivest szerzőhármastól (Cormen és társai, 1990) származnak. Ezekben a művekben a hangsúlyt a kezelhető problémákat megoldó algoritmusok tervezésére és elemzésére helyezték. Az NP-teljességnek, illetve a kezelhetetlenség más formáinak az elméletébe a legjobb bevezetők (Garey és Johnson, 1979) és (Papadimitriou, 1994). Az elmélet tárgyalásán túlmenően Garey és Johnson meggyőzően, példákkal illusztrálják, hogy a számítógépes szakemberek miért a polinom és az exponenciális futási időigény határára teszik egyhangúan a kezelhető és kezelhetetlen problémák közötti határvonalat. A szerzők az NP-teljesként vagy más szempontból kezelhetetlennek ismert problémák terjedelmes katalógusát is mellékelik.

A valószínűség-számításról jó művek (Chung, 1979; Ross, 1988; Bertsekas–Tsitsiklis, 2002; Feller, 1971).