“递延决定的原则”正式意味着什么 -- algorithm-analysis 领域 和 probability-theory 领域 和 randomized-algorithms 领域 和 probabilistic-algorithms 领域 cs 相关 的问题

What does the “principle of deferred decisions” formally mean


简体版||繁體版
7
vote

问题

中文

我在Mitzenmacher和Upfal在随机算法上的书中遇到了"延期决策原则" 短语和在线其他几个课程。它不是条件概率吗?在我的理解中,似乎是一种直观的方法,使用条件概率:

$ pr( bigcap_ {i = 1} ^ {n} e_i)= prod_ {i = 1} ^ {n} pr(e_i | e_ {i-1}, dots,e_ {0 $ e_0 = imptyset $。

是我的理解吧?

英文原文

I have encountered the phrase "Principle of deferred decisions" in Mitzenmacher and Upfal's book on Randomized Algorithms and several other courses online. Isn't it just conditional probability? In my understanding, it seems to be an intuitive way of using conditional probability:

$\Pr(\bigcap_{i = 1}^{n} E_i) = \prod_{i = 1}^{n} \Pr(E_i | E_{i-1},\dots,E_{0})$ where $E_0 = \emptyset$.

Is my understanding right?

           
 
 

回答列表

6
 
vote

延迟决策的原理是我们有两种方法来制作随机选择的概念是等同的。

一种方式是,当您在某些算法中需要随机输入时,您可以在确切的步骤中抛出硬币。通过另一种方式,您可以想象有一个甲骨文已经无数次折叠了硬币,并且有一些序列的序列是$ hththhh dots $,我们查询这个oracle告诉我们下一个随机结果。

基本上我们可以推迟实际使用随机输入的行为,只要我们必须且这不会影响此输入的随机性

 

The principle of deferred decisions is the concept that we have two ways to make a random choice both of which are equivalent.

One way is that you can toss a coin yourself at the exact step when you need a random input in some algorithm. In the other way you can imagine that there is an oracle who has already tossed a coin infinitely many times and has some sequence of the form $HTHTHH\dots$, and we query this oracle to tell us the next randomized outcome.

Basically we can defer the act of actually using a randomized input for as long as we have to and this won't affect the randomness of this input.

 
 

相关问题

11  NP-HARD问题是否平均多项式?  ( Can an np hard problem be polynomial on average ) 
我想知道是否有任何$ np $ -hard问题是平均案例中的"polynomial" 。我认为有两种方法可以解释这个吗? 如果$ p neq $,可以有一个算法解决$ np $ -hard问题,摊销(平均案例)$ o(n ^ k)$的运行时间为常数$ k $? 是否存在任何问题,这些问题是$ np $-and中的...

-1  了解使用随机算法的多项式平等测试  ( Understanding polynomial equality testing using randomized algorithms ) 
文件从服务器下载,表示为$ a = {0,1 } ^ n $。服务器与$ b = {0,1 } ^ n $。我们希望使用随机算法确保$ a = b $确保一定程度的确定性。 以下是以下是从此引用的过程讲座pdf 我无法围绕为什么有必要的一些步骤。所以这些是我的问题。 1)在步骤1中,我认为应该选择$ c...

0  散列算法最小化分布  ( Hashing algorithm which minimizes distribution ) 
考虑应用 A1, A2 .. AN 具有属性 P11, P12,... PN1, PN2..我们有以下约束 - total number of properties >> number of applications total number of properties >> number of bucke...

0  如何在设定值随机变量上实施条件概率分布  ( How to implement conditional probability distribution on set valued random varia ) 
当两个RV的事件被设置时,我正在尝试实施条件概率分布。如果我尝试从真实或分类变量推断概念,以便为我设置令人困惑。在通常的场景中,对于某些分立的RVS, $ X,Y $ ,我们可以使用贝叶斯定理来计算两个"准时" 事件的条件概率: $$ p(y = y | x = x)= frac {p(x = x | y = y...

2  绽放过滤器变型  ( Bloom filter variant ) 
我一直在玩一个简单的概率数据结构,它非常类似于绽放过滤器。如果盛开过滤器将使用$ k $独立的散列函数选择$ k $ of $ m $ bits设置,则该结构使用$ m $哈希函数,并使用概率$ p $设置每个位。 这种结构不会产生低于绽放过滤器的假阳性率,但似乎非常快速地计算,特别是如果$ m $是机器字大小的一些...

2  随机Quicksort中较小分区大小的概率界限  ( Probability bounds on size of smaller partition in randomized quicksort ) 
让0美元<一个< 0.5美元是一些常数。我们有一个$ n $ -element数组作为输入。随机化Quicksort随机选择一个元素,作为枢轴和分区。概率1-2A $ 1-2A $最小的部分大于$ $。 我们如何计算这种概率? 尝试72小时后,我达到遵循这意味着有效区域是(1-a)n-an = n(1-2...

1  BPP澄清  ( Bpp clarification ) 
我知道$ sf bpp [2/3,1 / 3] = bpp [ alpha, beta] $当$ alpha lt beta $时,但我在维基百科上读取了一些让我困惑的东西: 在实践中,1/3美元的错误概率可能是不可接受的,但定义中的1/3美元的选择是任意的。它可以是0美元到$ 1/2 $(独占)之间的任...

2  具有双面误差的概率算法  ( Probabilistic algorithm with two sided error ) 
我目前正在研究概率算法,遇到三个主要复杂性等级: BPP:最坏情况的多项式时间,双面误差 RP:最坏情况的多项式时间,单面误差 ZPP:平均例外多项式时间,没有错误 起初我无法理解为什么人们会使用一个可能err的算法。在某些情况下,我认为它确实有意义,例如,因为对RSA加密的原始测试。使用的算法仅有一侧错误...

0  PCP定理的参考  ( Reference on pcp theorem ) 
有人可以推荐关于PCP定理的引用,该PCP定理解释了如何通过示例而不是正式的CS语言工作? 具体来说,我正在寻找如何修改图形着色的示例,以便检查几个彩色或类似的东西。 在CSTHEORY.STACKEXCHANGE被要求将其移到此处。 ...

1  基于转换概率的Anagrams求解器  ( Anagrams solver based on transitions probability ) 
我有一个英语字典(文本文件)和2克,3克和4克的频率作为每个单词的开头。我需要编写一种算法,使用给定的单词,基于转换概率计算可能的字谜(必须进入字典)(我的赋值要求我使用此方法)。 我想使用维特比算法,但我不知道它是否是正确的选择。您如何看待模拟退火算法?你能给我任何帮助吗或建议? ...

1  PCP定理中的多项式是什么?  ( Whats the polynomial involved in the pcp theorem ) 
pcp定理始终谈论长度$ poly(n)的证明$。但是那种多项式是什么?你能在现实生活中实际构建PCP吗? ...

2  条件随机字段(CRF)模型的输出权重是什么?  ( What is the meaning of the output weights of a conditional random field crf mo ) 
问题 当培训我的线性链CRF 时,我用一些包含观察值的序列和每个观察的"地面真理" 标签喂食。我目前正在使用HCRF Matlab接口。 (请参阅 1 ) 在我的情况下,我有4个连续观察值(一些在间隔[-1,1]中,有些[140,200];虽然没有外部[ - 10,250])。标签是1到17之间的整数,总共提供17...

6  概率的多时间机器总是在所有输入上停止?  ( Probabilistic poly time machine always halts on all inputs ) 
在概率多时机的通常定义中,据说机器在所有输入中都停止多项式时间。 是真的说机器停止所有输入,或者如果它停止它必须处于多项式时间? ...

2  Markov链概率在完整的图表中  ( Markov chain probability in a complete graph ) 
我很难了解以下内容。假设我们有一个以$ n $顶点的完整图形,其中最初,其中一个有一个信息。此时,我们关心的是,在每次$ $一个节点中,只有当接收方没有它时,只有当接收方没有选择它的一个邻居中的一个的节点,并将其发送信息。我们不关心发送的方式。 让$ x_t $是一个随机变量,代表在$ t $的时间内具有信息的节点数...

2  是否有一些分布的数学特性,其是概率多项式图定型机的输出?  ( Is there some mathematical properties of the distribution which is the output of ) 
让$ s_ {n} $是一个输入集,其元素为长度$ n $,即$ s_ {n} = sigma ^ {n} $。对于每个概率多项式算法$ a $和任何$ u in sigma ^ {*} $,存在一个函数$ f ^ {a} $,使得$ f ^ a(u)= mathrm {pr} [a(u)= 1] $。让$ ...

3  证明$ IP ^ star = np $  ( Proving ip star np ) 
考虑以下复杂性类$ ip ^ star $,$ ip $的变体。 一种语言$ l $的$ ip ^ star $如果有校样系统$(p,v)$ s.t. $ V $是多项式时间和:的验证者 $$ x in l 意味着pr [(p,v)(x)= 1] ge 3/4 \ x not in l 意味着...

5  独立集合施工随机算法分析  ( Analysis of a randomized algorithm for independent set construction ) 
假设 $ g =(v,e)$ 是 $ n $ 顶点和 $ m $ 边缘。下面我提出了一种用于获取 $ G $ 的独立集的随机算法。 step $ 1 $ :用 $ frac {2} {3} $ 概率。 步骤 $ 2 $ :对于每个剩余边缘,删除其一个endwortices。 我想要上限这个 $ 2 $ -...

3  绽放过滤器为20800万URL  ( Bloom filter for 208 million urls ) 
我需要创建一个208万URL的绽放过滤器。什么是偏航尺寸和哈希数量的良好选择?我尝试了大小的1 GB和4个哈希函数的位矢量,但它导致读取时的误报了太多。 我有一个包含数十亿个URL的Web内容的巨大Web语料库。我需要处理满足某些标准的URL的Web内容:URL应该在过去7天内在Web搜索结果中出现,至少5次。这由2...

1  如何从元素流均匀地样本,其中一些不合适?  ( How to sample uniformly from a stream of elements some of which are unsuited ) 
我以在线方式获得价值$ x_t $,并希望购买"好" ,其中"好" 意味着一些测量$ p(x_t)&gt; t $。考虑以下简单算法。 T = 0.7 N = 100 // or any value N > B B = 20 // or any value 1 < B < N l = 0 for t from...

1  统一采样与约束  ( Uniform sampling with constraints ) 
假设一个人想要在有限的字母表上统一地样本一个给定长度的字符串,这是$ w $满足一组结构约束(例如 - "第三个字符必须等于第一个字符和最后一个字符必须等于第二个")。 显而易见的方法是统一样本$ W $,检查约束是否保持并返回它。但是,我正在处理有许多限制的情况,随机字符串满足它们的概率非常低。有没有办法从满足一组...

2  如何在概率的2-SAT求解器的运行时间上证明某个上限?  ( How do i prove a certain upper bound on the runtime of a probabilistic 2 sat sol ) 
作为家庭作业我们必须在给定的概率算法上证明一组上限,以找到满足的2-CNF公式的令人满意的分配。问题在下面转载。对不起所有不正确的语言;英语不是我的母语,科学语言对我来说特别困难。 观察以下算法: 输入: a 2-cnf forfic $ f(x_1, dots,x_n)$ n ge1 $,其中每个子句包含两...

1  随机选择n位素数  ( Randomly choosing a n bit prime ) 
我一直在研究一些数字理论,我遇到了这个问题: lagrange的素数定理指出,随着n增加,少于 $ n $ 是 $θ( n / log(n))$ 。 考虑以下算法选择随机的n位prime: 1)选择一个随机的n位数字 $ k $ 。 2)在 $ k上运行原始测试。$ 3)如果它通过测试,输出 $ k ...

6  BPP搜索:提升正确性是什么?  ( Bpp search what does boosting correctness entail ) 
对我来说并不是很清楚,如何以及如果我可以在 bpp (有界误差概率多项式 - 时间)搜索问题。你们中的任何人都可以解释我如何工作? 使用BPP搜索,我的意思是一个可能具有假正负,正确解决方案和无解决方案的问题。这是一个定义: 概率的多项式算法$ a $解决关系的搜索问题$ r $如果 每一次$ x∈s $,$ pr...

4  有效地执行“批处理”近似会员查询的方法  ( Ways to perform batch approximate member queries efficiently ) 
在这个问题中,我第一次给出 n 我必须以空间有效的方式存储的值数。然后我给了 m 我必须检查它们是否被添加到数据结构中的值(例如,在操作之后,我知道哪个值是成员,哪个价值是成员,哪个值)。 我可以使用绽放过滤器并简单地迭代 99887665544332 ,但由于 m 相当大,我想看看是否有更有效的方式。数据的一个可能...

4  理论上了解模拟退火信息  ( Understanding simulated annealing information theoretically ) 
所以我最近重新发现了模拟退火,但其他人似乎很清楚的道路。我知道Metropolis-Hastings作为一种采样算法,它创造了一个Markov-Chain,该链条是通过归一化一些功能而产生的分布。意识到您可以使用它来优化许多事物,并且您甚至可以继续拒绝,这是一个很小的飞跃,甚至可以抵制到目前为止你发现的最少值。但是更...




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