Rosa Leão – 2017

Estatística e Modelos Probabilísticos - COE241

Aula de hoje

Algoritmo para simular uma fila

Medidas de interesse

Média amostral

Teorema do Limite Central

Aula passada

Geração de variáveis aleatórias:

Transformada Inversa

Acceptance-Rejection Method

Rosa Leão – 2017

Simulação

O que é uma simulação?realização da evolução de um sistema estocástico no tempo

Como caracterizar o sistema em um instante de tempo?

através de seu estado

Como construir um simulador?programa que “acompanha” evolução do estado do sistema no tempo

Rosa Leão – 2017

Tempo Médio na Fila + Servidor

Como obter tempo médio via simulação?

Tempo médio na fila + servidor:tempo desde o instante de chegada até o instante de saída

Wi : tempo de espera do i-ésimo elemento a

chegar na fila (v.a.)

W =1n∑i=1

nW iEstimativa

Rosa Leão – 2017

Fila - Parâmetros

O que precisamos saber para simular uma fila?

Processo de chegada

Tempo de serviço

Capacidade da fila

Política de atendimento

aleatório

determinístico

Parâmetros das v.a.

ex. Poisson (taxa)

Rosa Leão – 2017

Fila - Estado

Qual o estado do sistema?número de elementos na fila

Estado evolui (muda) em instantes discretos no tempo

Em que instantes?

instante de chegada e instante de saída

Rosa Leão – 2017

Fila - Eventos

Ações que modificam o estado do sistema

Dois eventos: chegada e saídaO que ocorre em cada um destes eventos?

Chegadaanotar o instante de chegada do elemento

incrementar a fila

Saídaanotar instante de saída do elemento

decrementar a fila

Quando atualizar o tempo?

Quando gerar próxima chegada ou saída?

Rosa Leão – 2017

Simulação – Variáveis

Variáveist: representa o instante de tempo que o simulador se encontra

variáveis de estado: representam o estado do sistema no tempo t

variáveis de interesse: representam valores que permitem o cálculo de medidas de interesse

Rosa Leão – 2017

Simulação – EventosEventos

ações que modificam o estado do sistema

Ao ocorrer um evento

variáveis são atualizadas (tempo, estado do sistema, medidas de interesse)

Permite seguir o modelo no tempo

t

eventos

variáveis são atualizadas(tempo, estado, etc)

Rosa Leão – 2017

Lista de EventosLista contendo todos os eventos que irão ocorrer no futuro

tipo de evento, instante de ocorrência do evento

ordenada por ordem de ocorrência

E1

T1

E2

T2

E1

T3

E1

T4

Lista de Eventos

Simulador processa próximo evento da listaremove evento da lista

Quando adicionar eventos na lista?ao processar um evento

Rosa Leão – 2017

Simulador Genérico

1.Inicializar variáveis

2.Inserir um ou mais eventos na lista de eventos

3.Enquanto não chegar ao fim da simulação

4.Remover próximo evento da lista de eventos

5.Processar evento

Dá início a simulação

Definir estado inicial

Condição para terminar simulação (ex. t > t

max)

Diminui lista de eventos

Atualiza variáveis, gera eventos, gera outras informações

Rosa Leão – 2017

Simulação da Fila

Estado: N (número de elementos no sistema)

Eventos: EC , E

S (chegada e saída)

Tempo: t

Condição de parada: t > tmax

Estado inicial: fila vazia (N = 0)

Início: chegada no instante 0 (EC, 0)

EC

0Lista de Eventos

Rosa Leão – 2017

Simulação da Fila

Algumas variáveisN

C : número total de chegadas até o momento

NS : número total de saídas até o momento

N : número de elementos na fila

C(i) : instante de chegada do i-ésimo elemento

S(i) : instante de saída do i-ésimo elemento

Rosa Leão – 2017

Inicialização1.t = 0

2.N = 0

3.NC = 0

4.NS = 0

5.Adicionar evento (EC, 0)

Rosa Leão – 2017

Evento de Chegada1.t = t

E // t

E = tempo de ocorrência do evento

2.N = N + 1

3.NC = N

C + 1

4.C(NC) = t

5.Gerar x ~ FX(x) // tempo até próxima chegada

6.Adicionar evento (EC, t+x)

7.Se (N = 1) // fila estava vazia

8. Gerar y ~ FS(y) // tempo de serviço

9. Adicionar evento (ES, t+y)

Rosa Leão – 2017

Evento de Saída1.t = t

E

2.N = N – 1

3.NS = N

S + 1

4.S(NS) = t

5.Se (N > 0) // fila não está vazia

6. Gerar y ~ FS(y) // tempo de serviço

7. Adicionar evento (ES, t+y)

Rosa Leão – 2017

Medidas de Interesse

Utilização (fração de tempo servindo)

Tempo médio na fila + servidor

Número médio na fila

Fração de elementos descartados (fila finita)

Fração de tempo que a fila possui mais do que k elementos

Rosa Leão – 2017

UtilizaçãoN(t)

t

Sistema ocioso

Sistema ocupado

Utilização: fração de tempo que o sistema está ocupado

Medir os tempos ocioso e ocupado

Rosa Leão – 2017

Tempo médio na fila + servidor

S(i) – C(i) : tempo em fila + servidor do i-ésimo elemento

W =1N S

∑i=1

N S

S i −C i

Uma estimativa do tempo médio na fila + servidor

Rosa Leão – 2017

Número médio na fila

N(t)

t

Como medir E[N] (até certo T grande)?

E[N] = ∫T

N t d t

T

Rosa Leão – 2017

Número médio na filaN(t)

t

T : tempo total

E[N] =

∑i= 0

∞

T i=T

Ti : tempo que o sistema passa com i elementos

1/T∑i=0

∞

i T i 1/T∫t= 0

t=TN t dt=

Rosa Leão – 2017

Fração de elementos descartados

Fdescarte

: Nd /N

C

Nd : número de elementos que chegam e

encontram a fila cheia

NC : número total de chegadas até o momento

Rosa Leão – 2017

Como estimar medidas de interesse

Medida de interesse X

ex. X = “número de pessoas que chegaram e viram a fila vazia nas primeiras 2 horas”

Resultado da simulação fornece uma amostra de X

O que acontece se executarmos o simulador novamente?

Outro valor de X

se usarmos outra semente

independente do primeiro valor

Rosa Leão – 2017

Como estimar medidas de interesse

Supor medida de interesse X

X é uma variável aleatória

E[X] não é conhecido

Xi : resultado da i-ésima execução

supor n execuções do simulador

Como estimar E[X]?

calculando a média amostral de X

Rosa Leão – 2017

Média amostral

Xi : resultado da i-ésima execução

X1, ..., X

n : sequência de v.a. iid

X n=1n ∑i=1

nX i

Média amostral variável aleatória:soma de v.a. é uma outra v.a.

Rosa Leão – 2017

Qualidade do estimadorX

n : estimador para média real

Para ser sem tendência (unbiased)

É necessário que

Qualidade do estimador depende da variância

E [X n]=

Var [Xn]=Var [1 /n∑i=1

nX i]

Var [Xn]=1/n2∑i=1

nVar [X i]

Var [Xn]=nσ2/n2=σ2/ndiminui com n

Rosa Leão – 2017

Soma de Variáveis Aleatórias

Seja X1, X

2, ..., X

n uma sequencia de v.a. iid

com valor esperado e variância μ<∞ σ2<∞

Sn=∑i=1

nX iSeja a soma da sequência

Para onde vai esta soma?soma possui valor único (para um dado n)?

Rosa Leão – 2017

Soma de Variáveis Aleatórias

S n=∑i=1

nX iSeja a soma da sequência

Var [Sn]=Var [n X n]=n2Var [Xn]

Var [Sn]=n2σ2/n=nσ2

E sua distribuição?

o que podemos afirmar?

Sabemos que :

Logo:

E[ Sn]=E [n Xn]=n E [X n]=nμ

P [S nz ]=?

Sn=n Xn

Rosa Leão – 2017

Teorema do Limite CentralDistribuição da soma de v.a. iid converge para distribuição Normal

Resultado fundamental em probabilidade

Seja X1, X

2, ..., X

n uma sequencia de v.a. iid

com valor esperado e variância

Seja a soma da sequência

quando

Então Normal com mesma média e variância

∞ 2∞

S n=∑i=1

nX i

n ∞P [S n≤z ] N n , n 2

Rosa Leão – 2017

Distribuição NormalImportante distribuição (conhecida também como distribuição de Gauss)

Dois parâmetros: média e variância

Normal padrão:

∞ 2∞

=0 , 2=1

Exemplos da distribuiçãoNormal (função de densidade) – diferentes parâmetros

Rosa Leão – 2017

NormalizaçãoSeja X

1, X

2, ..., X

n uma sequencia de v.a. iid com

valor esperado e variância

Seja a nova sequência

Transformar a soma Sn numa v.a. com valor

esperado 0 e variância 1

E[Zn]=E [Sn−nμ

σ √n]=0 Var [Zn]=Var [

Sn−nμ

σ √n]=1

Temos que:

P [Z nz ] z quando n∞

EntãoNormal padrão – N(0, 1)

∞ σ2<∞

Z n=Sn−nμ

σ√n

Rosa Leão – 2017

Teorema do Limite CentralSeja X

1, X

2, ..., X

n uma sequencia de v.a. iid

com valor esperado e variância ∞ 2∞

limn∞

P[ X n−

/ n z ]= z

convergência em probabilidade

função de distribuição cumulativa da Normal padrão

Z n=Sn−n

nX n−

/ n=

dividindo numerador e denominador por n

X n=1n

S nonde

média amostral

Resultado

Rosa Leão – 2017

Comparação com Grandes Números

Qual é a diferença?

Lei dos grandes números

média converge para seu valor esperado

Teorema do Limite Central

distribuição converge para Normal

limn ∞

P [ X n−

/n z ]= z

limn ∞

P [∣X n−∣]=1

Rosa Leão – 2017

Teorema do Limite Central na Prática

Na prática n é finito

TLC vale no limite

Com n grande, mas finito resultado é aproximado

usaremos esta aproximação

quando n é suficientemente grande (ex. n > 30)

P [S n≤z ] N n , n 2