Tirar pelotas en cubos con capacidad $2$

Question

$n$ se lanzan bolas al azar en $k$ contenedores de capacidad limitada $c$ . Si una bola cae en un contenedor lleno, "rebota" aleatoriamente en otro contenedor hasta que encuentra un contenedor no lleno.

¿Cuántas papeleras se espera que estén llenas después de lanzar todas las bolas? Una solución para $c = 2$ para $n < 2k$ es específicamente lo que busco. (Así que en este caso, encontrar el número de contenedores vacíos es igual de bueno).

Estoy teniendo problemas con el hecho de que el número de contenedores elegibles cambia a medida que se lanzan las bolas, dependiendo de dónde hayan caído hasta el momento. He mirado en otros problemas de bolas y contenedores aquí, pero no puedo encontrar ninguno que tiene esta característica. Editar: Esta pregunta también tiene esta función pero no tiene respuesta. Un comentarista dice: "Desgraciadamente, por lo que yo sé, se trata de un problema bastante insoluble". Pero quizá se pueda hacer algo para $c=2$ .

Si quieres saberlo, estoy intentando calcular equilibrios para una simulación de población en la que las criaturas (jugadores) pueden o no encontrarse. Si una criatura tiene la suerte de no toparse con otra (como una sola bola en un cubo), recibe comida gratis. Si dos criaturas chocan entre sí (dos bolas en un cubo), juegan una ronda de halcones y tórtolas. El simulador asume que una criatura puede saber cuándo dos criaturas ya se están encontrando en un lugar, y entonces se mantiene alejada.

Podría encontrar numéricamente los resultados específicos que necesito, pero me encantaría encontrar una solución general (para cualquier $n<2k$ incluso con $c=2$ ).

Answer 1

Supongamos que se lanzan bolas a los contenedores (sin tapar los contenedores) hasta que el doble del número de contenedores vacíos más el número de contenedores con una bola sea exactamente igual a $2k-n$ . Ahora, dejemos que $b_0$ , $b_1$ y $b_2$ es el número de contenedores con exactamente $0$ exactamente $1$ y con $2$ o más bolas, respectivamente.

Sabemos que $$b_0 + b_1 + b_2 = k,$$ y $$ 2b_0 + b_1 = 2k-n.$$

Restando la segunda ecuación del doble de la primera, obtenemos que $$b_1 + 2b_2 = n.$$ Por tanto, si lanzamos bolas a los contenedores (sin tapar los contenedores) hasta que se cumpla la condición anterior, y retiramos todas las bolas sobrantes de los contenedores a partir de dos o más bolas, el resultado es exactamente el mismo que si lanzamos $n$ bolas en $k$ cubos, limitando el tamaño de los cubos a $2$ .

Veamos ahora las expectativas para un proceso de Poisson. Esto no demostrará directamente tu teorema, pero deberías ser capaz de poner buenos límites sobre cuánto difiere la expectativa de un proceso de Poisson de tu problema exacto de las bolitas, y demostrar que te dará la respuesta correcta hasta aproximadamente $1/\sqrt{k}$ .

Un proceso de Poisson con tasa $\lambda$ arrojará un número esperado de $e^{-\lambda} k$ contenedores con $0$ bolas, y $\lambda e^{-\lambda} k$ contenedores con $1$ pelota. Por lo tanto, para encontrar la tasa correspondiente a $n$ bolas, tenemos que resolver las ecuaciones:

$$ 2 e^{-\lambda} k + \lambda e^{-\lambda} k = 2k - n,$$

o

$$ 2 - e^{-\lambda} (2 + \lambda) = \frac{n}{k}.$$

Podemos resolver esta ecuación numéricamente y representar gráficamente la fracción de cubos que se llenan como la relación entre bolas y cubos, $n/k$ va de $0$ a $2$ .

Si el número de casillas es igual al número de bolas, aproximadamente el 31,8% de las casillas se llenan con dos bolas. Si hay tres bolas por cada dos cubos, se llenan aproximadamente el 61,8% de los cubos.

De hecho, la misma solución se aplicará a cualquier capacidad máxima, aunque la resolución de las ecuaciones será más difícil.

Answer 2

Esto es más una sugerencia de enfoque que una solución. No obstante, creo que puede resultar útil.

Trabajar hacia atrás : Comience con cada uno de los $k$ contenedores llenos hasta su capacidad de $c=2$ pelotas. A continuación, retire las bolas una a una del conjunto de $2k$ hasta que tenga el número necesario $n$ restante.

I piense en (pero no puedo demostrarlo) que este proceso es estadísticamente equivalente a llenar los contenedores de la manera "directa". Parecería simplificar la enojosa tarea de determinar cuántos contenedores vacíos y llenos existen en cada fase.

No estoy seguro de que esto conduzca a una solución de forma cerrada... ¡pero podría ser!