Concept icon
Concept

Applying Hoeffding to the exceptional swap directions

For W equal to the sum of Q independent zero-one trials with the same success probability p, Hoeffding gives Pr(|W-Qp|>=a)<=2*exp(-2a^2/Q), for a>0. This is a standard concentration inequality invoked here, not proved by the example. Because the selected interval contains all integer levels within R/4 of the mean, its outside probability is at most 2*exp(-R^2/(8Q)). The random choices here count basis directions uniformly. They are not independent values for the repeated original variables in auxiliary copies. The latter still share their original bits.

0

1

Concept icon
Updated 2026-11-07

Contributors are:

Who are from:

Tags

Math