用偏硬币造公平硬币

UnBiased coin

专题: Probability / 概率
难度: L2
来源: Brainstellar

题目详情

有一枚偏硬币，出现正面的概率为 $p$ ，反面的概率为 $1-p$ （其中 $0.5<p<1$ ）。

如何利用这枚偏硬币构造一次“公平抛硬币”（得到正/反概率各 $1/2$ ）？

We have a weighted coin that shows a Head with probability $p$ and tails with $1-p$ , $(0.5<p<1)$ . How to define two equally likely events using this coin?

Each event is a function of the outcomes of one or more coin tosses. For example, we can toss 2 times and define Event1 as [HH, TT] and Event2 as [TH, HT].

Hint

Since $p$ is unknown, the probability of HH and TT are unreliable.

解析

冯·诺依曼（Von Neumann）方法：

连续抛两次：
- 若结果为 HT，则输出 H。
- 若结果为 TH，则输出 T。
- 若为 HH 或 TT，则丢弃这两次结果，重新来。

因为 $P(HT)=p(1-p)$ 与 $P(TH)=(1-p)p$ 相等，所以在条件事件“出现 HT 或 TH”下，输出 H 与 T 的概率各为 $1/2$ 。

Original Explanation

Toss 2 times, event1 is HT, event2 is TH, and repeat the process otherwise.

Solution

For an arbitrary $p$ , this cannot be accomplished in a single toss. If we toss twice, we observe that the probability of HT and TH is the same, i.e. the probability of heads in the first toss and tails in the second is the same as its reverse, i.e. $p \cdot (1-p) = (1-p) \cdot p$

Hence, we can declare these two as the two events. If we observe HH or TT, we retry.

Follow-up question

What's the probability of an infinite repetition?

Follow-up Answer

Let us calculate the probability of the first retry

Probability of HH or TT = $p^2 + (1-p)^2$

$P(r)= 2p^2 -2p + 1$

This is a quadratic equation, with a minimum value of $P(r) = 0.5$ at $p=0.5$ , and $0.5 < P(r)< 1$ for the range $0.5 < p < 1$

Thus, the probability of an infinite repetition is $P(r) \cdot P(r) \cdot ... = 0$ (because $P(r) < 1$ )

Note that if $r$ is close to 1 then $P(r)$ is close to 1, and it might take a very long sequence before event 1 or event 2 occurs.