La expectativa de que la Última que quedaba en el Recipiente

Question

Usted decide jugar un día de fiesta juego de beber. Se empieza con 100 contenedores de ponche de huevo en una fila. El 1 de envase contiene 1 litro de ponche de huevo, el 2 contiene 2 litros de agua, todo el camino hasta el número 100, que contiene 100 litros. Selecciona un contenedor uniformemente al azar y tomar un litro sorbo de ella. Si el contenedor está vacío después de tomar este sip, que se quite de la fila y seleccione sólo del resto de las botellas. Continúe este proceso hasta que sólo hay 1 botella restantes. ¿Cuál es el número esperado de litros de ponche de huevo en esta última botella? ¿Qué es esto como esto como una función de n, el número de partida de botellas?

Se me ocurrió este problema mismo, recientemente, y no estoy realmente seguro de cómo acercarse a él. No puedo encontrar la esperanza condicional de una botella, dado que es la última que queda usando la linealidad de las expectativas, pero no me queda claro cómo utilizar esto para obtener la expectativa general.

Answer 1

Encontrar la respuesta exacta que puede no ser factible para 100 contenedores, creo. Me las arreglé para calcular hasta 5 contenedores de uso de recurrencia y una computadora. El siguiente código de python genera la recurrencia de 5 contenedores con las condiciones de contorno:

def g(n):
    bac = 'f'+str(n)+'('+','.join(['x'+str(i) for i in xrange(1,n+1)])+')'
    if n == 2:
        print 'f2(0,x2)==x2'
        print 'f2(x1,0)==x1'
        print 'f2(x1,x2)==(f2(x1-1,x2)+f2(x1,x2-1))/2'
        return 
    a = []
    for i in xrange(1,n+1):
        print bac.replace('x'+str(i), '0')+ '=='+bac.replace('x'+str(i), '').replace(',,', ',').replace('(,', '(').replace(',)',')').replace('f'+str(n),'f'+str(n-1))
    a = []
    for i in xrange(1,n+1):
        a.append(bac.replace('x'+str(i), 'x'+str(i)+'-1'))
    print bac+'==('+'+'.join(a)+')/'+str(n)
    return g(n-1)

g(5)

que da la recurrencia

f5(0,x2,x3,x4,x5)==f4(x2,x3,x4,x5)
f5(x1,0,x3,x4,x5)==f4(x1,x3,x4,x5)
f5(x1,x2,0,x4,x5)==f4(x1,x2,x4,x5)
f5(x1,x2,x3,0,x5)==f4(x1,x2,x3,x5)
f5(x1,x2,x3,x4,0)==f4(x1,x2,x3,x4)
f5(x1,x2,x3,x4,x5)==(f5(x1-1,x2,x3,x4,x5)+f5(x1,x2-1,x3,x4,x5)+f5(x1,x2,x3-1,x4,x5)+f5(x1,x2,x3,x4-1,x5)+f5(x1,x2,x3,x4,x5-1))/5
f4(0,x2,x3,x4)==f3(x2,x3,x4)
f4(x1,0,x3,x4)==f3(x1,x3,x4)
f4(x1,x2,0,x4)==f3(x1,x2,x4)
f4(x1,x2,x3,0)==f3(x1,x2,x3)
f4(x1,x2,x3,x4)==(f4(x1-1,x2,x3,x4)+f4(x1,x2-1,x3,x4)+f4(x1,x2,x3-1,x4)+f4(x1,x2,x3,x4-1))/4
f3(0,x2,x3)==f2(x2,x3)
f3(x1,0,x3)==f2(x1,x3)
f3(x1,x2,0)==f2(x1,x2)
f3(x1,x2,x3)==(f3(x1-1,x2,x3)+f3(x1,x2-1,x3)+f3(x1,x2,x3-1))/3
f2(0,x2)==x2
f2(x1,0)==x1
f2(x1,x2)==(f2(x1-1,x2)+f2(x1,x2-1))/2

que puede ser de entrada a friCAS y podemos calcular los valores como f5(1,2,3,4,5).

Aquí están las respuestas para el número de contenedores que se 2,3,4,5:

\begin{align*} \frac{3}{2}, \frac{125}{72}, \frac{157885}{82944}, \frac{685466694095183}{335923200000000} \end{align*}

Y para 100 contenedores, una simulación monte-carlo da una respuesta cercana a $5.6$

Answer 2

EDITAR Esta respuesta sólo es válida en el supuesto de que la probabilidad de tomar un sorbo de una botella es proporcional al número de sorbos restantes.

Deje $\alpha$ el número de maneras en que podemos organizar todos los sip (incluso contando el uno en el extremo que no se toman)

$$\alpha = \frac{(\sum\limits_{i=1}^{100} i)!}{\prod\limits_{i=1}^{100} (i!)} $$

(hay $\sum\limits_{i=1}^{100} i$ sorbos, y para la botella $i$, $i!$ sip son "idénticos")

Deje $N(m)$ el número de maneras de organizar todos los sip en una forma que exactamente $m$ sorbos de una botella de permanecer en el final es :

$$N(m) = \sum\limits_{l=m}^{100} \frac{(C_l^m) m! (\sum\limits_{i=1}^{100}i - l) (\sum\limits_{i=1}^{100}i -m -1)!}{\prod\limits_{i=1}^{100} (i!)}$$

(Para entender la fórmula, usted tiene que trabajar hacia atrás. Considere el caso donde la botella de $l$ es la última botella. Luego hay $(C_l^m)$ formas de seleccionar el $m$ sorbos de la botella que están tomadas el pasado, y hay $m!$ formas de orden. La sip antes de que la última no puede ser de botella de $l$ ya que hay exactamente $m$ sorbos a la izquierda, por lo tanto el factor de $(\sum\limits_{i=1}^{100} - l)$. Después de eso, hay $(\sum\limits_{i=1}^{100}i -m -1)$ sorbos que se puede arreglar de alguna manera.)

Deje $P(m)$ la probabilidad de tener exactamente $m$ sorbos en la última botella.

$$P(m) = \frac{N(m)}{\alpha} = \sum\limits_{l=m}^{100} \frac{(C_l^m)m!(\sum\limits_{i=1}^{100}i - l) (\sum\limits_{i=1}^{100}i -m -1)!}{(\sum\limits_{i=1}^{100} i)!}$$

Ahora, se espera que el número de los restantes sorbos en la última botella es única :

$E = \sum\limits_{m = 1}^{100} m P(m)$

Answer 3

Usted puede pensar que hay un grupo de números, con $k$ número $k$, $k = 1, 2, \ldots, n$, un total de $\frac {n(n+1)} {2}$ números en el grupo. Cada permutación de los números correspondientes a una secuencia de tomar las botellas.

El número total de permutaciones es dada por el multinomial coeffcient:

$$ \frac {\displaystyle \left(\frac {n(n+1)}{2}\right)!} {\displaystyle \prod_{k=1}^n k!}$$

El número de permutaciones dado que el número de $i$ es puesto en la final $$ \frac {\displaystyle \left(\frac {n(n+1)}{2}-1\right)!} {\displaystyle \prod_{\substack{k=1 \\ k \neq i}}^n k! (i-1)!}$$

Por lo que la probabilidad de tener número $k$ al final es

$$ \frac {\displaystyle 2k} {n(n+1)}, k = 1, 2, \ldots, n$$

Tenga en cuenta que este tiene una forma más intuitiva de interpretar: Usted también puede considerar la posibilidad de fijar el primer número - el número de permutaciones será el mismo. La probabilidad es igual al número de la $k$th botella dividido por el número total de botellas.

A continuación, la expectativa está dada por

$$ \sum_{k = 1}^n \frac {2k^2} {n(n+1)} = \frac {2} {n(n+1)} \times \frac {n(n+1)(2n+1) } {6} = \frac {2n+1} {3}$$