12
$\begingroup$

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.

$\endgroup$
  • 4
    $\begingroup$ Post your computation of the conditional expectation of the amount left in the bottle. $\endgroup$ – A.S. Dec 18 '15 at 0:32
  • $\begingroup$ A one-liter sip?! $\endgroup$ – Brian Tung Jan 4 '16 at 22:52
5
+100
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ That's suspiciously close to $1+\ln 100$. Of course, that may mean nothing at all... $\endgroup$ – Brian Tung Jan 4 '16 at 22:57
  • $\begingroup$ Maybe that's the asymptotic formula. I believe it can at least be answered as a summation involving binomials. $\endgroup$ – gar Jan 5 '16 at 11:37
  • $\begingroup$ I checked for 120, simulation was closer to 6, but $1+\ln{120} \approx 5.78$ $\endgroup$ – gar Jan 8 '16 at 4:58
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Hi, I tried the formula for some smaller numbers, but got negative values. What's the formula's answer for 2 or 3 bottles? $\endgroup$ – gar Dec 28 '15 at 17:04
  • $\begingroup$ I made a mistake in one of the formulas. It has been corrected. I get $E = 4/3$ for 2 bottles, and $E = 79/60$ for 3 bottles. I find this weird, since the expected value is slightly lower for the case with 3 bottles. Maybe it is a calculation error, maybe it is some strange statistical outcome... $\endgroup$ – fredq Dec 30 '15 at 19:09
  • $\begingroup$ But the answer is lower for 2 bottles also, isn't it? $\endgroup$ – gar Jan 1 '16 at 14:05
  • $\begingroup$ upon more reflection, i noticed my approach is flawed because bottles with more sips are more likely to be chosen. However, in the original question, all bottle with at least 1 sip has the same probability. $\endgroup$ – fredq Jan 4 '16 at 22:28
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Sorry I maybe misinterpret the question. $\endgroup$ – BGM Dec 17 '15 at 11:41
  • $\begingroup$ In special case $n=2$ the answer is $\frac122+\frac121=\frac32\neq\frac53$ so unfortunately this does not work. $\endgroup$ – drhab Dec 17 '15 at 14:31
  • $\begingroup$ Sorry to get back late here. I realize I have think wrongly after posting the answer (sorry about that again). The only thing that is correct above is the total number of ways to take the bottles is indeed $\left(\frac {n(n+1)} {2}\right)!$, but each permutation is not equally likely. Because this number grows so fast, so brute force method may not be suitable for you. Even for $n = 3$ case, I need to exhausted all 60 ways and compute the expectation to be $\frac {125} {72}$. I guess the complexity of the problem is high and not sure if there is a smart method to do. $\endgroup$ – BGM Dec 18 '15 at 3:54
  • $\begingroup$ In a general framework, what I can think of now is that you maybe able to express the problem as a recursive problem just like what we did in Markov chain. Let $Y$ and $X_i$ be the number of liters in the last and $i$ bottle, be $f(k_1,k_2,...,k_n)=E[Y|(X_1,X_2,...,X_n)=(k_1,k_2,...,k_n)]$, and $a(k_1,k_2,...,k_n)$ be the number of non-zero $k_i$. The boundary condition is when $a=1$, then $f = k_i$ (the non-zero one), and $f=\frac {1} {a} [f(k_1-1,k_2,...,k_n)+...+f(k_1,k_2,...,k_n-1)]$. Not sure if these kind of formulation can help, beside brute force. I guess they require similar effort. $\endgroup$ – BGM Dec 18 '15 at 4:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.