0

Suppose we have 2 piles of coins, each with $n$ coins. Every time we randomly pick a pile and take away 1 coin. When one of the piles becomes empty, what is the expectation of the number of coins in the remaining pile?

neverevernever
  • 351
  • let $f(n,m)$ be the answer when piles start off with $n,m$ coins. then $f(n,m) = \frac{1}{2}f(n-1,m)+\frac{1}{2}f(n,m-1)$. you also have the conditions $f(n,0) = n, f(0,m) = m$. solve the recurrence for $f(n,m)$ for general $n,m$. then see what you get for $n=m$ – mathworker21 Sep 25 '19 at 03:23
  • @mathworker21 - you mean there is a closed form for this? – antkam Sep 25 '19 at 04:37
  • @antkam i guess that's implicit in my comment. do u think there isn't? i didnt try – mathworker21 Sep 25 '19 at 04:43
  • @mathworker21 - hmm... will try tomorrow! :) – antkam Sep 25 '19 at 04:48
  • Computation shows that $$f(n,n)={(2n-1)!!\over(2n-2)!!}$$ for $n\leq20$, but I haven't tried to find the formula for $f(n,m)$ yet. – saulspatz Sep 25 '19 at 05:46
  • Related: https://math.stackexchange.com/questions/1011354/banach-matchbox-problem –  Sep 27 '19 at 07:24

1 Answers1

1

Let $X_i$ be the number of potential draws from pile $i\in \{0,1\}$ until the other pile is empty. Then $$ \mathsf{P}(X_i=k)=\binom{n+k-1}{k}\left(\frac{1}{2}\right)^{n+k}. $$ Letting $Y$ denote the number of remaining coins in a non-empty pile after the other pile has been emptied, for $m\in\{1,\ldots,n\}$ one gets \begin{align} \mathsf{P}(Y=m)&=\mathsf{P}(Y=m,X_1<n)+\mathsf{P}(Y=m,X_2<n) \\ &=\mathsf{P}(X_1=n-m)+\mathsf{P}(X_2=n-m) \\ &=\binom{2n-m-1}{n-m}\left(\frac{1}{2}\right)^{2n-m-1}. \end{align} Finally, \begin{align} \mathsf{E}Y&=\sum_{m=1}^n m\binom{2n-m-1}{n-m}\left(\frac{1}{2}\right)^{2n-m-1}=\binom{2(n-1)}{n-1}\frac{2n-1}{2^{2(n-1)}} \\ &=\frac{(2n-1)!!}{(2n-2)!!}\approx\frac{2n-1}{\sqrt{\pi(n-1)}}\approx 2\sqrt{\frac{n-1}{\pi}}. \end{align}

  • How do you get $\sum_{m=1}^n m\binom{2n-m-1}{n-m}\left(\frac{1}{2}\right)^{2n-m-1}=\binom{2(n-1)}{n-1}\frac{2n-1}{2^{2(n-1)}}$? I got this far, but couldn't see how to simplify the sum. – saulspatz Sep 25 '19 at 14:05
  • \begin{align} &\sum_{m=1}^n m\binom{2n-m-1}{n-m}\left(\frac{1}{2}\right)^{2n-m-1}=\sum_{k=1}^{n-1} (n-k)\binom{n+k-1}{k}\left(\frac{1}{2}\right)^{n+k-1} \ &\qquad =n-n\sum_{k=0}^{n-2} \binom{n+k}{k}\left(\frac{1}{2}\right)^{n+k} \ &\qquad =n\binom{2n}{n}\left(\frac{1}{2}\right)^{2n}+n\binom{2n-1}{n-1}\left(\frac{1}{2}\right)^{2n-1}=\ldots, \end{align} where the second line uses the fact that $$ \sum_{k=0}^n\binom{n+k}{k}\left(\frac{1}{2}\right)^{n+k}=1. $$ –  Sep 25 '19 at 16:19
  • For the last identity see Example 2 in this book. –  Sep 25 '19 at 17:11