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)?
Let's abstract to using a generic probability of accidentally tipping all of the dominoes over at $p\gt 0.$ Let $D_p$ be the random number representing the total number of dominoes (including the domino that you originally tip over) when the probability of accidentally tipping the dominoes over for any individual domino is $p \gt 0$, then we have $$\mathbb{P} \left[ D_p = d \right] = p (1-p)^{d-1},$$ since in order for you to tip over the $d$th domino you must first not have knocked over the first $(d-1)$ dominoes, each with a probability of $(1-p),$ and then knock over the $d$th domino, with probability $p.$
So for any $d \gt 0,$ the probability of $D \leq d$ is equal to $$\mathbb{P} \left[ D_p \leq d \right] = \sum_{m=1}^{d} \mathbb{P} \left[ D_p = m \right] = \sum_{m=1}^d p(1-p)^{m-1} = p \cdot \frac{1 - (1-p)^d}{1-(1-p)} = 1 - (1-p)^d.$$ Alternatively, we have $$\mathbb{P} \left[ D_p \gt d \right] = 1 - \mathbb{P} \left[ D_p \leq d \right] = (1-p)^d.$$ The integer $M_p$ is the median of the distribution of $D_p$ if and only if we have $$\mathbb{P} \left[ D_p \leq M_p \right] = 1 - (1 - p)^{M_p} \geq \frac{1}{2}$$ and $$\mathbb{P} \left[ D_p \geq M_p \right] = \mathbb{P} \left[ D_p \gt M_p \right] + \mathbb{P} \left[ D_p = M_p \right] = (1-p)^{M_p-1} \geq \frac{1}{2}.$$ Therefore, combining these two equations we need $$(1-p)^{M_p} \leq \frac{1}{2} \lt (1-p)^{M_p - 1}.$$ Taking natural logarithms of all sides we get $$M_p \ln (1-p) \leq -\ln 2 \lt (M_p - 1) \ln(1-p),$$ or equivalently $$M_p - 1 \lt -\frac{\ln 2}{\ln (1-p)} \leq M_p,$$ or equivalently $$M_p = \Big\lceil -\frac{\ln 2}{\ln (1-p)} \Big\rceil.$$
Therefore, if $p = 0.01,$ then we get $$M_{0.01} = \Big\lceil -\frac{\ln 2}{0.99} \Big\rceil = \lceil 68.9675639365\dots \rceil = 69$$ is the median number of dominoes that you will have placed when they all get knocked down. For further confirmation we see we get $$\mathbb{P} \left[ D_p \leq 68 \right] = 0.495114111213 \lt \frac{1}{2} \lt \mathbb{P} \left[ D_p \leq 69 \right] = 0.500162970101.$$
Though the note said to explicitly ignore the expectation, we see that \begin{align*}E_p = \mathbb{E} \left[ D_p \right] &= \sum_{m=1}^\infty m \mathbb{P} \left[ D_p = m \right]\\ &= \sum_{m=1}^\infty m p (1-p)^{m-1} \\ &= p \sum_{m=1}^\infty m (1-p)^{m-1} \\ &= p \left[ \frac{d}{dt} \left( \frac{1}{1-t} \right) \right|_{t=1-p} \\ &= p \left[ \frac{1}{(1-t)^2} \right|_{t = 1-p} \\ &= p \frac{1}{(1 - (1-p))^2} = p \frac{1}{p^2} = \frac{1}{p}.\end{align*} In particular, we see that for the Classic question, we have $E_{0.01} = 100 \gt M_{0.01} = 69.$
The Extra Credit question looks at the limit of $M_p / E_p = p M_p$ as $p \downarrow 0.$ Given the formulae above, we see that the limit of the ratio of the median to the average number of dominos placed is given by $$\lim_{p \to 0} p M_p = \lim_{p \to 0} p \cdot - \frac{\ln 2}{\ln ( 1- p) } = \lim_{p \to 0} \frac{ p\ln 2}{ - \ln (1-p) } = \lim_{p \to 0} \frac{ \ln 2 }{1 - p} = \ln 2,$$ where the first equal sign comes from the squeeze theorem and the second to last equal sign is an application of L'Hôpital's Rule. So not only do we have $M_p \lt E_p$ in the case of $p = 0.01,$ but for all small $p \approx 0.$
No comments:
Post a Comment