18
$\begingroup$

Suppose you are building a domino tower using identical pieces of unit length. You place a new domino piece, one at a time, on the top of the tower. However there is a random error in the placement of dominoes, so a new piece is placed some small random distance off the center of the previous piece, $x_{n+1}=x_n + \delta$, where $x_n$ is the horizontal position of nth piece. The characteristic size of the random error is $\sigma\ll$ 1, e.g., $\delta$ is drawn from a Gaussian distribution, $exp(-(\delta/\sigma)^2)$, or from a uniform distribution $-\sigma/2 < \delta < \sigma/2$, or from some other. Obviously some part of the tower will be eventually off balance and it will fall. Question: How does the expected maximum height of the tower, $\langle N \rangle$, depend on $\sigma$? Experimentally (on a computer) I see that the scaling law is very simple: $\langle N \rangle \propto 1/\sigma^2$ (for any distribution function used for $\delta$). How can this be derived analytically? enter image description here

$\endgroup$
7
  • $\begingroup$ Where did you plot this diagram ? $\endgroup$
    – 0x90
    Dec 14, 2013 at 7:53
  • 1
    $\begingroup$ IDL software exelisvis.com/ProductsServices/IDL.aspx $\endgroup$ Dec 14, 2013 at 7:54
  • $\begingroup$ I will start from this. If when I place the $N$th block and the tower falls from the $M$th block, it means $|\frac{1}{N-M}\sum_{i=M+1}^N x_i -x_M|>0.5$. which means the center of weight above $M$th block is out of support from the $M$th block. $\endgroup$
    – MoonKnight
    Dec 14, 2013 at 8:51
  • $\begingroup$ @MoonKnight What you are saying is certainly true. My computer code tests this condition for all M, once a new block is placed. So this would show that for $\delta$>0.5 already the second block would fall. But a particularly interesting scaling appears for $\sigma$<<1, because it is a simple power law independent of the form of $\delta$ distribution. $\endgroup$ Dec 14, 2013 at 15:00
  • $\begingroup$ Presumably, for small $\sigma$, you get some form of the central limit theorem kicking in, making the sum of all the different $\delta$s more or less normal for $N-M$ sufficiently large. $\endgroup$
    – Arthur
    Aug 27, 2022 at 14:22

1 Answer 1

1
$\begingroup$

I did not have a rigorous proof here, but the following analysis should provide some reasoning to your quesiton.

If we denote $\delta_i=x_i-x_{i-1}$, we can define $$ \Delta_M^{(N)}\equiv \frac{1}{N-M}\sum_{i=1}^{N-M}i\delta_{N-i+1}=\frac{1}{N-M}\sum_{i=M+1}^N x_i -x_M $$

Because $\delta_i \sim (i.i.d.) (0,\sigma^2)$, $$ \text{Var}(\Delta_M^{(N)})=\sum_{i=1}^{N-M}\left(\frac{i}{N-M}\right)^2\text{Var}(\delta_{N-i+1}) = \frac{(N-M+1)(2N-2M+1)}{6(N-M)}\sigma^2, \quad \text{mean}(\Delta_M^{(N)})=0 $$

The condition that the tower falls at height $N$ is $$ \text{Condition }a_N:\quad \exists M<N, \text{s.t.} \left|\Delta_M^{(N)}\right|>0.5 $$ $$ \text{Condition }b_N:\quad \forall n<N, \forall k<n, \left|\Delta_k^{(n)}\right|<0.5 $$

So the expected maximum height $$ \langle N \rangle = \sum_{N=2}^\infty N \cdot P(a_N \cap b_N) $$

Unfortunately, $a_N$ and $b_N$ do not seem to be independent to me, and I don't know how to evaluate the joint probability. What is worse, I don't even know how to evaluate $P(a_N)$ or $P(b_N)$. For example,

$$ P(a_N)=P\left(\bigcup_{M<N} \left|\Delta_M^{(N)}\right|>0.5 \right) $$ Again this is hard to evaluate because I don't think $\Delta_M^{(N)}$ are independent random variables within the same $N$.

What I can do is give the following, $$ \forall M<N, \quad P\left(\left|\Delta_M^{(N)}\right|>0.5\right) \le P\left(\left|\Delta_1^{(N)}\right|>0.5\right) $$

Suppose $\delta_i$ follows the normal distribution, a ROUGH estimate of the expected height can PROBABLY be given as $$ \tilde{N} \sigma^2 = \sum_{N=2}^\infty N \sigma^2 P\left(\left|\Delta_1^{(N)}\right|>0.5\right) \approx \sum_{N=2}^\infty N \sigma^2 \chi_1^2\left[(0.5)^2/(N\sigma^2/3)\right]\approx \int_0^\infty x \chi_1^2(0.75/x) dx =\text{const.} $$

Here $\chi_1^2(x)$ is the complementary CDF of chi-squared distribution with one degree of freedom. The $\approx$ sign holds here because $\sigma^2\ll 1$

So this rough estimate has the property $\tilde{N} \propto 1/\sigma^2$

Note: the normal assumption for $\delta_i$ is not needed for the conclusion, because

  1. According to central limit theory, even though $\delta_i$ are not normal, $\Delta_1^{(N)}$ is still approximately normal distributed at large $N$

  2. You can replace $\chi^2$ distribution with the corresponding variance distribution of your distribution without changing the conclusion.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .