3. Decomposição de \(S\)

Dedicamos este capítulo à decomposição do espaço de estados \(S\). Vamos considerar que \(\{C_n\}\) seja uma Cadeia de Markov estacionária com espaço de estados \(S\) e \(x,y\in S\) estados da cadeia.

Definição 3.1: Estado acessível.

Dizemos que o estado \(y\) é acessível do estado \(x\) se \(\rho_{x,y} > 0\). Escrevemos \(x \rightarrow y\).

Por exemplo, na Figura 3.1, há uma caminhada do estado 1 ao estado 3, passando pelo estado 2, então o estado 3 é acessível a partir de 1. Não há nenhuma caminhada do estado 5 ao 3, então o estado 3 não é acessível a partir de 5. O estado 2 é acessível a partir de si mesmo, mas o estado 6 não é acessível a partir de si mesmo.

Para ver o significado probabilístico de acessibilidade, suponha que um passeio \(i_0, i_1,\cdots, i_n\) exista do estado \(i_0\) para \(i_n\). Então, condicionado em \(C_0 = i_0\), há uma probabilidade positiva, \(p_{{i_0},{i_1}}\), de que \(C_1 = i_1\) e, consequentemente uma vez que \(p_{{i_0},{i_1}}> 0\), existe uma probabilidade positiva de \(C_2 = i_2\). Continuando esse argumento, existe uma probabilidade positiva de que \(C_n = i_n\), de modo que \(P(C_n = i_n | C_0 = i_0)> 0\). Da mesma forma, se \(P(C_n = i_n | C_0 = i_0)> 0\), então deve existir uma caminhada de \(n\) passos de \(i_0\) a \(i_n\).

Para concluir o exemplo da Figura 3.1, \(p_{1,3}^{(2)} = p_{1,2}p_{2,3}> 0\). Por outro lado, \(p_{5,3}^{(n)} = 0\) para todo \(n\geq 1\).

Figura 3.1: Representação gráfica de uma Cadeia de Markov de 6 estados; um arco direcionado de \(i\) para \(j\) é incluído no gráfico se, e somente se, \(p_{i,j}> 0\).

Pode-se demonstrar que \(y\) é acessível desde \(x\) se, e somente se, \(p_{x,y}^{(n)}>0\), para algum \(n\geq 1\). Também é possível mostrar que se \(y\) for acessível de \(x\) e se \(z\) for acessível de \(y\), então \(z\) é acessível desde \(x\). Isto implica que esta propriedade dos estados é transitiva e, assim, se \[ p_{x,y}^{(n)} >0 \qquad \mbox{e} \qquad p_{y,z}^{(m)}>0 \qquad \mbox{então} \qquad p_{x,z}^{(n+m)}>0\cdot \] Resumidamente, podemos escrever que, se \[ x \rightarrow y \qquad \mbox{e} \qquad y \rightarrow z \qquad \mbox{então} \qquad x \rightarrow z\cdot \]

Definição 3.2: Comunicação estre estados.

Dizemos que o estado \(x\) se comunica com o estado \(y\) se \(x\) é acessível do estado \(y\) e se \(y\) for acessível do estado \(x\), ou seja, se \(x \rightarrow y\) e \(y \rightarrow x\). Escrevemos \(x \rightleftharpoons y\).

um fato importante sobre a comunicação entre estados é que se \(x \rightleftharpoons y\) e \(z \rightleftharpoons y\) então \(x \rightleftharpoons z\). Para ver isso, observe que \(x \rightleftharpoons y\) e \(z \rightleftharpoons y\) implica que \(x \rightarrow y\) e \(y \rightarrow z\), logo \(x \rightarrow z\). Similarmente, \(z \rightarrow x\), de maneira que \(x \rightleftharpoons z\).

Exemplo 3.1.

No Exemplo 1.7 definimos uma possível matriz de transição entre paginas na web. Com o código a continuação, encontramos que a potência 1000 da matriz de probabilidades de transição é da forma:

library(markovchain)
estados = c("1","2","3","4","5")
Google.T=matrix(c(0,1/2,1/2,0,0,1/5,1/5,1/5,1/5,1/5,
                  1/3,1/3,0,1/3,0,0,0,0,0,1,
                  0,0,1/2,1/2,0),
              nrow=5,ncol=5,byrow=T, dimnames=list(estados,estados))
Google = new("markovchain", states=estados, transitionMatrix=Google.T, 
            name="Exemplo 1.7: Google PageRank, o motor de busca do Google.")
library(diagram)
par(mar=c(0,0,1,0))
plotmat(A = Google.T,
        box.type = "circle",          # shape of box
        box.lwd = 1,                  # border density of box
        relsize = 0.9,                # scaling factor for size of graph
        cex.txt = 0.7,                # size of probabilities
        lwd = 1,                      # border density of state to state arrows
        lcol = "black",
        box.col = "cornsilk1",
        box.size = 0.1,               # size of box
        box.prop = 0.6,               # height to width ratio of box
        arr.length = 0.5, arr.width = 0.2,
        self.cex = 0.5,                          # size of self probability box
        self.shifty = -0.03, self.shiftx = 0.13, # location of self prob. box
        # name = c("North Dhaka","Middle Dhaka","South Dhaka"),  # Optional
        main = "Diagrama das probabilidades de transição",
        cex.main = 1.3                # relative size of main title
        )

Google^1000

## Exemplo 1.7: Google PageRank, o motor de busca do Google.^1000 
##  A  5 - dimensional discrete Markov Chain defined by the following states: 
##  1, 2, 3, 4, 5 
##  The transition matrix  (by rows)  is defined as follows: 
##           1         2         3         4         5
## 1 0.1052632 0.1578947 0.2210526 0.2421053 0.2736842
## 2 0.1052632 0.1578947 0.2210526 0.2421053 0.2736842
## 3 0.1052632 0.1578947 0.2210526 0.2421053 0.2736842
## 4 0.1052632 0.1578947 0.2210526 0.2421053 0.2736842
## 5 0.1052632 0.1578947 0.2210526 0.2421053 0.2736842

Assim percebemos que nesta cadeia todos os estados se comunicam.

Definição 3.3: Classe de estados.

Uma classe \(\Delta\) de estados é um conjunto não vazio de estados, de modo que cada \(x \in \Delta\) se comunica com todos os outros estados \(y \in \Delta\) e não se comunica com \(z \notin \Delta\).

Esta definição implica que \(\Delta \subseteq S\), sendo \(S\) o espaço de estado da cadeia \(\{C_n\}\) e \(\Delta \neq \varnothing\). Utilizando novamente o exemplo da Figura 3.1, \(\{2,3\}\) é uma classe de estados, \(\{1\}\), \(\{4\}\), \(\{5\}\) e \(\{6\}\) são as outras classes. Observe que o estado 6 não se comunica com nenhum outro estado e nem mesmo pode ser acessado por ele mesmo, mas o conjunto que consiste em \(\{6\}\) sozinho ainda é uma classe.

Todo o conjunto de estados em uma determinada Cadeia de Markov é particionado em uma ou mais classes disjuntas dessa maneira. Observemos que no Exemplo 3.1 existe somente um classe, esta formada por todos os estados da cadeia.

A relação de equivalência no conjunto \(S\) o decompõe em classes de equivalência. Se \(S\) for enumerável, isso significa que \(S\) pode ser particionado em subconjuntos disjuntos \(\Delta_1, \Delta_2, \Delta_3,\cdots\) de \(S\) de modo que; dois elementos \(x,y\in S\) tais que \(x \rightleftharpoons y\) se, e somente se, eles pertencerem ao mesmo subconjunto da partições.

Teorema 3.1

Seja \(x\) um estado recorrente e suponha que \(x\) se comunica com \(y\). Então, \(y\) é recorrente e \(\rho_{x,y}=\rho_{y,x}=1\).

Demonstração.

Consideremos \(y\neq x\), caso contrário não teríamos nada a provar. Dado que \[ P_x(T_y < \infty) \, = \, \rho_{x,y} < 0, \] vemos que \(P_x(T_y=n) < 0\) para algum inteiro positivo \(n\). Seja \(n_0\) o menor de tais inteiros positivos, isto é, seja \[ n_0 \, = \, \min\big\{ n\geq 1 \, : \, P_x(T_y=n) < 0 \big\}\cdot \] Segue das expressões acima que \(p_{x,y}^{(n_0)} < 0\) e \[ p_{x,y}^{(m)} \, = \, 0, \qquad 1\leq m < n_0\cdot \] Dado que \(p_{x,y}^{(m)} > 0\), podemos encontrar estados \(y_1,\cdots,y_{n_0-1}\) tais que \[ P_x(C_1=y_1,\cdots,C_{n_0-1}=y_{n_0-1},C_{n_0}=y)=p_{x,y_1}\cdots p_{y_{n_0-1},y}>0\cdot \] Nenhum dos estados \(y_1,\cdots,y_{n_0-1}\) iguais a \(x\) ou \(y\). Se algum deles fosse igual \(x\) ou \(y\), seria possível ir de \(x\) para \(y\) com probabilidade positiva em menos de \(n_0\) passos, em contradição com \(p_{x,y}^{(m)} \, = \, 0\), \(1\leq m < n_0\). Vamos agora mostrar que \(\rho_{y,x}=1\). Suponha que, ao contrário disso, \(\rho_{y,x}< 1\). Então, se a cadeia partir de \(y\) tem probabilidade positiva \(1-\rho_{y,x}\) de nunca atingir \(x\). Mais ao ponto, uma Cadeia de Markov partindo do estado \(x\) tem a probabilidade positiva \(p_{x,y_1}\cdots p_{y_{n_0-1},y}(1-\rho_{y,x})\) de visitar os estados \(y_1,\cdots,y_{n_0-1},y\) sucessivamente nos primeiros \(n_0\) tempos e nunca retornar a \(x\) depois do tempo \(n_0\). Mas, se isso acontecer, a Cadeia de Markov nunca retornará a \(x\) a qualquer tempo \(n\ge 1\), portanto temos uma contradição com a suposição de que \(x\) é um estado recorrente. Dado que \(\rho_{y,x}=1\), existe um inteiro positivo \(n_1\) tal que \(\gamma^{(n_1)}_{y,x}>0\). Agora \[ \begin{array}{rcl} p^{(n_1+n+n_0)}_{y,y} & = & \displaystyle P_y(C_{n_1+n+n_0}=y) \\[0.6em] & \ge & \displaystyle P_y(C_{n_1}=x,C_{n_1+n}=x,C_{n_1+n+n_0}=y) \\[0.6em] & = & \displaystyle p^{(n_1)}_{y,x}p^{(n)}_{x,x}p^{(n_0)}_{x,y}\cdot \end{array} \] Portanto, \[ \begin{array}{rcl} \mbox{E}_y\big(N(y)\big) & \ge & \displaystyle \sum_{n=n_1+1+n_0}^\infty p^{(n)}_{y,y} \,= \, \displaystyle \sum_{n=1}^\infty p^{(n_1+n+n_0)}_{y,y} \\[1.1em] & \ge & \displaystyle p^{(n_1)}_{y,x}p^{(n_0)}_{x,y}\sum_{n=1}^\infty p^{(n)}_{x,x} \, = \, \displaystyle p^{(n_1)}_{y,x}p^{(n_0)}_{x,y}\mbox{E}_x\big(N(x)\big) \, = \, \infty, \end{array} \] do qual segue que \(y\) é também um estado recorrente. Desde que \(y\) é recorrente e \(y\) se comunica com \(x\), vemos da primeira parte da demonstração do teorema que \(\rho_{x,y}=1\). Isto completa a prova do teorema.

Como consequência deste teorema afirmamos que, para Cadeias de Markov finitas, um estado recorrente é um estado \(x\) que é acessível a partir de todos os estados acessíveis a partir de \(x\), \(x\) é recorrente se \(x \rightarrow y\) implica que \(y \rightarrow x\).

De acordo com este teorema, um estado \(x\) em uma Cadeia de Markov finita é recorrente se não houver possibilidade de ir para um estado \(y\) a partir do qual não possa haver retorno. Como veremos mais tarde, se uma Cadeia de Markov entrar em um estado recorrente, ela retorna a esse estado eventualmente com probabilidade 1 e, portanto, continuará retornando infinitamente, na verdade, esta propriedade serve como a definição de recorrência para Cadeias de Markov infinitas ou com infinitos estados.

Um estado \(x\) é transiente se houver algum estado \(y\) que seja acessível a partir de \(x\), mas do qual não há retorno possível. Cada vez que o sistema retorna para \(x\), existe a possibilidade de ir para \(y\); eventualmente, essa possibilidade ocorrerá sem mais retornos para \(x\).

Definição 3.4: Conjunto de estados fechado.

Um conjunto \(F\subset S\) de estados é dito ser um conjunto fechado se não existirem estados dentro de \(F\) que se comuniquem com qualquer estado fora de \(F\).

Esta definição significa que se \(F\) for um conjunto fechado, então \[ \rho_{x,y} \, = \, 0, \qquad x\in F \quad \mbox{e} \quad y\notin F\cdot \] De maneira equivalente, \(F\) é um conjunto de estados fechado se, e somente se, \[ p_{x,y}^{(n)} \, = \, 0, \qquad x\in F, \quad y\notin F \quad \mbox{e} \quad n\geq 1\cdot \]

Mais ainda, da condição fraca que \[ p_{x,y} \, = \, 0, \qquad x\in F \quad \mbox{e} \quad y\notin F, \] podemos demonstrar que \(F\) seja um conjunto de estados fechado. Se a expressão acima se cumpre, então para \(x\in F\) e \(y\notin F\) temos que \[ p_{x,y}^{(2)} \, = \, \sum_{z\in S} p_{x,z}p_{z,y} \, = \, \sum_{z\in F} p_{x,z}p_{z,y} \, = \, 0, \] e a condição \(p_{x,y}^{(n)} = 0, \, x\in F, \, y\notin F, \, n\geq 1\) se cumpre por indução.

Significa que, se \(F\) for um conjunto de estados fechados, então a Cadeia de Markov começando em \(F\), estará em \(F\) o tempo todo com probabilidade um. Se \(a\) for um estado absorvente então o conjunto \(\{a\}\) é fechado.

Definição 3.5: Conjunto de estados irredutível.

A classe \(F\subseteq S\) de estados é dita ser um conjunto irredutível se cada estado \(x\in F\) se comunica com qualquer outro estado \(y\in F\).

Deduzimos, pelo Teorema 3.1, que se \(F\) for um conjunto de estados irredutível fechado; então um ou outro: ou todo estado em \(F\) é recorrente ou todo estado em \(F\) é transiente.

Para o exemplo da Figura 3.1, \(\{2,3\}\) e \(\{5\}\) são classes recorrentes e as outras classes são transientes. Em termos do grafo de uma Cadeia de Markov, uma classe é transiente se houver quaisquer arcos direcionados indo de um estado na classe para um estado fora da classe. Cada Cadeia de Markov com finito espaço de estados deve ter pelo menos uma classe recorrente de estados e pode ter arbitrariamente muitas classes adicionais de estados recorrentes e estados transientes.

Teorema 3.2

Seja \(F\) um conjunto irredutível fechado de estados recorrentes. Então:

\(\rho_{x,y} \, = \, 1\),
\(P_x\big(N(y)=\infty\big)=1\),
\(\mbox{E}_x\big(N(y)\big)=\infty\),

para todo \(x,y\in F\).

Demonstração.

Consequência imediata do Teorema 3.1.

Uma Cadeia de Markov irredutível é uma cadeia cujo espaço de estados é irredutível, ou seja, uma cadeia em que cada estado se comunica de volta consigo e também com todos os outros estados. Tal Cadeia de Markov é necessariamente quer uma cadeia transiente ou uma cadeia recorrente. O Teorema 3.2 implica, em particular, que uma Cadeia de Markov irredutível recorrente visita todos seus estados infinitas vezes com probabilidade um.

Teorema 3.3

Seja \(F\) um conjunto finito e fechado de estados irredutíveis. Então, cada estado em \(F\) é recorrente.

Demonstração.

Sabemos, pelo Teorema 2.10 que se \(S\) for finito contém pelo menos um estado recorrente. O mesmo argumento mostra que qualquer conjunto finito de estados contém, ao menos, um estado recorrente. Seja agora \(F\) finito irredutível fechado. Sabemos que todo estado em \(F\) é transiente ou todo estado em \(F\) é recorrente e que \(F\) tem, ao menos, um estado recorrente. Segue então que todo estado em \(F\) é recorrente.

Faremos um resumo dos resultados até agora para Cadeias de Markov com espaço de estados finito. O Teorema 3.3 nos disse que se a cadeia for irredutível ela deve ser recorrente. Se a cadeia não for irredutível, podemos utilizar os Teoremas 3.1 e 3.3 para identificar quais estados são recorrentes e quais são transientes. Com o exemplo a seguir mostramos o procedimento de identificação de estados recorrentes e transientes de duas formas: de maneira teórica e também de maneira numérica.

Exemplo 3.2.

Considere uma Cadeia de Markov com espeço de estados \(S=\{0,1,2,3,4,5\}\) e matriz de transição: \[ \mathcal{P} \, = \, \begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 \\ \frac{1}{4} & \frac{1}{2} & \frac{1}{4} & 0 & 0 & 0 \\ 0 & \frac{1}{5} & \frac{2}{5} & \frac{1}{5} & 0 & \frac{1}{5} \\ 0 & 0 & 0 & \frac{1}{6} & \frac{1}{3} & \frac{1}{2} \\ 0 & 0 & 0 & \frac{1}{2} & 0 & \frac{1}{2} \\ 0 & 0 & 0 & \frac{1}{4} & 0 & \frac{3}{4} \end{pmatrix}\cdot \]

Queremos determinar quais estados são recorrentes e quais transientes.

Como primeiro passo no estudo, vamos determinar por inspeção quais estados se comunicam com quais outros. Isto pode ser realizado indicando a matriz da seguinte forma: \[ \mathcal{P} \, = \, \begin{pmatrix} + & 0 & 0 & 0 & 0 & 0 \\ + & + & + & + & + & + \\ + & + & + & + & + & + \\ 0 & 0 & 0 & + & + & + \\ 0 & 0 & 0 & + & + & + \\ 0 & 0 & 0 & + & + & + \end{pmatrix}\cdot \]

O elemento \((x,y)\) desta matriz é \(+\infty\) ou \(0\) de acordo com \(\rho_{x,y}\), se for positivo ou zero. Isto é, de acordo se \(x\) se comunica ou não com \(y\). Claro que, se \(p_{x,y}>0\) então \(\rho_{x,y}>0\). O contrário não é verdade em geral. Por exemplo, \(p_{2,0}=0\) mas \[ p^{(2)}_{2,0} \, = \, p_{2,1}p_{1,0} \, = \, \frac{1}{5}\times \frac{1}{4} \, = \, = \, \frac{1}{20}\, > \,0, \] portanto, \(\rho_{2,0}>0\).

O estado \(0\) é absorvente, logo recorrente. Vemos da matriz de \(+\) e zeros que \(\{3,4,5\}\) é um conjunto de estados fechado irredutível. Pelo Teorema 3.3 este resultado implica que os estados 3, 4 e 5 são recorrentes. Os estados 1 e 2 se comunicam com o 0, mas nenhum deles pode ser alcançado desde o 0. Do Teorema 3.1, por negação, temos que os estados 1 e 2 devem ser transientes. Resumindo, os estados 1 e 2 são transientes e os estados 0, 3, 4 e 5 são recorrentes.

Neste exemplo, o primeiro tabalho foi identificar quais estados se comunicam. Isto pode ser realizado utilizando as linhas de comando a seguir:

Estados = c("0", "1", "2", "3", "4", "5")
Prob.T=matrix(c(1,0,0,0,0,0,1/4,1/2,1/4,0,0,0,
                0,1/5,2/5,1/5,0,1/5,0,0,0,1/6,1/3,1/2,
                0,0,0,1/2,0,1/2,0,0,0,1/4,0,3/4), 
              nrow = 6, ncol = 6,byrow=T, dimnames=list(Estados,Estados))
ProbT = new("markovchain", states=Estados, transitionMatrix=Prob.T, name="Exemplo 3.2")
ProbT

## Exemplo 3.2 
##  A  6 - dimensional discrete Markov Chain defined by the following states: 
##  0, 1, 2, 3, 4, 5 
##  The transition matrix  (by rows)  is defined as follows: 
##      0   1    2         3         4    5
## 0 1.00 0.0 0.00 0.0000000 0.0000000 0.00
## 1 0.25 0.5 0.25 0.0000000 0.0000000 0.00
## 2 0.00 0.2 0.40 0.2000000 0.0000000 0.20
## 3 0.00 0.0 0.00 0.1666667 0.3333333 0.50
## 4 0.00 0.0 0.00 0.5000000 0.0000000 0.50
## 5 0.00 0.0 0.00 0.2500000 0.0000000 0.75

is.accessible(ProbT)

##       0     1     2     3     4     5
## 0  TRUE FALSE FALSE FALSE FALSE FALSE
## 1  TRUE  TRUE  TRUE  TRUE  TRUE  TRUE
## 2  TRUE  TRUE  TRUE  TRUE  TRUE  TRUE
## 3 FALSE FALSE FALSE  TRUE  TRUE  TRUE
## 4 FALSE FALSE FALSE  TRUE  TRUE  TRUE
## 5 FALSE FALSE FALSE  TRUE  TRUE  TRUE

No código acima apresentado utilizamos o comando is.accesible para identificar quais estados se comunicam e por reposta temos TRUE, caso a resposta seja afirmativa e FALSE, caso contrário.

Uma outra forma de identificar quais estados são transientes e quais recorrentes é calculando uma potência elevada da matriz de transição, por exemplo:

ProbT^2000

## Exemplo 3.2^2000 
##  A  6 - dimensional discrete Markov Chain defined by the following states: 
##  0, 1, 2, 3, 4, 5 
##  The transition matrix  (by rows)  is defined as follows: 
##     0 1 2    3          4         5
## 0 1.0 0 0 0.00 0.00000000 0.0000000
## 1 0.6 0 0 0.10 0.03333333 0.2666667
## 2 0.2 0 0 0.20 0.06666667 0.5333333
## 3 0.0 0 0 0.25 0.08333333 0.6666667
## 4 0.0 0 0 0.25 0.08333333 0.6666667
## 5 0.0 0 0 0.25 0.08333333 0.6666667

Identificamos que os estados 0, 3, 4 e 5 são recorrentes e, por negação do Teorema 3.1, vemos que se \(x\) for recorrente e \(y\) transiente, então \(x\) não se comunica com \(y\). Justamente é isso que observamos na matriz anterior dos estados 1 e 2, por isso concluímos que estes estados são transientes.

Mais ainda, podemos auxiliarmos do pacote de funções markovchain. Neste pacote, a função transientStates, identifica quais estados são transientes, basta somente digitar:

transientStates(ProbT)

## [1] "1" "2"

obtendo como resposta que os estados 1 e 2, nesta situação, são transientes.

Também, utilizando a função steadyStates, no mesmo pacote, podemos identificar os estados recorrestes digitando:

steadyStates(ProbT)

##      0 1 2    3          4         5
## [1,] 0 0 0 0.25 0.08333333 0.6666667
## [2,] 1 0 0 0.00 0.00000000 0.0000000

Na primeira linha, onde aparecer um valor zero ou próximo de zero significa que o estado correspondente não é recorrente. Ou seja, identificamos que os estados 0, 3, 4 e 5 são recorrentes.

Seja \(S\) o espaço de estados de uma Cadeia de Markov. Denotaremos por \(S_T\) o conjuntos dos estados transientes em \(S\) e por \(S_R\) o conjunto dos estados recorrentes em \(S\). No Exemplo 3.2, \[ S_T=\{1,2\} \qquad \mbox{e} \qquad S_R=\{0,3,4,5\}\cdot \] Ainda o conjunto \(S_R\) pode ser decomposto nos conjuntos fechados disjuntos e irredutíveis de estados \(F_1=\{0\}\) e \(F_2=\{3,4,5\}\). O teorema a seguir mostra que esta decomposição sempre é possível qualquer seja \(S_R\) não vazio.

Teorema 3.4

Suponha que o conjunto \(S_R\) de estados recorrentes em \(S\), seja não vazio. Então, \(S_R\) é a união finita ou enumerável de conjuntos fechados disjuntos e irredutíveis \(F_1,F_2,\cdots\).

Demonstração.

Escolhemos \(x\in S_R\) e seja \(F\) o conjunto de todos os estados \(y\in S_R\) tais que \(x\) comunica \(y\). Devido a \(x\) ser recorrente \(\rho_{x,x}=1\) e, portanto, \(x\in F\). Verifiquemos agora se \(F\) é um conjunto fechado e irredutível. Suponhamos que \(y\) pertence a \(F\) e que \(y\) se comunica com \(z\). Devido a \(y\) ser recorrente, segue pelo Teorema 3.1 que \(z\) também é recorrente. Logo, \(z\in F\). Isto mostra que \(F\) é fechado. Suponhamos agora que \(y\) e \(z\) estejam ambos em \(F\). Foi nossa escolha que \(x\) fosse recorrente e que se comunica com \(y\), segue do Teorema 3.2 que \(y\) se comunica com \(x\). Dado que \(y\) se comunica com \(x\) e \(x\) se comunica com \(z\), concluímos que \(y\) se comunica com \(z\). Isto mostra que \(F\) é irredutível.

Para concluir a demonstração devemos provar que se \(F\) e \(D\) forem dois subconjuntos fechados irredutíveis de \(S_R\) então ou são disjuntos ou são idênticos. Suponhamos que não sejam disjuntos e que exista um estado \(x\) que pertença a ambos, \(x\in F\) e \(x\in D\). Escolhemos um \(y\in F\). Sabemos que \(x\) se comunica com \(y\), devido a \(x\) pertencer a \(F\) e \(F\) ser um conjunto irredutível. Dado que \(D\) é fechado, \(x\) que está em \(D\) também e se comunica com \(y\), implica que \(y\) está também em \(D\). Logo, todo estado em \(F\) está também em \(D\). Similarmente, todo estado em \(D\) está também em \(F\) logo, \(F\) e \(D\) são idênticos.

Podemos usar nossa decomposição do espaço de estados de uma Cadeia de Markov para entender o comportamento de um sistema deste tipo. Se a Cadeia de Markov começa em um dos conjuntos de estados recorrentes fechados irredutíveis \(F_i\), ela permanece em \(F_i\) para sempre e, com probabilidade um, visita todos os estados \(F_i\) infinitas vezes. Se a Cadeia de Markov começa no conjunto de estados transientes \(S_T\), ou ela permanece em \(S_T\) para sempre ou, em algum momento, entra num dos conjuntos \(F_i\) e permanece lá a partir desse momento, mais uma vez visitando todos os estados em \(F_i\) infinitas vezes.

Exemplo 3.3: Continuação do Exemplo 3.2.

Podemos obter um resumo da Cadeia de Markov com o comando summary do pacote selecionado markovchain:

Estados = c("0", "1", "2", "3", "4", "5")
Prob.T=matrix(c(1,0,0,0,0,0,1/4,1/2,1/4,0,0,0,
                0,1/5,2/5,1/5,0,1/5,0,0,0,1/6,1/3,1/2,
                0,0,0,1/2,0,1/2,0,0,0,1/4,0,3/4), 
              nrow = 6, ncol = 6,byrow=T, dimnames=list(Estados,Estados))
ProbT = new("markovchain", states=Estados, transitionMatrix=Prob.T, name="Exemplo 3.2")
summary(ProbT)

## Exemplo 3.2  Markov chain that is composed by: 
## Closed classes: 
## 0 
## 3 4 5 
## Recurrent classes: 
## {0},{3,4,5}
## Transient classes: 
## {1,2}
## The Markov chain is not irreducible 
## The absorbing states are: 0

A pergunta que fica é: como o algoritmo faz a classificação? a resposta está na seguinte seção.

3.1. Classificando os estados

Esta seção fornece o algoritmo de rotulagem de Fox and D. M. Landi (1968) para determinar as classes irredutíveis fechadas e os estados transientes de uma Cadeia de Markov finita. Definimos o algoritmo de maneira mais formal.

O algoritmo explora habilmente as seguintes propriedades de uma matriz de probabilidade de transição:

O estado \(s\) é absorvente se e somente se \(p_{s,s}> 0\) e \(p_{s,x} = 0\) para todos os \(x\neq s\).
Se o estado \(s\) é absorvente e \(p_{y,s}> 0\), então estado \(y\) é transiente.
Se o estado \(s\) é transiente e \(p_{y,s}> 0\), então o estado \(y\) é transiente.
Se o estado \(x\) se comunica com \(y\) e \(y\) se comunica com \(z\), então \(x\) se comunica com \(z\).
Se o estado \(x\) se comunica com \(y\), então \(x\) é transiente se \(y\) for transiente e \(x\) é recorrente se \(y\) for recorrente.

Observe que as propriedades acima dependem apenas do padrão de 0 e entradas positivas, de modo que se apenas uma decomposição for necessária, a matriz \(\mathcal{P}\) pode ser substituída por uma matriz de incidência \(\mathcal{B}\) com \(b_{x,y} = 1\) se \(p_{x,y}> 0\) e 0 caso contrário.

Suponha que \(S = \{1,2,..., N\}\). No algoritmo, \(L(x)\) denota o rótulo atribuído ao estado \(x\); estados recorrentes recebem um rótulo \(R\), estados transientes \(T\) e estados não rotulados \(O\). O conjunto \(U\) denota estados não rotulados e \(S(x)\) denota estados que foram identificados como se comunicando com \(x\).

Usamos o conjunto \(W\) para indicar os índices de linhas e colunas em uma matriz agregada construída na etapa 5. Uma descrição verbal do algoritmo segue sua declaração formal.

3.1.1. O algoritmo de decomposição

Inicialização. Seja \(S(x)=\{x\}\), \(L(x)=O\) para \(x=1,2,\cdots,N\), \(U=S\) e \(W=S\).
Identificação preliminar.

Para cada \(x\in U\), se \(p_{x,x}>0\) e \(p_{x,y}=0\) para todo \(y\neq x\), seja \(L(x)=R\) e subtituir \(U\) por \(U\setminus \{x\}\).
Se \(U=\emptyset\), ir até o passo 6; caso contrário, para cada \(y\) para o qual \(L(y)=R\), se \(p_{x,y}>0\) para qualquer \(x\in U\), seja \(L(x)=T\) e substitua \(u\) por \(U\setminus \{x\}\).

Parando. Se \(U = \emptyset\), ir para a etapa 6; caso contrário, defina \(r = 0\) e ir para a etapa 4.
Formação do caminho.

Selecione um \(x\in U\), defina \(x_r=x\).
Escolha um estado \(y\neq x_r\), para o qual \(p_{x_r,y}>0\); seja \(x_{r+1}=y\).

Se \(L(x_{r+1})=T\), definimos \(L(x)=T\) para \(x\in S(x_0)\cup \cdots \cup S(x_{r+1})\) e então substituimos \(U\) por \(U\setminus \{S(x_0)\cup \cdots \cup S(x_{r+1})\}\) indo para a etapa 3.
Se \(L(x_{r+1})\neq T\) e \(x_{r+1}=x_k\) para algum \(k\), \(0\leq k\leq r\), ir para a etapa 5. Caso contrário, substitua \(r\) por \(r + 1\) e ir para a etapa 4(b).

Agregação de caminho.

Substitua \(p_{x_k,y}\) por \(p_{x_k,y}+p_{x_{k+1},y}+\cdots+p_{x_r,y}\) para todo \(y\in W\).
Substitua \(p_{x,x_k}\) por \(p_{x,x_k}+p_{x,x_{k+1}}+\cdots+p_{x,x_r}\) para todo \(x\in W\).
Substitua \(S(x_k)\) por \(S(x_k)\cup \cdots \cup S(x_r)\).
Substitua \(W\) por \(W\setminus \{x_{k+1},\cdots x_r\}\), isto é, excluir linhas e colunas \(x_{k+1},\cdots x_r\) da matriz.
Se \(p_{x_k,x_k}>0\) e \(p_{x_k,y}=0\), para todo \(y\in W\) faça o seguinte:

Seja \(L(x)=R\), para todo \(x\in S(x_k)\) e substitua \(U\) por \(U\setminus S(x_k)\).
Se \(k>0\), fazemos \(L(x)=T\) para todo estado \(x\in S(x_0)\cup \cdots \cup S(x_{k-1})\) e, então, substituimos \(U\) por \(U\setminus \{S(x_0)\cup \cdots \cup S(x_{k-1})\}\).
Para \(y\in U\) se \(p_{y,x_h}>0\) para algum \(h\), \(0\leq h\leq k\), seja \(L(x)=T\) para todo \(x\in S(y)\) e substituimos \(U\) por \(U\setminus S(y)\).
Ir para a etapa 3.

Seja \(r=k\) e ir para a etapa 4.

Classificação. Para cada \(x\in W\) para o qual \(L(x) = R\), \(S(x)\) é uma classe irredutível fechada. Todos os outros estados são transientes.

Podemos parafrasear as etapas 4 e 5 do algoritmo da seguinte maneira. Escolha um estado não classificado e comece um caminho começando por ele. Estenda o caminho até que ele identifique um estado transiente ou ele faça um ciclo; ou seja, ele repete o estado prévio na cadeia.

No primeiro caso, classifique todos os estados no caminho como transientes; caso contrário, combine todos os estados do ciclo e determine se eles são recorrentes. Observe que as etapas 5(a) - 5(d) são uma maneira bastante formal de dizer “substitua a linha e a coluna \(x_k\), pela soma das entradas nas linhas e colunas \(x_k,x_{k+1},\cdots,x_r\) e exclua essas linhas e colunas da matriz”. O algoritmo acima funciona com a matriz completa, mas ignora as colunas “excluídas”.

Se, em vez de utilizar a matriz de probabilidade de transição, usarmos a matriz de incidência para os cálculos, substituiremos as etapas 5(a) e 5(b) por uma operação booleana “ou”; isto é, se \(u = 0\) e \(\nu = 0\), então \(u + \nu = 0\), caso contrário, \(u + \nu = 1\). Usar a matriz de incidência permite o armazenamento eficiente de matrizes grandes e cálculos mais rápidos.

O algoritmo descrito requer \(O(|S|^2)\) comparações. Como existem \(S^2\) pares de ídices, este algoritmo é extremamente eficiente. Este algoritmo está programado no pacote de funções markovchain e no seguinte exemplo mostra-se numa aplicação.

Exemplo 3.4: Mobilidade social.

Em um artigo acerca da mobilidade social na Grão-Bretanha de pós-guerra de Glass and Hall no livro Glass (1954), fizeram um estudo da mudança intergeracional nos estados.

Nesse trabalho os autores distinguem sete estados em seu estudo de mobilidade social:

profissional, alto administrativo;
gerencial;
inspeção, supervisão, não manual de alto grau;
não manual de baixo grau;
manual especializado;
manual semi-especializado;
manual não qualificado.

A partir de seus dados, surge a seguinte matriz de probablidades de transição: \[ \mathcal{P}=\begin{pmatrix} 0.386 & 0.147 & 0.202 & 0.062 & 0.140 & 0.047 & 0.016 \\ 0.107 & 0.267 & 0.227 & 0.120 & 0.207 & 0.052 & 0.020 \\ 0.035 & 0.101 & 0.188 & 0.191 & 0.357 & 0.067 & 0.061 \\ 0.021 & 0.039 & 0.112 & 0.212 & 0.431 & 0.124 & 0.061 \\ 0.009 & 0.024 & 0.075 & 0.123 & 0.473 & 0.171 & 0.125 \\ 0.000 & 0.013 & 0.041 & 0.088 & 0.391 & 0.312 & 0.155 \\ 0.000 & 0.008 & 0.036 & 0.083 & 0.364 & 0.235 & 0.274 \end{pmatrix}\cdot \]

Podemos obter um resumo da Cadeia de Markov com o comando summary do pacote selecionado markovchain:

Estados = c("(1)","(2)","(3)","(4)","(5)","(6)","(7)")
Prob.T=matrix(c(0.386,0.147,0.202,0.062,0.140,0.047,0.016,
                0.107,0.267,0.227,0.120,0.207,0.052,0.020,
                0.035,0.101,0.188,0.191,0.357,0.067,0.061,
                0.021,0.039,0.112,0.212,0.431,0.124,0.061,
                0.009,0.024,0.075,0.123,0.473,0.171,0.125,
                0.000,0.013,0.041,0.088,0.391,0.312,0.155,
                0.000,0.008,0.036,0.083,0.364,0.235,0.274), 
              nrow = 7, ncol = 7, byrow=T, dimnames=list(Estados,Estados))
ProbT = new("markovchain", states=Estados, transitionMatrix=Prob.T, name="Exemplo 3.4")
summary(ProbT)

## Exemplo 3.4  Markov chain that is composed by: 
## Closed classes: 
## (1) (2) (3) (4) (5) (6) (7) 
## Recurrent classes: 
## {(1),(2),(3),(4),(5),(6),(7)}
## Transient classes: 
## NONE 
## The Markov chain is irreducible 
## The absorbing states are: NONE

Temos como resposta que todos os estados são recorrentes; portanto é uma cadeia recorrente e irredutível.

3.2. Probabilidade de absorção

Queremos saber qual a probabilidade de uma cadeia, começando em qualquer estado \(x\), chegar a um destes conjuntos fechados irredutíveis de estados recorrentes?

Sabemos, pela Definição 2.3, que se \(F\) for um conjunto fechado de estados irredutíveis recorrentes então \[ \rho_{_{x,F}} \, = \, P_x(T_F < \infty), \] é a probabilidade de que uma Cadeia de Markov a partir de \(x\), eventualmente, visite o conjunto \(F\).

Desde que a cadeia continue permanentemente em \(F\), uma vez que atinge este conjunto, chamamos de \(\rho_{_{x,F}}\) a probabilidade que uma cadeia a partir de \(x\) seja absorvida pelo conjunto \(F\). Logico que \(\rho_{_{x,F}}=1\), \(x\in F\) e \(\rho_{_{x,F}}=0\) se \(x\) for um estado recorrente que não esteja em \(F\). Ele não é tão claro como calcular \(\rho_{_{x,F}}\) para \(x\in S_T\), o conjunto de estados transientes.

Se houver apenas um número finito de estados transientes e, em particular, se \(S\) em si for finito é sempre possível calcular \(\rho_{_{x,F}}\), \(x\in S_T\) resolvendo um sistema de equações lineares em que há tantas equações como incógnitas, ou seja, os elementos de \(S_T\).

Para entender por que este é o caso, observemos que, se a cadeia partir de \(x\), pode entrar em \(F\) apenas entrando em \(C\) no tempo 1 ou por estar em \(S_T\) no tempo 1 e entrando em \(F\) em algum momento futuro. O primeiro evento tem probabilidade \(\sum_{y\in F} p_{x,y}\) e o último evento tem probabilidade \(\sum_{y\in S_T} p_{x,y}\rho_{_{y,F}}\).

Assim \[ \rho_{_{x,F}} \, = \, \sum_{y\in F} p_{x,y}+\sum_{y\in S_T} p_{x,y}\rho_{_{y,F}}, \qquad x\in S_T\cdot \]

A equação acima se cumpre sempre que \(S_T\) seja finito ou infinito, mas está longe de ser claro como a resolver para as incógnitas \(\rho_{_{x,F}}\), \(x\in S_T\) quando \(S_T\) é infinito. Uma dificuldade adicional ao fato de \(S_T\) ser infinto acontece quando a equação acima não necessariamente tem solução única. Afortunadamente esta dificuldade não acontece quando \(S_T\) é finito.

Teorema 3.5

Suponhamos que o conjunto dos estados transientes \(S_T\) seja finito e que \(F\) seja o conjunto fechado irredutível dos estados recorrentes da cadeia. Então, o sistema de equações \[ f(x)=\sum_{y\in F} p_{x,y}+\sum_{y\in S_T} p_{x,y}\, f(y), \qquad x\in S_T, \] tem por solução única \[ f(x)=\rho_{_{x,F}}, \qquad x\in S_T\cdot \]

Demonstração.

Se a primeira expressão no teorema for válida, então \[ f(y)=\sum_{z\in F} p_{y,z}+\sum_{z\in S_T} p_{y,z}\, f(z), \qquad y\in S_T\cdot \] Substituindo-a, temos que \[ \begin{array}{rcl} f(x) & = & \displaystyle \sum_{y\in F} p_{x,y}+\sum_{y\in S_T} \sum_{z\in F} p_{x,y}p_{y,z} \, + \, \displaystyle \sum_{y\in S_T} \sum_{z\in S_T} p_{x,y}p_{y,z}\, f(z)\cdot \end{array} \] A soma dos primeiros dois termos é justamente \(P_x(T_F\le 2)\) e o terceiro termo se reduz a \(\sum_{z\in S_T} p^{(2)}_{x,z} \, f(z)\), o qual é o mesmo do que \(\sum_{y\in S_T} p^{(2)}_{x,y}\, f(y)\). Então \[ f(y)=P_x(T_F\le 2)+\sum_{y\in S_T} p^{(2)}_{x,y}\, f(y)\cdot \] Repetindo este argumento infinitas vezes ou utilizando a indução matemática, concluímos que para todos os inteiros positivos \(n\) se satisfaz que \[ f(y)=P_x(T_F\le n)+\sum_{y\in S_T} p^{(n)}_{x,y}\, f(y), \qquad x\in S_T\cdot \] Dado que cada \(y\in S_T\) é transiente, segue que \[ \lim_{n\to\infty} p^{(n)}_{x,y}=0, \qquad x\in S \quad \mbox{e} \quad y\in S_T \cdot \] De acordo com as suposições do teorema, \(S_T\) é um conjunto finito. Resulta, portanto, que do resultado acima a soma naterior se aproxima de zero quando \(n\to\infty\). Por consequência, para \(x\in S_T\) \[ f(x)=\lim_{n\to\infty} P_x(T_F\le n) = P_x(T_C<\infty)=\rho_{_{x,F}}, \] como desejado.

Exemplo 3.3: Continuação do Exemplo 3.2.

No Exemplo 32 foi obtido que o conjunto \(F=\{0,2,4,5\}\) é constituído de estados recorrentes. Queremos encontrar as probabilidades da cadeia visitar o conjunto \(F\) partindo dos estados transientes 1 e 2.

Encontremos \[ \rho_{1,0}=\rho_{{1,\{0\}}} \qquad \mbox{e} \qquad \rho_{2,0}=\rho_{{2,\{0\}}}\cdot \] Da matriz de transição no Exemplo 3.2, temos que \(\rho_{1,0}\) e \(\rho_{2,0}\) são determinados pelas equações \[ \rho_{1,0}=\frac{1}{4}+\frac{1}{2}\rho_{1,0}+\frac{1}{4}\rho_{2,0} \qquad \mbox{e} \qquad \rho_{2,0}=\frac{1}{5}\rho_{1,0}+\frac{2}{5}\rho_{2,0}\cdot \]

Resolvendo este sistema encontramos que \(\rho_{1,0}=\frac{3}{5}\) e \(\rho_{2,0}=\frac{1}{5}\). De maneira similar encontramos que \(\rho_{{1,\{3,4,5\}}}=\frac{2}{5}\) e \(\rho_{{2,\{3,4,5\}}}=\frac{4}{5}\).

Alternativamente, podemos encontrar as probabilidades no exemplo pela subtração de \(\rho_{\{0\}}(1)\) e \(\rho_{\{0\}}(2)\) de 1, devido a que existe somente um número finito de estados transientes. Isto é possível segundo o teorema a seguir.

Teorema 3.6

Seja \(S_T\) finito, isto é, o número de estados transientes na Cadeia de Markov é finito. Então, \[ \sum_{i=1}^\infty \rho_{_{x,F_i}}=1, \qquad x\in S_T, \] onde \(F_1,F_2,\cdots\) é a coleção, finita ou infinita enumerável, de conjuntos disjuntos fechados e irredutíveis de estados recorrentes da cadeia.

Demonstração.

Para verificar a afirmação notemos que para \(x\in S_T\) \[ \sum_{i=1}^\infty \rho_{_{x,F_i}} \, = \, \sum_{i=1}^\infty P_x(T_{F_i} <\infty) \, = \, P_x(T_{S_R}<\infty)\cdot \] Dado que existe somente um número finito de estados transientes e cada estado transiente é visitado somente um número finito de vezes, a probabilidade \(P_x(T_{S_R}<\infty)\), de que um estado recorrente seja atingido é 1, portanto a afirmação se verifica.

Uma vez que a Cadeia de Markov, começando no estado transiente \(x\) entra em um conjunto fechado irredutível \(F\) de estados recorrentes, ela visita então todos os estados em \(F\). Assim \[ \rho_{x,y}=\rho_{_{x,F}},\qquad x\in S_T \quad \mbox{e} \quad y\in F\cdot \]

Exemplo 3.4: Continuação do Exemplo 3.3.

Da demonstração do Teorema 3.6, temos que em nosso prévio exemplo \[ \rho_{1,3}=\rho_{1,4}=\rho_{1,5}=\rho_{1,\{3,4,5\}}=\frac{2}{5} \qquad \mbox{e} \qquad \rho_{2,3}=\rho_{2,4}=\rho_{2,5}=\rho_{2,\{3,4,5\}}=\frac{4}{5}, \] são as probabilidades de atingirmos o estado de conjuntos recorrentes \(F=\{3,4,5\}\) a partir dos estados transientes.

O tema das Cadeias de Markov é melhor estudado considerando-se tipos especiais: o primeiro tipo que vamos estudar são as chamadas Cadeias de Markov absorventes, depois estudaremos as Cadeias de Markov regulares e depois as ergódicas.

3.3. Cadeias absorventes

Ao fazer a decomposição do espaço de estados podemos identificar tipos especiais de Cadeias de Markov. O primeiro tipo especial que vamos estudar é a chamada Cadeia de Markov absorvente.

Definição 3.5: Cadeias absorventes.

Uma Cadeia de Markov é absorvente se tiver pelo menos um estado absorvente e se, a partir de cada estado, é possível ir para um estado absorvente.

Em uma Cadeia de Markov absorvente, um estado que não é absorvente é transiente. Devemos esclarecer que nestas cadeias é possível atingir um estado absorvente não necessariamente em uma única etapa.

Exemplo 3..5: A caminhada do bêbado.

Um homem caminha ao longo de um trecho de quatro quarteirões segundo o grafo na Figura 3.5. Se ele estiver no nodo 1, 2 ou 3, então ele caminha para a esquerda ou para a direita com a mesma probabilidade. Ele continua até ele chegar ao nodo 4, onde há um bar ou ao nodo 0, que está sua casa.

Se ele atinge ou sua casa ou o bar, ele permanece lá. Podemos então construir uma Cadeia de Markov com estados \(S=\{0,1,2,3,4\}\). Observamos que os estados 0 e 4 são absorventes.

A matriz de transiçõo é então: \[ \begin{matrix} & \\ \mathcal{P} = \begin{matrix} 0 \\ 1 \\ 2 \\ 3 \\ 4 \end{matrix} \left( \vphantom{ \begin{matrix} 12 \\ 12 \\ 12 \\ 12 \\ 12 \end{matrix} } \right. \end{matrix} \hspace{-1.2em} \begin{matrix} 0 & 1 & 2 & 3 & 4 \\ 1 & 0 & 0 & 0 & 0 \\ 1/2 & 0 & 1/2 & 0 & 0 \\ 0 & 1/2 & 0 & 1/2 & 0 \\ 0 & 0 & 1/2 & 0 & 1/2 \\ 0 & 0 & 0 & 0 & 1 \end{matrix} \hspace{-0.2em} \begin{matrix} & \\ \left. \vphantom{ \begin{matrix} 12 \\ 12 \\ 12 \\ 12 \\ 12 \end{matrix} } \right)\cdot \end{matrix} \]

estados = c("0","1","2","3","4")
P=matrix(c(1,0,0,0,0,1/2,0,1/2,0,0,
           0,1/2,0,1/2,0,0,0,1/2,0,1/2,
           0,0,0,0,1),
         nrow=5,ncol=5,byrow=T, dimnames=list(estados,estados))
P.caminhada = new("markovchain", states=estados, transitionMatrix=P, 
            name="Exemplo 3.5: Caminhada do bêbado.")
set.seed(896)
par(mar=c(0,0,0,0))
plot(P.caminhada,package="diagram")

Figura 3.5: Caminha do bêbado.

Os estados 1, 2, e 3 são transientes e a partir destes é possível alcançar os estados absorventes 0 e 4. Assim, a cadeia é absorvente. Quando um processo chega a um estado absorvente, diremos que ele é absorvido.

A pergunta mais óbvia que pode ser feita sobre a cadeia é: Qual é a probabilidade de que o processo vai eventualmente atingir um estado absorvente? Outras questões interessantes incluem:

Qual será a probabilidade de que o processo vai acabar em um determinado estado absorvente?
Em média, quanto tempo será necessário para que o processo seja absorvido?
Em média, quantas vezes o processo estará em cada estado transiente?

As respostas a todas estas questões dependem, em geral, no estado a partir do qual o processo é iniciado, bem como das probabilidades de transição.

Exemplo 3.6: Gestão de cálculos biliares.

Este exemplo têm como base o artigo de Sox et al. (1988). Os médicos que diagnosticam cálculos biliares assintomáticos são confrontados com a decisão: remover imediatamente a vesícula biliar para evitar possíveis complicações com risco de vida ou adiar a cirurgia até que as complicações ocorram. Qual é a tendência de longo prazo de cada estratégia?

Na ausência de um estudo clínico, a análise da Cadeia de Markov que descreve o comportamento desta situação é muitas vezes a única forma eficaz de avaliar os riscos e benefícios das diversas estratégias de tratamento médico. Cadeias de Markov podem ser usadas para modelar este cenário.

Suponha que, na muito simplificada a estratégia de adiar a cirurgia, o paciente vai continuar a ter cálculos biliares assintomáticos, estado \(A\), num período de 4 meses para o próximo com probabilidade 0.95. Uma das duas principais complicações, estado \(C\), colecistite ou complicações biliares, podem surgir necessitando de cirurgia, com probabilidade de 0.04. Por causa da idade específica do paciente, ele terá probabilidade 0.01 de morte natural, estado \(D\).

Se a doença evoluir e se tornar sintomática, em seguida será realizada a cirurgia, com um risco de morte de 0.005 por possíveis complicações devido a esta. Uma vez bem sucedida a cirurgia realizada, o paciente entra em estado de recuperação, estado \(R\). Noventa por cento dos pacientes passam para o estado bom \(W\), enquanto 9% permanecem no estado de recuperação de cada ano e 1% morrem de causas naturais. Uma vez que um paciente entra no estado bom, ele continua lá até a morte, com probabilidade de 0.99.

A matriz a seguir é a matriz de transição de probabilidades para a estratégia de adiar a cirurgia até que ocorram complicações. \[ \begin{matrix} \begin{matrix} \end{matrix} & \begin{matrix} A \quad & C \quad & \;\; R \quad & \; W \quad & \; D \; \end{matrix} \\ \mathcal{P} \, = \, \begin{matrix} A \\ C \\ R \\ W \\ D \end{matrix} & \begin{pmatrix} \; 0.95 \, & \; 0.04 \; & \; 0 \; & \; 0 \; & \; 0.01 \; \\ \; 0 & 0 & 0.995 & 0 & 0.005 \\ 0 & 0 & 0.09 & 0.90 & 0.01 \\ 0 & 0 & 0 & 0.99 & 0.01 \\ 0 & 0 & 0 & 0 & 1 \end{pmatrix}\cdot \end{matrix} \]

Observemos que o estado \(D\) é absorvente. Uma vez que o paciente chega a este estado é impossível sair. Para entendermos as consequências da estratégia a longo prazo vamos encontrar diversas potências da matriz de transição.

Assim

estados = c("A","C","R","W","D")
G = matrix(c(0.95,0.04,0,0,0.01,0,0,0.995,0,0.005,
                  0,0,0.09,0.90,0.01,0,0,0,0.99,0.01,
                  0,0,0,0,1),
              nrow=5,ncol=5,byrow=T, dimnames=list(estados,estados))
G.biliares = new("markovchain", states=estados, transitionMatrix=G, 
            name="Exemplo 3.6: Gestão de cálculos biliares.")
G.biliares^8

## Exemplo 3.6: Gestão de cálculos biliares.^8 
##  A  5 - dimensional discrete Markov Chain defined by the following states: 
##  A, C, R, W, D 
##  The transition matrix  (by rows)  is defined as follows: 
##           A          C            R         W          D
## A 0.6634204 0.02793349 3.231840e-02 0.2002410 0.07608667
## C 0.0000000 0.00000000 4.759054e-08 0.9274050 0.07259498
## R 0.0000000 0.00000000 4.304672e-09 0.9227447 0.07725531
## W 0.0000000 0.00000000 0.000000e+00 0.9227447 0.07725531
## D 0.0000000 0.00000000 0.000000e+00 0.0000000 1.00000000

G.biliares^32

## Exemplo 3.6: Gestão de cálculos biliares.^32 
##  A  5 - dimensional discrete Markov Chain defined by the following states: 
##  A, C, R, W, D 
##  The transition matrix  (by rows)  is defined as follows: 
##           A           C            R         W         D
## A 0.1937115 0.008156273 9.436618e-03 0.5163179 0.2723777
## C 0.0000000 0.000000000 3.796128e-33 0.7286419 0.2713581
## R 0.0000000 0.000000000 3.433684e-34 0.7249803 0.2750197
## W 0.0000000 0.000000000 0.000000e+00 0.7249803 0.2750197
## D 0.0000000 0.000000000 0.000000e+00 0.0000000 1.0000000

G.biliares^100

## Exemplo 3.6: Gestão de cálculos biliares.^100 
##  A  5 - dimensional discrete Markov Chain defined by the following states: 
##  A, C, R, W, D 
##  The transition matrix  (by rows)  is defined as follows: 
##             A            C             R         W         D
## A 0.005920529 0.0002492854  2.884175e-04 0.3613916 0.6321502
## C 0.000000000 0.0000000000 2.936510e-104 0.3678810 0.6321190
## R 0.000000000 0.0000000000 2.656140e-105 0.3660323 0.6339677
## W 0.000000000 0.0000000000  0.000000e+00 0.3660323 0.6339677
## D 0.000000000 0.0000000000  0.000000e+00 0.0000000 1.0000000

Como este resultado sugere, quando \(\mathcal{P}\) for elevada a potências mais e mais elevadas, o sistema tenderá para o estado absorvente de modo que, com probabilidade 1, os pacientes acabarão por morrer.

Este exemplo sugere as seguintes propriedades de Cadeias de Markov absorventes:

Independentemente do estado original de uma Cadeia de Markov absorvente, em um número finito de etapas a cadeia vai entrar em um estado absorvente e, em seguida, ficar nesse estado,
As potências da matriz de transição chegam mais e cada vez mais perto de alguma matriz especial.
A tendência de longo prazo depende do estado inicial, a alteração do estado inicial pode modificar o resultado final.

A terceira propriedade distingue as cadeias absorventes das cadeias regulares (ver Definição 3.7), onde o resultado final independe do estado inicial. Esta propriedade não é ilustrada no Exemplo 3.6 uma vez que existe apenas um estado absorvente. Em situações onde existam mais do que um estado absorventes esta propriedade é aparente.

3.3.1. Forma canônica

Considere uma Cadeia de Markov arbitrária absorvente. Vamos numerar os estados de modo que os estados transientes venham em primeiro lugar. Se houverem \(r\) estados absorventes e \(t\) estados transientes, a matriz de probabilidades de transição terá a seguinte forma canônica \[ \begin{matrix} \begin{matrix} \end{matrix} & \begin{matrix} Transiente \quad & Absorvente \end{matrix} \\ \mathcal{P} \, = \, \begin{matrix} Transiente \\ Absorvente \end{matrix} & \begin{pmatrix} \qquad Q \qquad & \qquad R \qquad \\ 0 & \mbox{I} \end{pmatrix}\cdot \end{matrix} \] sendo \(\mbox{I}\) uma matriz identidade de ordem \(r\times r\), \(0\) é uma matriz \(r\times t\) de zeros, \(R\) é uma matriz \(t\times r\) diferente de zero e \(Q\) uma matriz \(t\times t\). Escrita a cadeia desta forma temos que os primeiros \(t\) estados são transientes e os últimos \(r\) estados serão absorventes.

Sabemos que \(p^{(n)}_{x,y}\) é a probabilidade do processo estar no estado \(y\) após \(n\) passos, quando iniciou-se no estado \(x\). Um procedimento de álgebra matricial mostra que \(\mathcal{P}^n\) é da forma \[ \begin{matrix} \begin{matrix} \end{matrix} & \begin{matrix} Transiente \quad & Absorvente \end{matrix} \\ \mathcal{P}^{n} \, = \, \begin{matrix} Transiente \\ Absorvente \end{matrix} & \begin{pmatrix} \qquad Q^n \qquad & \qquad R^* \qquad \\ 0 & \mbox{I} \end{pmatrix}\cdot \end{matrix} \] onde \(R^*\) representa a matriz \(t\times r\), no canto superior do lado direito de \(\mathcal{P}^n\).

Esta submatriz pode ser escrita em termos de \(Q\) e \(R\), mas a expressão é complicada e não é necessária neste momento. A forma de \(\mathcal{P}^n\) mostra que as componentes de \(Q^n\) fornecem as probabilidades de passar de um estado transiente inicial a um outro estado transiente após \(n\) passos.

Teorema 3.7: Probabilidade de absorção.

Numa Cadeia de Markov absorvente, a probabilidade de que o processo vai ser absorvido é 1, isto é, \[ \lim_{n\to\infty} Q^n=0 \cdot \]

Demonstração.

Dado que a cadeia é absorvente, de cada estado \(x\) transiente é possível chegar a um estado absorvente. Seja \(m_x\) o número mínimo de passos necessários para atingir um estado absorvente, a partir de \(x\). Seja \(p_x\) a probabilidade de que, a partir de \(x\), o processo não atingirá um estado absorvente em \(m_x\) passos. Então \(p_x <1\).

Seja \(m\) o maior dos \(m_x\) e seja \(p\) o maior dos \(p_x\). A probabilidade de não serem absorvidos em \(m\) passos é inferior ou igual a \(p\), em \(2n\) passos é menor ou igual a \(p^2\), etc. Uma vez que \(p < 1\) estas probabilidades tendem a 0. Dado que a probabilidade de não serem absorvidos em \(n\) passos é monótona decrescente, estas probabilidades também tendem a 0 e, então, \[ \displaystyle \lim_{n\to\infty}Q^n=0\cdot \]

Exemplo 3.7: Continuação do Exemplo 3.6.

Utilizando os comandos R a seguir podemos identificar a forma canônica numa cadeia absorvente.

estados = c("A","C","R","W","D")
Prob.T=matrix(c(0.95,0.04,0,0,0.01,0,0,0.995,0,0.005,
                0,0,0.09,0.90,0.01,0,0,0,0.99,0.01,0,0,0,0,1),
              nrow=5,ncol=5,byrow=T, dimnames=list(estados,estados))
ProbT = new("markovchain", states=estados, transitionMatrix=Prob.T, 
            name="Gestão de cálculos biliares")
ProbT

## Gestão de cálculos biliares 
##  A  5 - dimensional discrete Markov Chain defined by the following states: 
##  A, C, R, W, D 
##  The transition matrix  (by rows)  is defined as follows: 
##      A    C     R    W     D
## A 0.95 0.04 0.000 0.00 0.010
## C 0.00 0.00 0.995 0.00 0.005
## R 0.00 0.00 0.090 0.90 0.010
## W 0.00 0.00 0.000 0.99 0.010
## D 0.00 0.00 0.000 0.00 1.000

canonicForm(ProbT)

## Gestão de cálculos biliares 
##  A  5 - dimensional discrete Markov Chain defined by the following states: 
##  D, A, C, R, W 
##  The transition matrix  (by rows)  is defined as follows: 
##       D    A    C     R    W
## D 1.000 0.00 0.00 0.000 0.00
## A 0.010 0.95 0.04 0.000 0.00
## C 0.005 0.00 0.00 0.995 0.00
## R 0.010 0.00 0.00 0.090 0.90
## W 0.010 0.00 0.00 0.000 0.99

Identificamos então que a matriz de transição entre estados transientes é \[ \begin{matrix} \begin{matrix} \end{matrix} & \begin{matrix} A \quad & C \quad & \;\; R \quad & \; W \; \end{matrix} \\ Q \, = \, \begin{matrix} A \\ C \\ R \\ W \end{matrix} & \begin{pmatrix} \; 0.95 \, & \; 0.04 \; & \; 0.000 \; & \; 0.00 \\ \; 0.00 & 0.00 & 0.995 & 0.00 \\ 0.00 & 0.00 & 0.090 & 0.90 \\ 0.00 & 0.00 & 0.000 & 0.99 \end{pmatrix}\cdot \end{matrix} \]

Elevando a uma potência elevada a forma canônica, podemos verificar a afirmação do Teorema 3.7.

canonicForm(ProbT)^800

## Gestão de cálculos biliares^800 
##  A  5 - dimensional discrete Markov Chain defined by the following states: 
##  D, A, C, R, W 
##  The transition matrix  (by rows)  is defined as follows: 
##           D            A            C            R            W
## D 1.0000000 0.000000e+00 0.000000e+00 0.000000e+00 0.0000000000
## A 0.9996762 1.509678e-18 6.356538e-20 7.354366e-20 0.0003238497
## C 0.9996762 0.000000e+00 0.000000e+00 0.000000e+00 0.0003238497
## R 0.9996778 0.000000e+00 0.000000e+00 0.000000e+00 0.0003222224
## W 0.9996778 0.000000e+00 0.000000e+00 0.000000e+00 0.0003222224

3.3.2. Matriz fundamental

Anteriormente foi obtido que a probabilidade de permanecer em estados transientes numa cadeia absorvente converge a zero, mas a pergunta agora é: Qual seria a probabilidade de permanecer em estados transientes, em tais cadeias, em \(n\) passos finitos? o seguinte teorema fornece essa resposta.

Teorema 3.8: Probabilidade de absorção.

Para uma Cadeia de Markov absorvente a matriz \(\mbox{I}-Q\) tem como inversa \[ (\mbox{I}-Q)^{-1}=\mbox{I}+Q+Q^2+\cdots \cdot \] O elemento \((x,y)\) da matriz \((\mbox{I}-Q)^{-1}\) fornece o número esperado de vezes que a cadeia visita o estado \(y\), uma vez que começa no estado \(x\). O estado inicial é contado se \(x=y\).

Demonstração.

Seja \((\mbox{I}-Q)x=0\), isto é, \(x=Qx\). Então, repetindo \(n\) vezes, vemos que \(x=Q^nx\). Desde \(\displaystyle \lim_{n\to\infty} Q^n=0\), temos \[ \displaystyle \lim_{n\to\infty} Q^nx=0, \] então \(x=0\). Assim, a matriz \((\mbox{I}-Q)^{-1}\) existe. Observemos que \[ (\mbox{I}-Q)(\mbox{I}+Q+Q^2+\cdots+Q^n)=\mbox{I}-Q^{n+1} \cdot \] Então, multiplicando ambos os lados por \((\mbox{I}-Q)^{-1}\) temos \[ \mbox{I}+Q+Q^2+\cdots+Q^n=(\mbox{I}-Q)^{-1}(\mbox{I}-Q^{n+1}) \cdot \] Fazendo \(n\) tender ao infinito temos \[ (\mbox{I}-Q)^{-1}=\mbox{I}+Q+Q^2+\cdots \cdot \]

Sejam \(x\) e \(y\) dois estados transientes fixos. Definamos \(\pmb{1}_y(k)\) uma variável aleatória indicadora igual a 1 se a cadeia está no estado \(y\) após \(k\) passos e 0 caso contrário. Para cada \(k\), esta variável aleatória depende tanto de \(x\) quanto de \(y\). Temos então que \[ P\big(\pmb{1}_y(k)=1\big)=q_{x,y}^k \] e \[ P\big(\pmb{1}_y(k)=0\big)=1-q_{x,y}^k, \] onde \(q_{x,y}^k\) é o \((x,y)\)-ésimo elemento da matriz \(Q^k\). Estas equações valem tambéém para \(k=0\), desde que \(Q^0=\mbox{I}\). Portanto, dado que \(\pmb{1}_y(k)\) assume somente os valores 0 ou 1, \(\mbox{E}\big(\pmb{1}_y(k)\big)=q_{x,y}^k\).

O número esperado de vezes que a cadeia está no estado \(y\), nos primeiros \(n\) passos, uma vez que se inicia no estado \(x\), é claramente \[ \mbox{E}\big(\pmb{1}_y(0)+\pmb{1}_y(1)+\cdots+\pmb{1}_y(n)\big)=q_{x,y}^0+q_{x,y}^1+\cdots+q_{x,y}^n \cdot \] Fazendo então \(n\) tender ao infinito obtemos \[ \mbox{E}\big(\pmb{1}_y(0)+\pmb{1}_y(1)+\cdots\big)=q_{x,y}^0+q_{x,y}^1+\cdots=(\mbox{I}-Q)^{-1}_{x,y} \cdot \]

Definição 3.6: Matriz fundamental.

Para uma Cadeia de Markov absorvente, a matriz \(\mbox{I}-Q\) é chamada de matriz fundamental. Os elementos de \(\mbox{I}-Q)^{-1}_{x,y}\) fornecem o número esperado de vezes que o processo está no estado transiente \(y\) se for iniciado o processo no estado transiente \(x\).

Exemplo 3.8: Continuação do Exemplo 3.7.

No exemplo do andar do bêbado, a matriz de transição na forma canônica é: \[ \begin{matrix} & \\ \mathcal{P} = \begin{matrix} 1 \\ 2 \\ 3 \\ 0 \\ 4 \end{matrix} \left( \vphantom{ \begin{matrix} 12 \\ 12 \\ 12 \\ 12 \\ 12 \end{matrix} } \right. \end{matrix} \hspace{-1.2em} \begin{matrix} 1 & 2 & 3 & 0 & 4 \\ 0 & 1/2 & 0 & 1/2 & 0 \\ 1/2 & 0 & 1/2 & 0 & 0 \\ 0 & 1/2 & 0 & 0 & 1/2 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \end{matrix} \hspace{-0.2em} \begin{matrix} & \\ \left. \vphantom{ \begin{matrix} 12 \\ 12 \\ 12 \\ 12 \\ 12 \end{matrix} } \right)\cdot \end{matrix} \] da qual vemos que a matriz \(Q\) é \[ Q=\begin{pmatrix} 0 & 1/2 & 0 \\ 1/2 & 0 & 1/2 \\ 0 & 1/2 & 0 \end{pmatrix}, \] e que \[ \mbox{I}-Q=\begin{pmatrix} 1 & -1/2 & 0 \\ -1/2 & 1 & -1/2 \\ 0 & -1/2 & 1 \end{pmatrix}\cdot \]

Calculando \(\mbox{I}-Q)^{-1}\), obtemos \[ \begin{matrix} \begin{matrix} \end{matrix} & \begin{matrix} 1 \; & \; 2 \; & \;\; 3 \end{matrix} \\ (\mbox{I}-Q)^{-1} \, = \, \begin{matrix} 1 \\ 2 \\ 3 \end{matrix} & \begin{pmatrix} \; 3/2 \, & \; 1 \; & \; 1/2 \\ 1 & 2 & 1 \\ 1/2 & 1 & 3/2 \end{pmatrix}\cdot \end{matrix} \]

A partir da linha do meio de \(\mbox{I}-Q)^{-1}\) vemos que, se a cadeia inicia-se no estado 2, o número esperado de visitas aos estados 1, 2 e 3 antes de ser absorvido é 1, 2 e 1, respectivamente.

3.4. Cadeias regulares

Esta é mais uma situação de cadeias na qual não exitem estados transientes.

Definição 3.7: Cadeia de Markov regular.

Uma Cadeia de Markov é chamada uma cadeia regular, se alguma potencia da matriz de transição tem apenas elementos positivos.

Em outras palavras, numa cadeia regular, para algum \(n\) é possível ir de qualquer estado para qualquer estado em exatamente \(n\) passos. Fica claro a partir desta definição que, cada cadeia regular é ergódica. Por outro lado, uma cadeia ergódica não é necessariamente regular, como mostram os seguintes exemplos.

Exemplo 3.9.

Considere uma Cadeia de Markov com matriz de transição definida por \[ \begin{matrix} \begin{matrix} \end{matrix} & \begin{matrix} 0 & 1 \end{matrix} \\ \mathcal{P} \, = \, \begin{matrix} 0 \\ 1 \end{matrix} & \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}\cdot \end{matrix} \]

Então, fica claro que é possível mover-se a partir de qualquer estado para qualquer estado, de modo que a cadeia é ergódica. No entanto, se \(n\) for ímpar, não será possível passar do estado 0 ao estado 0 em \(n\) passos e, se \(n\) for par, não será possível passar do estado 0 ao estado 1 em \(n\) passos, pelo que a cadeia não é regular.

Por exemplo:

estados = c("0","1")
Exemplo = matrix(c(0,1,1,0), nrow=2, ncol=2, byrow=T, 
                 dimnames=list(estados,estados))
Exemplo = new("markovchain", states=estados, transitionMatrix = Exemplo, 
            name="Exemplo 3.9: Cadeia ergódica mas não regular.")
Exemplo^101

## Exemplo 3.9: Cadeia ergódica mas não regular.^101 
##  A  2 - dimensional discrete Markov Chain defined by the following states: 
##  0, 1 
##  The transition matrix  (by rows)  is defined as follows: 
##   0 1
## 0 0 1
## 1 1 0

Exemplo^100

## Exemplo 3.9: Cadeia ergódica mas não regular.^100 
##  A  2 - dimensional discrete Markov Chain defined by the following states: 
##  0, 1 
##  The transition matrix  (by rows)  is defined as follows: 
##   0 1
## 0 1 0
## 1 0 1

Um exemplo mais interessante do que este de Cadeia de Markov não regular ergódica é fornecido pelo modelo Ehrenfest.

Exemplo 3.10.

Lembremos que no modelo de urna Ehrenfest, no Exemplo 1.8, a matriz de transição para este exemplo é: \[ \begin{matrix} \begin{matrix} \end{matrix} & \begin{matrix} 0 & 1 \, & 2 \, & 3 \, & 4 \end{matrix} \\ \mathcal{P} \, = \, \begin{matrix} 0 \\ 1 \\ 2 \\ 3 \\ 4 \end{matrix} & \begin{pmatrix} 0 & 1 & 0 & 0 & 0 \\ \frac{1}{4} & 0 & \frac{3}{4} & 0 & 0 \\ 0 & \frac{1}{2} & 0 & \frac{1}{2} & 0 \\ 0 & 0 & \frac{3}{4} & 0 & \frac{1}{4} \\ 0 & 0 & 0 & 1 & 0 \end{pmatrix}\cdot \end{matrix} \]

Nesta situação, se iniciarmos no estado 0 iremos, depois de qualquer número par de passos, estarmos nos estados 0, 2 ou 4 e depois de qualquer número ímpar de etapas estaremos nos estados 1 ou 3. Assim, esta cadeia é ergódica, mas não regular. Isto pode ser observado nas potências 100 e 101 da matriz de transição, as quais assumem os valores:

estados = c("0","1","2","3","4")
Ehrenfest = matrix(c(0,1,0,0,0,1/4,0,3/4,0,0,
                     0,1/2,0,1/2,0,0,0,3/4,0,1/4,
                     0,0,0,1,0), nrow=5, ncol=5, byrow=T, 
                 dimnames=list(estados,estados))
Ehrenfest = new("markovchain", states=estados, transitionMatrix = Ehrenfest, 
            name="Exemplo 3.10: Cadeia de Ehrenfest.")
Ehrenfest^100

## Exemplo 3.10: Cadeia de Ehrenfest.^100 
##  A  5 - dimensional discrete Markov Chain defined by the following states: 
##  0, 1, 2, 3, 4 
##  The transition matrix  (by rows)  is defined as follows: 
##       0   1    2   3     4
## 0 0.125 0.0 0.75 0.0 0.125
## 1 0.000 0.5 0.00 0.5 0.000
## 2 0.125 0.0 0.75 0.0 0.125
## 3 0.000 0.5 0.00 0.5 0.000
## 4 0.125 0.0 0.75 0.0 0.125

Ehrenfest^101

## Exemplo 3.10: Cadeia de Ehrenfest.^101 
##  A  5 - dimensional discrete Markov Chain defined by the following states: 
##  0, 1, 2, 3, 4 
##  The transition matrix  (by rows)  is defined as follows: 
##       0   1    2   3     4
## 0 0.000 0.5 0.00 0.5 0.000
## 1 0.125 0.0 0.75 0.0 0.125
## 2 0.000 0.5 0.00 0.5 0.000
## 3 0.125 0.0 0.75 0.0 0.125
## 4 0.000 0.5 0.00 0.5 0.000

Qualquer matriz de transição que não tem zeros determina uma cadeia de Markov regular. No entanto, é possível que uma Cadeia de Markov regular tenha zeros na matriz de transição. Vejamos o seguinte exemplo.

Exemplo 3.11: Terra de Oz.

De acordo com Kemeny, Snell, and Thompson (1974), a Terra de Oz é um excelente lugar para morar por muitas coisas, mas não por um bom tempo por causa do clima.

Eles nunca tem dois dias agradáveis seguidos. Se eles têm um bom dia \(B\), eles são tão propensos a ter neve \(N\) quanto chuva \(C\) no dia seguinte. Se tiverem neve ou chuva, tem possibilidade meio de ter o mesmo no dia seguinte. Se não houver mudança de neve ou chuva, tem apenas metade de probabilidade de uma mudança para um bom dia.

Com esta informação, formamos a matriz de transição da Cadeia de Markov como segue: \[ \begin{matrix} & \\ \mathcal{P} = \begin{matrix} \mbox{C} \\ \mbox{B} \\ \mbox{N} \end{matrix} \left( \vphantom{ \begin{matrix} 12 \\ 12 \\ 12 \end{matrix} } \right. \end{matrix} \hspace{-1.2em} \begin{matrix} \mbox{C} & \mbox{B} & \mbox{N} \\ \frac{1}{2} & \frac{1}{4} & \frac{1}{4} \\ \frac{1}{2} & 0 & \frac{1}{2} \\ \frac{1}{4} & \frac{1}{4} & \frac{1}{2} \end{matrix} \hspace{-0.2em} \begin{matrix} & \\ \left. \vphantom{ \begin{matrix} 12 \\ 12 \\ 12 \end{matrix} } \right)\cdot \end{matrix} \]

Podemos observar que esta matriz de transição tem \(p_{B,B}=0\), mas \(\mathcal{P}^2\) não tem zeros, então esta é uma Cadeia de Markov regular

estados = c("C","B","N")
Oz = matrix(c(1/2,1/4,1/4,1/2,0,1/2,1/4,1/4,1/2),
              nrow=3, ncol=3, byrow=T, 
              dimnames=list(estados,estados))
Oz = new("markovchain", states=estados, transitionMatrix = Oz,
         name="Exemplo 3.11: Terra de Oz.")
Oz^2

## Exemplo 3.11: Terra de Oz.^2 
##  A  3 - dimensional discrete Markov Chain defined by the following states: 
##  C, B, N 
##  The transition matrix  (by rows)  is defined as follows: 
##        C      B      N
## C 0.4375 0.1875 0.3750
## B 0.3750 0.2500 0.3750
## N 0.3750 0.1875 0.4375

Exemplos de cadeias não regulares são as cadeias absorventes. Por exemplo, seja \[ \mathcal{P} = \begin{pmatrix} 1 & 0 \\ \frac{1}{2} & \frac{1}{2} \end{pmatrix} \] a matriz de transição de uma Cadeia de Markov. Todas as potências de \(\mathcal{P}\) terão um 0 no canto superior direito. Vamos agora discutir dois teoremas importantes relacionados às cadeias regulares.

Primeiro demonstremos um teorema auxiliar.

Teorema 3.9.

Seja \(\mathcal{P}\) uma matriz de transição de ordem \(r\) com elementos positivos. Seja \(\epsilon\) o menor valor de \(\mathcal{P}\). Seja \(\pmb{x}\) qualquer vetor coluna de dimensão \(r\), sendo \(M_0\) o máximo e \(m_0\) o mínimo de suas componentes. Sejam agora \(M_1\) e \(m_1\) os valores máximo e mínimo respectivos das componentes do vetor \(\mathcal{P}\pmb{x}\). Então \(M_1\leq M_0\), \(m_1\geq m_0\) e \[ M_1-m_1\leq (1-2\epsilon)(M_0-m_0)\cdot \]

Demonstração.

Seja \(\pmb{x}'\) o vetor obtido de \(x\) substituindo uma das componentes \(m_0\) por \(M_0\). Então \(\pmb{x}\leq \pmb{x}'\). Cada componente de \(\Gamma \pmb{x}'\) é da forma \[ a\cdot m_0+(1-a)\cdot M_0=M_0-a(M_0-m_0), \] onde \(a\geq \epsilon\). Assim, cada componente de \(\mathcal{P} \pmb{x}'\) é menor ou igual do que \[ M_0-\epsilon(M_0-m_0)\cdot \] Dado que \(\pmb{x}\leq \pmb{x}'\), temos que \[ M_1\leq M_0-\epsilon(M_0-m_0)\cdot \] Aplicando este resultado ao vetor \(-\pmb{x}\) obtemos que \[ -m_1\leq -m_0-\epsilon(-m_0+M_0)\cdot \] Somando os resultados anteriores, temos que \[ \begin{array}{rcl} M_1-m_1 & \leq & M_0-m_0-2\epsilon(M_0-m_0) \\[0.8em] & = & (1-2\epsilon)(M_0-m_0) \cdot \end{array} \]

Devemos observar que \(\epsilon\), o menor valor de \(\mathcal{P}\), é sempre menor ou igual a 1/2. Este teorema nos fornece uma forma mais simples da demonstração do seguinte teorema fundamental para Cadeias de Markov regulares.

Teorema 3.10: Teorema fundamental.

Seja \(\mathcal{P}\) a matriz de transição de uma Cadeia de Markov regular. Então, \[ \lim_{n\to\infty} \mathcal{P}^n=W, \] onde \(W\) é uma matriz com todas as linhas iguais ao mesmo vetor \(w\). O vector \(w\) é um vector de probabilidades estritamente positivo, isto é, as componentes são todas positivas e somam um.

Demonstração.

Primeiro vamos assumir que a matriz \(\Gamma\) não tem zeros. Seja \(\epsilon\) o menor valor em \(\mathcal{P}\). Seja agora \(\rho_j\) um vetor coluna com 1 na \(j\)-ésima componente e zeros nas outras. Sejam \(M_n\) e \(m_n\) os valores máximos e mínimos dos vetores \(\mathcal{P}^n\rho_j\). Dado que \(\Gamma^n\rho_j=\Gamma\cdot \Gamma^{n-1}\rho_j\), temos do Teorema 3.9 que \(M_1\geq M_2\geq M_3\geq \cdots\), \(m_1\leq m_2\leq m_3\leq \cdots\) e \[ M_n-m_n\leq (1-2\epsilon)(M_{n-1}-m_{n-1}), \] para \(n\geq 1\). Fazendo \(d_n=M_n-m_n\) este resultado nos disse que \[ d_n\leq (1-2\epsilon)^n d_0\cdot \] Logo \(\lim_{n\to\infty} d_n=0\) e então, \(M_n\) e \(m_n\) tem limite comum. Portanto, \(\mathcal{P}^n\rho_j\) tende a um vetor com todas as componentes iguais.

Seja \(\alpha_j\) este valor comum. Logicamente, para todo \(n\), \(m_n\leq \alpha_j\leq M_n\). Em particular, dado que \(0 \leq m_1\) e \(M_1\leq 1\), temos que \(0 \leq \alpha_j\leq 1\). Agora \(\mathcal{P}^n\rho_j\) é a \(j\)-ésima coluna de \(\Gamma^n\). Então, a \(j\)-ésima coluna de \(\Gamma^n\) tende a um vetor com todas as componentes iguais a \(w_j\). Isto é, \(\mathcal{P}^n\) tende a uma matriz \(W\) com todas as linhas iguais ao vetor \(\pmb{w}=(w_1,w_2,\cdots,w_r)\). Dado que as somas das linhas de \(\mathcal{P}^n\) são sempre 1, o mesmo vale para o limite. Isto completa a demonstração no caso da matriz assumir somente valores positivos.

Considerar agora o caso seguinte em que \(\mathcal{P}\) somente seja assumida ser regular. Seja \(N\), tal que \(\mathcal{P}^N\) tenha somente valores positivos e aplicamos a primeira parte da demonstração à matriz \(\mathcal{P}^N\).

Queremos mostrar que a potência \(\mathcal{P}^n\) de uma matriz de transição regular, isto é, que a matriz de probabilidades de transição de uma cadeia regular tende a uma matriz com todas as linhas da mesma forma. Significa o mesmo de mostrar que \(\mathcal{P}^n\) converge a uma matriz com colunas constantes. Agora, a \(j\)-ésima coluna de \(\mathcal{P}^n\) é \(\mathcal{P}^n \rho_j\), onde \(\rho_j\) é um vetor coluna com 1 na \(j\)-ésima linha e 0 nas outras. Assim, precisamos apenas mostrar que para qualquer vetor coluna \(\pmb{\rho}\), \(\mathcal{P}^n \pmb{\rho}\) se aproxima de um vetor constante, quando \(n\) tende ao infinito.

Uma vez que cada linha de \(\mathcal{P}\) é um vector de probabilidades, \(\mathcal{P}\pmb{\rho}\) substitui \(\pmb{\rho}\) pelas médias dos seus componentes. Aqui está um exemplo: \[ \begin{pmatrix} 1/2 & 1/4 & 1/4 \\ 1/3 & 1/3 & 1/3 \\ 1/3 & 1/2 & 1/6 \end{pmatrix} \begin{pmatrix} 1 \\ 2 \\ 3 \end{pmatrix} = \begin{pmatrix} 1/2\cdot 1 + 1/4\cdot 2 + 1/4\cdot 3 \\ 1/3\cdot 1 + 1/3\cdot 2 + 1/3\cdot 3 \\ 1/3\cdot 1 + 1/2\cdot 2 + 1/6\cdot 3 \end{pmatrix} = \begin{pmatrix} 7/4 \\ 2 \\ 11/6 \end{pmatrix}\cdot \]

O resultado do processo de cálculo da média faz as componentes de \(\mathcal{P}\pmb{\rho}\) mais semelhantes do que as de \(\pmb{\rho}\). Em particular, os máximos decrescem de 3 para 2 e os mínimos aumentos de 1 a 11/6. Na prova mostramos que, como nós fazemos mais e mais desta média para obter \(\mathcal{P}^n\pmb{\rho}\), a diferença entre o máximo e mínimo tende a 0 quando \(n\to\infty\). Isto significa que \(\mathcal{P}^n\pmb{\rho}\) tende a um vetor constante.

O elemento \((i,j)\) de \(\mathcal{P}^n\), \(p_{i,j}^{(n)}\) é a probabilidade de que o processo esteja no estado \(j\) após \(n\) passos se inicia-se no estado \(i\). Se denotamos a linha comum de \(W\) por \(w\), então o Teorema 3.10 afirma que, a probabilidade da cadeia estar no estado \(j\) a longo prazo é de aproximadamente \(w_j\), a \(j\)-ésima componente de \(w\) e é independente do estado inicial.

Exemplo 3.12.

Lembre-se do exemplo da Terra de Oz, o Exemplo 3.10. A potência sexta da matriz de transição \(\mathcal{P}\) é, com três casas decimais, \[ \begin{matrix} & \\ \mathcal{P}^6 = \begin{matrix} \mbox{C} \\ \mbox{B} \\ \mbox{N} \end{matrix} \left( \vphantom{ \begin{matrix} 12 \\ 12 \\ 12 \end{matrix} } \right. \end{matrix} \hspace{-1.2em} \begin{matrix} \mbox{C} & \mbox{B} & \mbox{N} \\ 0.4 & 0.2 & 0.4 \\ 0.4 & 0.2 & 0.4 \\ 0.4 & 0.2 & 0.4 \end{matrix} \hspace{-0.2em} \begin{matrix} & \\ \left. \vphantom{ \begin{matrix} 12 \\ 12 \\ 12 \end{matrix} } \right)\cdot \end{matrix} \]

Assim, para este grau de precisão, a probabilidade de chuva seis dias depois de um dia de chuva é a mesma que a probabilidade de chuva seis dias depois de um dia agradável ou seis dias depois de um dia de neve. O Teorema 3.10 prevê que, para grandes valores de \(n\), as linhas de \(\mathcal{P}^n\) vão se aproximar de um vetor comum. É interessante que isso ocorra tão cedo neste exemplo.

Teorema 3.11.

Seja \(\mathcal{P}\) a matriz de transição de uma Cadeia de Markov regular, seja \[ W=\lim_{n\to\infty} \mathcal{P}^n, \] com componentes comuns \(\pmb{w}\) e seja \(\pmb{x}\) um vetor coluna com todas as componentes iguais a 1. Então

\(\pmb{w}\mathcal{P}=\pmb{w}\) e qualquer vetor linha \(\pmb{\nu}\) tal que \(\pmb{\nu}\mathcal{P}=\pmb{\nu}\), é múltiplo de \(\pmb{w}\).
\(\mathcal{P} c=c\) e qualquer vetor coluna \(\pmb{x}\) tal que \(\mathcal{P} \pmb{x}=\pmb{x}\), é múltiplo de \(c\).

Demonstração.

Note-se que uma consequência imediata deste teorema é o fato de que existe apenas um único vetor de probabilidades \(\nu\), tal que a \(\nu\mathcal{P}=\nu\).

3.5. Cadeias ergódicas

Lembremos as definições básicas relevantes para uma cadeia absorvente. Na classificação dos estados, as classes de equivalência foram divididas em conjuntos transitórios e ergódicos. Os primeiros, uma vez deixados, nunca mais são inseridos; enquanto os últimos, uma vez inseridos, nunca mais são deixados. Se um estado é o único elemento de um conjunto ergódico, é chamado estado absorvente. Para esse estado \(s_i\), a entrada \(p_ii\) deve ser 1 e, portanto, todas as outras entradas nesta linha da matriz de transição são 0.

Uma cadeia, todos cujos estados não transitórios estão absorvendo, é chamada de cadeia absorvente. Essas cadeias nos ocuparão no presente capítulo.

Vamos agora generalizar os resultados obtidos na última seção. Lá eles foram provados para as cadeias regulares e agora vamos estende-los a uma cadeia arbitrária que consiste em um conjunto único ergódico, ou seja, a uma cadeia ergódica. Sabemos que essa cadeia deve ser regulares ou cíclicas. Uma cadeia cíclica consiste de \(d\) cíclos e uma cadeia regular pode ser pensado como o caso especial em que \(d = 1\). Os resultados a serem obtidos serão generalizações dos resultados anteriores no sentido de que se escolhemos \(d = 1\) neles , obtemos os resultados da seção anterior. Por uma questão de fato, na maior parte dos resultados d não vai, aparece explicitamente, para que o resultado of the capítulo anterior será mostrado para conter para todas as cadeias ergódicas.

Uma cadeia ergodic é caracterizada pelo facto de que consiste de uma única classe ergodic, isto é, é possível ir de cada estado de todos os outros estados. No entanto, se d> 1, então tal transição é possível apenas para valores de n especiais. Assim, nenhum poder da P é positiva, e diferentes poderes terá zeros em posições diferentes, esses zeros mudar ciclicamente para os poderes. Assim pn não pode convergir. Esta é a diferença mais importante entre as cadeias cíclicas e regulares.

Mas, enquanto os poderes falhar a convergir, temos o seguinte mais fraca resultado. Um segundo tipo importante da Cadeia de Markov que vamos estudar em detalhe são as chamadas cadeias ergódicas ou irredutíveis. Esta é uma situação na qual não existem estados transientes.

Agora vamos generalizar os resultados obtidos no último capítulo. Lá eles foram provados para cadeias regulares, e agora nós os estenderemos a uma cadeia arbitrária que consiste em um único conjunto ergódico, isto é, a uma cadeia ergódica. Sabemos que essa cadeia deve ser regular ou cíclica. Uma cadeia cíclica consiste em d classes cíclicas, e uma cadeia regular pode ser considerada o caso especial em que d = 1. Os resultados a serem obtidos serão generalizações dos resultados anteriores, no sentido de que se definirmos d = 1 nelas , obtemos um resultado do capítulo anterior. De fato, na maioria das os resultados d não “, aparecem explicitamente, de modo que o resultado do capítulo anterior será mostrado para todas as cadeias ergódicas.

Uma cadeia ergódica é caracterizada pelo fato de consistir em uma única classe ergódica, ou seja, é possível ir de todos os estados para todos os outros estados. No entanto, se d> 1, a transição simples é possível apenas para valores n especiais. Portanto, nenhuma potência de P é positiva, e potências diferentes terão zeros em posições diferentes, esses zeros mudando ciclicamente para as potências. Portanto, pn não pode convergir. Essa é a diferença mais importante entre cadeias cíclicas e regulares. Mas enquanto os poderes falham em convergir, temos o seguinte resultado mais fraco.

Teorema 3.12.

Em qualquer Cadeia de Markov finita, não importa onde o processo comece, a probabilidade após \(n\) etapas de o processo estar em um estado ergódico tende a 1 quando \(n\) tende ao infinito.

Demonstração.

Se o processo atingir um estado ergódico, ele poderá nunca deixe sua classe de equivalência e, portanto, em todas as etapas futuras em um estado ergódico. Suponha que ele comece em um estado transitório. Está classe de equivalência não é mínima; portanto, há um elemento mínimo abaixo dele. Isso significa que deve ser possível alcançar um conjunto ergódico. Suponhamos que, a partir de qualquer estado transitório, seja possível alcançar um O estado ergódico não passa de passos. (Como existe apenas um número finito dos estados, n é simplesmente o máximo do número de etapas necessárias de cada estado.) Portanto, existe um número positivo p tal que a probabilidade de entrar em um estado ergódico em no máximo n etapas é pelo menos p, de qualquer estado transitório. Daí a probabilidade de não atingir um ergódico O estado em n etapas é no máximo (1 - p), que é menor que 1. A probabilidade de não atingir um estado ergódico em etapas kn é menor ou igual a (1 - P) A ;, e essa probabilidade tende a ° à medida que k aumenta. Portanto, o teorema segue.

3.6. Exercícios

Mostrar que se o estado \(x\) é recorrente e não se comunica com o estado \(y\), então \(p_{x,y}=0\).
Prove que, se o número de estados em uma Cadeia de Markov é \(M\) e, se o estado \(j\) pode ser alcançado a partir do estado \(i\), então ele pode ser alcançado em, no máximo, \(M\) etapas.
Mostre que se o estado \(x\) se comunica com \(y\) e \(y\) se comunica com \(z\), então \(x\) se comunica com \(z\).
Considere uma Caceia de Markov com espaço de estados \(\{1,2,\cdots,9\}\) e matriz de probabilidades de transição \[ \mathcal{P} = \begin{pmatrix} 0.0 & 0.5 & 0.0 & 0.0 & 0.5 & 0.0 & 0.0 & 0.0 & 0.0 \\ 0.0 & 0.0 & 1.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 \\ 0.0 & 0.0 & 0.0 & 1.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 \\ 1.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 \\ 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 1.0 & 0.0 & 0.0 & 0.0 \\ 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 1.0 & 0.0 & 0.0 \\ 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 1.0 & 0.0 \\ 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 1.0 \\ 1.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 \end{pmatrix}\cdot \] Esta cadeia é irredutível? ou seja, prove que o conjunto de estados irredutíveis \(F\) satisfaz \(F=S\), sendo \(S=\{1,\cdots,9\}\). Prove também que esta cadeia é recorrente, ou seja, prove que cada estado em \(S\) é recorrente.
Considere uma cadeia de Markov nos números inteiros não negativos de modo que, começando no estado \(x\), a cadeia passe ao estado \(x+1\) com probabilidade \(p\), \(0 < p < 1\) e vá para o estado \(0\) com probabilidade \(1-p\).

Mostre que essa cadeia é irredutível.
Encontre \(P_0(T_0=n)\), \(n\geq 1\).
Mostre que esta cadeia é recorrente.

O Fiscal de Mídia identificou seis estados associados à televisão: 0 (nunca assiste TV), 1 (assiste apenas notícias), 2 (assiste TV com bastante frequência), 3 (viciado), 4 (em modificação de comportamento), 5 (morte encefálica). As transições de estado para estado podem ser modeladas como uma cadeia de Markov com a seguinte matriz de transição: \[ \begin{matrix} & \\ \mathcal{P} = \begin{matrix} 0 \\ 1 \\ 2 \\ 3 \\ 4 \\ 5 \end{matrix} \left( \vphantom{ \begin{matrix} 12 \\ 12 \\ 12 \\ 12 \\ 12 \end{matrix} } \right. \end{matrix} \hspace{-1.2em} \begin{matrix} 0 & 1 & 2 & 3 & 4 & 5 \\ 1.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 \\ 0.5 & 0.0 & 0.5 & 0.0 & 0.0 & 0.0 \\ 0.1 & 0.0 & 0.5 & 0.3 & 0.0 & 0.1 \\ 0.0 & 0.0 & 0.0 & 0.7 & 0.1 & 0.2 \\ 1/3 & 0.0 & 0.0 & 1/3 & 1/3 & 0.0 \\ 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 1.0 \end{matrix} \hspace{-0.2em} \begin{matrix} & \\ \left. \vphantom{ \begin{matrix} 12 \\ 12 \\ 12 \\ 12 \\ 12 \end{matrix} } \right)\cdot \end{matrix} \]

Quais estados são recorrentes e quais transientes.
Começando do estado 1, qual é a probabilidade de o estado 5 ser atingido antes do estado 0, ou seja, qual é a probabilidade de um visualizador de notícias acabar com morte cerebral?

Uma certa Cadeia de Markov que surge na genética tem estados \(0,1,\cdots, 2d\) e função de transição \[ p_{x,y} \, = \, {2d \choose y}\left(\dfrac{x}{2d}\right)^y\left(1-\dfrac{x}{2d}\right)^{2d-y}\cdot \] Encontre \(\rho_{0,\{x\}}=P_0(T_{\{x\}} < \infty)\), \(0 \leq x\leq 2d\).

3.7. Bibliografia

Fox, B. L., and D. M. D. M. Landi. 1968. “An Algorithm for Identifying the Ergodic Subchains and Transient States of a Stochastic Matrix.” The RAND Corporation, Santa Monica, California, 619–21.

Glass, D. V. 1954. Social Mobility in Britain. London: Routledge & Kegan Paul Ltd.

Kemeny, J. G., J. L Snell, and G. L. Thompson. 1974. Introduction to Finite Mathematics. Englewood Cliffs, NJ: Prentice-Hall.

Sox, H., M. Blatt, M. Higgins, and K. Marton. 1988. “Medical Decision Making.” Butterworth Publishing, Boston, 191–93.

Cadeias de Markov

2025-06-19

3. Decomposição de \(S\)

3.1. Classificando os estados

3.1.1. O algoritmo de decomposição

3.2. Probabilidade de absorção

3.3. Cadeias absorventes

3.3.1. Forma canônica

3.3.2. Matriz fundamental

3.4. Cadeias regulares

3.5. Cadeias ergódicas

3.6. Exercícios

3.7. Bibliografia