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

## What does the “principle of deferred decisions” formally mean

7 ### 问题

\$ 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 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 )

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

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

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

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

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

1  BPP澄清  ( Bpp clarification )

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

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

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

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 )

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

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

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

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

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

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

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

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

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

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

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

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

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