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

## Clock solitaire game and principle of deferred decision

2

### 问题

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

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 )

0  散列算法最小化分布  ( Hashing algorithm which minimizes distribution )

2  随机Quicksort中较小分区大小的概率界限  ( Probability bounds on size of smaller partition in randomized quicksort )

0  PCP定理的参考  ( Reference on pcp theorem )

5  独立集合施工随机算法分析  ( Analysis of a randomized algorithm for independent set construction )

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

3  绽放过滤器为20800万URL  ( Bloom filter for 208 million urls )

1  基于转换概率的Anagrams求解器  ( Anagrams solver based on transitions probability )

6  BPP搜索：提升正确性是什么？  ( Bpp search what does boosting correctness entail )

1  统一采样与约束  ( Uniform sampling with constraints )

2  是否有一些分布的数学特性，其是概率多项式图定型机的输出？  ( Is there some mathematical properties of the distribution which is the output of )

2  Markov链概率在完整的图表中  ( Markov chain probability in a complete graph )

2  条件随机字段（CRF）模型的输出权重是什么？  ( What is the meaning of the output weights of a conditional random field crf mo )

1  随机选择n位素数  ( Randomly choosing a n bit prime )

2  如何在概率的2-SAT求解器的运行时间上证明某个上限？  ( How do i prove a certain upper bound on the runtime of a probabilistic 2 sat sol )

-1  了解使用随机算法的多项式平等测试  ( Understanding polynomial equality testing using randomized algorithms )

1  如何从元素流均匀地样本，其中一些不合适？  ( How to sample uniformly from a stream of elements some of which are unsuited )

6  概率的多时间机器总是在所有输入上停止？  ( Probabilistic poly time machine always halts on all inputs )

4  理论上了解模拟退火信息  ( Understanding simulated annealing information theoretically )

2  具有双面误差的概率算法  ( Probabilistic algorithm with two sided error )

2  绽放过滤器变型  ( Bloom filter variant )

0  如何在设定值随机变量上实施条件概率分布  ( How to implement conditional probability distribution on set valued random varia )

3  证明\$ IP ^ star = np \$  ( Proving ip star np )

4  有效地执行“批处理”近似会员查询的方法  ( Ways to perform batch approximate member queries efficiently )

11  NP-HARD问题是否平均多项式？  ( Can an np hard problem be polynomial on average )