A diszkrét momentum-probléma, és alkalmazása távközlési hálózatok megbízhatóságára

Diplomamunka

Készítette: Kotnyek Balázs V. matematikus Témavezető: Prékopa András egyetemi tanár

Eötvös Loránd Tudományegyetem Természettudományi Kar Operációkutatási Tanszék

Budapest, 1997.

Tartalom

1 Bevezetés 2

2 Valószínűségek becslése a lineáris programozás segítségével 4 2.1 A Boole-Bonferroni típusú egyenlőtlenségek . . . . . . . . . . . . 4 2.2 A lineáris programozási feladat . . . . . . . . . . . . . . . . . . . 6 2.3 Duál-megengedett bázisok . . . . . . . . . . . . . . . . . . . . . . 8 2.4 P (μ ≥ 1) becslése . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.5 P (μ = r) becslése . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.6 P (μ ≥ r) becslése . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

3 Becslések zárt alakban 18 3.1 Mátrixinverzek zárt alakban . . . . . . . . . . . . . . . . . . . . . 18 3.2 Véges differenciák . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3.3 Zárt alakú becslések P (μ ≥ 1)-re . . . . . . . . . . . . . . . . . . 22 3.4 Zárt alakú becslések P (μ = r)-re, valamint P (μ ≥ r)-re . . . . . 26

4 A diszkrét momentum-probléma 28 4.1 Differencia-hányadosok és duál-megengedett bázisok . . . . . . . 31 4.2 Általánosítás . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 4.3 Becslések a hatványmomentumok felhasználásával . . . . . . . . 36

5 Alkalmazások 39 5.1 A kielégíthetőségi probléma . . . . . . . . . . . . . . . . . . . . . 39 5.2 Sztochasztikus szállítási hálózatok . . . . . . . . . . . . . . . . . 40 5.3 Hálózatok megbízhatósága . . . . . . . . . . . . . . . . . . . . . . 42

6 Távközlési hálózatok megbízhatósága 44 6.1 A modell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 6.2 A megbízhatóság becslése . . . . . . . . . . . . . . . . . . . . . . 45 6.3 A fixpont módszer . . . . . . . . . . . . . . . . . . . . . . . . . . 46

6.3.1 Elfogadási valószínűségek→beérkezési paraméterek …. 46 6.3.2 Beérkezési paraméterek→elfogadási valószínűségek …. 48

6.4 Egy konkrét példa . . . . . . . . . . . . . . . . . . . . . . . . . . 49

1. Fejezet

Bevezetés

Valószínűségek becslése magasabb dimenziós terekben számos esetben előforduló probléma a megbízhatóság-elméletben, a sztochasztikus programozásban, a statisztikában és gyakorlatilag az összes sztochasztikus rendszerekkel foglalkozó tudományágban. Általában egyszerűbb eseményekből összetett események valószínűségét kell megbecsülni például, ha meg akarjuk határozni az x_{1}, …, x_{n} valószínűségi változók együttes eloszlását, amihez {x_{1} ≤ t_{1}, …, x_{n} ≤ t_{n}} alakú összetett események valószínűségét kell kiszámolni. Ez a feladat jelenik meg többek között a sztochasztikus programozásban, ha valószínűséget kell maximalizálnunk, vagy valószínűségi korlátok mellett kell egy függvény értékét optimalizálnunk. Sajnos a legtöbb esetben az ehhez hasonló, magasabb dimenziós valószínűségek kiszámolása rendkívül bonyolult. Ebben a dolgozatban egy olyan módszert mutatunk be, amely az alacsonyabb dimenziós valószínűségek ismeretében a lineáris programozás segítségével kielégítő becsléseket szolgáltat összetett események valószínűségére. A módszert Prékopa András dolgozta ki.

Az első, valamely összetett esemény valószínűségét becslő egyenlőtlenség George Boole nevéhez fűződik [3, 5, 4]. Az ismert Boole-egyenlőtlenség véges sok esemény úniójának valószínűségét becsüli felülről az események valószínűségének összegével. C.E. Bonferroni volt az, aki 1937-ben ezt továbbfejlesztve [2] a legfeljebb k db. eseményből (1 ≤ k ≤ m, ahol m < n) álló metszetvalószínűségeketet használó becsléseket látott be. Általában azonban ezek a becslések nem a legjobbak, ugyanannyi információ birtokában élesebb becsléseket is adhatunk. A fentebb említett módszer a lehető legjobb becslést adja meg ezen információk felhasználásával.

Dawson és Sankoff voltak az elsők, akik a lineáris programozás elméletét használva nyertek becsléseket 1967-ben [8]. Az ő állításaikra adott más bizonyítást Galambos 1977-ben [11]. Azóta számos eredmény született, így például Kwerel, 1975 [23]; Sathe, Pradhan és Shah, 1980 [34]; Galambos és Mucci, 1980 [12]; Móri és Székely, 1985 [26]. Prékopa, 1988 [27], 1990 [29] és Prékopa és Boros, 1989 [6] foglalta általános keretbe a problémát.

A diplomamunka felépítése a következő. A 2. fejezetben bemutatjuk a problémákat, megadjuk az ezeket leíró lineáris programozási feladatokat, és algoritmust adunk ezek megoldására [27] és [29] alapján. A 3. fejezetben zárt alakú becsléseket vezetünk le az összetett valószínűségekre [6] alapján. A 4. fejezetben az addigiak általánosítását, a diszkrét momentum-problémát tárgyaljuk [28] alapján. Az 5. fejezetben a módszer különféle alkalmazásait mutatjuk be [7],

[31] és [32] alapján. A 6. fejezet egy gyakorlati probléma kapcsán mutatja be, hogy a becslési módszerünk milyen sokoldalúan használható.

Szeretném megköszönni témavezetőmnek, Prékopa Andrásnak, a diplomamunka elkészítéséhez nyújtott hasznos tanácsait.

Valószínűségek becslése a lineáris programozás segítségével

2.1 A Boole-Bonferroni típusú egyenlőtlenségek

Legyenek A_{1}, …, A_{n} tetszőleges események egy tetszőleges valószínűségi mezőben. Ezen elemi eseményekből összetett események valószínűségét szeretnénk becsülni. A legelső és legismertebb ilyen eredmény a Boole-egyenlőtlenség, amelyet George Boole fedezett fel [3, 5, 4] és amely az A_{1}, …, A_{n} események úniójának, vagyis annak a valószínűségét becsüli, hogy legalább egy bekövetkezik az események közül:

P (⋃_{i=1}^{n} A_{i}) ≤ ∑_{i=1}^{n} P (A_{i})  (2.1)

Ezt alkalmazva a komplementer eseményekre (\overline{A}_{i}, i = 1, …, N) az A_{1}, …, A_{n} metszetére kapunk alsó becslést:

P (⋂_{i=1}^{n} A_{i}) ≥ ∑_{i=1}^{n} P (A_{i}) − (n − 1)

ezek a becslések, bár fontos szerepet játszanak sok elméleti és gyakorlati problémában, elég durvák, ám ha csak a P (A_{i}), i = 1, …, n valószínűségeket ismerjük, akkor nem is tudunk ezeknél jobb becslést adni, ahogy azt Fréchet [10] bizonyította. Ha azonban ismerünk néhányat a metszetvalószínűségek közül, akkor élesebb becsléseket kaphatunk.

A formulák egyszerűsítése érdekében a továbbiakban az események únióját összeadással, metszetét szorzással jelöljük.

Vezessük be a következő jelöléseket:

S_{k} = ∑_{1≤i_{1}<...<i_{k}≤n} P (A_{i_{1}} … A_{i_{k}})  k = 1, …, n
S_{0} = 1

A klasszikus szita-formula szerint:

P (∑_{i=1}^{n} A_{i}) = S_{1} − S_{2} + ⋯ + (−1)^{n−1} S_{n}  (2.2)

A Bonferroni-egyenlőtlenségek [2] ezen összeg első néhány tagját használják:

P (∑_{i=1}^{n} A_{i}) ≥ ∑_{k=1}^{2m}(−1)^{k−1} S_{k}  (m ≥ 1)

P (∑_{i=1}^{n} A_{i}) ≤ ∑_{k=1}^{2m+1}(−1)^{k−1} S_{k}  (m ≥ 0)

Ezek általánosításához vezessük be a μ valószínűségi változót, amely az A_{i}-k közül bekövetkezők számát jelöli. Vagyis μ lehetséges értékei: 0, 1,…, n, és pl. {⋃_{i=1}^{n} A_{i}} = {μ ≥ 1}, {⋂_{i=1}^{n} A_{i}} = {μ = n}. Ekkor a

P (μ ≥ r) ≥ ∑_{i=1}^{m} x_{i}S_{i}  vagy a

P (μ ≥ r) ≤ ∑_{i=1}^{m} y_{i}S_{i}

(m, r ∈ {0, 1, …, n}, x_{i}, y_{i} valós számok) alakú egyenlőtlenségeket Boole-Bon-ferroni típusú egyenlőtlenségeknek nevezzük.

A μ és az S_{k} kapcsolatáról szól a következő tétel, amelyre Takács Lajos bizonyítását közöljük (ld. [36])

Tétel 2.1 Az S_{k} a μ valószínűségi változó k-adik binomiális momentuma, azaz

S_{k} = E [(\begin{matrix}μ \\ k \end{matrix})] k = 0, …, n

Bizonyítás. Legyenek ξ_{1}, ξ_{2}, …, ξ_{n} az A_{1}, …, A_{n} események indikátor-válto-zói, azaz ξ_{i} = 1, ha A_{i} bekövetkezik, különben ξ_{i} = 0. Így μ = ξ_{i} + ⋯ + ξ_{n}, és

(\begin{matrix}μ \\ k \end{matrix}) = ∑ ; \begin{matrix}k_{1} + ⋯ + k_{n} = k \\ k_{1} ≥ 0, …, k_{n} ≥ 0 \end{matrix} (\begin{matrix}ξ_{1} \\ k_{1} \end{matrix}) ⋯ (\begin{matrix}ξ_{n} \\ k_{n} \end{matrix})

Mivel ξ_{i} csak 0 vagy 1 lehet, a fenti összeg olyan tagjai, amelyben k_{i}-k valamelyike nagyobb mint 1, nullával egyenlők:

(\begin{matrix}μ \\ k \end{matrix}) = ∑_{1≤i_{1}<···<i_{k}≤n} ξ_{i_{1}} ⋯ ξ_{i_{k}}

Várható értéket véve, és felhasználva az E(ξ_{i_{1}} ⋯ ξ_{i_{k}}) = P (A_{i_{1}} ⋯ A_{i_{k}}) egyenlőséget a tétel állítása következik. □

Ebben a fejezetben becslést szeretnénk adni a P (μ ≥ 1), P (μ = r) (r ∈ {0, 1, …, n}) és a P (μ ≥ r) (r ∈ {1, …, n}) értékeire, vagyis azon események valószínűségére, hogy legalább egy, pontosan r, illetve legalább r bekövetkezik az A_{i}-k közül. Persze, ha ismerjük az S_{1}, …, S_{n} értékeit, akkor pontosan is kiszámolhatjuk a kérdéses valószínűségeket. A P (μ ≥ 1)-re a 2.2 egyenlet ad egy formulát, a másik kettőre pedig a következők:

P (μ = r) = ∑_{k=r}^{n}(−1)^{k−r} (\begin{matrix}k \\ r \end{matrix}) S_{k}

P (μ ≥ r) = ∑_{k=r}^{n}(−1)^{k−r} (\begin{matrix}k − 1 \\ r − 1 \end{matrix}) S_{k}

Ezeket a formulákat Jordán Károly publikálta 1927-ben [19], de már C. Jordan ismerte őket 1867-ben [17].

Ha n nagy, akkor ezek a formulák nem nyújtanak praktikus módszert a valószínűségek kiszámolásához, mivel az S_{i}-kben foglalt valószínűségek száma n-nek exponenciális függvénye, így ésszerű időn belül nem tudjuk az összes S_{i}- t kiszámolni. Ám a lineáris programozás segítségével kellően éles becsléseket kaphatunk csupán S_{1}, …, S_{m} (m < n) ismeretében is.

2.2 A lineáris programozási feladat

Vezessük be a következő jelölést:

P (μ = i) = v_{i} i = 0, 1, …, n

Az 2.1 Tétel alapján

S_{k} = ∑_{t=0}^{n} (\begin{matrix}t \\ k \end{matrix}) v_{t} k = 0, 1, …, n

Tegyük fel, hogy ismerjük S_{1}, …, S_{m} értékét (m < n). Ekkor v_{i}-kre teljesül az alábbi feltételrendszer:

v_{0}+ v_{1}+ v_{2}+⋯ +  v_{m}+⋯ +  v_{n} = 1 ; v_{1}+ 2v_{2}+⋯ + mv_{m}+⋯ +  nv_{n} = S_{1} ; v_{2}+⋯ +(\begin{matrix}m \\ 2 \end{matrix}) v_{m}+⋯ + (\begin{matrix}n \\ 2 \end{matrix}) v_{n} = S_{2} ; ⋮ ; v_{m}+⋯ +(\begin{matrix}n \\ m \end{matrix}) v_{n} = S_{m} ; v_{1} ≥ 0,v_{2} ≥ 0 … v_{m} ≥ 0 … v_{n} ≥ 0  (2.3)

Ez azt jelenti, hogy v_{0}, …, v_{n} benne van a 2.3 által meghatározott n-dimenziós konvex poliéderben. Az általunk becsülni kívánt valószínűségek v_{i}-k függvényei, tehát felső és alsó becslést kaphatunk P (μ ≥ 1), P (μ = r) és P (μ ≥ r) pontos értékére, ha kiszámoljuk a következő lineáris programozási feladatok optimumát.

min (v_{1} + ⋯ + v_{n})
feltéve, hogy ∑_{i=1}^{n} (\begin{matrix}i \\ k \end{matrix}) v_{i} = S_{k}  k = 1, …, m
v_{i} ≥ 0  i = 1, …, n

(2.4)

max (v_{1} + ⋯ + v_{n})
feltéve, hogy ∑_{i=1}^{n} (\begin{matrix}i \\ k \end{matrix}) v_{i} = S_{k}  k = 1, …, m
v_{i} ≥ 0  i = 1, …, n

(2.5)

min  v_{r}
feltéve, hogy ∑_{i=0}^{n} (\begin{matrix}i \\ k \end{matrix}) v_{i} = S_{k}  k = 0, …, m
v_{i} ≥ 0  i = 0, …, n

(2.6)

max  v_{r}
feltéve, hogy ∑_{i=0}^{n} (\begin{matrix}i \\ k \end{matrix}) v_{i} = S_{k}  k = 0, …, m
v_{i} ≥ 0  i = 0, …, n

(2.7)

min (v_{r} + ⋯ + v_{n})
feltéve, hogy ∑_{i=0}^{n} (\begin{matrix}i \\ k \end{matrix}) v_{i} = S_{k}  k = 0, …, m
v_{i} ≥ 0  i = 0, …, n

(2.8)

max (v_{r} + ⋯ + v_{n})
feltéve, hogy ∑_{i=0}^{n} (\begin{matrix}i \\ k \end{matrix}) v_{i} = S_{k}  k = 0, …, m
v_{i} ≥ 0  i = 0, …, n

(2.9)

Észrevehető, hogy a 2.4 és a 2.5 feladatok feltételei között nem szerepel a v_{0} + v_{1} + ⋯ + v_{n} = 1, v_{0} ≥ 0. Ezt azért hagyhatjuk el, mert a célfüggvényt korlátozza felülről, mégpedig 1-gyel. A 2.4 feladat optimuma mindenképpen kisebb, vagy egyenlő, mint 1, ha pedig a 2.5 feladat optimuma nagyobb, mint 1, akkor figyelembe véve a korlátot, megállapíthatjuk, hogy a legjobb felső becslés P (μ ≥ 1)-re egyenlő 1-gyel. Ezt a többi feladatnál nem tehetjük meg, ezért azokban szerepel az S_{0}-ra, és a v_{0}-ra vonatkozó feltétel is.

A lineáris programozási feladatok megoldásához duál-módszert fogunk alkalmazni, ezért előbb vessünk néhány pillantást a duál-megengedett bázisokra.

2.3 Duál-megengedett bázisok

Tekintsünk egy lineáris programozási feladatot:

min (ill. max) c^{T} x
felt., hogy Ax = b
x ≥ 0

(2.10)

ahol x, c ∈ R^{n}, b ∈ R^{m}, A egy m × n-es (m < n) teljes rangú mátrix. Az A oszlopai legyenek: a_{1}, a_{2}, …, a_{n}. Legyen B egy bázisa A-nak, azaz B = (a_{i_{1}}, a_{i_{2}}, …, a_{i_{m}}), I = {i_{1}, …, i_{m}} ⊂ {1, 2, …, n}, és a_{i_{1}}, a_{i_{2}}, …, a_{i_{m}} függetlenek. (Néha, ha ez világosabbá teszi a jelölést, B helyett B(I)-t írunk.) Jelöljük c_{B}-vel a c báziskomponenseiből alkotott vektort. Egy y vektort, amire teljesül, hogy:

y^{T} B = c_{B}^{T}

a B-hez tartozó duálvektornak hívunk. A B-t duál-megengedettnek nevezzük, ha a minimalizálás (ill. maximalizálás) esetén

\begin{aligned}y^{T} a_{p} & ≤ & c_{p} & ∀p ∈ \{1, …, n\}\I \\ (y^{T} a_{p} & ≥ & c_{p} & ∀p ∈ \{1, …, n\}\I) \end{aligned}  (2.11)

Ha y^{T} a_{p} ≠ c_{p} ∀p ∈ {1, …, n}\I-re, akkor a bázist duál-nemdegeneráltnak mondjuk, különben duál-degenerált.

Ha B duál-megengedett, y a hozzá tartozó duálvektor , akkor

\begin{aligned}y^{T} a_{p} & = & c_{B}^{T}B^{−1}a_{p} ≤ & c_{p} & ∀p ∈ \{1, …, n\} \\ (y^{T} a_{p} & = & c_{B}^{T}B^{−1}a_{p} ≥ & c_{p} & ∀p ∈ \{1, …, n\}) \end{aligned}

minimalizálás, illetve maximalizálás esetén, tehát y^{T} = c_{B}^{T}B^{−1} megengedett megoldása az 2.10 feladat duálfeladatának, amely a következő alakú:

max y^{T} b
felt., hogy y^{T} A ≤ c

a minimalizálás, illetve

min y^{T} b
felt., hogy y^{T} A ≥ c^{T}

a maximalizálás esetén.

Ezért y^{T} b értéke—az ismert dualitás-tételek szerint— kisebb, vagy egyenlő (nagyobb, vagy egyenlő), mint az 2.10 feladat optimuma.

A 2.11 egyenlőtlenséget optimalitási feltételnek nevezik, mert ha a bázis egyszerre primál- és duál-megengedett , akkor optimális. Ekkor y^{T} b egyenlő az 2.10 feladat optimumával. Ha még a bázis duál-nemdegenerált is, akkor a bázishoz tartozó bázismegoldás az egyetlen optimális megoldása a feladatnak.

A c_{p} − c_{B}^{T}B^{−1}a_{p} különbség kielégíti a következő azonosságot minden p ∈ {1, …, n}\I-re:

( \begin{matrix}1 & c_{B}^{T} \\ 0 & B \end{matrix} ) ( \begin{matrix}c_{p} − c_{B}^{T}B^{−1}a_{p} \\ B^{−1}a_{p} \end{matrix} ) = ( \begin{matrix}c_{p} \\ a_{p} \end{matrix} )

vagyis

c_{p} − y^{T} a_{p} = c_{p} − c_{B}^{T}B^{−1}a_{p} = \begin{matrix}| & \begin{matrix}c_{p} & c_{B}^{T} \\ a_{p} & B \end{matrix} & | \\ | & \begin{matrix}1 & c_{B}^{T} \\ 0 & B \end{matrix} & | \end{matrix} = \frac{1}{|B|} | \begin{matrix}c_{p} & c_{B}^{T} \\ a_{p} & B \end{matrix} |  (2.12)

ha p ∈ {1, …, n}\I.

2.4 P (μ ≥ 1) becslése

A 2.12 azonosságból látszik, hogy a duál-megengedettség megállapításához determinánsok előjelét kell vizsgálni. Lássunk először egy tételt, amelyet később sokszor fel fogunk használni.

A következő, Pascal-mátrixnak nevezett mátrix minorjait vizsgáljuk:

( \begin{matrix}1 & 1 & 1 & 1 & … & 1 \\ & 1 & 2 & 3 & … & n \\ & & 1 & (\begin{matrix}3 \\ 2 \end{matrix}) & … & (\begin{matrix}n \\ 2 \end{matrix}) \\ & & & & ... & ⋮ \\ & & & & & 1 \end{matrix} )

A fődiagonális alatt lévő ki nem írt elemek mind 0-k. Minornak, a szokásos módon, a mátrix néhány sora, és ugyanannyi oszlopa által meghatározott részmátrix determinánsát nevezzük. Blokkminornak hívjuk, ha egymást követő sorok és oszlopok határozzák meg. Az ígért tétel a következő:

Tétel 2.2 A Pascal-mátrix minorjaira teljesül az alábbi két állítás:

(a) Minden minor nemnegatív.

(b) Az olyan minorok mind pozitívak, amelyeknek csak pozitív elemei vannak a diagonálisban, vagy afelett.

Bizonyítás. A Pascal-mátrix mérete (n) szerinti indukcióval bizonyítunk. Ha n = 1, akkor az állítások triviálisak. Tegyük fel, hogy (a) és (b) igaz az n méretű Pascal-mátrixra. Vegyünk egy r × r-es minort az n + 1 méretű Pascalmátrixból. Legyenek ennek a sorai a mátrix i_{1}, …, i_{r} indexű sorai, oszlopai a mátrix j_{1}, …, j_{r} indexű oszlopai (0 ≤ i_{1} < ⋯ < i_{r} ≤ n + 1, 0 ≤ j_{1} < ⋯ < j_{r} ≤

n + 1), azaz a minor a következő alakú (azzal a megegyezéssel, hogy (\begin{matrix}a \\ b \end{matrix}) = 0,

ha a < b):

M = | \begin{matrix}(\begin{matrix}j_{1} \\ i_{1} \end{matrix}) & … & (\begin{matrix}j_{r} \\ i_{1} \end{matrix}) \\ ⋮ & & ⋮ \\ (\begin{matrix}j_{1} \\ i_{r} \end{matrix}) & … & (\begin{matrix}j_{r} \\ i_{r} \end{matrix}) \end{matrix} |

Ha i_{r} < n + 1 és j_{r} < n + 1, akkor a minor tekinthető úgy is, mint az n-méretű Pascal-mátrix egy minorja, és akkor az induktív feltevés szerint kész vagyunk. Ha i_{r} = n + 1 vagy j_{r} = n + 1, akkor három esetet választhatunk szét:

(1) i_{1} ≥ 1, j_{1} ≥ 1: Szorozzuk meg a minor k-adik sorát i_{k}-val, és osszuk el

az l-edik oszlopát j_{l}-lel (i_{k} > 0, j_{l} > 0). Ekkor (\begin{matrix}j_{l} \\ i_{k} \end{matrix})-ból (\begin{matrix}j_{l−1} \\ i_{k−1} \end{matrix}) lesz, és az így

transzformált mátrixra az indukció miatt már igazak a tétel állításai, vagyis az eredetire is igazak.

(2) i_{1} ≥ 1, j_{1} = 0: Ekkor a minor első oszlopában csupa 0 áll.

(3) i_{1} = 0: Ekkor a minor első sorában csupa 1 áll. Vonjuk ki az utolsó előtti oszlopot az utolsóból,…, az elsőt a másodikból, és fejtsük ki a kapott determinánst az első sora szerint:

M = | \begin{matrix}(\begin{matrix}j_{2} \\ i_{2} \end{matrix}) − (\begin{matrix}j_{1} \\ i_{2} \end{matrix}) & … & (\begin{matrix}j_{r} \\ i_{2} \end{matrix}) − (\begin{matrix}j_{r−1} \\ i_{2} \end{matrix}) \\ ⋮ & & ⋮ \\ (\begin{matrix}j_{2} \\ i_{r} \end{matrix}) − (\begin{matrix}j_{1} \\ i_{r} \end{matrix}) & … & (\begin{matrix}j_{r} \\ i_{r} \end{matrix}) − (\begin{matrix}j_{r−1} \\ i_{r} \end{matrix}) \end{matrix} |  (2.13)

A (\begin{matrix}k_{1} \\ l \end{matrix}) − (\begin{matrix}k_{2} \\ l \end{matrix}) = ∑_{z=k_{2}}^{k_{1}−1} (\begin{matrix}z \\ l − 1 \end{matrix}) összefüggést alkalmazva (k_{1} > k_{2}), a 2.13 ezzel

egyenlő:

∑_{z_{1}=j_{1}}^{j_{2}−1} ⋯ ∑_{z_{r−1}=j_{r−1}}^{j_{r}−1} | \begin{matrix}(\begin{matrix}z_{1} \\ i_{2} − 1 \end{matrix}) & … & (\begin{matrix}z_{r−1} \\ i_{2} − 1 \end{matrix}) \\ ⋮ & & ⋮ \\ (\begin{matrix}z_{1} \\ i_{r} − 1 \end{matrix}) & … & (\begin{matrix}z_{r−1} \\ i_{r} − 1 \end{matrix}) \end{matrix} |  (2.14)

Az összegben szereplő összes determináns az n-méretű Pascal-mátrix egy minorja, vagyis nemnegatív, így M ≥ 0: az (a) állítást beláttuk. Ha M-re teljesülnek a (b) állítás feltételei is, azaz i_{1} ≤ j_{1}, …, i_{r} ≤ j_{r}, akkor ez teljesül legalább egyre a 2.14-ban szereplő minorok közül is. Az ilyenek az induktív feltevés szerint pozitívak, tehát M is az. Ezzel a (b) állítást is beláttuk. □

Megjegyzés. Ennek a tételnek egy másfajta, más témakörhöz kapcsolódó bizonyítása szerepel [14]-ben. A [27]-ben található hasonló szerepű állítás bizonyítása nem teljes, de a későbbi alkalmazásokhoz elegendő.

Jelöljük a_{1}, …, a_{n}-nel a 2.4 és 2.5 problémák egyenlőség feltételei által meghatározott mátrix (A) oszlopait. Legyen továbbá c^{T} = (1, 1, …, 1), B egy bázismátrix I pedig a bázisindexek halmaza. A B bázis duál-megengedettségét és duál-nemdegenerativitását vizsgáljuk a következőkben.

Tétel 2.3 A 2.4 és 2.5 feladatokban minden bázis duál-nemdegenerált.

Bizonyítás. A 2.12 összefüggés alapján azt kell bebizonyítanunk, hogy

| \begin{matrix}1 & c_{B}^{T} \\ a_{p} & B \end{matrix} | ≠ 0  ∀p ∈ \{1, …, n\}\I-re  (2.15)

Az oszlopok megfelelő cseréjével a Pascal-mátrix egy minorját kaphatjuk, mégpedig olyat, amelyet az első (m+1) sor határoz meg. Az 2.2 Tétel szerint ez a determináns pozitív, tehát a 2.15 determináns értéke különbözik nullától. □

A duál-megengedett bázisok szerkezetét a következő tétel írja le:

Tétel 2.4 A 2.4-2.5 feladatok egy bázisa duál-megengedett pontosan akkor, ha a következő szerkezetű (a bázisindexekkel kifejezve):

minimalizálás, m páros

I = {i, i + 1, j, j + 1, …, k, k + 1}

minimalizálás, m páratlan

I = {i, i + 1, j, j + 1, …, k, k + 1, n}

maximalizálás, m páros

I = {1, i, i + 1, j, j + 1, …, k, k + 1, …, n}

maximalizálás, m páratlan

I = {1, i, i + 1, j, j + 1, …, k, k + 1, }

(Az indexek növekvő sorrendben vannak elhelyezve.)

Bizonyítás. Tekintsük először a minimalizálást. Ekkor 2.12 szerint

c_{p} − c_{B}^{T}B^{−1}a_{p} = \begin{matrix}| & \begin{matrix}1 & c_{B}^{T} \\ a_{p} & B \end{matrix} & | \\ | & \begin{matrix}1 & c_{B}^{T} \\ 0 & B \end{matrix} & | \end{matrix} p ∈ \{1, …, n\}\I

előjelét kell vizsgálni. A 2.2 Tétel szerint a nevező pozitív, a számláló pedig nullától különböző értékű. A B bázis duál-megengedett pontosan akkor, ha

| \begin{matrix}1 & c_{B}^{T} \\ a_{p} & B \end{matrix} | > 0  (2.16)

minden p ∈ {1, …, n}\I-re. Legyenek a bázisindexek növekvő sorrendben {i_{1}, i_{2}, …, i_{m}}. Ekkor 2.16 így írható:

| \begin{matrix}1 & 1 & ⋯ & 1 \\ a_{p} & a_{i_{1}} & ⋯ & a_{i_{m}} \end{matrix} | > 0

Megfelelő oszlopcserékkel elérhető, hogy a_{p} a helyére kerüljön, vagyis az indexek növekvő sorrendben legyenek. Az így kapott determináns pozitív az 2.2 Tétel szerint, tehát 2.16 teljesüléséhez az kell, hogy páros sok oszlopcserét hajtsunk végre. Ebből pedig már következik a tétel állítása minimalizálás esetére, attól függően, hogy m páros, vagy páratlan. A maximalizálás ugyanígy kezelhető. □

A duál-megengedett bázisok ismeretében igen egyszerű algoritmusokat konstruálhatunk a 2.4 és a 2.5 feladatok megoldására. Ezek az algoritmusok a lexikografikus duál-módszer (ld. [24]) speciális esetei lesznek. Először egy kiinduló bázist kell keresnünk, amely duál-megengedett (B). Ha ez a bázis primálmegengedett, azaz

B^{−1}S ≥ 0

ahol S^{T} = (S_{1}, …, S_{m}), akkor B optimális. Ha ez nem teljesül, akkor válasszunk egy j-t, amelyre (B^{−1}S)_{j} < 0 és töröljük B-ből a j. oszlopot (általában ez nem egyenlő a_{j}-vel). A bázisba bejövő vektort úgy válasszuk meg, hogy a duál-megengedettség megmaradjon. Ezt a vektort konnyű megtalálni, mert mindössze egy lehetőség van a 2.4 Tételben leírt bázisszerkezet megőrzésére. Mivel egyetlen lehetőség van, úgy is mondhatjuk, hogy a bejövő vektort lexikografikusan választjuk, tehát az algoritmus véges lépésszámban végetér.

Megjegyezendő, hogy lehet olyan optimális bázis, amely nem duál-meg-engedett. Ez előáll, ha primál-degeneráltság keletkezik, vagyis az optimális bázismegoldás egyik koordinátája 0. Ekkor a bázisban ennek megfelelő vektort kicserélhetjük egy tetszőleges bázison kívüli vektorra, szintén 0 értékkel. Így a duál-megengedettség megszűnhet, ha az új bázis szerkezete nem felel meg a 2.4 Tételben leírtakéval, de az új bázis optimális marad.

Az algoritmushoz szükséges a B^{−1}-ek számolása. A következő fejezetben részben ezzel foglalkozunk, és képletet vezetünk le az inverzre, de erre általában a gyakorlatban nincs szükség, mert m elég kicsi, így egyszerűbb úton is megkaphatjuk B^{−1} értékét. A speciális szerkezetű, egymást követő indexű vektorokból álló bázis inverzére képlet található [27]-ben is.

Módosíthatjuk a problémát felső korlátok szerepeltetésével. Ezt az indokolja, hogy az S_{1}, …, S_{m} értékeit általában közvetlenül nem ismerjük, a

P (A_{i_{1}} … A_{i_{k}}), 1 ≤ i_{1} < … < i_{k} ≤ n, 1 ≤ k ≤ m  (2.17)

valószínűségekből számoljuk ki őket. Ha viszont csak az az S_{i}-ket használjuk, elveszítjük a 2.17-ban foglalt információ nagy részét. Ezt elkerülhetjük további feltételek beiktatásával. Ha ismerjük a 2.17 valószínűségeket, számoljuk ki az összes metszetvalószínűséget, amely az A_{1}, …, A_{n}, \overline{A}_{1}, …, \overline{A}_{n} események közül legfeljebb m metszetére vonatkozik, úgy hogy A_{i} és \overline{A}_{i} közül (1 ≤ i ≤ n) legfeljebb csak az egyiket használjuk egyszerre.A

P (μ = t) = v_{t} = ∑_{1≤i_{1}<...<i_{t}≤n} P (A_{i_{1}} … A_{i_{t}} \overline{A}_{j_{1}} … \overline{A}_{j_{n−t}})

összefüggésből, ahol {j_{1}, …, j_{n−t}} = {1, …, n}\{i_{1}, …, i_{t}} látszik, hogy a 2.17 valószínűségek használatával elérhető legjobb felső korlát v_{t}-re a következő:

v_{t} ≤ ∑_{1≤i_{1}<...<i_{t}≤n} q_{i_{1}...i_{t}} = V_{t}  t = 1, 2, …, n

ahol q_{i_{1}...i_{t}} az A_{i_{1}} … A_{i_{t}} \overline{A}_{j_{1}} … \overline{A}_{j_{n−t}} események közül az összes lehetséges módon kiválasztott m esemény metszetének valószínűsége közül a minimális. Ha m nem elég kicsi az új feltételekhez meglehetősen sok számolás szükséges, ezért gyengébb változatát is használhatjuk. Például azt, amikor q_{i_{1}...i_{t}} kiszámolásához m-nél kevesebb eseményt engedünk meg.

Ha felső korlátok szerepelnek a feltételek között, módosítanunk kell az algoritmust. Ezt megtehetjük a következőképpen:

1. lépés: Oldjuk meg a felső korlát nélküli feladatot a fentebb leírt módon.

2. lépés: Ha az optimális megoldás teljesíti a felső korlát feltételeket, akkor készen vagyunk.

3. lépés: Ha van a bázismegoldásnak olyan komponense, amelyik nagyobb, mint a felső korlátja, válasszunk ki egy ilyet (legyen ez v_{k}), és rögzítsük az értékét v_{k} = V_{k}-val. Oldjuk meg az így módosított feladatot, majd lépjünk vissza a 2. lépésre.

A 3. lépésben leírt módosítás azt jelenti, hogy töröljük a feltételek közül a k.

oszlopot és a v_{k}-t, valamint a jobboldalakból kivonunk (\begin{matrix}k \\ i \end{matrix}) V_{k}-t. Így egy olyan

feladatot kapunk, amire a 2.4 Tétel igaz marad, ezért ugyanazt az algoritmust használhatjuk, mint a felső korlát nélküli feladatnál.

2.5 P (μ = r) becslése

Jelöljük a_{0}, a_{1}, …, a_{n}-nel a 2.3-ban foglalt egyenletrendszer együttható-mátri-xának oszlopait. Ez a mátrix jelenik meg a 2.6 és 2.7 feladatok egyenlőség típusú feltételeiben is. Legyen B egy bázisa ennek a mátrixnak (indexhalmaza: I), továbbá legyen c = e_{r}, az r-edik egységvektor, azaz c_{r} = 1; c_{s} = 0, s = 0, 1, …, r − 1, r + 1, …, n. Mivel a 2.2 Tétel szerint |B| > 0, ezért a duálmegengedettséghez a

| \begin{matrix}c_{p} & c_{B}^{T} \\ a_{p} & B \end{matrix} | p ∈ \{0, 1, …, n\}\I  (2.18)

determináns előjelét kell megvizsgálni.

Ha c_{B} ≠ 0, azaz r ∈ I, akkor 2.18 egyenlő a következővel:

(−1)^{g+1}|(a_{p}, B_{r})|  (2.19)

ahol g az a_{r} előtt álló bázisvektorok számát jelöli (0 ≤ g ≤ m), B_{r} pedig egy (m + 1) × m méretű mátrix, amit B-ből az a_{r} oszlop törlésével nyerünk. A 2.19 abszolút értéke pozitív , mivel |(a_{p}, B_{r})|-ből az oszlopok megfelelő cseréjével a Pascal-mátrix egy minorjához jutunk, mégpedig olyanhoz, amely a 2.2 Tétel szerint pozitív. A következő tétel a duál-megengedett bázisok szerkezetét írja le:

Tétel 2.5 Legyen 0 ≤ r ≤ n. A 2.6-2.7 feladat egy bázisa duál-megengedett pontosan akkor, ha indexhalmaza a következő halmazok egyikével egyezik meg.

Minimalizálás, m+1 páros

• r ∉ I

• {0, i, i+1, …, j, j+1, r−1, r, r+1, k, k+1, …, t, t+1}, ha 2 ≤ r ≤ n−1

• {i, i + 1, …, j, j + 1, r − 1, r, r + 1, k, k + 1, …, t, t + 1, n},

ha 1 ≤ r ≤ n − 2
• {0, 1, i, i + 1, …, j, j + 1}, ha r = 0
• {i, i + 1, …, j, j + 1, n − 1, n}, ha r = n

Minimalizálás, m+1 páratlan

• r ∉ I

• {0, i, i + 1, …, j, j + 1, r − 1, r, r + 1, k, k + 1, …, t, t + 1, n},

ha 2 ≤ r ≤ n − 2

• {i, i+1, …, j, j+1, r−1, r, r+1, k, k+1, …, t, t+1}, ha 1 ≤ r ≤ n−1

• {0, 1, i, i + 1, …, j, j + 1, n}, ha r = 0
• {0, i, i + 1, …, j, j + 1, n − 1, n}, ha r = n

Maximalizálás, m+1 páros

• {i, i + 1, …, j, j + 1, r, k, k + 1, …, t, t + 1, n}, ha 0 ≤ r ≤ n − 1
• {0, i, i + 1, …, j, j + 1, r, k, k + 1, …, t, t + 1}, ha 1 ≤ r ≤ n

Maximalizálás, m+1 páratlan

• {i, i + 1, …, j, j + 1, r, k, k + 1, …, t, t + 1}, ha 0 ≤ r ≤ n

• {0, i, i + 1, …, j, j + 1, r, k, k + 1, …, t, t + 1, n}, ha 1 ≤ r ≤ n − 1

Az indexek növekvő sorrendben állnak.

Ha n > m + 2, akkor minden olyan bázis duál-degenerált, amelyre r ∉ I. Az összes többi esetben duál-nemdegenerált bázist kapunk.

Bizonyítás. Ha a_{r} nincs a bázisban, akkor a 2.18 determináns egyenlő 0-val abban az esetben, ha c_{p} = 0, és egyenlő |B| > 0-val, ha p = r, azaz c_{p} = 1. Tehát a bázis mindenképpen duál-megengedett, és duál-degenerált vagy duálnemdegenerált attól függően, hogy létezik-e olyan nem bázisbeli a_{p}, amire c_{p} = 0, vagy nem létezik, azaz n > m + 2, vagy n = m + 2.

Ha a_{r} benne van a bázisban, akkor—ahogy azt már leírtuk— 2.18 nem lehet egyenlő nullával, tehát a bázis duál-nemdegenerált.

Tegyük fel először, hogy minimalizálunk, m+1 páros, valamint, hogy r ∈ I. Legyen 2 ≤ r ≤ n−1 és g páros. Ekkor B duál-megengedett akkor és csak akkor, ha |(a_{p}, B_{r})| < 0 minden nembázikus a_{p} vektorra. Ebből következik, hogy a_{0} és a_{r−1} benne kell hogy legyen a bázisban, mivel ellenkező esetben a_{p} = a_{0}, illetve a_{p} = a_{r−1} ellentmondásra vezetne. Ezenkívül az a_{0} és a_{r−1} közötti bázisbeli vektorok—ha vannak—egymást követő indexű párok kellenek hogy legyenek, különben találhatnánk olyan nembázikus a_{p} vektort (0 < p < r − 1), hogy |(a_{p}, B_{r})| > 0 lenne. Hasonlóképpen belátható, hogy a_{r+1}-nek benne kell lennie a bázisban, és az (r + 1)-nél nagyobb indexű bázisvektoroknak párokat kell alkotniuk. Így megkaptuk az második struktúrát az első csoportból.

Most tegyük fel, hogy 1 ≤ r ≤ n − 2, és g páratlan. Ekkor a duálmegengedettséghez |(a_{p}, B_{r})| > 0 kell hogy legyen minden nembázikus p-re. Ez azt jelenti, hogy a_{r−1}, a_{r+1} és a_{n} benne kell hogy legyen B-ben, különben ellentmondásra jutnánk. Az összes többi esetleges vektornak párokat kell alkotnia. Ezzel a harmadik struktúrát kaptuk meg az első csoportból.

Az állítás többi része teljesen hasonlóan igazolható □

2.6 P (μ ≥ r) becslése

Most térjünk rá P (μ ≥ r) becslésére. Az a_{0}, a_{1}, …, a_{n}, a B, és az I jelentse ugyanazt, mint az előző részben, c pedig legyen az a vektor, amire c_{i} = 0 (i = 0.1…. , r − 1) és c_{j} = 1 (j = r, r + 1, …, n). Ilyen jelölésekkel a 2.8, illetve 2.9 feladatban B duál-megengedett, ha

| \begin{matrix}c_{p} & c_{B}^{T} \\ a_{p} & B \end{matrix} |  (2.20)

megfelelően nemnegatív, illetve nempozitív ∀p ∈ {0, 1, …, n}\I-re. Ennek vizsgálatához szükség lesz a következő tételre.

Tétel 2.6 Legyen 1 ≤ i_{1} < … < i_{t} < … < i_{m+2} ≤ n, 1 ≤ t ≤ m + 1. Ekkor

(−1)^{t} | \begin{matrix}0 & … & 0 & 1 & … & 1 \\ a_{i_{1}} & … & a_{i_{t}} & a_{i_{t+1}} & … & a_{i_{m+2}} \end{matrix} | > 0  (2.21)

Bizonyítást a 4. fejezetben ennek a tételnek egy általánosabb alakjára adunk (ld. 4.1 Tétel). Most már kimondhatjuk a duál-megengedett bázisokról szóló tételt:

Tétel 2.7 Legyen 1 ≤ r ≤ n. A 2.8-2.9 feladat egy bázisa duál-megengedett pontosan akkor, ha indexhalmaza a következő halmazok egyikével egyezik meg. (Az indexek növekvő sorrendben állnak.)

Minimalizálás, m+1 páros

• I ⊂ {0, 1, …, r − 1}, ha r ≥ m + 1

• {0, i, i + 1, …, j, j + 1, r − 1, k, k + 1, …, t, t + 1}, ha 2 ≤ r ≤ n − 1

• {i, i + 1, …, j, j + 1, r − 1, k, k + 1, …, t, t + 1, n}, ha 1 ≤ r ≤ n

Minimalizálás, m+1 páratlan

• I ⊂ {0, 1, …, r − 1}, ha r ≥ m + 1

• {0, i, i + 1, …, j, j + 1, r − 1, k, k + 1, …, t, t + 1, n}, ha 2 ≤ r ≤ n

• {i, i + 1, …, j, j + 1, r − 1, k, k + 1, …, t, t + 1}, ha 1 ≤ r ≤ n − 1

Maximalizálás, m+1 páros

• I ⊂ {r, r + 1, …, n}, ha n − r ≥ m
• {i, i + 1, …, j, j + 1, r, k, k + 1, …, t, t + 1, n}, ha 1 ≤ r ≤ n − 1
• {0, i, i + 1, …, j, j + 1, r, k, k + 1, …, t, t + 1}, ha 1 ≤ r ≤ n

Maximalizálás, m+1 páratlan

• I ⊂ {r, r + 1, …, n}, ha n − r ≥ m
• {i, i + 1, …, j, j + 1, r, k, k + 1, …, t, t + 1}, ha 1 ≤ r ≤ n

• {0, i, i + 1, …, j, j + 1, r, k, k + 1, …, t, t + 1, n}, ha 1 ≤ r ≤ n − 1

Azok a bázisok, amelyekre I ⊂ {0, 1, …, r − 1} (I ⊂ {r, r + 1, …, n}) duáldegeneráltak a minimalizálási (maximalizálási) problémában, ha r > m + 1 (n − r + 1 > m + 1). A többi esetben a bázisok duál-nemdegeneráltak.

Bizonyítás. Nézzük először a minimalizálást. Ha I ⊂ {0, 1, …, r − 1}, akkor 2.20 vagy nulla, vagy pozitív értékű attól függően, hogy c_{p} = 0, vagy c_{p} = 1. Vagyis mindenképpen duál-megengedett, és duál-degenerált akkor és csak akkor, ha r > m + 1.

Jelölje g ismét az r-nél kisebb indexű bázisvektorok számát. Tegyük fel, hogy m+1 páros. Legyen 2 ≤ r ≤ n − 1 és g páros. Ekkor a_{0} és a_{r−1} benne van a bázisban, különben p = 0 és p = r − 1 esetén a 2.20 determináns a 2.6 Tétel alapján negatív lenne. Ha vannak r-nél kisebb indexű bázisvektorok, akkor azoknak párokat kell alkotniuk, mivel így biztosítható, hogy a (c_{p}, a_{p})^{T} vektort a megfelelő helyre illesztve a 2.21 determinánsban páratlan számú oszlopcserét kelljen végrehajtani. Hasonló okoskodással belátható, hogy az r-nél nagyobb indexű vektoroknak is párokban kell megjelenniük, vagyis megkaptuk a második fajta struktúrát az első csoportból. Ha feltesszük, hogy 1 ≤ r ≤ n és g páratlan, akkor a harmadik fajta struktúrát kapjuk. Ha m+1 páratlan, ugyanígy igazolni lehet az állítást.

Ha maximalizálunk és I ⊂ {r, r + 1, …, n}, akkor 2.20 vagy negatív, vagy nulla attól függően, hogy c_{p} = 0, vagy c_{p} = 1, alkalmazva a 2.6 Tételt. Tehát a duál-megengedettség biztosított, és a duál-degeneráltság akkor lép fel, ha n − r + 1 > m + 1. A többi eset igazolása ugyanúgy megtehető, mint a minimalizálásnál. □

A 2.6-2.7 és a 2.8-2.9 feladatok megoldására a duál-megengedett bázisok ismeretében egyszerű algoritmusokat készíthetünk a duál-módszer megfelelő módosításával. Az egyetlen dolog, amit el kell döntenünk az, hogy egy báziscserénél melyik vektor jöjjön be a bázisba úgy, hogy fenntartsuk a duál-megengedettséget, és elkerüljük a ciklizálást. Ezt esetszétválasztással, és a 2.5 és 2.7 Tétel használatával megtehetjük. (Részletesen ld. [29].) Ezekben a feladatokban is bevezethetünk egyéni felső korlátokat és hasonlóképpen járhatunk el, mint a P (μ ≥ 1) esetében tettük.

Becslések zárt alakban

Az előző fejezetben egy algoritmikus módszert írtunk le, amely a duál-megen-gedett bázisok ismeretében éles becslést szolgáltat a P (μ ≥ 1), P (μ = r) és P (μ ≥ r) valószínűségekre, feltéve, ha ismerjük az S_{1}, …, S_{m} értékeit (m < n). Az algoritmus minden konkrét esetben megadja a legjobb becslést, de előfordulhat, hogy nekünk nem a becslés értéke az érdekes, hanem az, hogy ez miként függ az S_{1}, …, S_{m}-től. Ebben a fejezetben ezt vizsgáljuk, és zárt alakú becsléseket adunk a duál-megengedett bázisok segítségével. Ezek a becslések nem feltétlenül élesek, de azt el tudjuk dönteni, hogy mikor azok. Ahogy azt a 2.3 részben leírtuk, minden duál-megengedett bázis egy (nem feltétlenül éles) becslést szolgáltat. (Az optimális bázishoz tartozó ad éles becslést.) Tehát ahány duálmegengedett bázisunk van, annyi zárt alakú becslést kaphatunk. Ehhez viszont szükségünk van az előforduló bázisok inverzére.

3.1 Mátrixinverzek zárt alakban

Az olyan alakú mátrixok inverzét szeretnénk meghatározni, amilyenek a 2.4-2.9 feladatokban bázisként előfordulhatnak. A 2.4-2.5 illetve a 2.6-2.9 feladatokban más-más alakú az egyenlőség-feltételek mátrixa, ezért ezt a két esetet külön tárgyaljuk. Vizsgáljuk először a 2.4-2.5 feladatokat. Ott egy bázis a következő alakú lehet:

B(I) = ( \begin{matrix}i_{1} & i_{2} & … & i_{m} \\ (\begin{matrix}i_{1} \\ 2 \end{matrix}) & (\begin{matrix}i_{2} \\ 2 \end{matrix}) & … & (\begin{matrix}i_{m} \\ 2 \end{matrix}) \\ ⋮ & ⋮ & & ⋮ \\ (\begin{matrix}i_{1} \\ m \end{matrix}) & (\begin{matrix}i_{2} \\ m \end{matrix}) & … & (\begin{matrix}i_{m} \\ m \end{matrix}) \end{matrix} )  (3.1)

ahol I = {i_{1}, …, i_{m}} a bázisindexek halmaza (1 ≤ i_{1} < 1_{2} < … < i_{m} ≤ n).

Tétel 3.1

det B(I) = \frac{i_{1} ⋯ i_{m}}{2!3! ⋯ m!} ∏_{l<k}(i_{k} − i_{l})

Bizonyítás.

det B(I) = | \begin{matrix}i_{1} & i_{2} & … & i_{m} \\ (\begin{matrix}i_{1} \\ 2 \end{matrix}) & (\begin{matrix}i_{2} \\ 2 \end{matrix}) & … & (\begin{matrix}i_{m} \\ 2 \end{matrix}) \\ ⋮ & ⋮ & & ⋮ \\ (\begin{matrix}i_{1} \\ m \end{matrix}) & (\begin{matrix}i_{2} \\ m \end{matrix}) & … & (\begin{matrix}i_{m} \\ m \end{matrix}) \end{matrix} |

= \frac{i_{1} ⋯ i_{m}}{2!3! ⋯ m!} | \begin{matrix}1 & 1 & … & 1 \\ i_{1}⋮ & ⋮ & & ⋮ \\ i_{1}^{m−1} & i_{2}^{m−1} & … & i_{m}^{m−1} \end{matrix} |

A jobb oldalon álló determináns a jól ismert Vandermonde-determináns, így az állítás következik. □

Az igért, a bázis inverzéről szóló tétel a következő:

Tétel 3.2 Legyen [b_{sp}]_{s=1,...,m}^{p=1,...,m} a B(I) mátrix inverze. Ekkor b_{sp} a következő alakú:

b_{sp} = \frac{(−1)^{p−1}p ∑_{α=1}^{p}(−1)^{α−1} (\begin{matrix}p − 1 \\ α − 1 \end{matrix}) ∏_{u∈I\\{i_{s}\}}(u − α)}{i_{s} ∏_{u∈I\\{i_{s}\}}(u − i_{s})}

Bizonyítás. A következő kombinatorikus azonosságot fogjuk használni:

(−1)^{p} ∑_{α=1}^{p}(−1)^{α} (\begin{matrix}p \\ α \end{matrix}) (\begin{matrix}α \\ i \end{matrix}) = δ_{ip} i ≥ 1, p ≥ 1

ahol δ_{ip} a jól ismert Kronecker-delta. Tehát, ha e_{1}, …, e_{m} az m-dimenziós egységvektorok, akkor

e_{p} = (−1)^{p} ∑_{α=1}^{p}(−1)^{α} (\begin{matrix}p \\ α \end{matrix}) a_{α} p = 1, …, m  (3.2)

ahol a_{α} a 2.4-2.5 probléma egyenlőség-feltételei által meghatározott mátrix egy oszlopa. Legyen B(I, i_{s}, a) az a mátrix, amelyet B(I)-ből kapunk, ha a_{i_{s}}-et kicseréljük a-ra. A 3.2 alapján:

det B(I, i_{s}, e_{p}) = (−1)^{p} ∑_{α=1}^{p}(−1)^{α} (\begin{matrix}p \\ α \end{matrix}) det B(I, i_{s}, a_{α})  (3.3)

Mivel

b_{sp} = \frac{det B(I, i_{s}, e_{p})}{det B(I)}  (3.4)

ezért csak a következő törtet kell kifejtenünk:

\frac{det B(I, i_{s}, a_{α})}{det B(I)}

A nevezőre alkalmazhatjuk a 3.1 Tételt, és bár ugyanez közvetlenül nem alkalmazható a számlálóra, mivel B(I, i_{s}, a_{α}) oszlopai nem az indexeik növekvő sorrendjében állnak, a Vandermonde-determinánsról szóló azonosság ebben a helyzetben is fennáll, azaz

\frac{det B(I, i_{s}, a_{α})}{det B(I)} = \frac{α}{i_{s}} \frac{∏_{u∈I\\{i_{s}\}}(u − α)}{∏_{u∈I\\{i_{s}\}}(u − i_{s})}  (3.5)

Ha behelyettesítjük 3.5-öt a 3.3-ba, akkor figyelembe véve 3.4-et a tétel állítását kapjuk. □

Most nézzük a 2.6-2.9 feladatokat. Ezekben egy bázis a következő alakú lehet:

B(I) = ( \begin{matrix}1 & 1 & … & 1 \\ i_{0} & i_{1} & … & i_{m} \\ (\begin{matrix}i_{0} \\ 2 \end{matrix}) & (\begin{matrix}i_{1} \\ 2 \end{matrix}) & … & (\begin{matrix}i_{m} \\ 2 \end{matrix}) \\ ⋮ & ⋮ & & ⋮ \\ (\begin{matrix}i_{0} \\ m \end{matrix}) & (\begin{matrix}i_{1} \\ m \end{matrix}) & … & (\begin{matrix}i_{m} \\ m \end{matrix}) \end{matrix} )  (3.6)

ahol I = {i_{0}, i_{1}, …, i_{m}} a bázisindexek halmaza (0 ≤ i_{0} < i_{1} < i_{2} < … < i_{m} ≤ n). A 2.2 Tétel azt állítja, hogy ennek a bázisnak a determinánsa pozitív. A bázis inverzét a következő tétel adja meg.

Tétel 3.3 Legyen [b_{sp}]_{s=0,...,m}^{p=0,...,m} a 3.6 mátrix inverze. Ekkor b_{sp} a következő alakú:

b_{sp} = \frac{(−1)^{p} ∑_{α=0}^{p}(−1)^{α} (\begin{matrix}p \\ α \end{matrix}) ∏_{u∈I\\{i_{s}\}}(u − α)}{∏_{u∈I\\{i_{s}\}}(u − i_{s})}  (3.7)

Bizonyítás. Bevezetve a

B(I + 1) = ( \begin{matrix}i_{0} + 1 & … & i_{m} + 1 \\ (\begin{matrix}i_{0} + 1 \\ 2 \end{matrix}) & … & (\begin{matrix}i_{m} + 1 \\ 2 \end{matrix}) \\ ⋮ & & ⋮ \\ (\begin{matrix}i_{0} + 1 \\ m + 1 \end{matrix}) & … & (\begin{matrix}i_{m} + 1 \\ m + 1 \end{matrix}) \end{matrix} )

mátrixot a következő egyenlőség teljesül:

B(I)^{−1} = ( \begin{matrix}i_{0} + 1 \\ & i_{1} + 1 \\ & & . & . & . \\ & & & & & i_{m} + 1 \end{matrix} ) B(I + 1)^{−1} ( 1 ; \frac{1}{2} ; ... ; \frac{1}{m+1} )

Legyenek c_{sp} (s = 0, 1, …, m, p = 0, 1, …, m) a B(I + 1)^{−1} mátrix elemei. A 3.2 Tétel alapján

c_{sp} = \frac{(−1)^{p}(p + 1) ∑_{α=0}^{p}(−1)^{α} (\begin{matrix}p \\ α \end{matrix}) ∏_{u∈I\\{i_{s}\}}(u − α)}{(i_{s} + 1) ∏_{u∈I\\{i_{s}\}}(u − i_{s})}

Mivel b_{sp} = (i_{s} + 1)c_{sp} \frac{1}{p+1}, a tétel bizonyított. □

A következő részben bevezetjük a véges differencia fogalmát, amellyel egyszerűsíthetjük a fenti bonyolult jelöléseket.

3.2 Véges differenciák

Legyen f(i_{1}, …, i_{m}) valós értékű, m változós, az R^{m} tér (i_{1}, …, i_{m}) alakú rácspontjain értelmezett függvény.

Definíció 3.1 Az f függvény első-, illetve p-edrendű (p=2,3,…) véges differenciája a következő:

∇f(i_{1}, …, i_{m}) = f(i_{1}, …, i_{m}) − f(i_{1} − 1, …, i_{m} − 1)
∇^{p}f(i_{1}, …, i_{m}) = ∇ [∇^{p−1}f(i_{1}, …, i_{m})]

Terjesszük ki a definíciót p = 0 esetére: ∇^{0}f(i_{1}, …, i_{m}) = f(i_{1}, …, i_{m}). Könnyen igazolható p szerinti indukcióval, hogy:

∇^{p}f(i_{1}, …, i_{m}) = ∑_{α=0}^{p}(−1)^{α} (\begin{matrix}p \\ α \end{matrix}) f(i_{1} − α, …, i_{m} − α)  (3.8)

Ha f(i_{1}, …, i_{m}) = f_{1}(i_{1}) ⋯ f_{m}(i_{m}) alakú, akkor további formulák nyerhetők: Ha m = 2, akkor p szerinti indukcióval:

∇^{p}f_{1}(i_{1})f_{2}(i_{2}) = ∑_{α=0}^{p} (\begin{matrix}p \\ α \end{matrix}) ∇^{α}f_{1}(i_{1})∇^{p−α}f_{2}(i_{2} − α)

Az m szerinti indukcióval, pedig:

∇^{p} (∏_{j=1}^{m} f_{j}(i_{j})) = ∑_{\begin{matrix}α_{1}+α_{2}+···+α_{m}=p \\ α_{i}≥0,egész \\ i=1,...,m \end{matrix}} \frac{p! ∏_{s=1}^{m} ∇^{α_{s}}f_{s} (i_{s} − ∑_{t=1}^{s−1} α_{t})}{α_{1}!α_{2}! ⋯ α_{m}!} (3.9)

Alkalmazzuk a 3.9 képletet f_{1}(i_{1}) = i_{1}, f_{2}(i_{2}) = i_{2}, …, f_{m}(i_{m}) = i_{m} esetére. Ekkor α_{1}, …, α_{m} értékét 0-ra és 1-re korlátozhatjuk, mivel ∇^{p}i = 0, ha p ≥ 2.

Ha j_{1} < j_{2} < … < j_{m−p} jelöli azokat az indexeket, amelyekre α_{1}, …, α_{m} értéke 0, akkor

∇^{α_{1}}f_{1}(i_{1})∇^{α_{2}}f_{2}(i_{2} − α_{1}) … ∇^{α_{m}}f_{m}(i_{m} − α_{1} − … − α_{m−1}) =
[i_{j_{1}} − (j_{1} − 1)][i_{j_{2}} − (j_{2} − 2)] ⋯ [i_{j_{m−p}} − (j_{m−p} − m + p)]

És így

∇^{p}i_{1}i_{2} … i_{m} = p! ∑_{1≤j_{1}<j_{2}<...<j_{m−p}≤m} ∏_{k=1}^{m−p}(i_{j_{k}} − j_{k} + k)  (3.10)

A véges differenciákat használva a 3.8 alapján 3.7-et így is írhatjuk:

b_{sp} = \frac{(−1)^{p}∇^{p} ∏_{u∈I\\{i_{s}\}} u}{∏_{u∈I\\{i_{s}\}}(u − i_{s})}  (3.11)

3.3 Zárt alakú becslések P (μ ≥ 1)-re

Legyen B egy bázis a 2.4-2.5 feladatban. Ekkor B-nek olyan alakja van, mint amilyen a 3.1 alatti mátrixnak. A hozzá tartozó duálvektor c_{B}^{T}B^{−1}, ahol c_{B}^{T} = (1, 1, …, 1).

Tétel 3.4 Legyen I = {i_{1}, …, i_{m}}. A B(I) bázishoz tartozó duálvektor komponensei a következők:

(c_{B}^{T}B^{−1})_{p} = (−1)^{p} \frac{∇^{p}i_{1}i_{2} ⋯ i_{m}}{i_{1}i_{2} ⋯ i_{m}}

ahol p = 1, 2, …, m.

Bizonyítás. Vezessük be a következő mátrixot:

B̂ = ( \begin{matrix}1 & i_{1} + 1 & i_{2} + 1 & … & i_{m} + 1 \\ 0 & (\begin{matrix}i_{1} + 1 \\ 2 \end{matrix}) & (\begin{matrix}i_{2} + 1 \\ 2 \end{matrix}) & … & (\begin{matrix}i_{m} + 1 \\ 2 \end{matrix}) \\ ⋮ & ⋮ & ⋮ & & ⋮ \\ 0 & (\begin{matrix}i_{1} + 1 \\ m + 1 \end{matrix}) & (\begin{matrix}i_{2} + 1 \\ m \end{matrix}) & … & (\begin{matrix}i_{m} + 1 \\ m + 1 \end{matrix}) \end{matrix} )

Nyilván teljesül az alábbi összefüggés:

B̂ = ( 1 ; \frac{1}{2} ; ... ; \frac{1}{m+1} ) ( \begin{matrix}1 & 1 & … & 1 \\ 0 & i_{1} & … & i_{m} \\ ⋮ & ⋮ & & ⋮ \\ 0 & (\begin{matrix}i_{1} \\ m \end{matrix}) & … & (\begin{matrix}i_{m} \\ m \end{matrix}) \end{matrix} )

× ( \begin{matrix}1 \\ & i_{1} + 1 \\ & & . & . & . \\ & & & & & i_{m} + 1 \end{matrix} )

A jobb oldalon, középen álló mátrix nem más, mint

( \begin{matrix}1 & c_{B}^{T} \\ 0 & B \end{matrix} )  (3.12)

Ezért

( \begin{matrix}1 & −c_{B}^{T}B^{−1} \\ 0 & B^{−1} \end{matrix} ) = ( \begin{matrix}1 & c_{B}^{T} \\ 0 & B \end{matrix} )^{−1}

= ( \begin{matrix}1 \\ & i_{1} + 1 \\ & & . & . & . \\ & & & & & i_{m} + 1 \end{matrix} ) B̂^{−1} ( 1 ; \frac{1}{2} ; ... ; \frac{1}{m+1} )

A B̂ inverzét a 3.2 Tétel adja meg, I = {1, i_{1} + 1, …, i_{m} + 1} választással. Nekünk csak az első sorra van szükségünk:

c_{1p} = (−1)^{p−1}p ∑_{α=1}^{p}(−1)^{α−1} (\begin{matrix}p − 1 \\ α − 1 \end{matrix}) \frac{(i_{1} + 1 − α) ⋯ (i_{m} + 1 − α)}{i_{1}i_{2} ⋯ i_{m}}

p = 1, 2, …, m. Mivel

−c_{B}^{T}B^{−1} = (\frac{c_{12}}{2} , …, \frac{c_{1m+1}}{m + 1})

ezért

(c_{B}^{T}B^{−1})_{p} = (−1)^{p−1} ∑_{α=0}^{p}(−1)^{α} (\begin{matrix}p \\ α \end{matrix}) \frac{(i_{1} − α) ⋯ (i_{m} − α)}{i_{1}i_{2} ⋯ i_{m}}

= (−1)^{p−1} \frac{∇^{p}i_{1}i_{2} ⋯ i_{m}}{i_{1}i_{2} ⋯ i_{m}}

p = 1, 2, …, m-re. □

Legyen b = (S_{1}, …, S_{m}). Ekkor a 2.3 részben leírtak alapján

c_{B}^{T}B^{−1}b ≤ P (μ ≥ 1)  (3.13)

a minimalizálás, illetve

c_{B}^{T}B^{−1}b ≥ P (μ ≥ 1)  (3.14)

a maximalizálás esetén, ha B duál-megengedett. Figyelembevéve a duál-megen-gedett bázisok szerkezetéről szóló 2.4 Tételt, kimondhatjuk a következő állítást.

Tétel 3.5 Legyen f(i_{1}, …, i_{m}) = i_{1}i_{2} ⋯ i_{m}

(a) Ha m páros, és (i, i + 1, …, t, t + 1) m darab 1 és n közötti különböző egész szám növekvő sorrendben, akkor

P (μ ≥ 1) ≥ ∑_{p=1}^{m}(−1)^{p−1} \frac{∇^{p}f(i, i + 1, …, t, t + 1)}{f(i, i + 1, …, t, t + 1)}S_{p}

és az egyenlőtlenség éles, ha {a_{i}, a_{i+1}, …, a_{t}, a_{t+1}} primál-megengedett bázis a 2.4 feladatban.

(b) Ha m páros, és (i, i+1, …, t, t+1) m-2 darab 2 és (n-1) közötti különböző egész szám növekvő sorrendben, akkor

P (μ ≥ 1) ≤ ∑_{p=1}^{m}(−1)^{p−1} \frac{∇^{p}f(1, i, i + 1, …, t, t + 1, n)}{f(1, i, i + 1, …, t, t + 1, n)}S_{p}

és az egyenlőtlenség éles, ha {a_{1}, a_{i}, a_{i+1}, …, a_{t}, a_{t+1}, a_{n}} primál-megengedett bázis a 2.5 feladatban.

(c) Ha m páratlan, és (i, i + 1, …, t, t + 1) m-1 darab 1 és (n-1) közötti különböző egész szám növekvő sorrendben, akkor

P (μ ≥ 1) ≥ ∑_{p=1}^{m}(−1)^{p−1} \frac{∇^{p}f(i, i + 1, …, t, t + 1, n)}{f(i, i + 1, …, t, t + 1, n)}S_{p}

és az egyenlőtlenség éles, ha {a_{i}, a_{i+1}, …, a_{t}, a_{t+1}, a_{n}} primál-megengedett bázis a 2.4 feladatban.

(d) Ha m páratlan, és (i, i+1, …, t, t+1) m-1 darab 2 és n közötti különböző egész szám növekvő sorrendben, akkor

P (μ ≥ 1) ≤ ∑_{p=1}^{m}(−1)^{p−1} \frac{∇^{p}f(1, i, i + 1, …, t, t + 1)}{f(1, i, i + 1, …, t, t + 1)}S_{p}

és az egyenlőtlenség éles, ha {a_{1}, a_{i}, a_{i+1}, …, a_{t}, a_{t+1}} primál-megengedett bázis a 2.5 feladatban.

Ennek a tételnek az alkalmazásával levezetünk néhány konkrét zárt alakú alsó és felső becslést. Legyen először m = 2. Könnyen ellenőrizhető, hogy

\begin{aligned}∇i_{1}i_{2} & = & i_{1} + i_{2} − 1 \\ ∇^{2}i_{1}i_{2} & = & 2 \end{aligned}  (3.15)

A 2.4 Tétel szerint minden duál-megengedett bázis {i, i+1} (1 ≤ i ≤ n−1) alakú a minimalizálás esetén, tehát a 3.5 tételt,és 3.15-öt alkalmazva i_{1} = i, i_{2} = i+1re az alábbi alsó korlátot kapjuk:

P (μ ≥ 1) ≥ \frac{2}{i + 1}S_{1} − \frac{2}{i(i + 1)}S_{2}  (3.16)

Ez az egyenlőtlenség éles, ha a_{i}, a_{i+1} megengedett bázis a 2.4 feladatban, azaz az

\begin{aligned}iv_{i} + (i + 1)v_{i+1} & = & S_{1} \\ (\begin{matrix}i \\ 2 \end{matrix}) v_{i} + (\begin{matrix}i + 1 \\ 2 \end{matrix}) v_{i+1} & = & S_{2} \end{aligned}  (3.17)

egyenletrendszer megoldása nemnegatív:

v_{i} = S_{1} − \frac{2}{i}S_{2} ≥ 0
v_{i+1} = −\frac{i − 1}{i + 1}S_{1} + \frac{2}{i + 1}S_{2} ≥ 0

Ezzel ekvivalens a következő:

iS_{1} − 2S_{2} ≥ 0
(i − 1)S_{1} − 2S_{2} ≤ 0

Mivel (n − 1)S_{1} − 2S_{2} ≥ 0 mindig teljesül, ebből S_{1} > 0-t feltéve, i-re az alábbi összefüggést kapjuk:

i − 1 = ⌊\frac{2S_{2}}{S_{1}} ⌋  (3.18)

Ha maximalizálunk, akkor csak az {a_{1}, a_{n}} lehet duál-megengedett bázis, tehát ismét a 3.5 Tételt és 3.15-öt alkalmazva (i_{1} = 1, i_{2} = n):

P (μ ≥ 1) ≤ S_{1} − \frac{2}{n}S_{2}

Ez az egyenlőtlenség éles is, mert {a_{1}, a_{n}} primál-megengedett. Ez könnyen ki is számolható, de abból a tényből is következik, hogy a 2.5 feladatnak van megengedett megoldása és véges optimuma, akkor pedig létezik legalább egy primál-duál megengedett bázisa is.

Legyen most m = 3. Ekkor a 3.8, vagy a 3.10 képletet használva:

\begin{aligned}∇i_{1}i_{2}i_{3} & = & i_{1}i_{2} + i_{1}i_{3} + i_{2}i_{3} − i_{1} − i_{2} − i_{3} + 1 \\ ∇^{2}i_{1}i_{2}i_{3} & = & 2i_{1} + 2i_{2} + 2i_{3} − 6 \\ ∇^{3}i_{1}i_{2}i_{3} & = & 6 \end{aligned}  (3.19)

A 2.4 feladat duál-megengedett bázisai a 2.4 Tétel szerint {i, i + 1, n} alakúak (1 ≤ i ≤ n − 2). A 3.5 Tételt és 3.19-et alkalmazva (i_{1} = i, i_{2} = i + 1, i_{3} = n) kapjuk:

P (μ ≥ 1) ≥ \frac{i + 2n − 1}{(i + 1)n}S_{1} − \frac{2(2i + n − 2)}{i(i + 1)n}S_{2} + \frac{6}{i(i + 1)n}S_{3}  (3.20)

amely egyenlőtlenség éles, ha {a_{i}, a_{i+1}, a_{n}} primál-megengedett bázis a 2.4 feladatban. Ez teljesül, ha i-t a következőképpen választjuk meg:

i = 1 + ⌊\frac{2((n − 2)S_{2} − 3S_{3})}{(n − 1)S_{1} − 2S_{2}}⌋

(Ezt hasonlóképpen lehet levezetni, mint a 3.18-at.) Megjegyezendő, hogy (n − 1)S_{1} − 2S_{2} ≥ 0 mindig teljesül, és egyenlőség akkor és csak akkor áll, ha a 2.4 feladat minden v megengedett megoldásra: v_{1} = v_{2} = ⋯ = v_{n−1} = 0, vagyis az A_{1}, …, A_{n} események 1 valószínűséggel megegyeznek. Ebben az esetben 3.20 teljesül minden i-re, és a P (μ ≥ 1) ≥ P (A_{i}) alakra redukálódik.

A 2.5 feladat duál-megengedett bázisai {1, i, i + 1} alakúak, tehát

P (μ ≥ 1) ≤ S_{1} − \frac{2(2i − 1)}{i(i + 1)}S_{2} + \frac{6}{i(i + 1)}S_{3}  (3.21)

és ez éles, ha

i = 2 + ⌊\frac{3S_{3}}{S_{2}} ⌋

Ha S_{2} = 0, akkor S_{3} = 0, és akkor 3.21 egyenlőséggel teljesül.

Az m = 4 esetre zárt alakú alsó, és felső becsléseket talál az érdeklődő a [6]-ban, vagy [30]-ban.

Végül megemlítjük, hogy a 3.5 Tétel következményeként az eredeti Bonferroni-egyenlőtlenségek is kiadódnak. Valóban, a B = (a_{1}, a_{2}, …, a_{m}) duálmegengedett bázis a 2.4, vagy a 2.5 feladatban, attól függően, hogy m páros, vagy páratlan. Mivel

B^{−1} = ( \begin{matrix}1 & 2 & 3 & … & m \\ 0 & 1 & (\begin{matrix}3 \\ 2 \end{matrix}) & … & (\begin{matrix}m \\ 2 \end{matrix}) \\ ⋮ & ⋮ & ⋮ & & ⋮ \\ 0 & 0 & 0 & … & 1 \end{matrix} )^{−1}

= ( \begin{matrix}1 & −2 & 3 & … & (−1)^{m−1}m \\ 0 & 1 & − (\begin{matrix}3 \\ 2 \end{matrix}) & … & (−1)^{m−2} (\begin{matrix}m \\ 2 \end{matrix}) \\ ⋮ & ⋮ & ⋮ & & ⋮ \\ 0 & 0 & 0 & … & 1 \end{matrix} )

és c_{B}^{T} minden komponense egyenlő 1-gyel, ezért c_{B}^{T}B^{−1}b = S_{1} − S_{2} + ⋯ + +(−1)^{m−1}S_{m}, azaz

P (μ ≥ 1) ≥ S_{1} − S_{2} + ⋯ + (−1)^{m−1}S_{m} ha m páros
P (μ ≥ 1) ≤ S_{1} − S_{2} + ⋯ + (−1)^{m−1}S_{m} ha m páratlan

3.4 Zárt alakú becslések P (μ = r)-re, valamint P (μ ≥ r)-re

Teljesen hasonlóan, mint az előző részben belátható a következő két tétel.

Tétel 3.6 Legyen I valamelyik a 2.5 Tételben leírt bázisszerkezetek közül a minimalizálás (maximalizálás) esetén. Ekkor a

∑_{p=0}^{m} \frac{(−1)^{p}∇^{p} ∏_{u∈I\\{i_{s}\}} u}{∏_{u∈I\\{i_{s}\}}(u − i_{s})}S_{p}  (3.22)

összeg alsó (felső) korlátja P (μ = r)-nek. Ez a becslés éles, ha I egyben egy a 2.6-2.7 feladatokban primál-megengedett bázis indexhalmaza is.

Tétel 3.7 Legyen I valamelyik a 2.7 Tételben leírt bázisszerkezetek közül a minimalizálás (maximalizálás) esetén. Jelölje b_{sp} ugyanazt, mint a 3.7-ban. Ekkor

∑_{p=0}^{m} S_{p} ∑_{s≥r} b_{sp} = ∑_{s≥r} ∑_{p=0}^{m} b_{sp}S_{p}

alsó (felső) korlátja P (μ ≥ r)-nek. Ha továbbá I egy a 2.8-2.9 feladatokban primál-megengedett bázis indexhalmaza is, akkor ez a becslés éles.

P (μ ≥ r)-re zárt alakú becslések m = 2 és m = 3 esetére [6]-ban találhatók.

A diszkrét momentum-probléma

Ebben a fejezetben az eddigiek általánosítását tárgyaljuk. Eddig azt csináltuk, hogy egy valószínűségi eloszláson értelmezett speciális függvényekre adtunk alsó és felső korlátokat, ismerve néhány binomiális momentum értékét. A következőkben nem szorítkozunk a binomiális momentumokra, hanem a hatványmomentumokat is használjuk, ezenkívül a célfüggvényeket is szélesebb körből választjuk.

Legyen ξ egy diszkrét valószínűségi változó, amely az értékeit az előre adott z_{0} < z_{1} < … < z_{n} számokon veszi fel. Legyen p_{i} = P (ξ = z_{i}) (i = 0, 1, …, n). Tegyük fel, hogy nem ismerjük a p_{i}-k értékét, de ismerjük vagy az első m hatványmomentumot: μ_{k} = E(ξ^{k}), k = 1, …, m, vagy az első m binomiális

momentumot: S_{k} = E [(\begin{matrix}ξ \\ k \end{matrix})] k = 1, …, m, ahol m < n. A célunk az,

hogy minimalizáljuk, vagy maximalizáljuk p_{i}-k egy lineáris függvényét a momentumfeltételek mellett. Vagyis a következő lineáris programozási feladatok megoldásra vagyunk kiváncsiak:

min ill. max {f_{0}p_{0} + ⋯ + f_{n}p_{n}}
felt., hogy p_{0} + ⋯ + p_{n} = 1
z_{0}p_{0} + ⋯ + z_{n}p_{n} = μ_{1}
z_{0}^{2}p_{0} + ⋯ + z_{n}^{2}p_{n} = μ_{2}
⋮
z_{0}^{m}p_{0} + ⋯ + z_{n}^{m}p_{n} = μ_{m}
p_{0} ≥ 0, …, p_{n} ≥ 0

(4.1)

min ill. max {f_{0}p_{0} + ⋯ + f_{n}p_{n}}
felt., hogy p_{0} + ⋯ + p_{n} = 1

z_{0}p_{0} + ⋯ + z_{n}p_{n} = S_{1}

(\begin{matrix}z_{0} \\ 2 \end{matrix}) p_{0} + ⋯ + (\begin{matrix}z_{n} \\ 2 \end{matrix}) p_{n} = S_{2}

⋮

(\begin{matrix}z_{0} \\ m \end{matrix}) p_{0} + ⋯ + (\begin{matrix}z_{n} \\ m \end{matrix}) p_{n} = S_{m}

p_{0} ≥ 0, …, p_{n} ≥ 0

(4.2)

A 4.1, illetve 4.2 problémát hatvány-, illetve binomiális momentum problémának fogjuk nevezni.

Ezek a problémák a diszkrét momentum problémák körébe tartoznak azzal a plusz feltétellel, hogy itt a valószínűségi változó egy speciális, előre adott véges halmazra koncentrálódik. Az ilyen esetekben a klasszikus Csebisev-Markov egyenlőtlenségek nem adnak jó becsléseket a megoldásra. A gyakorlatban pedig gyakran előfordulnak ilyen valószínűségi változók, például a 2. fejezetben definiált μ is ilyen, amely mivel n db. esemény közül a bekövetkezők számát jelöli, csak a 0, 1, …, n számokat veheti fel. De ilyen diszkrét eloszlásra jutunk akkor is, ha olyan valószínűségi változóra vonatkozó momentum problémára akarunk közelítő megoldást adni, amely a valós számegyenes egy véges intervallumán értelmezett, de nincs megkötve, hogy diszkrét-e, vagy nem. Ugyanis minden ilyen valószínűségi változót tetszőlegesen megközelíthetünk diszkrét valószínűségi változókkal, amelyek az intervallum egy megfelelően sűrű véges részhalmazán veszik fel az értéküket. (A momentum problémákról és a Csebisev-Markov egyenlőtlenségekről bővebben ld. [30])

A 4.1 illetve 4.2 lineáris programozási feladat egyenlőség feltételeinek mátrixát jelöljük A-val. Ennek az oszlopai legyenek: a_{0}, a_{1}, …, a_{n}, a feltételek jobb oldalán álló vektort pedig jelölje b. Azaz a hatványmomentum probléma esetén:

a_{i} = ( 1 ; z_{i} ; ⋮ ; z_{i}^{m} ) i = 0, 1, …, n; b = ( 1 ; μ_{1} ; ⋮ ; μ_{m} )  (4.3)

és a binomiális momentumok esetén:

a_{i} = ( 1 ; z_{i} ; ⋮ ; (\begin{matrix}z_{i} \\ m \end{matrix}) ) i = 0, 1, …, n; b = ( 1 ; S_{1} ; ⋮ ; S_{m} )  (4.4)

A kétfajta momentum probléma egymásba alakítható a Stirling-számok alkalmazásával. Jelöljük s(l, k)-val, illetve S(l, k)-val az elsőfajú és másodfajú Stirling-számokat, amelyek a következő egyenletekkel vannak definiálva:

\begin{aligned}(z)_{l} & = & ∑_{k=0}^{l} s(l, k)z^{k} \\ z^{l} & = & ∑_{k=0}^{l} S(l, k)(z)_{k} \end{aligned}  (4.5)

ahol (z)_{0} = 1, (z)_{k} = z(z − 1)(z − 2) ⋯ (z − k + 1), k = 1, 2, …-ra. (A Stirlingszámokra zárt alakú képletet ld. például [33]-ban.) Legyen s_{lk} = s(l, k)/l!, és S_{lk} = S(l, k)k!. Ekkor 4.5-ből következik, hogy ha megszorozzuk a 4.3 vektorokat balról a

T_{1} = ( \begin{matrix}s_{00} \\ s_{10} & s_{11} \\ s_{20} & s_{21} & s_{22} \\ ⋮ & & & ... \\ s_{m0} & s_{m1} & s_{m2} & … & s_{mm} \end{matrix} )

mátrixszal, akkor a 4.4 vektorokat kapjuk, és ha a 4.4 vektorokat megszorozzuk balról a

T_{2} = ( \begin{matrix}S_{00} \\ S_{10} & S_{11} \\ S_{20} & S_{21} & S_{22} \\ ⋮ & & & ... \\ S_{m0} & S_{m1} & S_{m2} & … & S_{mm} \end{matrix} )

mátrixszal, akkor a 4.3 vektorokat kapjuk. Továbbá az is igaz, hogy T_{2} = T_{1}^{−1}.

Néha az f-et kiterjesztjük a [z_{0}, z_{n}] intervallum összes pontjára, ezért vezessük be az f(z_{k}) jelölést, jelentse ez ugyanazt, mint az f_{k}. Az f-et a következő speciális esetekben vizsgáljuk részletesen.

(1) Az f függvény (m+1)-ed rendű differencia-hányadosai a {z_{0}, …, z_{n}} halmazon (a definíciót ld. a következő részben) legyenek mind pozitívak. Ez teljesül például, ha f a [z_{0}, z_{n}]-en értelmezett, és f^{(m+1)}(z) > 0 az intervallum minden z belső pontjában. Ekkor a 4.1 és 4.2 feladatok optimumai éles alsó, illetve felső becslések E[f(ξ)]-re.

(2) f_{r} = 1; f_{i} = 0 ha i ≠ r valamilyen 0 ≤ r ≤ n-re. Ekkor az optimumok P (ξ = z_{r})-re adnak becslést.

(3) f_{0} = ⋯ = f_{r−1} = 0; f_{r} = ⋯ = f_{n} = 1 valamilyen 1 ≤ r ≤ n-re. Ekkor P (ξ ≥ z_{r})-re kapunk becslést.

Látható, hogy a (2) és (3) esetek a 2. fejezetben leírtak közvetlen általánosításai.

4.1 Differencia-hányadosok és duál-megengedett bázisok

Definíció 4.1 Legyen f a z_{0} < z_{1} < … < z_{n} véges halmazon értelmezett függvény. Az f függvény elsőrendű differencia-hányadosai a következők:

[z_{i_{1}}, z_{i_{2}}]f = \frac{f(z_{i_{2}}) − f(z_{i_{1}})}{z_{i_{2}} − z_{i_{1}}} 0 ≤ i_{1} < i_{2} ≤ n

A k-adrendű, vagy k-adik differencia-hányadosai pedig (k ≥ 2):

[z_{i_{1}}, …, z_{i_{k+1}}]f = \frac{[z_{i_{2}}, …, z_{i_{k+1}}]f − [z_{i_{1}}, …, z_{i_{k}}]f}{z_{i_{k+1}} − z_{i_{1}}} 0 ≤ i_{1} < … < i_{k+1} ≤ n

Megjegyzés. Az f függvényt k-ad rendben konvexnek mondjuk, ha mindegyik k-ad rendű differencia-hányadosa pozitív. Az, hogy f első rendben konvex, ekvivalens azzal, hogy növekvő, az pedig, hogy másodrendben konvex azt jelenti, hogy

f(z_{j}) < \frac{z_{k} − z_{j}}{z_{k} − z_{i}} f(z_{i}) − \frac{z_{j} − z_{i}}{z_{k} − z_{i}} f(z_{k})

minden 0 ≤ i < j < k ≤ n ponthármasra, amit röviden úgy fogunk hívni, hogy a függvény konvex.

Ismert (ld. például [18]) a következő azonosság:

[z_{i_{1}}, …, z_{i_{k+1}}]f = \begin{matrix}| & \begin{matrix}1 & 1 & … & 1 \\ z_{i_{1}} & z_{i_{2}} & … & z_{i_{k+1}} \\ ⋮ & ⋮ & & ⋮ \\ z_{i_{1}}^{k−1} & z_{i_{2}}^{k−1} & … & z_{i_{k+1}}^{k−1} \\ f(z_{i_{1}}) & f(z_{i_{2}}) & … & f(z_{i_{k+1}}) \end{matrix} & | \\ | & \begin{matrix}1 & 1 & … & 1 \\ z_{i_{1}} & z_{i_{2}} & … & z_{i_{k+1}} \\ ⋮ & ⋮ & & ⋮ \\ z_{i_{1}}^{k−1} & z_{i_{2}}^{k−1} & … & z_{i_{k+1}}^{k−1} \\ z_{i_{1}}^{k} & z_{i_{2}}^{k} & … & z_{i_{k+1}}^{k} \end{matrix} & | \end{matrix}  (4.6)

A nevező egy Vandermonde-determináns, amely pozitív, ha 0 ≤ i_{1} < i_{2} < … < i_{k+1} ≤ n, tehát ebben az esetben a [z_{i_{1}}, …, z_{i_{k+1}}]f előjele a számláló előjelétől függ. Az is látszik 4.6-ból, hogy z_{i_{1}}, …, z_{i_{k+1}} sorrendje nem számít: ha felcseréljük őket, a számlálóban, és a nevezőben ugyanazokat az oszlopcseréket kell végrehajtani, tehát a hányados nem változik. Ezért [z_{i_{1}}, …, z_{i_{k+1}}]f helyett írhatunk [z_{i}, i ∈ I]f-et is, ha I = {i_{1}, …, i_{k+1}}.

Megjegyzés. Be lehet látni, hogy ha f összes, egymást követő pontokon értelmezett (k+1)-edik differencia-hányadosa pozitív, akkor az összes (k+1)- edik differencia-hányadosa is pozitív (ld. például [28]).

Szükségünk lesz a következő tételre.

Tétel 4.1 Legyen 1 ≤ i_{1} < … < i_{t} < … < i_{m+2} ≤ n, 1 ≤ t ≤ m + 1. Ekkor

(−1)^{t} | \begin{matrix}0 & … & 0 & 1 & … & 1 \\ a_{i_{1}} & … & a_{i_{t}} & a_{i_{t+1}} & … & a_{i_{m+2}} \end{matrix} | > 0

ahol az a_{i_{1}}, …, a_{i_{m+2}} vektorok 4.3, vagy 4.4 alakúak.

Bizonyítás. Nézzük először a 4.3 alakú vektorokat. A Vandermonde-determi-nánsra igaz a következő azonosság:

| \begin{matrix}1 & 1 & … & 1 \\ v_{0} & v_{1} & … & v_{m} \\ ⋮ & ⋮ & & ⋮ \\ v_{0}^{m} & v_{1}^{m} & … & v_{m}^{m} \end{matrix} | = | \begin{matrix}v_{1} − v_{0} & … & v_{m} − v_{m−1} \\ ⋮ & & ⋮ \\ v_{1}^{m} − v_{0}^{m} & … & v_{m}^{m} − v_{m−1}^{m} \end{matrix} |  (4.7)

Tehát ha v_{0} < v_{1} < … < v_{m}, akkor a jobb oldalon álló determináns pozitív. Egyszerűen belátható, hogy

(−1)^{t} | \begin{matrix}0 & … & 0 & 1 & … & 1 \\ a_{i_{1}} & … & a_{i_{t}} & a_{i_{t+1}} & … & a_{i_{m+2}} \end{matrix} |

= | a_{i_{1}}, a_{i_{2}} − a_{i_{1}}, …, a_{i_{t}} − a_{i_{t−1}}, a_{i_{t+2}} − a_{i_{t+1}}, …, a_{i_{m+2}} − a_{i_{m+1}} |

Az első sor első eleme 1, a többi 0, tehát a determinánst kifejtve az első sora szerint egy 4.7 alakú determinánst kapunk, amely pozitív.

A 4.4 alakú vektorokra abból következik az állítás, hogy ha a_{0}, …, a_{n} 4.3 alakú, akkor T_{1}a_{0}, …, T_{1}a_{n} 4.4 alakú, és |T_{1}| > 0. □

A 4.1 Tétel úgy is interpretálható, hogy a g(z_{i_{1}}) = ⋯ = g(z_{i_{t}}) = 0, g(z_{i_{t+1}}) = ⋯ = g(z_{i_{m+2}}) = 1 függvényt bevezetve:

(−1)^{t+m+1}[z_{i_{1}}, …, z_{i_{m+2}}]g > 0

Térjünk most rá a duál-megengedett bázisok vizsgálatára. Jelölje A az egyenlőség-feltételek mátrixát a 4.1 feladatban, B ennek egy bázisát, b pedig a jobb oldalon álló vektort. Ekkor T_{1}A , T_{1}B és T_{1}b lesz a megfelelő mátrix, bázis, illetve vektor a 4.2 feladatban, és fennállnak a következő összefüggések:

(T_{1}B)^{−1}T_{1}b = B^{−1}b
f_{p} − f_{B}^{T} (T_{1}B)^{−1}(T_{1}a_{p}) = f_{p} − f_{B}^{T} B^{−1}a_{p}

Vagyis B akkor és csak akkor primál-megengedett az 4.1-ben, ha T_{1}B primálmegengedett 4.2-ben, és B akkor és csak akkor duál-megengedett a 4.1-ben, ha T_{1}B duál-megengedett a 4.2-ben. Ezért elég a 4.1 feladatban megkeresni a duál-megengedett bázisokat. Legyen L_{I}(z) az m-edrendű Lagrange-polinom a (z_{i}, f(z_{i})), i ∈ I párokra, azaz:

L_{I}(z) = ∑_{i=0}^{m} f(z_{i})L_{I,i}(z)  (4.8)

ahol

L_{I,i}(z) = ∏_{j∈I\\{i\}} \frac{z − z_{j}}{z_{i} − z_{j}}

Definiáljuk a következő vektort minden valós z-re:

a(z) = ( 1 ; z ; ⋮ ; z^{m} )

Azt állítjuk, hogy

f_{B}^{T} B^{−1}(I)a(z) = L_{I}(z)  (4.9)

Valóban, a(z_{i}) = a_{i} i ∈ I-re, így

f_{B}^{T} B^{−1}(I)a(z_{i}) = f(z_{i}) i ∈ I

és ezért 4.9 teljesül minden valós z-re. A jól ismert (ld. például [35]) formula szerint minden olyan z-re, amelyre f értelmezve van:

f(z) − L_{I}(z) = ∏_{j∈I}(z − z_{j})[z, z_{i}, i ∈ I]f  (4.10)

A 4.9 összefüggésből látszik, hogy B(I) duál-megengedettsége a 4.1 feladatban minimalizálás (maximalizálás) esetén ekvivalens azzal, hogy f(z) nagyobb (kisebb), vagy egyenlő, mint L_{I}(z) minden z_{i}, i ∈ I-re. A 4.10-ből viszont az következik, hogy a [z, z_{i}, i ∈ I]f differencia-hányadosok előjelének ismeretében karakterizálni tudjuk a duál-megengedett bázisokat. A felsorolt speciális esetekben a következő tételek teszik ezt meg:

Tétel 4.2 Tegyük fel, hogy az f(z), z ∈ {z_{0}, z_{1}, …, z_{n}} függvény minden (m+1)-edik differencia-hányadosa pozitív. Ekkor a 4.1 és 4.2 feladatokban minden bázis duál-nemdegenerált, és a duál-megengedett bázisok indexhalmaza megegyezik valamelyikkel az alább felsoroltak közül (az indexeket növekvő sorrendben elhelyezve):

m + 1 páros  m + 1 páratlan
minimalizálás {j, j + 1, …, k, k + 1}  {0, j, j + 1, …, k, k + 1}
maximalizálás {0, j, j + 1, …, k, k + 1, n} {j, j + 1, …, k, k + 1, n}

Bizonyítás. A fentebb elmondottak alapján elég a 4.1 feladatra bizonyítani. Legyen I egy tetszőleges bázis indexhalmaza. Ha z ∉ {z_{i}, i ∈ I} akkor 4.10 alapján f(z) − L_{I}(z) ≠ 0, tehát a bázis duál-nemdegenerált.

A duál-megengedettség vizsgálatához tekintsük először a minimalizálást. A feltételezés szerint [z, z_{i}, i ∈ I]f > 0 minden z ∉ {z_{i}, i ∈ I}-re, tehát a duálmegengedettséghez az kell, hogy minden ilyen z-re

∏_{j∈I}(z − z_{j}) > 0

Ez akkor teljesül, ha I-ben az indexek párosával állnak, ha (m+1) páros, illetve még a 0 is benne van, ha (m+1) páratlan. Ez pont az, mint ami a tétel állításban szerepel.

Ha maximalizálunk, akkor

∏_{j∈I}(z − z_{j}) < 0

kell hogy legyen minden z ∉ {z_{i}, i ∈ I}-re, amely pont azokra a struktúrákra vezet, amiket állítottunk. □

Tétel 4.3 Tegyük fel, hogy f_{r} = 1 és f_{i} = 0 minden i ≠ r-re, ahol 0 ≤ r ≤ n. Ekkor a 2.5 Tétel állításai a duál-megengedett és a duál-degenerált bázisok szerkezetéről fennállnak.

Bizonyítás. A 4.6, 4.9 és a 4.10 összefüggésekből a tétel egyenesen következik. A példa kedvéért nézzük meg a minimalizálás, (m+1) páros, 2 ≤ r ≤ n−1, r ∈ I esetet, és tegyük fel, hogy páros számú r-nél kisebb index van I-ben. Ekkor 4.6 szerint

[z, z_{i}, i ∈ I]f < 0, ha z < z_{r}
[z, z_{i}, i ∈ I]f > 0, ha z > z_{r}

Tehát a ∏_{j∈I}(z − z_{j}) szorzatnak negatívnak kell lennie z < z_{r}-re, és pozitívnak kell lennie z > z_{r}-re. ebből pedig már következik a megfelelő struktúra. □

Tétel 4.4 Tegyük fel, hogy f_{0} = ⋯ = f_{r−1} = 0; f_{r} = ⋯ = f_{n} = 1 valamilyen 1 ≤ r ≤ n-re. Ekkor a 2.7 Tétel állításai a duál-megengedett és a duál-degenerált bázisok szerkezetéről fennállnak.

Bizonyítás. A 4.6 4.9 és a 4.10 összefüggésekre, és a 4.1 Tételre támaszkodva a bizonyítás az eddigiekhez hasonlóan végezhető el. □

4.2 Általánosítás

A következő, az eddigiek általánosításként előálló feladattal foglalkozunk:

min ill. max {f_{0}p_{0} + ⋯ + f_{n}p_{n}}
felt., hogy p_{0} + ⋯ + p_{n} = 1
a_{10}p_{0} + ⋯ + a_{1n}p_{n} = b_{1}
a_{20}p_{0} + ⋯ + a_{2n}p_{n} = b_{2}
⋮
a_{m0}p_{0} + ⋯ + a_{mn}p_{n} = b_{m}
p_{0} ≥ 0, …, p_{n} ≥ 0

(4.11)

Jelöljük A-val az egyenlőség-feltételek mátrixát, a_{0}, …, a_{n}-nel ennek az oszlopait.

Definíció 4.2 Az A váltakozó előjelű, ha minden 1 ≤ i_{1} < … < i_{t} < … < i_{m+2} ≤ n-re, (1 ≤ t ≤ m + 1)

(−1)^{t} | \begin{matrix}0 & … & 0 & 1 & … & 1 \\ a_{i_{1}} & … & a_{i_{t}} & a_{i_{t+1}} & … & a_{i_{m+2}} \end{matrix} | > 0

A 4.1 Tétel pont azt mondja ki, hogy a 4.1 és 4.2 feladatok mátrixa váltakozó előjelű. Az alábbi három tétel a 2. fejezet megfelelő tételeinek általánosításai, és ugyanúgy beláthatóak a 2.12 képletre alapozva, mint azok:

Tétel 4.5 Tegyük fel, hogy minden (m+1)-rendű minor A-ból és minden

(m+2)-rendű minor (\begin{matrix}f^{T} \\ A \end{matrix} )-ból pozitív. (f^{T} = (f_{0}, f_{1}, …, f_{n})) Ekkor a 4.1 fela-

datban minden bázis duál-nemdegenerált, és a duál-megengedett bázisok indexhalmaza megegyezik valamelyikkel az alább felsoroltak közül:

m + 1 páros  m + 1 páratlan
minimalizálás {j, j + 1, …, k, k + 1}  {j, j + 1, …, k, k + 1, n}
maximalizálás {0, j, j + 1, …, k, k + 1, n} {0, j, j + 1, …, k, k + 1}

Az indexeket növekvő sorrendben elhelyezve.

Tétel 4.6 Tegyük fel, hogy f_{r} = 1; f_{i} = 0 ha i ≠ r valamilyen 0 ≤ r ≤ n-re, továbbá A minden (m+1)-rendű minorja pozitív. Ekkor a 2.5 Tétel állításai következnek.

Tétel 4.7 Tegyük fel, hogy f_{0} = ⋯ = f_{r−1} = 0; f_{r} = ⋯ = f_{n} = 1 valamilyen 1 ≤ r ≤ n-re, továbbá A minden (m+1)-rendű minorja pozitív, és A váltakozó előjelű. Ekkor a 2.7 Tétel állításai következnek.

A következő tétel a duálvektor komponenseiről szól:

Tétel 4.8 A következő állítások a 4.11 feladat duálvektoraira teljesülnek:

(a) Tegyük fel, hogy minden (m+1)-rendű minor (\begin{matrix}f^{T} \\ A \end{matrix} )-ból pozitív, és B

egy tetszőleges bázisa A-nak. Ekkor az f_{B}^{T} B^{−1} duálvektor komponensei mind különböznek 0-tól, és váltakozó előjelűek, plusszal kezdve.

(b) Tegyük fel, hogy f_{r} = 1; f_{i} = 0 ha i ≠ r valamilyen 0 ≤ r ≤ n-re, B(I) egy olyan bázis, hogy |B(I)| > 0, és I-ben páros (páratlan) számú r-nél kisebb index van, továbbá r ∈ I és minden m-rangú minor A-ból pozitív. Ekkor az f_{B}^{T} B^{−1} duálvektor komponensei mind különböznek 0-tól, és váltakozó előjelűek, plusszal (minusszal) kezdve.

(c) Legyenek f_{0} = ⋯ = f_{r−1} = 0; f_{r} = ⋯ = f_{n} = 1 valamilyen 1 ≤ r ≤ nre. Tegyük fel, hogy B(I) egy olyan bázis, hogy |B(I)| > 0, és I-ben páros (páratlan) számú r-nél kisebb index van, valamint hogy I ⊄ {0, …, r − 1}, I ⊄ {r, …, n}. Tegyük fel még azt is, hogy A-ból bármelyik sort törölve a maradék mátrix váltakozó előjelű lesz. Ekkor az f_{B}^{T} B^{−1} duálvektor komponensei mind különböznek 0-tól, és váltakozó előjelűek, plusszal (minusszal) kezdve.

Bizonyítás.

( \begin{matrix}1 & −f_{B}^{T} B^{−1} \\ 0 & B^{−1} \end{matrix} ) = ( \begin{matrix}1 & f_{B}^{T} \\ 0 & B \end{matrix} )^{−1}

Tehát az f_{B}^{T} B^{−1} vektor komponensei pozitív számszorosai (1/|B|-szeresei) az

( \begin{matrix}1 & f_{B}^{T} \\ 0 & B \end{matrix} )

mátrix megfelelő minorjainak (az első oszlopot és sorban a 2., 3.,…, (m+2)- edik sort kitörölve) váltakozó előjellel ellátva, plusszal kezdve. Az (a) esetben az összes ilyen minor pozitív, míg a (b) és (c) esetben pozitívak illetve negatívak attól függően, hogy páros, vagy páratlan számú r-nél kisebb index van-e I-ben, feltéve hogy r ∈ I a (b) esetben, és I ⊄ {0, …, r − 1}, I ⊄ {r, …, n} a (c) esetben. □

A 4.6 és 4.7 Tétel következménye az alábbi állítás.

Tétel 4.9 Legyen 1 ≤ r ≤ n − 1, és tekintsük a következő problémákat a 4.11 feladatra vonatkozólag:

(a) maximalizálás a 4.6 Tétel feltételei mellett

(b) maximalizálás a 4.7 Tétel feltételei mellett

(c) minimalizálás a 4.7 Tétel feltételei mellett, r helyett (r+1)-re

Az (a) feladat optimális megoldása egyértelmű, és egyben optimális megoldása (b)-nek és (c)-nek is.

A 4.11 feladat feltételei mellett a p_{r} + ⋯ + p_{n} maximuma megegyezik a p_{r} maximumának és a p_{r+1} + ⋯ + p_{n} minimumának összegével

Bizonyítás. Az (a) feladat összes duál-megengedett bázisa duál-nemdege-nerált, így az optimális megoldás egyértelmű. Mivel minden (a)-ban duálmegengedett bázis duál-megengedett (b)-ben és (c)-ben is, ez az egyértelmű optimális megoldás optimális megoldása (b)-nek és (c)-nek is. A többi ebből következik. □

4.3 Becslések a hatványmomentumok felhasználásával

A hatványmomentum probléma optimumára (különböző f-ek esetén) szeretnénk zárt alakú alsó és felső becsléseket adni. Ugyanazt a módszert követjük, amit a 3. fejezetben. Megtehetnénk, hogy az ott leírt, binomiális momentumokat használó becsléseket a Stirling-számok segítségével egyszerűen átírnánk, de ennél sokkal elegánsabb becsléseket kapunk, ha a módszert közvetlenül a hatványmomentumokra alkalmazzuk.

Legyen B(I) egy bázisa a 4.1 feladatnak. A 4.9 összefüggésből következik, hogy

f_{B}^{T} B(I)^{−1} ( 1 ; μ_{1} ; ⋮ ; μ_{m} ) = f_{B}^{T} B(I)^{−1}E[a(ξ)] = E[L_{I}(ξ)]  (4.12)

Tétel 4.10 Legyen az f a z_{0} < z_{1} < … < z_{n} diszkrét halmazon értelmezve. Tegyük fel, hogy az f (m+1)-edik differencia-hányadosai mind pozitívak. Ekkor a következő állítások teljesülnek:

(a) Ha m+1 páros, és I = {j, j + 1, …, k, k + 1}, akkor

E[f(ξ)] ≥ E[L_{I}(ξ)]

(b) Ha m+1 páros, és I = {0, j, j + 1, …, k, k + 1, n}, akkor

E[f(ξ)] ≤ E[L_{I}(ξ)]

(c) Ha m+1 páratlan, és I = {0, j, j + 1, …, k, k + 1}, akkor

E[f(ξ)] ≥ E[L_{I}(ξ)]

(d) Ha m+1 páratlan, és I = {j, j + 1, …, k, k + 1, n}, akkor

E[f(ξ)] ≤ E[L_{I}(ξ)]

Az egyenlőtlenségek akkor élesek, ha I egy primál-megengedett bázis indexhalmaza.

Bizonyítás. Az állítások a 4.2 Tételből, és a 4.12 azonosságból következnek, azon elv alapján amit a 3. fejezetben is használtunk. □

Ha m=1, azaz a függvény konvex , akkor ezt a tételt alkalmazva a következő egyenlőtlenségeket kapjuk:

\frac{z_{j+1} − μ_{1}}{z_{j+1} − z_{j}} f(z_{j}) + \frac{μ_{1} − z_{j}}{z_{j+1} − z_{j}} f(z_{j+1}) ≤ E[f(ξ)] ≤ \frac{z_{n} − μ_{1}}{z_{n} − z_{0}} f(z_{0}) − \frac{μ_{1} − z_{0}}{z_{n} − z_{0}} f(z_{n})

A jobb oldali egyenlőtlenség csak z_{0}, z_{n}, f(z_{0}), f(z_{n})-től függ, és mindig éles. A bal oldali egyenlőtlenség éles, ha z_{j} < μ_{1} < z_{j+1}. Terjesszük ki az f definícióját a [z_{0}, z_{n}] intervallumra: legyen f(z) = f(z_{i}) + t[f(z_{i+1}) − f(z_{i})], ha z = z_{i} + t(z_{i+1}−z_{i}), (0 < t < 1 és i = 0, 1, …, n−1). Így egy szakaszosan lineáris, konvex függvényt kapunk, amire a fenti egyenlőtlenség igaz marad. Mivel minden véges intervallumon értelmezett, konvex függvény tetszőleges pontossággal közelíthető szakaszosan lineáris, konvex függvénynyel, a következő egyenlőtlenséget kapjuk (z_{0} = α, z_{n} = β):

f(μ_{1}) ≤ E[f(ξ)] ≤ \frac{β − μ_{1}}{β − α} f(α) − \frac{μ_{1} − α}{β − α}f(β)

Ezek pont a Jensen-, és az Edmundson-Madansky egyenlőtlenségek (ld. [16], illetve [9] és [25])

Az alábbi két tétel a másik két fajta függvényre ad hasonló becsléseket.

Tétel 4.11 Legyen f_{r} = 1; f_{i} = 0 ha i ≠ r valamilyen 0 ≤ r ≤ n-re. Ekkor a következő állítások teljesülnek a 4.1 feladatban:

(a) Ha I egy duál-megengedett bázis indexhalmaza a minimalizálásnál, akkor

P (ξ = z_{r}) ≥ E[L_{I,r}(ξ)]

(b) Ha I egy duál-megengedett bázis indexhalmaza a maximalizálásnál, akkor

P (ξ = z_{r}) ≤ E[L_{I,r}(ξ)]

Az egyenlőtlenségek akkor élesek, ha a bázisok primál-megengedettek is.

Tétel 4.12 Legyen f_{0} = ⋯ = f_{r−1} = 0; f_{r} = ⋯ = f_{n} = 1 valamilyen 1 ≤ r ≤ n-re. Ekkor a következő állítások teljesülnek a 4.1 feladatban:

(a) Ha I egy duál-megengedett bázis indexhalmaza a minimalizálásnál, akkor

P (ξ ≥ z_{r}) ≥ E[ ∑_{j∈I,j≥r} L_{I,j}(ξ)]

(b) Ha I egy duál-megengedett bázis indexhalmaza a maximalizálásnál, akkor

P (ξ ≥ z_{r}) ≤ E[ ∑_{j∈I,j≥r} L_{I,j}(ξ)]

Az egyenlőtlenségek akkor élesek, ha a bázisok primál-megengedettek is.

Ezekből a tételekből m különböző értékei mellett számos alsó, és felső becslést lehet levezetni a megfelelő valószínűségi függvényekre. (ld. például [6]). Az éles becslések meghatározása azonban általában olyan bonyolut, hogy már m = 3 esetén is érdemesebb a 2. fejezetben leírt algoritmust használni.

Alkalmazások

5.1 A kielégíthetőségi probléma

Boole-egyenletnek nevezünk egy olyan Boole-változós (x_{1}, …, x_{N}, ahol x_{i} = 0 vagy 1) egyenletet, amelynek az egyik oldala 0, a másik pedig véges számú klóz (azaz néhány x_{i} és néhány \overline{x}_{j} = 1 − x_{j} szorzata) összege. A kielégíthetőségi probléma egy olyan Boole-vektor létezésére vonatkozik, amely kielégíti az egyenletet. Boros és Prékopa [7]-ben az eddig leírt elméletet alkalmazta a probléma megoldására. Ebben a részben röviden leírjuk, hogyan.

Egy Boole-egyenlet úgy is megfogalmazható, hogy minden klóz legyen egyenlő 0-val. Legyen n a klózok száma. Az A_{i} jelölje azon x ∈ {0, 1}^{N} vektorok halmazát, amire az i-edik klóz nulla. Például, ha a Boole-egyenlet a következő:

x_{1}\overline{x}_{2}x_{3} + \overline{x}_{1}x_{2}x_{3}x_{4} + \overline{x}_{1}\overline{x}_{4} = 0

akkor

A_{1} = \{x : x_{1}\overline{x}_{2}x_{3} = 0\}
A_{2} = \{x : \overline{x}_{1}x_{2}x_{3}x_{4} = 0\}
A_{3} = \{x : \overline{x}_{1}\overline{x}_{4} = 0\}

ha x = (x_{1}, x_{2}, x_{3}, x_{4}). Randomizáljuk az x_{i}-ket, vagyis tekintsük úgy, mintha független 0,1 értékű valószínűségi változók lennének P (x_{i} = 1) = p_{i}, 0 < p_{i} < 1, i = 1, …, N valószínűséggel. A p_{1}, …, p_{N} számokat mi magunk választjuk meg. Eszerint az A_{i}-k valószínűségi események lesznek, és tekinthetjük a P (\overline{A}_{1} ∪ ⋯ ∪ \overline{A}_{n}) valószínűséget. Alkalmazzuk a 3.5 Tételt az \overline{A}_{1}, …, \overline{A}_{n} eseményekre és valamilyen általunk meghatározott, megfelelő m-re. Legyen U(p_{1}, …, p_{N}) egy a tételből adódó felső korlát. Igaz tehát a következő:

P (\overline{A}_{1} ∪ ⋯ ∪ \overline{A}_{n}) ≤ U(p_{1}, …, p_{N})

Az U(p_{1}, …, p_{N}) polinomiális függvénye p_{1}, …, p_{N}-nek. Azt könnyű belátni, hogy U bármely választása esetén

U(p_{1}, …, p_{N}) ≥ Min{U(p_{1}, …, 0, …, p_{N}), U(p_{1}, …, 1, …, p_{N})}

Tegyük fel, hogy találtunk olyan p_{1}, …, p_{N} számokat, hogy U(p_{1}, …, p_{N}) < 1. Ekkor x_{1}, …, x_{N}-et válasszuk meg a következőképpen:

Először nézzük x_{1}-et. Ha U(1, p_{2}, …, p_{N}) ≤ U(0, p_{2}, …, p_{N}), akkor legyen x_{1} = 1, különben x_{1} = 0. Ha x_{1}, …, x_{i−1}-et (i = 2, …, N) már meghatároztuk, és U(x_{1}, …, x_{i−1}, 1, p_{i+1}, …, p_{N}) ≤ U(x_{1}, …, x_{i−1}, 0, p_{i+1}, …, p_{N}), akkor legyen x_{i} = 1, különben x_{i} = 0. Az így választott x_{i}-k kielégítik a Booleegyenletet.

Ez az algoritmus egyszerű és hatékony, de kell hozzá olyan p_{1}, …, p_{N}, amire U(p_{1}, …, p_{N}) < 1. Ha ilyet nem tudunk rögtön találni, alkalmazzunk néhány minimalizáló lépést az U(p_{1}, …, p_{N}) polinomon, amíg a fenti egyenlőtlenséget el nem érjük! Az is lehet azonban, hogy a Boole-egyenlet nem kielégíthető. Ebben az esetben a maximális kielégíthetőségi problémát oldhatjuk meg, ahol minél több klóz nullával való egyenlőségét akarjuk elérni. Ekkor a felső korlátot annak a valószínűségére keressük, hogy legalább r bekövetkezik az A_{1}, …, A_{n} események közül.

5.2 Sztochasztikus szállítási hálózatok

A szállítási hálózat egy olyan G(N, A) irányított gráf, amelynek N a csúcshalmaza, A ⊂ N ×N az élhalmaza. Feltesszük hogy ha (i, k) ∈ A, akkor (k, i) ∈ A. Minden (i, k) ∈ A élhez tartozik egy y(i, k) ∈ R kapacitás, és minden i ∈ N csúcshoz egy d(i) ∈ R igény. Ha d(i) < 0, akkor az abszolút értékét kínálatnak is nevezhetjük. A szállítási hálózat sztochasztikus, ha az igényfüggvény, vagy a kapacitásfüggvény vagy mindkettő valószínűségi változó. Például szállítási hálózatnak tekinthető az energia hálózat, ahol az erőművek illetve a fogyasztók a csúcsok, és a távvezetékek az élek. De hasonlóan modellezhetőek a hidrológiai hálózatok, ahol a tározók és a csatornák játszanak szerepet.

A szállítási hálózatnál az egyik legfontosabb kérdés az, hogy ki lehet-e mindig elégíteni az igényeket. Vezessük be a hálózati folyam fogalmát: egy f(i, k) (i, k) ∈ A valós függvény, amely kielégíti a következő feltételeket:

f(i, k) + f(k, i) = 0
f(i, k) ≤ y(i, k) ∀(i, k) ∈ A

Az y és az f definíciója kiterjeszthető az egész N × N-re ha f(i, k) = y(i, k) = 0 minden olyan (i, k)-ra, amely (N × N)\A-ban van. A következő jelölésekkel egyszerűsíthetjük a formuláinkat (B, C ⊂ N):

y(B, C) = ∑_{i∈B,k∈C} y(i, k)

f(B, C) = ∑_{i∈B,k∈C} f(i, k)

d(B) = ∑_{i∈B} d(i)

Az igényfüggvényt kielégíthetőnek mondjuk, ha

f(N, i) ≥ d(i) ∀i ∈ A

Megadható egy olyan karakterizációja a kielégíthető igényeknek, amely nem használja a folyam fogalmát:

Tétel 5.1 (Gale és Hoffman) A d(i), i ∈ N igényfüggvény kielégíthető akkor és csak akkor, ha ∀S ⊆ N-re

d(S) ≤ y(\overline{S}, S)

Rövid bizonyítását ld. [13]-ban.

A sztochasztikus szállítási hálózatok esetén nagyon fontos szerepe van annak az esemény valószínűségének, hogy az igényfüggvény kielégíthető:

P (d(S) ≤ y(\overline{S}, S), minden S ⊆ N-re)

Ezt a valószínűséget szeretnénk meghatározni. A pontos kiszámolása általában rettentő bonyolult a szóba jövő S-ek nagy száma miatt. Két jelenség azonban segítségünkre van. Az első az, hogy az egyenlőtlenségek (az ellenőrizendő Sek) számát jelentősen csökkenthetjük, a redundancia kizárásával; másik pedig az, hogy alkalmazhatjuk az előző fejezetekben leírt becslési módszereket. Az első egyszerűsítésről itt nem írunk bővebben, az érdeklődő olvasó megtalálja [31]-ben, vagy [30]-ban.

Tegyük fel tehát, hogy n db. egyenlőtlenség maradt a redundáns egyenlőtlenségek eliminációja után, és jelöljük T_{1}, …, T_{n}-nel a megmaradt S-eket (T_{1}, …, T_{n} ⊆ N). A következő valószínűséget akarjuk becsülni:

P = P (d(T_{i}) ≤ y(\overline{T}_{i}, T), i = 1, …, n)

Jelöljük A_{i}-vel azt az eseményt, hogy az n-edik egyenlőtlenség teljesül. Legyen

S_{k} = ∑_{1≤i_{1}<...<i_{k}≤n} P (A_{i_{1}} ⋯ A_{i_{k}}) k = 1, …, n

(Ennek az S_{k}-nak természetesen nincs köze az eredeti egyenlőtlenségekben szereplő S ⊆ N halmazokhoz.) Legyen továbbá m egy egész szám, amelyre 2 ≤ m < n teljesül. Jelöljük V_{min}-nel, illetve V_{max}-szal a 2.6 illetve 2.7 feladatok optimumát r = n esetén. Azaz:

V_{min} ≤ P = P (A_{1} ⋯ A_{n}) ≤ V_{max}

Ezzel a módszerrel, m értékét növelve kellően szoros becslést adhatunk P -re.

Sok esetben az \overline{A}_{1}, \overline{A}_{2}, …, \overline{A}_{n} események használata numerikusan kedvezőbb. Ilyenkor az \overline{S}_{k}-kra (k = 1, …, m) felírt 2.4-2.5 alakú feladatok optimumaira, \overline{V}_{min}-re és \overline{V}_{max}-ra igaz, hogy:

\overline{V}_{min} ≤ P (\overline{A}_{1} + ⋯ + \overline{A}_{n}) ≤ \overline{V}_{max}

és akkor

1 − \overline{V}_{max} ≤ P (A_{1} ⋯ A_{n}) ≤ 1 − \overline{V}_{min}

Könnyen belátható, hogy 1 − \overline{V}_{max} = V_{min}, és 1 − \overline{V}_{min} = V_{max}, tehát tényleg csak a numerikus szempontokok játszanak szerepet az A_{i} és \overline{A}_{i} közötti választásban. Ha valaki az S_{k}-k (\overline{S}_{k}-k) kiszámítására kiváncsi, forduljon [31]- hez.

5.3 Hálózatok megbízhatósága

Legyen a hálózat egy G(N, A) gráf, N a csúcsok, A az élek halmaza. Az egyszerűség kedvéért legyenek az élek irányítatlanok. Az élek működnek, vagy nem működnek egymástól függetlenül nem feltétlenül ugyanolyan valószínűséggel, vagyis ha A = {e_{1}, …, e_{s}}, akkor bevezethetjük az x_{1}, …, x_{s} véletlen Booleváltozókat, ahol x_{i} = 1 akkor és csak akkor, ha az i-edik él működik. Legyen P (x_{i} = 1) = p_{i}, i = 1, …, s. Így modellezhetők például a kommunikációs hálózatok, ahol az él működése azt jelenti, hogy tud hívást fogadni.

Két fajta megbízhatósági probléma merülhet fel: a két pont közötti, ahol arra vagyunk kiváncsiak, hogy milyen valószínűséggel létezik működő út két adott pont között; illetve az összes pont közötti ahol bármely két pont közötti működő út létezésének a valószínűsége a kérdés. Ez utóbbit hívhatjuk összefüggőségi problémának is. A megbízhatósági valószínűségek kiszámolása általában lehetetlen a szóba jöhető utak nagy száma miatt, de alkalmazhatjuk az eddig leírt becslési eljárásokat.

E célból tekintsük először a két pont közötti megbízhatósági problémát. Legyen s és t az előre adott két végpont (s, t ∈ N, s ≠ t). Generáljunk set és t-t összekötő utakat, és őket elválasztó vágásokat. Annak a valószínűsége, hogy létezik legalább egy működő út s és t között nagyobb vagy egyenlő, mint annak a valószínűsége, hogy a generált utak között létezik legalább egy működő, és kisebb vagy egyenlő, mint 1 minusz annak a valószínűsége, hogy a generáltak közül legalább egy vágás nem működik (azaz egyetlen él sem működik abban a vágásban). Ezen korlátozó valószínűségeket becsüljük meg a 2.4 feladat sémája szerint.

Legyen P = {P_{i}}, C = {C_{i}} a generált utak és vágások halmaza, az A_{i} pedig jelölje azt az eseményt, hogy az i-edik út, illetve vágás mőködik:

A_{i} = { ∏_{j∈P_{i}} x_{j} = 1} P_{i} ∈ P

illetve

A_{i} = { ∏_{j∈C_{i}} x_{j} = 1} C_{i} ∈ C

Legyen az ezen eseményekre felírt 2.4 feladat optimuma L(P, p, m) illetve L(C, p, m). Belátható, hogy 0 ≤ L(P, p, m) ≤ 1, 0 ≤ L(C, p, m) ≤ 1, és ha P-t vagy C-t egy bővebb halmazra cseréljük, akkor az L(P, p, m), illetve L(C, p, m) értéke nem csökken.

Jelöljük P_{st}-vel a két pont közötti megbízhatóság valószínűségét. Az eddigiek alapján P_{st}-t a következőképpen becsülhetjük:

L(P, p, m) ≤ P (∑_{i=1}^{n} A_{i}) ≤ P_{st}

ha |P| = n, és

P_{st} ≤ 1 − L(C, 1 − p, m)

Hasonlóképpen járhatunk el ha az összefüggőségi problémát vizsgáljuk. Ekkor feszítőfákat és vágásokat kell generálni, és azokkal becsülni az összefüggőség valószínűségét.

A becslések pontossága természetesen függ a m értékétől, a generált élhalmazrendszerek nagyságától, de jelentősen függ ezen élhalmazok kiválasztásától is. Ha például a generált utak az élek viszonylag szűk halmazára koncentrálódnak, akkor nem kapunk elég éles becslést. Azt szeretnénk, ha az általunk kiválasztott úthalmaz (vágáshalmaz) az éleket a lehető legegyenletesebben fedje le, és hogy viszonylag nagy valószínűséggel működő (nem működő) éleket tartalmazzon. Prékopa, Boros és Lih cikke [32] a következő algoritmust ajánlja (csak az s-et és t-t összekötő utakra írjuk le az algoritmust, a többi hasonlóképpen készíthető el, vagy megtalálható az idézett cikkben):

Bemenet: A G(N, A) gráf; a p valószínűségi vektor; a végpontok s, t ∈ N; a generálni kívánt utak száma, n; és ha szükséges egy K konstans az algoritmus végességét biztosítandó.

Kimenet: Az s-et a t-vel összekötő legfeljebb n db. út P halmaza.

0. lépés: Legyen d(e) = − log p(e), f(e) = 0 minden e ∈ A-ra. Legyen d(e) az e él súlya, f(e)-vel pedig az e-n átmenő, kiválasztott utak számát jelöljük. Legyen P = ∅. Legyen továbbá δ egy fix, pozitív konstans.

1. lépés: Legyen P a d(e) súly szerint minimális s és t közötti út.

2. lépés: Ha P ∉ P, akkor P = P ∪ {P }, f(e) = f(e) + 1 minden e ∈ P -re, és R = 0. Ha P ∈ P, akkor R = R + 1, és STOP, ha R > K.

3. lépés: Minden e ∈ P -re legyen r(e) egy véletlen egész szám 0 és f(e) között, és d(e) = r(e)δ − log p(e).

4. lépés: Ha |P| < n, akkor 1. lépés, különben STOP.

Mint látható, az algoritmus a minimális út megkeresésére szolgáló jól ismert módszerekre épül. Numerikus példákat az idézett Prékopa-Boros-Lih cikkben [32] találhat az olvasó.

Távközlési hálózatok megbízhatósága

Ebben a fejezetben egy a gyakorlathoz még közelebb álló alkalmazást fejtünk ki Greenberg és Srikant munkája [15] alapján. A vizsgálatunk tárgya a többsávos integrált szolgáltatású távközlési hálózat, alapja pedig egy fixpont módszer. Az utóbbi időben számos fixpont módszert használó leírás született (ld. [15] referenciáit), de ezek nagyrészt az egyszerűbb, hangátvitelre készült hálózatokra (voice networks) vonatkoznak. Az integrált szolgáltatású hálózatok két fontos dologban különböznek ezektől:

• Míg a hangátviteli hálózatok teljesen összefüggőek (vagy majdnem teljesen azok), és két csúcs között a hívás legfeljebb egy közbenső csúcson megy át, addig az integrált szolgáltatású hálózatok sokkal kevésbé összefüggőek, és a hívások is sokkal több átmeneten kereszül haladhatnak (általában 1-6 közbülső csúccsal).

• A hangátviteli hálózatokban minden hívás azonos sávszélességű, az integrált szolgáltatású hálózatoknak ezzel szemben sok különböző sávszélességű hívást kell kezelnie.

Ezek a különbségek sajnos lehetetlenné teszik a hangátviteli hálózatokra készült módszerek használatát az integrált szolgáltatású hálózatokban a számolási idő megnövekedése miatt. A számítási bonyolultság ugyanis exponenciális mind a sávszélességi osztályok, mind a lehetséges átviteli utak számában. Az 5.3 részben leírt becslések segítségével azonban túlléphetünk ezeken a nehézségeken.

6.1 A modell

Legyen a hálózatunknak N csúcsa, 1, 2, …, N-nel jelölve. Az élek irányítatlanok, az i és a j csúcs között haladót jelölje (i, j). Minden (i, j) élhez tartozik egy C_{ij} kapacitás, amelyet sávszélességi egységben (trunk) mérünk. A hálózatba érkező hívások S db. osztályba sorolhatók a sávszélességük és a kapcsolat felépítésének módja szerint. Az s-edik osztályba eső hívások sávszélessége b_{s}, azaz ha létrejön a kapcsolat, akkor ez a hívás b_{s} csak általa használt egységet foglal el egyszerre a forrásától a céljáig tartó út minden élén.

Minden (i, j) csúcspárhoz tartozik egy i és j közötti utakból álló P_{i,j}^{(1)}, P_{i,j}^{(2)}, … rendezett sor, amelyek az útkiosztást határozzák meg: a hívás azon az úton fog átmenni, amelyiken először elfogadható. Egy úton akkor elfogadható, ha minden élén elfogadható. Azt, hogy egy hívás egy élen mikor elfogadható, kétfajtaképpen dönthetjük el: kontrollal, vagy anélkül. A kontroll alatt egy olyan mechanizmust értünk, amely alkalmas a hívások közötti esetleges prioritás-különbségek kezelésére. Ebben a modellben ezt egységfenntartással (trunk reservation) érjük el, a következőképpen: Ha nincs kontroll, akkor egy s osztályba tartozó hívás elfogadható az (i, j) élen, ha b_{s} kisebb vagy egyenlő, mint a nem használt egységek száma. Ha van kontroll, akkor az s osztályba tartozó hívás elfogadható az élen, ha b_{s} kisebb vagy egyenlő, mint a nem használt egységek száma minusz r, ahol r egy s-től, i-től, j-től és esetleg még más paraméterektől függő pozitív konstans. Ha r-et kicsinek választjuk, akkor a hívás nyilván nagyobb eséllyel megy át a hálózaton, tehát a nagyobb prioritású hívásokhoz kisebb r-et kell választani.

A hívások forgalmát a következőképpen modellezhetjük: egy s típusú hívás az (i, j) csúcspárra egy λ_{i,j}(s) paraméterű Poisson-folyamat szerint érkezik. Ezek a folyamatok mind a csúcspárok, mind a típusok szerint egymástól függetlenek. Ha el lett fogadva, akkor a hívás időtartamát egy μ_{i,j}(s) paraméterű exponenciális eloszlás írja le, amely független a más (i, j)-re és s-re vonatkozó eloszlástól, és a beérkezési folyamatoktól is.

A fixpont módszer a következő két statisztikai feltevésen alapul:

F1 (Él függetlenség): Annak a valószínűsége, hogy a hívás elfogadható egy úton egyenlő azoknak a valószínűségeknek a szorzatával, hogy a hívás elfogadható az út élein.

F2 (Poisson feltevés): Egy adott típusú hívás egy adott élre Poisson-folyamat szerint érkezik. A folyamat paramétere függhet az él állapotátától.

6.2 A megbízhatóság becslése

A távközlési hálózatok egyik legfontosabb jellemzője a két pont közötti megbízhatóság, amely azt méri, hogy milyen valószínűséggel megy át egy hívás egy adott csúcsból egy másik adott csúcsba. Ez majdnem ugyanaz, mint a 5.3 részben leírt két pont közötti megbízhatósági probléma, a különbség csak annyi, hogy itt előre meghatározott utakon mehet csak át a hívás, ezért ezt nevezhetjük útkorlátozott változatnak. Ez a korlátozás azonban nem szünteti meg a számítások bonyolultságának problémáját, így itt is becslést kell alkalmaznunk.

Tekintsük az (i, j) csúcspárt. Legyen P_{i,j} az útkiosztást meghatározó P_{i,j}^{(1)}, P_{i,j}^{(2)}, … utak halmaza. A következő valószínűséget akarjuk megbecsülni:

P ( egy s típusú, az (i, j) csúcspárra érkező hívás átmegy)

amely egyenlő az alábbival

P ( egy s típusú hívás legalább egy úton P_{i,j}-ből elfogadható)

Tegyük fel, hogy ismerjük annak a valószínűségét, hogy egy (k, l) él elfogadja az s típusú hívást. Jelöljük ezt a_{k,l}(s)-sel. A következő hálózatot vizsgáljuk:

• a csúcsok: i, j és minden csúcs, amely P_{i,j}-ben előfordul

• az élek: a P_{i,j}-ben előforduló élek

• P ( a (k, l) él működik) = a_{k,l}(s)

Ezután elvégezhetjük az 5.3 részben bemutatott becslési eljárást annyi változtatással, hogy csak olyan utakat generálunk, amelyek P_{i,j}-ben vannak, és csak olyan vágásokat, amelyek P_{i,j}-t vágják el, azaz minden P_{i,j}-beli útnak van éle a vágásban.

Az a_{k,l}(s)-ek meghatározására fogjuk az említett fixpont módszert használni. Mint majd látni fogjuk, ebben még egyszer előfordul a 5.3 részben leírt becslési eljárás.

6.3 A fixpont módszer

Tegyük fel, hogy az (i, j) él olyan állapotban van, hogy az s típusú hívásokat el tudja fogadni. Ennek a valószínűsége a_{i,j}(s). Az F2 feltevés szerint az ilyen hívások Poisson-folyamat szerint érkeznek az élre. Jelöljük ν_{i,j}(s)-sel a Poissonfolyamat paraméterét. Belátjuk, hogy minden (i, j) élre egymástól függetlenül létezik egy leképezés a_{k,l}(s)-ekről ν_{i,j}(s)-re (ahol k és l az útkiosztástól függő csúcsok), és ν_{i,j}(s)-ről a_{i,j}(s)-re.

Vegyük ennek a két leképezésnek a kompozícióját: beérkezési paraméterek→ elfogadási valószínűségek→beérkezési paraméterek. Keressük meg ennek az összetett leképezésnek a fixpontját egyszerre rögzítve a ν_{i,j}(s)-ek és az a_{i,j}(s)-ek értékét. Az így kapott a_{i,j}-kkel számolhatunk a megbízhatóság becslésénél. Bár némely feltétel fennállása esetén nem egyértelmű a fixpont, az eddig megvizsgált gyakorlati problémákban ez nem fordult elő.

6.3.1 Elfogadási valószínűségek→beérkezési paraméterek

Tekintsük az (i, j) élt, és tegyük fel, hogy olyan állapotban van, hogy el tudja fogadni az s típusú hívásokat. Vegyünk egy (k, l) csúcspárt. Tegyük fel, hogy van olyan (k, l)-hez tartozó út P_{k,l}-ben, amely tartalmazza (i, j)-t. Legyen egy ilyen út az m-edik, a P_{k,l}^{(m)}. A (k, l) csúcspárra érkező s típusú hívások közül azok, amelyek P_{k,l}^{(m)}-en mennek, egy Poisson-folyamat szerint érkeznek

az (i, j) élre. Legyen ennek a folyamatnak a paramétere ν_{i,j}^{(m)}(k, l, s). Kiterjeszthetjük a definíciót az összes (k, l) csúcspárra, és m-re ha azokra, amelyekre P_{k,l}^{(m)} nem tartalmazza az (i, j)-t: ν_{i,j}^{(m)}(k, l, s) = 0. A ν_{i,j}^{(m)}(k, l, s) paramétereket megkaphatjuk az eredeti Poisson-folyamat ritkításával. Nézzük, hogyan:

Ha m = 1, vagyis az (i, j) rajta van a (k, l) pár első útján, akkor mivel az (i, j) élen a hívás elfogadható, az egész úton akkor lesz elfogadható, ha a többi élen is az, tehát:

ν_{i,j}^{(1)}(k, l, s) = λ_{k,l}(s) ∏_{(u,v)∈P_{k,l}^{(1)},(u,v)≠(i,j)} a_{u,v}(s)

Ha m > 1, akkor

ν_{i,j}^{(m)}(k, l, s) = λ_{k,l}(s)R_{i,j}^{(m)}(k, l, s) ∏_{(u,v)∈P_{k,l}^{(m)},(u,v)≠(i,j)} a_{u,v}(s)

ahol

R_{i,j}^{(m)}(k, l, s) =
P (a P_{k,l}^{(1)}, …, P_{k,l}^{(m−1)} utak nem elfogadhatóak | P_{k,l}^{(m)} elfogadható)

Ha ismerjük ν_{i,j}^{(m)}(k, l, s) értékét minden m-re, és (k, l)-re, akkor kiszámolhatjuk az (i, j)-re érkező hívások paraméterét:

ν_{i,j}(s) = ∑_{k,l} ∑_{m} ν_{i,j}^{(m)}(k, l, s)

Az R_{i,j}^{(m)}(k, l, s) kiszámolásához vegyük észre, hogy 1 − R_{i,j}^{(m)}(k, l, s) egy k, l végpontú, útkorlátozott megbízhatósági valószínűség, a következő hálózatra:

• az élek és csúcsok: az összes P_{k,l}^{(1)}, …, P_{k,l}^{(m)}-ben levő él és csúcs

• a P_{k,l}^{(m)}-beli élek 1 valószínűséggel működnek, a többi (u, v) él a_{u,v}(s) valószínűséggel működik

• az utak, amelyekre a feladat korlátozódik: P_{k,l}^{(1)}, …, P_{k,l}^{(m−1)}

Ha ezt az útkorlátozott, két végpontú megbízhatósági problémát az előző részben leírtak szerint approximáljuk, akkor R_{i,j}^{(m)}(k, l, s) egy jó becslésével tudunk számolni. Egyszerűen ki tudjuk számolni R_{i,j}^{(m)}(k, l, s)-et, ha egy további feltevést teszünk:

F3 (Útfüggetlenség): Az, hogy egy hívást egy úton elfogadunk, statisztikailag független attól, hogy egy másik úton elfogadjuk-e.

Ez például teljesül az említett hangátviteli hálózatokra, mert ott egy út maximum két élből áll, vagyis az egy csúcspárhoz tartozó utak diszjunktak. Ha F3-at elfogadjuk, R_{i,j}^{(m)}(k, l, s)-et a következőképpen számolhatjuk ki:

R_{i,j}^{(m)}(k, l, s) = ∏_{z=0}^{m−1} (1 − ∏_{(u,v)∈P_{k,l}^{(z)},(u,v)≠(i,j)} a_{u,v}(s))

Sajnos a tapasztalatok azt mutatják, hogy ha az F3 feltevést elfogadjuk, akkor a megbízhatósági valószínűségre rossz becsléseket kapunk, tipikusan jóval kisebbeket a valós értéknél. Ha azonban F3-at csak az R_{i,j}^{(m)}(k, l, s) kiszámolásánál használjuk, a megbízhatósági valószínűség becslésénél nem, elfogadható becsléseket kapunk. Belátható, hogy így tipikusan alulbecsüljük a megbízhatóság valószínűségét. (ld. [15])

Érdemes megjegyezni, hogy ennél a leképezésnél nem használtuk ki, hogy a hívás időtartama exponenciális eloszlású.

6.3.2 Beérkezési paraméterek→elfogadási valószínűségek

Nincs kontroll

Ha nincs kontroll, a klasszikus szorzat-formulák írják le a hívás elfogadásának valószínűségét [21]. Létezik továbbá egy egyszerű rekurzió, amellyel gyorsan kiszámolhatóak ezek a valószínűségek [20]. A jelölés egyszerűsítése érdekében a továbbiakban tekintsünk el az (i, j) indextől, úgyis csak egy fix élre összpontosítunk. Legyen n_{s} a pillanatnyilag élő s típusú hívások száma. Ekkor az összes elfoglalt egység száma: n = ∑_{s} b_{s}n_{s}. Jelöljük P (n)-nel annak a valószínűségét, hogy n egység foglalt. Az említett rekurzió:

nP (n) = ∑_{s} b_{s}ϱ(s)P (n − b_{s}) n = 0, …, C

ahol ϱ(s) = ν(s)/μ(s), és P (n) = 0, ha n < 0, valamint

∑_{n=0}^{C} P (n) = 1

Az elfogadás valószínűségét a következőképpen fejezhetjük ki:

a(s) = 1 − ∑_{n=C−b_{s}+1}^{C} P (n) = ∑_{n=0}^{C−b_{s}} P (n)

Egy élre az a(s)-ek kiszámolása O(CS) ideig tart.

Van kontroll

Ha kontrollt alkalmazunk az elfogadásnál, a szorzat-formula nem marad igaz, így a rekurziót sem alkalmazhatjuk. Ehelyett megtehetjük, hogy egy {(n_{1}, …, n_{S}) : ∑_{s} b_{s}n_{s} ≤ C, n_{s} ≥ 0} értékeket felvevő S-dimenziós Markovláncnak tekintjük a foglaltsági folyamatot, és ennek a stacionárius eloszlását számoljuk ki. A baj az, hogy ez túl sok számolással jár, különösen, hogy ezt minden élre el kell végezni. Nekünk olyan módszer kellene, amely C-ben lineáris idejű. Egy sikeres megközelítés található [1]-ben: transzformáljuk a problémát egydimenzióssá! Ehhez fel kell tennünk a következőt:

• az n_{s}-ek egymáshoz viszonyított aránya nem, vagy csak nagyon keveset változik, ahogy n értéke változik.

Jelöljük α(s)-sel az s típusú élő hívások átlagos számát (α(s) = E(n_{s})). A születési és halálozási folyamatok egyensúly egyenletéből (ld. például [22]):

α(s) = a(s)\frac{ν(s)}{μ(s)}  (6.1)

Tegyük fel, hogy α(s) ismert minden s-re, és tekintsük azt a Markov-láncot (ez lényegében egy általánosított születési-halálozási folyamatnak tekinthető), amely értékei {0, 1, …, C}, és ha az n állapotban van, akkor átugorhat

• az n + b_{s} állapotba ν(s)I(C − n − r ≥ b_{s}) infinitezimális arány mellett

• az n − b_{s} állapotba μ(s)n_{\frac{α(s)}{∑_{t} α(t)}}I(n ≥ b_{s}) infinitezimális arány mellett

minden s-re. A valóságban a leugrás valószínűsége n_{s}-től függ, de mi a feltevés alapján n_{\frac{α(s)}{∑_{t} α(t)}}-vel közelítettük ez utóbbi értékét.

Tegyük fel, hogy ismerjük ennek a Markov-láncnak a stacionárius eloszlását, {P (n), n = 0, …, C}-t. Ekkor az elfogadás valószínűsége

a(s) = ∑_{n=0}^{C−b_{s}−r} P (n)

A P (n), és így az a(s) kiszámolásához egy újabb fixpont rendszert oldunk meg: 6.1 alapján P (n) meghatározza α(s)-et, amely meghatározza a lánc átmenetvalószínűségeit, amelyek meghatározzák P (n)-et. Belátható, hogy ez a módszer C-ben lineáris idejű, és a becslés aszimptotikusan egzakt, ha C elég nagy és b_{s} ≪ C.

6.4 Egy konkrét példa

A csillagszerű hálózatokat vizsgáljuk [15] alapján. Ezekben (pl. 6.1 ábra) van N db. központi csúcs és N db. mellékcsúcs. A központi mag teljes gráfot alkot. Minden mellékcsúcs egy élen kapcsolódik a maghoz. Az útkiosztás az utak

[figure]

6.1 Ábra: Csillagszerű hálózat N=5 esetén

növekvő sorrendjében történik. A kontpollparaméter értéke egy fix r minden magbeli élen, ha az út nem minimális hosszú. Vagyis egy b sávszélességű hívást akkor fogad el egy magbeli él, feltéve, hogy az nem a minimális hosszúságú úton megy, ha az élen legalább b + r szabad egység van. Az összes többi esetben az r értéke 0, azaz elég b szabad egység az elfogadáshoz. Az 6.1 és a 6.2 táblázat különböző r-ekre mutatja be a két végpontú megbízhatósági valószínűségekre kapott becsléseket az eddig leírt módszert használva, illetve szimulációval.

A következő számértékek lettek használva: N = 10, C = 100 minden élre. Háromfajta hívás lehet, a sávszélességeik: b_{1} = 1, b_{2} = 2, b_{3} = 3. Minden i, j magbeli csúcspárra, és s = 1, 2, 3-ra λ_{i,j}(s) = 15, és minden i, j mellékcsúcsokra s = 1, 2, 3-ra λ_{i,j}(s) = 10. Továbbá μ_{i,j}(s) = 1 minden i, j-re, és s-re

r  magbeli csúcsok  mellékcsúcsok
1  2  3  1  2  3
5 97.96 92.26 82.94 98.04 92.54 83.50
10 97.29 92.57 86.79 97.32 92.82 86.91
15 96.74 92.47 87.51 96.75 92.48 87.52
20 96.32 92.09 87.53 96.32 92.08 87.52
25 96.06 91.82 87.42 96.06 91.81 87.40

6.1 Táblázat: A megbízhatósági valószínűségek százalékban: fixpont módszer

r  magbeli csúcsok  mellékcsúcsok
1  2  3  1  2  3
5 97.63 91.85 82.86 97.92 91.73 82.65
10 97.21 92.90 86.57 97.04 92.88 87.09
15 96.72 92.66 87.54 96.69 93.02 85.96
20 96.29 92.39 87.70 95.99 92.25 87.00
25 96.20 92.12 87.50 96.24 92.03 86.50

6.2 Táblázat: A megbízhatósági valószínűségek százalékban: szimuláció

Irodalom

[1] N. Bean, R.J. Gibbens, and S. Zachary. Asymptotic analysis of single resource loss systems in heavy traffic, with applications to integrated services networks. Adv. in Applied Prob., 27:273–292, 1995.

[2] C.E. Bonferroni. Teoria statistica delle classi e calcolo delle probabilità. Volume in onore di Riccardo Dalla Volta, Università di Firenze, 1937.

[3] G. Boole. Laws of thought, 1854. American reprint of 1854 edition, Dover, New York.

[4] G. Boole. Collected logical works. In R. Rhees, editor, Studies in Logic and Probability, volume Vol I. Open Court Publ. Co., Lasalle, 1952.

[5] G. Boole. Of propositions numerically definite. In Transactions of the Cambridge Philosophical Society, Part II, XI. 1968. reprinted as Study IV in the next reference.

[6] E. Boros and A. Prékopa. Closed form two-sided bounds for probabilities that exactly r and at least r out of n events occur. Mathematics of Operations Research, 14:317–342, 1989.

[7] E. Boros and A. Prékopa. Probabilistic bounds and algorithms for the maximum satisfiability problem. Annals of Operations Research, 21:109– 126, 1989.

[8] Dawson D.A. and Sankoff. An inequality for probabilities. Proc. Am. Math. Soc., 18:504–507, 1967.

[9] H.P. Edmundson. Bounds on the expectation of a convex function of a random variable. Technical report, The Rand Corporation Paper 982, Santa Monica, CA, 1956.

[10] M. Fréchet. Les probabilités associées a un systèm d’événement compatibles et dépendants. Actualités Scientifique et Indrustielles, (Nos. 859, 942), 1940. 1943.

[11] J. Galambos. Bonferroni inequalities. Annals of Probability, 5:577–581, 1977.

[12] J. Galambos and R. Mucci. Inequalities for linear combinations of binomial moments. Publ. of Math., 27:263–269, 1980.

[13] D. Gale. A theorem on flows in networks. Pacific J. Math, 7:1073–1082, 1957.

[14] I. Gessel and G. Viennot. Binomial determinants, paths, and hook length formulae. Advances in Mathematics, 58:300–321, 1985.

[15] A.S. Greenberg and R. Srikant. Computational Techniques for Accurate Performance Evaluation of Multirate, Multihop Communication Networks. AT&T Bell Laboratories, 1994. kézirat.

[16] J.L. Jensen. Sur les fonctions convexes et les inégalités entre les valeurs moyennes. Acta Math., 30:175–193, 1906.

[17] C. Jordan. De quelques formules de probabilité. Comp. Rend. Acad. Sci. Paris, 65:993–994, 1867.

[18] C. Jordan. Calculus of Finite Differences. Chelsea, New York, 1947.

[19] K. Jordán. A valószínűségszámítás alapjai. Matematikai és Fizikai Lapok, 34:109–136, 1927.

[20] J.S. Kaufman. Blocking in a shared resource environment. IEEE Trans. Commun., COM-29:1474–1481, October 1981.

[21] F.P. Kelly. Loss networks. The Annals of Applied Probability, 1(3):319–378, August 1991.

[22] L. Kleinrock. Sorbanállás, kiszolgálás. Műszaki Kiadó, Budapest, 1979.

[23] S.M. Kwerel. Most stringent bounds on aggregated probabilities of partially specified dependent probality systems. Journal of the Am. Stat. Assoc., 70:472–479, 1975.

[24] C.E. Lemke. The dual method for solving the linear programming problem. Naval. Res. Logist. Quart., 1:36–47, 1954.

[25] A. Madansky. Bounds on the expectation of a convex function of a multivariate random variable. Ann. Math. Statist., 30:743–746, 1959.

[26] T.F. Móri and G.J. Székely. A note on the background of several Bonferroni-Galambos-type inequalities. Journal of Applied Prob., 22:836–843, 1985.

[27] A. Prékopa. Boole-Bonferroni inequalities and linear programming. Operations Research, 36:145–162, 1988.

[28] A. Prékopa. The discrete moment problem and linear programming. Discrete Applied Mathematics, 27:235–254, 1990.

[29] A. Prékopa. Sharp bound on probabilities using linear programming. Operations Research, 38:227–239, 1990.

[30] A. Prékopa. Stochastic Programming. Akadémiai Kiadó, Budapest, 1995.

[31] A. Prékopa and E. Boros. On existence of a feasible flow in a stochastic transportation network. Operations Research, 39:119–129, 1991.

[32] A. Prékopa, E. Boros, and Keh-Wei Lih. The use of binomial moments for bounding network reliability. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 5:197–212, 1991.

[33] J. Riordan. Combinatorial Identities. Wiley, New York, 1968.

[34] Y.S Sathe, M. Pradhan, and S.P. Shah. Inequalities for the probability of the occurrence of at least m out of n events. Journal of Applied Probability, 17:1127–1132, 1980.

[35] G. Stoyan and G. Takó. Numerikus módszerek. ELTE-Typotex, Budapest, 1993.

[36] L. Takács. On the method of inclusion and exclusion. Journal of the Am. Stat. Assoc., 62:102–113, 1967.