了解Monte Carlo概率 -- algorithms 领域 和 probability-theory 领域 和 randomized-algorithms 领域 和 monte-carlo 领域 cs 相关 的问题

Understanding Monte Carlo Probabilities


简体版||繁體版
3
vote

问题

中文

我试图在蒙特卡罗(MC)算法上掌握一个很好的掌握,但我觉得我缺少一些基础。

我不明白是如何通过运行更多的执行来提高其给出正确解决方案的信心。

所以如果我错了,请纠正我,假设$ pr [false] leq 0.5 $。假设我们需要找到执行的数量,以便$ PR [FALSE] LEQ 0.125 $,从而提高信心。

是真的,所需执行的数量为3美元,自0.5×3 = 0.125 $?

提前感谢...

英文原文

I am trying to get a good grasp on Monte Carlo (MC) algorithms, but I feel I am missing something fundamental.

What I don't understand is how MC improves its confidence of giving the correct solution by running more executions.

So please correct me if I am wrong and assume that $Pr[false] \leq 0.5$. Assume we need to find the number of executions so that $Pr[false] \leq 0.125$, thus improving confidence.

Is it true that the number of needed executions is $3$, since $0.5^3=0.125$?

Thanks in advance...

           

回答列表

4
 
vote
vote
最佳答案
 

这是概率放大的概念,其中通过多次运行算法来提高算法的正确性概率。您正在谈论蒙特卡罗算法,它具有单面错误。允许举个例子(从 wikipedia )具有如此类似的特征:

Solovay"strassen原始测试用于确定a 给定的数字是素数。它总是对素数答案 数字输入;对于复合输入,它以概率答案为假 至少1/2,概率最多为1/2。因此,虚假 算法的答案肯定是正确的,而真实 答案仍然不确定;据说这是一个(1/2)-correct 假偏置算法。

上述算法返回错误答案的概率最多为1/2。现在,关键的想法是理解,算法的连续运行产生了彼此的独立的答案 - 因此,在运行两次时,算法返回错误答案的概率 时间是大多数 $( frac {1} {2})^ 2 $ 。因此,在 $ k $ 迭代之后,错误答案的概率减少为大多数 $( frac {1} { 2})^ K $ 。因此,如果我们采用算法返回 false 如果第一个 $ k $ 运行,则提供输出false ,否则返回 true ,然后我们的方案返回错误答案的概率最多 $ 1 - ( frac {1} {2 })^ $ ,它可以被驱动到 $ 0 $ $ k $ < / span>。

 

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 Solovayxe2x80x93Strassen primality test is used to determine whether a given number is a prime number. It always answers true for prime number inputs; for composite inputs, it answers false with probability at least 1/2 and true with probability at most 1/2. Thus, false answers from the algorithm are certain to be correct, whereas the true answers remain uncertain; this is said to be a (1/2)-correct false-biased algorithm.

The probability that the above algorithm returns an incorrect answer is thus at most 1/2. Now, the key idea is to understand that successive runs of the algorithm produce answers that are independent of each other - hence, on running it twice, the probability that the algorithm returns an incorrect answer both times is at most $(\frac{1}{2})^2$. Thus, after $k$ iterations, the probability of an incorrect answer reduces to at most $(\frac{1}{2})^k$. Thus, if we adopt the scheme that the algorithm returns false if the any of the first $k$ runs give an output of false, else return true, then the probability that our scheme returns an incorrect answer is at most $1 - (\frac{1}{2})^k$, which can be driven down to $0$ for large values of $k$.

 
 

相关问题

1  可以使用Monte Carlo树搜索解决最短路径问题吗?  ( Can the shortest path problem be solved using monte carlo tree search ) 
我认为Monte Carlo树搜索可以用来找到最短的路径,但似乎仅考虑在模拟步骤中考虑赢/丢失的结果。 如果我们将路径长度视为仿真步骤的结果,则会如何运行后传播?似乎沿着仿真步骤中的长路径最终有最佳路径的节点可能会受到惩罚。 ...

3  我们如何从蒙特卡洛获得一个拉斯维加斯算法?  ( How can we get a las vegas algorithm from a monte carlo one ) 
我正在尝试从本书的随机算法上解决一些练习,随机算法。这不是一部作业。我只是努力提高我的技能。 这里是练习: 练习1.3:考虑一个Monte Carlo算法$ a $ a for a for of问题$ pi $,其预期的运行时间$ t(n)$ t(n)$ t(n)$上的任何实例$ n $,它产生a正确解决概率$ ...

2  Monte Carlo树搜索的部分扩展是什么?  ( What is partial expansion in monte carlo tree search ) 
我正试图了解对MCTS算法的修改,称为部分扩展。 从我读取的内容,它可以在扩展孙子节点之前不需要扩展所有子节点。 但是,我在概念上概念地了解这一过程及其潜在利益。有人可以帮帮我吗? ...

0  在Monte Carlo在蒙特卡罗或更一般地估算自相关时间的过程是什么程序?  ( What is the procedure for performing a binning analysis in monte carlo or more ) 
我正在研究类似于insing模型的蒙特卡罗项目。我发现了许多关于我的代码的许多例子: https ://github.com/danielsela42/mc_tbg_model/blob/master/mc_project/mcproj_binned.py (我的代码)。 从一些纸张上读取分析分析,每个分叉步骤后的误...

1  将总距离最小化到来自一组点的点  ( Minimizing total distance to a point from a set of points ) 
我读过问题: 有$ N $随机放置。放置一个停车场,使得(直线)到所有房屋的距离很小。 我已经写了一个蒙特卡洛算法,但这不能是最佳方法。 除了用Monte-Carlo方法逼近位置之外的解决方案吗?特别是通过使用图表或者是错误的方法? 有没有办法进入计算最佳位置? 这个问题的名称是什么? ...

1  Monte Carlo树搜索如何发生来自一个节点的多个分支?  ( How do multiple branches from one node occur with the monte carlo tree search ) 
我想我理解蒙特卡罗树搜索。它通过树,直到它到达叶节点,它分支(创建子节点)。但是,分支仅发生在叶节点(右?)。因此,分支从不从非叶节点出来。那么一个节点如何有多个分支(多个子节点)出来的?为清楚起见,这是一张图片: 所以这不是那个过程只是继续重复吗?它不是叶节点,因此算法不会分支(创建另一个子节点)...所以它...

5  蒙特卡罗树搜索连接5树设计  ( Monte carlo tree search in connect 5 tree design ) 
我正在尝试为连接5算法创建MCTS AI。但是,我在设计树上很困惑。以下是算法的快速描述: 初始状态, s0 是oi 放置石头,或换句话说,Ai的转弯。是正确的,每个节点应该是AI的转弯,而不是人类? 在扩展阶段,您需要"创建子节点" 。在我的游戏中,孩子节点将各自成为AI可以移动的地方。但是,如果我想选择下一个可移...

1  粒子过滤器中的预测阶段有哪些使用?  ( What use does the predictor stage in a particle filter have ) 
我有点困惑粒子滤波器。 我理解通用粒子过滤算法,但在一些文献中,粒子过滤器具有通用粒子过滤器中未提及的预测阶段。 我认为它基于观察来称重粒子。什么是用于用于的预测阶段? ...

2  算法以昂贵成本函数的高维参数空间  ( Algorithm to sample high dimensional parameter space of expensive cost function ) 
我正在寻找算法的建议(显然这是正确的,所以为此),可有效扫描成本函数的高维参数空间来评估昂贵的函数。 通过昂贵评估我的意思是,人们只能在现代计算机上每秒进行o(1)评估。 有效地,我的意思是,该算法应该学会避免没有解决方案的区域:成本函数的评估可能会失败某些参数。 仍然在效率的方面,该算法应产生一组样本,该样本表示...

3  了解Monte Carlo概率  ( Understanding monte carlo probabilities ) 
我试图在蒙特卡罗(MC)算法上掌握一个很好的掌握,但我觉得我缺少一些基础。 我不明白是如何通过运行更多的执行来提高其给出正确解决方案的信心。 所以如果我错了,请纠正我,假设$ pr [false] leq 0.5 $。假设我们需要找到执行的数量,以便$ PR [FALSE] LEQ 0.125 $,从而提高信心。...

0  寻找最佳元素组合的算法  ( Algorithm for finding best combination of elements ) 
说我有一个非常大,任意数量的变量,每个变量可以分配为类型a,b或c。 这些类型有费用:A型是最便宜的,C是最昂贵的,但它们的费用从变量变化到变量。 例如,{a,c,c}实际上可能比{c,a,a}更昂贵,如果第一个变量恰好是值得更多的,但我们不会知道在为我们分配类型和何种方面的总成本是多少运行程序。 我们也不想低于一...

0  了解政策第一访问蒙特卡罗控制算法  ( Understanding on policy first visit monte carlo control algorithm ) 
我正在经历蒙特卡罗的方法,直到现在。但是,我实际上正在研究诺斯龙软政策的政策首次访问Monte Carlo控制,这使我们能够估计加强学习中的最佳政策。 我遇到了解算法的蓝色步骤。是一对st,从不应该出现在给定的一组状态吗?在这种情况下,以下伪代码永远不会实现?什么是ST,出现在一组动作状态中的具体情况? 如果...

4  对抗蒙特卡罗树搜索不对称  ( Adversarial monte carlo tree search asymmetry ) 
Monte Carlo树搜索用UCT称赞它的不对称树增长, 不仅仅是非承诺的有前途的子树。 但是在一个2人的对手游戏中,当一个节点的胜利是下面的节点的损失时,树的增长不会对每个节点的当前播放器非常有利,并且导致不那么不对称树增长? ...

1  如何在Monte Carlo树搜索中避免在UCT公式中归零?  ( How to avoid division by zero in uct formula in monte carlo tree search ) 
在蒙特卡罗树搜索算法的步骤2(扩展)中,创建一个或多个子节点,其中一个名为C的一个节点被选中。模拟步骤应用于C的C分数为0/1或1/1。另一个新创建的叶节点发生了什么?我假设他们得分为0/0,这与UCT公式不合适,这些公式将通过最大化WINS / Total Simulations来探索哪些节点+在评估此表达式时将导...

3  如何保护AI从人类的“不合逻辑”移动中?  ( How do you protect an ai from a human doing illogical moves ) 
使用蒙特卡罗方法和评估功能。一些动作将被视为比其他动作更有利。 作为计算机自身播放,它通常会用于最佳动作。因此,训练自己处理这些动作。 但是如果人类确实有几个似乎有害的动作,何时才能抛出轨道。然后使用人类的专业知识,继续赢得比赛? 如何驾驶AI来解释这一点? 或者我们必须假设它可以概括从"完美" 游戏到普遍存在游戏的...

1  这种模拟退火试图解决的问题是什么问题?  ( What problem is this application of simulated annealing trying to solve ) 
我正在阅读其维基百科页面上的模拟退火,并被绘制到说明退火时间表的特定示例。以下是图片及其描述: 说明冷却时间表对模拟退火性能的影响。问题是重新排列图像的像素,以便最小化某个势能功能,这导致类似的颜色在短范围内吸引,并且在稍微较大的距离处吸收。基本移动交换两个相邻像素。通过快速冷却时间表(左)和缓慢的冷却时间表...

4  UCT1算法:“仿真总数”是什么意思?  ( Uct1 algorithm what does total number of simulations mean ) 
在读取UCT1算法时(我正在编写蒙特卡罗树搜索),我的公式遇到了麻烦。 $$ frac {w_i} {n_i} + sqrt { frac { ln t} $$ wikipedia ,这个guy ,和这个家伙所有人都说$ t $,或者他们用于该变量的其他任何东西,等于" 模拟总数" 。这是什么意思,究竟是什么?...

3  蒙特卡罗树搜索算法如何决定何时展开?  ( How does the monte carlo tree search algorithm decide when to expand ) 
我理解,MCT算法展开了它的树,后它是所选的最佳路线。但是,它如何决定何时结束选择,然后展开树?它不能只是遍历整个图形......然后它总是在同一个地方(右?)生成子节点,因此,MCT在遍历搜索树时如何决定生成子节点? ...

1  MCTS如何防止在遍历阶段中选择终端状态?  ( Mcts how to prevent selecting a terminal state in traversal phase ) 
Hello我目前正在研究MCTS的实现,我遇到了我的树遍历策略选择带终端游戏状态的节点的问题。此外,我如何防止选择只有具有终端游戏状态的儿童节点的节点(依此类推)? ...

0  设计Mont Carlo和Las Vegas算法来解决最大独立集  ( Devise mont carlo and las vegas algorithms to solve maximum independent set ) 
我正在尝试设计一个拉斯维加斯算法来解决最大独立集,但我不知道如何开始。 也,我想为这个问题设计一个Mont Carlo算法。 我会感谢任何帮助。 谢谢。 ...

5  从概率密度函数生成值  ( Generating values from a probability density function ) 
如果我有概率密度函数,则某些f(x)是&gt; = 0到处并集成到1,是有没有方法可以使用该PDF生成随机数? 我知道有盒式映射变换将均匀随机数转换为高斯,但是常规情况有什么,或者至少是PDF的更常规情况? ...

1  大流行棋盘游戏 - 找到所有可能的下一个操作  ( Pandemic board game find all possible next 4 actions ) 
我希望我在合适的社区上询问这一点。 我正在建立一个人工智能来玩棋盘游戏大流行。 AI使用蒙特卡罗算法。实现游戏规则和AI后,它按预期工作(非常糟糕,但它有效)。 我认为当前算法具有动作色散的主要问题。在大流行中,每个玩家都被允许多达4个动作。可能的动作的数量通常在10到100之间。当前算法运行1000个蒙特卡罗模拟...

2  蒙特卡罗算法:有些问题是否有两个对面的蒙特卡罗算法可以解决它?  ( Monte carlo algorithms are there any problems where two opposite monte carlo a ) 
我开始阅读概率算法和Monte-Carlo算法。由于Monte-Carlo只能为真假提供一定的答案,我想知道它是否可以想到对于同样的问题,有两个相反的蒙特卡罗算法,能够提供一定的答案。 (通过对面,我的意思是一个人会确定什么时候是假的,而另一个是肯定的,当它是真的时) 例如:存在一个基于序列的素数测试Monte-C...

3  如何估算使用Monte Carlo满足给定DNF公式的作业数量?  ( How to estimate how many assignments satisfy a given dnf formula using monte car ) 
允许,家庭作业。 为了这个问题的目的:$ phi $是一个类似于这个的dnf公式:$(x_1 wedge neg x_3 wedge x_4) vee( neg x_1 wedge x_2)$也$ c_i $在此公式中是一个条款,例如$ c_1 = x_1 wedge neg x_3 wedge x_...

2  什么是用于查找汉密尔顿人道的Monte-Carlo算法的示例?  ( What is an example of a monte carlo algorithm for finding a hamiltonian path ) 
我最近已知有没有蒙特-Carlo算法(s?),用于确定图表中是否存在哈密顿路径。我正在努力弄清楚它是如何工作的。什么是随机元素? ...

相关问题

1  可以使用Monte Carlo树搜索解决最短路径问题吗? 
3  我们如何从蒙特卡洛获得一个拉斯维加斯算法? 
2  Monte Carlo树搜索的部分扩展是什么? 
0  在Monte Carlo在蒙特卡罗或更一般地估算自相关时间的过程是什么程序? 
1  将总距离最小化到来自一组点的点 
1  Monte Carlo树搜索如何发生来自一个节点的多个分支? 
5  蒙特卡罗树搜索连接5树设计 
1  粒子过滤器中的预测阶段有哪些使用? 
2  算法以昂贵成本函数的高维参数空间 
3  了解Monte Carlo概率 
0  寻找最佳元素组合的算法 
0  了解政策第一访问蒙特卡罗控制算法 
4  对抗蒙特卡罗树搜索不对称 
1  如何在Monte Carlo树搜索中避免在UCT公式中归零? 
3  如何保护AI从人类的“不合逻辑”移动中? 
1  这种模拟退火试图解决的问题是什么问题? 
4  UCT1算法:“仿真总数”是什么意思? 
3  蒙特卡罗树搜索算法如何决定何时展开? 
1  MCTS如何防止在遍历阶段中选择终端状态? 
0  设计Mont Carlo和Las Vegas算法来解决最大独立集 
5  从概率密度函数生成值 
1  大流行棋盘游戏 - 找到所有可能的下一个操作 
2  蒙特卡罗算法:有些问题是否有两个对面的蒙特卡罗算法可以解决它? 
3  如何估算使用Monte Carlo满足给定DNF公式的作业数量? 
2  什么是用于查找汉密尔顿人道的Monte-Carlo算法的示例? 



© 2021 it.wenda123.org All Rights Reserved. 问答之家 版权所有