Expectation of Last Remaining Container

Question

You decide to play a holiday drinking game. You start with 100 containers of eggnog in a row. The 1st container contains 1 liter of eggnog, the 2nd contains 2 liters, all the way until the 100th, which contains 100 liters. You select a container uniformly at random and take a one liter sip from it. If the container is empty after taking this sip, you remove it from the row and select only from the remaining bottles. You continue this process until there is only 1 bottle remaining. What is the expected number of liters of eggnog in this last bottle? What is this as this as a function of n, the number of starting bottles?

I came up with this problem myself recently, and I'm not really sure how to approach it. I can find the conditional expectation of a bottle given that it is the last one remaining using linearity of expectations, but it's not clear to me how to use this to get the overall expectation.

Answer 1

You may think there is a group of numbers, with $k$ number $k$, $k = 1, 2, \ldots, n$, a total of $\frac {n(n+1)} {2}$ numbers in the group. Each permutation of numbers corresponding to a sequence of taking the bottles.

The total number of permutation is given by the multinomial coeffcient:

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

The number of permutation given that the number $i$ is put at the end $$ \frac {\displaystyle \left(\frac {n(n+1)}{2}-1\right)!} {\displaystyle \prod_{\substack{k=1 \\ k \neq i}}^n k! (i-1)!}$$

So the probability of having number $k$ at the end is

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

Note that this has a more intuitive way to interpret: You may also consider fixing the first number - the number of permutation will be the same. The probability is equal to the number of the $k$th bottle divided by the total number of bottles.

Then the expectation is given by

$$ \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}$$

Answer 2

Finding the exact answer may not be feasible for 100 containers, I think. I managed to compute up to 5 containers using recurrence and a computer. The following python code generates the recurrence for 5 containers with the boundary conditions:

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)

which gives the recurrence

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

which can be input to friCAS and we can compute values like f5(1,2,3,4,5).

Here are the answers for number of containers being 2,3,4,5:

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

And for 100 containers, a monte-carlo simulation gives an answer close to $5.6$

Answer 3

EDIT This answer is valid only in the assumption that the probability of taking a sip from a bottle is proportional to the number of sips remaining.

Let $\alpha$ be the number of ways we can arrange all the sips (even counting the one in the end that are not taken)

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

(there are $\sum\limits_{i=1}^{100} i$ sips, and for the bottle $i$, $i!$ sips are "identical")

Let $N(m)$ be the number of ways to arrange all sips in a way that exactly $m$ sips of one bottle remain in the end is :

$$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!)}$$

(To understand the formula, you have to work backward. Consider the case where the bottle $l$ is the last bottle. Then there are $(C_l^m)$ ways to select the $m$ sips from that bottle that are taken last, and there are $m!$ ways to order them. The sip before the last one can not be from bottle $l$ since there are exactly $m$ sips left, hence the factor $(\sum\limits_{i=1}^{100} - l)$. After that, there are $(\sum\limits_{i=1}^{100}i -m -1)$ sips that can be arranged in any way.)

Let $P(m)$ be the probability of having exactly $m$ sips in the last bottle.

$$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)!}$$

Now, the expected number of remaining sips in the last bottle is only :

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