Another “Wall Street” Brain Teaser

You have a printer that randomly shuffles the order of pages of your papers. To put your work back in order, you proceed through the stack on the printer as follows:

Given a page $p$, if neither $p\pm1$ have been seen, create a new pile. If one of $p+1$ or $p-1$ have been seen, add $p$ to the front of $p+1$’s pile or the end of $p-1$’s pile. If both $p\pm1$ have been seen, merge the two piles into one. What’s an upper bound on the maximum number of piles you’ll have at any moment while reconstructing an $n$ page document?

We can think of this process as a series of binary strings. Each step can be represented by $S_t \in \{0, 1\}^n$ with the bit at index $p$ set if that page has been seen. If we count the expected instances of “$01$” as a function of $t \in [0, 1]$. Without too much effort, we see that $E[f\big(t)] \approx n(t - t^2)$. This is maximized around $n/4$ when $t = n/2$. When $n$ is large, the maximum exceeds its expectation by $\mathcal{\Theta}\big(n^{1/2})$.