La caja A tiene m bolas, la caja B tiene n bolas. Saca una bola al azar de una de las cajas. ¿Cuál es la expectativa de bolas restantes cuando una caja está vacía?

Question

Existen $m$ bolas en la casilla A y $n$ bolas en la caja B. Por cada vez, sacas una bola de cualquiera de las dos cajas con la misma probabilidad. (es decir, 1/2) Dejas de sacar cuando hay una caja vacía (es decir, paras en cuanto una caja se queda vacía).

a) ¿cuál es la expectativa del número de bolas en la caja no vacía cuando se deja de extraer?

b) si $m=n=c$ cuál es la tendencia la expectativa va cuando el $c$ ¿llega hasta el infinito?

Si a) es demasiado complejo, responder simplemente a b) también ayuda.

TEN EN CUENTA QUE SE TRATA DE UN PROBLEMA MATEMÁTICO PERO NO DE PROGRAMACIÓN.

Estos son los resultados de la simulación mediante programación dinámica, como se indica a continuación.

c=1 resultado=1.0

c=4 resultado=2.1875

c=16 resultado=4.478397890925407

c=36 resultado=6.7468086213781735

c=81 resultado=10.139752756675115

c=100 resultado=11,26969580185129

c=225 result=16.916286965946945

c=400 result=22.560532075769885

c=625 resultado=28.203837846306

c=961 result=34.975204560067226

Así que realmente parece que va a $\sqrt{N}$ como $c$ llega hasta el infinito. ¿Alguien tiene idea de por qué crece así?

Answer 1

Como ha comprobado: si $X_{m,n}$ es el valor esperado del número que queda en la casilla, entonces:

$$\begin{align} X_{m,n}&=X_{n,m}\\X_{m,0}&=X_{0,m}=m\\X_{m,n}&=\tfrac{1}2\left(X_{m-1,n}+X_{m,n-1}\right)\quad m,n>0 \end{align} $$

Creo que esto da para $m,n>0$

$$X_{m,n} = \frac1{2^{m+n}}\left(\sum\limits_{i=1}^m i2^i{m+n-1-i \choose n-1}+\sum\limits_{j=1}^n j2^j{m+n-1-j \choose m-1} \right)$$

Eso parece que debería simplificar, pero parece estar relacionado con OEIS A188553 que no tiene una fórmula explícita dada en general. Si la tabla OEIS es $T(a,b)$ entonces parece $X_{m,n} = \frac{1}{2^{m+n-1}}(T(m+n-1,m-1)+T(m+n-1,n-1))$

Esto conduce a una forma explícita cuando $m=n=c$ dando $X_{m,n} = \frac1{2^{2c-1}}\sum\limits_{i=1}^c i2^i{2c-1-i \choose c-1} = \frac{2c}{4^c}{2c \choose c}$ y para grandes $c$ se trata de $\sqrt{4 c /\pi}$

Answer 2

Mi respuesta cuando $m=n=c$ está de acuerdo con @Henry.

Sea $X$ denota el número de veces que muestrea bolas hasta que una caja está vacía. En $k \in \{c,...,2c-1\}$ tenemos $$\mathbb{P}(X=k)=2\cdot (0.5)^{k}{k-1 \choose c-1}$$ El valor esperado de $X$ es $$\mathbb{E}(X)=\sum_{k=c}^{2c-1}k\mathbb{P}(X=k)=2c\Bigg[1-4^{-c}{2c \choose c}\Bigg]$$ Aviso $2c-X$ bolas permanece en la caja vacía y $\mathbb{E}(2c-X)={2c \over 4^c}{2c \choose c}$ .