Scrigroup - Documente si articole

Username / Parola inexistente      

Home Documente Upload Resurse Alte limbi doc  

Statistica


COMPACTITATEA SPATIULUI STRATEGIILOR STATISTICE

Statistica

+ Font mai mare | - Font mai mic




COMPACTITATEA SPATIULUI STRATEGIILOR STATISTICE




Fie problema de decizie statistica [(H, T , Q), (X, K P ), (D, D S), L].

Daca functia de pierdere L(h,d) este marginita in raport cu h si d atunci ea determina urmatoarele semimetriei pe cele doua spatii H si D.

d (h1,h2)=

d (d1, d2)=

Aceste doua semi-metrici determina doua metrici pe multimea claselor de echivalenta determinate de ele. Se numeste acoperire numarabila a spatiului deciziilor, sirul cu proprietatile: unde ,1, ,2,, ,km sunt disjuncte diam( ) 0 cand m si reprezinta diametrul multimii .

Definitia 1.1. Fie structura statistica discreta a observatiilor (X, K P) si structura statistica a deciziilor (D, D S) cu spatiul deciziilor, spatiu metric compact in raport cu metrica dD indusa de functie de pietre L. Sirul de strategii statistice S converge catre strategia statistica S0IS daca, =S0(x,A) xIX AID, A-multime deschisa si S0(x, A)=0.

Observatie. Aceasta convergenta o vom numi convergenta regulata. Aceasta definitie este foarte restrictiva in cazul absolut continuu.

Definitia 1.2. Fie structura statistica a observatiilor (X, K P) dominata de probabilitatea privilegiata P* si structura statistica a deciziilor (D, D S cu spatiul deciziilor D compact in raport cu metrica indusa de functia de pierdere L. Sirul de strategii statistice S converge catre strategia statistica S0I S daca, exista o acoperire numarabila , astfel ca:

=P( ) AIK I

unde     P(D )= .

Teorema 1.3. Daca structura statistica a observatiilor (X, K P ) este discreta si spatiul deciziilor din structura statistica a deciziilor (D, D S este un spatiu metric compact in raport cu metrica indusa de L, iar spatiul strategiilor S este inchis in raport cu convergenta regulata, atunci spatiul strategiilor statistice S este compact, in raport cu convergenta regulata.

Demonstratie. Presupunem ca spatiul observatiilor X este format numai din numere intregi pozitive, adica elementul aleator X este discret. Deoarece spatiul deciziilor D este complet, atunci exista o submultime compacta D0 D astfel ca: S(x,D0)=1 xIX SIS. Fie xIX si sirul de strategii statistice S deoarece D0 este compacta si S inchisa, atunci sirul Si(x, ) contine un subsir (Sij(x, ) care converge catre strategia statistica S0(x, ), adica: S0(x,B) BI K S0(x, B0)=0. Deoarece este numarabil din subsirul astfel ca: Sij(x,B) S0(x,B) xIX, BID, S0(x, B)=0.

Teorema 1.4. Daca structura statistica a observatiilor (X, K P ) este dominata si spatiul deciziilor D din structura statistica a deciziilor (D, D S este un spatiu metric compact in raport cu matricea metrica indusa de L, iar spatiul strategiilor S este inchis in raport cu convergenta regulata atunci spatiul strategiilor S este compact in raport cu convergenta regulata.

Demonstratie. Fie P* masura de probabilitate care domina structura statistice a observatiilor. Fie sirul de strategii statistice S si subsirul (sij)j=1 ( (Si) ales astfel ca:

lim P(B|C, Sij)=P (B C) BID, B deschisa si P (C B)=0, CIK, C cub cu varfurile rationale.

Deoarece C este numarabila si spatiul tuturor masurilor de probabilitate definite pe un spatiu compact este compact (teorema 6.4. [111] atunci subsirul este construit cu ajutorul procedurii de diagonalizare. Pentru orice B probabilitatea P (B|C) definita pentru toate cuburile cu varfurile rationale poate fi extinsa la o functie de multime complet aditiva, P (B C), BIK

Notam pe P (B C) , BIK. cu

P(B/C)= P (C B)

Alegem acoperirea numarabila care satisface restrictiile:

a) Pentru orice element al acoperii numarabile exista o multime deschisa notata astfel ca:

b) P ( B BIK I( )

Din relatiile (1), (2) si restrictia (b) rezulta ca: =P(B ) BIK si B marginita. Proprietati ale functiei de multime:

i) P(B )

ii) P(B )=P( )

Fie Z un element al sirului ( ) si (Zi) un subsir al sirului ( ) astfel ca Zi Zj= i j, Z= Deoarece functia de multime P(B D) este complet aditiva, avem

iii) P(B Z)= .

Pentru orice multime BID din teorema lui Radon-Nicodim [95] rezulta ca exista functia S (x,B)=(dP(x,B)/dP*)(x)

Din i, ii si iii rezulta ca pentru orice x fixat, S este o probabilitate, iar ca functie de x este o functie masurabila deci S w,D) este o strategie statistica

IV) S (x, )

V) S (x, )= S (x, )

VI) S (x,Z)= , Zj Zi= , i j, Z=

Si din restrictia b rezulta ca S (x, )= S (x, )= S (x, ) xIX. Pentru orice multime deschisa ZID , Z ( ) si orice xIX fie

VII) S0(x,Z)=

Pentru orice xIX, S0(x,Z) poate fi extinsa la o functie de multime complet aditiva S0(x, b) definita pentru orice BID . Din relatiile VI si VII rezulta ca:

VIII) S0(x, )=S (x, )

Deoarece . S (x, )= S (x,B)=S0(x,B).

Din VIII rezulta ca: S0(x, )=0. Prin urmare

S0(x, )=S (x, / S (x,D)

Din constructie si din proprietatile IV-VI rezulta ca S0(w,D) este o strategie statistica.

Deci ( B,Sij)=P( B,S0), BIK I

2 Compactitatea slaba a spatiului strategiilor

Definitia 2.1. Sirul de strategii statistice converge intrisec catre strategia S0IS daca =r(h,S0) uniform in raport cu h.

Definitia 2.2. Sirul de strategii statistice S converge catre strategia S0 in raport cu probabilitatea apriori Q (Q-converge) daca =R(Q,S0).

Definitia 2.3. Sirul de strategii statistice (Si) S converge slab intrisec daca

R(Q,Si) R(Q,S0) QIQ.

Spatiul S este slab intrisec compact daca orice sir contine subsir slab intrisec este convergent catre S0.

Propozitia 2.4. Daca sirul de strategii statistice converge intrisec atunci -Q-converge catre strategia S0.

Demonstratia evidenta.

Teorema 2. Fie structura statistica discreta (X, K P) a observatiilor, iar spatiul deciziilor D din structura statistica a deciziilor este un spatiu metric compact in raport cu metrica indusa de functia de pierdere L.

a) Daca sirul de strategii statistice converge catre strategia S0, atunci Si converge slab catre S0;

b) Spatiul strategiei statistice S este compact in sensul slabconvergentei.

Demonstratie. Fie probabilitatea apriori Q pe spatiul starilor (H,T si sirul de strategii statistice ales astfel ca R(Q,Si)< i.

Deoarece Si converge catre S0 rezulta ca Si(x,B)=S0(x,B) xIX, BID, deschisa S0(x, B)=0

Fie PhIP puterea caracteristica a strategiei statistice

P(B h,Si)= dPh(x).

Din teoremele 1.3. si 1.4. rezulta ca

=P(B h,S0) h, BID, B deschisa si P( B h,S0)=0

Deoarece L(h,d) este continua si D compact rezulta ca:

=

Punctul b este o consecinta punctului a si a teoremelor 1.3. si 1.4.

Separabilitatea intriseca a spatiului starilor

Presupunem ca probabilitatea ca experimentarea sa fie realizata in cel mult n etape cand se utilizeaza strategia S este 1. Vom utiliza metricile urmatoare:

d1(h1,h2)= ,

d2(h1,h2)= ,

d3(h1,h2)= ,

d4(h1,h2)= d1(h1,h2)+ d3(h1,h2).

Teorema 3.1. Fie structura statistica a observatiilor (X, K P ) dominata si spatiul deciziilor D din structura statistica a deciziilor (D, D S este metric compact in raport cu metrica indusa de functia de pierdere marginita L. Atunci, spatiul starilor H este spatiu metric separabil in raport cu metrica d2.

Demonstratie. Din teorema 1.3.11 rezulta ca H este separabil in sensul metricii d1.Fie metrica: d4(h1,h2)= d1(h1,h2)+ d3(h1,h2).Vom arata ca H este de asemenea separabil in sensul metrici d4(h1,h2). Deoarece D este compact, rezulta din teorema 2.1. [111] spatiul H este conditional compact in sensul metricii d3(h1,h2). Prin urmare, pentru orice e > 0 este posibil sa impartim spatiul starilor H intr-un numar finit de submultimi disjuncte H1, H2, H3,, Hm astfel ca diametrele multimilor Hi in raport cu metrica d3 sa fie mai mici decat e.Deoarece H este separabil in sensul metricii d1, exista o submultime numarabila H i Hi densa in Hi in raport cu metrica d1.Fie



H 0=

Evident H0 este numarabila si 2e-densa in sensul metricii d4. Teorema este demonstrata daca vom arata ca, daca in sensul metricii d4, atunci in sensul metricii d2. Fie un sir, astfel ca e> exista n(e) astfel ca d4(hi,h0) e, d4(hn,h0)< e cand n>n(e) atunci:

1) uniform in raport cu d si de indata ce n>n(e

uniform in raport cu AIK

Fie M(h,L S,x)= media conditionata a lui L cand este adoptata strategia

statistica S si rezultatul experimentului este x. Din teorema lui Fubini rezulta ca

r(h,S)=

Din relatia (1) rezulta ca:

M(hi,L S,x) uniform in raport cu S si x.

Dar dPh(x)<e pentru i>n(e SI S

Din relatia 2 rezulta ca:

6) uniform in raport cu S.

Din relatiile 4.6. rezulta ca: .

Strategii statistice optime

Problema de decizie statistica [(H, T), Q, (X, K P), (D, D S L] se numeste regulata daca structura statistica a observatiilor este discreta sau dominata de o probabilitate privilegiata P*, functia de pierdere L este marginita in h, spatiul deciziilor D este compact in raport cu metrica indusa de L, spatiul strategiilor S este convex si inchis in raport cu convergenta regulata.

Teorema 4.1. Fie problema de decizie statistica regulata

[(H, T), Q, (X, K P), (D, D S), L] care indeplineste conditiile de mai sus, atunci exista o strategie optima S0 in raport cu .

Demonstratia rezulta imediat din teorema 1.3, 1.4. si 2. Functia de pierdere fiind marginita atunci functia de risc (r(h,S)) este marginita si ne permite sa definim o metrica in spatiul starilor notata cu r, numita metrica intriseca.

r (h1, h2)=

Definitia 4.2. Fie problema de decizie statistica [(H, T), Q, (X, K P), (D, D S), L) (H, r), . Se spune ca sirul Qi converge in sens ordinar catre Q0 daca oricare ar fi AIT, A deschisa, Q0( )=0 adica Qi T Q0.

Teorema 4.3. Fie problema de decizie statistica regulata

[(H, T, Q), (X, K P), (D, D S), L] si daca converge in sens ordinar, atunci .

Demonstratie rezulta din teorema 3.1. si teorema 2.14.[111].

Teorema 4.4. Fie problema de decizie statistica regulata

[(H, T, Q), (X, K P), (D, D S), L] si pe spatiul strategiilor statistice S definita preordinea atunci exista o strategie statistica S0 astfel ca SI S

Demonstratie. Fie sirul de strategii statistice S astfel ca =

Deoarece S este compact in raport cu metrica intriseca (teorema 2.5), rezulta ca exista un subsir de strategii statistice astfel ca:

hIH.     (1)

Din relatia (1) rezulta ca:

r(h S0) , hIH si deci S0 S SIS

Teorema 4. Fie problema de decizie statistica regulata,

[(H, T, Q), (X, K P), (D, D S), L] daca Q0 este probabilitatea apriori care mai putin favorabila, atunci orice strategie optima in raport cu relatia atunci este optima in raport cu .

Demonstratie. Deoarece Q0, este probabilitatea apriori cea mai putin favorabila

= . Fie S0 optima in raport cu relatia atunci = si din teorema 3.4.[111] rezulta R(Q0,S0) de unde

rezulta ca S0 S, SI S.

Teorema 4.6. Fie problema de decizie statistica regulata,

[(H, T, Q), (X, K P), (D, D S), L] si Q0 probabilitatea apriori cea mai putin favorabila si S0 este o strategie optima in raport cu relatia de m-preferinta atunci

Q0( (2)

Demonstratie. Din teorema 4. rezulta ca = care implica =r(Q0,S0). Insa aceasta are loc daca are loc (2) si teorema este demonstrata. Se spune ca starea h este degenerata daca exista o multime deschisa in raport cu r, H astfel ca Q( )=0.

Teorema 4. Fie problema de decizie statistica regulata.

[(H, T, Q), (X, K P), (D, D S), L si Q0 o probabilitate apriori cea mai putin favorabila si S0 este optima in raport cu relatia de preordine atunci r(h S0)= r(h S0) hIH

Demonstratie. Presupunem ca exista o stare h IHN(Q0) unde N(Q0) este deschisa in raport cu metrica indusa de functia de risc cu Q(N(Q0))=0 si r(h S0)< si pentru hIH H h IH rezulta

r(h S0)< hIH .Deoarece h0IN(Q0) avem

Q0(H )>0.    (4)

Relatiile (3) si (4) contrazic teorema 4.6.

Fata de ipotezele facute la inceputul paragrafului se va presupune ca, convergenta regulata implica convergenta uniforma in raport cu functia de pierdere.

Teorema 4.8. Fie problema de decizie statistica regulata [H T, Q), (X K P ) D D S), L] si (Qi) astfel ca TIT. Q0- continua in raport cu metrica intrinseca. Atunci:

(i)         R(Qi,S) R(Q0,S) uniform in raport cu S,

(ii)       = si

(iii)     R(Q0,S).

Demonstratie. Deoarece convergenta regulata implica =L(h,d) rezulta ca uniform in raport cu S. Demonstratia este analoaga cu cazul secvential.

Teorema 4.9. Fie problema de decizie statistica regulata [H T, Q), (X K P D D S), L] in care convergenta regulata implica convergenta uniforma in raport cu functia de pierdere si H este compact. Atunci exista o probabilitate apriori cea mai putin favorabila

Demonstratie. Fie un sir de probabilitati astfel ca

Deoarece H este convergent, exista un subsir astfel ca:

TIT deschisa cu proprietatea Q0( (6)

Din teorema 4.8, rezulta:

.

Din relatiile (5) si (7) rezulta ca teorema este demonstrata. Fie Q0 o multime numarabila de probabilitati apriori si QH - multimea probabilitatilor punctuale. Presupunem ca exista un sir de probabilitati apriori care este dens in QT=Q0 QH in raport cu semimetrica indusa de riscul mediu d(Q1,Q2)=

Teorema 4.10. Fie structura statistica a starilor (Q,T, QT). daca problema de decizie statistica este regulata [(Q, T, QT), (X K, P ), D D S), L] atunci exista o strategie m-preferata S0 si un sir de strategii statistice astfel ca limSi=S0, si pentru orice i, Si este o strategie b-preferata in raport cu Qi, care este o combinatie convexa de un numar finit ni de probabilitati din Q0

Demonstratie. Fie Sj o strategie m-preferata in raport cu Qj= adica

SI S (8)

deoarece Q este finita si deoarece problema de decizie este un joc finit cu suma nula rezulta ca exista a a aj ak>0, 1 k j, astfel ca R(Q ,Sj) R(Q ,S) SI S unde Q

Adica Sj este o strategie optima in raport cu relatia . Fie S0 limita unui subsir de strategii statistice a lui (Si) in sensul convergentei regulate. Deoarece convergenta regulata implica convergenta slab-intrinseca [din teorema 2.] si din (1) rezulta ca

R(Qi,S0) R(Qi,S) SI S .

din teorema 3.4 pagina 88 [111] rezulta ca R(Qi,S)= deoarece pentru strategia m-preferata S0 nu se impun restrictii asupra probabilitatilor apriori care intervin in relatia (8) teorema este demonstrata.

Daca spatiul starilor H este separat in sensul semimetricii induse de functia de risc r(h,S) atunci fie multimea H densa H in atunci multimea (Q= ) este densa in QH in sensul riscului mediu.

Definitia 4.11. Fie problema de decizie regulata H T, Q), (X K P ) D D S), L].

(i) Strategia statistica Sb se numeste b-optima, daca exista probabilitatea apriori Q astfel ca Sb sa fie optima in raport cu .

(ii)    Strategia statistica Sm se numeste m-optima daca este optima in raport cu relatia

Fie SB multimea tuturor strategiilor statistice SIS pentru care functia de risc r(h,S) este marginita in raport cu H

Teorema 4.12. Daca o problema de decizie statistica este regulata, atunci multimea strategiilor statistice slab b-optime formeaza o clasa completa relativ la SB

Demonstratie. Fir SI SB si care nu este o strategie slab b-optima. Fie L*(h,S)=L(h,S)-r(h,S)



Daca in problema de decizie regulata initiala inlocuim functia de pierdere L cu L* obtinem o noua problema de decizie regulata. Deoarece noua problema de decizie statistica este regulata atunci exista o strategie statistica Sm m-optima. Existenta strategiei statistice m-optime Sm rezulta din teorema 4. Din teorema 4.6. rezulta ca strategia Sm este slab-b-optima. Deoarece S nu este o strategie slab b-optima rezulta ca exista cel putin o stare astfel ca functia de risc r*(h,S) corespunzatoare functiei de pierdere L* sa devina r*(h,S)=r(h,S)-r(h,S0) deoarece r*(h,S0)=0 si S0 este o strategie m-optima rezulta r*(h,Sm)= r(h,Sm)- r(h,S0) hIH.

Din relatiile (1) si (2) rezulta ca Sm>S0 deci ne-au dat o strategie S0ISB care nu este slab b-optima si exista o strategie Sm slab b-optima astfel ca Sm>S ceea ce trebuia demonstrat.

Fie Qd familia tuturor probabilitatilor apriori Q cu proprietatea ca oricare ar fi QIQd exista o submultime finita Hf H astfel ca Q(Hf) =1, cu alte cuvinte tripletul (H, T, Qd) formeaza o structura statistica discreta. Fie multime strategiilor optime in raport cu relatia pentru orice QI Qd.

Teorema 4.13. Daca problema de decizie statistica este regulata, atunci este o clasa esential completa in raport cu SB

Demonstratie. Am notat cu inchiderea multimii in raport cu convergenta regulata. Fie S0I S B, L*(h d L(h d r(h S0). Deoarece problema de decizie statistica obtinuta prin inlocuirea functiei de pierdere L cu L* este regulata si deoarece familia Q contine multimea probabilitatilor punctuale rezulta din teorema 4.10. ca exista o solutie m-preferata S a problemei de decizie in care L s-a locuit cu L* care este un element al lui . Deoarece r*(h S0)=0 hIH avem r*(h Sm)= r(h Sm)-r(h S0) hIH adica Sm>S0 ceea ce trebuie demonstrat.

Fie Q0 multimea tuturor probabilitatilor apriori cu proprietatea ca, pentru orice Q0 Q exista un sir Q astfel ca: limQi(T)=Q0(T) TIT..Fie multimea strategiilor optime in raport cu relatia , QIQd.

Teorema 4.14. Daca problema de decizie statistica est regulata atunci este o clasa esentiala completa in raport cu S B

Demonstratie. Fie strategia statistica S0ISB si functia de pierdere L*(h d L(h d r(h S0) cu functia de risc asociata r*(h S). problema de decizie obtinuta prin schimbarea lui l cu L* este de asemenea regulata. Daca

=Q0(T) T atunci d(Qi,Q0)= -r(Q0,S) cand i

Din teorema 4. rezulta ca exista o strategie m-optima SmI . Deoarece r*(h S0)=0 hIH si r*(h S0)= r(h Sm)-r(h S0) 0. Rezulta Sm>S0 ceea ce trebuie demonstrat.

Teorema 4.1 Daca problema de decizie statistica este regulata atunci clasa strategiilor statistice b-optime este o clasa completa in raport cu S B

Demonstratie. Deoarece problema de decizie este regulata din teorema 4.11. rezulta ca clasa strategiilor slab b-optime este b-optima, deci clasa strategiilor b-optime este completa in raport cu S B

7 Criteriu iterat de regret minimax

O abordare rationala a problemelor de decizie consta in determinarea unui criteriu care sa satisfaca anumite proprietati. Chernoff in [17] da o lista de proprietati pentru jocuri contra naturii finite, care a fost extinsa pentru s-jocuri de Atkinson modificand si lista de proprietati.

Aceasta a fost adoptata pentru probleme de decizie de Nordbroc [80] si extinsa deV. Preda [88], [86]. In continuare se considera criteriul iterat de regret minimax care este extins pentru decizii pe structuri statistice, si algoritmizat in vederea rezolvarii lui practice cand spatiile S si H sunt finite.

Fie problema de decizie statistica [(H, T), (X, K P), (D, D S , L] W= multimea functiilor de risc, corespunzatoare strategiilor statistice SI S

Ipoteza de marginire a functiei de pierdere L implica marginirea multimii W si de asemenea, ipoteza de convexitate a multimii de strategii S implica convexitatea multimii W.Presupunem ca, intre clasele de echivalenta a strategiilor statistice si multimea W exista o corespondenta bijectiva.

Este evident ca, orice preordine introdusa in multimea W induce o preordine in multimea strategiilor statistice S, astfel se va considera problema de decizie caracteristica numai de multimile (H,W).

Definitia 1. Fie r1,r2 IW, r1<r2 daca si numai daca r1(h) r2(h), hIH si exista cel putin o stare astfel ca r1(h) r2(h).

Definitia 2. Fie rIW, r se numeste admisibil, daca nu exista IW astfel ca >r.

Definitia 3. Fie C W se numeste completa daca oricare ar fi rIWC exista I C astfel ca >r.

Pentru orice problema de decizie statistica se considera multimea B= cu urmatoarea norma =

Definitia 4. Pentru orice B1, B2 B,

d(B1, B2)=max , unde d(f1,f2)=

Un criteriu de alegere a unei strategii optime care este o relatie de preordine imparte multimea S in multimea strategiilor optime si neoptime. Vom nota cu W0 W care este optim in raport cu preordinea introdusa.

Se dau in continuare proprietatile pe care trebuie sa le satisfaca un criteriu.

P.1. Pentru orice problema de decizie W0

P.2. Pentru orice problema de decizie (H,W),W0 este convexa

P.3. Daca (H,W) si (H ,W ), h: H H bijectiva si daca W0oh atunci si W =W0 h

P.4. Daca (H,W) si (H ,W a> fix , b H E1 o functie fixata oarecare, atunci si W aW+b si atunci W0 aW0+b

P. Daca (H ,W) si (H,W H) unde HIH . Daca pentru orice rIW r este masurabila in raport cu s-algebra T de submultime din H si daca pentru orice hIH exista probabilitatea astfel ca , rIW, atunci , unde s-a notat cu multimea optima pentru (H ,W) si cu W0 multimea optima pentru ( ).

P.6. Daca (H,W), (H,W(n)), n=1,2,..d(W,W(n)) cand n si daca rnIW(n)0 si d(rn,r) 0, cand n atunci rIW0.

P. Orice rIW0 este admisibila.

P.8. Daca (H,W), (H,W ) si C este o clasa completa in ambele probleme, atunci W0=W

Proprietatea P.1. Pentru o problema de decizie statistica asigura existenta unei solutii optime in raport cu criteriu dat.

Proprietatea P.2. Cere convexitatea multimii functiilor de risc, care este indeplinita daca spatiul S este convex sau liniar, deoarece r(h,S) este o functie liniara in raport cu S.

Proprietatea P.3. Arata ca multimea solutiilor optime nu depinde de renumerotarea starilor.

Proprietatea P.4. Arata ca definirea valorii zero si a unitatii pentru functia de utilitate sunt irelevante, adica este unica incepand o transformare de tipul celei din propozitia 2.4.3.

Proprietatea P. Contine cazul special al duplicarii naturii.

Proprietatea P.6. Cuprinde notiunea ca un criteriu nu ar selecta strict multimile optime care ar semana foarte mult.

Proprietatea P. Arata ca strategiile optime care nu sunt si admisibile sunt neinteresante.

Proprietatea P.8. Arata ca multimea strategiilor optime nu depinde decat de strategiile importante, adica de deciziile dintr-o clasa completa.

Definitia Fie un sir de numere pozitive care converge la zero si problema de decizie caracterizata de multimile (H,W).Criteriu iterat de regret minimax (IMR) corespunzator sirului selecteaza si o multime optima IMR(en)W=W0 pe baza algoritmului dat mai jos.

0 START[IMR]

1 INPUT

2 K=IMR(en)W     //satisface P.1, adica W0

3 W1 W

4 v1(h)

5 z1

6 IF z1 LS

6.1 W0←W1

6.2 n←1

Else

7 WHILE n< Ni

1 Wn+1

2 n←n+1

3 vn(h):=

4 zn

5 W0 W0 Wn

OUTPUT

9 STOP

Observatie. LS reprezinta limita superioara pentru distanta z care, teoretic poate lua valoarea si Ni reprezinta numarul de iteratii pentru criteriu care de asemenea poate fi In continuare se dau conditii suficiente pentru ca acest criteriu sa satisfaca cele 8 proprietati. Fara alte conditii in plus s-ar putea ca W0= (a se vedea exemplele din [80])

Definitia 6 Fie multimea functiilor de risc W atasata unei probleme de decizie, W se numeste intrisec slab compacta daca pentru orice sir exista un subsir si rIW astfel ca , hIH.

Teorema 7 Daca (H,W) satisface proprietatea P.1. si W este slab compacta, atunci W0 este slab compacta.

Demonstratie. Daca z1= , atunci W0=W si teorema este demonstrata. Vom arata prin inductie ca WN este nevida si slab compacta. Evident, WM+1 este nevida si fie astfel ca hIH deoarece aceasta implica , hIH si deci rIWN+1, deci WN+1 este intrinsec slab compact. Astfel, prin inductie Wn este nevida si intrinsec slab compacta pentru orice n. Fie un sir cu rnIWn. Deoarece W1 este intrinsec slab compacta, rezulta ca exista un subsir si rIW1, astfel ca

, hIH.

Presupunand ca rIWN rezulta ca rIWN+1 si prin inductie rIWN pentru orice n si deci W0

Sa aratam ca W0 este intrinsec slab compact, fie , atunci rnIWn pentru orice n si ca mai sus putem gasi un subsir si rIW astfel ca , hIH, prin urmare W0 este intrinsec slab compact.

Proprietatea P.2. este o verificare simpla pentru multimea optima W0 in raport cu criteriul W0.

Teorema 8. Fie (H, W) care satisface P.1. atunci W0 este convexa.

Teorema 9. Fie (H,W ) o problema de decizie care satisface P.1. si h: H H o functie bijectiva. Definim W din W =W0 h, si problema (H,W) atunci W =W0 h.

Demonstratie. Este evident ca v =v1 h si z =z1. astfel daca z1=z deoarece multimile optime coincid cu multimile W si W , rezulta ca W =W0 h. Daca z1=z < rezulta prin inductie ca W n=Wn h pentru orice n, W =W0 h si deci teorema este demonstrata.

Vom arata ca acest criteriu satisface proprietatea P.4. (schimbarea scalei si originii) intr-o problema de decizie.

Teorema 10. Fie (H,W) care satisface ipoteza P.1. si a>0 si b H e fixe. Punand W aW+b si considerand problema (H,W ) atunci (H,W ) satisface P.1. si W aW0+b

Demonstratie. Se arata ca, v av1+b si z az1, prin urmare teorema este adevarata cand; daca z1< prin inductie rezulta ca W n aW+b, din care rezulta teorema.

Se va arata ca acest criteriu satisface proprietatea P.(duplicarea naturii) intr-o problema de decizie generala.

Teorema 11. Fie (H ,W ) care satisface ipoteze P.1. Fie HIH si problema de decizie (H,W) unde W=W H . Presupunem ca pentru orice h IH exista o probabilitate Q0 pe H astfel ca pentru orice rIW sa avem r(h )= . Atunci W H=W0.



Demonstratie. Multimea W0 este multime optima in raport cu criteriu interesat de regret minimax pentru problema de decizie generala (H,W) si respectiv W multimea optima pentru problema de decizie caracterizata de (H ,W ). Deoarece si z =z1, atunci cand z1= . Teorema este demonstrata.

Daca z1< se utilizeaza inductia pentru a arata ca Wn= W n H pentru W, din care rezulta teorema.

Vom arata ca IMR satisface ipoteza P.6. de continuitate daca W este inchisa.

Teorema 12. Fie (H,W) si (H,W(N)) pentru N=1,2,3, cele doua probleme de decizie care satisfac ipoteza P.1. si d(W,WN) 0 cand N . Presupunem ca z1< atunci

n

n

n

Demonstram mai intai ca: a) d( 0 si z1 cand N . Fie N suficient de mare, astfel ca d( ,W)<e atunci pentru orice h dat exista r1IW1, astfel ca r1(h v1(h e exista I , astfel ca h v1(h e Astfel (h) v1(h)+e. Similar, v1(h) (h)+2e si rezulta ca d( ,v1) Pentru a arata ca z1, se observa ca z1 d(v1, e< e pentru N suficient de mare. Similar z1+2e si prin urmare z1.

b) Sa aratam ca d( ,W2) 0 cand N . Cand z1=0, avem ca W2= atunci pentru orice I avem d(v2, ) d(v1, )+ +e1 si trecand la limita, rezulta d( ,W2) 0 daca z1>0 fie e>0, dat, si presupunem ca (e z1+e z1. Fie a= .Fie N suficient de mare, astfel ca: d(W1, a/9, d(v1, a/9, |z1 a/18, e |z1 18, z1/2< <3z1/2.

c) Se arata ca . Fie r un element arbitrar din W2.

c1) Daca d(v1,f) z1+e z1a/3 alegem rNI astfel ca d(r,rN) a/9+e/2 si se observa ca rNI

c2) Daca d(v1,r)>z1+e z1a/3 alegen un r0IW2 cu d(v1, r0)<z1+e z1/10. Daca d(r,r0) e/2 alegem ca in cazul c1, cu d(r, )<e/2 si prin urmare d(r, )<e.

Cand d(r,r0)>e/2 definim = pr0+(1-p)r, unde p=e d(r,r0). Din inegalitatea triunghiului pentru norme si deoarece d(r,r0) z1+e1z1 avem d(v1,r) z1+e z1a/3. Atunci ca si in cazul c1 se poate gasi o functie cu proprietatea d( , e/2 si de asemenea d( r, ) < e.

d) Pentru a arata ca se urmeaza o cale analoaga celei de la punctul c, utilizand in plus inegalitatea z1/2< +3z1/2. Punctele c si d demonstreaza ca d( ,W2) e

La punctele a, b si c am aratat ca d( , v) z1 si d( ,W2) 0, N

Presupunand ca rezulta ca , , . Prin urmare, din inductie rezulta ca teorema este demonstrata.

Teorema urmatoare caracterizeaza continuitatea criteriului.

Teorema 13. Fie problema de decizie caracterizata de (H,W) si (H,WN, N=1,2, care satisfac proprietatea P.1. si W este inchisa. Daca rNIWN N astfel ca d(rN,r) pentru un r atunci rIW0.

Demonstratie. Daca z1< , pentru un n fix din teorema 12. rezulta ca d( ,rN) cand N , astfel avem d( ,r) cand N si avem rIWn, prin urmare rIWn oricare ar fi n, adica rIW0. Daca z1= , in acest caz din punctul a al teoremei rezulta ca pentru orice N suficient de mare. Vom arata ca rIW1. Deoarece W1= W01 rezulta ca rIW0 si teorema este demonstrata.

Pentru demonstrarea ultimilor doua proprietati vom presupune ca W este o multime compacta.

Daca W este compacta si convexa, atunci proprietatea P.1. este satisfacuta, z1 este finit si W este slab compact. Se arata ca W0 se reduce la un singur punct care este admisibil.

Lema 14. Daca (H,W) caracterizeaza o problema de decizie si W este convexa si compacta, atunci d(vn,v) zn z si pentru orice rIW0 avem d(v,r)=z (unde z si v se refera la solutia optima rIW0).

Demonstratie. Presupunem ca . Atunci exista un subsir a lui si sirul astfel ca pentru orice k. Deoarece este compacta pentru orice k, se poate gasi un element astfel ca a stfel,

v ( )>e k.    (*)

Deoarece rezulta din compactitatea lui W ca exista un subsir convergent pentru un r0IW. Deoarece pentru , rezulta r0IWn si astfel r0IW0. Astfel pentru un numar suficient de mare v(h) r0(h) < (h e h Acesta contrazice (*) si deci d(vn,v) . Rezulta ca zn<z+e pentru orice n suficient de mare, si prin urmare z<zn, avem zn z. Deoarece en 0 din inegalitatea triunghiului rezulta d(v,r)=z pentru orice rIW0.

Teorema 1 Daca W este convexa si compacta, atunci z=0, adica W0 se reduce la un singur punct in plus ca W0 este admisibila.

Demonstratie. Presupunem z>0 si 0<e<Z. Fie h1IH si alegem r1IW0 astfel ca r1(h)=v(h1). Definim A1= si prin urmare A1 . Procedand analog, definim An si An . Alegem hn+1IA si rn+1IW0 astfel ca rn+1(hn+1)=v(hn+1). Definim An+1= . Astfel An+1 pentru ca daca ea ar fi vida, atunci ar trebui sa avem

.

Pentru orice h, ceea ce contrazice lema 14. Prin metoda de mai sus, am selectat un sir (hn H si un sir (rn) W0 astfel ca pentru m<n, rm(hn)>r(hn)+z-e si rn(hn)=v(hn). Astfel d(rm,rn) z-e pentru m n, ceea ce contrazice compactitatea lui W0. Prin urmare z=0. Sa aratam admisibilitatea, fie r0I W0 si presupunem ca r0 nu este admisibila. Atunci din definitie rezulta ca, exista r1I W. deoarece aceasta contrazice z=0, rezulta ca r0 trebuie sa fie admisibila si teorema este demonstrata. La inceput vom arata ca daca in problema de decizie (H,W), W este o multime convexa si compacta, atunci multimea S a a strategiilor statistice admisibile este o clasa compacta.

Daca problema de decizie caracterizata de (H,W ) are W convexa si compacta cu S a S atunci W =W0.

Teorema 16. Daca in problema de decizie caracterizata de (H,W) multimea W este convexa si compacta cu A este multimea strategiilor admisibile in W, atunci A este o clasa compacta.

Demonstratie. Fie rIW/A si Tr= . Multimea Tr W convexa si compacta. Astfel fie problema de decizie caracterizata de (H, Tr W) care are W cu r0 admisibila in Tr W. Daca exista r1ITr W, r1>r0, atunci r1ITr W, ceea ce contrazice ca r0 este admisibila in raport cu (H Tr W) prin urmare r0 este admisibila in raport cu (H, W) si rezulta ca este o clasa completa, ceea ce trebuia demonstrat.

Definitia 1 Fie problemele de decizie si (H, W ) definim An(clasele admisibile corespunzatoare in Wn,(W n), n=1,2,r An daca nu exista r0IWm, astfel ca r0>r

Lema 18. Daca avem problemele de decizie caracterizate de (H, W ) si (H, W) cu W si W multimi convexe si compacte si multimile admisibile A si A atunci An=A Wn si A n= A W n n=1,2,3,

Demonstratia prin inductie, din ipoteza rezulta ca lema este adevarata pentru n=1. Presupunem lema adevarata pentru n. Aplicand teorema 16. la problema caracterizata de (H, Wn) avem ca . Analog pentru problema de decizie a doua obtinem .

Din ipoteza de inductie rezulta An= A n care da vN=v N. In mod similar pentru zn= rezulta ca zn=z n. Trebuie sa verificam ca An+1=An Wn+1, adica An+1=A Wn+1. Rezulta ca An+1=A n+1 si lema este complet demonstrata.

Teorema 19. Fie problema de decizie (H,W) cu multimea functiilor de risc convexa si compacta A W o multime ce caracterizeaza strategiile admisibile si similar problem de decizie caracterizata de (H, W ) nu W convexa si compacta si A W multimea ce caracterizeaza strategiile admisibile din W . Daca A=A atunci W =W0.

Teorema 20. Fie problemele de decizii statistice caracterizate de multimile (H, W) si (H, W ) cu W si W convexe si compacte.Fie C W si C W , C clasa completa in ambele. Atunci W0=W

Demonstratie. Din teorema 16. rezulta ca A este o clasa completa. Dar A este o clasa complet minimala si A C similar si A C se verifica ca A= A . Aplicand teorema 19. rezulta ca W0=W






Politica de confidentialitate



DISTRIBUIE DOCUMENTUL

Comentarii


Vizualizari: 1229
Importanta: rank

Comenteaza documentul:

Te rugam sa te autentifici sau sa iti faci cont pentru a putea comenta

Creaza cont nou

Termeni si conditii de utilizare | Contact
© SCRIGROUP 2021 . All rights reserved

Distribuie URL

Adauga cod HTML in site