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[30][30]
where 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 x
in [0,1) for each (i,j) couple. I use this number x and the probability p[i][j]
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 N tests.
And then I divide this number by the number 900*N.
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
the matrix 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 330.7xxxxxxx
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.


marked as duplicate by whuber Dec 18 '17 at 18:05

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ i agree with Andy W's comment after Glen's answer. You aren't answering the same question. $\endgroup$ – Mohammad Athar Dec 18 '17 at 15:34
  • $\begingroup$ @MohammadAthar Yes, but there's another comment that one can from that probability matrix compute the expected number of empty cells. $\endgroup$ – peter.petrov Dec 18 '17 at 15:57
  • $\begingroup$ My answer to the thread you reference, as well as an answer by Xi'an (who did an efficient simulation with $10^8$ iterations), anticipated and answered your questions. $\endgroup$ – whuber Dec 18 '17 at 18:05
  • $\begingroup$ @whuber Well, I don't in full understand Xi'an's answer. So I was hoping someone to write in plainer words or in other words how one can go on from the point where I am... But since my question is closed now I guess that won't happen. $\endgroup$ – peter.petrov Dec 18 '17 at 21:45
  • $\begingroup$ Anyway thanks I will think some more and see what I can do myself from here $\endgroup$ – peter.petrov Dec 18 '17 at 21:53