Exact Probability Powering from Samples Alone at the Collision Scale

Temperature sampling normally needs the probability distribution, yet many systems, from simulators to language models reasoning toward a final answer, provide only *samples*. We ask how to sample exactly at temperature $1/k$ from samples alone, drawing each outcome with probability proportional to $p_i^k$, the $k$th power of its probability, for a fixed integer $k\ge 2$ (probability powering). Known approaches face a trade-off between speed and exactness. Classical rejection sampling, which keeps an outcome only when $k$ fresh samples agree, is exact but slow: with $n$ equally likely outcomes, it needs $\Theta (n^{k-1})$ samples. The first-collision shortcut, which returns the first outcome to appear $k$ times among all samples drawn so far (a $k$-fold collision), is fast—needing only $\Theta (n^{1-1/k})$ samples—but biased. Refined collision-based methods reduce this bias but remain approximate. In this work, we show that this trade-off is unnecessary. We define the *collision map*, a random update built from one collision and the other outcomes seen before it, and prove that it preserves the target distribution. Our sampler, **Collision-map CFTP**, composes these maps backward in time (coupling from the past) *without knowing* the probabilities or which outcomes are possible. It returns an *exact* output after a bounded expected number of collisions, needing only $\Theta (n^{1-1/k})$ samples instead of rejection's $\Theta (n^{k-1})$. Conversely, every sampler that is exact for every distribution must see its output $k$ times before returning it, so none can beat this method on *any* input by more than a factor depending only on $k$ (instance optimality). *Exactness thus costs only a constant factor over the biased shortcut*, e.g., for squaring, we prove that this factor is below $11$ on every input and tends to $8/3$ on large uniform inputs. Simulations match the predicted costs and output distributions. At temperature $1/2$ over a million equally likely outcomes, our Collision-map CFTP uses about 3,400 samples per output on average, whereas rejection needs about 2,100,000. All theorems are formally verified in Lean 4.