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?

  • $\begingroup$ Whatever deterministic points you select in advance, your system $M$ might behave "uncharacteristically" specifically in those points (think large, thin spikes). If, however,$M$ has a smooth response to its parameters, because you have only 2-D space, deterministic quadratures could be more efficient. $\endgroup$ – A.S. Feb 2 '16 at 19:32
  • $\begingroup$ Interesting point. Referring to your fact $M$ might behave "uncharacteristically" in the selected points: I guess $M$ might behave uncharacteristically in either case. In the sense, what would be the difference between having 10,000 random samples according to a uniform distribution or simply having 10,000 equally distributed deterministic points? In any case, once, the 10,000 points/samples are fixed, it is always just one fix perspective (while at all other points it might be look totally different)? Do you get my point? Does that question make sense to you? Thank you very much! $\endgroup$ – Frank Merzen Feb 2 '16 at 19:44
  • $\begingroup$ But Monte Carlo samples are random (while the system is fixed), so the chances that you only sample at a small "uncharacteristic" range is small. For a fixed $M$, a deterministic algorithm will always produce the same result - possibly wildely inaccurate. A Monte Carlo algorithm will produce a different result each time - all of which are likely be close to "truth". $\endgroup$ – A.S. Feb 2 '16 at 19:52
  • $\begingroup$ Mmmm.. but at the end, what I do in practice is, I evaluate $M$ with 10,000 randomly drawn samples. But, I do this only once. So, does it make a difference in practice? Somehow, my point is that I don't see the difference between evaluating $M$ with 10,000 random points or 10,000 deterministic point given the fact that I do all this only once. At the end, I only look at 10,000 points and thats it. I apologize for the confusion I cause. $\endgroup$ – Frank Merzen Feb 2 '16 at 20:00
  • $\begingroup$ Suppose you have to play Russian roullette only once and the revolver is loaded with one bullet by your opponent. Would you 1. Pull the trigger right away. 2. Deterministically select the number of clicks you'll rotate the cylinder (your opponent has abilities to predict your deterministic choices correctly) 3. Spin the cylinder vigorously making opponent's deterministic prediction abilities moot? $\endgroup$ – A.S. Feb 2 '16 at 20:08

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.

Hope this answers your doubts. Feel free to ask for clarifications on whatever you want.

  • $\begingroup$ My impression is that the deterministic version of a probabilistic algorithm often involves substantially rewriting the algorithm. I doubt that in general, if you have a Monte Carlo algorithm with input parameter in the range $[0,5]$, the deterministic version of the algorithm is simply to do one "run" for each value in the finite set $\{5, 5+\frac{5}{n}, 5+\frac{10}{n}, 5+\frac{15}{n}, \dots, 10\}$ for some $n$. $\endgroup$ – David K Feb 3 '16 at 20:18
  • $\begingroup$ @DavidK Yep, that is correct. $\endgroup$ – Jsevillamol Feb 3 '16 at 20:24
  • $\begingroup$ Thank you a lot! I understand your points. But referring to the interesting example of the long proof: Suppose, nobody wants to cheat in the entire setting. Why would it not simply be fine to deterministically say, we check the long proof at point $x$, $y$, and $z$, rather than drawing three "random" points? In any case, I only get an answer for $3$ points. But, I will think about it again more carefully. Thanks again! $\endgroup$ – Frank Merzen Feb 3 '16 at 21:04
  • $\begingroup$ It is an interesting point. If we did change the points each times we ran the algorithm, then it would be equivalent to randomly picking the points. If we did not, then our algorithm would be systematically biased toward some results, which is something we clearly do not want. $\endgroup$ – Jsevillamol Feb 3 '16 at 21:26
  • $\begingroup$ Returning to the 'long proofs' settings, it could turn out that there are two ways of doing the same proof, where in one the difficult steps are the 1,5 and 10, and in other the difficult steps are 2, 3 and 4. Then if we only checked 1,5, 10 we would be biased into accepting more wrong answers which try to follow the second procedure. $\endgroup$ – Jsevillamol Feb 3 '16 at 21:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.