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$$X$ 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$$Y$ 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. 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.

8. Problema do Colecionador de Cupons Você quer coletar cada um de $n$$n$ cupons diferentes e recebe todo dia um cupom aleatório pelo correio, quanto tempo precisa esperar? Dica:

   $T^{(i)}$$T^{(i)}$ é o primeiro instante em que $i$$i$ cupons tenham sido recebidos, assim, $T^{(1)}=0<T^{(2)}=1<T^{(3)}<\cdots <T^{(n)}.$$T^{(1)}= 0 < T^{(2)} = 1 < T^{(3)} < \dots < T^{(n)}.$ Determine $\mathbb{E}(T^{(n+1)}-T^{(n)})$$\mathbb E (T^{(n+1)} - T^{(n)})$.