This question already has an answer here:
This question is a continuation of
How should one approch Project Euler problem 213 ("Flea Circus")?
I followed the approach of Glen_b outlined in his
answer in the page referenced above. I am using Java.
So now I am at a point where I think I have correctly calculated the probabilities
p[i][j] denotes the probability of the
(i,j) square being empty after these 50 steps
(1 step = 1 ring bell) from the problem statement.
Now I am treating these 900 numbers from the
p array as describing 900 random variables.
So I start doing a Monte Carlo simulation.
For now I am doing
N = 60 000 000 such tests/experiments.
In a single experiment I loop through the
p array, and I generate one random number
[0,1) for each
(i,j) couple. I use this number
x and the probability
to generate a boolean value
0/1 which says if the square is empty or not.
Then I count how many empty squares I got in all my
And then I divide this number by the number
This should give me the Monte-Carlo approximated answer.
But my problem is that I think I am too far away from the precision that is needed.
Why? Because I then run another
N such experiments.
And the answers I get in the 1st set of
N experiments compared to the
answer in the 2nd set of
N experiments differ by way too much
(they differ in the 4th or even in the 3rd sign after the decimal dot).
I wonder why. Aren't 60 million tests good/many enough?
If not (i.e. if I need more experiments), and if I am so far away as it seems then...
How can I finish solving this problem in reasonable runtime, given that I have already
p with the probabilities.
Or maybe... I am not doing the Monte-Carlo simulation quite right
( though I doubt that because I am getting already some answers like
so I am obviously on the right track i.e. I do not have any major logical bugs).
I am not sure.
Any help/guidance (about how to finish the solution from here) would be much appreciated.