I bet all of you know the now famous theorem of the infinite monkeys. Starting from this idea someone devised the following problem:
Suppose there is a monkey sitting in front of a terminal consisting of n keys. The monkey will press any of those keys at random and, when all of them will be pressed, she will receive a banana as a payment for her efforts. We are mainly interested in how long will it take for her to obtain that banana in the following two cases:
- when a key is pressed it remains pressed
- when a key is pressed for the second time it will behave as though it was not pressed at all.
Practically, we are interested to see what is the average number of keystrokes for the specific number n of keys.
This is what we’ll be doing here. For the first part of our instalment we will use Numerical Methods to deal with the exact mathematical equation for the average number of keystrokes needed.
The second instalment of this problem will tackle with a Monte-Carlo approach to this problem and (maybe) with reducing the computational cost of Monte-Carlo methods, the main reason behind choosing this problem.
Read the rest of this entry »