Analisi Statistisca in Simulazione

Analisi Statistisca in Simulazione

Aspetto fondamentale in simulazione, a volte sottovalutato Corrette interpretazione dei risultati

* Analisi dei dati di input

definizione e parametrizzazione del modello caratterizzazione del carico (distribuzioni, etc.)

* Analisi dei risultati di un esperimento di simulazione

derivare le caratteristiche stocastiche degli indici valutati

• analisi del comportamento transiente influenza delle condizioni iniziali

• analisi del comportamento stazionario (steady-state) sistema in equilibrio, elim. della fase transiente

• numero di esperimenti, lunghezza degli esperimenti

• condizioni iniziali di ogni esperimento.

* Convalida degli esperimenti di simulazione Esempi:

- stimare se un processo di arrivo ad un sistema (p.es. di calcolo) è Poissoiniano di media λ

- stimare se un processo di servizio di un servente è esponenziale

- stimare i parametri di una distribuzione data

- caratterizzare il carico del sistema composto da input multiclasse

• stazionarietà e indipendenza

Analisi statistica classica

• stima della media

• stima della varianza

• stima della distribuzione

* test di "goodness of fit"

* test di Kolmogorov-Smirnov

• operazioni su intervalli di confidenza

• Stazionarietà della popolazione osservata Indipendenza delle osservazioni

(proprietà non sempre verificate sia in input che in output) Stima della media

• x₁ x₂ ... xn campione di osservazioni indipendenti (v.c.)

• popolazione caratterizzata da una funzione di distribuzione di probabilità f(x) di media E[x] = µ e varianza Var[x] = σ²

• media campionaria

x = Σ _{xi / n}

stimatore non distorto della media µ della distribuzione

• x è una v.c. di media

E[x] = E[Σi xi / n] = n µ / n = µ e di varianza

Var[x] = E[(x-µ)²] = Σi Var[xi] / n² = σ² / n x è una buona stima di µ se σ/n è piccolo poiché (disuguaglianza di Chebyshev)

Prob{| x - µ | > c σ/√n } ≤ 1/ c² (1)

• la distribuzione f(x) è normale se f(x) è normale,

altrimenti, per il teorema del limite centrale, per n → ∞ tende ad una normale di media µ e varianza σ²/n

(approssimazione per n>30)

• (x - µ) / (σ/√n) → Ζ normale (0,1) funzione cumulativa F_Z(u) = Prob { Z ≤ u }

• spesso anche la varianza σ² è ignota

• Stima della varianza del campione Var[x] = E[(x-µ)²]

• lo stimatore Σi (xi - x)² / n è distorto

• varianza campionaria

S² = Σ _{(xi - x)}^{2 / (n-1)}

stimatore non distorto della varianza σ² della distribuzione

• S² è una v.c. di media

E[S² ] = E[Σi (xi - x)²/(n-1)] = E[(Σi xi² - n x²)/(n-1)] =

= (Σi E[ xi²] - n E[x²] )/(n-1) = (n (µ²+σ²)-n(µ²+σ²/n) /(n-1) =

= σ²

• deviazione standard campionaria S

stimatore non distorto della deviazione standard σ

• lo stimatore della varianza può essere utilizzato per valutare la bontà della stima della media per la (1)

• Se il campione è ottenuto come risultato di un esperimento di simulazione e si vuole stimare la media µ, si continua la simulazione finché n è tale che σ/√n ovvero S/√n è inferiore ad una quantità prefissata

1. fissare un valore d accettabile per la deviazione standard 2. generare almeno 30 valori dei dati

3. continuare la generazione fino a k valori tali che S/√k<d , dove S è calcolata con i k valori calcolati 4. si ottiene la stima di µ, calcolandola sui k valori

generazione ricorsiva di x e di S²

Intervalli di confidenza

• necessità di calcolare intervalli di confidenza dello stimatore x

• x₁ x₂ ... xn campione di osservazioni indipendenti e identicamente distribuite (i.i.d.) di media µ e varianza σ²

• media campionaria x : v.c. di media µ e di varianza σ²/n

• S²/n è uno stimatore non distorto di σ²/n

• anche la variabile

(x - µ) / (S/√n) → t-Student con n-1 gradi di libertà ma per n>30 → Ζ normale (0,1)

funzione cumulativa F_Z(u) = Prob { Z ≤ u }

• qα percentile 100a della distribuzione normale Prob{ Z ≤ qα } = α

• uα è tale che Prob{ Z ≤ uα } = 1 - α

• per la simmetria Prob{ - uα/2≤ Z ≤ uα/2 } = 1 - α Prob{ - uα/2≤ √n (x - µ) / S ≤ uα/2 } = 1 - α Prob{ - uα/2≤ √n (µ - x) / S ≤ uα/2 } = 1 - α

Prob{ x- (S/√n)uα/2 ≤ µ ≤ x+(S/√n)uα/2 } = 1 - α intervallo di confidenza per la media µ

nozione probabilistica; probabilità a priori

µ, valore teorico, cade nell'intervallo con prob. 1-α

• utilizzare i valori di uα/2 tabulati Esempio:

α = 0.05 1−α=0.95 uα/2 =1.96

intervallo di confidenza al 100(1−α) =95%

x ± (S/√n) 1.96

Prob{ x- (S/√n) 1.96 ≤ µ ≤ x+(S/√n)1.96} = 0.95

• Conviene ridurre l'ampiezza dell'intervallo di confidenza

• Due misure di precisione:

precisione assoluta → semiampiezza dell'intervallo

precisione relativa → 100(semiampiezza dell'intervallo / x)

• si usa la misura relativa se non si hanno informazioni sull'ordine di grandezza di µ

Es.: x=8, intervallo [7.5,8.5] prec. rel.=100(0.5/8)=6%

• Per ridurre l'ampiezza dell'intervallo di confidenza si deve aumentare il numero n di osservazioni

ampiezza ∝ 1/√n se S è circa costante

• Se il campione è ottenuto come risultato di un esperimento di simulazione e si vuole stimare la media µ, utilizzando gli intervalli di confidenza, fissato un livello di confidenza 100(1−α), si continua la simulazione finchè n è tale che l'intervallo di confidenza ha una ampiezza inferiore ad una quantità prefissata.

• ampiezza dell'intervallo di confidenza 2 (S/√n)uα/2

1. fissare un valore d ed il livello di confidenza 100(1−α) 2. generare almeno 30 valori dei dati

3. continuare la generazione fino a k valori tali che

2 (S/√n)uα/2<d , dove S è calcolata con i k valori calcolati 4. si ottiene la stima di µ, calcolando l'intervallo di

confidenzax x±(S/√n)uα/2

dove x ed S sono calcolati sui k valori determinati al passo 3

generazione ricorsiva di x e di S²

• tipici valori α = 0.01, 0.05, 0.1,

a cui corrispondono uα/2 = 2.57, 1.96, 1.64 e i livelli di confidenza del 99%, 95%, 90%.

Stima della varianza della popolazione

• metodo indiretto : σ² = E[x²] - E²[x]

dato un campione x₁...xn si stima E[x] tramite gli intervalli di confidenza, e si deriva E²[x]

e dal campione x₁²...xn² si deriva E[x²]

combinando opportunamente gli intervalli di confidenza

• metodo diretto : basato su S², v.c. di media σ² e varianza → 0 per n → ∞

si dimostra che la v.c. (n-1)S²/σ² ha distribuzione X² con n-1 gradi di libertà

Si può applicare la tecnica degli intervalli di confidenza, come nel caso della media, ma facendo riferimento alla distribuzione X² anzichè alla distribuzione normale

Prob{ (n-1)S²/qα1 ≤ σ² ≤ (n-1)S²/qα2 } = 1 - α dove qα1 e qα2 sono i percentili della v.c. X²(n-1) tali che Prob{qα1 ≤ X²(n-1) ≤ qα2 } = 1 - α

ΜΑ questo metodo di stima della varianza è sensibile alla distribuzione del campione. Se il campione non ha distribuzione normale tale tecnica non può essere applicata.

• calcolo dell'intervallo di confidenza per la varianza σ² con il metodo di jackknifing (Miller 1974,Lavenberg83,Kleigren74) meno sensibile all forma della distribuzione del campione

dato un campione x₁...xn si calcola la media e la varianza campionaria con l'osservazione j rimossa, 1≤j≤n

xj = Σ_i≠j xi /(n-1)

Sj²= Σ_{i≠j xi}² /(n-2) - (n-1) xj /(n-2) si definiscono gli "pseudovalori" 1≤j≤n

zj = n S² - (n-1) Sj²

(nota: S²= Σ_{i xi}² _/(n-1) ^{- n x2}/(n-1) ) da cui

E[zj] = n E[S²] - (n-1) E[Sj²] = σ² quindi la distribuzione di zj ha media σ²

Indichiamo con z e S_z² la media e la varianza campionaria del campione z₁...zn

z = Σ_{j zj /n}

S_z²= Σ_{j (zj-z)}^{2 /(n-1)}

da cui la v.c. (z - σ²) /(S_z /√n) è distribuita secondo una t- Student con n-1 gradi di libertà, da cui, come nel caso precedente si ottiene l'intervallo di confidenza per la varianza Prob{ z-(S_z/√n) uα/2 ≤ σ² ≤ z+(S_z/√n) uα/2 } = 1 - α

dove uα/2 è definito come nel caso della media.

Operazioni sugli intervalli di confidenza

• dalle osservazioni relative a due v.c. X e Y rispettivamente di media µ e η

si vuole valutare la stima del rapporto ∂ = µ / η

si ottiene un campione z₁...zn dove zi= (xi, yi) 1≤i≤n

• calcoliamo le medie campionarie z = (x, y)

x = Σ_{i xi /n} ^{y =} Σ_{i yi /n}

• definiamo la matrice di covarianza del campione S²= Σi (zi-z) (zi-z)^T /(n-1)

S₁₁² S₁₂² S₂₁² S₂₂²

S₁₁² =Σ_{i (xi-x)}^{2 /(n-1) S}222 =Σ_{i (yi-y)}^{2 /(n-1)}

S₂₁² = S₁₂² = Σi (xi-x) (yi-y) /(n-1)

• stima puntuale del rapporto µ / η A) stimatore di Fieller

∂F = [x y - k S¹²²] / [y²- k S₂₂²] dove

k = uα/2 / n B) stimatore di Beale

∂B = [x/y] [1+ S¹²²/(n x y)] / [1+ S₂₂²/(n y²)]

C) stimatore classico

∂C = [x/y]

D) stimatore jackknife

∂J = Σ_{i Li / n}

dove

Li = n [x/y] - (n-1) [Σ_{j≠i xj /}Σ_j≠i yj] 1≤i≤n E) stimatore di Tin

∂T =[x/y] [1+ (S¹²²/(x y) - S₂₂²/(y²))/n ]

• tutti gli stimatori sono consistenti (convergono al valore vero con probabilità 1) e sono generalmente distorti

• B) D) E) tendono a ridurre la distorsione

• calcolo dell'intervallo di confidenza per il rapporto ∂ = µ / η 1) stimatore di Iglehart : basato sulla stima puntuale ottenuta utilizzando lo stimatore di Fieller:

∂F ± √D/(y² - k S₂₂²) dove

D = [x y - k S₁₂²] - [y - k S₂₂²][x - k S₁₁²] e il livello di confidenza dipende da k = uα/2 / n 2) stimatore classico

∂C ± uα/2 γ /(y √n)

dove γ = [S₁₁² - 2 ∂CS¹²² + (∂C)² S₂₂²]^1/2 2) stimatore jackknife

∂J ± uα/2 γ' /(√n)

dove γ' = [Σ_{i (Li - 2} ^∂_J^{)2 / (n-1)]1/2}

• nei due ultimi stimatori γ e γ' rappresentano stime delle varianze del campione

• lo stimatore jackknife produce migliori risultati dal punto di vista statistico, specie per campioni piccoli

• più complesso da realizzare

• si può utilizzare come stima puntuale lo stimatore di Baele e/o di Tin

• utilizzare il metodo classico per l'intervallo di confidenza, speciamente se il campione è di grandi dimensioni.

Altre operazioni sugli intervalli di confidenza

• siano µ e η due parametri con intervalli di confidenza [µ inf, µsup] [ηinf, ηsup]

rispettivamente al livello di confidenza

100 (1-α1) 100 (1-α2)

• si ricava per µ - η

Prob{µinf - ηsup ≤ µ - η ≤ µsup - ηinf} = 1 - α1- α2

• per A µ + B , A>0

Prob{A µinf + B ≤ A µ + B ≤ A µsup + B} = 1 - α1

• per max(0,µ) = µ +, µ ≥0 , n>0

Prob{ (µ+inf )n ≤ (µ +)n ≤ (µ+sup )n} = 1 - α1

• queste regole sono utilizzate nel metodo indiretto della stima della varianza (vedi P.4.7)

Analisi dei risultati in Simulazione

caratterizzazione del carico

realizzazione 1^ input

realizzazione 2^ input

realizzazione n^ input

esperimento di simulazione

esperimento di simulazione esperimento di simulazione

1^ output

2^ output

n^ output

... ...

distribuzione sequenza output

INFERENZA STATISTICA GENERAZIONE

CASUALE

Schema di un esperimento di simulazione Metodi di analisi statistica classica

stazionarietà della popolazione indipendenza delle osservazioni

In generale le osservazioni ricavate da un esperimento di simulazione solitamente NON sono i.i.d.

influenza delle condizioni iniziali correlazione fra le osservazioni stazionarietà del sistema ?

Metodi per ottenere osservazioni da esperimenti di simulazione che possano essere considerate i.i.d.

Output di esperimenti di simulazione : sequenze casuali x₁...xn

Valutazione di indici di prestazione :

p.es. : tempi di risposta, throughput, utilizzazioni

Valutazione della media, varianza, distribuzione di probabilità Analisi dei risultati:

derivare le caratteristiche stocastiche degli indici valutati

• comportamento transiente (short-run)

simulazione a termine : intervallo predefinito [0,TE]

TE è il tempo di occorrenza di un evento predefinito, specificato PRIMA dell'inizio della simulazione

influenza delle condizioni iniziali (stato)

Si possono ricavare n osservazioni indipendenti soltanto eseguendo n run (prove) di simulazione

* sullo stesso periodo,

* con le stesse condizioni iniziali e

* con diverse sequenze di numeri pseudocasuali (e i semi diversi non devono essere in relazione fra loro)

* ottenere una osservazione per ogni prova metodo delle PROVE RIPETUTE

applicabile anche per l'analisi stazionaria

• comportamento stazionario (long-run, steady-state) tempo di simulazione → ∞

problemi : stazionarietà

sistema in equilibrio, elim. della fase transiente indipendenza

• Stazionarietà : Eliminazione della fase transiente determinare no tale che ogni osservazione del campione xno⁺¹ xno⁺² ... xno⁺ n

provenga (approssimativamente) dalla stessa popolazione con distribuzione di probabilità stazionaria F(x), di media µ e varianza σ² (distribuzione invariante nel tempo)

no ???

•Stima della lunghezza della fase transiente Indipendenza dallo stato iniziale

Eliminare le osservazioni xi tali che F(xi) ≠ F(x)

Più semplicemente : studiare la convergenza della media della distribuzione µi = E[xi]

La sequenza {µi , i=1,2,…} → µ

•lim i→∞ µi = µ è C.N. per lim i→∞ F(xi) = F(x)

•run pilota per determinare no : stima della sequenza {µi, i≥1}

Si effettuano M prove ripetute e si genera la sequenza delle medie campionarie:

x₁₁...x₁n x₂₁...x₂n

…

x_M1...x_Mn stima di µi è

x_i = M

∑

x_ji

1≤i≤n

sequenza delle medie campionarie {xi, i≥1} , dove ogni xi fluttua attorno alla media

E[xi] = µi

* per M abbastanza grande {xi, i≥1} si può considerare una stima del punto di convergenza della sequenza {µi, i≥1}

* si tabulano gli intervalli di confidenza di un sottoinsieme delle medie campionarie xi per avere una idea della convergenza.

NOTA: tali intervalli sono validi solo singolarmente, poichè per un insieme di n eventi E₁...Ek si ha per la prob. congiunta

Prob{ ∩ _{i Ei}} ^≥ 1 - Prob{not Ei}

es.: se tutti gli intevalli sono al 90% di confidenza, la prob.

congiunta relativa ai k valori è solo ≥ 1- 0.1 k

* Utilizzare queste informazioni in modo intuitivo

* Tabulare la sequenza{xi, i≥1} per un periodo sufficientemente lungo per eliminare le oscillazioni a breve termine, ma non troppo lungo per non osservare una distorsione delle fluttuazioni a lungo termine.

* Dalla sequenza{xi, i≥1}→ sequenza{xi(K), i≥1}

xi(K) = (2K+1)^-1

∑

j = -K K

xi + j se i ≥ K+1

x_i(K) = (2i-1)^-1

∑

j = -(i-1) i-1

x_{i + j} se i < K+1

definisce la media (dinamica) su una ampiezza di 2K+1 elementi

* alcuni autori suggeriscono una sola prova (M=1), e considerano la stabilizzazione della media campionaria

dipendenza dal seme più economico

* la convergenza della media è solo C.N. per la convergenza della distribuzione

* si può stimare la stabilizzazione di altre quantità (es.percentili) p.es. la varianza σ² della distribuzione, considerando la stima ottenuta dalla varianza campionaria

Si² = Σj (xji - xi)² / (M-1) 1≤i≤n osservata in funzione di i fino alla stabilizzazione a lungo termine, poichè Var[Si² ]= σi² =Var[xi].

Utilizzare eventualmente anche gli int. di confidenza Eventuale correzione come per la media.

Metodi di analisi dei risultati

•Stazionarietà e indipendenza

* metodo delle PROVE RIPETUTE

* metodo RIGENERATIVO

* metodo BATCH

METODO DELLE PROVE RIPETUTE

•rigenerazione artificiale

•eliminare la fase transiente

•ripetere l'esperimento M volte (M prove ripetute), eliminando in ogni prova le informazioni relative alla fase transiente

•ogni prova i fornisce ni osservazioni, 1≤i≤M ed è considerata indipendente dalle altre prove

x₁₁...xn¹¹ → y₁ z₁ x₁₂...xn²² → y₂ z₂

…

x_1M...xn^MM → y_M z_M

•si calcola

yj =

∑

i = 1 n_i

xij z

j =

∑

i = 1 n_i

xij

2 1≤j≤M

allora i campioni

y₁...y_M z₁...z_M n₁...n_M

si possono considerare i.i.d. e si può quindi applicare l'analisi statistica classica per la stima di media e varianza.

•medie teoriche delle distribuzioni di yj, zj ed nj : δ = E[yj] λ = E[zj] γ = E[nj]

• poichè

E[x] = δ / γ =E[ Σ_{i xij}]/ ^E[nj]

E[x²] = λ / γ =E[ Σ_{i x}²_ij]/ ^E[nj]

si possono ottenere le relative stime dalle stime di δ, λ e γ : σ² = E[x²] -E²[x] = ( λ / γ ) - ( δ / γ )²

•si utilizzano le operazioni su intervalli di confidenza

•ni ha tipicamente distribuizione unforme in [a,b], con a e b opportuni, dipendenti dal sistema, dalle variabili da stimare e dalla precisione

p.es. [50,100]

•se ni è costante si possono avere problemi dovuti alla dipendenza fra prove

•in ogni prova si devono raccogliere le osservazioni a partire da uno stato stazionario

1) si stabilisce tramite il run pilota uno stato stazionario ogni prova parte da quello stato

2) ogni prova parte da uno stato non stazionario

si effettua l'eliminazione della fase transiente in ogni prova

•in ogni prova considerare sequenze random diverse

p.es. ogni prova i>1 utilizza come semi dei generatori gli ultimi valori generati nella prova i-1.

Convadida del modello di Simulazione

•stabilire se il modello nel suo dominio di applicabilità è sufficientemente accurato per l'applicazione prevista

•confronto fra i risultati forniti dal modello di simulazione e misure effettuate sul sistema reale.

•stabilire la verosimiglianza fra modello e sistema

•almeno per un sottoinsieme significativo di parametri (carico del sistema e configurazione)

•un modello non convalidato richiede la revisione di almeno una possibile causa

definizione del modello (rappresentatività) parametrizzazione

metodo di analisi dell'output

proprietà statistiche delle sequenze generate correttezza del programma

•analisi statistica dei dati prodotti dal modello e dal sistema

•due fasi : calibratura convalida

•calibratura (messa a punto - tuning)

verifica della rappresentatività del modello rispetto ad un insieme di dati (iniziali) provenienti dal sistema

•verifica :

generatori di numeri pseudocasuali

caratteristiche probabilistiche delle var. (esogene) metodi per l'osservazione delle var. endogene

•convalida

verifica della rappresentatività del modello anche rispetto a comportamenti futuri del sistema

•la risposta (parziale o totale) del modello varia secondo la stessa legge probabilistica della risposta del sistema.

proprietà delle var. endogene: confronto fra risultati forniti dal simulatore e dati osservati dal sistema reale.

•come effettuare il confronto con il sistema reale

con un modello matematico con un altro simulatore

•convalida con un modello matematico

il simulatore viene eseguito sotto le stesse ipotesi valide per il modello matematico

es.: M/M/1

reti di Jackson reti BCMP

•si estrae un campione dal simulatore es.: tempi di risposta

•si effettua una stima della grandezza in esame, generandone l'intervallo di confidenza

•si confronta il valore stimato con il valore teorico prodotto dal modello matematico (media, varianza, distribuzione)

•il confronto dà esito positivo se il valore teorico cade nell'intervallo di confidenza stimato.

•convalida con sistemi reali o con un altro simulatore

•si estrae un campione dal simulatore

•si considera un campione dal sistema reale o da un altro simulatore

•confronto

fissata una variabile di risposta Y Y= f(X1,…Xp)

funzione di variabili indipendenti detti fattori che rappresentano le caratteristiche operative del sistema

(p.es. discipline di servizio, distribuzioni,...) ogni fattore può assumere dei livelli

differenze qualitative o quantitative

p fattori, n livelli → n^p combinazioni di valori con cui valutare Y

esprimento è detto fattoriale n^p

•Esempio:

sistema aperto formato da una singola risorsa a canale multiplo (n canali)

Y= tempo medio di residenza X1= disciplina di servizio X2 = distribuzione dei servizi

X3 = numero di canali a capacità totale costante [n/µ i(n)]=cost

X1 = FIFO, SPTF

X2 = esponenziale, normale, uniforme X3 = canale singolo, doppio, quadruplo

•analisi di varianza e regressione (lineare e/o non lineare) sui dati del modello e su quelli del sistema di riferimento

•dai parametri discordanti : indicazioni per le modifiche.

•convalida : simulatore ⇔ sistema di riferimento

modello robusto se i risultati non dipendono in modo critico dalle ipotesi di funzionamento e dalle caratteristiche operative.

valutazione di diverse caratteristiche operative.

proprietà di insensitività

non esistono risultati generali per modelli simulativi, mentre esistono alcuni risultati per modelli analitici.

•Analisi dell'errore errore di troncamento

problema per simulazioni (run) molto lunghi

•metodi di riduzione dell'errore di calcolo

* doppia precisione

maggior occupazione di memoria

* uso di interi

arrotondamento di reali

non richiedono normalizzazione distorsione (invers. prop. alla scala)

permette anche la simulazione ad intervalli fissi

* somme parziali

sequenza divisa in sottosequenze e calcolo strutturato

* recupero dell'errore

uso di accumulatori per recuperare l'errore