Tópico: Urna de Pólya

Um excelente exemplo de como Cadeias de Markov podem gerar interessantes modelos de situações reais são as chamadas Urnas de Pólya. Esse processo modela sistemas de física, biologia, computação e economia que apresentam o que chamamos de reforço.

Tome por exemplo duas empresas que competem pelo mercado de aviões. Inicialmente, não temos nenhuma razão para escolher uma em detrimento da outra, portanto compramos nosso primeiro avião de cada empresa com probabilidade meio. Porém, depois que já compramos diversos aviões de uma determinada empresa, ela já recebeu bastante dinheiro que pode ser reinvestido para gerar melhor tecnologia e aumentar as chances que ela seja escolhida novamente no futuro. Isso é o que chamamos de reforço.

Vamos agora apresentar rigorosamente um modelo para situações desse tipo. O nosso modelo começa com uma urna contendo duas bolas, uma vermelha e uma azul. No cada passo do processo, escolheremos uma bola da urna ao acaso, olharemos sua cor e retornaremos essa bola para dentro urna junto com mais uma bola da mesma cor. Isso pode será formalizado à seguir.

Vamos construir uma medida em $\{0,1\}^{\mathbb{N}}$, dotado da $\sigma$-álgebra produto. Fixada uma sequência finita $w_{1},\dots,w_{n}$ em $\{0,1\}$, definimos

que nada mais é que o número de bolas do tipo $x$ que se encontram na urna no tempo $n$. Quando tivermos uma sequência infinita de $w_{i}$’s, escreveremos $N^{n}_{x}$ para denotar $N_{x}(w_{1},\dots,w_{n})$.

Para cada $n\geq 1$, definimos $K_{n}:\{0,1\}^{n}\to\mathcal{P}(\{0,1\})$ por

Ou seja, dadas cores $w_{1},\dots,w_{n}$, escolheremos uma bola de cor $1$ proporcionalmente ao número $N_{1}$ de bolas de cor $1$ que já foram sorteadas.

Mostre que todos $K_{n}$ acima definem núcleos de transição. Além disso a seguinte sequência de medidas é compatível no sentido de Kolmogorov:

• •
  ​

  $P_{1}=\Ber(1/2)$,

• •
  ​

  $P_{2}=P_{1}\star K_{1}$,

• •
  ​

  $P_{3}=P_{2}\star K_{2},\dots$

Conclua que existe a medida $P$ em $\{0,1\}^{\mathbb{N}}$ que define o modelo de Pólya.

Podemos agora fazer perguntas como por exemplo: será que escolheremos bolas de ambas as cores para sempre, ou a partir de um certo momento escolheremos bolas de apenas uma cor com certa probabilidade. Mais precisamente, qual é a probabilidade de $[X_{i}=1,\text{ infinitas vezes}]$?

Para responder perguntas desse tipo, iremos mostrar algo muito curioso, que pode ser entendido como uma outra maneira de representar o modelo descrito acima. Mas antes, vamos colecionar alguns fatos sobre o modelo da Urna de Pólya.

Primeiramente vamos olhar para os seguintes eventos. Fixamos $n\geq 1$ e uma sequência $w_{1},\dots,w_{n}\in\{0,1\}$ e seja $A$ o evento $\{w_{1}\}\times\dots\times\{w_{n}\}\times\{0,1\}\times\dots$ Note que os eventos desse tipo (junto com o evento $\varnothing$) formam um $\pi$-sistema que gera a $\sigma$-álgebra canônica de $\{0,1\}^{\mathbb{N}}$, portanto essa coleção é bastante completa para identificar a distribuição da Urna de Pólya.

Podemos calcular a probabilidade do evento $A$ acima

O que é muito interessante sobre a equação acima é que ela nos remete a problemas combinatórios ao notarmos o fator binomial acima.

Vamos portanto construir um processo completamente diferente que apresenta as mesmas probabilidades que o anterior. Seja $\mathcal{S}_{N}$ o conjunto de todas as permutações $\sigma$ de $\{1,\dots,N\}$. É fácil ver que

Um método muito interessante de se produzir uma permutação uniforme é dado pelos seguintes exercícios.

Seja $n\geq 1$ um inteiro, $P$ uma probabilidade em $(E,\mathcal{A})$, $\sigma$ uma permutação fixa em $\mathcal{S}_{n}$. Então

onde $X_{i}$ como sempre representam as coordenadas canônicas em $(E^{n},\mathcal{A}^{\otimes n},P^{\otimes n})$.

Ou em outras palavras, aplicar uma permutação fixa a uma sequência \iidnão altera sua distribuição. Sequências de elementos aleatórios (não necessariamente \iid’s) que satisfazem (2.129) são ditas intercambiáveis.

Um outro exercício interessante nesse tópico é o seguinte {exercise} Seja $n\geq 1$ e $F:[0,1]^{n}\to\mathcal{S}_{n}$ dada por

Mostre que $F_{*}(U_{[0,1]}^{\otimes n})=U_{\mathcal{S}_{n}}$.

Ou seja, ordenar uma sequência de uniformes independentes nos fornece uma permutação uniforme. Como prometido, isso nos dá uma maneira de construir uma permutação uniforme de $\{1,\dots,n\}$ à partir de uma sequência \iid(que é algo que já estamos começando a entender melhor).

Podemos agora escrever nossa probabilidade de observar uma sequência no modelo da Urna de Pólya em termos de uma sequência \iidde variáveis aleatórias.

Agora estamos prontos para provar o resultado principal que nos ajudará a calcular probabilidades no modelo da Urna de Pólya.

Dado $u\in[0,1]$, seja $P_{u}=\Ber(u)^{\otimes\mathbb{N}}$, ou seja a probabilidade que nos dá uma sequência infinita de moedas independentes com probabilidade $u$ de sucesso. Definimos agora $\widebar{K}:[0,1]\times(\mathcal{P}(\{0,1\})^{\otimes\mathbb{N}})\to[0,1]$ dada por

A função $\widebar{K}$ definida acima é um núcleo entre $[0,1]$ e $\{0,1\}^{\mathbb{N}}$.

O resultado muito curioso a qual nos referimos é o seguinte.

A lei $P$ definida no Exercício 2 é igual a $U_{[0,1]}\widebar{K}$.

Em outras palavras, digamos que realizamos os seguintes experimentos. Primeiramente João realiza o processo da Urna de Pólya e anota a sequência das cores obtidas. Depois Maria sorteia uma variável aleatória $X$ de distribuição uniforme em $[0,1]$ e depois joga infinitas vezes uma moeda com probabilidade $X$ de obter vermelho e $(1-X)$ de obter azul, anotando também quais cores foram obtidas. Finalmente, não seríamos capazes de distinguir essas duas sequências (mesmo que pudéssemos repetir várias vezes esse experimento) pois elas tem a mesma distribuição em $\{0,1\}^{\mathbb{N}}$.

Mostre que a probabilidade, segundo o modelo da Urna de Pólya, de que observemos infinitas bolas de ambas as cores é um.