Apostila - Aguiar

Embed Size (px)

DESCRIPTION

Apostila sobre Avaliação e Desenvolvimento, feita pelo professor, Paulo Aguiar da UFRJ

Text of Apostila - Aguiar

  • Avaliacao e DesempenhoMAB-515, DCC/UFRJ

    Apostila

    Paulo Aguiar, DCC/IM

    27 de julho de 2013

    1

  • Conteudo

    1 Motivacao 6

    2 Revisao de Analise Combinatoria 10

    3 Alocacao de bolas em urnas 14

    4 Teoria de Probabilidade 15

    5 Eventos igualmente provaveis 18

    6 Probabilidade Condicional 21

    7 Problemas de Aplicacao 23

    8 Aplicacao: Confiabilidade (Reliability) 26

    9 Experimentos de Bernoulli 28

    10 Variaveis Aleatorias 29

    10.1 Variavel Discreta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

    10.2 Funcao Distribuicao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

    10.3 Funcoes Singulares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

    10.4 Variavel Aleatoria Contnua . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

    10.5 Propriedade da Falta de Memoria . . . . . . . . . . . . . . . . . . . . . . . . 35

    10.6 Relacao entre Distribuicao Exponencial e Processo Poisson . . . . . . . . . . 36

    10.7 Variavel Aleatoria Mista . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

    11 Funcoes de Variaveis Aleatorias 39

    11.1 Metodologia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

    11.2 Geracao de Distribuicoes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

    12 Distribuicao Conjunta Cumulativa de V.As. 44

    2

  • 13 Propriedades de Variaveis Aleatorias 49

    13.1 Media, Esperanca ou Valor Esperado . . . . . . . . . . . . . . . . . . . . . . 49

    13.2 Momentos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

    13.3 Esperanca Condicional . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

    13.4 Variancia Condicional . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

    14 Transformadas 60

    14.1 Transformada de Laplace Unilateral para Funcoes Contnuas . . . . . . . . . 60

    14.1.1 Analiticidade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

    14.1.2 Propriedades da Transformada de Laplace . . . . . . . . . . . . . . . 65

    14.1.3 Alguns Pares de Transformadas de Laplace . . . . . . . . . . . . . . . 67

    14.2 Transformada Z para Funcoes Discretas . . . . . . . . . . . . . . . . . . . . . 68

    14.2.1 Analiticidade da Transformada Z dentro do crculo unitario . . . . . . 73

    14.2.2 Propriedades da Transformada Z . . . . . . . . . . . . . . . . . . . . 74

    14.2.3 Pares de Transformadas Z . . . . . . . . . . . . . . . . . . . . . . . . 75

    15 Teoria de Filas 76

    15.1 Introducao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76

    15.2 A fila M/M/1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

    15.3 A fila M/G/1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81

    15.3.1 A Vida Residual do Servico . . . . . . . . . . . . . . . . . . . . . . . 81

    15.3.2 A Media do Perodo Ocupado . . . . . . . . . . . . . . . . . . . . . . 83

    15.3.3 A Transformada de Laplace da pdf do Perodo Ocupado . . . . . . . 84

    15.3.4 A transformada Z do numero presente na fila M/G/1 . . . . . . . . . 85

    15.3.5 A transformada de Laplace do tempo gasto na fila M/G/1 FCFS . . . 87

    15.4 A Fila M/G/1 com Ferias . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88

    15.4.1 O Perodo Ocioso na Fila M/G/1 com ferias . . . . . . . . . . . . . . 89

    15.4.2 O Perodo Ocupado na Fila M/G/1 com Ferias . . . . . . . . . . . . 91

    15.4.3 A transformada Z do numero presente na fila M/G/1 com ferias . . . 91

    3

  • 15.4.4 A transformada de Laplace do tempo gasto na fila M/G/1 com feriasFCFS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93

    15.5 Fila M/G/1 com disciplina LCFS sem interrupcao de servico . . . . . . . . . 94

    15.6 M/G/1 com Disciplina LCFS com interrupcao de servico e continuidade . . . 95

    15.7 M/G/1 com disciplina LCFS com interrupcao de servico sem continuidade . 96

    15.8 Sistema de Filas com Classes de Usuarios . . . . . . . . . . . . . . . . . . . . 98

    15.9 Lei da Conservacao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103

    15.10Redes de Filas M/M/1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104

    16 Desigualdades e Limites 108

    16.1 Normalizacao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108

    16.2 Funcao de Gauss ou Distribuicao Normal . . . . . . . . . . . . . . . . . . . . 110

    16.3 Teorema do Limite Central . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110

    16.4 Aproximando Distribuicoes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113

    16.5 Percentil . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114

    16.6 Estimadores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114

    16.6.1 Estimando a Media . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114

    16.6.2 Estimando a Variancia . . . . . . . . . . . . . . . . . . . . . . . . . . 115

    16.7 Intervalo de Confianca . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116

    16.7.1 Intervalo de Confianca para a Media de uma Populacao com VarianciaDesconhecida . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116

    16.7.2 Intervalo de Confianca para a Media de uma Populacao com VarianciaConhecida . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118

    16.7.3 Distribuicao 2 (chi-square) . . . . . . . . . . . . . . . . . . . . . . . 118

    16.7.4 Intervalo de Confianca para a Variancia de uma Populacao Normalcom Media Desconhecida . . . . . . . . . . . . . . . . . . . . . . . . . 118

    16.7.5 Intervalos Parciais de Confianca . . . . . . . . . . . . . . . . . . . . 120

    16.7.6 Intervalo de Confianca para Proporcoes . . . . . . . . . . . . . . . . 121

    16.7.7 Comparacao de Alternativas . . . . . . . . . . . . . . . . . . . . . . 123

    17 Simulacao 125

    4

  • 17.1 Geracao de Numeros (Pseudo) Aleatorios . . . . . . . . . . . . . . . . . . . . 125

    17.2 Simulacao de M/M/1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127

    17.3 Medidas de Desempenho . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130

    17.4 Calculo das Estatsticas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131

    17.5 Depuracao do Modelo Simulado . . . . . . . . . . . . . . . . . . . . . . . . . 131

    17.6 Metodo de Analise de Resultado . . . . . . . . . . . . . . . . . . . . . . . . . 132

    17.7 Da Escolha das Sementes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133

    18 Cadeia de Markov em Tempo Discreto 135

    18.1 Classificacao dos Estados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136

    18.2 Teoremas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139

    18.3 Tempo medio para ir de um estado a outro . . . . . . . . . . . . . . . . . . . 142

    18.4 Espaco de Estados Infinito . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143

    19 Cadeia de Markov em Tempo Contnuo 150

    19.1 CMTC Homogenea . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152

    19.2 Processo Nascimento e Morte (Birth-Death Processes) . . . . . . . . . . . . . 153

    19.3 Processo de Nascimento Puro com taxa constante . . . . . . . . . . . . . . . 156

    19.4 Solucao de CMTC em Equilbrio . . . . . . . . . . . . . . . . . . . . . . . . 157

    19.5 Tempo medio entre retornos a um estado . . . . . . . . . . . . . . . . . . . . 158

    19.6 Tempo medio para ir de um estado a outro . . . . . . . . . . . . . . . . . . . 160

    5

  • 1 Motivacao

    Experimento 1: Duas pessoas, A e B, lancam, a cada vez, uma moeda ao ar. Ganha ojogo quem tira CARA primeiro. Suponhamos que A inicia o jogo. Assuma:

    Probabilidade de dar CARA = P{CARA} = p, 0 < p < 1 Probabilidade de dar COROA = P{COROA} = 1 p

    Pergunta: Seria razoavel ter p = 1 ou p = 0? O que significaria?

    Queremos obter:

    P{ pessoa A ganhar o jogo } = PA= P{ quem comeca ganha}= Pinicia

    Solucao pelo metodo da enumeracao de todas as possibilidades:

    Evento Probabilidade Explicacao

    A ganha na jogada 1 pA ganha na jogada 3 (1 p)2p A perde, B perde e A ganhaA ganha na jogada 5 (1 p)4pA ganha na jogada 7 (1 p)6p PA = Pinicia

    n=0(1 p)2np = 1/(2 p)

    Recordacao: Serie Geometrica

    n=0

    qn = 1 + q + q2 +

    = 1 + q(1 + q + q2 + )

    = 1 + qn=0

    qn

    e entao

    n=0 qn = 1/(1 q).

    OBS.:

    n=0 qn tem que convergir e portanto 0 < q < 1.

    Em geral, an = a0qn1 e

    n=0 an =

    a01q .

    Tambem, Sn =n

    i=1 ai =a0anq1q , onde an = aoq

    n1.

    0chap1.tex, 07/09/09

    6

  • Solucao recursiva:

    Se A nao ganhar na primeira jogada, a partir da segunda jogada seria como se B estivesseiniciando o jogo naquele momento e a probabilidade de B ganhar seria igual a Pinicia = PA.

    Vamos montar o pensamento recursivo, condicionando na ocorrencia do resultado daprimeira jogada. A tecnica de condicionamento e muito importante na solucao de problemascomplexos.

    Podemos entao escrever:

    PA = P{A ganhar e deu cara na jogada 1} + P{A ganhar e deu coroa na jogada 1}= P{ A ganhar | deu cara na jogada 1} P{deu cara na jogada 1} +

    P{ A ganhar | deu coroa na jogada 1} P{deu coroa na jogada 1}= 1 p+ (1 p) P{ B nao ganha o jogo a partir da jogada 2}= p+ (1 p)(1P{B ganha o jogo a partir da jogada 2})= p+ (1 p)(1 Pinicia)= p+ (1 p)(1 PA), e entao, PA = 1/(2 p)

    Conceito: probabilisticamente o jogo se repete apos o resultado de