Modelagem e Análise de Sistemas de Computação Aula...

Figueiredo – 2009

Modelagem e Análise de Sistemas de Computação

Aula 19Aula de hoje

Lei dos grandes números

Calculando integrais

Gerando outras distribuições

Método da transformada inversa

Aula passadaIntro a simulaçãoGerando números pseudo-aleatórios

Figueiredo – 2009

Lei dos Grandes NúmerosVocê já deve conhecer (intuitivamente)

Experimento: jogar n vezes dado com seis faces

D : resultado de uma jogada

N1(n) : número de vezes que

resultado é 1

F1(n) : fração de vezes que

o resultado é 1 F 1 n =N 1 n

n

Figueiredo – 2009

Lei dos Grandes Números

F 1 n =N 1 n

nRealizar experimento (jogar o dado)

quanto vale F1(10)?

e F1(100)?

e F1(1000)?

F1(n) converge para P[D = 1]

quando n tende ao infinito!

P[D = 1] = 1/6

prob. do resultadoser igual a 1

Figueiredo – 2009

Lei dos Grandes NúmerosFrequência relativa do resultado de um experimento aleatório converge para sua probabilidade

Atribui significado físico a um conceito abstrato (probabilidade)

probabilidade existe!

números (quando muitos) convergem

Resultado fundamental em probabilidade e estatística

Figueiredo – 2009

Lei dos Grandes NúmerosGeneralização: média de uma sequência de v.a. (iid) converge para seu valor esperado

Média amostral: X n=∑i=1

nX i

n

X n E [ X ] quando n tende ao infinito

Sequência (iid): X 1 , X 2 , . . . , X n

Variável aleatória: XValor esperado: E [ X ]

E [ X ]=E [X i ]para todo i

Convergência:

Figueiredo – 2009

ExemploExperimento: jogar um dado

X v.a. que indica o resultado

Xi v.a. que indica o resultado

do i-ésimo experimento

3, 1, 2, 5, 6, 3, 2, 1, 4, 4, 2, 3, 5, 6, 1, 2, 2, 5, 3, 1.

Sequência de resultados de experimentos repetidos

Média: X n=∑i=1

nX i

n6 12 0

=3 . 0 5

Quanto vale E[X]? E [ X ]=3 . 5

=

Figueiredo – 2009

Lei dos Grandes NúmerosDuas versões

Lei fraca e lei forte

Diferem na forma como a convergência é definida

X n=∑i=1

nX i

n

∞

Seja X1, X

2, ..., X

n uma sequencia de v.a. iid

com valor esperado

Seja a média da sequência

Figueiredo – 2009

Lei dos Grandes Números

Lei fraca dos grandes números

para qualquer

limn∞

P [∣ X n−∣]=1

0

Lei forte dos grandes números

convergência em probabilidade

P [ limn∞

X n=]=1 convergência quase certa (almost surely)

Média converge para valor esperado!

Figueiredo – 2009

Lei Fraca dos Grandes Números (Prova)

Caso onde Xi possui variância

X n

2∞

é uma variável aleatória

E [ X n]=

Temos então

Var [ X n]=

2

nLembrando desigualdade de Chebyshev

P [∣X −∣k]1k 2

Figueiredo – 2009

Lei Fraca dos Grandes Números (Prova)

Dado

=k

n

0

Escolher k, tal que

P [∣X n−∣k

n]1− 1

k 2

Aplicando Chebyshev a X n

P [∣X n−∣]1−

2

n2

Substituindo, temos Converge para 1 quando n vai ao infinito

Figueiredo – 2009

Aplicação NuméricaAvaliação numérica de integrais

Como calcular a seguinte integral?

=∫0

1g xdx

Se U é uma v.a. Uniforme [0, 1], então

E [ g U ]=∫0

1g x f U x dx

∫0

1g xdx=

=

Figueiredo – 2009

Resolvendo Integrais

Considere uma sequência U1, U

2, ..., U

k de

v.a. independentes e uniforme [0,1]

∑i=1

kg U i

kE [ g U ]= k ∞quando

Como calcular E[g(U)] ?

Lei dos grandes númerossequência de v.a. i.i.d. converge para média

Gerar várias v.a. uniformes, aplicar g() aos valores, e tirar a média

Figueiredo – 2009

Resolvendo Integrais

Conhecido como Método de Monte Carlo

Generalização para quaisquer limites de integração

mudança de variáveis

Generalização para integrais múltiplasgeração de vetor de uniformes (iid)

muito poderoso

Figueiredo – 2009

Exemplo: Estimando Pi

X, Y : v.a. independentes uniforme (-1, 1)

definem um ponto dentro do quadrado

(-1, 1)

(-1, -1)

(1, 1)

(1, -1)

.

Definir v.a. Indicadora

Estar dentro do círculo: I(x2 + y2 <= 1)

Calcular sua probabilidade e valor esperado

Figueiredo – 2009

Gerando Outras DistribuiçõesComo gerar v.a. de outras distribuições?

P [X = x j]= p j

V.a. discreta X

Utilizar a uniforme!

∑ jp j=1

Como gerar valores de X?

p1 p 2 p 3 p 4 p 50

. . .

1. . .

U(0,1)

x 1 x 2 x 3 x 4 x 5

Figueiredo – 2009

Gerando V.A. Discreta

P [ X=x j ]=p j

V.a. discreta X

∑ jp j=1

Se e U é uniforme (0,1) , então0ab1P [aU b ]=b −a

Assim, temos

P [ X=x j ]=P [∑i=1

j−1p iU ∑i=1

jp i]=p j

Figueiredo – 2009

Gerando uma GeométricaP [ X=i ]=p q i−1X é geométrica :

X ocorrência do primeiro sucesso de um experimento independente

p p q p q 2 p q 3 p q 40

. . .

1. . .

U(0,1)

1 2 3 4 5

P [ X j−1 ]=1−P [X j−1 ]

= 1 – P[primeiros j-1 experimentos são falhas]

= 1−q j−1

Figueiredo – 2009

Gerando V.A. Contínua

Método da Transformada Inversa generalização da técnica que acabamos de ver

Mesma idéia: utilizar uniforme(0,1)

0

1

x

FX(x)U(0,1)

x

Função de probabilidadecumulativa

Figueiredo – 2009

Método da Transformada

Inversa 0

1

x

FX(x)U(0,1)

x

Seja U uniforme (0, 1) e X uma v.a. com função distribuição cumulativa F. X é dado por:

X =F −1U

onde F-1 é a inversa de F (valor de x para o qual F(x) = u)

Figueiredo – 2009

Método da Transformada Inversa (Prova)

Seja F uma função de probabilidade cumulativa

Seja X = F-1(U) e U uma v.a. Uniforme (0,1)

Seja FX a distribuição de X

Provar que FX(x) = F(x)

F X x =P [X x ]P [F−1

U x ]=

P [F F −1U F x ]

P [U F x ]

F x

=

=

=

definição

Equivalência deeventos e monotonicidade de F

definiçãouniforme

Figueiredo – 2009

Gerando uma Exponencial

Seja X v.a. exponencial com parâmetro

F X x =1 −e− x

x=F X−1u

F x =u

Pelo método, temos que

Então

1−e − x=u

e− x=1−u

− x= l o g 1−u

x=−1

l o g 1−u x=−1

l o gu

(1-U) também é uniforme(0,1)

F x =F F −1u

Figueiredo – 2009

Gerando um Processo de Poisson

Como gerar eventos de acordo com o processo de Poisson?

Seja N(t) uma v.a. Poisson com parâmetro

eventos

t

P [N t o=k ]=

t o

k

k !e−t o

Seja S o tempo entre chegadas

Qual a distribuição do tempo entre chegadas?

S

P [S t ]=? Exponencial!

Figueiredo – 2009

Gerando um Processo de Poisson

Gerar sequência de exponenciais com parâmetro

eventos

t

Quantos eventos em um intervalo to?

S

P [S t ]=e−t

Gerar exponencias em sequência até que soma dos tempos seja maior que t

o