这是一个众所周知的问题，这里和 stackoverflow 已经讨论了几个很好的解决方案（似乎我不能发布多个链接，但快速的谷歌搜索会给你一些有趣的条目）。看看维基百科条目

http://en.wikipedia.org/wiki/Fair_coin#Fair_results_from_a_biased_coin

这是一个经典问题，我相信最初归因于冯诺依曼。一种解决方案是继续成对抛硬币，直到两对不同，然后按照对中第一个硬币的结果。

明确地让成为抛的结果，其中是第一个硬币，是第二个硬币。每个硬币都有正面的概率。那么由于对称性，这意味着。为了明确地看到这种对称性，请注意意味着结果是或，由于独立性，这两者的可能性相同。$(X_i,Y_i)$$i$$X_i$$Y_i$$p$$P(X_i=H|X_i\neq Y_i)=P(X_i=T|X_i\neq Y_i)$$P(X_i=H|X_i\neq Y_i)=1/2$$X_i\neq Y_i$$(H,T)$$(T,H)$

根据经验，直到这样一个不等对的等待时间是

当接近 0 或 1 时会爆炸（这是有道理的）。$p$

我不确定如何有效地总结这些术语，但只要滚动和成功总数使得为偶数，我们就可以停止，因为我们可以划分不同的我们可以将和分成两组等概率的排序，每组对应于不同的输出标签。我们需要注意我们还没有停止这些元素，即没有一个元素有一个长度为的前缀，并且有次成功使得是偶数。我不确定如何将其转换为预期的翻转次数。$n$$t$$\binom{n}{t}$$n$$t$$n'$$t'$$\binom{n'}{t'}$

为了显示：

我们可以停在 TH 或 HT，因为它们的概率相等。向下移动帕斯卡三角形，下一个偶数项在第四行：4、6、4。这意味着如果出现一个正面，我们可以在掷骰后停止，因为我们可以创建一个二分匹配：HHHT 与 HHTH，技术上 HTHH 与THHH 虽然我们已经为此停下来了。类似地，产生与 TTHH 匹配的 HHTT（其余的，我们在到达它们之前就已经停止了）。$\binom42$

对于，所有序列都有停止前缀。处变得更有趣，我们将 FFFFTTFT 与 FFFFTTTF 匹配。$\binom52$$\binom83$

对于 ，如果我们停止了，则没有停止的机会是和预期的滚动次数。对于我们保持滚动对直到它们不同的解决方案，没有停止的机会是，如果我们停止了 4，则预期滚动数。通过递归，预期翻转的上限对于提出的算法是。 $p=\frac12$$\frac1{128}$$\frac{53}{16}$$\frac{1}{16}$$\frac{128}{127} \cdot \frac{53}{16} = \frac{424}{127} < 4$

我编写了一个 Python 程序来打印停止点：

import scipy.misc
from collections import defaultdict


bins = defaultdict(list)


def go(depth, seq=[], k=0):
    n = len(seq)
    if scipy.misc.comb(n, k, True) % 2 == 0:
        bins[(n,k)].append("".join("T" if x else "F"
                                   for x in seq))
        return
    if n < depth:
        for i in range(2):
            seq.append(i)
            go(depth, seq, k+i)
            seq.pop()

go(8)

for key, value in sorted(bins.items()):
    for i, v in enumerate(value):
        print(v, "->", "F" if i < len(value) // 2 else "T")
    print()

印刷：

FT -> F
TF -> T

FFFT -> F
FFTF -> T

FFTT -> F
TTFF -> T

TTFT -> F
TTTF -> T

FFFFFT -> F
FFFFTF -> T

TTTTFT -> F
TTTTTF -> T

FFFFFFFT -> F
FFFFFFTF -> T

FFFFFFTT -> F
FFFFTTFF -> T

FFFFTTFT -> F
FFFFTTTF -> T

FFFFTTTT -> F
TTTTFFFF -> T

TTTTFFFT -> F
TTTTFFTF -> T

TTTTFFTT -> F
TTTTTTFF -> T

TTTTTTFT -> F
TTTTTTTF -> T