A random stacking process (Q1850032)

The author considers the following game. You have an unbounded supply of chips in each of \(k\) colors that you want to stack. Each time you place a chip on top of the stack, there is probability \(1-\varepsilon\) that it stays, and probability \(\varepsilon\) it falls off the stack, and with it go also the rest of the chips at the top until, but not including the next chip of the same color. (If there is no chip of the same color, then all go.) The game ends when the stack reaches height \(N\) and the last chip sticks. Let \(T_N\) denote the expected duration of the game. The main result asserts that: (i) if \(\varepsilon <1/k\), then \(T_n\leq N/(1- \varepsilon k)\) for any strategy; (ii) if \(\varepsilon =1/k\), then there is a unique ``cycling'' strategy maximizing \(T_N\), and \(T_N\) is quadratic in \(N\); (iii) if \(\varepsilon >1/k\), then there is a strategy ensuring that \(T_N\) is exponential in \(N\).