Inspired by some truly incredible domino construction, Ed Foley poses the following puzzle:
You are placing many, many dominoes in a straight line, one at a time. However, each time you place a domino, there is a 1 percent chance that you accidentally tip it over, causing a chain reaction that tips over all dominoes you’ve placed. After a chain reaction, you start over again.
If you do this many, many times, what can you expect the median (note: not the average) number of dominoes placed when a chain reaction occurs (including the domino that causes the chain reaction)? More precisely, if this median number is M, then you would expect to have placed fewer than M dominoes at most half the time, and more than M dominoes at most half the time.
The following tree diagram summarizes the domino placement and total length:
In order to determine the median length, the sum of the probabilities of all probabilities from $0$ to $M$ must greater than and as close to $\frac{1}{2}$.
This is an finite geometric sum with $a_1 = \frac{1}{100}$ and $r = \frac{99}{100}$.
\begin{align*} \frac{1}{100}\sum\limits_{d=0}^{M-1} \left(\frac{99}{100}\right)^d &\ge \frac{1}{2} \\ \frac{1}{100}\left(\frac{1-\left(\frac{99}{100}\right)^M}{1-\frac{99}{100}}\right) &\ge \frac{1}{2} \\ 1-\left(\frac{99}{100}\right)^M &\ge \frac{1}{2} \\ \frac{1}{2} &\ge \left(\frac{99}{100}\right)^M \\ \ln \frac{1}{2} &\ge M\ln \frac{99}{100} \\ \frac{\ln \frac{1}{2}}{\ln \frac{99}{100}} \approx 68.97 &\ge M\\ \end{align*}You’re placing dominoes again, but this time the probability of knocking each domino over and causing a chain reaction isn’t 1/100, but rather 10-k, where k is a whole number. When k = 1, the probability of knocking over a domino is 10 percent; when k = 2, this probability is 1 percent; when k = 3, this probability is 0.1 percent, and so on.
Suppose the expected median number of dominoes placed that initiates a chain reaction is M. As k gets very, very large, what value does M/10k approach?
The following tree diagram summarizes the domino placement and total length:
Solving similarly as in Fiddler above :
\begin{align*} \frac{1}{10^k}\sum\limits_{d=0}^{M-1} \left(1-\frac{1}{10^k}\right)^d &\ge \frac{1}{2} \\ \frac{1}{10^k}\left(\frac{1-\left(1-\frac{1}{10^k}\right)^M}{1-\left(1-\frac{1}{10^k}\right)}\right) &\ge \frac{1}{2} \\ 1-\left(1-\frac{1}{10^k}\right)^M &\ge \frac{1}{2} \\ \frac{1}{2} &\ge \left(1-\frac{1}{10^k}\right)^M \\ 2 &\ge \left(\frac{10^k}{10^k-1}\right)^M \\ 2 &\ge \left(1+\frac{1}{10^k-1}\right)^M \\ \ln 2 &\ge M\ln \left(1+\frac{1}{10^k-1}\right) \\ \ln 2 &\ge \frac{M}{10^k}\ln \left(1+\frac{1}{10^k-1}\right)^{10^k} \\ \frac{M}{10^k} &\approx \frac{\ln 2}{\ln \left(1+\frac{1}{10^k-1}\right)^{10^k}} \\ \end{align*}Evaluating as $k \rightarrow \infty$,
\begin{align*} \lim_{k \rightarrow \infty} \frac{M}{10^k} &= \lim_{k \rightarrow \infty} \frac{\ln 2}{\ln \left(1+\frac{1}{10^k-1}\right)^{10^k}} \\ &= \frac{\ln \big(\lim_{k \rightarrow \infty} 2\big)}{\ln \left(\lim_{k \rightarrow \infty} \left(1+\frac{1}{10^k-1}\right)^{10^k}\right)} \\ &= \frac{\ln 2}{\ln \left(\lim_{k \rightarrow \infty} \left(1+\frac{1}{10^k}\right)^{10^k}\right)} \\ &= \frac{\ln 2}{\ln \left(\lim_{j \rightarrow \infty} \left(1+\frac{1}{j}\right)^j\right)} \\ \end{align*}