1

Note: Although the title might sound silly, the question is (probably) not. It originated in a university-level probability course where I came across it. This most certainly is some known problem which maybe goes under another name as I did not find anything related.

The question goes as follows. Suppose $A$ has two identical boxes of candy $K_1$ and $K_2$ in his pocket which both contain $n$ pieces of candy. During the day, $A$ repeatedly reaches into his pocket and grabs randomly from either one of the boxes one piece of candy. What is the probability that, when A grabs into an empty candy box, in the other box there are exactly $0 \leq k \leq n$ pieces of candy left? Assume that it is okay for the candy box to be empty as long as $A$ does not try to grab a candy from it.

What I attempted is the following. I first defined the underlying set of possible outcomes as

$$\Omega = \{ (j, k)\;\vert\; j \in K_1, k \in K_2, 0\leq j,k \leq n\}$$

and assumed the probability for reaching in either $K_1$ or $K_2$ to be equal, i.e. $p_{K_i} = \frac{1}{2},\; i \in {1,2}$. I then proceeded by setting up a probability tree starting with $(n, n)$. I thought that what I had to do was, for each $(0, k)\; 0 \leq k \leq n$ and $(k, 0)\; 0 \leq k \leq n$ respectively to figure out the possible routes to go there and then try to find the probabilities depending on the exact $k$. $A$ can reach at most $2n$ times into his pocket before all candy is gone. Hence I thought that the lowest possible probability would be associated to the case where he alternates the boxes. After all boxes are empty he would necessarily grab an empty one next. Similarly, if he only grabs from one box again and again he would only need $n+1$ grabs before he reaches into an empty box with $n$ pieces of candy being in the other box. Yet, for the cases in the middle there are certain "detours" he can take which grow fast with the tree. As a result, what I do not get is the kind of pattern from which to extract the probability for every $k$?

EDIT: In the end I found that this problem is a variant of Banach's matchbox problem. There is a solution here at this site.

Taufi
  • 1,095

1 Answers1

1

We can model the unfolding story as a random walk in the first quadrant of the $(x,y)$-plane. Start at $(0,0)$. Make one unit step $\to$ each time you take a candy from box $K_1$, and make one unit step $\uparrow$ each time you take a candy from box $K_2$. When the walk reaches one of the points $(n,k)$ or $(k,n)$ then one box is empty, but this is not felt yet. Only when the walk makes a step out of the square $[0,1]^2$ an empty box has been opened, but there are still $k'=n-k$ candies in the other box. At $(n,k)$ or $(k,n)$ with $k<n$ this happens with probability ${1\over2}$, at $(n,n)$ with probability $1$. It has been told here many times that there are ${j+k\choose k}$ different walks from $(0,0)$ to the point $(j,k)$. The probability that the point $(n,k)$ is reached is therefore given by $${1\over 2^{n+k}}{n+k\choose k}\qquad(0\leq k\leq n)\ ,$$ and the point $(k,n)$ is reached with the same probability. It follows that the probability of having exactly $k'$ leftover candies when opening an empty box is given by $${1\over 2^{2n-k'}}{2n-k'\choose n}\qquad(0\leq k'\leq n)\ .$$

Christian Blatter
  • 226,825