Concentration for Random Permutations by Exposure

Exposing a Random Permutation One Value at a Time

A statistic of a random permutation often depends on all \(n\) assignments, so its distribution can be difficult to calculate directly. Instead, reveal the permutation sequentially and track the conditional expectation of the statistic after each revelation. These conditional expectations form a martingale. If changing two assigned values cannot change the statistic very much, then the martingale increments are bounded, and Azuma-Hoeffding gives a deviation bound.

Fix an integer \(n\ge1\). Take \(\Omega\) to be the set of all permutations of \(\{1,\ldots,n\}\), let \(\mathcal{F}\) be its power set, and give each permutation probability \(1/n!\). Write \(\Pi(i)\) for the value assigned to position \(i\), so \(\Pi\) is uniform on these \(n!\) possibilities. Let \(F= f(\Pi)\) be a real-valued statistic. For \(0\le k\le n\), let \(\mathcal{F}_k=\sigma(\Pi(1),\ldots,\Pi(k))\), with \(\mathcal{F}_0=\{\varnothing,\Omega\}\), and define \(M_k=\mathbb{E}[F\mid\mathcal{F}_k]\). Thus \((M_k)_{k=0}^n\) is a real-valued process with time indices \(0,\ldots,n\), on this probability space, with state space \(\mathbb{R}\) and filtration \((\mathcal{F}_k)\).

The key point is that the unexposed assignments are not independent draws. Given the first \(k\) values, the remaining values are assigned uniformly over the remaining positions. The proof below uses this conditional uniformity directly.

The Exposure Increment Bound

Proof. Fix \(k\) and a possible history \(\Pi(1),\ldots,\Pi(k-1)\). Let \(R\) be the set of values not yet revealed. For each \(a\in R\), let \(g(a)\) be the conditional expectation of \(f(\Pi)\) given this history and \(\Pi(k)=a\). We first show that \(|g(a)-g(b)|\le L\) for any \(a,b\in R\). If \(a=b\), this difference is zero. If \(a\ne b\), pair every completion with \(\Pi(k)=a\) to a completion with \(\Pi(k)=b\) as follows: locate the position \(r\) holding \(b\) in the first completion, then exchange the values at positions \(k\) and \(r\). This gives a bijection between the completions in the two conditional sets, because the same exchange reverses the map. Corresponding completions differ by one transposition, so their \(f\)-values differ by at most \(L\). Averaging over the paired completions gives \(|g(a)-g(b)|\le L\).

Given the fixed history, each value in \(R\) is equally likely to be \(\Pi(k)\). Consequently \(M_{k-1}\) is the average of the numbers \(g(a)\), \(a\in R\), while \(M_k=g(\Pi(k))\). All these numbers lie in an interval of length at most \(L\), by the pairwise bound just proved. A number in that interval differs from their average by at most \(L\). Hence \(|M_k-M_{k-1}|\le L\). The history and \(k\) were arbitrary, so the bound holds almost surely for every increment. \(\square\)

This argument also explains why an exposure martingale is useful: its increment bound comes from comparing conditional expectations across possible next revelations, rather than trying to compute the full distribution of \(F\).

Indeed, \(M_0=\mathbb{E}f(\Pi)\) and \(M_n=f(\Pi)\). The stated bound follows by applying the Azuma-Hoeffding inequality for martingale differences with deterministic bounds \(c_k\), a standard result established in the earlier material on Azuma-Hoeffding inequalities. When all bounds equal \(L\), \(\sum_{k=1}^n c_k^2=nL^2\). If this sum is zero, nonnegativity implies every \(c_k=0\); the increment bounds then give \(M_k=M_{k-1}\) almost surely at every step. This handles constant statistics and avoids an undefined denominator.

For any \(n\ge1\), exchanging two assigned values can change fixed-point status only at the two affected positions. Each of their indicators changes by at most 1, so the fixed-point count has sensitivity at most 2. The theorem therefore gives, for \(t>0\), $$ \mathbb{P}\bigl(|F-1|\ge t\bigr)\le 2\exp\left(-\frac{t^2}{8n}\right). $$ Here \(\mathbb{E}F=1\), since each of the \(n\) positions has probability \(1/n\) of receiving its own value. For example, with \(n=10\) and \(t=8\), the bound is \(2\exp(-64/80)=2e^{-4/5}\). This is a valid upper bound even if a particular choice of threshold makes it uninformative; a probability bound can always also be replaced by its minimum with 1.

Common Mistake: Treating the Remaining Values as Independent

After one value has been revealed, the remaining values are sampled without replacement. For example, in the fixed-point calculation with \(n=4\) and \(\Pi(1)=2\), position 2 cannot be fixed, since value 2 has already been used. The correct conditional expectation is \(0+0+1/3+1/3=2/3\). Counting position 2 as having probability \(1/3\) of being fixed would give the incorrect value \(1\). After \(\Pi(2)=1\) is also revealed, positions 3 and 4 each have probability \(1/2\), not 1, of receiving their own value: the two remaining values have not yet been assigned to those positions. Their combined expected contribution is 1.

A second error is to use the sensitivity bound as though it were a bound on the total deviation. The theorem bounds each martingale increment; the tail estimate depends on the sum of the squared increment bounds. With \(n\) increments bounded by \(L\), that sum is \(nL^2\), not \(L^2\). If all increment bounds are zero, do not substitute into a formula with a zero denominator: the martingale is constant and every positive-threshold deviation event has probability zero.

The method applies whenever a statistic is defined on a uniform permutation and a transposition sensitivity bound can be established. The conditional-expectation martingale handles the dependence created by sampling without replacement, while the sensitivity calculation supplies the quantitative control needed for concentration.