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(1−p)d−1,
So for any d>0, the probability of D≤d is equal to P[Dp≤d]=d∑m=1P[Dp=m]=d∑m=1p(1−p)m−1=p⋅1−(1−p)d1−(1−p)=1−(1−p)d.
Therefore, if p=0.01, then we get M0.01=⌈−ln20.99⌉=⌈68.9675639365…⌉=69
Though the note said to explicitly ignore the expectation, we see that Ep=E[Dp]=∞∑m=1mP[Dp=m]=∞∑m=1mp(1−p)m−1=p∞∑m=1m(1−p)m−1=p[ddt(11−t)|t=1−p=p[1(1−t)2|t=1−p=p1(1−(1−p))2=p1p2=1p.
The Extra Credit question looks at the limit of Mp/Ep=pMp as p↓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 limp→0pMp=limp→0p⋅−ln2ln(1−p)=limp→0pln2−ln(1−p)=limp→0ln21−p=ln2,
No comments:
Post a Comment