6
votes
Accepted
What is the difference between Simulated Annealing and Monte-Carlo Simulations?
Monte Carlo simulation is a method for computing a function. Simulated annealing is an optimization heuristic. Other than that, the only common thread behind these two methods is the use of randomness....
- 270k
6
votes
Accepted
Is there some kind of expected error margin for my Monte Carlo algorithm?
Suppose that you are trying to estimate some quantity $\mu$ by performing some random experiment $X$ with mean $\mu$ and variance $\sigma^2$. In order to obtain a better estimate, you can repeat the ...
- 270k
5
votes
Accepted
Generating values from a probability density function
You can integrate the PDF to a CDF F(x), then uniformly generate a random number x between 0 and 1 and choose a y such that F(y)=x as your sample. This is more or less difficult, depending on your PDF....
- 5,910
5
votes
Accepted
Approximate Bayesian Computation VS Monte Carlo Simulation
Yes, ABC is a specific application of Monte Carlo method. That application is approximating likelihood functions.
Anything that happens in a computer is actually deterministic. However, ABC, like any ...
- 608
5
votes
Accepted
Do RP algorithms exist?
The algorithms you are looking for are also called one-sided-error Monte Carlo algorithms.
The idea is to randomly guess a witness for the input being a YES-instance. If you find one, your answer "...
- 71.1k
5
votes
Accepted
UCT1 Algorithm: What does "total number of simulations" mean?
The UCT1 algorithm is actually an algorithm for a multi-armed bandit. There is a machine with several arms. At each round you pull one of the arms and get some reward. Your goal is to maximize your ...
- 270k
4
votes
How can we get a Las Vegas algorithm from a Monte Carlo one?
First, the algorithm should run forever; since you are going to stop when you have a correct answer. By this way you can guarantee that you never outputs a wrong answer. So, probability of error is ...
- 289
3
votes
Accepted
How does MCTS handle games with large numbers of poor moves?
Issues like these are essentially solved in the MCTS itself. The principle of the algorithm is that it tries to make the best pick, rather than guaranteeing it (if done in this randomized fashion ...
- 322
3
votes
How to find the best exploration parameter in a Monte Carlo tree search?
The value of $C = \sqrt 2$ was shown to ensure the asymptotic optimality when rewards are in the $[0,1]$ range (Kocsis, Szepesvári, 2006).
In many games, that reward range is straightforward: ...
- 1,937
3
votes
Pi approximation with Montecarlo: Why not just evenly distributed points?
Let us compare the efficiency of both methods. The first method generates random points on the unit square $[-1,1]^2$, and checks how many of them lie inside the unit circle – the fraction should be $\...
- 270k
3
votes
How do you protect an AI from a human doing "illogical" moves?
In principle, the problem of building an AI where this can never happen seems equivalent to the problem of building an AI that plays perfectly.
More precisely: If the AI can perfectly evaluate the ...
D.W.♦
- 143k
3
votes
Accepted
What is an example of a Monte-Carlo algorithm for finding a Hamiltonian path?
There are several such algorithms for various graph problems; for Hamiltonian path one example is due to Björklund [1]. These algorithms are often algebraic and the "random element" stems from the ...
- 22.1k
3
votes
Accepted
What is the optimal algorithm for playing the hangman word game?
It is possible to compute the optimal strategy, but the computation might be fairly intensive, and I'm not sure whether it will give you much of a gain over simple heuristics. I'll explain how below. ...
D.W.♦
- 143k
3
votes
Describe a Monte Carlo algorithm for the Triangle Packing problem
Although I agree with Yuval, I'll try to get you started on the connection to their longest path approach. The goal is, given a graph $G$, to define a polynomial $P_G$ which is nonzero iff $G$ has $k$ ...
- 13.2k
3
votes
Uniformly sample $x,y\in\{0,1\}^n$ with Levenstein distance $k$
There are two considerations: running time, and correctness.
Running time: When $k < (n-1)/\lg(4n)$, heuristically I expect the running time of your algorithm to be fine and I'd guess you won't ...
D.W.♦
- 143k
3
votes
Accepted
Question about what exponentially small probability of success means in randomized algorithms
A quantity is exponentially small (with respect to parameter $n$) if it is $\Omega(\alpha^n)$ and $O(\beta^n)$ for some $\alpha,\beta \in (0,1)$.
A quantity is polynomially small if it is $\Omega(n^{-...
- 270k
2
votes
Accepted
Minimizing total distance to a point from a set of points
It's a two-dimensional facility location problem. In this case, the optimum location is the centre of gravity (also known as the barycentre or centroid) of the locations of the houses, which is easily ...
- 80.4k
2
votes
Accepted
What is a proper way of solving a multibody nonlinear problem?
OK, I finally fixed this issue, the right thing to do in such non-linear situation is to use simulated annealing. I am implementing a gradient guided simulated annealing, which works pretty ...
- 41
2
votes
Monte Carlo: what is a seed?
The seed is an initial number of the pseudorandom number generator(PRNG) which is in fact fully deterministic. It returns a sequence of numbers that looks random enough for many purposes, but always ...
- 9,325
2
votes
Accepted
Monte Carlo algorithm: Element in array
It doesn't matter what other elements are. We can assume that $k$ elements in $V$ are equal to $x$. Then the probability for a correct answer would be $k/n$ and $1-k/n$ for an incorrect answer. Then ...
- 81
2
votes
What is the difference between Simulated Annealing and Monte-Carlo Simulations?
Simulated Annealing is closely related to Markov-Chain Montecarlo, and the Metropolis algorithm. The main difference is that MCMC aims to generate samples that respect and underlying distribution, ...
- 21
2
votes
Accepted
How to estimate how many assignments satisfy a given DNF formula using Monte Carlo?
Let $\alpha$ be a satisfying assignment. Suppose that it satisfies the terms $\{C_j : j \in J\}$. If you choose $C_i$ in the first step, then the probability that you choose $\alpha$ in the third step ...
- 270k
2
votes
Generate a random magic square on a large field
Here's a decent algorithm that will quickly generate large magic squares.
First Step: Establish Rows
1. Put all numbers in a bucket.
2. Loop through the rows, 0 to n.
3. Take out n (where n is the ...
- 21
2
votes
Accepted
Monte Carlo Algorithms : Are there any problems where two opposite Monte Carlo algorithms could solve it?
A Las Vegas algorithm is one which is always correct, but is only efficient in expectation. Given two "opposite" Monte Carlo algorithm, you can create a Las Vegas algorithm by alternating both ...
- 270k
2
votes
Accepted
Pandemic board game - find all possible next 4 actions
Without more details, I think it is important to precise that Pandemic is 2-4 players cooperative game. Players are allowed to discuss about strategy and share any information (even if the rules are ...
- 1,730
2
votes
UCT (Upper Confidence bounds applied to Trees)
This result is stated in:
Kocsis, L., & Szepesvári, C. (2006, September). Bandit based monte-carlo planning. In European conference on machine learning (pp. 282-293). Springer, Berlin, Heidelberg....
- 620
2
votes
Describe a Monte Carlo algorithm for the Triangle Packing problem
Koutis gives an $O^*(2^{3k})$ algorithm for the more general problem of $3$-set $k$-packing in his paper Faster algebraic algorithms for path and packing problems. This was improved by Björklund, ...
- 270k
1
vote
Pandemic board game - find all possible next 4 actions
You didn't explain how your solution today works, so it's hard to give any concrete pointers. But more generally, in a Monte Carlo solution, you'll take random steps all the way to a terminal state (...
- 111
1
vote
How to find the best exploration parameter in a Monte Carlo tree search?
You can go with whatever the literature recommends is a reasonable value without knowing any specifics of your problem. Otherwise, it is perfectly possible (and even to be expected) that a good value ...
- 22.1k
1
vote
Accepted
How to decrease the confidence of a Monte Carlo algorithm in its answer?
You can compute the probability that outcome $e$ is the unique plurality answer, when repeating the algorithm $k$ times, as follows:
$$
\sum_{\substack{a+b+c+d+e=k \\ a,b,c,d,e \geq 0 \\ e > a,b,c,...
- 270k
Only top scored, non community-wiki answers of a minimum length are eligible