41
$\begingroup$

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:
           Stack
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.
           Quarters
Apologies if all this is too elementary!

Added. To provide a data point, here is one simulated topple-height histogram:
           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:
           delta^2

$\endgroup$
1
  • 12
    $\begingroup$ Don't ever apologise for being elementary. $\endgroup$ Oct 6, 2011 at 22:23

2 Answers 2

17
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ That's impressive reasoning, Ori! $\endgroup$ Oct 7, 2011 at 9:59
  • 3
    $\begingroup$ [Edited only to supply a missing ")"; cf. xkcd.com/859] $\endgroup$ Oct 7, 2011 at 12:16
  • 2
    $\begingroup$ @Joseph: thanks. @Noam: So that's why I've had a restless night! $\endgroup$ Oct 7, 2011 at 16:22
9
$\begingroup$

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.

$\endgroup$
5
  • 2
    $\begingroup$ That looks roughly quadratic in 1/delta. $\endgroup$
    – JSE
    Oct 7, 2011 at 2:32
  • $\begingroup$ what are the second moments? $\endgroup$
    – Will Sawin
    Oct 7, 2011 at 2:53
  • $\begingroup$ I voted this up so now you can comment. :) $\endgroup$
    – JRN
    Oct 7, 2011 at 2:53
  • $\begingroup$ @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. $\endgroup$ Oct 7, 2011 at 9:58
  • $\begingroup$ For $\delta=\frac{1}{5}$, you see 34.65, and I calculate 34.66. Our simulations are in accord. :-) $\endgroup$ Oct 7, 2011 at 12:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.