# Monte-Carlo simulation with sampling from uniform distribution

I used to work with Monte-Carlo simulations for a while. In my case, I generated random data for a variety of input parameters according to uniform distributions (with non-negative support), say for example two variables $a$ and $b$ where data is generated: $a_1, \dots, a_n \leftarrow U(1,2)$ and $b_1, \dots, b_n \leftarrow U(4,5)$.

Eventually, I evaluated a deterministic model $M$ for all generated pairs $(a_i,b_i)$ and calculate some statistics, like sample average of $\frac{M(a_1,b_1) + \dots + M(a_n,b_n)}{n}$.

Here is my question: What is the purpose of drawing random samples from the uniform distribution, rather than deterministically select $n$ equally distributed point from the interval $[1,2]$ and $[4,5]$ respectively and simply evaluate $M$ with those points? So, what would be the purpose of doing this stochastically rather than deterministically?

#### Solutions Collecting From Web of "Monte-Carlo simulation with sampling from uniform distribution"

This is actually a big open question in Computational Complexity.

There are (among many others) two big classes of problems called P and BPP. Without going into too much detail, P includes all the problems which can be efficiently solved deterministically, while BPP includes those which can be solved efficiently using a source of randomness with a small random error (which can be exponentially minimized by repetition).

Now, it is easy to see that $P\subset BPP$, since deterministic algorithms are a special kind of random algorithms in which we make no use of the randomness whatsoever.

It intuitively seems like the randomization helps us compute some things faster. For example, you can quickly test for primality using randomness.

However, most researchers believe that actually $P=BPP$; that is, that every problem which can be efficiently solved using a probabilistic algorithm can also be efficiently solved by a deterministic one. Indeed, for primality testing this was shown to be the case (see AKS algorithm). The studies of derandomization are many and promising, though the question is still open.

Things are taken to a new level in the context of what are called interactive proofs. To be concise, an interactive proof is a procedure by which you can verify the proof of an answer to a problem. If the verifier is restricted to be deterministic (that is called dIP class) it turns out that it haves significantly less power that if it is allowed to use randomness, incurring in a small probabilistic error (the class IP).

One example of a problem with a probabilistic verifier but which we do not know whether there is a deterministic one is Graph Nonisomorphism (GNI).

The interactive procedure for GNI is actually quite simple. Imagine we are given two graphs and you want to prove me that they are not isomorphic. Then I can randomly choose one of the graphs and do a random permutation of one (all of this in secret), and then ask you from which graph it came. If they are truly non-isomorphic, then you being all powerful will be able to tell me the answer, while if they are isomorphic then nobody can say with better than 50% chance from which graph did it came. It could have been either!

It feels like I’ve drifted off too much from your original question, so let’s consider another scenario which is closer to what you expose: verifying very long proofs.

This is another example of a kind of problems we can verify probabilistically but not deterministically. Oversimplifying, imagine you are given a very long proof and you want to check whether it is true. Then it is possible to show that the question is in a special form, and only check some parts of it. If the parts you check are sound, you can conclude with high probability that the proof is correct. Thus we can potentially with $n$ checks verify a proof with $2^n$ steps. However, if we knew in advance which steps were going to be checked then we could make a fake proof in which only those steps are sound, defeating the purpose of the verification. For more on this topic, search for the class PCP.