Intereting Posts

Given two randomly chosen natural numbers, what is the probability that the second is greater than the first?
inverse of diagonal plus sum of rank one matrices
Fourier Series $\sin(\sin(x))$
Relative compactness of metric space
Every Submodule of a Free Module is Isomorphic to a Direct Sum of Ideals
“Well defined” function – What does it mean?
Why is the graph of a continuous function to a Hausdorff space closed?
Hard Definite integral involving the Zeta function
prove the divergence of cauchy product of convergent series $a_{n}:=b_{n}:=\dfrac{(-1)^n}{\sqrt{n+1}}$
Help with a proof. Countable sets.
Matrix for rotation around a vector
$\sum_{i=0}^m \binom{m-i}{j}\binom{n+i}{k} =\binom{m + n + 1}{j+k+1}$ Combinatorial proof
Let $\alpha,\beta$ be the distinct positive roots of the equation $\tan x=2x$,then find $\int_{0}^{1}\sin \alpha x \sin \beta x$dx
Proofs involving $ (A\setminus B) \cup (A \cap B)$
Manifold diffeomorphic to $\mathbb{S}^1\times\mathbb{R}$.

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?

- Approximating $\pi$ using Monte Carlo integration
- Monte Carlo double integral over a non-rectangular region (Matlab)
- Why Monte Carlo integration is not affected by curse of dimensionality?
- Expected Value and Variance of Monte Carlo Estimate of $\int_{0}^{1}e^{-x}dx$
- Why does Monte-Carlo integration work better than naive numerical integration in high dimensions?
- Probability that a stick randomly broken in two places can form a triangle

- Using multivariate hypergeometric distribution to compute probability of multiple events
- Finding UMVUE of $p^s$ in Bernoulli distribution
- Convolution of continuous and discrete distributions
- Probability that the student can solve 5 of 7 problems on the exam
- convergence of entropy and sigma-fields
- Why is the probability of a continuous variable taking a particular value zero? Explain only logically
- Baseball betting and probablity
- Probability of rolling a die
- Probability of picking all elements in a set
- Making 400k random choices from 400k samples seems to always end up with 63% distinct choices, why?

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.

- Prove that $a^3+b^3+c^3 \geq a^2b+b^2c+c^2a$
- How can I find out if a non-convergent series is “indeterminate” (that is, “oscillating”) or “divergent”?
- Fixed sum of combinations
- Green's Function ODE
- How do I start from a 10% discount and find the original price?
- Proving two lines trisects a line
- Why is this $0 = 1$ proof wrong?
- Part of simple proof of nontrivial center in p-group
- Probability describing how many adjacent hexagons overlap a circle of a given radius
- Closed Bounded but not compact Subset of a Normed Vector Space
- The field of Laurent series over $\mathbb{C}$ is quasi-finite
- How do I show that the integral of $e^{inx}$ over a set of measure $1$ is nonzero for some nonzero $n$?
- Is the empty set a power set?
- Why does the graph of $e^{1/z}$ look like a dipole?
- Hint on a limit that involves the Hurwitz Zeta function