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....
user avatar
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 ...
user avatar
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....
user avatar
  • 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 ...
user avatar
  • 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 "...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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: ...
user avatar
  • 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 $\...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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. ...
user avatar
  • 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$ ...
user avatar
  • 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 ...
user avatar
  • 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^{-...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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, ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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....
user avatar
  • 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, ...
user avatar
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 (...
user avatar
  • 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 ...
user avatar
  • 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,...
user avatar

Only top scored, non community-wiki answers of a minimum length are eligible