Un juego probabilístico con bolas y urnas

Question

Tenemos $N$ urnas formando un círculo y $M<N$ bolas (por ejemplo, $N=9,M=6$ en el diagrama). En cada paso visitamos, secuencialmente, en el sentido de las agujas del reloj, una urna. Si está ocupada por una bola, decimos a $hit$ ha ocurrido. En otros lugares ( Srta. ), elegimos al azar uno de los $M$ bolas y moverlo a la urna actual. El objetivo es calcular el porcentaje medio de aciertos, para un $N,M$ A largo plazo.

Me enfrenté a este problema hace algunos años, para alguna aplicación concreta (algún modelo de caché). No es terriblemente difícil, pero no es tan sencillo como podría parecer. También es interesante contrastar con la intuición (¿por qué lado apostarías en este ejemplo?).

Tengo una solución, ( con dos pruebas diferentes - las publicaré pronto publicado en la respuesta más abajo) pero me gustaría saber de otros intentos - o quizás alguna referencia - esto probablemente debería haber sido estudiado en alguna parte.

Algunos resultados (exactos):

 N  M   p
------------
 3  2  1/3
 4  2  1/7
 5  3  7/25

Editado: como se ha averiguado semiempíricamente en una respuesta más adelante, el porcentaje de aciertos viene dado por $$p= \frac{S(N-1,M-1)}{S(N,M)}$$ donde $S(N,M)$ son Números Stirling del segundo tipo .

Answer 1

Dada: $$ f(a,a)=1 $$ $$ f(0,a)=0 $$ $$ f(a,b)=a \cdot f(a,b-1)+f(a-1,b-1) $$ La probabilidad es: $$ P(M,N)=\frac{f(M-1,N-1)}{f(M,N)} $$ Esto fue lo que encontré después:

• Generar un montón de aproximaciones mediante una simulación.
• Adivinando sus valores exactos como fracciones.
• Detección y ampliación de patrones para $M=N-1$ y $M=2$
• Detectar el ligero indicio de que el denominador de un número es el numerador de otro.
• Desplazamiento de fracciones a la representación requerida para que el patrón sea absoluto.
• Utilizando este patrón para hacer más conjeturas.
• Mirando durante mucho tiempo un montón de números aparentemente revueltos.

Todavía queda por hacer:

• Averiguar por qué funciona esta fórmula, no lo sé, pero al menos por ahora le daré un descanso.
• Buscando una representación que proporcione un cálculo más eficiente, (¿es realmente posible?), la fórmula actual es $O(M \cdot (N-M))$ .

Answer 2

A largo plazo, el sistema alcanzará un estado estacionario en el que cada paso hace girar la distribución de probabilidad en una urna para que siga siendo la misma en relación con la urna que se visitará a continuación (la "urna actual"). Así, habrá una distribución estacionaria sobre los posibles patrones de bolas en relación con la urna actual. Esta distribución puede determinarse explícitamente, e implica la recursión que encontró eBusiness.

Al analizar los patrones de bolas, podemos ignorar la última urna (en el sentido de las agujas del reloj desde la urna actual), que era la urna actual del paso anterior, ya que siempre contiene una bola. Sólo consideraré los estados con una bola en la última urna, y no incluiré esa bola en las representaciones de los patrones de bolas en lo que sigue.

Para cada patrón de bolas, comenzando por la urna actual y moviéndose en el sentido de las agujas del reloj, forme un "producto de huecos" que contenga un "factor de huecos" por cada urna vacía ("hueco"), siendo el factor de huecos el número de bolas que aún no se han encontrado. Por ejemplo, para $N=8$ , $M=4$ el patrón *--*-*- (donde "*" representa una bola y "-" representa un hueco; recuerde que la última bola no se muestra) se asocia con el producto $3\cdot3\cdot2\cdot1$ . La distribución estacionaria sobre los patrones viene dada por estos productos, normalizados por su suma.

Para demostrar esto, tenemos que mostrar que el proceso deja invariante esta distribución; es decir, para cada patrón $i$ Debemos tener

$$\sum_jp_ip_{ij}=p_j\;,$$

donde $p_i$ es la probabilidad estacionaria y $p_{ij}$ es la probabilidad de transición del estado $i$ al estado $j$ . Podemos multiplicar esta ecuación por la constante de normalización (la suma de los productos de brecha) para expresarla en términos de los productos de brecha en lugar de las probabilidades normalizadas. Demostraré que esto se cumple por inducción sobre $M+N$ .

El caso inicial $M=1$ es fácil de comprobar: Sólo hay un estado posible, en el que la bola única está en la última urna, y por lo tanto su probabilidad sale correctamente como $1$ . Desde $N\ge M$ Esto fundamenta la inducción.

En general $M$ y $N$ Podemos distinguir dos tipos de patrones, dependiendo de si la urna anterior a la última (la "penúltima urna"), que era la urna actual hace dos pasos (en el "penúltimo paso") contiene una bola.

El caso en el que no es así es relativamente sencillo. El penúltimo paso dejó una bola en la penúltima urna. Si no hay ninguna bola allí, significa que el paso anterior sacó la bola de allí, y por lo tanto no sacó una bola de ningún otro lugar. Por lo tanto, en este caso sólo hay un patrón predecesor posible, y es el mismo patrón excepto que todas las bolas, excepto la última, se han desplazado hacia delante en uno. La probabilidad de esta transición es $1/M$ y esta es también la relación de los productos de la brecha, ya que el desplazamiento ha convertido una brecha con $M$ bolas para entrar en un hueco con $1$ balón por venir. Por lo tanto, la condición de estacionariedad se cumple en este caso.

El segundo caso, en el que la penúltima urna contiene una bola, es un poco más complicado; aquí es donde necesitamos la hipótesis de inducción. Para ver de qué estados podría haber surgido ese patrón, podemos desplazarlo hacia atrás en uno (creando un hueco en la parte delantera). Así es como se veía al paso anterior, excepto que hay un hueco donde estaba la bola que ahora está en la última urna. Así que obtenemos los posibles patrones predecesores colocando una bola en uno de estos huecos.

Ahora vamos a truncar el patrón (no desplazado) eliminando la primera urna, y luego desplazar también el patrón truncado (creando un hueco en la parte delantera del patrón truncado). De nuevo tenemos que considerar dos casos, dependiendo de si la primera urna contiene una bola. Si es así, el patrón truncado tiene $M'=M-1,N'=N-1$ y si no lo hace, entonces $M'=M,N'=N-1$ .

De nuevo, el primer caso (cuando la primera urna contiene una bola) es relativamente sencillo. Es útil considerar un ejemplo; consideremos el patrón (no truncado, no desplazado) **-*--** ; entonces tenemos los siguientes patrones:

• **-*--** (original)
• -**-*--* (desplazado)
• *-*--** (truncado)
• -*-*--* (truncado y desplazado).

Los patrones no desplazados tienen los mismos productos de brecha. Los huecos de los patrones desplazados tienen una correspondencia unívoca entre sí y están asociados a los mismos factores de hueco, excepto el hueco de la parte delantera, que vale $M$ en el patrón no truncado y $M-1$ en el patrón truncado. Así, si llenamos el hueco de la parte delantera, todos los factores de hueco son iguales, mientras que si llenamos cualquier otro hueco, obtenemos un factor $M-1$ en lugar de $M$ en el patrón truncado. Pero esto funciona perfectamente, ya que las probabilidades de transición son $1$ si llenamos el hueco de la parte delantera, y si llenamos cualquier otro hueco, $1/(M-1)$ en el caso truncado y $1/M$ en el caso no truncado. Así, la condición de estacionariedad para el patrón no truncado se deduce de la del patrón truncado, que se cumple por la hipótesis de inducción.

El segundo caso (cuando la primera urna está vacía) es un poco más complicado. Volvamos a utilizar un ejemplo:

• -*-*--** (original)
• --*-*--* (desplazado)
• *-*--** (truncado)
• -*-*--* (truncado y desplazado).

Ahora hay un hueco más en el patrón desplazado no truncado que en el truncado desplazado (dos en la parte delantera en lugar de sólo uno), por lo que hay un término más en la condición de estacionariedad. Si numeramos los huecos en el patrón desplazado no truncado empezando por $0$ en la parte delantera y denota los productos de la brecha que obtenemos al rellenar la brecha $i$ en los patrones desplazados no truncados y truncados por $g_i$ y $g_i'$ respectivamente, y los productos de brecha de los patrones no desplazados por $g$ y $g'$ las condiciones de estacionalidad son

$$ \begin{eqnarray} 1\cdot g_0+\frac1Mg_1+\frac1M\sum_{i>1}g_i &=& g\,\,\,\text{(untruncated),}\\ 1\cdot g_1'+\frac1M\sum_{i>1}g_i' &=& g'\,\,\,\text{(truncated).} \end{eqnarray} $$

Pero $Mg_0=(M-1)g_1$ ya que los patrones correspondientes sólo difieren en si el primer hueco está antes o después de la primera bola, por lo que la primera condición se puede reescribir como

$$ 1\cdot g_1+\frac1M\sum_{i>1}g_i=g\;. $$

Los factores de desfase son los mismos en los casos truncados y no truncados, excepto por un factor adicional $M$ para los patrones no truncados, así que esto es sólo un múltiplo de la condición para el caso truncado, que se mantiene por la hipótesis de inducción. Esto completa la prueba por inducción.

La tasa de aciertos es la suma de las probabilidades estacionarias de todos los patrones con una bola en la primera urna, que es la suma de los productos de los huecos de todos esos patrones dividida por la suma de los productos de los huecos de todos los patrones. Denotemos por $f(M,N)$ la suma de los productos de la brecha para todos los patrones. Entonces la suma de los productos de hueco para los patrones con una bola en la primera urna es $f(M-1,N-1)$ ya que los patrones correspondientes con la primera urna y la bola eliminada tienen los mismos productos de hueco. Por otro lado, la suma de los productos de hueco para los patrones sin bola en la primera urna es $Mf(M,N-1)$ ya que los patrones correspondientes con la primera urna y el hueco eliminados contienen un factor menos $M$ para el hueco que falta. Así pues, tenemos $f(M,N)=f(M-1,N-1)+Mf(M,N-1)$ y el porcentaje de aciertos es $f(M-1,N-1)/f(M,N)$ . Junto con las condiciones iniciales $f(0,N)=0$ (ya que siempre debe haber una bola en la última urna) y $f(N,N)=1$ (ya que en este caso sólo hay un estado y su producto vacío es $1$ ), esta es la recursión que encontró eBusiness.

P.D.: Nótese que hay una correspondencia directa entre los recuentos de estados en la respuesta de leonbloy y los productos de brecha en la mía, ya que mis factores de brecha corresponden al número de colores posibles para la brecha en el enfoque de leonbloy.

Answer 3

Parece que la probabilidad $p$ viene dada por $p=S(n-1,m-1)/S(n,m)$ donde $S(\cdot,\cdot)$ denota los números de Stirling del segundo tipo. Por lo tanto, debemos ver nuestra historia de las bolas y las urnas de tal manera que estos números jueguen un papel. Propongo lo siguiente:

El número de Stirling $S(n,k)$ cuenta el número de maneras de dividir el conjunto $[n]:=\{1,2,\ldots, n\}$ en $k$ subconjuntos no vacíos. Que las bolas estén coloreadas por $m$ diferentes colores. Supongamos que acabamos de visitar la urna $n\equiv 0$ y que la bola roja está ahora en esta urna. En la siguiente $n$ pasos cada urna $1$ , $\ldots$ , $n-1$ ve exactamente una bola: o bien la bola ya está allí o bien se busca en otro lugar. Número de urna $n$ puede ver un nuevo balón o no. Cuando el $n$ pasos son sobre una partición de $[n]$ en $m$ bloques se ha realizado: Las urnas que vieron una bola del mismo color pertenecen al mismo bloque. Tenemos un acierto en el $n^{\rm th}$ paso si el bloque rojo está formado únicamente por el número de urna $n$ .

Ahora hay $S(n,m)$ particiones de $[n]$ en $m$ bloques y $S(n-1,m-1)$ particiones de $[n]$ donde el elemento $n$ es un bloque de un elemento. Así que si se pudiera demostrar que a la larga todas estas particiones son equiprobables, habríamos terminado.

Answer 4

Había ideado dos derivaciones, una utilizando una cadena de Markov (aquí aparecen los números de Stirling por su significado combinatorio), otra utilizando una recursión para las distribuciones de probabilidades para diferentes $N,M$ (esto lleva a una recursión como la de la respuesta de eBusiness). Pongo aquí la primera, porque es más sencilla y la posterior es más difícil de justificar. Al final, algunas asimétricas.

---

Numeremos las urnas relativamente a la posición actual, de modo que urna $1$ es el siguiente en ser visitado, urna $N$ es el más visitado recientemente.

La clave para obtener una cadena de Markov solucionable es definir los estados de forma aparente manera "inflada": en lugar del estado natural, con $M$ componentes, (para cada bola, lista su posición), el estado será un vector de $N$ tomando valores en $1 \cdots M$ . El vector de estado enumera, para cada urna, la última bola colocada en ella (se supone que todas las urnas ya han sido visitadas al menos una vez).

Observe que todos los números de las bolas deben aparecer en la lista. Algunas se repetirán; pero podemos detectar en qué urna está actualmente una bola: es la más a la derecha (índice mayor=más reciente). Entonces, tendremos un acierto si el primer componente no se repite. Y la regla de transición de estado es: si golpear , desplazar y girar los elementos a la izquierda; si Srta. , se desplaza hacia la izquierda y coloca en la última posición un número al azar (la bola seleccionada).

Por ejemplo, para la posición en el diagrama (N=9, M=6; asumimos algún pasado arbitrario para las urnas actualmente vacías), suponiendo que estamos a punto de visitar la urna superior, podríamos tener esta secuencia de estados (los asteriscos corresponden a las urnas vacías; son sólo aquellos números que tienen alguna repetición a la derecha).

S(t)   = \[ 3  4\* 5  2\* 4  2  6\* 1  6 \]
                                       hit
S(t+1) = \[ 4\* 5  2\* 4  2  6\* 1  6  3 \]   
                                       miss; ball '6' was randomly chosen
S(t+2) = \[ 5  2\* 4  2  6\* 1  6\* 3  6 \]   

Fíjate en eso:

• Un estado válido corresponde a un mapeo suryectivo de $\{1 \cdots N\}$ a $\{1 \cdots M\}$ (deben aparecer todos los números de las bolas).
• Todos los estados válidos son accesibles desde cualquier otro.
• Un estado puede tener una transición de salida con probabilidad 1 (estado de éxito), o $M$ transiciones igualmente probables. Por lo tanto, la matriz de transición sólo tiene $1$ y $1/M$ como entradas no nulas.
• Transiciones en curso: (esta es la clave) cada estado tiene una transición de entrada con probabilidad 1 o M con $1/M$ ; en el ejemplo anterior: podemos decir que el estado $S(t+1)$ es después del golpe con un solo estado previo posible); y ese estado $S(t+2)$ es después de la visita a con $M$ posibles estados anteriores. Por tanto, tanto las filas como las columnas de la matriz de transición suman uno: es doblemente estocástico .

Pero un irreducible [ editado : en realidad también es ergódica, como se señala en los comentarios] y la cadena de Markov doblemente estocástica, en estado estacionario, tiene estados equiprobables .

Ahora, el número total de estados (número de mapeos) es equivalente al número de formas de colocar $N$ objetos en $M$ contenedores, sin ningún contenedor vacío; esto viene dado por el número de Stirling del segundo tipo (multiplicado por $M!$ para tener en cuenta las bolas distinguibles): $\#S= M! \; S(N,M)$

Para contar los estados de golpeo $S_h$ El primer componente debe ser único, por lo que $\#S_h = M (M-1)! \; S(N-1,M-1) = M! \; S(N-1,M-1)$

La probabilidad de acierto, entonces, es sólo el número de estados de acierto sobre el número total de estados.

$$p = \frac{\#S_h}{\#S} = \frac{S(N-1,M-1)}{S(N,M)}$$

Algunos valores:

       M    2        3        4          5        6         7        8  
     N  
     3   0.33333
     4   0.14286  0.50000
     5   0.06666  0.28000  0.60000
     6   0.03226  0.16666  0.38462   0.66667
     7   0.01587  0.10299  0.25714   0.46429   0.71429
     8   0.00787  0.06522  0.17695   0.33333   0.52632   0.75000
     9   0.00392  0.04198  0.12432   0.24471   0.39683   0.57576  0.77778

Por cierto, para el diagrama de ejemplo (9,6), el porcentaje de aciertos es de aproximadamente el 40%.

---

Asintótica : Para grandes $N,M$ Los números Stirling de segunda clase crecen rápidamente y sus asimétricos son bastante complicados. Aquí va un enfoque probabilístico muy simple.

Supongamos que acabamos de visitar la urna superior; debe estar ocupada. Podemos estimar la probabilidad de que la bola sobreviva en esa posición después de una ronda completa como la probabilidad de que en $N-1$ trata de que nunca ocurra el evento "fallo y mi bola fue seleccionada". Esta supervivencia corresponde a un evento de éxito. Entonces, asumiendo la independencia:

$$p \approx (1 - \frac{1-p}{M})^{N-1} \approx e^{-r(1-p)}$$

con $N,M \to \infty$ y $r = N/M$ . Lo implícito $p(r)$ podría expresarse explícitamente mediante la función de Lambert (véase aquí ).

El supuesto de independencia no es exacto, pero el error es asimétricamente despreciable. Tengo otro argumento probabilístico (mejor), que lleva a la misma expresión, me lo ahorraré (en caso de que alguien esté interesado, que me envíe un mensaje).

Answer 5

Para $M=2$ Me sale $\frac{1}{2^{N-1}-1}$ . Si alguna vez golpeamos, las dos bolas están en los dos últimos recipientes, por lo que después de cada $1$ habrá una carrera de $0$ 's al menos $N-2$ largo. Si recogemos la pelota que acabamos de golpear $N-2$ veces seguidas, golpearemos la otra bola y la carrera será $N-2$ . Si recogemos el balón que estaba detrás $N-1$ veces seguidas tendremos una racha de $N-1$ . Si elegimos las dos bolas diferentes sucesivamente, estamos en el mismo estado de tener las dos bolas en los dos últimos bins visitados, por lo que la carrera media a partir de ahora es la misma que una carrera media. Con la probabilidad $\frac{1}{2}$ elegimos AB o BA y añadimos dos ceros a la carrera media. Con la probabilidad $\frac{1}{4}$ elegimos AAB o BBA y añadimos tres ceros. Esto continúa hasta $\frac{1}{2^{N-3}}$ añadimos $N-2$ ceros, más $\frac{1}{2^{N-1}}$ añadimos $N-1$ ceros. Así que si $r$ es la carrera media, tenemos $$r=\frac{N-2}{2^{N-2}}+\frac{N-1}{2^{N-1}}+\sum_{i=1}^{N-3}\frac{i+1+r}{2^i}+\frac{N-1+r}{2^{N-1}}$$ $$\frac{3}{2^{N-1}}r=3-\frac{N}{2^{N-3}}+\frac{N-2}{2^{N-2}}+\frac{N-1}{2^{N-1}}+\frac{N-1}{2^{N-1}}$$ $$r=2^{N-1}-2$$

Así que la densidad de unos es $1$ en $2^{N-1}-1$

Añadido: otra forma de ver esto es utilizar la matriz de transición de Markov. Hay una bola en la urna en la que estamos actualmente. Definir el estado $1$ para tener la otra bola en la siguiente urna hasta el estado $N-1$ teniendo la otra bola en el último contenedor visitado. Estado $1$ devuelve un acierto y pasa al estado $N-1$ . Todos los demás estados $k$ devuelven un fallo y una transición con probabilidad $0.5$ al estado $k-1$ y la probabilidad $0.5$ al estado $N-1$ . Así que para $N=6$ la matriz tiene el siguiente aspecto $$\left(\begin {array} {c c c c c} 0&.5&0&0&0\\0&0&.5&0&0\\0&0&0&.5&0\\0&0&0&0&.5\\1&.5&.5&.5&.5\end{array}\right)$$ y el vector propio correspondiente al valor propio $1$ es $(1,2,4,8,16)^T$ dando un porcentaje de aciertos de $\frac{1}{31}$ como se ha reclamado.