top of page

PESQUISA OPERACIONAL

Disciplina: Processos Estocásticos

Processos Estocásticos

  

(Sequências Markovianas de Dois Estados)

  

 

 

SEQÜÊNCIAS MARKOVIANAS DE DOIS ESTADOS:

Anteriormente, introduziu-se o conceito de uma Sequência Markoviana Independente. Afirmou-se que era uma Sequência Aleatória ou Processo Aleatório Discreto X1, X2, X3,... que tinha a seguinte Propriedade: Condicionado ao conhecimento do valor de Xn-1 ("o estado atual"), a probabilidade, de que Xn assumia algum dado valor ("um estado futuro") não será afetada pelo conhecimento dos valores de X1, X2, ..., Xn-2 ("os estados passados"). Isto é,

                                       Pr[Xn=in / X1=i1, ... , Xn-1=in-1 ]=Pr[Xn=in / Xn-1=in-1]

 

No caso de uma Sequência Markoviana Dependente Estacionária, aquelas probabilidades foram consideradas como não dependentes de n, e, definiu-se as quantidades

 

                                                            Pij=Pr[Xn=j / Xn-1=i]                                               (A)

 

como as Probabilidades de Transição de Um Passo do Processo. É claro, elas são Probabilidades Condicionais e satisfazem

 

                                                                             Σj Pij   para cada i

 

onde a soma se estende sobre o Espaço dos Estados Total do Processo.

O mais simples exemplo significativo desse processo seria aquele em que o Espaço dos Estados consiste somente de DOIS (2) Estados. Eles poderiam ser rotulados como "Sucesso", e "Fracasso", ou 0 e 1. Neste caso, haveriam QUATRO (4) Probabilidades de Transição de Um Passo:

                                         P00, P01P10, P11, que satisfazem P00 + PO1=1, P1O + P11=1.

 

Lê-se: P00 (Probabilidades de estar no estado 0 dado que estava no estado 0; P01 (Probabilidades de estar no estado 1 dado que estava no estado 0; e assim por diante!

 

Muitos processos do mundo real se comportam dessa maneira, ao menos em termos de uma primeira aproximação. Por exemplo, os dois estados poderiam se referir a um símbolo transmitido corretamente ou deturpado, em qualquer dos casos, em um sistema de comunicações; a uma máquina em funcionamento ou em reparos em uma fábrica; a uma posição de memória vazia ou preenchida em um sistema de memória de computador: ou a muitas outras situações.

 

De modo a organizar melhor as idéias, considere-se uma Aplicação (EXEMPLO) de cunho militar, na qual um Modelo Markoviano tenha sido usado com sucesso. Ao disparar o canhão principal de um tanque, observa-se que cada projétil disparado atinge ou erra o seu alvo com uma probabilidade que depende do sucesso da primeira descarga disparada. Se o tiro anterior foi feliz, o comandante do tanque tem seu alvo acertado, e apresenta uma probabilidade relativamente alta de repetir o acerto quando do próximo tiro. Se o tiro anterior foi infeliz então, o alvo deve ser corrigido, e a probabilidade de errar será menor no próximo tiro. O tanque e o alvo podem estar, ambos, em movimento. Assim, uma vez que o resultado de um certo tiro seja conhecido, o sucesso ou fracasso dos tiros anteriores é de relativa importância quanto a predizer o sucesso do próximo tiro. Assim, em termos de uma aproximação razoável, é possível supor que se esteja a observar um Processo Markoviano Estacionário com Espaço de Estado {0, 1}, onde 0 indica um "acerto" e 1 indica um "erro".

 

Suponha-se que observações de campo de batalha possibilitem uma Estimativa das Probabilidades de Transição de Um passo, como se segue:

 

                                                                                P00=¾ e P01

                                                                                                    P10 =½ e P11 =½.

Assim, por exemplo, se um dado tiro acerta o alvo, a probabilidade é de ¾ de que o próximo tiro também acerte etc. Indiquemos o processo por X1, X2, X3, ... A variável aleatória Xn assume valores 0 ou 1, dependendo do fato do n-ésimo tiro ser um acerto ou um erro. Para estudar o comportamento do processo, deseja-se avaliar todas as probabilidades da forma:

                                                                                                                   para n=1, 2, 3, ...                         (A)

 

onde essas probabilidades não dependem de k, uma vez que tem Processo como Estacionário. Nesta notação,

 

Note-se que:

 

                       

 

para cada i, já que Xk+n deve ser igual a 0 ou 1. Agora seja i=0, e suponha que Xk=0 para algum k fixado. Assim, para qualquer n, o EVENTO (do Espaço Amostral) [Arquivo ".PDF"Xk+n+1=0 tem Probabilidade Condicional          

 

A seguir, considere o que deve acontecer no passo anterior [(k+n)-ésimo passo] de modo que o EVENTO Xk+n+1=0 seja verdadeiro. Tanto Xk+n=0 e uma Transição de UM Passo do Estado ao estado 0 ao estado 0 ocorre em se passando do (k+n)-ésimo ao (k+n+1)-ésimo estado, com Xk+n=1, e a transição será do estado 1 ao estado 0. Esses dois EVENTOS têm probabilidades:    

 

 

(condicionado a Xk=0)*

 

Uma vez que só há duas formas Mutuamente Exclusivas nas quais o EVENTO Xk+n+1=0 pode ocorrer, tem-se:

 

                                                                                                                                                    (B)

 

para n=1, 2, 3, ...

 

Já que:                        , a Equação (B) pode ser escrita como:

 

 

                                                                                                                                                   

                                                                                                                                                    (C)

 

ou

 

                                                                                                                                                                                         (D)

 

para n=1, 2, 3, ...

A fórmula (D) é uma Fórmula Recursiva ou Equação de Diferenças da forma                                        (E)

com                                   Pela aplicação dessa fórmula, repetitivamente, pode-se resolver          em termos de           

 

 

 

 

 

                                                                                                                                                    (F)

Se           a fórmula para a Soma de uma Progressão Geométrica implica

 

 

 

 

                                                                                                                                                    (G)

Determinando                                                      e mudando de n para n-1, tem-se:

 

 

 

 

 

                                                                                                                                                                                          (H)

 

 

desde que                  De modo semelhante, obtem-se:

 

 

                                                                                                                                                                                          (I)

 

 

As fórmulas (H) e (I) determinam todos os          já que

 

 

                                                    

No exemplo de disparo de canhão considerado P00= ¾, P10= ½. Assim, P00 - P10= ¼, 1-P00 + P10= ¾, e (H) implica

 

 

                                                                                                                                                     (J)

 

 

De modo semelhante

 

 

                                                                                                                                                     (K)

 

 

                                                                                                                                                                                       

                                                                                                                                                                                           (L)

 

 

                                                                                                                                                                                           (M)

 

Observe que

 

                                                                                                                                                                                            (N)

                                                                                                                                                                               

                                                                                                                                                                                            (O)           

As fórmulas (N) e (O) dão as probabilidades de transição, após um número muito grande de etapas, de um "acerto" e um "erro" em um dado tiro. Pode-se observar que, à medida que n aumenta, a probabilidade de um "acerto" tende a ser a mesma não se levando em consideração se a sequência de tiros começou com um "acerto" ou com um "erro". As probabilidades        e as maneiras nas quais elas tendem a seus valores limite se encontram esboçadas na Figura abaixo:

Figura A: Probabilidades Condicionais para um Problema (Exemplo) de Disparo de Canhão como uma Cadeia Markoviana de 2 (DOIS) Estados.

Este simples exemplo ilustra muitas idéias que se discutirão em detalhes, nos tópicos subsequentes. Neste sentido, se estará lidando com:

 

  1. Métodos gerais de computar probabilidades como        .

  2. Condições sob as quais         tende a um valor limite Pj quando n→∞.

  3. Condições sob as quais esse valor limite é o mesmo, a despeito do estado inicial i.

  4. Condições sob as quais os próprios limites Pj formam uma Função de Densidade de Probabilidade (isto é, somem até 1).

  5. Modos de computar os limites Pj.

_______________________

* Intuitivamente isto parece óbvio. Oportunamente, a Demonstração será dada de forma rigorosa!

____________________________________

Fonte:

Clarke, A. Bruce. and Disney, L. Ralph.: Probabilidade e Processos Estocásticos. Livros Técnicos e Científicos Editora S.A., Rio de Janeiro, 1979.

  A partir de 23 Jul de 2018

Você é o Visitante de Número

bottom of page