Three Noises for the Argmax
9 min read
We often want to favor candidates with higher scores while still giving the others a chance. One way is to add independent random noise to each score and choose whichever is largest afterward.
Some familiar noise distributions give surprisingly simple formulas for the chance that each candidate wins. Those probabilities let us see exactly how the choice of noise affects the selection.
The Common Calculation
Write the \(n\) candidate scores as \(s_1,\ldots,s_n\) and their independent continuous noise draws as \(Z_1,\ldots,Z_n\). The selected candidate is:
\[ \arg\max_i\{s_i+Z_i\}. \]
Assume every noise draw has the same density \(f\) and cumulative distribution function \(F\), where \(F(t)\) is the probability that a draw is at most \(t\). Fix candidate \(i\) and condition on its noise taking the value \(t\). It wins when every rival’s noisy score falls below \(s_i+t\):
\[\begin{align} \Pr(i\text{ wins}\mid Z_i=t) &=\Pr(s_j+Z_j<s_i+t\text{ for every }j\ne i) \\ &=\Pr(Z_j<t+s_i-s_j\text{ for every }j\ne i) \\ &=\prod_{j\ne i}F(t+s_i-s_j). \end{align}\]
The first line states the event that candidate \(i\) beats every rival. The second isolates each rival’s noise, and the third uses independence. Now average over candidate \(i\)’s own noise:
\[ \Pr(i\text{ wins}) = \int_{-\infty}^{\infty} f(t)\prod_{j\ne i}F(t+s_i-s_j)\,dt. \]
The density \(f(t)\) weights candidate \(i\)’s possible perturbations, and each factor in the product is the chance of clearing one rival. The scores enter only through pairwise gaps.
If the noise has scale \(b>0\), we can use unit-scale noise and divide every score by \(b\):
\[ \arg\max_i\{s_i+bZ_i\} = \arg\max_i\{s_i/b+Z_i\}. \]
Thus the meaningful quantity is a score gap divided by the noise scale. We will work at unit scale first and restore \(b\) when comparing the three distributions. The noise enters the integral only through \(F\) and \(f\), so each of the next three sections substitutes one distribution and simplifies the product: Gumbel collapses it to a softmax, exponential noise to permute-and-flip, and Laplace to neither.
The diagram compares the three noise distributions inside this common calculation:
For two candidates, let \(g\geq0\) be their score gap. At the same noise scale \(b\), the exact probabilities are:
| Noise | Probability that the candidate lower by \(g\) wins |
|---|---|
| Gumbel | \(1/(1+e^{g/b})\) |
| Exponential | \(\tfrac12e^{-g/b}\) |
| Laplace | \(\tfrac14(g/b+2)e^{-g/b}\) |
The plot shows these three formulas over the same normalized score gap. Equal scale does not make the winner distributions interchangeable.
Gumbel: Shifts Become Powers
A standard Gumbel variable has cumulative distribution function and density:
\[ F(t)=e^{-e^{-t}}, \qquad f(t)=e^{-t}F(t). \]
In the plot, increasing the scale lowers the peak and stretches the longer right tail while the mode stays at zero.
Claim: with standard Gumbel noise, the winner follows the softmax distribution of the scores:
\[ \Pr(i\text{ wins}) = \frac{e^{s_i}}{\sum_j e^{s_j}}. \]
Proof
The relevant property of the Gumbel cumulative distribution function is that a shift of the input becomes a power. For any real number \(c\):
\[\begin{align} F(t+c) &=e^{-e^{-(t+c)}} \\ &=e^{-e^{-c}e^{-t}} \\ &=F(t)^{e^{-c}}. \end{align}\]
The first line substitutes the Gumbel formula, the second separates the shift from \(t\), and the third recognizes the original cumulative distribution function. For rival \(j\), set \(c=s_i-s_j\):
\[ F(t+s_i-s_j) = F(t)^{e^{s_j-s_i}}. \]
Every rival therefore contributes a power of the same number \(F(t)\). Substitute this identity into the common winner formula:
\[\begin{align} \Pr(i\text{ wins}) &=\int_{-\infty}^{\infty} e^{-t}F(t) \prod_{j\ne i}F(t)^{e^{s_j-s_i}}\,dt \\ &=\int_{-\infty}^{\infty} e^{-t}F(t)^{\sum_j e^{s_j-s_i}}\,dt \\ &=\int_{-\infty}^{\infty} e^{-t}\exp\!\left(-e^{-t}\sum_j e^{s_j-s_i}\right)\,dt \\ &=\int_0^\infty \exp\!\left(-u\sum_j e^{s_j-s_i}\right)\,du \\ &=\frac{1}{\sum_j e^{s_j-s_i}} \\ &=\frac{e^{s_i}}{\sum_j e^{s_j}}. \end{align}\]
The first line inserts the Gumbel density and the shifted cumulative distribution functions. The second combines their powers, including the factor \(F(t)\) as the missing \(j=i\) term. The third expands \(F(t)\), the fourth substitutes \(u=e^{-t}\), and the fifth integrates an exponential density. The last line multiplies numerator and denominator by \(e^{s_i}\).
At noise scale \(b\), the same calculation replaces every score by \(s_i/b\). Large \(b\) flattens the softmax, while small \(b\) concentrates it on the highest score.
There is another way to see the same identity. If \(Z_i\) is standard Gumbel, then \(e^{-Z_i}\) is a standard exponential variable, and maximizing \(s_i+Z_i\) is equivalent to minimizing \(e^{-Z_i}/e^{s_i}\). These are independent exponential variables with rates \(e^{s_i}\). The exponential minimum identity gives probability \(e^{s_i}/\sum_j e^{s_j}\) that the minimum occurs at \(i\).
Yellott [Yellott, JMP ’77] proved that this behavior characterizes Gumbel noise. With at least three candidates, an independent additive-noise model follows the softmax for every score vector only when the noise is Gumbel, up to location and scale.
Exponential: A Boundary and Memorylessness
A standard exponential variable is nonnegative. Its cumulative distribution function and density are:
\[ F(t)= \begin{cases} 0,&t<0,\\ 1-e^{-t},&t\geq0, \end{cases} \qquad f(t)=e^{-t}\mathbf{1}[t\geq0]. \]
In the plot, the support boundary remains fixed at zero as the scale stretches the right tail.
The zero in the first branch changes the common integral. Candidate \(i\) has no chance to win unless its own noise reaches at least the gap between its score and the best score. Consequently, its winner probability is:
\[ \Pr(i\text{ wins}) = \int_{\max_j s_j-s_i}^{\infty} e^{-t}\prod_{j\ne i} \left(1-e^{-(t+s_i-s_j)}\right)\,dt. \]
The lower limit is the first value of \(t\) for which every cumulative distribution factor is nonzero. Unlike the Gumbel case, shifts do not turn the factors into powers of one shared function, so the product does not reduce to a softmax.
With two candidates we can evaluate the result directly. Suppose candidate 1 leads candidate 2 by \(g\geq0\). Candidate 2 wins when \(Z_2-Z_1>g\), so:
\[\begin{align} \Pr(\text{candidate 2 wins}) &=\int_0^\infty \Pr(Z_2>g+t)e^{-t}\,dt \\ &=\int_0^\infty e^{-(g+t)}e^{-t}\,dt \\ &=\frac12e^{-g}. \end{align}\]
The first line conditions on \(Z_1=t\), the second uses the exponential tail, and the third evaluates the integral. At the same unit scale, Gumbel noise gives the lower-scoring candidate probability \(1/(1+e^g)\). Their ratio is:
\[ \frac{\tfrac12e^{-g}}{1/(1+e^g)} = \frac{1+e^{-g}}{2}. \]
It equals one when the scores tie and approaches one half as the gap grows. This comparison concerns the probability of selecting the lower score in the two-candidate case.
Exponential noise also has the memoryless property. Conditional on exceeding a threshold, the amount by which it exceeds that threshold is a fresh exponential variable. That property identifies its noisy argmax with permute-and-flip, introduced by McKenna & Sheldon [MS, NeurIPS ’20].
Claim: Exponential noisy argmax with scale \(b\) has the same output distribution as permute-and-flip with coin probabilities \(e^{s_i/b}\) after shifting the best score to zero.
Proof
Subtract the best score from every score, so that \(\max_i s_i=0\). This shift does not change the argmax.
Let \(Z_i\) be the exponential noise of scale \(b\) added to candidate \(i\). Collect the candidates whose noisy scores cross zero:
\[ S=\{i:s_i+Z_i\geq0\}. \]
Candidate \(i\) enters \(S\) independently with probability:
\[\begin{align} \Pr(i\in S) &=\Pr(Z_i\geq-s_i) \\ &=e^{s_i/b}. \end{align}\]
The best candidate enters with probability one, so \(S\) is never empty. Conditional on \(i\in S\), memorylessness says that the excess \(s_i+Z_i\) is a fresh exponential variable of scale \(b\). The excesses are independent and identically distributed across \(S\), so their maximum is uniform over the candidates in \(S\).
Permute-and-flip independently marks candidate \(i\) with probability \(e^{s_i/b}\), visits the candidates in a uniform random order, and returns the first marked candidate. It creates the same random set \(S\). Conditional on \(S\), the first marked candidate in a uniform permutation is also uniform over \(S\). The two selectors agree conditional on every possible \(S\), so their output distributions agree.
Ding, Kifer, Saghaian, Steinke, Wang, Xiao & Zhang [DK+, ’21] proved this equivalence for any number of candidates.
The two-candidate calculation extends to a stronger comparison. If a selector returns candidate \(i\), define its regret as the score lost relative to the maximum:
\[ R=\max_j s_j-s_i. \]
McKenna & Sheldon’s Theorem 2 states that, at the same scale and for every threshold \(t\geq0\):
\[ \Pr(R^{\mathrm{exp}}\geq t) \leq \Pr(R^{\mathrm{Gum}}\geq t). \]
Here the superscripts denote exponential and Gumbel noise. This is the precise sense in which exponential noise does no worse: it is no more likely to lose at least \(t\) score units, for any \(t\). Integrating the tail probabilities also gives no larger expected regret.
Laplace: Two Exponential Tails
Laplace noise combines an exponential tail on each side of zero. A standard Laplace variable is symmetric, with density:
\[ f(t)=\frac12e^{-|t|}. \]
In the plot, increasing the scale lowers the central peak and stretches both tails by the same amount.
Its right tail resembles the exponential distribution, but it can also be negative. This removes the exponential distribution’s hard boundary and its memoryless threshold construction. It also lacks Gumbel’s shift-to-power identity, so the common winner integral has no comparable collapse.
Again take two candidates separated by a gap \(g\geq0\). The lower score wins when the difference of two independent Laplace variables exceeds \(g\). Its winning probability is:
\[ \Pr(\text{candidate 2 wins})=\frac14(g+2)e^{-g}. \]
Deriving the Laplace probability
For \(t\geq0\), the density of that difference is the convolution:
\[\begin{align} f_{Z_2-Z_1}(t) &=\frac14\int_{-\infty}^{\infty} e^{-|z|-|z+t|}\,dz \\ &=\frac14\left( \int_{-\infty}^{-t}e^{2z+t}\,dz +\int_{-t}^{0}e^{-t}\,dz +\int_0^\infty e^{-2z-t}\,dz \right) \\ &=\frac14\left( \frac12e^{-t}+te^{-t}+\frac12e^{-t} \right) \\ &=\frac14(t+1)e^{-t}. \end{align}\]
The second line splits the real line where the two absolute values change sign. The three pieces correspond to both noises being on the left, on opposite sides, and both being on the right. Integrating this density above the score gap gives the lower candidate’s chance of winning:
\[\begin{align} \Pr(\text{candidate 2 wins}) &=\int_g^\infty\frac14(t+1)e^{-t}\,dt \\ &=\frac14(g+2)e^{-g}. \end{align}\]
The extra factor \(g+2\) comes from Laplace’s two-sided support. An exponential variable can clear the score gap only by giving the lower candidate a large positive draw. With Laplace noise, a large positive draw for the lower candidate and a negative draw for the leader can share that work.
A Short Privacy Connection
These probability identities also give three mechanisms for differentially private selection. Let one person’s data change each score by at most \(\Delta\), and let \(\varepsilon>0\) be the privacy budget.
Gumbel noise of scale \(2\Delta/\varepsilon\) gives the exponential mechanism of McSherry & Talwar [MT, FOCS ’07], because the softmax weights become \(e^{\varepsilon s_i/(2\Delta)}\). Exponential noise at the same scale gives permute-and-flip. Both selectors are \(\varepsilon\)-differentially private for arbitrary sensitivity-\(\Delta\) scores.
Laplace noise of scale \(2\Delta/\varepsilon\) gives the usual report-noisy-max guarantee for arbitrary scores. For monotone scores such as counts, adding one record moves every score in \([0,\Delta]\) rather than in \([-\Delta,\Delta]\). Dwork & Roth’s Claim 3.9 [DR, ’14] then reduces the sufficient Laplace scale to \(\Delta/\varepsilon\).
“Half the noise” means half the scale parameter, and only under the monotonicity assumption. The distributions have different shapes, so the statement does not imply half the variance or half the expected regret.