The monkey typewriter revisited
by Mithrandir
In the previous article I presented a strange problem, dubbed the MT problem (the Monkey typewriter). This time we will deal with the same problem but from another point of view: the results obtained by Monte Carlo simulation.I will post here the two source files needed for simulating both cases and then I will give some results.
For the first case, we have the following C code:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define NUM_SIMS 1000
int full(char *keys, int n){
int i;
for (i = 0; i < n; i++)
if (!keys[i])
return 0;
return 1;
}
int main(int argc, char** argv){
int n, sim;
unsigned long long t = 0ll; //the time counter
float T; //the average time
char *keys; //the keys
srand(time(NULL));
sscanf(argv[1], "%d", &n);
for (sim = 0; sim < NUM_SIMS; sim++){
keys = (char*) calloc(n, sizeof(char));
while (!full(keys, n)){
keys[rand() % n] = 1; //new keystroke
t++;
}
free(keys);
}
T = (float)t / NUM_SIMS;
printf("%f\n", T);
return 0;
}
For the second case, the one when an odd number of the same key presses is required, I used the previous code where I have changed only one line (26) as in:
keys[fallplace] = !keys[fallplace]; //new keystroke
The results are as follows:
| Number of keys | First case | Second case |
|---|---|---|
| 1 | 1.00 | 1.00 |
| 2 | 2.96 | 3.99 |
| 3 | 5.47 | 10.1 |
| 4 | 8.52 | 21.03 |
| 5 | 11.4 | 42.2 |
| 6 | 14.7 | 82.6 |
| 7 | 18.1 | 156 |
| 8 | 21.9 | 310 |
| 9 | 25.6 | 606 |
| 10 | 29.4 | 1.19e3 |
| 11 | 33.4 | 2.27e3 |
| 12 | 37.6 | 4.75e3 |
| 13 | 41.8 | 9.24e3 |
| 14 | 46.8 | 18.3e3 |
| 15 | 49.8 | 35.9e3 |
| 16 | 54.4 | 72.5e3 |
| 17 | 58.2 | 146e3 |
| 18 | 63.5 | 282e3 |
| 19 | 67.3 | 547e3 |
| 20 | 72.6 | 1.13e6 |
As you can see, in both cases, the simulations were accordingly to the theoretical answers obtained in the previous instalment of this problem. I will insert here some plots of the relative error between the simulated and the calculated times (see the previous post for the exact computation of the average times).
For the first case, we have the following difference.
As you can see, the maximum error was lower than 3%. However, in the second case the Monte Carlo method used provided a bigger error (lower than 4% as proved by the following plot).
It is easy to see that the second case, that where we are interested in an odd number of key presses, is the most difficult one. We have to wait a longer time, the Monte Carlo simulations are providing greater errors and so on. However, there was no reason to make a big difference between the two cases until now. For both simulations we used the same numbers of iterations (1000). But we need more steps in the second case if we want to achieve the same error between the cases. Nevertheless, as the second case takes more time, the number of iterations cannot grow indefinitely. Thus, we will need to find a way to stop the simulation at exactly the same moment where there will be no need for further runs. This moment is the moment when we will receive too few information and we are content with what he have until then. But I will let this for the third part.
