返回题库

用硬币等概率选 3 个选项

Alice in a restaurant

专题
Probability / 概率
难度
L4

题目详情

Alice is in a restaurant trying to decide between three desserts. How can she choose one of three desserts with equal probability with the help of a fair coin? What if the coin is biased and the bias is unknown?

解析

公平硬币：抛两次，映射

  • TH → 甜点 A
  • HT → 甜点 B
  • TT → 甜点 C
  • HH → 重新开始

因为在“非 HH”的条件下 TH/HT/TT 等概率，所以每个甜点概率都是 1/31/3。

偏置且偏置未知的硬币：先用冯·诺依曼方法从偏置硬币抽取“公平比特”。

  • 连续抛两次：若出现 HT 则输出 0；若出现 TH 则输出 1；若 HH 或 TT 则丢弃重来。

这样得到的 0/1 是严格等概率且相互独立（不依赖未知偏置）。

然后用两次公平比特得到 00/01/10/11，并将 00/01/10 映射到 A/B/C，11 丢弃重来，即可实现等概率 1/31/3。