# Questions tagged [monte-carlo]

The tag has no usage guidance.

50 questions
Filter by
Sorted by
Tagged with
53 views

### How to design an unbounded Monte Carlo algorithm for SAT(Boolean Satisfiability Problem) problem?

I want the algorithm to be in polynomial time and the correct answer rate is 0.5 or more. (True / false judgment is polynomial time) All the methods I think of take exponential time(2^n). Can anyone ...
60 views

### Uniformly sample $x,y\in\{0,1\}^n$ with Levenstein distance $k$

Given alphabet $\{0,1\}$, we want to uniformly sample $x,y \in \{0,1\}^n$ such that $ed(x,y)=k$, where $ed$ denotes the Levenstein distance, i.e., the minimum number of edit operations (insert, delete,...
166 views

95 views

### How to decrease the confidence of a Monte Carlo algorithm in its answer?

Recall that a Monte Carlo algorithm is $p$-correct if it outputs a correct answer with probability at least $p$. In the case of decision problems, where the answer is binary, repeating the MC ...
122 views

### Monte Carlo Algorithms : Are there any problems where two opposite Monte Carlo algorithms could solve it?

I started reading on Probabilistic algorithms and Monte-Carlo algorithms. Since a Monte-Carlo can only give a certain answer for either True or False, I was wondering if it's conceivable that for the ...
42 views

### Randomly construct linear combination that is within bounds over two basis

Given rank deficient matrix $A$, I want to randomly construct vectors $\vec{x}$ such that: $0 \le x_{j} \le 1$ $0 \le b_{j} \le 1$ where $\vec{b} = A\vec{x}$ Matrix $A$ is about 10 x 15. I want to ...
377 views

### Understanding On-policy First Visit Monte Carlo Control algorithm

I am going through the Monte Carlo methods, and it's going fine until now. However, I am actually studying the On-Policy First Visit Monte Carlo control for epsilon soft policies, which allows us to ...
67 views

### Pi approximation with Montecarlo: Why not just evenly distributed points?

With the randomised algorithm for Pi approximation (see https://www.geeksforgeeks.org/estimating-value-pi-using-monte-carlo/ ), I keep wondering why just using points with an even distance should'n ...
342 views

### Generate a random magic square on a large field

If consecutive natural numbers 1 .. n^2 are placed in a n*n grid so that sum of numbers in each column and in each row is a constant then we call it a magic square. I would like to generate magic ...
76 views

### How do you protect an AI from a human doing "illogical" moves?

Using a monte carlo approach and evalutation function. Some moves will deemed to be more advantageous than others. As a computer plays itself, it will generally go for the best moves possible. And ...
2k views

### What is the difference between Simulated Annealing and Monte-Carlo Simulations?

What is the difference between Simulated Annealing and Monte-Carlo Simulations? Is Simulated Annealing a specific type of Monte-Carlo simulation, or are they completely separate techniques?
131 views

### Do Nested Monte Carlo Algorithm always find the best score where score is the number of moves on the leftmost path

I am studying Nested Monte Carlo Algorithm addressing the problem of guiding the search toward better states when there is no available heuristic. It uses nested levels of random games in order ...
406 views

### How to estimate how many assignments satisfy a given DNF formula using Monte Carlo?

Admittedly, homework. For the purpose of this question: $\phi$ is a DNF formula similar to this one: $(x_1 \wedge \neg x_3 \wedge x_4) \vee (\neg x_1 \wedge x_2)$ Also $C_i$ is a clause in this ...
332 views

### What is partial expansion in Monte Carlo Tree Search?

I'm trying to understand the modification to the MCTS algorithm called Partial Expansion. From what I've been reading it enables one to not require all child nodes to have been expanded before ...
4k views

### Monte Carlo: what is a seed?

I have reached a chapter in the notes I am following where a program written in C++ is using a Monte Carlo method to estimate $\pi$. It mentions a 'seed', but does not say what this is. I have tried ...
40 views

### Card Shuffling, Bounding Mixing time using Paths and Flows

I've been struggling with a problem that is very similar to a 2014 question posted here. The question in particular is 3(1) and 3(2). To paraphrase, we are supposed to use paths and an encoding ...
216 views

### Monte Carlo algorithm: Element in array

Design a Monte Carlo algorithm that checks in constant time if a given element $x$ is in a $n$-dimensional vector $V$. Calculate the probability for a correct answer. Then suppose $n=10$, how many ...
37 views

### Not grasping Bayesian Monte Carlo

I've read several sources of information that describe the process of Bayesian Monte Carlo Quadrature but am just not understanding the details enough to be able to implement it. For instance two ...
2k views

### Generating values from a probability density function

If I have a probability density function, some f(x) which is >= 0 everywhere and integrates to 1, is there a method to generate random numbers using that PDF? I know there is the box-muller transform ...
146 views

### Monte Carlo Tree Search in connect 5 tree design

I'm trying to create a mcts ai for connect 5 algorithm. However, I'm confused on designing the tree. Here is a quick description of the algorithm: The initial state, S0 is the board state where the ...
949 views

### How does MCTS handle games with large numbers of poor moves?

I am trying to understand how pure Monte Carlo tree search (https://en.wikipedia.org/wiki/Monte_Carlo_tree_search) handles games where random playout will likely result in a loss easily avoided by ...
208 views

### UCT1 Algorithm: What does "total number of simulations" mean?

When reading up on the UCT1 algorithm (I'm writing a Monte Carlo tree search), I'm having trouble with the formula. $$\frac{w_i}{n_i} + \sqrt{\frac{\ln t}{n_i}}$$ Wikipedia, this guy, and this guy all ...
385 views

### How does the Monte Carlo Tree Search Algorithm Decide When to Expand?

I understand that the MCTS algorithm expands its tree after it has selected the best route to take. However, how does it decide when to end selection and then expand the tree? It cannot just traverse ...
249 views

### What did Dijkstra think about Monte Carlo algorithms? [closed]

In A Discipline of Programming, Dijkstra wrote: Two circumstances have changed the scene since then.* The one is the insight that, even in the case of fully deterministic machines, program testing ...
3k views

### How can we get a Las Vegas algorithm from a Monte Carlo one?

I am trying to solve some exercises on random algorithms from this book, randomized algorithms. This is not a homework. I am only trying to improve my skills. Here is the exercise: Exercise 1.3: ...
633 views

### How do multiple branches from one node occur with the Monte Carlo Tree Search?

I think I understand the Monte Carlo Tree search. It goes through the tree until it reaches a leaf node, where it branches (creates a child node). However, the branching only occurs at the leaf nodes (...
16 views

### What use does the predictor stage in a particle filter have?

Im a bit confused about the particle filter. I understand the generic particle filter algorithm but in some literature say particle filter has predictor stage which is not mentioned in the generic ...
20 views

2k views

### Algorithm for finding best combination of elements

Say I have a very large, arbitrary number of variables, each of which I can assign to be type A, B, or C. The types come with expenses: Type A's are the least expensive, and C's are the most ...
328 views

### Do RP algorithms exist?

I think I understand the RP complexity class (along with coRP, BPP, and ZPP). However, I can't seem to think of how an RP algorithm might be formulated. How can the random coin flip possibilities ...