5
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. Some PDFs have analytical solutions, others need numerical methods. For some distribution Rejection sampling works well, some distributions can be sampled ...
5
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 total reward. In this algorithm, $t$ is the round number: $t = 1$ in the first round, $t = 2$ in the second round, and so on.
When using UCT1 to perform Monte ...
5
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 other MCM, must have a good pseudo-random generator. There is no difference in the amount of randomness required by the methods.
Examples of Monte Carlo ...
5
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 "YES" is always correct; if you don't find one, you say "NO" even though the correct answer may be "YES" (we want to restrict the likelihood of this event). If the ...
4
This is the idea of probability amplification, in which one improves the probability of correctness of the algorithm by running it multiple times. You are talking about Monte-Carlo algorithms which have one-sided error. Lets take an example (from Wikipedia) having such a similar feature :
The Solovay–Strassen primality test is used to determine whether a
...
4
If you use a fixed seed then Monte Carlo is also repeatable. Monte Carlo sampling has the advantage that the expected number of points inside your figure is proportional to the area, which is not necessarily the case for a grid — you can come up with a contrived figure in which the grid is off by a lot, whereas random points are impossible to "fool" ...
4
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.
In Monte Carlo simulation, we are aiming at computing some quantity $A$ by finding an easily samplable random variable $X$ whose expectation is $A$. We ...
3
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 value of each board position, then it is also able to play perfectly even if the adversary plays imperfectly. Conversely, if there is a situation where the AI ...
3
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 $\pi/4$. If we sample $N$ points, our estimate has roughly normal distribution with mean $\pi/4$ and variance $\pi/4(1-\pi/4)/N$, and so we expect an error of ...
3
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 rather than a 'pure MCTS' fashion). The trees are built up out of large amounts of collected data, aggretating success rates in the nodes. Nodes that end up being ...
3
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 zero.
So, the algorithm should be as following:
Algorithm LA
1) for i = 1 to infinity do
2) solMC = MC(n)
3) if solMC is correct
4) return solMC
...
3
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 application of the Schwartz–Zippel lemma. Usually, the algorithms work so that the graph property we are interested in is somehow represented as a (multivariate) ...
2
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 efficiently.
Thanks for everyone who gave me suggestions and guidance to the right path!
Have fun (mixed with a lot of frustrations) with modeling!
2
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 calculated from their co-ordinates.
2
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 generates the same sequence for given value.
In order to make simulation non-repeatable (returning always the same value) they advice different initial value ...
2
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 after $m$ tries, the probability of failure would be $(1-\frac{k}{n})^m$.
And the probability of success in $m$ tries is the probability of not to be failed in ...
2
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 is 0 if $i \notin J$ and $2^{-(n-|C_j|)}$ if $i \in J$. Hence the probability of sampling $\alpha$, assuming there are $m$ terms, is
$$
p(\alpha) = \frac{2^{-n}...
2
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.
It is the content of Theorems 5 & 6. Sadly there is no detailed proof for theorem 5.
The main reference for this is:
Auer, P., Cesa-Bianchi, N., & ...
2
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: maximum and minimum possible scores can be translated to 0 and 1 (0 could mean a loss and 1 a win).
The accuracy of this squashing seems to have a minimal impact (...
2
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 algorithms (or running them in parallel), halting whenever one of them produces a certain answer.
In the language of complexity theory, this corresponds to the ...
2
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 ambigous on the possibility to share card in hand information). Moreover to achieve victory efficiently, players have to trade cards which is hard without ...
2
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. The main idea is to use dynamic programming.
Deterministic strategies
Let me start first with the special case of deterministic strategies for choosing which ...
1
Using barycentric coordinate and keeping sum of coordinate equal to 1 do not sample a convex polytope uniformly.
import numpy as np
import matplotlib.pyplot as plt
N = 1000000 # Number of samples
V = 5 # Generate points within a V-gon
# generate columns that each sum to 1
s = np.exp(-np.random.uniform(0, 1, size=(V, N)))
s /= s.sum(axis=0)
# generate ...
1
The highlighted line basically says that time $t$ must be the first occurrence of the pair $(S_t, A_t)$ in the complete trajectory from $0$ up to and including $t$. This is why there is "first-visit" in the name of the algorithm; it only runs updates for $(S_t, A_t)$ pairs if $t$ is the first occurrence (first "visit") of a particular state-action pair in a ...
1
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 of $C$ will depend not only on your problem, but on the details of your instances.
In general with all (meta)heuristics, a good choice of parameters comes down ...
1
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,d}} \frac{n!}{a!b!c!d!e!} \left(\frac{1}{4}\right)^e \left(\frac{3}{16}\right)^{k-e}.
$$
This can be computed explicitly. When $k = 70$, the probability is ...
1
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 size of row) numbers randomly from the bucket.
4. Sum those numbers. If they don't equal the solution sum, goto 3.
5. If they do equal the solution sum, stick ...
1
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, while SA aims to find the maximum of a function. The similarity is that in both cases you want to visit the parts of the function that have the high values with ...
1
Partial expansion is a pruning/reduction strategy. Instead of requiring all children to be explored in selection you could set a threshold like done in "Move Count Pruning" (MCP) based on only expanding the first 10 children only. Usually you call ucb_sample if all children are explored depending on your weights.
Another example could be based on the ...
1
Your vector has n entries. If x is in the vector, then finding it when you pick a random index has probability at least 1/n (higher if there are multiple copies of x).
Only top voted, non community-wiki answers of a minimum length are eligible
