Will the stack ever underflow?

Question

A program issues n push operations and n pop operations on a stack, in a uniformly random interleaving. A pop on an empty stack is an error. What is the probability the whole sequence runs without ever popping from an empty stack?

Accepted Answer

Represent the sequence as a lattice path: +1 for a push, -1 for a pop. The running height is the current stack size. Since there are n pushes and n pops, the path starts and ends at 0. "Never pop from empty" means the height never goes below 0, so we need paths that stay \ge 0 throughout: exactly the Dyck paths. All interleavings are equally likely, and there are \binom{2n}{n} of them. The number that stay non-negative is the Catalan number Cn = \frac{1}{n+1}\binom{2n}{n}. (One clean derivation: by the reflection/cycle argument, among the \binom{2n}{n} sequences, exactly a fraction 	frac{1}{…

Will the stack ever underflow?

Your answer

More Probability questions