Exercícios Ergodicidade

Nos exercícios abaixo, sempre que necessário, considere $(X_n{)}_{n\ge 0}$$(X_n)_{n\geq 0}$ uma cadeia de Markov sobre o conjunto de estados $S$$S$ com transições $P$$P$ e distribuição inicial $\lambda$$\lambda$.

1. Suponha que uma cadeia de Markov tenha matriz de transição

   $$\begin{array}{c}P=\left(\begin{array}{ccc}0& 1-p& p\\ p& 0& 1-p\\ 1-p& p& 0\end{array}\right),\text{para }0<p<1.\end{array}$$

   Encontre a distribuição estacionária.

   ---

    

2. Para a cadeia de dois estados com

   $$\begin{array}{c}P=\left(\begin{array}{cc}1-p& p\\ q& 1-q\end{array}\right),\end{array}$$

   onde $0<p,q<1$$0 < p, q < 1$ e $p+q\ne 1$$p+q\neq 1$​ encontre a distribuição limite.

   ---

    

3. Encontre a distribuição estacionária da cadeia de Markov do tempo cuja matriz de transição é:

   	Chuva	Neve	Limpo
   Chuva	$\frac{1}{5}$$\tfrac{1}{5}$	$\frac{3}{5}$$\tfrac{3}{5}$	$\frac{1}{5}$$\tfrac{1}{5}$
   Neve	$\frac{1}{10}$$\tfrac{1}{10}$	$\frac{4}{5}$$\tfrac{4}{5}$	$\frac{1}{10}$$\tfrac{1}{10}$
   Limpo	$\frac{1}{10}$$\tfrac{1}{10}$	$\frac{3}{5}$$\tfrac{3}{5}$	$\frac{3}{10}$$\tfrac{3}{10}$

   ---

    

4. Cadeia de Markov preguiçosa: Seja $(X_n)$$(X_n)$ uma cadeia de Markov irredutível em um espaço de estados enumerável $S$$S$, com matriz de transição $P$$P$ e distribuição estacionária $\pi$$\pi$. Seja $a\in (0,1)$$a \in (0,1)$ e defina

   $$L=aP+(1-a)I,$$

   onde $I$$I$ é a matriz identidade. Mostre que $L$$L$ é a matriz de transição de uma cadeia de Markov $(Y_n)$$(Y_n)$ irredutível e aperiódica, cuja distribuição estacionária é $\pi$$\pi$​.

   ---

    

5. Para um grafo $G=(V,E)$$G=(V,E)$​ conexo e finito, um passeio aleatório simples pelos vértices do grafo $G$$G$ é definido por um vetor estocástico $\lambda$$\lambda$ para a distribuição inicial e matriz de transição

   $$\begin{array}{c}{p}_{i,j}=\{\begin{array}{ll}1/d(i),& \text{ se }\{i,j\}\in E(G)\\ 0,& \text{ caso contrário }\end{array}\end{array}$$

   onde $d(i)=\sum _{j\in V}{a}_{i,j}$${d}(i) = \sum_{j\in V} a_{i,j}$ é o grau do vértice $i$$i$ em $G$$G$, ou seja, é a quantidade de arestas a que $i$$i$​ pertence. Determine a distribuição estacionária desse passeio aleatório.

   ---

    

6. No exercício anterior, descreva a(s) distribuição(ões) estacionária(s) se o grafo for desconexo.

   ---

    

7. Um grafo $G=(V,E)$$G=(V,E)$ é dito completo se $E$$E$ é formado por todos os $(\genfrac{}{}{0ex}{}{|V|}{2})$$\binom{|V|}{2}$ possíveis pares não ordenados de vértices. Se um passeio aleatório simples começa em $v_0\in V$$v_0\in V$m qual o tempo esperado para o passeio visitar todos os vértices do grafo completo?

   ---

    

8. Movimentos aleatórios no xadrez. Considere um tabuleiro de xadrez com um rei branco solitário realizando movimentos aleatórios, ou seja, a cada jogada ele escolhe, de forma uniforme ao acaso, uma das casas possíveis para se mover. A cadeia de Markov correspondente é irredutível e/ou aperiódica?

   Mesma pergunta, mas agora com o rei substituído por um bispo.

   Mesma pergunta, mas agora com um cavalo.

   ---

9. A cada instante $n=0,1,2,\dots$$n = 0, 1, 2, \dots$, um número $Y_n$$Y_n$ de partículas entra em uma câmara, onde $Y_n:n\ge 0$${Y_n : n \ge 0}$ são variáveis independentes, cada uma com distribuição de Poisson de parâmetro $\lambda$$\lambda$. As durações de vida das partículas são independentes e geometricamente distribuídas com parâmetro $p$$p$. Seja $X_n$$X_n$ o número de partículas presentes na câmara no instante $n$$n$. Mostre que $(X_n{)}_{n\ge 0}$$(X_n)_{n \ge 0}$ é uma cadeia de Markov e determine sua distribuição estacionária. (Dica: Se $X_n\sim \text{Pois}(\mu )$$X_n \sim \text{Pois}(\mu)$ então $\text{Bin}(X_n,1-p)$$\text{Bin}(X_n, 1-p)$ tem distribuição $\text{Pois}(\mu (1-p))$$\text{Pois}(\mu(1-p))$ )

   ---

10. Use o exercício 3 da lista anterior para provar que toda cadeia de Markov finita tem pelo menos uma distribuição estacionária. (dica: $\mathbb{E}[T_j\mid X_0=i]<\mathrm{\infty }$$\mathbb{E}[T_j\mid X_0=i]<\infty$ para todo $i$$i$.)