\(\newcommand{\prob}{\operatorname{P}}\) \(\newcommand{\e}{\operatorname{e}}\)

Simulação de Processos

Simulaçao de variável aleatória de Poisson:

Variável aleatória de Poisson:

A variável aleatória \(X\), com contra-domínio no conjunto dos números naturais \(\mathbb{N}\), tem distribuição de Poisson com parâmetro \(\lambda, ~ \lambda >0\) se sua função de probabilidade é dada por: \[ p_i = \prob\{X=i\}= \frac{\e^{-\lambda}\lambda^i}{i!}, ~ i=1,2, \dots. \]

As variáveis aleatórias são utilizadas em uma ampla gama de aplicações. Essas variáveis aleatórias são usadas para a distribuição do número de sucessos em uma quantidade grande de tentativas (consideradas independentes ou, pelo menos, fracamente dependentes), com probabilidade de sucesso pequena. Suponha que \(X\) seja uma variável aleatória binomial com parâmetros \((n,p)\), representando a quantidade de sucessos em \(n\) tentativas independentes, com probabilidade de sucesso \(p\) e seja \(\lambda = np\). Então: \[\begin{align} \prob\{X = i \} & = \frac{n!}{(n-i)! i!} p^i(1-p)^{n-i} \\ & = \frac{n!}{(n-i)! i!} \left( \frac{\lambda}{n}\right) ^i \left( 1 - \frac{\lambda}{n}\right) ^{n-i}\\ & = \frac{n(n-1)\dots (n-i+1)}{n^i} \frac{\lambda^i }{i!} \frac{(1-\frac{\lambda}{n})^n}{ (1-\frac{\lambda}{n})^i} \end{align}\]

Para \(n\) grande e \(p\) pequeno,

\[ \left(1-\frac{\lambda}{n} \right)^n \approx \e^{-\lambda}, \quad \frac{n(n-1) \dots (n-i+1)}{n^i} \approx 1, \quad \left(1 - \frac{\lambda}{n} \right)^i \approx 1. \]

Portanto, para \(n\) grande e \(p\) pequeno. \[ \prob\{X = i \} \approx \frac{\e^{-\lambda} \lambda^i}{i!} \]

A média e a esperança de uma variável aleatória binomial \(Y\) são: \[ \operatorname{E}(Y) = np, \quad \operatorname{Var}(Y)= np(1-p) \approx np \quad \text{para } p \text{ pequeno.} \]

Dada a relação entre as variáveis aleatórias binomial e de Poisson é intutitivo que, para uma variável aleatória de Poisson, \(X\), com parâmetro \(\lambda\). \[ \operatorname{E}(X) = \operatorname{Var}(X) = \lambda. \]

Eventualmente, pode ser útil usar a fórmula recursiva abaixo para calcular probabilidades da distribuição de Poisson: \[\begin{align} \frac{p_{i+1}}{p_i} = \frac{\frac{\e^{-\lambda} \lambda^{i+1}}{(i+1)!}}{ \frac{\e^{-\lambda}\lambda^{i}}{i!}} = \frac{\lambda}{i + 1} \end{align}\]

ou, equivalentemente, \[ \tag{*} p_{i+1} = \frac{\lambda}{i+1}p_i, ~ i\geq 0 \]

Gerador de variável aleatória de Poisson:

Para usar o método da transformação inversa na construção de um gerador de números aleatórios de uma variável aleatória de Poisson, \(X\), com média \(\lambda\) a chave é o da expressão recursiva acima \(\tag{*}\). No algoritmo proposto abaixo, \(p=p_i = \prob\{X = i \}\) e \(F = F(i) = \prob\{X \leq i \}\).

Algoritmo:

Passo 1- Gerar um número aleatório \(U \sim \mathcal{U}(0,1)\).

Passo 2 - Ajustar \(i=0\), \(p = \e^{-\lambda}\) e \(F=p\).

Passo 3- Se \(U < F\), faça \(X = i\) e pare.

Passo 4- Ajustar \(p = \frac{\lambda p}{(i+1)}\), \(F = F + p\), \(i = i + 1\) (aumente uma unidade no valor de \(i\)).

Passo 5 - Retorne ao passo 3.

No passo 3, verifica-se \(U < \e^{-\lambda}=p_0\). Caso positivo, o valor gerado é \(X=0\). Caso negativo, computa-se \(p_1\) usando-se a recursão, retorna-se ao passo 3, comparando com o valor \(U\) gerado anterioremente da uniforme. Se \(U < p_0 + p_1\), \(X=!\), caso contrário, faz-se novamente a recursão e o algoritmo prossegue.

O algoritmo acima verifica sucessivamente se o valor da Poisson é \(0\), e é \(1\), se é \(2\) e assim por diante. Portanto, a quamtidade de comparações será o valor gerado \(X\) mais um, ou seja, em média o procedimento necessitará fazer \(\lambda +1\) buscas. Isso pode ser um problema quando \(\lambda\) é alto. Como os valor mais provável de uma Poisson é um dos dois inteiros mais próximos de \(\lambda\), um algoritmo mais eficiente verificaria primeiro um desses valors , ao invés de iterar a partir do zero. Verifique o Algoritmo 4.1, apresentado no Apêndice de Programas e explicado na seção 4.2 de Ross (2006).

Simulação de um processo de Poisson:

Processo de Poisson homogêneo:

Suponha que eventos estejam ocorrendo ao acaso em um intervalo de tempo \([0, t]\) qualquer. Seja \(N(t)\) os eventos que ocorrem nesse intervalo de tempo. Esses eventos constituem um processo de Poisson com taxa \(\lambda\), \(\lambda >0\) se:

1. \(N(0) = 0\), ou seja, o processo é iniciado no instante \(0\).

2. A quantidade de eventos ocorrendo em intervalos de tempos mutuamente exclusivos são independentes. Essa é a suposição de incrementos independentes, que estabelece que o número de eventos que ocorrem até o instante \(t\) (\(N(t)\)) é independente do número de eventos entre os instantes \(t\) e \(t+s\) (\(N(t+s) - N(t)\))

3. A distribuição do número de eventos que ocorrem em um dado intervalo depende somente do comprimento do intervalo a não de sua posição. Essa é a suposição de incrementos estacionários que estabelece que a distribuição de probabilidade de \(N(t+s) - N(t)\) é a mesma para qualquer valor de \(t\)

4. Em um pequeno intervalo de tempo \(h\) a probabilidade de um evento ocorrer é aproximadamente \(\lambda h\), ou seja quando \(h \to 0\) a probabilidade de ocorrer um evento tende a um valor \(\lambda\): \[\begin{equation} \lim_{h\to 0} \prob \left \{\frac{N(h)=1}{h} \right\}=\lambda \end{equation}\]

5. Em um pequeno intervalo de tempo \(h\), a probabilidade de ocorrerem dois ou mais eventos é aproximadamente \(0\): \[ \lim_{h\to 0} \prob\left\{\frac{N(h) \geq 2}{h} \right \}=0 \]

Essas suposições implicam que o número de eventos ocorrendo em um intervalo de tempo \(t\) é uma variável aleatória de Poisson com média \(\lambda t\). A prova pode ser encontrada em Ross (2009), página 494.

Seja agora \(X_1\), o instante da ocorrência do primeiro evento e, para \(n>1\), \(X_n\) denota o tempo transcorrido entre o (n-1)-ésimo e o n-ésimo evento. A sequência \(\{X_n, ~ n=1, 2, \dots \}\) é denominada a sequência dos tempos entre chegada. por exemplo, se \(X_1 = 5\) e \(X_2 = 10\), então o primeiro evento ocorreu no instante de tempo 5 e o segundo, 15. Note que o evento \(\{X_1 > t \}\) ocorre se, e somente se, não tenha ocorrido nenhum evento no intervalo \([0, t]\), ou seja:

\[ \prob\{ X_1 > t \} = \prob\{N(t) = 0\} = \e^{-\lambda t} \] e, portanto, \(X_1\) tem distribuição exponencial com média \(1/ \lambda\). Para obter a distribuição de \(X_2\), note que:

\[\begin{align} \prob \{X_2 > t | X_1 = s \} & = \prob \{0 \text{ eventos em } (s, s+t]~ | ~ X_1 = s) \} \\ & = \prob\{N(s +t) - N(s) = 0 \} \\ & = \e^{-\lambda t} \end{align}\]

As últimas duas equações levam em conta suposições de incrementos independentes e estacionários do processo de Poisson. Conclue-se assim que a distribuição de \(X_2\) também é uma exponencial com média \(1/ \lambda\) e, também, que \(X_2\) é independente de \(X_1\). Pode-se provar que:

Os tempos entre chegadas de um processo de Poisson, \(X_1, X_2, \dots\), são independentes e identicamente distribuídos, de acordo a uma variável aleatória exponencial com parâmetro \(\lambda\).

A prova pode ser encontrada em Ross (2006).

Seja \(S_n\) o instante da ocorrência no n-ésimo evento, \(S_n = \sum_{i=1}^n X_i\). \(S_n\) será menor ou igual a \(t\) se, e somente se, tiver ocorrido pelo menos \(n\) eventos até o tempo t, ou seja: \[\begin{align} \prob\{S_n \leq t \} & = \prob \{N(t) \geq n \} & = \sum_{j=n}^\infty \e^{-\lambda t} \frac{(\lambda t)^j}{j!} \end{align}\]

Essa é a expressão da função de ditribuição acumulada de \(S_n\). Derivando-a em relação a \(t\), obtemos a função de densidade de probabilidade de \(S_n\), \(f_{S_n}(t)\):

\[\begin{align} f_{S_n}(t) & = \sum_{j=n}^\infty (-\lambda) \e^{-\lambda t} \frac{(\lambda t)^{j}}{j!} \\ & = \sum_{j=n}^\infty \lambda \e^{-\lambda t} \frac{(\lambda t)^{j-1}}{(j-1)!} - \sum_{j=n}^\infty \lambda \e^{-\lambda t} \frac{(\lambda t)^j}{j!} \\ & = \lambda \e^{-\lambda t} \frac{(\lambda t)^{n-1}}{(n-1)!} \end{align}\]

Portanto, o instante de ocorrência do n-ésimo evento de um processo de Poisson com taxa \(\lambda\) é uma variável aleatória gama com parâmetros \((n, \lambda)\).

Distribuição condicional dos instantes de chegada:

Suponha que no instante \(t\) ocorreu exatamente um evento de um processo de Poisson. Desejamos determinar a distribuição do tempo no qual o evento ocorreu. Como o processo de Poisson possui incrementos estacionários e independentes, parece razoável que cada intervalo de igual amplitude \([0, t]\) tenha a mesma probabilidade de conter o evento. Em outras palavras, o instante de ocorrência do evento deveria ser uniformemente distribuído sobre \([0, t]\). Isso pode ser verificado, desde que, para \(s\leq t\):

\[\begin{align} \prob\{X_1 < s| N(t) = 1 \} & = \frac{\prob \{X_1 < s, N(t) = 1\}}{ \prob \{ N(t) = 1 \} } \\ & = \frac{\prob \{N(s) = 1, ~ N(t) - N(s) = 0\}}{ \prob\{ N(t) = 1 \} } \\ & = \frac{\lambda s \e^{-\lambda s} \e^ {- \lambda(t-s)} }{ \lambda t \e^{-\lambda t} } \\ & = \frac{s}{t} \end{align}\]

Este resultado pode ser generalizado, mas antes necessitamos apresentar o conceito de estatísticas de ordem.

Sejam \(Y_1, Y_2, \dots Y_n\) uma sequência de variáveis aleatórias contínuas independentes e identicamente distribuídas com função de densidade de probabilidade \(f\). Sua função de densidade de probabilidade conjunta é dada por: \[ f(y_1, y_2, \dots, y_n) = f(y_1) f(y_2) \dots f(y_n) = \prod_{i=1}^nf(y_i) \]

Dizemos que \(Y_{(1)}, Y_{(2)}, \dots, Y_{(n)}\) são as estatísticas de ordem correspondentes da sequência \(\{Y_i, i= 1, 2, \dots, n\}\), se \(Y_{(1)} \leq Y_{(2)} \leq \dots \leq Y_{(n)}\), ou seja, \(Y_{(k)}\) é 0 k-ésimo valor ordenado daquela sequência. A função de densidade de probabilidade conjunta das estatísticas de ordem é dada por: \[ f(y_1, y_2, \dots, y_n) = n! \prod_{i=1}^nf(y_i), ~ y_1 < y_2 < \dots < y_n \]

pois:

1. O vetor aleatório \((Y_{(1)}, Y_{(2)}, \dots, Y_{(n)})\) será igual a \(y_1, y_2, \dots, y_n\) se \(Y_1, Y_2, \dots, Y_n\) for igual a qualquer das \(n!\) permutações de \((y_1, y_2, \dots, y_n)\).

2. Se \((Y_1, Y_2, \dots, Y_n) = (y_{i_1}, y_{i_2} \dots, y_{i_n})\) é uma permutação de \(y_1, y_2, \dots, y_n\) sua função de densidade de probabilidade conjunta é dada por: \[ f(y_{i_1}) f(y_{i_2}) \dots f(y_{i_n}) = \prod_{i=1}^nf(y_i) \]

Por exemplo, seja \(\{Y_i, i=1, 2, \dots n \}\) uma sequência de variáveis aleatórias independentes e identicamente distribuídas de acordo com uma distribuição uniforme, no intervalo \((0,t)\). Então, a função de densidade conjunta de suas estatísticas de ordem \(Y_{(1)}, Y_{(2)}, \dots, Y_{(n)}\) é: \[ f(y_1, y_2, \dots, y_n) = \frac{n!}{t^n},~ 0 <y_1 < y_2 < \dots < y_n < t. \]

Teorema:

Os \(n\) tempos de chegadas \(S_1, S_2, \dots, S_n\), dado \(N(t) = n\), têm a distribuição das estatísticas de ordem correspondentes a \(n\) variáveis aleatórias uniformemente distribuídas no intervalo \((o, t)\).

Prova:

Vamos determinar a função de densidade condicional de \(S_1, S_2, \dots, S_n\), dado que \(N(t) = n\). Seja \(0 < t_1 < t_2 < \dots < t_{n+1}=t\) e seja \(h_i\) pequeno o suficiente de maneira que \(t_i + h_i < t_{i+1}, ~i=1, 2, \dots, n\). Assim: \[\begin{align} & \prob\left\{t_i \leq S_i \leq t_{i} + h_i, i = 1, 2, \dots , n ~ | ~ N(t) =n \right\} = \\ & = \frac{\prob\left( \bigcup_{i=1}^n \{ N(t_i+h_i) - N(t_i)=1 \} \cap \bigcup_{i=1}^n \{ N(t_i) - N(t_{i-1}+ h_{i-1}) = 0 \} \right) }{\prob\{N(t)=n\}} \\ & = \frac{\lambda h_1 \e^{-\lambda h_1} \lambda h_2 \e^{-\lambda h_2}\dots \lambda h_n \e^{-\lambda h_n} ~ \e^{-\lambda(t - h_1 - h_2 - \dots - h_n)}}{ \frac{\e^{-\lambda t}(\lambda t)^n}{n!} } = \frac{n!}{t^n}h_1 h_2 \dots h_n \end{align}\]

Fazendo \(h_i \to 0\), obtemos a função de densidade de probabilidade condicional de \(S_1, S_2, \dots, S_n\), dado \(N(t) = n\), que é: \[ f(t_1, t_2, \dots, t_n) = \frac{n!}{t^n} \]

que completa a prova.

Dizemos que, sob a condição de \(n\) eventos ocorrerem no intervalo \((0, t)\), as variáveis aleatórias associadas aos instantes de sua ocorrência, \(S_1, S_2, \dots, S_n\), estão distribuídas independente e uniformemente no intervalo \((0,t)\).

Gerador de processo de Poisson homogêneo:

Suponha que se deseja gerar os primeiros \(n\) eventos de uma processo de Poisson homogêneo, com taxa \(\lambda\). Uma primeira alternativa seria usar a propriedade de que os tempos entre sucessivos eventos desse processo são variáveis aleatórias independentes exponenciais, com taxa \(\lambda\). Portanto, gera-se esses tempos entre chegadas \(X_i\). O instante da ocorrência do j-ésimo evento é dos \(j\) primeiros tempos entre chegadas e os valores dos \(n\) primeiros instantes de tempo são \(S_j = \sum_{i=1}^j X_i, ~ j = 1, 2, \dots n\). Se o objetivo é gerar os tempos de ocorrências do evento de interesse no intervalo de tempo \(T\), basta gerar sucessivamente os tempos entre chegada, parando o procedimento quando sua soma exceder \(T\). No algoritmo abaixo, \(I\) é o número de eventos que ocorrem no intervalo de tempo \((0, T)\) e \(S(I)\) é o instante de chegada mais recente.

- Algoritmos (Alternativa 1)

Passo 1- \(t=0\), \(I=0\).

Passo 2- Gerar um número aleatório \(U \sim \mathcal{U}(0,1)\).

Passo 3- Faça \(t = t - \frac{1}{\lambda} \log(U)\). Parar se \(t > T\).

Passo 4- \(I = I + 1\), \(S(I) = t\).

Passo 5 - Retorne ao passo 2.

O valor final de I representa o número de eventos que ocorrem durante o intervalo de tempo \((0, T)\) e os valores \(S(1), S(2), \dots, S(I)\) são os \(I\) tempos de chegada em ordem crescente.

Há outra alternativa para gerar os instantes de ocorrência do evento de interesse de um processo de Poisson, no intervalo de tempo \((0, T)\). Ele usa a propriedade que apresentamos acima, referente à distribuição dos instantes de chegada, dado que a quantidade de ocorrências é \(N(T) = n\)

- Algoritmos (Alternativa 2)

Passo 1- Gerar \(N(T)\), a quantidade de eventos que ocorreram no período de tempo \(T\),

Passo 2 - Gerar \(n\) números aleatórios uniformes no intervalo \((0,1)\), \(U_1, U_2, \dots, U_n\).

Passo 3- Ordenar os valores \(\{TU_1, TU_2, \dots, TU_n \}\).

A quantidade total de eventos ocorridos no intervalo \((0,T)\), \(N(T)\) é uma variàvel aleatória de Poisson com média \(\lambda T\). Esse valor deve ser gerado pelas abordagens estelecidas na seção que trata sobre geração de variável aleatória de Poisson, A variável aleatória \(TU\) está distribuída uniformemente no intervalo \(0, T\). Os valores ordenados são os instantes de chegada dos eventos do processo de Poisson \(S_i,~ i=1, 2, ...,n\) e as diferenças \(X_i = S_i - S_{i-1}, ~S_0=0\), os tempos entre chegadas.

Processo de Poisson não homogêneo:

Do ponto de vista de modelagem a maior fraqueza do processo de Poisson é a hipótese de que os eventos têm mesma probabilidade de ocorrer qualquer intervalo de igual tamanho. Uma generalização que relaxa essa hipótese leva ao denominado processo de Poisson não homogêneo ou processo não estacionário.

Sejam eventos ocorrendo aleatoriamente no tempo e \(N(t)\) a variável aleatória associada à quantidade de eventos que ocorrem no intervalo de tempo \((0,t])\), então \(\{N(t), t \geq 0 \}\) constitui um processo de Poisson não-homogêneo, com função de intensidade \(\lambda(t), ~ t \geq 0\), se:

1. \(N(0) = 0\).

2. A quantidade de eventos que ocorrem em intervalos de tempos mutuamente exclusivos são independentes.

3. Em um pequeno intervalo de tempo \((t,t+h)\) a probabilidade de um evento ocorrer é aproximadamente \(\lambda(t) h\), ou seja quando \(h \to 0\) a probabilidade de ocorrer um evento tende a um valor \(\lambda\): \[\begin{equation} \lim_{h\to 0} \prob \left \{\frac{N(h)=1}{h} \right\} =\lambda(t) \end{equation}\]

4. Em um pequeno intervalo de tempo \(h\), a probabilidade de ocorrerem dois ou mais eventos é aproximadamente \(0\): \[ \lim_{h\to 0} \prob\left\{\frac{N(h) \geq 2}{h} \right \}= 0 \]

A função valor médio é definida por: \[ m(t) = \int_0^t \lambda(s) \operatorname{d}\!s, ~t\geq 0. \]

Teorema

Suponha que eventos estejam ocorrendo de acordo a um processo de Poisson com taxa \(\lambda\) e suponha que, independentemente da trajetória anterior do processo, um evento que ocorre no instante \(t\) é contado com probabilidade \(p(t)\). Então, esse processo de contagem constitui um processo de Poisson não homogêneo, com função de intensidade \(\lambda(t) = \lambda p(t)\).

Prova encontra-se em Ross (2006), página 30.

Geração de processo de Poisson não homogêneo:

A ser implementado. Leia a Seção 5.5 de Ross (2006).

Simulação de cadeia de Markov:

Cadeia de Markov:

Seja o exemplo, retirado de Albert and Rizzo (2012), do seguinte passeio aleatório: pessoas caminhando em círculos, se posicionando nos pontos 1, 2, 3, 4, 5 ou 6.

A regra do passeio indica que se a pessoa está em um determinada posição, no próximo passo ela tem a mesma probabilidade de permanecer parada ou de se mover para uma posição vizinha. Se ela se mover, tem a mesma probabilidade de se mover para a esquerda ou para a direita. Esses movimentos probabilísticos podem ser modelados por uma cadeia de Markov.

Considere que o conjunto dos estados possíveis da locação da pessoa seja: \(\{1, 2, 3, 4, 5, 6, \}\). se uma pessoa está agora no estado \(1\), no próximo passo, ela só poderá estar nas posições \(\{1, 2, 6 \}\). Assim, dado que a pessoa está posicionada no instante atual em \(1\), as probabilidades de estar em um dos estados possíveis são:

\[ \tag{*} \prob(i|1) = \begin{cases} 0,5 &\text{, se }\, i = 1\\ 0.25 & \text{, se } i = 2 \text{ ou }6 \\ 0 & \text{, se }\, i = 3, 4 \text{ ou } 5 \end{cases} \]

Essas probabilidades condicionais do modelo são denominadas probabilidades de transição e podem ser dispostas numa matriz, em que, as linhas indicam a posição atual e as colunas, a posição no próximo passo. Assim o valor da linha \(1\), coluna \(1\) será \(0.5\); coluna \(2\), \(0,25\); coluna \(3\), 0 e assim por diante até a coluna \(6\), que será 0.25; Preenchendo essa matriz, teremos: \[\begin{equation} \mathbf{P} = \begin{matrix} 1 \\ 2 \\ 3 \\ 4 \\ 5 \\ 6 \end{matrix} \begin{bmatrix} 0.50 & 0.25 & 0 & 0 & 0 & 0.25 \\ 0.25 & 0.50 & 0.25 & 0 & 0 & 0 \\ 0 & 0.25 & 0.50 & 0.25& 0 & 0 \\ 0 & 0 & 0.25 & 0.50& 0.25 & 0 \\ 0 & 0 & 0 & 0.25& 0.50 & 0.25 \\ 0 & 0 & 0 & 0 & 0.25 & 0.50 \end{bmatrix} \label{matrix} \end{equation}\]

Cada linha dessa matrix apresenta as probabilidades de transição do estado atual para cada um dos estados possíveis. No exemplo, os valores da linha \(1\) representam as probabilidades de transição desse estado, para todo o espaço de estados . Para facilitar, utilizaremos a notação \(P_{ij}\) para respresentar a probabilidade de transição do estado \(i\) para o estado \(j\), ou seja, \(P_{ij} = \prob(j|i)\).

Percebe-se também que a soma de cada uma das linhas é 1, pois, cada linha, digamos a \(i\), \(i = 1, 2, \dots, 6\), é a distribuição de probabilidade de a cadeia mudar-se para o estado \(j\), \(j = 1,2, \dots, 6\), condicionada ao estado atual dela ser \(i\). De maneira geral, para uma cadeia de Markov com espaço de estados finito \(S = \{s_1, s_2, \dots, s_n \}\):

\[ \sum_{j=s_1}^{s_n} P_{ij}=1 \]

Uma cadeia de Markov é caracterizada por:

• seu espaço de estados (\(S\));

• sua distribuição de probabilidades inicial \(\mathbf{p}^{(0)}=(p^{(0)}_j)_{j \in S}\);

• probabilidades de transição do estado {i} para o estado {j} (\(P_{ij}\)).

Uma cadeia é dita homogênea, quando as probabilidades de transição \(P_{ij}\) não dependem do tempo {k}, como nesse exemplo de passeio aleatório.

Os estados de uma cadeia de Markov são classificados como recorrentes, quando, após a cadeia passar por ele, é certo que ela retorna a ele em algum instante de tempo,ou seja, a cadeia passa por ele infinitas vezes. Por outro lado, quando é incerto que a cadeia retorne a ele, o estado é denominado transiente ou transitório. Nesse caso a cadeia passa por ele uma quantidade finita de vezes. É denominado absovente o estado em que não há transiçao, após a passagem da cadeia por ele.

Seja o diagrama abaixo:

Percebe-se que o estado os estados \(1\) e \(2\) são recorrentes, os estados \(0\) e \(3\) são transientes e o estado \(4\) é absorvente,

De uma maneira mais formal, seja \(f_{ij}^{(k)}\), \(k \in \mathbb{N}\), a probabilidade de a cadeia passar pela primiera vez no estado \(j\) a partir do estado \(i\), em \(k\) passos, ou seja:

\[ f_{ij}^{(k)} = \prob(X_k = j| X_0 = i, X_1 \not= j, X_2 \not= j, \dots, X_{k-1} \not= j) \]

Assim, a probabilidade do primeiro retorno a \(i\) é definida como: \[ f_{ii} = \sum_{k>0}f_{ii}^{(k)} \]

ou, de outra maneira, a probabilidade de a cadeia retornar eventualemnte ao estado \(i\). O estado \(i\) é denominado recorrente se, e somente se, \(f_{ii} = 1\), caso contrário esse estado é denominado transiente (f_{ii}<1).

A condição \(p_{ij}^{(k)}>0\) para algum \(k\) significa que a cadeia eventualmente passa pelo estado \(j\), partindo do estado \(i\). Dizemos então que \(j\) é acessível a partir de \(i\), sendo expresso por \(i \to j\). Quando \(j\) não é acessível a partir de \(i\), \(p_{ij}^{(k)} = 0,~ \forall k\). Se \(i \to j\) e \(j \to i\), dizemos que os estados se comunicam, denotando por \(i \leftrightarrow j\). O operador \(i \leftrightarrow j\) define uma relação de equivalência sobre o espaço de estados \(S\), ou seja:

1. \(i \leftrightarrow i\);

2. Se \(i \leftrightarrow j\), então \(j \leftrightarrow i\);

3. Se \(i \leftrightarrow k\) e \(k \leftrightarrow j\), então \(i \leftrightarrow j\).

Dois estados que se comunicam tem a mesma classificação e, assim, as relações de equivalência particionam \(S\) em classes de equivalência, sendo elas: recorrência, transiência e período.

1. Um conjunto \(C \subset S\) é irredutível se \(i \leftrightarrow j\) para \(\forall ~ i,j\in C\). Quando um subconjunto de \(S\) não for irredutível, ele é dito redutível.

2. Quando há uma única classe de comunicação dizemos que a cadeia é irredutível.

3. Dizemos que \(C\) é absorvente se \(P_{ij}=0\) para \(i \in C\) e \(j \not\in C\).

Perceba que \(P_{00}^(n)\) só pode ocorrer na cadeias em instantes \(n=2k\), \(n=4k\), \(n=6k\), o mesmo ocorrendo em todos os outroestados.

Define-se período de um estado \(i\) por: \[ \tau(i) = \operatorname{mdc} \{n: p_{ij}^{(n)}>0 \} \]

Se \(\tau(i)>1\), dizemos que o estdo \(i\) é periódico, nesse caso \(p_{ii}^{(n)}=0\), a menos que \(n\) seja múltiplo de \(\tau(i)\). Caso \(\tau(i)=1\)$, dizemos que \(i\) é aperiódico. No exemplo acima, todos os estados tem período \(\tau(i)=2\).

Considere agora o diagrama de estados a seguir:

Essa cadeia é redutível e o espaço de estado tem três classes de equivalência de comunicação \(S = \{1, 2 \} \cap \{3,4 \} \cap \{5, 6\}\). Os conjuntos \(\{1, 2 \}\) e \(\{5, 6 \}\) são irredutíveis e recorrentes e o conjunto \(\{3,4 \}\) é transiente, pois, uma vez que a cadeia deixa alguns desses estados ela nunca mais retorna. Todos os estados tem período 1, pois \(P_{ii} > 0\) e a cadeia portanto é aperiódica.

Há assim algumas propriedades importantes para se verificar em uma cadeia de Markov:

• Irredutibilidade: Diz-se que a cadeia é irredutível, quando é possível percorrer todo os estados em um ou mais estado.

• Periodicidade: quando, estando em um particular estado, a cadeia pode retornar a este estado em intervalos periódicos. Nesse caso ela é dita periódica.

É importante salientar que as probabilidades de transição não dependem de toda a trajetória. mas apenas de sua posição atual. Essa propriedade é denominada markoviana, pois: \[ \prob \big(X_{n+1}=j~|~X_n=i, ~X_{n-1}=s_{n-1},\cdots, ~X_{0}=s_{0}\big)= \prob \big(X_{n+1}=j~|~X_n=i \big) \]

Seja, \(p_j^{(k)}\) a probabilidade de a cadeia passar pelo estado \(j \in S\), no passo \(k\). Assim, pelo Teorema da Probabilidade Total temos: \[ \tag{**} p_{j}^{(k)} = \sum_{i \in S} P_{i j}\, p_{i}^{(k-1)} \]

Sem perda de generalidade, utilizaremos a partir deste ponto o espaço de estado finito \(S = \{1, 2, \dots, n\}\).seja \(\mathbf{p}^{(k)} = (p_1^{(k)}, p_2^{(k)}, \dots, p_n^{(k)})^\prime\) a distribuição das probabilidades de passagem da cadeia no passo \(k\). A forma matricial da expressão é: \[ {\mathbf{p}^{(k)}}^\prime = {\mathbf{p}^{(k-1)}}^\prime \mathbf{P} \]

Suponha encontrar um vetor de probabilidades \(\boldsymbol{\pi}\), tal que: \[ \boldsymbol{\pi}^\prime = \boldsymbol{\pi}^\prime \mathbf{P} \]

Se existir, \(\boldsymbol{\pi}\) é a distribuição invariante da cadeia. Se uma cadeia tem espaço de estados finito e for irredutível e aperiódica, então a distribuição invariante é única.

Demonstração empírica:

Considere que o passeio aleatório do início desta seção iniciou no passo \(3\). Simule muitos passos da cadeia de Markov, usando a matriz de transição \(P\). A frequência relativa que cada estado pode ser uma aproximação de \(\boldsymbol{\pi}\).

Função para simular uma cadeia de Markov no passo \(j\):

markov.simula <- function(P, inicial, passo.j){
    # =========================================================
    #   Função para simular estado no passo j
    #
    # Argumentos:
    #      P:           matriz de probabilidade de transição
    #     inicial:  estado inicial da cadeia
    #     passo.j:  passo da cadeia
    #
    # Saída:
    #     trajetoria:   estados até o passo j
    #
    # Fonte: Abert, J.; Rizzo, M. R in example, Springer, 2012.
    # ==========================================================

        n.estados = dim(P)[1]
        estado <- inicial
        trajetoria <- numeric()
        for(j in 1:passo.j){
            estado <- sample(n.estados, size = 1, prob = P[estado, ])
            trajetoria[j] <- estado
        }
        return(trajetoria)
}

A matriz de probabilidades de transição do passeio aleatório apresentado nesta seção é homogênea e é dada por:

    # Matriz de probabilidades de transição

P <- diag(0.5, 6)
for(i in 1:5)   P[i+1, i] <- 0.25 
P[6, 1] <- 0.25
P[upper.tri(P)] <- t(P)[upper.tri(P)]
P

##      [,1] [,2] [,3] [,4] [,5] [,6]
## [1,] 0.50 0.25 0.00 0.00 0.00 0.25
## [2,] 0.25 0.50 0.25 0.00 0.00 0.00
## [3,] 0.00 0.25 0.50 0.25 0.00 0.00
## [4,] 0.00 0.00 0.25 0.50 0.25 0.00
## [5,] 0.00 0.00 0.00 0.25 0.50 0.25
## [6,] 0.25 0.00 0.00 0.00 0.25 0.50

A simulação de uma trajetória da cadeia com 1000 passos é dada a seguir:

    # Simulação de trajetórias

passeios <- markov.simula(P, 3, 1000)

obtendo-se a seguinte estimativa da distribuição da cadeia no tempo \(1000\):

  # estimação distribuição no instante 1.000
prop.table(table(passeios))

## passeios
##     1     2     3     4     5     6 
## 0.204 0.182 0.141 0.130 0.159 0.184

Pode-se provar que a distribuição invariante dessa cadeia é \((1/6, 1/6, 1/6, 1/6, 1/6, 1/6)^\prime\). Empiricamente verifica-se que \(\boldsymbol{\pi}^\prime = \boldsymbol{\pi}^\prime \mathbf{P}\):

estacionaria <- rep(1, 6)/6
estacionaria %*% P

##           [,1]      [,2]      [,3]      [,4]      [,5]      [,6]
## [1,] 0.1666667 0.1666667 0.1666667 0.1666667 0.1666667 0.1666667

Há uma diferença entre a distribuição estimada e a exata, indicando que talvez simulação de tejetórias com 1000 passos possa não ser um procedimento preciso para essa finalidade. Verifica-se a convergência para os valores das probabilidades estacionárias em todos os estados.

Fica uma pergunta: uma trajetória mais longa traria uma precisão maior na estimação da distribuição invariante por esse procedimento? Essa estimação aparentemente é não enviesada, mas qual será sua precisão? Ao calcularmos as frequèncias relativas estamos calculando médias amostrais?

Referências

Albert, Jim, and Maria Rizzo. 2012. R by Example. Springer Science & Business Media.

Ross, Sheldon. 2006. Simulation. Academic Press.

———. 2009. Probabilidade: Um Curso Moderno Com Aplicaçoes. Bookman Editora.