Un problema Tratar con poner las bolas en la papelera y el valor esperado - posible respuesta incorrecta

Question

Por favor, considere el problema siguiente. Es mi respuesta correcta. Si no es correcta, entonces ¿de dónde me salen mal?
Problema:
Siguen lanzando bolas en $n$ cajas hasta que uno de los cubos que tiene dos bolas. Para cada lanzamiento hay un $\frac{1}{n}$ de probabilidad de que la bola de tirar cae en uno de los recipientes. ¿Cuál es el número esperado de lanzamientos?
Respuesta:
Deje $p_i$ la probabilidad de que después de $i$ lanza tenemos al menos un bin con dos bolas. \begin{eqnarray*} p_1 &=& 0 \\ p_2 &=& 1 - ( 1 - \frac{1}{n} ) = \frac{1}{n} \\ p_3 &=& 1 - (1 - \frac{1}{n})(1 - \frac{1}{n-1}) \\ p_3 &=& 1 - (\frac{n-1}{n})(\frac{n-1-1}{n-1}) \\ p_3 &=& 1 - (\frac{n-2}{n}) = \frac{2}{n} \\ p_4 &=& 1 - (1 - \frac{1}{n})(1 - \frac{1}{n-1})(1 - \frac{1}{n-2}) \\ p_4 &=& 1 - ( \frac{n-1}{n} )( \frac{n-2}{n-1} )( \frac{n - 2 -1}{n - 2} ) \\ p_4 &=& 1 - \frac{n-3}{n} = \frac{3}{n} \\ \end{eqnarray*}
Ahora para $1 <= i <= n$ tenemos: $p_i = \frac{i-1}{n}$. \begin{eqnarray*} E &=& 2p_2 + 3p_3 + 4p_4 + ... (n+1)p_{n+1} \\ E &=& \sum_{i = 1}^{n} \frac{i(i+1)}{n} = \frac{1}{2n} \sum_{i=1}^{n} i^2 + i \\ E &=& \frac{1}{2n}(\frac{n(n+1)(2n+1)}{6} + \frac{n(n+1)}{2} ) \\ E &=& \frac{n+1}{4n} ( \frac{2n+1}{3} + 1 ) \\ \end{eqnarray*}

Aquí está una actualización a mi respuesta:

Deje $p_i$ la probabilidad de que después de $i$ lanza tenemos al menos un bin con dos bolas. \newline \begin{eqnarray*} p_1 &=& 0 \\ p_2 &=& 1 - ( 1 - \frac{1}{n} ) = \frac{1}{n} \\ p_3 &=& 1 - (\frac{n-1}{n})( \frac{n-2}{n}) \\ p_3 &=& 1 - \frac{(n-1)(n-2)}{n^2} = \frac{n^2 - (n^2 - 3n + 2)}{n^2} \\ p_3 &=& \frac{3n-2}{n^2} \\ p_4 &=& 1 - (\frac{n-1}{n})(\frac{n-2}{n})(\frac{n-3}{n}) \\ p_4 &=& 1 - \frac{(n^2-3n+2)(n-3)}{n^3}\\ p_4 &=& 1 - \frac{n^3-3n^2+2n - 3n^2 +9n - 6}{n^3}\\ p_4 &=& \frac{3n^2-2n + 3n^2 - 9n + 6}{n^3}\\ p_4 &=& \frac{3n^2 + 3n^2 - 11n + 6}{n^3}\\ \end{eqnarray*}

\begin{eqnarray*} E &=& 2p_2 + 3p_3 + 4p_4 + ... (n+1)p_{n+1} \\ \end{eqnarray*} Ahora, estoy en el camino correcto? Lo que es, es lo que tengo hasta ahora, ¿correcto?
Gracias,
Bob

Answer 1

Utilizar el principio del palomar.

Si el número de lanzamientos ($n$) $\geq b+1$ , entonces al menos uno de bin contendrá $2$ bolas. Si el número de lanzamientos es $0 < n < b$, la probabilidad de que cada pelota va en una bandeja distinta es $$\frac{1 \times 2 \times ...(b-n+1)}{b^n} = \frac{b!}{n!\times b^n}$$

Así que la probabilidad de que una caja contiene más de un balón $n$ tiros es $$1-\frac{b!}{n!\times b^n}$$

Por lo que el número esperado de lanzamientos se pueden encontrar con $$E(b) = 1+ \sum_{k=1}^{b} \frac{b!}{\left(b-k\right)!b^k}$$

Visualizado, esto se parece a:

Answer 2

Se da el número$n$ de contenedores y se fija. Indica con$E(j)$$(0\leq j\leq n)$ el número esperado de lanzamientos adicionales cuando hay$j$ contenedores vacíos y el juego aún no ha terminado. Luego tenemos la siguiente recursión:$$E(j)=1+{j\over n}E(j-1)\quad(n\geq j\geq 1),\qquad E(0)=1\ .$ $ Esto proporciona $$ \ eqalign {E (n) & = 1+ {n \ over n} E (n-1) \ cr & = 1 + {n \ over n} \ left (1+ {n-1 \ over n} E (n-2) \ right) \ cr & = 1 + {n \ over n} \ left (1+ {n-1 \ over n} \ izquierda (1+ {n-2 \ sobre n} E (n-3) \ derecha) \ derecha) \ cr & = \ ldots \ cr} $$ y lleva a$$E(n)=1+\sum_{k=1}^n{n(n-1)\cdots\bigl(n-(k-1)\bigr)\over n^k}\ ,$ $ como en la respuesta de Joseph Eck.

Answer 3

Deje $T$ el número de lanzamientos que toma para conseguir a $2$ bolas en $1$ de las papeleras. Si usted todavía está lanzando bolas después de $i$ tira es porque ninguno de los contenedores tiene más de $1$ bola, de modo que no es $1$ pelota en $i$ papeleras $$ \Pr(T=i+1|T>i) = \frac{i}{n} .$$

Next, using Bayes' rule

$$ \Pr(T=i+1|T>i) = \frac{\Pr(T=i+1)}{\Pr(T>i)} ,$$

which implies that

$$ \Pr(T=i+1) = \Pr(T>i)\Pr(T=i+1|T>i) .$$

Since

$$ \Pr(T>i) = 1 - \sum_{k=1}^i\Pr(T=k) ,$$

and letting $p_i =\Pr(T=i+1)$, it follows that

$$p_2 = \frac{1}{n} \quad\text{and}\quad p_{i+1}=\frac{(n+1-i)i}{n(i-1)}p_{i} \quad\text{for}\; i\ge 3. $$

A continuación, $$\mathbb E[T] = \sum_{i=2}^n p_i i,$$ que no he sido capaz de resolver analíticamente pero he escrito el siguiente código de Matlab para calcular:

N = 100;
E = zeros(N,1);
for n = 2:N    
    p = zeros(n+1,1);    
    p(2) = 1/n;    
    for i = 2:n
        p(i+1) = p(i)*(n+1-i)*i/(n*(i-1));
    end    
    E(n) = sum(p'*(1:n+1)');
end
plot(2:N,E(2:N,1))

El código que se genera de la siguiente parcela con $n$ $x$- eje y $\mathbb E[T]$ $y$- eje:

Answer 4

Deje $p_i$ denotar el número de formas en que podemos obtener $i$ lanzamientos.
Obviamente $2\le i\le (n+1)$

Para encontrar $p_i$ -

1.Primero, encuentre el número de formas en que podemos poner $(i-1)$ bolas en los cubos de basura de tal manera que no hay dos van en la misma bandeja

Número de formas = $^np_{i-1}$

2.Puesto que la siguiente bola en una de las bandejas que ya tiene una bola de

Número de formas = $i-1$

$\therefore p_i=(i-1)^np_{i-1}$

---

$\therefore$ El número total de maneras=$$\sum^{n+1}_{i=2}(i-1)^np_{i-1}$$

Poner los valores en cada caso, podemos obtener el valor esperado para el número de lanzamientos como $$\sum^{n+1}_{i=2}\frac{i(i-1)^np_{i-1}}{\sum^{n+1}_{i=2}(i-1)^np_{i-1}}=\frac{\sum^{n+1}_{i=2}i(i-1)^np_{i-1}}{\sum^{n+1}_{i=2}(i-1)^np_{i-1}}$$

Answer 5

Varias respuestas ya han sido siempre, pero déjeme mostrarle un enfoque diferente para conseguirlo.

En el primer sorteo ha $p_1=0$ y seguro con 1 bola de reciclaje.

En la segunda, ya sea que usted golpea la bola (prob. $p_2=1/n=(1-p_1)1/n$) o puedes acabar con los 2 de una bola de contenedores (prob. $q_2=1-p_2=(n-1)/n$).

En este punto, prestar atención al hecho de que $$ \bbox[lightyellow] { \pi _{\,k} = {{k - 1} \over n}\quad \quad \mu _{\,k} = 1 - \pi _{\,k} = {{n - \left( {k - 1} \right)} \over n} }$$

son de transición de probabilidades, es decir, probabilidades condicionales, y precisamente:
- $\pi _{\,k}$ es la prob. de tener un "hit" en el $k$-ésimo lanzamiento, teniendo en cuenta que usted no tiene ningún golpe antes;
- $\mu _{\,k}$ es la prob. de no tener un "hit" en el $k$-ésimo lanzamiento, teniendo en cuenta que usted no tiene ningún golpe antes.
mientras que $p_k$ $q_k$ son en general las probabilidades de que, desde todas las bandejas vacías,
- tenemos un éxito en (exactamente) el $k$-th toss ($p_k$);
- tenemos (exactamente) $k$ uno-bola de contenedores en el $k$-ésimo lanzamiento, es decir, sin hit hasta que se mezcle ($q_k$);

Por lo tanto se debe tener claro que
- $\pi_k \ne p_k$$\mu_k \ne q_k$ a pesar de que en los dos primeros lanzamientos de ellos coinciden;
- $q_k \ne 1-p_k$, debido a $1-p_k$ es la probabilidad de tener un éxito en un lanzamiento diferente de $k$, mientras que $1-q_k$ es la probabilidad de tener un éxito después de la $k$-ésimo de la sacudida;

Así $$ \left\{ \matriz{ q_{\,3} = \mu _{\,1} \mu _{\,2} \mu _{\,3} = \left( {1 - \pi _{\,1} } \right)\left( {1 - \pi _{\,2} } \right)\left( {1 - \pi _{\,3} } \right) = q_{\,2} \left( {1 - \pi _{\,3} } \right) = \hfill \cr = {{n\left( {n - 1} \right)\left( {n - 2} \right)} \over {n^{\,3} }} = {{n^{\,\subrayado {\,3\,} } } \más de {n^{\,3} }} \hfill \cr p_{\,3} = \left( {1 - \pi _{\,2} } \right)\pi _{\,3} = \left( {1 - \pi _{\,1} } \right)\left( {1 - \pi _{\,2} } \right)\pi _{\,3} = q_{\,2} \pi _{\,3} = \hfill \cr = q_{\,2} - q_{\,3} = {{n - 1} \over n}{2 \sobre n} \hfill \cr p_{\,3} \quad \ne \quad 1 - q_{\,3} \hfill \cr} \right. $$ y, en general, $$ \bbox[lightyellow] { \left\{ \matriz{ q_{\,k} = {{n^{\,\underline {\k\,} } } \over {n^{\,k} }}\quad \left| {\;0 \le k} \right. \hfill \cr p_{\,k} = q_{\,k - 1} - q_{\,k} = q_{\,k - 1} {{k - 1} \over n} = {{\left( {k - 1} \right)\,n^{\,\underline {\,k - 1\,} } } \over {n^{\,k} }}\quad \left| {\;1 \le k} \right. \hfill \cr} \right. }$$ donde $x^{\,\underline {\,k\,} }$ representa la Caída Factorial

Desde que obtenemos $$ \left\{ \matriz{ q_{\,0} = q_{\,1} = 1 \hfill \cr q_{\,m} = 0\quad \left| {\;n < m} \right. \hfill \cr \sum\limits_{1\, \le \;k} {p_{\,k} } = \sum\limits_{1\, \le \;k\; \le \,n + 1} {p_{\,k} } = \sum\limits_{1\, \le \;k\; \le \,n + 1} {\left( {q_{\,k - 1} - q_{\,k} } \right)} = q_{\,0} - q_{\,n + 1} = 1 \hfill \cr} \right. $$ pues es claro que en el toss $n+1$ tenemos un éxito seguro, si no teníamos antes ($\pi_{n+1}=1$).

Viene para el cálculo del valor esperado, hemos $$ \bbox[lightyellow] { \eqalign{ & E(k;\,n) = \sum\limits_{1\, \le \;k\; \le \,n + 1} {k\,p(k,n)} = \sum\limits_{1\, \le \;k\; \le \,n + 1} {\,{{k\left( {k - 1} \right)\,n^{\,\underline {\,k - 1\,} } } \over {n^{\,k} }}} = \cr & = \sum\limits_{1\, \le \;k\; \le \,n + 1} {\left( {k\,p(k - 1,n) - k\,q(k,n)} \right)} = \cr & = \sum\limits_{1\, \le \;k\; \le \,n + 1} {\left( {\left( {k - 1} \right)\,p(k - 1,n) - k\,q(k,n) + q(k - 1,n)} \right)} = \cr y = - \left( {n + 1} \right)p(n + 1,n) + \sum\limits_{1\, \le \;k\; \le \,n + 1} {q(k - 1,n)} = \sum\limits_{0\, \le \;k\; \le \,n} {q(k,n)} \cr} }$$ cuando el cambio de notación es obvio.
Coincide con la respuesta ya está dada por C. Blatter.

Ahora, $q(k,n)$ puede ser escrito como $$ q(k,n) = {{\,n^{\,\underline {\k\,} } } \over {n^{\,k} }} = k!\a la izquierda( \matriz{ n \cr k \cr} \right)\left( {{1 \over n}} \right)^{\,k} = \prod\limits_{0\, \le \;j\; \le \,k - 1} {\left( {1 - {j \sobre n}} \right)} = {{\,\Gamma (n + 1)} \over {n^{\,k} \,\Gamma (n - k + 1)}} $$ pero, por desgracia, no pude encontrar (y la duda no es) cerrado fórmula para la suma.

Una aproximación asintótica para un gran $n$ no obstante, podría ser construido, a través de diversas enfoques, dependiendo de las metas que usted pueda tener.