Un problema de bolas y colores

Question

Una caja contiene n bolas coloreadas de 1 a n. Cada vez coges dos bolas de la caja, la primera y la segunda, ambas uniformemente al azar y pintas la segunda bola con el color de la primera. Después, vuelves a meter ambas bolas en la caja. ¿Cuál es el número esperado de veces que hay que hacerlo para que todas las bolas de la caja tengan el mismo color?

Respuesta (Spoiler puesto a través de rot13.com): Gur fdhner bs gur dhnagvgl gung vf bar yrff guna a.

Alguien me planteó este enigma hace unos cuatro años. Lo he pensado de vez en cuando, pero no he sido capaz de resolverlo. Sin embargo, me dieron la respuesta y sospecho que puede haber una solución elegante.

Gracias.

Answer 1

Probablemente pueda hacerse observando la suma de cuadrados de los tamaños de los grupos de colores y construyendo después una martingala adecuada. Pero he aquí una solución algo elegante: ¡invertir el tiempo!

Formulemos así la pregunta. Sea $F$ sea el conjunto de funciones de $\{1,\ldots,n\}$ a $\{1,\ldots,n\}$ que son casi identidad, es decir, $f(i)=i$ excepto un único valor $j$ . Entonces, si $f_t$ es una secuencia i.i.d. uniforme de $F$ y $$g_t=f_1 \circ f_2 \circ \ldots \circ f_t$$ puede definir $\tau= \min \{ t | g_t \verb"is constant"\}$ . Se trata entonces de calcular $\mathbb{E}(\tau)$ .

Ahora, también se puede definir la secuencia $$h_t=f_t \circ f_{t-1} \circ \ldots \circ f_1$$ Es decir, la diferencia es que mientras $g_{t+1}=g_t \circ f_{t+1}$ aquí tenemos $h_{t+1}=f_{t+1} \circ h_t$ . Se trata de la inversión temporal del proceso original.

Obviamente, $h_t$ y $g_t$ tienen la misma distribución por lo que $$\mathbb{P}(h_t \verb"is constant")=\mathbb{P}(g_t \verb"is constant")$$ por lo que si definimos $\sigma=\min \{ t | h_t \verb"is constant"\}$ entonces $\sigma$ y $\tau$ tienen la misma distribución y, en particular, la misma expectativa.

Calculando ahora la expectativa de $\sigma$ es sencillo: si el rango de $h_t$ tiene $k$ valores distintos, entonces con probabilidad $k(k-1)/n(n-1)$ este número disminuye en 1 y, en caso contrario, permanece igual. Por lo tanto $\sigma$ es la suma de distribuciones geométricas con parámetros $k(k-1)/n(n-1)$ y su expectativa es $$\mathbb{E}(\sigma)=\sum_{k=2}^n \frac{n(n-1)}{k(k-1)}= n(n-1)\sum_{k=2}^n \frac1{k-1} - \frac1{k} = n(n-1)(1-\frac1{n}) = (n-1)^2 .$$

Answer 2

Considere sólo aquellas secuencias de selecciones que dan como resultado que el color final sea $c$ . Si en algún momento de una secuencia tenemos $k$ de las bolas de este color, podemos definir $E_k$ como el número esperado de selecciones a partir de aquí antes de que se coloreen todas las bolas $c$ .

Para ello, hay que tener en cuenta que no todas las selecciones son igual de probables: cada selección debe multiplicarse por la probabilidad de que dé lugar a $c$ siendo el color eventual. Felizmente, esta probabilidad es simplemente $k'/n$ donde $k'$ es el número de bolas coloreadas $c$ después de esta selección.

Eso nos da: $E_k = 1 + \frac{(k+1)(n-k)E_{k+1} + (k-1)(n-k)E_{k-1} + (n(n-1)-2k(n-k))E_k}{n(n-1)}$ .

Esto se simplifica a $2kE_k = \frac{n(n-1)}{n-k} + (k+1)E_{k+1} + (k-1)E_{k-1}$ . De ello se deduce que $E_1 = n/2 + E_2$ y, en general, si $E_{k-1} = w_{k-1}(n) + E_k$ entonces $E_k = w_k(n) + E_{k+1}$ con $w_k(n) = \frac{n(n-1)}{(n-k)(k+1)} + \frac{k-1}{k+1}w_{k-1}(n)$ .

La expectativa requerida, $E_1$ ahora resuelve:

$E_1 = \sum_{i=1}^{n-1}{w_i(n)}$

$ = n(n-1) \sum_{i=1}^{n-1}{ \frac{1}{(n-i)(i+1)}(1 + \sum_{j=i+1}^{n-1}{ \prod_{k=i+1}^j{ \frac{k-1}{k+1} } }) }$

$ = n(n-1) \sum_{i=1}^{n-1}{ \frac{1}{(n-i)(i+1)}(1 + \sum_{j=i+1}^{n-1}{ \frac{i(i+1)}{j(j+1)} }) }$

$ = n(n-1) \sum_{i=1}^{n-1}{ \frac{1}{(n-i)(i+1)}(1 + i(i+1)(\frac{n-1}{n} - \frac{i}{i+1})) }$

$ = n(n-1) \sum_{i=1}^{n-1}{ \frac{1}{n} }$

$ = (n-1)^2$ .

(Lo siento, no pude encontrar cómo hacer funcionar ecuaciones multilínea en jsMath, así que las dividí).

Answer 3

Esta respuesta está inspirada en el comentario de JBL a la respuesta de Aaron:

Fijar $n$ para no tener que incluirlo en mi anotación. En todos los demás aspectos, copia la notación de Aaron. JBL observa que parece haber números $f(1)$ , $f(2)$ , ..., $f(n-1)$ tal que $$ p_{\lambda} = \sum_{k \in \lambda} f(k). \quad \quad (*)$$

Demostraremos que tales $f$ y dar fórmulas para ellos. En particular, quedará claro que $f(1) = (n-1)^2/n$ demostrando el resultado. Por comodidad, fijamos $f(0)=f(n)=0$ .

---

Parece mejor describir la $f$ mediante la siguiente relación $$ \frac{k}{n} = \frac{k(n-k)}{n(n-1)} \left( - f(k-1) + 2 f(k) - f(k+1) \right) \ \mbox{for} \ 1 \leq k \leq n-1 \quad \quad (**)$$

Nuestra demostración se divide en dos partes: mostrar que existe una solución única para $(**)$ y demostrando que el $f$ obedece $(*)$ . Primero hacemos la segunda parte.

---

Debemos establecer la relación de Markov: $$\sum_{k \in \lambda} f(k) = 1 + \sum_{\mu} p(\lambda \to \mu) \sum_{k \in \mu} f(k).$$ Para cualquier $k$ en $\lambda$ la partición modificada $\mu$ contiene $k-1$ , $k+1$ o $k$ dependiendo de si perdemos una bola del color correspondiente, ganamos una o mantenemos el mismo número. Las probabilidades de estos sucesos son $k(n-k)/n(n-1)$ , $k(n-k)/n(n-1)$ y $1-2 k(n-k)/n(n-1)$ respectivamente.

Así que debemos demostrar que $$\sum_{k \in \lambda} f(k) = 1 + \sum_{k \in \lambda} \left( \frac{k(n-k)}{n(n-1)} f(k-1) + \left( 1- \frac{2k(n-k)}{n(n-1)} f(k) \right) + \frac{k(n-k)}{n(n-1)} f(k+1)\right).$$ Cancelación de $\sum_{k \in \lambda} f(k)$ de ambas partes, debemos demostrar que $$0 = 1 - \sum_{k \in \lambda} \frac{k(n-k)}{n(n-1)} \left( - f(k-1) + 2 f(k) - f(k+1) \right). $$

Por $(**)$ la ecuación definitoria de la $f$ 's, esto es $$1- \sum_{k \in \lambda} (k/n) = 1 - |\lambda|/n=0$$ ~ como desee.

Por lo tanto, si podemos encontrar $f$ 's obediente $(**)$ tendremos $(*)$ .

---

Sea $g_j$ sea la longitud $(n-1)$ vector $$( n-j, 2(n-j), 3(n-j), \ldots, j(n-j), \ldots, 3j, 2j, j)$$ La característica clave de $g_j$ es que $$- g_j(k-1) + 2 g_j(k) - g_j(k+1) = \begin{cases} n \quad k=j \\ 0 \quad k \neq j \end{cases}$$ donde fijamos $g_j(0)=g_j(n)=0$ . Sea $f$ sea el vector $(f(1), f(2), \ldots, f(n-1))$ .

Vuelva a escribir $(**)$ como $$ \frac{n-1}{n-k} = - f(k-1) + 2 f(k) - f(k+1).$$ Así que vemos que $$f = \sum_{k=1}^{n-1} \frac{n-1}{n(n-k)} g_k$$

En particular, $$f(1) = \sum_{k=1}^{n-1} \frac{n-1}{n(n-k)} (n-k) = \frac{(n-1)^2}{n}$$ como desee. Más generalmente, $$f(j) = \sum_{k=1}^{j-1} \frac{n-1}{n(n-k)} k(n-j) + \sum_{k=j}^{n-1} \frac{n-1}{n(n-k)} j(n-k) = \frac{(n-1)(n-j)}{n} \sum_{k=1}^{j-1} \frac{k}{n-k} + \frac{j(n-j)(n-1)}{n}.$$

---

Answer 4

Sólo deseo añadir algo de sentido a $f(k)$ ...

Déjalo:

$X_{i}$ - el número de bolas del color $i$ a la vez $t=0$ .

$A_{i}$ - el caso de que al final todas las bolas sean del color $i$ .

Usando esta notación:

$E(T|X_{1}=\lambda_{1},\ldots ,X_{n}=\lambda_{n}) = \sum E(1_{A_{i}}T|X_{1}=\lambda_{1},\ldots,X_{n}=\lambda_{n})$ .

Pero $E(1_{A_{i}}T|X_{1}=\lambda_{1},\ldots,X_{n}=\lambda_{n})$ depende únicamente de $\lambda_{i}$ y se denota por $f(\lambda_{i})$ .

Utilizando el análisis de "primer paso" obtenemos:

$E(1_{A_{i}}T|X_{i}=k)=dE(1_{A_{i}}(T+1)|X_{i}=k+1)+ dE(1_{A_{i}}(T+1)|X_{i}=k-1)+(1-2d)E(1_{A_{i}}(T+1)|X_{i}=k)$

donde $d=\frac{k(n-k)}{n(n-1)}$

Se puede calcular (utilizando el teorema de Doob o de otro modo) que $E(1_{A_{i}}|X_{i}=k)=\frac{k}{n}$ .

Y utilizando esto obtenemos la ecuación de David Speyer (**) para $f(k)$ .

Answer 5

Para n=3, un turno te lleva 2 de un color y 1 de otro. Para llegar a un solo color tienes que elegir uno de los 2 (prob=2/3), luego elegir el de impar (prob=1/2). Así que el número esperado de turnos es 1+3=4