Appunti del corso Sistemi di servizio e simulazione Massimo Roma

PROPOSIZIONE

Data una variabile aleatoria uniforme in [0,1) allora per ogni funzione di distribuzione continua F la variabile aleatoria

X=F^(-1)(U) ha come funzione di distribuzione la F

Vogliamo generare osservazioni da questa distribuzione di probabilità assegnata continua, questa proposizione dice: ho

una successione assegnata, faccio questo: mi calcolo

Osservazioni casuali estratte da una distribuzione

A partire dalle U applichiamo l’inversa della funzione di ripartizione, queste le possiamo considerare come osservazioni

estratte da una distribuzione continua

Esempio Ho le Ui che sono le osservazioni che stanno tra 0 e 1, per ognuna di queste trovo Xi

(funzione inversa)

Dim: Funzione di distribuzione di X. La dimostrazione sarà che

F è di ripartizione, quindi non decrescente. Ho che:

Quindi posso sostituire sopra

Può capitare che la F sia non definita quando la funzione non è strettamente monotona. In questi casi si usa la

PSEUDO INVERSA

Basta definire

Esempio

Voglio generare osservazioni casuali da una distribuzione esponenziale

Qualcuno mi dà delle osservazioni casuali

Calcolo l’inversa

Passiamo da osservazioni pseudocasuali in 0,1 a osservazioni estratte da diverse distribuzioni

Osservazione:

Osservazioni pseudocasuali in 0,1

Sono anche queste osservazioni pseudo-casuali in [0,1)

Cambia la correlazione, non ottengo le stesse Xi nei due casi. Il cambiamento della correlazione sarà importante quando

parleremo di teniche per la riduzione della varianza

Vediamo ora come si procede nel caso discreto

Caso discreto

Vediamo graficamente come si fa Formalmente devo determinare il più

piccolo valore di ksegnato tale che

E porre

Tesi

Dobbiamo far vedere che

Caso in cui abbiamo difficoltà a calcolare l’inversa:

In questo caso devo scrivere in forma esplicita la funzione inversa, può

non essere sempre possible

11 mag 2018

In riferimento ad un sistema a coda devo generare tempi di interarrivo e tempi di servizio.

Generare osservazioni casuali da distribuzioni di probabilità.

La maggior parte dei metodi si basano sulla generazione di osservazioni casuali uniformemente distribuite nell’intervallo

[0,1). Generiamo realizzazioni di variabili aleatorie.

Vogliamo far sì che tutti gli infiniti numeri in [0,1) possano comprarire nella successione con la stessa probabilità. Utilizziamo

un algoritmo di tipo deterministico, è inevitabile che la generazione di osservazioni casuali venga fatta in maniera

deterministica.

Con opportune scelte di m, a, c si riesce ad avere delle osservazioni che se analizzate con metodi statistici sono buone

approssimazioni di osservazioni davvero distribuite uniformemente in [0,1). Noi generiamo solo numeri razionali, se

prendiamo numeri m molto grandi i punti generati sono molto densi, la densità è una proprietà topologica che permette di

approssimare anche i numeri irrazionali attraverso una sequenza di numeri razionali.

Abbiamo due metodi per trasformare i dati.

Esercizio esame del 07/01/2008

Si vuole generare una succesione di osservazioni casuali da una distribuzione triangolare, che ha per funzione di

distribuzione la seguente:

Con il metodo della trasformazione inversa (dobbiamo definirla). Generare i primi 4 termini della successione utilizzando

come generatore di numeri pseudocasuali in [0,1) un generatore congruenziale lineare moltiplicativo (c=0) con seme 3 m=5

e a=3.

Svolgimento:

Dobbiamo vedere se la funzione è invertibile.

Tra 0 e 1 è un arco di parabola, per x tra 1 e 2 è un arco di parabola con la concavità verso il basso, poi vale 1

Funzione continua, nell’intervallo [0,2] è strettamente monotona crescente, quindi

l’invertibilità è garantita.

Poiché è definita per casi dei valori delle ascisse anche per l’inversa sarà uguale.

Il generatore congruenziale lineare ha questa espressione:

Esame 11/02/2009

Trasformazione inversa

Generatore congruenziale lineare

Inverto la funzione: Cambio segno per poter riapplicare il log

Dobbiamo usare questa

Generare le prime 4 osservazioni Fare i conti

Esercizio di esame

Dstribuzione di Cauchy

Trasformazione inversa

Generatore congruenziale lineare:

Quando facciamo la trasformazione inversa la lasciamo come parametrica, poi all’ultimo ci mettiamo i numeri

Funzione monotona crescente, possiamo fare l’inversa su tutto l’asse reale

Questa è la trasformazione inversa

Esame 19/12/2014

Distribuzione la cui densità di probabilità è la seguente:

Dobbiamo trovare la funzione di ripartizione, bisgona fare l’integrale

Dovremmo verificare che non sia una densità, cioè:

In questo caso è così, in teoria si dovrebbe fare questa verifica e poi la continuità, quindi vedere quanto fa F(1) da destra e

da sinistra È una funzione invertibile in [0,2]

Ora a partire da questa si fa la stessa cosa che negli esercizi precedenti.

Metodo acceptance-rejection

Supponiamo di voler generare osservazioni estratte da una distribuzione di probabilità che ha per funzione di ripartizione F

e la densità f. Supponiamo di disporre di un metodo per generare osservazioni casuali da un’altra distribuzione, che ha

densità g.

Genero osservazioni Y (che non è la distribuzione desiderata) poi si accettano o si rifiutano quelle della distribuzione la

cui densità è quella desiderata f. L’accettazione o il rifiuto avvengono con probabilità proporzionale al rapporto

Si prende questo rapporto e si cerca una costante che sia un upper bound di questo. Si cerca una c tale che risulti f/c

minore o uguale c per ogni y

Passo 1: Si genera una osservazione casuale della variabile aleatoria y, quella della distribuzione di appoggio

Si genera un numero casuale U della distribuzione uniforme in [0,1) indipendente da Y

Passo 2: Se risulta che U è minore o uguale di f(Y)/cg(Y) allora c’è l’accettazione, si pone X=Y e stop, altrimenti si torna al

Passo 3: passo 1 e si itera

Se in g ci mettiamo 1 allora anche le y sono numeri in [0,1), possiamo farlo perché la g la scegliamo noi.

Accettiamo quando si verifica l’evento, quello che dovremmo fare è cercare la probabilità che questo evento accada, è

un evento condizionato.

In termini generali il tipo di distribuzione di probabilità che mi aspetto per le x generate in questo modo è la

distribuzione di probabilità delle y condizionata all’accettazione.

Proposizione:

La variabile aleatoria X generata con il metodo A-R ha densità di probabilità f. (Questo è il risutato teorico che ci dice che

l’algoritmo funziona)

Dim:

Ricaveremo le espressioni di alcuni pezzi pioi le metteremo insieme per avere il risultato finale.

Questa la teniamo da parte

Nell’algoritmo ci sta una richiesta che le u sono generate indipendentemente

Calcoliamo ora dalla x. Se sono indipendenti questa probabilità condizionata è uguale alla

probabilità in cui viene meno il condizionamento.

Mettiamo da parte anche questo

Mettiamo da parte anche questo

La probabilità al denominatore è venuta 1/c

quindi sostituisco

Ho fatto vedere che la funzione di distribuzione di X è uguale a F(x), cioè la distribuzione desiderata.

Il test sostanzialmente è il test che fa tonrare le cose, c serve a far tornare i conti con la densità se no rimarrebbe

una costante. Esempio

Osservazioni casuali da variabile aleatoria con densità

(È la distribuzione β con parametri 1 e 2)

Qui usare il metodo dell’inversa sarebbe difficile da applicare. Applichiamo il metodo alternativo della accettazione. Devo

appoggiarmi ad una distribuzione nota della quale so generare le osservazioni. Devo quindi inventarmi una g(x) densità di

probabilità per la quale dispongo di un mertodo per generare osservazioni casuali.

Prima cosa che serve è il calcolo della c, che era la limitazione superiore.

Potremmo riuscire a determinre con delle maggiorazioni a priori, se no calcolo il punto di

massimo, sostituisco e trovo il valore massimo assunto dalla funzione.

Per far vedere che è un massimo si calcola la derivata seconda per x=1/4 ci accorgiamo che è minore di 0 quindi abbiamo

un punto di massimo relativo.

Per trovare c devo fare

Non dobbiamo per forza trovare il massimo, dobbiamo trovare solo una limitazione superiore, anche più grande del

massimo. In certi casi conviene trovare il punto di massimo ma andrebbe bene qualsiasi punto.

Test:

Abbiamo il test, ora possiamo scrivere il metodo

In genere dobbiamo solo scrivere lo schema del metodo, se non espressamente richiesto non dobbiamo generare i dati.

Passo 1: genero una osservazione casuale U1 (devo generare la Y)

Passo 2: genero osservazione casuale U2 U(0,1) (che sarebbe la U)

Passo 3: se U (cioè U2): Altrimenti si torna al passo 1

17 mag 2018 Progettazione di una simulazione

L’estensione dei file di Arena è sempre d.o.e

D.O.E

Cose da tenere sotto controllo:

➡ dobbimo utilizzare le statistiche per interpretare i risultati della simulazione, purtroppo però i risultati delle simulazioni

sono correlati e non indipendenti. Primo problema: I PROCESSI DI OUTPUT NON SONO INDIPENDENTI.

➡ per garantirci una certa accuratezza predefinita nei dati di uscita dobbiamo fare un certo numero di repliche: il carico

computazionale richiesto potrebbe essere non banale. Ovvero per raccogliere la quantità di dati necessaria affinché la

statistica sia significativa potremmo avere tempi molto elevati: POSSIBILE ELEVATO CARICO COMPUTAZIONALE.

Dalle slide

n è il numero delle repliche, m la lunghezza delle repliche

Supponiamo di avere i dati di output di una simulazione: questi dati dal punto di vista teorico li potremmo vedere (li

chiamiamo Yi) come delle realizzazioni di variabili aleatorie.

Per noi i dati di uscita sono interpretabili come un processo stocastico Yi a tempo discreto.

Le Yi potrebbero essere il tempo passato in coda dell’i-esimo utente oppure una qualche misura di prestazione che mi

interessa. Queste Yi nella maggior parte dei casi non sono indipendenti ma correlate, così non possiamo applicare i

metodi standard della statistica. Allora si fanno un certo numero di repliche nel seguente modo:

Siccome le repliche sono indipendenti ogni riga è indipendente dalle altre righe.

Faccio tante righe ma invece di ragionare per righe ragiono per colonne. Ogni volta che prendo un elemento questo

appartiene ad una replica diversa, queste righe sono indipendenti quindi i valori appartengono a repliche diverse.

Ragionando per righe nella tabella riesco a risolvere il problema dell’indipendenza.

Una grossa distinzione: sono interessato a misure di prestazione del sist