Começando o estudo de tais sistemas, podemos perceber que a propriedade de Markov é muito importante e reduz a probabilidade condicional a uma única
transição, como pode ser observado na Definição 2. Isso permitirá encontrar propriedades estudando o conceito de probabilidade de transição.
Definição I.1 (Probabilidade de transição).
Seja \(\{C_t \, : \, t\in \mathbb{N}\}\) uma Cadeia de Markov com espaço de estados \(S\) e sejam \(x,y\in S\). A probabilidade
\begin{equation}
P(C_{t+1}=y \, | \, C_t=x),
\end{equation}
se conhece como probabilidade de transição em um passo ou simplesmente probabilidade de transição. Também denotada como \(p_{x,y}(t,t+1)\),
a qual representa a probabilidade de transição do estado \(x\) no tempo \(t\) ao estado \(y\) no tempo \(t+1\).
Podemos encontrar processos nos quais as probabilidades de transição variam com o tempo e, portanto, necessitam ser explicitamente escritas como uma função do
tempo \(t\), por exemplo, \(p_{x,y}(t)\), mas não consideraremos tais processos no presente texto e doravante, presume-se que a probabilidade de transição é
independente do tempo.
Definição I.2 (Cadeia de Markov homogênea).
Uma Cadeia de Markov \(\{C_t \, : \, t\in \mathbb{N}\}\) é dita ser homogênea ou estacionária se as probabilidades de transição \(p_{x,y}(t)\) não
dependem do tempo.
Desta maneira, no caso de Cadeias de Markov estacionárias, a probabilidade de transição em \(p_{x,y}(t)\) se reduz a
\begin{equation}
P(C_{t+1}=y \, | \, C_t=x) \, = \, P(C_1=y \, | \, C_0=x),
\end{equation}
e, portanto, em \(p_{x,y}(t,t+1)\) não faz mais sentido escrever o instante de observação da cadeia, a qual se reduz a simplesmente \(p_{x,y}\) ou, como
comentado acima, a probabilidade de transição é independente do tempo. Cadeias de Markov homogêneas ou estacionárias serão nosso objeto de
estudo neste artigo.
Exemplo I.1: Cadeia com dois estados.
Uma Cadeia de Markov com dois estados é um processo de Markov para um sistema que pode assumir somente dois valores, por exemplo, 0 e 1. Podemos observar um gráafico
representativo na Figura I.1. Partindo do estado 0, permanece nele com probabilidade \(1-\alpha\) e assume valor 1 com probabilidade \(\alpha\). Da mesma forma, se o estado atual
é 1, permanece nele com probabilidade \(1-\beta\) e muda para 0 com probabilidade \(\beta\).
Figura I.1: Grafo das probabilidades de transição na cadeia com dois estados.
Para um exemplo de uma Cadeia de Markov tendo dois estados considere uma máquina que, no início de um dia em particular será classificada como em perfeitas
condições ou com falhas de operação. Suponhamos que, se a máquina for classificada no início do dia \(n\) com falhas, com probabilidade
\(\alpha\) vai ser reparada com êxito e estará em condições de funcionamento no início do \((n+1)\)-ésimo dia. Considere-se também
que, se a máquina está em perfeitas condições de funcionamento, no início do dia \(n\), com probabilidade \(\beta\) vai ter uma falha causando
mau funcionamento e será classificada assim, no início da \((n+1)\)-ésimo dia. Finalmente, seja \(\pi_0(0)\) a probabilidade de que a máquina esteja
com falhas de funcionamento inicialmente, isto é, no início do dia 0.
Seja 0 estado que corresponde à máquina com falhas de funcionamento e seja 1 o estado que corresponde à máquina em perfeitas condições de
funcionamento. Seja \(C_n\) a variável aleatória denotando o estado da máquina no tempo \(n\). De acordo com a descrição acima
\begin{equation}
P(C_{n+1}=1 \, | \, C_n=0) \, = \, \alpha, \qquad \qquad \qquad P(C_{n+1}=0 \, | \, C_n=1) \, = \, \beta,
\end{equation}
e
\begin{equation}
P(C_0=0) \, = \, \pi_0(0)\cdot
\end{equation}
Dado que há somente dois estados 0 e 1, segue que
\begin{array}{c}
P(C_{n+1}=0 \, | \, C_n=0) \, = \, 1-\alpha, \\
P(C_{n+1}=1 \, | \, C_n=1) \, = \, 1-\beta,
\end{array}
e que a probabilidade \(\pi_0(1)\), de estar inicialmente no estado 1 é dada por
\begin{equation}
\pi_0(1) \, = \, P(C_0=1) \, = \, 1-\pi_0(0)\cdot
\end{equation}
Vamos escrever a função de probabilidade de \(C_n\) em função da distribuição inicial. Com esse objetivo escrevemos que \(P(C_0 = 0) = \pi_0(0)\),
então
\begin{equation}
P(C_1=0) \, = \, (1-\alpha-\beta)\pi_0(0) \, + \, \beta\cdot
\end{equation}
No caso trivial de \(\alpha=\beta= 0\) é claro que para todo \(n\)
\begin{equation}
P(C_n=0) \, = \, \pi_0(0) \qquad \text{e} \qquad P(C_n=1) \, = \, \pi_0(1)\cdot
\end{equation}
Suponhamos agora que \(\alpha+\beta > 0\). Então, pela fórmula da soma de uma progressão geométrica,
\begin{equation}
\sum_{k=0}^{n-1} (1-\alpha-\beta)^k \, = \, \dfrac{1-(1-\alpha-\beta)^k}{\alpha+\beta}\cdot
\end{equation}
Concluímos que
\begin{equation}
P(C_n=0) \, = \, \dfrac{\beta}{\alpha+\beta}+(1-\alpha+\beta)^n\left( \pi_0(0)-\dfrac{\beta}{\alpha+\beta}\right),
\end{equation}
por consequência que
\begin{equation}
P(C_n=1) \, = \, \dfrac{\alpha}{\alpha+\beta}+(1-\alpha+\beta)^n\left( \pi_0(1)-\dfrac{\alpha}{\alpha+\beta}\right)\cdot
\end{equation}
Suponha agora \(\alpha\) e \(\beta\) não sejam ambas zero nem ambas um. Então, \(0 < \alpha+\beta < 2\), o qual implica que
\begin{equation}
|1-\alpha-\beta| < 1\cdot
\end{equation}
Neste caso, podemos fazer \(n\to\infty\) nas expressões acima e concluímos que
\begin{equation}
\lim_{n\to\infty} P(C_n=0) \, = \, \dfrac{\beta}{\alpha+\beta} \qquad \mbox{e} \qquad \lim_{n\to\infty} P(C_n=1) \, = \, \dfrac{\alpha}{\alpha+\beta}\cdot
\end{equation}
Podemos também encontrar as probabilidades limite \(\beta/(\alpha+\beta)\) e \(\alpha/(\alpha+\beta)\) por um procedimento diferente. Suponha que queremos escolher \(\pi_0(0)\) e
\(\pi_0(1)\) de maneira que \(P(C_n=0)\) e \(P(C_n=1)\) não dependam de \(n\). Das expressões respectivas acima percebemos que, para obtermos isso, devemos escolher
\begin{equation}
\pi_0(0) \, = \, \dfrac{\beta}{\alpha+\beta} \qquad \mbox{e} \qquad \pi_0(1) \, = \, \dfrac{\alpha}{\alpha+\beta}\cdot
\end{equation}
Então, se a cadeia \(\{C_n\}\) tiver como distribuição inicial
\begin{equation}
P(C_0=0) \, = \, \dfrac{\beta}{\alpha+\beta} \qquad \mbox{e} \qquad P(C_0=1) \, = \, \dfrac{\alpha}{\alpha+\beta},
\end{equation}
temos, para todo \(n\), que
\begin{equation}
P(C_n=0) \, = \, \dfrac{\beta}{\alpha+\beta} \qquad \mbox{e} \qquad P(C_n=1) \, = \, \dfrac{\alpha}{\alpha+\beta}\cdot
\end{equation}
A descrição do processo é vaga porque ela realmente não disse quando \(\{C_n\}\) satisfaz a propriedade de Markov. Suponhamos, porém, que a
propriedade de Markov se sustenta. Podemos usar essa informação adicional para calcular a distribuição conjunta de \(C_0,C_1,\cdots,C_n\).
Por exemplo, seja \(n=2\) e sejam \(c_{_0},c_{_1},c_{_2}\) os valores observados da cadeia, cada um sendo igual a 0 ou 1. Então,
\begin{array}{rcl}
P(C_0=c_{_0}, C_1=c_{_1}, C_2=c_{_2}) & = & P(C_0=c_{_0}, C_1=c_{_1})P(C_2=c_{_2} \, | \, C_0=c_{_0}, C_1=c_{_1}) \\
& = & P(C_0=c_{_0})P(C_1=c_{_1} \, | \, C_0=c_{_0})P(C_2=c_{_2} \, | \, C_0=c_{_0}, C_1=c_{_1})\cdot
\end{array}
Agora, as probabilidades \(P(C_0=c_{_0}\) e \(P(C_1=c_{_1} \, | \, C_0=c_{_0})\) são determinadas por \(\alpha\), \(\beta\) e \(\pi_0(0)\) só que, sem a propriedade de
Markov valendo não podemos expressar \(P(C_2=c_{_2} \, | \, C_0=c_{_0}, C_1=c_{_1})\) em termos de \(\alpha\), \(\beta\) e \(\pi_0(0)\). Se a propriedade de Markov é satisfeita,
contudo, então
\begin{equation}
P(C_2=c_{_2} \, | \, C_0=c_{_0}, C_1=c_{_1}) \, = \, P(C_2=c_{_2} \, | \, C_1=c_{_1}),
\end{equation}
a qual é determinada por \(\alpha\), \(\beta\) e \(\pi_0(0)\). Neste caso
\begin{equation}
P(C_0=c_{_0}, C_1=c_{_1}, C_2=c_{_2}) \, = \, P(C_0=c_{_0})P(C_1=c_{_1} \, | \, C_0=c_{_0})P(C_2=c_{_2} \, | \, C_1=c_{_1})\cdot
\end{equation}
Na tabela a seguir apresentamos a distribuição conjunta das variáveis \(C_0,C_1\) e \(C_2\) segundo os valores de \(c_{_0},c_{_1}\) e \(c_{_2}\).
Esta seção dedica-se ao estudo de três características importantes das Cadeias de Markov: a função de transição, a
distribuição inicial e a matriz de transição. Toda vez que lidemos com situações que possam ser modeladas desta maneira, estaremos
interessados em identificar estas características. Mais ainda, estas características serão importantes para encontrar propriedades das Cadeias de Markov.
Função de transição
Pela Definição I.1 podemos perceber que a probabilidade de transição, numa Cadeia de Markov estacionária, é uma função dos
estados e não mais dos instantes de tempo. Dedicaremos especial atenção a esta função, a qual permitirá deduzir propriedades destes modelos.
Definição I.3 (Função de transição).
Seja \(\{C_t \, : \, t\in \mathbb{N}\}\) uma Cadeia de Markov estacionária com espaço de estados \(S\). A função \(p\), definida como
\begin{equation}
p_{x,y} \, = \, P(C_{1}=y \, | \, C_0=x), \qquad x,y\in S,
\end{equation}
é chamada de função de transição da cadeia.
Em particular, dado que a cadeia satisfaz as exigências da Definição I.6, de cadeia estacionária, podemos escrever que
\begin{equation}
P(C_{t+1}=y \, | \, C_t=x) \, = \, p_{x,y}, \qquad t\geq 1\cdot
\end{equation}
Agora, pela propriedade Markoviana, temos que
\begin{equation}
P(C_{t+1}=y \, | \, C_0=c_0,\cdots,C_{t-1}=c_{t-1},C_t=x) \, = \, p_{x,y}\cdot
\end{equation}
Em outras palavras, se a Cadeia de Markov está no estado \(x\) no tempo \(n\), então não importa como ela chegou a \(x\), ela tem probabilidade \(p_{x,y}\)
de estar no estado \(y\) no passo seguinte. Por esta razão os números \(p_{x,y}\) são chamados também de probabilidades de transição de
uma etapa da Cadeia de Markov.
Esta função, a qual é uma probabilidade condicional, satisfaz propriedades básicas da função de probabilidade resumidas no seguinte
teorema.
Teorema I.1.
Seja \(\{C_t \, : \, t\in \mathbb{N}\}\) uma Cadeia de Markov estacionária com espaço de estados \(S\) e função de trnasição \(p\).
Então
\begin{equation}
p_{x,y}\geq 0, \qquad x,y\in S
\end{equation}
e
\begin{equation}
\sum_{y\in S} p_{x,y} \, = \, 1, \qquad x\in S\cdot
\end{equation}
Demonstração.
Exercício ▉
Observe que, na segunda afirmação do teorema acima o estado inicial \(x\) é fixo e o estado de chegada são todos os \(y\in S\), nada afirma-se acerca da probabilidade \(\sum_{x\in S} p_{x,y}\).
Exemplo I.2: Cadeia com dois estados (Continuação)
Continuando com o Exemplo I.1 percebemos que a função de transição, segundo a descrição no texto é
\begin{equation}
p_{0,0} \, = \, 1-\alpha, \quad p_{0,1} \, = \, \alpha, \quad p_{1,0} \, = \, \beta \quad \mbox{e} \quad p_{1,1} \, = \, 1-\beta\cdot
\end{equation}
Observemos que pelo fato de tanto \(\alpha\) quanto \(\beta\) serem probabilidades, todas as probabilidades de transição são maiores ou iguais a zero. Ainda
vemos que \(p_{0,0}+p_{0,1} = 1\) e \(p_{1,0}+p_{1,1} = 1\), como enunciado pelo Teorema I.1.
Os resultados que serão apresentados neste texto referem-se à situação de Cadeias de Markov homogêneas ou estacionárias e, como vimos,
a função de transição foi definida para este tipo de cadeias. Além dessa característica vamos estudar agora outras duas que nos
permitirão continuar os estudos avançados das Cadeias de Markov estacionárias ou homogêneas.
Distribuição inicial
Um vetor que consiste de números não negativos que somam 1 é chamado de vetor de probabilidades. Um vetor de probabilidades cujas coordenadas especificam
as probabilidades de que uma Cadeia de Markov esteja em cada um dos seus estados no tempo inicial é chamado de distribuição inicial da cadeia ou o vetor de
probabilidade inicial.
Definição I.4 (Distribuição inicial).
Seja \(\{C_n\}\) uma Cadeia de Markov estacionária com espaço de estados \(S\). A função \(\pi_0(x)\), \(x\in S\), definida como
\begin{equation}
\pi_0(x) \, = \, P(C_{0}=x), \qquad x\in S,
\end{equation}
é chamada de distribuição inicial da cadeia.
Fica implícito que a dimensão do vetor \(\pi_0\) é igual ao número de estados ou elementos em \(S\). Esta probabilidade inicial ou distribuição
inicial foi objeto de estudo no Exemplo 1, nesse exemplo mostramos uma situação na qual a distribuição de qualquer \(C_n\) é igual à distribuição
inicial.
Como toda função de probabilidade, a distribuição inicial satisfaz que
\begin{equation}
\pi_0(x)\geq 0, \qquad x\in S
\end{equation}
e
\begin{equation}
\sum_{x\in S} \pi_0(x) \, = \, 1\cdot
\end{equation}
A distribuição conjunta de \(\{C_0,C_1,C_2\}\) pode ser facilmente expressa em termos da função de transição e da distribuição
inicial. Por exemplo,
\begin{equation}
P(C_0=c_{_0}, C_1=c_{_1}) \, = \, P(C_0=c_{_0})P(C_1=c_{_1} \, | \, C_0=c_{_0}) \, = \, \pi_0(c_{_0})p_{c_{_0},c_{_1}}\cdot
\end{equation}
Dado que \(\{C_0, C_1, C_2\}\) satisfaz a propriedade de Markov e tem distribuição de transição estacionária, isto é, satisfaz a Definição I.2,
vemos que
\begin{array}{rcl}
P(C_2=c_{_2} \, | \, C_0=c_{_0}, C_1=c_{_1}) & = & P(C_2=c_{_2} \, | \, C_1=c_{_1}) \\
& = & P(C_1=c_{_2} \, | \, C_0=c_{_1}) \, = \, p_{c_{_1},c_{_2}}\cdot
\end{array}
Então
\begin{equation}
P(C_0=c_{_0}, C_1=c_{_1}, C_2=c_{_2}) \, = \, \pi_0(c_{_0})p_{c_{_0},c_{_1}}p_{c_{_1},c_{_2}}\cdot
\end{equation}
Em situações gerais se consegue escrever a probabilidade conjunta em termos da distribuição inicial e da função de transição
como no teorema a seguir.
Teorema I.2.
Seja \(\{C_n\}\) uma Cadeia de Markov em \(S\) com função de trnasição \(p\). Então, podemos escrever a função de probabilidade
conjunta de \(C_0,C_1,\cdots,C_n\) como
\begin{equation}
P(C_0=c_{_0},C_1=c_{_1},\cdots,C_n=c_{_n}) \, = \, \pi_{0}(c_{_0})p_{c_{_0},c_{_1}}p_{c_{_1},c_{_2}}\cdots p_{c_{_{n-1}},c_{_n}} \cdot
\end{equation}
Demonstração.
Para \(n = 2\) provamos acima que esta expressão da probabilidade conjunta é válida. Por indução percebemos que também esta expressão é
válida para qualquer \(n\).
▉
É geralmente mais conveniente, no entanto, inverter a ordem de nossas definições. Diz-se que \(\gamma_{x,y}\), \(x,y\in S\) é uma função de
transição se satisfizer
\begin{equation}
p_{x,y}\geq 0, \qquad x,y\in S
\end{equation}
e
\begin{equation}
\sum_{y\in S} p_{x,y} \, = \, 1, \qquad x\in S\cdot
\end{equation}
Dizemos que \(\pi_0(x)\), \(x\in S\), é a probabilidade inicial da cadeia se satisfaz
\begin{equation}
\pi_0(x)\geq 0, \qquad x\in S
\end{equation}
e
\begin{equation}
\sum_{x\in S} \pi_0(x) \, = \, 1\cdot
\end{equation}
Pode ser mostrado que, dado qualquer função de transição \(p\) e qualquer distribuição inicial \(\pi_0\), existe um espaço
de probabilidade e variáveis aleatórias \(\{C_n\}\), definidas nele, satisfazendo a afirmação do Teorema I.2 (Doob, 1953). Logo, demonstra-se também
que essas variáveis aleatórias formam uma Cadeia de Markov com a função de transição \(p\) e distribuição inicial \(\pi_0\).
O leitor pode estar incomodado com a possibilidade de que algumas das probabilidades condicionais que discutimos podem não estar bem definidas. Por exemplo, o lado esquerdo
da probabilidade na Definição I.2, a chamada propriedade de Markov, não está bem definida, se
\begin{equation}
P(C_0=c_0,\cdots,C_n=c_n) \, = \, 0\cdot
\end{equation}
Essa dificuldade é resolvida observando as equações: \(p_{x,y}\geq 0\), \(\sum_{y\in S} p_{x,y} = 1\), \(\pi_0(x)\geq 0\) e \(\sum_{x\in S} \pi_0(x) = 1\).
Estas equações definem a função de transição e a distribuição inicial as quais estão bem definidas, assim como a
equação no Teorema I.2 que descreve a distribuição conjunta de \(\{C_0,C_1,\cdots,C_n\}\), a qual também está bem definida. Não é
difícil mostrar que, se a expressão da distribuição conjunta no Teorema I.2 se satisfaz então as equações acima são válidas
sempre que as probabilidades condicionais nas respectivas equações estejam bem definidas. O mesmo será válido para a qualificação de outras
equações, envolvendo probabilidades condicionais, que serão obtidas posteriormente.
Em breve será evidente que a função de transição de uma Cadeia de Markov tem um papel muito maior na descrição de suas propriedades
do que o da distribuição inicial. Por esta razão, costuma-se estudar simultaneamente toda a Cadeia de Markov com uma dada função de transição.
Na verdade, nós aderimos à convenção usual de que, por uma Cadeia de Markov com a função de transição \(p\), o que
realmente queremos dizer é que nos referimos à família de todas as Cadeias de Markov com função de transição \(p\).
Matriz de transição
Suponha uma Cadeia de Markov estacionária com espaço de estados \(S = \{s_{_1}, s_{_2}, s_{_3},\cdots, s_{_d}\}\) finito. Em situações como esta é
conveniente definir as probabilidades de transição como a matriz
\begin{equation*}
\begin{matrix}
& \\
\mathcal{P} = \begin{matrix} s_{_1} \\ s_{_2} \\ s_{_3} \\ \vdots \\ s_{_d} \end{matrix}
\left( \vphantom{ \begin{matrix} 12 \\ 12 \\ 12 \\ 12 \\ 12 \end{matrix} } \right.
\end{matrix}
\hspace{-1.2em}
\begin{matrix}
s_{_1} & s_{_2} & s_{_3} & \cdots & s_{_d} \\
p_{{s_{_1}},{s_{_1}}} & p_{{s_{_1}},{s_{_2}}} & p_{{s_{_1}},{s_{_3}}} & \cdots & p_{{s_{_1}},{s_{_d}}} \\
p_{{s_{_2}},{s_{_1}}} & p_{{s_{_2}},{s_{_2}}} & p_{{s_{_2}},{s_{_3}}} & \cdots & p_{{s_{_2}},{s_{_d}}} \\
p_{{s_{_3}},{s_{_1}}} & p_{{s_{_3}},{s_{_2}}} & p_{{s_{_3}},{s_{_3}}} & \cdots & p_{{s_{_3}},{s_{_d}}} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
p_{{s_{_d}},{s_{_1}}} & p_{{s_{_d}},{s_{_2}}} & p_{{s_{_d}},{s_{_3}}} & \cdots & p_{{s_{_d}},{s_{_d}}}
\end{matrix}
\hspace{-0.2em}
\begin{matrix}
& \\
\left. \vphantom{ \begin{matrix} 12 \\ 12 \\ 12 \\ 12 \\ 12 \end{matrix} } \right)\cdot
\end{matrix}
\end{equation*}
de elementos as probabilidades de transição entre os estados, escritas como
\begin{equation}
p_{x,y} \, = \, P(C_1=y \, | C_0=x), \qquad x,y\in S\cdot
\end{equation}
Definição I.5 (Matriz de transição).
Seja \(\{C_t \, : \, t\in \mathbb{N}\}\) uma Cadeia de Markov estacionária com espaço de estados \(S = \{s_{_1},s_{_2},\cdots,s_{_d}\}\) finito. A matriz quadrada \(\mathcal{P}\),
definida acima, é conhecida como a matriz de probabilidades de transição.
Exemplo I.3 Cadeia com dois estados (Continuação)
No Exemplo I.1, a matriz \(\mathcal{P}\) de probabilidades de transição no caso de uma cadeia com dois estados foi considerada da forma:
\begin{equation}
\begin{matrix} \begin{matrix} \end{matrix} & \begin{matrix} \; 0 \; & \quad 1 \; \end{matrix} \\
\mathcal{P} \, = \, \begin{matrix} 0 \\ 1 \end{matrix} &
\begin{pmatrix} 1-\alpha & \alpha \\ \beta & 1-\beta \end{pmatrix},
\end{matrix}
\end{equation}
significando que \(s_{_1}=0\) e \(s_{_2}=1\).
Teorema I.3.
Seja \(\{C_n\}\) uma Cadeia de Markov em \(S= \{s_{_1}, s_{_2}, s_{_3},\cdots, s_{_d}\}\) estacionária e função de transição
\(p\). A matriz \(\mathcal{P}=\big(p_{x,y}\big)\), de probabilidades de transição, satisfaz as seguintes propriedades:
A primeira propriedade é evidente pelo fato de cada \(p_{x,y}\) ser uma probabilidade. Para a segunda propriedade observemos que para qualquer estado \(x\in S\)
e qualquer inteiro \(n\geq 0\) temos que
\begin{equation}
P\big(C_{n+1}\in S \big) \, = \, P\big(C_{n+1}\in S \, | \, C_n=x \big) \, = \, 1
\end{equation}
e, dado que os evento, \(\{C_{n+1}=s_{_1}\}, \{C_{n+1}=s_{_2}\}, \cdots, \{C_{n+1}=x\},\cdots\) são disjuntos, podemos escrever
\begin{array}{rcl}
P\big(C_{n+1}\in S \, | \, C_n=x \big) & = & \displaystyle P\left(\bigcup_{i=1}^d \big(C_{n+1}=s_{_i} \, | \, C_n=x\big) \right) \\
& = & \displaystyle \sum_{i=1}^d P\big( C_{n+1}=s_{_i} \, | \, C_n=x\big) \, = \, 1\cdot
\end{array}
▉
Este último resultado signifia que a partir de qualquer estado \(x\), com probabilidade finita, uma cadeia assume necessariamente algum elemento do espaço de
estado na próxima vez. Geralmente uma matriz quadrada satisfazendo estas duas propriedades se disse que é uma matriz estocástica.
Devido à propriedade de Markov, esta matriz capta a essência do processo, e determina o comportamento da cadeia em qualquer momento no futuro. Se a matriz também
satisfaz a condição por colunas, isto é, quando a soma das colunas também é 1, então se disse que a cadeia é duplamente estocástica.
Vamos rever a seguir alguns exemplos clássicos de Cadeias de Markov e alguns outros para ilustrar os conceitos e resultados da teoria geral.
Cadeia com dois estados
Embora simples, esta cadeia é suscetível a muitas aplicações devido ser comum encontrar situações em que a dualidade ser ou não ser,
estar ou não estar, ter ou não ter está presente, sempre em uma alternância constante entre um estado e outro.
Exemplo I.4 - Cadeia com dois estados.
Uma Cadeia de Markov com dois estados é um modelo de Markov para um sistema que pode assumir somente dois valores, por exemplo, 0 e 1. Partindo do estado 0, permanece nele
com probabilidade \(1-\alpha\) e assume valor 1 com probabilidade \(\alpha\). Da mesma forma, se o estado atual é 1, permanece nele com probabilidade \(1-\beta\) e muda para
0 com probabilidade \(\beta\).
No caso particular \(\alpha=1-\beta\), as variáveis \(C_1, C_2, \cdots\) são independentes e identicamente distribuídas tais que \(P(C_n = 0) = 1 -\alpha\) e
\(P(C_n = 1) = \alpha\), para cada \(n\geq 1\). Quando \(\alpha\neq 1-\beta\), \(C_n\) depende \(C_{n-1}\).
Variáveis aleatórias independentes
Como Exemplo 1 mostrou, em algumas situações justifica-se a construção de cadeias com variáveis aleatórias independentes.
Exemplo I.5 - Variáveis aleatórias independentes
A estrutura mais simples possível é a de variáveis aleatórias independentes. Este seria um bom modelo para sistemas com experimentos repetidos, nos
quais os estados futuros do sistema são independentes dos estados passados e do estado presente. Em muitos sistemas que surgem na prática, no entanto, os estados
passados e o presente exercem influência nos estados futuros. Vejamos como construir tais sistemas com variáveis aleatórias independentes.
Seja \(\xi_0,\xi_1,\xi_2,\cdots\) uma sequência de variáveis aleatórias independentes, com valores no conjunto \(\{0, 1,2, \cdots\}\), identicamente distribuídas
com probabilidades dadas por \(\alpha_0,\alpha_1,\cdots\).
Definiremos várias Cadeias de Markov a partir desta sequência:
(a) A sequência \(C_n=\xi_n\) é uma Cadeia de Markov com probabilidades de transição
\begin{equation}
P(C_{n+1}=c_{_{n+1}} \, | \, C_n=c_{_n}) \, = \, P(C_{n+1}=c_{_{n+1}}) \, = \, \alpha_{n+1}\cdot
\end{equation}
Recordemos que as variáveis são independentes, isto é, a matriz de probabilidades de transição é da forma
\begin{equation*}
\begin{matrix}
& \\
\mathcal{P} = \begin{matrix} 0 \\ 1 \\ 2 \\ \vdots \end{matrix}
\left( \vphantom{ \begin{matrix} 12 \\ 12 \\ 12 \\ 12 \end{matrix} } \right.
\end{matrix}
\hspace{-1.2em}
\begin{matrix}
0 & 1 & 2 & \cdots \\
\alpha_0 & \alpha_1 & \alpha_2 & \cdots \\
\alpha_0 & \alpha_1 & \alpha_2 & \cdots \\
\alpha_0 & \alpha_1 & \alpha_2 & \cdots \\
\vdots & \vdots & \vdots & \vdots
\end{matrix}
\hspace{-0.2em}
\begin{matrix}
& \\
\left. \vphantom{ \begin{matrix} 12 \\ 12 \\ 12 \\ 12 \end{matrix} } \right)\cdot
\end{matrix}
\end{equation*}
(c) O processo \(C_n=\xi_1+\xi_1+\cdots+\xi_n\) é uma Cadeia de Markov com matriz de probabilidades de transição da forma
\begin{equation*}
\begin{matrix}
& \\
\mathcal{P} = \begin{matrix} 0 \\ 1 \\ 2 \\ \vdots \end{matrix}
\left( \vphantom{ \begin{matrix} 12 \\ 12 \\ 12 \\ 12 \end{matrix} } \right.
\end{matrix}
\hspace{-1.2em}
\begin{matrix}
0 & 1 & 2 & \cdots \\
\alpha_0 & \alpha_1 & \alpha_2 & \cdots \\
0 & \alpha_0 & \alpha_1 & \cdots \\
0 & 0 & \alpha_0 & \cdots \\
\vdots & \vdots & \vdots & \vdots
\end{matrix}
\hspace{-0.2em}
\begin{matrix}
& \\
\left. \vphantom{ \begin{matrix} 12 \\ 12 \\ 12 \\ 12 \end{matrix} } \right)\cdot
\end{matrix}
\end{equation*}
Uma situação particular desta cadeia é conhecido como passeio aleatório simples e é muitas vezes utilizado por físicos como um
modelo aproximado das flutuações na posição de uma molécula relativamente grande.
Exemplo I.6 - Fast food
Suponha que cada vez que uma criança adquire uma refeição de criança em seu restaurante fast food favorito, ele recebe uma das quatro figuras de
super-heróis. Naturalmente, a criança quer coletar todas as quatro figuras de ação e assim ele come regularmente no restaurante para completar a
coleção.
Este processo pode ser descrito por uma Cadeia de Markov e a matriz de probabilidades de transição é da forma:
\begin{equation*}
\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 \\
0 & 1 & 0 & 0 & 0 \\
0 & 1/4 & 3/4 & 0 & 0 \\
0 & 0 & 1/2 & 1/2 & 0 \\
0 & 0 & 0 & 3/4 & 1/4 \\
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}
\end{equation*}
O grafo correspondente a esta matriz é mostrado na Figura I.2 abaixo. Vamos explicar agora o procedimento para encontrarmos esta matriz.
Figura I.2: Grafo das probabilidades de transição do Exemplo I.6 - Fast-food.
Neste caso, seja \(S = \{0, 1, 2, 3, 4\}\) o espaço de estados, ou seja, o número das diferentes figuras de super-heróis que a criança tem recolhido
após a compra de \(k\) refeições. Supondo que cada refeição contém um dos quatro super-heróis, com igual probabilidade, e que a
matriz de transição em qualquer refeição é independente do que está contido em todas as refeições anteriores ou futuras,
então a matriz de probabilidades de transição é \(\mathcal{P}\) mostrada anteriormente.
Inicialmente, quer dizer, antes de todas as refeições serem compradas, o processo começa em 0, estado no qual a criança não tem figuras de
super-heróis. Quando a primeira refeição é comprada, a Cadeia de Markov deve passar para o estado 1, uma vez, não importa qual figura de ação
está contido na refeição, a criança terá agora um super-herói. Assim, \(p_{0,1} = 1\), e \(p_{0,j} = 0\) para todo \(j \neq 1\).
Se a criança tem uma figura de ação, quando ele compra a próxima refeição, ele tem uma chance de 25% de receber um duplicado e 75%
de chance de conseguir uma nova figura de super-herói.
Assim, \(p_{1,1} = 1/4\), \(p_{1,2} = 3/4\) e \(p_{1,j} = 0\) para a \(j \neq 1, 2\). Lógica semelhante é usada para completar o restante da matriz.
A criança pode estar interessada em saber o número médio de refeições que ela precisa comprar até que sua coleção esteja
completa. Ou, talvez a criança salvou-se apenas o dinheiro suficiente para comprar 10 almoços e quer saber quais suas chances de completar o conjunto antes de ficar
sem dinheiro. Vamos desenvolver a teoria necessária para responder a essas e outras perguntas.
Um outro exemplo de Cadeia de Markov, desta vez famoso, é o mecanismo de busca ou motor de busca de informações na Internet. Os motores de busca são
sistemas de software projetados para encontrar informações armazenadas em um sistema computacional a partir de palavras-chave indicadas pelo utilizador, reduzindo
o tempo necessáio para encontrar informações.
Exemplo I.7 - Motor de busca do Google
Os motores de busca surgiram logo após o aparecimento da Internet, com a intenção de prestar um serviço extremamente importante: a busca de qualquer
informação na rede, apresentando os resultados de uma forma organizada, e também com a proposta de fazer isto de uma maneira rápida e eficiente. A partir
deste preceito básico, diversas empresas se desenvolveram, chegando algumas a valer milhões de dólares. Entre as maiores empresas encontram-se Google, Yahoo,
Lycos. Os buscadores se mostraram imprescindíveis para o fluxo de acesso e a conquista de novos visitantes.
Suponha que o internauta navega por páginas da Web em um universo de cinco páginas, como mostrado na Figura I.3 (a), sendo cada página os elementos do espaço
de estados \(S = \{1, 2, 3, 4, 5\}\). O internauta escolhe a próxima página para ver selecionando com igual probabilidade a partir das páginas apontadas pela
página atual. Se uma página não tem qualquer ligação de saída (por exemplo, página 2), em seguida, o interessado seleciona qualquer
uma das páginas do universo, com igual probabilidade. Poderíamos estar interessados em encontrar a probabilidade de que o internauta veja a \(i\)-ésima página.
O comportamento de visualização pode ser modelado por uma Cadeia de Markov em que o estado representa a página atualmente visualizada. Se a página atual
aponta para \(k\) páginas, então a próxima página é selecionado a partir desse grupo com probabilidade \(1/k\). Se a página atual não
aponta para nenhuma página, então a próxima página pode ser qualquer uma das cinco páginas com probabilidade de transição 1/5.
O modelo markoviano de internauta aleatório constitui a base para o algoritmo PageRank, que foi introduzido pelo Google para classificar a importância de uma página
na Web. O ranking de uma página é dado pela chamada distribuição estacionária da Cadeia de Markov (ver Parte IV). O tamanho do espaço de estados
nessa Cadeia de Markov é de bilhões de páginas e no Exemplo I.7 mostramos a abordagem básica para a atribuição do ranking de páginas Web
segundo uma Cadeia de Markov. Para maiores informações acerca do algoritmo PageRank ver o livro Langville, A.M. and Meyer, C.D.(2006). Google's PageRank and Beyond: The
Science of Search Engine Rankings. Princeton University Press.
Figura I.3: Grafo das probabilidades de transição num buscador.
Esta estratégia resolve de maneira simples o caso em que os usuários ficam presos em uma página sem links de saída, ou seja, página 2 na Figura I.3 (a).
O método, no entanto, não é suficiente para assegurar que a Cadeia de Markov é irredutível (Seção III.3) e aperiódica (Seção IV.5).
Por exemplo, na Figura I.3 (b) os usuários também podem tornar-se presos na classe periódica. Isto coloca um problema para o algoritmo de classificação
que usa o poder da matriz de probabilidade de transição para obter a distribuição estacionária (Parte IV). Para lidar com este problema, o algoritmo
PageRank também assume a chamada classificação apropriada. Maiores informações podem ser encontradas no artigo Page, Brin, Motwani & Winograd (1998)
e mais recentemente no livro Langville & Meyer (2011), dentre outros.
Cadeia de Ehrenfest
Paul Ehrenfest (1880 - 1933), foi um físico austríaco. Ehrenfest é importante na história da probabilidade por causa de seus modelos de difusão, como as
cadeias de Ehrenfest, desenvolvidos para dar uma interpretação estatástica à segunda lei da termodinâmica.
Exemplo I.8 - Cadeia de Ehrenfest
O seguinte é um modelo simples de intercambio de calor ou de moléculas de gás entre dois corpos isolados. Suponha que temos duas caixas, identificadas como
\(1,2,\cdots,d\). Inicialmente, algumas dessas bolas estã na caixa 1 e as restantes estão na caixa 2. Um inteiro é escolhido aleatoriamente a partir de \(1, 2,\cdots, d\)
e a bola rotulada por esse inteiro é removida da sua caixa e colocada na caixa oposta. Este procedimento é repetido indefinidamente com seleções
independente de uma tentativa para outra. Seja \(C_n\) o número de bolas na caixa 1 após a \(n\)-ésima tentativa. Então \(\{C_n\}\) é uma Cadeia
de Markov em \(S = \{0, 1, 2, \cdots, d\}\).
A probabilidade de transição desta Cadeia de Markov é calculada supondo que há \(x\) bolas na caixa 1 no tempo \(n\). Em seguida, com probabilidade
\(x/d\) a bola escolhida na \((n + 1)\)-ésima tentativa será retirada da caixa 1 e transferida para a caixa 2. Neste caso, restarão \(x - 1\) bolas na caixa
1 no instante de tempo \(n + 1\). Da mesma forma, com probabilidade \((d - x)/d\) a bola escolhida na tentativa \((n + 1)\)-ésima sairá da caixa 2 e será
transferida para a caixa 1, resultando em \(x + 1\) bolas na caixa 1 no tempo \(n + 1\). Assim, a função de transição desta Cadeia de Markov é
dada por:
\begin{equation}
p_{x,y} \, = \, \left\{ \begin{array}{cc} \dfrac{x}{d}, & y=x-1, \\ 1-\dfrac{x}{d}, & y=x+1, \\ 0, & \mbox{caso contrário} \end{array}\right.\cdot
\end{equation}
Note-se que esta cadeia somente pode ir, em uma transição, de \(x\) para \(x-1\) ou \(x+1\) com probabilidade positiva.
Os exemplos mostrados até o momento foram teóricos. Mostramos agora duas situações relacionadas a experiências práticas.
Exemplo I.9 - Experiência de criação de plantas.
Um botânico está estudando uma certa variedade de plantas que é monóica (tem órgãos masculinos e femininos em fores separadas em uma única
planta). Ele começa com duas plantas I e II e poliniza-as transversalmente atravessando o macho I com a fêmea II e a fêmea I com o macho II para produzir
dois descendentes. As plantas originais são destruídas e o processo é repetido assim que a nova geração estiver madura. Várias replicações
do estudo são executadas simultaneamente. O botânico pode estar interessado na proporção de plantas em qualquer geração que tenham cada
um dos vários genótipos possíveis para um gene específico.
Suponha que o gene tenha dois alelos, \(A\) e \(a\). O genótipo de um indivíduo será uma das três combinações \(AA\), \(Aa\) ou \(aa\). Quando
um novo indivíduo nasce, obtém um dos dois alelos (com probabilidade 1/2 cada) de um dos pais e ele obtém de forma independente um dos dois alelos do outro
pai. Os dois descendentes obtêm seus genótipos independentemente uns dos outros. Por exemplo, se os pais têm genótipos \(AA\) e \(Aa\), então uma
descendência receberá \(A\) com certeza do primeiro pai e receberá \(A\) ou \(a\) do segundo pai com uma probabilidade de 1/2 cada. Considere os estados desta
população serem o conjunto de genótipos dos dois membros da população atual. Não vamos distinguir o conjunto \(\{AA, Aa\}\) de \(\{Aa,AA\}\).
Existem então seis estados: \(\{AA,AA\}\), \(\{AA, Aa\}\), \(\{AA; aa\}\), \(\{Aa, Aa\}\), \(\{Aa, aa\}\) e \(\{aa, aa\}\). Para cada estado, podemos calcular a probabilidade de
que a próxima geração esteja em cada um dos seis estados. Por exemplo, se o estado for \(\{AA,AA\}\) ou \(\{aa, aa\}\), a próxima geração
estará no mesmo estado com probabilidade 1. Se o estado for \(\{AA, aa\}\), a próxima geração estará no estado \(\{Aa,Aa\}\) com probabilidade 1.
Os outros três estados têm transições mais complicadas.
Figura I.4: A geração que segue \(\{Aa, Aa\}\), grafo do estudo botânico.
Se o estado atual é \(\{Aa, Aa\}\), então todos os seis estados são possíveis para a próxima geração. Para calcular a probabilidade
de transição, ajuda a calcular primeiro a probabilidade de uma prole dada ter cada um dos três genótipos. A Figura I.4 acima ilustra a possível
prole neste estado. Cada seta que vai para baixo na Figura I.4 é uma possível herança de um alelo, e cada combinação de setas que termina em um
genótipo tem probabilidade de 1/4. Segue-se que a probabilidade de \(\{AA\}\) e \(\{aa\}\) são ambas 1/4, enquanto a probabilidade de \(Aa\) é 1/2, porque duas
combinações diferentes de flechas levam a essa prole. Para que o próximo estado seja \(\{AA,AA\}\), ambos os descendentes devem ser \(\{AA\}\) independentemente,
então a probabilidade dessa transição é 1/16. O mesmo argumento implica que a probabilidade de uma transição para \(\{aa, aa\}\) é 1/16.
Uma transição para \(\{AA, Aa\}\) exige que uma prole seja \(\{AA\}\) (probabilidade 1/4) e a outra seja \(\{Aa\}\) (probabilidade 1/2). Mas os dois genótipos
diferentes podem ocorrer em qualquer ordem, então toda a probabilidade de tal transição é \(2\times (1/4)\times (1/2) = 1/4\). Um argumento semelhante
mostra que uma transição para \(\{Aa, aa\}\) também tem probabilidade 1/4. Uma transição para \(\{AA aa\}\) exige que uma prole seja \(\{AA\}\)
(probabilidade 1/4) e a outra seja \(\{aa\}\) (probabilidade 1/4). Mais uma vez, estes podem ocorrer em duas ordens, então toda a probabilidade \(2\times (1/4)\times (1/4) = 1/8\).
Por subtração, a probabilidade de uma transição para \(\{Aa, Aa\}\) deve ser \(1 - 1/16 - 1/16 - 1/4 - 1/4 - 1/8 = 1/4\). Aqui está a matriz de
transição, que pode ser verificada de forma semelhante àquela que acabamos de fazer:
\begin{equation*}
\begin{matrix}
& \\
\mathcal{P} = \begin{matrix} \{AA,AA\} \\ \{AA,Aa\} \\ \{AA,aa\} \\ \{Aa,Aa\} \\ \{Aa,aa\} \\ \{aa,aa\} \end{matrix}
\left( \vphantom{ \begin{matrix} 12 \\ 12 \\ 12 \\ 12 \\ 12 \\ 12 \end{matrix} } \right.
\end{matrix}
\hspace{-1.2em}
\begin{matrix}
\{AA,AA\} & \{AA,Aa\} & \{AA,aa\} & \{Aa,Aa\} & \{Aa,aa\} & \{aa,aa\} \\
1.0000 & 0.0000 & 0.0000 & 0.0000 & 0.0000 & 0.0000 \\
0.2500 & 0.5000 & 0.0000 & 0.2500 & 0.0000 & 0.0000 \\
0.0000 & 0.0000 & 0.0000 & 1.0000 & 0.0000 & 0.0000 \\
0.0625 & 0.2500 & 0.1250 & 0.2500 & 0.2500 & 0.0625 \\
0.0000 & 0.0000 & 0.0000 & 0.2500 & 0.5000 & 0.2500 \\
0.0000 & 0.0000 & 0.0000 & 0.0000 & 0.0000 & 1.0000
\end{matrix}
\hspace{-0.2em}
\begin{matrix}
& \\
\left. \vphantom{ \begin{matrix} 12 \\ 12 \\ 12 \\ 12 \\ 12 \\ 12 \end{matrix} } \right)\cdot
\end{matrix}
\end{equation*}
Exemplo I.10 - Problema de gerenciamento.
Em uma indústria, a produção de um determinado produto é regulada de acordo com o estoque existente no final do dia. Ou seja, se existirem pedidos
insatisfeitos ou se o estoque é zero, a produção do próximo dia abrange as ordens insatisfeitas mais duas a mais unidades métricas (u.m.).
Pelo contrário, se existe um estoque não zero, não há produção para o dia seguinte. Sabemos ainda que a demanda dos consumidores pelo
produto é de 1 u.m. por dia com probabilidade de 60%, ou 2 u.m. por dia com probabilidade de 40%. Queremos saber, por exemplo, qual é a probabilidade
de ter ordens insatisfeitas no longo prazo.
Uma vez que a demanda máxima do produto é de 2 u.m., a produção da fábrica no primeiro dia de sua função deve ser de 2 u.m. e,
portanto, no final do dia, o estoque é zero ou 1 u.m.. No primeiro caso, o processo é repetido da mesma maneira. No último caso, a produção do
dia seguinte é zero e, portanto, no final deste dia, o estoque é zero (neste caso o processo é repetido da mesma maneira) ou há ordens insatisfeitas de
1 u.m.. No último caso, a produção do dia seguinte é de 3 u.m. ou seja, 1 u.m. para cobrir as ordens insatisfeitas do dia anterior mais 2 u.m., e assim
por diante. Torna-se, portanto, evidente que, de acordo com o ritmo de produção acima mencionado, há três situações possíveis no final
de cada dia: ordens insatisfeitas de 1 u.m., estoque zero e estoque de 1 u.m.. Evidentemente, nosso problema pode ser descrito com uma Cadeia de Markov tendo como matriz de probabilidades
de transição:
\begin{equation*}
\begin{matrix}
& \\
\mathcal{P} = \begin{matrix} \mbox{Ordens insatisfeitas} \\ \mbox{Estoque zero} \\ \mbox{Estoque 1 u.m.} \end{matrix}
\left( \vphantom{ \begin{matrix} 12 \\ 12 \\ 12 \end{matrix} } \right.
\end{matrix}
\hspace{-1.2em}
\begin{matrix}
\mbox{Ordens insatisfeitas} & \mbox{Estoque zero} & \mbox{Estoque 1 u.m.} \\
0.0 & 0.4 & 0.6 \\
0.0 & 0.4 & 0.6 \\
0.4 & 0.6 & 0.0
\end{matrix}
\hspace{-0.2em}
\begin{matrix}
& \\
\left. \vphantom{ \begin{matrix} 12 \\ 12 \\ 12 \end{matrix} } \right)\cdot
\end{matrix}
\end{equation*}
Uma matriz de transição para o número de linhas telefónicas ocupadas.
Suponha que o número de linhas usadas nos tempos 1, 2, ... formem uma Cadeia de Markov com matriz de probabilidades de transição estacionária. Essa
cadeia possui seis estados possíveis 0, 1, ..., 5, onde \(i\) é o estado no qual exatamente \(i\) linhas estão sendo usadas em um determinado momento
\((i = 0, 1,\cdots, 5)\). Suponha que a matriz de transição \(\mathcal{P}\) seja a seguinte:
\begin{equation*}
\begin{matrix}
& \\
\mathcal{P} = \begin{matrix} 0 \\ 1 \\ 2 \\ 3 \\ 4 \\ 5 \end{matrix}
\left( \vphantom{ \begin{matrix} 12 \\ 12 \\ 12 \\ 12 \\ 12 \\ 12 \end{matrix} } \right.
\end{matrix}
\hspace{-1.2em}
\begin{matrix}
0 & 1 & 2 & 3 & 4 & 5 \\
0.1 & 0.4 & 0.2 & 0.1 & 0.1 & 0.1 \\
0.2 & 0.3 & 0.2 & 0.1 & 0.1 & 0.1 \\
0.1 & 0.2 & 0.3 & 0.2 & 0.1 & 0.1 \\
0.1 & 0.1 & 0.2 & 0.3 & 0.2 & 0.1 \\
0.1 & 0.1 & 0.1 & 0.2 & 0.3 & 0.2 \\
0.1 & 0.1 & 0.1 & 0.1 & 0.4 & 0.2\end{matrix}
\hspace{-0.2em}
\begin{matrix}
& \\
\left. \vphantom{ \begin{matrix} 12 \\ 12 \\ 12 \\ 12 \\ 12 \\ 12 \end{matrix} } \right)\cdot
\end{matrix}
\end{equation*}
(a) Supondo que todas as cinco linhas estejam em uso em um determinado momento de observação, determinar a probabilidade de que exatamente quatro linhas
serão usadas no próximo tempo de observação.
(b) Supondo que nenhuma linha esteja em uso em um determinado momento, determinar a probabilidade
de que pelo menos uma linha esteja em uso no próximo momento de observação.
Mostre que o seguinte processo auto-regressivo é um processo Markov:
\begin{equation}
C_n \, = \, \rho C_{n-1}+\xi_n, \qquad C_0 \, = \, 0,
\end{equation}
onde \(\xi_1,\cdots,\xi_n\) são variáveis aleatórias independentes e igualmente distribuídas.
Cinco pontos são marcados sobre um círculo. Um processo se move a partir de um determinado ponto a seus vizinhos, com uma probabilidade de 1/2 para cada vizinho.
Encontre a matriz de transição da Cadeia de Markov resultante.
Sejam \(\{C_n\}\) e \(\{D_n\}\) duas Cadeias de Markov com espaço de estados \(S=\mathbb{Z}\). É necessariamente \(\{C_n+D_n\}\) uma Cadeia de Markov?
Seja \(\{\overline{C}_n\}\) a sequência de médias amostrais calculadas a partir de \(C_1,C_2,\cdots\), uma sequência de variáveis aleatórias
independentes e identicamente distribuídas, isto é,
\begin{equation}
\overline{C}_n \, = \, \dfrac{1}{n}\big( C_1+C_2+\cdots+C_n\big)\cdot
\end{equation}
(a) É \(\{\overline{C}_n\}\) um processo de Markov?
(b) Se a resposta à primeira parte é sim, encontrar a probabilidade de transição \(P\big( \overline{C}_n=y \, | \, \overline{C}_{n-1}=x\big)\).
Seja \(\{C_n\}\) uma Cadeia de Markov. Prove que, para todo \(1< r < n\),
\begin{equation}
P\big( C_r=c_{_r} \, | \, C_i = c_{_i}\big) \, = \, P\big( C_r=c_{_r} \, | \, C_{r-1}=c_{_{r-1}}, C_{r+1}=c_{_{r+1}}\big),
\end{equation}
sendo \(i=1,2,\cdots,r-1,r+1,\cdots,n\) e \(c_{_1},c_{_2},\cdots\) os valores observados da cadeia.
Realizamos uma sequência de experimentos da seguinte forma: primeiro uma moeda honesta é lançada. Em seguida, se no experimento \(n-1\) sai cara, jogamos
uma moeda honesta; se nele sai coroa lançamos uma moeda que tem probabilidade de \(1/n\) de obter cara. Quais são as probabilidades de transição? É
este um processo estacionário?
Uma urna contém inicialmente cinco bolas pretas e cinco bolas brancas. A seguinte experiência é repetida indefinidamente: Uma bola é retirada da
urna; se a bola for branca, ela é colocada de volta na urna, caso contrário ela é deixada de fora. Considere \(C_n\) o número de bolas pretas restantes
na urna após a \(n\)-ésima retirada da urna.
(a) É \(\{\overline{C}_n\}\) um processo de Markov? Se assim for, encontrar as probabilidades de transição adequados e faça o grafo correspondente.
(b) Será que as probabilidades de transição dependem de n?.
Mostrar que qualquer sequência de variáveis aleatórias independentes que assumem valores em um conjunto enumerável \(S\) é uma Cadeia de
Markov. Em qual condição essa cadeia é homogênea?
Demonstrar o Teorema I.1.
Suponha que João está atirando cestas no ginásio da escola e está muito interessado no número de cestos que ele é capaz de acertar
em sequência. Suponha que cada tiro vai entrar no cesto com uma probabilidade \(\alpha\in (0,1)\) e que o sucesso ou fracasso de cada tiro é independente de todos
os outros tiros. Considere \(C_n\) ser o número de cestas que ele acertou após \(n\) tiros. Assim, por exemplo, \(C_0 = 0\) e \(C_1\in \{0,1\}\), dependendo se ele
acertou ou não o primeiro tiro. É razoável modelar \(C_n\) como uma Cadeia de Markov? Qual é o espaço de estado? Qual é a matriz de
probabilidadaes de transição?
Para uma Cadeia de Markov \(\{C_n\}\), prove que
\begin{equation}
P\big( C_n=x \, | \, C_{n_{_1}}=c_{_{n_1}},\cdots,C_{n_{_k}}=c_{_{n_k}}\big) \, = \, P\big( C_n=x \, | \, C_{n_{_k}}=c_{_{n_k}}\big)
\end{equation}
quaisquer sejam \(n_{_1} < n_{_2} < \cdots < n\).
Prove as expressões das matrizes de transição no Exemplo I.5 (b) e (c).
Suponha que um aluno vai chegar na hora ou atrasado para uma determinada classe e que os eventos de que ele está na hora ou atrasado para a aula, em dias sucessivos,
formam uma Cadeia de Markov com matriz de probabilidades de transição estacionária. Suponhamos também que, se ele está atrasado em um determinado dia,
então a probabilidade de que ele vai chegar na hora certa no dia seguinte é de 0.8. Além disso, se ele chega em tempo em um determinado dia, então a
probabilidade de que ele chegará tarde no dia seguinte é de 0.5.
(a) Se o aluno está atrasado em um determinado dia, qual é a probabilidade de que ele vai estar na hora em cada um dos próximos três dias?
(b) Se o aluno está no tempo em um determinado dia, qual é a probabilidade de que ele chegará tarde em cada um dos próximos três dias?
Suponha que a profissão de um homem pode ser classificada como profissional, trabalhador qualificado ou operário não qualificado. Suponha que, dos
filhos de homens profissionais, 80 por cento são profissionais, 10 por cento são trabalhadores qualificados e 10 por cento são trabalhadores não
qualificados. No caso dos filhos de trabalhadores qualificados, 60 por cento são hábeis trabalhadores qualificados, 20 por cento são profissionais e 20
por cento são trabalhadores não qualificados. Finalmente, no caso de operários não qualificados, 50 por cento dos filhos são operários
não qualificados e 25 por cento em cada um são as chances das outras duas categorias. Suponha que cada homem tem pelo menos um filho e que seguindo a profissão
de um filho escolhido aleatoriamente de uma determinada família através de várias gerações temos definida uma Cadeia de Markov. Configure a
matriz de probabilidades de transição. Encontre a irobabilidade de que um neto escolhido aleatoriamente de um operário não qualificado seja um homem
profissional.
No Exercício anterior assumimos que todo homem tem pelo menos um filho. Suponha que, ao invés disso a probabilidade de que um homem tenha pelo menos um filho
seja 0.8. Formar uma Cadeia de Markov com quatro estados. Se um homem tem pelo menos um filho, a probabilidade de que o filho esteja em uma profissão específica seja
a mesma que no Exercício mencionado. O quarto estado seria o caso de não houver filho e, portanto, não existir continuidade na linha masculina. Encontre a
matriz de probabilidades de transição e encontre a probabilidade de que um neto escolhido aleatoriamente de um operário não qualificado seja um homem
profissional.
Considere um passeio aleatório, isto é, uma Cadeia de Markov com espaço de estados o conjunto \(S = \{0,1,\cdots,M\}\) e probabilidades de transição
\begin{equation}
p_{0,1} \, = \, 1, \qquad p_{M,M-1} \, = \, 1
\end{equation}
e, para \(x=1,2,\cdots,M-1\),
\begin{equation}
p_{x,x-1} \, = \, 1-\alpha, \qquad p_{x,x+1} \, = \, \alpha, \qquad \mbox{com} \qquad 0 < \alpha < 1\cdot
\end{equation}
Desenhe o grafo da matriz de probabilidades de transição.
Uma máquina é constituída por duas partes que não são reparadas de forma independente. A parte operante falha durante qualquer dia com
probabilidade \(\alpha\). Uma parte que não esteja funcionando será reparada no dia seguinte com probabilidade \(\beta\). Defina \(C_n\) como o número de
peças trabalhando no \(n\)-ésimo dia. Mostre que \(\{C_n\}\) é uma Cadeia de Markov com três estados e apresentar sua matriz de probabilidades de
transição.
Seja \(\{C_n \, : \, n\geq 0\}\) uma Cadeia de Markov. Mostre que
\begin{equation}
P\big( C_0=c_{_0} \, | \, C_1=c_{_1}, \cdots, C_n=c_{_n}\big) \, = \, P\big( C_0=c_{_0} \, | \, C_1=c_{_1}\big)\cdot
\end{equation}
