时钟纸牌游戏和延期决定原则 -- probability-theory 领域 和 randomized-algorithms 领域 和 probabilistic-algorithms 领域 cs 相关 的问题

Clock solitaire game and principle of deferred decision


简体版||繁體版
2
vote

问题

中文

我一直在阅读Rajeev Motwani和Prabhakar Raghavan的随机算法书。在第3.5节中,他们已经引入了延迟决定的原理,这是一个不同的概率空间。他们提供的一个例子是一个时钟纸牌游戏。游戏如下。最初52张卡随机分组为4张13张牌。桩标有1,2,3美元,...,10,q,j,k,a $。游戏首先从$ K $标记的堆中绘制一张卡。将从桩的面值从桩的桩的下一次绘制进行。对于一个例子,假设绘制的卡是7,然后我们去标有7美元$ 7 $的堆,然后从这个堆中选择卡。我们以这种方式继续。当我们到达空堆时,游戏结束。如果在游戏结束时所有桩都空无一次,则一个赢。很容易显示最后一张卡必须有面值$ k $。

现在,分析获胜的概率,作者假设名为"延迟决定原则" 的不同概率空间。这个想法是"随着游戏的进步,让随机选择展开,而不是提前修复整套选择。" 有了这个,他们得出结论,赢得的概率,52号卡为$ k $的可能性是1/13。任何人都可以解释为什么这是1/13?
英文原文

I have been reading the randomized algorithm book by Rajeev Motwani and Prabhakar Raghavan. In section 3.5 they have introduced principle of deferred decision which is a different probability space. The example they provided is a clock solitaire game. The game is as follows. Initially 52 cards are randomly grouped into 4 cards of 13 piles. The piles are labeled $1,2,3,...,10,Q,J,K,A$. The game starts by drawing a card from $K$ labeled pile. The next draw will be taken place from the pile with the face value of the drawn card. For an example suppose the drawn card is 7, then we go to the pile labeled $7$ and pick a card from this pile. We continue in this fashion. The game ends when we reach an empty pile. And one wins if all the piles are empty when the game ends. It is easy to show that the last card drawn must have face value $K$.

Now, to analyze the probability of winning, the author assumes a different probability space named "Principle of deferred decision". The idea is to "let the random choices unfold with the progress of the game, rather than fix the entire set of choices in advance." With this, they conclude that the probability of winning i.e., the probability that 52nd card being $K$ is 1/13. Can anyone explain why this is 1/13?

        
 
 

回答列表

1
 
vote

你可以表明,只要游戏进行,所需的下一个卡就是一个统一选择的随机卡,在尚未挑选的卡中。我们可以想象即使游戏确实停止也会继续相同的过程。从那个角度来看,我们拥有的是甲板的完全随机顺序;一旦达到第四个国王,游戏就会停止;如果第四个国王是最后一张牌,我们赢了。现在第四个国王是最后一张卡的概率与最后一张卡是国王的概率相同,这是1/13。

 

You can show that as long as the game goes on, the next card being picked is a random card chosen uniformly among the cards not already picked. We can imagine the same process continuing even if the game does stop. From that point of view, what we have is a completely random order of the deck; the game stops once the fourth king is reached; we win if the fourth king is the last card. Now the probability that the fourth king is the last card is the same as the probability that the last card is a king, which is 1/13.

 
 
   
   

相关问题

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

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...

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...

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

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

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

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

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

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

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] $。让$ ...

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

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...

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

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

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...

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

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

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

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

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...

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 意味着...

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

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中的...




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