Recall that \begin{align*} \mathbb{P}(\text{Falling in} | p) &= \sum_{n=0}^{\infty} F_n \\ &= \sum_{n=0}^{\infty} \frac{2n!}{n!(n+1)!}\cdot p\big(p(1-p)\big)^n \end{align*} where \(n=0\) corresponds with falling in on the first step and \(p\) is the probability of taking a step toward the pool. Now, suppose that this series converges (see the Proof via Calculus tab for a proof of convergence). lets try to estimate what it converges to. Consider the truncated series of the first 6 terms of \(F_n\): \begin{align*} \mathbb{P}\left(\text{Falling in} | p=\frac{1}{3}\right) &\approx \sum_{n=0}^{5} \frac{2n!}{n!(n+1)!}\cdot \left(\frac{1}{3}\right)\left(\frac{1}{3}\left(1-\frac{1}{3}\right)\right)^n \\ &\approx \sum_{n=0}^{5} \frac{2n!}{n!(n+1)!}\cdot \frac{2^n}{3^{2n+1}} \\ &\approx \frac{(2\cdot0)!}{(0)!((0)+1)!}\cdot \frac{2^0}{3^{2(0)+1}} + \frac{(2\cdot1)!}{(1)!((1)+1)!}\cdot \frac{2^1}{3^{2(1)+1}} + \frac{(2\cdot2)!}{(2)!((2)+1)!}\cdot \frac{2^2}{3^{2(2)+1}} + \\ &\quad\frac{(2\cdot3)!}{(3)!((3)+1)!}\cdot \frac{2^3}{3^{2(3)+1}} + \frac{(2\cdot4)!}{(4)!((4)+1)!}\cdot \frac{2^4}{3^{2(4)+1}} + \frac{(2\cdot5)!}{(5)!((5)+1)!}\cdot \frac{2^5}{3^{2(5)+1}} \\ &\approx 1\cdot \frac{1}{3} + 1\cdot\frac{2}{27} + 2\cdot\frac{4}{243} + 5\cdot\frac{8}{2187} + 14\cdot\frac{16}{19,683} + 42\cdot\frac{32}{177,147}\\ &\approx \frac{28,201}{59,049}\\ &\approx 0.47759 \end{align*} To get a better idea of the convergence, we take take additional terms in the partial sum to give us the following results: \begin{align*} \sum_{n=0}^{10} F_n &\approx 49.333290 \% & \sum_{n=0}^{20} F_n &\approx 49.902007 \% \\ \sum_{n=0}^{40} F_n &\approx 49.995978 \% & \sum_{n=0}^{83} F_n &\approx 49.999990 \% \\ \end{align*} These terms appear to be relatively close to \(\frac{1}{2}\), so perhaps the series converges to 0.5? Now, we could attempt to verify this experimentally without much difficultly at all. In fact, without building the series, without discovering the impact of Catalan Numbers within this problem, we already had the tools to experiment with this situation. Use the next tab to run experiments to see if the robot indeed falls in approximately half of the time. See the third tab for Javascript code which could produce a similar experiment.
Experimenting with the Perilous Pool
Instructions: This applet will help you to better understand the Big question from the video introduction. We will try to answer the question "What is the total probability of falling in?"
Click on the 'Take a Random Step' button until either the robot falls into the pool or until you think the robot is far enough away that it probably won't fall in (use your best judgement, but be consistent; after all the robot could hypothetically keep taking steps forever), then press the 'Reset Robot' button to update the probability of falling in and to reset the position of the robot. When the robot is more than 5 steps away from the pool, an arrow will appear to indicate that the robot is off-screen.
Steps away from the pool: 1
Total steps taken: 0
Estimated probability of falling in: / 0 total games =
Steps Taken:
function repeat1000000() {
var prob = 1/3;
var stepcount = 1;
var lostgames = 0;
var totalgames = 0;
while(totalgames < 1000000){
if(Math.random() < prob){// Step left
stepcount--;
if (stepcount == 0) {
lostgames++;
totalgames++;
stepcount = 1;
}
} else {// Step right
stepcount++;
if (stepcount >= 83) {
totalgames++;
stepcount = 1;
}
}
}
console.log(round((lostgames / totalgames) *100,6) + '%');
}
function round(value, decimals) {
return Number(Math.round(value+'e'+decimals)+'e-'+decimals);
}
For some final commentary, it is worth constructing a confidence interval around the proportion of \(\frac{1}{2}\) to get an idea of what kinds of results we would expect to see. If we wanted to construct a Confidence interval such that only 1 in 30 results would typically be outside of the interval, then constructing a 97% confidence interval will do the job. Therefore \(z=2.17\), and with a sample size of 1 million the confidence interval is: \begin{align*} \bar{x}\pm z \cdot s_x &= p \pm 2.17 \cdot\sqrt{ \frac{p(1-p)}{n}}\\ &= 0.5\pm 2.17 \cdot\sqrt{ \frac{0.25}{1,000,000}}\\ &= 0.5\pm 0.001085 \end{align*} Which gives us an anticipated 97% Confidence Interval of \[ (49.8915\%, 50.1085\%) \]