A successive-revelation variance bound for a uniform permutation

Let ${\mathcal{F}}_k$ reveal the first $k$ entries of $\pi$, and let $M_k$ be the average of $f$ over permutations agreeing with those entries. Thus $M_0=Ef$, $M_N=f$, and the average of $M_k$ conditional on ${\mathcal{F}}_{k-1}$ is $M_{k-1}$. For $j<k$, averaging $(M_j-M_{j-1})(M_k-M_{k-1})$ first over completions of the first $k-1$ entries gives zero. Expanding the square of $f-Ef={\sum }_k(M_k-M_{k-1})$ therefore gives $\mathrm{Var}(f)={\sum }_{k}E[(M_k-M_{k-1}{)}^2]$. All these conditional averages are finite sums.

Fix a prefix of length $k-1$ and put $q=N-k+1$. For each remaining image $a$, let $u_a$ be the average of $f$ over completions whose kth entry is $a$. The conditional variance of $M_k$ is $\frac{1}{2q^2}{\sum }_{a,b}(u_a-u_b{)}^2$. Choose a uniform completion $\pi$ of the prefix and independently choose $l$ uniformly from $\{k,\dots ,N\}$. Given $\pi (k)=a$, the image $b=\pi (l)$ is uniform among the $q$ remaining images. For fixed $a,b$, swapping position $k$ with the location of $b$ is a bijection from completions with kth image $a$ onto completions with kth image $b$. Hence $E[f(\pi )-f(\pi (k,l))\mid a,b,{\mathcal{F}}_{k-1}]=u_a-u_b$. By [F3], the conditional variance just displayed is at most $\frac{1}{2}E[(f(\pi )-f(\pi (k,l)){)}^2\mid {\mathcal{F}}_{k-1}]$.

Average step 2.1 over prefixes and sum over $k$ using step 1.1. The independent uniform choice of $l$ gives the displayed estimate. If every squared difference has expectation at most $b$, each inner average is at most $b$, so the sum is at most $Nb\mathrm{/}2$. For $N=1$ both sides of the displayed estimate are zero.