# Generating function for Banach's matchbox problem

Here's the description for Banach's matchbox problem from Concrete Mathematics EXERCISE 8.46 (edited)

Stefan Banach used to carry two boxes of matches, one containing $m$ matches and the other one containing $n$ matches. Whenever he needed a light he chose a box at random, each with probability $\frac 1 2$, independent of his previous choices. After taking out a match he'd put the box back in its pocket (even if the box became empty -- all famous mathematicians used to do this). When his chosen box was empty he'd throw it away and reach for the other box.

• Once he found that the other box was empty too. What's the probability $p_{m,n}$ that this occurs?
• Generalizing your answer to part (a), find a closed form for the probability $p_{k,m,n}$ that exactly $k$ matches are in the other box when an empty one is first thrown away.

The answer to these two problems only show two generating functions and the answer:

(a) $P(w,z) = 1 + \frac 1 2 (wP(w,z) + zP(w,z)) = (1 - \frac 1 2 (w+z))^{-1} \tag 1$ hence $p_{m,n} = 2^{-m-n} \binom {m+n} n$ (b) $P_k(w,z) = \frac 1 2 (w^k+z^k)P(w,z) \tag 2$ hence $p_{k,m,n} = 2^{k-1-m-n} \left( \binom{m+n-k}m + \binom{m+n-k}n \right)$

where $P(w,z) = \sum_{m,n \ge 0} p_{m,n}w^mz^n$ and $P_k(w,z) = \sum_{m,n \ge 0} p_{k,m,n}w^mz^n$ is generating functions for $p_{m,n}$ and $p_{k,m,n}$.

I'm confused that the two equations for generating functions come out first then we get the closed form. I don't know how they come directly.

There might be a reasonable explanation for formula (1):

We have $p_{m,n} = \frac 1 2 (p_{m-1,n} + p_{m,n-1}) + [m=n=0]$ for all integers $m,n$ where $p_{m,n} = 0$ whenever $m<0$ or $n<0$. $[P]$ is Iverson bracket. Multiplying $z^mw^n$, summing up over all integers $m,n$ we get equation (1), but equation (2) lacks evidence. Although we can interpret $p_{k,m,n} = \frac 1 2 (p_{m-k,n} + p_{m,n-k})$ combinatorially, we cannot explain why the generating function arises, because the preceding formula gives the closed-form directly, without generating function.

So I guess that there's a direct way to obtain equation (1) and (2), without the assistant of recurrence relations, just like section 7.1 DOMINO THEORY AND CHANGE, or section 8.4 FLIPPING COINS.

Any help? Thanks!

Postscript: There's a combinatorial proof for (b). Mention that (a) is a special case of (b). $\newcommand{\length}{\mathrm{length}}$

First, we define the probablility space for the matchbox problem. We use symbol $L$ indicating fetching a match from the left matchbox, and symbol $R$ from the right one. The elementary events are defined as strings of $L$ and $R$ which ends at an attempt of fetching the match from the empty matchbox. For example, when $m=2$ and $n=1$, we have the probability space $\Omega = \{LLL, LLRL, LLRR, LRLL, LRLR, LRR, RLLL, RLLR, RLR, RR\}$. The elementary event $LLRR$ means that the 1st and 2nd matches are from the left matchbox, and the 3rd is from the right one. The 4th time is trying to fetch the match from the right matchbox, but it's empty. $\length(\omega)$ indicates the length of elementary event $\omega$. We have $\Pr(\omega) = 2^{-\length(\omega)}$.

Now let's try to enumerate all elementary events for the problem (b). There're two cases: Case 1, the right matchbox remains $k$ matches. We use $\Omega_1$ to indicate such elementary event. For each $\omega \in \Omega_1$, there're $m+1$ $L$'s in $\omega$, and $n-k$ $R$'s in it, and the last symbol of $\omega$ is $L$. For each $\omega \in \Omega_1$, $\Pr(\omega) = 2^{\length(\omega)} = 2^{-(m+n-k+1)}$, and $|\Omega_1| = \dbinom{m+n-k}m$. Case 2, the left matchbox remains $k$ matches, saying $\Omega_2$. We have $|\Omega_2| = \dbinom{m+n-k}n$, and for each $\omega \in \Omega_2$, we have $\Pr(\omega) = 2^{\length(\omega)} = 2^{-(m+n-k+1)}$.

Thus \begin{align*} p_{k,m,n} &= \sum_{\omega \in \Omega_1 \cup \Omega_2} \Pr(\omega) \\ &= \sum_{\omega \in \Omega_1} \Pr(\omega) + \sum_{\omega \in \Omega_2} \Pr(\omega) \\ &= 2^{-(m+n-k+1)} \left( \binom{m+n-k}{m} + \binom{m+n-k}{n} \right) \end{align*}

Just like you did for the first part, by conditioning on the first match removed, we get the recurrence $$p_{k,m,n} = \frac{1}{2} p_{k,m-1, n} + \frac{1}{2} p_{k,m,n-1} + \frac{1}{2}[m=k, n=0 \; \text{or} \; m=0, n=k]$$where $p_{k,i,j}$ is 0 if $i<0$, $j<0$, or both $i,j<k$. Why the factor of 1/2? When you're at exactly $0$ and $k$, you need pick next from the box with 0 matches, which happens half the time.

When we translate the recurrence into a power series, we get $$P_k(w,z) = \frac{w+z}{2}P_k(w,z) + \frac{1}{2}(w^k + z^k)$$So $$P_k(w,z) = \frac{1}{2} \frac{w^k+z^k}{1 - \frac{w+z}{2}}$$where before $$P = \frac{1}{1 - \frac{w+z}{2}}$$

• Alright. I'm looking for anybody else interpreting the equation (2) directly, other wise I'll take your answer. Jun 5, 2012 at 2:02

Lol not quite anybody else, but here goes: interpret the problem as a random walk on the lattice $\mathbb{Z}^2$, where you start at $(m,n)$, and at each step move either one down or one left.

The problem is then: what are the odds you hit either $(k,0)$ or $(0,k)$, times $\frac{1}{2}$, the half being there for the same reason as in the recurrence above.

By the nature of the walk, these are disjoint events. So our desired probability is sum of the probabilities of hitting $(k,0)$ and hitting $(0,k)$ (times $\frac{1}{2}$ still).

Now I claim the odds of hitting $(k,0)$ are exactly $p_{m-k,n}$. But indeed this is clear, shift the starting point and desired hitting point down by $k$, you have the first problem.

• Using this relation between $p_{k,m,n}$ and $p_{m,n}$, We don't need generating functions. I want to study generating functions more closely, so I posted this question. Jun 5, 2012 at 5:47
• In addition, $p_{m,n}$ could also be solved without generating functions. It's not very hard to see that $p_{m,n} = \binom{m+n}{m} / 2^{m+n}$ because we temporarily allow to fetch matches from an empty matchbox, and there're $2^{m+n}$ ways to fetch where $\binom{m+n}{m}$ ways are legal. It's trivial to show that, the two probability models are equivalent. Hence, the probability is $\binom{m+n}{m}/2^{m+n}$. Am I right? Jun 5, 2012 at 5:51
• oh woah, you're asking for a way to get a relationship between the generating functions, that avoids actually looking at the underlying probabilities? I have no idea o_O, and I totally misunderstood your question. I'm not great with recurrences, so these looked hard to solve for me... :/ ...My b Jun 5, 2012 at 5:56
• and yeah, I agree with your derivation of $\binom{m+n}{m}/2^{m+n}$, where you get the binomial coefficient since it counts the number of draws of $m+n$ Ls and Rs, which contain exactly $m$ Ls and $n$ Rs. slick man Jun 5, 2012 at 6:00
• I‘m fairly confused with probability problems, even if it's elementary. The probability space converts each other flexibly. Concrete Mathematics gives a source of this problem, but in that book, there's no generating function. Jun 5, 2012 at 6:00