This week’s Fiddler is about rounding!

You are presented with a bag of treats, which contains $n \geq 3$ peanut butter cups and some unknown quantity of candy corn kernels (with any amount being equally likely). You reach into the bag $k$ times, with $3 \leq k \leq n$, and pull out a candy at random. Each time, it’s a peanut butter cup! How many candy kernels do you expect to be in the bag?

My solution:

[Show Solution]

Define the following random variables:

- $m$: number of candy corn kernels in the bag
- $K$: whether we draw $k$ peanut butter cups in a row (true/false)

We are asked to calculate the expected number of corn kernels in the bag given that we draw $k$ peanut butter cups in a row. In other words, we want to find $\mathbb{E}(m\mid K)$.

An easier quantity to calculate is the probability that we draw $k$ peanut butter cups in a row given that there are $m$ candy corn kernels in the bag. This is given by:

\begin{align*}

\mathbb{P}(K\mid m)

&= \frac{n}{n+m}\cdot \frac{n-1}{n+m-1}\cdots\frac{n-k+1}{n+m-k+1} \\

&= \frac{n!(n+m-k)!}{(n-k)!(n+m)!} \\

&= \binom{n}{k}\binom{n+m}{k}^{-1}

\end{align*}Using Bayes’ rule, we can express the desired expectation in terms of the conditional probability above:

\begin{align*}

\mathbb{E}(m\mid K)

&= \sum_{m=0}^\infty m\cdot \mathbb{P}(m\mid K)

= \sum_{m=0}^\infty m\cdot \frac{\mathbb{P}(K \mid m)\mathbb{P}(m)}{\mathbb{P}(K)}

\end{align*} Now substitute: $\mathbb{P}(K) = \sum_{m=0}^\infty \mathbb{P}(K\mid m)\mathbb{P}(m)$ and obtain:

\begin{align*}

\mathbb{E}(m\mid K)

&= \frac{\sum_{m=0}^\infty m\cdot \mathbb{P}(K \mid m)\mathbb{P}(m)}{\sum_{m=0}^\infty \mathbb{P}(K \mid m)\mathbb{P}(m)} \\

&= \frac{\sum_{m=0}^\infty m\cdot \mathbb{P}(K \mid m)}{\sum_{m=0}^\infty \mathbb{P}(K \mid m)}

\end{align*}where in the last step, we used the fact that $\mathbb{P}(m)$ is the same for all $m$ so we canceled it from the numerator and denominator. Substituting our expression for $\mathbb{P}(K\mid m)$, we obtain:

\begin{align*}

\mathbb{E}(m\mid K)

&= \frac{\sum_{m=0}^\infty m\binom{n}{k}\binom{n+m}{k}^{-1}}{\sum_{m=0}^\infty \binom{n}{k}\binom{n+m}{k}^{-1}}

= \frac{\sum_{m=0}^\infty m\binom{n+m}{k}^{-1}}{\sum_{m=0}^\infty \binom{n+m}{k}^{-1}}

%= \frac{n-k+1}{k-2}

\end{align*}

To simplify this, define the following quantity:

\[

f(k,a,b) := \sum_{i=a}^b \binom{i}{k}^{-1}

\]and observe that we have:

\[

\mathbb{E}(m\mid K) = \frac{\sum_{j=1}^\infty f(k,n+j,\infty)}{f(k,n,\infty)}

\]It turns out we can evaluate $f$, and that it has the nice closed-form expression:

\[

f(k,a,b) = \frac{k}{k-1}\left( \binom{a-1}{k-1}^{-1}-\binom{b}{k-1}^{-1}\right)

\]This formula can be proved by induction and is related to something called the German tank problem.

With this formula in hand, we can take the limit $b\to\infty$ and see that:

\[

f(k,a,\infty) = \frac{k}{k-1}\binom{a-1}{k-1}^{-1}

\]Substituting into our expression for the desired expectation, we obtain:

\begin{align*}

\mathbb{E}(m\mid K)

&= \frac{\sum_{j=1}^\infty f(k,n+i,\infty)}{f(k,n,\infty)} \\

&= \frac{\sum_{j=1}^\infty \frac{k}{k-1}\binom{n+j-1}{k-1}^{-1}}{\frac{k}{k-1}\binom{n-1}{k-1}^{-1}} \\

&= \binom{n-1}{k-1}\sum_{j=1}^\infty \binom{n+j-1}{k-1}^{-1} \\

&= \binom{n-1}{k-1} f(k-1,n,\infty) \\

&= \binom{n-1}{k-1} \frac{k-1}{k-2} \binom{n-1}{k-2}^{-1} \\

&= \frac{(n-1)!}{(n-k)!(k-1)!} \frac{k-1}{k-2} \frac{(n-k+1)!(k-2)!}{(n-1)!} \\

&= \frac{n-k+1}{k-2}

\end{align*}

Therefore, our final answer is:

$\displaystyle

\mathbb{E}(m\mid K) = \frac{n-k+1}{k-2}

$

I undoubtedly found the most complicated possible solution for this problem… So if somebody can show me a more elegant solution (perhaps a counting argument?) then I would be much obliged!