这是对在不同大小的均匀离散分布之间进行转换的传统问题的一种扭曲。
对于这个例子，我们可以掷两次骰子，得到 36 种可能性之一。通常的解决方案是，前 35 个可以平均分布在输出 1..7 中，最后一个可以被拒绝，从而导致重新滚动。但是，这不受掷骰次数的限制，因为您可以无限期地被拒绝。我的问题是，是否存在有界算法？
一个略显粗略的论点说不，如下所示。每个掷骰子的信息量是位，我们需要位的倍数。很不幸是不合理的，所以我们不能完美地用完信息——我们总是会丢失信息。丢失的信息意味着您拒绝了某些数字。因此，您将永远无法限制算法所需的掷骰数。
由于很多原因，这个论点非常粗略，而且可能是错误的，但论点的总体主旨感觉有点正确。我是对的，如果是这样，我该如何改进这个“证明”？
论据很好。不过，我认为您可以将其提炼成更简单的东西。
一系列滚动确定了一个分支概率树，每个节点有六个分支。因为滚动是独立的，并且每个结果的概率为，所以到达第级的给定节点（即滚动的特定序列）的机会是。让是滚动次数的任意界限。那么任何事件的机会都是形式的数字的总和，其中。这样的总和显然是的倍数。由于有多大，它都不能实现为任何此类事件的概率。
这是同一想法的另一种阐述。次掷骰后 发生的任何事件的机会，当以为基数写入时，可以在以 6 为基数的“seximal”点之后使用最多个数字。由于需要无限扩展，因此它不可能作为任何此类事件的机会出现。
如果您对使用 base感到不舒服，那么（通过类比）考虑一个（假设的）十面骰子，每个结果都有的机会。在次滚动之后，所有概率都可以用恰好位的小数表示。像、等这样的数字不会以任何这样的概率出现。
如果我按照你的说法，我们可以注意到这必然是非理性的，所以我们总是会丢失一些信息（这是真的，因为5个不同的结果用一个数字表示，第36个结果被丢弃）。
但是，我确实认为，通过定义重新滚动的事件及其概率，您可以使用马尔可夫不等式来限制重新滚动的数量。重新滚动 k 的概率迅速衰减到 0，因此对于您喜欢的一些较大的 k，您可以开始使用零概率定理。