Hay $n$ bolas negras y $n$ bolas blancas en una bandeja. Puedo retirar las bolas de una en una sin reemplazo hasta que haya un número igual de blanco y negro bolas. ¿Cuál es el número esperado de bolas que tengo que retirar?
Parece que la respuesta debe ser $4^n\left/{2n \choose n}\right.$. Así, por $n = 3$ sería:
$$4^3\left/{6 \choose 3}\right. = \frac{64}{20} = \frac{16}{5}$$
He verificado las respuestas para$n = 2$$n = 3$, pero no estoy en condiciones de probar el resultado general.
Su conjetura es verdadera. El siguiente argumento no es elegante, pero funciona!
El número de arreglos de $k$ blanco y $k$ bolas negras donde la primera se produce una compensación en$2k$$2 C_{k-1}$, donde $C_{k-1}={1\over k}{2(k-1)\choose k-1}$ $k-1$th Catalán número.
El número de arreglos de $n$ blanco y $n$ bolas negras donde la primera se produce una compensación en $2k$ es por lo tanto $$ {2\over k}{2(k-1)\choose k-1} {2(n-k)\choose n-k}.\tag 1$$
Todos los ${2n\choose n}$ arreglos son igualmente probables, por lo que la probabilidad de que la ecualización de la primera se produce en el momento $2k$ es $$\mathbb{P}(T=2k)= {1\over{2n\choose n}} {2\over k}{2(k-1)\choose k-1} {2(n-k)\choose n-k}.\tag 2$$
El tiempo de espera para la ecualización es por lo tanto $$\mathbb{E}(T)={1\over{2n\elegir n}} \sum_{k=1}^n 2k\, {2\sobre k}\,{2(k-1)\elegir k-1} {2(n-k)\elegir n-k}.\etiqueta 3$$
La cancelación de la $k$'s en (3) y el uso de la conocida identidad $$\sum_{k=1}^n {2(k-1)\choose k-1} {2(n-k)\choose n-k}=4^{n-1}\tag4$$ da el resultado.
Supongamos que la primera bola es blanca y que se detenga en el número de sorteo $2k$. A continuación, el $2k$-th bola dibujado era negro, y el $2k-2$ bolas extraídas en las posiciones de $2$ a través de $2k-1$ formar un Dyck palabra de longitud $2k-2$. Por el contrario, cualquier secuencia de $2k-2$ blanco y negro de bolas en el que el número de bolas negras nunca supera el número de bolas blancas pueden ocupar los $2k-2$ posiciones. Por lo tanto, no se $C_{k-1}$ secuencias de sorteos comenzando con una bola blanca que terminar con empate $2k$. Si nos imaginamos continuar hasta que la caja está vacía, hay $\binom{2n-2k}{n-k}$ formas para completar el proyecto, para un total de $C_{k-1}\binom{2n-2k}{n-k}$ total sorteos que empezar con una bola blanca y el primer balance (en números iguales de blanco y negro de bolas) en dibujar $2k$. Hay un número igual de partida con una pelota negra, por lo que
$$2C_{k-1}\binom{2n-2k}{n-k}=\frac2k\binom{2k-2}{k-1}\binom{2n-2k}{n-k}$$
de la $\binom{2n}n$ total dibuja primero el equilibrio en dibujar $2k$. El número esperado de sorteos de la primera equilibrado de la muestra es, por tanto,
$$\binom{2n}n^{-1}\sum_{k=1}^n\frac2k\binom{2k-2}{k-1}\binom{2n-2k}{n-k}(2k)=4\binom{2n}n^{-1}\sum_{k=1}^n\binom{2k-2}{k-1}\binom{2n-2k}{n-k}\;,$$
y tu conjetura es equivalente a
$$4^{n-1}=\sum_{k=1}^n\binom{2k-2}{k-1}\binom{2n-2k}{n-k}=\sum_{k=0}^{n-1}\binom{2k}k\binom{2n-2k-2}{n-k-1}$$ or, after replacing $n-1$ by $$ n, a
$$4^n=\sum_{k=0}^n\binom{2k}k\binom{2n-2k}{n-k}\;.$$
Usted puede encontrar una prueba de esta identidad en esta pregunta , junto con un esbozo de una combinatoria de la prueba; esta respuesta da un total de combinatoria prueba.
Me gustaría empezar por definir $f(n,m), n \ge m$ como el número esperado de sorteos a partir de $n$ bolas blancas y $m$ bolas negras con $n-m$ bolas negras en la mano. Luego tenemos a $f(n,n)=1+f(n,n-1)$
$f(n,0)=n$
$f(n,n-1)=\frac n{2n-1}+\frac{n-1}{2n-1}(1+f(n,n-2))$
$f(n,m)=1+\frac m{n+m}f(n,m-1)+\frac n{n+m}f(n-1,m)$
donde los casos son revisados en este orden y buscar una solución. No hay garantías de que esto va a funcionar.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
