用硬币等概率选 3 个选项

公平硬币：抛两次，映射

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

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

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

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

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

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

---

英文解析

Solution 1: Denote the desserts by $A,B$ , and $C$ . First, suppose the coin is fair. Denote heads by $H$ and tails by $T$ . The procedure to choose one of three desserts with equal probability is as follows: toss the coin twice; let the outcomes $T H,H T$ , and $T T$ correspond to choosing desserts $A,B$ , and $C$ , respectively; if the outcome is $H H$ , repeat the procedure.

Note that the probability of our procedure not being repeated is $\textstyle p = \frac{3}{4}$ ; hence, the number of times our procedure is repeated is a geometric random variable with $p$ as its parameter. The expected number of times our procedure is repeated is $\begin{array}{r}{\frac{1}{p} = \frac{4}{3}} \end{array}$ . Since each procedure involves two coin tosses, the expected number of coin tosses before Alice chooses one of three desserts with equal probability is $\frac{8}{3}$ .

Now, suppose the coin is biased. One procedure to choose one of three desserts with equal probability would be as follows: toss the coin four times; denote by THHT, HTTH, and THTH the outcomes corresponding to choosing desserts $A,B$ , and $C$ , respectively; all the other 4- toss outcomes result in repeating the procedure.

Solution 2: An alternative procedure is as follows: toss the coin three times; denote by $HTT, THT$ , and $HTT$ the outcomes corresponding to choosing desserts $A, B$ , and $C$ , respectively; all the other 3 - toss outcomes result in repeating the procedure.

Using an argument similar to the case with a fair coin, one finds that the expected number of tosses of a coin with an unknown bias, before Alice chooses one of three desserts with equal probability, is $\frac{64}{3}$ and 8, respectively, for the two procedures described above.