Explicación intuitiva/heurística de la urna de Polya

Question

Supongamos que tenemos una urna con una bola roja y otra azul. En cada paso, sacamos una sola bola de la urna y anotamos su color; a continuación, volvemos a introducir esa bola en la urna, junto con una bola adicional del mismo color.

Esta es la urna de Polya, y uno de los datos básicos sobre ella es el siguiente: el número de bolas rojas después de $n$ es uniforme sobre $\{1, \ldots, n+1\}$ .

Esto es muy sorprendente para mí. Aunque no es difícil demostrarlo mediante un cálculo directo, me pregunto si alguien puede dar una explicación intuitiva/heurística de por qué esta distribución debería ser uniforme.

Hay bastantes preguntas sobre la urna de Polya en math.stackexchange, pero ninguna de ellas parece preguntar exactamente esto. La más cercana es esta pregunta donde hay algunas buenas explicaciones de por qué, asumiendo como arriba que empezamos con una bola roja y otra azul, la probabilidad de sacar una bola roja en el $k$ El paso es $1/2$ por cada $k$ (se deduce por simetría).

Answer 1

Por inducción: Supongamos que la proposición es verdadera para (digamos) $m=5$ , donde $m=n+1$ es el número total de bolas, por lo que las urnas pueden tener $k=1\cdots 4$ bolas rojas con probabilidad uniforme. El experimento entonces se puede imaginar así: tenemos 4 urnas, cada una con 5 bolas, la primera con $1$ bola roja, la segunda con 2, etc. Escogemos una de estas 4 urnas, con la misma probabilidad, y luego escogemos una bola con probabilidad uniforme de la urna. Esto es lo mismo que decir que elegimos una bola al azar, siempre de manera uniforme, del total $4\times 5=20$ bolas. La siguiente imagen ayuda (espero) a visualizar las posibles alternativas.

A la izquierda, tenemos las 4 urnas, y las 20 bolas, de las que sacaremos una. A la derecha, las mismas bolas están dispuestas con un desplazamiento a lo largo de la diagonal. De esta manera podemos identificar todas las bolas que, si se seleccionan, llevarán a cada una de las nuevas urnas (diagrama inferior). Como tenemos el mismo número de bolas totales para cada nueva urna, cada una tendrá la misma probabilidad.

Answer 2

Lo mejor que puedo hacer aquí es un argumento inductivo:

• Claramente, después de $0$ sorteos, siempre hay exactamente $1$ bola roja con una probabilidad de $1 = \frac1{0+1}$ es decir, la certeza de estar allí.

• Para el caso inductivo, observamos que el dibujo $n + 1$ bolas comienza con el dibujo $n$ bolas, y luego otra. Después de sacar la $n$ bolas, hay una probabilidad uniforme de cualquier número de bolas rojas en la urna de $1$ a $n+1$ por inducción. Es decir, para cualquier $1 \leq k \leq n+1$ la probabilidad de $k$ bolas rojas es $\frac1{n+1}$ . Ahora, ¿cuál es la probabilidad de tener $k$ bolas rojas después $n + 1$ ¿Dibujos? Consideremos algunos casos:

  1. Si $2 \leq k \leq n + 1$ tenemos dos casos más a considerar con probabilidad no nula: $k$ bolas después $n$ sorteos, y luego sacar una bola azul, o tenemos $k - 1$ después de $n$ sorteos, y luego sacamos una bola roja. Ahora, después de haber dibujado $n$ veces, hay son $n+2$ bolas en total en la urna. Las posibilidades de sacar una bola bola azul, dadas $k$ bolas rojas en la urna es $\frac{n + 2 - k}{n + 2}$ . Las posibilidades de sacar una bola roja dada $k - 1$ bolas rojas es $\frac{k - 1}{n + 2}$ . Los dos números de bolas rojas después de $n$ son igualmente probables por la hipótesis inductiva, con probabilidad $\frac1{n+1}$ . La probabilidad global es entonces $\frac1{n + 1}(\frac{n + 2 - k}{n + 2} + \frac{k - 1}{n + 2}) = \frac1{n + 2}$ .

  2. Si $k = 1$ entonces nunca debemos sacar una bola roja. Así que debemos tener exactamente $1$ bola roja que queda después de $n$ dibuja, y luego dibuja una bola azul. Por inducción, la probabilidad de $1$ balón después de $n$ dibujar es $\frac1{n+1}$ . Sacar una bola azul después de esto tiene probabilidad $\frac{n+1}{n+2}$ . Multiplicando las dos probabilidades se obtiene fácilmente la $\frac{1}{n+2}$ .

  3. Si $k = n+2$ entonces el problema es simétrico, considerando $k=1$ para las bolas azules en lugar de las rojas, por lo que se aplica el argumento anterior.

---

Parece que Polya eligió esta pregunta intencionadamente desafiar nuestras propias intuiciones, que a menudo son erróneas. Parece haber elaborado la pregunta también para obligarnos a utilizar un ingenioso argumento de inducción, rematado con la guinda de un argumento basado en la simetría. Naturalmente, nos inclinamos a pensar en algún tipo de distribución de probabilidad geométricamente decreciente a través de $n$ . Una vez realizada la simetría, debemos actualizarla: quizás la distribución se aproxime a una distribución normal como $n$ ¿se hace grande? Estas son ciertamente las intuiciones que tuve cuando vi esta pregunta. Pero no me fío de mi intuición. Y hago bien en no hacerlo. Esta es una buena demostración de dónde falla la intuición, al menos al principio, antes de que nos empapemos realmente del problema. Así que buscamos en su lugar una demostración rigurosa, y la más elegante.

Como dijo Einstein en una ocasión, "todo debe hacerse tan simple como sea posible, pero no más simple". Erdos solía decir que las pruebas más elegantes eran "de libro". No voy a manchar el nombre de ninguno de los dos afirmando que lo anterior es "lo más sencillo posible" o "de libro", pero sin duda es lo mejor que se me ocurre. Intuitivamente, no creo que se pueda "comprimir" mucho más el argumento, sin perder su esencia. Que intuición que no puedo explicar, es sólo una corazonada.

Dicho esto, el clave Los pasos del argumento, creo, son los siguientes. El primero es dar con la a la derecha idea de inducción: es decir, inducción sobre $n$ no $k$ . Hay un momento conceptual "aha" cuando te das cuenta de que el dibujo $n + 1$ las bolas son las mismas que las del primer dibujo $n$ bolas, y luego dibujar otra. El segundo momento "aha" es cuando sigues tu idea anterior para la inducción, y notas que todos los valores de $k$ bolas después $n + 1$ dibuja, excepto los casos de esquina de $n + 2$ y $1$ puede ocurrir exactamente de dos maneras: o bien $k$ las bolas se eligen entre $n$ y luego no más, o $k - 1$ son elegidos, y $1$ más. Seguimos esta corazonada, calculamos las matemáticas y, de repente, aparece la respuesta correcta. Entonces nos quedan los casos de esquina. El caso de $1$ también funciona, ¡hurra! El toque final de elegancia es utilizar un argumento simétrico en el caso de $n+2$ en lugar de elaborarlo desde cero.

---

Hay una forma más corta de explicar esto, casi intuitivamente, pero pierde la nitidez del argumento anterior. Aun así, es una buena intuición auxiliar para complementar lo anterior. De nuevo, imaginemos la prueba inductiva. Imagina todos los valores posibles para las bolas rojas: $1, 2, 3, \dots, n+2$ . En el siguiente paso, cada elección "regala" parte de su probabilidad a la siguiente. Está claro que los valores más grandes dan más que los más pequeños: porque hay más posibilidades de sacar otro rojo una vez que ya se tiene el rojo. Pero también obtienen más, porque obtienen un valor del número inferior. Aun así, en conjunto pierden. Cada uno obtiene $\frac{k - 1}{n + 2}$ y da $\frac{k}{n + 2}$ Así que $1$ "regala" un valor de $\frac1{n + 2}$ a $2$ . $2$ "consigue" esto, y regala $\frac2{n + 2}$ a $3$ etc. Finalmente, cuando todos los valores se transmiten de esta manera, la distribución vuelve a ser uniforme, excepto que ahora con $\frac1{n + 2}$ en lugar de $\frac1{n + 1}$ .

Answer 3

Este es un argumento no inductivo:

El proceso se puede simular de la siguiente manera: Comienza con una bola roja seguida de una azul en una línea. En cada paso, elija una bola de la línea (uniformemente al azar), e inserte una bola inmediatamente antes de ella, del mismo color que la bola elegida.

Después de cualquier número de pasos, la línea consiste en un montón de bolas rojas seguidas de un montón de bolas azules, y la última bola roja es la misma que la bola roja original. Si etiquetamos esta bola roja original 1 y luego etiquetamos todas las bolas insertadas en el orden en que fueron insertadas (y no etiquetamos la bola azul original, que ahora está al final de la línea), el número de bolas rojas es ahora la posición del número 1.

Sin embargo, todas las permutaciones de los números del 1 al n son igualmente probables, por lo que la posición del número 1 tiene la misma probabilidad de estar en cualquier lugar.