Cadeias de Markov
Fernando Lucambio Pérez
2025-08-12
1. Introdução
É frequentemente possível representar o comportamento de um sistema físico descrevendo todos os estados diferentes que este pode ocupar e indicando como se move de um estado para outro no tempo. Se a evolução futura do sistema depender apenas do seu estado atual, o sistema pode ser representado por um processo de Markov, um caso particular de processos estocásticos. Sequências de variáveis aleatórias que evoluem de alguma maneira no tempo servem como descrição informal do conceito de processo estocástico. Apresentamos a seguir a definição formal.
Definição 1.1: Processo estocástico.
Um processo estocástico é uma família \(\{C_t\}\), \(t\in T\) de variáveis aleatórias dependentes, definidas no mesmo espaço de probabilidade, indexadas pelo conjunto \(T\).
Os processos estocástico podem ser classificados de diversas maneiras. Aqui estamos interessados em duas dessas classificações:
A primeira é segundo as variáveis que o compõem, sejam discretas ou contínuas, identificando os processos estocásticos como discretos ou contínuos, respectivamente.
Uma outra classificação é segundo o conjunto de índices. Caso o conjunto \(T\) seja um subconjunto dos números inteiros ou naturais, chamamos o processo estocástico de processo a tempo discreto, em outras situações chama-se de processo a tempo contínuo, por exemplo, estamos no caso de processos a tempo conínuo quando \(T=\mathbb{R}\) ou \(T=[0,+\infty)\).
Em qualquer caso, pensamos em um processo estocástico como uma família de variáveis aleatórias que evoluem com o tempo. Estas variáveis podem mesmo ser independentes, o qual seria um caso muito especial e de pouco interesse. Pelo contrário, estamos preocupados com uma situação geral, e esperamos realista, de modelos para a evolução aleatória. Um destes modelos satisfaz a seguinte propriedade: condicionado em seus valores no \(n\)-ésimo instante, seus valores futuros não dependem de seus valores anteriores. Esta propriedade provou ser muito útil na sua análise e é a teoria geral dos processos com essa propriedade à qual voltamos nossa atenção agora.
Considere um processo estocástico discreto \(\{C_n\}\) com espaço amostral \(S\), finito ou infinito enumerável. \(S\) também é conhecido como o conjunto dos valores possíveis de serem assumidos pelas variáveis aleatórias \(C_0,C_1,\dots\). Pensemos na sequência de variáveis aleatórias \(C_0,C_1,\cdots,C_{n-1}\) como o passado, \(C_n\) como o presente e \(C_{n+1},C_{n+2},\cdots\) como o futuro do processo em relação ao tempo \(n\). A lei de evolução de um processo estocástico é frequentemente pensada em termos da distribuição condicional do futuro, dado o presente e os estados anteriores do processo.
Uma vez que estamos interessados em sistemas não-determinísticos, pensamos \(\{C_n\}\) como variáveis aleatórias definidas em um espaço de probabilidade comum. Pouco pode ser dito sobre essas variáveis aleatórias, a menos que alguma estrutura adicional seja imposta a eles. Uma propriedade útil dos processos estocásticos, que nos permite obter as probabilidades conjuntas é a propriedade de Markov. Basicamente, um processo estocástico é dito ser Markoviano se o futuro do processo, dado o presente, é independente do passado.
Definição 1.2: Propriedade de Markov.
Seja \(\{C_n\}\) um processo estocástico discreto com espaço amostral \(S\), finito ou infinito enumerável. Dizemos que \(\{C_n\}\) satisfaz a propriedade de Markov se, dado o estado atual, os estados passados não têm influência sobre o futuro. A propriedade de Markov é definida precisamente pela exigência de que \[ P(C_{n+1}=c_{n+1} \, | \, C_0=c_0,C_1=c_1,\cdots,C_n=c_n)=P(C_{n+1}=c_{n+1} \, | \, C_n=c_n), \] para qualquer seja a escolha do número natural \(n\) e os números \(c_0,c_1,\cdots,c_{n+1}\in S\). O espaço amostral \(S\), de um processo estocástico discreto a tempo discreto, é chamado de espaço de estados.
Andrei A. Markov obteve os primeiros resultados para processos estocásticos discretos finitos em 1906. Uma generalização para espaços de estados infinitos enumeráveis foi dada por Kolmogorov em 1936. Andrei Nikolaevich Kolmogorov (1903-1987) foi um matemático soviético. Kolmogorov participou das principais descobertas científicas do século XX nas áreas de probabilidade e estatística e na teoria da informação. A definição desta propriedade, também chamada de memória Markoviana, é que os estados anteriores são irrelevantes para a predição dos estados seguintes, desde que o estado atual seja conhecido.
Definição 1.3.
Um processo estocástico \(\{C_n\}\) discreto satisfaz a propriedade de Markov se, para cada \(n\) e \(m\), a distribuição condicional de \(C_{n+1},\cdots,C_{n+m}\) dado \(C_0,C_1,\cdots,C_n\) é a mesma que a sua distribuição condicional dado \(C_n\).
Isto quer dizer que, um processo estocástico satisfazendo a propriedade de Markov satisfaz que \[ P(C_{n+1},\cdots,C_{n+m} \, | \, C_0,C_1,\cdots,C_n)=P(C_{n+1},\cdots,C_{n+m}\, | \, C_n)\cdot \]
1.1. Cadeias de Markov
Estamos agora em condições de entender e, portanto, apresentar a definição do conceito principal e foco deste estudo: o que são Cadeias de Markov.
Definição 1.4: Cadeias de Markov.
Um processo estocástico \(\{C_n\}\) que satisfaz a propriedade de Markov é chamado de processo de Markov. Se, além disso, o processo estocástico for a tempo discreto e formado por variáveis aleatórias discretas o processo de Markov é chamado Cadeia de Markov.
Observemos que ao definirmos Cadeia de Markov nada é dito acerca do espaço de estados. Agora, como as variáveis aleatórias \(C_0,C_1,\cdots,C_n,\cdots\) que formam a Cadeia de Markov são discretas, então o espaço de estados \(S\) é finito ou infinito enumerável.
O estudo das Cadeias de Markov é válido a partir de dois pontos de vista. Em primeiro lugar, existe uma ampla teoria desenvolvida e, em segundo lugar, há um grande número de sistemas que surgem na prática que podem ser modelados desta forma, de modo existirem muitas aplicações práticas.
Como suporte computacional utilizamos a linguagem de programação e ambiente de desenvolvimento integrado para cálculos estatísticos e gráficos R Core Team (2025), versão
version[['version.string']]## [1] "R version 4.5.1 (2025-06-13)"O termo cadeia de Markov é empreguado quando o espaço de estados é discreto. A informação mais frequentemente procurada num modelo deste tipo é a probabilidade de estar num determinado estado ou subconjunto de estados num determinado momento após o sistema se tornar operacional.
1.2. Propriedades
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 1.2. Isso permitirá encontrar propriedades, que veremos a continuação, estudando o conceito de probabilidade de transição.
Definição 1.5: 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 \[ P(C_{t+1}=y \, | \, C_t=x), \] 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 agora e doravante, presume-se que a probabilidade de transição é independente do tempo.
Definição 1.6: 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 \[ P(C_{t+1}=y \, | \, C_t=x) \, = \, P(C_1=y \, | \, C_0=x), \] 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.
Exemplo 1.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áfico representativo na Figura 1.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 for 1, permanece nele com probabilidade \(1-\beta\) e muda para 0 com probabilidade \(\beta\).
Figura 1.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 \[ P(C_{n+1}=1 \, | \, C_n=0) \, = \, \alpha, \qquad \qquad P(C_{n+1}=0 \, | \, C_n=1) \, = \, \beta, \] e \[ P(C_0=0) \, = \, \pi_0(0)\cdot \]
Dado que há somente dois estados 0 e 1, segue que \[ \begin{array}{c} P(C_{n+1}=0 \, | \, C_n=0) \, = \, 1-\alpha, \\[0.8em] 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 \[ \pi_0(1) \, = \, P(C_0=1) \, = \, 1-\pi_0(0)\cdot \]
A partir desta informação, podemos calcular \(P(C_n = 0)\) e \(P(C_n = 1)\). Observamos que \[ \begin{array}{rcl} P(C_{n+1}=0) & = & P(C_n=0, \, C_{t+1}=0) \, + \, P(C_n=1, \, C_{n+1}=0)\\[0.8em] & = & P(C_n=0)P(C_{n+1}=0 \, | \, C_n=0) \, + \, P(C_n=1)P(C_{n+1}=0 \, | \, C_n=1) \\[0.8em] & = & (1-\alpha) P(C_n=0) \, + \, \beta P(C_n=1) \\[0.8em] & = & (1-\alpha) P(C_n=0) \, + \, \beta\big(1-P(C_n=0) \big) \\[0.8em] & = & (1-\alpha-\beta)P(C_n=0) \, + \, \beta\cdot \end{array} \]
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 \[ P(C_1=0) \, = \, (1-\alpha-\beta)\pi_0(0) \, + \, \beta\cdot \]
No caso trivial de \(\alpha=\beta= 0\) é claro que para todo \(n\) \[ P(C_n=0) \, = \, \pi_0(0) \qquad \text{e} \qquad P(C_n=1) \, = \, \pi_0(1)\cdot \] Suponhamos agora que \(\alpha+\beta > 0\).
Então, pela expressão da soma de uma progressão geométrica, \[ \sum_{k=0}^{n-1} (1-\alpha-\beta)^k \, = \, \dfrac{1-(1-\alpha-\beta)^k}{\alpha+\beta}\cdot \]
Concluímos que \[ P(C_n=0) \, = \, \dfrac{\beta}{\alpha+\beta}+(1-\alpha+\beta)^n\left( \pi_0(0)-\dfrac{\beta}{\alpha+\beta}\right), \] por consequência que \[ P(C_n=1) \, = \, \dfrac{\alpha}{\alpha+\beta}+(1-\alpha+\beta)^n\left( \pi_0(1)-\dfrac{\alpha}{\alpha+\beta}\right)\cdot \]
Suponha agora \(\alpha\) e \(\beta\) não sejam ambas zero nem ambas um. Então, \(0< \alpha+\beta <2\), o qual implica que \[ |1-\alpha-\beta| \leq 1\cdot \] Neste caso, podemos fazer \(n\to\infty\) nas expressões acima e concluímos que \[ \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 \]
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 \[ \pi_0(0) \, = \, \dfrac{\beta}{\alpha+\beta} \qquad \mbox{e} \qquad \pi_0(1) \, = \, \dfrac{\alpha}{\alpha+\beta}\cdot \] Então, se a cadeia \(\{C_n\}\) tiver como distribuição inicial \[ P(C_0=0) \, = \, \dfrac{\beta}{\alpha+\beta} \qquad \mbox{e} \qquad P(C_0=1) \, = \, \dfrac{\alpha}{\alpha+\beta}, \] temos, para todo \(n\), que \[ P(C_n=0) \, = \, \dfrac{\beta}{\alpha+\beta} \qquad \mbox{e} \qquad P(C_n=1) \, = \, \dfrac{\alpha}{\alpha+\beta}\cdot \]
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 for satisfeita, contudo, então \[ P(C_2=c_{_2} \, | \, C_0=c_{_0}, C_1=c_{_1}) \, = \, P(C_2=c_{_2} \, | \, C_1=c_{_1}), \] a qual é determinada por \(\alpha\), \(\beta\) e \(\pi_0(0)\). Neste caso \[ 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 \]
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}\).
\[ \begin{array}{ccc|c}\hline c_0 & c_1 & c_2 & P(C_0=c_0, C_1=c_1,C_2=c_2) \\[0.8em]\hline 0 & 0 & 0 & \pi_0(0)(1-\alpha)^2 \\[0.4em] 0 & 0 & 1 & \pi_0(0)(1-\alpha)\alpha \\[0.4em] 0 & 1 & 0 & \pi_0(0)\alpha\beta \\[0.6em] 0 & 1 & 1 & \pi_0(0)\alpha(1-\beta) \\[0.6em] 1 & 0 & 0 & (1-\pi_0(0))(1-\alpha)\beta \\[0.6em] 1 & 0 & 1 & (1-\pi_0(0))\alpha\beta \\[0.6em] 1 & 1 & 0 & (1-\pi_0)(1-\beta)\beta \\[0.6em] 1 & 1 & 1 & (1-\pi_0(0))(1-\beta)^2 \\\hline \end{array} \]
1.3. Características
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.
1.3.1. Função de transição
Pela Definição 1.3 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 1.7: 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 \[ p_{x,y} \, = \, P(C_{1}=y \, | \, C_0=x), \qquad x,y\in S, \] é chamada de função de transição da cadeia.
Em particular, dado que a cadeia satisfaz as exigências da Definição 1.2, de cadeia estacionária, podemos escrever que \[ P(C_{t+1}=y \, | \, C_t=x) \, = \, p_{x,y}, \qquad t\geq 1\cdot \] Agora, pela propriedade Markoviana, temos que \[ P(C_{t+1}=y \, | \, C_0=c_0,\cdots,C_{t-1}=c_{t-1},C_t=x) \, = \, p_{x,y}\cdot \]
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 1.1.
Seja \(\{C_t \, : \, t\in \mathbb{N}\}\) uma Cadeia de Markov estacionária com espaço de estados \(S\) e função de transição \(p\). Então \[ p_{x,y}\geq 0, \qquad x,y\in S \] e \[ \sum_{y\in S} p_{x,y} \, = \, 1, \qquad x\in S\cdot \]
Demonstração.
Exercício.Observe que, na segunda afirmação do teorema acima o estado inicial \(x\) é fixo e os estados de chegada são todos os \(y\in S\), nada afirma-se acerca da probabilidade \(\sum_{x\in S} p_{x,y}\).
Exemplo 1.2: Cadeia com dois estados.
Continuando com o Exemplo 1.1 percebemos que a função de transição, segundo a descrição no texto é \[ 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 \]
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 1.1.
Os resultados que serão apresentados aqui 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.
1.3.2. 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 1.8: 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 \[ \pi_0(x) \, = \, P(C_{0}=x), \qquad x\in S, \] é 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.2, 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 \[ \pi_0(x)\geq 0, \qquad x\in S \] e \[ \sum_{x\in S} \pi_0(x) \, = \, 1\cdot \]
A distribuição conjunta de \(\{C_0,C_1,C_2\}\) pode ser expressa em termos da função de transição e da distribuição inicial. Por exemplo, \[ 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 \]
Também \[ \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}) \\ & = & \pi_0(c_{_0})p_{c_{_0},c_{_1}}P(C_2=c_{_2} \, | \, C_0=c_{_0}, C_1=c_{_1})\cdot \end{array} \]
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 1.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 \[ 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 \]
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 1.2.
Seja \(\{C_n\}\) uma Cadeia de Markov em \(S\) com função de transição \(p\). Então, podemos escrever a função de probabilidade conjunta de \(C_0,C_1,\cdots,C_n\) como \[ 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 \]
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 \[ p_{x,y}\geq 0, \qquad x,y\in S \] e \[ \sum_{y\in S} p_{x,y} \, = \, 1, \qquad x\in S\cdot \]
Dizemos que \(\pi_0(x)\), \(x\in S\), é a probabilidade inicial da cadeia se satisfaz \[ \pi_0(x)\geq 0, \qquad x\in S \] e \[ \sum_{x\in S} \pi_0(x) \, = \, 1\cdot \]
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 1.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 1.2, a chamada propriedade de Markov, não está bem definida, se \[ P(C_0=c_0,\cdots,C_n=c_n) \, = \, 0\cdot \] 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 1.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 1.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\).
1.3.3. 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 \[ \tag{1.1} \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} \] de elementos as probabilidades de transição entre os estados, escritas como \[ p_{x,y} \, = \, P(C_1=y \, | C_0=x), \qquad x,y\in S\cdot \]
Definição 1.8: Matriz de probabilidades 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 1.3: Cadeia com dois estados.
No Exemplo 1.1, a matriz \(\mathcal{P}\) de probabilidades de transição no caso de uma cadeia com dois estados foi considerada da forma: \[ \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} \] significando que \(s_{_1}=0\) e \(s_{_2}=1\).
Teorema 1.3.
Seja \(\{C_n\}\) uma Cadeia de Markov em \(S= \{s_{_1}, s_{_2}, s_{_3},\cdots, s_{_d}\}\) estacionária com função de transição \(p\). A matriz \(\mathcal{P}=\big(p_{x,y}\big)\), de probabilidades de transição, satisfaz as seguintes propriedades:
\(p_{x,y}\geq 0\), quaisquer sejam \(x,y\in S\).
\(\displaystyle \sum_{y\in S} p_{x,y} \, = \, 1\).
Demonstração.
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 \[ P\big(C_{n+1}\in S \big) \, = \, P\big(C_{n+1}\in S \, | \, C_n=x \big) \, = \, 1 \] e, dado que os eventos, \(\{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 estados na próxima vez. Geralmente uma matriz quadrada satisfazendo estas duas propriedades se disse que ser 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.
1.4. Exemplos
Vamos rever a seguir alguns exemplos clássicos de Cadeias de Markov e alguns outros para ilustrar os conceitos e resultados da teoria geral.
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 1.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\).
Esta cadeia foi representada na Figura 1.1.
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}\).
Como o Exemplo 1.1 mostrou, em algumas situações justifica-se a construção de cadeias com variáveis aleatórias independentes.
Exemplo 1.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 sequência \(C_n=\xi_n\) é uma Cadeia de Markov com probabilidades de transição \[ P(C_{n+1}=c_{_{n+1}} \, | \, C_n=c_{_n}) \, = \, P(C_{n+1}=c_{_{n+1}}) \, = \, \alpha_{n+1}\cdot \] Recordemos que as variáveis são independentes, isto é, a matriz de probabilidades de transição é da forma \[ \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} \]
A sequência \(C_n = \max\{\xi_1,\xi_2,\cdots,\xi_n\}\) é uma Cadeia de Markov com matriz de probabilidades de transição da forma \[ \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 & 3 & \cdots \\ \alpha_0 & \alpha_1 & \alpha_2 & \alpha_3 & \cdots \\ \alpha_0 & \alpha_0+\alpha_1 & \alpha_2 & \alpha_3 & \cdots \\ \alpha_0 & \alpha_0 & \alpha_0+\alpha_1+\alpha_2 & \alpha_3 & \cdots \\ \vdots & \vdots & \vdots & \vdots & \vdots \end{matrix} \hspace{-0.2em} \begin{matrix} & \\ \left. \vphantom{ \begin{matrix} 12 \\ 12 \\ 12 \\ 12 \\ 12 \end{matrix} } \right)\cdot \end{matrix} \] Observemos que, por exemplo, \[ P(C_{n+1}=0 \, | \, C_n=0) \, = \, P(\max\{\xi_1,\cdots,\xi_{n+1}\}=0 \, | \, C_n=0), \] dado que \(C_{n+1}=\max\{\xi_1,\cdots,\xi_{n+1}\}=\max\{C_n,\xi_{n+1}\}\), temos então que \[ P(\max(C_n,\xi_{n+1})=0 \, | \, C_n=0) \, = \, P(\xi_{n+1}=0) \, = \, \alpha_0\cdot \]
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{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} \] Uma situação particular desta cadeia é conhecida 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 1.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 assume a forma: \[ \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} \]
O grafo correspondente a esta matriz é mostrado na Figura 1.2 abaixo. Vamos explicar agora o procedimento para encontrarmos esta matriz.
Figura
1.2. Grafo das probabilidades de transição do Fast-food.
Neste caso, \(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 criana 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 esteja 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, ela 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 pode ser utilizada 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.
A partir deste preceito básico, diversas empresas se desenvolveram, chegando algumas a valer bilhõ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.
Exemplo 1.7: Google PageRank, o 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.
O Google utilizou o algoritmo PageRank para classificar as páginas da web em um resultado de pesquisa até 24 de setembro de 2019. O algoritmo foi desenvolvido por Larry Page e Serguey Brin e o nome “PageRank” foi dado em homenagem a Larry Page. O PageRank é um dos métodos que o Google utiliza para determinar a relevância ou importância de uma página.
Para aplicar o algoritmo PageRank, consideramos a web como um grafo direcionado, onde as páginas da web são nós e os hiperlinks são arestas. O PageRank classifica as páginas com base no número de backlinks que apontam para essa página. Uma página com links para muitas páginas recebe uma classificação alta. Para descobrir a pontuação da página, deve-se considerar que o internauta pode selecionar qualquer página. No entanto, nem sempre as páginas são selecionadas sequencialmente. Na maioria das vezes, um internauta seguirá os links de uma página sequencialmente, ou seja, a partir de uma página \(i\), o internauta seguirá os links de saída e seguirá para um dos vizinhos de \(i\). Mas isso pode não acontecer sempre.
Em uma porcentagem menor, porém positiva, das vezes, o internauta abandona a página atual e escolhe arbitrariamente uma página diferente da web e se teletransporta para lá. Para levar em conta essa situação, Page e Brin introduziram um fator denominado fator de amortecimento \(d\), que reflete a probabilidade de o internauta abandonar a página atual e se teletransportar para uma nova. Como ele pode se teletransportar para qualquer página da web, cada página tem \(1/n\) de probabilidade de ser escolhida (Rai and Lal 2016).
Primeiramente, a versão simplificada do algoritmo PageRank é definida abaixo:
A matriz de probabilidades de transição para a Cadeia de Markov cujo grafo é apresentado na Figura 1.3 (a) é \[ \begin{matrix} & \\ \mathcal{P} = \begin{matrix} 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} 1 & 2 & 3 & 4 & 5 \\ 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 \end{matrix} \hspace{-0.2em} \begin{matrix} & \\ \left. \vphantom{ \begin{matrix} 12 \\ 12 \\ 12 \\ 12 \\ 12 \end{matrix} } \right)\cdot \end{matrix} \]
Suponha que o internauta navega por páginas da Web em um universo de cinco páginas, como mostrado na Figura 1.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, a 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.
Figura
1.3. Grafo das probabilidades de transição num buscador.
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 será selecionada 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 Capítulo 5. O tamanho do espaço de estados nessa Cadeia de Markov é de bilhões de páginas e no Exemplo 1.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 de Langville and Meyer (2011).
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, a página 2 na Figura 1.3 (a). O método, no entanto, não é suficiente para assegurar que a Cadeia de Markov seja irredutível (Seção 3.3) e aperiódica (Seção 4.5). Por exemplo, na Figura 1.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 (Capítulo 4).
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 et al. (1998) e mais recentemente no livro Langville and Meyer (2011), dentre outros.
Paul Ehrenfest (1880 - 1933), foi um físico austríaco 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 1.8: Cadeia de Ehrenfest.
O seguinte constitui um modelo simples de intercambio de calor ou de moléculas de gás entre dois corpos isolados. Suponha que temos duas caixas 1 e 2, e bolas identificadas (rotuladas) como \(1,2,\cdots,d\). Inicialmente, algumas dessas bolas estão na caixa 1 e as restantes estão na caixa 2. Um número 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 será 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\}\) será 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: \[ 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 \]
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 1.9: Experiência de criação de plantas.
Um botânico está estudando uma certa variedade de plantas que é monóica, ou seja, tem órgãos masculinos e femininos em flores 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 outropai. 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\} \mbox{ e } \{aa, aa\}\cdot \]
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
1.4. A geração que segue \(\{Aa,
Aa\}\), grafo do estudo botânico.
Se o estado atual for \(\{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 calcular primeiro a probabilidade de uma prole dada ter cada um dos três genótipos. A Figura 1.4 acima ilustra a possível prole neste estado. Cada seta que vai para baixo na Figura 1.4 é uma possível herança de um alelo e cada combinação de setas que termina em em 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\). A matriz de transição, que pode ser verificada de forma semelhante àquela que acabamos de fazer:
\[ \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} \]
Exemplo 1.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 for 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 existir um estoque não zero, não haverá 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 será 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 seu funcionamento deve ser de 2 u.m. e, portanto, no final do dia, o estoque é zero ou 1 u.m.. No primeiro caso, o processo será repetido da mesma maneira. No último caso, a produção do dia seguinte será zero e, portanto, no final deste dia, o estoque será zero; neste caso o processo será repetido da mesma maneir ou haverá ordens insatisfeitas de 1 u.m..
No último caso, a produção do dia seguinte será 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, existem 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{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} \]
Exemplo 1.11: Potencial humano.
Descrevemos a aplicação de cadeias de Markov na previsão do potencial humano em uma empresa de serviços de TIC do Condado de Medımurje, Croácia. A referida empresa possui três departamentos: Programação, Departamento Executivo e Gerente e Negócios Gerais. Este exemplo foi apresentado no artigo de Hrustek, Kecek, and Polgar (2020).
A Programação contrata funcionários responsáveis pela programação e designers. O Departamento Executivo contrata engenheiros e gerentes subordinados ao diretor executivo. O Gerente e Negócios Gerais contrata um gerente, seu assistente e consultor, vários funcionários individuais em determinadas funções, contador, gerente de potencial humano, secretária e faxineiro.
A Tabela 1 apresenta a entrada e saída de funcionários nos três departamentos da empresa de TIC ao longo de um ano. Em 31 de julho de 2018, a Programação contava com 25 funcionários, o Departamento Executivo com 16 funcionários e o Gerente e Negócios Gerais com um gerente e 20 funcionários. No início do período pesquisado, a empresa contava com 62 funcionários.
Ao longo do ano pesquisado, os funcionários foram reestruturados devido ao trabalho em um novo projeto, o que resultou na mudança de local de trabalho de 12 funcionários para maximizar o efeito do trabalho. Além disso, 50 funcionários permaneceram nos mesmos cargos. Em 31 de julho de 2019, a Programação contava com 26 funcionários, o Departamento Executivo com 18 funcionários e a Gerência e Negócios Gerais com um gerente e 17 funcionários. Ao final do período pesquisado, a empresa contava com 62 funcionários.
\[ \begin{array}{l|ccc|c}\hline \mbox{Movimentação } & & \mbox{Departamento} & \mbox{Gerência e } & \\ \mbox{do número de trabalhadores} & \mbox{Programação} & \mbox{Executivo} & \mbox{Negócios Gerais} & \mbox{Total} \\\hline\hline \mbox{Estado (julho de 2018)} & 25 & 16 & 21 & 62 \\ \mbox{Saída de trabalhadores} & 3 & 3 & 6 & 12 \\ \mbox{Permanência nos mesmos cargos} & 22 & 13 & 15 & 50 \\ \mbox{Entrada de novos trabalhadores} & 4 & 5 & 3 & 12 \\ \mbox{Estado (julho de 2019)} & 26 & 18 & 18 & 62 \\\hline \end{array} \]Tabela 1.1: Fluxo de entrada e saída de trabalhadores nos três departamentos da empresa de TIC.
A Tabela 1.2 apresenta a estrutura de entrada e saída de trabalhadores na referida empresa ao longo do período pesquisado, de 31 de julho de 2018 a 31 de julho de 2019. As colunas mostram a entrada de trabalhadores devido à transição para outros departamentos e as linhas apresentam a saída de trabalhadores devido à transição para outros departamentos.
\[ \begin{array}{l|ccc|c}\hline \mbox{Departamentos} & & \mbox{Departamento } & \mbox{Gerência e } & \\ & \mbox{Programação} & \mbox{Executivo} & \mbox{Negócios Gerais} & \mbox{Total} \\\hline\hline \mbox{Programação} & 0 & 1 & 2 & 3 \\ \mbox{Departamento Executivo} & 2 & 0 & 1 & 3 \\ \mbox{Gerência e Negócios Gerais} & 2 & 4 & 0 & 6 \\ \mbox{Total} & 4 & 5 & 3 & 12 \\\hline \end{array} \]Tabela 1.2: Estrutura de entrada e saída de funcionários em empresa de TIC.
Ao prever o número de trabalhadores em departamentos individuais após o período de três anos e com base nos dados das Tabelas 1.1–1.2, a aplicação da Cadeia de Markov começa com a obtenção de um vetor de estado inicial cujos elementos são iguais à razão entre o número de funcionários em cada departamento ao final do período pesquisado (31 de julho de 2019) e o número total de funcionários na empresa. O vetor de estado inicial para a empresa pesquisada é: \[ (3/12,3/12,6/12)=(1/4,1/4,1/2)\cdot \]
1.5. Exercícios
- 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{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} \]
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.
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: \[ C_n \, = \, \rho C_{n-1}+\xi_n, \qquad C_0 \, = \, 0, \] 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 é, \[ \overline{C}_n \, = \, \dfrac{1}{n}\big( C_1+C_2+\cdots+C_n\big)\cdot \]
É \(\{\overline{C}_n\}\) um processo de Markov?
Se a resposta à primeira parte for 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\), \[ 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), \] 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\) saiu cara, jogamos uma moeda honesta; se nele saiu 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 será colocada de volta na urna, caso contrário ela será deixada de fora. Considere \(C_n\) o número de bolas pretas restantes na urna após a \(n\)-ésima retirada da urna.
É \(\{\overline{C}_n\}\) um processo de Markov? Se assim for, encontrar as probabilidades de transição adequados e faça o grafo correspondente.
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 2.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 será o espaço de estados? Qual será a matriz de probabilidades de transição?
Para uma Cadeia de Markov \(\{C_n\}\), prove que \[ 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) \] quaisquer sejam \(n_{_1}< n_{_2} < \cdots < n\).
Prove as expressões das matrizes de transição no Exemplo 2.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.
Se o aluno está atrasado em um determinado dia, qual será a probabilidade de que ele vai estar na hora em cada um dos próximos três dias?
Se o aluno está no tempo em um determinado dia, qual será 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% são profissionais, 10% sâo trabalhadores qualificados e 10% são trabalhadores não qualificados. No caso dos filhos de trabalhadores qualificados, 60% são hábeis trabalhadores qualificados, 20% são profissionais e 20% são trabalhadores não qualificados. Finalmente, no caso de operários não qualificados, 50% dos filhos são operários não qualificados e 25% 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 probabilidade 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 \[ p_{0,1} \, = \, 1, \qquad p_{M,M-1} \, = \, 1 \] e, para \(x=1,2,\cdots,M-1\), \[ p_{x,x-1} \, = \, 1-\alpha, \qquad p_{x,x+1} \, = \, \alpha, \qquad \mbox{com} \qquad 0 < \alpha < 1\cdot \] 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 partes 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 \[ 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 \]