How does the author find $M_n(p)$ in the Toilet Paper Problem

Question

In this paper, The Toilet Paper Problem, by D. Knuth, in the first page the author states that

Let us assume that people enter the toilet stalls independently at random, with probability $p$ that they are big-choosers and probability $q = 1 - p$ that they are little-choosers. If the janitor supplies a particular stall with two fresh rolls of toilet paper, both of length $n$, let $M_n (p)$ be the average number of portions left on one roll when the other roll first empties. (We assume that everyone uses the same amount of paper, and that the lengths are expressed in terms of this unit.) For example, it is easy to establish that

$$M_1(p) = 1, \quad M_2(p) = 2-p, ...$$

, but how does he find $M_n(p)$ ?

I mean, if $n = 1$, people choose one of the stalls at random and since both stalls have 1 unit of paper, the other will be left with 1 unit of paper, hence $M_1(p) = 1$, but for other cases, I couldn't derive the relations clearly.

Answer 1

Keeping track rather of both roll states as $M(a,b)$ with $0\le a\le b$, we find $$M(a,b)=\begin{cases}(1-p)M(a-1,b)+pM(a,b-1)&0<a<b\\ M(a-1,a)&0<a=b\\ b&0=a(<b)\end{cases} $$ This is good enough to compute $M_n(p)=M(n,n)$ for small $n$, e.g., one quickly obtains $$ M_{10}(p)=-1430p^{17} + 11440p^{16} - 39182p^{15} + 74074p^{14} - 82478p^{13} + 52426p^{12} - 15782p^{11} + 502p^{10} + 246p^9 + 118p^8 + 54p^7 + 22p^6 + 6p^5 - 2p^4 - 6p^3 - 8p^2 - 9p + 10$$

Answer 2

Let's compute $M_2(p)$. We want the 'average' or 'expected' number of sheets left on one of the rolls when the other one is empty.

Starting both rolls with 2 sheets, label this $[2,2]$. The first person goes into the stall and uses one sheet. Regardless of who it is, big or small chooser, they take from second roll . So now we have $[2,1]$. The second user comes in. With probability $q=1-p$ they are small user so we end up with $[2,0]$. With probability $p$ they are big chooser so we end up with $[1,1]$. In that first scenario we terminate so with probability $q$ we are left with 2 sheets. In the second scenario it doesn't matter who comes in, by the end of the step we end up with $[1,0]$. Thus with probability $q$ we end with $[2,0]$ and with probability $p$ we end with $[1,0]$. And so on average we have $2q+p=2-2p+p=2-p$.

Try doing out $M_3(p)$. I recommend doing this with a tree diagram. Branching with the probabilities of big or small chooser and terminating a branch when a roll runs out.

For $M_n(0)$ this means we always have small choosers, so we get $[n,n]\rightarrow [n,n-1]\rightarrow [n,n-2]\rightarrow \cdots \rightarrow [n,0].$ And so $M_n(0)=n$. For $M_n(1)$, we always have big choosers so we have $[n,n]\rightarrow [n,n-1]\rightarrow [n-1,n-1]\rightarrow \cdots \rightarrow [1,1]\rightarrow [0,1].$