Baixe o app para aproveitar ainda mais
Prévia do material em texto
Processos Estocásticos Um processo estocástico é uma família de variáveis aleatórias que descreve a evolução de algum processo no tempo. Definição 1. Um processo estocástico {X(t), t ∈ T} é uma coleção de variáveis aleatórias onde t representa, na maioria das vezes, o tempo. X(t) são variáveis aleatórias que representam o estado do processo no tempo t. Se T é um conjunto enumerável, então {X(t), t ∈ T} é um processo estocástico discreto no tempo. Se T é um conjunto não enumerável, então {X(t), t ∈ T} é um processo estocástico contínuo no tempo. Exemplos: a) {Xn, n = 0, 1, 2, ....} é um processo estocástico discreto no tempo indicado por inteiros positivos. b) {Xt, t ≥ 0 } é um processo estocástico contínuo no tempo indicado por números reais positivos. O Espaço de Estados de um processo estocástico representa o conjunto de todos possíveis valores das variáveis aleatórias X(t). Cada um desses possíveis valores é denominado estado do processo Definição 2. Um processo estocástico contínuo {X(t), t ∈ T} possui incrementos independentes se para todos os inteiros t0 ≤ t1 ≤ t2 ≤ .... ≤ tn, as variávies aleatórias X(t1 )-X(t0), X(t2 )-X(t1 ), X(t3 )-X(t2), X(tn )- X(tn-1) são independentes. Definição 3. Um processo estocástico contínuo {X(t), t ∈ T} possui incrementos estacionários se X(t1+s)-X(t1) tem a mesma distribuição de X(t2+s)-X(t2), para todo t ∈ T. X(t) t 0 t 1 t 2 t 3 t n-1 t n t X(t) t 1 t 1 +s t 2 t 2 +s t Processo de Poisson ”Incerteza é a marca indelével do universo. Assim um evento terá, pela sua própria natureza, uma chance, maior ou menor, conhecida ou desconhecida, e sua probabilidade será relativa aos nossos conhecimentos naquilo que lhe diz respeito.” Poisson, 1837. (Sceaux, França) Dennis Poisson Um Processo de Poisson com parâmetro (ou taxa de chegada λ) é um processo estocástico contínuo no tempo {X(t), t ≥ 0 }, satisfazendo as seguintes condições: a) t = 0, X(0) = 0. b) Para todo t0 ≤ t1 ≤ t2 ≤ .... ≤ tn, os incrementos em intervalos não sobrepostos X(t1 )-X(t0), X(t2 )-X(t1 ), X(t3 )-X(t2), X(tn )- X(tn-1) são variáveis aleatórias independentes. c) Para t ≥ 0, s > 0 e k > 0, os incrementos apresentam Distribuição de Poisson: ( ) ( )[ ] ( ) t k e k tksXstXP λλ −⋅==−+ ! t – intervalo de tempo. k – número de eventos que ocorrem no intervalo de tempo t. (número de bits; pacotes; chamadas; requisições) O Processo de Poisson X(t), é um processo de contagem onde a probabilidade de ocorrência de um determinado número de eventos k em qualquer intervalo de tempo t é definido pela equação de Poisson. Exemplo 1: O número de requisições que chegam a um servidor é em média 30 requisições/min. Qual a probabilidade de chegarem 4 requisições no intervalo [t1, t1+ 10s]? streqksreqreq 104/5,0min/30 ==≡=λ ( ) ( )[ ] ( ) 1755,0 4 105,0410 105,0 4 11 =⋅ ⋅− ⋅−e ! ==tX+tXPk = 4 req t 1 t 1 +10 t t= 10sX(t) Propriedades do Processo de Poisson Propriedade 1. Na condição c, os incrementos são estacionários, pois a equação de Poisson não depende de s. Os incrementos dependem somente do comprimento do intervalo t. O valor esperado de uma variável aleatória de Poisson é dado por: ( ) ( )[ ] tsXstXE λ=−+ Considerando que os incrementos são estacionários a equação acima é válida para qualquer valor de s. Se s = 0: ( ) ( )[ ] tXtXE λ=− 0 Propriedade 2. A probabilidade que exatamente um evento ocorre em um intervalo de tempo arbitrariamente pequeno de comprimento h, dada pela equação de Poisson: ( ) ( )[ ] hr ehsXshXPP λλ −⋅==−+= 1 Expandindo em série de Taylor: ( ) ( ) ( ) ( ) ( )hOhP n hhhh hP r n r += − ++ − + − + − +⋅= λ λλλλ λ ! .... !3!2!1 1 321 O(h) representa qualquer função de h tal que: ( ) 0lim 0 = → h hO h A probabilidade que nenhum evento ocorra no intervalo h: ( ) ( )[ ] )(10 hOhesXshXPP hr +−===−+= − λλ A probabilidade de ocorre mais de um evento no intervalo h: ( ) ( )[ ] )()(21 hOhOsXshXPPr ≅−=>−+= Exemplo 2: Uma conversação em uma rede ad-hoc sem fio é severamente perturbada por sinais interferentes de acordo com o Processo de Poisson de taxa λ = 0,1 interferência/min. a) Qual a probabilidade que nenhum sinal interferente ocorra nos 2 primeiros minutos de conversação? ( ) ( )[ ] ( ) ( ) 8187,0 !0 21,0 ! 002 21,0 0 =⋅ ⋅ =⋅⋅==− ⋅−⋅− ee k tXXP t k λλ b) Dado que os 2 primeiros minutos não sofrem interferências qual é a probabilidade que no próximo minuto, precisamente um sinal interferente ocorrerá? Eventos Independentes: Para todo t, os incrementos em intervalos não sobrepostos são variáveis aleatórias independentes. ( ) ( ) ( ) ( )[ ] ( ) ( )[ ] ( ) 0905,0 !1 11,0 123002/123 11,0 1 =⋅ ⋅ ==−≡=−=− ⋅−eXXPXXXXP Exemplo 3: Durante um certo intervalo de tempo [t1, t1+10s] chegam ao roteador em média 40 pacotes/s. Um provedor de serviço de Internet (ISP) quer determinar a probabilidade de chegarem 20 pacotes no intervalo [t1, t1+ 1s] e 30 pacotes no intervalo [t1, t1+3s]. Considere o processo de chegada Possoniano. Eventos Independentes: Para todo t, os incrementos em intervalos não sobrepostos são variáveis aleatórias independentes. ( ) ( ) ( ) ( )[ ] ( ) ( ) ( ) ( )[ ]101t3t20t1t30t3t20t1t 11111111 =XX,=XXP==XX,=XXP +−+−+−+−+ Eventos independentes – a probabilidade conjunta será dada pelo produto das duas: ( ) ( )[ ] ( ) ( )[ ] ( ) ( ) 26240 10 140 20 1111 1010 240 20 140101t3t20t1t −⋅−⋅− ⋅⋅⋅⋅⋅+−+⋅−+ =e ! e ! ==XXP=XXP Teoremas do Processo de Poisson Teorema 1 Um processo de contagem N(t) que satisfaz às condições: a) N(0) = 0. b) N(t) tem incrementos estacionários e independentes. c) P[N(h)=1]= λh + O(h) d) P[N(h)>1]= O(h) Então o processo N(t) é Poisson com taxa λ. Prova. Temos que demonstrar que as condições c) e d) são equivalentes às condições c) do processo de Poisson. ( )[ ]ntNPtPn ==)( k=0 k=1X(t) 0 1 2 3 t X(t) t1 t1+1 t1+3 t k=20 k=10 Demonstrando para n=0: ( )[ ] ( )[ ]0)(,0)(0)(0 ==−+==+=+ tNtNhtNPhtNPhtP ( ) ( )[ ] [ ]0)(0)(0 =⋅=−+=+ tNPtNhtNPhtP ( ) ( )[ ] [ ]0)(00 =⋅==+ tNPhNPhtP Intervalos não sobrepostos Temos: ( )[ ] ( )[ ] ( )[ ] 101 10 ==+=→== ∑∑ ∞ = ∞ = kk khNPhNPkhNP ( )[ ] ( )[ ] ( )[ ]∑ ∞ > =−=−== 1 110 k khNPhNPhNP ( )[ ] ( ) hhOhOhhNP λλ −=++−== 1)()(10 ( ) )()()(1)()( 00000 tPh tPhtP htPhtP ⋅−= −+ ⇒−⋅=+ λλ Observe a derivada Po´(t) Seja: tectP ⋅−⋅= λ)(0 . Para determinar o valor de c: ( )[ ] 100)(0 =→=== ⋅− ceNPtP tλ . Por analogia: ( ) ( )[ ] ( ) t k e k tksXstXP λλ −⋅==−+ ! Teorema 2 Seja {X(t), t ≥ 0} um processo de Poisson com taxa λ>0 e sejam t0 ≤ t1 ≤ t2 ≤ .... ≤ tn, os tempos de ocorrência de eventos sucessivos. Então os intervalos de tempo que separam dois eventos sucessivos (interarrival times) ℑn = tn – tn-1 são variáveis aleatórias independentes e identicamente distribuídas exponencialmente com média 1/λ. Pacotes espaçados de forma aleatória ℑn possui distribuição exponencial com média 1/λ Prova: Para qualquer s ≥ 0 e qualquer n ≥ 1 o evento {ℑn > s} é equivalente ao evento { X(tn-1+s)– X(tn-1 )= 0}, ou seja, não ocorreram chegadas no intervalo s. { } [ ] Snnn etXstXPsP ⋅−−− ==−+=>ℑ λ0)()( 11 O que implica que qualquer intervalo de chegada tem uma distribuição exponencial: { } XnX exPxF ⋅−−=≤ℑ= λ1)( XX X edx xF xf ⋅−⋅== λλ )( )( Teorema 3 Dado que exatamente um evento de um processo de Poisson {X(t), t ≥ 0} tem ocorrido no intervalo [0, t] o instante de ocorrência deste evento é uniformemente distribuído no intervalo [0, t]. Prova: Representando por s o instante de ocorrência do evento, 0 ≤ s ≤ t, devemos calcular a probabilidade [ ] { } { }[ ]{ }[ ]1)(1)( 1)(/ 11 = =≤ℑ ==≤ℑ tXP tXsP tXsP Usando a equivalência de eventos: { } { }1)()( 001 =−+↔≤ℑ tXstXs Devido à estacionaridade do Processo de Poisson: { } { }[ ] { } { }[ ] { } { }[ ]0)()(1)(1)(1)(1)(1 =−======≤ℑ sXtXsXtXsXtXs Aplicando a independência de incrementos sobre intervalos não sobrepostos, resulta: [ ] [ ] [ ][ ]1)( 0)()(1)( 1)(/1 = =−⋅= ==≤ℑ tXP sXtXPsXPtXsP Por meio da equação de Poisson: [ ] t s et eestXsP t StS = ⋅ ⋅⋅⋅ ==≤ℑ − −−− λ λλ λ λ )( 1 1)(/ Teorema 4 Se X(t) e Y(t) são dois processos de Poisson independentes com taxas λx e λy, então Z(t) = X(t) + Y(t) também é Poisson com taxa λz = λx + λy. Prova. { } { } { }sss YXZ >ℑ>ℑ↔>ℑ [ ] [ ] [ ] [ ] ( ) SSSSYXYXZ ZYXYX eeeesPsPssPsP λλλλλ −+−−− ==⋅=>ℑ⋅>ℑ=>ℑ>ℑ=>ℑ , A soma de dois processos de Poisson independentes também é Poisson com taxa igual à soma das taxas individuais. Exemplo 4: Seja X(t) = X1(t) + X2(t) a soma de dois processos de Poisson independentes com taxas λ1 e λ2. Se o processo X(t) tiver uma chegada qual a probabilidade que esta chegada venha do processo X1(t)? [ ] { } { }[ ][ ] { } { }[ ] [ ]1 01 1 11 1/1 2111 =X(t)P =(t)X=(t)XP =X(t)P =X(t)=(t)XP ==X(t)=(t)XP ∩ ≡ ∩ [ ] [ ] [ ] ( ) ( ) ( ) 21 1 21 21 21 121 1 01 λ+λ λ =tλ+etλ+λ tetetλ =X(t)P =(t)XP=(t)XP = λ λλ ⋅⋅ ⋅⋅⋅⋅⋅ = ⋅ − −− Exemplo 5: A chegada de pacotes de voz (VoIP) na entrada de um roteador é um processo de Poisson com taxa λ = 0,1 pacotes/minuto. Devido a um upgrade para instalar um WFQ com regra de prioridade, o roteador é desligado durante 10 minutos. a) Qual a probabilidade de não receber pacotes VoIP enquanto desligado? ( ) ( )[ ] 1100,10010 −⋅−⋅−− e=e=e==XXP tλ b) Qual a probabilidade de chegarem mais que 10 pacotes VoIP durante o período de upgrade? ( ) ( )[ ] ( ) ( )[ ] ( ) ( ) ∑∑∑ −−⋅− −⋅−⋅⋅−≤−−− 10 0 1 10 0 1 10 0 1111110010110010 =k=k k =k tλ k k! e=e k! =e k! tλ=XXP=>XXP Série de Taylor: ∑ ∞ = =+++++= 0 432 ! ... !4!3!2 1 k k x k xxxxxe ∑∑ = ∞ = ≅= 10 00 1 ! 1 ! 1 kk kk e ( ) ( )[ ] ( ) ( )[ ] 0110010110010 11 =⋅−≅≤−−− − eeXXP=>XXP c) Se durante o upgrade chegar 1 pacote qual é o minuto mais provável em que o pacote chegou? A distribuição é uniforme, qualquer intervalo possui a mesma probabilidade. Exemplo 6: Uma série de seqüências de teste com um número variável de N bits todos iguais a 1 são transmitidos em um canal de comunicação. Devido aos erros de transmissão, cada bit 1 pode ser corrompido independentemente dos outros e chegar corretamente com probabilidade p. O comprimento N das seqüências é uma variável aleatória de Poisson com comprimento médio de λ bits. Neste teste, a soma Y dos bits na seqüência é analisada para determinar a qualidade do canal. Calcule a fdp de Y. Y – variável aleatória binomial de parâmetros (N, p) [ ] [ ] [ ]∑ ∞ = =⋅==== 0 / n nNPnNkYPkYP [ ] ( )∑ ∞ = −− ⋅⋅⋅⋅ == 0 !n n knk e n qp k n kYP λλ p – probabilidade de não ocorrer erros q = 1- p – probabilidade de ocorrer erros k – quantidade de bits com erro n – seqüência de bits Binomial – quantas combinações poderão existir para representar bits errados. [ ] ( ) ( ) ( ) ∑∑∑ ∞ = −− − −∞ = − −−−∞ = −− − ⋅⋅⋅ ⋅ ⋅=⋅ − ⋅⋅⋅⋅= − ⋅⋅⋅== 0 )( 00 )!(!)!(!)!(! n knkn k k n k knknk n nknk kn q k ep kn q k ep kn q k epkYP λ λλ λλλ λλλ Mudança de variáveis: ∞=→∞= =→= −= mn mkn knm 0 [ ] ( ) p k q kk m mmkk e k pe k ep m q k epkYP λλ λλ λλλλ −−∞ = − ⋅⋅=⋅⋅=⋅⋅⋅⋅⋅== ∑ !!!! 0 Exemplo 7: Num roteador são suportadas quatro classes de QoS. Cada classe possui pacotes chegando de acordo com um processo de Poisson com taxas λj (j = 1, 2, 3, 4). Suponha que o roteador falhe no instante t1 e permaneça durante um intervalo de tempo T. Qual é a função densidade de probabilidade do número total de pacotes das quatro classes que chegam no intervalo T? Seja a taxa total: ∑ = = 4 1j T jλλ O número médio de pacotes das 4 classes no buffer do roteador durante o intervalo T: [ ] ∑ = ⋅=⋅== 4 1j T jTTnNE λλ A função densidade de probabilidade do número total de chegadas: [ ] λλ −⋅== e n nNP n ! Exemplo 8: Pacientes chegam a um consultório de acordo com um Processo de Poisson de taxa = 0,1 pacientes/min. O doutor não irá atender um paciente até que pelo menos três pacientes estejam na sala de espera. a) Encontre o tempo médio de espera até que o primeiro paciente seja admitido pelo doutor. [ ] min301,03 =→⋅=→⋅ TTTλ=NE T b) Qual é a probabilidade de que ninguém seja atendido na primeira hora? Não haverá atendimento se houver menos de 3 pessoas na sala de espera na primeira hora: ( )[ ] ( ) ( ) ( ) 0,6600,1 2 600,1 1 600,1 02 0 25 !2 600,1 !1 600,1 !0 600,1k60.][ −⋅−⋅−⋅− = =⋅⋅+⋅⋅+⋅⋅== ∑ eeee=XPNaoAtendP k Exemplo 9: Pacotes de dados transmitidos por um modem sobre uma linha telefônica formam um processo de Poisson de taxa 15 pacotes/segundo. Usando Mk para denotar o número de pacotes transmitidos na k-ésima hora, encontre a fmp conjunta de M1e M2: ( )212,1 ,mmp mm . Teorema 8.2 (apostila): Para um processo de Poisson N(t) de taxa λ, a fmp conjunta é dada por: )(,...0, )!()!(! ),...,( 11 112 2 1 1 1)(),...,( 2121211 1 − − α−−α−−α− −λ=α≤≤≤ − ⋅α⋅⋅⋅ − ⋅α⋅⋅α − iiik kk nn k nnn ktNtN ttnnnn e nn e n e=nnp kk k t mm e m e m e=mmp mmmm MM λ=α=α=α ⋅α =⋅α⋅⋅α α−+α−α− 21 21 21 2 2 1 1 21, !!!! ),( 22211 21 Exemplo 10: Um help desk para ADSL atende somente 3 tipos de pedidos por parte dos usuários. Os pedidos chegam ao help desk de acordo com um processo de Poisson com diferentes taxas: λ1 = 8 pedidos / hora - problemas de login λ2 = 6 pedidos / hora - problemas de hardware λ3 = 6 pedidos / hora - problemas de software Os processos de chegada são independentes. O período de atendimento é das 8:00 às 18:00. Responda: a) Qual é o numero esperado de pedidos em um dia? rapedidos/ho20321 =++= λλλλ T [ ] apedidos/di160=Tλ=NE T ⋅ b) Qual a probabilidade que em 20 minutos exatamente três pedidos cheguem relativos a problemas de hardware? ( ) ( ) ( )[ ] ( )[ ] ( )[ ] ( )[ ] ( ) 866 3 8 32 3 21 3 1 33 1 23 1 13 1 33 1 23 1 1 101,73 1 3 1 3 3 16 3 1 3 03003,0, − ⋅−⋅−⋅− −−− ×⋅⋅ ⋅ ⋅⋅⋅⋅⋅⋅⋅= ⋅⋅ =ee ! e=tete ! tλte =XP=XP=XP==X=X=XP λλλ c) Qual a probabilidade que nenhum pedido chegue nos últimos 15 minutos de funcionamento? ( )[ ] 3 20 4 1 106,74 1 0 − ⋅− − ×⋅⋅ =ete==XP TλT d) Qual a probabilidade que exatamente um pedido chegue entre 10:00 e 10:12 e dois pedidos cheguem entre 10:06 e 10:30? { } { }[ ] ==)X()X(=)X(P 20,10,510,2 −∩ { } { } { }[ ]∑ −∩−−∩= 1 0 10,20,510,10,20,1 =k k+=)X()X(k=)X()X(k=)X(P ∑ −− − −− ×⋅ − ⋅⋅⋅ 1 0 3 1 6 1 22 102,18 1 6 1 22 =k k+kk = k)!+( e k)!( e k! e= 0 6 12 30 60 t 0 0,1 0,2 0,5 1 k=2 k=1X(t) 0 6 12 30 60 t 0 0,1 0,2 0,5 1 1-KKX(t) 1+K e) Se no instante t+s existem k+m pedidos, qual é a probabilidade que k pedidos foram recebidos até o instante t? [ ] { } { }[ ][ ] [ ] [ ] [ ]m+k=s)+X(tP m=X(t)s)+X(tPk=X(t)P= m+k=s)+X(tP m+k=s)+X(tk=X(t)P=m+k=s)+X(tk=X(t)P −⋅∩/ ( ) ( ) ( )( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) mk mk mk st mk s m t k st s st t mk mk mk st m s k t e mk st e m se k t = + ⋅ + ⋅+= + + ⋅ = ⋅ + +λ ⋅λ⋅⋅λ + +λ− + λ−λ− !! ! ! !! ! !! [ ] mk st s st t m mk mkstXktXP + ⋅ + ⋅ + =+=+= )(/)( Exemplo 11: Em uma linha de produção de resistores de 1000, a resistência real de cada resistor é uma variável aleatória R com distribuição uniforme entre 950 e 1050.Assuma que os valores das resistências dos diferentes resistores são independentes. A companhia tem uma encomenda de resistores de 1% de tolerância (resistências entre 990 e 1010). Um testador automático toma um resistor por segundo e mede sua resistência exata (este teste demora 1 segundo). O processo estocástico N(t) denota o número de resistores com tolerância de 1% encontrados em t segundos. A variável aleatória Tr segundos é o tempo decorrido até encontrarmos r resistores com tolerância de 1%. (a) Calcule p, a probabilidade de um resistor ter tolerância de 1%. [ ] 20,0 100 20%1 == =RP Tol (b) Qual é a fmp de N(t)? tnpp n t np ntntN ,...,1,0,)1()()( =−⋅ = − (c) Calcule E[T1], o tempo esperado para encontrar o primeiro resistor com tolerância de 1%. V.A. com Distribuição Binomial: [ ] pt=tNE ⋅)( [ ] seg p =TE 5 20,0 11 1 == 0 t t+s t X(t) k K+m 0 t t+s t X(t) k m 950 990 1010 1050 (d) Qual a probabilidade do primeiro resistor com tolerância 1% ser encontrado em exatamente 5 segundos. 08192,05)2,01(2,0 1 5 )1()1()( 151)()( ⋅=−⋅⋅ =⇒−⋅⋅ = −− tN ntn tN pppn t np (e) E[T2|T1 = 10], a esperança condicional do tempo necessário para encontrar o segundo resistor com tolerância de 1%, dado que o primeiro foi encontrado em 10 segundos. [ ] [ ] seg p TE=TE 15510112 =+=+ Exemplo 12: A chegada de ataques de vírus em um PC pode ser modelada por um processo de Poisson com taxa λ=6 ataques/h. a) Qual a probabilidade que exatamente um ataque irá ocorrer entre 1 PM e 2 PM? [ ] ( ) ( ) 66 1 6 !1 16 ! 1)1()2( −−⋅− ⋅=⋅⋅=⋅⋅==− eee k tXXP t k λλ b) Suponha que no momento em que o PC é ligado não houve ataque, mas ao desligá-lo 60 ataques ocorreram. Qual o valor médio do tempo em que o PC ficou ligado? [ ] [ ] htXEtttXE 10 6 60)()( ===→⋅= λ λ c) Dado que ocorreram 6 ataques entre 1 PM e 2 PM qual é a probabilidade de que o quinto ataque chegou entre 1:30 PM e 2 PM? Vamos representar o instante de chegada do quinto ataque por T. [ ] )(6)1(/)( tFXtTXP T==< { } { }[ ] { } { }[ ] [ ]6)1( 0)1(6)(6)1(5)()( = ==+=== XP XtXPXtXPtFT [ ] [ ] [ ] [ ] [ ] 65 56 6)1( 0)()1(6)(1)()1(5)()( tt XP tXXPtXPtXXPtXPtFT −== =−⋅=+=−⋅== 0,89062564/572/11 =− =)(F)(F TT d) Qual é o valor esperado do instante em que o quinto ataque ocorra? Dado uma variável aleatória T o seu valor esperado: [ ] dxxfxTTE T )(∫== Def. dt tdFtf TT )( )( = ( )5430 tt=(t)fT −⋅ [ ] ( ) min42,85714h0,71428630 1 0 65 ⇒=−⋅=⋅ ∫∫ tt(t)dtft=T=TE T 0 5 ataque 1h
Compartilhar