Questions tagged [monte-carlo]

The tag has no usage guidance.

13 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
2
votes
1answer
56 views

Algorithm to sample high-dimensional parameter space of expensive cost function

I am looking for recommendations for algorithms (apparently this is the right SO site for that) that efficiently scan the high-dimensional parameter space of a cost function that is very expensive to ...
2
votes
0answers
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 ...
2
votes
0answers
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 ...
1
vote
0answers
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 ...
1
vote
0answers
51 views

How to avoid division by zero in UCT formula in Monte Carlo tree search?

In step 2 (expansion) of the Monte Carlo tree search algorithm, one or more child nodes are created, and one node named C is chosen among them. The simulation step is applied to C giving it a score of ...
1
vote
0answers
19 views

What problem is this application of simulated annealing trying to solve?

I was reading about simulated annealing on its Wikipedia page, and was drawn to a particular example illustrating the annealing schedule. Below is the picture and its description: Example ...
1
vote
0answers
160 views

Combining TWO Monte Carlo algorithms to get a Las Vegas algorithm that solves the same problem

I came across a problem that I have no clue how to solve. Consider two Monte Carlo algorithms, called A and B that both solve the same problem. A is true-biased and t-correct, while B is false-...
1
vote
0answers
104 views

Can the shortest path problem be solved using Monte Carlo Tree Search?

I think Monte Carlo Tree Search could be used to find the shortest path, but it seems that this method is only used considering win/lose outcomes in the simulation step. If we consider the path ...
1
vote
0answers
164 views

Is MCTS an appropriate method for this problem size (large action/state space)?

I'm doing a research on a finite horizon decision problem with $t=1,\dots,40$ periods. In every time step $t$, the (only) agent has to chose an action $a(t) \in A(t)$, while the agent is in state $s(t)...
1
vote
0answers
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 ...
0
votes
0answers
29 views

What is the procedure for performing a binning analysis in Monte Carlo, or more generally, estimating autocorrelation times?

I'm working on a monte carlo project similar to the Ising model. I've found many examples on which I've based my code: https://github.com/danielsela42/MC_TBG_Model/blob/master/mc_project/mcproj_binned....
0
votes
0answers
82 views

Devise Mont Carlo and Las Vegas Algorithms to Solve Maximum Independent Set

I am trying to devise a Las Vegas algorithm to solve Maximum Independent Set, but I don't know how to start. Also, I want to devise a Mont Carlo algorithm for this problem. I would appreciate any help....
0
votes
1answer
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 ...