COMPACTITATEA SPATIULUI STRATEGIILOR STATISTICE

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 (h₁,h₂)=

d (d₁, d₂)=

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 d_D indusa de functie de pietre L. Sirul de strategii statistice S converge catre strategia statistica S₀IS daca, =S₀(x,A) xIX AID, A-multime deschisa si S₀(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 S₀I 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 D₀ D astfel ca: S(x,D₀)=1 xIX SIS. Fie xIX si sirul de strategii statistice S deoarece D₀ este compacta si S inchisa, atunci sirul S_i(x, ) contine un subsir (S_ij(x, ) care converge catre strategia statistica S₀(x, ), adica: S₀(x,B) BI K S₀(x, B⁰)=0. Deoarece este numarabil din subsirul astfel ca: S_ij(x,B) S₀(x,B) xIX, BID, S₀(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 (s_ij)_j=1 ( (S_i) ales astfel ca:

lim P(B|C, S_ij)=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 (Z_i) un subsir al sirului ( ) astfel ca Z_i Z_j= 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)= , Z_j Z_i= , 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) S₀(x,Z)=

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

VIII) S₀(x, )=S (x, )

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

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

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

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

Deci ( B,S_ij)=P( B,S₀), BIK I

2 Compactitatea slaba a spatiului strategiilor

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

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

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

R(Q,S_i) R(Q,S₀) QIQ.

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

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

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 S₀, atunci S_i converge slab catre S₀;

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,S_i)< i.

Deoarece S_i converge catre S₀ rezulta ca S_i(x,B)=S₀(x,B) xIX, BID, deschisa S₀(x, B)=0

Fie P_hIP puterea caracteristica a strategiei statistice

P(B h,S_i)= dP_h(x).

Din teoremele 1.3. si 1.4. rezulta ca

=P(B h,S₀) h, BID, B deschisa si P( B h,S₀)=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:

d₁(h₁,h₂)= ,

d₂(h₁,h₂)= ,

d₃(h₁,h₂)= ,

d₄(h₁,h₂)= d₁(h₁,h₂)+ d₃(h₁,h₂).

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 d₂.

Demonstratie. Din teorema 1.3.11 rezulta ca H este separabil in sensul metricii d₁.Fie metrica: d₄(h₁,h₂)= d₁(h₁,h₂)+ d₃(h₁,h₂).Vom arata ca H este de asemenea separabil in sensul metrici d₄(h₁,h₂). Deoarece D este compact, rezulta din teorema 2.1. [111] spatiul H este conditional compact in sensul metricii d₃(h₁,h₂). Prin urmare, pentru orice e > 0 este posibil sa impartim spatiul starilor H intr-un numar finit de submultimi disjuncte H₁, H₂, H₃,., H_m astfel ca diametrele multimilor H_i in raport cu metrica d₃ sa fie mai mici decat e.Deoarece H este separabil in sensul metricii d₁, exista o submultime numarabila H _i H_i densa in H_i in raport cu metrica d₁.Fie

H ⁰=

Evident H⁰ este numarabila si 2e-densa in sensul metricii d₄. Teorema este demonstrata daca vom arata ca, daca in sensul metricii d₄, atunci in sensul metricii d₂. Fie un sir, astfel ca e> exista n(e) astfel ca d₄(h_i,h₀) e, d₄(h_n,h₀)< 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(h_i,L S,x) uniform in raport cu S si x.

Dar dP_h(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 S₀ 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 (h₁, h₂)=

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

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 S₀ 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 S₀) , hIH si deci S₀ S SIS

Teorema 4. Fie problema de decizie statistica regulata,

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

Demonstratie. Deoarece Q₀, este probabilitatea apriori cea mai putin favorabila

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

rezulta ca S₀ S, SI S.

Teorema 4.6. Fie problema de decizie statistica regulata,

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

Q⁰( (2)

Demonstratie. Din teorema 4. rezulta ca = care implica =r(Q⁰,S₀). 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 Q⁰ o probabilitate apriori cea mai putin favorabila si S₀ este optima in raport cu relatia de preordine atunci r(h S₀)= r(h S₀) hIH

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

r(h S₀)< hIH .Deoarece h₀IN(Q⁰) avem

Q⁰(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 (Q_i) astfel ca TIT. Q₀- continua in raport cu metrica intrinseca. Atunci:

(i)         R(Q_i,S) R(Q₀,S) uniform in raport cu S,

(ii)       = si

(iii)     R(Q₀,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 Q₀( (6)

Din teorema 4.8, rezulta:

.

Din relatiile (5) si (7) rezulta ca teorema este demonstrata. Fie Q₀ o multime numarabila de probabilitati apriori si Q^H - multimea probabilitatilor punctuale. Presupunem ca exista un sir de probabilitati apriori care este dens in Q^T=Q⁰ Q^H in raport cu semimetrica indusa de riscul mediu d(Q₁,Q₂)=

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

Demonstratie. Fie S_j o strategie m-preferata in raport cu Q^j= 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 a_j a_k>0, 1 k j, astfel ca R(Q ,S_j) R(Q ,S) SI S unde Q

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

R(Q_i,S₀) R(Q_i,S) SI S .

din teorema 3.4 pagina 88 [111] rezulta ca R(Q_i,S)= deoarece pentru strategia m-preferata S₀ 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 Q^H 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 S^b se numeste b-optima, daca exista probabilitatea apriori Q astfel ca S^b sa fie optima in raport cu .

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

Fie S^B 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 S^B

Demonstratie. Fir SI S^B 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 S^m m-optima. Existenta strategiei statistice m-optime S^m rezulta din teorema 4. Din teorema 4.6. rezulta ca strategia S^m 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,S₀) deoarece r^*(h,S₀)=0 si S₀ este o strategie m-optima rezulta r^*(h,S^m)= r(h,S^m)- r(h,S₀) hIH.

Din relatiile (1) si (2) rezulta ca S^m>S₀ deci ne-au dat o strategie S₀IS^B care nu este slab b-optima si exista o strategie S^m slab b-optima astfel ca S^m>S ceea ce trebuia demonstrat.

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

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

Demonstratie. Am notat cu inchiderea multimii in raport cu convergenta regulata. Fie S₀I S ^B, L^*(h d L(h d r(h S₀). 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 S₀)=0 hIH avem r^*(h S^m)= r(h S^m)-r(h S₀) hIH adica S^m>S₀ ceea ce trebuie demonstrat.

Fie Q⁰ multimea tuturor probabilitatilor apriori cu proprietatea ca, pentru orice Q⁰ Q exista un sir Q astfel ca: limQ_i(T)=Q₀(T) TIT..Fie multimea strategiilor optime in raport cu relatia , QIQ^d.

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 S₀IS^B si functia de pierdere L^*(h d L(h d r(h S₀) cu functia de risc asociata r^*(h S). problema de decizie obtinuta prin schimbarea lui l cu L^* este de asemenea regulata. Daca

=Q₀(T) T atunci d(Q_i,Q₀)= -r(Q₀,S) cand i

Din teorema 4. rezulta ca exista o strategie m-optima S^mI . Deoarece r^*(h S₀)=0 hIH si r^*(h S₀)= r(h S^m)-r(h S₀) 0. Rezulta S^m>S₀ 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 r_1,r₂ IW, r₁<r₂ daca si numai daca r₁(h) r₂(h), hIH si exista cel putin o stare astfel ca r₁(h) r₂(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 B₁, B₂ B,

d(B_1, B₂)=max , unde d(f₁,f₂)=

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 W⁰ 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 W⁰

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

P.3. Daca (H,W) si (H ,W ), h: H H bijectiva si daca W₀oh atunci si W =W⁰ h

P.4. Daca (H,W) si (H ,W a> fix , b H E₁ o functie fixata oarecare, atunci si W aW+b si atunci W⁰ aW⁰+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 W⁰ multimea optima pentru ( ).

P.6. Daca (H,W), (H,W⁽ⁿ⁾), n=1,2,..d(W,W⁽ⁿ⁾) cand n si daca r_nIW⁽ⁿ⁾⁰ si d(r_n,r) 0, cand n atunci rIW⁰.

P. Orice rIW⁰ este admisibila.

P.8. Daca (H,W), (H,W ) si C este o clasa completa in ambele probleme, atunci W⁰=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(e_n)W=W⁰ pe baza algoritmului dat mai jos.

0 START[IMR]

1 INPUT

2 K=IMR(e_n)W     //satisface P.1, adica W⁰

3 W₁ W

4 v₁(h)

5 z₁

6 IF z₁ LS

6.1 W⁰←W₁

6.2 n←1

Else

7 WHILE n< Ni

1 W_n+1←

2 n←n+1

3 v_n(h):=

4 z_n

5 W⁰ W⁰ W_n

OUTPUT

9 STOP

Observatie. LS reprezinta limita superioara pentru distanta z care, teoretic poate lua valoarea si N_i 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 W⁰= (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 W⁰ este slab compacta.

Demonstratie. Daca z₁= , atunci W⁰=W si teorema este demonstrata. Vom arata prin inductie ca W_N este nevida si slab compacta. Evident, W_M+1 este nevida si fie astfel ca hIH deoarece aceasta implica , hIH si deci rIW_N+1, deci W_N+1 este intrinsec slab compact. Astfel, prin inductie W_n este nevida si intrinsec slab compacta pentru orice n. Fie un sir cu r_nIW_n. Deoarece W₁ este intrinsec slab compacta, rezulta ca exista un subsir si rIW₁, astfel ca

, hIH.

Presupunand ca rIW_N rezulta ca rIW_N+1 si prin inductie rIW_N pentru orice n si deci W⁰

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

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

Teorema 8. Fie (H, W) care satisface P.1. atunci W⁰ 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 =W₀ h, si problema (H,W) atunci W =W⁰ h.

Demonstratie. Este evident ca v =v₁ h si z =z₁. astfel daca z₁=z deoarece multimile optime coincid cu multimile W si W , rezulta ca W =W⁰ h. Daca z₁=z < rezulta prin inductie ca W _n=W_n h pentru orice n, W =W⁰ 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 aW⁰+b

Demonstratie. Se arata ca, v av₁+b si z az₁, prin urmare teorema este adevarata cand; daca z₁< 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 Q₀ pe H astfel ca pentru orice rIW sa avem r(h )= . Atunci W _H=W⁰.

Demonstratie. Multimea W⁰ 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 =z₁, atunci cand z₁= . Teorema este demonstrata.

Daca z₁< se utilizeaza inductia pentru a arata ca W_n= 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,W^N) 0 cand N . Presupunem ca z₁< atunci

n

n

n

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

b) Sa aratam ca d( ,W₂) 0 cand N . Cand z₁=0, avem ca W₂= atunci pentru orice I avem d(v₂, ) d(v₁, )+ +e₁ si trecand la limita, rezulta d( ,W₂) 0 daca z₁>0 fie e>0, dat, si presupunem ca (e z₁+e z₁. Fie a= .Fie N suficient de mare, astfel ca: d(W₁, a/9, d(v₁, a/9, |z₁- a/18, e |z₁ - 18, z₁/2< <3z₁/2.

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

c₁) Daca d(v₁,f) z₁+e z₁-a/3 alegem r^NI astfel ca d(r,r^N) a/9+e/2 si se observa ca r^NI

c₂) Daca d(v₁,r)>z₁+e z₁-a/3 alegen un r₀IW₂ cu d(v₁, r₀)<z₁+e z₁/10. Daca d(r,r₀) e/2 alegem ca in cazul c₁, cu d(r, )<e/2 si prin urmare d(r, )<e.

Cand d(r,r₀)>e/2 definim = pr₀+(1-p)r, unde p=e d(r,r₀). Din inegalitatea triunghiului pentru norme si deoarece d(r,r₀) z₁+e₁z₁ avem d(v₁,r) z₁+e z₁-a/3. Atunci ca si in cazul c₁ 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 z₁/2< +3z₁/2. Punctele c si d demonstreaza ca d( ,W₂) e

La punctele a, b si c am aratat ca d( , v) z₁ si d( ,W₂) 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,W^N, N=1,2,. care satisfac proprietatea P.1. si W este inchisa. Daca r^NIW^N N astfel ca d(r^N,r) pentru un r atunci rIW⁰.

Demonstratie. Daca z₁< , pentru un n fix din teorema 12. rezulta ca d( ,r^N) cand N , astfel avem d( ,r) cand N si avem rIW_n, prin urmare rIW_n oricare ar fi n, adica rIW⁰. Daca z₁= , in acest caz din punctul a al teoremei rezulta ca pentru orice N suficient de mare. Vom arata ca rIW₁. Deoarece W₁= W⁰₁ rezulta ca rIW⁰ 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, z₁ este finit si W este slab compact. Se arata ca W⁰ 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(v_n,v) z_n z si pentru orice rIW⁰ avem d(v,r)=z (unde z si v se refera la solutia optima rIW⁰).

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 r₀IW. Deoarece pentru , rezulta r₀IW_n si astfel r₀IW⁰. Astfel pentru un numar suficient de mare v(h) r₀(h) < (h e h Acesta contrazice (*) si deci d(v_n,v) . Rezulta ca z_n<z+e pentru orice n suficient de mare, si prin urmare z<z_n, avem z_n z. Deoarece e_n 0 din inegalitatea triunghiului rezulta d(v,r)=z pentru orice rIW⁰.

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

Demonstratie. Presupunem z>0 si 0<e<Z. Fie h₁IH si alegem r₁IW⁰ astfel ca r₁(h)=v(h₁). Definim A₁= si prin urmare A₁ . Procedand analog, definim A_n si A_n . Alegem h_n+1IA si r_n+1IW⁰ astfel ca r_n+1(h_n+1)=v(h_n+1). Definim A_n+1= . Astfel A_n+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 (h_n H si un sir (r_n) W⁰ astfel ca pentru m<n, r_m(h_n)>r(h_n)+z-e si r_n(h_n)=v(h_n). Astfel d(r_m,r_n) z-e pentru m n, ceea ce contrazice compactitatea lui W⁰. Prin urmare z=0. Sa aratam admisibilitatea, fie r₀I W⁰ si presupunem ca r₀ nu este admisibila. Atunci din definitie rezulta ca, exista r₁I W. deoarece aceasta contrazice z=0, rezulta ca r₀ 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 =W⁰.

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 T_r= . Multimea T_r W convexa si compacta. Astfel fie problema de decizie caracterizata de (H, T_r W) care are W cu r₀ admisibila in T_r W. Daca exista r₁IT_r W, r₁>r₀, atunci r₁IT_r W, ceea ce contrazice ca r₀ este admisibila in raport cu (H T_r W) prin urmare r₀ 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 A_n(clasele admisibile corespunzatoare in W_n,(W _n), n=1,2,.r A_n daca nu exista r₀IW_m, astfel ca r₀>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 A_n=A W_n 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, W_n) avem ca . Analog pentru problema de decizie a doua obtinem .

Din ipoteza de inductie rezulta A_n= A _n care da v_N=v _N. In mod similar pentru z_n= rezulta ca z_n=z _n. Trebuie sa verificam ca A_n+1=A_n W_n+1, adica A_n+1=A W_n+1. Rezulta ca A_n+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 =W⁰.

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 W⁰=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 W⁰=W