height of domino tower

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? • Where did you plot this diagram ? – 0x90 Dec 14 '13 at 7:53
• IDL software exelisvis.com/ProductsServices/IDL.aspx – Maxim Umansky Dec 14 '13 at 7:54
• 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. – MoonKnight Dec 14 '13 at 8:51
• @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. – Maxim Umansky Dec 14 '13 at 15:00

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.