Can You Tip the Dominoes?

You place dominoes in a line one at a time. Each domino you place has a $1\%$ chance of tipping over, which knocks down every domino placed so far; then you start again. Over many rounds, what is the median number of dominoes placed (counting the one that triggers the cascade) at the moment a cascade happens?

The Fiddler, Zach Wissner-Gross, March 7, 2025(original post)

Solution

The number $N$ of dominoes placed up to and including the trigger is geometric: each placement independently triggers with probability $p=0.01$, so $\mathbb{P}(N>n)=(1-p)^n$. The median is the smallest $n$ with $\mathbb{P}(N\le n)\ge\tfrac12$, i.e. $$(1-p)^n\le\tfrac12 \iff n\ge\frac{\ln 2}{-\ln(1-p)}=\frac{\ln 2}{-\ln 0.99}\approx 68.97,$$ so the median is $$\left\lceil\frac{\ln 2}{-\ln 0.99}\right\rceil=\boxed{69}.$$ (Check: $0.99^{68}\approx0.5050>\tfrac12$ and $0.99^{69}\approx0.4998<\tfrac12$, so the cumulative probability first crosses $\tfrac12$ at $n=69$.)

The computation

Play the rounds rather than the formula: the dominoes placed before a $1\%$ trigger is exactly a geometric draw, so simulate millions of rounds and take the empirical median.

import numpy as np
rng = np.random.default_rng(0)
N = rng.geometric(0.01, 5_000_000)        # placements up to and including the trigger
print(np.median(N))                       # 69.0

Extra Credit

Replace $1\%$ by $10^{-k}$ for a whole number $k$, and let $M$ be the resulting median. What does $M/10^{k}$ approach as $k\to\infty$?

Solution

The median is $M=\bigl\lceil\ln 2/(-\ln(1-10^{-k}))\bigr\rceil$. For small $x$, $-\ln(1-x)=x+\tfrac{x^2}{2}+\cdots$, so with $x=10^{-k}$, $$\begin{gathered} \frac{M}{10^{k}}\approx\frac{\ln 2}{10^{k}\,(-\ln(1-10^{-k}))} =\frac{\ln 2}{1+\tfrac12 10^{-k}+\cdots}\\[4pt] \longrightarrow\boxed{\ln 2\approx0.6931}. \end{gathered}$$ The ceiling washes out in the limit since $M$ grows like $10^k\ln 2$. (The official extra-credit value is paywalled; this is my own.)

The computation

For each $p=10^{-k}$, find the median straight from the distribution: binary-search the smallest $n$ whose survival $(1-p)^n$ drops to $\tfrac12$. The ratio $M/10^k$ marches to $\ln 2$.

def median_geom(p):
    hi = 1
    while (1 - p)**hi > 0.5: hi *= 2          # bracket the crossing
    lo = 1
    while lo < hi:
        mid = (lo + hi) // 2
        if (1 - p)**mid <= 0.5: hi = mid
        else: lo = mid + 1
    return lo
for k in range(1, 8):
    M = median_geom(10.0**-k)
    print(k, M, round(M / 10**k, 4))          # -> 0.6931 = ln 2