17
$\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$
  • $\begingroup$ Where did you plot this diagram ? $\endgroup$ – 0x90 Dec 14 '13 at 7:53
  • 1
    $\begingroup$ IDL software exelisvis.com/ProductsServices/IDL.aspx $\endgroup$ – Maxim Umansky Dec 14 '13 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 '13 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$ – Maxim Umansky Dec 14 '13 at 15:00
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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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