Reemplazo iterativo de chocolates$3$ en una caja de$10$

Question

En la nevera hay una caja que contiene 10 caro, de alta calidad chocolates Belgas, que mi mamá sigue para los visitantes. Cada día, cuando la mamá se va de la casa para el trabajo, en secreto, pick 3 chocolates al azar, me alimento de ellos y reemplazarlos con ordinario y barato, que tienen exactamente la misma envoltura. Al día siguiente hago lo mismo, obviamente arriesgar a comer también algunos de los baratos. Cuántos días en promedio se tarda para la sustitución completa de la cara bombones de chocolate barato?

Me gustaría decir $10/3$ , pero esto es muy simplista. También, el número total de formas de seleccionar 3 chocolates de 10 es $\binom {10} 3=\frac {10!}{3!7!} = 120$ lo que significa que después de 120 días se han sustituido todos los chocolates, pero no creo que es correcto.

Alguna ayuda?

Answer 1

Croquis (no una solución completa, pero un mapa de ruta hacia una):

Vamos a proceder de forma recursiva. Deje $E_i$ denotar el número esperado de días que se tarda dado que tiene exactamente $i$ buenos izquierda. La respuesta que queremos es $E_{10}$.

Vamos a calcular $E_1$, por ejemplo. Cada día el buen uno se seleccionan con probabilidad de $\frac {3}{10}$. Por lo tanto $$E_1=\frac {10}3$$

Ahora vamos a considerar $E_2$. El primer sorteo se $0,1$ o $2$ de los buenos. Podemos deducir rápidamente que $$\binom {10}3 \times E_2=\binom 83\times (E_2+1)+\binom 82\times \binom 21 \times (E_1+1)+ \binom 81\times \binom 22\times (1)$$

Esto se resuelve a $$E_2=\frac {115}{24}\approx 4.7917$$

Del mismo modo, para $i>2$ $$\binom {10}3\times E_i=\binom {10-i}3\times (E_i+1)+\binom {10-i}2\times \binom i1\times (E_{i-1}+1)$$ $$+\binom {10-i}1\times \binom i2\times (E_{i-2}+1)+\binom {10-i}0\times \binom {i}3\times (E_{i-3}+1)$$

Y podemos resolver el sistema paso por paso. El cálculo requiere un poco de atención, ya que en la recursividad, debemos definir $\binom nm=0$ cuando $n<m$.

Al final tengo acerca de $\boxed {9.046}$ pero como los comentarios se indican claramente, un gran número de errores por descuido se realizaron en la ruta, así que te aconsejo comprobar cuidadosamente.

Answer 2

Auto-contenido, forma cerrada, la solución al problema.

Supongamos que hay $n$ caro chocolates y cada día que secretamente pick $m$ chocolates para el reemplazo. Deje $T$ ser una variable aleatoria que indica el número de días que se necesita para reemplazar todas las caras de los chocolates. Observe que, dado cualquier conjunto de $S$ de los chocolates, la probabilidad de que usted ha conseguido evitar el $S$ en cada uno de los $i$ días es $$ \left[\binom{n-|S|}{m}/\binom{n}{m}\right]^i. $$ De hecho, cada uno de los elegidos conjuntos de chocolates es independiente de los demás y tiene la probabilidad de $\binom{n-|S|}{m}/\binom{n}{m}$ de evitar que el conjunto dado $S$, ya que hay $\binom{n-|S|}{m}$ $m$-elemento subconjuntos evitando $S$.

Por lo tanto, la probabilidad de que usted ha logrado evitar, al menos, uno de chocolate durante el primer $i$ días es $$ \mathbb P(\text{evite el chocolate número 1})+\cdots +\mathbb P(\text{evite el chocolate número n}) $$ $$ -\mathbb P(\text{evitar chocolates número 1 y 2})-\mathbb P(\text{evitar chocolates número 1 y 3})-\cdots -\mathbb P(\text{evitar chocolates número $n-1$ e $n$}) $$ $$ \text{$+$ similares suma de todos los $3$ elemento subconjuntos, etc}. $$ El cálculo anterior es mediante el principio de inclusión-exclusión: empezamos por la superación de la probabilidad, a continuación, reste fuera de la doble contabilización, a continuación, vuelva a agregar en la triple cuenta, y así sucesivamente hasta que nos han clavado la probabilidad exacto que estamos buscando.

Observe que cada una de las probabilidades en la pantalla anterior sólo depende del número de elementos en el conjunto. Así, podemos agrupar un número determinado de elementos, tomando nota de que vamos a tener $\binom{n}{s}$ establece que contribuyen a que el plazo para la $s$-elemento de subconjuntos. Por lo tanto, $$ \mathbb P(T>i)=\sum_{s=1}^n\binom{n}{s}\cdot (-1)^{s+1}\left[\binom{n-s}{m}/\binom{n}{m}\right]^i. $$

El uso de la cola de la suma para la expectativa de la fórmula que establece que $$ \mathbb ET=\sum_{i=0}^{\infty}\mathbb P(T>i), $$ obtenemos que $$ \mathbb ET=\sum_{i=0}^{\infty}\sum_{s=1}^n\binom{n}{s}(-1)^{s+1}\left[\binom{n-s}{m}/\binom{n}{m}\right]^i. $$ Todo lo que queda es para simplificar esta expresión. La manipulación de infinito alternando las sumas pueden ser sutiles, pero en este se puede reorganizar el orden de resumen ya que la serie converge absolutamente. Por lo tanto $$ \mathbb ET=\sum_{s=1}^n\binom{n}{s}(-1)^{s+1}\sum_{i=0}^{\infty}\left[\binom{n-s}{m}/\binom{n}{m}\right]^i=\sum_{s=1}^n\binom{n}{s}(-1)^{s+1}\frac{1}{1-\binom{n-s}{m}/\binom{n}{m}}, $$ donde hemos aplicado la serie geométrica de la fórmula $\sum_{i=0}^{\infty}x^i=\frac{1}{1-x}$ en la segunda igualdad.

Finalmente, podemos multiplicar a través de la fracción para obtener que $$ \boxed{\mathbb ET=\binom{n}{m}\sum_{s=1}^n\frac{(-1)^{s+1}\binom{n}{s}}{\binom{n}{m}-\binom{n-s}{m}}}. $$

Substituting $n=10$ and $m=3$, we can evaluate the formula using this python snippet:

from math import factorial
from fractions import Fraction

def binom(n,k): # binomial coefficient n choose k
  return 0 if n < k else factorial(n)/factorial(k)/factorial(n-k)

def e(n,m): # expected number of days to replace all n chocolates if replaced m at a time
  return binom(n,m)*sum(Fraction(pow(-1,s+1)*binom(n,s),binom(n,m)-binom(n-s,m)) for s in range(1,n+1))

e(10,3) # Fraction(8241679, 911064), approximately 9.05 days

This is the general analytical solution to the problem. To see all the missteps and sources that inspired this solution, keep reading below for the previous iterations of this answer that led to here.

---

See the bottom of this post for a previous incarnation of this answer, which cited an incorrect formula and was therefore incorrect.

This problem has appeared many times in the literature. A closed-form solution is known and is valid with $3$ and $10$ replaced with arbitrary integers $m$ and $n$ satisfying $0\leq m\leq n$.

Theorem 2 in Stadje [1990] (specifically equation (2.15) therein) with $p=1$ and $l=s=$ n los estados que la expectativa deseada es igual a $$ \binom{n}{m}\sum_{j=0}^{n-1}\frac{(-1)^{n-j+1}\binom{n}{j}}{\binom{n}{m}-\binom{j}{m}}. $$ En este caso, $n=10$ e $m=3$ y por lo tanto el número esperado de días iguales $$ \frac{8241679}{911064}\approx 9.05. $$

A very nice and self-contained derivation of this formula appears at mathoverflow, although beware that the answer containing this derivation has a minor mistake, which I have corrected both in this post and over at the linked mathoverflow post as well.

---

Original answer, which cited an incorrect formula from mathoverflow. I have corrected that formula and posted an explanation of the mistake at mathoverflow.

This problem has been solved (with $3$ and $10$ replaced $b$ and $$ n, respectivamente) en matemáticas de desbordamiento (y en la literatura clásica). La fórmula general para el valor esperado del número de lotes que se requiere es $$ \sum_{s=1}^{n-b}\frac{(-1)^{s+1}\binom{n}{s}}{1-\binom{n-s}{b}/\binom{n}{b}}. $$ Conectar $n=10$ e $b=3$rendimientos $$ \frac{\binom{10}{1}}{1-\binom{9}{3}/\binom{10}{3}}-\frac{\binom{10}{2}}{1-\binom{8}{3}/\binom{10}{3}}+\frac{\binom{10}{3}}{1-\binom{7}{3}/\binom{10}{3}}-\cdots +\frac{\binom{10}{7}}{1-\binom{3}{3}/\binom{10}{3}}, $$ en el que se evalúa a $$ \frac{41039983}{911064}\aprox 45. $$ En comparación con la otra respuesta veo que estamos de acuerdo en que el denominador, pero no en el numerador...

[MODIFICAR:] De hecho, la respuesta incorrecta es exactamente $36$ mayor que la respuesta correcta. La respuesta incorrecta es igual a $$ \binom{10}{3}\sum_{j=3}^{9}\frac{(-1)^{11-j}\binom{10}{j}}{\binom{10}{3}-\binom{j}{3}} $$ mientras que la respuesta correcta es igual a $$ \binom{10}{3}\sum_{j=0}^{9}\frac{(-1)^{11-j}\binom{10}{j}}{\binom{10}{3}-\binom{j}{3}} $$ y la diferencia es $$ \binom{10}{3}\sum_{j=0}^{2}\frac{(-1)^{11-j}\binom{10}{j}}{\binom{10}{3}-\binom{j}{3}}=-\binom{10}{0}+\binom{10}{1}-\binom{10}{2}=-1+10-45=-36. $$

Answer 3

Luego de @lulu escribí el siguiente programa para calcular la cantidad de días esperados necesarios para tomar $n$ 'chocolates caros', dado que solo puedes tomar $k$ en un día:

 from fractions import Fraction

#n - number of 'expensive chocolates' at start
#g - number of 'expensive chocolates' in current state of recursion
#k - number of chocolates taken each turn
def expected(n,g,k):
    if g<=0:
        return Fraction()
    if k>=n:
        return Fraction(1,1)
    ex=ncr(n-g,k)
    for i in range(1,k+1):
        ex+=ncr(n-g,k-i)*ncr(g,i)*(expected(n,g-i,k)+Fraction(1,1))
    return ex/(ncr(n,k)-ncr(n-g,k))

def ncr(n,r):
    if r>n:
        return Fraction()
    c=Fraction(1,1)
    while r>0:
        c*=Fraction(n,r)
        n-=1
        r-=1
    return c
 

Por ejemplo, ejecutar expected(10,10,3) da Fraction(8241679, 911064) que es equivalente a $$\frac{8241679}{911064}\approx9.046212999\text{ days}$ $ para el caso en cuestión.

Answer 4

Esto es sólo un numérica suplemento a @lulu bonita respuesta. Desde quería ver mejor el desarrollo de la $E_k, 1\leq k\leq 10$, hice el cálculo un poco detallada. Al final de una recurrencia de la relación se da.

Se denota con $E_k$ el número esperado de días que lleva, dado que tenemos exactamente $k$ buenos izquierda y obtener la siguiente @lulu enfoque:

\begin{align*} \binom{10}{3}E_1&=\binom{9}{3}\left(E_1+1\right)+\binom{9}{2}\binom{1}{1}\\ \binom{10}{3}E_2&=\binom{8}{3}\left(E_2+1\right)+\binom{8}{2}\binom{2}{1}\left(E_1+1\right) +\binom{8}{1}\binom{2}{2}\\ \binom{10}{3}E_3&=\binom{7}{3}\left(E_3+1\right)+\binom{7}{2}\binom{3}{1}\left(E_2+1\right) +\binom{7}{1}\binom{3}{2}\left(E_1+1\right)+\binom{7}{0}\binom{3}{3}\\ \binom{10}{3}E_4&=\binom{6}{3}\left(E_4+1\right)+\binom{6}{2}\binom{4}{1}\left(E_3+1\right) +\binom{6}{1}\binom{4}{2}\left(E_2+1\right)+\binom{6}{0}\binom{4}{3}\left(E_1+1\right)\tag{1}\\ \binom{10}{3}E_5&=\binom{5}{3}\left(E_5+1\right)+\binom{5}{2}\binom{5}{1}\left(E_4+1\right) +\binom{5}{1}\binom{5}{2}\left(E_3+1\right)+\binom{5}{0}\binom{5}{3}\left(E_2+1\right)\\ \binom{10}{3}E_6&=\binom{4}{3}\left(E_6+1\right)+\binom{4}{2}\binom{6}{1}\left(E_5+1\right) +\binom{4}{1}\binom{6}{2}\left(E_4+1\right)+\binom{4}{0}\binom{6}{3}\left(E_3+1\right)\\ \binom{10}{3}E_7&=\binom{3}{3}\left(E_7+1\right)+\binom{3}{2}\binom{7}{1}\left(E_6+1\right) +\binom{3}{1}\binom{7}{2}\left(E_5+1\right)+\binom{3}{0}\binom{7}{3}\left(E_4+1\right)\\ E_{10}&=E_7+1\\ \end{align*}

Los términos en cada una de las líneas más arriba, que no se multiplican por $E_k$ puede ser simplificado con el uso de Vandermonde de la identidad. Tomando por ejemplo la línea (1) tenemos \begin{align*} \binom{10}{3}E_4&=\binom{6}{3}\left(E_4+1\right)+\binom{6}{2}\binom{4}{1}\left(E_3+1\right) +\binom{6}{1}\binom{4}{2}\left(E_2+1\right)+\binom{6}{0}\binom{4}{3}\left(E_1+1\right)\\ &=\sum_{j=0}^3\binom{6}{3-j}\binom{4}{j}E_{4-j}+\color{blue}{\sum_{j=0}^3\binom{6}{3-j}\binom{4}{j}}\\ &=\sum_{j=0}^3\binom{6}{3-j}\binom{4}{j}E_{4-j}+\color{blue}{\binom{10}{3}}\\ \binom{10}{3}\left(E_4-1\right)&=\sum_{j=0}^3\binom{6}{3-j}\binom{4}{j}E_{4-j}\tag{2} \end{align*}

Establecimiento $E_0=1$ se obtiene la relación de recurrencia de acuerdo a (2) \begin{align*} \color{blue}{\binom{10}{3}\left(E_k-1\right)}&\color{blue}{=\sum_{j=0}^{\min\{3,k\}}\binom{10-k}{3-j}\binom{k}{j}E_{k-j}\qquad\qquad 1\leq k\leq 7}\\ \color{blue}{E_0}&\color{blue}{=1}\\ \color{blue}{E_{10}}&\color{blue}{=E_7+1} \end{align*}

Obtenemos la solución de la relación de recurrencia: \begin{align*} E_1&=\frac{10}{3}\approx 3.333\\ E_2&=\frac{115}{24}\approx 4.792\\ E_3&=\frac{787}{136}\approx5.787\\ E_4&=\frac{6\,661}{1\,020}\approx 6.530\\ E_5&=\frac{15\,999}{2\,244}\approx 7.125\\ E_6&=\frac{330\,641}{43\,384}\approx 7.621\\ E_7&=\frac{7\,330\,615}{911\,064}\approx 8.046\\ \color{blue}{E_{10}}&\color{blue}{=\frac{8\,241\,679}{911\,064}\approx 9.046} \end{align*}

Answer 5

SUGERENCIA para un enfoque de Markov

Si en un cierto punto, usted ha $A$ ordinarias y $B$ chocolates belgas, al seleccionar a los tres chocolates puede seleccionar :
- $[a,a,a]$ (tres ordinario ch.) con prob. $$ {Un \over {A + B}}{{A - 1} \over {A - 1 + B}}{{A - 2} \over {A - 2 + B}} = {{A^{\,\subrayado {\,3\,} } } \más de {\left( {A + B} \right)^{\,\subrayado {\,3\,} } }} $$
- $[a,a,b]$ con prob. $$ {Un \over {A + B}}{{A - 1} \over {A - 1 + B}}{B \over {A - 1 + B}} = {{A^{\,\underline {\,2\,} } B^{\,\subrayado {\,1\,} } } \más de {\left( {A + B} \right)^{\,\underline {\,2\,} } \left( {A - 1 + B} \right)}} $$
- $[a,b,a]$ con prob. $$ {Un \over {A + B}}{B \over {A - 1 + B}}{{A - 1} \over {A - 1 + B - 1}} = {{A^{\,\underline {\,2\,} } B^{\,\subrayado {\,1\,} } } \más de {\left( {A + B} \right)^{\,\subrayado {\,3\,} } }} $$
y así sucesivamente, obteniendo el desarrollo de $$ \left( {A + B} \right)^{\,\subrayado {\,3\,} } = \sum\limits_j {\left( \matriz{ 3 \hfill \cr j \hfill \cr} \right)A^{\,\underline {\,3 - j\,} } B^{\,\underline {\,j\,} } } $$ La caída factorial en el numerador se asegurará de que no vamos a recoger con más piezas que la que está disponible, y vamos a asegúrese de que la fracción sea nulo, siempre que el numerador es nulo.

Al final, vamos a restaurar tres ordinario chocolates, es decir, traer a $A$ a $A+3$ y restaurar el total de la original $N=A+B$

Por lo tanto, es posible escribir las probabilidades de que después de un ciclo de cosecha y restaurar el número de ordinario ch. pasa de $A$ a $A+0,\, A+1, \, A+2, \, A+3$ (con $B$ siendo el complemento de a $N$).
Eso significa que podemos configurar un 4-diagonal de la Matriz de Markov para $A$, o bien por $B$, y el estudio de las características de este.

La realización de los cálculos como por encima de la $A$-ésima fila de la matriz de transición será $$ \begin{array}{*{20}c} {} & | & \cdots & A & {A + 1} & {A + 2} & {A + 3} \\ \hline A & | & \ddots & {\frac{{A^{\,\underline {\,3\,} } }}{{N^{\,\underline {\,3\,} } }}} & {3\frac{{A^{\,\underline {\,2\,} } \left( {N - A} \right)^{\,\underline {\,1\,} } }}{{N^{\,\underline {\,3\,} } }}} & {3\frac{{A^{\,\underline {\,1\,} } \left( {N - A} \right)^{\,\underline {\,2\,} } }}{{N^{\,\underline {\,3\,} } }}} & {\frac{{\left( {N - A} \right)^{\,\underline {\,3\,} } }}{{N^{\,\underline {\,3\,} } }}} \\ \end{array} $$

Ejemplo

Para contener las dimensiones de la matriz, vamos a considerar el caso de $N=4$, entonces la matriz de transición es $$ T\left( 4 \right) = \frac{1}{4} \, \left( {\matriz{ 0 & 0 & 0 & 1 & 0 \cr 0 & 0 & 0 & 3 & 1 \cr 0 & 0 & 0 & 2 & 2 \cr 0 & 0 & 0 & 1 & 3 \cr 0 & 0 & 0 & 0 & 1 \cr } } \right) $$