Exercícios Embaralhamento

1. Dados uma matriz de transição $P$$P$ e $\lambda$$\lambda$​ uma distribuição nos estados $S$$S$, a condição de balanço detalhado é

   $${\lambda }_j{p}_{j,i}={\lambda }_i{p}_{i,j}$$

   (1.1) Prove que se a condição de balanço detalhado é satisfeita para todos $i,j\in S$$i,j\in S$, então $\lambda$$\lambda$ é estacionária. (1.2) Prove que se a condição de balanço detalhado é satisfeita para todos $i,j\in S$$i,j\in S$, então

   $${\lambda }_{i_0}{p}_{i_0,i_1}\cdots p_{i_{n-1},i_n}={\lambda }_{i_n}{p}_{i_n,i_{n-1}}\cdots p_{i_1,i_0}.$$

   para quaisquer $i_0,\dots ,i_n\in S$$i_0,\dots,i_n\in S$. Nesse caso dizemos que a cadeia é reversível.

   ---

    

2. Verifique que $\sigma \in S_n$$\sigma\in S_n$​ é um embaralhamento riffle diferente da identidade se e só se tem exatamente 1 descida. Uma descida ocorre quando σ(i)>σ(i+1). Conclua que é um embaralhamento riffle se e só se tem no máximo uma descida.

   Verifique, também, que o número de descidas é igual para $\sigma$$\sigma$ e ${\sigma }^{-1}$$\sigma^{-1}$ e conclua que

   $$\sigma \text{ é um riffle shuffle}⟺{\sigma }^{-1}\text{ é um riffle shuffle}$$

   e que $\mathrm{Rif}(\sigma )=\mathrm{Rif}({\sigma }^{-1})$$\mathrm{Rif}(\sigma)=\mathrm{Rif}(\sigma^{-1})$.

   ---

    

3. Um embaralhamento "top-in-at-random" é um método de embaralhamento de cartas onde a carta do topo é repetidamente removida e inserida em uma nova posição aleatória no baralho. Esse embaralhamento tem a seguinte regra de parada fortemente uniforme: PARE assim que a carta original do fundo (rotulada $n$$n$) for inserida de volta no baralho pela primeira vez. Durante o processo, a ordenação das cartas abaixo dessa “última” carta é completamente uniforme

   seja $T_i$$T_i$ a variável aleatória que conta o número de embaralhamentos realizados até que, pela primeira vez, $i$$i$ cartas estejam abaixo da carta $n$$n$. Então o tempo de parada $T$$T$ é dado por $T_n$$T_n$. (3.1) Mostre que $\mathbb{E}[T_n]=n(1+\frac{1}{2}+\cdots +\frac{1}{n})\approx n\ln (n)$$\mathbb{E}[T_n] = n(1+\tfrac12+\cdots+\tfrac1n)\approx n\ln(n)$. (3.2) Mostre que $\mathbb{P}(T_n>k)\le n{(1-\frac{1}{n})}^k$$\mathbb{P} (T_n>k) \le n\left(1-\tfrac 1n\right)^k$. (3.3) Conclua que para $k=\lceil n\log n+cn\rceil$$k= \lceil n\log n + cn\rceil$ vale que $\mathbb{P}(T_n>k)<n\exp (-k/n)\le \exp (-c)$$\mathbb{P} (T_n>k) < n\exp(-k/n)\le \exp(-c)$. (3.4) Deduza um limitante superior para a distância, em variação total, da distribuição após $k$$k$ embaralhamentos para a distribuição uniforme $\Vert {\mathrm{Top}}^{(k)}-U{\Vert }_{TV}$$\Vert \mathrm{Top}^{(k)} -U\Vert_{TV}$​.

   ---

4. Um tempo de estacionariedade forte (strong stationary time) para uma cadeia de Markov é um tempo de parada $T$$T$ tal que $X_T$$X_T$ tem distribuição estacionária e é independente de $T$$T$, isto é,

   $$\mathbb{P}[T=k,X_k=j]={\pi }_j.$$

   Observe que um tempo estacionariedade forte é altamente desejável na prática porque ele garante que a amostra é escolhida exatamente da distribuição estacionária.

   Vamos limitar o tempo de mistura de um passeio aleatório simples em um circuito comprimento $n$$n$. Considere um passeio aleatório preguiçoso e simples $(X_n{)}_n$$(X_n)_n$ em um circuito de comprimento $n=2^k$$n=2^k$ com vértices $\{0,1,2,\dots ,n-1\}$$\{0, 1, 2, \ldots, n-1\}$, como início $X_0=0$$X_0=0$, onde em cada vértice permanecemos com probabilidade $1/2$$1/2$ e vamos para a esquerda/direita com probabilidade $1/4$$1/4$, isto é,

   $$P=\frac{1}{2}\mathrm{Id}+\frac{1}{4}A$$

   onde Id é a matriz identidade e $A$$A$ a matriz de adjacências do grafo.

Seja $T_i$$T_i$ o primeiro instante a partir de $T_{i-1}$$T_{i-1}$ em que passeio atinge a distância $2^{k-2-i}$$2^{k-2-i}$. Por exemplo, se $n=16$$n = 16$, no instante $T_0$$T_0$ o passeio está uniformemente distribuído nos vértices de distância $4$$4$, ou seja, em $\{4,12\}$$\{4, 12\}$; no instante $T_1$$T_1$ está uniformemente distribuído nos vértices a distância $2$$2$ de $\{4,12\}$$\{4,12\}$, ou seja, uniformemente distribuído em $\{2,6,10,14\}$$\{2, 6, 10, 14\}$; e em $T_2$$T_2$ estará uniformemente distribuído em todos os vértices ímpares. Agora, dando mais um passo, o caminhante ficará uniformemente distribuído em todo o circuito!

(4.1) Condicionando no primeiro passo, mostre que um passeio aleatório em $\mathbb{Z}$$\mathbb{Z}$ iniciado em $0$$0$ que permanece parado com probabilidade $1-\theta$$1 - \theta$ e se move para a esquerda/direita com probabilidade $\theta /2$$\theta/2$ atinge $\pm b$$\pm b$ em tempo esperado $b^2/\theta$$b^2 / \theta$. (4.2) Use o resultado anterior para mostrar $\mathbb{E}[T_i-T_{i-1}]=\frac{2^{2(k-2-i)}}{1/2}$$\mathbb{E}[T_i - T_{i-1}] = \frac{2^{\,2(k-2-i)}}{1/2}$ e mostre que a esperança do tempo de parada final $1+T_{k-2}$$1 + T_{k-2}$ é no máximo $\frac{1}{6}{n}^2$$\frac{1}{6} n^2$. (4.3) Denote por $P^{(t))}(0,\cdot )$$P^{(t))}(0,\cdot)$ a distribuição de $X_t$$X_t$ condicionado a $X_0=0$$X_0=0$. Prove