21 - Processos de Markov
1. DEFINIÇÃO
Para um dado sistema físico, obedecendo a certas leis de probabilidades
podemos enunciar o seguinte princípio: a probabilidade de que um sistema físico
estará num determinado estado no momento t2 pode ser deduzido a partir do
conhecimento do seu estado num qualquer momento anterior t1, e não depende
da história do sistema antes do momento t1. Um Processo Estocástico que
represente observações dum sistema físico que satisfaça esta condição é um
Processo de Markov.
Um caso especial de Processo de Markov é uma Cadeia de Markov, que pode ser
definida como um Processo Estocástico cujo desenvolvimento pode ser tratado
como uma série de transições entre certos valores (chamados "estados" do
processo), com a propriedade da lei de probabilidade do desenvolvimento futuro
do processo, dado que está num estado, depende apenas do estado e não de como
o processo chegou a esse estado. O número de estados possível pode ser finito
ou infinito numerável
1
Em termos matemáticos, dizemos que um Processo Estocástico de Parâmetro
Discreto { Xt, t = 0, 1, 2, ...} ou de Parâmetro Contínuo { Xt, t  0} é um
Processo de Markov se, para qualquer conjunto de n momentos t1 < t2 < ... <
tn do conjunto T do processo, a distribuição condicional de Xt, para dados
valores de Xt1,..., Xtn-1, depende apenas de Xtn-1(o valor conhecido mais
recente); mais precisamente, para quaisquer valores reais x1, ..., xn
P(Xtn xn | Xt1= x1,..., Xtn-1 = xn-1) = P(Xtn xn | Xtn-1 = xn-1)
(1)
Da expressão (1) pode-se facilmente concluir que, dado o "presente" do
processo, o "futuro" é independente do "passado".
Os Processos de Markov podem ser classificados não só pelo seu parâmetro,
contínuo ou discreto, mas também pelo espaço dos estados (conjunto dos
possíveis valores do Processo Estocástico), que também pode ser contínuo ou
discreto. Os Processos de Markov cujo espaço de estados é discreto, dizem-se
Cadeias de Markov e usa-se habitualmente para espaço dos estados o conjunto
{ 0, 1, 2, ...} .
Um Processo de Markov é descrito pela função de probabilidade de transição.
Se o sistema estiver num estado x, no momento t0, existe uma probabilidade
2
fixa do estado no momento t ( > t0 ) pertencer a um conjunto E.
O caso que nos vai interessar será o das Cadeias de Markov de parâmetro
discreto.
Neste caso, as variáveis aleatórias X0, X1,..., Xn,... são discretas, o conjunto T é
discreto (T = {0,1,...,n,...}), o número de estados é finito ou infinito numerável e
podemos substituir a equação (1) por:
P(Xm= xm | X0= x0,..., Xm-1 = xm-1) = P(Xm= xm | Xm-1 = xm-1)
(2)
Além disto, a função de probabilidade de transição pode ser descrita da forma:
pj,k(m,n) = P( Xn = k | Xm = j )
(3)
isto é, a probabilidade do sistema estar no estado k no momento n dado que no
momento m esteve no estado j.
O caso que vamos estudar ainda é mais especial: a partir de agora vamos considerar
que a Cadeia de Markov é homogênea.
Diz-se que a Cadeia de Markov é homogênea ou estacionária se pj,k(m,n) depende
apenas da diferença n-m. Chamamos então função de probabilidade de transição
em n passos da Cadeia de Markov homogênea a:
pj,k(n) = P( Xn+t = k | Xt = j ) = P( Xn = k | X0 = j ) , para todo o inteiro t  0
(4)
3
Vamos ver ainda mais algumas notações que iremos usar:
Probabilidade de transição a um passo, isto é, pj,k(1):
pj,k = P( Xt+1 = k | Xt = j ) = P( Xn = k | X0 = j ), para todo o inteiro t  0
(5)
Probabilidade (não condicional) de no momento n o sistema estar no estado j:
pj(n) = P( Xn = j )
(6)
A melhor forma de escrever as probabilidades de transição de uma Cadeia de
Markov com espaço de estados {0,1,2,...} é através da matriz de transição a n
passos:
P(n) = [ pj,k(n)]
(7)
Note-se que os elementos desta matriz satisfazem:
pj,k(n)  0 para todo j, k
(8)
para todo j, k
(9)
4
A matriz de transição a um passo é representada da forma:
P = [ pj,k ]
(10)
Outra forma de representação de uma Cadeia de Markov com número finito de
estados é o diagrama de transição, onde são representados os estados e as transições
entre estes, isto é, as que correspondem a probabilidades de transição num passo
diferentes de zero.
2. CADEIAS DE MARKOV
Exemplo 1: Consideremos uma das linhas de enchimento de garrafas da Pepsi e a
máquina que se encarrega de encher as garrafas ao longo do dia. Esta máquina estando
a funcionar em perfeitas condições, pode no dia seguinte começar a funcionar com
defeito, atrasando assim o enchimento das garrafas, com probabilidade 0,09, ou pode
passar a uma situação de avaria total, com probabilidade 0,01, o que implica a
paragem da linha de enchimento. Estando a trabalhar com defeito a máquina pode
manter-se nessa situação, dia após dia, com probabilidade 0,55 ou passar à situação de
avaria total com probabilidade 0,45, situação que é definitiva até se proceder à
reparação ou substituição.
5
Seja Xn a variável aleatória que regista o estado da máquina no dia n.
Para este sistema vamos considerar como espaço de estados {0,1,2}, onde
0 - máquina em perfeitas condições
1 - máquina com defeito
2 - máquina em avaria total
ou seja, estes três valores representam os três estados possíveis em que se pode
encontrar a máquina.
Visto que o espaço de estados é discreto, a variável Xn é discreta, pois só pode
tomar um dos três valores possíveis. Além disso o conjunto dos índices também é
discreto, correspondendo ao dia 1, 2,...,n,.... Pelo enunciado, temos indicação que o
estado da máquina num dado dia depende apenas do estado da máquina no dia
anterior. Podemos então dizer que estamos perante uma Cadeia de Markov de
parâmetro discreto, homogênea, com um número finito de estados.
Vamos então representar esta Cadeia de Markov.
6
O enunciado indica-nos as probabilidades de transição num passo, ou seja:
p0,0 = 0,9; p0,1 = 0,09; p0,2 = 0,01;
p1,0 = 0; p1,1 = 0,55; p1,2 = 0,45;
p2,0 = 0; p2,1 = 0; p2,2 = 1.
A matriz de probabilidades de transição num passo é então:
7
Vejamos ainda o diagrama de transições:
Os valores nas linhas orientadas correspondem às probabilidades de transição
num passo, diferentes de zero, e logo a soma das linhas que partem do mesmo
estado tem que ser igual a 1. Este diagrama dá-nos uma idéia de como o sistema
funciona de um instante para o outro imediatamente a seguir e ajuda-nos a
perceber as relações que existem entre os estados, como iremos ver mais à frente.
8
3 - EQUAÇÕES DE CHAPMAN-KOLMOGOROV
Uma relação fundamental satisfeita pela função de probabilidade de transição de uma
Cadeia de Markov homogênea é a chamada equação de Chapman-Kolmogorov.
(11)
Note-se que este somatório percorre todos os estados da Cadeia de Markov (E
significa Espaço dos Estados). Estas equações mostram apenas que quando o sistema
passa dum estado j para um estado k em n passos, o sistema passará por um estado i
em u (menos de n) passos.
Vejamos agora esta equação em termos matriciais:
Podemos escrever as Equações de Chapman-Kolmogorov matricialmente, segundo as
notações já descritas anteriormente, da forma:
P(n) = P(u) P(n-u) , para todo o momento 0  u  n
(12)
Para que servem então estas Equações? A resposta é simples: as Equações de
Chapman-Kolmogorov fornecem um método de cálculo das probabilidades e das
9
matrizes de transição em n passos.
Vamos ver em termos matriciais o que acontece. Visto que a equação (12) se
verifica para todo o u, consideremos em particular u = 1. Temos então, visto que
P(1) = P:
P(n) = P.P(n-1)
(13)
Aplicando novamente a equação (12) a P(n-1) com u = 1, temos:
P(n) = P. P. P(n-2) = P2.P(n-2)
(14)
Aplicando sucessivamente este raciocínio, vemos facilmente que:
P(n) = Pn = Pn-1.P = P.Pn-1
(15)
Em termos de probabilidades de transição, isto corresponde a:
(16)
Daqui conclui-se que basta-nos conhecer as probabilidades de transição num passo
que, de uma forma recursiva, podemos determinar as probabilidades de transição
em n passos.
10
Consideremos agora o vetor das probabilidades não condicionais:
p(n) = [ pj(n)] , onde pj(n) = P( Xn = j ) (como já tínhamos visto antes) (17)
Pelos teoremas das probabilidades condicionais, temos que:
(18)
E logo, facilmente se verifica que:
p(n) = p(0).P(n)
(19)
Logo, pela equação (15) podemos escrever:
p(n) = p(0).P n
(20)
Ou seja, as equações de Chapman-Kolmogorov permitem-nos, desde que saibamos
as probabilidades de transição num passo e um conjunto de probabilidades de
estados iniciais (no momento 0), obter as probabilidades do sistema estar num
determinado estado ao fim de n passos.
11
Vejamos a concretização destes resultados no nosso exemplo.
Suponhamos que queremos saber a situação do sistema em 2 dias, isto é, as
probabilidades de transição em 2 passos. Basta então:
P(2) = P2 =
Algumas conclusões que podemos tirar: ao fim de dois dias a probabilidade da
máquina passar do estado "em perfeitas condições" para o de "avaria total" (p0,3(2))
é já de 0,0595, as probabilidades da máquina se manter no estado 0 e 1 ao fim de
dois dias (p0,0(2) e p1,1(2)) diminuem e as restantes aumentam. Apenas o estado 2 se
mantém, o que faz sentido, visto que se a máquina entra em avaria total não altera o
seu estado a não ser que haja uma influência externa no sistema (p2,2(2) = 1).
Analogamente podemos obter P(3) e P(4):
P(3) = P2.P =
12
P(4) = P2.P2 =
Verifica-se então a tendência de diminuição da probabilidade da máquina se
manter nos estados 0 e 1 e de aumento das restantes probabilidades de transição.
Verificamos também que o comportamento relativo ao estado 2 se mantém.
Suponhamos agora que nos é dada uma distribuição de probabilidades iniciais, ou
seja, suponhamos que no momento em que se começou a observar o sistema este
estava em perfeitas condições, isto é, X0= 0. Assim podemos dizer que:
p(0) =
Queremos saber quais as probabilidades do sistema estar em cada um dos estados
possíveis ao fim de dois dias, isto é:
p(2) = p(0).P2 =
13
Vemos então que ao fim de dois dias a máquina continuará em "perfeitas condições"
com probabilidade 0,81, estará a trabalhar com "defeito" com probabilidade 0,1305
ou estará no estado de "avaria total" com probabilidade 0,0595.
Suponhamos agora que não é certo que a máquina esteja inicialmente a funcionar em
"perfeitas condições". Vamos considerar então uma outra distribuição inicial das
probabilidades dos estados e suponhamos que queremos saber como será a
distribuição das probabilidades ao fim de 4 dias. Seja então:
p(0) =
Temos então:
p(4) = p(0).P4 =
Neste caso, considerando que no início do processo a máquina estava no estado 0
com probabilidade 0,6 ou no estado 1 com probabilidade 0,4, ao fim de 4 dias a
máquina manter-se-á no estado 0 com probabilidade 0,3937, estará no estado 1 com
probabilidade 0,1237 ou estará no estado 2 com probabilidade 0,4826. Vemos
assim, que como o estado 0 e 1 dão acesso num passo ao estado 2, com esta
distribuição de probabilidades inicial, a probabilidade do sistema estar no estado 2
ao fim de alguns dias aumenta substancialmente.
14
Vimos assim que com as Equações de Chapman-Kolmogorov, facilmente se podem
determinar a distribuição de probabilidades não condicionais e das probabilidades de
transição em qualquer momento n, sabendo apenas a distribuição inicial das
probabilidades dos estados e as probabilidades de transição a um passo.
4. CLASSIFICAÇÃO DOS ESTADOS DUMA CADEIA DE MARKOV
No item anterior, preocupamo-nos apenas com o estudo da evolução ao longo do
tempo de uma Cadeia de Markov de parâmetro discreto homogênea. Vamos agora ver
resumidamente como se podem classificar os estados desta cadeia e algumas das
propriedades da Cadeia relacionadas com estas classificações
Diz-se que o estado k é acessível a partir do estado j (ou que j dá acesso a k) se, para
algum inteiro n  0, pj,k(n) > 0 e escreve-se j k.
No nosso exemplo, o estado 0 dá acesso a todos os outros, incluindo ele próprio, o
estado 1 dá acesso ao estado 2 e a ele próprio e o estado 2 dá acesso apenas a ele
próprio.
Diz-se que dois estados j e k comunicam se j é acessível a partir de k e k é acessível a
partir de j, isto é, j k e k j. Neste caso, escreve-se j k.
15
No exemplo, todos os estados comunicam apenas com eles próprios.
Tem-se ainda, em geral, que:
a) j j (reflexividade), isto é, todos os estados comunicam com eles próprios, pois:
pj,j(0) = P(X0 = j | X0 = j ) = 1;
(21)
(b) Se j  k então k j (simetria), pela própria definição de comunicação;
(c) Se j k e k i então j i (transitividade), utilizando as Equações de
Chapman-Kolmogorov tem-se:
pj,i(n1+n2) = pj,k(n1).pk,i(n2) > 0
(22)
visto que, como j k então j k e logo existe n1 tal que pj,k(n1) > 0 e como k i
então k i e logo existe n2 tal que pk,i(n2) > 0.
Com estas três propriedades da comunicação é possível definir Classes de
Comunicação e logo dividir o nosso espaço dos estados numa união de classes
disjuntas. Assim, os estados de uma Cadeia de Markov podem consistir numa ou
mais classes disjuntas. No caso em que só existe uma classe de comunicação diz-se
que a Cadeia de Markov é irredutível.
16
No nosso exemplo temos três classes de comunicação: C1={0}, C2={1} e C3={2} e
logo não é irredutível.
Uma questão que se põe usualmente é: se o processo começar num dado estado j, será
que o sistema voltará a passar neste estado?
Seja fjj a probabilidade do processo voltar ao estado j, sabendo que este começa no
estado j.
Se fjj = 1 dizemos que j é um estado recorrente e se fjj < 1 dizemos que j é um estado
transiente. Existe um caso especial de estados recorrentes: se pjj = 1 então o estado dizse absorvente
No nosso exemplo, o estado 2 é um estado absorvente, e logo recorrente, e os estados 0
e 1 são transientes. Porquê?
Para o estado 2 não é complicado, pois não é necessário recorrer ao cálculo de f22, mas
para os outros a questão é mais difícil, pois em geral o cálculo de fjj não é imediato.
Um outro resultado que nos facilita esta questão é o seguinte:
Uma classe em que nenhum dos estados dá acesso a outro estado de outra classe diz-se
classe de comunicação recorrente, e logo todos os seus estados são recorrentes. De
forma análoga, se algum dos estados da classe der acesso a um estado doutra classe,
diz-se que a classe de comunicação é transiente e todos os seus estados são
transientes.
17
Assim, se analisarmos as classes C1 e C2 do nosso exemplo, os seus estados dão acesso
a estados das outras duas classes e logo são estados transientes. Na classe C3, o estado 2
não dá acesso a nenhum dos outros estados, ou seja esta classe é recorrente.
Vamos agora ver algumas propriedades de fjj que nos podem permitir o cálculo do seu
valor.
Pela forma como é definido estado recorrente, implica que o sistema passa infinitas
vezes nestes estados, pois fjj = 1 significa que se o sistema passar pelo estado j, voltará a
passar no estado j e começando novamente neste estado, o sistema voltará a passar por
ele e assim sucessivamente. Assim, podemos dizer que o número esperado de
momentos que o sistema passa pelo estado j é infinito.
Analogamente, se j é um estado transiente, o número esperado de momentos que o
sistema passa pelo estado j é finito .
Conclui-se então que um estado j é recorrente se, e somente se, o número esperado de
momentos que o sistema passa pelo estado j for infinito, dado que o processo começou
no estado j.
18
Vamos então agora ver como calcular o número esperado de momentos que o
sistema passa pelo estado j, dado que X0 = j. Para isso vamos definir:
(23)
Logo,
(24)
representa o número de momentos que o processo está no estado j dado que X0 = j.
Assim, o número esperado é dado por:
(25)
Concluímos assim que:
j recorrente 
2
j transiente 
2
19
Vejamos no nosso exemplo como podemos aplicar estes resultados: relativamente
ao estado 2, que já sabemos ser recorrente, temos que pi,i(n) = 1, para todo n
inteiro e logo,
(28)
Para os outros dois estados, se analisarmos as matrizes de transição a 1, 2, 3 e 4
passos, verificamos que:
Estado 0:
Estado 1:
p00 = 0,9
p11 = 0,55
p00(2) = 0,81 = (0,9)2
p11(2) = 0,3025 = (0,55)2
p00(3) = 0,729 = (0,9)3
p11(3) = 0,166375 = (0,55)3
p00(4) = 0,6561 = (0,9)4
p11(4) = 0,09150625 = (0,55)4
20
Logo, podemos concluir (e é fácil de provar por indução) que:
p00(n) = (0,9)np11(n) = (0,55)n
Obtemos assim duas séries geométricas ambas com razão menor que 1 (0,9 e 0,55) e
logo são convergentes, isto é:
(29)
Confirmamos assim o que já sabíamos: estes dois estados são transientes.
Outra propriedade importante dos estados de uma Cadeia de Markov é a sua
periodicidade.
O período de um estado k , p (k), pode ser definido como :
p (k) = m.d.c.{n: pk,k(n) > 0}
(30)
ou seja, é o número mínimo de passos que o sistema leva a retornar ao estado k,
partindo de k.
Se p (k) = 1 dizemos que k é aperiódico, caso contrário dizemos que é periódico.
21
No nosso exemplo, temos que:
{n: pi,i(n) > 0} =  , com i ={0,1,2}
(31)
logo, p (i) = 1, com i ={0,1,2}, ou seja, todos os estados são aperiódicos.
Exemplo 2 :Vejamos rapidamente um exemplo em que os estados não são todos
aperiódicos. Consideremos a seguinte matriz de transição, P e o respectivo
diagrama de transições:
Neste caso, para qualquer um dos estados, verifica-se facilmente que:
{n: pi,i(n) > 0} = {2, 4, 6, ..., 2t, ...}
(32)
e logo, p (i) = 2, ou seja, ambos são estados periódicos, de período 2.
22
Tal como a recorrência, a periodicidade é também uma propriedade das classes de
comunicação, ou seja, se um estado duma classe tem período t, então todos os
estados dessa classe têm período t.
Os estados recorrentes podem ainda ser classificados quanto ao seu tempo médio de
retorno, mkk:
O estado recorrente k diz-se recorrente positivo se mkk for finito, caso contrário
(i.e., for infinito) diz-se recorrente nulo.
Se a Cadeia de Markov for finita todos os seus estados são recorrentes positivos.
Se os estados recorrentes positivos forem aperiódicos, dizem-se estados ergódicos.
5. DISTRIBUIÇÃO LIMITE E DISTRIBUIÇÃO ESTACIONÁRIA
A noção de Cadeia de Markov envolve o conceito de um sistema dinâmico que
evolui ao longo do tempo. Assim é do nosso interesse o estudo do comportamento ao
fim de muito tempo.
Imaginemos que queríamos saber como se encontrava a nossa máquina ao fim de 3
meses, isto é, vamos calcular a matriz de transição a 90 passos:
23
P(90) = P90 =
(33)
Ou seja, ao fim de três meses, sem haver qualquer interferência exterior na
máquina, esta entrará no estado de "avaria total" seja qual for o estado inicial, o
que já seria de esperar, visto que este estado é absorvente.
Esta igualdade das linhas da matriz deve-se ao facto de existir um estado
absorvente na nossa cadeia, que leva à tendência de ao fim de várias passagens o
sistema ficar no estado de "avaria total", independentemente do estado inicial.
Exemplo 3: Consideremos um sistema de informação que transmite os dígitos "0"
ou "1". Cada dígito transmitido passa por várias etapas, podendo ser alterado. Os
dígitos, "0" e "1", passam inalterados com probabilidade 1/2 e 2/3,
respectivamente. Como se comporta o sistema ao fim de 20 etapas?
Vejamos a matriz de transição a 20 passos:
24
P(20) = P20 =
(34)
Isto leva-nos a pensar que a probabilidade do sistema estar num dado estado ao fim
de 20 passos, neste caso, é independente do estado inicial, ou seja, existe uma
probabilidade limite de ao fim de um grande número de passagens o sistema estar
num estado j, independentemente do estado inicial. Isto leva-nos às distribuições
limite e estacionária de uma Cadeia de Markov, ou seja, ao estudo do
comportamento assintótico das respectivas probabilidades de transição.
Diz-se que uma Cadeia de Markov com espaço de estados E tem distribuição limite
se existir uma distribuição de probabilidades {p k, k E}, com a propriedade de, para
todo o j e k pertencentes a E:
(35)
Esta distribuição não depende da distribuição inicial dos estados e logo, facilmente
se prova que a probabilidade não condicional pk(n) também tende para p k quando n
tende para  .
25
Diz-se que uma Cadeia de Markov com espaço de estados E tem distribuição
estacionária se existir uma distribuição de probabilidades {p k, k E}, com a
propriedade de, para todo k pertencente a E:
(36)
O nome de "distribuição estacionária" deve-se ao fato que se se verificar a
equação (36) então , para todo o inteiro n:
(37)
Mas então em que condições podemos afirmar que existem estas distribuições
e que são uma só?
Existem vários teoremas que nos dão condições para a existência de uma e de
outra, mas vamos apenas considerar o seguinte:
Para uma Cadeia de Markov irredutível e ergódica tem-se que
existe e é independente de j. Além disso,
26
onde os p k’s são os únicos que satisfazem simultaneamente as equações:
pk > 0
para k 

Os pk’s chamam-se probabilidades estacionárias da Cadeia de Markov e relacionamse com o tempo médio de retorno da forma:
, para k E
(39)
Observações:
1 - A existência de distribuição estacionária não significa que o sistema fique sempre
num mesmo estado. Continuam a existir transições entre os estados e existem
probabilidades de transição, o que revela que existem probabilidades diferentes de o
sistema estar num ou noutro estado.
27
2 - Note-se que vamos ter mais uma equação do que o número de variáveis, no
sistema (38), mas visto que a solução é única, uma das equações será redundante e
desaparecerá. Obviamente que não pode ser a última, visto que a solução pk = 0,
para k E, verifica as restantes equações mas não é uma distribuição de
probabilidades.
Vejamos o exemplo 3:
p 0 = p 0 p00 + p 1 p10 =
p 1 = p 0 p01 + p 1 p11 =
p0+p1=1
Obtém-se:
p 0 = 0, e p 1 = 0,4.
E logo, m0,0 = 1,667 etapas e m1,1 = 2,5 etapas.
28
Outros resultados importantes:
•Se j e k são estados recorrentes pertencentes a diferentes classes, devido à
definição de classe, então:
pj,k(n) = 0, para todo n.
(40)
Se k é um estado transiente, então
, para todo j.
(41)
Este último resultado mostra o que acontece com o nosso exemplo da máquina da
Pepsi, que embora não seja uma cadeia irredutível e ergódica tem distribuição
limite e estacionária, no entanto, esta distribuição corresponde ao sistema se
encontrar sempre no estado 2 independentemente do estado inicial
CUSTO MÉDIO ESPERADO POR UNIDADE DE TEMPO
Consideramos até aqui apenas as Cadeias de Markov irredutíveis e ergódicas. O
que acontece se não considerarmos que os estados são todos aperiódicos?
Neste caso o limite
pode não existir. Se considerarmos o exemplo 2,
em que vimos que os dois estados tinham periodicidade dois, o que acontece é
que, se o processo começar no estado 0:
29
(42)
Logo,
, não existe.
No entanto, o limite da média de Cesàro existe sempre para estados recorrentes, ou
seja, para uma Cadeia de Markov irredutível com estados recorrentes positivos
tem-se:
onde p k’s verificam as equações (38).
Com este resultado podemos calcular o custo médio esperado por unidade de
tempo, que nos vai ser útil para o estudo dos Processos de Decisão Markovianos.
O custo médio esperado incorrido nos primeiros n períodos é dado por:
onde C(Xt) é a variável aleatória que corresponde ao custo incorrido quando o
processo está no estado Xt e toma um dos valores C(0), C(1),..., C(k),...,
independentemente de t.
30
Usando o resultado (43) temos que o custo médio esperado por unidade de
tempo (limite) é dado por:
Uma medida alternativa é o custo médio real por unidade de tempo (limite) que
é dado por:
para a maioria dos caminhos.
Como se pode ver, as duas medidas levam ao mesmo resultado.
Suponhamos no nosso exemplo 3 que existe um custo para o envio de dígitos, ou
seja, se Xt = 0 então C(0) = 2 u.m. e se Xt = 1 então C(1) = 3 u.m.. Para este
exemplo o custo esperado por unidade de tempo é:
31
CUSTO MÉDIO ESPERADO POR UNIDADE DE TEMPO PARA FUNÇÕES
DE CUSTOS COMPLEXAS
No caso anterior vimos apenas funções de custo dependentes no estado em que o
sistema se encontra no momento t. Vamos ver agora funções de custo que
dependem não só do estado do sistema mas também doutra variável aleatória.
Consideremos as seguintes condições:
•{Xt} é uma Cadeia de Markov irredutível com todos os estados recorrentes
positivos;
•Existe uma sequência de variáveis aleatórias {Dt}, independentes e identicamente
distribuídas (i.i.d.), associada à Cadeia de Markov;
•Para cada valor m = 0, ± 1, ± 2, ..., fixo, é incorrido um custo C(Xt, Dt+m) no
momento t, para t = 0,1, 2, ...;
•A sequência (X0, X1, ..., Xt) deve ser independente de Dt+m;
Nestas condições temos o custo médio esperado por unidade de tempo (limite)
dado por:
(47)
com f(k) = E[ C(k, Dt+m)] , sendo este valor esperado condicional calculado de
acordo com a distribuição de probabilidade das variáveis aleatórias Dt, dado o
estado k.
32
Analogamente, o custo médio real por unidade de tempo (limite), para a
maioria dos caminhos, é dado por,:
(48)
Temos agora todas as ferramentas que precisamos para trabalharmos com os
Processos de Decisão Markovianos.
33