Loading [MathJax]/jax/output/HTML-CSS/jax.js

Sunday, March 9, 2025

Well below average domino placement

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>0. Let Dp 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>0, then we have P[Dp=d]=p(1p)d1, since in order for you to tip over the dth domino you must first not have knocked over the first (d1) dominoes, each with a probability of (1p), and then knock over the dth domino, with probability p.

So for any d>0, the probability of Dd is equal to P[Dpd]=dm=1P[Dp=m]=dm=1p(1p)m1=p1(1p)d1(1p)=1(1p)d. Alternatively, we have P[Dp>d]=1P[Dpd]=(1p)d. The integer Mp is the median of the distribution of Dp if and only if we have P[DpMp]=1(1p)Mp12 and P[DpMp]=P[Dp>Mp]+P[Dp=Mp]=(1p)Mp112. Therefore, combining these two equations we need (1p)Mp12<(1p)Mp1. Taking natural logarithms of all sides we get Mpln(1p)ln2<(Mp1)ln(1p), or equivalently Mp1<ln2ln(1p)Mp, or equivalently Mp=ln2ln(1p).

Therefore, if p=0.01, then we get M0.01=ln20.99=68.9675639365=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 P[Dp68]=0.495114111213<12<P[Dp69]=0.500162970101.

Though the note said to explicitly ignore the expectation, we see that Ep=E[Dp]=m=1mP[Dp=m]=m=1mp(1p)m1=pm=1m(1p)m1=p[ddt(11t)|t=1p=p[1(1t)2|t=1p=p1(1(1p))2=p1p2=1p. In particular, we see that for the Classic question, we have E0.01=100>M0.01=69.

The Extra Credit question looks at the limit of Mp/Ep=pMp as p0. 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 limp0pMp=limp0pln2ln(1p)=limp0pln2ln(1p)=limp0ln21p=ln2, 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 Mp<Ep in the case of p=0.01, but for all small p0.

No comments:

Post a Comment