A rigorous computation of the mean time to empty a stack of given size

Question

We are given a set of M objects in a stack S. In each iteration, an object (say O) is popped out of the stack. With probability $p_1$, O gives rise to 2 new objects which are added to S, thus S now contains $M+1$ objects. With probability $p_2$, O gives to rise to 1 new object and added to S, thus S contains M objects . With probability $1-(p_1 + p_2)$, O does not generate any new object, so S contains $M-1$ objects.

How to compute the expected number of iterations before which the stack becomes empty?

An intuitive approach-: If we denote $z$ to be the change in the number of objects in S at each iteration, then $E[z] = p_1\cdot 1 + p_2 \cdot 0 + (1-p_1-p_2)\cdot -1 = −1+2p_1+p_2$. So the expected number of iterations for stack to become empty is $M/(1-2 p_1 - p_2)$. Further assume, $1-2p_1-p_2 > 0$, to prevent unbounded stack growth.

If the intuitive approach is correct, can someone provide me a hopefully simple but rigorous proof as to why it is correct.

More specifically, I am trying to wrap my head around the idea that without computing a probability distribution of the number of items in S at each iteration, simply computing the expectation of the change in number of items is sufficient.

Answer 1

One wants to compute every $E(T_M)$, where $T_M$ denotes the number of moves necessary to empty a stack of size $M$.

Until the stack becomes empty, its size performs a random walk on the set of nonnegative integers $M$, whose steps from every positive $M$ are $M\to M+1$, $M\to M$ and $M\to M-1$, with respective probabilities $p_1$, $p_2$ and $p_3=1-p_1-p_2$. Thus, if $p_1\geqslant p_3$, every $E(T_M)$ is infinite.

If $p_1<p_3$, that is, if $2p_1+p_2<1$, we first make use of the elementary remark that, to empty a stack of size $M$, one must first reach a stack of size $M-1$, then reach a stack of size $M-2$, and so on until a stack of size $0$. By homogeneity, this shows that $$E(T_M)=ME(T_1)$$ for every positive $M$. On the other hand, starting from size $1$, the usual one-step decomposition yields $$E(T_1)=1+p_1E(T_2)+p_2E(T_1)+p_3\,0$$ thus, $$E(T_1)=\frac1{1-2p_1-p_2}$$ and, finally, for every $M$,

$$E(T_M)=\frac M{1-2p_1-p_2}$$

Answer 2

Let $X_n$ denote the stack size at step $n$, and let $Z_n$ denote the change in stack size on the $n$th step. Then $X_0=M$, $X_{n}=X_{n-1}+Z_{n-1}=X_{n-2}+Z_{n-2}+Z_{n-1}=\ldots=X_0+(Z_1+\ldots+Z_n)$; that is, $$X_n=M+\sum_{i=1}^nZ_i. $$ Therefore $$E[X_n]=M+n\,E[Z_1]$$ assuming that the $Z_i$ are iid; consequently, the value of $n$ for which $E[X_n]=0$ is such that $0=M+n\,E[Z_1]$. Thus, using the result for $E[Z_1]$ that you've already found, $$n=-{M\over E[Z_1]}={M\over 1-2 p_1 - p_2}.$$