#+name: oneex:2 #+begin_exercise In the numerical example, our monkey had just three keys to hit. Adapt the code to show that \(T(0)=17602\) when the monkey has the original keyboard with 26 keys at its disposal. #+begin_solution Just change \(p=1/3\) to \(p=1/26\) in the code and run it. #+end_solution #+end_exercise Here is a related fun problem to analyze with first-step analyis. A mouse sits on one corner of a cube whose edges are made of wire. There is some chese diagonally opposite the mouse. One any corner, the mouse chooses at uniformly any edge, and moves to the next corner. When traversing an edge takes one minute, what is the expected time for the mouse to reach the cheese? [fn::We assume that the cheese does not move. A really interesting extension is to suppose that the cheese is also moving.] #+begin_exercise Show that the expected time is \(10\) minutes. #+begin_solution The mouse starts at the far side of the cheese. Thus, it takes at minimum three edges to get to the cheese.. Let the expected time to hit the cheese be given by \(T(3)\). Now the mouse takes one edge, and then it has at least two edges to travel, which takes expected time \(T(2)\). \(T(1)\) is defined similarly. A tiny bit of though shows that the times should satisfy the relations: \begin{align*} T(3) &= 1 + T(2), & T(2) &= 1 + T(1) \frac 2 3 + T(3)\frac 13, & T(1) &= 1 + T(2)\frac 23. \end{align*} Solving gives $T(1)= 7, T(2)=9, T(3) = 10$. #+end_solution #+end_exercise * Estimating hitting times with simulation <

#+begin_exercise Check the numerical results we obtained above to see that [[eq:24]] indeed is satisfied for \(mmm\). #+begin_solution Recall that \(T=27\), \(q=2/3\) and $T(0)= 39$ for \(mmm\) string. Indeed, $27 = 1 + 39\cdot 2/3 = 1+ 26$. #+end_solution #+end_exercise We next consider the \(mum\) case. #+begin_exercise For the \(mum\) sequence, explain that $T = 1+(1-2p) T(0) + p T(1) + p T(2)$, and check the numbers for the example. #+begin_solution Starting from \(mum\), when \(X_{}=m\) we move to string \(mumm\) which corresponds to state \(m\). When \(X_{}=u\), we get string \(mumu\) which is state \(mu\). Only after $X_{i} = n$ we return to \(0\). To check, note that $T=27, p = 1/3, T(0)=30, T(1)=27, T(2)=21$. Filling it in: $27=1+30/3 + 27/3 + 21/3 = 1 + 10+9+7$. #+end_solution #+end_exercise And now it is time to reconcile all the above. #+begin_exercise Explain why stopping to throw a die as soon as a winning pattern emerges does not necessarily lead to equal winning chances? #+begin_solution The pattern \(mum\) has more potential to build up from previous outcomes. Therefore it can appear sooner. However, once we have seen \(mmm\), it can appear within one extra throw again, while \(mum\) can never recur after one key stroke. These two effects balance out for \(mum\) and \(mmm\), so that \(T=27\) for both sequences. #+end_solution #+end_exercise Now we know this, we also understand why the children need not have the same winning probabilities if we use hitting times of different types of outcomes (compare $(1,6)$ to $(1,1)$ for example) to determine which child should win the cookie. * Summary By studying the above toy problem we covered many nice and useful ideas. With the typing monkey, we observed the subtle fact that the expected time to first hit a pattern need not be equal to the average time between such a pattern occuring in the long run. The model and methods of this section can be formulated in terms Markov chains, which form a very useful and powerful framework to analyze probability problems.