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.

erorrs1

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).

erorrs2

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.

About these ads