PUZZLE ENCERRADO

Dovish It

Edição #013 · dez. de 2023

Imagine que você está em um salão de um restaurante fechado. Um pássaro entra pela janela e começa a voar aleatoriamente por cima das mesas. Você quer saber qual a probabilidade de sua mesa ser “premiada”.

Vamos modelar o problema da seguinte maneira. Imagine que o restaurante tem n mesas enfileiradas em linha reta e que a janela pela qual o pássaro entrou está na mesa 1. Considere que, após o pássaro entrar, as janelas e portas estão todas fechadas.

Considere que o pássaro se move em intervalos de 1 segundo e que, no instante t, ele tem 50% de probabilidade de ficar onde está e 50% de se mover para uma mesa vizinha. Por exemplo, se ele está sobrevoando a mesa 3, ele tem 50% de probabilidade de ficar na mesa 3, 25% de ir para a mesa 4 e 25% de ir para a mesa 2. No caso de ele estar sobrevoando a mesa n ou a mesa 1, ele tem 50% de probabilidade de ficar na mesma mesa e 50% de probabilidade de ir para a única mesa vizinha.

(a) Suponha que o restaurante tem 5 mesas (n=5). Supondo que uma mesa foi “premiada” após exatamente 10 segundos, qual é a probabilidade de ter sido a mesa de número 5?

(b) Defina p(t, k) como: “supondo que uma mesa foi “premiada” após exatamente t segundos, qual a probabilidade de ter sido a mesa k.” Qual o menor valor de t tal que p(t, 5) está entre 12% e 13%?

// Leaderboard

Quem resolveu

8 soluções corretas · Puzzle #013

Andre Costa

Gustavo Aldama Mourão Soares Pereira

Igor Dias

Ivan Petrin

Leonardo Martos Barbosa

Lucas De Andrade Santos Duarte

Lucas Giacone

Victor Marques Moreno

// Solução

Resolução do Puzzle #013

Considere um vetor $P(t)$ em que a entrada $k$ é $p(t, k)$ , a probabilidade de se estar em $k$ no instante $t$ . Pode-se definir uma matriz de transição para a dinâmica do problema, em que a entrada $(i,j)$ é a probabilidade de irmos da casa $j$ para a $i$ em um passo:

A = \begin{pmatrix} p_{1 \rightarrow 1} & p_{2 \rightarrow 1} & p_{3 \rightarrow 1} & \dots & p_{n \rightarrow 1} \\ p_{1 \rightarrow 2} & p_{2 \rightarrow 2}& p_{3 \rightarrow 2} & \dots & p_{n \rightarrow 2} \\ & & \vdots & & \\ p_{1 \rightarrow n} & p_{2 \rightarrow n} & p_{3 \rightarrow n} & \dots & p_{n \rightarrow n} & \end{pmatrix}

De modo que podemos resolver $P(t)$ recursivamente:

P(t+1) = A P(t) \implies P(t)=A^tP(0)

Para $n=5$ , temos

A=\begin{pmatrix} 0.5 & 0.25 & 0 & 0 & 0 \\ 0.5 & 0.5 & 0.25 & 0 & 0 \\ 0 & 0.25 & 0.5 & 0.25 & 0 \\ 0 & 0 & 0.25 & 0.5 & 0.5 \\ 0 & 0 & 0 & 0.25 & 0.5 \\ \end{pmatrix} \quad \text{e} \quad P(0) = \begin{pmatrix} 1 \\ 0 \\ 0 \\ 0 \\ 0 \\ \end{pmatrix}

Calculando em um computador, obtemos:

P(10)= \begin{pmatrix} 0.1766 \\ 0.3226 \\ 0.2495 \\ 0.1774 \\ 0.0739 \end{pmatrix}

Portanto, a resposta do item a) é 7.39%

Para o item b), calculamos $P(t)$ para $t=1, 2, 3,…$

O primeiro valor de $t$ para o qual $p(t, 5)$ está entre $0.12$ e $0.13$ é $t=25$ .

Por que a probabilidade de acabarmos nas pontas aparenta convergir para metade da probabilidade de acabarmos no meio quando $t \rightarrow \infty$ ?

Para $t=25$ , por exemplo, o vetor de probabilidades fica

P(25) = \begin{pmatrix} 0.1298 \\ 0.2567 \\ 0.25 \\ 0.2433 \\ 0.1202 \end{pmatrix}

Entenderemos melhor a dinâmica do problema se nos livrarmos da assimetria nas pontas: ao invés de considerar que as mesas $1$ e $n$ só tem um vizinho, estenda o salão infinitamente de modo que todos tenham dois vizinhos:

1 \:\: 2 \:\: 3 \:\: \cdots (n-1) \:\: n

\Downarrow

\:\:\:\:\:\:\:\:\: \cdots \:\: 3 \:\: 2 \:\: 1 \:\: 2 \:\: 3 \:\: \cdots (n-1) \:\: n \:\: (n-1) \:\: \cdots

Isto é, cada mesa terá infinitas “cópias virtuais", de modo que, por exemplo, quando o pássaro vai da mesa 1 para a mesa 2 do restaurante, no salão estendido ele tem a opção de ir para a mesa 2 ou para a 2 virtual. Assim, podemos considerar que o pássaro sempre vai para esquerda, direita ou fica parado com probabilidades de 25%, 25% e 50%, respectivamente.

Mais formalmente, associamos cada mesa do restaurante a um subconjunto dos inteiros, de modo que quando o pássaro estiver sobre a mesa $k$ , o pássaro virtual estará sobre algum dos inteiros associados à mesa $k$ . O diagrama abaixo ilustra parte do salão estendido para $n=5$ : o eixo $y$ apresenta a mesa no salão normal e o eixo $x$ , os inteiros associados no salão estendido.

Agora fica evidente o por quê da probabilidade do pássaro estar nas pontas converge para metade da probabilidade de estar em uma mesa do meio: cada período da associação $\text{mesa} \leftrightarrow \text{inteiro}$ tem apenas 1 inteiro associado às mesas 1 e n, mas dois inteiros associados às mesas do meio (visualmente, um na “subida" e outro na “descida").

Na verdade, o salão virtual nos dá muito mais que mera intuição sobre a dinâmica do problema. Com a devida diligência, podemos calcular $p(t, k)$ explicitamente para qualquer par $t$ , $k$ .

Para tanto, vamos introduzir a função geratriz do movimento do pássaro:

F_t(x)=x^1(0.5x^0 + 0.25x^1 +0.25 x^{-1})^t

Essa série nos é útil pois o coeficiente do termo $x^k$ em sua expansão é exatamente $\overline{p}(t,k)$ , a probabilidade do pássaro acabar sobre a mesa virtual $k$ após $t$ segundos:

F_t(x)=\sum_{k}{a_k x^k} \quad \text{:} \quad a_k=\overline{p}(t,k)

Portanto, para acharmos $p(t,k)$ , basta somar os coeficientes $a_k \prime$ de todos os inteiros $k^{\prime}$ associados à mesa $k$ :

p(t,k)=\sum_{k^{\prime} \text{assoc.} k}{\overline{p}(t,k^{\prime})}=\sum_{k^{\prime} \text{assoc.} k}{a_{k \prime }}

Vamos explorar um pouco melhor $F_t(x)$ :

F_t(x)=x^1(0.5x^0 + 0.25x^1 +0.25 x^{-1})^t = x^1\frac{(2x+x^2+1)^t}{2^{2t}x^t}

\implies F_t(x)=\frac{(x+1)^{2t}}{2^{2t}x^{t-1}}=\sum_{k}{a_k x^k}

No caso particular de $n=5$ e $k=5$ , os inteiros associados à mesa 5 são os inteiros da forma $8x+5$ (Verifique você mesmo!). Portanto:

p(t, 5)=\sum_{k=8x+5}{a_kx^k}

Mas como achamos a soma de um subconjunto dos coeficientes de uma série? A soma do conjunto de todos os coeficientes é fácil:

\sum_k{a_k}=\sum_k{a_k1^k}=F_t(1)=\frac{(1+1)^{2t}}{2^{2t}1^{t-1}}=1

Para o nosso subconjunto, podemos usar uma ideia parecida: substituir valores de x em $F_t(x)$ para ficarmos só com coeficientes, mas de forma que os coeficientes que não são da forma $8x+5$ “sumam". Podemos fazer isso se olharmos para uma série ligeiramente diferente, $G(x)=x^3F_t(x)$ , e utilizarmos a oitava raiz primitiva da unidade $\zeta=e^{\frac{2\pi i}{8}}=cis(\frac{2\pi}{8})$ .

O poder de $\zeta$ reside no fato de que

(\zeta^i)^0+(\zeta^i)^1+\dots+(\zeta^i)^7=\frac{\zeta^{8i}-1}{\zeta^i-1} =\begin{cases} 0 & \text{se 8 não divide i} \\ 8 & \text{se 8 divide i} \end{cases}

Logo,

\frac{G(\zeta^0)+G(\zeta^1)+\dots G(\zeta^7)}{8}=\sum_{k=8x+5}{a_k} \quad \text{onde} \quad G(x)=\frac{(x+1)^{2t}}{2^{2t}x^{t-4}}

pois os únicos termos de $G$ que “sobrevivem" são aqueles que multiplicam potências de $x$ múltiplas de 8, isto é, exatemente os $a_{8x+5}$ . Vamos às contas: