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
Tags
Math
Related
Applying the Binomial Formula for One Head in Three Flips
A factory manufactures light bulbs with a 5% defect rate, where the status of each bulb is independent of the others. A quality control inspector randomly selects a sample of 20 bulbs. Which of the following expressions correctly represents the probability that exactly 3 of the sampled bulbs are defective?
Free-Throw Probability Analysis
Evaluating a Statistical Model for Card Draws
Learn After
Related
Applying the Binomial Formula for One Head in Three Flips
A factory manufactures light bulbs with a 5% defect rate, where the status of each bulb is independent of the others. A quality control inspector randomly selects a sample of 20 bulbs. Which of the following expressions correctly represents the probability that exactly 3 of the sampled bulbs are defective?
Free-Throw Probability Analysis
Evaluating a Statistical Model for Card Draws