Calcular la expectativa de pasos de decisiones $n$ diferentes bolas de la misma

Question

Supongamos que se nos da $n$ bolas de diferentes colores. Cada vez que levantar dos bolas al azar y cambiar el color de la segunda bola a la de la primera, luego nos ponemos de vuelta. La pregunta es ¿cuál es la expectativa de pasos cuando estas bolas de convertirse en el mismo color.

He resuelto el problema de la $n=2, 3, 4$. El ingenuo solución es resolver un sistema de ecuaciones recursivas. Pero hay también muchos estados si $n$ es mayor de $4$.

Según lo solicitado por el comentario, ahora os presento mi solución para $n=3$; similar método funciona para $n=4$. Deje $E(1, 2, 3)$ ser el deseado expectativa, tenemos $$ E(1, 2, 3)=1+\frac{1}{6}(E(1, 1, 2)+E(1, 2, 2)+etc.)=1+E(1,1, 2) $$ y $$ E(1, 1, 2)=1+\frac{1}{3}(E(1,1,2)+E(1,1,1)+E(1, 2, 2))=1+\frac{2}{3}E(1,1,2). $$ No es difícil ver que $E(1,1,2)$ es finito, por lo tanto $E(1,1,2)=3$$E(1,2,3)=4$.

P. S. me preguntó esto por un teléfono entrevistador. Si yo o no a la pregunta equivocada, entonces espero que no podría ser un " inteligente y rápida solución para casos generales.

Answer 1

El seguimiento de los Cristianos Blatter la respuesta, me crujió a través de todas las ecuaciones para $n=5$ y, el uso Cristiano de la notación, se encontró

$$E_{11111}=16$$

Junto con el trivial de los resultados de la $E_1=0$$E_{11}=1$, el OP informó $E_{111}=4$, y otro de cálculo para obtener $E_{1111}=9$, la secuencia de los valores esperados,

$$0,1,4,9,16,\ldots$$

parece sospechosamente familiar. Le tocaría a alguien para echar un vistazo a $n=6$. También podría ayudar si alguien controla de forma independiente de mi trabajo en $n=5$ (e $n=4$, para el caso), para asegurarse de que yo no estoy engañando a mí mismo. (Observación, añadió más tarde: me escribió una rápida y sucia de la simulación por ordenador y miró casos hasta el $n=10$. Los resultados parecen estar de acuerdo con $(n-1)^2$ como el valor esperado. Esto me da un poco más de confianza que hice el $n=5$ de los casos correctamente. Aún así, nadie debería tomar mi palabra para ella.)

Si, de hecho, los valores esperados son todas las plazas, no debe ser una simple prueba, pero no tengo idea de lo que podría ser.

Answer 2

Nota: La siguiente "viejo" respuesta se ocupa de la organización de los experimentos numéricos sobre este problema. Para una solución completa del problema de verificación de mi otra respuesta a continuación.

Al analizar este juego debemos olvidar los nombres de los colores. Los estados del juego son las particiones de $n$, es decir, las diferentes formas de escritura $n$ como suma de enteros positivos. Para $n=3$ estos son $$(3), (2,1), (1,1,1)\ ,$$ y para $n=5$ hay $7$ de ellos, a saber $$(5), (4,1), (3,2), (3,1,1), (2,2,1), (2,1,1,1), (1,1,1,1,1)=:(1^5)\ .$$ Para $n=10$ tendríamos $42$ estados. El estado inicial del juego es $(1^n)$, y el estado final es $(n)$.

En el caso de $n=5$ tenemos las ecuaciones $$\eqalign{E_5&=0\cr E_{41}&=1+{4\over5}\cdot{3\over4}E_{41}+{4\over5}\cdot{1\over4}E_5+{1\over5}E_{32}\cr E_{32}&=1+{3\over5}\cdot{2\over4}E_{32}+{3\over5}\cdot{2\over4}E_{41}+{2\over5}\cdot{3\over4}E_{32}+{2\over5}\cdot{1\over4}E_{32}\cr}$$ y $4$ más de este tipo.

Tal vez usted puede manejar los casos $5$, $6$, y $7$; luego pídale a OEIS si los números significan algo..

Answer 3

Esto es casi una Moran proceso: la única diferencia es que en una Moran proceso, las dos bolas se realiza un muestreo con reemplazo, de modo que con una probabilidad de $1/n$ una bola sustituye a sí mismo y no pasa nada. En el Moran proceso, se espera que el número de pasos hasta la "fijación" (todas las pelotas que al ser del mismo color) a $t^*=n(n-1)$ (ver, por ejemplo, WJ Ewens, Matemática de la Genética de poblaciones, 2004, (3.54)). Desde una fracción de $1/n$ de esos pasos son auto-sustituciones que se han omitido en este proceso, se espera que el número de pasos que en este caso es $t=(1-1/n)t^*=(n-1)^2$.

Debo mencionar que la llave de paso en la derivación de la Moran proceso es que para calcular el tiempo esperado para la fijación, por simetría, uno puede elegir a un solo balón y el estado en que está uno a tomar, y luego simplemente seguir el número de bolas con su color. Esto reduce drásticamente el tamaño del espacio de estado y le da un simple recursividad.

Answer 4

@Daniel Weissmann la respuesta es la clave para la solución completa que sigue.

Es suficiente para calcular el número esperado de dibujos bajo la condición de que el color rojo de las ganancias. Sólo tenemos que distinguir la $n+1$ estados $s_k$ $\>(0\leq k\leq n)$ donde hay $k$ bolas rojas y $n-k$ nonred bolas. Los estados $s_0$ $s_n$ son los estados del terminal. Cuando estamos en estado de $s_k$, $1\leq k\leq n-1$, el siguiente dibujo va a alterar el estado iff una bola roja y una nonred pelota se dibujan. Con igual probabilidad esto lleva a que el estado $s_{k-1}$, resp. $s_{k+1}$. Si se denota la probabilidad de ganar cuando en el estado de $s_k$ $p_k$ con lo que tenemos $$p_k=(1-2\lambda_k)p_k+{\lambda_k}(p_{k-1}+p_{k+1})\ ,$$ donde $\lambda_k={k(n-k)\over n(n-1)}$. Esto implica $p_{k-1}-2p_k+p_{k+1}=0$, que junto con $p_0=0$, $p_n=1$ conduce a la "comportamiento lineal" $$p_k={k\over n}\qquad(0\leq k\leq n)\ .\tag{1}$$ Denotan por $e_k$ $(1\leq k\leq n)$ el número esperado de planos complementarios cuando estamos en estado de $s_k$, bajo la condición de que el rojo gana. Entonces tenemos la siguiente recursión, válido para $1\leq k\leq n-1$: $$e_k={1\over p_k}\biggl(\lambda_kp_{k-1}(e_{k-1}+1)+(1-2\lambda_k)p_k(e_k+1)+\lambda_k p_{k+1}(e_{k+1}+1)\biggr)\ .$$ El uso de $(1)$ esto puede ser simplificado a $$2k e_k=(k-1)e_{k-1}+(k+1)e_{k+1}={n(n-1)\over n-k}\qquad(1\leq k\leq n-1)\ .$$ Ahora ponemos $$f_k:={ke_k\over n(n-1)}\quad(1\leq k\leq n-1), \qquad f_0=f_n:=0$$ y obtener las siguientes ecuaciones para el $f_k$ $\>(1\leq k\leq n-1)$: $$-f_{k-1}+2f_k-f_{k+1}={1\over n-k}\qquad(1\leq k\leq n-1)\ .$$ Deje $A$ ser la banda de la matriz de este sistema (todos los elementos $\geq2$ fuera de la diagonal principal son cero). Su inverso $B=[b_{ik}]$ está dado por $$b_{ik}=\cases{{(n-i)k\over n} & $(k\leq i)$\cr {(n-k)i\sobre n}&$(k\geq i)\ .$\cr}$$ De ello se sigue que $$e_1=n(n-1)f_1=n(n-1)\sum_{k=1}^{n-1}b_{1k}{1\over n-k}=n(n-1)\sum_{k=1}^{n-1}{(n-k)\cdot1\over n(n-k)}=(n-1)^2\ .$$