# Topple height of randomly stacked bricks

What is the expected height of a stack of unit-length bricks, each one stacked on the previous with a uniformly random shift within $\pm \delta$? The stack topples if the center of gravity of the top $k$ does not rest on the brick under that top group. For example, here I used $\delta = \frac{1}{3}$, and the stack was stable after the 21st brick was placed (the green top-group center-of-gravity dots), but the 22nd brick caused the centers of gravity to shift (red dots), with the cg of the top four bricks (arrow marked) now overhanging the 18th brick beneath:

Let $N(\delta)$ be the expected height (number of bricks) of such a stack. Computing this is elementary in some sense, but I am not arriving at a satisfactory formulation to let me see the overall growth clearly. Perhaps this has been studied, given the vast literature on brick-stack overhangs? If so, a pointer would be appreciated.

I set out to explore random stacks of disks, but even the above simpler rectangular bricks case is more intricate than I anticipated.

Apologies if all this is too elementary!

Added. To provide a data point, here is one simulated topple-height histogram:

Update. Here is a plot of Aaron Golden's data, $N(\delta)$ vs. $\delta^{-2}$, which certainly supports Ori's $\delta^{-2}$ conclusion, as JSE noted:

-
Don't ever apologise for being elementary. –  James Cranch Oct 6 '11 at 22:23

The distribution should be roughly geometric with expectation roughly $\delta^{-2}$. To bound from above, in every $2\delta^{-2}$ steps there is a constant (independent of $\delta$) probability that the location of the $\delta^{-2}$ brick will be at least offset of 3 from the first brick. Then there is a constant probability for the next $\delta^{-2}$ bricks to be all at offset 2 or more, thus causing collapse. This event can happen independently for every batch of $\delta^{-2}$ bricks, so we get domination by geometric distribution with expectation $O(\delta^{-2})$.

On the other hand, the probability that the center of the brick never strays more than $1/4$ away from the center for $t$ bricks should be roughly $e^{-ct\delta^2}$ so we get bound from below by a geometric distribution with expectation $\Omega(\delta^{-2})$ too.

The coins case should be similar, still $\delta^{-2}$, but with a different constant.

-
That's impressive reasoning, Ori! –  Joseph O'Rourke Oct 7 '11 at 9:59
[Edited only to supply a missing ")"; cf. xkcd.com/859] –  Noam D. Elkies Oct 7 '11 at 12:16
@Joseph: thanks. @Noam: So that's why I've had a restless night! –  Ori Gurel-Gurevich Oct 7 '11 at 16:22

This is intended as a comment on the question, but I lack the MO reputation to leave comments.

I think it would be worthwhile to start by carefully verifying that the numerical experiments are coming out correctly. I wrote a quick program to simulate the stacking you describe and I get a sequence of average heights:

1.87, 6.10, 13.22, 22.67, 34.65, 48.56, 65.18, 83.94

over 100,000 stacks for $\delta$ equal to 1, 1/2, 1/3, 1/4, 1/5, 1/6, 1/7, 1/8. Does this agree with your results? If not maybe we should compare source code.

-
That looks roughly quadratic in 1/delta. –  JSE Oct 7 '11 at 2:32
what are the second moments? –  Will Sawin Oct 7 '11 at 2:53
I voted this up so now you can comment. :) –  Joel Reyes Noche Oct 7 '11 at 2:53
@Aaron: Yes! For $\delta=\frac{1}{3}$, you see 13.22, which matches my (less accurate) 13.28. I'll make further comparisons as my schedule permits. –  Joseph O'Rourke Oct 7 '11 at 9:58
For $\delta=\frac{1}{5}$, you see 34.65, and I calculate 34.66. Our simulations are in accord. :-) –  Joseph O'Rourke Oct 7 '11 at 12:08