知识卡片

普通读书笔记卡 · 3728.a.3.b.1.a.1

未知主持人策略时随机换门

理解等级:高级

在附录给出的未知主持人换门邀请策略模型下,设收到邀请后初选正确的后验概率为q。留下会以概率q获胜,换门会以概率1−q获胜;若用独立硬币决定、各以1/2概率留下或换门,则

Pr(获胜|受邀) = q/2 + (1−q)/2 = 1/2。

所以无论未知的主持人策略把q推到哪里,50%换门都把受邀后的条件胜率固定在1/2。若偏向留下,主持人可让邀请更多发生在初选错误时;若偏向换门,他可让邀请更多发生在初选正确时,从而把最坏结果压到1/2以下。

此结论限于该模型。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 附录C 计数与概率 · 查看原书依据

      If you don’t know pright and pwrong, what choice of pswitch maximizes the minimum probability of winning over all the choices of pright and pwrong? Let’s return to the original

    参考来源

    - 位置:《算法导论(第4版)》附录C《计数与概率》(OEBPS/appendix003.xhtml,文本字符[45000,49224))。 - 结论依据:附录C问题C-1(h)–(j)给出主持人两种邀请概率和选手换门概率的模型,并要求证明换门概率1/2的极小极大性质;q形式是对原公式的等价展开。 - 原始内容:If you don’t know p right and p wrong , what choice of p switch maximizes the minimum probability of winning over all the choices of p right and p wrong ? Let’s return to the original